<< . .

. 23
( : 33)



. . >>

∈ Z—
a p := a 4
p

eine Quadratwurzel des Quadrates a modulo p ist. Damit sind ±a p die beiden
(einzigen) Quadratwurzeln von a modulo p. Man erh¤lt die Wurzeln modulo
einer Primzahl p ≡ 3 (mod 4) somit durch einfaches Potenzieren. Das wird das
Rabin-Verfahren vereinfachen.


Bemerkung
Für Primzahlen p ≡ 5 (mod 8) kann man Quadratwurzeln ebenfalls relativ ein-
fach gewinnen. Im Fall p ≡ 1 (mod 8) gibt es spezialisierte Algorithmen, wie
etwa den von Tonelli und Shanks. Mehr dazu ist in [7, § 1.5] zu ¬nden.




9.3.3 Das Verfahren

Das Rabin-Verfahren ist ein Public-Key-Verfahren. Der Empf¤nger R gibt seinen
öffentlichen Schlüssel bekannt und beh¤lt sich einen geheimen Schlüssel.

Für die Schlüsselerzeugung geht R wie folgt vor:
Schlüsselerzeugung.

R w¤hlt zwei Primzahlen p und q mit p, q ≡ 3 (mod 4) und p = q.

Es ist n = p q der öffentliche Schlüssel.

Es ist (p, q) der geheime Schlüssel.

Der Teilnehmer T möchte an den Empf¤nger R eine Nachricht senden.

C=N 2

!
T R
n=p q
176 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Verschlüsselung. Der Teilnehmer T geht für die Chiffrierung seines Klartextes
N wie folgt vor:
T besorgt sich den öffentlichen Schlüssel n von R.
T stellt seinen Klartext N als Element von Z — dar, d. h. N ∈ Z — .
n n

T berechnet den Geheimtext C = N 2 in Z — .
n

T sendet C an R.
Man beachte, dass der Geheimtext C ∈ Z — wegen n = p q, p = q, nach Lemma
n
— hat. Der Klartext N ist eine dieser vier Wurzeln.
9.1 vier Quadratwurzeln in Z n
Die vier Quadratwurzeln b1 , . . . , b4 modulo n erh¤lt man mit dem chinesischen
Restsatz aus den Quadratwurzeln w1 , . . . , w4 modulo p und modulo q (vgl. die
Bemerkung auf Seite 174). Und die Quadratwurzeln modulo p und modulo q
sind einfach zu bestimmen, da p und q kongruent 3 modulo 4 sind.
Entschlüsselung. Der Empf¤nger R geht zur Entschlüsselung des von T erhal-
tenen Geheimtextes C wie folgt vor:
p+1 q+1
R berechnet a p = C 4 ∈ Z — und aq = C 4 ∈ Z — und erh¤lt mit ±a p und
p q
±aq die vier Quadratwurzeln von C modulo p und q.
R ermittelt mit dem chinesischen Restsatz aus den vier Quadratwurzeln ±a p
modulo p und ±aq modulo q von C die vier Quadratwurzeln b1 , . . . , b4 von C
modulo n (vgl. die Bemerkung zu Lemma 9.1):
(a p , aq ) ’ b1 , (a p , ’aq ) ’ b2 , (’a p , aq ) ’ b3 , (’a p , ’aq ) ’ b4 .

R entscheidet, welche der vier Wurzeln b1 , . . . , b4 der Klartext N ist.

Bemerkung
Die Entschlüsselung liefert neben einem richtigen drei falsche Ergebnisse. Das ist
ein entscheidender Nachteil des Rabin-Verfahrens. Man könnte die Entschlüsse-
lung eindeutig machen, indem man nur Klartexte mit einer bestimmten Struk-
tur zul¤sst. Aber dadurch würde dann das Rabin-Verfahren nicht mehr algorith-
misch ¤quivalent zum Faktorisierungsproblem sein (siehe Abschnitt 9.3.4).

Beispiel
Es seien p = 3 und q = 7. Damit ist n = 21 der öffentliche Schlüssel von R. Der

