<< . .

. 15
( : 33)



. . >>



Geheimtextmenge C = Z n .


Schlüsselmenge K = {e ∈ N ; ggT(e, •(n)) = 1} (oft erw¤hnt man auch n

in der Schlüsselmenge, d. h. K = {(n, e) ∈ N — N ; ggT(e, •(n)) = 1}).

Verschlüsselungsfunktionen f e mit e ∈ K de¬niert durch f e (N ) = N e für

N ∈ P.

Entschlüsselungsfunktionen f d mit d ∈ K de¬niert durch f d (C) = C d für

C ∈ C, wobei
e d ≡ 1 (mod •(n)) .
7.1 Das Verfahren von Rivest, Shamir und Adleman 113

Dabei wird d mit dem euklidischen Algorithmus (siehe Satz 4.10) zu e ∈ K be-
stimmt.
In Lemma 7.1 zeigen wir, dass das Verfahren funktioniert, d. h. dass das Ent-
schlüsseln eines verschlüsselten Klartextes N wieder den Klartext N liefert:

f d ( f e (N )) = f d (N e ) = N e d = N .


Bemerkung
Die Zahlen n = p q und e sind öffentlich bekannt. Einem Angreifer darf die Zahl
•(n) = (p ’ 1) (q ’ 1) (siehe das Beispiel auf Seite 75) nicht bekannt sein, er
kann sonst ebenso wie der Empf¤nger mithilfe des euklidischen Algorithmus den
geheimen Schlüssel d ermitteln.
W¤hlt man für die Zahlen p und q große Primzahlen, so ist es im Allgemeinen
schwierig, aus der Kenntnis von n = p q die Primfaktoren p und q und damit
•(n) = (p ’ 1) (q ’ 1) zu ermitteln. In der Praxis werden die Primzahlen p und
q von der Größenordnung 512 Bit gew¤hlt. Bei der Wahl der Primzahlen p und
q sind noch weitere Aspekte zu berücksichtigen, auf die wir in Abschnitt 7.4.1
eingehen werden.

Man beachte, dass die Voraussetzungen des folgenden Lemmas genau die Situa-
tion im RSA-Kryptosystem wiedergeben:

Lemma 7.1
Es seien p = q Primzahlen, n = p q, d, e ∈ N mit ggT(e, •(n)) = 1, e d ≡
1 (mod •(n)) und a ∈ Z. Dann gilt aed ≡ a (mod n).

Beweis. Wegen e d ≡ 1 (mod •(n)) existiert ein r ∈ Z mit e d = 1 + r •(n) =
1 + r (p ’ 1) (q ’ 1). Nach dem Satz 6.10 von Fermat gelten die folgenden Kon-
gruenzen:

aed ≡ a1+r(p’1)(q’1) ≡ a (a p’1 )r(q’1) ≡ a (mod p) ,
aed ≡ a1+r(p’1)(q’1) ≡ a (aq’1 )r(p’1) ≡ a (mod q) .

Die erste Kongruenz besagt p | aed ’ a, die zweite q | aed ’ a. Da p und q verschie-
dene Primzahlen sind, gilt somit auch p q | aed ’ a, d. h. aed ≡ a (mod n).

Die Kongruenz aed ≡ a (mod n) bedeutet aber nichts anders als die Gleichheit
aed = a in Z n . Damit folgt aus Lemma 7.1 die Korrektheit des RSA-Verfahrens:
Der Empf¤nger R erh¤lt den Geheimtext C = N e ∈ Z n und berechnet mit seinem
geheimen Schlüssel d durch Potenzieren den Klartext:

C d = N ed = N ∈ Z n .
114 7 Das RSA-Verfahren

7.1.2 Die Schlüsselerzeugung
Beim RSA-Verfahren sind die beiden Zahlen n und e öffentlich bekannt. Wir
fassen von nun an die beiden Zahlen zum öffentlichen Schlüssel (n, e) zusam-
men. Wir schildern die Schlüsselerzeugung, also die Erzeugung des öffentlichen
Schlüssels (n, e) und des geheimen Schlüssels d durch den Empf¤nger R:
R w¤hlt zwei Primzahlen p = q.
R berechnet n := p q, •(n) = (p ’ 1) (q ’ 1) (siehe das Beispiel auf Seite 75).
R w¤hlt ein e ∈ N mit 1 < e < •(n) und ggT(e, •(n)) = 1.
R berechnet d ∈ N mit e d ≡ 1 (mod •(n)).
Es sind dann (n, e) der öffentliche Schlüssel von R und d der geheime Schlüssel
von R. Es sind auch die Größen p, q, •(n) geheim zu halten. Ist n¤mlich einem
Angreifer eine dieser drei Größen bekannt, so kann er d berechnen.

