. 1
( 9)



>>

Christian Karpfinger | Hubert Kiechle

Kryptologie
Christian Karpfinger | Hubert Kiechle


Kryptologie
Algebraische Methoden und Algorithmen

STUDIUM
Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der
Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über
<http://dnb.d-nb.de> abrufbar.




Privatdozent Dr. Christian Karpfinger
Technische Universit¤t München
Zentrum Mathematik
Boltzmannstraße 3
85747 Garching
E-Mail: karpfing@ma.tum.de


Privatdozent Dr. Hubert Kiechle
Universit¤t Hamburg
Department Mathematik
Bundesstraße 55
20146 Hamburg
E-Mail: hubert.kiechle@uni-hamburg.de




1. Auflage 2010

Alle Rechte vorbehalten
© Vieweg +Teubner | GWV Fachverlage GmbH, Wiesbaden 2010
Lektorat: Ulrike Schmickler-Hirzebruch | Nastassja Vanselow
Vieweg +Teubner ist Teil der Fachverlagsgruppe Springer Science+Business Media.

Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede
Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne
Zustimmung des Verlags unzul¤ssig und strafbar. Das gilt insbesondere für
Vervielf¤ltigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung
und Verarbeitung in elektronischen Systemen.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk
berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im
Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten w¤ren und daher
von jedermann benutzt werden dürften.

Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg
Druck und buchbinderische Verarbeitung: Ten Brink, Meppel
Gedruckt auf s¤urefreiem und chlorfrei gebleichtem Papier.
Printed in the Netherlands

ISBN 978-3-8348-0884-4
Vorwort

Das vorliegende Buch entstand aus wiederholten Vorlesungen zur Kryptologie,
die wir Autoren an der Technischen Universit¤t München bzw. an der Universit¤t
Hamburg für Mathematik- und Informatikstudenten gehalten haben. Wir kon-
zentrierten uns in den Vorlesungen (und damit auch im vorliegenden Buch) auf
die mathematischen Grundlagen kryptogra¬scher und kryptoanalytischer Ver-
fahren. Solche Verfahren werden heutzutage im Internet und im elektronischen
Datenaustausch angewendet und bilden damit eine Schlüsseltechnologie.
Die moderne Kryptologie benutzt vor allem Methoden der Algebra, der Zah-
lentheorie und der algebraischen Geometrie. Wir entwickeln diese Theorien im
vorliegenden Buch, soweit sie benötigt werden. Dabei stellen wir die mathemati-
schen Grundlagen so weit möglich vollst¤ndig und mit der gebotenen Pr¤zision
dar. Wir halten es n¤mlich für wichtig, dass auch ein Anwender ein tieferes, über
das algorithmische hinausgehende Verst¤ndnis für dieses interessante, höchstak-
tuelle Gebiet hat. Eine korrekte Anwendung der Mathematik ist Grundlage für
die Sicherheit im modernen Datenverkehr.
Die mathematischen Grundlagen werden im vorliegenden Buch stets an der Stel-
le entwickelt, an der sie benötigt werden. Dabei setzen wir Grundkenntnisse aus
der linearen Algebra und etwas Analysis voraus, wie sie im ersten Studienjahr in
den einschl¤gigen Vorlesung für Mathematik- und Informatikstudenten vermit-
telt werden.
Der vorliegende Text kann als Grundlage für eine vierstündige Vorlesung ge-
nutzt werden. L¤sst man die mit einem Stern— versehenen Kapitel und Abschnit-
te (und die dazugehörigen Unterabschnitte) weg, so bleibt ein Themenkreis für
eine zweistündige Vorlesung erhalten.
Für das Lesen von Teilen des Skriptes, für die zahlreichen Hinweise, Anregungen,
Verbesserungsvorschl¤ge, Aufgaben und Beispiele danken wir Susanne Apel,
Matthias Bargmann, Jana Bretschneider, Dominik Fischer, Frank Himstedt, Frank
Hofmaier, Lisa Kehrer, Andreas Kreisel, Bertram Poettinger, Fabian Reimers und
Annika Vernbro.
Nicht zuletzt danken wir Frau Schmickler-Hirzebruch und Frau Vanselow vom
Vieweg+Teubner Verlag für die erfreuliche Zusammenarbeit.
Trotz sorgf¤ltigem und mehrfachen Lesen des Skriptes sind sicherlich einige Feh-
ler im Text verblieben. Hinweise darauf sind jederzeit herzlich willkommen.

München, Hamburg, im August 2009 Christian Karp¬nger, Hubert Kiechle
Inhalt

Vorwort v

1 Klassische Verfahren 1
1.1 Worum geht™s? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Monoalphabetische Chiffrierung . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Das Kerckhoffs™sche Prinzip und die Angriffsarten . . . . . . . . . . . . 6
1.4 Die Halbgruppe der Strings . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Kryptosysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Polyalphabetische Chiffrierung . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Af¬ne Chiffren und ihre Kryptoanalyse * . . . . . . . . . . . . . . . . . 18

2 Das One-Time-Pad und perfekte Sicherheit 23
2.1 Das One-Time-Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Elementare Wahrscheinlichkeitsrechnung . . . . . . . . . . . . . . . . . 25
2.3 Der Satz von Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 Block-Chiffren “ AES und DES 33
3.1 Endliche Körper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 Feistel-Chiffren * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Betriebsmodi * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5 Differentielle und lineare Kryptoanalyse * . . . . . . . . . . . . . . . . . 56

4 Komplexit¤t und Einwegfunktionen 57
4.1 Komplexit¤t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Der erweiterte euklidische Algorithmus . . . . . . . . . . . . . . . . . . 65
4.3 Die primen Restklassengruppen . . . . . . . . . . . . . . . . . . . . . . . 71
4.4 Einwegfunktionen und Hashfunktionen . . . . . . . . . . . . . . . . . . 76

5 Symmetrische Authenti¬kation 81
5.1 Message Authentication Code . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 Der Satz von Gilbert-MacWilliams-Sloane . . . . . . . . . . . . . . . . . 84
5.3 Beweisbar perfekte Systeme * . . . . . . . . . . . . . . . . . . . . . . . . 87
5.4 Ausblick: Mehrfach perfekte Systeme * . . . . . . . . . . . . . . . . . . 92
viii Inhalt

6 Exponentiationschiffren 93
6.1 Algebraische Grundlagen der Exponentiationschiffren . . . . . . . . . . 93
6.2 Das Pohlig-Hellman-Verfahren * . . . . . . . . . . . . . . . . . . . . . . 102
6.3 Schnelle Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

7 Das RSA-Verfahren 111
7.1 Das Verfahren von Rivest, Shamir und Adleman . . . . . . . . . . . . . 111
7.2 Der chinesische Restsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.3 RSA und das Faktorisierungsproblem * . . . . . . . . . . . . . . . . . . 122
7.4 Wahl der Parameter p, q, e und d bei RSA . . . . . . . . . . . . . . . . . 126
7.5 Kettenbrüche * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.6 Der Wiener-Angriff * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

8 Primzahltests 141
8.1 Probedivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
8.2 Der Fermat-Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.3 Der Miller-Rabin-Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.4 Der AKS-Test * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
8.5 Vergleich der Primzahltests . . . . . . . . . . . . . . . . . . . . . . . . . 164

9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin 167
9.1 Der Dif¬e-Hellman-Schlüsselaustausch . . . . . . . . . . . . . . . . . . 167
9.2 Das ElGamal-Verschlüsselungsverfahren . . . . . . . . . . . . . . . . . 171
9.3 Das Rabin-Verschlüsselungsverfahren * . . . . . . . . . . . . . . . . . . 173

10 Diskrete Logarithmen 179
10.1 Das diskrete Logarithmenproblem . . . . . . . . . . . . . . . . . . . . . 179
10.2 Der Baby-Step-Giant-Step-Algorithmus von Shanks . . . . . . . . . . . 180
10.3 Pollards -Methode * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
10.4 Die Reduktion nach Silver-Pohlig-Hellman . . . . . . . . . . . . . . . . 186

11 Faktorisierung 191
11.1 Prinzipielles Vorgehen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.2 Pollards -Methode * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Pollards p ’ 1-Methode . . . . . . . . . . . . . . . .
11.3 . . . . . . . . . . . . 194
11.4 Faktorisierung mit Differenzen von Quadraten . . . . . . . . . . . . . . 197
11.5 Die Kettenbruchmethode von Morrison-Brillhardt * . . . . . . . . . . . 201
11.6 Das quadratische Sieb . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

12 Signaturverfahren 209
12.1 Allgemeines zu Signaturverfahren . . . . . . . . . . . . . . . . . . . . . 209
12.2 Das RSA-Signaturverfahren . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.3 Das ElGamal-Signaturverfahren . . . . . . . . . . . . . . . . . . . . . . . 212
12.4 Digital Signature Standard “ DSS . . . . . . . . . . . . . . . . . . . . . . 216
Inhalt ix

13 Elliptische Kurven * 219
13.1 Projektive Ebenen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
13.2 De¬nition elliptischer Kurven . . . . . . . . . . . . . . . . . . . . . . . . 224
13.3 Tangenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
13.4 Die Gruppe E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Die Gruppe (E, +) . . . . . . .
13.5 . . . . . . . . . . . . . . . . . . . . . . . . 237

14 Anwendungen elliptischer Kurven in der Kryptologie * 241
14.1 Das ElGamal-Verfahren auf elliptischen Kurven . . . . .. . . . . . . . 241
14.2 Das Signaturverfahren ECDSA . . . . . . . . . . . . . . .. . . . . . . . 242
14.3 Faktorisierung mit elliptischen Kurven . . . . . . . . . . .. . . . . . . . 244
14.4 Zur Anzahl der Punkte einer Kurve . . . . . . . . . . . .. . . . . . . . 247

Literaturverzeichnis 255

Index 257
1 Klassische Verfahren

