<< . .

. 27
( : 33)



. . >>


Zun¤chst wird durch geeignete Wahl einer Schranke S ∈ N das Siebintervall
I := [’S, S] © Z festgelegt. Das ist die Menge aller ganzen Zahlen zwischen ’S
und S. Nun bestimmt man f (a) für alle a ∈ I. In der Praxis wird S so gew¤hlt,
dass ’N < f (a) < N, es muss also nicht modulo N reduziert werden.
Das Vorzeichen von f (a) ist das von a und f (0) < 0, sodass ν0 (a) ∈ {0, 1} trivial
zu bestimmen ist.
Es sei a p eine Nullstelle von f modulo p. Dann ist f (a p + k p) ≡ 0 (mod p) für
alle k ∈ Z. Anders ausgedrückt p | f (a p + k p) für die beiden Nullstellen von f
in Z p und alle k ∈ Z. Weil N ein Quadrat modulo p ist, existieren diese Nullstel-
len. Um sie zu bestimmen muss nur eine Wurzel Np aus N modulo p berechnet
werden, d. h. Np ≡ N (mod p) (vgl. dazu die Bemerkung auf Seite 175). Dann
2

sind √ √
ap = ’ N + Np und b p = ’ N ’ Np

die beiden Nullstellen von f modulo p (außer im Fall p = 2, da gibt es nur eine,
n¤mlich N2 = 1). Wir suchen a p im Siebintervall I und wissen, dass ausgehend
206 11 Faktorisierung

von f (a p ) jede p-te Zahl f (a) durch p teilbar ist. Diese Divisionen “ und nur diese
“ werden ausgeführt. Anschließend wird dasselbe mit b p wiederholt.
Entsprechend kann für ungerade Primzahlen mit Potenzen von p verfahren wer-
den. Auch hier gibt es genau zwei Lösungen der Gleichung f (X) ≡ 0 (mod p j )
für alle j (siehe Lemma 6.14). Von diesen Nullstellen ausgehend l¤uft man mit
Schrittweite p j (nach links wie nach rechts) und kann abermals durch p dividie-
ren. Man dividiert nur durch p, weil man in den j ’ 1 Schritten zuvor ja schon
jeweils durch p dividiert hat. √
Für p1 = 2 wird a so gew¤hlt, dass a + N ungerade ist; für p2 = 4 ebenso, falls
1
N ≡ 1(mod 4) (sonst gibt es keine Lösung). Im Fall j > 2 gibt es vier Lösungen,
aber nur wenn N ≡ 1(mod 8). Zusammengefasst ergibt sich:

Bestimme die Schranken S, B und die zugehörige Faktorbasis F.

Für alle a ∈ Z mit ’S ¤ a ¤ S berechne f (a), notiere das Vorzeichen in ν0 (a)
und setze U(a) := | f (a)|.
j
Für alle Primzahlpotenzen pi < B mit pi aus der Faktorbasis bestimme die
j
der Kongruenzgleichung f (X) ≡ 0 (mod pi ).
Nullstellen a j
pi

j j
Ersetze für alle k ∈ Z mit |a pi + k pi | ¤ S den Eintrag U(a pi + k pi ) durch
j j
U(a pi + k pi )/pi , und erhöhe νi (a pi + k pi ) um eins. Dieser Schritt ist der Reihe
nach auszuführen: Erst für pi , dann für p2 , dann für p3 usw.
i i

Überall dort, wo am Schluss eine 1 steht, also für solche a mit U(a) = 1, ist
eine Kongruenz gem¤ß Abschnitt 11.4.3 gewonnen. Die zugehörigen Vektoren
(ν0 (a), . . . , νr (a)) bilden die Spalten der dort angegebenen Matrix.

Evtl. liefert die Large Prime Variation noch weitere Kongruenzen, wenn U(a)
eine Primzahl ist.

Da man nur p j ¤ B prüft, werden “ im Unterschied zur Kettenbruchmethode “
nur B-potenzglatte Zahlen f (a) erfasst.
Der vierte Schritt unseres Faktorisierungsalgorithmus ¤hnelt dem Sieb des Era-
tosthenes, deswegen spricht man von einem Siebverfahren.