7.1.3 Die Verschlüsselung
Die Erzeugung des Geheimtextes C aus dem Klartext N ist einfach: Der Sender
S besorgt sich den öffentlichen Schlüssel (n, e) des Empf¤ngers R und geht wie
folgt vor:
S codiert seine Nachricht in den Klartext N ∈ Z n .
S berechnet den Geheimtext C := N e ∈ Z n .
S sendet den Geheimtext C an R.


7.1.4 Die Entschlüsselung
Die Entschlüsselung
C ’ Cd = N
mit dem geheimen Schlüssel d klappt wegen Lemma 7.1.

Beispiel
Es seien p = 7 und q = 11. Dann gilt n = 77, •(n) = 6 · 10 = 60. Die Wahl e = 13
erfüllt ggT(e, 60) = 1. Damit hat R den öffentlichen Schlüssel (n, e) = (77, 13).
Mit dem euklidischen Algorithmus berechnet R seinen geheimen Schlüssel d:

1 ≡ 37 · 13 (mod 60) ,

sodass d = 37.
Nun will S an R die Nachricht N = 7 ∈ Z77 senden. Dazu besorgt sich S den
öffentlichen Schlüssel (n, e) = (77, 13) und verschlüsselt N = 7 zu
13
C = Ne = 7 = 35 .
7.1 Das Verfahren von Rivest, Shamir und Adleman 115

Der Geheimtext C = 35 ∈ Z77 wird an R gesandt. Dieser entschlüsselt den Ge-
heimtext mit seinem geheimen Schlüssel d = 37:

37
C d = 35 =7

und erh¤lt so den Klartext N = 7 ∈ Z77 zurück. Es ist bemerkenswert, dass das
funktioniert, obwohl N = 7 in Z77 nicht invertierbar ist.



7.1.5 Hybridverfahren

Der Rechenaufwand beim RSA-Verfahren ist im Allgemeinen um ein Vielfaches
höher als der bei einem symmetrischen Verfahren. Wir werden weitere Public-
Key-Verfahren kennenlernen, aber auch diese sind erheblich teurer als die sym-
metrischen Verfahren. Mithilfe eines einfachen Tricks kann durch ein Public-Key-
Verfahren ein ef¬zienteres symmetrisches Verfahren genutzt werden. Wir gehen
von folgender Situation aus. S will an R eine Nachricht N senden. Der öffentliche
Schlüssel von R sei (n, e).

S verschlüsselt einen Klartext N mit einem symmetrischen Verfahren zu ei-
nem Geheimtext C.

Den Schlüssel k zum Entschlüsseln dieser Nachricht C verschlüsselt S (nach
einer passenden Codierung) mit dem öffentlichen Schlüssel (n, e) des Emp-
f¤ngers R zu k .

S sendet das Paar (C, k ) an den Empf¤nger R.

R entschlüsselt k mit seinem geheimen Schlüssel des Public-Key-Verfahrens
und erh¤lt den Schlüssel k.

R benutzt dann k, um aus C den Klartext N zu erhalten.

Solche Verfahren werden Hybridverfahren genannt, weil sie die Vorteile der
symmetrischen mit den Vorteilen der asymmetrischen Kryptogra¬e verbinden.

Bemerkung
Der im Allgemeinen höhere Rechenaufwand eines Public-Key-Verfahrens ist hier
auf das Ver- und Entschlüsseln eines Schlüssels, also einer meist sehr kurzen Se-
quenz, beschr¤nkt. Bei AES etwa, das h¤u¬g mit RSA gekoppelt wird, liegt die
Schlüssell¤nge zwischen 128 und 256 Bit.
Eine andere Methode, einen Schlüssel über einen unsicheren Kanal auszutau-
schen, um dann mit einem symmetrischen Verfahren kommunizieren zu können,
ist der Dif¬e-Hellman-Schlüsselaustausch. Darauf gehen wir in Kapitel 9 ein.
116 7 Das RSA-Verfahren

