Dieses Projekt ist das Thema ("Kryptanalyse der doppelten Spaltentranspositionschiffre") meiner Masterarbeit -- die Abschlussarbeit kann hier geladen werden.

Einleitung

Kryptologie, also die Verschlüsselung von Nachrichten, ist in der heutigen Zeit ein elementarer Bestandteil unseres Alltags geworden. Weder im öffentlichen noch im privaten Bereich kann auf die Anwendung kryptologischer Verfahren verzichten werden und sie spielen auch für das Militär eine wichtige Rolle.

Während heutzutage fast ausschließlich rechnergestützt gearbeitet wird, musste in den Jahrhunderten vor Entwicklung elektronischer Datenverarbeitung auf einfachere Verfahren zurückgegriffen werden. Eine wichtige Anwendung der Verschlüsselungstechnik im 19. und frühen 20. Jahrhundert war dabei der sogenannte Doppelwürfel (Übchi); ein Verfahren mit einer zweifach angewendeten Spaltentransposition. Dieses Verfahren ist von Hand durchführbar und bis heute ist kein Ciphertext-only Angriff bekannt geworden.

In dieser Arbeit wird erstmals eine lineare Kryptanalyse auf das Verfahren durchgeführt. Aus diesen Erkenntnissen wird eine Anwendung implementiert, die einen automatisierten Known-Plaintext Angriff auf die Verschlüsselung ermöglicht. So lässt sich bereits mit einem Bruchteil des Klartextes der Schlüssel zurückrechnen. Eigenschaften, die der Chiffre ursprünglich ihre Sicherheit garantieren sollten, werden hier ausgenutzt um das Verfahren zu brechen.

Verschlüsselung

Die Funktionsweise der Verschlüsselung wird nun an einem Beispiel demonstriert. Zunächst benötigen wir einen Klartext, der verschlüsselt werden soll. Der Klartext lautet an dieser Stelle:
HALLODASHIERISTEINLANGERBEISPIELTEXTUMDASVERFAHRENZUZEIGEN
Ebenso werden zwei Schlüssel benötigt. Als ersten Schlüssel verwenden wir NOTEBOOK, dessen Länge 8 beträgt. Nun wird der Klartext zeilenweise in ein Rechteck eingetragen, dessen Breite von der Länge des angewendeten Schlüssels bestimmt wird. Die Höhe des Würfels (also die vertikale Seitenlänge) ist abhängig von der Länge des verwendeten Textes.

Wie zu sehen, ist die letzte Zeile nicht vollständig gefüllt. Dies ist nur dann der Fall, wenn die Schlüssellänge ein ganzzahliger Teiler der Klartextlänge ist. Anschließend wird der Schlüssel der Chiffre alphabetisch sortiert. Es muss sich dabei um eine stabile Sortierung handeln, was bedeutet, dass die Reihenfolge der Spalten bewahrt wird, sofern dessen Schlüsselzeichen identisch sind. Es werden allerdings dabei nicht nur die Schlüsselzeichen vertauscht, sondern auch die darunterliegende Spalte. Dieser Eigenschaft verdankt die Spaltentranspositionschiffre ihren Namen.

Wie zu erkennen, hat sich die Position der Lücken verändert - dies kann allerdings ignoriert werden. Andernfalls wäre das Auffüllen mit Füllzeichen möglich, die nicht im Klartextalphabet enthalten sind, wobei diese am Ende auch wieder entfernt werden können. Essentiell für den Doppelwürfel und der nächste Schritt, ist das spaltenweise Auslesen der entstandenen Matrix. Das Ergebnis wird also nicht in Lesereihenfolge entnommen, sondern spaltenweise.

