Kryptologie - Institut für Theoretische Informatik

Transcrição

Skript zur Vorlesung:
Kryptologie
Sommersemester 2007
Dr. Andreas Jakoby
Institut für Theoretische Informatik
Universität zu Lübeck
Inhaltsverzeichnis
1 Einführung
1
2 Klassische Kryptosysteme
3
2.1
Zwei-Wege Kryptosysteme: Das Kryptosystem von Julius Caesar . . . . . . . . . . . .
3
2.2
Affine Kryptosysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Das PLAYFAIR-System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4
Polyalphabetische Kryptosysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.4.1
Vigenère System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.4.2
Die Kryptoanalyse des Vigenère Verfahrens . . . . . . . . . . . . . . . . . . . .
11
2.4.3
Die Kryptoanalyse bei unbekannter Schlüssellänge: Der Kasiski-Test . . . . . .
12
2.4.4
Der Friedman-Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.4.5
Eine Verallgemeinerung des Vigenère Verfahrens . . . . . . . . . . . . . . . . .
17
Rotor-Chiffriermaschinen: Die Enigma . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.5
3 Der Begriff der Sicherheit
22
3.1
Kryptosysteme mit perfekter Sicherheit . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.2
A priori Annahmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.2.1
Variante 1: 1-Gramm-Quellen . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.2.2
Variante 2: 2-Gramm-Quellen . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.2.3
Variante 3: Markov-Ketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Bayes’scher Ansatz in der Kryptoanalyse . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.3
4 Symmetrische Verschlüsselungsalgorithmen
4.1
35
Der Data Encryption Standard (DES) . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.1.1
Aufbau des DES-Kryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.1.2
Berechnung der Funktion f . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.1.3
Die Teilschlüssel Ki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.1.4
Die Entschlüsselöung eines DES-Cyphertextes . . . . . . . . . . . . . . . . . . .
41
I
4.2
Das Triple DES-Kryptosystem (TDES)
. . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.3
Iterierte Blockkryptosysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.4
Differentielle Kryptoanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.5
Lineare Kryptoanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.5.1
Ein erster Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.5.2
Zusammensetzung von affin-linearen Approximationen . . . . . . . . . . . . . .
52
4.5.3
Angriff auf den letzten Rundenschlüssel für ein SPN-Kryptosystem . . . . . . .
55
Advanced Encryption Standard (AES) . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.6.1
Mathematische Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
4.6.2
Zustand des AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
4.6.3
Die Unterfunktionen des AES . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
4.6.4
Die Rundenschlüssel beim AES . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
4.6.5
Der AES-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
4.6
5 Public Key Kryptographie
69
5.1
Das generelle Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.2
Das Merkle-Hellman Kryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
5.2.1
Konstruktion des öffentlichen Schlüssels . . . . . . . . . . . . . . . . . . . . . .
71
5.2.2
Entschlüsselungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
5.2.3
Attacke von Shamir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
Probleme aus der Zahlentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
5.3.1
Grundlegende Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
Das RSA-Kryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
5.3
5.4
II
1
Einführung
Die Geschichte der Kryptologie geht zurück bis in die Antike. Die Anwendungsbereiche der Kryptologie
sind historisch mehr im militärischen Bereich angesiedelt, jedoch gelangte die Kryptologie im Verlaufe
des letzten Jahrhunderts immer mehr ins Zentrum des allgemeinen Interesses. So benutzen wir heute
fast alltäglich kryptographische Protokolle beim elektronischen Zahlungsverkehr oder beim Umgang
mit einem Geldautomaten.
Die Kryptologie besteht aus zwei wesentlichen Disziplinen:
1. der Kryptographie, d.h. die Kunst eine Nachricht zu verschlüsseln, so dass es für einen Unbefugten nicht möglich ist diese zu lesen oder zu manipulieren, und
2. der Kryptoanalyse, d.h. der Kunst dieses doch zu tun.
Das allgemeine Szenario in der Kryptologie besteht aus drei Personen, die wir Alice, Bob und Eve
nennen. Alice möchte eine Nachricht über einen unsicheren Kanal an Bob senden, so dass es für
Eve, die Zugriff auf den Kanal hat, nicht möglich ist den Inhalt der Nachricht zu erkennen oder zu
manipulieren. Wir können also folgendes Bild für das Basismodell der Kryptologie zeichnen:
Alice:
Bob:
Verschlüsselt die
Nachricht und
sendet sie an Bob.
Empfängt die verschlüsselte
Nachricht und entschlüsselt
sie.
unsicherer Kanal
unsicherer Kanal
Eve:
Greift auf den Kanal zu, versucht
die verschlüsselte Nachricht zu
entschlüsseln oder zu ändern.
Abbildung 1: Basismodell der Kryptologie.
Die Nachricht, die von Alice an Bob gesendet werden soll, nennen wir Plaintext und die verschlüsselte
Nachricht Ciphertext. Um ein praktikables Kryptosystem zu erhalten, muss sichergestellt sein, dass
1. die Verschlüsselung des Plaintextes für Alice einfach zu berechnen ist,
2. die Entschlüsselung des Ciphertextes für Bob einfach zu berechnen ist und
3. die Entschlüsselung bzw. die Manipulation des Ciphertextes für Eve nur mit enormen Aufwand
möglich ist.
Die klassische Lösung dieser Problemstellung führt uns zu den sogenannten Secret-Key-Kryptosystemen, wo sowohl Alice als auch Bob einen geheimen Schlüssel besitzen, der es ihnen erlaubt einen
Plaintext effizient zu verschlüsseln bzw. den Ciphertext effizient zu entschlüsseln.
Bevor wir auf verschiedene Kryptoverfahren im Detail eingehen, wollen wir den Begriff der Sicherheit
näher formalisieren. Zunächst müssen wie hierbei die Rolle von Eve etwas näher betrachten. Wir oben
1
gesagt, versucht Eve den Ciphertext zu entschlüsseln oder zu manipulieren. Prinzipiell können wir
zwei verschiedene Formen einer solchen Attacke unterscheiden:
1. Die aktive Attacke: Hierbei erlauben wir es Eve die Nachricht von Alice an Bob zu verändern.
2. Die passive Attacke: Hierbei ist es Eve nur erlaubt die Nachricht von Alice an Bob abzuhören.
Bestehend auf diesem Wissen kann Eve versuchen den Plaintext zu bestimmen.
Erlauben wir aktive Attacken, so müssen wir zunächst die Frage beantworten, welches Ziel Eve verfolgt.
So ist es möglich, dass sie nur den Ciphertext entschlüsseln möchte oder aber diesen so manipulieren
will, dass Bob eine falsche Nachricht erhält. Da sich diese Frage bei passiven Attacke nicht stellt,
können wir für diesen Fall eine einfache Definition angeben, die auf der Ununterscheidbarkeit der
Kommunikation zwischen Alice und Bob basiert. Wir definieren hierfür zunächst:
Definition 1 Seien X = {Xi }i∈N und Y = {Yi }i∈N zwei Familien von Zufallsvariablen, wobei wir
für ein festes Polynom p die Variablen Xi , Yi nur Werte aus {0, 1}≤p(i) annehmen. Dann nennen
wir X und Y ununterscheidbar, wenn für alle i und alle w ∈ {0, 1}≤p(i) gilt
Pr[Xi = w] = Pr[Yi = w] .
Wir nennen X, Y statistisch ununterscheidbar, wenn für alle Polynome q und für alle hinreichend große i gilt
X
1
|Pr[Xi = w] − Pr[Yi = w]| ≤
.
q(i)
≤p(i)
w∈{0,1}
Wir nennen X, Y berechenbar ununterscheidbar, wenn für alle probabilistischen polynomialzeitbeschränkten Algorithmen E , für alle Polynome q und für alle hinreichend große i gilt
|Pr[E(i, Xi ) = 1] − Pr[E(i, Yi ) = 1]| ≤
1
.
q(i)
Als Xi und Yi können wir die möglichen Kommunikationssequnezen zwischen Alice und Bob bzw.
den übertragenen Ciphertext bei einem Plaintext x bzw. y sehen. Wünschenswert wäre es, wenn ein
Kryptosystem so sicher wäre, dass Eve keinen Unterschied zwischen dem möglichen Ciphertexten für x
und y erkennen könnte. Dieses würde bedeuten, dass Xi und Yi ununterscheidbar sind. Die wenigen
Kryptosysteme, welche diese Sicherheit gewährleisten sind sogenannte One-Time Pad Verfahren.
Betrachten wir nun die Definition von berechenbarer Ununterscheidbarkeit. Den Algorithmus E ,
den wir hier herangezogen haben, können wir als die Attacke von Eve betrachten, die das Verschlüsselungsverfahren von Alice polynomiell oft befragen bzw. belauschen kann. Wäre die Differenz
1
|Pr[E(i, Xi ) = 1] − Pr[E(i, Yi ) = 1]| größer als q(i)
für ein Polynom q , dann könnte Eve nach q(i)
Versuchen mit großer Wahrscheinlichkeit zwischen x und y unterscheiden. Das Verfahren wäre also
nicht besonders sicher. Es wäre somit erstrebenswert, wenn ein Kryptosystem zumindest berechenbare
Ununterscheidbarkeit der Ciphertexte gewährleisten könnte. Leider konnte diese Güte für die meisten
heute benutzten Kryptosystem (noch) nicht nachgewiesen werden – jedoch auch nicht das Gegenteil.
Nichtsdestotrotz stellen diese Verfahren einen wesentlichen Pfeiler der Informatik dar.
Mit diesem etwas düsteren Bild, dass nur zur Vorsicht mahnen soll, wollen wir die Vorlesung beginnen.
2
2
Klassische Kryptosysteme
2.1
Zwei-Wege Kryptosysteme: Das Kryptosystem von Julius Caesar
Sei Σ = {A, . . . , Z, β} das lateinische Alphabet, wobei β das Leerzeichen darstellt. Die Verschlüsselung erfolgt mit Hilfe einer einfachen Permutation der Buchstaben. Hierzu schreiben wir zunächst die
Symbole aus Σ in eine Reihe und dann diese Symbole noch einmal geshiftet darunter. Ein Beispiel
ist in der folgenden Tabelle illustriert.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z β
Y Z β A B C D E F G H I J K L M N O P Q R S T U V W X
Um einen Plaintext zu verschlüsseln oder den Ciphertext zu entschlüsseln, genügt es die Zeichen
des entsprechenden Textes gemäß der Tabelle zu ersetzen, d.h. im Plaintext ersetzen wir A durch
Y, B durch Z usw. Analog ersetzen wir im Ciphertext Y durch A, Z durch B usw. Das angegebene
Verfahren erfüllt somit die ersten beiden Bedingungen, die wir an ein Kryptoverfahren gestellt haben.
Es verbleibt somit noch zu untersuchen, ob ein Ciphertext auch schwierig für Eve zu entschlüsseln ist,
d.h. wie schwierig die Kryptoanalyse für dieses Verfahren ist.
Wir unterscheiden bei der Kryptoanalyse zwei Szenarien:
1. Das Kryptosystem, welches für die Verschlüsselung herangezogen wurde, ist unbekannt.
2. Das Kryptosystem, welches für die Verschlüsselung herangezogen wurde, ist bekannt, aber der
aktuelle Schlüssel ist unbekannt.
Im Folgenden gehen wir davon aus, dass das Kryptosystem bekannt ist. Für diese Annahme sprechen
drei Gründe:
• Ist das Verfahren sicher in diesem Fall, dann ist es auch sicher für den Fall, dass das System
nicht bekannt ist.
• Die Erfahrung zeigt, dass sich die Struktur eines Kryptosystems im Allgemeinen nicht lange
geheim halten lässt.
• Die Anzahl der bekannten Kryptosysteme ist recht klein, daher ist es im Prinzip möglich alle
sinnvollen Verfahren parallel zu attackieren.
Als nächstes müssen wir uns fragen, welche Informationen Eve zur Verfügung stehen. Hierbei zeigen
sich mehrere Möglichkeiten:
1. nur den Ciphertext,
2. Ciphertexte und einige dazugehörige Plaintexte oder
3. Ciphertexte und einige dazugehörige Plaintexte, die von Eve bestimmt werden können, d.h. Eve
kann Alice dazu zwingen einige bestimmt Texte zu verschlüsseln.
3
In der Praxis tauchen je nach Form der Attacke alle drei Fälle auf. Es ist daher interessant alle
diese Fälle zu untersuchen. Da es sich bei dem Verfahren von Caesar um einen einfache zyklische
Shiftoperation handelt, kann ein entsprechend verschlüsselter Ciphertext sehr einfach entschlüsselt
werden.
Wir wollen nun versuchen das Caesar-Kryptoverfahren zu verallgemeinern. Hierzu führen wir folgende
Abstraktion durch:
Transformiere jede Einheit des Plaintexts und jede Einheit des Ciphertexts in ein mathematisches Objekt, welches wir einfach manipulieren können. Diese Transformation soll effizient zu berechnen sein. Für das Caesar-Kryptosystem ist dieses der Z26 = {0, . . . , 26} .
Diese Transformation hat den Vorteil, dass wir jetzt auf die Operationen Addition und
Multiplikation (modulo 27) zurückgreifen können. Im Folgenden identifizieren wir oft die
Texteinheiten und deren mathematische Repräsentation.
Das Caesar-Kryptosystem hat nun die Form f (x) = (x + r) mod 27 , wobei wir A durch 0, B durch
1, usw. repräsentieren. In unserem Beispiel oben ist r = 24 .
Allgemein können wir das Caesar-Kryptosystem für ein Alphabet der Größe m für ein r ∈ {0, . . . , m−
1} durch die Formel
f (x) = (x + r) mod m
darstellen. Der Schlüssel bei diesem Verfahren ist somit r . Da es nur m Möglichkeiten gibt den
Schlüssel zu wählen, folgt die Unsicherheit dieses Verfahrens aus folgender Beobachtung:
Beobachtung 1 Damit ein Kryptosystem sicher ist, muss es eine große Auswahl von möglichen
Schlüsseln geben.
Um die Anzahl der Schlüssel zu vergrößern, können wir zwei mögliche Verallgemeinerungen vornehmen:
1. Wir fassen eine Folge von k Buchstaben zu einem Symbol zusammen, d.h. wir betrachten
sogenannte k -Gramme. Sei x1 . . . xk ein solches k -Gramm, dann erhalten wir folgende Verschlüsselungsformel:
!
k
X
i−1
f (x1 . . . xk ) =
r+
xi · m
mod mk
mit r ∈ {0, . . . , mk − 1} .
i=1
Wir erhalten mk verschiedene Schlüssel r .
2. Wir führen einen zweiten Schlüssel ein und betrachten
f (x) = (a · x + r) mod m
mit r, a ∈ {0, . . . , m − 1} .
Es gibt somit m2 viele Schlüssel (a, r) . Diese Verallgemeinerung hat jedoch den Nachteil, dass
f nicht mehr injektiv sein muss: Sei (a, r) = (3, 3) und m = 27 , dann gilt f (8) = f (17) = 0 .
Sei a−1 das multiplikative Inverse zu a modulo m , d.h. a · a−1 mod m = 1 , dann gilt für die
Entschlüsselung
f −1 (y) = (a−1 · y − a−1 · r) mod m .
Existiert das multiplikative Inverse von a , so können wir den Ciphertext effizient entschlüsseln. Es
gilt:
4
Lemma 1 Die Gleichung a · x ≡ 1 mod m hat genau dann eine Lösung, wenn a und m teilerfremd
sind. Hat a · x ≡ 1 mod m eine Lösung, so ist diese eindeutig.
Um die Wahl von a nicht unnötig einzuschränken, wählen wir daher meistens eine Primzahl für m .
Wenden wir uns nun wieder der Analyse der Sicherheit von Caesars Kryptoverfahren zu. Es gilt:
Theorem 1 Seien p eine Primzahl, a, r ∈ {0, . . . , p − 1} zwei Schlüssel und x1 , x2 ∈ {0, . . . , p − 1}
zwei Nachrichten mit x1 6= x2 . Kennt Eve x1 , x2 , f (x1 ), f (x2 ) , so kann sie den Schlüssel (a, r) des
Kryptosystems f (x) = (a · x + r) mod p einfach berechnen.
Beweis: Seien n1 = f (x1 ) und n2 = f (x1 ) . Es gilt
n1 − n2 ≡ a · (x1 − x2 ) mod p .
Da p eine Primzahl ist, existiert auch das multiplikative Inverse (x1 − x2 )−1 von (x1 − x2 ) . Mit
Hilfe dieses Wertes können wir a und schließlich r effizient bestimmen.
Eine weitere Verallgemeinerung von Caesars Kryptoverfahren erhalten wir, indem wir beliebige Permutationen der Buchstaben zulassen. In diesem Fall ist die Permutation selber der Schlüssel. Man
beachte, dass es 27! viele Permutationen und somit 27! verschiedene Schlüssel gibt. Es ist hierbei
jedoch nicht nötig alle diese Schlüssel zu testen, da uns im Allgemeinen eine einfache Häufigkeitsanalyse der Buchstaben in den möglichen Plaintexten und eine entsprechende Ersetzung der Buchstaben
im Ciphertext weiter hilft. Eine Häufigkeitsanalyse der deutschen Sprache ergibt die folgende Tabelle
E
18,46 %
N
11,42 %
I
8,02 %
R
7,14 %
S
7,04 %
A
5,38 %
T
5,22 %
U
5,01 %
D
4,94 %
Solche Tabelle muss man jedoch mit einer gewissen Vorsicht genießen, da die Häufigkeiten der Buchstaben oft vom Kontext der analysierten Texte abhängen. Um einen Text zu entschlüsseln, machen
wir jetzt eine Häufigkeitsanalyse der Buchstaben im Ciphertext und ersetzten das am häufigsten vor
kommende Symbol im Ciphertext durch das Symbol, welches in unserer Tabelle das höchste Gewicht
hat, usw.
Aufgabe 1 Beweisen Sie Lemma 1.
Aufgabe 2 Bestimmen Sie die Komplexität des Verfahrens aus dem Beweis von Theorem 1.
Aufgabe 3 Der nachfolgende Text ist mit Hilfe der Formel f (x) = (a · x + r) mod m entstanden.
Bekannt ist, dass die Symbol Q und X am seltensten im Plaintext benutzt wurde. Bestimmen Sie den
Schlüssel (a, r) .
UELYMJLNQLHQXXLP β FNEQPLHTQETQCLTFYMZLUZSQZFUEJLOMZ
O β ZDECFOELMZLQZUSYML β RLETUDLWUZPLHTUOTLTFYMZL
UZSQZFUEJLYMJLZ β ELNJLAC β AQCLYAAXUOMEU β ZLCQD β XGQLQLMLA β Q
5
2.2
Affine Kryptosysteme
Wir betrachten wie zuvor ein endliches Alphabet Σ der Mächtigkeit N . Wie schon im letzten Abschnitt können wir die Symbole aus Σ durch Zahlen aus ZN darstellen. Wir betrachten hierfür
eine bijektive Kodierungsfunktion C : Σ → ZN . Der Einfachheit halber erweitern wir die Funktion C
auch auf Zeichenfolgen. Ein Plaintext w = wm−1 . . . w0 kann somit auch als Zahl im ZN m dargestellt
werden:
m−1
X
C(w) =
C(wi ) · N i .
i=0
Wir können folglich w als eine m -stellige N -näre Zahl auffassen. Bei einem affinem Kryptosystem
erhalten wir den verschlüsselten Text durch die Transformation t
t(C(w)) =
m−1
X
yi · N i = (a · C(w) + r) mod N m
mit a, r ∈ ZN m
i=0
wobei y0 , . . . , ym−1 ∈ ZN . Die Zeichenfolge C −1 (ym−1 ) . . . C −1 (y0 ) gibt dann den Ciphertext wieder.
Als Schlüssel dienen die beiden Zahlen (a, r) . Um eine Entschlüsselung des Ciphertexts zu garantieren,
verlangen wir, dass a und N m teilerfremd sind, d.h. ggT(a, N M ) = 1 . Um den Text zu entschlüsseln,
benötigen wir die Zahlen (â, r̂) wobei â = a−1 mod N m und r̂ = N m − a−1 · r mod N m ist. Die
Schlüssel (a, r) und (â, r̂) müssen vom Sender, d.h. Alice, und dem Empfänger, d.h. Bob, sicher
aufbewahrt werden.
Betrachten wir zunächst die Frage, wieviele Werte es für a gibt, die wie als Schlüssel wählen können.
Es gilt:
Die Menge aller Zahlen in Zn , die teilerfremd zu n sind bezeichnen wir mit
Z∗n = { k ∈ Zn | ggT(k, n) = 1 } .
Die Mächtigkeit dieser Menge wird auch als Eulersche ϕ -Funktion bezeichnet. Es gilt
Y
1
∗
.
ϕ(n) = |Zn | = n ·
1−
p
Primzahlen p mit ggT(p,n)6=1
Wichtige Spezialfälle der ϕ -Funktion für Primzahlen p, q und α ∈ N+ sind
ϕ(p)
ϕ(pq)
α
ϕ(p )
= p−1
=
(p − 1)(q − 1)
= pα−1 (p − 1) .
Betrachten wir nun die Sicherheit dieses Kryptoverfahrens, so erkennen wir, das wir auch für dieses
Verfahren die in Theorem 1 beschriebene Attacke heranziehen können. Sind also einige Plaintexte
und die dazugehörigen Ciphertexte bekannt, dann können wir den Schlüssel effizient bestimmen. Wir
wollen nun der Frage nachgehen, ob der Schlüssel auch in dem Fall gefunden werden kann, wenn nur
Ciphertexte zur Verfügung stehen. Um eine mögliche Attacke besser zu verstehen, beginnen wir mit
einem Beispiel:
Beispiel 1 Betrachten wir das lateinische Alphabet Σ = {β, A, B, . . . , Z} und die Kodierungsfunktion C , die den Elementen von Σ in der oben gegebenen Reihenfolge die Werte von 0 bis 26
6
zuordnet. Ferner betrachten wir den Schlüssel (7, 26) . Dann gilt C(KL) = 309 , t(C(KL)) = 2 und
C −1 (T (C(KL))) = βB sowie C(ZL) = 714 , t(C(ZL)) = 650 und C −1 (T (C(ZL))) = XB . In
diesem Beispiel haben sowohl die Plaintexte als auch die Ciphertexte den gleichen Suffix. Es stellt sich
also die Frage, ob dieses immer der Fall ist, d.h. haben Ciphertexte immer den gleichen Suffix, wenn
die dazugehörigen Plaintexte den gleichen Suffix haben?
Theorem 2 Sei Σ ein festes endliches nicht leeres Alphabet mit |Σ| = N und m eine feste Plaintextlänge. Ferner sein (a, r) ein Schlüssel mit ggT(a, N m ) = 1 und w, w0 ∈ Σm zwei Nachrichten,
die einen gemeinsamen Suffix der Länge i ≤ m haben, dann haben für alle Kodierungsfunktionen
C : Σ → ZN auch die Ciphertexte C −1 (t(C(w))) und C −1 (t(C(w0 ))) einen gemeinsamen Suffix der
Länge i .
Pm−1
Pm−1
Pm−1
Pm−1
Beweis: Sei C(w) = j=0 C(wj )·N j = j=0 xj ·N j und C(w0 ) = j=0 C(wj0 )·N j = j=0 x0j ·N j
wobei für alle j < i gilt xj = x0j . Ferner sei
= t(C(w)) = a · w + r mod N m =
y
m−1
X
yj · N j
j=0
y0
= t(C(w0 )) = a · w0 + r mod N m =
m−1
X
yj0 · N j .
j=0
Wir haben zu zeigen, dass für alle j < i gilt yj = yj0 . Nach Konstruktion gilt:
a·
m−1
X
j
xj · N + r ≡
j=0
m−1
X
yj · N
j
mod N
m
a·
und
j=0
m−1
X
x0j · N j + r
j=0
≡
m−1
X
yj0 · N j mod N m .
j=0
Betrachten wir die N -näre Darstellung von a und r , so folgt aus diesen Äquivalenzen für alle ` ≤ m :
a·
m−1
X
j
xj · N + r
≡ a·
j=0
a·
m−1
X
`−1
X
j
xj · N + r =
j=0
x0j · N j + r
j=0
≡ a·
`−1
X
Aus der Annahme, dass xj =
`−1
X
j=0
yj · N j
mod N `
yj0 · N j
mod N `
j=0
x0j · N j + r =
j=0
x0j
`−1
X
`−1
X
j=0
für alle j < i , folgt unmittelbar, dass
xj · N j + r =
`−1
X
x0j · N j + r mod N i .
j=0
Da die N -näre Repräsentation einer Zahl eindeutig ist, folgt die Gleichheit der Werte yj und yj0 für
alle j < i .
Kombinieren wir Theorem 2 mit einer Häufigkeitsanalyse, so können wir sukzessive die Suffixe der
Nachricht dekodieren. Wir fassen hierbei den geratenen Suffix der Länge ` als tatsächlichen Suffix
der Nachricht auf und können den Schlüssel – oder besser einen möglichen Schlüssel – modulo N `
bestimmen. Wir beginnen somit mit dem Schlüssel modulo N , mit Hilfe dieses Schlüssels bestimmen
wir den Schlüssel modulo N 2 , u.s.w.
Aufgabe 4 Beweisen Sie, dass ein affines Kryptosystem mit Schlüsseln (a, r) ∈ N2 und a, r <
N m bei einmaliger Anwendung und einem Plaintext w ∈ Σm perfekte Sicherheit bietet, d.h. die
Zufallsvariablen der Ciphertexte für alle Plaintexte aus Σm sind ununterscheidbar.
7
Aufgabe 5 Geben Sie ein Verfahren an, mit dessen Hilfe ein affines Kryptosystem mit Schlüsseln
(a, r) ∈ N2 und a, r < N m geknackt werden kann. Gehen Sie hierbei davon aus, dass für ein hinreichend großes k der Plaintext die Länge m · k hat und daher in k Blöcke Bi der Länge m zerlegt
wurde. Jeder dieser Blöcke wurde anschließend mit Hilfe der gleichen Schlüssel verschlüsselt.
2.3
Das PLAYFAIR-System
Um die oben beschriebene Schwäche der affinen Kryptosysteme zu überwinden, wurde von Sir Charles
Wheatstone folgendes Verfahren vorgeschlagen:
Man nehme die Symbole A, B, . . . , Z
Matrix, z.B.:
S
R
H
T
B
ohne J und verteile diese zufällig in einer 5 × 5 Y
I
C
N
K
D
P
A
O
M
W
U
X
G
Q
Z
L
F
E
V
Die Verschlüsselung erfolgt nach den folgenden Regeln:
1. Erweitere den Plaintext, so dass er von gerader Länge ist.
2. Partitioniere den Plaintext in Blöcke der Länge 2, wobei wir garantieren müssen, dass
in keinem Block zwei gleiche Symbole stehen.
3. Sind die beiden Symbole in der gleichen Spalte, dann ersetzen wir diese durch die
zyklisch nach unten versetzen Symbole in der Matrix, z.B. SH → RT , IK → CY .
4. Sind die beiden Symbole in der gleichen Zeile, dann ersetzen wir diese durch die
zyklisch nach rechts versetzen Symbole in der Matrix, z.B. AX → XF .
5. In den verbleibenden Fällen spannen die Symbole im Block ein Rechteck auf, z.B.
P F . Wir ersetzen dann diese Symbole durch die Symbole in der gleichen Zeile, die
die jeweiligen freien Ecken des Rechtecks darstellen, z.B. P F → LA .
Bei diesem Verfahren wird das Problem, dass ein gleicher Suffix im Plaintext auch einen gleichen Suffix
im Ciphertext zur Folge hat, gelöst. Jedoch gilt diese Beobachtung nicht für Suffixe gerader Länge.
Das Verfahren kann einfach auf Matrizen anderer Dimension erweitert werden, z.B. auf 3×9 -Matrizen.
Ferner können diese Matrizen durch einen einfachen Schlüssel generiert werden. Man nehme einen
einfachen Begriff, z.B. MAGIC, fülle die ersten Positionen der Matrix mit diesen Symbolen und fülle
die verbleibenden Positionen mit den verbleibenden Symbolen des Alphabets auf. So erhalten wir z.B.:
M
B
K
Q
V
A
D
L
R
W
G
E
N
S
X
I
F
O
T
Y
C
H
P
U
Z
Die wesentlichen Schwachstellen diese Verfahrens sind:
1. Es vernachlässigt die Häufigkeiten von 2-Grammen. So machen die 18 häufigsten 2-Gramme ca.
90% eines Textes in deutsch aus.
8
2. Beim PLAYFAIR-Verfahren führen verschiedene Schlüssel zur gleichen Verschlüsselung, z.B.:
P
R
B
H
V
A
S
C
I
W
L
T
D
K
X
M
O
F
Q
Y
E
N
G
U
Z
E
N
G
U
Z
P
R
B
H
V
A
S
C
I
W
L
T
D
K
X
M
O
F
Q
Y
U
Z
E
N
G
H
V
P
R
B
I
W
A
S
C
K
X
L
T
D
Q
Y
M
O
F
Eine Matrix, die sich durch einen zyklischen Shift aller Spalten b.z.w. Zeilen einer anderen Matrix
um den gleichen Wert ergibt, führt zu einem äquivalenten Schlüssel. Dieses reduziert die Anzahl
der möglichen Schlüssel und somit die Komplexität, den Schlüssel zu knacken.
PLAYFAIR wurde vom britischen Außenministerium vom Krim- bis zum Ersten Weltkrieg eingesetzt.
2.4
Polyalphabetische Kryptosysteme
Die bisher untersuchten Kryptosysteme benutzen nur eine Regel zur Verschlüsselung, daher nennen
wir diese monoalphabetische Kryptosysteme. Ein polyalphabetisches Kryptosystem stellt
mehrere Regeln zur Auswahl. Wir zerlegen den Text in verschiedene Einheiten und verschlüsseln die
erste Einheit mit Hilfe der ersten Regel, die zweite mit Hilfe der zweiten Regel, u.s.w. Wenn k Regeln
zur Verfügung stehen, wird die ` te Einheit nach der (` mod k) + 1 ten Regel verschlüsselt.
2.4.1
Vigenère System
Eines der bekanntesten und ältesten polyalphabetische Kryptosysteme ist das Vigenère System,
welches auf der nachfolgenden Tabelle beruht, die auch Vigenère Tabelle genannt wird:
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
9
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Dieses System wurde im 16. Jahrhundert von Blaise de Vigenère (1523-1596) entwickelt. Es basiert auf
Arbeiten von Alberti, Trithemius und Porta, welche sich schon vor ihm mit der polyalphabetischen
Verschlüsselung befasst hatten.
Dieses System kann als eine Verallgemeinerung des Caesar-Verfahrens angesehen werden. Neben der
Tabelle benötigt man für dieses System noch ein Schlüsselwort w = w0 . . . wk−1 , in dem alle Symbole
des Alphabets maximal einmal vorkommen. Die Verschlüsselung eines Plaintextes x = x0 . . . xm−1
erfolgt nach folgender Regel:
Ersetze das Symbol xi im Plaintext durch das C(xi ) te Symbol in der C(wi mod k ) mod
26 ten Zeile der Vigenère Tabelle, wobei C : Σ → Z|Σ| eine adäquate Kodierungsfunktion
ist.1
Wollen wir mit einem Schlüssel MAGIC den Text CRYPTOLOGY verschlüsseln, so erhalten wir
OREXVALUOA.
Zur Entschlüsselung eines Ciphertextes y = y0 . . . ym−1 verfahren wir wie folgt:
Sei yi das j te Symbol in der C(wi mod k ) mod 26 ten Zeile der Vigenère Tabelle, dann ist
das dazugehörige Plaintextsymbol C −1 (j) .
Es ist einfach zu erkennen, dass dieser Algorithmus nicht auf die Vigenère Tabelle beschränkt werden
muss. Benutzen wir anstelle der Berechnung der Zeile und Spalte ein Suchverfahren nach der Zeile,
deren ersten Eintrag wi mod k und für die Verschlüsselung die Spalte, deren erster Eintrag xi ist,
so können wir diesen Verschlüsselungsalgorithmus auch auf andere Tabellen wie z.B. die Beaufort
Tabelle anwenden.
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
1 Beim
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
Aufzählen der Zeilen und Symbole der Zeilen starten wir mit 0.
10
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Die Entschlüsselung erfolgt in solchen Tabellen nach folgender Regel:
Sei yi das j te Symbol in der Zeile, die mit C(wi mod k ) beginnt. Ersetze yi durch das
j te Symbol in der ersten Zeile.
Damit eine Tabelle zur Verschlüsselung herangezogen werden kann, muss sie den folgenden Bedingungen genügen:
1. In jeder Zeile müssen alle Symbole aus Σ genau einmal vorkommen.
2. In jeder Spalte müssen alle Symbole aus Σ genau einmal vorkommen. Diese Regel können wir
auch darauf beschränken, dass in der ersten Spalte alle Symbole aus Σ genau einmal vorkommen.
Aufgabe 6 Beweisen Sie, dass das affinen Kryptosysteme bei einmaliger Benutzung für den Fall,
dass die Länge von r im Schlüssel genau der Länge der Nachricht entspricht, perfekte Sicherheit
bietet.
Aufgabe 7 Geben Sie ein Verfahren zum Knacken des PLAYFAIR-Verfahren an. Bestimmen sie
dessen Zeitkomplexität.
Aufgabe 8 Verallgemeinern Sie das PLAYFAIR-Verfahren auf k -dimensionale Matrizen. Betrachten Sie hierbei, dass zunächst nur ein festes Alphabet Σ zur Verfügung steht.
2.4.2
Die Kryptoanalyse des Vigenère Verfahrens
Bei der Kryptoanalyse des Vigenère Verfahren unterscheiden wir zwei Szenarien:
1. Die Schlüssellänge k des Schlüssels w = w0 . . . wk−1 ist bekannt.
2. Die Schlüssellänge k ist unbekannt.
Die Kryptoanalyse bei bekannter Schlüssellänge
Sei x = x0 . . . xm−1 der Plaintext, der verschüsselt werden soll. Platzieren wir nun in einer Tabelle die
Symbole des Plaintextes so, dass die Symbole, deren Verschüsselungsregel durch das gleiche Schlüsselsymbol bestimmt wird, eine Spalte bilden, so erkennen wir, dass die Verschlüsselungsregeln periodisch
wechseln. Sei ` = bm/kc , so erhalten wir:
w0
x0
xk
..
.
w1
x1
xk+1
..
.
x(`−1)k
x`k
x(`−1)k+1
x`k+1
...
...
...
wk−2
xk−2
x2k−2
..
.
. . . x(`−1)k−2
...
xm
wk−1
xk−1
x2k−1
..
.
x(`−1)k−1
Lemma 2 Sei k die Länge des Schlüsselworts, dann kann das Vigenère Verfahren in k monoalphabetische Verschlüsselungverfahren untergliedert werden.
11
Wir erkennen, dass alle Symbole xi des Plaintexts mit Hilfe der i mod k ten monoalphabetischen
Verschlüsselungsregel verschlüsselt wurden. D.h. für alle i ∈ Zk können wir xi xk+i x2k+i . . . als
monoalphabetisch verschlüsselten Text betrachten, und diesen versuchen mit Hilfe der bereits diskutierten Hilfsmittel zu entschlüsseln. In vielen Abhandlungen über das Vigenère Verfahren wird vom
Schlüsselwort verlangt, dass jedes Element des Alphabets maximal einmal vorkommt. Somit ist die
Schlüsselwortlänge durch |Σ| beschränkt. Eine andere Methode, die Schlüssellänge (zumindest mit
hoher Wahrscheinlichkeit korreck) zu bestimmen, wurde von dem englischen Mathematiker Charles
Babbage (1854) gefunden und von dem preussischen Major Friedrich W. Kasiski (1863) zum ersten
Mal eingesetzt. Dieses Verfahren ist als Kasiski-Test bekannt.
2.4.3
Die Kryptoanalyse bei unbekannter Schlüssellänge: Der Kasiski-Test
Der Kasiski-Test versucht, wie bereits oben beschrieben, die Schlüssellänge zu bestimmen. Dieses
Verfahren basiert auf folgender Beobachtung:
Beobachtung 2 Wenden wir auf zwei gleiche Textfragmente im Plaintext jeweils die gleichen Verschlüsselungssequenzen an, so erhalten wir zweimal die gleichen Fragmente im Ciphertext.
Dieses Verhalten wird in folgenden Beispiel aus [S90] sichtbar. Die Leerzeichen in diesem Text sind
nur der bessern Übersicht halber eingefügt:
AVXZH
KALBR
GLGMO
HBWMS
PELHH
ABABK
HIGHP
RALFX
BUPNP
VCLTO
CGLGB
KHPEL
WZXVT
CFJOG
GSSLZ
ZHBUU
HCSBZ
VIMOF
STPFU
XSGAV
LLILF
VXHHB
NPZWP
AVXTC
ZWPBZ
ESOLA
MHALG
HBUMF
LACGL
UCMIS
WMPGO
RDWMO
HALVX
HDKTA
LQHTS
HMLFR
BLBVL
UGTBB
BZPGG
LAQHT
HGTBB
COLKB
MVJXP
LHTSP
GHUHH
ALOML
LFRZA
HALVX
HFMVT
SKVBM
LTCKL
VITYS
PHAVW
TAVXH
VHWPG
AHUAB
TPGMV
AVMVC
GHUZR
HEKBA
WHALB
RIYCI
TSZGL
HFMVT
LHIGH
OSLAC
VNTWW
MOILH
YMTUR
FMVTL
VBGLL
ZHTRS
VTCSM
YLKLA
HABZS
VTJCN
MOSKV
LFEFI
JXYPX
LHIGH
Wie wir sehen, kommt das Fragment VXHFMVTLHIGH dreimal im Ciphertext vor. Die Wahrscheinlichkeit, dass zwei gleiche Textfragmente im Ciphertext durch zwei gleiche Textfragmente im Plaintext
entstanden sind, ist größer als die Wahrscheinlichkeit, dass diese durch zwei unterschiedliche Fragmente
entstanden sind. Der Kasiski-Test nutzt diese Eigenschaft wie folgt aus:
1. Bestimme alle Fragmente v0 , v1 , . . . , v` , die im Ciphertext zumindest zweimal vorkommen. In
12
unserem Beispiel sind dieses:
v0
v1
=
HALVXHFMVTLHIGH (zweimal)
=
VXHFMVTLHIGH (dreimal)
v2
v3
=
=
VXH (viermal)
AVX (dreimal)
v4
=
HAL (viermal)
v5
=
VX (sechsmal)
2. Bestimme für alle Paare von Vorkommen eines Fragments vi die Partition des Ciphertextes in
wvi qvi r und die dazgehörigen Längen von vi q . Wir bezeichnen die Länge vi q für das j te Paar
von vi mit ì,j . Für unser Beispiel erhalten wir
`0,1
`1,1
`2,1
`3,1
`4,1
`5,1
= 375
= 129 `1,2 =
= 12
...
= 141 `3,2 =
= 246 `4,2 =
= 180 . . .
246 `1,3
39
60
=
...
`4,3 =
375
69
...
3. Bestimme alle Teiler der Werte ì,j und sortiere diese nach ihrer Häufigkeit. Wir erhalten
für
für
für
für
für
für
für
für
375
129
246
180
141
60
69
12
1,
1,
1,
1,
1,
1,
1,
1,
3,
3,
2,
2,
3,
2,
3,
2,
5, 25, 125, 15, 75, 375,
43, 129,
3, 41, 6, 82, 123, 246,
3, 4, 6, 5, 10, 15, 20, 45, 12, 36, 60, 180,
47, 141,
3, 4, 6, 5, 10, 15, 20, 12, 60,
23, 69,
3, 4, 6, 12 .
Der am häufigsten vorkommende Teiler ist die 3. Wir werden sehen, dass dieser Teiler schon
zum Erfolg führt. Daher werden wir auf die Analyse des Ciphertextes für die weiteren Teiler
verzichten. Im Allgemeinen führt jedoch die erste Wahl nicht immer zum Erfolg.
4. Betrachte den im letzten Schritt gefundenen Teiler als Länge k des Schlüssels. Nach Lemma 2
können wir den Ciphertext in k Teile aufteilen, welche alle mit Hilfe einen monoalphabetischen
Verfahrens verschlüsselt wurden. Für unser Beispiel erhalten wir bei k = 3 :
y0 y1 y2
AVX
LBR
OST
SGA
LFB
UGT
PGG
TAH
PGM
VCY
HAB
JCN
VCF
SSL
UUR
y0 y1 y2
ZHH
VIM
PFU
VHM
LBV
BBT
VHW
UAB
VVT
LKL
ZSK
WZX
JOG
ZWM
DWM
y0 y1 y2
CSB
OFH
LQH
LFR
LPH
AVX
PGV
ZHT
CSM
ACG
HPE
VTL
UCM
PGO
OHA
y0 y1 y2
ZHA
DKT
TSL
VIT
AVW
HFM
BGL
RSB
VCL
LGB
LHB
ACG
ISA
LFR
LVX
y0 y1 y2
LVX
ASK
TCK
YSM
YMT
VTL
LRA
UPN
TOE
MHA
UMF
LGH
LOM
ZAT
HFM
13
y0 y1 y2
HFM
VBM
LVN
OIL
URA
HIG
LFX
PZW
SOL
LGM
LHT
UHH
LRI
SZG
VTL
y0 y1 y2
VTL
OSL
TWW
HPE
BAB
HPN
AVX
PBZ
ACO
VJX
SPH
WHA
YCI
LJX
HIG
y0 y1 y2
HIG
ACG
HBW
LHH
KVX
PZW
TCL
HGT
LKB
PGH
EKB
LBM
LFE
YPX
H
y0 y1 y2
HKA
LGM
MSX
LLI
HHB
PBZ
AQH
BBT
AVM
UZR
AVT
OSK
FIG
ZHB
Zählen wir die Vorkommen der einzelnen Buchstaben so erhalten wir:
A
B
C
D
E
F
G
H
I
s0
12
4
2
2
1
1
0
15
1
s1
5
9
11
0
0
10
13
14
7
s2
9
12
0
0
4
2
10
11
3
J
K
L
M
N
O
P
Q
R
s0
2
1
27
2
0
6
10
0
1
s1
2
5
1
2
0
4
7
2
3
s2
0
4
13
17
4
2
0
0
5
S
T
U
V
W
X
Y
Z
s0
5
6
9
14
2
0
4
7
s1
13
4
1
11
3
1
0
5
s2
0
13
1
2
6
12
1
2
Wissen wir zudem, dass der Text in Englisch geschrieben wurde, so können wir bekannte statistische Daten über die Buchstabenhäufigkeiten im Englischen heranziehen:
E
T
A
12,31%
10,45%
8,05%
O
N
I
7,94%
7,19%
7,18%
S
R
H
6,59%
6,03%
5,14%
In einem ersten Ansatz können wir versuchen den Buchstaben E auf den Buchstaben im Ciphertext zu setzen, welcher am häufigsten vorkommt. Ein alternativer Ansatz versucht die Dreierfolge
RST auf die Folge von 3 Buchstaben im Alphabet zu übertragen, welche am häufigsten im Ciphertext vorkommt. Wir erhalten zwei mögliche Verschlüsselungsfunktionen
(a) R −→ T, S −→ U, T −→ V
Diese Funktion hätte zur Folge, dass W −→ Y, X −→ Z, Y −→ A. Somit kämen im Plaintext
der Buchstabe W viermal, der Buchstabe X siebenmal und der Buchstabe Y zwölfmal vor.
Dieses ist jedoch nach unserer Buchstabenhäufigkeitstabelle im Englischen sehr unwahrscheinlich.
(b) R −→ Y, S −→ Z, T −→ A
Dieses resultiert in einer Verschlüsselungsfunktion von f0 (x) = x + 7 mod 26 .
Analog erhalten wir für f1 (x) = x + 14 mod 26 und f2 (x) = x + 19 mod 26 .
Der Schlüssel könnte somit HOT sein. Entschlüsseln wir den Ciphertext mit Hilfe dieses Schlüssels,
so erhalten wir:
THESTOVEISTHEHEARTOFSAUNA. . .
2.4.4
Der Friedman-Test
Eine weitere Möglichkeit einen Kandidaten für die Länge eines Schlüsselworts zu bekommen, stellt
der Friedman-Test (William Friedman, 1925) dar. Die wesentliche Idee bei diesem Text basiert auf
der Analyse, mit welcher Wahrscheinlichkeit zwei zufällig und unabhängig ausgewählte Buchstaben
im Plaintext gleich sind.
n
Sei x = x0 . . . xn−1
P∈ Σ ein Plaintext der Länge n und für alle b ∈ Σ sei nb die Anzahl der b in
x , dann gilt n = b∈Σ nb . Die Anzahl der Paare in x ist gegeben durch
m = n2
und die Anzahl der Paare die Form xi = xj = b ist
mb = n2b .
14
Die Anzahl der Paare die aus zwei identischen Buchstaben bestehen ist
X
mΣ =
mb .
b∈Σ
Wir betrachten hierbei Paare bei denen die Reihenfolge berücksichtigt wird und eine Position zweimal
gezogen werden darf.
Die Wahrscheinlichkeit bei einem zufällig unabhängig gewählten Paar auf zwei identischen Buchstaben
zu treffen ist
mΣ
p(x) =
.
(1)
m
Diese Wahrscheinlichkeit wird oft auch als Koinzidenzindex bezeichnet. Es ist einfach zu erkennen,
dass unser oben angestellten Überlegungen für jede beliebige Zeichenkette x ∈ Σn gültig ist.
Die Wahrscheinlichkeit, dass ein zufällige Position in einem hinreichend langen englischen Text den
Buchstabe b ∈ {A, . . . , Z} binhaltet ist in folgender Tabell beschrieben:
A
B
C
D
E
F
G
pb
0,0856
0,0139
0,0279
0,0378
0,1304
0,0289
0,0199
H
I
J
K
L
M
N
pb
0,0528
0,0627
0,0013
0,0042
0,0339
0,0249
0,0707
O
P
Q
R
S
T
U
pb
0,0797
0,0199
0,0012
0,0677
0,0607
0,1045
0,0249
V
W
X
Y
Z
pb
0,0092
0,0149
0,0017
0,0199
0,0008
Die Wahrscheinlichkeit, dass zwei zufällige Positionen in einem englischen Text zwei identische Buchstaben beinhalten ist
X
p =
p2b
b∈Σ
wohingegen in einer zufälligen Zeichenkette diese Wahrscheinlichkeit durch
p̂ =
X
|Σ|−2 =
b∈Σ
1
|Σ|
gegeben ist. Für die englische Sprache gilt
p = 0, 06873314 . . .
und
p̂ = 0, 03846 . . . .
Für einen monoalphabetisches Verschlüsselungsverfahren gilt:
Beobachtung 3 Sei x ein Plaintext und y ein zu x gehöriger Ciphertext, welcher durch ein monoalphabetisches Verschlüsselungsverfahren erzeugt wurde, dann gilt p(x) = p(y) , d.h. x und y haben
den gleichen Koinzidenzindex.
Im Folgenden werden wir sehen, dass der Koinzidenzindex für einen Ciphertext der über das Vigenère
Verfahrens erzeugt wurde mit der Länge des Schlüsselwortes fällt. Um zu entscheiden, ob ein Ciphertext über ein mono- oder ein polyalphabetisches Verfahren erzeut wurde können wir folgende Regel
benutzen:
15
Ist p ≈ p , so wurde der Ciphertext über ein monoalphabetische Verfahren erzeugt. Gilt
p ≈ p̂ , so wurde der Ciphertext über ein polyalphabetische Verfahren erzeugt.
Sei k die Länge des Schlüsselworts. Wie wir aus Lemma 2 wissen zerfällt ein über das Vigenère
Verfahren erzeugtes Ciphertext in k Teile, die über ein monoalphabetische Verschlüsselungverfahren
generiert werden. Ist der Text lang genug, so können wir aus Beobachtung 3 folgern, dass in jedem
dieser Teile der Koinzidenzindex des Plaintextes unverändert beibehalten wird. Betrachten wir jedoch
ein Positionspaar mit zwei Positionen, die zu unterschiedlichen monoalphabetische Verschlüsselungverfahren gehören, so reduziert sich die Wahrscheinlichkeit auf ein identisches Paar zu stossen. Im
günstigsten Fall ist diese Wahrscheinlichkeit gleich 1/26 .
Im Folgenden werden wir als Arbeitshypothese annehmen, dass bei einem Paar von Positionen innerhalb eines Teil, der mit einem monoalpabetischen Verschlüsselungsverfahrens
generiert wurde die Wahrscheinlichkeit für gleiche Symbole durch p gegeben ist. Bei einem
Paar aus zwei verschiedenen Teilen, ist diese Wahrscheinlichkeit p̂ .
Jeder Teil, der über eine bestimmtes monoalpabetisches Verschlüsselungsverfahren generiert wird hat
eine Größe von n/k . Es gibt somit n Möglichkeiten die erste Position zu wählen und nk Möglichkeit
die zweite Position im gleichen Teil des Ciphertextes zu wählen. Es gibt somit
n2
k
q =
Paare von Positionen, die sich in einem Teil des Ciphertextes befinden. Die Anzahl der Paare von
Positionen aus unterschiedlichen Teilen des Ciphertextes ist gegeben durch
n2 (k − 1)
.
k
q =
Die Anzahl der Positionspaare mit identischen Buchstaben ist somit
mΣ = p ·
n2 (k − 1)
n2
+ p̂ ·
.
k
k
Folglich gilt
mΣ
p + p̂ · (k − 1)
=
.
2
n
k
Mit Hilfe dieser Formel und den angegebenen Abschätzungen für p und p̂ erhalten wir
p(y) =
k ≈
0, 06873 − 1/26
p(y) − 1/26
≈
0, 0303
.
p(y) − 0, 03846
Betrachten wir das in Kapitel 2.4.2 diskutierte Beispiel, so erhalten wir:
A
B
C
D
E
F
G
ni
26
25
13
2
5
13
23
H
I
J
K
L
M
N
ni
40
11
4
10
41
21
4
O
P
Q
R
S
T
U
16
ni
12
17
2
9
18
23
11
V
W
X
Y
Z
n
ni
27
11
13
5
14
400
(2)
Aus dieser Tabelle und mit Hilfe der Gleichung 1 erhalten wir p(y) = 0, 05565 . und aus der Approximation 2 den Wert k = 1, 8 . . . . Dieser Wert kann als ein Indiez dafür gesehen werden dass zur
Verschlüsselung des Ciphertextes ein sehr kurzer Schlüssel benutzt wurden.
Betrachten wir nun die Approximation 2 in ihren Extremen: Für ein monoalphabetisches Verfahren
erhalten wir p(y) ≈ 0, 06873 und somit k ≈ 1 . Für einen zufällig gewählten Text z erhalten wir
1
p(z) ≈ 26
und somit k → ∞ .
2.4.5
Eine Verallgemeinerung des Vigenère Verfahrens
Auf Vigenère geht auch eine Verallgemeinerung des Vigenère Verfahrens zurück, wohingegen sich die
Literatur nicht einig ist, wer der Entwickler des Vigenère Verfahrens ist [K67].
Die Verallgemeinerung, die wir nun kurz vorstellen wollen, bezieht den Nachrichtentext bei der Schlüsselgenerierung mit ein. Sei w = w1 . . . wk ein Schlüssel und x = x1 . . . xn eine Nachricht – beide ohne
Leerzeichen – dann erhalten wir den neuen Schlüssel durch
w0 = w1 . . . wk x1 . . . xn−k .
Verschlüsseln wir eine Nachricht mit Hilfe dieses Verfahrens, so müssen wir zunächst einen Präfix des
Ciphertextes entschlüsselt haben, um den Schlüssel für den nächsten Teil des Ciphertextes zu erhalten.
Die Eigenschaft einer Periodizität können wir zum Knacken dieses Verfahrens nicht mehr ausnutzen.
Aufgabe 9 Benutzen Sie den Test von Kasiski um folgenden Text zu entschlüsseln
KSMEHZBBLKSMEMPOGAJXSEJCSFLZSY .
Aufgabe 10 Versuchen Sie den folgenden Text zu entschlüsseln
TPOGDJRJFSUBSFCSQLGPCOFUQNFDSFCLVIFOTGNWGT .
2.5
Rotor-Chiffriermaschinen: Die Enigma
Das Prinzip der Rotor-Chiffriermaschine wurde zu Beginn des letzten Jahrhunderts unabhängig von
mehreren Personen erfunden. Zu nennen sind hier vor allem: Der Amerikaner E. H. Hebern (1917, Patent 1924), der Deutsche A. Scherbius (Patent 1918), der Niederländer H. A. Koch (Patent 7.10.1919)
und der Schwede A. G. Damm (Patent 10.10.1919).
Das Prinzip der Rotor-Chiffriermaschine basiert wie die schon früher diskutierten Verfahren von Caesar und Vigenère auf der Permutation der Buchstaben eines Alphabets Σ = {A, . . . , Z} . Bei der
Enigma kamen hierbei je nach Typ die sukzessive Ausführung von 3 bis 4 Permutationen zum Einsatz. Im Folgenden bezeichnen wir diese Permutationen mit Π1 , Π2 , Π3 , Π4 . In Abbildung 2 wird die
Hintereinanderausführung von zwei Permutationen illustriert.
17
A B C D E F G H I
J K L M N O P Q R S T U V W X Y Z
D L H I A B C K E F X N P J G R M T O Z Y W S U Q V
L G K E D I H X A T P J R F C U B Z N V Q S O Y M W
Abbildung 2: Hintereinanderausführung von zwei Permutationen.
Die sukzessive Ausführung von 3 bis 4 Permutationen bringt jedoch keinen zusätzlichen Sicherheitsgewinn. Auf die Gründe für dieses Verfahren werden wir später eingehen.
A B C D E F G H I
D L H I A B C K E F X N P J G R M T O Z Y W S U Q V
L G K E D I H X A T P J R F C U B Z N V Q S O Y M W
A B C D E F G H I
T D S B M K Q X V P F R E Z U J G L C A O I Y H W N
B R X V T D S F M K H Z J P Q L E A U N W Y C O G I
R Q F M B V X H T A J P L K S O D N Z I G C U W E Y
Abbildung 3: Die Funktion f
−1
= Π−1
1 ◦ Π2 ◦ Π5 ◦ Π2 ◦ Π1 .
Auf die so permutierte Folge wenden wir eine weitere Permutation Π5 an, welche eine paarweise
Symbolvertauschung realisiert. Diese Permutation wird auch Reflektor oder Umkehrwalze genannt.
Abschließend durchlaufen wir die Permutationen Π1 , Π2 , Π3 , Π4 noch einmal rückwärts in umgekehrter Reihenfolge. Die resultierende Verschlüsselungsfunktion ist somit
f
−1
−1
−1
= Π−1
1 ◦ Π2 ◦ Π3 ◦ Π4 ◦ Π5 ◦ Π4 ◦ Π3 ◦ Π2 ◦ Π1 .
18
Die Funktion von f ist in Abbildung 3 illustriert.
Den Vorteil dieser Verschlüsselungsfunktion können wir schnell erkennen, wenn wir das Verfahren
zweimal hintereinander anwenden. Sei
−1
−1
−1
y = Π−1
1 (Π2 (Π3 (Π4 (Π5 (Π4 (Π3 (Π2 (Π1 (x))))))))) ,
dann gilt
−1
−1
−1
Π−1
1 (Π2 (Π3 (Π4 (Π5 (Π4 (Π3 (Π2 (Π1 (y)))))))))
=
−1
−1
−1
−1
−1
−1
−1
Π−1
1 (Π2 (Π3 (Π4 (Π5 (Π4 (Π3 (Π2 (Π1 (Π1 (Π2 (Π3 (Π4 (Π5 (Π4 (Π3 (Π2 (Π1 (x))))))))))))))))))
=
−1
−1
−1
Π−1
1 (Π2 (Π3 (Π4 (Π5 (Π5 (Π4 (Π3 (Π2 (Π1 (x)))))))))) .
Beachten wir, dass eine paarweise Symbolvertauschung ihre eigene Umkehrfunktion darstellt, so erhalten wir
−1
−1
−1
x = Π−1
1 (Π2 (Π3 (Π4 (Π5 (Π4 (Π3 (Π2 (Π1 (y))))))))) .
Die von der Enigma realisierte Funktion stellt somit ihre eigene Umkehrfunktion dar. Geben wir zum
Beispiel das Symbol H in unserem Beispiel (Abbildung 3) ein, so erhalten wir in der Verschlüsselung
das Symbol X. Geben wir jetzt wiederum das Symbol X ein, so erhalten wir H. Die Enigma konnte
also ohne Umbau sowohl zur Verschlüsselung als auch zur Entschlüsselung benutzt werden. Da die
Realisierung jedoch auf einem Stromkreis basierte, war es bei der Realisierung verboten, dass ein
Symbol auf sich selbst abgebildet wurde.
Die einzelnen Permutationen wurden auf einer Walze realisiert, so dass durch das Drehen einer Walze
Πi eine neue Permutation Π0i ensteht. Der wesentliche Trick besteht nun darin, dass sich die erste
Walze mit jedem Symbol um eine Position in der Permutation dreht, die zweite Walze mit jedem
26 ten Symbol dreht, die dritte Walze mit jedem 262 ten Symbol dreht, und die letzte Walze mit
jedem 263 ten Symbol dreht.
Um die Sicherheit zu erhöhen, wurden zudem noch vor der eigentlichen Enigma-Verschlüsselung vier
Buchstabenpaare aus den 26 Buchstaben vertauscht. Dieses wurde mit Hilfe eines Steckerbrett realisiert. Ferner konnten die Walzen gegen andere Walzen ausgetauscht und untereinander permutiert
werden. Zur Verfügung standen 5 Walzen. Der Tagesschlüssel bestand aus folgenden Punkten:
1. Walzenauswahl
2. Walzenreihenfolge
3. Walzengrundstellung
4. Steckerbrettverkabelung.
Insgesamt gab es somit
4
5 · 4 · 3 · 2 · 26 ·
26
2
·
24
2
· 22
2 ·
4!
20
2
= 8995419473040000
mögliche Schlüssel. Mit der Nachricht wurde auch der Nachrichtenschlüssel übermittelt. Dieser bestand
aus den ersten sechs Zeichen der Nachricht – die Einstellung der Walzen wurde einmal wiederholt. Mit
diesem wurden die Walzen in eine neue Ausgangsposition gebracht. Mit dem so erhaltenen System
konnte mit der Entschlüsselung des eigentlichen Textes begonnen werden.
19
A B C D E F G H I
X F N J
J K L M N O P Q R S T U V W X Y Z A B
K C D E M G H Z P R L I T O V Q B A Y U W S X
A F L E M X J N H K O P R I G D U C Q Z S W Y V B T A
A B C D E F G H I
R E Q Y B S W K L N H I U J P O C A F V M T G Z D X R E
Z S J N H Q Y B U W K X O A I L V P T C E R D M G F Z
R S
I B U Z N J K H P O A L W Y M Q C X F G D T E V R
Abbildung 4: Die Funktion f
= Π1−1 ◦ Π−1
2 ◦ Π5 ◦ Π2 ◦ Π1 für das 28te Symbol.
Die Kryptoanalyse der Enigma gestalltete sich im zweiten Weltkrieg als eine sehr aufwendiges Problem.
So beschäftigten bei den Alliierten bis zu 10000 Mathematiker, Ingenieure und Hilfskräfte zwischen
1939 und 1945 mit dieser Aufgabe. Es muss hier noch erwähnt werden, dass es einer polnischen Gruppe
von 15 Mathematikern um M. Rejewski bereits vor Beginn des zweiten Weltkries gelungen war das
Verfahren der ersten Varianten der Enigma zu knacken.
Besonders Hilfreich bei der Kryptoanalyse zeigen sich hierbei einige Fehler der Deutschen bei der
Verschlüsselung. So wurde in vielen Fällen als Testsignal eine längere Folge von A’s verschlüsselt. Auch
die Eigenschaft, dass jede Nachricht mit einer zweifachen Wiederholung des Nachrichtenschlüssels
begann konnten sich die Alliierten zu Nutze machen, um den Suchraum für den Tagesschlüssel von
9 · 1018 stark einzugrenzen. Zudem kamen den Alliierten noch einige Zufälle zu Hilfe, so konnten sie
in einigen versenkten U-Booten und durch Spionage die Walzen der Enigma erbeuten. Ferner fiehlen
ihnen hin und wieder Schlüsselbücher in die Hände. Leider gibt es nur eine sehr beschränkte Literatur
über die Kryptoanalyse der Enigma. Daher werden wir uns nun von den klassischen Verfahren langsam
verabschieden und uns der modernen Kryptologie zuwenden.
Eine gute Darstellung der Enigmaverschlüsselung ist im Internet unter
http://de.wikipedia.org/wiki/Enigma %28Maschine%29
und unter
20
http://www.mywiseowl.com/articles/Enigma machine
zu finden. Auf diesen Seiten wird auch auf einige Details in der Konstruktion der Enigma eingegangen.
21
3
Der Begriff der Sicherheit
Wir wollen uns nun wieder dem Problem zuwenden, mit dem wir uns schon in der ersten Stunde kurz
beschäftigt haben: Was verstehen wir unter dem Begriff Sicherheit? Wie wir schon gesehen haben
können wir kryptographische Verfahren in verschiedene Stufen der Sicherheit einsortieren:
• perfekte oder uneingeschränkte Sicherheit,
• probabilistische Sicherheit,
• Sicherheit gegen algorithmische Attacken und
• unsicher.
Für viele bekannte Verfahren ist jedoch die Zuordnung zu einer dieser Sicherheitsklassen noch nicht
bekannt. Um trotz dem eine Klassifikation dieser Verfahren zu erhalten, führen wir eine weitere Sicherheitsklasse ein, die
• beweisbare Sicherheit.
Diese Form der Sicherheit basiert auf dem Begriff der Reduktion. Um zu zeigen, dass ein Verfahren
beweisbar sicher ist, zeigen wir, dass das knacken einer signifikanten Anzahl von Schlüsseln auch das
effiziente Lösen bestimmter (vermutlich) schwieriger Probleme zur Folge hätte. Ein oft benutztes Beispiel für ein solches vermutlich schwieriges Problem, ist das Problem der große Zahlen zu faktorisieren.
Wir wollen uns nun mit einigen dieser Sicherheitsbegriffen etwas näher auseinander setzen. Sei
Zm = {0, 1, . . . , m − 1}
und
Zm,n = Znm .
Dann definieren wir die Menge aller möglichen Plaintexte als
[
Zm,n
Pt :=
n∈N
und die Menge aller möglichen Ciphertexte als
Ct :=
[
Zm,n .
n∈N
Definition 2 Eine kryptographische Transformation ist eine Familie von bijektiven Transformationen T = (T (n) )n∈N mit
T (n) : Zm,n → Zm,n
für ein beliebiges aber festes Alphabet Zm . Hängt die kryptographische Transformation von der Wahl
(n)
eines Schlüssels w ab, so schreiben wir auch Tw = (Tw )n∈N .
Ein Kryptosystem ist eine Familie von kryptographischen Transformationen
T
= { Tw | w ∈ K }
wobei K die Menge aller möglichen Schüssel ist.
22
Für die Kryptoanalyse gehen wir davon aus, dass das Kryptosystem bekannt jedoch der Schlüssel
unbekannt ist. Zusammenfassend besitzt ein Angreifer auf das Kryptosystem folgende Kenntnisse
über das System:
• a priori Annahmen über die Wahrscheinlichkeitsverteilung PrPt der möglichen Plaintexte Pt,
• a priori Annahmen über die Wahrscheinlichkeitsverteilung Pr K der möglichen Schlüssel K ,
• das benutzte Kryptosystem T ,
• einige Beispiele y = Tw (x) für verschiedene w ∈ K und x ∈ Pt und
• der zu entschlüsselnde Ciphertext Y .
Aus dem a priori Wissen über PrPt und Pr K können wir folgende Wahrscheinlichkeiten bestimmen:
1. PrPt, K (x, w) , d.h. die Wahrscheinlichkeit, dass zur Verschlüsselung von x der Schlüssel w
benutzt wird:
PrPt, K (x, w) = PrPt (x) · Pr K (w) .
Wir gehen davon aus, dass Plaintext und Schlüssel unabhängig von einander gewählt werden.
2. PrCt (y) , d.h. die Wahrscheinlichkeit, dass der Ciphertext y vorkommt:
X
PrCt (y) =
PrPt, K (x, w) .
(x,w)∈Pt×K mit y=Tw (x)
3. PrPt,Ct (x, y) , d.h. die Wahrscheinlichkeit, dass y die Verschlüsselung von x ist:
X
PrPt,Ct (x, y) =
PrPt, K (x, w) .
w∈K mit Tw (x)=y
4. PrCt,Pt (y, x) , d.h. die Wahrscheinlichkeit, dass y die Verschlüsselung von x ist:
X
PrCt,Pt (y, x) =
PrPt, K (x, w) .
−1
w∈K mit Tw
(y)=x
5. PrCt, K (y, w) , d.h. die Wahrscheinlichkeit, dass bei y der Schlüssel w benutzt wurde:
X
PrCt, K (y, w) =
PrPt, K (x, w) .
x∈Pt mit Tw (x)=y
6. PrPt|Ct (x|y) , d.h. die bedingte Wahrscheinlichkeit vom Plaintext x unter der Voraussetzung,
das der Ciphertext y vorliegt:
PrPt|Ct (x|y) =
PrCt,Pt (y, x)
.
PrCt (y)
7. Pr K |Ct (w|y) , d.h. die bedingte Wahrscheinlichkeit vom Schlüssel w unter der Voraussetzung,
das der Ciphertext y vorliegt:
PrK|Ct (w|y) =
23
PrCt, K (y, w)
.
PrCt (y)
8. PrCt|Pt (y|x) , d.h. die bedingte Wahrscheinlichkeit vom Ciphertext y unter der Voraussetzung,
das der Plaintext x vorliegt:
PrCt|Pt (y|x) =
PrPt,Ct (x, y)
.
PrCt (y)
Bei den Definitionen der bedingten Wahrscheinlichkeiten müssen wir davon ausgehen, dass
PrCt (y) > 0
bzw. PrPt (x) > 0
ist. Im Fall, dass diese Wahrscheinlichkeiten gleich Null sind, so definieren wir auch die entsprechenden
bedingten Wahrscheinlichkeiten als Null.
3.1
Kryptosysteme mit perfekter Sicherheit
Mit Hilfe dieser Wahrscheinlichkeiten können wir nun den Begriff der perfekten Sicherheit definieren:
Definition 3 Ein Kryptosystem T nennen wir genau dann uneingeschränkt bzw. perfekt sicher,
wenn für alle Plaintexte x und alle Ciphertexte y mit PrCt (y) > 0 gilt
PrPt|Ct (x|y)
=
PrPt (x) .
In anderen Worten, wann immer ein Kryptoanalytiker einen Ciphertext sieht, erhält er über den
Plaintext keine zusätzliche Information.
Aufgabe 11 Beweisen Sie: Ein Kryptosystem T ist genau dann uneingeschränkt sicher, wenn für
alle Plaintexte x und alle Ciphertexte y mit PrPt (x) > 0 gilt
PrCt|Pt (y|x)
=
PrCt (y) .
Aufgabe 12 Betrachten Sie das in Abbildung 3 eingeschränkte Enigma-Verfahren. Verschlüsseln Sie
die Nachricht x = ABCABC. Sei y die verschlüsselte Nachricht. Welchen Text erhalten Sie, wenn
Sie zur Entschlüsselung die beiden Permutationen vertauschen.
Wir wollen nun eine Beziehung zwischen der Anzahl der Schlüssel und der Anzahl der möglichen
Plaintexte herleiten.
Theorem 3 Sei T Kryptosystem, welches für alle n -Gramme x, y mit PrPt (x) > 0 und PrCt (y) >
0 uneingeschränkte Sicherheit bietet. Dann gilt
|K| ≥ |{ x ∈ Zm,n | PrPt (x) > 0 }| .
Beweis: Definiere
Zm,n,Pt
:= { x ∈ Zm,n | PrPt (x) > 0 }
Zm,n,Ct
:= { x ∈ Zm,n | PrCt (x) > 0 } .
Im Folgenden nehmen wir an, dass alle Schlüssel in w ∈ K mit strikt positiver Wahrscheinlichkeit
vorkommen, d.h. Pr K (w) > 0 . Es gilt:
24
Lemma 3 Für alle Schlüssel w ∈ K ist die (eingeschränkte) Transformation Tw : Zm,n,Pt → Zm,n,Ct
injektiv.
Beweis: Aus der Definition folgt, dass vollständige Tw : Zm,n → Zm,n bijektiv ist. Ferner gilt
X
PrPt (x) · Pr K (w) .
PrCt (y) =
(x,w)∈Pt×K mit y=Tw (x)
Somit gilt genau dann PrCt (y) > 0 , wenn für ein Paar (x, w) mit y = Tw (x) die Wahrscheinlichkeiten
PrPt (x) und Pr K (w) strikt positiv sind, d.h. PrPt (x) > 0 und Pr K (w) > 0 . Da alle Schlüssel
aus K mit einer strikt positiven Wahrscheinlichkeit gewählt werden, gilt für alle Schlüssel w ∈ K
Tw (Zm,n,Pt ) ⊆ Zm,n,Ct . Folglich ist die (eingeschränkte) Transformation Tw : Zm,n,Pt → Zm,n,Ct
injektiv.
Lemma 4 Für alle Ciphertexte y ∈ Zm,n,Ct gilt:
∀x ∈ Zm,n,Pt ∃w ∈ K : Tw (x) = y .
Beweis: Der Beweis erfolgt über eine Widerspruchsannahme. Für y ∈ Zm,n,Ct sei x ∈ Zm,n,Pt ein
Plaintext, für den kein Schlüssel w mit Tw (x) = y existiert. Da T ein Kryptosystem mit perfekter
Sicherheit ist, wissen wir
PrPt (x)
=
PrPt|Ct (x|y) =
P
=
w mit Tw (x)=y
PrPt,Ct (x, y)
PrCt (y)
PrPt (x) · PrK (w)
PrCt (y)
= 0.
Dieses widerspricht der Voraussetzung von x ∈ Zm,n,Pt und somit PrPt (x) > 0 .
Lemma 5 Für alle x1 , x2 ∈ Zm,n,Pt mit x1 6= x2 und für alle w1 , w2 ∈ K mit Tw1 (x1 ) = Tw2 (x2 )
gilt w1 6= w2 .
Beweis: Der Beweis erfolgt wieder über eine Widerspruchsannahme. Seien x1 , x2 ∈ Zm,n,Pt mit
x1 6= x2 zwei Plaintexte mit Tw (x1 ) = Tw (x2 ) für einen Schlüssel w ∈ K . Wie wir oben gesehen
haben, ist Tw eingeschränkt auf Zm,n,Pt injektiv. Somit folgt aus Tw (x1 ) = Tw (x2 ) unmittelbar,
dass x1 = x2 ist.
Fassen wir die letzten beiden Lemmata zusammen, so sehen wir, dass es für jeden Ciphertext in Zm,n,Ct
und für jeden Plaintext x ∈ Zm,n mit PrPt (x) > 0 genau einen für x individuellen Schlüssel w ∈ K
geben muss, so dass Tw (x) = y ist. Folglich muss es mindestens so viele Schlüssel wie Plaintexte in
einem uneingeschränkt sicheren Kryptosystem geben.
Zunächst scheint die Generierung von uneingeschränkt sicheren Kryptosystemen wegen der enormen
Schlüsselmenge eine schwierige Aufgabe darzustellen. Betrachten wir jedoch so genannte One-TimePads, so sehen wir, dass diese Verfahren eine sehr einfache Struktur haben können. One-Time-PadVerfahren wurden 1918 von dem Amerikaner G. S. Vernam eingeführt und von C. Shannon [S49]
näher untersucht. Das wesentliche Problem bei diesen Verfahren ist die Schlüsselübergabe, da, wie
wir gesehen haben, die Anzahl der Schlüssel nach unten durch die Anzahl aller möglichen Plaintexte
beschränkt ist.
25
Sei w = (w0 , . . . , wn−1 ) eine Folge von n unabhängigen uniform verteilten Zufallsvariablen über Zm .
1
. One-Time-Pads
Das bedeutet: Für alle i ∈ {0, . . . , n − 1} und für alle z ∈ Zm gilt Pr(wi = z) = m
definieren wir als die bijektive Funktion
T (n) : X = (x0 , . . . , xn−1 ) −→ Y = (y0 , . . . , yn−1 )
mit einem randomisiert generierten Schlüssel w = (w0 , . . . , wn−1 ) , wobei für alle i ∈ {0, . . . , n − 1}
gilt
yi = Tw(n)
(xi ) := (xi + wi ) mod m .
i
Somit gilt Pr K (w) = m1n . Zudem gilt K = Zm,n und folglich |K| = mn . Da wir den Plaintext
ebenfalls aus Zm,n wählen, gibt es mindestens so viele Schlüssel wie Plaintexte. Für den One-TimePad gilt:
Theorem 4 Für jede Plaintextquelle S , sind die Zufallsvariablen y0 , . . . , yn−1 , die wir über den
oben definierten One-Time-Pad erhalten, unabhängig und uniform verteilt über Zm . Es gilt
PrCt ((y0 , . . . , yn−1 )) =
1
mn
y = (y0 , . . . , yn−1 ) ∈ Zm,n .
für alle
Beweis: Die Werte xi , yi bestimmen eindeutig den Wert wi über die Formel (yi − xi ) ≡ wi mod m .
Ferner sind die Werte wi unabhängig und uniform aus Zm gewählt. Somit gilt
X
PrPt,Ct (x, y) =
PrPt (x) · PrK (w)
(n)
k∈K mit Tw (x)=y
=
PrPt (x) ·
1
·
mn
X
w∈K mit
=
1
(n)
Tw (x)=y
1
PrPt (x) · n
m
und somit
PrCt (y)
=
X
PrPt,Ct (x, y)
x∈Zm,n
=
X
1
PrPt (x)
·
n
m
x∈Zm,n
1
.
mn
Analog können wir für jede einzelne Position yi im Ciphertext zeigen, dass
=
1
.
m
Fassen wir diese beiden Beobachtungen zusammen, so folgt, dass die Zufallsvariablen y0 , . . . , yn−1
unabhängig und uniform verteilt sind.
PrCt (yi ) =
Aus diesem Theorem folgt:
PrPt|Ct (x|y)
=
PrPt,Ct (x, y)
PrCt (y)
P
(n)
=
=
=
w∈K mit Tw (x)=y
PrPt (x) · PrK (w)
PrCt (y)
1
mn
· PrPt (x)
1
mn
PrPt (x) .
26
Dieses impliziert:
Theorem 5 Der oben definierte One-Time-Pad ist ein perfekt sicheres Kryptosystem für alle Plaintexte der Länge n .
3.2
A priori Annahmen
Zu Beginn dieses Kapitels sind wir kurz auf die a priori Annahmen über Pr K (w) und PrPt (x)
eingegangen. Eine naheliegende Annahme ist, dass die Schlüssel w über Pr K uniform verteilt sind,
d.h. jeder Schlüssel kommt mit der gleichen Wahrscheinlichkeit vor. Abhängig von der Umgebung ist
diese Annahme jedoch mit Vorsicht zu genießen, da ein Mensch, der sich einen Schlüssel frei wählen
kann, zumeist einen Schlüssel wählt, den er sich einfach merken kann. In vielen Bereichen sind wir
jedoch nicht auf das Erinnerungsvermögen von Menschen angewiesen, in diesen Fällen können wir von
einer uniformen Schlüsselverteilung ausgehen.
Für den Plaintext ist die Situation komplizierter. Zur Vereinfachung werden wir davon ausgehen, dass
die Sprache des Plaintextes dem Kryptoanalytiker bekannt ist (Analysen zur Spracherkennung sind
in [B94] zu finden). Um ein Modell für die Verteilung des Plaintextes zu bekommen können wir alle
Zeichenketten der Länge n dieser Sprache auflisten und die entsprechenden Wahrscheinlichkeiten
bestimmen. Dieses Modell zeigt jedoch zwei wesentliche Schwachstellen auf:
1. Eine entsprechende Datenbank muss eine enorme Menge an Daten verwalten.
2. Die zu berücksichtigenden Wahrscheinlichkeiten sind nummerisch schwer zu behandeln.
Daher wollen wir verschiedene eingeschränkte Modell betrachten. Diese Modelle sollen folgende Eigenschaften aufweisen:
1. Das Modell soll charakteristische Eigenschaften der Sprache hinreichend genau reflektieren. Eine
dieser Eigenschaften kann zu Beispiel die Häufigkeit bestimmter Buchstabenkombinationen sein.
So kommt in vielen Sprachen (z.B. Deutsch, Französisch, Englisch) nach dem Buchstaben q
immer der Buchstabe u. Somit existieren die Kombinationen qa und qz in diesen Sprachen
nicht.
2. Berechnungen innerhalb der Sprachrepräsentation sollen ohne große Probleme möglich sein.
Prinzipiell kann jede Sprache mit einer beliebig hohen Genauigkeit repräsentiert werden, jedoch steigt
der Aufwand der Repräsentation sehr schnell.
Die grundlegende Idee zur Modellierung einer Sprache beruht auf einen probabilistischen Prozess. Eine
Plaintextquelle modellieren wir mit Hilfe einer (endlichen oder unendlichen) Sequenz von Zufallsvariablen X0 , X1 , . . . . Einen Plaintext x = x0 , x1 , . . . erhalten wir dann über ein Zufallsexperiment aus
diesen Variablen, wobei
PrPt (x) = Pr(X0 = x0 , X1 = x1 , . . .)
ist. Eine Plaintextquelle für n -Gramme definieren wir über die Wahrscheinlichkeiten
Pr(Xj = x0 , Xj+1 = x1 , . . . , Xj+n−1 = xn−1 )
für alle (x0 , . . . , xn−1 ) ∈ Zm,n und alle j, n ∈ N .
Um ein solides mathematisches Modell zu erhalten, müssen wir garantieren, dass die folgenden Bedingungen erfüllt sind:
27
1. PrPt (x0 , . . . , xn−1 ) ≥ 0 für alle n ∈ N und (x0 , . . . , xn−1 ) ∈ Zm,n .
P
2.
(x0 ,...,xn−1 )∈Zm,n PrPt (x0 , . . . , xn−1 ) = 1 für alle n ∈ N .
P
3. PrPt (x0 , . . . , xn−1 ) = (xn ,...,xs−1 )∈Zm,n−s PrPt (x0 , . . . , xs−1 ) für alle n, s ∈ N mit s > n .
Die ersten beiden Bedingungen sind zwei klassische Axiome für Wahrscheinlichkeitsverteilungen, nicht
Negativität und Normalisierung. Die dritte Bedingung ist ein Spezialfall von Kolmogoroffs Konsistenzforderung. Diese stellt eine Verbindung zwischen Präfixen und deren Verlängerungen dar. Die Bedeutung dieser Eigenschaft zeigt sich zum Beispiel im Deutschen bei der Verknüpfung von einzelnen
Worten, wie zum Beispiel: Bügeleisen, Bügelbrett, usw.
Wir wollen jetzt auf verschiedene Quellenmodelle eingehen.
3.2.1
Variante 1: 1-Gramm-Quellen
Die einfachste Form eines Quellenmodells ist die 1-Gramm-Quelle:
Definition 4 Eine Plaintextquelle generiert 1-Gramme über Zm , indem sie eine Folge von n Symbolen x0 , . . . , xn−1 aus Zm unabhängig voneinander jeweils mit einer Wahrscheinlichkeit von p(xi )
wählt. Wir erhalten somit
n−1
Y
PrPt (x0 , . . . , xn−1 ) =
p(xi ) .
i=0
Die Wahrscheinlichkeiten p(xi ) für xi ∈ Zm müssen wir empirisch über eine Häufigkeitsanalyse bestimmen. Eine entsprechende Tabelle für Englisch haben wir bereits im Abschnitt über den FriedmanTest angegeben. Es ist einfach zu erkennen, das 1-Gramm-Quellen die drei mathematischen Bedingungen erfüllen, die wir an eine Plaintextquelle gerichtet haben. Jedoch werden von einer 1-Gramm-Quelle
viele charakteristische Eigenschaften von Sprachen nicht reflektiert, so ist PrPt (QE) ≈ 0, 000156 > 0 .
3.2.2
Variante 2: 2-Gramm-Quellen
Definition 5 Eine Plaintextquelle generiert 2-Gramme über Zm , indem sie eine Folge von n/2 Paaren von Symbolen x0 , . . . , xn−1 aus Zm unabhängig voneinander jeweils mit einer Wahrscheinlichkeit
von p(x2i x2i+1 ) wählt. Wir erhalten somit
(n−1)/2
PrPt (x0 , . . . , xn−1 ) =
Y
p(x2i x2i+1 ) .
i=0
Wie schon für 1-Gramme müssen wir auch für 2-Gramme die Wahrscheinlichkeiten p(x2i x2i+1 ) empirisch bestimmen. Um eine hinreichend gute Aussage über die Wahrscheinlichkeiten p(x2i x2i+1 ) herleiten zu können, müssen wir entsprechend große Texte analysieren. Die nachfolgenden Tabellen zeigen
die Häufigkeiten aller 262 2-Gramme eines englischen Textes der aus 67320 2-Grammen besteht. Die
Werte N (i, j) , dass heißt der Eintrag in der i ten Spalte und j ten Zeile steht für das 2-Gramm
(i, j) . Um die entsprechenden Wahrscheinlichkeiten zu erhalten, müssen wir p(i, j) = N (i, j)/67320
berechnen.
28
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
7
114
319
158
492
98
122
646
236
18
14
359
351
249
48
241
–
470
200
381
72
65
282
9
17
18
B
125
7
–
3
27
–
–
2
51
–
1
5
65
2
57
–
–
15
4
2
87
–
1
–
1
–
C
251
2
52
4
323
–
–
5
476
–
–
6
5
281
91
1
–
79
94
22
103
–
–
15
3
–
D
304
1
1
33
890
–
2
3
285
–
1
197
–
761
130
–
–
129
9
1
51
2
4
–
2
–
E
13
394
453
572
326
150
271
2053
271
26
187
513
573
549
21
310
–
1280
595
872
91
522
239
17
84
36
F
65
–
–
1
106
108
–
–
80
–
1
28
2
46
731
–
–
14
8
4
11
–
–
–
–
–
G
151
–
–
20
93
–
20
–
174
–
–
29
–
630
46
–
–
80
–
1
80
–
–
–
–
–
H
13
–
339
1
16
–
145
2
1
–
7
–
–
6
14
42
–
8
186
2161
2
–
175
1
–
–
I
311
74
202
273
118
188
95
426
10
5
56
407
259
301
52
75
–
541
390
865
54
223
259
15
20
17
J
13
7
–
5
4
–
–
–
–
–
–
–
–
4
8
–
–
–
–
–
–
–
–
–
–
–
K
67
–
86
–
27
–
–
–
31
–
4
21
–
30
44
–
–
94
30
–
3
–
–
–
1
–
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
N
1216
–
3
8
1029
1
51
14
1550
–
20
1
8
88
1232
1
–
149
7
9
318
–
44
–
5
–
O
5
118
606
111
30
326
129
287
554
45
7
208
240
239
125
268
–
510
234
756
4
46
159
1
64
4
P
144
–
–
–
143
–
–
–
62
–
–
11
139
2
164
103
–
25
128
2
81
–
–
47
9
–
Q
–
–
1
1
25
–
–
–
5
–
–
–
–
3
–
–
–
–
3
–
–
–
–
–
–
–
R
764
81
113
49
1436
142
150
56
212
1
3
9
5
5
861
409
–
97
9
295
306
–
13
–
9
–
S
648
28
23
75
917
3
29
10
741
–
39
104
47
340
201
32
–
300
277
257
256
2
45
–
44
–
T
1019
6
237
2
301
58
28
85
705
–
1
68
1
743
223
51
–
273
823
131
263
–
2
23
5
–
U
89
89
92
91
36
54
58
31
7
48
1
72
65
56
533
81
73
88
192
120
6
1
–
–
4
1
V
137
2
–
15
160
–
–
–
155
–
–
15
1
31
188
–
–
65
–
3
3
1
–
–
–
–
W
37
–
–
6
153
–
–
4
–
–
–
3
–
8
194
–
–
8
13
54
–
–
–
–
3
–
X
17
–
–
–
113
–
–
–
14
–
–
–
–
1
7
–
–
1
–
–
2
–
–
5
–
–
29
L
681
152
98
19
340
35
23
6
352
–
7
378
2
33
234
144
–
75
48
62
230
–
5
–
5
1
Y
202
143
25
40
90
5
6
15
1
–
4
219
37
71
23
3
–
140
27
125
3
5
3
–
2
–
M
182
6
4
27
253
1
3
6
184
–
1
22
126
47
397
13
–
139
37
27
69
1
–
1
11
–
Z
15
–
–
–
3
–
–
–
49
–
–
–
–
2
2
–
–
–
–
3
1
–
–
–
1
2
Es ist einfach zu erkennen, dass eine 2-Gramm-Quelle die englische Sprache viel besser reflektiert als
eine 1-Gramm-Quelle. So gilt PrPt (QE) = 0 und PrPt (HELP ) = 0, 0000061 > 0 = PrPt (LHEP ) .
Auf der anderen Seite gilt
PrPt (HELP ) = 0, 0000061 < 0, 0000064 = PrPt (HEP L) ,
obwohl HEPL kein englischer Begriff ist. Um solche Fehlerwahrscheinlichkeiten noch weiter zu reduzieren, müssen wir t -Gramme für t > 2 analysieren. Hier entsteht jedoch das Problem, dass die
dazugehörigen Tabellen exponentiell in t wachsen und die benötigte Datenmenge enorm ist.
3.2.3
Variante 3: Markov-Ketten
Eine dritte Variante zur Modellierung von Plaintextquellen erhalten wir über das Markov-Kettenmodell.
Definition 6 Eine Plaintextquelle generiert 1-Gramme aus Zm über eine Markov-Kette mit Übergangswahrscheinlichkeiten P = (p(s|t))s,t∈Zm und mit Initialwahrscheinlichkeiten π = (π(s))s∈Zm ,
wenn für alle n ∈ N und alle x = (x0 , . . . , xn−1 ) ∈ Zm,n gilt
PrPt (x0 , . . . , xn−1 ) = π(x0 ) ·
n−2
Y
p(xi+1 |xi ) .
i=0
Ferner müssen die folgenden Bedingungen erfüllt sein:
1. p(s|t) ≥ 0 für alle s, t ∈ Zm .
P
2.
s∈Zm p(s|t) = 1 für alle t ∈ Zm .
P
3. π(s) ≥ 0 für alle s ∈ Zm und
s∈Zm π(s) = 1 .
P
4. π(s) = t∈Zm π(t) · p(s|t) für alle s ∈ Zm .
Das Ziel des Markov-Ketten Modells ist es, die Sprache mit Hilfe eines probabilistischen endlichen Automaten zu beschreiben, der m Zustände besitzt. Mit der Wahrscheinlichkeitsverteilung π bestimmen
wir das Symbol, mit dem der Text beginnen soll. Die Wahrscheinlichkeiten p(s|t) beschreiben uns
dann eine Fortsetzung des Textes. Die Wahrscheinlichkeiten p(s|t) können wir mit Hilfe der Tabelle
der 2-Gramme im letzten Abschnitt berechnen. Es gilt
p(s|t) =
N (t, s)
.
h∈Zm N (h, t)
P
Die Wahrscheinlichkeiten π für die englische Sprache sind in der nachfolgenden Tabelle wiedergegeben.
A
B
C
D
E
F
G
π
0,0723
0,0060
0,0282
0,0483
0,1566
0,0167
0,0216
H
I
J
K
L
M
N
π
0,0402
0,0787
0,0006
0,0064
0,0396
0,0236
0,0814
O
P
Q
R
S
T
U
30
π
0,0716
0,0161
0,0007
0,0751
0,0715
0,0773
0,0272
V
W
X
Y
Z
π
0,0117
0,0078
0,0030
0,0168
0,0010
Die Werte von π können aus den bedingten Wahrscheinlichkeiten P wie folgt bestimmt werden:
Stellen wir π als (Zeilen-)Vektor und P als Matrix dar, so folgt aus der vierten Eigenschaft, die wir
von dem Markov-Ketten Modell gefordert haben:
π = π·P .
Sei π (`) (j) die Wahrscheinlichkeit, dass die Markov-Kette im ` ten Schritt im Zustand j ist, dass
heißt π (`) (j) = Pr(X`−1 = j) . Aus der Definition folgt unmittelbar π (0) (j) = π(j) und aus der vierten
Eigenschaft der Markov-Ketten π (`) (j) = π(j) für alle ` ∈ N . Die Wahrscheinlichkeiten π (`) (j) sind
somit stationär. Um die Wahrscheinlichkeiten π zu erhalten, genügt es somit die Gleichung π = π · P
zu lösen. Die Lösung dieses Systems wird in vielen Standardwerken beschrieben, siehe hierzu [F68].
Es ist jedoch auch für das Markov-Ketten Modell einfach zu erkennen, dass es eine Sprache nicht
perfekt beschreibt. So gilt weiterhin
PrPt (HELP ) < PrPt (HEP L) .
Aufgabe 13 Betrachten Sie folgendes Szenario: Alice möchte, dass Bob einen Multiple-Choice Test
ausfüllt. Hierzu würfelt sie für jedes Kästchen ki des Tests ein Zufallsbit ri und sendet den Test
mit der Zufallssequenz r = (r0 , . . . , rn−1 ) an Bob mit Hilfe eines Kuriers Eve. Bob füllt jetzt den
Test aus, indem er die Sequenz x = (r0 ⊕ x0 , . . . , rn−1 ⊕ xn−1 ) berechnet. Hierbei stehen die Werte
xi für die binäre Kodierung der Ja/Nein-Antwort für Kästchen ki . Im Anschluss nimmt Bob mit
einem neuen Kurierdienst Eva Kontakt auf. Nachdem er sich davon überzeigt hat, dass Eva nicht Eve
ist, sendet er seine Antworten über Eva an Alice. Zeigen Sie, dass das so benutzte Verfahren perfekte
Sicherheit für die Antworten von Bob garantiert.
Aufgabe 14 Weisen Sie für die drei oben beschriebenen Varianten von Plaintextquellen nach, dass
diese die drei geforderten mathematischen Bedingungen an eine Plaintextquelle erfüllen.
Aufgabe 15 Erweitern Sie das Markov-Ketten Modell darauf, dass es bei den bedingten Wahrscheinlichkeiten die letzten ` Symbole des Plaintextes berücksichtigt.
3.3
Bayes’scher Ansatz in der Kryptoanalyse
Im Folgenden wollen wir uns mit der Aufgabe des Kryptoanalytikers näher beschäftigen. Diese besteht
in erster Linie aus der Suche nach einer Funktion δ , welche einen gegebenen Ciphertext korrekt
entschlüsselt.
Definition 7 Eine deterministische Entscheidungsfunktion δ = (δ (n) )n∈N ist eine Sequenz von
Transformationen δ (n) : Zm,n → Zm,n . Die Menge aller deterministischen Entscheidungsfunktionen
bezeichnen wir mit ∆D .
Wie oben schon angedeutet, soll eine Entscheidungsfunktion einen verschlüsselten Text entschlüsseln,
dass heißt, sie soll auf Eingabe einen Ciphertextes y einen Plaintext x ausgeben, so dass bei der Wahl
eines entsprechenden Schlüssels w y = Tw (x) ist. Da diese Funktion deterministisch ist, generiert
sie auch für andere Plaintext-Schlüssel-Paare (x0 , w0 ) mit y = Tw0 (x0 ) als Ausgabe den Plaintext x .
Ergebnisse der Form Tw0 (x0 ) 6= x0 sind fehlerhaft. Um die Qualität einer deterministischen Entscheidungsfunktion bei der Entschlüsselung von Ciphertexten zu messen, definieren wir den Verlust einer
Entscheidungsfunktion:
31
Definition 8 Sei δ ∈ ∆D , dann definieren wir die Verlustfunktion Lδ von δ für alle x ∈ Pt und
y ∈ Ct durch
1 für δ(y) 6= x
Lδ (x, y) =
0 für δ(y) = x .
Da es sich beim Plaintext und dem Ciphertext um Zufallsvariablen handelt, interessiert uns unter
anderem der erwartete Verlust einer Entscheidungsfunktion. Wir definieren daher
X
Ln,δ := E[Lδ(n) ] =
PrPt,Ct (x, y) · Lδ (x, y)
x,y∈Zm,n
und
Lδ := { Ln,δ | n ∈ N } .
Unser Ziel ist es einen Entscheidungsfunktion zu finden, welche den erwarteten Verlust minimiert.
Definition 9 Eine deterministische Entscheidungsfunktion δ ∗ nennen wir optimal, wenn
1. δ ∗ ∈ ∆D ist und
2. für alle δ ∈ ∆D und alle n ∈ N gilt Ln,δ∗ ≤ Ln,δ .
Eine spezielle Form der Entscheidungsfunktionen erhalten wir mit folgender Definition:
Definition 10 Eine deterministische Entscheidungsfunktion δB nennen wir Bayes’sche Entscheidungsfunktion, wenn
PrPt|Ct (δB (y)|y) = max PrPt|Ct (x|y) .
x∈Zm,n
Man beachte, dass δB (y) genau dann definiert ist, wenn PrCt (y) > 0 ist.
Abhängig von der Verteilung PrPt ist es möglich, dass für verschiedene Ciphertexte y Plaintexte x
existieren, so dass bei geeignetem Schlüssel w Tw (x) = y ist und zudem PrPt (x) maximal ist. Es
kann daher mehrere verschiedene Bayes’sche Entscheidungsfunktion geben. Die wesentliche Bedeutung
dieser Entscheidungsfunktionen folgt aus dem nachfolgenden Theorem:
Theorem 6 Eine deterministische Entscheidungsfunktion δ ist genau dann optimal, wenn sie eine
Bayes’sche Entscheidungsfunktion ist.
Beweis: Es gilt:
Ln,δ
= E[Lδ(n) ]
X
=
PrPt,Ct (x, y) · Lδ (x, y)
x,y∈Zm,n
=
X
PrCt (y) · PrPt|Ct (x|y) · Lδ (x, y)
x,y∈Zm,n
=
X
X
PrCt (y) · PrPt|Ct (x|y) · Lδ (x, y)
y∈Zm,n x∈Zm,n
=
X
y∈Zm,n
PrCt (y) ·
X
x∈Zm,n
32
PrPt|Ct (x|y) · Lδ (x, y)
Zur Vereinfachung der zweiten Summe setzen wir nun unser Wissen über die Definition von Lδ (x, y)
ein: Lδ (x, y) ist genau dann 0, wenn δ(y) = x ist.
X
X
PrCt (y) ·
PrPt|Ct (x|y) · Lδ (x, y)
Ln,δ =
y∈Zm,n
=
X
x∈Zm,n mit δ(y)6=x
X
PrCt (y) ·
y∈Zm,n
PrPt|Ct (x|y)
x∈Zm,n mit δ(y)6=x
Da für jedes y maximal ein x existiert, so dass δ(y) = x ist, können wir im nächsten Schritt diese
Formel insoweit vereinfachen, dass wir in der zweiten Summe die Komplementärmenge betrachten:


X
X
Ln,δ =
PrCt (y) · 1 −
PrPt|Ct (x|y)
y∈Zm,n
=
X
x∈Zm,n mit δ(y)=x
PrCt (y) · 1 − PrPt|Ct (δ (n) (y)|y) .
y∈Zm,n
Wir wollen nun die beiden Richtungen des Theorems beweisen:
1. Die Entscheidungsfunktion δ ist genau dann optimal, wenn Ln,δ minimal ist.
2. Da die Entscheidungsfunktion δ (n) für jedes y unabhängig von anderen Ciphertexten y 0 gewählt
werden kann, und PrCt (y) unabhängig von δ (n) (y) ist, gilt: Ln,δ ist genau dann minimal, wenn
für alle y PrPt|Ct (δ (n) (y)|y) maximal ist, d.h.
PrPt|Ct (δ (n) (y)|y) =
max PrPt|Ct (x|y) .
x∈Zn,m
Fassen wir zusammen: Die Entscheidungsfunktion δ ist genau dann optimal, wenn δ eine Bayes’sche
Entscheidungsregel ist.
Wir wollen nun ein Beispiel für Entscheidungsfunktionen diskutieren. Als Verschlüsselungsfunktion
betrachten wir
T7 (i) ≡ i + 7 mod 26
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
Wir verschlüsseln den Plaintext SENDHELP und erhalten den Ciphertext ZLUKOLSW. Um eine optimale Entscheidungsfunktion zu finden, benötigen wir die Werte der bedingten Wahrscheinlichkeiten
PrPt|Ct (x|ZLU KOLSW ) .
Für alle 268 8-Gramme x . Da wir jedoch annehmen, dass der Kryptoanalytiker das benutzte Verschlüsselungsverfahren kennt, können wir die Anzahl der betrachteten 8-Gramme auf 26 reduzieren.
Ersetzen wir in y die Zeichen durch die entsprechenden Werte, so erhalten wir
y = (y0 , y1 , y2 , y3 , y4 , y5 , y6 , y7 ) = (25, 11, 20, 10, 14, 11, 18, 22)
und für die interessanten 8-Gramme
y−w
=
(y0 − w, y1 − w, y2 − w, y3 − w, y4 − w, y5 − w, y6 − w, y7 − w)
=
(25 − w, 11 − w, 20 − w, 10 − w, 14 − w, 11 − w, 18 − w, 22 − w) mod 26 .
33
Für die zu betrachtenden Wahrscheinlichkeiten gilt
 1
 26 · PrPt (y − w mod 26)
PrPt,Ct (x, y) =

0
und
PrCt (y) =
X
PrPt,Ct (x, y) =
x∈Z26,8
für x = y − w mod 26
mit k ∈ {0, . . . , 25}
sonst.
25
X
1
· PrPt (y − w mod 26) .
26
w=0
Fassen wir zusammen:
PrPt (y − w mod 26)
PrPt|Ct (y − w mod 26|y) = P25
.
k=0 PrPt (y − k mod 26)
Die nachfolgende Tabelle fasst die Wahrscheinlichkeiten PrPt|Ct (y − w mod 26|y) für die Plaintextquellen aus Definition 4 bis 6 zusammen:
k
Y −k
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ZLUKOLSW
YKTJNKRV
XJSIMJQU
WIRHLIPT
VHQGKHOS
UGPFJGNR
TFOEIFMQ
SENDHELP
RDMCGDKO
QCLBFCJN
PBKAEBIM
OAJZDAHL
NZIYCZGK
MYHXBYFJ
LXGWAXEI
KWFVZWDH
JVEUYVCG
IUDTXUBF
HTCSWTAE
GSBRVSZD
FRAQURTC
EQZPTQXB
DPYOSPWA
COXNROVZ
BNWMQNUY
AMVLPMTX
PrPt
nach Def. 4
0,00002353
0,00000736
0,00000003
0,05269719
0,00004373
0,00012522
0,00601645
0,35013155
0,00158882
0,00000412
0,00100489
0,00013951
0,00000043
0,00000164
0,00007197
0,00000134
0,00001388
0,00037299
0,58014350
0,00006560
0,00066643
0,00000002
0,00658287
0,00003584
0,00005462
0,00020646
PrPt
nach Def. 5
0,00000089
0,00000000
0,00000000
0,00418837
0,00000000
0,00000000
0,00000000
0,99580491
0,00000088
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000495
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
PrPt
nach Def. 6
0,00000309
0,00000000
0,00000000
0,00033815
0,00000000
0,00000000
0,00000000
0,99965766
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000111
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
0,00000000
Demnach würde eine optimale Entscheidungsfunktion unter der Annahme, dass eine 1-Gramm Plaintextquelle vorliegt den Text HTCSWTAE liefern und für die beiden anderen oben vorgestellten Plaintextquellen den Plaintext SENDHELP.
34
4
Symmetrische Verschlüsselungsalgorithmen
Definition 11 Ein symmetrisches Kryptosystem ist ein Verschlüsselungssystem, welches den
gleichen Schlüssel zur Ver- und Entschlüsselung verwendet. Bei manchen symmetrischen Verfahren
(z. B. IDEA) ist es notwendig, den aus dem Verschlüsselungs-Schlüssel einen EntschlüsselungsSchlüssel zu berechnen. Im Gegensatz hierzu benutzt ein asymmetrischen Kryptosystem zur Verund Entschlüsselung ein Schlüsselpaar.
Wir unterteilt die symmetrischen Verfahren in Blockchiffren und Stromchiffren.
• Bei einem Stromchiffre wird der Plaintext Zeichen für Zeichen ver- bzw. entschlüsselt.
• Bei einem Blockchiffre wird der Plaintext Block für Block ver- bzw. entschlüsselt, wobei die Blöcke
eine feste Größe haben. In einem Schritt werden somit mehrere Zeichen ver- bzw. entschlüsselt.
Die bisher vorgestellten Verfahren zählen (mehr oder weniger) zu den Stromchiffresysteme. Im Folgenden werden wir nun die beiden bekanntesten symmetrischen Verschlüsselungsalgorithmen vorstellen:
den DES und den AES.
4.1
Der Data Encryption Standard (DES)
Bis 1970 wurde die Kryptographie vom Militär dominiert. 1973 wurde daher vom National Bureau of
Standards (NBS) der USA eine erste Ausschreibung für ein standardisiertes Verschlüsselungsverfahren
gestartet. 1975 wurde das DES im Federal Register veröffentlicht und galt viele Jahre als Standardkryptosystem für kommerzielle Anwendungen. Seit 1994 gelang es das DES durch immer weiter verbesserte Verfahren immer schneller zu knacken. Daraufhin wurde 1999 der Triple-DES (TDES, 3DES)
als neuer Standard veröffentlicht und 2005 der DES als Standard außer Kraft gesetzt. 2006 wurde ein
FPGA-basierte Parallelrechner COPACOBANA vorgestellt mit dessen Hilfe das DES in weniger als
9 Tagen geknackt werden konnte. Die Materialkosten dieses Rechners liegen unter 10.000 Dollar. Die
folgende Beschreibung des DES und des TDES folgt der Beschreibung aus [FIPS99].
4.1.1
Aufbau des DES-Kryptosystems
Das DES-System verschlüsselt einen 64-Bit Block mit Hilfe eines 64-Bit Schlüssels K . 56 Bit des
Schlüssels sind frei wählbar. Jedes 8-te Bit des Schlüssels ist so gewählt, dass in jedem 8-Bit Block
des Schlüssels eine ungerade Anzahl von 1-en stehen. Die Verschlüsselung geschieht in 18 Stufen:
• Die erste und die letzte Stufe bestehen aus einer festen Permutation der Eingabe bzw. der
Ausgabe.
• Die eigentliche Verschlüsselung geschieht in den 16 verbleibenden Stufen.
Aus dem Plaintext x wird mit Hilfe einer Permutation IP (initial permutation) die permutierte
Eingabe generiert, die wir in zwei Hälften L0 und R0 aufteilen.
35
Für die nächsten 16 Stufen (den Verschlüsselungsstufen) generieren wir aus dem Schlüssel K jeweils
ein 48-Bit Teilschlüssel Ki . In den Verschlüsselungsstufen berechnen wir für i ∈ [1..16]
Li
:= Ri−1
Ri
:= Li−1 ⊕ f (Ri−1 , Ki )
wobei ⊕ das Bitweise xor der beiden binären Zeichenketten bezeichnet. Auf die Berechnung von f
werden wir noch eingehen. Nach den 16 Verschlüsselungsstufen erhalten wir den Preoutput R16 L16
aus dem wir über die inverse Permutation IP −1 die Ausgabe generieren.
R1 = L0 ⊕ f (R0 , K1 )
R16 = L15 ⊕ f (R15 , K16 )
K1
R0
I
R1
R16
O
U
N
P
IP
IP −1
f
U
T
T
P
U
⊕
L0
L0 R0 = IP (x)
L1
L16
L1 = R0
L16 = R15
T
Die einzelnen Permutationen (in der Konstruktion von f und bei der Erzeugung der Teilschlüssel werden noch weitere Permutationen vorgestellt) sollen unter anderem eine möglichst gut Durchmischung
der Bits des Plaintextes garantieren. Neben der gut Durchmischung soll durch die Permutationen
auch garantiert werden, dass einzelne Bits des Plaintexts möglichst viele Stellen des Ciphertextes
beeinflussen. So unterscheidet sich die Ciphertexte von
x1 = 064
und x2 = 063 1
bereits nach der 3-ten Verschlüsselungsstufen in 21 Bits und nach Abschluß der DES Verschlüsselung
in 34 Bits. Einen derartigen Effekt nennen wir auch Lawineneffekt.
Im Folgenden zählen wir die Bitpositionen in einem Binärstring mit den Werten i = 1, 2, . . . , 64 auf.
Für IP bzw. für IP −1 wählen wir:
IP
58
60
62
64
57
59
61
63
50
52
54
56
49
51
53
55
42
44
46
48
41
43
45
47
34
36
38
40
33
35
37
39
36
26
28
30
32
25
27
29
31
18
20
22
24
17
19
21
23
10
12
14
16
9
11
13
15
2
4
6
8
1
3
5
7
IP−1
40 8
39 7
38 6
37 5
36 4
35 3
34 2
33 1
48
47
46
45
44
43
42
41
16
15
14
13
12
11
10
9
56
55
54
53
52
51
50
49
24
23
22
21
20
19
18
17
64
63
62
61
60
59
58
57
32
31
30
29
28
27
26
25
Die Lesweise dieser Tabellen ist wie folgt:
• Für eine n × m -Tabelle T sei T [i, j] der Wert in der i -ten Spalte und j -ten Zeile von T .
• Für einen n · m -Bit String w ist u = T (w) der String, der an der Position i + (j − 1) · n mit
i ∈ [1..n] und j ∈ [1..m] das T [i, j] -te Zeichen von w stehen hat.
Somit steht in der permutierten Eingabe IP (x) an der ersten Stelle das 58-ste Bit der Eingabe, an
der zweiten Stelle das 50-ste Bit der Eingabe, u.s.w.
4.1.2
Berechnung der Funktion f
Die Funktion f verknüpft wie folgt Ri mit dem Teilschlüssel Ki+1 :
1. Mit Hilfe der Tabelle E expandieren wir Ri auf 48 Bits, indem wir 16 der 32 Bits verdoppeln.
2. Das expandierte Ri wird bitweise mit Ki+1 ge-xor-ed.
3. Den resultierenden String teilen wir in 8 Blöcke Bi a 6 Bit auf, d.h.
B1 . . . B8 = Ki+1 ⊕ E(Ri ) .
4. Auf den i -ten 6-Bit Block Bi wenden wir die über Si gegebene S -Box-Operation Si (Bi ) an.
Diese S -Box-Operation reduziert die 6-Bit eines Blocks Bi auf 4-Bits.
5. Die konkatenierte Folge der 4-Bit Blöcke Si (Bi ) permutieren wir abschließende mit Hilfe der
Permutation P . Das 32-Bit Resultat dieser Permutation gibt uns das Resultat Funktion f an.
Ri (32 Bits)
E
48 Bits
Ki+1 (48 Bits)
⊕
S8
S1
P
Ri+1 (32 Bits)
37
Wir wollen nun zunächst die beiden Tabellen E und P vorstellen, und im Anschluß auf die S -BoxOperation eingehen. Die Expandierungstabelle E hat die folgende Gestallt:
32
4
8
12
16
20
24
28
1
5
9
13
17
21
25
29
2
6
10
14
18
22
26
30
3
7
11
15
19
23
27
31
4
8
12
16
20
24
28
32
5
9
13
17
21
25
29
1
Die erste Zeile von E(Ri ) wird (nach dem xor-en mit einem Teil des Teilschlüssel) in der ersten
S -Box-Operation weiterverarbeitet, die zweite Zeile in der zweiten S -Box-Operation und so weiter.
Man beachte, dass die letzten beiden Einträge jeder Zeile den ersten beiden Einträgen der Folgezeile
entsprechen.
Die Tabelle P hat die folgende Gestallt:
16
29
1
5
2
32
19
22
7
12
15
18
8
27
13
11
20
28
23
31
24
3
30
4
21
17
26
10
14
9
6
25
Wie die Permutation IP realisiert die Permutation P wieder eine gute Durchmischung des resultierenden Binärstrings. Beachte, dass dieses bei E nicht der Fall ist.
Die Si -Box-Operation ist wie folgt aufgebaut:
• Wir betrachten den 6-Bit Block Bi und unterteilen den Binärstring in zwei Teile: in die ersten
beiden Bits Bi1 und in die verbleibenden 4 Bits Bi2 .
• Das Ergebnis der Si -Box-Operation ist der Binärstring des Werts der Tabelle Si in der Bi1 -ten
Zeile und der Bi2 -ten Spalte. Hierbei werden Bi1 und Bi2 als Zahlen interpretiert.
Designkriterien für gut S -Boxen wurden in [C94] veröffentlicht. Im Folgenden werden wir die S Boxen des DES-Systems vorstellen:
S1
0
1
2
3
0
14
0
4
15
1
4
15
1
12
2
13
7
14
8
3
1
4
8
2
4
2
14
13
4
5
15
2
6
9
6
11
13
2
1
7
8
1
11
7
38
8
3
10
15
5
9
10
6
12
11
10
6
12
9
3
11
12
11
7
14
12
5
9
3
10
13
9
5
10
0
14
0
3
5
6
15
7
8
0
13
4.1.3
S2
0
1
2
3
0
15
3
0
13
1
1
13
14
8
2
8
4
7
10
3
14
7
11
1
4
6
15
10
3
5
11
2
4
15
6
3
8
13
4
7
4
14
1
2
S3
0
1
2
3
0
10
13
13
1
1
0
7
6
10
2
9
0
4
13
3
14
9
9
0
4
6
3
8
6
5
3
4
15
9
6
15
6
3
8
7
5
10
0
7
S4
0
1
2
3
0
7
13
10
3
1
13
8
6
15
2
14
11
9
0
3
3
5
0
6
4
0
6
12
10
5
6
15
11
1
6
9
0
7
13
8
9
12
5
11
9
7
0
8
6
10
2
1
12
7
11
13
10
6
12
12
12
6
9
0
13
0
9
3
5
14
5
11
2
14
15
10
5
15
9
8
1
2
11
4
9
13
8
1
15
10
12
5
2
14
11
7
14
12
3
12
11
12
5
11
13
4
11
10
5
14
2
15
14
2
15
8
1
7
12
7
10
3
13
8
8
1
4
15
9
9
2
7
1
4
10
8
2
3
5
11
5
12
14
11
12
11
1
5
12
13
12
10
2
7
14
4
14
8
2
15
15
9
4
14
S5
0
1
2
3
0
2
14
4
11
1
12
11
2
8
2
4
2
1
12
3
1
12
11
7
4
7
4
10
1
5
10
7
13
14
6
11
13
7
2
7
6
1
8
13
8
8
5
15
6
9
5
0
9
15
10
3
15
12
0
11
15
10
5
9
12
13
3
6
10
13
0
9
3
4
14
14
8
0
5
15
9
6
14
3
S6
0
1
2
3
0
12
10
9
4
1
1
15
14
3
2
10
4
15
2
3
15
2
5
12
4
9
7
2
9
5
2
12
8
5
6
6
9
12
15
7
8
5
3
10
8
0
6
7
11
9
13
1
0
14
10
3
13
4
1
11
4
14
10
7
12
14
0
1
6
13
7
11
13
0
14
5
3
11
8
15
11
8
6
13
S7
0
1
2
3
0
4
13
1
6
1
11
0
4
11
2
2
11
11
13
3
14
7
13
8
4
15
4
12
1
5
0
9
3
4
6
8
1
7
10
7
13
10
14
7
8
3
14
10
9
9
12
3
15
5
10
9
5
6
0
11
7
12
8
15
12
5
2
0
14
13
10
15
5
2
14
6
8
9
3
15
1
6
2
12
S8
0
1
2
3
0
13
1
7
2
1
2
15
11
1
2
8
13
4
14
3
4
8
1
7
5
15
3
12
10
6
11
7
14
8
7
1
4
2
13
8
10
12
0
15
9
9
5
6
12
10
3
6
10
9
11
14
11
13
0
12
5
0
15
3
13
0
14
3
5
14
12
9
5
6
15
7
2
8
11
4
6
10
9
4
Die Teilschlüssel Ki
Die Konstruktion der Teilschlüssel Ki erfolgt wieder in mehreren Stufen:
39
1. Im ersten Schritt werden mit Hilfe der Tabelle PC-1 der Schlüssel K permutiert und die redundanten Kontroll-Bits heraus gefiltert. Dieses sind die Bits 8, 16, 24, 32, 40, 48, 56, 64.
2. Die verbleibenden 56 Bits werden in zwei 28-Bit Blöcke aufgeteilt: C0 und D0 .
3. Sukzessive generieren wir aus C0 die Folge C1 , . . . , C16 und aus D0 die Folge D1 , . . . , D16 .
Hierbei erhalten wir aus Ci−1 und Di−1 über zyklische Shifts die Blöcke Ci und Di . Die
Anzahl der Shifts ist von i abhängig.
4. Aus der Konkatenation der Blöcken Ci und Di selektieren wir über die Tabelle PC-2 den
Teilschlüssel Ki .
Die folgende Graphik illustriert das zusammenwirken der einzelnen Schritte:
K
K1
K16
PC-2
PC-2
C0
Linksshift
C1
Linksshifts
C2
C16
D0
Linksshift
D1
Linksshifts
D2
D16
e
y
K
PC-1
C0 D0 = PC-1 (K)
Die Tabelle PC-1 hat die folgende Gestalt:
57
1
10
19
63
7
14
21
49
58
2
11
55
62
6
13
41
50
59
3
47
54
61
5
33
42
51
60
39
46
53
28
25
34
43
52
31
38
45
20
17
26
35
44
23
30
37
12
9
18
27
36
15
22
29
4
und die Tabelle PC-2 die folgende Gestalt:
14
3
23
16
41
30
44
46
17
28
19
7
52
40
49
42
11
15
12
27
31
51
39
50
24
6
4
20
37
45
56
36
40
1
21
26
13
47
33
34
29
5
10
8
2
55
48
53
32
Die Anzahl der Shifts um aus Ci−1 den Block Ci bzw. aus Di−1 den Block Di zu generieren hängt
von i ab:
i:
Anzahl der Shifts:
i:
Anzahl der Shifts:
1
1
9
1
2
1
10
2
3
2
11
2
4
2
12
2
5
2
13
2
6
2
14
2
7
2
15
2
8
2
16
1
Mit Hilfe der Tabelle PC-2 wählen wir wählen wir die 48 Bits des Teilschlüssels Ki des 56-Bit
Schlüssels Ci Di aus. Der Schlüssel setzt sich bei jedem Auswahlschritt aus der Konkatenation der
beiden aktuellen Blöcke Ci Di zusammen. Da wir die beiden Blöcke des 56-Bit Schlüssels vor jedem
Auswahlschritt zyklisch Shiften, wird bei jedem Auswahlschritt eine veränderte Kollektion an Bits
ausgewählt.
4.1.4
Die Entschlüsselöung eines DES-Cyphertextes
Die Entschlüsselung eines DES-Cyphertextes geschieht mehr oder weniger über das gleiche Verfahren,
mit dem wir die Verschlüsselung vorgenommen haben. Wir starten mit der folgenden Beobachtung:
Da sich Li ohne Veränderung aus Ri−1 ergibt, können wir die Formel
Ri = Li−1 ⊕ f (Ri−1 , Ki )
umstellen zu
Ri = Li−1 ⊕ f (Li , Ki ) .
Die Teilschlüssel Ki sind unabhängig von Eingabe und von Li und Ri und können daher unabhängig vom aktuellen Zustand des Systems generiert werden. Daher ist es möglich die obige Formel
so umzustellen, dass wir den Wert Li−1 aus Ri und Li bestimmen können. Wir erhalten
Li−1 = Ri ⊕ f (Li , Ki ) .
und nach Konstruktion
Ri−1 = Li .
Die folgenden Graphik illustriert die Entschlüsselöung eines DES-Cyphertextes:
L15 = R16 ⊕ f (L16 , K16 )
L0 = R1 ⊕ f (L1 , K1 )
K16
L16
I
L15
L0
O
U
N
P
IP
IP −1
f
U
T
T
P
U
R16
R16 L16 = IP (y)
⊕
R15
R0
R15 = L16
R0 = L1
41
T
4.2
Das Triple DES-Kryptosystem (TDES)
Aufgrund der immer schnelleren Attacken gegen das DES-System wurde 1999 ein modifiziertes DESSystem, das TDES, vorgestellt. Ziel des TDES-Kryptosystems war es, dass DES-Kryptosystem sicherer
gegen Angriffe zu machen. Hierbei sollte sowohl die Verschlüsselung als auch die Entschlüsselung mit
Hilfe des einfachen DES möglich sein. Ferner sollte es mit dem neuen System auch möglich sein
Ciphertexte, die mit DES verschlüsselt wurden, zu entschlüsseln.
Ein erster Ansatz besteht darin einen Text mehrmals mit DES unter verschiedenen Schlüsseln zu
verschlüsseln. Dieses würde zwar das System sicherer machen, jedoch würden die Schwächen des DES
erhalten bleiben. Der TDES wählt einen anderen Ansatz.
Sei EK (x) die Verschlüsselung von x mit Hilfe des DES-Kryptosystems unter dem Schlüssel K und
sei DK (y) die Entschlüsselung von y mit Hilfe des DES-Kryptosystems unter dem Schlüssel K .
Seien K1 , K2 , K3 drei Schlüssel, dann erhalten wir die Verschlüsselung von x mit Hilfe des TDESKryptosystems unter dem Schlüssel K1 , K2 , K3 über
EK3 (DK2 (EK1 (x)))
und die dazugehörige Entschlüsselung über
DK1 (EK2 (DK3 (x)))
Beim TDES unterscheiden wir drei verschiedene Betriebsformen:
1. Alle Schlüssel sind paarweise unterschiedlich,
2. K1 = K3 6= K2 und
3. K1 = K2 = K3 . Dieses entspricht dem DES-Kryptosystems, der TDES ist somit abwärtskompatibel.
4.3
Iterierte Blockkryptosysteme
Bevor wir auf die Kryptoanalyse des DES-Kryptosystems eingehen, werden wir noch einige Verallgemeinerungen des DES-Kryptosystems vorstellen.
Definition 12 Ein iteriertes r -Runden Blockkryptosystem besteht aus einer Rundenfunktion g : Zm,n × Zk,l → Zm,n , welche in r Runden den Plaintext x ∈ Zm,n mit Hilfe der Rundenschlüssel K1 , . . . , Kr ∈ Zk,l verschlüsselt. Setzen wir y 0 := x , so erhalten wir
yi
= g(y i−1 , Ki )
und erhalten den Ciphertext y := y r . Um den Ciphertext entschlüsseln zu können, muss es möglich
sein für jeden festen Rundenschlüssel die Umkehrfunktion von g zu berechnen.
Viele Kryptosysteme basieren auf den Operationen auf endlichen Körpern, daher werden wir nachfolgend einige Begriffe wiederholen.
Definition 13 Sei K eine Menge (mit mindestens zwei Elementen) und + , · zwei Verknüpfungen
auf K . (K, +, ·) heißt Körper, wenn für alle a, b, c ∈ K die folgenden Gesetzmäßigkeiten gelten:
42
Assoziativgesetz bezüglich +
• : a + (b + c) = (a + b) + c
Kommutativgesetz bezüglich +
• : a+b=b+a
Assoziativgesetz bezüglich ·
• : a · (b · c) = (a · b) · c
Kommutativgesetz bezüglich ·
• : a·b=b·a
Distributivegesetz
• : a · (b + c) = a · b + a · c
neutrales Element bezüglich +
• : ∃0 ∈ K∀a ∈ K : a + 0 = a
inverses Element bezüglich +
• : ∀a ∈ K∃ − a ∈ K : −a + a = 0
neutrales Element bezüglich ·
• : ∃1 ∈ K∀a ∈ K : a · 1 = a
inverses Element bezüglich ·
• : ∀a ∈ K∃a−1 ∈ K : a−1 · a = 1
Für den endlichen Körper mit zwei Elementen {0, 1} mit
0 + 0 = 1 + 1 = 0, 0 + 1 = 1 + 0 = 1, 0 · 0 = 0 · 1 = 1 · 0 = 0, 1 · 1 = 1
bezeichnen wir mit F2 oder GF (2) .
Besonders interessieren uns endlichen Körper.
Definition 14 Einen endlichen Körper, d.h. den Menge K des Körpers (K, +, ·) umfasst endlich
viele Elemente, nennen wir auch Galoiskörper oder Galoisfeld GF (|K|) . Von besonderem Interesse sind Galoisfelder deren Größe eine Primzahlpotenz ist, d.h. Galoisfelder mit |K| = pn für
eine Primzahl p . Wir bezeichnen ein solches Feld auch mit GF (pn ) . Da alle endlichen Körper der
gleichen Kardinalität zueinander isomorph sind, können wir uns auf die Polynomrepräsentation des
Körpers einschränken:
• Es sei K ein Körper. Dann heißt ein Polynom f ∈ K[x] in der Variable x irreduzibel, wenn
f nicht konstant ist und es keine nicht konstanten Polynome g, h ∈ K[x] gibt, so dass f = g · h
ist.
• Eine Polynomrepräsentation von GF (pn ) generieren wir wie folgt:
– Wähle ein irreduzibels Polynom g ∈ GF(p)[x] vom Grad n und Koeffizienten in GF (p) –
ein solchen Polynom existiert immer wenn GF (pn ) existiert.
– Wir erhalten die gewünschte Repräsentation über GF (p)[x]/(g(x)) :
∗ Die Elemente von GF (p)[x]/(g(x)) erhalten wir über die Menge aller Polynome mit
Grad kleiner n und Koeffizienten aus GF (p) .
43
∗ + entspricht der Polynomaddition, wobei wir die jeweiligen Koeffizienten modulo p
addieren.
∗ · entspricht der Polynommultiplikation, wobei wir zunächst den Grad mit Hilfe der Polynomdivision durch g(x) reduzieren. Der Rest bei der Division, d.h. das Polynom mit
einem Grad kleiner n , stellt das gesuchte Ergebnis von · dar, wobei wir abschließend
noch die Koeffizienten modulo p berechnen.
Aus der Definition der Addition innerhalb der Polynomrepräsentation von GF (2n ) erhalten wir:
Stellen wir die Koeffizienten der Elemente von GF (2n ) in der Polynomrepräsentation als
einen Binärstring der Länge n dar, dann entspricht die Addition zweier Elemente des
GF (2n ) dem bitweise xor dieser Strings.
Mit Hilfe von GF (2n ) können wir nun eine spezielle Form von iterierten Blockkryptosystemen vorstellen:
Definition 15 Ein iteriertes r -Runden Blockkryptosystem nennen wir ein r -Runden FeistelKryptosystem, wenn der Plaintext x gerade Länge hat, d.h. x = x1 x2 mit |x1 | = |x2 | , und für
die Rundenfunktion g gilt:
g : GF(2n ) × GF(2n ) × GF(2m ) → GF(2n ) × GF(2n )
wobei
g(x1 , x2 , z) = (x2 ⊕ h(x1 , z), x1 )
n
ist. Die Funktion h : GF(2 ) ×GF(2m ) → GF(2n ) ist hierbei beliebig und ⊕ das xor der Binärstrings
x2 und h(x1 , z) .
Sei x = xL xR ein gegebener Plaintext mit xL , xR ∈ Z2,n , K1 , . . . , Kr ∈ Z2,m die Rundenschlüssel,
die mit Hilfe eines Schlüsselgenerierungsalgorithmus aus einem Schlüssel K generiert werden. Wir
r r
1
0
yR mit
:= xR und erhalten y = yL
:= xL und yR
setzen yL
i−1 i−1
i−1
i
i
(yL
, yR
) := (yR
, yL ⊕ h(yR
, Ki ))
für alle i ∈ [1..r] .
Schränken wir die Abbildung h weiter ein, so kommen wir zu Kryptosystemen, die weitgehend mit
dem DES-System übereinstimmen.
Definition 16 Eine Abbildung f : Zm,n → Zm,k über einen Körper (Zm , +, ·) nennen wir affin,
wenn wir wir sie mit Hilfe einer k × n -Matrix A ∈ Zk×n
und einem Translationsvektor t ∈ Zkm
m
über
f (x) = A · x + t
für x ∈ Znm beschreiben läßt. Die Operationen innerhalb dieses Matrix-Vektor-Produkts und die innerhalb nachfolgende Vektor-Vektor-Addition entsprechen den Körperoperationen.
Ist t der 0-Vektor, wobei 0 das neutrale Element bez. + ist, dann nennen wir die Abbildung auch
linear.
44
Definition 17 Ein r -Runden Feistel-Blockkryptosystem nennen wir ein iteriertes r -Runden
DES-Kryptosystem, wenn für die Funktion h : GF(2n ) × GF(2m ) → GF(2n ) in
g(x1 , x2 , z) = (x2 ⊕ h(x1 , z), x1 )
gilt
h(x1 , z) = f (E(x) ⊕ z)
m
n
wobei f : GF(2 ) → GF(2 ) mit m ≥ n ist und E : GF(2n ) → GF(2m ) affine Expansionsfunktion
ist.
Den nichtlinearen Anteil in f bezeichnen wir in Anlehnung an DES als S -Box-Operation.
In der Literatur wird noch auf eine weitere Form von iterierte r -Runden Blockkryptosystem untersucht:
Definition 18 Ein iteriertes r -Runden Blockkryptosystem nennen wir ein r -Runden SubstitutionsPermutations-Kryptosystem (kurz. SPN-Kryptosystem), wenn wir g wir folgt beschreiben
können: sei
• S0 , . . . , Sk−1 : Z2,m → Z2,m eine Folge von k Abbildungen,
• π : [0..k · m − 1] → [0..k · m − 1] eine Permutation der Positionen eines k · m Bit-Binärstrings
und
• K1 , . . . , Kr ∈ Z2,k·m eine Folge von r Rundenschlüssel,
dann erhalten wir y i = g(y i−1 , Ki ) über
wi
= y i−1 ⊕ Ki
i
des Binärstrings wi in k Blöcke der Länge m
und für die Aufteilung w0i , . . . , wk−1
yi
i
= π(S0 (w0i ) . . . Sk−1 (wk−1
)) .
Den nichtlinearen Anteil in den Abbildungen Sj bezeichnen wir wieder als S -Box-Operation.
Die nachfolgende Abbildung zeigt uns ein 2-Runden SPN-Kryptosystems mit einer Aufteilung in 2
Blöcke.
K1
K2
π
y00
w01
S0
π
y01
⊕
y10
w02
S0
y02
w12
S1
y12
⊕
w11
S1
y11
Wir wollen nun noch einen letzten Typ von iterierten Blockkryptosystemen vorstellen.
45
Definition 19 Ein iteriertes r -Runden Blockkryptosystem nennen wir ein lineares r -Runden
Kryptosystem über F2 wenn
• für jede Runde i ∈ [0..r]
y
i
:= Ci (x) =
x
für i = 0
πi (y i−1 ⊕ Ki ) für i ∈ [1..r]
ist, wobei πi eine feste Permutation der n Bits, Ki der Rundenschlüssel und y i der Rundentext angibt.
Im nachfolgenden Abschnitt werden wir die differentielle Kryptoanalyse vorstellen. Im Wesentlichen
basiert diese auf den folgenden Beobachtungen über lineare Abbildungen bzw. über lineare Kryptosystem.
Beobachtung 4 Es gilt
• Für eine lineare Abbildung f und alle Eingabe x1 , x2 gilt f (x1 + x2 ) = f (x1 ) + f (x2 ) .
• Somit gilt für alle Plaintexte x1 , x2 und alle i ∈ [1..r]
Ci (x1 ⊕ x2 ) = Ci (x1 ) ⊕ Ci (x2 ) ,
d.h. die Differenz der Ciphertexte hängt nur von der Differenz der Plaintexte ab.
• Es gilt
y1i ⊕ y2i
= πi (y1i−1 ⊕ Ki ) ⊕ πi (y2i−1 ⊕ Ki )
= πi (y1i−1 ⊕ Ki ⊕ y2i−1 ⊕ Ki )
= πi (y1i−1 ⊕ y2i−1 )
= πi (· · · (π1 (x1 ⊕ x2 )) · · · )
= πi (· · · (π1 (x1 )) · · · ) ⊕ πi (· · · (π1 (x2 )) · · · ),
d.h. der Schlüssel beeinflusst die Differenz in der i -ten Runde nicht.
Beobachtung 5 Seien x1 , x2 , x3 , x4 ∈ Z2,n mit x1 ⊕ x2 = x3 ⊕ x4 , dann gilt für unser lineares
Kryptosystem und für alle i ∈ [1..r]
Ci (x1 ) ⊕ Ci (x2 ) = Ci (x3 ) ⊕ Ci (x4 ) .
Für die nichtlineare S -Box-Operation gilt diese Beobachtung im Allgemeinen nicht, d.h. für viele
Binärstrings x1 , x2 , x3 , x4 ∈ Z2,n mit x1 ⊕ x2 = x3 ⊕ x4 gilt
S(x1 ) ⊕ S(x2 ) 6= S(x3 ) ⊕ S(x4 ) .
46
4.4
Differentielle Kryptoanalyse
Zur Kryptoanalyse des DES-Kryptosystems wurden 1990 die differentielle und 1993 die lineare Kryptoanalyse vorgestellt. Die wesentliche Ideen dieser Attacken werden wir im Folgenden vorstellen.
Es zeigte sich jedoch, dass das DES-System weitgehend immun gegen differentielle Attacken ist. Dieses
liegt vorallem in dem nichtlinearen Anteil des DES, der im Wesentlichen auf den S -Boxen-Operationen
basiert. Aus den von Coppersmith veröffentlichten Entwurfsprinzipien der S -Boxen können wir schließen, dass diese Form der Analyse schon lange vor deren Veröffentlichung bekannt war. Eine Betrachtung der differentielle Kryptoanalyse zeigt uns somit ein wesentliches Entwurfskriterium des S -Boxen
des DES-Systems.
Die differentielle Kryptoanalyse basiert auf der Betrachtung zweier simultan verschlüsselter Plaintexte
x1 , x2 . Hierbei analysieren wir nicht die jeweiligen resultierenden Ciphertexte y1 , y2 von x1 , x2 ,
sondern richten unser Augenmerk auf die Differenz x1 − x2 . Rechnen wir in F2 , dann ist x1 − x2 =
x1 + x2 und x1 + x2 = x1 ⊕ x2 .
Sei S eine feste S -Box. Für x, ∆E , ∆A ∈ Z2,n definieren wir:
• die Ausgabedifferenz ∆S (∆E , x) := S(x) ⊕ S(x ⊕ ∆E ) ,
• die Anzahl der Übergänge ∆E → ∆A AS (∆E , ∆A ) := |{x | ∆S (∆E , x) = ∆A }|
• die Übergangswahrscheinlichkeit
AS (∆E , ∆A )
2n
p(S; ∆E , ∆A ) :=
für den Übergang ∆E → ∆A und die bedingten Wahrscheinlichkeiten
AS (∆E , ∆A )
.
0
∆0 AS (∆E , ∆A )
p(S; ∆A |∆E ) :=
P
A
Betrachten wir eine gegebene Menge von S -Boxen, dann können wir diese Wahrscheinlichkeiten
p(S; ∆E , ∆A ) für alle S -Boxen bestimmen. Ein Kryptosystem bietet einen Angriffspunk für die
differentielle Kryptoanalyse, wenn sich die Übergangswahrscheinlichkeiten für eine S -Box deutlich
unterscheiden. Unter dieser Voraussetzung können wir einige Bits des Rundenschlüssels bestimmen.
Wir definieren weiter:
• Seien x1 , x2 zwei Plaintexte und y1i , y2i die dazugehörigen Ciphertexte nach der i -ten Runde.
Arbeitet unser Kryptosystem in r Runden, dann gilt
y10 = x1
und y20 = x2
und für die zu x1 und x2 gehörigen Ciphertexte y1 und y2
y1 = y1r
und y2 = y2r .
• Wir definieren die Rundendifferenz von x1 , x2 über
∆i (x1 , x2 ) = y1i ⊕ y2i .
Insbesondere gilt
∆0 (x1 , x2 ) = x1 ⊕ x2
und
47
∆r (x1 , x2 ) = y1 ⊕ y2 .
Betrachten wir anstelle einer Differenz die Entwicklung der Differenz über die einzelnen Runden, so
erhalten wir die sogenannte Charakteristik eines Blockkryptosystems:
Definition 20 [Charakteristik eines Blockkryptosystems]
• Eine Folge von `+1 aufeinander folgenden Differenzen z0 , . . . , z` nennen wir ` -Runden-Charakteristik.
• Ein Plaintextpaar x0 , x1 besitzt die ` -Runden Charakteristik z0 , . . . , z` , wenn für alle
j ∈ [0..`]
∆j (x1 , x2 ) = zj
ist.
Die differentielle Kryptoanalyse untersucht die Wahrscheinlichkeiten verschiedener Charakteristiken
und versucht mit Hilfe einer r − 1 -Runden-Charakteristik Bits des letzten Rundenschlüssels Kr zu
bestimmen. Die verbleibenden Bits des Rundenschlüssels müssen wir dann über die Betrachtung aller
verbleibenden Kombinationen (exhaustive search) bestimmen. Es besteht jedoch die Hoffnung, dass
sich die Anzahl der verbleibenden möglichen Schlüssel mit Hilfe der differentiellen Kryptoanalyse stark
stark reduzieren lässt.
Für die differentielle Kryptoanalyse bestimmen wir nun für jede Charakteristik die Wahrscheinlichkeit,
dass diese Charakteristik auch tatsächlich auftritt. Sei z0 , . . . , z` eine ` -Runden Charakteristik und
sei ∆i die Zufallsvariable der Rundendifferenz für die i -te Runde. Dann gilt:
• Sind die Rundenschlüssel der einzelnen Runden voneinander unabhängig, so gilt
Y
Pr[∆` = z` |∆0 = z0 ] =
Pr[∆i = zi |∆i−1 = zi−1 ] .
i∈[1..`]
• Sind die Rundenschlüssel der einzelnen Runden nicht voneinander unabhängig, d.h. sie wurden
durch einen Algorithmus aus einem Schlüssel K generiert, dann kann die Wahrscheinlichkeit
Pr[∆` = z` |∆0 = z0 ] nicht mehr durch unsere obige Formel bestimmt werden.
• In vielen Fällen (so beim DES, LOKI, FEAL) habe experimentelle Untersuchungen gezeigt,
dass die obige Formel eine gute Approximation für Pr[∆` = z` |∆0 = z0 ] darstellt, so dass
wir in vielen Fällen davon ausgehen können, dass die Rundenschlüssel tatsächlich unabhängig
voneinander sind.
Wie bestimmen wir nun die Wahrscheinlichkeiten Pr[∆i = zi |∆i−1 = zi−1 ] ? Beschreiben wir die
Verschlüsselung in einer Runde nur mit einer S -Box, dann gilt
Pr[∆i = zi |∆i−1 = zi−1 ] = p(S; zi |zi−1 ) .
Arbeiten mehrere S -Boxen in jeder Runde parallel, so müssen wir die einzelnen Wahrscheinlichkeiten
miteinander in Beziehung setzten, z.B. indem wir das Produkt der entsprechenden Wahrscheinlichkeiten betrachten. Oder die Verschlüsselung der einzelnen Runden mit Hilfe einer größeren S -Box
modellieren.
Wird nach der S -Box noch eine lineare Transformation T auf das Ergebnis der S -Box ausgeführt,
so muss dieses ebenfalls berücksichtigt werden:
Pr[∆i = zi |∆i−1 = zi−1 ] = p(S; T −1 (zi )|zi−1 ) .
48
Der Einfachheit halber können wir diese linearen Transformationen als Teil der S -Box-Operation
betrachten. Mit diesen Wahrscheinlichkeiten erhalten wir den folgenden Basisalgorithmus für die
differentielle Kryptoanalyse:
1. Sei für jeden Rundenschlüssel Kr initiiere dessen Erfolgszähler e(Kr ) mit 0.
2. Wähle eine wahrscheinliche r − 1 -Runden Charakteristik z0 , . . . , zr−1 ,.
3. Wähle einen Plaintext x0 und bestimme x1 = x0 ⊕ z0 , sowie die dazugehörigen Ciphertexte
y0 , y 1 .
4. Bestimme alle Kandidaten für den Rundenschlüssel Kr , so dass
S −1 (y0 , Kr ) ⊕ S −1 (y1 , Kr ) = zr−1 .
gilt. Für jeden gefundenen Kandidaten Kr setze e(Kr ) := e(KR ) + 1 .
5. Wiederhole die Schritte 3 bis 5 bis der Erfolgszähler eines Rundenschlüssels im Vergleich zu
den anderen Rundenschlüsseln signifikant größer ist. Wir wählen diesen Schlüssel als aktuellen
Rundenschlüssel.
Als Faustregel gilt: Wir benötigen O(1/Pr[∆` = z` |∆0 = z0 ]) Plaintextpaare für diesen Angriff. Da
wir die Verschlüsselung dem Besitzer des Schlüssels überlassen müssen (in Schritt 3), gehört dieser
Angriff zu den sogenannten chosen-plaintext-Angriffen.
Betrachten wir unseren Basisalgorithmus etwas näher, so sehen wir, dass wir von der Charakteristik
nur z0 und zr−1 benötigen. Dieses führt uns zu der Betrachtung des sogenannten Differentials.
Definition 21 Ein ` -Runden Differential ist ein Paar von Differenzen z0 , z` wobei z0 die Plaintextdifferenz und z` die Differenz von zwei Rundentexten der ` -ten Runde darstellt.
Analog zur bedingen Wahrscheinlichkeit einer ` -Runden Charakteristik können wir auch die bedinge
Wahrscheinlichkeit eines ` -Runden Differentials z0 , z` bestimmen
X
Y
Pr[∆` = z` |∆0 = z0 ] =
Pr[∆i = zi |∆i−1 = zi−1 ] .
z1 ,...,z`−1 i∈[1..`]
Die Wahrscheinlichkeit für ein Differential kann sich um einige Größenordnungen von der Wahrscheinlichkeit einer Charakteristik unterscheiden.
Wollen wir die differentielle Kryptoanalyse mit Hilfe der Differentiale betreiben, dann können wir
wieder den oben vorgestellten Basisalgorithmus heranziehen.
Abhängig von dem vorhandenen Kryptosystem werden in der Literatur noch verschiedene Varianten
der differentielle Kryptoanalyse untersucht. Wir werden auf diese jedoch nicht näher eingehen.
Wie bereits zuvor angedeutet, wurden die S -Boxen des DES so konstruiert, dass mit Hilfe der differentiellen Kryptoanalyse kein erfolgversprechender Angriff zu erwarten ist. Die differentielle Kryptoanalyse ist jedoch so allgemein gefasst, dass wir sie gegen jede Form von Kryptosystem einsetzen
können. Inwiefern wir jedoch mit einem Erfolg rechnen können, wollen wir hier nicht untersuchen.
49
4.5
Lineare Kryptoanalyse
Im Folgenden nehmen wir an, dass eine Verschlüsselung eine Boolesche Transformation der Eingabebits
X0 , . . . , Xn−1 in die Ausgabebits Y0 , . . . , Yn−1 darstellt.
• Einen linearen Ausdruck A(X0 , . . . , Xn−1 ) in X0 , . . . , Xn−1 mit den Koeffizienten a0 , . . . ,
an−1 ∈ {0, 1} definieren wir über
n−1
X
ai · Xi .
i=0
• Einen affin-linearen Ausdruck A(X0 , . . . , Xn−1 ) in X0 , . . . , Xn−1 mit den Koeffizienten
a0 , . . . , an−1 ∈ {0, 1} definieren wir über
n−1
X
ai · Xi + 1 .
i=0
Die Terme sind hierbei über GF (2) definiert.
Ein Paar (AE , AA ) nennen wir eine affin-lineare Approximation einer Transformation T , wenn
AE = AE (X0 , . . . , Xn−1 ) ein affin-linearen Ausdruck in den Eingabebits und AA = AA (Y0 , . . . , Yn−1 )
ein affin-linearen Ausdruck in den Ausgabebits von T ist.
Zwischen den Bits X0 , . . . , Xn−1 und den Bits Y0 , . . . , Yn−1 besteht
• eine lineare Beziehung, wenn für a0 , . . . , an−1 , b0 , . . . , bn−1 ∈ {0, 1}
n−1
X
ai · Xi
=
i=0
n−1
X
bi · Yi
i=0
ist und
• eine (nichtlineare) affin-lineare Beziehung, wenn
n−1
X
ai · Xi
=
i=0
n−1
X
bi · Yi + 1
i=0
ist.
Eine affin-lineare Approximation (AE , AA ) wir von einer Eingabe x0 , . . . , xn−1 und der dazugehörigen Ausgabe y0 , . . . , yn−1 erfüllt, wenn eine affin-lineare Beziehung zwischen den Ausdrücken besteht, d.h. wenn AE (x0 , . . . , xn−1 ) = AA (y0 , . . . , yn−1 ) ist. Eine affin-lineare Approximation
(AE , AA ) ist im deterministischen Sinne gültig, wenn (AE , AA ) für alle Eingaben und den dazugehörigen Ausgaben erfüllt ist.
Ist eine affin-lineare Approximation nicht im deterministischen Sinne gültig, dann untersuchen wir die
Wahrscheinlichkeit, mit der diese Approximation für eine zufällige Eingabe-Ausgabekombinationen
gültig ist. Die Wahrscheinlichkeit p(AE , AA ) für eine affin-lineare Approximation (AE , AA ) ist der
Anteil aller Eingabe-Ausgabekombinationen, die die affin-lineare Approximation (AE , AA ) erfüllen,
d.h.
p(AE , AA ) := |{x ∈ {0, 1}n |AE (x) = AA (T (x))}| · 2−n .
50
Beobachtung 6
• Die lineare und die affine-lineare Beziehung sind komplementär zueinander:
n−1
X
ai · Xi =
i=0
n−1
X
bi · Yi
⇐⇒
i=0
n−1
X
ai · Xi 6=
i=0
n−1
X
bi · Yi + 1 .
i=0
• Für jede affine-lineare Approximation (AE , AA ) gilt
p(AE , AA ) = 1 − p(AE + 1, AA ) .
Die lineare Kyptoanalyse basiert auf der Annahme, dass bei optimaler Nichtlinearität einer Transformation T , für jede affine-lineare Approximation (AE , AA ) die Wahrscheinlichkeit p(AE , AA ) etwa
1
2 ist.
Mit Hilfe einer affin-linearen Approximation (AE , AA ) , für die die Wahrscheinlichkeit p(AE , AA )
deutlich von 12 abweicht, können wir dann hoffen, einzelne Schlüsselbits bestimmen zu können.
4.5.1
Ein erster Algorithmus
Wir betrachten zunächst den Fall, dass einem Angreifer eine affine-lineare Approximation (AE , AA )
für ein Kryptosystem bekannt ist, so dass
AE
=
n−1
X
ai · x[i] = AA =
i=0
n−1
X
i=0
bi · y[i] +
n−1
X
ci · K[i]
i=0
für alle Schlüssel K = K[0] . . . K[n−1] mit einer Wahrscheinlichkeit pL 6= 12 gilt. x = x[0] . . . x[n−1]
gibt hierbei den Plaintext und y = y[0] . . . y[n − 1] den Ciphertext an. Den Wert |pL − 21 | nennen
wir auch die Verzerrung oder den Bias der Approximation.
Um eine solche Approximation zu finden, kann ein Angreifer ein Kryptosystem über eine längere Zeit
analysieren. Hierbei sucht der Angreifer nach einer affine-lineare Approximation (AE , AA ) , für die
der Wert des Bias maximal ist. Wir gehen im Folgenden davon aus, dass bei einer konkreten Attacke
dem Angreifer die Koeffizienten ai , bi , ci für i ∈ [0..n − 1] bekannt sind.
Lineare Kryptoanalyse — Basisalgorithmus:
Gegeben eine affine-lineare Approximation (AE , AA ) mit maximalem Bias pL . Sei N die Anzahl
der Plaintext-Ciphertext-Paare (xj , y j ) , die wir benutzen.
Pn−1
j
1. Bestimme die Anzahl N 0 der Plaintext-Ciphertext-Paare (xi , y i ) für die
i=0 ai · x [i] =
Pn−1
j
i=0 bi · y [i] gilt.
Pn−1
0
2. Ist N 0 > N/2 , so setzen (oder besser raten) wir
i=0 ci · K[i] = 0 und für N ≤ N/2 raten
Pn−1
wir
i=0 ci · K[i] = 1 .
Dieses Verfahren gibt uns 1 Bit Information über den Schlüssel und somit nicht notwendigerweise 1
Bit des Schlüssels.
Als Faustregel können wir angeben, dass ca. |pL − 12 |−2 Plaintext- Ciphertext-Paare benötigt werden,
um dieses Bit an Information mit hinreichend großer Wahrscheinlichkeit bestimmen zu können.
51
4.5.2
Zusammensetzung von affin-linearen Approximationen
Wir wollen nun auf die Frage eingehen, wie wir eine affine-lineare Approximation (AE , AA ) eines
Kryptosystems bestimmen können?
1. Wir analysieren alle möglichen affin-lineare Approximationen (AE , AA ) für unser Kryptosystem
und bestimmen die jeweiligen Wahrscheinlichkeiten p(AE , AA ) . Der Aufwand für diese Analyse
wächst exponentiell in der Anzahl der Eingabe-, Ausgabe- und Schlüsselbits.
2. Oft ist es einfacher anstelle der affin-lineare Approximationen des ganzen Systems die affinlineare Approximationen der einzelnen S -Boxen zu bestimmen und diese dann zu kombinieren.
Im Folgenden wollen wir darauf eingehen, wie affine-lineare Approximationen (bei Unabhängigkeit der einzelnen Rundenschlüssel) kombiniert werden können.
Wir betrachten ein SPN-Kryptosystem und untersuchen, wie wir aus den affine-lineare Approximation
der einzelnen S -Boxen eine affine-lineare Approximation des ganzen Systems erhalten. Hierbei sei
i,j
(Ai,j
E , AA )
die affin-lineare Approximation der S -Box Sj in der i -ten Runde. Das xor-en eines Rundentextes
mit einem Rundenschlüssel geschieht zwischen zwei Runden, bzw. zwischen den dazugehörigen S Box-Operation.
Zunächst wollen wir zeigen, wie affin-lineare Approximationen einer Runde kombiniert werden können.
Im Anschluß werden wir zeigen, wie wir die resultierenden affin-linearen Approximationen aller Runden
kombinieren können.
Zusammensetzung von parallel arbeitenden S -Boxen einer Runde:
Wir betrachten die affin-lineare Approximation der S -Boxen einer Runde. Der Einfachheit halber
bezeichnen wir diese mit (AjE , AjA ) und
pj
= p(AjE , AjA ) =
1
+ εj .
2
Die zusammengesetzte affin-lineare Approximation ist dann
X
X
(
AjE ,
AjA ) .
j∈[0..k−1]
j∈[0..k−1]
Man beachte, dass eine Wahl der Belegung der Eingabe- und Ausgabebits die zusammengesetzte affinlineare Approximation genau dann erfüllt, wenn die Anzahl der durch diese Belegung nicht erfüllten
affin-lineare Approximation (AjE , AjA ) gerade ist.2
Lemma 6 Sei p(AjE , AjA ) =
p(
1
2
X
j∈[0..k−1]
2 Zur
ist
+ εj für alle j ∈ [0..k − 1] , dann gilt
AjE ,
X
AjA )
j∈[0..k−1]
=
1
+ 2k−1 ·
2
Y
εj .
j∈[0..k−1]
Erinnerung, die Wahrscheinlichkeit, dass eine Belegung eine affin-lineare Approximation (AjE , AjA ) nicht erfüllt,
+ 1, AjA ) = 1 − pj = 21 − εj .
p(AjE
52
Beweis: Der Beweis folgt über eine vollständige Induktion über k , indem wir die Wahrscheinlichkeiten
pk und qk untersuchen.
• p` ist die Wahrscheinlichkeit, dass in den ersten ` affin-lineare Approximationen eine gerade
Anzahl von Approximationen nicht erfüllt sind.
• q` = 1 − p` ist die Wahrscheinlichkeit, dass in den ersten ` affin-lineare Approximationen eine
ungerade Anzahl von Approximationen nicht erfüllt sind.
Für ` > 1 gilt
p` =
1
+ ε`
2
· p`−1 +
1
− ε`
2
1
+ 2`−1 ·
2
Y
· q`−1 .
Setzen wir die Induktionsannahme
p`−1 =
εj
j∈[0..`−1]
in diese Gleichung ein, so folgt, dass für alle `
p` =
Y
1
+ 2` ·
εj
2
j∈[0..`]
gilt und somit
p(
X
j∈[0..k−1]
AjE ,
X
AjA ) = pk
j∈[0..k−1]
=
1
+ 2k−1 ·
2
Y
εj
j∈[0..k−1]
ist.
Zusammensetzung mehrerer Runde:
Aufgrund der obigen Zusammenfassung aller S -Boxen einer Runde können folgendes vereinfachtes
SPN-Kryptosystem betrachten:
• Zu Beginn der i -ten Runde xor-en wir den Rundenschlüssel Ki mit dem Rundentexte y i−1
der i − 1 -ten Runde.
• Anschließend führen wir die S -Box-Operation aus, die durch eine S -Box gegeben ist.
• Zum Abschluß einer Runde permutieren wir das Ergebnis mit Hilfe einer Permutation π .
Sei (AiE , AiA ) die affin-lineare Approximation der S -Box der i -ten Runde und sei
p(AiE , AiA ) =
1
± εi .
2
Wie wir bereits gesagt haben, interessieren wir uns für eine Approximation mit maximalem Bias, daher
betrachten wir im Folgenden sowohl positive als auch negative Abweichungen der Wahrscheinlichkeit
p(AiE , AiA ) von 12 .
Wir zeigen zunächst, wie wir die beiden ersten Runden zusammenfassen können, sowie welche Approximation (AE , AA ) und Wahrscheinlichkeit p(AE , AA ) daraus resultiert:
53
• Sei (A0E , A0A ) die Approximation der S -Box der ersten und (A1E , A1A ) die Approximation der
S -Box der zweiten Runde.
• Unser Ziel ist die Approximation (A0E , A1A ) für die ersten beiden Runden.
Die beiden Approximationen (A0E , A0A ) und (A1E , A1A ) können wir jedoch nur dann zur Approximationen (A0E , A1A ) zusammensetzen, wenn die rechte Seite der ersten Approximation zur linken Seite
der zweiten Approximation passt. Hierbei müssen wir berücksichtigen, dass zwischen den beiden S Boxen die Ausgabe der ersten S -Box permutiert und der Rundenschlüssel R1 der zweien Runde
1
addiert wird. Es gilt somit Yi0 = Xπ(i)
⊕ K1 [i] .
Wir betrachten daher nur Approximationspaare (A0E , A0A ) und (A1E , A1A ) mit
0
0
A0A (y00 , . . . , yn−1
) = A1E (π(y00 , . . . , yn−1
) ⊕ K1 ).
Wir wollen nun versuchen, die Anforderungen an die beiden Approximation (A0E , A0A ) und (A1E , A1A )
etwas einfacher darzustellen. Sei
n−1
X
A1E (x10 , . . . , x1n−1 ) =
a1i · x1i ⊕ s1
i=0
dann gilt
A1E ((x̂10 , . . . , x̂1n−1 ) ⊕ K1 )
X
=
a1i · (x̂1i ⊕ K1 [i]) ⊕ s1
i∈[1..n−1]
X
=
a1i · x̂1i ⊕
i∈[0..n−1]
X
=
X
a1i · K1 [i] ⊕ s1
i∈[0..n−1]
a1i
·
x̂1i
⊕ k1 ⊕ s1
i∈[0..n−1]
für ein Korrekturbit k1 =
ist. Wir definieren daher
Pn−1
i=0
a1i · K1 [i] ∈ {0, 1} . Beachte, dass k1 unabhängig von der Eingabe
Ã1E
:= A1E + k1 .
Ferner definieren wir
π
Ã1E (x10 , . . . , x1n−1 )
= Ã1E (π(x10 , . . . , x1n−1 ))
und nennen wir die Approximationen (A0E , A0A ) und (A1E , A1A ) konsistent, wenn
A0A =
π
Ã1E
ist. Sind zwei Approximationen (A0E , A0A ) und (A1E , A1A ) zueinander konsistent, dann ist im zusam0
mengefassten System die Approximation (A0E , A1A ) genau für die Werte x00 , . . . , x0n−1 , y00 , . . . , yn−1
, y01 ,
1
. . . , yn−1 erfüllt, für die entweder
0
A0E (x00 , . . . , x0n−1 ) = A0A (y00 , . . . , yn−1
)
und
π
0
1
Ã1E (y00 , . . . , yn−1
) = A1A (y01 , . . . , yn−1
)
0
A0E (x00 , . . . , x0n−1 ) 6= A0A (y00 , . . . , yn−1
)
und
π
0
1
Ã1E (y00 , . . . , yn−1
) 6= A1A (y01 , . . . , yn−1
)
oder
gilt.
Wir wollen nun die Wahrscheinlichkeit p(A0E , A1A ) untersuchen. Hierbei müssen wir jedoch folgendes
beachten: Sind die Ereignisse (A0E , A0A ) ist erfüllt und (π Ã1E , A1A ) ist erfüllt nicht unabhängig, dann
54
können wir aus den Wahrscheinlichkeiten p(A0E , A0A ) und p(π Ã1E , A1A ) keine Aussage über die Wahrscheinlichkeit p(A0E , A1A ) herleiten. Wir nennen (A0E , A0A ) und (π Ã1E , A1A ) unabhängig, wenn die
Ereignisse (A0E , A0A ) ist erfüllt und (π Ã1E , A1A ) ist erfüllt unabhängig sind.
Aus p(AiE , AiA ) = 12 ± εi folgt unmittelbar p(π ÃiE , AiA ) = 21 ± εi . An Stelle von p(AiE , AiA ) =
können wir für ein geeignetes s ∈ {0, 1} auch p(AiE , AiA ) = 12 + (−1)s · εi schreiben.
1
2
± εi
Wir gehen nun von der Annahme aus, dass (A0E , A0A ) und (π Ã1E , A1A ) unabhängig sind, dann gilt für
geeignete Werte s0 , s1 ∈ {0, 1} :
p(A0E , A1A )
= p(A0E , A0A ) · p(π Ã1E , A1A ) + (1 − p(A0E , A0A )) · (1 − p(π Ã1E , A1A ))
1
1
=
+ (−1)s0 · ε0 ·
+ (−1)s0 · ε0
2
2
1
1
+
− (−1)s0 · ε0 ·
− (−1)s1 · ε1
2
2
s0
s1
(−1) · ε1
1 (−1) · ε0
+
+
+ (−1)s1 +s2 · ε0 · ε1
=
4
2
2
(−1)s1 · ε1
1 (−1)s0 · ε0
−
+ (−1)s1 +s2 · ε0 · ε1
+ −
4
2
2
1
=
+ (−1)s1 +s2 · 2 · ε0 · ε1 .
2
Analog zu dieser Analyse können wir auch mehr als zwei Runden zusammenfassen. Wir erhalten:
Lemma 7 Sei p(AiE , AiA ) = 12 ± εi für alle i ∈ [0..k − 1] und sei (π ÃiE , AiA ) unabhängig von
(A0E , Ai−1
A ) , dann gilt für die Konkatenation der k Runden
Y
p(A0E , Ak−1 ) − 1 = 2k−1 ·
εj .
A
2
j∈[0..k−1]
Beweis: Der Beweis folgt über eine vollständige Induktion über k . Die jeweiligen Schritte erfolgen
analog zu unserer Analyse bei der Zusammenfassung der ersten beiden Runden.
4.5.3
Angriff auf den letzten Rundenschlüssel für ein SPN-Kryptosystem
Eine affin-lineare Approximation (AE , AA ) nennen wir dominant, wenn ihre Wahrscheinlichkeit
p(AE , AA ) deutlich größer ist als alle anderen affin-lineare Approximationen.
Zur Vereinfachung betrachten wir wieder ein SPN-Kryptosystem, welches in jeder Runde nur eine
S -Box besitzt. Da S -Box-Operationen injektiv sind, können wir jede einzelne S -Box-Operation
invertieren. Wir erhalten den folgenden Algorithmus:
Lineare Kryptoanalyse — Algorithmus für ein SPN:
Gegeben eine dominante affin-lineare Approximation (A0E , Ak−2
A ) für die ersten k − 1 Runden. Sei
N die Anzahl der Plaintext-Ciphertext-Paare (xj , y j ) , die wir benutzen.
1. Bestimme eine zufällige Menge an Testschlüssel K für die letzte Runde.
55
2. Bestimme N zufällige Plaintext-Ciphertext-Paare (xj , y j ) ( j ∈ [0..N − 1] ).
3. Für jeden Schlüssel K` ∈ K sei e(K` ) die Anzahl der Plaintext- Ciphertext-Paare (xj , y j ) für
−1 j
die A0E (xj ) = Ak−2
(y ) ⊕ K` ) gilt.
A (S
1
4. Sei p(A0E , Ak−2
A ) = 2 + ε , dann ist die erwartete Anzahl der Paare, die die Approximation
k−2
0
(AE , AA ) erfüllen, bei N zufälligen Plaintext-Ciphertext-Paaren (xj , y j ) gleich N · 21 + ε .
Der Schlüssel K` ∈ K , für den der Wert e(K` ) am nähsten an N · ( 12 + ε) liegt, ist mit großer
Wahrscheinlichkeit der richtige Rundenschlüssel.
Ein guter Überblick über die differentielle und über die lineare Kryptoanalyse wird von Knudsen in
seinem Survey [K98] gegeben. Eine Einführung über dieses Thema anhand eines Beispiels wird in
[M03] gegeben.
Aufgabe 16 Stellen Sie das DES-Kryptosystem als SPN-Kryptosystem mit einer S -Box dar. Beschreiben Sie die S -Box-Operation, die Permutation und den Algorithmus zur Generierung der Rundenschlüssel. Um die Eingabe und Ausgabe in eine geeignet Form zu bringen, dürfen Sie vor und nach
der Verschlüsselung jeweils eine lineare Transformation einsetzen.
Aufgabe 17 Betrachten Sie die folgenden beiden S -Boxen:
x
000
S0 (x) 000
S1 (x) 111
001
010
011
010
100
010
011
110
101
100
011
000
101
111
001
110
101
100
111
001
110
1. Zeigen Sie, dass die dazugehörigen Operationen nicht linear sind.
2. Bestimmen Sie die einzelnen Eingabe-/Ausgabedifferenzen und deren Übergangswahrscheinlichkeiten p(Si ; ∆E , ∆A ) .
3. Bestimmen Sie die affin-lineare Approximation mit dem maximalen Bias für diese S -Boxen.
Bestimmen ferner Sie die affin-lineare Approximation der Konkatenation dieser Boxen, wenn
diese parallel auf zwei unabhängigen Blöcken ausgeführt werden, sowie die dazu gehörige Wahrscheinlichkeit.
4.6
Advanced Encryption Standard (AES)
Aufgrund der Schwächen von DES kam es 1998 zu der Ausschreibung für einen neuen Standard, dem
AES. Hierbei sollte das neue Verfahren die folgenden Kriterien erfüllen:
• Gesucht war ein symmetrischer Algorithmus, genauer ein Blockchiffre.
• Das Verfahren sollte Blöcke von 128 Bits verwenden und Schlüssel von 128, 192 und 256 Bit
Länge einsetzen können.
• Der neue Standard sollte leicht in Hard- und Software zu implementieren sein und eine überdurchschnittliche Performance haben.
• Für den Einsatz in Smartcards sollten nur geringe Ressourcen erforderlich sein (d.h. kurze Codelänge, niedriger Speicherbedarf).
56
• Der Algorithmus musste frei von patentrechtlichen Ansprüchen sein und von jedermann unentgeltlich genutzt werden können.
• AES sollt allen bekannten Methoden der Kryptoanalyse widerstehen können.
Als Gewinner der Ausschreibung im Oktober 2000 der nach seinen Entwicklern Joan Daemen und
Vincent Rijmen benannte Rijndael-Algorithmus [FIPS01] bekanntgegeben.
4.6.1
Mathematische Grundlagen
Die Basiseinheit für Berechnungen im AES stellt das Byte dar, daher sind viele Operationen im AES
im GF (28 ) definiert. Um den Wert eines Byte darzustellen benutzen wir entweder die Binärzahl-, die
Hexadezimalzahl- oder die Polynomrepräsentation. Betrachten wir die Polynomrepräsentation eines
Bytes, so benutzen wir im AES das irreduzible Polynom
m(x)
=
x8 + x4 + x3 + x + 1 .
Zur Erinnerung:
• Die Addition ⊕ entspricht dem Bitweisen xor, bzw. dem xor der korrespondierenden Koeffizienten der Polynome.
• Die Multiplikation · entspricht der Polynommultiplikation modulo m(x) .
Die Multiplikation kann mit Hilfe der iterierten Multiplikation eines Polynoms mit x und dem bedingten Subtrahieren (bzw. Addieren) von m(x) ) implementiert werden. Auf dem Bitlevel bedeutet
dieses:
• Führe einen Linksshift aus.
• Erhalten wir einen Überlauf, so xor-e das Resultat mit 100011011 .
• Übernehme nur die hinteren 8 Bits.
Diese Operation nennen wir xtime () .
Um die Operationen in GF (28 ) zu verdeutlichen, hier ein paar Beispiele.
• Beispiel für die Addition:
100111002 ⊕ 110001112 = 010110112
oder äquivalent
(x7 + x4 + x3 + x2 ) ⊕ (x7 + x6 + x2 + x1 + 1) = x6 + x4 + x3 + x1 + 1 .
57
• Beispiel für die Multiplikation:
(x6 + x4 + x2 + x + 1) · (x7 + x + 1)
= x13 + x11 + x9 + x8 + 2 · x7 + x6 + x5 + x4 + x3 + 2 · x2 + 2 · x + 1
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1
≡ (x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1) ⊕ (x5 · m(x))
≡ (x11 + x4 + x3 + 1) ⊕ (x3 · m(x))
≡ x7 + x6 + 1
mod m(x) .
• Beispiel für xtime () :
xtime(x7 + 1) = 1000000102 ⊕ 1000110112 = 000110012 ≡ x4 + x3 + 1 .
Das multiplikative Inverse p−1 (x) zu einem Polynom p(x) , d.h.
p(x) · p−1 (x) ≡ 1 mod m(x)
können wir mit Hilfe des erweiterten Algorithmus von Euklid bestimmen.
Mit Hilfe dieses Verfahrens können wir für zwei Polynome p(x) und m(x) zwei Polynome p̃(x) und
m̃(x) bestimmen, so dass
p(x) · p̃(x) + m(x) · m̃(x) = 1
ist. Wir erhalten somit
p−1 (x) = p̃(x) mod m(x) .
Abhängig von der Operation, benutzt man beim AES verschiedene Darstellungen der Werte der einzelnen Bytes. Ist b7 b6 . . . b0 die Darstellung eines Bytes in Binärdarstellung, dann erhalten wir die
Polynomdarstellung über
(b7 b6 . . . b0 )2 = b7 · x7 + b6 · x6 + b5 · x5 + b4 · x4 + b3 · x3 + b2 · x2 + b1 · x + b0 .
Um die Binärdarstellung in Hexadezimal Darstellung umzuwandeln, benutzen wir für b7 b6 b5 b4 und
b3 b2 b1 b0 die folgende Tabelle
00002
00012
00102
00112
01002
01012
01102
01112
=
=
=
=
=
=
=
=
016
116
216
316
416
516
616
716
10002
10012
10102
10112
11002
11012
11102
11112
=
=
=
=
=
=
=
=
816
916
A16
B16
C16
D16
E16
F16
Polynome mit Koeffizienten in GF (28 )
Neben den Polynomen zur Darstellung der Werte in GF (28 ) benutzen wir beim AES noch Polynomen
vom Grad 3, deren Koeffizienten wiederum Elemente des endlichen Körpers (GF (28 ) ) darstellen. Verschiedene Operationen im AES können wir mit Hilfe von Addition und Multiplikation dieser Polynome
definieren. Diese Polynome selbst, bilden jedoch keinen endlichen Körper. Sei
a(x) = a3 · x3 + a2 · x2 + a1 · x + a0
58
ein solches Polynom, dann benutzen wir auch die Schreibweise
[a0 , a1 , a2 , a3 ] .
Seien
a(x)
= a3 · x3 + a2 · x2 + a1 · x + a0
b(x)
= b3 · x3 + b2 · x2 + b1 · x + b0
zwei solche Polynome, dann definieren wir
• die Addition + über
a(x) + b(x) = (a3 ⊕ b3 ) · x3 + (a2 ⊕ b2 ) · x2 + (a1 ⊕ b1 ) · x + (a0 ⊕ b0 )
• und die Multiplikation ⊗ über die Polynommultiplikation modulo x4 + 1 .
Es gilt
xi mod (x4 + 1) = xi mod 4
somit können wir die Multiplikation ⊗ wie folgt vereinfachen: Sei
d(x) = d3 · x3 + d2 · x2 + d1 · x + d0 = a(x) ⊗ b(x)
dann erhalten wir


d0
a0
 a1
 d1 



 d2  =  a2
d3
a3

a3
a0
a1
a2
a2
a3
a0
a1
 
a1
b0
 b1
a2 
·
a3   b2
a0
b3


 .

Die Multiplikation ⊗ mit einem festen Polynom a(x) ist nicht für alle Polynome a(x) invertierbar.
Im AES wir jedoch ein Polynom benutzt welches ein multiplikatives Inverses besitzt:
a(x)
=
0316 · x3 + 0116 · x2 + 0116 · x + 0216
a−1 (x)
=
0B16 · x3 + 0D16 · x2 + 0916 · x + 0E16 .
Wählen wir
a(x) = 0116 · x3 ,
d.h. a3 = 0116 und a2 = a1 = a0 = 0016 , dann erhalten wir über die Operation ⊗ eine Rotation
nach links:
[0016 , 0016 , 0016 , 0116 ] ⊗ [b0 , b1 , b2 , b3 ] = [b1 , b2 , b3 , b0 ] .
4.6.2
Zustand des AES
Die Basiseinheit für Berechnungen im AES stellt das Byte dar. Sei a0 . . . a7 die folge der Bits im
Speicher, dann benutzen wir die Darstellungen
(a7 . . . a0 )2
und
a7 · x7 + . . . + a1 · x + a0 .
59
Die Blocklänge beim AES beträgt 128 Bits, d.h. 16 Byte. Abhängig vom Grad der Sicherheit, benutzt
das AES Schlüssel der Länge 128, 192 oder 256 Bit, bzw. 16, 24 oder 32 Byte. Ist x ein Block
bestehend aus n Bytes, dann bezeichnen wir im Folgenden mit x[i] das i -te Byte.3
Den Zustand des AES können wir Byteweise mit Hilfe eines 4 × 4 -Arrays beschreiben:
in0
in1
in2
in3
Input
in4 in8
in5 in9
in6 in10
in7 in11
in12
in13
in14
in15
−→
s0,0
s1,0
s2,0
s3,0
Zustand
s0,1 s0,2
s1,1 s1,2
s2,1 s2,2
s3,1 s3,2
s0,3
s1,3
s2,3
s3,3
−→
out0
out1
out2
out3
Output
out4 out8
out5 out9
out6 out10
out7 out11
out12
out13
out14
out15
Um ein 1-dimensionales Feld aus 16 Bytes in eine 2-dimensionale 4×4 -Matrix umzuwandeln definieren
wir die Funktion Square : ({0, 1}8 )16 → ({0, 1}8 )4×4 . Sei
s = (si,j )i,j∈[0..3] = Square(x)
für x ∈ ({0, 1}8 )16 , dann gilt für alle i, j ∈ [0..3]
si,j
= x[i + 4 · j] .
Die Funktion InvSquare : ({0, 1}8 )4×4 → ({0, 1}8 )16 gibt die Umkehrfunktion von Square () an,
d.h. für
x = InvSquare(s)
gilt
x[i + 4 · j] = si,j .
Sei s = (si,j )i,j∈[0..3] und s0 = (s0i,j )i,j∈[0..3] , dann definieren wir
s ⊕ s0 = (si,j ⊕ s0i,j )i,j∈[0..3]
als die elementweise Addition in GF (28 ) und somit als das bitweises Xor der Matrizen.
4.6.3
Die Unterfunktionen des AES
Die einzelnen Verschlüsselungsschritte des AES lassen sich mit Hilfe von 4 individuellen Unterfunktionen und deren Umkehrfunktionen aufbauen:
• AddRoundKey () und InvAddRoundKey ()
• ShiftRows () und InvShiftRows ()
• MixColumns () und InvMixColumns ()
• SubBytes () und InvSubBytes ()
1. AddRoundKey () und InvAddRoundKey () :
Bei AddRoundKey () sind Funktion und Umkehrfunktion identisch:
3 Allgemein bezeichnen wir mit x[i] das i -te Element in der Zeichenkette x . An anderer Stelle beziehen wir uns
hierbei oft auf ein Bit. Zur Vereinfachung der Darstellung werden wir beim AES mit x[i] das i -te Byte in x bezeichnen.
60
• Eingabe: eine 4 × 4 -Byte-Matrix s und ein 16-Byte Rundenschlüssel Ki
• Ausgabe: die 4 × 4 -Byte-Matrix s ⊕ Square(Ki ) .
Die einzelnen Rundenschlüssel K0 , . . . , Kr−1 werden mit Hilfe der Funktion KeyExpansion () aus
dem Schlüssel K generiert. Die 4 × 4 -Byte-Matrix s gibt den aktuellen Zustand des Rundentextes
an.
Ki [0] Ki [1] Ki [2] Ki [3] Ki [4] Ki [5] Ki [6] Ki [7] Ki [8] Ki [9] Ki [10]Ki [11]Ki [12]Ki [13]Ki [14]Ki [15]
⊕
s0,0
s0,1
s0,2
s0,3
s00,0
s00,1
s00,2
s00,3
s1,0
s1,1
s1,2
s1,3
s01,0
s01,1
s01,2
s01,3
s2,0
s2,1
s2,2
s2,3
s02,0
s02,1
s02,2
s02,3
s3,0
s3,1
s3,2
s3,3
s03,0
s03,1
s03,2
s03,3
2. ShiftRows () und InvShiftRows () :
ShiftRows () führt einen zyklischen Shift auf die einzelnen Zeilen einer 4×4 -Byte-Matrix aus. Hierbei
wird die i -te Zeile um i Positionen geshifted.
• Eingabe: eine 4 × 4 -Byte-Matrix s .
• Ausgabe: die 4 × 4 -Byte-Matrix s0 mit
s0i,j
= si,(j+i) mod 4 .
Für die Umkehrfunktion InvShiftRows () erhalten wir:
s0i,(j+i) mod 4 = si,j .
ShiftRows ()
s0,0
s0,1
s0,2
s0,3
s00,0
s00,1
s00,2
s00,3
s1,0
s1,1
s1,2
s1,3
s01,0
s01,1
s01,2
s01,3
s2,0
s2,1
s2,2
s2,3
s02,0
s02,1
s02,2
s02,3
s3,0
s3,1
s3,2
s3,3
s03,0
s03,1
s03,2
s03,3
61
3. MixColumns () und InvMixColumns () :
MixColumns () interpretiert jede Spalte der 4 × 4 -Byte-Matrix als ein Polynom
sj
= s3,j · x3 + s2,j · x2 + s1,j · x + s0,j
mit Koeffizienten aus GF (28 ) und Multipliziert ( ⊗ ) dieses mit dem Polynom
p(x) = 0316 · x3 + 0216 · x2 + 0116 · x + 0116
• Ausgabe: die 4 × 4 -Byte-Matrix
 0 
s0,j
 s01,j 
 0  =
 s2,j 
s03,j
s0 mit

0216
 0116

 0116
0316
0316
0216
0116
0116
0116
0316
0216
0116
 
0116
s0,j
 s1,j
0116 
·
0316   s2,j
0216
s3,j




bzw.
s00,j
:=
(0216 · s0,j ) ⊕ (0316 · s1,j ) ⊕ s2,j ⊕ s3,j
s01,j
s02,j
s03,j
:=
(0216 · s1,j ) ⊕ (0316 · s2,j ) ⊕ s3,j ⊕ s0,j
:=
(0216 · s2,j ) ⊕ (0316 · s3,j ) ⊕ s0,j ⊕ s1,j
:=
(0216 · s3,j ) ⊕ (0316 · s0,j ) ⊕ s1,j ⊕ s2,j
für alle j ∈ [0..3] .
p(x) ⊗ sj (x)
s0,0
s0,1
s0,2
s0,3
s00,0
s00,1
s00,2
s00,3
s1,0
s1,1
s1,2
s1,3
s01,0
s01,1
s01,2
s01,3
s2,0
s2,1
s2,2
s2,3
s02,0
s02,1
s02,2
s02,3
s3,0
s3,1
s3,2
s3,3
s03,0
s03,1
s03,2
s03,3
Die Umkehrfunktion InvMixColumns () erhalten wir über die Multipliziert ( ⊗ ) des Spalten-Polynoms
mit
p−1 (x) = 0B16 · x3 + 0D16 · x2 + 0916 · x + 0E16
• Ausgabe: die 4 × 4 -Byte-Matrix s0
 0 

s0,j
 s01,j 

 0  = 
 s2,j 

s03,j
mit
0E16
0916
0D16
0B16
0B16
0E16
0916
0D16
62
0D16
0B16
0E16
0916
 
0916
s0,j
 s1,j
0D16 
·
0B16   s2,j
0E16
s3,j




bzw.
s00,j
:=
(0E16 · s0,j ) ⊕ (0B16 · s1,j ) ⊕ (0D16 · s2,j ) ⊕ (0916 · s3,j )
s01,j
s02,j
s03,j
:=
(0E16 · s1,j ) ⊕ (0B16 · s2,j ) ⊕ (0D16 · s3,j ) ⊕ (0916 · s0,j )
:=
(0E16 · s2,j ) ⊕ (0B16 · s3,j ) ⊕ (0D16 · s0,j ) ⊕ (0916 · s1,j )
:=
(0E16 · s3,j ) ⊕ (0B16 · s0,j ) ⊕ (0D16 · s1,j ) ⊕ (0916 · s2,j )
für alle j ∈ [0..3] .
4. SubBytes () und InvSubBytes () :
SubBytes () ist eine elementweise Transformation einer 4 × 4 -Byte-Matrix mit Hilfe einer nichtlinearen invertierbaren S -Box.
s0i,j
=
Eintrag in der u-ten Zeile und v-ten Spalte
der S-Box Tabelle
wobei si,j = uv mit u, v ∈ {0, 1}4 ist.
Für die Umkehrfunktion InvSubBytes () erhalten wir:
s0i,j
=
Eintrag in der u-ten Zeile und v-ten Spalte
der inversen S-Box Tabelle
wobei si,j = uv mit u, v ∈ {0, 1}4 ist.
Die folgende Tabelle gibt die S -Box für das AES wieder:
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0
63
CA
B7
04
09
53
D0
51
CD
60
E0
E7
BA
70
E1
8C
1
7C
82
FD
C7
83
D1
EF
A3
0C
81
32
C8
78
3E
F8
A1
2
77
C9
93
23
2C
00
AA
40
13
4F
3A
37
25
B5
98
89
3
7B
7D
26
C3
1A
ED
FB
8F
EC
DC
0A
6D
2E
66
11
0D
4
F2
FA
36
18
1B
20
43
92
5F
22
49
8D
1C
48
69
BF
5
6B
59
3F
96
6E
FC
4D
9D
97
2A
06
D5
A6
03
D9
E6
6
6F
47
F7
05
5A
B1
33
38
44
90
24
4E
B4
F6
8E
42
7
C5
F0
CC
9A
A0
5B
85
F5
17
88
5C
A9
C6
0E
94
68
63
8
30
AD
34
07
52
6A
45
BC
C4
46
C2
6C
E8
61
9B
41
9
01
D4
A5
12
3B
CB
F9
B6
A7
EE
D3
56
DD
35
1E
99
A
67
A2
E5
80
D6
BE
02
DA
7E
B8
AC
F4
74
57
87
2D
B
2B
AF
F1
E2
B3
39
7F
21
3D
14
62
EA
1F
B9
E9
0F
C
FE
9C
71
EB
29
4A
50
10
64
DE
91
65
4B
86
CE
B0
D
D7
A4
D8
27
E3
4C
3C
FF
5D
5E
95
7A
BD
C1
55
54
E
AB
72
31
B2
2F
58
9F
F3
19
0B
E4
AE
8B
1D
28
BB
F
76
C0
15
75
84
CF
A8
D2
73
DB
79
08
8A
9E
DF
16
S -Box
s0,0
s0,1
s0,2
s0,3
s00,0
s00,1
s00,2
s00,3
s1,0
s1,1
s1,2
s1,3
s01,0
s01,1
s01,2
s01,3
s2,0
s2,1
s2,2
s2,3
s02,0
s02,1
s02,2
s02,3
s3,0
s3,1
s3,2
s3,3
s03,0
s03,1
s03,2
s03,3
Die Tabelleneinträge der S -Box knnen wie folgt berechnet werden: Sei si,j ein Byte, welches wir mit
Hilfe der S -Box transformieren wollen, dann verfahren wir wie folgt:
−1
8
• Bestimme das multiplikative Inverse s−1
i,j von si,j in GF (2 ) . Für si,j = 00 wählen wir si,j =
00 .
−1
• Seien s−1
i,j [i] die Bits von si,j , d.h.
−1
−1
−1
−1
−1
−1
−1
s−1
= s−1
i,j
i,j [7]si,j [6]si,j [5]si,j [4]si,j [3]si,j [2]si,j [1]si,j [0]
dann erhalten wir die Bits des Ergebnisses
s0i,j
= s0i,j [7]s0i,j [6]s0i,j [5]s0i,j [4]s0i,j [3]s0i,j [2]s0i,j [1]s0i,j [0]
s0i,j [i]
−1
−1
= s−1
i,j [i] ⊕ si,j [i + 4 mod 8] ⊕ si,j [i + 5 mod 8]
über
−1
⊕s−1
i,j [i + 6 mod 8] ⊕ si,j [i + 7 mod 8] ⊕ c[i]
wobei c = c[7]c[6]c[5]c[4]c[3]c[2]c[1]c[0] = 011000112 ist.
Alternativ können wir die Tabelleneinträge auch über die folgende affin-lineare Transfromation aus
dem multiplikative Inverse s−1
i,j von si,j bestimmen:












s0i,j [0]
s0i,j [1]
s0i,j [2]
s0i,j [3]
s0i,j [4]
s0i,j [5]
s0i,j [6]
s0i,j [7]












 = 










1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
64
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
  s−1 [0]
i,j
−1
s
 
i,j [1]
 

  s−1
[2]
  i,j
  s−1
[3]
 ·  i,j
  s−1 [4]
  i,j
  s−1 [5]
  i,j
  s−1 [6]
i,j
s−1
i,j [7]


 
 
 
 
 
 
+
 
 
 
 

1
1
0
0
0
1
1
0












Die folgende Tabelle gibt die inverse S -Box für das AES wieder:
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
4.6.4
0
52
7C
54
08
72
6C
90
D0
3A
96
47
FC
1F
60
A0
17
1
09
E3
7B
2E
F8
70
D8
2C
91
AC
F1
56
DD
51
E0
2B
2
6A
39
94
A1
F6
48
AB
1E
11
74
1A
3E
A8
7F
3B
04
3
D5
82
32
66
64
50
00
8F
41
22
71
4B
33
A9
4D
7E
4
30
9B
A6
28
86
FD
8C
CA
4F
E7
1D
C6
88
19
AE
BA
5
36
2F
C2
D9
68
ED
BC
3F
67
AD
29
D2
07
B5
2A
77
6
A5
FF
23
24
98
B9
D3
0F
DC
35
C5
79
C7
4A
F5
D6
7
38
87
3D
B2
16
DA
0A
02
EA
85
89
20
31
0D
B0
26
8
BF
34
EE
76
D4
5E
F7
C1
97
E2
6F
9A
B1
2D
C8
E1
9
40
8E
4C
5B
A4
15
E4
AF
F2
F9
B7
DB
12
E5
EB
69
A
A3
43
95
A2
5C
46
58
BD
CF
37
62
C0
10
7A
BB
14
B
9E
44
0B
49
CC
57
05
03
CE
E8
0E
FE
59
9F
3C
63
C
81
C4
42
6D
5D
A7
B8
01
F0
1C
AA
78
27
93
83
55
D
F3
DE
FA
8B
65
8D
B3
13
B4
75
18
CD
80
C9
53
21
E
D7
E9
C3
D1
B6
9D
45
8A
E6
DF
BE
5A
EC
9C
99
0C
F
FB
CB
4E
25
92
84
06
6B
73
6E
1B
F4
5F
EF
61
7D
Die Rundenschlüssel beim AES
Um den Rundenschlüssel zu bestimmen benötigen wir noch einige einfache Hilfsfunktionen, die auf
einem 4-Byte Wort w = w[0]w[1]w[2]w[3] arbeiten:
RotWord ()
• führt einen zyklischen Shift um ein Byte nach links aus:
RotWord(w[0]w[1]w[2]w[3]) = w[1]w[2]w[3]w[0] .
SubWord ()
• wendet einen S -Box-Operation auf jedes Byte an:
SubWord(w[0]w[1]w[2]w[3]) = S(w[0])S(w[1])S(w[2])S(w[3]) .
Rcon (i)
• für i ∈ N mit i > 0 ist
Rcon(i) = ci 0016 0016 0016 ,
wobei wir die Rundenkonstante ci wie folgt über die Operationen in GF (28 ) und der Polynomdarstellung bestimmen
ci = xi−1
(modm(x)) .
Alle diese Operationen können wir auch mit Hilfe der Multiplikation ⊗ und Addition + von Polynomen mit Koeffizienten in GF (28 ) darstellen.
65
Algorithm 1 KeyExpansion (K)
Eingabe: 4 · k -Byte Schlüssel K
Ausgabe: Folge der Rundenschlüssel (K0 , . . . , K` )
1: ` := 6 + k
2: for i = 0 to k − 1 do hi := K[4i]K[4i + 1]K[4i + 2]K[4i + 3] end for
3: for i = k to 4 · ` do
4:
t := hi−1
5:
if (i mod k) = 0 then
6:
t := SubWord(RotWord(t)) ⊕ Rcon(i/k)
7:
else
8:
if k = 8 ∧ (i mod k) = 4 then t := SubWord(t) end if
9:
end if
10:
hi := hi−k ⊕ t
11: end for
12: for i = 0 to ` do Ki := h4i h4i+1 h4i+2 h4i+3 end for
13: Return ((K0 , . . . , K` ))
Die folgenden beiden Grafiken illustrierten die Arbeitsweise von KeyExpansion (K) bei einer Schlüssellänge
von 16 und 24 Byte bzw. 128 und 192 Bit, d.h. k = 4 bzw. k = 6 :
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
h0
h1
h2
h3
h4
h5
h6
h7
h8
h0
h1
h2
h3
h4
h5
h6
h7
h8
h9
h10 h11 h12
RotWord ()
RotWord ()
RotWord ()
RotWord ()
SubWord ()
SubWord ()
SubWord ()
SubWord ()
Rcon (1)
⊕
⊕
Rcon (2)
⊕
Rcon (1)
⊕
⊕
⊕
66
Rcon (2)
⊕
⊕
Und die folgende Grafik schlielich illustriert die Arbeitsweise von KeyExpansion (K) bei einer Schlüssellänge
von 32 Byte bzw. 256 Bit, d.h. k = 8 :
⊕
⊕
⊕
⊕
⊕
⊕
h0
h1
h2
h3
h4
h5
h6
h7
h8
h9
h10 h11 h12 h13 h14 h15 h16
RotWord ()
SubWord ()
Rcon (1)
RotWord ()
SubWord ()
⊕
SubWord ()
Rcon (2)
⊕
⊕
⊕
4.6.5
⊕
Der AES-Algorithmus
Der AES-Algorithmus verschlüsselt einen Plaintext von 16 Byte in mehreren Runden. Die Anzahl der
Runden hängt hierbei von der Schlüssellänge ab. Es gilt:
• bei 16-Byte Schlüssel beträgt die Rundenzahl 10,
• bei 24-Byte Schlüssel beträgt die Rundenzahl 12 und
• bei 32-Byte Schlüssel beträgt die Rundenzahl 14.
Die Beschreibung von AES in Federal Infomation Processing Standards Publication 197 erlaubt auch
die Benutzung größerer Blöcke und Schlüssel. Auf die hierbei benötigten relativ einfachen Modifikationen werden wir jedoch nicht eingehen.
Algorithm 2 AES-Verschlüsselung (x, K)
Eingabe: 16-Byte Plaintext x und 4 · k -Byte Schlüssel K
Ausgabe: 16-Byte Ciphertext y
1: (K0 , . . . , K` ) := KeyExpansion (K)
2: s := Square (x)
3: s := AddRoundKey (s, K0 )
4: for i = 1 to ` − 1 by +1 do
5:
s := SubBytes (s) ; s := ShiftRows (s)
6:
s := MixColumns (s) ; s := AddRoundKey (s, Ki )
7: end for
8: s := SubBytes (s)
9: s := ShiftRows (s)
10: s := AddRoundKey (s, K` )
11: Return ( InvSquare (s))
67
Algorithm 3 AES-Entschlüsselung (y, K)
Eingabe: 16-Byte Ciphertext y und 4 · k -Byte Schlüssel K
Ausgabe: 16-Byte Plaintext x
1: (K0 , . . . , K` ) := KeyExpansion (K)
2: s := Square (y)
4: for i = ` − 1 to 1 by −1 do
5:
s := InvShiftRows (s) ; s := InvSubBytes (s)
6:
s := AddRoundKey (s, Ki ) ; s := InvMixColumns (s)
7: end for
8: s := InvShiftRows (s)
9: s := InvSubBytes (s)
11: Return ( InvSquare (s))
68
5
Public Key Kryptographie
Bei den bisher betrachteten Kryptosystemen handelt es sich um Zwei-Wege Kryptosysteme, d.h. um
eine Nachricht sicher zu übertragen, mussten zunächst der Schlüssel sicher übertragen werden. Im
Anschluss konnte dann mit Hilfe dieses Schlüssels die Nachricht übertragen werden. Diesen zusätzlichen sicheren Transport benötigen wir nicht mehr, wenn ein Public Key Kryptosystem benutzt wird.
In einem solchen System teilen wir die beiden Aufgaben eines Schlüssels in Zwei-Wege Kryptosysteme, d.h. Verschlüsseln und Entschlüsseln, auf zwei Schlüssel auf: einen öffentlichen Schlüssel zur
Verschlüsselung der Nachricht und einen privaten Schlüssel zur Entschlüsselung. Diese Idee geht auf
Diffie und Hellman (1976) [DH76] zurück, und hat seit dem die Kryptographie wesentlich beeinflusst.
5.1
Das generelle Schema
Das generelle Szenario für ein Public Key System hat die folgende Gestalt: Gegeben sind ` Personen
A1 , . . . , A` . Jede dieser Personen Ai generiert einen öffentlichen Schlüssel wi und einen privaten
Schlüssel w̃i . Die öffentlichen Schlüssel sammeln wir in einer Liste. Möchte Ai an Aj eine Nachricht
x senden, so verschlüsselt Ai diese Nachricht mit Hilfe von wj und sendet die Nachricht an Aj . Aj
entschlüsselt die Nachricht mit Hilfe von w̃i .
Damit dieses Verfahren sicher ist, müssen die folgenden Eigenschaften erfüllt sein:
1. Der Schlüssel w̃i darf nur mit großem Aufwand aus wi (oder irgendwelchen Plaintext-Ciphertext
Paaren) zu berechnen sein.
2. Die Verschlüsselung eines Plaintextes muss einfach sein.
3. Die Entschlüsselung ohne Kenntnis von w̃i muss sehr schwer sein.
Diese Voraussetzungen führen uns zu sogenannten One-Way Funktionen:
Definition 22 Seien X, Y zwei nicht-leere Mengen. Eine One-Way Funktion f ist eine injektive
Funktion f : X → Y , so dass f (x) in polynomieller Zeit in der Länge von x für alle x ∈ X berechenbar ist, aber die Umkehrfunktion f −1 (y) für jeden interessanten Anteil der Werte y ∈ Range(f )
nicht effizient berechenbar ist.
Aufgabe 18 Beweisen Sie: Ist P = N P , so gibt es keine One-Way Funktionen.
Aufgabe 19 Betrachten Sie die folgende Attacke auf einen Ciphertext y ∈ Zm,n , der durch ein
Public-Key Verfahren A mit öffentlichem Schlüssel w generiert wurde:
Wähle einen Text x ∈ Zm,n . Bestimme den Ciphertext y 0 für x unter Verwendung des
Schlüssels w . Ist y 0 = y , so nennen wir die Wahl von x erfolgreich.
Zeigen Sie: Gilt für alle Polynome q
Pr(die Wahl von x ist erfolgreich) <
1
,
q(n)
dann ist die Wahrscheinlichkeit, einen Wert x auch bei einer polynomiell häufigen Wiederholung
1
dieser Attacke erfolgreich zu wählen, kleiner q(n)
für alle Polynome q .
69
Aufgabe 20 Zeigen Sie wie mit Hilfe eines Public-Key Verfahrens ein Authentifizierungsverfahren
implementiert werden kann.
Bisher konnte der Beweis für die Existenz von One-Way Funktionen noch nicht erbracht werden.
Zwar scheint die Beantwortung dieser Frage mit der Problematik, ob P gleich N P ist, im Zusammenhang zu stehen. Um jedoch eine für die Kryptographie anwendbare One-Way Funktion zu finden,
müssen noch einige weitere Kriterien erfüllt sein, welche über die klassischen Worst-Case Bedingungen
hinausgehen:
1. Probleme mit hoher Worst-Case Komplexität können auf den meisten Eingabeinstanzen einfach
gelöst werden. Zudem existieren keine nicht-linearen unteren Schranken für die meisten N P vollständigen Probleme.
2. Für praktische Anwendungen genügt es, wenn wir f −1 randomisiert effizient berechnen können.
Somit schließt die nicht effiziente Berechenbarkeit von f −1 auch die polynomielle randomisierte
Berechenbarkeit von f −1 aus. Selbst aus dem Wissen, dass es keinen effizienten deterministischen Algorithmus für f −1 gibt, können wir jedoch nicht schließen, dass es keinen effizienten
randomisierten Algorithmus gibt.
3. Da die meisten relevanten Eingaben für die Kryptoanalyse von beschränkter Länge sind, dürfen
wir uns bei der nicht effizienten Berechenbarkeit von f −1 nicht auf uniforme Komplexitätsklassen beschränken. Vielmehr müssen wir fordern, dass f −1 auch nicht durch nicht-uniform
konstruierbare Schaltkreisfamilien polynomieller Größe berechnet werden kann.
4. Selbst, wenn alle oben beschriebenen Voraussetzungen erfüllt sind, und f −1 auf fast allen Eingaben nicht effizient berechnet werden kann, ist es möglich, dass die wenigen Eingaben, auf
denen eine Invertierung von f effizient möglich ist, alle interessanten Eingaben umfasst, wie
10
zum Beispiel alle Eingaben der Länge ≤ 22 .
Trotz dieser demotivierenden Einschränkungen gibt es dennoch einige vielversprechende Kandidaten
für One-Way Funktionen:
1. die modulare Exponentiation mit der Umkehrfunktion des diskreten Logarithmus,
2. das Produkt von Primzahlen mit der Umkehrfunktion der Primzahlzerlegung und
Pn
3. berechne M = i=0 xi · ai mit ai ∈ N und xi ∈ {0, 1} . Die Umkehrfunktion dieser Funktion
stellt eine Verallgemeinerung des Rucksackproblems dar.
Es bleibt jedoch zu klären, wie wir eine One-Way Funktion einsetzen können, um ein Public-Key
Verfahren zu bekommen. Hierfür greifen wir auf sogenannte Trap-Door Funktionen zurück. In der
folgenden Definition gibt Ko die Menge der öffentlichen und Kp die Menge der privaten Schlüssel
an.
Definition 23 Eine Funktion f : Pt × Ko → Ct nennen wir Trap-Door Funktion, wenn die drei
nachfolgenden Bedingungen erfüllt sind:
1. Two (·) = f (·, wo ) ist eine One-Way Funktion für alle wo ∈ Ko .
2. Es existiert ein Polynom p , so dass Two (x) in deterministischer (bzw. randomisierter) Zeit
p(|x|) für alle wo ∈ Ko berechnet werden kann.
70
3. Es existiert eine One-Way Funktion d : Kp → Ko und eine in polynomieller Zeit berechenbare
Funktion g : Kp × Ct → Pt , so dass
∀x ∈ Pt ∀y ∈ Ct ∀wo ∈ Ko : y = f (x, wo ) =⇒ x = g(d−1 (wo ), y) .
Wie gefährlich es ist, sich bei der Auswahl einer Trap-Door Funktion auf ein N P -vollständiges Problem zu verlassen, zeigt das folgende Beispiel (vergleiche hierzu [K86]).
5.2
Das Merkle-Hellman Kryptosystem
Das Merkle-Hellman Kryptosystem basiert auf dem Rucksack-Problem. Hierfür stellen wir den Plaintext als eine binäre Zeichenkette x = (x0 , . . . , xn−1 ) ∈ {0, 1}n dar. Ferner sei w = (w0 , . . . , wn−1 ) ∈
Nn ein Rucksack-Vektor, d.h. eine Instanz des Rucksack-Problems, mit Rucksackvolumen
y = w · xT
=
n−1
X
wi · xi .
i=0
Pn−1
Das Resultat y ist eine Zahl zwischen 0 und
w und gibt (aufgefüllt mit führenden Nullen)
Pn−1 i=0 i
den Ciphertext der Länge ` = dlog2 (1 + i=0 wi )e wieder. Damit die Entschlüsselung erfolgreich
durchgeführt werden kann, müssen wir die Werte von w geschickt wählen. Im Folgenden wollen wir
zunächst auf die Konstruktion von w eingehen. Im Anschluss stellen wir das Entschlüsselungsverfahren für diese Kryptosystem vor, um dann abschließend die Attacke von Shamir [S82] zu diskutieren.
5.2.1
Konstruktion des öffentlichen Schlüssels
Die Hintertür zum Merkle-Hellman Verfahren besteht aus einem Paar (k, m) ∈ N × N , deren Werte
hinreichend groß gewählt werden und die die Bedingung
k < m
und
ggT(k, m) = 1
(3)
erfüllen. Wir wählen nun n Werte w̃ = (w̃0 , . . . , w̃n−1 ) , so dass
m >
n−1
X
w̃i
und
∀i ∈ {1, . . . , n − 1} : w̃i >
i=0
i−1
X
w̃j
(4)
j=0
ist. Um ein Public-Key Verfahren zu bekommen, wählt die entsprechende Person die Werte k, m, w̃ so,
dass die Bedingungen (3) und (4) erfüllt sind. Anschließend berechnet sie w = (w0 , . . . , wn−1 ) , wobei
wi = (k · w̃i ) mod m ist. Die Werte k, m, w̃ stellen den privaten und der Vektor w den öffentlichen
Schlüssel dar.
5.2.2
Entschlüsselungsverfahren
Sei y der empfangene Ciphertext. Wir berechnen zunächst ỹ = (k −1 · y) mod m . Da m und k
Teilerfremd sind, können wir das multiplikative Inverse zu k modulo m eindeutig bestimmen. Für
71
ỹ gilt:
ỹ
=
(k −1 · y) mod m = (
n−1
X
k −1 · wi · xi ) mod m
i=0
=
n−1
X
(
k −1 · k · w̃i · xi ) mod m =
i=0
n−1
X
w̃i · xi .
i=0
Wir bestimmen nun den Plaintext x = (x0 , . . . , xn−1 ) wie folgt: Sei ỹn = ỹ , dann gilt für i =
n − 1, . . . , 0
ỹi+1
ỹi = ỹi+1 mod w̃i
und
xi =
.
w̃i
5.2.3
Attacke von Shamir
Gegeben sei eine Instanz des Merkle-Hellman Systems, d.h.
k, m, w = (w0 , . . . , wn−1 ), w̃ = (w̃0 , . . . , w̃n−1 ) .
Der Kryptoanalytiker kennt von dieser Instanz nur den öffentlichen Schlüssel w = (w0 , . . . , wn−1 ) . Das
Ziel des Kryptoanalytikers ist es, ein teilerfremdes Paar k, m zu berechnen, so dass für die Sequenz
w = (w0 , . . . , wn−1 ) mit wi ≡ wi · k mod m die Bedingung 4 erfüllt sind, d.h.
m >
n−1
X
wi
und
∀i ∈ {1, . . . , n − 1} : wi >
i=0
i−1
X
wj .
(5)
j=0
Es ist einfach zu erkennen, dass die Werte k, m, w auf die gleiche Art und Weise zur Entschlüsselung
von y benutzt werden können, wie die Werte k, m, w̃ . Das Verfahren von Merkle und Hellman hat
somit mehrere Hintertüren.
Dividieren wir die Werte wi durch m , so erhalten wir
−1
wi
k
≡ wi ·
mod 1
m
m
und
n−1
X
−1
k
wi ·
mod 1 < 1 .
m
i=0
−1
Zur Vereinfachung wählen wir r =
k
m
, d.h.
n−1
X
wi · r mod 1 < 1 .
(6)
i=0
Der Verlauf der Funktion (wi · r) mod 1 ist in Abbildung 5 dargestellt.
Wir suchen zunächst einen Punkt r0 auf der r -Achse, so dass dieser Wert die Bedingung (6) erfüllt.
Wir können nun die folgende Beobachtungen anstellen:
• Die pi -te Nullstelle der Sägezahnkurve (wi · r) mod 1 ist pi /mi .
• Damit das Merkle-Hellman Kryptosystem einen Plaintext gut verschlüsselt, sollten die Werte wi
möglichst gross sein, d.h. die Längen der Binärdarstellungen diese Werte liegen nahe bei Länge
der Binärdarstellung von m .
72
(wi · r) mod 1
1
0
r
0
1
wi
2
wi
pi
wi
3
wi
wi −1
wi
pi +1
wi
1
Abbildung 5: Verlauf der Funktion fi (r) = (wi · r) mod 1 .
• Somit ist die Länge der Binärdarstellung von wi = fi (r) kleiner als die Länge der Binärdarstellung von wi und daher muss r in der Nähe einer Nullstelle pi von fi liegen.
Aufbauend auf diesen Beobachtungen können wir das folgende System von Ungleichungen aufstellen:
1 ≤ p1 ≤ w1 − 1,
1 ≤ p2 ≤ w2 − 1,
..
.
1 ≤ pn ≤ wn − 1,
−ε2 ≤
−ε3 ≤
−εn ≤
p1
w1
p1
w1
p1
w1
− wp22 ≤ ε02
− wp33 ≤ ε03
..
.
− wpnn ≤ ε0n ,
(7)
wobei die Werte von εi , ε0i akzeptable Abweichungen zwischen den Differenzen wp11 − wpii darstellen.
Diese Abweichungen sollen möglichst klein gewählt werden. In vielen Fällen ist es ausreichend eine
konstante Anzahl von diesen Ungleichungen zu lösen. Das System von Ungleichungen (7) kann mit
Hilfe von Lenstra’s Integer-Programming Algorithmus gelöst werden [L81].
Seien p1 ein Wert, der als Lösung für unser oben angegebenes Ungleichungssystem bestimmt wurde
und r1 , . . . , rh aufsteigende Werte mit
p1
p1 + 1
≤ r1 < r2 < . . . < rh <
.
w1
w1
Diese Werte können wir so wählen, dass zwischen jedem Paar von Werten rt , rt+1 alle Kurven r ·
wi mod 1 linear sind. Sei qit die Anzahl der Minima von r · wi mod 1 im Intervall (0, rt ) , dann gilt
für r ∈ [rt , rt+1 )
r · wi mod 1 = r · wi − qit .
Für r ∈ [rt , rt+1 ) können wir somit die nötigen Voraussetzungen für r neu formulieren:
n−1
X
(r · wi − qit ) < 1
und
∀i ≤ n − 1 :
i=0
i−1
X
(r · wj − qjt ) < (r · wi − qit ) .
j=0
Dieses Gleichungssystem beinhaltet genau eine Variable. Die Lösung dieses Systems ergibt ein Teilin−1
tervall It von [rt , rt+1 ) , so dass für alle r und für alle Werte k, m mit r = km das Paar k, m ein
Entschlüsselungssystem für jeden Ciphertext der untersuchten Instanz des Merkle-Hellman Systems
bereitstellt.
73
5.3
Probleme aus der Zahlentheorie
Wir werden uns nun verschiedene Kryptosysteme, die auf Problemen aus der Zahlentheorie basieren,
näher ansehen. Zuvor müssen wir uns jedoch mit verschiedenen Problemen aus der Zahlentheorie
beschäftigen. Die meisten der folgenden Punkte sollten schon bekannt sein. Um keine Missverständnisse
aufkommen zu lassen, werden wir auf einige Punkte aus der Zahlentheorie hier eingehen.
Zunächst ein paar Notationen. Seien m ∈ N und a, b ∈ Z , dann gilt
• a ≡ b mod m gdw. m|(a − b) , d.h. m teilt (a − b)
• [a]m = {x ∈ Z|a ≡ x mod m}
• Zm = {[0], [1], . . . , [m − 1]} und
• Z∗m = {[a] ∈ Zm |ggT(a, m) = 1} .
Es gilt
[a] · [b] = [a · b]
und
[a] + [b] = [a + b] .
Somit sind (Zm , +) und (Z∗m , ·) zwei Gruppen. Der Einfachheit halber identifizieren wir Zm und
Z∗m mit diesen Gruppen. Wir lassen die Klammern um die Elemente der Mengen Zm und Z∗m weg.
Ferner definiert (Zm , +, ·) einen kommutativen Ring.
Um innerhalb eines Restklassenringes rechnen zu können, fassen wir noch einige einfache Ergebnisse
zusammen:
Beobachtung 7 Seien m ∈ N+ , n ∈ N und a, b, c, d ∈ Z , dann gilt
a ≡ b mod m
a ≡ b mod m
und
und
a ≡ b mod m
und
c ≡ d mod m
c ≡ d mod m
=⇒
=⇒
a + c ≡ b + d mod m
a − c ≡ b − d mod m
c ≡ d mod m
=⇒
a · c ≡ b · d mod m
a ≡ b mod m
=⇒
an ≡ bn mod m .
Da wir in einem Restklassenring nicht mit der gebräuchlichen Division arbeiten können, benutzen wir
das modulare Inverse als Umkehrfunktion der Multiplikation. a−1 ∈ Zm nennen wir das modulare
Inverse zu a modulo m , wenn a · a−1 ≡ 1 mod m ist. Es gibt jedoch nicht zu jedem Paar a, m das
modulare Inverse von a . Wie wir schon gesehen haben gilt:
Beobachtung 8 Die Äquivalenz a · x ≡ 1 mod m hat genau dann eine Lösung, wenn ggT(a, m) = 1
ist. Wenn eine Lösung von a · x ≡ 1 mod m existiert, so ist diese eineindeutig.
Von besonderer Bedeutung für verschiedene Kryptosysteme ist die Eulersche ϕ -Funktion,
Y
1
∗
ϕ(m) = |Zm | = m ·
1−
.
p
Primzahlen p<m mit ggT(p,n)6=1
Beobachtung 9 Für die Eulersche ϕ -Funktion gilt:
74
1. ϕ(m · n) = ϕ(m) · ϕ(n) für ggT(m, n) = 1 ,
2. ϕ(pα ) = pα−1 (p − 1) für Primzahlen p und
3. ϕ(p) = p − 1 für Primzahlen p .
Zahlen a werden wir im Weiteren immer als Binärzahlen darstellen. Mit n = 1 + blog2 ac bezeichnen
wir im Allgemeinen die Länge der Binärzahl.
5.3.1
Grundlegende Probleme
Definition 24 Größter gemeinsamer Teiler (ggT)
Gegeben: Zwei Zahlen a, b ∈ N .
Problem: Bestimme die größte Zahl, die sowohl a als auch b teilt.
Um den größten gemeinsamer Teiler zu finden, können wir auf den erweiterten Euklidischen Algorithmus zurückgreifen.
Algorithm 4 ErwEuklid
Eingabe: a, b ∈ N mit a > b
Ausgabe: d ∈ N , x, y ∈ Z mit d = ggT(a, b) und d = a · x + b · y
1: x0 = 1, x1 = 0, y0 = 0, y1 = 1 und r0 = a, r1 = b
2: for i = 1, 2, . . . bis ri+1 = 0 do
3:
qi = b ri−1
ri c
4:
ri+1 = ri−1 − qi · ri
5:
xi+1 = xi−1 − qi · xi
6:
yi+1 = yi−1 − qi · yi
7: end for
8: Ausgabe ri , xi , yi
Für diesen Algorithmus gilt:
Theorem 7 Algorithmus 4 berechnet den größten gemeinsamen Teiler zweier Zahlen a, b , indem er
maximal 1, 5 · log2 max{a, b} + O(1) Divisionen von Zahlen kleiner gleich max{a, b} ausführt.
Beweis: Der Beweis erfolgt, indem wir die folgenden Lemmata zeigen:
Lemma 8 Algorithmus 4 berechnet den größten gemeinsamen Teiler zweier Zahlen a, b korrekt.
Beweis: Zunächst zeigen wir über eine vollständige Induktion über i , dass r0 · xi + r1 · yi = ri ist.
Für i = 0 und i = 1 erhalten wir
r0 · x0 + r1 · y0 = r0 · 1 + r1 · 0 = r0
und
r0 · x1 + r1 · y1 = r0 · 0 + r1 · 1 = r1 .
Wir betrachten nun die Hypothese, dass die Aussage für alle i0 ≤ i erfüllt ist. Aus dem Algorithmus
wissen wir, dass
xi+1 = xi−1 − qi · xi
und
yi+1 = yi−1 − qi · yi
75
ist. Somit gilt:
r0 · xi+1 + r1 · yi+1
= r0 · xi−1 − r0 · qi · xi + r1 · yi−1 − r1 · qi · yi
= r0 · xi−1 + r1 · yi−1 − qi · (r0 · xi + r1 · yi )
= ri−1 − qi ri = ri+1 .
Die erste Aussage ist somit bewiesen.
Es gilt für alle i ≥ 1
ri+1 + ri ≤ ri−1 .
(8)
Nach Konstruktion gilt ri−1 − qi ri = ri+1 und somit ri+1 + ri = ri−1 − (qi − 1)ri . Da wir durch den
Algorithmus sicherstellen, dass ri+1 = ri−1 mod ri < ri ist, gilt qi ≥ 1 und somit ri+1 + ri ≤ ri−1 .
Da die Werte ri nicht negativ sind, gibt es ein n ∈ N , so dass rn+1 = 0 ist. Es verbleibt zu zeigen,
dass rn = ggT(a, b) ist.
Sei d = ggT(a, b) . Da rn = r0 · xn + r1 · yn = a · xn + b · yn ist, muss rn ein Vielfaches von d sein.
Da rn+1 = 0 ist, gilt rn−1 = qn · rn . Somit teilt rn den Wert rn−1 . Induktiv können wir nun für
alle i = n − 2, . . . , 0 zeigen, dass rn den Wert ri = qi+1 ri+1 + ri+2 teilt. Inbesondere teilt rn die
Werte r0 = a und r1 = b . Somit gilt rn = d .
Lemma 9 Algorithmus 4 benötigt maximal 1, 5·log2 max{a, b} +O(1) Divisionen von Zahlen kleiner
gleich max{a, b} .
Beweis: Algorithmus 4 benötigt genau eine Division pro Schleifendurchlauf. Die Anzahl der Schleifendurchläufe ist jedoch maximal, wenn wir den jeweiligen Wert ri pro Durchlauf nur um einen möglichst
kleinen Wert reduzieren. Somit erhalten wir eine möglichst lange Folge bei ri+1 + ri = ri−1 für alle
i ≥ 1 . Drehen wir die Zählrichtung um, so erhalten wir die Folge ai = ai−1 + ai−2 und Startwerte
a0 = a1 = 1 , d.h. wir erhalten die Folge der Fibonacci-Zahlen, wobei a = an die n -te und b = an−1
die (n − 1) -te Fibonacci-Zahl ist.
Für diese Zahlenfolge gilt
an =

√ !n+1
1  1+ 5
√ ·
−
2
5

√ !n+1
1− 5
 .
2
√
Da | 1−2 5 | < 0, 62 ist, gilt
lim
n→∞
√ !n+1
1− 5
= 0.
2
Das asymptotische Wachstumsverhalten von an wird somit durch
n + 1 ≈ log 1+√5 an .
2
Die Behauptung des Lemmas folgt unmittelbar.
Theorem 7 folgt unmittelbar aus diesen beiden Lemmata.
76
√ n+1
1+ 5
2
bestimmt. Es gilt
Definition 25 Modulare Inverse
Gegeben: Zwei Zahlen a, m ∈ N .
Problem: Bestimme a−1 ∈ Zm , so dass a−1 ·a ≡ 1 mod m ist, sofern dieser Wert existiert. a−1 = 0 ,
wenn kein Wert a−1 mit a−1 · a ≡ 1 mod m existiert.
Das modulare Inverse kann mit Hilfe des erweiterten Euklidischen Algorithmus berechnet werden.
Theorem 8 Das modulare Inverse kann auf Eingabe von a, m in Zeit O(max{log2 a, log2 m}2 ) berechnet werden.
Aufgabe 21 Führen Sie das Merkle-Hellman Kryptoverfahren (Ver- und Entschlüsselung) für die
Werte n = 5 , m = 8443 , k = 2550 und w̃ = (171, 196, 457, 1191, 2410) durch. Tip: k −1 =
3950 mod m .
Aufgabe 22 Beweisen Sie die Korrektheit des Entschlüsselungsverfahrens zum Merkle-Hellman Kryptosystem.
Aufgabe 23 Beweisen Sie die Korrektheit der Null-Teiler Eigenschaft für n ∈ N mit n ≥ 2 :
Die Aussage
∀k ∈ N∀` ∈ N :
k · ` ≡ 0 mod n =⇒ ` ≡ 0 mod n oder k ≡ 0 mod n
ist genau dann gültig, wenn n eine Primzahl ist.
Aufgabe 24 Beweisen Sie die Korrektheit des Kürzungsgesetzes für n ∈ N mit n ≥ 2 :
Die Aussage
∀k, `, j ∈ N :
j 6≡ 0 mod n und j · ` ≡ j · k mod n =⇒ ` ≡ k mod n
ist genau dann gültig, wenn n eine Primzahl ist.
Theorem 9 Chinesischer Restklassen Satz Seien m1 , . . . , mr r Zahlen, die paarweise relativ
prim Q
zueinander sind, d.h. für alle i, j ∈ {1, . . . , r} mit i 6= j gilt ggT(mi , mj ) = 1 , und sei
r
m = i=1 mi . Ferner seien a1 ∈ Zm1 , . . . , ar ∈ Zmr . Dann existiert genau eine eindeutig bestimmte
Zahl y ∈ Zm mit y ≡ ai mod mi für alle i ∈ {1, . . . , r} . Ferner kann y in polynomieller Zeit in der
Länge der Eingabe berechnet werden.
m
. Da die Werte m1 , . . . , mr alle paarweise relativ prim zueinander
Beweis: Für jedes i sei ni = m
i
sind, gilt ggT(mi , ni ) = 1 . Somit existiert auch das modulare Inverse n−1
von ni bezüglich mi .
i
Wir wählen
t
X
ŷ =
ni · n−1
und
y = ŷ mod m .
i · ai
i=1
Da nj von mi für alle i 6= j ein Vielfaches ist, gilt
y ≡ ŷ ≡ ni · n−1
i · ai ≡ ai mod mi .
Somit erfüllt y die erwünschten Bedingungen bezüglich der Restklassenzugehörigkeit.
77
Es verbleibt noch zu zeigen, dass dieser Wert eindeutig ist. Dieser Beweis erfolgt über eine Widerspruchsannahme. Sei x 6= y ein Wert in Zm , welcher die Voraussetzungen, d.h. x ≡ ai mod mi für
alle i erfüllt. Dann gilt x − y ≡ 0 mod mi für alle i . Folglich teilt mi die Differenz x − y Q
. Da die
r
Werte m1 , . . . , mr alle paarweise relativ prim zueinander sind, teilt auch das Produkt m = i=1 mi
die Differenz x − y . Da beide Werte x und y aus Zm gewählt wurden, folgt dass x − y = 0 und
somit x = y ist – ein Widerspruch.
Die Laufzeitschranke folgt unmittelbar aus der Formel zur Berechnung von ŷ und y .
Definition 26 Modulare Exponentiation
Gegeben: m ∈ N , m ≥ 2 , x ∈ N und a ∈ Z∗m .
Problem: Bestimme y ∈ Zm mit y ≡ ax mod m
Der folgende Algorithmus löst das Problem der modularen Exponentiation:
Algorithm 5 ModExp
Eingabe: m ∈ N , m ≥ 2 , x = x` . . . x0 ∈ N und a ∈ Z∗m
Ausgabe: y ∈ Zm mit y ≡ ax mod m
1: y = 1
2: for i = ` to 0 by −1 do
3:
if xi = 1 then
4:
y := y 2 · a mod m
5:
else
6:
y := y 2 mod m
7:
end if
8: end for
9: Ergebnis y
Aus der Analyse dieses Verfahrens folgt:
Theorem 10 Algorithmus 5 löst das Problem der modularen Exponentiation in Zeit O(max{log2 a,
log2 m, log2 x}3 ) .
Die Umkehrfunktionen der modularen Exponentiation geben zwei gute Kandidaten für Trap-Door
Funktion ab: die diskrete Wurzel, bzw. die Faktorisierung, und der diskrete Logarithmus:
Definition 27 Diskrete Wurzel
Gegeben: m ∈ N , m ≥ 2 , r ∈ N und a ∈ Z∗m .
Problem: Bestimme x ∈ Zm mit a ≡ xr mod m , wenn ein solcher Wert x existiert. Existiert keine
solche Lösung, so gebe Es existiert keine Lösung aus.
Um ein besseres Verständnis für das Problem der diskreten Wurzel zu erhalten, müssen wir auf die
Struktur der multiplikativen Gruppe Z∗m näher eingehen.
Theorem 11 Ist p eine Primzahl, so ist Z∗p eine zyklische Gruppe der Ordnung p − 1 .
78
Beweis: Für Primzahlen p haben wir bereits gesehen, dass |Z∗p | = ϕ(p) = p − 1 ist. Um zu erkennen,
dass Z∗p zyklisch ist, werden wir zeigen, dass ein Element x der Ordnung p − 1 in Z∗p existiert, d.h.
|{xi mod p|i ∈ N}| = p − 1 . Hierfür werden wir alle Elemente aus Z∗p verschiedener Ordnung zählen.
Sei d ∈ N , d > 0 , mit d|p − 1 , dann definieren wir
Sd = { a ∈ Z∗p | a ist von der Ordnung d } .
Es ist einfach zu erkennen, dass die Mengen Sd paarweise disjunkt sind. Es ist bekannt, dass diese
Mengen Z∗p partitionieren. Es gilt somit
X
|Sd | = |Z∗p | = p − 1 .
d mit d|p−1
Es gilt:
Lemma 10 Sei p eine Primzahl und f (x) = a0 · xn + · · · + an−1 · x + an eine Polynom mit f 6≡
0 mod p , dann hat f (b) ≡ 0 mod p maximal n unterschiedliche Lösungen.
Wir wollen nun folgendes Lemma zur Bestimmung der Kardinalitt der Mengen Sd zeigen:
Lemma 11 Sei d ein Wert mit d|p − 1 , dann ist entweder |Sd | = 0 oder |Sd | = ϕ(d) .
Beweis: Sei Sd eine nicht leere Menge und a ∈ Sd , dann sind die Werte a mod p, a2 mod p, . . . , ad mod
p alle paarweise unterschiedlich, und jedes Element dieser Folge ist eine Lösung von xd ≡ 1 mod p .
Wir kennen somit d Lösungen für xd ≡ 1 mod p .
Unter der Voraussetzung, dass Sd nicht leer ist, folgt aus Lemma 10:
Sd ⊆ { ai | i ∈ {1, . . . , d} } .
Wir betrachten nun ein festes k ∈ {1, . . . , d} . Ist ggT(k, d) = ` > 1 , dann gilt (ak )d/` = ak/`·d ≡
1 mod p . Somit ist ak von einer kleineren Ordnung als d .
Wir betrachten nun den Fall, dass ggT(k, d) = 1 ist, dann existiert ein modulares Inverses ` zu k ,
d.h. ` · k ≡ 1 mod d , und somit ist ak·` ≡ a mod p . Folglich gilt für alle e ∈ {1, . . . , d − 1}
((ak )e )` ≡ (ak·` )e ≡ ae 6≡ 1
mod p.
Somit ist |{(ak )e |e ∈ N}| = d und ak ist ein Element der Ordnung d , d.h. ak ∈ Sd .
Fassen wir zusammen, so erkennen wir:
Sd = { ak | 1 ≤ k ≤ d, ggT(k, d) = 1 }
und |Sd | = ϕ(d).
Unter der Annahme, dass für einige Werte d mit d|p − 1 die Menge Sd leer ist, gilt
X
X
|Sd | <
ϕ(d) .
d|p−1
d|p−1
Um die rechte Seite dieser Ungleichung abzuschätzen, benutzen wir das folgende Lemma:
79
Lemma 12 Für alle positiven ganzen Zahlen gilt
X
ϕ(d) = n .
d|n
Beweis: Sei n eine positive ganze Zahl und d ein Wert mit d|n , dann definiere
Rd = { m · i | m = n/d und i ∈ Z∗d } .
Zunächst gilt Rd ⊂ {1, . . . , n} und |Rd | = ϕ(d) .
Sei x ∈ {1, . . . , n} , m = ggT(x, n) , d = n/m und i = x/m . Da x = m · i , n = m · d und
m = ggT(x, n) ist, gilt ggT(i, d) = 1 und folglich gilt x ∈ Rd . Wir betrachten nun die Frage, ob x
auch in einer anderen Menge Re vorkommen kann, also, ob die Mengen Rd paarweise disjunkt sind.
Sei e ein entsprechender Wert, d.h. e|n und x ∈ Re . Dann gibt es Werte î und m̂ mit x = m̂ · î ,
n = m̂ · e und ggT(e, î) = 1 . Es gilt
n
· î = m̂ · î = x = m · i =
e
n
·i
d
und somit d · î = e · i . Da jedoch ggT(e, î) = 1 ist, erhalten wir e|d , und da ggT(d, i) = 1 ist,
erhalten wir d|e . Somit gilt e = d — ein Widerspruch. Folglich gehört jedes Element x ∈ {1, . . . , n}
zu genau einer Menge Rd und es gilt
X
X
|Rd | =
ϕ(d) = n .
d|n
d|n
Es gilt demnach
X
d|p−1
|Sd | <
X
ϕ(d) = p − 1 .
d|p−1
Diese Ungleichung widerspricht jedoch der Beobachtung, dass die Mengen Sd eine Partitionierung
der Menge Z∗p darstellen. Folglich ist für jeden Wert d mit d|p − 1 die Menge Sd nicht leer, dieses
gilt insbesondere für d = p − 1 .
Ein Element x ∈ Z∗p , welches die ganze Gruppe Z∗p aufspannt, d.h.
Z∗p = { xi | i ∈ {1, . . . , p} }
nennen wir Generator von Z∗p .
Definition 28 Diskreter Logarithmus
Gegeben: m ∈ N , m ≥ 2 , a ∈ Z∗m und x ∈ Z∗m .
Problem: Bestimme r ∈ Zm mit a ≡ xr mod m , wenn ein solcher Wert x existiert. Existiert keine
solche Lösung, so gebe Es existiert keine Lösung aus. Wir nennen diesen Wert r den diskreten
Logarithmus von a zur Basis x und schreiben r = dlogx (a) .
Für eine Primzahl p können wir folgende naheliegende Beobachtung zeigen:
Beobachtung 10 Für eine Primzahl p und einen Generator x von Z∗p gilt xp−1 ≡ 1 mod p .
80
Diese Beobachtung können wir in einem ersten Schritt wie folgt generalisieren:
Theorem 12 Kleiner Satz von Fermat
Für alle Primzahlen p und alle x ∈ Z∗p gilt xp−1 ≡ 1 mod p .
Beweis: Für alle Elemente x ∈ Z∗p gilt:
Beobachtung 11 Für alle Primzahlen p und alle x ∈ Z∗p gilt
{x mod p, 2 · x mod p, . . . , (p − 1) · x mod p} = Z∗p .
Beweis: Der Beweis erfolgt über eine Widerspruchsannahme. Sei x ∈ Z∗p mit {x mod p, 2 · x mod
p, . . . , (p−1)·x mod p} ⊂ Z∗p , dann existieren c1 , c2 ∈ Z∗p mit c1 ·x ≡ c2 ·x mod p und c1 6≡ c2 mod p .
Da p eine Primzahl ist, gilt ggT(x, p) = 1 . Somit existiert das multiplikative Inverse x−1 von x .
Es gilt
c1 · x ≡ c2 · x mod p
c1 · x · x−1 ≡ c2 · x · x−1 mod p
=⇒
=⇒
c1 ≡ c2 mod p
im Widerspruch zu c1 6≡ c2 mod p .
Aus dieser Beobachtung folgt
xp−1 · (p − 1)! ≡
p−1
Y
i·x ≡
i=1
p−1
Y
i ≡ (p − 1)! mod p .
i=1
Da p eine Primzahl ist, gilt ggT(p, (p − 1)!) = 1 und somit existiert das multiplikative Inverse
((p − 1)!)−1 von (p − 1)! . Es gilt
xp−1 · (p − 1)! ≡ (p − 1)! mod p
=⇒
xp−1 ≡ 1 mod p .
Eine Verallgemeinerung vom kleinen Satz von Fermat auf beliebige positive ganze Zahlen p ist auch
als der Satz von Euler bekannt.
Theorem 13 Satz von Euler
Sei n ∈ N mit n ≥ 2 , dann gilt für alle x ∈ Z∗n
xϕ(n) ≡ 1 mod n .
Beweis: Wir beweisen dieses Theorem zunächst für Primzahlpotenzen n = p` . Der Beweis erfolgt
über eine Induktion über ` . Für ` = 1 folgt die Behauptung unmittelbar aus dem kleinen Satz von
Fermat.
Sei ` > 1 , dann gilt ϕ(p` ) = (p − 1) · p`−1 = p` − p`−1 = p · (p`−1 − p`−2 ) und somit
`−1 `−2 p
`
`−1
`−2
xϕ(p ) ≡ xp·(p −p ) ≡
xp −p
mod p` .
Da ϕ(p`−1 ) = p`−1 − p`−2 ist, folgt aus der Induktionshypothese
`−1
xp
−p`−2
≡ 1 mod p`−1 .
81
Folglich gilt
`−1
xp
−p`−2
= 1 + c · p`−1
für eine geeignete Konstante c ∈ N . Zur Vereinfachung setzen wir z = c · p`−1 . Aus dem Binomialsatz
erhalten wir
p X
p
p
(1 + z) =
· 1i · z p−i .
i
i=0
Da pi für i ≥ 1 ein Vielfaches von p ist, gilt für alle i ∈ {1, . . . , p − 1}
p
· 1i · z p−i ≡ 0 mod p`
i
und somit, da p · (` − 1) ≥ ` ist,
`
xϕ(p
)
≡ 1 + z p ≡ 1 + cp · pp·(`−1) ≡ 1 mod p` .
Dieses beweist den Satz von Euler für Primzahlpotenzen.
Wir betrachten nun diesen Satz für beliebige n ∈ N mit n ≥ 2 . Sei n = p`11 ·p`kk die Primzahlzerlegung
von n . Zunächst gilt
xϕ(n) ≡ 1 mod pì i .
Die Behauptung folgt nun unmittelbar aus folgender Beobachtung:
Beobachtung 12 Seien m1 , m2 ∈ N mit m1 , m2 ≥ 1 und x1 , x2 ∈ N , dann gilt
x1 ≡ x2 mod m1
und
x1 ≡ x2 mod m2
=⇒
x1 ≡ x2 mod m1 · m2 .
Abschließend noch ein paar Bemerkungen zur Komplexität von der Berechnung der diskreten Wurzel. Für den Fall, dass m eine Primzahl ist, existiert ein polynomial zeitbeschränkter Las-Vegas
Algorithmus zur Berechnung der diskreten Wurzel [AMM77, B70]. Ist die Primzahlzerlegung von m
bekannt, so können wir diskreten Wurzeln mit Hilfe der Darstellung der Wurzel in der Chinesischen
Restklassendarstellung bestimmen.
5.4
Das RSA-Kryptosystem
Das RSA-Kryptosystem ist heute wohl das bekannteste Public-Key Kryptoverfahren. Benannt ist
dieses Verfahren nach dessen Entwicklern Rivest, Shamir und Adleman [RSA78], die 2002 für dessen
Entwicklung den Turing Award erhielten.
Sei A ein Teilnehmer an dem Public-Key-Kryptoverfahren, dann verfährt A wie folgt, um den öffentlichen Schlüssel wo und den privaten Schlüssel wp zu generieren.
1. A wählt zwei große Primzahlen pA und qA (von zumindest 200 Bits, wobei die Anzahl der
Bits in pA größer ist als die Anzahl der Bits in qA ).
2. Sei nA = pA · qA und ϕ(nA ) = ϕ(pA ) · ϕ(qA ) = (pA − 1) · (qA − 1) = nA − pA − qA + 1 .
82
3. Wähle eine zufällig Zahl eA ∈ {1, . . . , ϕ(nA )} mit ggT(eA , ϕ(nA )) = 1 und berechne dA =
e−1
A mod ϕ(nA ) .
4. Veröffentliche wo = (nA , eA ) und verwahre wp = (pA , qA , dA ) .
Zur Verschlüsselung eines Plaintextes x berechnet B y = xeA mod nA und sendet den Ciphertext
y an A . Zur Entschlüsselung berechnet A y dA mod nA .
83
Literatur
[AMM77] L. Adleman, K. Mander, G. Miller, On Taking Roots in Finite Fields, 18th FOCS, 1977, S.
175-177.
[B94] F. L. Bauer, Kryptologie, Springer-Verlag, 1994.
[B70] E. R. Berlekamp, Factoring Polynomials over Large Finite Fields, Mathematics of Computations
24, 1970, S. 713–735.
[B81] M. Blum, Coin Flipping per Telephon: A Protocol for Solving Problems Impossible, SIGACT
News 15, 1981, 23-27.
[B88] G. Brassard, Modern Cryptology, Springer-Verlag, 1988.
[BCC88] G. Brassard, D. Chaum, C. Crépeau, Minimum Disclosure Proofs of Knowledge, Journal of
Computer and System Science, Vol. 37, No. 2, 1988, 156-189.
[BSW95] A. Beutelspacher, J. Schwenk, K.-D. Wolfenstetter, Moderne Verfahren der Kryptographie,
Vieweg 1995.
[C94] D. Coppersmith, The Data Encryption Standard (DES) and Its Strength against attacks, IBM
J. Res. Dev. 38, No. 2, 1994, 243-250.
[CLRS01] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (second
edition), MIT Press, 2001.
[DH76] W. Diffie, M. E. Hellman, New Directions in Cryptography, IEEE Transactions on Information
Theory, IT-22 No. 6, 1976, S. 644–654.
[EP91] European Patent Application 0 428 252 A2, A System for Controlling Access to Broadcast
Transmissions, 1991.
[F68] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3. Auflage, Wiley,
1968.
[FIPS99] Federal Information Processing Standards Publication 46-3, Data Encryption Standard,
1999.
[FIPS01] Federal Information Processing Standards Publication 197, Announcing the ADVANCED
ENCRYPTION STANDARD (AES), 2001.
[GGM86] O. Goldreich, S. Goldwasser, S. Micali, How to Construct Random Functions, Journal of
the ACM, Vol. 33, No. 4, 1986, 210-217.
[GK96] O. Goldreich, H. Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM
Journal on Computing, Vol. 25, No. 1, 1996, 169-192.
[GMR85] S. Goldwasser, S. Micali, R. Rackoff, The Knowledge Complexity of Interactiv Proof Systems,
SIAM J. Comput. 8(1), 1989, 186-208; siehe auch Proc. 17. STOC, 1985, 291-304.
[GMW86] O. Goldreich, S. Micali, A. Wigderson, Proofs that Yield Nothing but their Validity and a
Methodology of Cryptographic Protocol Design, Proc. 27 FOCS, 1986, 171-185.
[J02] A. Jakoby, Skript zur Vorlesung: Interaktive Protokolle: Arthur-Merlin-Spiele und andere, Universität zu Lübeck, Institut für Theoretische Informatik, Sommersemester 2002.
[K67] D. Kahn, The Codebreakers: The Strory of Secret Writing, Macmillan, 1967.
84
[K98] L. Knudsen, Block Ciphers – A Survey, State of the Art in Applied Cryptography, LNCS 1528,
1998, 18-48.
[K87] N. Koblitz, A Course in Number Theory and Cryptology, Springer-Verlag, 1987.
[K86] E. Kranakis, Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.
[L81] H. W. Lenstra, Integer Programming with a Fixed Number of Variables, University of Amsterdam, Department of Mathematics, TR 81-03, 1981.
[L86] L. A. Levin, Average Case Complete Problems, SIAM Journal on Computing, Vol. 15, 1986,
285-286.
[L68] C. L. Liu, Introduction to Combinatorial Mathematics, McGrawHill, New York, 1968.
[M03] R. Matthes, Algebra, Kryptologie und Kodierungstheorie, Fachbuchverlag Leipzig, 2003.
[N91] M. Naor, Bit Commitment Using Pseudorandomness, Journal of Cryptology, 1991, 151-158.
[NPS99] M. Naor, B. Pinkas, R. Sumner, Privacy Preserving Auctions and Mechanism Design, 1st
ACM Conference on Electronic Commerce, 1999, S. 129-139.
[RSA78] R. Rivest, A. Shamir und L. Adleman, A Method for Obtaining Digital Signatures and PublicKey Cryptosystems, Communications of the ACM 21, 1978, S. 120-126.
[S90] A. Salomaa, Public-Key Cryptology, Springer-Verlag, 1990.
[S96] J. Schwenk, Conditional Access, in: taschenbuch der telekom praxis 1996, B. Seiler, Verlag
Schiele & Schön, Berlin.
[S79] A. Shamir, How to Share a Secret, Communications of the ACM 22, 1979, S. 612-613.
[S82] A. Shamir, A Polynomial Time Algorithm for Breaking the Merkle-Hellman Cryptosystem, 23rd
FOCS, 1982, S. 145-152.
[S49] C. E. Shannon, Communication Theory of Secrecy Systems, Bell Syst. Tech. J. 28, 1949, S.
379-423.
[Y82] A. Yao, Theory and applications of trapdoor functions, 23rd FoCS, 1982, S. 80–91.
[Y86] A. Yao, How to Generate and Exchange Secrets, 27rd FoCS, 1986, S. 162–167.
85

Kryptologie - Institut für Theoretische Informatik

Transcrição

Documentos relacionados

Mitschrift 21.04.2015

Sicherheitsanalyse des WEP Protokolls im IEEE 802.11

IT-Sicherheit in der Medizin - Webseiten der Mitarbeiter der Universität

Kleiner Satz von Fermat Hilfssatz: mn ist durch n

KD91 KS92 KS94 Miniatur-Beschleunigungsaufnehme Miniature

Hinterschaft und 2 breite Vorderschäfte für FN Bockdoppelflinte Mod

MOD Steuerungs- und Regel- technik - Bundesverband Modell

Schritt für Schritt Anleitung

Handout -

WLAN-Verschlüsselung WEP: Arbeitsweise und Designfehler