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