Hierbei werden die resultierenden Zeichen (falls noch nicht geschehen) in Großbuchstaben verwandelt und in 5er-Blöcke gruppiert. Dies soll die Lesbarkeit der Chiffrierten Nachricht erhöhen. Ebenfalls werden die entstandenen Lücken der letzten Zeile nicht berücksichtigt: OINPU FZLRA STRUS ERLAR GHHIB TSEEA INEEV NNDSG IMAEA TEEDH ILELI XEZ Zusammenfassend wurden der Klartext eingetragen, die Spalten in Abhängigkeit eines Schlüssels vertauscht und das Ergebis spaltenweise ausgelesen. Um die Sicherheit der Chiffre zu verstärken, muss dieser Vorgang - unter Verwendung eines zweiten unabhängigen Schlüssels - erneut durchgeführt werden. In diesem Beispiel verwenden wird den Schlüssel DECKEL und es ergibt sich ein neues Rechteck der Breite 6. Der Klartext der zweiten Runde, ist der Chiffretext der ersten und dieser wird zeilenweise in den Würfel eingetragen. Anschließend wird erneut die Spaltentransposition durchgeführt, wie sie bereits für die vorherige Runde beschrieben wurde.

Nachdem der Würfel spaltenweise permutiert wurde, kann man das Ergebnis der zweiten Runde auslesen. Wie zuvor wird erneut spaltenweise vorgegangen, um den resultierenden Chiffretext zu gewinnen.

Der Klartext wurde nun erfolgreich in den Chiffretext NRSGS ESAIE OZRAB INADI ILURT NDEHX USRHE VIEEP AEHEE GTLZF TLIAN MEL verschlüsselt und kann übermittelt werden.

Entschlüsselung

Nun soll der entstandene Chiffretext wieder entschlüsselt, also in den Klartext verwandelt werden. Dabei werden die Schritte der Verschlüsselung rückwärts ausgeführt. Während der Durchführung der Verschlüsslung wurde gezeigt, dass in der letzten Zeile der Matrix Lücken entstehen bzw. die Matrix nicht vollständig gefüllt ist. Aufgrund der daraus resultierenden Verschiebung gestaltet sich der Vorgang der Entschlüsselung etwas weniger intuitiv, ist jedoch trotzdem verlustfrei durchführbar. So muss zunächst ein leerer Würfel der zweiten Runde aufgestellt werden, wobei die nicht verwendeten Stellen der letzten Zeile (der Rest) unkenntlich gemacht werden müssen:

Nun kann der Chiffretext spaltenweise in die Matrix eingetragen werden. Die Reihenfolge der Eintragung entspricht der Reihenfolge der Schlüsselzeichen im Alphabet. Das Entschlüsselungsergebnis der ersten Runde ist das zeilenweise Auslesen des entstandenen Würfels.

Analog kann dieser Vorgang für die zweite Entschlüsselungsrunde mit dem ersten Schlüssel der Verschlüsselung durchgeführt werden. Wichtig ist hierbei erneut, dass die Spalten mit Überlänge bzw. die Spalten mit fehlenden Feldern in der letzten Zeile beachtet werden. Als Resultat kann der Klartext nun wieder zeilenweise aus dem Würfel entnommen und gelesen werden.

Software zur Kryptanalyse

Mit dieser Anwendung kann ein Known-Plaintext Angriff auf die Verschlüsselung gefahren werden. Mit bekanntem Klar/Chiffretextpaar sollen die zwei Permutationen ausgerechnet werden. In vielen Fällen genügt bereits ein Teil des Klartextes um ein eindeutiges Ergebnis zu erhalten.

Hier geht's zum Applet
Hinweis: Da der Zugriff auf die Zwischenablage bei unsignierten Applets nicht funktioniert, wurde das Programm mit diesem Zertifikat unterschrieben (SHA1: c46b6c1d2b9cc573c18b50a4a257e38b4a340751) und muss (abhängig von den Sicherheitseinstellungen) vorher installiert werden. Alternativ kann das Programm hier heruntergeladen und ausgeführt werden. Seit den letzten Java-Versionen funktioniert ein Applet ohne gültige Signatur nicht mehr; herunterladen und ausführen funktioniert natürlich weiterhin.

Beispiele

Die Klar- und Chiffretextpaare können nun in das Programm kopiert werden. Anschließend wird die Schlüssellänge über die zwei Slider festgelegt. Alternativ kann auch die passende Schlüssellänge automatisch gesucht werden - führt jedoch zu einer Erhöhung der Laufzeit.