Teilnehmer T will an R die Nachricht N = 10 ∈ Z21 senden und berechnet dazu
2
C = 10 = 100 = 16 .
R erh¤lt von T den Geheimtext C = 16 und ermittelt mittels der (geheimen) Prim-
zahlen p = 3 und q = 7 die vier Quadratwurzeln von 16 modulo 21; es gilt:
p+1 q+1
— —
2
= 16 = 1 ∈ Z3 und 16 = 16 = 4 ∈ Z7 .
4 4
16
9.3 Das Rabin-Verschlüsselungsverfahren * 177

Es sind also

a3 = 1 und ’a3 = ’1 = 2 die Quadratwurzeln modulo 3 von 16 und


a7 = 4 und ’a7 = ’4 = 3 die Quadratwurzeln modulo 7 von 16.


Mit dem chinesischen Restsatz ermittelt man zu den vier Kombinationen

w1 = (1, 4) , w2 = (1, 3) , w3 = (2, 4) , w4 = (2, 3)

die vier Quadratwurzeln

b1 = 4 , b2 = 10 , b3 = 11 , b4 = 17 .

Der Klartext N ist also unter den vier Wurzeln 4, 10, 11, 17 zu suchen.

(p’1) (q’1)
Wir bemerken noch, dass es wegen Korollar 9.2 in Z —q mit p = q genau
p 4
Quadrate gibt, sodass die Geheimtextmenge umfangreich ist.

9.3.4 Zur Sicherheit des Rabin-Verfahrens

Ein Angreifer, der einen Geheimtext C ∈ Z — abgefangen hat, steht vor dem Pro-
n
blem, die Quadratwurzeln von C zu bestimmen. Kann er die Zahl n faktorisieren,
d. h. die Primzahlen p und q bestimmen, so kann er ebenso wie der rechtm¤ßige
Empf¤nger R den Geheimtext C entschlüsseln. Interessant ist, dass hiervon auch
die Umkehrung gilt.

Lemma 9.3
Es seien p und q verschiedene (ungerade) Primzahlen und n = p q. Kann man zu je-
dem Quadrat c modulo n eine Quadratwurzel a modulo n bestimmen, so kann man n
faktorisieren.

Beweis. Man w¤hle zuf¤llig eine Zahl x ∈ {1, . . . , n ’ 1}. Ohne Einschr¤nkung
gelte ggT(x, n) = 1. Zu c = x2 ∈ Z — bestimme man eine Quadratwurzel a mo-
n
dulo n mit a ∈ {1, . . . , n ’ 1}: Es ist a eine der vier Quadratwurzeln modulo n
von c, und es gilt

a2 = x2 ∈ Z — ’ p q = n | (a2 ’ x2 ) = (a ’ x) (a + x) .
n

Nun gibt es vier Möglichkeiten (beachte, dass |a ’ x| ∈ {0, . . . , n ’ 1}):

p | a ’ x , q | a ’ x ’ ggT(a ’ x, n) = n ,
p | a + x , q | a + x ’ ggT(a ’ x, n) = 1 ,
p | a ’ x , q | a + x ’ ggT(a ’ x, n) = p ,
p | a + x , q | a ’ x ’ ggT(a ’ x, n) = q .
178 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Da jeder dieser vier F¤lle mit der gleichen Wahrscheinlichkeit eintritt, ist

d = ggT(a ’ x, n)

mit einer Wahrscheinlichkeit von 0.5 ein echter Teiler von n. Nach r Runden ist
die Zahl n also mit der Wahrscheinlichkeit von 1 ’ (1/2)r in ihre Primfaktoren
zerlegt.
Damit ist begründet, dass die beiden Probleme,

• n zu faktorisieren und

• Quadratwurzeln modulo n zu bestimmen,

(probabilistisch) algorithmisch ¤quivalent sind.

Bemerkung
Das Rabin-Verfahren kann durch einen Chosen-Cipher-Text-Angriff gebrochen
werden. Ein Angreifer A w¤hlt ein x ∈ {1, . . . , n ’ 1} und l¤sst den Geheim-
text C = x2 von R entschlüsseln. Dabei erh¤lt A die Quadratwurzel a modulo n
von R als mutmaßlichen Klartext zurück. Wie im Beweis zu Lemma 9.3 bestimmt
nun A mit einer Wahrscheinlichkeit von 0.5 einen Primteiler von n, indem er den
ggT der Zahlen n und a ’ x bestimmt. Wiederholt A den Angriff nur oft genug,
so erh¤lt A die Primfaktoren p und q. Auch wegen dieses Angriffs ist das Rabin-
Verfahren für die Praxis nicht relevant.