Unter Kryptogra¬e versteht man im ursprünglichen Sinne die Wissenschaft vom
Verschlüsseln von Informationen, um deren Geheimhaltung zu sichern. Im Zeit-
alter des Internet werden neben dieser Gew¤hrleistung von Vertraulichkeit wei-
tere Ziele durch kryptogra¬sche Methoden verwirklicht. Integrit¤t, Authentizit¤t,
digitale Unterschrift und Authorisierung sind moderne Schlagworte. Das, was sich
dahinter verbirgt, kann mit neueren kryptogra¬schen Methoden erreicht werden.
Die Kryptoanalyse, manchmal auch als Kryptanalyse bezeichnet, ist die Wissen-
schaft, die Methoden und Techniken entwickelt, um Informationen aus den ver-
schlüsselten Texten zu gewinnen “ etwa den ursprünglichen Text, Teile davon,
oder gar den Schlüssel, der zur Verschlüsselung benutzt wurde. In gewisser Wei-
se dient die Kryptoanalyse einem möglichen Angreifer. Tats¤chlich ist die Kryp-
toanalyse zur Überprüfung der Sicherheit kryptogra¬scher Methoden unerl¤ss-
lich. Sie schützt den Nutzer vor unliebsamen Überraschungen.
Die Kryptologie fasst die beiden Wissenschaften Kryptogra¬e und Kryptoanaly-
se zusammen. H¤u¬g wird der Begriff Kryptogra¬e für Kryptologie verwendet.

1.1 Worum geht™s?
Die Kryptogra¬e besch¤ftigt sich mit der Sicherung von Nachrichten gegen einen
unbefugten Zugriff. Im Gegensatz dazu steht die Codierungstheorie, die Daten
gegen zuf¤llig auftretende Fehler bei ihrer Übertragung schützen soll, und die
nicht Gegenstand dieses Buches ist. Ein bewusster unbefugter Zugriff auf Daten
wird in der Kryptologie Angriff genannt. Dagegen sollen die kryptogra¬schen
Verfahren schützen.
Die klassische Kryptogra¬e hatte prim¤r die Aufgabe,
• Vertraulichkeit zu gew¤hrleisten. D. h., Unbefugte sollten eine Nachricht
nicht lesen können.
Daneben schützt die moderne Kryptogra¬e
• Integrit¤t von Daten: Es wird sichergestellt, dass der Empf¤nger der Da-
ten eine eventuelle Ver¤nderung der Daten, die ein Angreifer verursachte,
erkennt.
• Authentizit¤t des Absenders: Der Empf¤nger merkt, wenn ein Unbefugter
sich für einen anderen Teilnehmer ausgibt.
• Unterschriften, mit allen rechtlichen Folgen.
• Authorisierung: Nur Befugte erhalten Zugang.
2 1 Klassische Verfahren

Es gibt ein Reihe weiterer Problemstellungen, zu denen die moderne Kryptogra-
¬e Lösungen anbietet (siehe [19]).
Natürlich gibt es für alle diese Probleme schon klassische Lösungen, wie etwa
der versiegelte Brief, die (h¤ndische) Unterschrift, das Postgeheimnis mit Andro-
hung von Strafe bei Verstößen usw. Die Mathematik hat aber mehr zu bieten: Der
elektronische Austausch von Daten erfordert neue Methoden, und die Methoden
der Mathematik sind prinzipiell unabh¤ngig vom Medium. Außerdem bietet die
Mathematik Methoden an, die wirklich nur das schützen, was zu schützen ist “
n¤mlich die Information. Schließlich ist es “ zumindest im Prinzip “ möglich, die
Sicherheit kryptogra¬scher Methoden zu beweisen. Dadurch ist man vor bösen
Überraschungen (wie etwa vor einer neuen Technologie) besser geschützt.

Bemerkung
Tats¤chlich gibt es nur wenige Verfahren, bei denen die Sicherheit beweisbar ist.
Für praktische Zwecke sind diese Verfahren eher von untergeordneter Bedeu-
tung, weil sie wenig ef¬zient sind. Wir werden sie in den Kapiteln 2 und 5 vor-
stellen.

Wir behandeln in diesem ersten Kapitel einige klassische kryptogra¬sche Ver-
fahren. Obwohl eine Verwendung dieser Verfahren heutzutage l¤ngst nicht mehr
empfehlenswert ist, l¤sst sich an ihnen das Wesen der Kryptologie verst¤ndlich
schildern. Zugleich zeigen uns diese Verfahren, warum die Mathematik die rich-
tige Sprache ist, in der sichere Verschlüsselungsmethoden zu formulieren sind.
Die gegen Ende des 16. Jahrhunderts entwickelte Vigenère-Chiffre macht als Para-
debeispiel einer klassischen Verschlüsselungsmethode einen Großteil dieses ers-
ten Kapitels aus. Sie galt fast 300 Jahre als sicher. Erst zur Mitte des 19. Jahrhun-
derts gelang es, Vigenère-Chiffren mit der damals neuen statistischen Analyse zu
brechen. Die statistische Analyse ist demnach ein kryptoanalytisches Konzept.
Einen möglichen Angreifer darf man niemals untersch¤tzen, man muss ihm nicht
nur höchste Intelligenz unterstellen, man sollte sogar stets davon ausgehen, dass
er auch die Methode der Verschlüsselung kennt. Dies ist der Inhalt des Kerck-
hoffs™schen Prinzips, das Grundlage jeder Verschlüsselungsmethode sein sollte.
Das erste Kapitel ist neben seinem einführenden Charakter von zwei Thesen ge-
leitet. Zum einen erfordert moderne Kryptologie einen tieferen Einblick in die
Mathematik, insbesondere in die Algebra. Zum anderen ist die Kenntnis der
kryptogra¬schen und kryptoanalytischen Methoden der klassischen Verfahren
zur Entwicklung neuer und sicherer Verfahren unabdingbar.

1.2 Monoalphabetische Chiffrierung
Hinter dem folgenden Geheimtext verbirgt sich eine der naheliegendsten Ver-
schlüsselungsmethoden:
HMIWIV XIBX MWX PIMGLX DY IRXWGLPYIWWIPR
Wie wurde verschlüsselt? Welcher Schlüssel wurde verwendet?
1.2 Monoalphabetische Chiffrierung 3

1.2.1 Die Caesar-Chiffre

Die Caesar-Chiffre, auch Verschiebe-Chiffre genannt, z¤hlt zu den ¤ltesten Ver-
fahren überhaupt. Wir beschreiben das Verfahren an einem Beispiel. Ist der Buch-
stabe K der Schlüssel, so wird der Text
mathe ist schoen
wie folgt verschlüsselt:
WKDRO SCD CMRYOX
Da K der 11-te Buchstabe des Alphabets ist, wird jeder Buchstabe um 10 Schritte
im Alphabet weitergez¤hlt. Dabei geht es nach Z mit A weiter. Die Buchstaben
des Alphabets werden also zyklisch vertauscht:
···
a b c p q r s t u v w x y z
···
K L M Z A B C D E F G H I J
Wie man bereits an diesem einfachen Beispiel sieht, ist die Caesar-Chiffre leicht
zu brechen. Das liegt daran, dass es nur sehr wenige Schlüssel “ n¤mlich 26 “ gibt,
die man alle durchprobieren kann.
Man kann die Suche sogar noch verkürzen, indem man im Geheimtext die h¤u-
¬gsten Buchstaben aus¬ndig macht. Die h¤u¬gsten Buchstaben deutscher Texte
sind e bzw. n mit einer H¤u¬gkeit von rund 17 bzw. 10 Prozent. Aufgrund dieser
Tatsache hat man den Schlüssel im Allgemeinen nach wenigen Versuchen ge-
funden. In dem sehr kurzen einführenden Beispiel ist das I im Geheimtext der
h¤u¬gste Buchstabe, sodass I wahrscheinlich für den Klartextbuchstaben e steht,
was auch korrekt ist.

Bemerkung
Wie in der klassischen Kryptogra¬e üblich, haben wir nur Großbuchstaben und
keine Sonderzeichen, Umlaute o. „. verwendet. Tats¤chlich wurden in der Praxis
nicht einmal Leerzeichen gesetzt, die wir hier der Übersichtlichkeit halber stehen
ließen.


1.2.2 Mathematische Modellierung
Um eine pr¤zisere und auch einfachere Beschreibung des von Caesar benutz-
ten Verfahrens zu erhalten, fassen wir die 26 Buchstaben des lateinischen Alpha-
bets als Zahlen, genauer als Elemente der additiven Restklassengruppe Z26 =
{0, 1, . . . , 25}, auf. Wie üblich ist dabei

a = a + 26 Z = {. . . , a ’ 26, a, a + 26, a + 52, . . . } .

Wir erinnern vorab an die De¬nition der Addition in der Restklassengruppe
(Z n , +), n ∈ N. Es gilt

(a + n Z) + (b + n Z) = (a + b) + n Z , d. h. a + b = a + b für a, b ∈ Z .
4 1 Klassische Verfahren

Beispiel
Die Verknüpfungstafel für (Z7 , +) lautet ausführlich:
+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5

Nun de¬nieren wir eine bijektive Abbildung

¦ : {A, B, C, . . . , Z} ’ Z26 ¦(A) = 0, ¦(B) = 1, . . . , ¦(Z) = 25 .
durch

Wir numerieren also die Buchstaben “ beginnend mit 0 “ durch. Manchmal lassen
wir auch den Querstrich bei a ∈ Z26 weg, w¤hlen dann aber stets den kleinsten
positiven Repr¤sentanten, wir schreiben also z. B. 3 = 3 = 29 in Z26 .
Der Klartext, das ist der Text, der verschlüsselt werden soll, kann nun als Zei-
lenvektor oder Wort über Z26 aufgefasst werden. Der Schlüssel wird ebenfalls als
Zahl, genauer als Restklasse k ∈ Z26 , aufgefasst, und die Verschlüsselung erfolgt
durch Addieren von k zu jeder einzelnen Komponente des Wortes:
Verschlüsselung
N = (a1 , . . . , an ) ’’ C = (a1 + k, . . . , an + k) .
Klartext Geheimtext

Die Bijektion ¦ wird als Codierung bezeichnet und tr¤gt nichts zur Geheimhal-
tung bei. Wir werden im Folgenden h¤u¬g nur die Verschlüsselung von Zahlen
(genauer gesagt von Elementen einer Halbgruppe) beschreiben, ohne auf die Co-
dierung einzugehen: Buchstaben bzw. Texte sind für uns also nur noch Zahlen
bzw. aneinandergereihte Zahlen. Um uns die Wahl des Alphabets frei zu halten,
werden wir im Folgenden anstelle von 26 h¤u¬g schlicht q ∈ N schreiben.
Die Caesar-Chiffre l¤sst sich mit etwas Mathematik leicht verallgemeinern und
dadurch auch erheblich verbessern. Dennoch wird sich herausstellen, dass sie in
dieser allgemeineren Form heutigen Anforderungen nicht genügt.