Klartext

HALLODASHIERISTEINLANGERBEISPIELTEXTUMDASVERFAHRENZUZEIGEN

Chiffretext

NRSGSESAIEOZRABINADIILURTNDEHXUSRHEVIEEPAEHEEGTLZFTLIANMEL

Schlüssel

Schlüssel1 (8): NOTEBOOK (4 5 8 2 1 6 7 3)
Schlüssel2 (6): DECKEL (2 3 1 5 4 6)

Klartext

Fest gemauert in der Erden Steht die Form, aus Lehm gebrannt. Heute muß die Glocke werden, Frisch, Gesellen! seid zur Hand. Von der Stirne heiß Rinnen muß der Schweiß, Soll das Werk den Meister loben, Doch der Segen kommt von oben. Zum Werke, das wir ernst bereiten, Geziemt sich wohl ein ernstes Wort; Wenn gute Reden sie begleiten, Dann fließt die Arbeit munter fort. So laßt uns jetzt mit Fleiß betrachten, Was durch die schwache Kraft entspringt, Den schlechten Mann muß man verachten, Der nie bedacht, was er vollbringt. Das ist ja, was den Menschen zieret Und dazu ward ihm der Verstand, Daß er im innern Herzen spüret, Was er erschafft mit seiner Hand. Nehmet Holz vom Fichtenstamme, Doch recht trocken laßt es sein, Daß die eingepreßte Flamme Schlage zu dem Schwalch hinein. Kocht des Kupfers Brei, Schnell das Zinn herbei, Daß die zähe Glockenspeise Fließe nach der rechten Weise. Was in des Dammes tiefer Grube Die Hand mit Feuers Hilfe baut, Hoch auf des Turmes Glockenstube Da wird es von uns zeugen laut. Noch dauern wirds in späten Tagen Und rühren vieler Menschen Ohr, Und wird mit dem Betrübten klagen, Und stimmen zu der Andacht Chor. Was unten tief dem Erdensohne Das wechselnde Verhängnis bringt, Das schlägt an die metallne Krone, Die es erbaulich weiter klingt.

Chiffretext

eRnhrsFn F icae utensamneu.eß erac s S it   n en,,ghheEi   et ftleh  s rhdeeml.ieFkbMncn  ueeßnza ceeDnüeselueA ciiebe bia. eitrrnhnelr nmdmh n  metse e ent  fs,greovd ldndn o.Bf  iWngtc,itcr .HnH lesmsmsftosriwehu e  edaesg emur  a rSlRcreinE o seter  s himWds r  rSine  imze ew s,ms masLt apdegebelcWwe ea,etsl ühed rseDi ße e cde,eoth dths utrh,ad ebfa hfdVgo r,cen nDtnehrrnH eern vsmei fKa gd uaitmsDiknct icakorsrprrä  .eHe  t,Zßbeibrehkj oeodledt vdaBKrra e l,bHihe acUu ecM,Do a   e ett  i ihh etti Uccrdiew d ssA. osalp nsi ed lsC nrKieezor Wn ßhl ehegnieotrßgDDped o ea h sDmelneaeäsrdgnHldpasin  umThhra rm nnrnihaarrrto ,r ueg.cd  hbnn Seef HrnugtbtonMtGmr,esFnswo rarHU e.ll rewdl it   rnr uneStmeFm im u m,eeDllcensa ioauer! l,hn eDis ssrmledtb tbeasattnDßknldnnccdn cdedeteDnerhidee rghhczaevdtdotV  auei jiieb,lwt FZdüeenßanerk zbtemi eeneeso ediVGWnr uiwoea ezbmeSsh ooi licdnkkdeni w tsncgenrhißeruus eDananSe  ßWem  ctrlwukrtretG z n e nne telhußioatne  si hm tf , g ametd neWn ;rser.edcWnaerN e tnße uetanc a rneeene  in lnetSiUecvoaeuehlo fwnKuOhebS nsinan alNe iisest h ta ,tazlhmeG zs     nrFacnst  ee t Tniuernm,Gnr.,,hhisshnzszcäemißeaw e hirtpriett erseddunrwntdnccid,uearnade dliFewdd stnmasoiWienes h,ne rgst aMtue Dnem nve t dn ße cGhä hiDeie ilt  i e c

