Sicherheitsaspekte kryptographischer Verfahren beim Homebanking
©2002
Diplomarbeit
83 Seiten
Zusammenfassung
Inhaltsangabe:Zusammenfassung:
In der vorliegenden Arbeit werden kryptographische Verfahren und Protokolle vorgestellt, die im HBCI-Standard zum Einsatz kommen. Das Hauptaugenmerk liegt hierbei auf den derzeit verwendeten Algorithmen DES und RSA sowie deren möglichen Nachfolgern Rijndael und ElGamal mit elliptischen Kurven. Die dafür notwendigen mathematischen Grundlagen werden ebenso wie die grundlegenden Begriffe der Kryptographie eingeführt. Es wird auf Sicherheitsaspekte der untersuchten Algorithmen und auf die zukünftige Entwicklung eingegangen. Dabei stellt sich heraus, daß mit den benutzten Verfahren die Sicherheit der Kommunikationspartner nur unwesentlich bis gar nicht beeinträchtigt werden kann. Beim praktischen Einsatz existieren aber noch Lücken, die für einen Angriff ausgenutzt werden können.
Inhaltsverzeichnis:Inhaltsverzeichnis:
1.Einleitung1
2.Mathematische Grundlagen3
2.1Hilfsmittel aus der Zahlentheorie3
2.1.1Komplexität von Algorithmen3
2.1.2Der Euklidische Algorithmus5
2.1.3Der Chinesische Restsatz7
2.1.4Der Satz von Euler-Fermat8
2.1.5Galoisfelder9
2.2Einwegfunktionen9
2.2.1Faktorisierung natürlicher Zahlen9
2.2.2Der diskrete Logarithmus10
2.2.3Nichtlineare Transformationen11
2.3Erzeugung von Zufallszahlen11
2.3.1Zufallszahlengeneratoren11
2.3.2Kongruenzgeneratoren12
2.3.3Schieberegister14
2.3.4Weitere Generatoren14
2.4Primzahltests und Faktorisierung15
2.4.1Probedivision und Fermat-Test15
2.4.2Der Miller-Rabin-Test16
2.4.3Pollards Methode17
2.4.4Das Quadratische Sieb18
3.Kryptographische Grundlagen19
3.1Grundbegriffe19
3.1.1Kryptosysteme19
3.1.2Block- und Stromchiffren20
3.2Symmetrische Kryptosysteme23
3.2.1Cäsar-Chiffre und One-Time-Pad23
3.2.2Der DES-Algorithmus24
3.2.3Weitere Algorithmen27
3.3Asymmetrische Kryptosysteme29
3.3.1Einführende Bemerkungen29
3.3.2Der RSA-Algorithmus30
3.3.3Weitere Verfahren31
3.4Hashfunktionen32
3.4.1SHA32
3.4.2MD4 und seine Varianten32
3.4.3RIPEMD-16033
3.4.4MDC-233
3.4.5Message Authentication Codes34
3.5Digitale Signaturen34
3.5.1RSA-Signaturen34
3.5.2ElGamal-Signaturen und DSA34
3.6Kryptographische Protokolle35
3.6.1Festcodes und Wechselcodes35
3.6.2Bidirektionale Protokolle36
3.6.3Weitere Protokolle37
4.Angriffe auf Kryptosysteme39
4.1Angriffe auf Kryptosysteme39
4.1.1Angriffsklassen39
4.1.2Brute-Force-Angriff40
4.1.3Kryptanalyse41
4.2Angriffe auf Protokolle42
4.2.1Einfache Angriffe42
4.2.2Arglistige Täuschung42
4.3Schwachstelle […]
In der vorliegenden Arbeit werden kryptographische Verfahren und Protokolle vorgestellt, die im HBCI-Standard zum Einsatz kommen. Das Hauptaugenmerk liegt hierbei auf den derzeit verwendeten Algorithmen DES und RSA sowie deren möglichen Nachfolgern Rijndael und ElGamal mit elliptischen Kurven. Die dafür notwendigen mathematischen Grundlagen werden ebenso wie die grundlegenden Begriffe der Kryptographie eingeführt. Es wird auf Sicherheitsaspekte der untersuchten Algorithmen und auf die zukünftige Entwicklung eingegangen. Dabei stellt sich heraus, daß mit den benutzten Verfahren die Sicherheit der Kommunikationspartner nur unwesentlich bis gar nicht beeinträchtigt werden kann. Beim praktischen Einsatz existieren aber noch Lücken, die für einen Angriff ausgenutzt werden können.
Inhaltsverzeichnis:Inhaltsverzeichnis:
1.Einleitung1
2.Mathematische Grundlagen3
2.1Hilfsmittel aus der Zahlentheorie3
2.1.1Komplexität von Algorithmen3
2.1.2Der Euklidische Algorithmus5
2.1.3Der Chinesische Restsatz7
2.1.4Der Satz von Euler-Fermat8
2.1.5Galoisfelder9
2.2Einwegfunktionen9
2.2.1Faktorisierung natürlicher Zahlen9
2.2.2Der diskrete Logarithmus10
2.2.3Nichtlineare Transformationen11
2.3Erzeugung von Zufallszahlen11
2.3.1Zufallszahlengeneratoren11
2.3.2Kongruenzgeneratoren12
2.3.3Schieberegister14
2.3.4Weitere Generatoren14
2.4Primzahltests und Faktorisierung15
2.4.1Probedivision und Fermat-Test15
2.4.2Der Miller-Rabin-Test16
2.4.3Pollards Methode17
2.4.4Das Quadratische Sieb18
3.Kryptographische Grundlagen19
3.1Grundbegriffe19
3.1.1Kryptosysteme19
3.1.2Block- und Stromchiffren20
3.2Symmetrische Kryptosysteme23
3.2.1Cäsar-Chiffre und One-Time-Pad23
3.2.2Der DES-Algorithmus24
3.2.3Weitere Algorithmen27
3.3Asymmetrische Kryptosysteme29
3.3.1Einführende Bemerkungen29
3.3.2Der RSA-Algorithmus30
3.3.3Weitere Verfahren31
3.4Hashfunktionen32
3.4.1SHA32
3.4.2MD4 und seine Varianten32
3.4.3RIPEMD-16033
3.4.4MDC-233
3.4.5Message Authentication Codes34
3.5Digitale Signaturen34
3.5.1RSA-Signaturen34
3.5.2ElGamal-Signaturen und DSA34
3.6Kryptographische Protokolle35
3.6.1Festcodes und Wechselcodes35
3.6.2Bidirektionale Protokolle36
3.6.3Weitere Protokolle37
4.Angriffe auf Kryptosysteme39
4.1Angriffe auf Kryptosysteme39
4.1.1Angriffsklassen39
4.1.2Brute-Force-Angriff40
4.1.3Kryptanalyse41
4.2Angriffe auf Protokolle42
4.2.1Einfache Angriffe42
4.2.2Arglistige Täuschung42
4.3Schwachstelle […]
Leseprobe
Inhaltsverzeichnis
ID 5579
Nöbel, Lars: Sicherheitsaspekte kryptographischer Verfahren beim Homebanking /
Lars Nöbel - Hamburg: Diplomica GmbH, 2002
Zugl.: Leipzig, Universität, Diplomarbeit, 2002
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 2002
Printed in Germany
Abstract
In der vorliegenden Arbeit werden kryptographische Verfahren und Proto-
kolle vorgestellt, die im HBCI-Standard zum Einsatz kommen. Das Haupt-
augenmerk liegt hierbei auf den derzeit verwendeten Algorithmen DES und
RSA sowie deren m¨oglichen Nachfolgern Rijndael und ElGamal mit ellipti-
schen Kurven. Die daf¨ur notwendigen mathematischen Grundlagen werden
ebenso wie die grundlegenden Begriffe der Kryptographie eingef¨uhrt. Es wird
auf Sicherheitsaspekte der untersuchten Algorithmen und auf die zuk¨unftige
Entwicklung eingegangen. Dabei stellt sich heraus, daß mit den benutzten
Verfahren die Sicherheit der Kommunikationspartner nur unwesentlich bis
gar nicht beeintr¨achtigt werden kann. Beim praktischen Einsatz existieren
aber noch L¨ucken, die f¨ur einen Angriff ausgenutzt werden k¨onnen.
Inhaltsverzeichnis
1 Einleitung
1
2 Mathematische Grundlagen
3
2.1 Hilfsmittel aus der Zahlentheorie . . . . . . . . . . . . . . . .
3
2.1.1
Komplexit¨at von Algorithmen . . . . . . . . . . . . . .
3
2.1.2
Der Euklidische Algorithmus . . . . . . . . . . . . . . .
5
2.1.3
Der Chinesische Restsatz . . . . . . . . . . . . . . . . .
7
2.1.4
Der Satz von Euler-Fermat . . . . . . . . . . . . . . . .
8
2.1.5
Galoisfelder . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2 Einwegfunktionen . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.1
Faktorisierung nat¨urlicher Zahlen . . . . . . . . . . . .
9
2.2.2
Der diskrete Logarithmus . . . . . . . . . . . . . . . . 10
2.2.3
Nichtlineare Transformationen . . . . . . . . . . . . . . 11
2.3 Erzeugung von Zufallszahlen . . . . . . . . . . . . . . . . . . . 11
2.3.1
Zufallszahlengeneratoren . . . . . . . . . . . . . . . . . 11
2.3.2
Kongruenzgeneratoren . . . . . . . . . . . . . . . . . . 12
2.3.3
Schieberegister . . . . . . . . . . . . . . . . . . . . . . 14
2.3.4
Weitere Generatoren . . . . . . . . . . . . . . . . . . . 14
2.4 Primzahltests und Faktorisierung . . . . . . . . . . . . . . . . 15
2.4.1
Probedivision und Fermat-Test . . . . . . . . . . . . . 15
2.4.2
Der Miller-Rabin-Test . . . . . . . . . . . . . . . . . . 16
2.4.3
Pollards Methode . . . . . . . . . . . . . . . . . . . . . 17
2.4.4
Das Quadratische Sieb . . . . . . . . . . . . . . . . . . 18
V
VI
INHALTSVERZEICHNIS
3 Kryptographische Grundlagen
19
3.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1
Kryptosysteme . . . . . . . . . . . . . . . . . . . . . . 19
3.1.2
Block- und Stromchiffren . . . . . . . . . . . . . . . . . 20
3.2 Symmetrische Kryptosysteme . . . . . . . . . . . . . . . . . . 23
3.2.1
C¨asar-Chiffre und One-Time-Pad . . . . . . . . . . . . 23
3.2.2
Der DES-Algorithmus . . . . . . . . . . . . . . . . . . 24
3.2.3
Weitere Algorithmen . . . . . . . . . . . . . . . . . . . 27
3.3 Asymmetrische Kryptosysteme
. . . . . . . . . . . . . . . . . 29
3.3.1
Einf¨uhrende Bemerkungen . . . . . . . . . . . . . . . . 29
3.3.2
Der RSA-Algorithmus . . . . . . . . . . . . . . . . . . 30
3.3.3
Weitere Verfahren . . . . . . . . . . . . . . . . . . . . . 31
3.4 Hashfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.1
SHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.2
MD4 und seine Varianten . . . . . . . . . . . . . . . . 32
3.4.3
RIPEMD-160 . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.4
MDC-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.5
Message Authentication Codes . . . . . . . . . . . . . . 34
3.5 Digitale Signaturen . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5.1
RSA-Signaturen . . . . . . . . . . . . . . . . . . . . . . 34
3.5.2
ElGamal-Signaturen und DSA . . . . . . . . . . . . . . 34
3.6 Kryptographische Protokolle . . . . . . . . . . . . . . . . . . . 35
3.6.1
Festcodes und Wechselcodes . . . . . . . . . . . . . . . 35
3.6.2
Bidirektionale Protokolle . . . . . . . . . . . . . . . . . 36
3.6.3
Weitere Protokolle . . . . . . . . . . . . . . . . . . . . 37
4 Angriffe auf Kryptosysteme
39
4.1 Angriffe auf Kryptosysteme . . . . . . . . . . . . . . . . . . . 39
4.1.1
Angriffsklassen . . . . . . . . . . . . . . . . . . . . . . 39
4.1.2
Brute-Force-Angriff . . . . . . . . . . . . . . . . . . . . 40
4.1.3
Kryptanalyse . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Angriffe auf Protokolle . . . . . . . . . . . . . . . . . . . . . . 42
4.2.1
Einfache Angriffe . . . . . . . . . . . . . . . . . . . . . 42
4.2.2
Arglistige T¨auschung . . . . . . . . . . . . . . . . . . . 42
4.3 Schwachstelle Benutzer . . . . . . . . . . . . . . . . . . . . . . 43
4.3.1
Sicherheit der Benutzerdaten . . . . . . . . . . . . . . . 43
4.3.2
Schutz der Benutzerdaten . . . . . . . . . . . . . . . . 44
INHALTSVERZEICHNIS
VII
5 Homebanking
45
5.1 Der HBCI-Standard . . . . . . . . . . . . . . . . . . . . . . . . 45
5.1.1
Beschreibung . . . . . . . . . . . . . . . . . . . . . . . 45
5.1.2
Ablauf des HBCI-Dialogs . . . . . . . . . . . . . . . . . 46
5.1.3
Sicherheitsmechanismen . . . . . . . . . . . . . . . . . 47
5.1.4
Signieren von Nachrichten . . . . . . . . . . . . . . . . 48
5.1.5
Verschl¨usselung von Nachrichten . . . . . . . . . . . . . 49
5.1.6
Erstinitialisierung DDV . . . . . . . . . . . . . . . . . 50
5.1.7
Erstinitialisierung RDH . . . . . . . . . . . . . . . . . 51
5.1.8
Sicherheitsmedien . . . . . . . . . . . . . . . . . . . . . 53
5.2 Schwachstellen des Protokolls . . . . . . . . . . . . . . . . . . 53
5.2.1
Kommunikation . . . . . . . . . . . . . . . . . . . . . . 53
5.2.2
Speicherung der Daten . . . . . . . . . . . . . . . . . . 54
5.3 Analyse der Angriffsm¨oglichkeiten . . . . . . . . . . . . . . . . 55
5.3.1
Allgemeine Angriffe . . . . . . . . . . . . . . . . . . . . 55
5.3.2
Angriffe auf das Protokoll . . . . . . . . . . . . . . . . 57
5.3.3
Angriffe auf Sicherheitsmedien . . . . . . . . . . . . . . 58
5.3.4
Angriffe auf Benutzer . . . . . . . . . . . . . . . . . . . 59
6 Weiterf¨
uhrende Betrachtungen
61
6.1 Neue kryptographische Algorithmen . . . . . . . . . . . . . . . 61
6.1.1
Advanced Encryption Standard . . . . . . . . . . . . . 61
6.1.2
Spezifikation von Rijndael (AES) . . . . . . . . . . . . 62
6.2 Weitere mathematische Methoden . . . . . . . . . . . . . . . . 66
6.2.1
Elliptische Kurven . . . . . . . . . . . . . . . . . . . . 66
6.2.2
EC-Kryptographie . . . . . . . . . . . . . . . . . . . . 69
7 Zusammenfassung
71
Abk¨
urzungsverzeichnis
bitweise Addition modulo 2
AES
Advanced Encryption Standard
ASCII
American Standard Code for Information Interchange
BBS
Bitgenerator nach Blum, Blum und Shub
BdB
Bundesverband deutscher Banken
CBC
Cipher-Block-Chaining-Modus
CFB
Cipher-Feedback-Modus
CID
Cardholders Information Data
DDV
DES-DES-Verfahren
DES
Data Encryption Standard
DSA
Digital Signature Algorithm
ECB
Electronic-Codebook-Modus
ECM
Faktorisierungsmethode mit elliptischen Kurven
(engl. elliptic curve factoring method)
EXPTIME
Komplexit¨atsklasse (exponentieller Zeitaufwand)
gcd(a, b)
gr¨oßter gemeinsamer Teiler von a und b
(engl. greatest common divisor)
GF(p
n
)
Galoisfeld der Ordnung p
n
HBCI
Homebanking Computer Interface
IDEA
International Data Encryption Algorithm
IFX
International Financial Exchange
IP
Internet Protocol
IPSEC
IP Security Protocol
ISO
International Standardization Organization
IV
Initialisierungsvektor
MAC
Message Authentication Code
MDC
Modification Detection Code
MDx
Message Digest x
MOV
Algorithmus von Menezes, Okamoto und Vanstone
IX
X
ABK ¨
URZUNGSVERZEICHNIS
Menge der nat¨
urlichen Zahlen
NFS
Zahlk¨orpersieb (engl. number field sieve)
NIST
National Institute of Standards and Technology
NP
Komplexit¨atsklasse (nichtdeterministisch polynomial)
NSA
National Security Agency
O()
Ordnung (Landau'sches O-Symbol)
OFB
Output-Feedback-Modus
OFX
Open Financial Exchange
P
Komplexit¨atsklasse (polynomialer Zeitaufwand)
PIN
Pers¨onliche Identifizierungsnummer
PSPACE
Komplexit¨atsklasse (polynomialer Speicherbedarf)
QS
Quadratisches Sieb
RACE
Research and Development in
Advanced Communication Technologies
RCx
Rivest Cipher x
RDH
RSA-DES-Hybridverfahren
RIPE
RACE Integrity Primitives Evaluation
RSA
Kryptosystem von Rivest, Shamir und Adleman
SHA
Secure Hash Algorithm
SSL
Secure Sockets Layer
SSSA
Algorithmus von Smart, Semaev, Satoh und Araki
TAN
Transaktionsnummer
TCP
Transmission Control Protocol
Menge der ganzen Zahlen
ZKA
Zentraler Kreditausschuß
Kapitel 1
Einleitung
"
In its simplest and most ancient form, cryptography is the pro-
blem of secure message exchange over insecure channels."
Shafi Goldwasser
"
Die besten Traktate ¨uber Kryptographie sind Werke ungl¨aubiger
Gelehrter. [ . . . ] Es gibt keine Geheimschrift, die sich nicht mit ein
wenig Geduld entziffern ließe!"
Umberto Eco in
"
Der Name der Rose"
Kryptographie ist die Lehre von den Problemen der Datensicherheit und
den Techniken, die zur Realisierung der Datensicherheit verwendet werden.
Die Grundlagen der heutigen Kryptographie sind schon seit l¨angerem er-
forscht, eine große Anzahl von Algorithmen zur Anwendung in der Praxis
wurde bereits entwickelt und wird heutzutage in sehr vielen Bereichen einge-
setzt. Trotzdem erfreut sich dieses Fachgebiet in der Forschung immer noch
großer Beliebtheit, denn alle bisherigen Ergebnisse k¨onnen nur eine zeitweili-
ge Sicherheit garantieren. Schon in naher Zukunft kann es passieren, daß ein
Verfahren entdeckt wird, welches die bestehenden Verschl¨usselungstechniken
unsicher macht. Auch die in der Praxis eingesetzten Protokolle sch¨utzen die
Benutzer nicht zwangsl¨aufig vor Angriffen, die Fahrl¨assigkeit eines Einzelnen
kann zu Sicherheitsl¨ucken im gesamten Kommunikationssystem f¨uhren. Die
Analyse von Angriffen auf vielfach eingesetzte Algorithmen und Protokolle
ist Ziel dieser Arbeit.
1
2
KAPITEL 1. EINLEITUNG
Die Grundlagen f¨ur diese Arbeit lieferten drei Standardwerke. Das Buch
"
Einf¨uhrung in die Kryptographie" von Johannes Buchmann [2] schildert
die mathematischen Grundlagen, beginnend bei den nat¨urlichen und ganzen
Zahlen bis zu den neuesten kryptographischen Ans¨atzen. Das Werk
"
Ange-
wandte Kryptographie" von Bruce Schneier [9] liefert eine detaillierte Be-
schreibung der kryptographischen Algorithmen und deren Implementierung.
Ein allgemeiner ¨
Uberblick ¨uber die gesamte Landschaft der heutigen Kryp-
tographie ist im Buch
"
Moderne Verfahren der Kryptographie" von Albrecht
Beutelspacher et al. [1] zu finden. F¨ur weitergehende Informationen sei hier
auf diese drei Werke verwiesen.
Die vorliegende Arbeit ist wie folgt gegliedert: In Kapitel zwei werden
zun¨achst einige Hilfsmittel aus der Mathematik vorgestellt. Kapitel drei be-
sch¨aftigt sich mit den grundlegenden Begriffen der Kryptographie, w¨ahrend
Kapitel vier auf Angriffe gegen Kryptosysteme eingeht. Im f¨unften Kapitel
wird die Analyse der Angriffsm¨oglichkeiten anhand eines Beispiels aus der
Praxis dargelegt. Schließlich wird in Kapitel sechs ein Blick auf neue krypto-
graphische Verfahren geworfen.
Kapitel 2
Mathematische Grundlagen
2.1
Hilfsmittel aus der Zahlentheorie
2.1.1
Komplexit¨
at von Algorithmen
Die Komplexit¨at von Algorithmen ist der Aufwand zur L¨osung eines Pro-
blems. Sie ist eine Funktion der Gr¨oße der Eingangsdaten. Zu ihrer Messung
kann die Anzahl der durchgef¨uhrten Operationen, der ben¨otigte Speicher-
platz oder die Rechenzeit benutzt werden. F¨ur die weiteren Betrachtungen
ist nur ihre Gr¨oßenordnung entscheidend, daher wird die Komplexit¨at von
Algorithmen mit dem folgenden Ordnungssymbol
1
angegeben:
Definition 2.1 Das Ordnungssymbol O(g(x)) beschreibt die Gr¨oßen-
ordnung einer Funktion. Es ist f (x) O(g(x)) f¨ur x a, wenn es eine
Umgebung U (a) und eine reelle Zahl C gibt, so daß gilt:
f (x)
g(x)
C f¨ur alle x U(a) mit x = a
Insbesondere gilt f (x) O(g(x)) f¨ur x a, falls lim
xa
f
(x)
g
(x)
existiert.
Es wird stets der Fall betrachtet, der den gr¨oßten Aufwand erfordert. Kon-
stante Faktoren und Terme niederer Ordnung werden vernachl¨assigt.
1
Siehe Teubner-Taschenbuch der Mathematik [16, Seite 253].
3
4
KAPITEL 2. MATHEMATISCHE GRUNDLAGEN
F¨ur einige Verschl¨usselungstechniken werden Algorithmen ben¨otigt, die nur
unter Kenntnis zus¨atzlicher Eingangsdaten effizient arbeiten, sonst aber einen
ungleich h¨oheren Zeitaufwand erfordern. Effiziente Algorithmen besitzen
eine Komplexit¨at, welche h¨ochstens so groß ist wie ein Polynom endlichen
Grades, sie haben eine sogenannte polynomiale Laufzeit. Das heißt, wenn
z
1
, z
2
, . . . , z
n
die Gr¨oßen der n Eingangsdaten sind, dann m¨ussen nichtne-
gative ganze Zahlen a
1
, a
2
, . . . , a
n
existieren, so daß die Komplexit¨at f des
Algorithmus wie folgt dargestellt werden kann:
f (z
1
, z
2
, . . . , z
n
) O(z
a
1
1
z
a
2
2
··· z
a
n
n
)
In der Komplexit¨atstheorie werden Probleme anhand ihrer Komplexit¨at in
verschiedene Klassen eingeteilt. In die Klasse P geh¨oren alle Probleme, die
mit polynomialem Zeitaufwand l¨osbar sind. Ein Problem geh¨ort zur Klas-
se NP, wenn die Verifizierung einer L¨osung mit polynomialen Zeitaufwand
m¨oglich ist. Das Finden der L¨osung kann dabei auch einen h¨oheren Aufwand
haben. Alle Probleme der Klasse P sind in der Klasse NP enthalten.
Ungekl¨art ist bisher, ob es ein Problem gibt, das zur Klasse NP, aber
nicht zur Klasse P geh¨ort. Ein NP-Problem heißt NP-vollst¨andig, wenn es
mindestens so schwer ist wie jedes beliebige Problem der Klasse NP. Ein
solches Problem repr¨asentiert sozusagen die gesamte Klasse.
Eine weitere Klasse ist PSPACE, die Klasse aller Probleme, welche mit
polynomialem Speicherplatz gel¨ost werden k¨onnen. Die Klasse NP ist in
PSPACE enthalten, auch hier ist die Gleichheit noch ungekl¨art. Im glei-
chen Sinne wie oben gibt es PSPACE-vollst¨andige Probleme, die die gesamte
Klasse repr¨asentieren.
Abbildung 2.1: Komplexit¨atsklassen
2.1. HILFSMITTEL AUS DER ZAHLENTHEORIE
5
Probleme, die mit exponentiellem Zeitaufwand l¨osbar sind, bilden die Klasse
EXPTIME. Alle bisherigen Klassen sind in ihr enthalten, allerdings wurde
bereits bewiesen, daß es Probleme in EXPTIME gibt, die nicht einmal in
PSPACE und damit in keiner der anderen Klassen liegen.
Bei den meisten kryptographischen Algorithmen ist die Sicherheit
dadurch gegeben, daß die Berechnungen der beteiligten Parteien nur einen
polynomialen Zeitaufwand haben, w¨ahrend jedoch ein Angreifer mindestens
ein NP-vollst¨andiges Problem l¨osen muß.
2.1.2
Der Euklidische Algorithmus
Es existieren sehr effiziente Algorithmen f¨ur die Grundrechenarten, die nur
einen geringen polynomialen Zeitaufwand ben¨otigen. Der Euklidische Algo-
rithmus ist ein gleichermaßen effizienter Algorithmus zur Berechnung des
gr¨oßten gemeinsamen Teilers zweier nat¨urlicher Zahlen. Der Ablauf gestaltet
sich folgendermaßen
2
:
Euklidischer Algorithmus
procedure euklid(a,b;g);
if a = 0 then begin
g := b;
end
else if b = 0 then begin
g := a;
end
else begin
repeat
r := a mod b;
a := b;
b := r;
until r = 0;
g := a;
end
return (g);
2
Siehe Beutelspacher et al. [1, Seite 116].
Alle Algorithmen sind in der Programmiersprache PASCAL notiert.
6
KAPITEL 2. MATHEMATISCHE GRUNDLAGEN
H¨aufig wird auch die Vielfachsummendarstellung des gr¨oßten gemeinsamen
Teilers gesucht. Diese wird durch das folgende Lemma geliefert
3
:
Lemma 2.1 (Lemma von B´
ezout) Seien a und b ganze Zahlen, die nicht
beide Null sind. Weiter sei g = gcd(a, b). Dann gibt es ganze Zahlen s und t
mit g = sa + tb. Letzteres heißt Vielfachsummendarstellung des gr¨oßten
gemeinsamen Teilers.
Zur Berechnung von s und t wird eine erweiterte Version des Euklidischen
Algorithmus eingesetzt
3
:
Erweiterter Euklidischer Algorithmus
procedure xeuklid(a,b;g,s,t);
if a = 0 then begin
g := b; s := 0; t := 1;
end
else if b = 0 then begin
g := a; s := 1; t := 0;
end
else begin
s1 := 1; s2 := 0; s := 0;
t1 := 0; t2 := 1; t := 1;
while (a mod b) <> 0 do begin
q := a div b; r := a mod b;
s := s1 + q * s2;
t := t1 + q * t2;
s1 := s2; s2 := s;
t1 := t2; t2 := t;
a := b; b := r;
end;
g := b;
end;
return (g,s,t);
3
Siehe Beutelspacher et al. [1, Seite 117].
2.1. HILFSMITTEL AUS DER ZAHLENTHEORIE
7
2.1.3
Der Chinesische Restsatz
F¨ur die Erl¨auterung der Funktionsweise einiger Kryptosysteme wird der
Chinesische Restsatz ben¨otigt. Er lautet
4
:
Satz 2.2 (Chinesischer Restsatz) Seien m
1
, m
2
, . . . , m
n
paarweise
teilerfremde nat¨urliche Zahlen und seien a
1
, a
2
, . . . , a
n
ganze Zahlen.
Dann hat das Gleichungssystem
x a
1
(mod m
1
)
x a
2
(mod m
2
)
...
x a
n
(mod m
n
)
eine L¨osung x, die eindeutig modulo m =
n
i
=1
m
i
ist.
Normalerweise wird dieser Satz in leicht ver¨anderter Form benutzt. Mit Hilfe
des Lemmas von B´ezout aus dem vorherigen Abschnitt kann folgender
Spezialfall formuliert werden
5
:
Folgerung 2.3 Seien m
1
und m
2
zwei teilerfremde nat¨urliche Zahlen und
sei s · m
1
+ t · m
2
= 1 die zugeh¨orige Vielfachsummendarstellung. Dann hat
das Gleichungssystem
x a
1
(mod m
1
)
x a
2
(mod m
2
)
die L¨osung x = a
2
· s · m
1
+ a
1
· t · m
2
, die eindeutig modulo m = m
1
m
2
ist.
Die L¨osung des Gleichungssystems kann berechnet werden, indem der erwei-
terte Euklidische Algorithmus auf m
1
und m
2
angewendet wird und die so
erhaltenen Werte s und t in die L¨osungsformel eingesetzt werden.
4
Siehe Buchmann [2, Seite 43].
5
Siehe Beutelspacher et al. [1, Seite 117].
8
KAPITEL 2. MATHEMATISCHE GRUNDLAGEN
2.1.4
Der Satz von Euler-Fermat
Definition 2.2 Die positiven nat¨urlichen Zahlen a und b heißen relativ
prim
zueinander, falls gcd(a, b) = 1 gilt.
Definition 2.3 Die Eulersche Funktion (a) einer nat¨urlichen Zahl a
ist die Anzahl aller positiven nat¨urlichen Zahlen n mit n a, die relativ prim
zu a sind. Insbesondere gilt f¨ur alle Primzahlen p: (p) = p - 1.
Damit kann ein weiteres Hilfsmittel aus der Zahlentheorie beschrieben
werden, der Satz von Euler-Fermat. Dieser spielt bei einigen Primzahltests
eine wichtige Rolle:
Satz 2.4 (Satz von Euler-Fermat) F¨ur alle positiven nat¨urlichen Zahlen
a und b, die relativ prim zueinander sind, gilt:
a
(b)
1 (mod b)
F¨ur den Fall, daß b eine Primzahl ist, gilt (b) = b - 1. Dadurch ergibt sich
der kleine Satz von Fermat als Spezialfall des obigen Satzes
6
:
Folgerung 2.5 (Kleiner Satz von Fermat) F¨ur jede Primzahl b und jede
nat¨urliche Zahl a mit 1 a < b gilt:
a
b-
1
1 (mod b)
Beweis: Der Satz von Euler-Fermat wird hier etwas allgemeiner bewiesen.
Dazu sei G eine endliche abelsche Gruppe mit einem neutralen Element e.
Die Ordnung von G sei ~
G. Ist nun g ein Element von G, so ist die Abbildung
G G,h gh eine Bijektion. Daher gilt
hG
h =
hG
(gh) = g
~
G
hG
h.
Somit gilt f¨ur alle g G: g
~
G
= e. Aus dem Restklassenring
/m entsteht
durch folgende Definition eine Gruppe bez¨uglich der Multiplikation:
(
/m)
= {a /m | gcd(a,m) = 1}
Dies ist eine endliche abelsche Gruppe, welche die Ordnung (m) hat
7
.
Daraus folgt die Behauptung.
6
Historisch gesehen wurde der Satz in dieser Form zuerst 1640 von Fermat formuliert,
ehe Euler ihn 1760 verallgemeinerte.
7
Die Eulersche Funktion (m) kann auch als Anzahl der Elemente dieser Gruppe
definiert werden. Diese Definition ist ¨aquivalent zu der vorher erw¨ahnten.
2.2. EINWEGFUNKTIONEN
9
2.1.5
Galoisfelder
Eine Menge K, auf der eine Addition und eine Multiplikation erkl¨art ist, heißt
K¨orper, falls K bez¨uglich der Addition und K \{0} bez¨uglich der Multiplika-
tion abelsche Gruppen sind und falls f¨ur alle a, b, c K das Distributivgesetz
(a + b) · c = a · c + b · c gilt. Besitzt ein K¨orper nur eine endliche Anzahl von
Elementen, dann wird er endlicher K¨orper bzw. Galoisfeld genannt.
Eine (echte) Teilmenge eines K¨orpers heißt (echter) Unterk¨orper, wenn sie
bez¨uglich derselben Rechenoperationen ebenfalls ein K¨orper ist. Ein Primk¨or-
per ist ein K¨orper, der keine echten Unterk¨orper besitzt. Endliche Primk¨orper
sind zum Gaußschen Restklassenring
/p isomorph, wobei die Primzahl p
die Anzahl der Elemente des entsprechenden Primk¨orpers ist.
Zu jeder Primzahl p und zu n = 1, 2, . . . gibt es bis auf Isomorphie genau
einen K¨orper mit p
n
Elementen, welcher mit GF (p
n
) bezeichnet wird. Auf
diese Weise k¨onnen alle m¨oglichen Galoisfelder erzeugt werden. Die speziellen
Galoisfelder GF (p) sind zu
/p isomorph.
2.2
Einwegfunktionen
2.2.1
Faktorisierung nat¨
urlicher Zahlen
Wichtige Grundbausteine der Kryptographie sind Funktionen, die leicht be-
rechnet, aber schwer invertiert werden k¨onnen. Durch sie kann zum Beispiel
verhindert werden, daß ein Angreifer den Schl¨ussel berechnen kann, wenn
er eine Nachricht und den dazugeh¨origen Geheimtext vorliegen hat. Eine
Funktion g : S T wird Einwegfunktion genannt, wenn sie folgende
Anforderungen erf¨ullt:
1. g(s) ist f¨ur alle s S leicht berechenbar, das heißt, g kann als Algo-
rithmus mit polynomialer Laufzeit dargestellt werden.
2. F¨ur fast alle Elemente t T ist es praktisch unm¨oglich, ein s S
mit g(s) = t zu berechnen. Insbesondere darf kein Algorithmus mit
polynomialer Laufzeit f¨ur g
-
1
bekannt sein
8
.
3. g(s) und s m¨ussen ¨ahnliche Gr¨oßenverh¨altnisse aufweisen
9
.
8
Die Forderung der Nichtexistenz eines solchen Algorithmus ist aus heutiger Sicht viel
zu hart, da selbst NP-vollst¨andige Funktionen g
-
1
dies nicht garantieren k¨onnen.
9
Siehe Apel [17, Seite 52]. Diese eher praktische Anforderung schließt Funktionen des
Typs g(x) = O(log
2
log
2
x
) aus.
10
KAPITEL 2. MATHEMATISCHE GRUNDLAGEN
Es existieren mehrere Funktionen, welche die Anforderungen an Einweg-
funktionen erf¨ullen. Das RSA-Kryptosystem (siehe Kapitel 3.3.2) basiert auf
der Multiplikation zweier Primzahlen, also g(p, q) = pq. Diese Operation
ist sehr effizient durchf¨uhrbar. Die Umkehrung, also die Faktorisierung des
Produkts, ist dagegen nur schwer durchf¨uhrbar, es sei denn, einer der Fak-
toren ist trivial. Bisher ist noch kein Algorithmus mit polynomialer Laufzeit
f¨ur g
-
1
bekannt. Einige Faktorisierungsalgorithmen mit nichtpolynomialem
Zeitaufwand werden sp¨ater noch erw¨ahnt.
2.2.2
Der diskrete Logarithmus
Definition 2.4 Sei a eine zu n teilerfremde nat¨urliche Zahl mit 1 a < n.
Sind s¨amtliche Potenzen a
d
mit 1 d < (n) modulo n von 1 verschieden,
so heißt a primitive Wurzel von n.
Sei nun n eine Zahl, welche primitive Wurzeln besitzt und a eine dieser
Wurzeln. Weiter sei y eine zu n teilerfremde Zahl mit 1 y < n. Dann
existiert genau eine Zahl x mit 0 x < (n), so daß gilt:
y a
x
(mod n)
Die Zahl x heißt diskreter Logarithmus von y zur Basis a modulo n. Die
Berechnung von y bei gegebenem x ist in polynomialer Laufzeit m¨oglich,
f¨ur die Umkehrfunktion jedoch ist derzeit kein Algorithmus bekannt, der
dies leistet. So besitzen die effizientesten heute existierenden Verfahren, der
Babystep-Giantstep-Algorithmus, der Pollard--Algorithmus und das Pohlig-
Hellman-Verfahren, nur einen nichtpolynomialen Zeitaufwand
10
.
Der diskrete Logarithmus kann f¨ur alle endlichen abelschen Gruppen
(multiplikativ geschrieben) definiert werden. Dazu sei n die Anzahl der
Elemente der endlichen abelschen Gruppe G. Weiterhin sei P G und
Q {P
z
| z }. Die Zahl k mod n aus /n, f¨ur die Q = P
k
gilt,
wird diskreter Logarithmus von Q zur Basis P genannt.
10
Siehe Buchmann [2, 151ff.].
2.3. ERZEUGUNG VON ZUFALLSZAHLEN
11
2.2.3
Nichtlineare Transformationen
Es seien p
1
, . . . , p
m
nichtlineare Polynome in n Variablen ¨uber dem zwei-
elementigen K¨orper GF (2). Alle in den Polynomen auftretenden Potenz-
produkte sind wegen a
2
= a f¨ur alle a GF(2) quadratfrei. Durch
g(a
1
, . . . , a
n
) = (p
1
(a
1
, . . . , a
n
), . . . , p
m
(a
1
, . . . , a
n
))
wird eine Funktion g : GF (2)
n
GF(2)
m
beschrieben, welche als nicht-
lineare Transformation bezeichnet wird. Der Funktionswert g(a
1
, . . . , a
n
)
ist f¨ur beliebige a
1
, . . . , a
n
GF(2)
n
mit nur polynomialem Zeitaufwand
berechenbar. Ist jedoch ein m-Tupel (b
1
, . . . , b
m
) GF(2)
m
gegeben, so ist
es sehr schwer, ein n-Tupel (a
1
, . . . , a
n
) GF(2)
n
zu finden, welches die
Gleichung g(a
1
, . . . , a
n
) = (b
1
, . . . , b
m
) erf¨ullt. Dazu m¨usste f¨ur das nicht-
lineare algebraische Gleichungssystem
p
1
(x
1
, . . . , x
n
) = b
1
...
p
m
(x
1
, . . . , x
n
) = b
m
eine L¨osung modulo 2 gefunden werden. Dies ist ein NP-vollst¨andiges
Problem und damit praktisch nicht durchf¨uhrbar.
2.3
Erzeugung von Zufallszahlen
2.3.1
Zufallszahlengeneratoren
F¨ur viele kryptographische Algorithmen werden Zufallszahlen ben¨otigt. Es
gibt mehrere M¨oglichkeiten, zuf¨allige Bitfolgen bereitzustellen. Ein Ansatz
daf¨ur ist die Verwendung von zuf¨alligen Ph¨anomenen der realen Welt. Dazu
geh¨oren physikalische Prozesse, etwa Hintergrundstrahlung, radioaktiver
Zerfall oder Diodenrauschen. Eine weitere M¨oglichkeit ist der Einsatz von
Softwarealgorithmen, die zum Beispiel die Zeit zwischen Anschl¨agen der
Tastatur oder Mausbewegungen messen.
