˝˛­. 1
(ţߨňň ŕţŰŔ¸ň˝˛Ôţ: 33)

╬├╦└┬╦┼═╚┼

ĐŰňń. ˝˛­. >>

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

˝˛­. 1
(ţߨňň ŕţŰŔ¸ň˝˛Ôţ: 33)

╬├╦└┬╦┼═╚┼

ĐŰňń. ˝˛­. >>