Beispiel
Wir wenden das quadratische Sieb auf N = 589 an. Das Polynom hat die Form
f (X) = (X + 24)2 ’ N. Mit der Schranke B = 10 ergibt sich die Faktorbasis
F = {’1, 2, 3, 5, 7}. Für S w¤hlen wir 5. Für die Nullstellen a p , b p erh¤lt man

4 3 5 7
p
N ≡ . . . (mod p) 22
1 1 1
±1 ’1, ’2 3, ’2
ap, bp 1
11.6 Das quadratische Sieb 207

Wegen N ≡ 5 (mod 8) kommen höhere Potenzen von 2 nicht vor.
Nun sieben wir beginnend mit 4 (in Zweierschritten), dann mit a3 = 1, mit b3 =
’1, mit a5 = ’1, mit b5 = ’2 und schließlich mit a7 , b7 in einem Schritt.

’5 ’4 ’3 ’2 ’1 0 1 2 3 4 5
i
f (i) ’228 ’189 ’148 ’105 ’60 ’13 36 87 140 195 252
’57 ’37 ’15
:4 9 35 63
’19 ’35
:3 3 65
’63 ’5
:3 29 21
’1
:5 13
’7
:5 7
’9 ’1
:7 1 3
Das Sieben mit 9 und 27 haben wir übersprungen. Die verbleibenden Potenzen
von 3 sind bei der Aufstellung der Matrix zu berücksichtigen. Wir geben exem-
plarisch zwei Spalten an: ν(’4) = (1, 0, 3, 0, 1) und ν(3) = (0, 2, 0, 1, 1). Insge-
samt ¬ndet man sechs. Wendet man die Large Prime Variation mit der Primzahl
13 an, so erh¤lt man eine weitere.

Bemerkung
W¤hlt man B von der Größenordnung exp 1 log N · log log N (und S von etwa
2
der gleichen Größenordnung), so ergibt sich die Laufzeit

