RSA

RSA ist ein von Ron Rivest, Adi Shamir, Leonard Adleman entwickeltes asymmetrisches Public-Key-Verfahren. Es überstand eine jahrelange Kryptoanalyse und wird heute als Standardverfahren von fast allen gängigen Verschlüsselungssystemen eingesetzt.

Wie das Verfahren funktioniert, soll am folgenden Beispiel gezeigt werden:

Primzahlen: p, q p = 47 q = 71

Öffentlicher Schlüssel:

n = pq n = 47 * 71 = 3337

e - CS zufällig gewählt e = 79

! prim zu (p-1)(q-1) 46 * 70 = 3220

Privater Schlüssel:

d = DCS

d = e¹ mod ((p-1)(q-1)) d = 79¹ mod 3220 = 1019

d wird mit dem erweiterten Euklidischen Algorithmus (siehe unten) berechnet,

p und q werden nicht mehr benötigt, dürfen aber niemals bekanntgegeben werden

Verschlüsselung:

M = Nachricht M = 6882326879666683

Blöcke Þ m= 668; m= 232; m= 687

m= 966; m= 668; m= 003

ci = mie mod n c= 688 mod 3337 = 1570

C = c+ c+...+c C = 1570 2756 2096 2276 2423 158

Entschlüsselung:

mi = cid mod n m= 1570¹¹ mod 3337 = 688

Erweiterter euklidischer Algorithmus

Ziel: Bestimmung von d

1. Schritt: Bestimmung des ggT [e, (p-1)(q-1)]

ges.: d geg.: e = 79;

(p-1)(q-1) = 3220

Lsg.: 1 = ed mod (p-1)(q-1) 1 = 79 d mod 3220

3220 = 79 * 40 + 60

79 = 60 * 1 + 19

60 = 19 * 3 + 3

19 = 3 * 6 + 1 ggT = 1

3 = 3 * 1 + 0

2. Schritt: Gleichungskette von unten auflösen

1 = 19 – 3 * 6 die 3 aus 3. Zeile einsetzen 3 = 60 – 19 * 3

1 = 19 - [ ( 60 – 19 * 3 ) * 6 ]

1 = 19 * 19 – 60 * 6

1 = 19 ( 79 – 60 ) – 60 * 6

1 = 19 * 79 – 60 * 25

1 = 19 * 79 – ( 3220 – 79 * 40 ) * 25

1 = 19 * 79 – 3220 * 25 + 79 * 40 * 25 ( 79 zusammenfassen )

1 = 79 ( 19 – 3220 * 25 / 79 + 40 * 25 ) 79 ( 19 – 3220 * 25 / 79 + 1000 )

1 = 79 * 1019 – 3220 * 25

79 * 1019 mod 3220 = 1

d = 1019