7.1.6 Zur Sicherheit von RSA
Wir versetzen uns nun die Lage eines Angreifers A:
C=N e

!
(n,e)
S R

A

Ein Angreifer A, dem ein Geheimtext C ∈ Z n des Senders S an den Empf¤nger
R in die H¤nde ger¤t, erh¤lt den Klartext N durch Lösen eines der folgenden
Probleme:
• Bestimme den geheimen Schlüssel d, d. h. die Lösungsmenge der Kongru-
enzgleichung:
e X ≡ 1 (mod •(n)) .
Dazu muss der Angreifer •(n) kennen.

Bestimme die e-te Wurzel aus C in Z n , d. h. die Lösung N ∈ Z n der Glei-

chung
Xe = C .

Die Lösung der Gleichung X e = C ist auch tats¤chlich eindeutig bestimmt, da der
Homomorphismus ι e : Z n ’ Z n , a ’ ae wegen Lemma 7.1 bijektiv ist, die Po-
tenzabbildung ι d ist das Inverse zu ι e . Damit ist das Ziehen der e-ten Wurzel das
Potenzieren mit d. Folglich sind die beiden geschilderten Probleme, vor denen
der Angreifer steht, ein und dasselbe Problem.
Beim RSA-Verfahren sind, wie bereits erw¤hnt, neben dem geheimen Schlüssel
d auch die Größen p, q und •(n) geheim zu halten, da ein Angreifer mit einer
dieser drei Größen aus dem öffentlichen Schlüssel (n, e) den geheimen Schlüssel
d ermitteln kann. Wir zeigen nun, dass man mit der Kenntnis von •(n) die Prim-
teiler p und q von n ermitteln kann. Es sind n¤mlich p und q die zwei Nullstellen
eines Polynoms vom Grad 2 mit Koef¬zienten, die von n und •(n) abh¤ngen,
und die Nullstellen eines Polynoms vom Grad 2 sind einfach zu bestimmen.

Lemma 7.2
Aus n und •(n) können p und q als Nullstellen des Polynoms

f = X 2 ’ (n ’ •(n) + 1) X + n

bestimmt werden.

Beweis. Sind n und •(n) bekannt, so kann das Polynom

f = X 2 ’ (n ’ •(n) + 1) X + n ∈ Z[X]
7.2 Der chinesische Restsatz 117

aufgestellt werden. Und wegen n ’ •(n) = p q ’ (p ’ 1) (q ’ 1) = p + q ’ 1 gilt:
(X ’ p) (X ’ q) = X 2 ’ (p + q) X + p q = X 2 ’ (n ’ •(n) + 1) X + n .
Damit sind die Nullstellen von f die Primzahlen p und q.

Bemerkung
Kann man n in seine Primfaktoren n = p q zerlegen, so kann man •(n) =
(p ’ 1) (q ’ 1) berechnen. Und kann man umgekehrt •(n) aus n berechnen, so
kann man nach Lemma 7.2 die Zahl n in ihre Primfaktoren zerlegen. Die beiden
Probleme, n zu faktorisieren und •(n) zu bestimmen, sind also algorithmisch
¤quivalent.


7.2 Der chinesische Restsatz

Um weitere Fragen zur Sicherheit des RSA-Verfahrens kl¤ren zu können, brau-
chen wir den sogenannten chinesischen Restsatz aus der Zahlentheorie. Dieser
Satz liefert ein Verfahren, ef¬zient Systeme von Kongruenzgleichungen zu lö-
sen. Damit können durch RSA verschlüsselte Geheimtexte unter gewissen Vor-
aussetzungen gebrochen werden. Wir leiten in einem ersten Abschnitt den chi-
nesischen Restsatz her und ziehen dann wichtige Folgerungen für die Euler™sche
•-Funktion.


7.2.1 Der chinesische Restsatz