1.2.3 Substitutions-Chiffren

Das Problem der zu geringen Anzahl von Schlüsseln bei der Caesar-Chiffre l¤sst
sich leicht lösen, indem man anstelle der 26 Verschiebungen jede beliebige Permu-
tation der 26 Buchstaben des Alphabets zul¤sst, z. B.
···
a b c p q r s t u v w x y z
.
···
L A H M X D R U E J B O I Z
1.2 Monoalphabetische Chiffrierung 5

Es gibt dann 26! ≈ 4 · 1026 Schlüssel. Das sind bereits zu viele, um selbst mit
einem sehr schnellen Rechner alle Möglichkeiten durchzuprobieren.

26! = 403 291 461 126 605 635 584 000 000

Das Sicherheitsproblem einer solchen Substitutions-Chiffre ist die jedem An-
greifer bekannte H¤u¬gkeitsverteilung der Buchstaben in einem durchschnittli-
chen deutschsprachigen Text “ wir geben diese H¤u¬gkeitsverteilung in der fol-
genden Gra¬k wieder:




Durch Z¤hlen der gleichen Buchstaben des Geheimtextes ¬ndet man die h¤u¬gs-
ten Buchstaben e und n und dann durch weiteres Kombinieren, etwa das Bestim-
men h¤u¬ger Buchstabenpaare wie ch, st, usw., weitere Buchstaben und dann
die restlichen Substitutionen.

Beispiel
Gegeben ist der Geheimtext:
ZHV KHI TC VJNKI STJNKI, HGTU STJNKI KHI TC TJVTV,
XVD MTVV TC TJVTV KHI, DHVV KHI TU TC VJNKI STJNKI.
Z¤hlt man die Buchstaben durch, so ¬ndet man vierzehn Mal den h¤u¬gsten
Buchstaben T, am zweith¤u¬gsten zwölf Mal den Buchstaben V und schließlich je
sieben Mal die Buchstaben J und H. Nach der oben angegebenen H¤u¬gkeitsver-
teilung der Buchstaben in einem durchschnittlichen deutschen Text entspricht
wohl dem Geheimtextbuchstaben T der Klartextbuchstabe e und dem Geheim-
textbuchstaben V der Klartextbuchstabe n. Wir vermuten zudem, dass der Ge-
heimtextbuchstabe J den Klartextbuchstaben i wiedergibt und setzen diese ein.
So erhalten wir den teilweisen Klartext:
6 1 Klassische Verfahren

ZHn KHI eC niNKI SeiNKI, HGeU SeiNKI KHI eC einen,
XnD Menn eC einen KHI, DHnn KHI eU eC niNKI SeiNKI.
Wer den Geheimtext noch nicht err¤t, erkennt, dass das Buchstabenpaar NK mit
fünf Mal am h¤u¬gsten auftritt. Setzt man dafür ch ein, so ergibt sich leicht der
Klartext
man hat es nicht leicht, aber leicht hat es einen,
und wenn es einen hat, dann hat er es nicht leicht.
Auch das Paar KH tritt mit vier Mal h¤u¬g auf. Man erkennt aber sofort, dass es
nicht für ch stehen kann.

Substitutions-Chiffren sind monoalphabetisch: Jeder Klartextbuchstabe wird im-
mer in denselben Geheimtextbuchstaben chiffriert. Durch eine statistische Ana-
lyse sind monoalphabetische Verfahren leicht zu brechen.

Bemerkung
In Zeitungen ¬ndet man manchmal Denksportaufgaben, die auch dieses Verfah-
ren benutzen. Dabei wird h¤u¬g jedem Buchstaben ein Zeichen “ das kein Buch-
stabe ist “ zugeordnet und die Aufgabe besteht darin, diese Zuordnung zu be-
stimmen und den geheimen Text zu entschlüsseln.



1.3 Das Kerckhoffs™sche Prinzip und die Angriffsarten
Monoalphabetische Verfahren sind leicht zu brechen “ vorausgesetzt, der Angrei-
fer weiß, dass monoalphabetisch verschlüsselt wurde. In der Tat sollte man davon
ausgehen, dass ein Angreifer dies weiß. Das ist der Inhalt des Kerckhoffs™schen
Prinzips, das wir in diesem Abschnitt erl¤utern. Anhand des Geheimtextes l¤sst
sich auch feststellen, ob monoalphabetisch verschlüsselt wurde. Wie das funktio-
niert, beschreiben wir in Abschnitt 1.6.2.
Man unterscheidet verschiedene Angriffsarten, die nachfolgend erl¤utert wer-
den. Ein Verschlüsselungsverfahren wird man nur dann als sicher bezeichnen,
wenn es gegen diese Angriffe gefeit ist.


1.3.1 Das Kerckhoffs™sche Prinzip
Das Verfahren, mit dem verschlüsselt wird, ist in der Praxis meist nicht geheim
zu halten. Tats¤chlich sollte es gar nicht geheim gehalten werden; zumindest darf
die Sicherheit des Verfahrens nicht auf einer solchen Geheimhaltung beruhen.

Das Kerckhoffs™sche Prinzip. Die Sicherheit eines Verschlüsselungssystems darf
nicht von der Geheimhaltung des Algorithmus abh¤ngen. Die Sicherheit gründet einzig
auf der Geheimhaltung des Schlüssels.
1.3 Das Kerckhoffs™sche Prinzip und die Angriffsarten 7

Wird dieses Prinzip beherzigt, können sowohl die Codierung als auch die ver-
wendeten Verfahren und auch die Implementierung offengelegt werden. Das bie-
tet eine Reihe von Vorteilen:

• Was geheim zu halten ist, ist klar umrissen und so wenig als nur möglich.

• Im Prinzip kann jeder Benutzer selbst die Sicherheit prüfen.

• Insbesondere Experten werden h¤u¬g verwendete Verfahren genau unter-
suchen und eventuelle Schwachstellen aufdecken. Das geschieht auch re-
gelm¤ßig.

• Man kann relativ sicher sein, dass keine geheimen Tricks “ etwa von Ge-
heimdiensten “ die Geheimtexte für bestimmte Kreise lesbar machen.

Bemerkung
Alle Systeme, die das Kerchhoffs™sche Prinzip nicht beachtet haben, sind gebro-
chen worden. So wurden oft auch Maschinen gebaut, die die Chiffrierung über-
nahmen. Hier ist eine physische Trennung zwischen Algorithmus (= Maschine)
und Schlüssel gegeben. Selbst wenn die Maschine in die H¤nde der Feinde f¤llt,
ist bei strikter Anwendung des Kerckhoffs™schen Prinzips die Sicherheit noch ge-
w¤hrleistet.

1.3.2 Angriffsarten
Natürlich darf der Klartext N aus einem Geheimtext C nicht ersichtlich sein. Das
bloße Abfangen eines verschlüsselten Textes C darf die Sicherheit nicht kompro-
mittieren, wie es etwa bei der Caesar-Chiffre der Fall ist. Das ist aber nur das Mi-
nimum an Sicherheit, das von einem Verschlüsselungsverfahren gefordert wer-
den muss. Die Ansprüche an Sicherheit sollten deutlich höher gesetzt sein. Ein
Angreifer könnte auch zu einem früheren Geheimtext C den dazugehörigen Klar-
text N kennen oder gar einen selbst gew¤hlten Klartext chiffrieren lassen und so
den zugehörigen Geheimtext erhalten. Eventuell kann der Angreifer bei wieder-
holten Angriffen seinen Klartext stets anpassen, um weitere Informationen aus
den Geheimtexten zu erhalten. Man unterscheidet die folgenden Angriffsarten.

Cipher-Text-Only: Der Angreifer kennt nur den verschlüsselten Text C.


Known-Plain-Text: Der Angreifer kennt einen Klartext N und den dazuge-

hörigen verschlüsselten Text C.

Chosen-Plain-Text: Der Angreifer kann einen Klartext N ausw¤hlen und

den dazugehörigen Geheimtext C erzeugen (lassen).

• Adaptive-Chosen-Plain-Text: Wie beim Chosen-Plain-Text-Angriff, aber
mit mehreren Runden, in denen der Angreifer seine Wahl anpassen kann.
8 1 Klassische Verfahren

• Chosen-Cipher-Text: Der Angreifer kann einen selbst bestimmten Geheim-
text C entschlüsseln lassen.
Ein Angreifer kann seine Attacke im Allgemeinen auch wiederholen, zumindest
sollte man als Sender oder Empf¤nger von verschlüsselten Nachrichten davon
stets ausgehen.
Wenn wir im Laufe der n¤chsten Kapitel Verschlüsselungsverfahren vorstellen,
werden wir immer wieder zeigen, welche Angriffstypen eventuelle Schwachstel-
len der Verfahren ausnutzen können und welche Erfolge ein Angreifer bei seinen
Attacken erzielen kann.
Bevor wir nun aber weitere (immer noch klassische) Verschlüsselungsverfahren
ansprechen, werden wir etwas mathematischer, um die Darstellung zu pr¤zisieren
und kompakter zu gestalten.

1.4 Die Halbgruppe der Strings

Ein String ist eine endliche Folge von Buchstaben eines vorgegebenen Alphabets.
Strings kann man verknüpfen, indem man sie aneinanderh¤ngt. Jeder Text, jedes
Buch ist in diesem Sinne ein String.
Für eine nichtleere Menge A, genannt Alphabet, setzen wir

A— := An .
n∈N0

Die Menge A— heißt die Menge der Wörter oder Strings über dem Alphabet A.
Es ist A0 = {µ} mit dem leeren Wort µ.
Weil die Vereinigung n∈N0 An disjunkt ist, gibt es zu jedem w ∈ A— genau ein
n ∈ N0 mit w ∈ An . Wir schreiben (w) = n und nennen n die L¤nge von w.
Zu v = v1 · · · v (v) , w = w1 · · · w (w) ∈ A— setzen wir

v · w := v1 · · · v w1 · · · w und µ · v = v = v · µ .
(v) (w)