Aufgaben

9.1 Der Empf¤nger E erh¤lt den ElGamal-Chiffretext (B, c) = (6, 6). Der öffent-
liche Schlüssel von E ist (p, g, A) = (13, 2, 11). Bestimmen Sie den zugehörigen
Klartext.

9.2 Es sei n = 589 ein öffentlicher Schlüssel beim Rabin-Verfahren. Bestimmen
Sie aus dem Geheimtext C = 442 alle möglichen Klartexte.

9.3 Es ist n = 124573 der öffentliche Schlüssel beim Rabin-Verfahren. Ein An-
2
greifer l¤sst bei einem Chosen-Cipher-Text-Angriff den Text 113 entschlüsseln und
erh¤lt dabei den mutmaßlichen Klartext 110459 zurück. Bestimmen Sie hiermit
die Primfaktorzerlegung von n.
10 Diskrete Logarithmen

Die Sicherheit vieler kryptogra¬scher Verfahren basiert auf der Schwierigkeit,
diskrete Logarithmen zu bestimmen. Beispiele sind der Dif¬e-Hellman-Schlüs-
selaustausch und das ElGamal-Verfahren, auch in der Variante als Signatur-
Verfahren, das wir in Kapitel 12 besprechen werden. Das diskrete Logarithmen-
problem ist daher von großer Bedeutung für die Kryptologie.
Wir behandeln in diesem Kapitel die zwei wichtigsten, nicht spezialisierten Al-
gorithmen, die zu einem Gruppenelement a einer zyklischen Gruppe g kleiner
Ordnung den diskreten Logarithmus x, d. h. die Potenz x mit a = g x bestimmen “
den Baby-Step-Giant-Step-Algorithmus von Shanks und Pollards -Methode. Damit
erhalten wir ein grobes Maß für die Sicherheit solcher kryptogra¬scher Verfahren.
In einem letzten Abschnitt zeigen wir, dass die Wahl einer großen Gruppenord-
nung |G| alleine nicht vor den Algorithmen von Shanks und Pollard schützt.
Entscheidend ist letztlich der größte Primteiler der Gruppenordnung |G|. Dieser
muss genügend groß gew¤hlt werden. Andernfalls greifen die Algorithmen von
Shanks und Pollard zusammen mit der Reduktion der Gruppe G auf Gruppen von
der Ordnung der Primteiler von |G|.

10.1 Das diskrete Logarithmenproblem
Sowohl das Dif¬e-Hellman- als auch das ElGamal-Verfahren lassen sich in einer
beliebigen endlichen zyklischen Gruppe G = g realisieren. Beide Verfahren
sind unsicher, wenn diskrete Logarithmen berechnet werden können, d. h.:

Aus a = g x und g kann x berechnet werden.

In diesem Abschnitt bezeichne G eine zyklische Gruppe und g ∈ G ein erzeugen-
des Element von G, also G = g .

10.1.1 Der diskrete Logarithmus
Das diskrete Logarithmenproblem, kurz DLP, lautet:
Gegeben ist a ∈ G = g , gesucht ist x ∈ Z mit a = g x .
Das kleinste nichtnegative solche x heißt diskreter Logarithmus von a zur Basis
g; wir schreiben hierfür x = Logg a.
Beispiel
— 6
Es ist 2 eine Primitivwurzel modulo 13, d. h. Z13 = 2 . Wegen 2 = 12 und
8
2 = 9 gilt:
Log2 (12) = 6 und Log2 (9) = 8 .
180 10 Diskrete Logarithmen

10.1.2 Enumeration

Die naive Herangehensweise, n¤mlich das sukzessive Berechnen von

g , g2 , g3 , g4 , . . .

und Vergleich mit a = g x in jedem Schritt, hat Laufzeit O(|G|), ist also nicht
sehr ef¬zient. Diese Methode nennt man auch Enumeration. Wir besprechen im
Folgenden bessere Methoden zur Berechnung diskreter Logarithmen.