Es ist klar, dass das kartesische Produkt R = R1 — · · · — Rn von Ringen R1 , . . . , Rn
mit den komponentenweisen Verknüpfungen
(a1 , . . . , an ) + (b1 , . . . , bn ) = (a1 + b1 , . . . , an + bn ) und
(a1 , . . . , an ) · (b1 , . . . , bn ) = (a1 b1 , . . . , an bn )
für (a1 , . . . , an ) , (b1 , . . . , bn ) ∈ R wieder einen Ring bildet.
Wir besch¤ftigen uns mit der umgekehrten Aufgabenstellung. Man gebe in dem
Ring (R, +, ·) Unterringe U1 , . . . , Un an, sodass R ∼ U1 — · · · — Un gilt. Wir füh-
=
ren eine solche Zerlegung in ein direktes Produkt für den Ring (Z m , +, ·), m ∈ N,
durch.

Lemma 7.3
Für paarweise teilerfremde r1 , . . . , rn ∈ Z ist
’ Z r1 — · · · — Z r n
Zr1 ···rn
ψ:
k + r1 · · · r n Z ’ (k + r1 Z, . . . , k + rn Z)
ein Ringisomorphismus (d. h. bijektiv und ein additiver und multiplikativer Homomor-
phismus).
118 7 Das RSA-Verfahren

Beweis. Die Abbildung ψ ist wohlde¬niert und injektiv, da für r := r1 · · · rn gilt:

k + rZ = l + r Z ” r | l ’ k ” ri | l ’ k für alle i = 1, . . . , n
” k + ri Z = l + ri Z für alle i = 1, . . . , n
” ψ(k + r Z) = ψ(l + r Z) .

Wegen
n n
|Zr | = r = ∏ ri = ∏ |Zri | = |Zr1 — · · · — Zrn |
i=1 i=1
ist ψ auch surjektiv. Nach De¬nition der Verknüpfungen ist ψ additiv und multi-
plikativ.

Bemerkung
Die Wohlde¬niertheit ist die Umkehrung der Injektivit¤t.

Wir machen uns klar, was die Surjektivit¤t der Abbildung ψ in Lemma 7.3 besagt:
Zu beliebigen a1 , . . . , an ∈ Z gibt es ein x ∈ Z mit

x + r1 Z = a1 + r1 Z , . . . , x + r n Z = a n + r n Z

oder anders geschrieben

x ≡ a1 (mod r1 ) , . . . , x ≡ an (mod rn ) .

Dies besagt, dass man ein System von Kongruenzgleichungen zu teilerfremden
Moduln simultan lösen kann. Das war bereits Sun-Tsu im 1. Jahrhundert unserer
Zeitrechnung bekannt.

Satz 7.4 (Chinesischer Restsatz)
Sind r1 , . . . , rn ∈ Z paarweise teilerfremd, so existiert zu beliebigen a1 , . . . , an ∈ Z ein
x ∈ Z mit
x ≡ ai (mod ri ) für alle i = 1, . . . , n .

Man beachte, dass dies eine Existenzaussage ist. Es gibt ein solches x. Wir zeigen
nun, wie wir die Menge aller solchen x explizit bestimmen können.


7.2.2 Lösen eines Systems von Kongruenzgleichungen

Für das konstruktive Lösen eines Systems von Kongruenzgleichungen der Form

X ≡ a1 (mod r1 ) , . . . , X ≡ an (mod rn )

mit paarweise teilerfremden r1 , . . . , rn ∈ Z und beliebigen a1 , . . . , an ∈ Z beachte
man die folgenden Schritte:
7.2 Der chinesische Restsatz 119

Setze m := r1 · · · rn und si := für i = 1, . . . , n.
m
ri

Bestimme xi ∈ Z mit xi si ≡ 1 (mod ri ) für i = 1, . . . , n.
Es ist dann
x = x1 s1 a1 + · · · + x n s n a n
eine Lösung des obigen Systems von Kongruenzengleichungen, und die Lö-
sungsmenge ist x + m Z.
Die Begründung ist einfach: Satz 4.20 garantiert, dass solche xi existieren, da ri
und si für alle i = 1, . . . , n teilerfremd sind “ man kann also x1 , . . . , xn mit dem
euklidischen Algorithmus bestimmen.
Weil für i = j das Element ri ein Teiler von s j ist, ist das angegebene x tats¤chlich
eine Lösung der n Kongruenzgleichungen. Für jedes i = 1, . . . , n gilt n¤mlich
n
‘ x j s j a j ≡ xi si ai ≡ ai (mod ri ) .
x=
j=1