Diese Verknüpfung · auf A— wird auch Konkatenation genannt. Wir schreiben
kurz v w anstelle von v · w, wir benutzen also kein spezielles Symbol für diese
Verknüpfung, sondern schreiben die zu verknüpfenden Wörter einfach hinter-
einander. Wir erhalten unmittelbar:

Lemma 1.1
Es sei A ein Alphabet.
(A— , · ) ist eine Halbgruppe mit neutralem Element µ.
(a)
Für v, w ∈ A— gilt (v w) = (v) + (w).
(b)

Im Computerzeitalter ist oft A = Z2 . In der Praxis liegen somit die Nachrichten
als String über Z2 vor. Für die L¤nge eines Strings über Z2 wird die Einheit Bit
benutzt.
1.5 Kryptosysteme 9

1.5 Kryptosysteme

Unter einem kryptogra¬schen System, kurz Kryptosystem, verstehen wir ein
Tupel (P, C, K, f , g) mit nichtleeren Mengen P, C, K und Abbildungen
f : P — K ’ C und g : C — K ’ P
mit der Eigenschaft:
(—) ∀ k ∈ K ∃ k ∈ K : g( f (x, k), k ) = x für alle x ∈ P .
Setzt man für k ∈ K bzw. k ∈ K
f k := f ( . , k) : P ’ C bzw. gk := g( . , k ) : C ’ P ,
so können wir die Eigenschaft (—) auch schreiben als:
(—) ∀ k ∈ K ∃ k ∈ K : gk —¦ f k = idP .
Es heißen
• P die Klartextmenge (P wie plain text),
• C die Geheimtextmenge (C wie cipher text),
• K die Schlüsselmenge (K wie key),
• f Verschlüsselungsfunktion,
• g Entschlüsselungsfunktion.
Die Bedingung (—) besagt, dass jeder durch einen Schlüssel k verschlüsselte Klar-
text durch einen Schlüssel k entschlüsselt werden kann. Außerdem ist die Be-
dingung gk —¦ f k = idP in (—) bekanntlich gleichwertig zur Injektivit¤t der Abbil-
dung f k bzw. zur Surjektivit¤t der Abbildung gk (vgl. Aufgabe 1.2). Folglich gilt
|P| ¤ |C|.

Bemerkung
Manchmal lassen wir die Abbildung g weg und nennen ein Viertupel (P, C, K, f )
ein Kryptosystem, wenn die Abbildungen f k für alle k ∈ K injektiv sind. Die In-
jektivit¤t von f k gew¤hrleistet n¤mlich die Existenz einer surjektiven Abbildung
gk : C ’ P mit gk —¦ f k = idP .

Beispiel
Die Caesar-Chiffre über dem Alphabet Z q mit q Buchstaben ist ein Kryptosys-
tem. Es ist P = Z — = C die Klartext- und Geheimtextmenge, Z q die Schlüssel-
q
menge, und für jedes k ∈ Z q ist durch
f k : Z — ’ Z — , w1 w2 · · · w ’ (w1 + k) (w2 + k) · · · (w + k)
(w) (w)
q q

eine Verschlüsselungsfunktion gegeben. Die Entschlüsselungsfunktion gk ist ge-
geben durch die Abbildung gk = f ’k = f q’k .
10 1 Klassische Verfahren

Die Bezeichnung f k bzw. gk werden wir stets in der obigen Bedeutung benutzen.
Mit jedem Kryptosystem (P, C, K, f , g) sind die Familien von Abbildungen f k und
gk gegeben.



1.5.1 Symmetrisch versus asymmetrisch

Die Tatsache, dass der zum Dechiffrieren benötigte Schlüssel k wie in (—) ange-
geben nicht mit dem Schlüssel zum Verschlüsseln k übereinstimmen muss, ist die
Basis für die asymmetrische Kryptogra¬e.
Wenn es möglich ist, ein Kryptosystem (P, C, K, f , g) zu ¬nden, bei dem aus der
Kenntnis von f k nicht auf k ∈ K bzw. gk mit gk —¦ f k = idP geschlossen wer-
den kann, dann muss man den Schlüssel k gar nicht geheim halten. Jeder kann
einem Empf¤nger Nachrichten zukommen lassen, die mit demselben öffentlich
bekannten Schlüssel verschlüsselt sind, und nur der Empf¤nger kann entschlüs-
seln. Verfahren, die diese Bedingungen erfüllen, nennt man asymmetrisch.
Im Gegensatz dazu heißt ein Kryptosystem (P, C, K, f , g) symmetrisch, wenn für
alle k ∈ K gilt gk —¦ f k = idP . Die in (—) angegebenen Schlüssel k und k sind also
gleich. Ein Beispiel ist die Caesar-Chiffre.
Man könnte den Begriff des symmetrischen Kryptosystems etwas allgemeiner
fassen, indem man verlangt, dass aus der Kenntnis von k ∈ K das Element k ∈
K, bzw. gk leicht bestimmt werden kann. Das bedeutet aber nur, dass es eine
Abbildung k ’ k gibt. Dann kann man auch setzen gk := gk und erh¤lt die oben
beschriebene Situation.

Bemerkung
Der eben für symmetrische Verfahren beschriebene Vorgang ist prinzipiell auch
für asymmetrische Verfahren möglich. Natürlich h¤ngt gk von k ab. Entschei-
dend ist die Tatsache, dass man keinen ef¬zienten Algorithmus kennt, der gk aus
k berechnet. Die Details sind etwas komplizierter und werden uns in Kapitel 4
besch¤ftigen.
Leider erfasst der Begriff Kryptosystem diesen feinen Unterschied nicht. Daher
meiden ihn manche Autoren. Wir meinen, dass er dennoch nützlich ist und die
algorithmischen Eigenschaften aus dem Kontext klar werden. Für symmetrische
Verfahren ist er allemal ad¤quat.



1.6 Polyalphabetische Chiffrierung

Durch statistische Analysen ist es leicht, monoalphabetische Chiffren zu brechen.
Dieser Angriff kann umgangen werden: H¤u¬ge Buchstaben, wie etwa e und n,
können durch verschiedene Zeichen dargestellt werden, sodass letztlich im Ge-
heimtext jeder Buchstabe gleich h¤u¬g vorkommt. Dennoch scheitert auch dieses
1.6 Polyalphabetische Chiffrierung 11

Vorgehen an der Statistik. Die H¤u¬gkeit von Buchstaben-Paaren, -Tripeln usw.
wird nicht ver¤ndert und erlaubt eine erfolgreiche Analyse.
Polyalphabetische Chiffren erreichen eine bessere Verteilung der H¤u¬gkeiten von
Buchstaben. Außerdem kann die Anzahl der Schlüssel beliebig groß gew¤hlt wer-
den. Eine wichtige Eigenschaft, die es im Prinzip erlaubt, die Systeme an sich
wandelnde Anforderungen anzupassen. Leider sind sie “ wie wir sehen werden
“ nicht gegen eine statistische Analyse gefeit, solange der Schlüssel deutlich kür-
zer als der Klartext ist.
In diesem Abschnitt wird als Beispiel für eine polyalphabetische Chiffre die
Vigenère-Chiffre diskutiert. In der klassischen Kryptogra¬e wurden viele Varian-
ten dieses Systems vorgeschlagen. Sie können (fast) alle mit Varianten der vorge-
stellten Angriffe gebrochen werden.



1.6.1 Die Vigenère-Chiffre

Gegeben sei das Alphabet Z q und ein String k = k1 · · · k ∈ Z q der L¤nge “
der Schlüssel bzw. das Schlüsselwort. Wir verschlüsseln nun den Klartext N =
x1 · · · xn ∈ Z n . Dazu wird dieser in Blöcke der L¤nge eingeteilt,
q

N = (x1 · · · x ) (x +1 · · · x2 ) (x2 +1 · · · x3 ) · · · (xr +1 · · · xn ) .

Falls n nicht durch teilbar ist, verbleibt ein Block xr +1 · · · xn einer L¤nge kleiner
als . Nun wird jeder Block xs +1 · · · x(s+1) mit der Verschlüsselungsfunktion f k
wie folgt verschlüsselt:

f k (xs · · · x(s+1) ) = (xs + k1 ) · · · (x(s+1) + k ) .
+1 +1

Der eventuell verbleibende Block einer L¤nge kleiner als wird mit entsprechend
verkürztem Schlüssel chiffriert.
Bei dieser Verschlüsselung wird jede Komponente mit einer Caesar-Chiffre ver-
schlüsselt:
Verschlüsselung
’’ + ki .
xs xs
+i +i


Beispiel
Erneut in Z26 erh¤lt man für = 4 und k = 2 6 3 4 beispielsweise:

Klartext N : ···
15 2 14 0 21 6 18 2 6
“+2 “+6 “+3 “+4 “+2 “+6 “+3 “+4 “+2 ···
Geheimtext C : ···
17 8 17 4 23 12 21 6 8

Die Entschlüsselung erfolgt mit f ’k . Aus dem Klartextbuchstaben 6 werden beim
Verschlüsseln die verschiedenen Geheimtextbuchstaben 12 und 8.
12 1 Klassische Verfahren

Die Vigenère-Chiffre ist ein polyalphabetisches Verfahren: Ein Klartextbuchsta-
be wird an verschiedenen Stellen des Textes im Allgemeinen zu verschiedenen
Geheimtextbuchstaben chiffriert.
Allein durch das Z¤hlen der verschiedenen Buchstaben des Geheimtextes erh¤lt
man kaum Hinweise auf den Klartext. Jedoch versagt die Vigenère-Chiffre offen-
sichtlich bei einem Known-Plain-Text-Angriff. Ein solcher liefert direkt den Schlüs-
sel oder Teile davon.
In der frühen Neuzeit wurde die Vigen©re-Chiffre natürlich nicht als Chiffre
über dem Restklassenring Z26 aufgefasst, sondern über dem üblichen Alpha-
bet A = {a, b, c, . . . , z} mit 26 Buchstaben. Die Addition des Schlüsselwortes
aus A erfolgt mit dem sogenannten Vigen©re-Quadrat, mit dessen Hilfe Vigen©re-
Chiffren für beliebige Schlüsselworte gebildet werden können.
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 E
. . .
. . .
. . .
ZABCDEFGHIJKLMNOPQRSTUVWXY
Für die konkrete Anwendung mit einem bestimmten Schlüsselwort ist ein Aus-
schnitt des Vigen©re-Quadrats aber bequemer zu benutzen. Wir zeigen dies an
einem Beispiel.