log N · log log N) .
O exp(

Es gibt eine Reihe von Vereinfachungen für dieses Verfahren.
• Manchmal werden die Rechnungen beschleunigt, wenn man bei Primzah-
len > 2 darauf verzichtet, höhere Potenzen zu sieben.
• Statt U(a) durch pi zu dividieren, kann man folgendermaßen vorgehen:
Setze im zweiten Schritt U(a) = log | f (a)|.
Ersetze U(a) durch U(a) ’ log pi .
Dabei kann der Logarithums relativ grob angen¤hert sein, weil wir ja wis-
sen, dass U(a) teilbar ist, und das delogarithmierte Ergebnis also ganzzahlig
sein muss.
In Abschnitt 14.3 werden wir das Faktorisierungsverfahren ECM, das auf ellipti-
schen Kurven basiert, behandeln. Kettenbruchmethode, ECM und quadratisches
Sieb haben asymptotisch die gleiche Laufzeit. Diese Laufzeit wird vom derzeiti-
gen Rekordhalter Zahlkörpersieb, das wir im Rahmen dieses Buches nicht behan-
deln können, unterboten.
208 11 Faktorisierung

Aufgaben

11.1 Warum sollten bei Pollards -Methode die Koef¬zienten c = 0 und c = ’2
für f (x) = x2 + c zur rekursiven Konstruktion der Folge (xi ) vermieden werden?

11.2 Implementieren Sie Pollards -Methode.

11.3 Bestimmen Sie alle Primzahlen p, sodass p ’ 1 5 -potenzglatt ist.

11.4 Es sei N eine natürliche Zahl mit mindestens zwei verschiedenen Primtei-
ler. Dann existieren zu jedem Quadrat x2 in Z — mindestens vier Quadratwurzeln
N
±x, ±y ∈ Z — , wobei 1 < ggT(x ’ y, N) < N. Hinweis: Betrachten Sie die Beweise
N
zu den Lemmata 9.1 und 9.3.

Beweisen Sie Korollar 11.4.
11.5

11.6 Bestimmen Sie mit den Daten aus dem Beispiel auf Seite 206 die Faktori-
sierung der Zahl N = 589, indem Sie das Verfahren aus Abschnitt 11.4.3 durch-
führen.

Zerlegen Sie 5 609 mit jedem der angegeben Verfahren.
11.7
12 Signaturverfahren

Wir greifen ein Thema wieder auf, das wir am Ende von Kapitel 4 im Ab-
schnitt 4.4.4 schon einmal auf sehr abstrakter Ebene angesprochen habe “ das Si-
gnieren von Nachrichten. Da wir jetzt (mutmaßliche) Einwegfunktionen mit Hin-
tertürchen zur Verfügung haben, können wir konkrete Verfahren beschreiben.
Die Aufgabe ist es, eine digitale Unterschrift zu erzeugen, die weder gef¤lscht
noch geleugnet werden kann. Ein digitales Dokument muss zweifellos einem
Verfasser zugeordnet werden. Das gelingt mithilfe von Public-Key-Verfahren, die
dazu umgekehrt werden. Um naheliegende Angriffe abzuwehren und die Verfah-
ren ef¬zienter gestalten zu können, ist es sinnvoll, Hashfunktionen einzusetzen.
Es wird dann nicht die Nachricht selbst, sondern ein Hashwert davon signiert.
Wir beschreiben das RSA- und ElGamal-Signaturverfahren, den sogenannten Digi-
tal Signature Standard sowie das Signaturverfahren nach Schnorr.
Auch wenn wir im vorliegenden Kapitel digitale Signaturen als bloße Authenti¬-
kationssysteme (siehe Kapitel 5) betrachten, bieten sie eigentlich mehr. Wir haben
das bereits in einer Bemerkung auf Seite 79 festgehalten.


12.1 Allgemeines zu Signaturverfahren
Wie in Abschnitt 4.4.4 beschrieben, kann man mit einer Art Umkehrung eines
Public-Key-Verfahrens eine digitale Signatur erzeugen.
Der Verfasser V eines Dokumentes kann mit seinem geheimen, nur ihm bekann-
ten Schlüssel d eines Public-Key-Verfahrens das Dokument N signieren. Es ent-
steht dabei aus N eine Signatur S = d(N ). Jeder andere Teilnehmer kann auf
den öffentlichen Schlüssel e des Unterzeichners zugreifen und damit die Gleich-
heit N = e(d(N )) veri¬zieren. Weil der geheime Schlüssel d nur dem Verfasser
V des Dokuments bekannt ist (oder sein sollte), ist dies ein Beweis dafür, dass die
Signatur S des Dokuments N vom Verfasser V stammt.
Diese schlichte Version hat noch einige Schw¤chen, auf die wir bei den konkreten
Beispielen eingehen werden.


12.2 Das RSA-Signaturverfahren
Ein Signaturverfahren ergibt sich aus der Einwegfunktion mit Hintertürchen des
RSA-Verschlüsselungsverfahren. Das zun¤chst beschriebene Verfahren ist nicht
sicher, aber es zeigt wesentliche Züge aller Signaturverfahren, daher sprechen
wir es kurz an. Wir werden sp¤ter geeignete Modi¬kationen beschreiben. Vorab
erinnern wir kurz an die Situation beim RSA-Verschlüsselungsverfahren.
210 12 Signaturverfahren

12.2.1 Wie l¤uft RSA?
Es sind p und q Primzahlen, n = p q, •(n) = (p ’ 1) (q ’ 1), e ∈ {2, . . . , •(n) ’ 1}
mit ggT(e, •(n)) = 1 und d ∈ {2, . . . , •(n) ’ 1} mit e d ≡ 1 (mod •(n)).
Es sind (n, e) der öffentliche Schlüssel des Empf¤ngers E einer Nachricht und d
der geheime Schlüssel von E.
Will ein Teilnehmer T an E eine Nachricht N ∈ Z n senden, so bildet er in Z n die
Potenz C = N e (die Zahlen n und e sind öffentlich zug¤nglich) und sendet diesen
Geheimtext C an E. Der Empf¤nger E entschlüsselt den Geheimtext C mit seinem
geheimen Schlüssel d, indem er C d berechnet. Nach Lemma 7.1 gilt C d = N .


12.2.2 Das Signaturverfahren mit RSA
Gegeben ist die Situation des RSA-Verschlüsselungsverfahren. Durch eine ein-
fache Modi¬kation erhalten wir das RSA-Signaturverfahren. Den geheimen
Schlüssel d beim RSA-Verfahren kennt nur E. Mit diesem geheimen Schlüssel d
kann nun aber E ein Dokument N signieren:

E stellt ein Dokument als N ∈ Z n dar.

E berechnet die Potenz S = N d mit seinem geheimen Schlüssel d.

E schickt das so signierte Dokument S an einen oder mehrere Teilnehmer T.

Teilnehmer T bestimmt mit dem öffentlich zug¤nglichen Schlüssel (n, e) die
Potenz S e = N ed = N ∈ Z n und erh¤lt so das Dokument N .

Jeder kann die Unterschrift wie T veri¬zieren.

Das (sinnvolle) Dokument N konnte nur von E in S verschlüsselt werden, da nur
E den geheimen Schlüssel d kennt. Das wird als Beweis dafür aufgefasst, dass das
Dokument N von E stammt.


12.2.3 Angriffe

Wie erw¤hnt, ist das beschriebene RSA-Signaturverfahren so noch nicht sicher.
Wir diskutieren einige Angriffe und gehen auch der Frage nach, wie diese abge-
wehrt werden können.
No-Message-Attacke. Ein Angreifer kann von jedem Element S ∈ Z n behaup-
ten, dass dieses ein von E signiertes Dokument ist. Die Veri¬kation der Signatur
mit dem öffentlichen Schlüssel e von E liefert dann ein N = S e ∈ Z n . Auch wenn
zu erwarten ist, dass N keine sinnvolle Nachricht ist, so kann dies doch einen Nut-
zen für einen Angreifer haben. Bei einer Überweisung eines Geldbetrages, kann
es durchaus vorkommen, dass man mit dem Betrag N zufrieden ist.
12.2 Das RSA-Signaturverfahren 211

Erzeugen von Signaturen aus bekannten Signaturen. Aus zwei bekannten
gültigen Signaturen kann eine weitere gültige Signatur erstellt werden. Sind n¤m-
lich S1 = N1 und S2 = N2 zwei von E signierte Dokumente, dann ist
d d


S = S1 S2 = (N1 N2 )d

die (gültige) Signatur des Dokuments N1 N2 . Indem ein Angreifer A diese Tatsa-
che ausnutzt, kann er mit einem Chosen-Plain-Text-Angriff jedes beliebige Doku-
ment im Namen von E signieren. Ist n¤mlich N ∈ Z n das Dokument, das A im
Namen von E signieren will, so kann er wie folgt vorgehen:

A w¤hlt ein Dokument b ∈ Z n mit ggT(n, b) = 1.
’1
A berechnet c = N b in Z n .

A l¤sst die beiden Dokumente b und c von E signieren und erh¤lt von E die
d
Signaturen S1 = b und S2 = cd .

A berechnet S = S1 S2 = (c b)d = N d .

A hat N mit dem geheimen Schlüssel d von E signiert: S = N d .

Dieser Angriff funktioniert, weil die Signatur-Abbildung N ’ N d ein Gruppen-
Homomorphismus ist. Das ermöglicht aus schon signierten Daten gültige Signa-
turen für neue Daten zu erzeugen. Bei einem brauchbaren Signaturschema sollte
das nicht möglich sein.


12.2.4 Wie man™s richtig macht

Bei dem beschriebenen RSA-Signaturverfahren taucht ein weiteres Problem auf.
Eventuell ist das Dokument, das signiert werden soll, zu groß, um es als ein Ele-
ment N ∈ Z n darstellen zu können. Es müsste dann in Blöcke zerlegt werden,
und jeder Block müsste einzeln signiert werden. Aber in dieser Weise ist das Ver-
fahren wenig ef¬zient, außerdem w¤re das Verfahren anf¤llig für Manipulations-
versuche. Den Schlüssel zur Lösung dieses Problems und auch zur Abwehr der
im vorigen Abschnitt beschriebenen Angriffe sind Hashfunktionen.
Bisher galt die Konvention, dass zu signierende Dokumente als N ∈ Z n codiert
waren. Diese Konvention benötigen wir im Folgenden nicht. In der Praxis ist das

Dokument N ein String über Z2 , d. h. N ∈ Z2 .
Wir modi¬zieren das in Abschnitt 12.2.2 beschriebene Verfahren unter Einsatz
einer geeigneten Hashfunktion h, die dem zu signierenden Dokument N , das
evtl. auch verschlüsselt sein kann, ein Element h(N ) ∈ Z n zuordnet.

Gegeben sei eine kollisionsresistente Hashfunktion h : Z2 ’ Z n , die öffent-
lich bekannt sein muss. Es ist zugelassen, dass verschiedene Teilnehmer dieselbe
Hashfunktion verwenden. Nun kann E sein Dokument N signieren:
212 12 Signaturverfahren

E berechnet den Hashwert h(N ) ∈ Z n zum Dokument N .

E berechnet die Potenz S = h(N )d mit seinem geheimen Schlüssel d.

E schickt das signierte Dokument (N , S) an einen oder mehrere Teilnehmer T.

T bestimmt mit der öffentlich zug¤nglichen Hashfunktion und dem öffentlich
zug¤nglichen Schlüssel (n, e) die Potenz S e und prüft, ob S e = h(N ). Nur im
Fall der Gleichheit akzeptiert T die Unterschrift S unter dem Dokument N .

Jeder kann die Unterschrift wie T veri¬zieren.

Wurde das Verfahren korrekt durchgeführt, so gilt S e = h(N )ed = h(N ) und die
Signatur wird als gültig akzeptiert. Nur E kann die Signatur S erzeugen, da nur
E den geheimen Schlüssel d kennt. Das wird als Beweis dafür akzeptiert, dass N
von E stammt und unver¤ndert vorliegt.
Die No-Message-Attacke l¤uft ins Leere, weil das Dokument ja explizit angegeben
wird. Damit der zweite Angriff “ das Erzeugen von Signaturen aus bekannten
Signaturen “ nicht möglich ist, darf h natürlich nicht multiplikativ sein.



12.3 Das ElGamal-Signaturverfahren

Auch das ElGamal-Verschlüsselungsverfahren l¤sst sich zu einem Signaturver-
fahren modi¬zieren.


12.3.1 Wie l¤uft ElGamal?

Es seien p eine Primzahl, g eine Primitivwurzel modulo p, g = Z — , A = g a p
für ein a ∈ {2, . . . , p ’ 2}. Dann ist (p, g, A) der öffentliche Schlüssel und a der
geheime Schlüssel des Empf¤ngers E beim ElGamal-Verfahren.
Der Sender G stellt seine Nachricht als Element N ∈ Z — dar, w¤hlt ein b ∈
p
{2, . . . , p ’ 2} zuf¤llig und berechnet B = g b und c = Ab N . Der Sender schickt

dann den Geheimtext (B, c) an E. Der Empf¤nger berechnet B’a c = N und erh¤lt
so den Klartext zurück (siehe auch Abschnitt 9.2.3).


12.3.2 Das Signaturverfahren nach ElGamal

Wir identi¬zieren im Folgenden gelegentlich die Restklasse a ∈ Z — mit dem
p
(kleinsten positiven) Repr¤sentanten a ∈ Z. Das ist zwar etwas schlampig, erleich-
tert aber erheblich die Schreibweise. Es ist eine lehrreiche Übung, diese Ungenau-
igkeit zu korrigieren “ man kann sich so auch davon überzeugen, dass unsere
schlampige Schreibweise durchaus seinen Sinn hat.
12.3 Das ElGamal-Signaturverfahren 213

Gegeben ist die Situation des ElGamal-Verschlüsselungsverfahren, es sei (p, g, A)
der öffentliche Schlüssel und a der geheime Schlüssel. Durch eine Modi¬kation
des Verschlüsselungsverfahrens erhalten wir das ElGamal-Signaturverfahren.

E signiert ein Dokument N ∈ Z — :
Signieren eines Datensatzes. p

E w¤hlt ein zuf¤lliges k ∈ {2, . . . , p ’ 2} mit ggT(k, p ’ 1) = 1.

E berechnet R = gk und eine Lösung s der Kongruenzgleichung

k X ≡ N ’ a R (mod (p ’ 1)) .

(dass diese Kongruenzgleichung lösbar ist, folgt aus der Teilerfremdheit von k
und p ’ 1, vgl. Korollar 4.19)

E schickt das signierte Dokument (N , R, s) an einen oder mehrere Teilneh-
mer T.

Veri¬kation der Signatur. Jeder Teilnehmer T kann die Signatur von E mittels
des öffentlichen Schlüssels von E veri¬zieren. Dazu berechnet T zum einen gN
und zum anderen A R Rs . Diese beiden Größen müssen übereinstimmen, da gilt:

A R Rs = g a R gk s = g a R+k s = gN .

Da nur E den geheimen Schlüssel a kennt, kann man dies als einen Beweis dafür
auffassen, dass das Dokument N von E stammt.

Beispiel
Wir w¤hlen die Primzahl p = 19, den Erzeuger g = 2 der Gruppe Z — und p
als geheimen Schlüssel a = 13. Damit ergibt sich der öffentlichen Schlüssel
(p, g, A) = (19, 2, 3). Mit der Nachricht N = 5 und der zuf¤lligen Wahl k = 7
7
ergibt sich R = 2 = 14. Als Lösung der Kongruenzgleichung

7 X ≡ 5 ’ 13 · 14 ≡ 3 (mod 18)

erhalten wir s = 3. Somit ist dann (N , R, s) = (5, 14, 3) das signierte Dokument,
dabei ist (14, 3) die Signatur. Zur Veri¬kation bestimmt man:

· 14 = 13 und gN = 2 = 13 .
3
14 5
A R Rs = 3

Wegen A R Rs = gN wird das signierte Dokument akzeptiert.

Die Signatur wird nicht akzeptiert, falls nicht 1 ¤ R ¤ p ’ 1 gilt. Es könnte Betrug
vorliegen, wie wir gleich zeigen werden.
214 12 Signaturverfahren

12.3.3 Angriffe

Das Ablehnen der Signatur im Fall R > p ’ 1 verhindert einen naheliegen-
den Angriff. Im Folgenden gehen wir wieder von der Situation des ElGamal-
Verfahrens aus, es sei (p, g, A) der öffentliche Schlüssel und a der geheime
Schlüssel.

Erzeugen von Signaturen aus bekannten Signaturen. Es ist manchmal mög-
lich, mithilfe einer bekannten ElGamal-Signatur (N , R, s) eine gültige Signatur
(R , s ) für ein beliebiges Dokument N zu erstellen. Jedoch gilt dann fast immer
R > p ’ 1. Wird die Größenbeschr¤nkung 1 ¤ R ¤ p ’ 1 also nicht eingehalten,
so kann es sein, dass aus einer bekannten Signatur eine neue Signatur konstruiert
wurde. Wir schildern das Vorgehen eines Angreifers, der dies zum Ziel hat.
Einem Angreifer A sei ein Dokument N mit der Signatur (R, s) bekannt. Und
es sei N ein weiteres Dokument, das A im Namen von E signieren will. Falls
das Element N , aufgefasst als Element des Restklassenringes Z p’1 , invertierbar
ist, d. h. N ∈ Z — oder anders ausgedrückt ggT(N , p ’ 1) = 1, so erreicht der

<< . .

. 27
( : 33)



. . >>