10.2 Der Baby-Step-Giant-Step-Algorithmus von Shanks
Der Baby-Step-Giant-Step-Algorithmus von Shanks ist eine Methode zur schnel-
len Berechnung diskreter Logarithmen. Die Aufgabenstellung lautet:
Gegeben ist a ∈ G = g , gesucht ist x = Logg (a).

10.2.1 Das Verfahren
Benötigt wird eine obere Schranke für die Gruppenordnung, wir setzen:

|G| = min k ∈ N ; k2 ≥ |G| ,
n :=


es ist dann n2 größer oder gleich |G|. Für jedes a ∈ G gilt somit x = Logg (a) ¤ n2 .
Wir dividieren die (gesuchte) Zahl x durch die Zahl n = |G| mit Rest:

x = q n + r , wobei r ∈ {0, . . . , n ’ 1} und q ∈ {0, . . . , n} .

Der Clou ist hierbei, dass das Element q wegen der Wahl von n in der Menge
{0, . . . , n} liegt. Wir erhalten

a = g x = gq n+r , also a g’r = gq n .

Wir ermitteln aus dieser letzten Formel nun r und q und damit den gesuchten
diskreten Logaritmus x = q n + r. Für r gibt es n Möglichkeiten, für q sind es
n + 1 Möglichkeiten. Wir erhalten zwei Listen von Gruppenelementen.