Schlüssel

Schlüssel1 (13): DASISTEINTEST (2 1 8 5 9 11 3 6 7 12 4 10 13)
Schlüssel2 (11): AUCHDASHIER (1 11 3 6 4 2 10 7 8 5 9)

Hinweis: Der erste Satz des Klartextes genügt um in ca. 1 Minute ein eindeutiges Ergebnis zu bekommen. Mit nur den ersten fünf Wörtern wird der Schlüssel in ca. 20 Minuten wiederhergestellt.

Klartext

ZUMKAMPFDERWAGENUNDGESAENGEDERAUFKORINTHUSLANDESENGEDERGRIECHENSTAEMMEFROHVEREINTZOGIBYKUSDERGOETTERFREUNDIHMSCHENKTEDESGESANGESGABEDERLIEDERSUESSENMUNDAPOLLSOWANDERTERANLEICHTEMSTABEAUSRHEGIUMDESGOTTESVOLLSCHONWINKTAUFHOHEMBERGESRUECKENAKROKORINTHDESWANDRERSBLICKENUNDINPOSEIDONSFICHTENHAINTRITTERMITFROMMENSCHAUDEREINNICHTSREGTSICHUMIHNHERNURSCHWAERMEVONKRANICHENBEGLEITENIHNDIEFERNHINNACHDESSUEDENSWAEREINGRAULICHTEMGESCHWADERZIEHNSEIDMIRGEGRUESSTBEFREUNDETESCHARENDIEMIRZURSEEBEGLEITERWARENZUMGUTENZEICHENNEHMICHEUCHMEINLOSESISTDEMEURENGLEICH

Chiffretext

AEGOMEEKHTGNEEGHOMRBKELTSOHTBCHOBNERHEMESYHIUEDRMUCEHHEIEDRGODNRCTRMNCEDINLUECSSLLETANGREKEHIEGIETRRNFOCSIEWEUAHARUNSRDEZNHNARBSNNCUNDTTHBISUIDINNSOEISHEIHARTRLTEROAINRZKKRHESLGNDLNIRTRMADEZEMRNDERMADRUHTUDDEESIEDIEGIICNARGHEANDSSVOZNKSNRISNDHGVZHTEEWSICDPABTHAINNCSNHETEREZNMKRIDIUIAKMLRUESSERRGHSENTTWTEEESKHTMGUNIEHERRRIHSLCWEEWSSNLETEOEEMIORUIOHNNDDOATNENLRNAPDOBEEHUECNLIUIAAEROSERGUIMEWEINCWFNEETTNTIUEUEUSEEEEMNDENNSMCFESNSOFMUAEDMSAHEIISEAGIDPGFESCGEHRREIKSIEUDEGGASLOEMUFATNNERIRSGECESGECTMSECAUEIGEGHRTEHNNFFUEEEAWCEEDCMUNFBRMARSEEVNEHE

Schlüssel

Schlüssel1 (21): (19 1 11 6 4 14 7 12 15 8 16 20 2 9 13 5 17 18 21 10 3)
Schlüssel2 (20): (16 1 5 10 2 6 17 11 7 18 12 3 8 13 4 19 14 9 20 15)

Hinweis: Die Laufzeit beträgt bei vollem Klartext ca. 30 Sekunden und bei der Hälfte des Klartextes ca. 2 Minuten. Mit einem Fünftel des Klartextes wird der Schlüssel in ca. 30 Minuten berechnet.

Weitere können über das Cryptool erstellt und getestet werden. Aus Kompatibilitätsgründen wird empfohlen, die Zeilenumbrüche vor der Verschlüsselung zu entfernen.

Quelltext

Der Sourcecode der Anwendung kann hier heruntergeladen werden und steht unter GNU GPLv2.