Beispiel
Wir verschlüsseln das Gedicht „Die Ameisen“ von Joachim Ringelnatz mit dem
Schlüsselwort „LYRIK“, sodass wir die Zeilen des Vigen©re-Quadrats notieren,
deren erste Buchstaben das Schlüsselwort ergeben, außerdem notieren wir das
Alphabet für den Klartext darüber:
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
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
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
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
I 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
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
Der Anschaulichkeit halber erfolgt die Verschlüsselung in einer dreizeiligen Dar-
stellung, in deren erster Zeile der Klartext, also das Gedicht, steht, in deren zwei-
ter Zeile das wiederholte Schlüsselwort und ganz unten der daraus resultierende
Geheimtext. Dieser entsteht, indem die Klartextbuchstaben durch die Geheim-
textbuchstaben ersetzt werden, die in den entsprechenden Zeilen der Schlüssel-
wortbuchstaben des Vigen©re-Quadrats stehen, so geht der Klartextbuchstabe i
über dem Schlüsselwortbuchstaben L über in den Geheimtextbuchstaben T usw.:
1.6 Polyalphabetische Chiffrierung 13

In Hamburg lebten zwei Ameisen, Die wollten nach Australien reisen.
LY RIKLYRI KLYRIK LYRI KLYRIKL, YRI KLYRIKL YRIK LYRIKLYRIK LYRIKL.
TL YIWMSIO VPZKMX KUVQ KXCZAOY BZM GZJCBOY LRKR LSJBBLJZMX CCZAOY

Bei Altona auf der Chaussee, Da taten ihnen die Beine weh,
YRI KLYRIK LYR IKL YRIKLYRI, KL YRIKL YRIKL YRI KLYRI KLY,
ZVQ KWRFVK LSW LOC AYIEDQVM NL RRBOY GYVOY BZM LPGEM GPF

und da verzichteten sie weise, Dann auf den letzten Teil der Reise.
RIK LY RIKLYRIKLYRI KLY RIKLY, RIKL YRI KLY RIKLYRI KLYR IKL YRIKL.
LVN OY MMBKGTPDPRVV CTC NMSDC UIXY YLN NPL CMDKRVV DPGC LOC PVQCP

Der Geheimtext lautet:
TLYIWMSIOVPZKMXKUVQKXCZAOYBZMGZJCBOYLRKRLSJBBLJZMXCCZAOYZVQKWRFVKLS
WLOCAYIEDQVMNLRRBOYGYVOYBZMLPGEMGPFLVNOYMMBKGTPDPRVVCTCNMSDCUIXYYLN
NPLCMDKRVVDPGCLOCPVQCP

Wir zeigen nun, wie man durch eine verfeinerte statistische Analyse die Vigenère-
Chiffre sogar durch einen Cipher-Text-Only-Angriff brechen kann.



1.6.2 Die Kryptoanalyse der Vigenère-Chiffre

Die Vigenère-Chiffre kann selbst bei sehr großen Schlüssell¤ngen noch gebrochen
werden, wenn man nur ausreichend Geheimtext zur Verfügung hat.
Die folgenden beiden Tests führen das Problem auf das (sehr einfache) Brechen
einer Caesar-Chiffre zurück. In der Tat liefern sie sehr zuverl¤ssige Sch¤tzungen
für die L¤nge des benutzen Schlüssels k = k1 · · · k .

Der Kasiski-Test. Wiederholen sich in einem Klartext Buchstabenfolgen (wie
z. B. ein), so werden sie im Allgemeinen in verschiedene Folgen verschlüsselt “
es sei denn, ihr Abstand ist ein Vielfaches der Schlüssell¤nge . Dann entstehen
zwei identische Folgen von Buchstaben im Geheimtext.
Hier setzt der Kasiski-Test an. Es werden sich wiederholende Buchstabenfolgen
gesucht und deren Abst¤nde d1 , . . . , dn bestimmt. Im Allgemeinen ist ein Teiler
von d1 , . . . , dn . Bildet man den größten gemeinsamen Teiler über alle diese Ab-
st¤nde, so ist also ein Teiler von t = ggT(d1 , . . . , dn ). Nun kann es aber auch
sein, dass sich zuf¤llig Buchstabenfolgen wiederholen. Diese kann man meistens
leicht entlarven. Diese Buchstabenfolgen liefern Abst¤nde d j , die zu den meisten
Abst¤nden di = d j teilerfremd sind.

Beispiel
Auf obiges Beispiel soll nun der Kasiski-Test angewandt werden. Dazu suchen
14 1 Klassische Verfahren

wir Wiederholungen im Geheimtext, denen Wiederholungen des Klartextes ent-
sprechen.

In Hamburg lebten zwei Ameisen, Die wollten nach Australien reisen.
TL YIWMSIO VPZKMX KUVQ KXCZA OY,.BZM GZJCBOY LRKR LSJBBLJZMX CCZAOY.
.. .. :::


Bei Altona auf der Chaussee, Da taten ihnen die Beine weh,
ZVQ KWRFVK LSW LOC AYIEDQVM, NL RR::: GYVOY.BZM LPGEM GPF,
BOY . ..

und da verzichteten sie weise, Dann auf den letzten Teil der Reise.
LVN OY MMBKGTPDPRVV CTC NMSDC UIXY YLN NPL CMDKRVV DPGC LOC PVQCP

Sich wiederholende Passagen haben wir im Text hervorgehoben. Wir bestimmen
ihre Abst¤nde und berechnen deren größten gemeinsamen Teiler t. Die tats¤ch-
liche Schlüssell¤nge sollte ein Teiler von t sein. Die faktorisierten Abst¤nde der
oben zu ¬ndenden Wiederholungen sind in der folgenden Tabelle dargestellt.

40 = 5 · 2 · 2 · 2 30 = 5 · 3 · 2
VQK: CZAOY:
65 = 13 · 5 50 = 5 · 5 · 2
OYBZM: BOY:
80 = 5 · 2 · 2 · 2 · 2 25 = 5 · 5
LOC: RVV:

Für t erhalten wir t = ggT(40, 30, 65, 50, 80, 25) = 5. Wie wir wissen, ist dies die
tats¤chliche Schlüssell¤nge.

Der Kasiski-Test liefert eine kleine Menge möglicher Schlüssell¤ngen, n¤mlich
die Teiler von t. Der folgende Friedman-Test liefert eine Sch¤tzung der Größen-
ordnung der Schlüssell¤nge . Kombiniert man die beiden Tests, so erh¤lt man in
den meisten F¤llen den genauen Wert von . Und hat man erst einmal die Schlüs-
sell¤nge , so ist es leicht, den Geheimtext zu entschlüsseln, weil man damit die
Verschlüsselung auf Caesar-Chiffrierungen zurückgeführt hat.

Der Friedman-Test. Dieser Test basiert auf der H¤u¬gkeitsverteilung (hi )i∈Zq
aller Buchstaben eines Geheimtextes C = x1 · · · xn ∈ Z n über dem Alphabet Z q .
q
Wir gehen vorab davon aus, dass wir irgendeinen Text (sprich einen String) x =
x1 · · · xn ∈ Z n vorliegen haben, und erkl¤ren zu diesem Text eine Größe I(x) ∈ Q
q
“ den Friedman™schen Koinzidenzindex.
Die Zahl h a := |{k ; xk = a}|, a ∈ Z q , gibt an, wie oft der Buchstabe a im Text
x = x1 · · · xn vorkommt. Die rationale Zahl

1
‘ h a (h a ’ 1)
I(x) :=
n (n ’ 1) a∈Z q


heißt der (Friedman™sche) Koinzidenzindex des Wortes x. Wir begründen:
1.6 Polyalphabetische Chiffrierung 15

Lemma 1.2
Der Friedman™sche Koinzidenzindex I(x) für einen String x = x1 · · · xn gibt die Wahr-
scheinlichkeit dafür an, dass bei zuf¤lliger Wahl zweier Buchstaben xi , x j , i = j, aus dem
String x diese beiden Buchstaben gleich sind.

Beweis. Die Anzahl der ungeordneten Paare xi , x j mit i = j und xi = x j = a ist
gleich
h a (h a ’ 1)
ha
= ,
2 2
und die Anzahl aller ungeordneten Paare xi , x j mit i = j ist

n (n ’ 1)
n
= .
2 2

Damit ergibt sich wegen

(ha ) 1
‘ ‘
I(x) = n= h a (h a ’ 1)
2
n (n ’ 1)
(2)
a∈Z q a∈Z q

die Behauptung.
Wir bestimmen nun den Koinzidenzindex für einen deutschen Durchschnittstext
und für einen Text, bei dem alle Buchstaben gleich oft vorkommen. Dazu stellen
wir vorab fest: Es sei x = x1 · · · xn ein String über dem Alphabet Z q . Angenom-
men, wir kennen die Wahrscheinlichkeit p a , mit der wir den Buchstaben a in x
bei zuf¤lliger Wahl ziehen. Dann ist die Zahl ‘ a∈Zq p2 in etwa die Wahrschein-
a
lichkeit dafür, dass wir bei zuf¤lliger Wahl von zwei Buchstaben im Text x zwei
gleiche Buchstaben ziehen, d. h.


I(x) ≈ p2 .
i
i∈Z26

Da man bei einem deutschen Durchschnittstext natürlich die Wahrscheinlichkei-
ten p a , pb , pc , . . . für die 26 Buchstaben des Alphabets kennt (vgl. die Gra¬k auf
Seite 5), erh¤lt man so leicht den Koinzidenzindex ID für einen solchen Text. Es
gilt
ID ≈ 0.0762 .
Und nun nehmen wir an, dass die Buchstaben in dem Text x = x1 · · · xn alle
gleichverteilt sind, d. h. p a = 1 für alle a ∈ Z q . Im Fall q = 26 erhalten wir für
q
einen solchen Text mit gleichverteilten Buchstaben den Index

IG ≈ 0.0385 .

Man bedenke, dass man bei der (polyalphabetischen) Vigenère-Chiffre eine sol-
che Gleichverteilung aller Buchstaben im Geheimtext als idealisiertes Ziel hat.
16 1 Klassische Verfahren