Ist y neben x eine weitere Lösung des Systems, so gilt

x ≡ y ≡ ai (mod ri ) für alle i = 1, . . . , n ’ ri | x ’ y für alle i = 1, . . . , n
’ m | x ’ y , d. h. x ≡ y (mod m) ,
folglich gilt y ∈ x + m Z. Andererseits ist jedes Element aus x + m Z Lösung des
Systems, sodass x + m Z die Lösungsmenge ist.

Beispiel
Gesucht ist die Lösungsmenge des Kongruenzensystems

X ≡ 2 (mod 5) , X ≡ 3 (mod 7) , X ≡ 2 (mod 4) .

Es ist also m = 140, s1 = 28, s2 = 20, s3 = 35.
Wir bestimmen nun x1 , x2 , x3 ∈ Z mit

28 x1 ≡ 1 (mod 5) , 20 x2 ≡ 1 (mod 7) , 35 x3 ≡ 1 (mod 4) .

Offenbar kann man x1 = 2, x2 = ’1, x3 = ’1 w¤hlen. Wenn dies nicht so
offensichtlich ist, wende man den euklidischen Algorithmus an. Damit haben wir
die Lösung:

x = 2 · 28 · 2 + (’1) · 20 · 3 + (’1) · 35 · 2 = ’18 .

Die Lösungsmenge lautet ’18 + 140 Z.

Bemerkung
Man erkennt, dass man nicht immer den kleinsten positiven Vertreter der Rest-
klasse ¬ndet. Ist das gewünscht, muss man noch eine Division mit Rest durch-
führen: ’18 + 140 Z = 122 + 140 Z.
120 7 Das RSA-Verfahren

7.2.3 Produktdarstellung der primen Restklassengruppen

Für die Abbildung ψ aus Lemma 7.3 und r := r1 · · · rn gilt
— —
ψ(k + r Z) ∈ Zr1 — · · · — Zrn ” ggT(k, ri ) = 1 für i = 1, . . . , n

” ggT(k, r) = 1 ” k + r Z ∈ Zr .

Somit ist die Einschr¤nkung ψ|Zr auf die (multiplikative) Gruppe Zr der inver-

tierbaren Elemente von Zr wegen Lemma 7.3 ein Gruppenisomorphismus von
— — —
Zr auf Zr1 — · · · — Zrn :

Lemma 7.5
(a) Für paarweise teilerfremde r1 , . . . , rn und r := r1 · · · rn ist

ψ|Zr : k + r1 · · · rn Z ’ (k + r1 Z, . . . , k + rn Z)


— — —
ein (multiplikativer) Isomorphismus von Zr1 ···rn auf Zr1 — · · · — Zrn .
ν
(b) Ist m = p11 · · · pνn die kanonische Primfaktorzerlegung von m > 1 aus N, so gilt
n

Z — ∼ Z —ν1 — · · · — Z —νn .
m= p
p1 n


Nach dem Fundamentalsatz 4.14 der Arithmetik kann jedes m ∈ N ≥2 als Produkt
von Primzahlpotenzen dargestellt werden:
ν
m = p11 · · · pνn .
n

Wegen Lemma 4.16 folgt für die Euler™sche •-Funktion (siehe Seite 75):
n n n n
1 1
ν ν
•(m) = |Z — | = ∏ |Z—νi | = ∏ •(pi i ) = ∏ pi i ∏
1’ =m 1’ .
m
pi pi
pi
i=1 i=1 i=1 i=1

Wir fassen zusammen:

Lemma 7.6
(a) Für paarweise teilerfremde s1 , . . . , sn ∈ N gilt

•(s1 · · · sn ) = •(s1 ) · · · •(sn ) .

(b) Sind p1 , . . . , pn die verschiedenen Primteiler von m > 1 aus N, so ist
1 1
•(m) = m 1’ ··· 1’ .
p1 pn

Beispiel
Es gilt etwa
1246
•(33) = •(3) •(11) = 20 , •(420) = 420 · · · · = 96 .
2357

<< . .

. 15
( : 33)



. . >>