View
221
Download
0
Category
Preview:
Citation preview
Facharbeit
Kryptographie und Kryptoanal yse
der Vigenère-Chiffre
von
JohannesWeitzel
MathematikGK/12
Herr Bergmann
Schuljahr2001/2002
18.März 2002
Inhaltsverz eichnis
1. Einführung 1
1.1. Wasist Kryptologie? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Grundla gen der Kryptologie 2
2.1. Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2. GrundlagenklassischerChiffren . . . . . . . . . . . . . . . . . . . . . . . 2
2.3. DerModulo-Operator. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Blaise de Vigenère 3
4. Die Vigenère-Chiffre 4
5. Kryptoanal yse der Vigenère-Chiffre 6
5.1. DerKasiski-Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.2. DerFriedman-Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.3. AuswertungderkryptoanalytischenTests . . . . . . . . . . . . . . . . . . 11
6. Fazit 12
A. Implementierung en in PASCAL 13
A.1. Die Vigenère-Chiffre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
A.2. Die KryptoanalysenachKasiskiundFriedman . . . . . . . . . . . . . . . 15
A.3. Vigenère-GUI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
B. Häufigkeiten der Buc hstaben der deutsc hen Sprac he 18
Literatur 19
i
1. Einführung
DieseFacharbeitbefasstsichmit derklassischenVigenère-Chiffre,die1586vondemFran-
zosenBlaisede Vigenère entwickelt wurde,undderenKryptoanalysenachVerfahrenvon
Kasiski und Friedman.Die Vigenère-Chiffre ist die bekanntesteunterallen periodischen
polyalphabetischenAlgorithmen.Sieist derPrototypfür vieleAlgorithmen,dieprofessio-
nell bis in unserJahrhundertbenutztwurden.
1.1. Was ist Kryptologie?
Kryptologie ist ein Teilgebietder Mathematik,dassichmit derKryptographie(demVer-
schlüsseln)undderKryptoanalyse(dem„Knacken“ von Codes)beschäftigt.DasVer- und
Entschlüsselnvon Nachrichtenübt auchheutenocheinegroßeFaszinationauf Menschen
allerBevölkerungsschichtenaus.FachleuteausdenBereichenMathematik,Informatikund
Linguistik beschäftigensichmit dieseraltenWissenschaft,diebiszurMitte deszwanzigs-
tenJahrhundertshauptsächlichmilitärischangewendetwurde.
Doch heutegeht Kryptographiealle Menschenan. Pläne,Patente,Verträgeund andere
vertraulicheDatenwerdenauf Rechnerngespeichertund weltweit überdasInternetaus-
getauscht.OhneKryptographiewäreesfür Firmenleicht, Industriespionagezu betreiben
oderfür Geheimdienste,InformationenüberPersonenzusammeln.
Aberauchfür Privatpersonenwird Kryptographieimmerwichtiger. Am Bankautomaten,in
Telefonzellen,beimMobilfunk oderbeimHomebanking— überallsoll Kryptographieden
sicherenDatenaustauschgarantieren,um die Privatsphärezu wahren.Wichtig ist, dassdie
benutzenAlgorithmenoffen gelegt werden,dennnur sokanngewährleistetwerden,dass
KryptologensichdieserAlgorithmenannehmenunddannversuchen,diesezu entschlüs-
seln.SindübereinenlangenZeitraumalle Attackenerfolglos,sostärktdiesdasVertrauen
der Benutzerin die SicherheitdesAlgorithmus.DiesesPrinzip wurdeauchschonim 19.
Jahrhundertvon dembelgischenKryptographenAugusteKerkhoffs (Kerkhoffs‘ Maxime)
gefordert:
Die SicherheiteinesVerschlüsselungsverfahrensdarf nur vonder Geheimhal-
tungdesSchlüsselsabhängen,nicht jedoch vonder GeheimhaltungdesAlgo-
rithmus.
1
2. Grundla gen der Kryptologie
2.1. Terminologie
Die Wissenschaftder Kryptologie enthälteinigeTermini, die vorabkurz dargestelltwer-
den.
Der lesbareText einerNachricht(message)wird Klartext genanntundmit M bezeichnet.
Man sagt,derKlartext wird übereinemAlphabet gebildet.Ein AlphabetA ist eineendli-
cheMengevonZeichen,derenMächtigkeit mit n � �A�dargestelltwird. AuchGeheimtext
(chiffre) C undderSchlüssel(key) K sind ZeichenkettenüberdemgleichenAlphabetA.
Beispielsweiseist „DIESERTEXTSOLLGEHEIMBLEIBEN“einKlartext überdemAlpha-
bet � A � B � C ��������� Z � .Die umkehrbareVerschlüsselungsfunktionE (encryption)wandeltden Klartext M mit
Hilfe desSchlüsselsK in denChiffr etextC. Die UmkehrungvonE zurWiederherstellung
wird Entschlüsselunggenanntundmit D (decryption)bezeichnet.
NachdiesenDefinitionengilt EK M � C undDK C � M. DaE umkehrbarist, gilt
DK EK M � � M �dennnachdemEntschlüsselneinesChiffretextessolltederKlartext herauskommen.Einen
solchenAlgorithmus nenntman symmetrischenAlgorithmus , da zum Chiffrieren und
zumDechiffrierenimmerdergleicheSchlüsselK benutztwird. BeiasymmetrischenAlgo-
rithmen , diein dieserArbeit jedochkeineRollespielen,wird zumChiffriereneinSchlüssel
K1 undzumDechiffrierenein andererSchlüsselK2 benutzt.Esgilt also:
EK1 M � C
DK2 C � M
DK2 EK1 M � � M �
2.2. Grundla gen klassisc her Chiffren
Esgibt verschiedeneMethoden,diebeiklassischenChiffren(dassindChiffren,diebisetwa
1950entwickelt wurden)zumEinsatzkommen.BeispielsweisewerdenbeieinerTranspo-
sitionschiffre die ZeichendesKlartextesvertauscht(Permutation).Siebleibenalsoerhal-
ten,sindim Chiffretext dannaberananderenPositionen.
2
Bei Substitionschiffren wird jedesZeichendesKlartextesdurchein anderesersetzt.Die
Positionbleibt jedochgleich.Eine Chiffre, bei der jedesKlartextzeichenimmer auf das-
selbeGeheimtextzeichenabgebildetwird, ist mit Hilfe einerTabellewie in AnhangB sehr
leichtzuentschlüsseln.SolcheChiffren,wie beispielsweisedieChiffre desrömischenKai-
sersCäsar(sieheauchKapitel 4, Fußnote2), nenntmanmonoalphabetisch. EineSubsti-
tionschiffre ist polyalphabetisch, wennsie nicht mehrmonoalphabetischist. Polyalpha-
betischheißtalso,dassein Klartextzeichennicht immer auf dasselbeGeheimtextzeichen
abgebildetwerdenmuss.Ein E im Klartext kannim Geheimtext mal einemA, mal einem
T odersonsteinemZeichendesbenutztenAlphabetsentsprechen.
Die im FolgendendargestellteVigenère-Chiffre isteinesolchepolyalphabetischeVerschlüs-
selung.
2.3. Der Modulo-Operator
In derVigenère-Chiffre sowie in vielenanderenkryptographischenAlgorithmenspieltder
Modulo-OperatoreinewichtigeRolle.Mit demModulo-OperatorberechnetmandenRest
einerDivision.BeimDividiereneinernatürlichenZahla durcheineanderenatürlicheZahl
b bleibt einRestr � � 0 � 1 ��������� b � 1 � . ZumBeispielist
23 : 3 = 7 Rest2 oder23= 7 � 3 � 2
27 : 3 = 9 Rest0 oder27= 9 � 3 � 0 �Definition: Seiena � b ��� undseia � bq � r. Dannschreibtman:
r = a mod b.
Zwei Zahlena, b ��� heißenrestgleich, wenna mod n = b mod n. Man schreibta � b
mod n undsprichta ist kongruent zu b modulo n .
3. Blaise de Vigenère
Blaisede Vigenère (1523bis 1596)wurdein Frankreichgeborenundgenossdie Ausbil-
dungeinesAdeligen,obwohl erdiesemStandgarnichtangehörte.Er arbeitetein verschie-
3
denenBerufenundwurdespäterSektretärdesHerzogsvonNevers.Nachdemdieserstarb,
wurdeVigenèrevoneinemGerichtbeauftragt,diplomatischeAufgabenin Romzuerfüllen.
Dort kamer erstmalsin Berührungmit derKryptographie.VerschiedeneKryptologenbe-
spracheneinBuchdesArztesundMathematikersJ.B. Porter . EsenthieltdieBeschreibung
eineskryptographischenAlgorithmus,derzudieserZeit alsnichtentschlüsselbargalt.Lei-
derwardieserAlgorithmussehrunpraktisch,denndieTabellenzumEntschlüsselnmussten
vomSenderundvomEmpfängerdergeheimenNachrichtimmermit sichgetragenwerden.
Außerdemwar dieserAlgorithmusbeimVerschlüsselnsehrfehleranfällig.Obwohl dieser
Algorithmusnichtviel angewandtwurde,verdanktPorterseinemSystemdieBezeichnung
„VaterdermodernenKryptographie“.
NachdemVigenèrenach Paris zurückkehrte,beganner seinekryptographischenStudi-
en,die er in seinemBuch „A Treatiseon SecretWriting“1, niederschrieb. Es enthältdas
Vigenère-Quadrat,welchesin Kapitel 4 genauerbeschriebenwird. Fachleutehieltendie
Vigenère-Chiffre für die größtekryptographischeErfindungseitJulius Cäsar2(100bis 44
v.Chr.). Tatsächlichwar VigenèresChiffre einewesentlicheVerbesserungzu PortersSys-
tem,denndiesesbenötigtespezielleTabellen,währendVigenèresChiffre lediglich ein gut
merkbaresSchlüsselwort unddasVigenère-Quadrat,dasimmerundüberallzu rekonstru-
ierenist, benötigt.
4. Die Vigenère-Chiffre
Die Vigenère-Chiffre ist eineVerschiebechiffre, bei der jedesZeichenim Alphabetver-
schobenwird, wobeider Betragder Verschiebungvon derPositiondesZeichensim Text
unddemSchlüsselwort abhängt.SenderundEmpfängermüssenbei derVigenère-Chiffre
ein Schlüsselwort vereinbaren.Außerdemmüssenbeideim Besitzdesuntendargestellten
Vigenère-Quadratssein.Die Buchstabenim Vigenère-Quadratsinddurchnummeriert,wo-
bei bei 0 begonnenwird. Der BuchstabeA hatalsodie Nummer0, B die Nummer1 bisZ
mit derNummer25.
1sinngemäß:„Eine AbhandlungüberGeheimschrift“2CäsarsAlgorithmusberuhtedarauf,BuchstabendesKlartextesum einegewissenAnzahlzu verschieben,
woraussich dannder Chiffretext ergab. Cäsarbenutztedazuden Schlüssel3, was beispielsweiseaus
einemA im Klartext einD im Chiffretext machte.
4
DasVigenère-Quadrat
- 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
0 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
1 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
2 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
3 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
4 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
5 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
6 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
7 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
8 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
9 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
10 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
11 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
12 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
13 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
14 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
15 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
16 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
17 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
18 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
19 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
20 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
21 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
22 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
23 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
24 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
25 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
Sollte der vereinbarteSchlüssel(im Beispiel „baum“) kürzerals der Klartext sein,muss
derSchlüsselsolangehintereinandergeschriebenwerden,bis er die LängedesKlartextes
erreicht.
Beispiel:
Klartext: diesertextsollgeheimbleiben
Schlüsselwort: baumbaumbaumbaumbaumbaumbau
Chiffretext: EIYEFRNQYTMAMLAQIECYCLYUCEH
Um diesesErgebniszuerhalten,gehtmanwie folgt vor: DerSenderverschlüsseltBuchsta-
befür Buchstabe.Um denBuchstabendmit demSchlüsselb zukodieren,suchtderSender
einfachdenEintragin Spalted undZeileb im Vigenère-Quadrat.Er findetdenBuchstaben
E, derdenerstenBuchstabendesChiffretext ergibt (Im Vigenère-Quadratfett dargestellt).
5
Auf dieseWeisewird nunfortgefahren,bisdergesamteText verschlüsseltist.
Zum Entschlüsselngehtmanandersvor. Der Empfängerist im BesitzdesChiffretextes
und desSchlüssels.Um denerstenBuchstabenzu entschlüsseln,suchter in der Spalteb
denEintragE. Gehter nunganznachobenim Vigenère-Quadrat,findeter dort denKlar-
textbuchstabend. SokannderEmpfängerdemChiffretext mit Hilfe desVigenère-Quadrat
Buchstabefür Buchstabeentschlüsseln.
MathematischkannmandasVerschlüsselnmit folgenderFormeldarstellen:
E z� i � z � Ki mod k modn � Vz� Ki mod k
K ist in dieserFormelderSchlüsselmit derLängek, dargestelltalsVektormit denNum-
mernderBuchstaben(baum entpricht1,0,20,12).V ist die Matrix desVigenère-Quadrats,
zdieNummerdeszuverschlüsselndenZeichensim Alphabet,i diePositionvonz im Klar-
text undn die LängedesAlphabets.
Will manim Beispielalsodass von „soll“ mit demu verschlüsselnsosetztmanein:
E z� i � 18 � K11 mod 4 mod26 � V18� K11 mod 4�
11 mod4 ergibt 3, undK3 ist der Buchstabeu, der im Vigenère-QuadratdenZahlenwert
20 hat.Nun ergibt sich:
E z� i � 18 � 20 mod26 � V18� 20 �
38 mod26 ergibt 12,wasim Vigenère-QuadratdemBuchstabenM entspricht.Nachdieser
FormelkannmannunTextemit derVigenère-Chiffre verschlüsseln.
EineImplementierungdieserChiffrier-Funktionin derProgrammiersprachePASCAL fin-
detsichim AnhangA.1.
5. Kryptoanal yse der Vigenère-Chiffre
Bei derAnalyseeinerVigenère-Chiffre ist daswichtigsteZiel dieBestimmungderSchlüs-
sellängek, dennwennmandiesebestimmthat,sofunktioniertderRestderEntschlüsselung
6
wie beieinergewöhnlichenVerschiebechiffre. Die Kryptoanalysesoll anHanddesfolgen-
denChiffretextesgezeigtwerden:
TFNMJ BDCRI TVVAF SRCJI FDPIN NNMKA PELIW TTPYQ
FUIWJ SJBIX ULMGP XRZWN FDQXO PICRS ALAER NVVKJ
HRVKJ OJQIM BKBIS TZKLZ FSMVW PSWXJ SLVXJ SYIPY
FERSW VEVLN FCBHF TDMRX DYTMH IVOIM JIVJZ FIMMS
FESSR QCQDN FIBIS DFUTZ UVZWT GZMAF SJQGM OZKLY
TFAMH IKMVT CJQII BQCWY JDUXJ FZVQJ OJKLR VJAXJ
EFKLR FYZWJ JEIPX FZVIR BJKLN OV
5.1. Der Kasiski-T est
Der Kasiski-Test geht auf denpreußischenInfanteriemajorFriedrich Wilhelm Kasiski
(1805bis 1881)zurück.ErfundenwurdedieserTestzwar 1854von demenglischenMa-
thematiker Charles Babbage(1792bis 1871),jedochhatBabbageseinenTestnie veröf-
fentlicht.ErstneunJahrespäterhatKasiskidiesgetan.
Der Kasiski-Testbasiertdarauf,dassmandenGeheimtext nachWiederholungenvon Zei-
chenfolgenmit mindestensdrei Zeichenuntersuchtund derenAbstandmisst. Je länger
die gefundenenZeichenfolgen,destogrößerdie Wahrscheinlichkeit, dassderAbstandein
Vielfachesder Schlüssellängeist. Die Erklärunghierfür ist einfach:Wiederholtsich eine
Zeichenfolgeim Klartext mit einemAbstandalsVielfachesderSchlüssellänge,sowird die
Wiederholung(bei einerVigenère-Chiffre) gleichcodiert.
Eskannnatürlichsein,dassim Chiffretext Wiederholungenauftreten,die reinzufällig sind
undderenAbstandnicht dasVielfachederSchlüssellängebeträgt.Die Wahrscheinlichkeit
für zufälligeWiederholungenist aberviel kleiner als für WiederholungendesVielfachen
derSchlüssellänge.
DurchsuchtmannundenGeheimtext nachsolchenWiederholungen,misstderenAbstand
undrechnetdessenPrimfaktorenaus,kommtmanzu folgendemErgebnis:
7
Zeichenfolge Abstand Primfaktoren
AFS 175 5 � 5 � 7VKJ 5 5
JOJ 145 5 � 29
JQI 125 5 � 5 � 5BIS 80 2 � 2 � 2 � 2 � 5ZKL 100 2 � 2 � 5 � 5XJS 5 5
MHI 60 2 � 2 � 3 � 5FZV 30 2 � 3 � 5JKL 30 2 � 3 � 5KLR 10 2 � 5
Auf denerstenBlick könntemanmeinen,dassdie Schlüsselwortlänge5 sei. Allerdings
kommtauchderFaktor2 häufigvor. Ein Schlüsselwort derLänge2 zu wählenwäreaber
äußerstunklug,da dasEntschlüsselndannnicht mehrschwerist. Trotzdemwird jetzt an
HanddesFriedman-Testsversucht,dieSchlüsselwortlängegenauerzubestimmen.
5.2. Der Friedman-T est
Der Friedman-Testwurde1925vom bedeutendenamerikanischenKryptologenWilliam
Friedman (1891 bis 1969) entwickelt. Friedmanwird heutezu einemder wichtigsten
Kryptologen,die jemalsgelebthaben,gezählt.Auch im zweitenWeltkrieg war Friedman
maßgeblichanEntschlüsselungenim AuftragderAmerikanerbeteiligt.
BeimFriedman-Testwird untersucht,mit welcherWahrscheinlichkeit zweiwillkürlich aus
einemText herausgegriffene Buchstabengleich sind. Der Koinzidenzindex gibt darauf
Antwort. Dasist dieWahrscheinlichkeit dafür, dasszweizufällig gewählteBuchstabenmit
beliebigemAbstandgleichsind.Ausgegangenwird vondemlateinischenAlphabetmit 26
Zeichen,wobeidie Häufigkeit derBuchstabenmit n1 für A, n2 für B bis n26 für Z angege-
benwird.
Die Längen desTextesergibt sichdannals
n �26
∑i � 1
ni �
8
Die GesamtanzahlallerderPaareausA‘s ist
n1 n1 � 12
�
Dennfür dieAuswahldeserstenA‘s gibt esn1 Möglichkeiten,für dieAuswahldeszweiten
nur nochn1 � 1 Möglichkeiten.
Also ergibt sichfür die GesamtzahlA allerPaare,bei dembeideBuchstabengleichsind:
A � n1 n1 � 12
� n2 n2 � 12
��������� n26 n26 � 12
� 26
∑i � 1
ni ni � 12
DieWahrscheinlichkeit I (FriedmanscherKoinzidenzindex) dafür, dasseinbeliebigesBuch-
stabenpaarauszweigleichenBuchstabenbesteht,berechnetsichdamitzu
I � ∑26i � 1 ni ni � 1
n n � 1 �
Bei langendeutschenTexten gilt I � Id� 0 � 0762,bei zufällig generiertenlangenTex-
ten mit n1� n2
� ����� � n26 ist die Wahrscheinlichkeit Ir � 126, was3,846Prozentent-
spricht.Eslässtsicherkennen,dassderWertbeideutschenTextendeutlichhöherliegt.Bei
demBeispielchiffretext ergibt sichderWert Ib� 0 � 043423.Mansieht,dassdie Verteilung
derBuchstabenim Beispielgeheimtext schonweitaus„zufälliger“ alsin durchschnittlichen
deutschenTextenist. Soist — wie bei monoalphabetischerVerschlüsselungüblich — ein
Angriff mit einerTabellewie in AnhangB nicht mehrmöglich.Die Wahrscheinlichkeit,
zweimaldenselbenBuchstabenzu ziehen,wächstmit derungleichmäßigenVerteilungder
Buchstaben.
Die Idee desFriedman-Testsist nun: Je längerdasSchlüsselwort gewählt wurde,desto
mehrentferntsichderKoinzidenzindex I weg vom Maximalwert (0,0762)hin zumMini-
malwert (0,03846).
Daesk Teiltextegibt, mit je etwan/k Buchstaben,gibt esinsgesamt
12� nk
nk� 1�� k � n n � k
2k
9
PaareausgleichenBuchstabeninnerhalbderTeiltexteund
n n � nk�� 1
2� n2 k � 1
2k
PaarevonBuchstabenausverschiedenenTeiltexten.Nunkönnenwir (beibekannterSchlüs-
sellängek) dieZahl derPaareausgleichenBuchstabenim Text angebenals
n n � k 2k
� Id � n2 k � 12k
� Ir �
Dividiert mannun durchdie Zahl der Paareingesamtn n � 1�� 2, wird die Wahrschein-
lichkeit für PaareausgleichenBuchstabengeliefert.Dieseist aberungefährgleich dem
Koinzidenzindex I, alsoschreibenwir
I � n n � k n n � 1 k � Id �
n2 k � 1n n � 1 k � Ir �
Aufgelöstnachk ergibt dasdie Formel
k � Id � Ir n n � 1 Ib � Irn � Id
�
WerdennundieobenberechnetenWerteeingesetzt,ergibt sich
k � 0 � 0762� 0 � 0385�� 267266 � 0 � 0434 � 0 � 0385 � 267 � 0 � 0762
� 7 � 5057�
Vergleicht mandiesenWert mit denÜberlegungendesKasiski-Tests,zeigt sich,dassder
Wert desBeispielsviel näheran5 alsan2 ist. Man kannalsovermuten,dassdie Schlüs-
sellängetatsächlich5 beträgt.
10
5.3. Auswer tung der kryptoanal ytisc hen Tests
Dawir dieSchlüssellängeziemlichgenaubestimmthaben,ist daskompletteEntschlüsseln
der geheimenNachrichteinfach,dennjederfünfte BuchstabedesGeheimtexteswird mit
demselbenBuchstabenverschlüsselt,d.h.mankannhierdechiffrierenwie beieinermono-
alphabetischenChiffre, wasdiesenVorgangstarkvereinfacht.Schreibenwir nun jeweils
immerdenersten,denzweitenusw. BuchstabendesGeheimtextesuntereinander. Esergibt
sichfolgendeTabelle:
1. TBTSFNPTFSUXFPANHOBTFPSSFVFTDIJFFQFDUGSOTICBJFOVEFJFBO
2. FDVRDNETUJLRDILVRJKZSSLYEECDYVIIECIFVZJZFKJQDZJJFYEZJV
3. NCVCPMLPIBMZQCAVVQBKMWVIRVBMTOVMSQBUZMQKAMQCUVKAKZIVK
4. MRAJIKIYWIGWXREKKIILVXXPSLHRMIJMSDITWAGLMVIWXQLXLWPIL
5. JIFINAWQJXPNOSRJJMSZWJJYWNFXHMZSRNSZTFMYHTIYJJRJRJXRN
Mit Hilfe der Tabelleder Häufigkeitsverteilungvon Buchstabenin deutschenTexten aus
AnhangB lässtsichderGeheimtext jetztentschlüsseln.In ZeileeinskommtF mit 12Vor-
kommnissenamhäufigstenvor, in Zeile zweiJ mit 8 Vorkommnissen,in Zeile 3 V mit 8
undM mit 7, in Zeile 4 I mit 9 und in Zeile 5 J mit 10. Man kanndavon ausgehen,dass
dieseBuchstabendemKlartext E entsprechen,daesdasim Deutschenamhäufigstenvor-
kommendeZeichenist. Gehtmannunim Vigenère-Quadratin dererstenZeilezumE, geht
dannnachuntenzumF, ergibt sichalsersterSchlüsselwortbuchstabedasB. Fährtmanso
nunfort undnimmt in derdrittenZeile denamzweithäufigstvorkommendenBuchstaben
M, ergibt sich dasSchlüsselwort BRIEF. Vollständigentschlüsseltergibt der Chiffretext
denKlartext:
SOFIEAMUNDSENWARAUFDEMHEIMWEGVONDERSCHULEDASERSTESTUECK
WARSIEMITJORUNNZUSAMMENGEGANGENSIEHATTENSICHUEBERROBOTE
RUNTERHALTENJORUNNHIELTDASMENSCHLICHEGEHIRNFUEREINENKOM
PLIZIERTENCOMPUTERSOFIEWARSICHNICHTSOSICHEROBSIEDAZUSTI
MMTEEINMENSCHMUSSTEDOCHMEHRSEINALSEINEMASCHINE,
welcherdemerstenAbsatzvon JosteinGaardersBestseller„SofiesWelt“ entspricht.
11
EineImplementierungderKryptoanalysenachKasiskiundFriedmanin derProgrammier-
sprachePASCAL findetsichim AnhangA.2.
6. Fazit
Seithundertenvon Jahrengibt esdie Notwendigkeit, InformationenundBotschaftenver-
schlüsseltund damit sichervon einemOrt zum anderenzu übermitteln.Insbesonderefür
Regierungs-undKriegsinformationenwardieswichtig.Vigenèrehatmit seinemVerschlüs-
selungskonzeptdie bislangbekanntenundpraktiziertenMethodenganzentscheidendwei-
ter entwickelt. Die FortschritteseinerTechnikbestehenunteranderemdarin,dassSender
und EmpfängerkeinekompliziertenVerschlüsselungstabellen,sondernnur dasleicht re-
konstruierbareVigenère-Quadrat,brauchten.Außerdemwar die Vigenère-Chiffre bis zur
EntwicklungderkryptoanalytischenTestsvon Kasiski (1863)undFriedman(1925)ohne
Schlüsselpraktischnichtdechiffrierbar. SiewaralsomehrerehundertJahreäußerstsicher.
SelbstheutenutzenProgrammewie Microsoft Money 98oderIntuit QuickbookseineAb-
wandlungderVigenère-Chiffre, umDateienzuverschlüsseln.
Der BedarfnachVerschlüsselungist im 20. Jahrhundert,vor allem seit der rasantenEin-
führung und NutzungdesInternets,z.B. zum Austauschvon Datenoder als Geschäfts-
plattform,erheblichgestiegen.Soverwundertesnicht,dassdieBedeutungwirksamerVer-
schlüsselungstechnikenerheblichzugenommenhat.Dennwennesnicht gelingt,Informa-
tionenoderGeschäftsvorgängeüberdasInternetsicher— dasheißtvor demunberechtigten
Zugriff durchDritte — durchzuführen,dannwird dieIdeedesInternetsunddamitdietech-
nologischeundweltwirtschaftlicheEntwicklungeinenempfindlichenRückschlagerleben.
12
A. Implementierung en in PASCAL
A.1. Die Vigenère-Chiffre
ProgrammzurVer- undEntschlüsselungnachVigenère.
program vigenere; {von Johannes Weitzel}
uses crt;
var eingabe, ausgabe, schluessel : string;
wahl : char;
function ucase (str : string) : string;
var i : integer;
begin
for i := 1 to length(str) do
str[i] := upcase(str[i]);
ucase := str;
end;
function schluesselanpassen(schluessel : string; len_eingabe, len_schluessel : integer) : string;
var i, j : integer;
zwischenschluessel : string;
begin
zwischenschluessel := ’’;
i := round(len_eingabe/len_schluessel+1);
j := 0;
repeat
zwischenschluessel := zwischenschluessel + schluessel;
inc(j);
until j >= i;
schluesselanpassen := zwischenschluessel;
end;
13
function verschluesseln(klartext, schluessel : string) : string;
var i, z : integer;
chiffretext : string;
begin
chiffretext := ’’;
for i := 1 to length(klartext) do
begin
z := Ord(klartext[i]) - Ord(’A’) + Ord(schluessel[i]) - Ord(’A’);
z := z mod 26;
z := z + Ord(’A’);
chiffretext := chiffretext + Chr(z);
end;
verschluesseln := chiffretext;
end;
function entschluesseln(chiffretext, schluessel : string) : string;
var i, z : integer;
klartext : string;
begin
klartext := ’’;
for i := 1 to length(chiffretext) do
begin
z := Ord(chiffretext[i]) + Ord(’A’) - Ord(schluessel[i]) + Ord(’A’);
z := z mod 26;
z := z + Ord(’A’);
klartext := klartext + Chr(z);
end;
entschluesseln := klartext;
end;
begin
clrscr; writeln(’Die Vigenere-Chiffre’);
Write(’Klartext bzw. Chiffretext eingeben: ’); ReadLn(eingabe);
Write(’Schluessel eingeben: ’); ReadLn(schluessel);
if length(eingabe) > length(schluessel) then
schluessel := schluesselanpassen(schluessel, length(eingabe), length(schluessel));
Write(’Verschluesseln [1] oder Entschluesseln [2] ?’);
repeat
wahl := readkey;
until wahl in [’1’, ’2’];
if wahl = ’1’ then
begin
ausgabe := verschluesseln(ucase(eingabe), ucase(schluessel));
writeln; writeln(’Chiffretext: ’ , ausgabe);
end
else
begin
ausgabe := entschluesseln(ucase(eingabe), ucase(schluessel));
writeln; writeln(’Klartext: ’ , ausgabe);
end; readln;
end.
14
A.2. Die Kryptoanal yse nach Kasiski und Friedman
ProgrammzurKryptoanalysenachKasiskiundFriedman.
program vig_anaylse; {von Johannes Weitzel}
uses crt;
const N = 160;
MAX = 10000;
I_d = 0.0762;
I_r = 0.0385;
var eingabe : string;
primzahlen : array [1..N] of integer;
Buchstabenanzahl : array [1..26] of integer;
Schluessellaenge, Koinzidenzindex : real;
function BerechneK(m : longint; Koinzidenzindex : real) : real;
begin
BerechneK := ((I_d - I_r) * m) / ((m - 1) * Koinzidenzindex - I_r * m + I_d);
end;
function BerechneI(m : longint) : real;
var i : integer;
FriedmannI : real;
begin
FriedmannI := 0;
for i := 1 to 26 do
begin
FriedmannI := FriedmannI + (Buchstabenanzahl[i] * (Buchstabenanzahl[i] - 1));
end;
FriedmannI := FriedmannI / (m * (m - 1));
BerechneI := FriedmannI;
end;
procedure ZaehleBuchstaben(str:string);
var i:integer;
begin
for i := 1 to length(str) do
inc(Buchstabenanzahl[Ord(str[i])-64]);
end;
15
procedure Faktorisierung(zahl : longint);
var i : integer;
test : boolean;
begin
i := 1;
test := true;
while test = true do
begin
while (primzahlen[i] < zahl) do
begin
if (zahl mod primzahlen[i] = 0) then
begin
zahl := zahl div primzahlen[i];
write(primzahlen[i]:8);
while (zahl mod primzahlen[i] = 0) do
begin
if (zahl = primzahlen[i]) then
break;
zahl := zahl div primzahlen[i];
write(primzahlen[i]:8);
end;
test := true;
end;
inc(i);
end;
test := false;
write(zahl:8);
end;
end;
procedure ErzeugePrimzahlen;
var a : array[1..MAX] of boolean;
i,j : longint;
begin
a[1]:=false;
for i:=1 to MAX do
a[i]:=true;
for i:=2 to MAX div 2 do
for j:=2 to MAX div i do
a[i*j]:=false;
j := 0;
for i:=2 to MAX do
begin
if a[i] = true then
begin
inc(j);
primzahlen[j] := i;
end;
if j >= N then break;
end;
end;
16
procedure analyse (str : string);
var i, j : integer;
such_str, vergleich_str : string;
pos_such_str, pos_vergleich_str, abstand : integer;
loesche_anfang : string;
backup_str: string;
begin
for i := 1 to (length(str)-3) do
begin
such_str := copy(str,i,3);
for j := i+1 to (length(str)-3) do
begin
vergleich_str := copy(str,j,3);
if vergleich_str = such_str then
begin
backup_str := str;
pos_such_str := pos(such_str,str);
loesche_anfang := copy(str,1,pos_such_str+2);
delete(str,1,pos_such_str+2);
pos_vergleich_str := pos(vergleich_str,str) + length(loesche_anfang);
abstand := pos_vergleich_Str - pos_such_str;
write(such_str);
write(’, Abstand: ’); write(abstand:4, ’, Faktoren: ’);
faktorisierung(abstand); writeln;
str := backup_str;
end;
end;
end;
end;
begin
clrscr;
writeln(’Programm zur Kryptoanalyse einer Vigenere-Chiffre’);
write(’Chiffretext eingeben (in Grossbuchstaben): ’);
readln(eingabe);
ZaehleBuchstaben(eingabe);
Koinzidenzindex := BerechneI(length(eingabe));
Schluessellaenge := BerechneK(length(eingabe),Koinzidenzindex);
writeln; writeln(’Friedman-Test’); writeln(’------------’);
writeln(’Koinzidenzindex I: ’ , Koinzidenzindex:3:6);
writeln(’Schluessellaenge k: ’ ,Schluessellaenge:3:6);
erzeugeprimzahlen;
writeln; writeln(’Kasiski-Test’); writeln(’------------’);
analyse(eingabe);
readln;
end.
17
A.3. Vigenère-GUI
Diesesin Delphi geschriebeneProgrammverbindetdie AlgorithmenausAnhangA.1 und
A.2 zu einerleicht bedienbarengrafischenOberfläche.Der Quellcode,derdenenausAn-
hangA.1 und A.2 sehrähnlich ist, befindetsich nebender ausführbarenDatei auf der
beigelegtenCD-ROM.
B. Häufigkeiten der Buc hstaben der deutsc hen
Sprac he
Buchstabe Häufigkeit (in %) Buchstabe Häufigkeit (in %)
a 6,51 n 9,78
b 1,89 o 2,51
c 3,06 p 0,79
d 5,08 q 0,02
e 17,40 r 7,00
f 1,66 s 7,27
g 3,01 t 6,15
h 4,76 u 4,35
i 7,55 v 0,67
j 0,27 w 1,89
k 1,21 x 0,03
l 3,44 y 0,04
m 2,53 z 1,13
18
Literatur
[1] Buchmann,Johannes. Einführungin die Kryptographie. Springer-VerlagBerlin Hei-
delberg 1999
[2] Ertel, Wolfgang. AngewandteKryptographie. FachbuchverlagLeipzig im CarlHanser
Verlag,MünchenWien 2001.
[3] Kippenhahn, Rudolf. VerschlüsselteBotschaften—Geheimschrift, EnigmaundChip-
karte. Rowohlt TaschenbuchVerlagGmbH,ReinbekbeiHamburg 1999
[4] Kuhlmann, Gregor. ProgrammierspracheTURBO-PASCAL—EinestrukturierteEin-
führung. Rowohlt TaschenbuchVerlagGmbH,ReinbekbeiHamburg 1987
[5] Kuhlmann, Gregor. Programmiersprache TURBO-PASCALfür Fortgeschrittene—
EinestrukturierteEinführung. Rowohlt TaschenbuchVerlagGmbH,ReinbekbeiHam-
burg 1988
[6] PC Magazin Spezial5/98. KryptographieundNetzwerksicherheit.
[7] Schneier, Bruce. AngewandteKryptographie:Protokolle, AlgorithmenundSourceco-
dein C. Addison-Wesley (Deutschland)GmbH,Bonn1996.
[8] Schüler DUDEN Mathematik I . BibliographischesInstitut F.A. BrockhausAG,
Mannheim1990
[9] Selke,Gisbert W.. Kryptographie—Verfahren,Ziele, Einsatzmöglichkeiten. O’Reilly
Verlag,Köln 2000
[10] http://raphael.math.uic.edu/~jeremy/crypt/contrib/deepak.html
(Entnahmedatum1.3.2002)
19
Recommended