Bemerkung
Wie in Aufgabe 1.5 gezeigt werden soll, gilt ‘ a∈Zq p2 ≥ 1 ; und Gleichheit gilt
a q
hierbei genau dann, wenn p a = pb für alle a, b ∈ Z q , d. h. wenn eine Gleichver-
teilung der Buchstaben herrscht.
Bei monoalphabetischer Chiffrierung bleibt der Index I vor und nach der Ver-
schlüsselung offenbar unver¤ndert. Daher ist I(x) ein Indikator dafür, ob mo-
noalphabetisch oder polyalphabetisch verschlüsselt wurde. Bei polyalphabeti-
scher Verschlüsselung wird I(x) n¤mlich kleiner, sofern die Schlüsselbuchstaben
gleichverteilt gew¤hlt wurden.


Für die folgende Betrachtung nehmen wir an, dass x ein mit der Vigenère-Chiffre
verschlüsselter deutscher Text sei. Die Schlüssell¤nge, die wir n¤herungsweise
bestimmen wollen, sei . Den Friedman™schen Koinzidenzindex I(x) können wir
mit der oben angegebenen Formel bestimmen, es sind hierbei nur die H¤u¬gkei-
ten der einzelnen Buchstaben zu ermitteln.
Nun ermitteln wir den Friedman™schen Koinzidenzindex I(x) zu dem Geheim-
text C = x1 · · · xn erneut, aber n¤herungsweise und in Abh¤ngigkeit von der
L¤nge des Schlüsselworts. Die n¤herungsweise Formel für I(x), die wir erhal-
ten, können wir nach au¬‚ösen. Daraus gewinnen wir eine N¤herung für .
Der Übersicht wegen stellen wir uns vor, der Text sei in ein -spaltiges Schema
eingetragen.
...
x1 x2 x
...
x +1 x +2 x2
. . . .
. . . .
. . . .
... xn
xr +1

Es liegt dann in jeder Spalte eine Caesar-Chiffrierung vor. Damit ist der Koinzi-
denzindex in jeder Spalte in etwa der Index eines (durchschnittlichen) deutsch-
sprachigen Textes:
I(xk , xk+ , xk+2 , . . . ) ≈ ID .

Die Wahrscheinlichkeit, in zwei verschiedenen Spalten ein Paar aus gleichen
Buchstaben zu w¤hlen, ist in etwa IG (hierbei nehmen wir an, dass das Schlüs-
selwort hinreichend zuf¤llig und groß genug ist, sodass also über die Spalten
verteilt in etwa eine Gleichverteilung der Buchstaben besteht).
Wir bestimmen nun den Koinzidenzindex. Dazu ist die Wahrscheinlichkeit zu
bestimmen, dass man bei zuf¤lliger Wahl von zwei Buchstaben xi , x j , i = j, aus
dem Geheimtext C = x1 · · · xn zwei gleiche Buchstaben xi = x j ausw¤hlt. Um
diese Wahrscheinlichkeit zu bestimmen, ermitteln wir zun¤chst, wie viele Buch-
stabenpaare es im Geheimtext bei der obigen Anordnung gibt.
Wenn wir zwei Buchstaben xi und x j zuf¤llig w¤hlen, dann liegen beide Buch-
staben xi und x j entweder in ein und derselben Spalte oder sie liegen in zwei
verschiedenen Spalten.
1.6 Polyalphabetische Chiffrierung 17

( n ’1)
n
n
Es gibt in etwa ( 2 ) = Buchstabenpaare in einer Spalte (dieses etwa be-
2
zieht sich darauf, dass die hinteren Spalten evtl. um ein Element kürzer sind,
n
bei den vorderen Spalten ist die Angabe ( 2 ) natürlich exakt). Für die Spalten
erhalten wir also
• Die Anzahl der ungeordneten Buchstabenpaare aus gleichen Spalten ist in
n ( n ’1)
= n (n’ ) .
etwa 2 2

Wir ermitteln nun, wie viele Möglichkeiten es gibt, zwei Buchstaben aus verschie-
n (n’1)
denen Spalten zu w¤hlen: Es gibt insgesamt (n) = Möglichkeiten, zwei
2 2
Buchstaben zu w¤hlen. Davon subtrahieren wir nun die oben gesch¤tzte Anzahl
der Möglichkeiten, zwei Buchstaben in einer Spalte zu w¤hlen, und erhalten in
etwa die Anzahl der Möglichkeiten, zwei Buchstaben in verschiedenen Spalten
zu w¤hlen:
n (n ’ 1) n n ’ 1 n (n ’ n )
’ = .
2 2 2
Wir halten fest:
• Die Anzahl der ungeordneten Buchstabenpaare aus verschiedenen Spalten
n (n’ n ) ’1
= n2 2 .
ist in etwa 2

Wegen Lemma 1.2 ist die relative H¤u¬gkeit von Paaren gleicher Buchstaben in
den Spalten durch ID gegeben, die von Paaren in verschiedenen Spalten durch
IG . Damit erhalten wir die erwartete Anzahl A von Paaren gleicher Buchstaben
im gesamten Geheimtext C = x1 · · · xn :

n (n ’ ) ’1
A= ID + n2 IG .
2 2
Wenn wir diese Anzahl A durch die Anzahl (n) aller möglichen Paare teilen, er-
2
halten wir eine N¤herung für den Friedman™schen Koinzidenzindex:
n’ ’1
A n
≈ = ID +
I(x) IG
(n ’ 1) n’1
n (n’1)
2
1 1
n n
= (ID ’ IG ) + IG ’ ID .
n’1 n’1 n’1
Daraus ergibt sich folgender Sch¤tzwert für die Schlüssell¤nge:

n (ID ’ IG )
≈ .
(n ’ 1) I(x) + ID ’ n IG

Beispiel
Wir wenden den Friedman-Test auf den Geheimtext aus dem Beispiel auf Seite
12 an. Um den Friedman-Test durchführen zu können, muss man erst den Fried-
manschen Koinzidenzindex I(C) des Geheimtextes C berechnen. Dazu bestimmt
18 1 Klassische Verfahren

man die H¤u¬gkeiten h± der Buchstaben ± des benutzten Alphabets, in diesem
Fall des 26-buchstabigen lateinischen Alphabets. Diese sind in folgender Tabelle
aufgelistet.
3 7 12 5 2 2 6 0 4
A B C D E F G H I
3 8 12 11 5 9 9 4 7
J K L M N O P Q R
4 3 2 12 3 4 11 8
S T U V W X Y Z
Daraus errechnet sich der Koinzidenzindex dann wie folgt:

3·2+7·6+···+8·7
1
· ‘ h± · (h± ’ 1) =
I(C) = ≈ 0.0457 .
n · (n ’ 1) ±∈A 156 · 155
26


Mit diesem Koinzidenzindex I(C) erhalten wir für die Schlüssell¤nge die Sch¤t-
zung:

n · (ID ’ IG ) 156 · (0.0762 ’ 0.0385)
≈ ≈ ≈ 5.10 .
(n ’ 1) · I(C) + ID ’ n · IG 155 · 0.0457 + 0.0762 ’ 156 · 0.0385

Dieses Ergebnis ist konsistent mit dem Ergebnis des Kasiski-Tests, der oben
durchgeführt wurde. Ein Angreifer, der mithilfe der beiden Tests die Schlüssel-
l¤nge = 5 ermittelt hat, kann den Geheimtext entschlüsseln, indem er ihn in
fünf Teilchiffren zerlegt und diese durch H¤u¬gkeitsanalyse knackt.

Ist im Extremfall der Schlüssel l¤nger als der zur Verfügung stehende Geheimtext,
und sind die Schlüsselbuchstaben gleichverteilt gew¤hlt, so ergibt sich I(C) =
IG . Dann l¤uft der Friedman-Test (und jeder andere Angriff) ins Leere. Unsere
Formel liefert für diesen Fall
≈ n.
Das wird im folgenden Kapitel genauer diskutiert.

Bemerkung
Wie schon erw¤hnt, sind viele Varianten der klassischen Vigenère-Chiffrierung
möglich. So kann etwa eine Substitutions-Chiffre anstelle einer einfachen Ver-
schiebe-Chiffre benutzt werden. Alle Varianten wurden gebrochen. Die statisti-
sche Analyse spielte dabei stets eine Schlüsselrolle.



1.7 Af¬ne Chiffren und ihre Kryptoanalyse *

Af¬ne Chiffren verallgemeinern die Vigenère-Chiffre. Sie nutzen die Tatsache aus,
dass Z q nicht nur eine abelsche Gruppe, sondern sogar ein Ring ist. Wir formu-
lieren af¬ne Chiffren nachfolgend noch etwas allgemeiner. Anstelle von Z q sei
ein kommutativer Ring R mit Einselement 1 gegeben.
1.7 Af¬ne Chiffren und ihre Kryptoanalyse * 19

1.7.1 Der Matrizenring über R

Ein Element u des Ringes R heißt Einheit, wenn es v ∈ R gibt mit u v = 1. Man
sagt auch, u sei invertierbar. Die Menge aller Einheiten bildet eine Gruppe R— ,
genannt die Einheitengruppe. Die Einheitengruppe von Z ist z. B. Z — = {±1}.
Aus der linearen Algebra sind Matrizen über einem Körper K bekannt. Es wur-
den Addition, Multiplikation und auch die Determinante von quadratischen Ma-
trizen eingeführt. Für jedes ∈ N ist (K — , +, ·) ein Ring mit Einselement I “ die
— -Einheitsmatrix. Und eine — -Matrix M über dem Körper K ist bekannt-
lich genau dann invertierbar, wenn die Determinante det M ungleich 0, d. h. eine
Einheit in K ist.
Für die De¬nitionen war es nicht entscheidend, dass K ein Körper ist, diese De¬-
nitionen sind auch für einen Ring R möglich. Und man erh¤lt dasselbe Resultat.
Wir bezeichnen den Ring der — -Matrizen über R mit der bekannten Addition
und Multiplikation von Matrizen mit R — . Und eine Matrix M ∈ R — ist genau
dann invertierbar, wenn die Determinante det M in R— liegt, d. h. eine Einheit in
R ist. Das zeigt man wie in der linearen Algebra mithilfe der Adjunkten. Auch
die meisten S¤tze zu Matrizen über einem Körper K bleiben im Falle eines Ringes
R richtig. So gelten etwa
• der Laplace™sche Entwicklungssatz für die Determinante und
• das Invertierbarkeitskriterium für Matrizen: Eine Matrix ist genau dann in-
vertierbar, wenn ihre Spalten linear unabh¤ngig sind.

