Excerpt
Diplomarbeit
E
LLIPTISCHE
K
URVEN ALS ALTERNATIVES
P
UBLIC
K
EY
-V
ERFAHREN
IM
H
OMEBANKING
-S
TANDARD
HBCI
René Algesheimer
Diplomarbeit
am Fachbereich 17: Mathematik
Johannes Gutenberg-Universität
Mainz
18.01.2000
II
III
Diese Arbeit beschreibt meine Forschungen am Fachbereich Mathematik der Johannes
Gutenberg-Universität Mainz im Rahmen meiner Diplomprüfung. Ich hoffe, dass diese meine
Arbeit zukünftigen Forschungen dient und HBCI als Sicherheitsstandard möglicherweise
verbessert.
Besonderen Dank möchte ich den folgenden Personen für Ihre unerschöpfliche
Unterstützung und Aufmunterung während meiner Arbeitsphase aussprechen.
An erster Stelle richtet sich mein Dank an Prof. Dr. Gerd Hofmeister, der mir durch sein
,,Seziermesser der Kritik" auf eine stets liebenswerte Art half, die Sprachmelodie der
Mathematik zu erfassen.
Weiterhin möchte ich Herrn Prof. Dr. Albrecht Beutelspacher herzlich danken, der mir trotz
seines straffen Zeitplans die Möglichkeit gab, bei ihm und im Fach Kryptologie meine
Diplomarbeit zu schreiben.
Für die Idee zu dieser Arbeit, für viele mathematische Gespräche und für noch mehr
mühevolle Kleinarbeit gilt mein besonderer Dank Herrn Detlef Hühnlein, Secunet Security
Networks AG Frankfurt. Auch Herrn Dr. Johannes Merkle, Secunet Security Networks AG
Frankfurt, gilt mein Dank für seine haarstäubenden Skizzen zu den elliptischen Kurven.
Meiner ehemaligen Übungsleiterin Frau Dr. Heike Neumann ist es sicherlich zuzuschreiben,
dass mein Interesse für die Kryptologie so entfacht wurde.
Begeistert schien keiner meiner Korrekturassistenten über den dicken Stapel Papier
gewesen zu sein, der plötzlich vor Ihnen auf dem Tisch lag. Dennoch haben sie alle
durchgehalten.
Ständige mathematische Ansprechpartnerin war Frau Joy Müller, IBM Cryptography
Research Group Zürich. Sie hat sicherlich den härtesten Teil der Korrektur übernommen. Für
ihre inhaltliche Korrektur und Finesse sei ein besonderer Dank ausgesprochen.
IV
Hätte Exaktheit einen Namen, so würde sie bestimmt Norman Hänsler heißen. Ihm gilt mein
Dank für seine hervorragend kleinliche Korrektur meines wissenschaftlichen Arbeitens, für
sein großes Ohr in dieser Zeit und viele herzhafte Lacher.
Für die Bereitschaft und Interesse, sich in fremdes Terrain zu wagen und meine Arbeit auf
Rechtschreibung Korrektur zu lesen, richtet sich mein Dankeschön an Julia Löhr und meinen
Daddy Edgar Algesheimer.
Mein letztes Dankeschön gebührt all jenen stillen Freunden, die sich so selten über
mangelnde Zeit mit mir beklagten, meiner Familie für die Harmonie und Joy für den tiefen
Sinn.
Mainz, den 1.1.2000
René Algesheimer
V
I
NHALTSVERZEICHNIS
Tabellenverzeichnis... IX
Abbildungsverzeichnis... X
Abkürzungsverzeichnis... XII
K
APITEL
1:
V
ORBEMERKUNGEN
1
1.1 P
ROBLEMSTELLUNG UND
Z
IELSETZUNG
... 3
1.2 M
ETHODIK UND
V
ORGEHENSWEISE
... 4
K
APITEL
2:
E
INIGE
G
RUNDLAGEN
7
2.1 E
INIGE ZAHLENTHEORETISCHE
A
SPEKTE
... 9
2.2 E
INIGE KRYPTOGRAFISCHE
A
SPEKTE
... 19
2.2.1
Terminologie... 19
2.2.2
Einweg- und Hashfunktionen... 25
2.2.3
Das Faktorisierungsproblem... 28
2.2.4 Das Problem des diskreten Logarithmus... 29
2.2.5
Zusammenfassung und Ausblick... 32
2.3 K
RYPTOGRAFISCHE
V
ERSCHLÜSSELUNGSSYSTEME
... 33
2.3.1
Anforderungen... 33
2.3.2
Symmetrische Verschlüsselung mit dem DES... 34
2.3.3
Asymmetrische Verschlüsselung... 38
2.3.3.1
Der RSA... 40
2.3.3.2
Das ElGamal-Verschlüsselungssystem... 42
2.4 D
IGITALE
S
IGNATUREN
... 45
2.4.1
Anforderungen... 45
2.4.2
Der Digital Signature-Algorithm (DSA)... 47
2.5 A
UTHENTIFIKATION MIT DEM
MAC... 50
2.6 C
HIPKARTEN ALS
S
ICHERHEITSMEDIUM
... 52
2.7 Z
USAMMENFASSUNG
... 55
K
APITEL
3:
D
EFINITION
,
A
BGRENZUNG UND
E
NTWICKLUNG DES
H
OMEBANKING
57
3.1 B
EGRIFFSBESTIMMUNG
H
OMEBANKING
... 59
3.2 D
IE
E
NTWICKLUNG DES
H
OMEBANKING IN
D
EUTSCHLAND
... 62
3.3 A
NFORDERUNGEN AN EINEN NEUEN
H
OMEBANKING
-S
TANDARD
... 65
3.3.1
Anforderungen an die Sicherheit... 65
3.3.2
Anforderungen an das Design... 67
3.4 Z
USAMMENFASSUNG UND
A
USBLICK
... 68
VI
K
APITEL
4:
HBCI
H
OMEBANKING
C
OMPUTER
I
NTERFACE
69
4.1 D
ER FORMALE
A
UFBAU VON
HBCI... 71
4.1.1
Die Syntax... 71
4.1.2
Der Aufbau einer HBCI-Nachricht... 73
4.1.3 Erstellung und Empfang einer Nachricht... 74
4.1.4 Der Dialog zwischen Kunde und Kreditinstitut... 75
4.2 S
ICHERHEIT IN
HBCI
UND
Ü
BERPRÜFUNG DER
A
NFORDERUNGEN
... 78
4.2.1
Anforderungen an die Sicherheit... 81
4.2.2
Anforderungen an das Design... 90
4.3 A
LTERNATIVEN ZU
HBCI... 94
4.4 Z
USAMMENFASSUNG UND
A
USBLICK
... 98
K
APITEL
5:
E
LLIPTISCHE
K
URVEN IN DER
K
RYPTOLOGIE
99
5.1 E
INFÜHRUNG IN DIE
T
HEORIE DER ELLIPTISCHEN
K
URVEN
... 101
5.1.1
Kurven in der Ebene... 101
5.1.2
Definition von elliptischen Kurven... 104
5.1.3
Elliptische Kurven als Gruppen... 110
5.1.4 Die Gruppenoperationen in der affinen Ebene... 117
5.1.5 Elliptische Kurven über endlichen Körpern... 120
5.1.6
Die Ordnung von E (K,
, O)... 122
5.1.7
Weil-Paarungen... 130
5.2 E
LLIPTISCHE
K
URVEN IN DER
P
UBLIC
K
EY
-K
RYPTOGRAFIE
... 132
5.2.1 Das Diskrete Logarithmus-Problem für elliptische Kurven... 132
5.2.2
Elliptische Kurven und Geheimtexte... 133
5.2.3
Verschlüsselungsverfahren mit elliptischen Kurven... 136
5.2.4
Signaturverfahren mit elliptischen Kurven... 138
K
APITEL
6:
E
LLIPTISCHE
K
URVEN ALS
S
ICHERHEITSBAUSTEIN IN
HBCI
141
6.1 K
RYPTOGRAFISCH SCHWACHE ELLIPTISCHE
K
URVEN
... 143
6.1.1
Singuläre elliptische Kurven... 144
6.1.2
Supersinguläre elliptische Kurven... 146
6.1.3 Elliptische Kurven mit Spur 1 und Spur 2... 146
6.1.4
Kritische elliptische Kurven... 147
6.2 K
RYPTOGRAFISCH STARKE ELLIPTISCHE
K
URVEN
... 148
6.3 D
IE
S
ICHERHEIT VON
EC-S
YSTEMEN IM
V
ERGLEICH ZUM
RSA
UND
DSA... 151
6.4 V
ORTEILE DER
I
NTEGRATION DER
EC-K
RYPTOSYSTEME IN
HBCI... 158
6.5 Z
USAMMENFASSUNG
... 162
Literaturverzeichnis... 163
Anhang A Beispiel einer Einzelüberweisung in HBCI ... 175
Anhang B Wer ist Alice, Bob und Mallory?... 178
Erklärung zur Diplomarbeit... 179
VII
T
ABELLENVERZEICHNIS
K
APITEL
2:
E
INIGE MATHEMATISCHE
G
RUNDLAGEN
7
Tabelle 2-1: Das R-Schema... 12
Tabelle 2-2: Das P-Q-Schema... 13
Tabelle 2-3: Komplexität eines Algorithmus... 22
Tabelle 2-4: Laufzeit verschiedener Klassen von Algorithmen... 23
Tabelle 2-5: Faktorisierung mit dem speziellen Zahlkörpersieb... 29
K
APITEL
3:
D
IE
E
NTWICKLUNG DES
H
OMEBANKING
57
Tabelle 3-1: Der Strukturwandel im Bankbetrieb... 64
K
APITEL
4:
HBCI
H
OMEBANKING
C
OMPUTER
I
NTERFACE
69
Tabelle 4-1: HBCI-Versionen... 71
Tabelle 4-2: Trennzeichen in der HBCI-Syntax... 73
Tabelle 4-3: Segmente vor der Verschlüsselung... 74
Tabelle 4-4: Segmente nach der Verschlüsselung... 75
Tabelle 4-5: Anforderung an die Identität... 89
Tabelle 4-6: Anforderung an die Authentifikation... 89
Tabelle 4-7: Anforderung an die Integrität... 89
Tabelle 4-8: Anforderung an die Vertraulichkeit... 90
Tabelle 4-9: Anforderung an die Doppeleinreichungskontrolle... 90
Tabelle 4-10: Anforderung an die Nicht-Abstreitbarkeit... 90
K
APITEL
5:
E
LLIPTISCHE
K
URVEN IN DER
K
RYPTOLOGIE
99
Tabelle 5-1: Naive Bestimmung von #E (
p
F
)... 125
Tabelle 5-2: Bestimmung von #E (
p
F
) über ord (P )... 126
Tabelle 5-3: Verfahren zur Ermittlung der Gruppenordnung... 128
Tabelle 5-4: Vergleich der Gruppen Z
*
p
und E (Z
p
)... 132
K
APITEL
6:
E
LLIPTISCHE
K
URVEN ALS
S
ICHERHEITSBAUSTEIN IN
HBCI
141
Tabelle 6-1: Erforderliche Rechenleistung zur Bestimmung eines ECDL mit dem
Rho-Algorithmus... 153
Tabelle 6-2: Erforderliche Rechenleistung zur Faktorisierung ganzer Zahlen
mit dem Zahlkörpersieb... 153
Tabelle 6-3: Erforderliche Schlüsselgrößen beim RSA, DSA und
EC-Systemen bei vergleichbarer Sicherheitsstufe... 154
Tabelle 6-4: Vergleich zwischen RSA, DSA und EC-Systemen... 155
Tabelle 6-5: Das richtige Kryptosystem für jede Anwendung... 157
VIII
A
BBILDUNGSVERZEICHNIS
K
APITEL
2:
E
INIGE MATHEMATISCHE
G
RUNDLAGEN
7
Abbildung 2-1: Funktionsschema einer Verschlüsslung... 21
Abbildung 2-2: Symmetrische Verschlüsselung... 34
Abbildung 2-3: Blockchiffrierung... 35
Abbildung 2-4: Der DES als Feistel-Netzwerk... 37
Abbildung 2-5: Der Triple-DES... 38
Abbildung 2-6: Asymmetrische Verschlüsselung... 39
Abbildung 2-7: Die Funktionsweise der RSA-Verschlüsslung... 40/41
Abbildung 2-8: Die Funktionsweise der ElGamal-Verschlüsselung... 43
Abbildung 2-9: Die Funktionsweise der DSA-Signatur... 48/49
Abbildung 2-10:Die Funktionsweise des MAC... 51
Abbildung 2-11:Angriffsmöglichkeiten bei der Verwendung von Chipkarten... 53
Abbildung 2-12:Kryptografische Bausteine... 55
K
APITEL
3:
D
IE
E
NTWICKLUNG DES
H
OMEBANKING
57
Abbildung 3-1: Electronic-Banking als Schnittstelle zwischen Kunde und Bank... 59
Abbildung 3-2: Electronic-Banking... 60
Abbildung 3-3: Das PIN / TAN-Verfahren... 62
Abbildung 3-4: Aspekte einer sicheren Transaktion... 65
Abbildung 3-5: Mögliche Angriffe auf eine Homebanking-Transaktion... 66
K
APITEL
4:
HBCI
H
OMEBANKING
C
OMPUTER
I
NTERFACE
69
Abbildung 4-1: Der Aufbau einer Kundennachricht... 73
Abbildung 4-2: Der Dialog in HBCI... 76
Abbildung 4-3: Authentifizierung von Chipkarte und Lesesystem... 79
Abbildung 4-4: Merkmale des DDV-Sicherheitsverfahrens in HBCI... 80
Abbildung 4-5: Merkmale des RDH-Sicherheitsverfahrens in HBCI... 81
Abbildung 4-6: Das RDH-Verfahren in HBCI... 84/85
Abbildung 4-7: Angriffe auf die Doppeleinreichungskontrolle... 88
Abbildung 4-8: Homebanking via OFX... 95
IX
K
APITEL
5:
E
LLIPTISCHE
K
URVEN IN DER
K
RYPTOLOGIE
99
Abbildung 5-1: Elliptische Kurven in allgemeiner Weierstraß-Normalform... 105
Abbildung 5-2: Elliptische Kurven in reduzierter Weierstraß-Normalform... 107
Abbildung 5-3: Singuläre elliptische Kurven... 109
Abbildung 5-4: Die Punktaddition
für zwei Punkte P und Q mit P
Q, -Q... 111
Abbildung 5-5: Die Punktaddition
für den Fall P = Q... 112
Abbildung 5-6: Das neutrale Element O der Gruppe E ( K,
, O)... 114
Abbildung 5-7: Das zu P inverse Element P der Gruppe E ( K,
, O)... 114
Abbildung 5-8: Nachweise des Assoziativgesetzes in der Gruppe E ( K,
, O)... 115
Abbildung 5-9: Herleitung der Gruppenformeln für die Gruppenverknüpfung
... 117
Abbildung 5-10:Die Funktionsweise der EC-ElGamal-Verschlüsselung... 137
Abbildung 5-11:Die Funktionsweise der ECDSA-Signatur... 139
K
APITEL
6:
E
LLIPTISCHE
K
URVEN ALS
S
ICHERHEITSBAUSTEIN IN
HBCI
141
Abbildung 6-1: Vergleich der Sicherheitsstufen von RSA, DAS und EC-Systemen... 156
A
BKÜRZUNGSVERZEICHNIS
2
A
Die euklidische oder affine Ebene... 102
n
A Der n-dimensionale affine Raum... 102
b
|
a
,
|
*
b
a
Bezüglich der Verknüpfung * ist das Element a ein Teiler von b... 10
a Die Restklasse von a mod m... 13
K
C
f
/ ,
f
C Kurve in der affinen Ebene, die durch
0
)
,
(
2
1
x
x
f
in K mit
]
,
[
2
1
x
x
K
f
definiert ist... 102
)
(K
C
f
Die Menge aller Punkte (x, y) der affinen Ebene mit
K
y
x
,
,
für die f (x, y) =0 mit
]
,
[
2
1
x
x
K
f
gilt... 102
char (K) Die Charakteristik eines Körpers K... 15
)
(E
Die Diskriminante einer elliptischen Kurve E... 108
E / K Eine elliptische Kurve E über einem Körper K... 105
E (K) Die Menge der K-rationalen Punkte von E / K ... 105
E (K,
, O) Die auf E (K) definierte Gruppe bzgl. mit
neutralem Element O... 103
E (K) [n],E [n] Die Menge aller n-Torsionspunkte aus E (K)... 131
# E (K) Die Gruppenordnung von E (
,
,
K
O)... 123
p
F Der endliche Körper mit p Elementen, p prim...........................
q
F Der endliche Körper mit q Elementen, q =
n
p , p prim,
n eine natürliche Zahl...
*
p
F
Die multiplikative Gruppe eines endlichen Körpers
p
F ...
x
f Die partielle Ableitung
x
f
/ von f nach x... 103
ggT(x,y), (x,y) Der größte gemeinsame Teiler von x und y... 11
grad f Der Grad einer Funktion... 102
j (E) Die j-Invariante einer elliptischen Kurve E... 110
K Der algebraische Abschluss eines Körpers K... 101
K Die additive Gruppe eines Körpers K...
*
K Die multiplikative Gruppe eines Körpers K...
]
,
[
2
1
x
x
K
Der Polynomring über K..... 102
N Die Menge der natürlichen Zahlen... 11
))
(
( n
g
O
Die asymptotische Notation zur Abschätzung von
Komplexitäten oder Laufzeiten von Algorithmen... 22
O Der unendliche (projektive) Punkt der Gruppe E (K, , O)... 103
2
P
Die projektive Ebene... 103
n
P Der n-dimensionale projektive Raum... 103
Q
P
Die Punktaddition der Punkte P und Q einer
elliptischen Kurve E... 110
nP Die skalare Multiplikation eines Punktes P einer elliptischen
Kurve E............ 112
)
(x
Die Eulersche
-Funktion
1
)
,
(
und
0
|
)
(
y
x
x
y
y
x
... 42
S (P,C,K)
Ein kryptografisches Verschlüsselungssystem mit einem
Plaintext P, einer Menge C von Chiffretexten und einer
Menge K von Schlüsseln... 20
W ( x = y ) Die Wahrscheinlichkeit dafür, dass das Argument x = y zutrifft... 30
p
x
Das Legendre-Symbol für
*
p
Z
x
und
3
p
eine Primzahl... 17
Z Die Menge der ganzen Zahlen... 15
Z
Z
n ,
n
Z Der Ring der ganzen Zahlen modulo n... 15
Beh.
Behauptung
Bew. Beweis
bzgl. Bezüglich
d.h. Das heißt
i.d.R. In der Regel
m.a.W. Mit anderen Worten
o.B.d.A. Ohne Beschränkung der Allgemeinheit
z.z. Zu zeigen
BTX Der Bildschirmtext... 62
CEPT Conférence Européenne des Administration des Postes... 67
DES Der Data Encryption-Standard... 35
DL
Das Problem des diskreten Logarithmus oder Discrete
Logarithm Problem
, die Berechnung diskreter
Logarithmen in endlichen Gruppen... 29
DSA Der Digital Signature-Algorithm... 47
EC Elliptic Curves... 101
ECDL Das Elliptic Curve Discrete Logarithm-Problem... 133
EDIFACT Electronic Data Interchange for Administration
Commerce and Transport... 72
F, IF
Das Faktorisierungsproblem oder Integer Factorization,
die Berechnung der Primfaktorzerlegung einer natürlichen Zahl.. 28
GSM Groupe Spéciale Mobile / Global System Mobile... 72
HBCI Homebanking Computer Interface... 69
HTML
Hypertext Markup Language... 94
HTTP Hypertext Transport Protocol... 94
ISDN Integrated Services Digital Network... 72
MAC Der Message-Authentication Code... 50
MIPS Million Instructions Per Second... 29
OFC Open Financial Connectivity... 94
OFX
Open Financial Exchange... 94
PPT Probabilistic Polynomial Time Algorithm... 19
RSA Der Rivest Shamir-Adleman- Algorithmus... 40
SigG Das Deutsche Signaturgesetz... 80
URL
Uniform Resource Locator... 95
ZKA Der Zentrale Kredit-Ausschuss... 62
V
ORBEMERKUNGEN
In diesem kurzen einführenden Kapitel sollen
die Problemstellung und Zielsetzung der vor-
liegenden Arbeit verdeutlicht werden.
Ferner soll die angewandte Methodik erläutert
und ein Überblick zu den einzelnen Kapitel
dieser Arbeit gegeben werden.
I
NHALT
1.1
Problemstellung und Zielsetzung
1.2
Methodik und Vorgehensweise
1.1
P
ROBLEMSTELLUNG UND
Z
IELSETZUNG
3
1.1 Problemstellung und Zielsetzung
In der Wirtschaft sind Zahlungen mit die wichtigsten Vorgänge. Die Digitalisierung von
Zahlungen ist deshalb eine wichtige Voraussetzung für die bevorstehende Digitalisierung
vieler Prozesse der Wirtschaft.
Die Transaktionssicherheit ist dabei eine der wichtigsten Grundlagen zu einer erfolgreichen
Durchführung von Zahlungen über offene Netze und damit oberste Aufgabe der Kryptologie.
In Deutschland versucht sich der Standard Homebanking Computer Interface, kurz HBCI,
dieser Aufgabe zu stellen.
In dieser Arbeit soll der Begriff des Homebanking zunächst definiert und abgegrenzt werden.
Aus einer kurzen geschichtlichen Betrachtung der Homebanking-Entwicklung in Deutschland
entstehen Sicherheits- und Design-Anforderungen an einen neuen Homebanking-Standard.
Wir wollen HBCI als neuen deutschen Homebanking-Standard vorstellen und überprüfen, ob
HBCI diesen Anforderungen gerecht wird. Weiterhin werden wir durch Betrachtung möglicher
Alternativen zu HBCI aufzeigen, dass HBCI zwar noch Defizite in sich trägt, aber derzeit
keine Alternativen für den deutschen Markt zu sehen ist.
Ziel dieser Arbeit ist es, elliptische Kurven als alternativen Public Key-Baustein für HBCI
vorzuschlagen. Wir werden deshalb elliptische Kurven vorstellen und die Vorteile aufzeigen,
die eine solche Integration für HBCI bringen würde. Nach dem derzeitigen wissen-
schaftlichen Stand können dadurch eine höhere Sicherheit, Transaktionseffizienz, Kosten-
einsparungen und eine Angleichung an das deutsche Signaturgesetz (SigG) als wesentliche
Verbesserungen erreicht werden.
Da HBCI aufgrund seiner offenen Struktur einer technischen Realisierung dieser Idee nicht
im Wege steht, liegt es lediglich am Zentralen Kredit-Ausschuss (ZKA), diesen Vorschlag zu
prüfen und möglicherweise für HBCI zu standardisieren.
4 K
APITEL
1:
V
ORBEMERKUNGEN
1.2 Methodik
und
Vorgehensweise
Diese Arbeit ist im Bewusstsein der neuen Rechtschreibereform geschrieben, um ihren
aktuellen Inhalt auch in der Form widerzuspiegeln.
Mit dem Ziel, den Leser stärker in die Thematik der Arbeit einzubeziehen, wird im Folgenden
das personalisierte ,,wir" als Ansprache verwendet. Damit sei stets die Gemeinschaft von
Autor und Leser angesprochen.
Durch einen umfangreichen Grundlagenteil soll dem fachunfremden Leser in dieser Arbeit
das thematische Verständnis erleichtert werden. Es werden lediglich einige wesentliche
mathematische Grundbegriffe vorausgesetzt.
Das K
APITEL
2 dieser Arbeit widmet sich einigen Grundlagen:
Für den Verlauf der Arbeit ist es unbedingt erforderlich, ein gemeinsames kryptografisches
und zahlentheoretisches Vokabular zu besitzen. In diesem Kapitel werden wir versuchen,
diese elementaren Begriffe und Sätze stringent und klar darzulegen.
Die Entwicklung des Homebanking soll in K
APITEL
3 betrachtet werden:
Da Homebanking derzeit ein sehr angesagtes Thema in den Medien ist, scheint es
erforderlich, unterschiedliche, im Raum stehende Begriffe, wie Online-Banking, Internet-
Banking oder Homebanking, voneinander abzugrenzen. Aufgrund der Geschichte und der
Entwicklung des Homebanking in Deutschland entsteht die Notwendigkeit eines neuen
Homebanking-Standards. Dieser muss sich einigen Anforderungen an Sicherheit und an das
Design stellen, die wir in diesem Kapitel herausarbeiten wollen.
In K
APITEL
4 wollen wir HBCI Homebanking Computer Interface als neuen deutschen
Homebanking-Standard vorstellen und die an den neuen Homebanking-Standard gestellten
Anforderungen in HBCI überprüfen. Weiterhin sollen mögliche Alternativen zu HBCI
betrachtet werden. Dabei werden wir feststellen, dass es derzeit in Deutschland keine
Alternative zu HBCI gibt; dennoch sind einige Defizite in HBCI der aktuellen Version 2.1
enthalten.
Da wir elliptische Kurven als alternativen Sicherheitsbaustein für HBCI vorschlagen wollen,
sollen im K
APITEL
5
Elliptische Kurven in der Kryptologie betrachtet und notwendige
mathematische Hintergründe anschaulich aufgezeigt werden.
1.2
M
ETHODIK UND
V
ORGEHENSWEISE
5
K
APITEL
6, Elliptische Kurven als Sicherheitsbaustein in HBCI, beschließt den Bogen dieser
Arbeit und soll die Vorteile aufzeigen, elliptische Kurven als alternatives Public Key-
Verfahren in HBCI einzubinden. Eine Einbindung dieser Art würde nicht nur Vorteile in
punkto Sicherheit oder Implementation bringen, sondern auch Kosten einsparen und einige
der aufgezeigten Defizite von HBCI beseitigen.
Dieser Bogenschluss stellt die Kernaussage meiner Arbeit dar und trägt die in den vorigen
Kapiteln gewonnen Erkenntnisse zusammen. Ein Einbindung dieser Art wird von der mich
bei dieser Arbeit begleitenden Firma Secunet Security Networks AG, Frankfurt derzeit auf
Realisierung geprüft.
E
INIGE
G
RUNDLAGEN
Bevor das eigentliche Thema der vorliegenden Arbeit behandelt
wird, sollen in diesem Anfangskapitel einige wichtige mathemati-
sche Grundlagen und Definitionen besprochen werden. Sie bilden
die gedanklichen Fundamente dieser Arbeit und sind überwiegend
den mathematischen Disziplinen der Zahlentheorie und der Krypto-
grafie zuzuordnen.
Für weitere Details verweise ich an folgende grundlegende Literatur:
Zahlentheorie:
[HD1995], [SCH1991],
Algebra:
[HUP1990],
Kryptografie:
[MOV1999], [SCHB1997], [BSW1995].
I
NHALT
2.1 Einige zahlentheoretische Aspekte
2.2 Einige kryptografische Aspekte
2.3 Kryptografische Verschlüsselungssysteme
2.4 Digitale Signaturen
2.5 Authentifikation mit dem MAC
2.6 Chipkarten als Sicherheitsmedium
2.7 Zusammenfassung
2.1
E
INIGE ZAHLENTHEORETISCHE
A
SPEKTE
9
2 Einige
Grundlagen
2-1
B
EMERKUNG
:
In diesem Kapitel sollen einige grundlegende zahlentheoretische und kryptografische Aspek-
te betrachtet werden, die für den weiteren Verlauf der Arbeit relevant sind. Aufgrund des Um-
fanges beschränken wir uns auf eine Auswahl, die hier von besonderem Interesse ist, und
setzen, ohne Anspruch auf Vollständigkeit, grundlegende Begriffe aus den Bereichen Men-
gen und Abbildungen, Gruppen und Gruppenhomomorphismen, Körper, Vektorräume und li-
neare Abbildungen voraus.
2.1 Einige zahlentheoretische Aspekte
2-2
D
EFINITION
:
Ist M eine endliche Menge von m Elementen, so bezeichnen wir mit
m
M
|:
|
die Elemen-
tenanzahl oder die Ordnung von M.
2-3
B
EMERKUNG
:
Im Folgenden wollen wir die mathematische Definition für Gruppen explizit formulieren, da
wir im späteren Verlauf der Arbeit darauf zurückkommen werden.
2-4
D
EFINITION
:
Es sei eine nichtleere Menge G und eine Abbildung
G
G
G
:
gegeben. Ferner seien
G
b
a
,
. Für
)
,
( b
a
schreiben wir auch
b
a
. Gilt dann:
1. Jedem geordneten Paar (a, b)
G
G ist genau ein Element c
G mit
b
a
c
zugeordnet,
2. es seien
G
c
b
a
,
,
)
(
)
(
c
b
a
c
b
a
(Assoziativgesetz),
3. es existiert ein
G
mit
a
a
a
für alle
G
a
. Das Element
nennen
wir das neutrale Element oder das Einselement,
4. zu jedem
G
a
existiert ein
G
b
mit
e
a
b
. Das Element b nennen wir dann
das zu a inverse Element,
so nennen wir das Paar (G,
) eine Gruppe.
Gilt außer den Axiomen 1. bis 4. auch noch das Kommutativgesetz
5.
a
b
b
a
für alle
G
b
a
,
,
so nennen wir (G,
) eine abelsche oder kommutative Gruppe.
10 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
2-5
D
EFINITION
:
Es sei
M
eine Menge und ,, * " eine assoziative Verknüpfung auf
M
. Ist
M
ungleich der
leeren Menge, so nennen wir das Paar (
M
, *) eine Halbgruppe.
Weiterhin bezeichnen wir ein Element
M
l
Linkseins in (
M
, *), falls für alle
M
a
gilt,
dass
a
a
l
*
ist. Analoges gilt für die Rechtseins
r
.
2-6
L
EMMA
:
Existiert mindestens eine Linkseins
l
und mindestens eine Rechtseins
r
, so ist
r
l
das eindeutig bestimmte Einselement.
Beweis:
r
r
l
l
*
.
2-7
D
EFINITION
:
Eine Halbgruppe (M, *) nennen wir genau dann regulär, wenn für alle
M
b
b
a
2
1
,
,
gilt:
2
1
2
1
*
*
b
b
b
a
b
a
,
2
1
2
1
*
*
b
b
a
b
a
b
.
2-8
D
EFINITION
:
Es sei (M, *) eine Halbgruppe. Wir bezeichnen ein Element
M
a
genau dann als einen
Teiler von
M
b
, falls ein Element
M
c
existiert mit
b
c
a
*
. Wir schreiben dann dafür
b
a
*
|
oder auch
b
a
M
|
. Ist die Menge und die Verknüpfung aus dem Kontext heraus bekannt,
so schreiben wir auch nur
b
a |
.
2-9
D
EFINITION
:
Wir nennen ein Element
M
e
eine Einheit von (M, *), wenn ein Element
M
a
existiert mit
a
e
*
.
2-10
D
EFINITION
:
Es sei
M
a
, aber a sei keine Einheit von (M, *).
a.) Wir
nennen
a genau dann unzerlegbares Element, wenn für beliebige
M
c
b
,
mit
c
b
a
*
stets folgt, dass entweder b oder c eine Einheit von (M, *) ist.
b.)
Genau dann nennen wir a ein Primelement, wenn für beliebige
M
c
b
,
mit
)
*
(
|
*
c
b
a
stets
b
a
*
|
oder
c
a
*
|
folgt.
2.1
E
INIGE ZAHLENTHEORETISCHE
A
SPEKTE
11
2-11
S
ATZ
:
Es sei (
M
, *) eine kommunikative reguläre Halbgruppe mit Einselement
. Weiterhin besit-
ze jedes Element
M
a
wenigstens eine Zerlegung
n
i
i
u
e
a
1
*
mit einer Einheit
M
e
und
unzerlegbaren Elementen
M
u
i
.
Genau dann ist die Zerlegung eindeutig bis auf die Einheiten und die Reihenfolge der Fakto-
ren, wenn jedes unzerlegbare Element von
M
bereits Primelement ist. (Das leere Produkt
setzen wir dabei gleich
).
Beweis: Vergleiche
dazu
[HD1995] S. 19f.
2-12
D
EFINITION
:
Es seien
Z
k
a
a ,...,
1
, wobei mindestens ein
i
a
0.
a.)
Wir nennen eine Zahl
N
t
genau dann gemeinsamen Teiler von
k
a
a ,...,
1
, wenn
j
a
t |
für alle j = 1,...,k.
b.)
Insbesondere gilt, dass
i
a
t
für alle
0
i
a
. Daher ist auch die Existenz eines
größten gemeinsamen Teilers
)
,...,
(
)
,...,
(
:
1
1
k
k
a
a
a
a
ggT
d
gesichert.
c.) Wir
bezeichnen
k
a
a ,...,
1
als teilerfremd, wenn
1
)
,...,
(
1
k
a
a
ggT
2-13
B
EMERKUNG
:
Es ist leicht zu zeigen, dass für zwei Elemente
Z
b
a,
mit
0
b
zwei Elemente
Z
r
q,
mit
(1)
r
qb
a
,
(2)
b
r
0
eindeutig bestimmt sind. Vergleiche dazu [HD1995] S. 38f.
2-14
D
ER
E
UKLIDISCHE
A
LGORITHMUS
:
Es seien o.B.d.A.
N
1
0
, a
a
gegeben. Nach 2-13 existieren eindeutig bestimmte
0
...
1
3
2
m
m
a
a
a
a
und
N
m
q
q
q
,...,
,
2
1
mit
(1)
2
1
1
0
a
a
q
a
1
2
0
a
a
,
(2)
3
2
2
1
a
a
q
a
2
3
0
a
a
,
. . .
. . .
. . .
(m-1)
m
m
m
m
a
a
q
a
1
1
2
1
0
m
m
a
a
,
(m)
1
1
m
m
m
m
a
a
q
a
0
1
m
a
.
12 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
Das Verfahren bricht nach endlich vielen Schritten, o.B.d.A. nach m Schritten, ab, weil die
Zahlen
0
N
,...
,
3
2
a
a
monoton fallen.
2-15
B
EMERKUNG
:
Folgende zwei Aussagen wurden in [HD1995] S. 39f. gezeigt und bewiesen:
a.)
Nach 2-14 gilt
m
a
a
a
)
,
(
1
0
.
b.)
Zu den Zahlen
Z
1
0
, a
a
mit
1
0
0 a
a
existieren zwei Zahlen
Z
1
0
, x
x
mit
1
1
0
0
1
0
)
,
(
a
x
a
x
a
a
.
2-16
D
AS
R-S
CHEMA
:
Es seien
N
1
0
, a
a
gegeben. Im R-Schema schreiben wir die
i
q
aus dem Euklidischen Algo-
rithmus in umgekehrter Reihenfolge hintereinander.
Wir setzen
1
:
,
0
:
1
m
m
R
R
und berechnen die folgenden
i
R
rekursiv gemäß
2
1
1
i
i
i
i
R
R
q
R
für
0
,
1
,...,
3
,
2
m
m
i
im Schema
q
m
q
1
m
q
...
2
q
1
q
R 0 +1
2
m
R
...
1
R
0
R
Quelle: [HD1995] S. 41
T
ABELLE
2-1:
Das R-Schema
also
2
1
0
1
m
m
R
q
usw.
Dann gilt:
)
(
)
1
(
)
,
(
1
0
0
1
1
0
a
R
a
R
a
a
m
.
Beweis: Vergleiche
dazu
[HD1995] S. 41f.
2-17
D
AS
P-Q-S
CHEMA
:
Es seien
N
1
0
, a
a
und die
i
q
aus dem Euklidischen Algorithmus gegeben. Wir setzen
1
1
0
:
P
,
1
:
q
P
und
1
:
Q
,
0
:
1
0
Q
und berechnen
i
i
Q
P
,
induktiv gemäß
1
1
1
:
i
i
i
i
P
P
q
P
und
1
1
1
:
i
i
i
i
Q
Q
q
Q
für i = 1,...,m im Schema
2.1
E
INIGE ZAHLENTHEORETISCHE
A
SPEKTE
13
q
1
q
2
q
...
1
m
q
m
q
P +1
1
q
2
P
...
1
m
P
m
P
Q 0 +1
2
Q
...
1
m
Q
m
Q
Quelle: [HD1995] S. 42
T
ABELLE
2-2:
Das P-Q-Schema
2
1
2
1 P
q
q
usw.
also
2
2
0
1
Q
q
usw.
Dann gilt
)
(
)
1
(
)
,
(
1
1
0
1
1
0
a
P
a
Q
a
a
m
m
m
und
ferner
)
,
(
1
0
0
a
a
a
P
m
sowie
)
,
(
1
0
1
a
a
a
Q
m
, die als Kontrollgleichungen dienen.
Beweis: Vergleiche
dazu
[HD1995] S. 42f.
2-18
B
EMERKUNG
:
Das R-Schema erfordert im Vergleich zum P-Q-Schema weniger Rechenaufwand; das P-Q-
Schema liefert dafür Kontrollen für die
i
P
und
i
Q
, benötigt dabei aber auch mehr Speicher-
aufwand.
2-19
D
EFINITION
:
Es seien
Z
b
a,
und
N
m
.
Gilt
)
(
|
b
a
m
, so schreiben wir dafür
)
(mod m
b
a
oder einfach nur
)
(m
b
a
.
2-20
F
OLGERUNG
:
Es seien
Z
b
a,
und
N
m
. Dann gilt die folgende Beziehung:
q
b
und
q
a
t
,
)
(
|
)
(mod
2
1
r
m
r
m
tm
b
a
b
a
m
m
b
a
Z
für geeignete
Z
r
q
q
,
,
2
1
.
2-21
B
EMERKUNG
:
Es sei
N
m
.
Dann wird, wie leicht zu zeigen ist, durch
)
(mod m
b
a
eine Äquivalenzrelation auf
Z
defi-
niert.
14 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
2-22
D
EFINITION
:
a.)
Wir nennen die Menge
)
(mod
:
m
a
b
b
a
|
Z
eine Restklasse von a mod m.
b.) Wir
nennen
a
eine prime Restklasse, falls (a, m) = 1 ist (unabhängig von der Wahl
der Repräsentanten
a
b
).
2-23
S
ATZ
:
Es seien
Z
x
b
a ,
,
und
N
m
. Dann gelten folgende Aussagen:
a.)
)
(mod m
b
ax
lösbar
b
m
a
|
)
,
(
.
b.) Gilt
b
m
a
|
)
,
(
, so gibt es genau (a,m) Lösungen mod m.
Beweis: Vergleiche
dazu
[HD1995] S. 102.
2-24
B
EMERKUNG
:
Mit Satz 2-23 können wir die Lösbarkeit von Kongruenzen überprüfen und diese dann gege-
benenfalls etwa mit dem R-Schema lösen.
2-25
D
EFINITION
:
Es sei
)
,
(
G
eine Gruppe und
G
g
.
Dann definieren wir
Z
i
g
g
i
|
:
und nennen diese Menge das Erzeugnis von g.
Gilt
g
G
, existiert also ein
G
g
, so dass für jedes Element
G
a
eine ganze Zahl
Z
i
existiert mit
a
g
i
, so heißt G zyklisch und g nennen wir ein erzeugendes Element
von G.
2-26
B
EMERKUNG
:
a.) Es
sei
N
n
und
n
n
n
n
n
mod
)
1
(
,...,
mod
1
,
mod
0
:
Z
die Menge aller Restklas-
sen. Wir schreiben für
n
Z
auch
Z
Z
n
.
b.) Es
sei
N
n
und
n
b
a
Z
,
mit
b
a
, d.h.
a
und
b
sind zwei verschiedene Darstel-
lungen derselben Nebenklasse. Wie wir uns leicht überlegen können, gilt dann
)
,
(
)
,
(
n
b
ggT
n
a
ggT
. Daher hängt
n
Z
nicht von der Wahl der Repräsentanten ab.
c.) Es
seien
N
n
,
Z
b
a,
und seien
Z
Z
k
nk
a
n
a
a
|
_
die Restklassen
modulo n. Wir definieren unabhängig von der Auswahl der Repräsentanten auf der
Menge
Z
Z
n
dieser Restklassen Addition und Multiplikation durch
Z
Z
Z
n
b
a
n
b
n
a
b
a
)
(
:
)
(
)
(
_
_
,
Z
Z
Z
n
b
a
n
b
n
a
b
a
)
(
:
)
(
)
(
_
_
.
Für die Addition schreiben wir häufig vereinfacht +, für die Multiplikation vereinfacht *.
2.1
E
INIGE ZAHLENTHEORETISCHE
A
SPEKTE
15
d.)
Das Paar (
n
Z
,
) ist dann eine abelsche Gruppe.
e.) Es
seien
N
n
und
1
)
,
(
|
:
*
n
a
ggT
a
n
n
Z
Z
sei die Menge derjenigen Elemente
aus
n
Z
, die teilerfremd zu n sind. Die Restklasse
n
a Z
nennen wir prime Restklas-
se mod n. Die primen Restklassen bilden bezüglich der Multiplikation eine Gruppe,
die sogenannte Einheitengruppe.
Für die Ordnung von
*
n
Z
gilt:
)
(
|
|
*
n
n
Z
, wobei
)
(n
für jedes
1
n
die Anzahl der
positiven ganzen Zahlen kleiner n ist, die zu n prim sind. Wir nennen
)
(n
auch die
Eulersche
-Funktion.
2-27
B
EMERKUNG
:
Folgende Zusammenhänge können leicht gezeigt werden:
a.) Sei
p eine Primzahl. Dann gilt:
1
)
(
p
p
.
b.) Seien
p, q zwei verschiedene Primzahlen. Dann gilt:
)
1
)(
1
(
)
(
q
p
pq
.
2-28
S
ATZ VON
E
ULER
:
Für alle
*
n
a Z
gilt
)
(mod
1
)
(
n
a
n
.
Beweis:
Die Ordnung der Gruppe (
n
Z
, *) ist
)
(
|
|
*
n
n
Z
. Da ein Gruppenelement a
mit der Ordnung der Gruppe potenziert wird, ergibt sich als Folgerung des
Satzes von Lagrange das neutrale Element der Gruppe.
2-29
F
OLGERUNG VON
F
ERMAT
:
Es sei p prim und
*
p
a Z
. Dann gilt
)
(mod
1
1
p
a
p
.
Beweis:
Folgt unmittelbar aus Bemerkung 2-27 a.).
2-30
S
ATZ
:
Es seien
N
n
,
Z
r
und seien
Z
Z
k
nk
r
n
r
r
|
_
die Restklassen mod n.
Wir haben in Bemerkung 2-26 unabhängig von der Auswahl der Repräsentanten auf der
Menge
Z
Z
n
dieser Restklassen Addition und Multiplikation definiert.
a.)
Dadurch wird (
Z
Z
n
, +, *) ein kommutativer Ring mit dem neutralem Element
Z
n
_
0
und dem Einselement
Z
n
1
1
_
.
b.) Ist
n keine Primzahl, so gibt es
Z
Z
n
b
a
_
_
,
mit
_
_
_
0 b
a
und
_
_
_
0
b
a
.
c.) Ist
n = p eine Primzahl, so ist (
Z
Z
p
, +, *) ein Körper aus p Elementen.
Beweis: siehe [HUP1990] S.55ff.
16 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
2-31
D
EFINITION
:
Es sei K ein Körper mit Einselement 1. Existiert ein
N
m
mit
0
1
...
1
m
in K, so nennen
wir das kleinste derartige m die Charakteristik von K. Gibt es kein solches m, so sagen wir,
dass K die Charakteristik 0 hat. Wir schreiben für die Charakteristik im Folgenden Char (K).
2-32
S
ATZ
:
Es sei K ein Körper:
a.) Dann
ist
Char K = 0 oder eine Primzahl.
b.) Ist
K endlich mit |K| = q, so ist Char K = p eine Primzahl mit p | q.
Beweis: siehe [HUP1990] S.58f.
2-33
D
EFINITION
:
Sei
N
n
. Dann heißt das Element
*
n
a Z
mit
n
a
0
(für a gilt laut Definition, dass
(a, n) = 1 ist) quadratischer Rest mod n, falls es ein
*
n
x Z
gibt mit:
)
mod(
2
n
a
x
.
Den Wert x nennen wir die Quadratwurzel von a mod n.
2-34
B
EISPIEL
:
Die quadratischen Reste mod n = 5 sind 1 und 4, denn es gilt:
)
5
mod(
1
1
2
,
)
5
mod(
4
2
2
,
)
5
mod(
4
3
2
,
)
5
mod(
1
4
2
.
Die Zahlen 2 und 3 sind keine quadratischen Reste mod (5), weshalb wir solche Zahlen
quadratische Nichtreste nennen.
2-35
B
EMERKUNG
:
Die Schwierigkeit, die Quadratwurzel mod n zu berechnen, hängt entscheidend vom Modul n
ab. Falls n eine ungerade Primzahl ist, besitzt jede Zahl in
*
n
Z
entweder keine oder genau
zwei Quadratwurzeln. Für letzteren Fall gibt es schnelle Verfahren, welche die Quadratwur-
zel modulo n berechnen. Vergleiche dazu Beispiel 2-23 und Bemerkung 2-24.
Ist n dagegen eine zusammengesetzte Zahl, etwa das Produkt zweier verschiedener Prim-
zahlen, ist die Berechnung der Quadratwurzeln mod n im Allgemeinen sehr schwierig.
2.1
E
INIGE ZAHLENTHEORETISCHE
A
SPEKTE
17
2-36
B
EMERKUNG
:
Ist die Berechnung der Quadratwurzel mod n sehr schwierig, so interessiert uns zumindest,
ob eine Zahl ein quadratischer Rest ist oder nicht. Dazu benötigen wir die folgende Definiti-
on.
2-37
D
EFINITION
:
Es sei
3
p
Primzahl,
*
p
x Z
. Der Ausdruck
0
falls p durch x teilbar ist.
p
x
:=
1 falls
x quadratischer Rest mod p ist.
-1
falls
x quadratischer Nichtrest mod p ist.
heißt Legendre-Symbol
.
Es sei
N
n
mit kanonischer Primfaktorzerlegung
n
p
p
v
p
n
|
)
(
und
*
n
x Z
, für das nach
Definition (x, n) = 1 gilt. Dann heißt
n
p
p
v
p
x
n
x
|
)
(
:
das Jakobi-Symbol.
In dem für uns interessanten Fall
pq
n
, p und q prim, ist das Jakobi-Symbol
n
x
dann
wie folgt definiert:
n
x :
p
x
q
x
2-38
B
EMERKUNG
:
Um zu entscheiden, ob eine Zahl x ein quadratischer Rest mod n ist oder nicht, müssen wir
zwei Fälle unterscheiden:
1. Es
sei
N
n
mit n = pq und p, q prim. Ferner sei
*
n
x Z
eine Zahl mit Jakobi-Symbol
1. In diesem Fall ist x ein quadratischer Nichtrest.
Begründung: Jeder quadratische Rest modulo n = pq muss quadratischer Rest mo-
dulo p und quadratischer Rest modulo q sein. In diesem Fall ist jeweils
eine dieser Aussagen nicht erfüllt.
2. Es
sei
N
n
mit n = pq und p, q prim. Ferner sei
*
n
x Z
eine Zahl mit Jakobi-Symbol
+1. In diesem Fall kann nichts darüber ausgesagt werden, ob x quadratischer Rest ist
oder nicht, weil
)
1
(
)
1
(
1
1
1
.
18 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
Vergleiche zu diesen Definitionen und zu weiterführenden Sätzen [BSW1995] S. 120f. und
[SCHB1997] S. 293f.
2-39
B
EISPIEL
:
Wir wollen die Quadratwurzeln modulo p für den Fall
p
x
mod
1
2
mit p einer ungeraden
Primzahl berechnen. Mit dem Legendre-Symbol wissen wir, dass die Gleichung genau im
Fall
4
mod
1
p
lösbar ist. Die zyklische Gruppe
*
p
F
hat die Ordnung
m
p
4
1
, demnach
liegen die 4-ten Einheitswurzeln alle in
p
F
:
i
,
1
mit
p
F
i
die Gleichung
0
1
2
i
erfüllt.
Wir suchen also entweder i bzw. i. Nun ist die Abbildung
4
1
*
,
,
,
1
,
1
:
p
p
x
x
i
i
F
ein Gruppenhomomorphismus. Wählen wir zufällig
*
p
F
y
, so gilt
5
,
0
)
|
)
(
(
*
p
F
y
i
y
W
.
Die Wahrscheinlichkeit dafür, dass
i
y
)
(
ist, beträgt demnach 0,5. Nach einigen Versu-
chen werden wir also eine Lösung der Gleichung
p
x
mod
1
2
herausgefunden haben.
2-40
B
EMERKUNG
:
Die Idee des Algorithmus zur Berechnung der Quadratwurzel modulo p funktioniert nach fol-
gender Idee:
Es sei
3
p
eine Primzahl und
*
p
F
a
. Wir wissen, dass das Legendre-Symbol für
1
p
a
ist. Es sollen nun Folgen
*
,
p
i
i
F
x
b
derart konstruiert werden, dass
2
i
i
x
ab
gilt und
i
b
ge-
gen 1 konvergiert. Wir erhalten dann ein x mit
2
x
a
.
Vergleiche dazu [RUP1998] S. 95f.
2.2
E
INIGE KRYPTOGRAFISCHE
A
SPEKTE
19
2.2 Einige kryptografische Aspekte
,,[...] cryptography is the art
of sending private messages
over an unsecure channel [...]"
[ENG1998]
2.2.1 Terminologie
2-41
B
EMERKUNG
:
Begriffe wie Kryptologie, Verschlüsselung oder Datensicherheit umgeben mehr denn je un-
seren Alltag. Vor einigen Jahren hätten wir zu diesen Begriffen sicherlich fiktive ,,Sciencefic-
tion-Filme" assoziiert. In der heutigen Entwicklung fortschreitender weltweiter Vernetzung
verstehen wir unter Kryptologie die Wissenschaft, die sich mit Verschlüsselungsverfahren
beschäftigt, mit dem Ziel, Informationen vor ungebetenen Dritten schützen zu können.
Die Kryptologie gliedert sich in zwei Teilgebiete, die elementar wichtig füreinander sind: Die
Kryptografie entwickelt Verschlüsselungsverfahren, um Datenschutz zu gewährleisten. Die
Kryptanalyse hingegen versucht, diese Verfahren auf ihre Sicherheit zu überprüfen, m.a.W.
eine verschlüsselte Information zu brechen und lesbar zu machen. ,,Theoretisch beweisbare
und gleichzeitig praktisch nutzbare Sicherheit ist immer noch der Wunschtraum aller Krypto-
logen." [WOB1997] S. 11. Daher ist es wichtig, dass wir stets die Stärken und Schwächen
der verwendeten kryptografischen Verfahren kennen.
In der Literatur werden die Begriffe Kryptologie und Kryptografie weitestgehend synonym
gebraucht.
Dazu wollen wir zunächst einige grundlegende Begriffe einführen:
2-42
D
EFINITION
:
Ein Algorithmus ist eine ,,[...] der Reihenfolge nach eindeutig festgelegte Sequenz von end-
lich vielen ´elementaren´ Operationen [...], mit denen aus gewissen Eingabedaten die Lö-
sung eines Problems berechnet kann" [STÖ1994] S. 10.
Die mathematischen Funktionen, die im weitesten Sinn zum Ver- und Entschlüsseln verwen-
det werden, bezeichnen wir auch als Algorithmen.
Unter der Laufzeit oder der ,,running time" eines Algorithmus bzgl. eines Inputs verstehen
wir die Zahl der Basisoperationen oder ,,Schritte", die für den Algorithmus bzgl. dieses Inputs
ausgeführt werden müssen. Ein ,,Schritt" bedeutet oft eine Bit-Operation; manchmal er-
scheint es auch sinnvoll, einen ,,Schritt" mit Maschinenzeit oder ähnlichem zu vergleichen.
Die sogenannte ,,Laufzeit im schlimmsten Fall" oder ,,worst-case running time" eines Algo-
rithmus ist eine obere Grenze der Laufzeit zu jedem Input, ausgedrückt durch eine Funktion
der Eingabegröße.
2-43
D
EFINITION
:
Ein Protokoll regelt eine festgelegte Abfolge verschiedener Aktionen zwischen mindestens
zwei Parteien. Der Sinn eines Protokolls besteht darin, eine vorgegebene Aufgabe, eine Ab-
frage oder eine Kommunikation genormt durchzuführen.
20 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
Anschaulich lässt sich ein Protokoll als Flussdiagramm darstellen, welches von oben nach
unten durchlaufen wird. Die nächste Ebene dieses Diagramms kann erst dann durchlaufen
werden, wenn die vorherige abgeschlossen ist.
Weitere wichtige Anforderungen an ein Protokoll:
Alle am Protokoll teilnehmenden Parteien kennen das Protokoll und alle Aktionen im Vo-
raus.
Die Parteien halten sich an die vom Protokoll festgelegten Regeln.
Jede Aktion ist vollständig, klar und ohne Missverständnisse definiert.
Es sollte unmöglich sein, mehr über das Protokoll zu erfahren oder mehr zu interagieren,
als im Protokoll selbst festgelegt ist.
Vergleiche dazu [SCHB1997] S. 25ff., [BSW1995], S.4f.
2-44
D
EFINITION
:
Unter einem kryptografischen Verschlüsselungssystem
)
,
,
(
K
C
P
S
verstehen wir im
Folgenden:
eine
Menge
M
(engl.: message), bzw. P (engl.: plaintext): Diese enthält die zu ver-
schlüsselnden Informationen wie digitale Bilder, Tonsequenzen oder Nachrichten.
eine
Menge
C von Chiffretexten (engl.: ciphertext): Dies ist die Menge aller verschlüssel-
ten Informationen.
eine
Menge
K (engl.: keys), die alle Schlüssel, die in
S
eingesetzt werden. Die Ver-
schlüsselung erfolgt über Chiffrierfunktionen E:
C
K
M
(engl.: encryption) und die
Entschlüsselung über Dechiffrierfunktionen D:
M
K
C
(engl.: decryption). Alle Funk-
tionen
D
d
E
e
und
sind eindeutig.
Dabei gilt:
m
k
k
m
E
D
)
),
,
(
(
2
1
für alle
M
m
und
K
k
k
2
1
,
.
Die beiden Schlüssel
2
1
, k
k
sind die beiden korrespondierenden Schlüssel, demnach die
Schlüssel der an einer Korrespondenz teilnehmenden Parteien.
Sind diese beiden identisch oder leicht voneinander abzuleiten, so sprechen wir von sym-
metrischen Kryptosystemen
.
Sender und Empfänger müssen zunächst einen geheimen
Schlüssel (secret key) vereinbaren, bevor sie verschlüsselt kommunizieren können. Darin
liegt jedoch meist die Schwierigkeit für beide Parteien, denn bereits dieser Schlüsselaus-
tausch muss sicher und geheim erfolgen. Die Sicherheit solcher Systeme liegt daher in der
Geheimhaltung dieses Schlüssels.
Sind diese beiden Schlüssel jedoch unterschiedlich, bzw. ist es in annehmbarer Zeit unmög-
lich, aus der Kenntnis eines Schlüssels den anderen Schlüssel oder die Nachricht herzulei-
ten, so sprechen wir von asymmetrischen
oder
Public Key-Kryptosystemen. In diesem
Fall ist der Chiffrierschlüssel (öffentlicher Schlüssel) öffentlich bekannt, so dass jeder Sender
eine Nachricht damit verschlüsseln kann.
2.2
E
INIGE KRYPTOGRAFISCHE
A
SPEKTE
21
Jedoch kann nur die Person, die den korrespondierenden Dechiffrierschlüssel (privater
Schlüssel) besitzt, diese Nachricht entschlüsseln.
Vergleiche hierzu: [SCHB1997], S. 1-10, [WOB1997] S. 105ff.
A
BBILDUNG
2-1:
Funktionsschema einer Verschlüsselung
2-45
D
EFINITION
:
Eine versuchte Kryptanalyse heißt Angriff. Nach dem Kerckhoffschen Prinzip ist davon
auszugehen, dass der Angreifer alle Einzelheiten des kryptografischen Algorithmus und des-
sen Implementation kennt.
Generell lassen sich folgende Angriffe voneinander unterscheiden:
a.)
Ciphertext-only-Angriff:
Der Angreifer verfügt über eine begrenzte Zahl an Chiffretexten, die mit demselben
Verschlüsselungsalgorithmus chiffriert wurden. Der Angreifer versucht damit nun, mög-
lichst viele zugehörige Klartexte herzustellen oder den verwendeten Schlüssel zu be-
rechnen.
b.)
Known-Plaintext-Angriff:
Der Angreifer verfügt nicht nur über eine begrenzte Zahl an Chiffretexten, sondern
auch über dazu gehörende Klartexte. Der Angreifer versucht damit nun, verwendete
Schlüssel zu berechnen oder einen Algorithmus zu finden, mit dem weitere Nachrich-
ten dechiffriert werden können.
c.)
Chosen-Plaintext-Angriff:
Der Angreifer verfügt nicht nur über eine begrenzte Zahl an Chiffretexten und zugehö-
riger Klartexte, sondern er kennt auch die Verschlüsselungsfunktion f . So kann er be-
stimmte, von ihm ausgewählte Klartexte verschlüsseln. Der Angreifer versucht damit
nun, den verwendeten Schlüssel zu berechnen oder einen Algorithmus zu finden, mit
dem weitere Nachrichten dechiffriert werden können.
d.)
Chosen-Ciphertext-Angriff:
Der Angreifer verfügt nicht nur über eine begrenzte Zahl an Chiffretexten und zugehö-
riger Klartexte, sondern er kennt auch die Entschlüsselungsfunktion
*
f
. So kann er
bestimmte, von ihm ausgewählte Chiffretexte entschlüsseln. Der Angreifer versucht
damit nun, den verwendeten Schlüssel zu berechnen oder einen Algorithmus zu fin-
den, mit dem weitere Nachrichten dechiffriert werden können.
Klartext
Chiffretext
Klartext
Verschlüsselung
Entschlüsselung
Dechiffrierschlüssel
Chiffrierschlüssel
22 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
2-46
D
EFINITION
:
Da sich Algorithmen in der Rechenkapazität erheblich voneinander unterscheiden, ist die
Komplexität eines Algorithmus, oder die Komplexität eines Angriffs verschieden. Die
sogenannte Komplexitätstheorie analysiert den Berechnungsaufwand verschiedener krypto-
grafischer Verfahren und untersucht so, wie sicher diese sind.
Nach Bruce Schneier [SCHB1998] S.9f. können wir diese Komplexität nach verschiedenen
Kriterien unterteilen:
Berechnungskomplexität: Wieviel Zeit ist notwendig, um den Angriff durchzuführen?
Datenkomplexität:
Wie viele Daten müssen eingegeben werden, um einen Angriff
durchzuführen?
Speicherkomplexität:
Wieviel Speicher benötigt der Angriff?
Quelle: [SCHB1997] S. 9
T
ABELLE
2-3:
Komplexität eines Algorithmus
In der Regel sollte die gesamte Komplexität eines Angriffs durch das Minimum dieser Teil-
komplexitäten abgeschätzt werden.
Leider ist es meist einfacher, Verfahren durch Angriffe als unsicher zu entlarven, als zu be-
weisen, dass Verfahren sicher sind.
2-47
B
EMERKUNG
:
Bei der Beschreibung der Komplexität von Algorithmen interessieren uns im Allgemeinen
konstante Faktoren weniger, da sie sehr stark von der Struktur der Algorithmen abhängen
und sich mit fortschreitender Technik stets ändern. Deshalb führen wir im Folgenden eine
Notation ein, die diese konstanten Faktoren unterdrückt.
2-48
D
EFINITION
:
Um Laufzeiten von Algorithmen zu vergleichen, nutzen wir die standardisierte asymptoti-
sche Notation.
Es sei n eine natürliche Zahl und f(n) eine monoton wachsende Funktion. Der Ausdruck
))
(
(
)
(
n
g
O
n
f
kennzeichnet eine obere Grenze von f(n), die durch eine Funktion g(n) be-
schrieben wird. Genauer:
Ein Algorithmus f besitzt die Komplexität O(g(n)), wenn es eine positive Konstante c und ein
N
0
n
gibt, so dass
)
(
)
(
0
n
cg
n
f
für alle
0
n
n
gilt. Anschaulich bedeutet dies, dass f
nicht schneller asymptotisch als g wächst.
Ein Algorithmus f besitzt die Komplexität o(g(n)), wenn für jede positive Konstante c ein
N
0
n
existiert, so dass
)
(
)
(
0
n
cg
n
f
für alle
0
n
n
gilt.
2.2
E
INIGE KRYPTOGRAFISCHE
A
SPEKTE
23
2-49
B
EMERKUNG
:
Beim Rechnen mit asymptotischen Notationen gelten unter anderem folgende Rechenregeln.
Es seien
N
n
,
))
(
(
)
(
1
1
n
g
O
n
f
und
))
(
(
)
(
2
2
n
g
O
n
f
. Dann gilt:
a.)
))
(
(
)
(
1
1
n
f
O
n
f
(Reflexivität),
b.) Falls
gilt
))
(
(
)
(
1
1
n
g
O
n
f
und
))
(
(
)
(
1
1
n
h
O
n
g
, dann gilt:
))
(
(
)
(
1
1
n
h
O
n
f
(Transiti-
vität),
c.)
))
(
),
(
(max(
)
(
)
(
2
1
2
1
n
g
n
g
O
n
f
n
f
,
d.)
))
(
)
(
(
)
(
)
(
2
1
2
1
n
g
n
g
O
n
f
n
f
.
2-50
D
EFINITION
:
Die Komplexität eines Verschlüsselungsverfahrens wird meist als Funktion der Eingabe-
größe n betrachtet. Dies ist sehr wichtig, da uns vor allem interessiert, wie sich ein Algorith-
mus verhält, wenn der Dateninput wächst. Einen Algorithmus nennen wir dann
konstant, wenn seine Laufzeit im schlimmsten Fall O (1) ist.
linear, wenn seine Laufzeit im schlimmsten Fall O (n) ist, wobei n die Größe des Inputs
ist.
polynomiell, wenn seine Laufzeit im schlimmsten Fall O (
m
n
) ist. Dabei ist m eine Kon-
stante und n die Größe des Inputs.
exponentiell, wenn seine Laufzeit im schlimmsten Fall durch
)
(
)
(n
f
t
O
beschrieben wer-
den kann. Dabei ist t eine Konstante größer 1 und f(n) eine polynomielle Funktion von n.
subexponentiell, wenn seine Laufzeit im schlimmsten Fall
)
(
))
)
(ln
)
1
(
(
1
n
n
o
c
e
O
ist. Dabei
ist c eine positive Konstante und
eine Kostante mit
1
0
.
Für
0
ist die Laufzeit demnach polynomiell, für
1
ist sie exponentiell.
KLASSEN
KOMPLEXITÄT ANZAHL DER
OPERATIONEN
BEI n =
6
10
LAUFZEIT BEI
6
10
OPERATIONEN/SEK.
Konstant O
(1)
1
1
.
Sek
Linear O
(n)
6
10
1 Sek.
Quadratisch O (
2
n
)
12
10
11,6 Tage
Kubisch
O (
3
n
)
18
10
32000 Jahre
Exponentiell O (
n
2
)
301030
10
301006
10
mal das Alter des Universums
Quelle: [SCHB1997] S. 9
T
ABELLE
2-4:
Laufzeit verschiedener Klassen von Algorithmen
24 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
Ein mathematisches Problem können wir dann als ,,schwierig zu brechen bezeichnen, wenn
selbst der beste Angriff zuviel Zeit in Abhängigkeit vom Input benötigt. Im Idealfall könnte
demnach ein Kryptograf von seinem Verschlüsselungsverfahren behaupten, dass es sicher
ist, wenn ein Angriff auf sein Verfahren von exponentieller Komplexität ist.
Ein subexponentieller Algorithmus kann als ,,schwierig zu brechen betrachtet werden, bietet
jedoch nicht die Sicherheit eines exponentiellen Algorithmus.
2-51
B
EMERKUNG
:
In dieser Bemerkung wollen wir kurz darauf eingehen, wie diese unterschiedlichen Komplexi-
täten zustande kommen.
a.)
Die Komplexität von Algorithmen, die auf einer natürlichen Zahl a operieren, ist ab-
hängig von der Größe (Länge) von a. Diese ist
a
a
lg
|
|
.
Wie lange benötigen die Basisoperationen? Abhängig von der Anzahl der Bits k in ei-
ner Zahl, können wir folgendes festhalten:
- Eine
Addition ist von linearer Komplexität. Zwei k-Bit Zahlen können in der Zeit
O(k) addiert werden.
- Eine
Multiplikation ist von quadratischer Komplexität
)
(
2
k
O
. Die Multiplikation
zweier Zahlen a und b benötigt
|)
|
|
(|
b
a
O
Bit Operationen.
- Eine
Division ist ebenfalls von quadratischer Komplexität. Eine Division von a
durch b benötigt die Zeit
))
|
|
)
|
|
1
((
b
q
O
.
b.)
Betrachten wir entsprechende modulare Operationen, so ergibt sich folgendes:
- Es
seien
N
n
und
n
b
a
Z
,
. Eine Addition der Art
)
(mod
n
b
a
ist nun eben-
falls von linearer Komplexität. Zwei k-Bit Zahlen können wiederum in der Zeit O(k)
addiert werden.
Anschaulich gesprochen können wir ,,über den Modul nicht hinausgehen". Falls
doch, müssten wir ,,n subtrahieren". Eine Subtraktion ist ebenfalls von linearer
Komplexität.
- Der
Ausdruck
a mod n bedeutet per Definition, ,,a durch n zu teilen und den Rest
als Lösung zu nehmen". Dieser Vorgang ist von quadratischer Komplexität.
- Eine
Multiplikation von a und b modulo n ist wiederum von quadratischer Komple-
xität. Werden a und b zunächst multipliziert, benötigen wir
|)
|
|
(|
b
a
O
Bit Opera-
tionen. Das Ergebnis ist dann durch n zu teilen. ,,Der Rest wird als Lösung ge-
nommen." Dieser Schritt ist von quadratischer Komplexität, daher auch der ge-
samte Ausdruck.
c.)
Die wichtigste Basisoperation in der Public Key-Kryptografie ist die Exponentiation.
Es seien
N
n
,
n
a Z
und
Z
m
. Dann verstehen wir unter einer Exponentiation
den Ausdruck
n
a
m
mod
.
2.2
E
INIGE KRYPTOGRAFISCHE
A
SPEKTE
25
Es gibt einen Algorithmus, der diese Operation in kubischer Komplexität
)
(
3
k
O
be-
rechnet, wobei
|
|
n
k
ist. Dieser Algorithmus nutzt 2k modulare Multiplikationen von
k-Bit Zahlen.
Um diesen zu verstehen, betrachten wir als Beispiel die Berechnung von
22
mod
2
21
:
Der naive Weg würde 21 Multiplikationen benötigen.
Dieser Algorithmus wiederholt dagegen eine Quadrierung:
1
2
)
22
(mod
2
,
2
2
)
22
(mod
4
,
4
2
)
22
(mod
16
,
8
2
)
22
(mod
14
,
16
2
)
22
(mod
20
.
Daraus ergibt sich:
)
21
(mod
10
2
4
20
2
2
2
2
2
1
4
16
1
4
16
21
.
2.2.2 Einweg- und Hashfunktionen
2-52
B
EMERKUNG
:
Die Sicherheit heutiger Public Key-Kryptosysteme beruht auf mathematischen Problemen,
die mit heutigen Mitteln extrem schwer zu berechnen sind. Diese Probleme bestehen aus
sogenannten Einwegfunktionen, die leicht ausgeführt, aber nur schwer umgekehrt werden
können.
Unter einer Einwegfunktion
verstehen wir eine Funktion f : X
Y, die einfach ausgeführt
werden kann, ihre Umkehrung jedoch fast unmöglich ist oder mit enormen Aufwand verbun-
den ist. Etwas genauer:
Ist ein beliebiges
X
x
vorgegeben, so ist f (x) = y einfach zu berechnen.
Ist jedoch ein
Y
y
vorgegeben, so kann ein zugehöriges Urbild
X
x
mit
)
(
x
f
y
nur mit enormem Aufwand berechnet werden.
Mathematisch gibt es aufgrund des heutigen Stands der Komplexitätstheorie keinen Beweis
dafür, dass Einwegfunktionen existieren, oder, dass sie konstruiert werden können. Den-
noch bildet die Einwegfunktion einen weiteren wichtigen Baustein vieler kryptografischer
Protokolle. Die Kryptografie baut darauf auf, dass die Umkehrung von Einwegfunktionen den
starken Restriktionen der Zeit und der Effizienz von Computersystemen unterliegt.
Vergleiche zu diesem Abschnitt: [BSW1995], S.12ff., [SCHB1997], S. 34ff./S. 406f. und
[GB1997], S.14ff.
Im Folgenden wollen wir eine exakte Definition für die Begriffe ,,einfach" und ,,fast unmöglich"
für Einwegfunktionen beschreiben.
26 K
APITEL
2:
E
INIGE
G
RUNDLAGEN
2-53
D
EFINITION
:
a.) Ein Problem ist einfach oder berechenbar, wenn es durch einen probabilistischen
1
Al-
gorithmus in polynomieller Zeit (Probabilistic Polynomial Time Algorithm, PPT) gelöst
werden kann.
Probleme, die nicht in polynomieller Laufzeit gelöst werden können, bezeichnen wir als
schwierig oder nicht berechenbar.
b.) Es sei
eine Funktion. Wir bezeichnen
als vernachlässigbar, wenn für jede Kon-
stante
0
c
eine ganze Zahl
c
k
existiert, so dass
c
k
k
)
(
für alle
c
k
k
. Eine ver-
nachlässigbare Funktion verschwindet demnach schneller als das Inverse jedes Poly-
noms.
c.) Eine Funktion
bezeichnen wir als nicht vernachlässigbar, wenn ein Polynom p exis-
tiert, so dass für alle hinreichend großen k gilt:
)
(
1
)
(
k
p
k
.
2-54
B
EMERKUNG
:
Übertragen auf Einwegfunktionen bedeutet dies: Jeder PPT-Algorithmus, der versucht eine
Einwegfunktion zu invertieren, wird dabei nur mit einer vernachlässigbaren Wahrscheinlich-
keit erfolgreich sein.
Das Gegenteil würde bedeuten, dass dieser Versuch in polynomieller Zeit ausführbar wäre.
2-55
D
EFINITION
:
Eine Funktion
*
*
1
,
0
1
,
0
:
f
bezeichnen wir als Einwegfunktion, falls gilt:
a.)
Es existiert ein PPT-Algorithmus , der für den Input
2
*
1
,
0
x
den Output f(x) aus-
gibt.
b.) Es
seien
N
k
und
k
x
1
,
0
zufällig gewählt (,,random"). Die Länge von x ist dem-
nach k. Sei
k
y
1
,
0
der Output von f(x). Für jeden PPT-Algorithmus A gibt es eine
vernachlässigbare Funktion
A
, so dass für alle hinreichend großen k gilt:
)
(
)]
(
);
(
;
1
,
0
|
)
(
[
k
y
A
z
x
f
y
x
y
z
f
W
A
k
R
.
In Worten formuliert bedeutet dies:
Die Wahrscheinlichkeit W dafür, dass y Output der Funktion f mit Input z ist unter der
Bedingung A(y) = z, ist kleiner als eine vernachlässigbare Funktion.
2-56
B
EMERKUNG
:
a.)
Obige Definition besagt nicht, dass es unmöglich ist, die Funktion f zu invertieren. Die
Wahrscheinlichkeit dafür ist aber sehr klein, sogar kleiner gleich einer vernachlässig-
bare Funktion. Für einen Angreifer besteht aber immer die Möglichkeit, eine richtige
Invertierung zu erraten.
1
Vergleiche dazu: [SCHB1997] S.629ff, [GB1997] S. 14ff.
2
Dieser Ausdruck legt keine feste Länge für x fest.
Excerpt out of 191 pages
- Quote paper
- René Algesheimer (Author), 2000, Elliptische Kurven als alternatives Public Key-Verfahren im Homebanking-Standard HBCI, Munich, GRIN Verlag, https://www.grin.com/document/185454
Similar texts
Publish now - it's free
✕
Excerpt from
191
pages
Comments