Schnelle modulare Exponentiation
©2005
Bachelorarbeit
118 Seiten
Zusammenfassung
Inhaltsangabe:Zusammenfassung:
In dieser Arbeit werden Algorithmen dargestellt und analysiert, die die in kryptographischen Verfahren häufig vorkommende modulare Exponentiation a^e mod m möglichst schnell berechnen.
Nach der Einleitung in Kapitel 1 werden in Kapitel 2 einige wichtige mathematische Grundlagen vorgestellt. Dabei handelt es sich um den euklidischen Algorithmus, den erweiterten euklidischen Algorithmus, um die modulare Arithmetik, Primzahlen und die für die Beurteilung der Komplexität von Algorithmen wichtige O-Notation.
In Kapitel 3 werden einige kryptographische Verfahren, in denen die modulare Exponentiation eine große Rolle spielt, beschrieben. Zur Beurteilung der Komplexität wird für jedes Verfahren aufgeführt, wie oft und mit welchen Bitlängen die modulare Exponentiation berechnet wird.
Die modulare Multiplikation ist Thema des Kapitels 4. Algorithmen für die Multiplikation und für die Reduktion nach der Schulmethode werden dargestellt. Es wird gezeigt wie mit einem speziellen Algorithmus für die Quadrierung eine Beschleunigung um ca. 25% erzielt werden kann. Ein rekursiver Multiplikationsalgorithmus, der für sehr große Zahlen schneller als der klassische Algorithmus arbeitet, wird vorgestellt. Den Schluss des Kapitels 4 bildet ein Abschnitt über die Montgomerymultiplikation.
In Kapitel 5 werden Methoden zur modularen Exponentiation behandelt, die ohne Vorberechnungen auskommen. Hierbei handelt es sich um die Binär-Methode, die m-ary-Method und die Fenstertechnik. Neben der Anzahl der Multiplikationen ist auch die Anzahl der während der Berechnung zu speichernden Zwischenergebnisse ein wichtiger Parameter für die Ausführungsgeschwindigkeit. Beide Parameter werden für die jeweiligen Verfahren diskutiert.
Die modulare Exponentiation mit Vorberechnungen wird in Kapitel 6 behandelt. Dort wird zunächst auf die Additionsketten eingegangen. Es wird gezeigt, dass das mathematische Problem des Findens einer möglichst kurzen Additionskette, gleichbedeutend mit dem Finden eines möglichst schnellen Exponentiationsalgorithmus ist. Im Unterabschnitt 6.1.1 wird auf die Möglichkeit eingegangen, durch mehrere parallel arbeitende Multiplizierer die Exponentiation zu beschleunigen. Es folgt ein Abschnitt über Divisionsketten, ein Verfahren, das nicht nur auf die Reduzierung der Multiplikationen abzielt. Durch Verringerung von zu speichernden Zwischenergebnissen werden langsame Speicherzugriffe verhindert und so eine Beschleunigung der […]
In dieser Arbeit werden Algorithmen dargestellt und analysiert, die die in kryptographischen Verfahren häufig vorkommende modulare Exponentiation a^e mod m möglichst schnell berechnen.
Nach der Einleitung in Kapitel 1 werden in Kapitel 2 einige wichtige mathematische Grundlagen vorgestellt. Dabei handelt es sich um den euklidischen Algorithmus, den erweiterten euklidischen Algorithmus, um die modulare Arithmetik, Primzahlen und die für die Beurteilung der Komplexität von Algorithmen wichtige O-Notation.
In Kapitel 3 werden einige kryptographische Verfahren, in denen die modulare Exponentiation eine große Rolle spielt, beschrieben. Zur Beurteilung der Komplexität wird für jedes Verfahren aufgeführt, wie oft und mit welchen Bitlängen die modulare Exponentiation berechnet wird.
Die modulare Multiplikation ist Thema des Kapitels 4. Algorithmen für die Multiplikation und für die Reduktion nach der Schulmethode werden dargestellt. Es wird gezeigt wie mit einem speziellen Algorithmus für die Quadrierung eine Beschleunigung um ca. 25% erzielt werden kann. Ein rekursiver Multiplikationsalgorithmus, der für sehr große Zahlen schneller als der klassische Algorithmus arbeitet, wird vorgestellt. Den Schluss des Kapitels 4 bildet ein Abschnitt über die Montgomerymultiplikation.
In Kapitel 5 werden Methoden zur modularen Exponentiation behandelt, die ohne Vorberechnungen auskommen. Hierbei handelt es sich um die Binär-Methode, die m-ary-Method und die Fenstertechnik. Neben der Anzahl der Multiplikationen ist auch die Anzahl der während der Berechnung zu speichernden Zwischenergebnisse ein wichtiger Parameter für die Ausführungsgeschwindigkeit. Beide Parameter werden für die jeweiligen Verfahren diskutiert.
Die modulare Exponentiation mit Vorberechnungen wird in Kapitel 6 behandelt. Dort wird zunächst auf die Additionsketten eingegangen. Es wird gezeigt, dass das mathematische Problem des Findens einer möglichst kurzen Additionskette, gleichbedeutend mit dem Finden eines möglichst schnellen Exponentiationsalgorithmus ist. Im Unterabschnitt 6.1.1 wird auf die Möglichkeit eingegangen, durch mehrere parallel arbeitende Multiplizierer die Exponentiation zu beschleunigen. Es folgt ein Abschnitt über Divisionsketten, ein Verfahren, das nicht nur auf die Reduzierung der Multiplikationen abzielt. Durch Verringerung von zu speichernden Zwischenergebnissen werden langsame Speicherzugriffe verhindert und so eine Beschleunigung der […]
Leseprobe
Inhaltsverzeichnis
ID 8925
Schmidt, Uwe: Schnelle modulare Exponentiation
Hamburg: Diplomica GmbH, 2005
Zugl.: FernUniversität Hagen, Bachelorarbeit, 2005
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2005
Printed in Germany
V
Inhaltsverzeichnis
Erkl¨
arung
III
Inhaltsverzeichnis
V
Abbildungsverzeichnis
VII
Tabellenverzeichnis
IX
Listings
X
Symbolverzeichnis
XI
Kurzfassung
XII
1
Einleitung
1
2
Grundlagen
3
2.1
Euklidischer Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2
Erweiterter euklidischer Algorithmus . . . . . . . . . . . . . . . . . . . . . .
3
2.3
Modulare Arithmetik, Restklassen . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3.1
Rechenregeln der modularen Arithmetik . . . . . . . . . . . . . . . .
5
2.4
Primzahlen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.5
Chinesischer Restsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.6
O-Notation
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3
Kryptographische Verfahren
8
3.1
Digital Signature Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.2
ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3
Pohlig Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.4
Rabin
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.5
RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.6
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4
Modulare Multiplikation
18
4.1
Modulare Multiplikation mit
"
Schulmethode" . . . . . . . . . . . . . . . . . .
18
4.2
Modulare Quadrierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.3
Rekursiver Multiplikationsalgorithmus
. . . . . . . . . . . . . . . . . . . . .
23
VI
Inhaltsverzeichnis
4.4
Montgomery-Multiplikation
. . . . . . . . . . . . . . . . . . . . . . . . . . .
24
5
Modulare Exponentiation ohne Precalculation
27
5.1
Square and Multiply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5.2
Left to Right Binary Method
. . . . . . . . . . . . . . . . . . . . . . . . . .
29
5.3
m-ary Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.4
Fenstertechnik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
5.5
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
5.6
Modulare Exponentiation mit der Montgomery-Multiplikation . . . . . . . .
42
6
Modulare Exponentiation mit Precalculation
45
6.1
Additionsketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
6.1.1
Parallelisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
6.2
Divisionsketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
6.3
BMGW-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.4
Exponentiation mit chinesischem Restsatz . . . . . . . . . . . . . . . . . . .
63
7
Ergebnis
65
8
Implementierung eines Verfahrens
68
A Anhang
73
A.1 Versuchsanordnung Rekursiver Multiplikationsalgorithmus . . . . . . . . . .
73
A.2 Tabellierung der Aufwandsfunktionen des BMGW-Algorithmus . . . . . . . .
81
A.3 Quellcode f¨
ur die Implementierung des Divisionskettenverfahrens . . . . . . .
84
Literaturverzeichnis
104
VII
Abbildungsverzeichnis
4.1
Beispiel Multiplikationen mit der
"
Schulmethode" . . . . . . . . . . . . . . .
21
4.2
Beispiel Quadrierung mit der
"
Schulmethode"
. . . . . . . . . . . . . . . . .
22
5.1
Multiplikationen bei m-ary abh¨
angig von der Nibblebreite . . . . . . . . . . .
37
5.2
Vergleich Bin¨
armethode, m-ary und Fenstertechnik . . . . . . . . . . . . . .
41
5.3
Vergleich Registerbedarf Bin¨
armethode, m-ary und Fenstertechnik . . . . . .
41
5.4
Vergleich Multiplikation Klassisch, Baretts und Montgomery . . . . . . . . .
44
6.1
K¨
urzeste Additionskette f¨
ur 63 . . . . . . . . . . . . . . . . . . . . . . . . . .
51
6.2
Parallelisierter AKG f¨
ur n = 63 . . . . . . . . . . . . . . . . . . . . . . . . .
51
6.3
Anzahl Multiplikationen bei BMGW in Abh¨
angigkeit der Basis b
. . . . . .
61
7.1
Funktionspyramide f¨
ur die Realisierung kryptographischer Verfahren
. . . .
65
8.1
Klassendiagramm zur Implementierung des Divisionsketten-Verfahrens
. . .
69
8.2
Screenshot Testprogramm Divisionsketten Tabreiter Additionsketten . . . . .
70
8.3
Screeshot Testprogramm Divisionsketten Tabreiter Divisionskette . . . . . .
71
8.4
Screenshot Testprogramm Divisionsketten Tabreiter Exponentiation . . . . .
72
VIII
Tabellenverzeichnis
2.1
Beispiel: Erweiterter euklidischer Algorithmus ggt(a, b) = 210 x + b y . . .
4
3.1
Anzahl der modularen Exponentiationen in verschiedenen kryptographischen
Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.1
Beispiel Reduktion 55 mod 7 . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.2
Zeitkomplexit¨
at beim rekursiven Multiplikationsalgorithmus
. . . . . . . . .
23
4.3
Vergleich der Laufzeiten f¨
ur 1000 Multiplikationen . . . . . . . . . . . . . . .
24
5.1
Beispiel Left to Right Binary Method . . . . . . . . . . . . . . . . . . . . . .
30
5.2
Berechnungen der a
nib
i
bei m-ary Method mit d=1
. . . . . . . . . . . . . .
33
5.3
Beispiel m-ary Method mit d=1 . . . . . . . . . . . . . . . . . . . . . . . . .
33
5.4
Berechnungen der a
nib
i
bei m-ary Method mit d=2
. . . . . . . . . . . . . .
33
5.5
Beispiel a
250
m-ary Method mit d=2
. . . . . . . . . . . . . . . . . . . . . .
33
5.6
Berechnung der a
nib
i
m-ary Method mit d=3 . . . . . . . . . . . . . . . . . .
34
5.7
Beispiel m-ary Method mit d=3 . . . . . . . . . . . . . . . . . . . . . . . . .
34
5.8
Aufwand bei m-ary Method f¨
ur c = a
250
mod m . . . . . . . . . . . . . . . .
34
5.9
Multiplikationen bei m-ary abh¨
angig von der Nibblebreite . . . . . . . . . . .
36
5.10 Prozentuale Ersparnis m-ary Methode gegen¨
uber Bin¨
ar Methode . . . . . . .
36
5.11 Multiplikationen bei Sliding Window abh¨
angig von der Nibblebreite . . . . .
38
5.12 Prozentuale Ersparnis Fenstermethoden gegen¨
uber m-ary Methode . . . . . .
39
5.13 Berechnung der a
nib
i
Sliding Window mit d=4 . . . . . . . . . . . . . . . . .
39
5.14 Vergleich Multiplikation Klassisch, Baretts und Montgomery . . . . . . . . .
43
5.15 Zeitgewinn Montgomery vs. Klassisch in Prozent . . . . . . . . . . . . . . . .
43
6.1
Beispiel: Erzeugen einer Additionskette f¨
ur 250 mit der Binary-Methode . . .
49
6.2
Modulare Exponentiation von g
250
mod m mit Additionskette . . . . . . . .
50
6.3
Divisionskette f¨
ur 16806267284414399481 mit Strategie 2 . . . . . . . . . . .
56
6.4
Beispiel f¨
ur Precomputation bei
"
einfachem BMGW" . . . . . . . . . . . . .
58
6.5
Durchschnittliche Anzahl an Multiplikationen bei Vorausberechnung von Zwei-
erpotenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6.6
Anzahl Multiplikationen beim BMGW-Algorithmus . . . . . . . . . . . . . .
62
6.7
Anzahl Multiplikationen und Speicherbedarf mit unterschiedlichen Zerlegungs-
methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
A.1 Laufzeit von je 1000 Multiplikationen von 1024-Bitzahlen in Millisekunden .
76
A.2 Laufzeit von je 1000 Multiplikationen von 2048-Bitzahlen in Millisekunden .
77
Tabellenverzeichnis
IX
A.3 Laufzeit von je 1000 Multiplikationen von 4096-Bitzahlen in Millisekunden .
79
A.4 Laufzeit von je 1000 Multiplikationen von 8192-Bitzahlen in Millisekunden .
81
A.5 Ergebnis des Vergleichs RecursiveMult und BigInteger.multiply . . . . . . . .
81
A.6 Auswertung der Aufwandsfunktionen des BMGW-Algorithmus . . . . . . . .
83
X
Listings
4.1
Klassischer Multiplikationsalgorithmus . . . . . . . . . . . . . . . . . . . . .
18
4.2
Multiplikationsalgorithmus f¨
ur Dualzahlen . . . . . . . . . . . . . . . . . . .
19
4.3
Reduktion a mod m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.4
Quadrierungsalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4.5
Montgomeryprodukt MP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
5.1
Left to Right Binary Method
. . . . . . . . . . . . . . . . . . . . . . . . . .
30
5.2
m-ary-Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
5.3
Binary-Method mit klassischer modularer Multiplikation . . . . . . . . . . .
42
5.4
Binary Method mit Montgomerymultiplikation . . . . . . . . . . . . . . . . .
42
6.1
Erzeugen einer Additionskette mit der Bin¨
ar-Methode . . . . . . . . . . . . .
48
6.2
Modulare Exponentiation mit Additionskette . . . . . . . . . . . . . . . . . .
49
6.3
"
Divisionskette Strategie 1"
. . . . . . . . . . . . . . . . . . . . . . . . . . .
54
6.4
"
Divisionskette Strategie 2"
. . . . . . . . . . . . . . . . . . . . . . . . . . .
54
6.5
"
Exponentiation mit Divisionsketten" . . . . . . . . . . . . . . . . . . . . . .
57
6.6
"
Einfaches BMGW" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.7
"
BMGW" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
A.1 Rekursiver Multiplikationsalgorithmus
. . . . . . . . . . . . . . . . . . . . .
73
A.2 AddChainCollection (Implementierung des Divisionskettenverfahrens) . . . .
84
A.3 AddChainCollection (Implementierung des Divisionskettenverfahrens) . . . .
89
A.4 CalcDivChain (Implementierung des Divisionskettenverfahrens)
. . . . . . .
94
A.5 DivChainExp (Implementierung des Divisionskettenverfahrens) . . . . . . . .
98
A.6 SQM (Implementierung des Divisionskettenverfahrens) . . . . . . . . . . . .
101
XI
Symbolverzeichnis
x
Kleinste ganze Zahl gr¨
oßer oder gleich x
x
Gr¨
oßte ganze Zahl kleiner oder gleich x
a | n
a teilt n d.h, a ist ein Teiler von n und n ein Vielfaches von a
a n
a ist kein Teiler von n
a b (mod m)
a ist kongruent zu b modulo m
a b (mod m)
a ist nicht kongruent zu b modulo m
v(n)
Bezeichnet die Anzahl der Einsen in der Bin¨
ardarstellung von n
ggt(a, b)
gr¨
oßter gemeinsamer Teiler von a und b
mZ
Die Menge aller Linearkombinationen von m
Z/mZ
Die Menge aller Restklassen mod m
Z
m
Vertretersystem von Z/mZ das aus jeder Restklasse das kleinste
Element enth¨
alt.
XII
Kurzfassung
In dieser Arbeit werden Algorithmen dargestellt und analysiert, die die in kryptographi-
schen Verfahren h¨
aufig vorkommende modulare Exponentiation a
e
mod m m¨
oglichst schnell
berechnen.
Nach der Einleitung in Kapitel 1 werden in Kapitel 2 einige wichtige mathematische Grund-
lagen vorgestellt. Dabei handelt es sich um den euklidischen Algorithmus, den erweiterten
euklidischen Algorithmus, um die modulare Arithmetik, Primzahlen und die f¨
ur die Beurtei-
lung der Komplexit¨
at von Algorithmen wichtige O-Notation.
In Kapitel 3 werden einige kryptographische Verfahren, in denen die modulare Exponentia-
tion eine große Rolle spielt, beschrieben. Zur Beurteilung der Komplexit¨
at wird f¨
ur jedes
Verfahren aufgef¨
uhrt, wie oft und mit welchen Bitl¨
angen die modulare Exponentiation be-
rechnet wird.
Die modulare Multiplikation ist Thema des Kapitels 4. Algorithmen f¨
ur die Multiplikation
und f¨
ur die Reduktion nach der
"
Schulmethode" werden dargestellt. Es wird gezeigt wie mit
einem speziellen Algorithmus f¨
ur die Quadrierung eine Beschleunigung um ca. 25% erzielt
werden kann. Ein rekursiver Multiplikationsalgorithmus, der f¨
ur sehr große Zahlen schneller
als der klassische Algorithmus arbeitet, wird vorgestellt. Den Schluss des Kapitels 4 bildet
ein Abschnitt ¨
uber die Montgomerymultiplikation.
In Kapitel 5 werden Methoden zur modularen Exponentiation behandelt, die ohne Vorbe-
rechnungen auskommen. Hierbei handelt es sich um die Bin¨
ar-Methode, die m-ary-Method
und die Fenstertechnik. Neben der Anzahl der Multiplikationen ist auch die Anzahl der
w¨
ahrend der Berechnung zu speichernden Zwischenergebnisse ein wichtiger Parameter f¨
ur
die Ausf¨
uhrungsgeschwindigkeit. Beide Parameter werden f¨
ur die jeweiligen Verfahren dis-
kutiert.
Die modulare Exponentiation mit Vorberechnungen wird in Kapitel 6 behandelt. Dort wird
zun¨
achst auf die Additionsketten eingegangen. Es wird gezeigt, dass das mathematische
Problem des Findens einer m¨
oglichst kurzen Additionskette, gleichbedeutend mit dem Fin-
den eines m¨
oglichst schnellen Exponentiationsalgorithmus ist. Im Unterabschnitt 6.1.1 wird
XIII
auf die M¨
oglichkeit eingegangen, durch mehrere parallel arbeitende Multiplizierer die Ex-
ponentiation zu beschleunigen. Es folgt ein Abschnitt ¨
uber Divisionsketten, ein Verfahren,
das nicht nur auf die Reduzierung der Multiplikationen abzielt. Durch Verringerung von zu
speichernden Zwischenergebnissen werden langsame Speicherzugriffe verhindert und so eine
Beschleunigung der Berechnung erzielt. In Abschnitt 6.3 wird ein Algorithmus f¨
ur die Be-
rechnung modularer Exponentiationen mit fester Basis und variablen Exponenten vorgestellt.
Beendet wird Kapitel 6 mit einem Abschnitt ¨
uber die Exponentiation mit dem chinesischen
Restsatz beim RSA-Verfahren.
In Kapitel 7 werden die Ergebnisse der vorangegangenen Kapitel zusammengefasst.
Die Arbeit endet mit Kapitel 8. Hier wird die beispielhafte Implementierung eines Verfahrens
zur modularen Exponentiation beschrieben.
1
1 Einleitung
Diese Arbeit hat die modulare Exponentiation
c = m
e
mod n
zum Thema. Synonym werden oft auch die Begriffe modulares Potenzieren oder diskrete
Exponentialfunktion benutzt. Die modulare Exponentiation ist, wie in dieser Arbeit gezeigt
wird, effizient berechenbar, deren Umkehrung, der diskrete Logarithmus, aber nicht. Aus
diesem Grunde wird die modulare Exponentiation als Einwegfunktion in kryptographischen
Algorithmen genutzt. Sie wird in vielen Verschl¨
usselungsverfahren mit ¨
offentlichem Schl¨
us-
sel ben¨
otigt. Diese so genannten asymmetrischen Verschl¨
usselungsverfahren, wie z.B. RSA,
sind elementarer Bestandteil sicherer Kommunikation im Internet. So werden Banktransak-
tionen via Internet meist mittels SSL gesichert. In diesem Protokoll findet unter anderem
die RSA-Verschl¨
usselung Anwendung. Immer mehr Daten die der strikten Geheimhaltung
unterliegen werden elektronisch ausgetauscht. Medizinische Daten, Steuererkl¨
arungen, Ge-
sch¨
afte in den Bereichen B2B (Business to Business) und B2C (Business to Customers)
enthalten sch¨
utzenswerte Informationen. Der gesamte E-Commerce ist ohne Verschl¨
usselung
mit asymmetrischen Verschl¨
usselungsverfahren nicht denkbar. Modulare Exponentiation ist
also kein exotisches Randthema. Im Gegenteil, st¨
andig wird diese auf privat und gesch¨
aft-
lich genutzten Rechnern ausgef¨
uhrt. Umso wichtiger ist es, dass diese Operation m¨
oglichst
schnell ausgef¨
uhrt wird.
Damit asymmetrische Verschl¨
usselungsverfahren sicher gegen Angriffe sind, muss mit sehr
großen Zahlen gearbeitet werden. Gerechnet wird hier ¨
ublicherweise mit Bitl¨
angen bis 2048.
Um sich die Gr¨
oße einer solchen Zahl zu verdeutlichen, setzt man in die Beziehung log
b
y =
log
b
z log
z
y f¨
ur b = 10 und f¨
ur z = 2 ein. So erh¨
alt man den Umrechnungsfaktor zwischen
dekadischem und bin¨
arem Logarithmus.
log
10
y = log
10
2 log
2
y
log
10
y 0, 301 log
2
y
2
1 Einleitung
Eine Bin¨
arzahl mit einer Bitl¨
ange von 2048 entspricht also einer Dezimalzahl mit 0, 301
2048 616 Stellen. Dies ist eine Gr¨
oße, die s¨
amtliche astronomischen Dimensionen sprengt.
Zum Vergleich, die Anzahl der Atome im gesamten Universum wird auf 10
78
[1], das Al-
ter des Universums wird auf ca. 4 10
16
Sekunden gesch¨
atzt [7]. Aus diesen Zahlen wird
deutlich, dass bei einem Versuch, eine Exponentiation a
e
auszuf¨
uhren, indem man a e-mal
mit sich selbst multipliziert, die Zeit die das Weltall existiert nicht ausreichen w¨
urde um
diese Berechnung auszuf¨
uhren. Das w¨
urde selbst dann nicht funktionieren, wenn jedes Atom
im Universum ein Hochleistungscomputer w¨
are und alle parallel an dieser Aufgabe arbeiten
w¨
urden. Entsprechend wichtig ist es, Algorithmen zu finden, die die modulare Exponentiati-
on in akzeptabler Zeit ausf¨
uhren k¨
onnen. In dieser Arbeit werden Verfahren dargestellt, die
die modulare Exponentiation mit solchen großen Zahlen erm¨
oglichen und effizient ausf¨
uhren.
Die existierenden Verfahren zur schnellen modularen Exponentiation k¨
onnen in verschiede-
ne Klassen eingeteilt werden: Verfahren, die vor der eigentlichen modularen Exponentiation
Vorberechnungen ausf¨
uhren und Verfahren, die ohne solche Vorberechnungen arbeiten. Ein
weiteres Klassifizierungsmerkmal ist, ob die Anzahl der Multiplikationen reduziert wird oder
der zeitliche Aufwand f¨
ur die einzelnen Multiplikationen verringert wird. Ein weiteres Un-
terscheidungsmerkmal ist, ob der Exponent oder die Basis variabel ist. Die in dieser Arbeit
vorgestellten Verfahren werden anhand dieser Merkmale eingeteilt und auf ihre Geschwin-
digkeit und ihren Speicherbedarf hin analysiert.
3
2 Grundlagen
2.1 Euklidischer Algorithmus
Der euklidische Algorithmus ist ein Verfahren zur effizienten Berechnung des gr¨
oßten ge-
meinsamen Teilers (ggt) zweier ganzer Zahlen. Er beruht auf Satz 2.1.1
Satz 2.1.1 Seien a, b Z dann gilt
1. b = 0 ggt(a, b) = |a|
2. b = 0 ggt(a, b) = ggt(|b|, a mod |b|)
Der euklidische Algorithmus besteht nun darin, Satz 2.1.1 so oft wiederholt auf das Zahlen-
paar anzuwenden, bis b = 0 ist.
Beispiel 2.1.1 ggt(210,65)=ggt(65,15)=ggt(15,5)=ggt(5,0)=5
2.2 Erweiterter euklidischer Algorithmus
Seinen a, b, n Z. Die Gleichung n = a x + b y ist genau dann durch ganze Zahlen x, y
l¨
osbar, wenn ggt(a, b) ein Teiler von n ist. Daraus folgt
Satz 2.2.1 Es gibt ganze Zahlen x und y mit ggt(a, b) = a x + b y.
Der erweiterte euklidische Algorithmus dient dazu, die Zahlen x und y aus Satz 2.2.1 zu
berechnen und lautet wie folgt.
1. x = 1, y = 0, u = 0, v = 1
2. q = a/b , r = a mod b
3. a = b, b = r, u = x - q u, v = y - q v
4
2 Grundlagen
4. x = u, y = v, u = u , v = v
5. Wenn b = 0 dann gehe zu Schritt 2.
Beispiel 2.2.1 Es sollen ggt(210, 65) und x, y in ggt(210, 65) = 210 x + 65 y berechnet
werden. In Tabelle 2.1 ist der Ablauf des erweiterten euklidischen Algorithmus tabellarisch
dargestellt. Der ggt(210, 65) = 5 l¨
asst sich somit als Linearkombination 5 = 210 x + 65 y
q
r
a
b
u
v
x
y
u
v
-
-
210
65
-
-
1
0
0
1
3
15
65
15
1
-3
0
1
1
-3
4
5
15
5
-4
13
1
-3
-4
13
3
0
5
0
13
-42
-4
13
13
-42
Tabelle 2.1: Beispiel: Erweiterter euklidischer Algorithmus ggt(a, b) = 210 x + b y
mit x = -4 und y = 13 darstellen.
Die Darstellung ggt(a, b) = a x + b y ist aber nicht eindeutig. Ist mit dem erweiterten
euklidischen Algorithmus eine L¨
osung x, y gefunden worden, so ist die L¨
osungsmenge L =
{(x - k b, y + k a)|k Z}
2.3 Modulare Arithmetik, Restklassen
In diesem Abschnitt werden einige wichtige Definitionen und S¨
atze angegeben. Sie sind aus [6]
¨
ubernommen.
Definition 2.3.1 Haben zwei Zahlen a, b Z bei Division durch m N den gleichen Rest,
so werden a und b als kongruent modulo m bezeichnet. Geschrieben: a b (mod m).
Definition 2.3.2 Die Menge aller Zahlen, die bei Division durch m den gleichen Rest r
haben, werden als Restklasse r modulo m bezeichnet. {b : a a (mod m)} = a + mZ.
Definition 2.3.3 Die Menge aller Restklassen modulo m wird mit Zm/Z bezeichnet.
Definition 2.3.4 Ein volles Restsystem zu Zm/Z ist eine Menge, die aus jeder Restklasse
mod m genau ein Element enth¨
alt. Enth¨
alt das volle Restsystem jeweils die kleinsten nicht
negativen Elemente der Restklassen, so wird dieses Restsystem mit Z
m
bezeichnet.
2.3 Modulare Arithmetik, Restklassen
5
Beispiel 2.3.1 Zu 2.3.2: Die Restklasse zu 1 mod 4: 1 + mZ = {1 ± 1 4, 1 ± 2 4...} =
{... - 11, -7, -3, 1, 5, 9, 13}
Zu 2.3.3: Die Menge aller Restklassen mod 4: {0 + 4Z, 1 + 4Z, 2 + 4Z, 3 + 4Z}.
Zu 2.3.4: Z
4
= {0, 1, 2, 3}
Definition 2.3.5 Ein reduziertes Restsystem Z
m
ist eine Teilmenge von Z
m
in der jedes
Element teilerfremd zu m ist. Z
m
= {a Z
m
|ggT (a, m) = 1}.
Satz 2.3.1 Jedes Element in Z
m
hat ein multiplikatives Inverses.
Definition 2.3.6 Die Eulersche (m)-Funktion gibt die Anzahl der Elemente in Z
m
an, die
ein multiplikatives Inverses haben.
Satz 2.3.2 F¨
ur jede Primzahl p gilt: (p) = p - 1.
Satz 2.3.3 Sei n = p
1
p
2
... p
k
und p
1
bis p
k
verschiedene Primzahlen. Dann gilt
(n) = (p
1
) ... (p
k
) = (p
1
- 1) ...(p
k
- 1)
Satz 2.3.4 (p
n
) = p
n-1
(p - 1)
2.3.1 Rechenregeln der modularen Arithmetik
Satz 2.3.5 ((a + b) + c) (mod m) (a + (b + c)) (mod m) (Assoziativgesetz der Addition)
Satz 2.3.6 ((a b) c) (mod m) (a (b c)) (mod m) (Assoziativgesetz der Multiplikation)
Satz 2.3.7 (a + b) (mod m) (b + a) (mod m) (Kommutativgesetz der Addition)
Satz 2.3.8 (a b) (mod m) (b a) (mod m) (Kommutativgesetz der Multiplikation)
Satz 2.3.9 (a (b + c)) (mod m) (a b + a c) (mod m) Distributivgesetz.
Satz 2.3.10 (a + b) (mod m) ((a (mod m) + b (mod m)) (mod m) (Reduzierbarkeit der
Addition)
6
2 Grundlagen
Satz 2.3.11 (a b) (mod m) ((a (mod m) b (mod m)) (mod m) (Reduzierbarkeit der
Multiplikation)
Satz 2.3.12 (a + 0) (mod m) a (mod m) (Neutrales Element der Addition)
Satz 2.3.13 (a 1) (mod m) a (mod m) (Neutrales Element der Multiplikation)
Satz 2.3.14 F¨
ur alle ganzen Zahlen a und m existiert eine ganze Zahl -a, sodass gilt:
(a + (-a)) (mod m) 0 (mod m) (Existenz des inversen Elements der Addition)
Satz 2.3.15 F¨
ur alle ganzen Zahlen a und m mit a 0 (mod m) und m ist prim existiert
eine ganze Zahl a
-1
, sodass gilt: (a a
-1
) (mod m) 1 (mod m) (Existenz des inversen
Elements der Multiplikation)
Satz 2.3.16 Aus a b (mod m) und b b (mod m) folgt a c (mod m) (Transitivit¨
at)
Satz 2.3.17 Die Kongruenz ax b mod n ist genau dann l¨
osbar, wenn ggt(a, n) | b
2.4 Primzahlen
Definition 2.4.1 Eine nat¨
urliche Zahl p > 1 heißt Primzahl, wenn sie genau zwei positive
Teiler hat, n¨
amlich 1 und p. Eine ganze Zahl >1 heißt zusammengesetzt, wenn sie keine
Primzahl ist. Eine Primzahl p, die die ganze Zahl a teilt, heißt Primteiler von a.
Satz 2.4.1 Kleiner Satz von Fermat: Sei p eine Primzahl und a eine beliebige ganze Zahl
kleiner p, dann gilt a
p-1
1 (mod p)
Satz 2.4.2 Sei a eine beliebige ganze Zahl und n eine Primzahl. Dann folgt aus 2.4.1 und
2.3.2 a
(n)
1 (mod n)
2.5 Chinesischer Restsatz
7
2.5 Chinesischer Restsatz
Seien m
1
, ...m
k
nat¨
urliche teilerfremde Zahlen mit M = m
1
m
2
... m
k
, und seien r
1
, ...r
k
ganze Zahlen, so besitzt das folgende System simultaner Kongruenz
x r
1
(mod m
1
)
x r
2
(mod m
2
)
...
x r
k
(mod m
k
)
eine eindeutige L¨
osung.
2.6 O-Notation
Die Laufzeit eines Algorithmus wird mit Hilfe der O-Notation angegeben [19]. F¨
ur eine
Funktion f : N N ist
O(f (n)) = {g : N N| es gibt Konstanten c und n
0
,
sodass f¨
ur alle n n
0
gilt:g(n) c f (n)}
Es werden also die multiplikativen und additiven Konstanten weggelassen.
Beispiele:
f (n) = 8 = O(1)
f (n) = 7n + 3 = O(n)
f (n) = 12n
2
+ 46 = O(n
2
)
f (n) = 2
n
+ 50 = O(2
n
)
Die Laufzeiten O(n
k
) mit k N und k 2 werden als polynomiell bezeichnet. Hat ein
Algorithmus eine Laufzeit von O(k
n
) mit k > 1 so wird diese als exponentiell bezeichnet.
Algorithmen mit polynomieller Laufzeit heißen effizient. Zu beachten ist aber, dass f¨
ur prak-
tische Anwendungen die weggelassenen Konstanten klein sein m¨
ussen, damit der Algorithmus
effizient ist.
8
3 Kryptographische Verfahren
In diesem Kapitel werden einige kryptographische Verfahren vorgestellt. Bei diesen Ver-
fahren handelt es sich, abgesehen vom Pohling-Hellman-Verfahren, um sogenannte Public-
Key-Verfahren, Verfahren mit ¨
offentlichen Schl¨
usseln. Das Besondere an ihnen ist, dass die
Kommunikationspartner kein gemeinsames Geheimnis (den geheimen, sogenannten symme-
trischen Schl¨
ussel) mehr teilen. Seit tausenden Jahren tauschen Menschen verschl¨
usselte
Botschaften aus. Grundlage aller Verfahren war immer, dass beide Parteien sich irgendwie
auf einen gemeinsamen Schl¨
ussel einigen mussten. Dieser Schl¨
usseltausch ist eine der großen
Sicherheitsl¨
ucken dieser Verfahren, denn vor der verschl¨
usselten Kommunikation musste un-
verschl¨
usselt der Schl¨
ussel getauscht werden. Neben der Sicherheit ist auch der logistische
Aspekt von Bedeutung. Ob im gesch¨
aftlichen, milit¨
arischen oder privaten Bereich, es fin-
det immer mehr Kommunikation statt, ohne dass sich die Parteien zuvor getroffen haben.
Es hat bis 1976 gedauert, bis Diffie und Hellman einen Algorithmus fanden, der den gehei-
men Schl¨
usseltausch ¨
uberfl¨
ussig macht. Aus diesem Ansatz entwickelte sich die Public-Key
Kryptographie. Hierbei besitzt jede Partei zwei Schl¨
ussel, den ¨
offentlichen Schl¨
ussel und den
geheimen Schl¨
ussel. Ihren ¨
offentlichen Schl¨
ussel geben alle Parteien allgemein bekannt. Je-
der, auch ein potentieller Angreifer, darf sie kennen. Ver- und entschl¨
usselt wird mit einem
allgemein bekannten Algorithmus. Will ein Sender, z.B. Alice, einem Empf¨
anger, z.B. Bob,
eine Nachricht senden, so verschl¨
usselt Alice diese mit Bobs ¨
offentlichem Schl¨
ussel. Nur Bob
kann diese Nachricht mit seinem geheimen Schl¨
ussel dechiffrieren.
Es geht in den folgenden Abschnitten in erster Linie darum zu zeigen, wie die modulare
Exponentiation in den verschiedenen Verfahren Verwendung findet. Zu unterscheiden sind
modulare Exponentiationen mit variabler Basis, konstantem Exponenten und konstantem
Modul und Exponentiationen mit konstanter Basis, variablem Exponenten und konstantem
Modul. Der erste Fall findet beispielsweise bei RSA statt, f¨
ur den zweiten Fall ist DSA (Di-
gital Signature Algorithm) ein Beispiel. Weiterhin wird f¨
ur jedes Verfahren die Anzahl der
modularen Exponentiationen angegeben.
3.1 Digital Signature Algorithm
9
3.1 Digital Signature Algorithm
Der Digital Signature Algorithm (DSA) wurde 1991 vom NIST (National Institute of Stan-
dards and Technology) vorgeschlagen und sp¨
ater zum Standard erkl¨
art [6]. Ziel ist es,
die Integrit¨
at der Nachricht und die Identit¨
at des Absenders zu verifizieren. Ein Signatur-
Algorithmus kann in drei Teile zerlegt werden, die Schl¨
usselerzeugung, das Signieren einer
Nachricht und das Verifizieren der Signatur.
1. Schl¨
usselerzeugung
· Erzeugen einer Primzahl q mit 2
159
< q < 2
160
.
· W¨ahlen einer Primzahl p mit 2
511+64t
< p < 2
512+64t
, t {0, ...8} und q ist ein
Teiler von p - 1.
· W¨ahlen einer Zahl x mit x < (p - 1) und x
(p-1)/q
(mod p) > 1.
· Berechnen von g = x
p-1
/q (mod p).
· Wahl einer Zufallszahl a aus {1, 2, ..., q - 1}.
· Berechnen von A = g
a
(mod p). Der ¨
offentliche Schl¨
ussel ist (p, q, g, A). Der ge-
heime Schl¨
ussel ist a.
2. Signieren
· Mit dem ¨offentlich bekannten Secure-Hash-Algorithm (SHA) wird der Hashcode
h der zu signierenden Nachricht berechnet.
· Wahl einer Zufallszahl k {1, 2, ..., q - 1}.
· Berechnen von r = (g
k
(mod p)) (mod q)
· Berechnen von s = k
-1
(h + a r) (mod q).
· Die Signatur ist (r, s).
3. Verifizieren
· Berechnen von w = s
-1
(mod q)
· Berechnen von u
1
= (h w) (mod q).
· Berechnen von u
2
= (r w) (mod q).
· Berechnen von v = ((g
u
1
A
u
2
) (mod p)) (mod q).
· Wenn v = r gilt ist die Signatur verifiziert.
10
3 Kryptographische Verfahren
Soll ein geeignetes Verfahren f¨
ur die modulare Exponentiation in DSA ausgew¨
ahlt werden,
so ist folgende Beobachtung wichtig. Werden verschiedene Nachrichten signiert, so findet die
Exponentiation immer mit der gleichen Basis statt, der Exponent ist variabel. Das Gleiche
gilt f¨
ur die Verifikation. Werden verschiedene Nachrichten vom selben Sender verifiziert ist die
Basis stets gleich, w¨
ahrend sich der Exponent ¨
andert. F¨
ur die Signatur wird eine modulare
Exponentiation ben¨
otigt, f¨
ur die Verifikation zwei modulare Exponentiationen.
3.2 ElGamal
Die Sicherheit des Verfahrens nach ElGamal beruht auf der Schwierigkeit der Berechnung
von diskreten Logarithmen ¨
uber endlichen K¨
orpern. Unter dem diskreten Logarithmus von
y zur Basis b versteht man die kleinste Zahl x f¨
ur die y = b
x
(mod p) gilt. Das Schl¨
usselpaar
wird wie folgt gebildet.
· Wahl einer Primzahl p, und zweier Zufallszahlen g < p und x < p.
· Berechnung von y = g
x
(mod p)
· x ist der private Schl¨
ussel.
· Der ¨offentliche Schl¨
ussel besteht aus y, g und p.
Zum Verschl¨
usseln einer Nachricht M besorgt sich der Sender den ¨
offentlichen Schl¨
ussel
(y, g, p) des Empf¨
angers, w¨
ahlt eine Zufallszahl k < p und berechnet den aus dem Paar a
und b bestehenden Chiffretext mit:
a = g
k
(mod p)
b = y
k
M (mod p)
Der Chiffretext ist also doppelt so lang wie der Klartext. Entschl¨
usselt wird mit
M
= a
p-1-x
b (mod p)
Beispiel: Gew¨
ahlt seien p = 97, g = 37 und x = 67. Dann gilt y = g
x
(mod p) = 37
67
(mod 97) =
92. Der ¨
offentliche Schl¨
ussel ist somit (92, 37, 97). Soll beispielsweise M = 70 verschl¨
usselt
3.2 ElGamal
11
werden und wurde k = 13 gew¨
ahlt, so gilt:
a = 37
13
(mod 97) = 7
b = 92
13
70 (mod 97) = 38
Das Paar (7,38) ist der Chiffretext. Zum Entschl¨
usseln wird nun M wie folgt berechnet:
M
= a
p-1-x
b (mod p) = 7
97-1-67
38 (mod 97) = 70
Dadurch, dass bei jeder Verschl¨
usselung der zuf¨
allige Wert k neu gew¨
ahlt wird, werden
gleiche Klartexte zu unterschiedlichen Chiffretexten kodiert. ElGamal wird daher auch als
randomisiertes Verfahren bezeichnet. Durch die zuf¨
allige Komponente werden statistische
Angriffe erschwert. Das ElGamal-Verfahren erh¨
alt somit eine zus¨
atzliche Sicherheit. F¨
ur die
Verschl¨
usselung werden zwei modulare Exponentiationen ben¨
otigt. Dabei liegt der Exponent
k in der Gr¨
oßenordnung der Primzahl p, die ¨
ublicherweise eine L¨
ange von 1024 Bit hat.
F¨
ur die Entschl¨
usselung wird eine modulare Exponentiation ben¨
otigt. Der Exponent x liegt
ebenfalls in der Gr¨
oßenordnung von p. Da der Chiffretext l¨
anger ist als der Klartext, wird
die modulare Exponentiation f¨
ur die Entschl¨
usselung aufw¨
andiger.
Das ElGamal-Verfahren eignet sich auch als Signaturverfahren. Ver- und Entschl¨
usselung
sind aber nicht vertauschbar. Daher verl¨
auft die Signatur anders als die Verschl¨
usselung.
Zum Signieren wird der Hashcode der zu signierenden Nachricht gebildet. Die Hashfunktion
h(M ) bildet die Nachricht auf die Menge {1, ..., p - 2} ab. Dann wird ein k {1, ..., p - 2}
gew¨
ahlt das zu p - 1 teilerfremd ist. Anschließend wird die aus dem Paar (r, s) bestehende
Signatur berechnet:
r = g
k
mod p
s = k
-1
(h(M ) - x r) mod (p - 1)
k
-1
ist darin das Inverse von k modulo p - 1. Zur Verifikation besorgt sich der Empf¨
anger
den ¨
offentlichen Schl¨
ussel (y, g, p). Zun¨
achst wird die Bedingung 1 r p - 1 gepr¨
uft. Ist
diese Bedingung erf¨
ullt, wird die Kongruenz
y
r
r
s
g
h(x)
mod p
12
3 Kryptographische Verfahren
gepr¨
uft. Ist die Kongruenz erf¨
ullt, wird die Signatur akzeptiert, ansonsten wird sie abgelehnt.
F¨
ur die Signatur wird also eine modulare Exponentiation ben¨
otigt. Zum Pr¨
ufen der Kongru-
enz y
r
r
s
g
h(x)
mod p werden drei modulare Exponentiationen ben¨
otigt.
3.3 Pohlig Hellman
Das Pohlig-Hellman-Verfahren ist zwar ein asymmetrisches Verfahren, jedoch kein Public-
Key-Verfahren. Es gibt verschiedene Schl¨
ussel zum Ver- und Entschl¨
usseln, aber die Schl¨
ussel
k¨
onnen leicht aus dem jeweils anderen berechnet werden. Dies bedeutet, dass Chiffrier- und
Dechiffrierschl¨
ussel geheim bleiben m¨
ussen. Es gibt also nicht die Unterscheidung zwischen
¨
offentlichem und privatem Schl¨
ussel. Aufgef¨
uhrt wird das Verfahren an dieser Stelle, da auch
hier die Ver- und Entschl¨
usselung durch modulare Exponentiation erfolgt. Der Schl¨
ussel wird
wie folgt erstellt:
· Wahl einer großen Primzahl p.
· Wahl einer Zahl e mit 0 < e < p und e und p - 1 sind teilerfremd.
· Wahl einer Zahl d mit d e 1 (mod p - 1).
Eine Nachricht M wird wie folgt chiffriert:
c = M
e
(mod p)
Dabei ist M eine nummerisch kodierte Nachricht f¨
ur die 0 M < p gilt. Dechiffriert wird
mit
M = c
d
(mod p)
Das Pohlig-Hellman-Verfahren eignet sich nur f¨
ur die verschl¨
usselte Kommunikation. Als Sig-
naturverfahren ist es nicht geeignet. Zum Ver- und Entschl¨
usseln wird jeweils eine modulare
Exponentiation ben¨
otigt.
3.4 Rabin
Ein weiteres Verschl¨
usselungsverfahren, bei dem die modulare Exponentiation verwendet
wird, ist das Rabin-Verfahren. Zur Schl¨
usselerzeugung werden zwei große Primzahlen p und
q mit p 3 (mod 4) und q 3 (mod 4) erzeugt. Die Kongruenzbedingung ist nicht zwingend
3.4 Rabin
13
notwendig, sie beschleunigt aber die Entschl¨
usselung [6]. Der ¨
offentliche Schl¨
ussel n ist das
Produkt aus p und q. Der geheime Schl¨
ussel ist das Paar (p, q). Der Klartext besteht aus
der Menge {0, ..., n - 1}. Zur Verschl¨
usselung besorgt sich der Sender einer Nachricht den
¨
offentlichen Schl¨
ussel n und berechnet aus der Nachricht M das Chiffrat c:
c = M
2
mod n
Zur Enschl¨
usselung werden zun¨
achst m
p
und m
q
berechnet:
m
p
= c
(p+1)/4
(mod p)
m
q
= c
(q+1)/4
(mod q)
Dann werden mit Hilfe des erweiterten euklidischen Algorithmus (siehe Abschnitt 2.2) zwei
Zahlen y
p
und y
q
berechnet, sodass y
p
p + y
q
q = 1 gilt. F¨
ur die Entschl¨
usselung gibt es
nun vier M¨
oglichkeiten:
M
1
= (y
p
p m
q
+ y
q
q m
p
) mod n
M
2
= n - M
1
M
3
= (y
p
p m
q
- y
q
q m
p
) mod n
M
4
= (a m
2
- b m
4
) mod n
Bei reinen Textnachrichten kann die richtige L¨
osung dadurch erkannt werden, dass es sich
dabei um einen lesbaren Text handelt. Dies beinhaltet aber immer eine Unsicherheit und ist
f¨
ur automatisierte Vorg¨
ange nicht geeignet. Eine andere M¨
oglichkeit ist es, eine Zeichense-
quenz zu vereinbaren, die vor der Verschl¨
usselung der Nachricht vorangestellt wird.
Es folgt ein Zahlenbeispiel, das die Ver- und Entschl¨
usselung beim Rabin-Verfahren demon-
striert. Es seien p = 11 q = 23 gew¨
ahlt. Dann ist n = 11 23 = 253 der ¨
offentliche Schl¨
ussel.
Es soll im Beispiel die Nachricht M = 158 verschl¨
usselt werden.
c = M
2
(mod n) = 158
2
(mod 253) = 170
Zum Dechiffrieren werden zun¨
achst mit Hilfe des euklidischen Algorithmus (siehe Abschnitt
2.2) y
p
und y
q
in y
p
11 + y
q
23 = 1 berechnet. Es ergibt sich y
p
= -2 und y
q
= 1. Dann
14
3 Kryptographische Verfahren
werden m
p
und m
q
berechnet:
m
p
= c
(p+1)/4
(mod p) = 170
(11+1)/4
(mod 253) = 246
m
q
= c
(q+1)/4
(mod q) = 170
(23+1)/4
(mod 253) = 49
Die vier m¨
oglichen L¨
osungen werden berechnet:
M
1
= (y
p
p m
q
+ y
q
q m
p
) mod n = (-2 11 49 + 1 23 246) (mod 253) = 26
M
2
= n - M
1
= 253 - 26 = 227
M
3
= (y
p
p m
q
- y
q
q m
p
) mod n = n = (-2 11 49 - 1 23 246) (mod 253) = 158
M
4
= n - M
3
mod n = 253 - 158 = 95
Die Anzahl der modularen Exponentiationen bei der Verschl¨
usselung ist klein. Es ist sogar
nur eine Quadrierung notwendig. Zum Entschl¨
usseln werden zwei modulare Exponentiatio-
nen ben¨
otigt. Das Rabin-Verfahren kann auch f¨
ur die digitale Signatur verwendet werden.
Dazu muss die zu signierende Nachricht M eine Primitivwurzel g mod p haben. Sonst muss
die Nachricht durch eine Redundanzfunktion ver¨
andert werden. Details finden sich in [15]
und [2]. Die digitale Signatur s wird dann berechnet mit
s = M
1
2
mod n
Die Verifikation erfolgt ¨
uber
M = s
2
mod n
Im Rabin-Signaturschema wird also nur bei der Verifikation eine modulare Exponentiation
ben¨
otigt. Dabei handelt es sich sogar nur um eine modulare Quadrierung.
3.5 RSA
RSA ist das wohl bekannteste Public-Key-Verfahren. Es wurde 1978 von Ron Rivest, Adi
Shamir und Leonard Adleman ver¨
offentlicht. Das Verfahren besteht aus zwei Teilen, dem
einmaligen Berechnen des ¨
offentlichen und privaten Schl¨
ussels und dem Ver- und Entschl¨
us-
selungsalgorithmus.
3.5 RSA
15
1. Konstruktion der Schl¨
ussel
· Gew¨ahlt werden zwei zuf¨allige Primzahlen p und q.
· Es wird das Produkt n = p q errechnet. n wird als RSA-Modul bezeichnet.
· Es wird eine Zahl 2 e < n - 1 gew¨ahlt, sodass e und (p - 1) (q - 1) relativ
prim zueinander sind. e ist der Chiffrier-Schl¨
ussel.
· Es wird eine Zahl d errechnet, sodass e d mit Rest 1 durch (p - 1) (q - 1) teilbar
ist: e d 1 mod((p - 1) (q - 1)). d ist der Dechiffrierschl¨
ussel.
· Der ¨offentliche Schl¨
ussel ist das Zahlenpaar (n,e), der private Schl¨
ussel ist das
Zahlenpaar (n,d).
2. Verschl¨
usselte Kommunikation :
· Zum Verschl¨
usseln wird die Nachricht in Teile zerlegt und als Zahl M dargestellt.
Die Bitl¨
ange dieser Zahl muss kleiner als die von e sein. Verschl¨
usselt werden die
einzelnen Abschnitte mit der modularen Exponentiation: c = M
e
(mod n).
· Entschl¨
usselt wird die Nachricht, bzw. die einzelnen Abschnitte, ebenfalls mit der
modularen Exponentiation: M = c
d
(mod n).
Zum Ver- und Entschl¨
usseln wird jeweils eine modulare Exponentiation ben¨
otigt. Je kleiner
der ¨
offentliche Schl¨
ussel e gew¨
ahlt wird, desto weniger aufw¨
andig ist die Verschl¨
usselung. Es
besteht dann aber die Gefahr der Low-Exponent-Attacke [6]. Um diese zu verhindern, wird
vielfach mit e = 2
16
+ 1 gearbeitet. Der private Schl¨
ussel d liegt in der Gr¨
oßenordnung des
RSA-Moduls n. Da n wenigstens eine 512-Bitzahl ist, ist die modulare Exponentiation zum
Entschl¨
usseln entsprechend aufw¨
andig. Eine große Beschleunigung dieser modularen Expo-
nentiation ist durch Anwendung des chinesischen Restsatzes m¨
oglich. In Abschnitt 6.4 wird
darauf n¨
aher eingegangen.
Neben der Verschl¨
usselung k¨
onnen mit RSA Nachrichten auch signiert werden. Dazu wird
der Hash-Code der Nachricht mit einem bekannten Verfahren gebildet. Mit dem geheimen
Schl¨
ussel wird dieser Hashcode anschließend verschl¨
usselt und als Signatur mit der Nachricht
versandt. Der Empf¨
anger bildet nun ebenfalls den Hashcode der Nachricht, entschl¨
usselt die
Signatur mit dem ¨
offentlichen Schl¨
ussel und vergleicht die Ergebnisse. Ist das Ergebnis seiner
Hashcode-Berechnung mit der entschl¨
usselten Signatur identisch, so kann sich der Empf¨
an-
ger der Identit¨
at des Senders und der Integrit¨
at der Nachricht sicher sein. Zum Signieren
und zur Verifikation wird jeweils eine modulare Exponentiation ben¨
otigt.
Wird eine l¨
angere Nachricht zur Verschl¨
usselung mittels RSA in x Teile zerlegt, so wer-
den diese Teile nacheinannder verschl¨
usselt. Das heißt, es werden nacheinander x modulare
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2005
- ISBN (eBook)
- 9783832489250
- ISBN (Paperback)
- 9783838689258
- DOI
- 10.3239/9783832489250
- Dateigröße
- 1.2 MB
- Sprache
- Deutsch
- Institution / Hochschule
- FernUniversität Hagen – Informatik
- Erscheinungsdatum
- 2005 (August)
- Note
- 1,3
- Schlagworte
- kryptographie square multiply fenstertechnik additionskette divisionskette