Beispiel

Wir betrachten zwei Matrizen über dem Ring (Z8 , +, ·); es gilt Z8 = {1, 3, 5, 7}.
Wegen
⎛ ⎞
230
23
= ’1 = 7 und det ⎝0 1 1⎠ = 4
det
11
020
ist die erste Matrix invertierbar, die zweite jedoch nicht. Es gilt:
⎛⎞ ⎛⎞ ⎛⎞ ⎛⎞
3 0
2 0
⎝0⎠ + 4 ⎝1⎠ + 4 ⎝1⎠ = ⎝0⎠ .
2
0 0
2 0
Daher sind die Spalten der Matrix linear abh¤ngig.


1.7.2 Af¬ne Abbildungen


Für eine Matrix M ∈ R und einen Vektor v ∈ R erkl¤ren wir die af¬ne Abbil-
dung

R R
f (M, v) : .
’ Mx+v
x
20 1 Klassische Verfahren

Lemma 1.3
Es seien M ∈ R — eine invertierbare Matrix und v ∈ R ein Vektor. Dann ist die af¬ne
Abbildung f (M, v) invertierbar. Das Inverse von f (M, v) ist f (M’1 , ’M’1 v) .


Beweis. Es sei x ∈ R . Dann gilt:

f (M’1 , ’M’1 v) —¦ f (M, v) (x) = f (M’1 , ’M’1 v) ( f (M,v) (x))
= f (M’1 , ’M’1 v) (M x + v)
= M’1 (M x + v) ’ M’1 v = x

Analog zeigt man f (M, v) —¦ f (M’1 , ’M’1 v) (x) = x. Folglich ist f (M, v) invertierbar,
und es ist f (M’1 , ’M’1 v) das Inverse von f (M, v) .




1.7.3 Af¬ne und lineare Chiffren
Lemma 1.3 liefert ein Verschlüsselungsverfahren. Ein Klartext N ∈ Rn wird in
Blöcke der L¤nge unterteilt

N = (x1 · · · x ) (x +1 · · · x2 ) · · · (xr +1 · · · x(r+1) )

(falls n, wird der letzte Block durch Buchstaben aus R zu einem Block der
L¤nge erg¤nzt) und dann jeder Block x = xs +1 · · · x(s+1) ∈ R mit einer inver-
tierbaren af¬nen Abbildung f (M, v) verschlüsselt:

Verschlüsselung
’’ f (M, v) (x) .
x

Mit der Umkehrabbildung g(M, v) := f (M’1 , ’M’1 v) wird dann jeder Block y =
f (M, v) (x) ∈ R entschlüsselt:

Entschlüsselung
’’ f (M’1 , ’M’1 v) (y) = x .
y

Bei einer solchen af¬nen Chiffre besteht der Schlüssel (M, v) aus einer invertier-
baren Matrix M ∈ R — und einem Vektor v ∈ R . Im Fall v = 0 spricht man von
einer linearen Chiffre.


Beispiel
Die Vigenère-Chiffre ist eine af¬ne Chiffre über R = Z q mit M = I , der —-
Einheitsmatrix, und v = k1 · · · k , dem Schlüsselwort.
1.7 Af¬ne Chiffren und ihre Kryptoanalyse * 21

1.7.4 Die Kryptoanalyse af¬ner Chiffren

Wir behandeln die Kryptoanalyse einer af¬nen Chiffre bei einem Known-Plain-
Text-Angriff. Gegeben sind + 1 Klartext-Geheimtext-Paare (xi , yi ) ∈ R — R ,
i = 0, . . . , , einer af¬nen Chiffre mit der Verschlüsselungsfunktion f (M,v) , also

yi = f (M,v) (xi ) für i = 0, . . . , ,

wobei M ∈ R — invertierbar und v ∈ R ist. Dann l¤sst sich der geheime Schlüs-
sel, das ist das Paar (M, v), leicht ermitteln, falls die Vektoren

x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 ∈ R

linear unabh¤ngig sind. Es gilt n¤mlich:

Lemma 1.4
Bilden die Vektoren x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 eine Basis des R , so erh¤lt man mit
den Matrizen

X = (x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 ) und Y = (y1 ’ y0 , y2 ’ y0 , . . . , y ’ y0 )

den geheimen Schlüssel (M, v) durch:

M = Y X ’1 und v = y0 ’ M x0 .

Beweis. Es sei i ∈ {1, . . . , }. Für die i-te Spalte der Matrix Y gilt:

yi ’ y0 = (M xi + v) ’ (M x0 + v) = M (xi ’ x0 ) .

Damit erhalten wir M X = Y. Da die Vektoren x1 ’ x0 , x2 ’ x0 , . . . , x ’ x0 eine
Basis des R bilden, ist die Matrix X invertierbar. Daher gilt M = Y X ’1 . Wegen
y0 = M x0 + v erh¤lt man mit der Kenntnis von M dann auch v.
Ist das Paar (M, v) erst einmal bekannt, so ist natürlich auch der Dechiffrier-
schlüssel (M’1 , ’M’1 v) leicht zu ermitteln. Im Fall R = Z q , q ∈ N, bestimmt
man M vorteilhaft durch einen Ansatz mit unbekannten Koef¬zienten und löst
das entstehende inhomogene lineare Gleichungssystem über Z q mit einem mo-
di¬zierten Gauß-Verfahren. Ist die Blockl¤nge zuerst nicht bekannt, so kann
man diese mit den Tests von Kasiski und Friedman wie für die Vigenère-Chiffre
ermitteln.
Die Kryptoanalyse wird bei einem Chosen-Plain-Text-Angriff trivial. L¤sst man
n¤mlich die + 1 Klartexte 0, e1 , . . . , e mit dem Nullvektor 0 ∈ R und den Ein-
heitsvektoren e1 , . . . , e ∈ R der kanonischen Basis verschlüsseln, so erh¤lt man
der Reihe nach den Vektor v und die Spalten der Matrix M. Daher spielen linea-
re Chiffren in der modernen Kryptologie keine Rolle mehr. Bei der Konstruktion
moderner Verfahren wird vielmehr darauf geachtet, sie so nichtlinear wie möglich
zu gestalten. Nicht-Linearit¤t ist ein wichtiges Qualit¤tskriterium.
22 1 Klassische Verfahren

Aufgaben
1.1 Die Skytale ist die ¤lteste bekannte Verschlüsselungsmethode, die für mili-
t¤rische Zwecke eingesetzt wurde. Sie wurde vor über 2500 Jahren von den Spar-
tanern verwendet: Ein schmaler Streifen Pergament oder Leder wird spiralförmig
um einen zylindrischen Stab gewickelt und in L¤ngsrichtung des Stabes beschrie-
ben. Wird der Streifen abgewickelt, bleibt ein unverst¤ndlicher Buchstabensalat.
Der (legitime) Empf¤nger wickelt den Streifen um einen Stab gleichen Durchmes-
sers und kann die Nachricht lesen.
Zeigen Sie, dass die Skytale unter geeigneten Annahmen eine lineare Chiffre ist.
Welches ist der Schlüssel?
1.2 Es sei S = (P, C, K, f , g) ein Kryptosystem. Zeigen Sie, dass für jedes k ∈ K
die Abbildungen f k := f ( . , k) : P ’ C injektiv und gk := g( . , k) surjektiv sind.
Bei welchen Angriffsarten versagen monoalphabetische Chiffren?
1.3
Gegeben ist der folgende Geheimtext:
1.4
KOZYVSQMFJKYDAFUXEQYPYZVVSFQGTOHQSSLXQQBAXUSXYOQBVMFGF
RSMQWEDUSSESUZUJHGNZZATQGTOHQZCLOYRZLLGBULYOYVMOTF
UYCZBVUMMGJLHEHVOYZRCLOFSJJBISZNYZRZUMSSJWLMSTOPQFKPYRH
RSMQWEAIFUVZWTCJZYZSIOUESRBZPSIZUZRSHHWGTOFUHKZWTIYSCQT
(a) Wenden Sie (i) den Kasiski-Test, (ii) den Friedman-Test an, und bestimmen
Sie die (vermutliche) L¤nge des Schlüsselwortes.
(b) Bestimmen Sie den zugehörigen Klartext. Welches Schlüsselwort wurde be-
nutzt?
m
1.5 Es seien m ∈ N und p1 , . . . pm nichtnegative reelle Zahlen mit ‘ pi = 1.
i=1
Zeigen Sie:
m m 2
(a) ‘ p2 = +‘ pi ’
1 1
.
i m m
i=1 i=1
m
1
(b) ‘ p2 ist nie kleiner als m. Wann liegt Gleichheit vor?
i
i=1

1.6 Folgendes Klartext-Geheimtext-Paar wurde mit einer af¬nen Chiffre über
Z12 mit Blockl¤nge 2 erzeugt:
1 3 6 2
N : x0 = , x1 = , x2 = , x3 = .
0 4 7 2
6 10 1 2
C : c0 = , c1 = , c2 = , c3 = .
3 1 1 2
Bestimmen Sie alle Schlüssel (M, v) ∈ GL2 (Z12 ) — Z2 , sodass M xi + v = ci für
12
i = 0, 1, 2, 3 gilt.
2 Das One-Time-Pad und perfekte
Sicherheit

Etwas salopp ausgedrückt ist ein Kryptosystem perfekt sicher, wenn ein Angreifer
einen Geheimtext zu jedem möglichen Klartext der gleichen L¤nge mit der glei-
chen Wahrscheinlichkeit entziffert. So vermutet ein Angreifer bei einem perfekt
sicheren Verfahren hinter dem Geheimtext
ODLHOWBPDOCP
die Klartexte
oder
ich liebe dich heute passt es
mit der gleichen Wahrscheinlichkeit, aber auch jeden anderen sinnigen oder un-
sinnigen Klartext, der 12 Buchstaben enth¤lt.
Perfekt sichere Kryptosysteme ¬nden in der Praxis nur selten Anwendung, da der
Schlüsselaustausch sehr umst¤ndlich ist. Soll ein Verfahren perfekt sicher sein,
so muss der Schlüssel mindestens so lang wie die Nachricht selbst sein, d. h.,
um eine Nachricht mit n Buchstaben vertraulich austauschen zu können, muss
vorher ein Schlüssel mit mindestens derselben L¤nge ausgetauscht werden.
Das sogenannte One-Time-Pad ist ein perfekt sicheres Verfahren. Und wie die Be-
zeichnung schon verr¤t, darf bei diesem Verfahren ein Schlüssel nur einmal be-
nutzt werden. Das One-Time-Pad ist im Wesentlichen eine Vigenère-Chiffre, bei
der der Schlüssel die L¤nge des Klartextes hat und jeder Buchstabe des Schlüssel-
Strings gem¤ß einer Gleichverteilung gew¤hlt wird.