a g’r = gq n
QQQ
kk
kkk QQQ
kkk QQQ
k QQQ
kkk
ukk Q(
’r , r = 0, . . . , n ’ 1 q n , q = 0, . . . , n
g
ag

a g0 , a g’1 , a g’2 , . . . , a g’n+1
Die Baby-Step-Liste: und
g0 , gn , g2n , . . . , gnn .
die Giant-Step-Liste:
10.3 Pollards -Methode * 181

Nun vergleicht man beide Listen. Ein gemeinsames Element a g’r = gq n in bei-
den Listen liefert die Zahlen r und q und damit den diskreten Logarithmus
x = q n + r = Logg (a) .
Wir führen den Algorithmus von Shanks an einem Beispiel durch.
Beispiel

Es sei G = Z97 = 5 , also g = 5, und es sei a = 31. Wir bestimmen x = Logg (a).

Wegen 92 < |Z97 | = 96 ¤ 102 gilt n = |G| = 10. Wir erhalten die Baby-Step-
Liste:
0 1 2 3 4 5 6 7 8 9
r
’r
31 · 5 31 45 9 60 12 80 16 42 86 56
und die Giant-Step-Liste:
0 1 2 3 4 5 6 7 8 9 10
q
q 10
5 1 53 93 79 16 72 33 3 62 85 43
Für r = 6 und q = 4 erhalten wir dasselbe Ergebnis 16. Folglich ist
x = q n + r = 4 · 10 + 6 = 46 = Log5 (31) .
10.2.2 In der Praxis
Auf einem Rechner wird man die Giant-Step-Liste im Voraus berechnen, sie ist
unabh¤ngig von der Größe a, dessen diskreter Logarithmus berechnet werden
soll. Die Giant-Step-Liste kann also mehrfach benutzt werden.
Anschließend berechnet man die Baby-Step-Liste schrittweise und vergleicht
nach Berechnen jedes einzelnen Wertes diesen mit den Werten aus der Giant-
Step-Liste “ das Suchen wird vereinfacht, wenn die Giant-Step-Liste sortiert ist.
Man braucht ¤ 2 n Gruppenoperationen und muss n Gruppenelemente spei-
chern. Wir halten fest:
Lemma 10.1
Die Komplexit¤t des Baby-Step-Giant-Step-Algorithmus zur Bestimmung des diskreten
Logarithmus in einer zyklischen Gruppe G ist O( |G|).
Wegen des Zeit- und Speicherbedarfs ist der Baby-Step-Giant-Step-Algorithmus
bei der Größenordnung von |G| > 2160 nicht mehr einsetzbar “ bei einer zykli-
schen Gruppe der Größenordnung 280 ist bereits ein Speicher von einem Terabyte
nötig, falls man jedes Gruppenelement als ein Byte darstellen kann.

10.3 Pollards -Methode *
Deutlich weniger speicheraufwendig als der Baby-Step-Giant-Step-Algorithmus
ist Pollards -Methode, die wir nun schildern. Die Aufgabenstellung lautet wie
oben:
Gegeben ist a ∈ G = g , gesucht ist x = Logg (a).
182 10 Diskrete Logarithmen

10.3.1 Das Verfahren
Pollards -Methode besteht aus drei Schritten:
1. Schritt. Zerlege die Menge G in drei (etwa gleich große) Teilmengen G1 , G2 ,
G3 mit 1 ∈ G2 .
2. Schritt. Bestimme ganze Zahlen s, t mit as = gt wie folgt: Erzeuge die Folge
x0 = 1, x1 , x2 , . . . durch
§
⎨ a xi , falls xi ∈ G1
xi , falls xi ∈ G2 .
2
xi+1 :=
©
g xi , falls xi ∈ G3

Offenbar gilt x1 ∈ {a, g}, x2 ∈ {a2 , a g, g2 }, ..., d. h.

xi = a±i g βi mit ±i , β i ∈ N0 für alle i = 1, 2, . . . .

Da G endlich ist, |G| = n ∈ N, gibt es Indizes i, j, i < j mit xi = x j , und es gilt:

xi = x j ” a±i g βi = a± j g β j ” a±i ’± j = g β j ’βi .

Damit haben die Zahlen

s := ±i ’ ± j und t := β j ’ β i

die gewünschte Eigenschaft.

Bemerkung
Im Allgemeinen kann man für s und t betragsm¤ßig kleinere Zahlen w¤hlen.
Dazu reduziere man ±i ’ ± j und β j ’ β i modulo n, d. h. man teilt ±i ’ ± j und
β j ’ β i durch n mit Rest und erh¤lt:

±i ’ ± j = qs n + s und β j ’ β i = qt n + t .

Für die so erhaltenen Zahlen s, t gilt s, t ∈ {0, . . . , n ’ 1}. Wegen an = 1 = gn
(beachte den Satz 6.9 von Euler) gilt weiter:

as = aqs n+s = a±i ’± j = g β j ’βi = gqt n+t = gt .

Auf diese Weise erh¤lt man die kleinsten positiven Zahlen s und t mit as = gt .

Bei dieser Form des Algorithmus sind die Größen x0 , x1 , . . . , xi , . . . , x j zu spei-
chern. Nach dem Geburtstagsparadoxon (siehe Aufgabe 2.2) erh¤lt man die Zah-
len i < j mit xi = x j etwa nach |G| Schritten. Das Geburtstagsparadoxon ist
hier anwendbar, weil die Folge (xi ) wegen der Wahl der Rekursion einer Zufalls-
folge sehr ¤hnlich ist. Zeit- und Speicherkomplexit¤t sind damit O( |G|). Wir
werden durch eine Modi¬kation des zweiten Schrittes im Abschnitt 10.3.2 die
Speicherkomplexit¤t auf O(1) bringen.
10.3 Pollards -Methode * 183

3. Schritt. Bestimme den diskreten Logarithmus x = Logg (a) wie folgt: Mit den
Zahlen s und t aus dem 2. Schritt gilt wegen a = g x und (ii) in Lemma 6.1 (b):

gt = as = gsx , d. h. s x ≡ t (mod n) .

Folglich ist das gesuchte x eine Lösung der Kongruenzgleichung

s X ≡ t (mod n) .

Die Lösungsmenge dieser Kongruenzgleichung ist nach Korollar 4.19 die Menge
v + n Z, wobei d = ggT(s, n) und v die ohne Einschr¤nkung kleinste positive
d
Lösung der Kongruenzgleichung ist. Wir erhalten v wie in der Bemerkung nach
Korollar 4.19 geschildert mit dem euklidischen Algorithmus. Da der diskrete Lo-
garithmus x kleiner als n ist, ¬ndet man x unter den d Zahlen
n n n
v, v+ , v + 2 , . . . , v + (d ’ 1) .
d d d
n
Enumeration, d. h. Bestimmen von gv+k d , k = 0, . . . , d ’ 1, und Vergleichen des
Ergebnisses mit a liefert x.

Bemerkung
Falls d groß sein sollte, so kann es durchaus ef¬zienter sein, das Verfahren von
vorne zu beginnen, um ein kleines d zu erhalten, als die Enumeration durchzu-
führen.

Beispiel

<< . .

. 23
( : 33)



. . >>