2.1 Das One-Time-Pad
Bevor wir erl¤utern, was man unter perfekter Sicherheit versteht, schildern wir das
One-Time-Pad “ eine perfekt sichere Strom-Chiffre.


2.1.1 Strom-Chiffren

Bei einer Strom-Chiffre wird, im Gegensatz zu einer Block-Chiffre, jeder Buchsta-
be xi des Klartextes N = x1 · · · xn ∈ A— , A ein Alphabet, sofort mithilfe eines
Schlüssels in einen Buchstaben des Geheimtextes verschlüsselt:
Klartext N : · · · xn
x1 x2
“ “ ··· “
Geheimtext C : ···
c1 c2 cn
24 2 Das One-Time-Pad und perfekte Sicherheit

Bei einer Block-Chiffre hingegen wird die Nachricht

N = x1 · · · xn = (x1 · · · x ) (x +1 · · · x2 ) · · · (xr +1 · · · xn ) ∈ An

blockweise chiffriert; dazu wird zun¤chst ein eventuell verbleibender letzter un-
vollst¤ndiger Block (xr +1 · · · xn ) durch weitere Buchstaben zu einem vollst¤ndi-
gen Block (xr +1 · · · x(r+1) ) aufgefüllt:

Klartext N : (x1 · · · x ) (x +1 · · · x2 ) · · · (xr +1 · · · x(r+1) )
“ “ ··· “
Geheimtext C : (c1 · · · c ) (c +1 · · · c2 ) ··· (cr +1 · · · c(r+1) )

Beispiel
Die Vigenère-Chiffre ist eine Strom-Chiffre. Jede af¬ne Chiffre mit M = I (siehe
Abschnitt 1.7.3) ist eine Block-Chiffre.

Wie bereits erw¤hnt, sind af¬ne Chiffren unsicher. Es gibt aber auch sichere
Block-Chiffren, wir werden solche in Kapitel 3 behandeln.



2.1.2 Das Verfahren

Das One-Time-Pad, zu deutsch Einmal-Block, ist eine Strom-Chiffre, die schon im
Jahre 1917 von den AT&T Mitarbeitern Gilbert Vernam und Joseph O. Mauborgne
für den Einsatz in der Telegra¬e vorgeschlagen wurde. Vernam hat diese Chif-
fre ein Jahr sp¤ter patentieren lassen. Daher spricht man auch von der Vernam-
Chiffre. Kennzeichnend für das One-Time-Pad ist, dass

• der benutzte Schlüssel nur einmal verwendet werden darf (One-time),

• der Schlüssel genauso lang wie die Nachricht ist,

• der Schlüssel-String zuf¤llig gew¤hlt werden muss.

Einfach ausgedrückt ist ein One-Time-Pad eine Vigenère-Chiffre mit einem Schlüs-
sel-String, der mindestens die L¤nge des Klartextes N hat; genauer:
Das One-Time-Pad ist ein Kryptosystem mit Klartext-, Geheimtext- und Schlüs-

selmenge P = C = K = Z2 “ die Menge der Strings über dem Alphabet Z2 .
— —
Es seien N = x1 · · · xn ∈ Z2 ein Klartext der L¤nge n und k1 · · · kr ∈ Z2 ein
Schlüssel der L¤nge r ≥ n, wobei jede Ziffer k i ∈ Z2 des Schlüssel-Strings zuf¤llig
(genauer gleichverteilt) gew¤hlt wird.
Wir w¤hlen die ersten n Bits des Schlüssel-Strings k := k1 k2 · · · k n und verschlüs-
seln:
C = f (N , k) := N + k = (x1 + k1 , . . . , xn + k n ) .
2.2 Elementare Wahrscheinlichkeitsrechnung 25


Die Entschlüsselung des Geheimtextes C = (y1 · · · yn ) ∈ Z2 erfolgt genauso:

N = f (C, k) := C + k = (y1 + k1 , . . . , yn + k n ) .

Die Sicherheit des One-Time-Pad ist fast offensichtlich. Da die Ziffern des Schlüs-
sels k gem¤ß einer Gleichverteilung zuf¤llig aus Z2 gew¤hlt werden, ist der Ge-
heimtext C = N + k gleichverteilt in Z2 . Beobachtet man C, so ist jede mögliche
n

Nachricht N gleichwahrscheinlich. Es gibt also keinen Hinweis auf den Inhalt
der Nachricht.
Wir werden dieses Argument im n¤chsten Abschnitt pr¤zisieren, wenn wir eine
De¬nition für den Begriff der perfekten Sicherheit haben werden.

Bemerkung
Der Schlüssel k darf nur einmal benutzt werden, da man ihn bei einem Known-
Plain-Text-Angriff als k = C + N ermitteln kann.

Das Verfahren kann man auf das Alphabet Z q , q > 1, verallgemeinern.

Ein großes Problem in der Praxis ist der Schlüsselaustausch. Dafür muss man
genauso viele Daten übertragen wie sp¤ter für die eigentliche Nachricht. Daher
werden One-Time-Pads nur für sehr spezielle Anwendungen eingesetzt.

Auch die Schlüsselerzeugung ist schwierig. Das Problem ist die Erzeugung
von Zufallsfolgen. Mathematische Methoden sind deterministisch, die erzeug-
ten Folgen sind also nicht zuf¤llig. Eine physikalische Erzeugung, etwa über
den radioaktiven Zerfall, ist hingegen sehr aufw¤ndig und langsam. In der
Praxis begnügt man sich meist mit Pseudozufallsfolgen. Das sind determinis-
tisch konstruierte Folgen, die wie zuf¤llig aussehen und deren Bildungsgesetz
schwer zu ¬nden ist.

TAN-Listen, wie sie etwa beim Online-Banking verwendet werden, stellen eine
Variante der Vernam-Chiffre dar. Sie dienen aber nicht der Verschlüsselung,
sondern der Authenti¬zierung und der Rechtsverbindlichkeit.



2.2 Elementare Wahrscheinlichkeitsrechnung

Wir führen einige Begriffe der Wahrscheinlichkeitstheorie ein und leiten schließ-
lich den Satz von Bayes her.
In diesem Abschnitt seien durchweg P eine endliche Menge und

Pot(P) = {A ; A ⊆ P}

die Potenzmenge von P.
26 2 Das One-Time-Pad und perfekte Sicherheit

2.2.1 Wahrscheinlichkeitsverteilung und Wahrscheinlichkeitsfunktion

Wir nennen eine Abbildung p : Pot(P) ’ [0, 1] mit den beiden Eigenschaften

p(P) = 1 und p(A ∪ B) = p(A) + p(B) , falls A © B = …

eine Wahrscheinlichkeitsverteilung auf der Menge P. Für jedes Element A ∈
Pot(P) bezeichnen wir die Zahl p(A) ∈ [0, 1] als die Wahrscheinlichkeit, mit der
das Ereignis A ∈ Pot(P) eintritt. Man beachte, dass p(…) = 0 gilt. Dies folgt aus:

p(A) = p(A ∪ …) = p(A) + p(…) .

Eine Wahrscheinlichkeitsfunktion auf der (endlichen) Menge P ist eine Abbil-
dung p : P ’ [0, 1] mit der Eigenschaft
˜

‘ p(x) = 1 .
˜
x∈P

Aus einer Wahrscheinlichkeitsverteilung p : Pot(P) ’ [0, 1] gewinnt man eine
Wahrscheinlichkeitsfunktion p : P ’ [0, 1], indem man setzt
˜

p(x) := p({x}) für alle x ∈ P .
˜

Es gilt dann n¤mlich:


‘ ‘
p(x) = p({x}) = p {x} = p(P) = 1 .
˜
x∈P x∈P x∈P

Ist umgekehrt eine Wahrscheinlichkeitsfunktion p : P ’ [0, 1] gegeben, dann
˜
wird durch p : Pot(P) ’ [0, 1], wobei

‘ für alle A ∈ Pot(P)
˜
p(A) := p(x)
x∈A

eine Wahrscheinlichkeitsverteilung de¬niert.
˜
Wir unterscheiden im Weiteren die beiden Abbildungen p und p nicht typogra-
¬sch, d. h., wir setzen p = p. Wir werden stets mit einer der beiden Abbildungen
˜
die andere als gegeben annehmen.

Beispiel
Es sei |P| = q = 0. Wir erkl¤ren eine Abbildung p : P ’ [0, 1] durch

1
für jedes x ∈ P .
p(x) :=
q

Offenbar ist p eine Wahrscheinlichkeitsfunktion auf der Menge P. Die daraus
resultierende Wahrscheinlichkeitsverteilung nennt man Gleichverteilung.
2.2 Elementare Wahrscheinlichkeitsrechnung 27

Wir betrachten die Gra¬k auf Seite 5 zur H¤u¬gkeitsverteilung der Buch-
staben a, b, c, . . . , z des deutschen Alphabets A in einem durchschnittlichen
deutschen Text. Ist h± die relative H¤u¬gkeit des Buchstabens ± ∈ A, so ist
p : A ’ [0, 1] mit
p(±) := h± für jedes ± ∈ A
eine Wahrscheinlichkeitsfunktion auf der Menge A.


2.2.2 Bedingte Wahrscheinlichkeit

Es sei p eine Wahrscheinlichkeitsverteilung auf der Menge P. Sind A, B ∈ Pot(P)
Ereignisse mit p(B) = 0, so nennt man

p(A © B)
p(A | B) :=
p(B)

die bedingte Wahrscheinlichkeit für das Eintreffen von A, wenn man B schon

. 1
( 9)



>>