Brechen von Spaltentausch-Chiffren mit längeren Schlüsseln
Angenommen, man fängt mehrere Funksprüche ab, deren Chiffrate jeweils 800 Zeichen haben, nur er letzte Funkspruch weicht davon ab und hat weniger Zeichen, weil es sich wohl um den Rest handelt. Eine Prüfung der Art der Chiffre hat ergeben, dass das Chiffrat den selben Koinzidenzindex wie die deutsche Sprache hat. Es handelt sich also um eine Transposition.Dann kann man davon ausgehen, dass Formblätter oder Karopapiere benutzt werden, um sehr lange Texte mit Spaltentausch-Verschlüsselung zu verschlüsseln und jeweils 800 Zeichen pro Blatt kodiert werden. Ein längerer Schlüssel würde das Verfahren sicherer machen, außerdem würden man mit sehr viel Platz verschwenden, wenn man nur wenig Spalten verwenden würde, denn es würden dann sehr viele Zeilen werden. Es ist also von einer größeren Anzahl von Zeilen auszugehen. Es wäre allerdings auch möglich dass mehrere Kolonnen nebeneinanderstünden, die jeweils mit demselben kurzen Schlüssel verschlüsselt wären. Das würde aber die Sicherheit unnötig mindern und die Verschlüsselungsarbeit wäre die gleiche.
Bei langen Schlüsseln müssten wir lange Zeichenketten anagrammieren. Bei Anwendung des üblichen Verfahrens wären wir bei langen Anagrammen zunehmend überfordert. Dann empfiehlt es sich, nach wahrscheinlichen Bigramm-Kontakten zu fahnden, um zusammenpassende Spalte zu finden.
Dies wollen wir an dem nachfolgenden Beispiel durchspielen. Gegeben sei der erste Funkspruch mit 800 Zeichen:
ZNAOW URIRN EDELC DEANI SIENE EEEUA REEUE TNEWS NADUD ESNIH SIRAE ESHNO EWUCS HEENA EANWN EENWS FEARU SESTL HESTW DNEJF EFEAU CNDEE SHEHS SNLCM BSNWC MHETL AHAHO EHMEF NUEUE EECEO NMDKM SUDUA NSENE ORNSC ITNWT REUID SNSKH ANLDR DEAEU OULOE CAEFN DABNS DMALK NURUN CERLI SHEGW AODSW MERSG SLSNE ERNCD ULNEN HEIDE HEHNE RSNCR CNSEE AKCET SHSSE WAGIF RURUL NESER NSECD CAOEH ESOSI RSEAH TRUES GRCEH SBNLS LUEST EUKAI TMAHA RNAAU LMARH EEGRG BMSIR EHACS SDLUE NAEEL GSIMT EENNU AOTUE NSREB HAEEI NRDNR SIENC SNRGC RWUEA RZDDT ATLIU NCUIN TFKLE NLCTC RHRRA SEUIE SGKRI LNEEE DKNBA MTNHS LNDIH EEEOE URENE WDOOL DMEED ENUTR LINWC SBEER UHARE USTNN DRLEN FUESZ NHMZD RUMAE NIGAD ANCEC ERKEU ENSHA ESMGT ETNNU DNELE EIECE NEDBH RCDVD NWTES NINES HRECO KNEON NTBRE TNEEA RLCEI EEISU EFSAE EANLE ANNHS HLEAU ERBEA SMRIM ZEDEH TIRNE ELSES RSCST APPRW GFRAI NHNTE NEITO DHSHD KLWEE HIEST SALIR EWEEA EAITF SDEIS USRTP KHCDS RAEIE GFCRC GNULO HANHD LULSD WDASS EERGL TOHNN
Fragen wir uns zuerst: "Welche Rechtecke mit welchen Kantenlängen kommen denn nun für 800 Zeichen in Frage?" Dazu errechnen wir uns die Primfaktoren von 800:
800 hat die Primfaktoren: 2 2 2 2 2 5 5
Produkte aus diesen Faktoren und damit mögliche Schlüssellängen sind:
2 2
4 2*2
5 5
8 2*2*2
10 5*2
16 2*2*2*2
20 5*2*2
25 5*5
32 2*2*2*2*2
40 5*2*2*2
50 5*5*2
80 5*2*2*2*2
100 5*5*2*2
160 5*2*2*2*2*2
200 5*5*2*2*2
400 5*5*2*2*2*2
2 wäre als Schlüssellänge viel zu kurz. Und alles über 100 unhandlich, selbst mit Papier im Querformat. Beginnen wir also mit 4 und schreiben den Geheimtext in 4 Spalten
ZCNR
NASC
AERD
OFEV
WNBD
UDHN
RAAW
IBET
RNEE
NSIS
... (gesamt 200 Zeilen)
Bei diesen kurzen Schlüsseln fällt das Anagrammieren noch leicht. Man sieht aber schenll: es ist kein also sinnvoller Anfang zu bilden. Versuchen wir also Schlüssellänge 5
ZNTME
NSRTE
AEUNI
ONEHS
WESSU
UOGLE
RRRNF
INCDS
RSEIA
NCHHE
... (gesamt 160 Zeilen)
Auch hier ist das Anagrammieren noch einfach. Wir werden auch hier keinen sinnvollen Beginn bilden können, mit dem wir in der 2. Zeile weiterlesen könnten. Überpringen wir einige Längen (von denen wir mit der nachfolgenden Methode feststellen werden, dass sie nicht in Frage kommen) und kommen gleich zur Länge 25
1234567890abcdefghijklmno
ZESNTNAIEITALILMUZSEERIWR
NUHELSESIFRAGEETTNMSEINEC
AEEJAEUHDRUUSNNNRHGNIMHEG
OTEFHNOEEUELICLHLMTISZNAN
WNNEAEUGHRSMMSCSIZENUETEU
UEAFHOLWEUGATNTLNDTEEDEAL
RWEEOROAHLRRERCNWRNSFENIO
ISAAENEONNCHEGRDCUNHSHETH
RNNUHSCDEEEENCHISMURATIFA
NAWCMCASRSHENRRHBADEEITSN
EDNNEIEWSESGUWREEENCERODH
DUEDFTFMNRBRAUAEENEOANDED
EDEENNNECNNGOESERILKNEHIL
LENEUWDRRSLBTAEOUGENLESSU
CSWSETASCESMURUEHAEEELHUL
DNSHURBGNCLSEZIUADIOASDSS
EIFEEENSSDUINDERRAENNEKRD
AHEHEUSLECERSDSEENCNNSLTW
NSASEIDSEASERTGNUCETHRWPD
IIRSCDMNAOTHEAKESENBSSEKA
SRUNESAEKEEABTRWTCERHCEHS
IASLONLECHUCHLIDNEDELSHCS
EEECNSKREEKSAILONRBTETIDE
NESMMKNNTSASEUNODKHNAAESE
ESTBDHUCSOIDENELREREUPSRR
EHLSKARDHSTLICEDLUCEEPTAG
ENHNMNUUSIMUNUEMEEDARRSEL
EOEWSLNLSRAERIDENNVRBWAIT
UESCUDCNESHNDNKEFSDLEGLEO
AWTMDREEWEAANTNDUHNCAFIGH
RUWHUDRNAARERFBEEAWESRRFN
ECDEAELHGHNESKANSETIMAECN
Hier fällt es schon viel schwieriger, Anagramme zu bilden und diese auf Plausibilität zu überprüfen, denn es gibt nicht wenige Kombinationsmöglichkeiten und es werden immer mehr mit zunehmender Schlüssellänge. Darum wollen wir nun nach wahrscheinlichen Bigramm-Kontakten fahnden, um zusammenpassende Spalten zu finden.Die Idee dahinter ist, dass ein Buchstabenpaar (Bigramm) eine gewisse Häufigkeit in der Sprache hat. Ein Blick auf die Häufigkeitsverteilung ergibt, dass die Bigramme 'en' und 'er' mit jeweils ca. 400 Vorkommen pro 10000 wesentlich häufiger (mehr als 100 mal so oft) vorkommen wie 'az', 'km' oder 'ph'. Da ja die Buchstaben bei einer Transposition die selben geblieben sind, gilt hier immer noch dieselbe statistische Verteilung.
Zuerst suchen wir uns eine Spalte aus, die uns augfrund der vielen häufigen Buchstaben darin besonders kontaktfreudig vorkommt. Dazu führen wir den entsprechenden Test durch.
Kontaktfreudigkeit für Spalte 1: 29777
Kontaktfreudigkeit für Spalte 2: 27590
Kontaktfreudigkeit für Spalte 3: 28640
Kontaktfreudigkeit für Spalte 4: 24782
Kontaktfreudigkeit für Spalte 5: 23882
Kontaktfreudigkeit für Spalte 6: 25125
Kontaktfreudigkeit für Spalte 7: 21300
Kontaktfreudigkeit für Spalte 8: 24249
Kontaktfreudigkeit für Spalte 9: 28344
Kontaktfreudigkeit für Spalte 10: 25913
Kontaktfreudigkeit für Spalte 11: 22844
Kontaktfreudigkeit für Spalte 12: 24522
Kontaktfreudigkeit für Spalte 13: 27037
Kontaktfreudigkeit für Spalte 14: 20168
Kontaktfreudigkeit für Spalte 15: 24980
Kontaktfreudigkeit für Spalte 16: 27995
Kontaktfreudigkeit für Spalte 17: 24682
Kontaktfreudigkeit für Spalte 18: 24510
Kontaktfreudigkeit für Spalte 19: 26064
Kontaktfreudigkeit für Spalte 20: 29109
Kontaktfreudigkeit für Spalte 21: 29587
Kontaktfreudigkeit für Spalte 22: 23195
Kontaktfreudigkeit für Spalte 23: 26132
Kontaktfreudigkeit für Spalte 24: 24011
Kontaktfreudigkeit für Spalte 25: 19875
Am kontaktfreudigsten ist Spalte 1 mit 29777
Als Sieger geht Spalte 1 mit dem höchsten Wert hervor (29777) und ist damit am geeignetes für eine Bigramm-Paarung. Knapp dahinter folgt Spalte 21 (29587).Das besonders kontaktfreudige Spalten nicht auch unbedingt gut zusammen auf Bigramm-Basis passen müssen, wollen wir untersuchen, indem wir die Affinität der Spalten im Bezug auf Bigramme zueinander berechnen. Dabei geht es nicht mehr um Häufigkeiten von Einzelbuchstaben, sondern von Buchstabenpaaren (Bigrammen). Wir stellen also eine Spalte rechts neben eine andere und bilden pro Zeile ein Bigramm-Paar über die Spalten. Die korrespondierenden Bigramm-Häufigkeiten der deutschen Sprache addieren wir dann, und an der Summe können wir dann ablesen wie affin die Spalten zueinander sind - man kann sich das als eine Art Anziehungskraft vorstellen.
Wir stellen also die 1. Spalte und die 21. Spalte probeweise nebeneinander (bringen sie in 'Kontakt') und erhalten so eine ganze Reihe von Bigrammen, für jede Zeile eines. Für diese Bigramme schlagen wir die Häufigkeiten nach und multiplizieren sie (solange sie nicht 0 sind).
Bigramme über 1. und 21. Spalte und Häufigkeiten in %%
ZE 28
NE 122
AI 5
OS 19
WU 9
UE 78
RF 18
IS 79
RA 80
NE 122
EE 23
DA 54
EN 400
LL 42
CE 1
DA 54
EN 400
AN 102
NH 17
IS 79
SH 9
IL 25
EE 23
NA 68
EU 36
EE 23
ER 409
EB 45
UE 78
AA 8
RS 54
EM 55
Produkt: 1,94 E+051
Die Affinität für "ZENEAIOSWUUERFISRANEEEDAEAber testen wir auch die andere Spalten gegen Spalte 9:
1 + 2: 4,60 E+044
1 + 3: 1,78 E+044
1 + 4: 8,52 E+042
1 + 5: 2,14 E+044
1 + 6: 1,35 E+047
1 + 7: 2,58 E+047
1 + 8: 1,24 E+047
1 + 9: 4,47 E+046
1 + 10: 5,71 E+045
1 + 11: 1,20 E+045
1 + 12: 2,39 E+046
1 + 13: 4,08 E+048
1 + 14: 7,97 E+045
1 + 15: 3,55 E+043
1 + 16: 3,46 E+045
1 + 17: 7,49 E+060 <<< (Kontaktfreude Sp. 17: 24682)
1 + 18: 8,02 E+043
1 + 19: 7,44 E+050
1 + 20: 3,59 E+045
1 + 21: 1,94 E+051 siehe Beispiel oben (Kontaktfreude Sp. 21: 29587)
1 + 22: 8,53 E+044
1 + 23: 1,13 E+049
1 + 24: 2,57 E+049
1 + 25: 2,96 E+044
Am besten rechts an die Spalte 1 passt die Spalte 17
Spalte 17 besitzt also (mit Abstand) eine höherere Affinität als Spalte 21, an Spalte 1 rechts "anzudocken", um Bigramme zu bilden. Was beweist, dass nicht automatisch die kontaktfreudigsten Spalten am besten zueinander passen, sondern sich eine weitergehende Bigramm-Untersuchung lohnt. Eine 100%ige Gewissheit, dass die Spalten zusammenpassen hat man natürlich nicht, aber wenn man das Verfahren für die weiteren Spalten weiterführt, sollte eine annähernde Reihenfolge der Buchstaben als Grundlage für die weitere Analyse herauskommen. Probieren wir es aus:
Reihenfolge: 1, 17
Was passt nun gut rechts an Spalte 17?
17 + 1: 8,59 E+040
17 + 2: 1,02 E+049
17 + 3: 3,41 E+046
17 + 4: 2,44 E+045
17 + 5: 3,18 E+041
17 + 6: 3,70 E+044
17 + 7: 5,18 E+040
17 + 8: 6,76 E+043
17 + 9: 4,28 E+043
17 + 10: 1,38 E+042
17 + 11: 3,32 E+045
17 + 12: 2,31 E+048
17 + 13: 1,52 E+048
17 + 14: 1,66 E+039
17 + 15: 1,52 E+045
17 + 16: 1,23 E+041
17 + 18: 2,99 E+039
17 + 19: 5,73 E+043
17 + 20: 1,07 E+048
17 + 21: 2,99 E+046
17 + 22: 2,57 E+053 <<<
17 + 23: 2,33 E+042
17 + 24: 1,63 E+044
17 + 25: 1,05 E+042
Am besten rechts an die Spalte 17 passt die Spalte 22.
Reihenfolge: 1, 17, 22
Doch weiter...
22 + 1: 9,09 E+047
22 + 2: 3,55 E+043
22 + 3: 1,36 E+045
22 + 4: 1,09 E+034
22 + 5: 6,43 E+039
22 + 6: 3,69 E+042
22 + 7: 9,65 E+040
22 + 8: 1,56 E+041
22 + 9: 8,30 E+045
22 + 10: 3,43 E+047
22 + 11: 7,85 E+042
22 + 12: 3,30 E+045
22 + 13: 4,28 E+042
22 + 14: 4,35 E+036
22 + 15: 8,21 E+038
22 + 16: 1,55 E+044
22 + 17: 6,08 E+041
22 + 18: 1,72 E+040
22 + 19: 7,66 E+040
22 + 20: 1,62 E+045
22 + 21: 2,59 E+050 <
22 + 23: 3,58 E+044
22 + 24: 3,21 E+052 <<<
22 + 25: 3,16 E+040
Am besten rechts an die Spalte 22 passt die Spalte 24.Reihenfolge: 1, 17, 22, 24
24 + 1: 3,35 E+042
24 + 2: 6,36 E+042
24 + 3: 2,12 E+043
24 + 4: 1,07 E+036
24 + 5: 1,69 E+042
24 + 6: 1,97 E+038
24 + 7: 3,17 E+040
24 + 8: 3,81 E+041
24 + 9: 2,47 E+045
24 + 10: 1,68 E+058 <<<
24 + 11: 1,27 E+041
24 + 12: 2,11 E+045
24 + 13: 2,99 E+044
24 + 14: 1,60 E+043
24 + 15: 1,41 E+037
24 + 16: 1,50 E+044
24 + 17: 1,38 E+040
24 + 18: 4,64 E+037
24 + 19: 2,73 E+037
24 + 20: 4,84 E+039
24 + 21: 3,39 E+044
24 + 22: 4,03 E+039
24 + 23: 1,95 E+049 <
24 + 25: 4,77 E+038
Am besten rechts an die Spalte 24 passt die Spalte 10.
Reihenfolge: 1, 17, 22, 24, 10
Wenn wir das Spielchen stur weiterführen führt das zu der kompletten Reihenfolge:
Reihenfolge: 1, 17, 22, 24, 10, 4, 11, 20, 25, 3, 18, 21, 14, 5, 12, 13, 19, 2, 8, 6, 16, 7, 15, 9, 23
1 g l n 0 4 a j o 3 h k d 5 b c i 2 8 6 f 7 e 9 m
Wenn wir die Spalten nach der Reihenfolge umstellen, ergibt sich die statistisch wahrscheinlichste Kombination aufgrund der Bigrammhäufigkeit. Übrigens eine Kombination aus 15.5 Quadrillionen. Vielleicht werden wir schon einzelne Wörter erkennen können und müssen nur noch ein paar Spalten umstellen. Und höchstwahrscheinlich wird die Spalte. an dem der Klartext beginnt, nicht am Anfang, sondern irgendwo mittendrin sein. Das bedeuted aber nur, dass wir einen Block von Spalten von vorne nach hinten verschieben müssen.
1 2 3 4 5 6 7 8 9 0 a b c d e f g h i j k l m n o 1 g l n 0 4 a j o 3 h k d 5 b c i 2 8 6 f 7 e 9 m
Z E S N T N A I E I T A L I L M U Z S E E R I W R Z U R W I N T E R S Z E I T A L S E I N M A L E I
N U H E L S E S I F R A G E E T T N M S E I N E C N T I E F E R S C H N E E L A G M U S S T E E I N
A E E J A E U H D R U U S N N N R H G N I M H E G A R M E R J U N G E H I N A U S G E H E N U N D H
O T E F H N O E E U E L I C L H L M T I S Z N A N O L Z A U F E I N E M S C H L I T T E N H O L E N
W N N E A E U G H R S M M S C S I Z E N U E T E U W I E E R E S N U N Z U S A M M E N G E S U C H T
U E A F H O L W E U G A T N T L N D T E E D E A L U N D A U F G E L A D E N H A T T E W O L L T E E
R W E E O R O A H L R R E R C N W R N S F E N I O R W E I L E R S O E R F R O R E N W A R N O C H N
I S A A E N E O N N C H E G R D C U N H S H E T H I C H T N A C H H A U S G E H E N S O N D E R N E
R N N U H S C D E E E E N C H I S M U R A T I F A R S T F E U E R A N M A C H E N U N D S I C H E I
N A W C M C A S R S H E N R R H B A D E E I T S N N B I S S C H E N W A E R M E N D A S C H A R R T
E D N N E I E W S E S G U W R E E E N C E R O D H E E R D E N S C H N E E W E G U N D W I E E R S O
D U E D F T F M N R B R A U A E E N E O A N D E D D E N E R D B O D E N A U F R A E U M T E F A N D
E D E E N N N E C N N G O E S E R I L K N E H I L E R E I N E N K L E I N E N G O L D E N E N S C H
L E N E U W D R R S L B T A E O U G E N L E S S U L U E S S E L N U N G L A U B T E E R W O D E R S
C S W S E T A S C E S M U R U E H A E E E L H U L C H L U E S S E L W A E R E M U E S S T E A U C H
D N S H U R B G N C L S E Z I U A D I O A S D S S D A S S C H L O S S D A Z U S E I N G R U B I N D
E I F E E E N S S D U I N D E R R A E N N E K R D E R E R D E U N D F A N D E I N E I S E R N E S K
A H E H E U S L E C E R S D S E E N C N N S L T W A E S T C H E N W E N N D E R S C H L U E S S E L
N S A S E I D S E A S E R T G N U C E T H R W P D N U R P A S S T D A C H T E E R E S S I N D G E W
I I R S C D M N A O T H E A K E S E N B S S E K A I S S K O S T B A R E S A C H E N I N D E M K A E
S R U N E S A E K E E A B T R W T C E R H C E H S S T C H E N E R S U C H T E A B E R E S W A R K E
I A S L O N L E C H U C H L I D N E D E L S H C S I N S C H L U E S S E L L O C H D A E N D L I C H
E E E C N S K R E E K S A I L O N R B T E T I D E E N T D E C K T E E R E I N S A B E R S O K L E I
N E S M M K N N T S A S E U N O D K H N A A E S E N D A S S M A N E S K A U M S E H E N K O N N T E
E S T B D H U C S O I D E N E L R E R E U P S R R E R P R O B I E R T E U N D D E R S C H L U E S S
E H L S K A R D H S T L I C E D L U C E E P T A G E L P A S S T E G L U E C K L I C H D A D R E H T
E N H N M N U U S I M U N U E M E E D A R R S E L E E R E I N M A L H E R U M U N D N U N M U E S S
E O E W S L N L S R A E R I D E N N V R B W A I T E N W I R W A R T E N B I S E R V O L L E N D S A
U E S C U D C N E S H N D N K E F S D L E G L E O U F G E S C H L O S S E N U N D D E N D E C K E L
A W T M D R E E W E A A N T N D U H N C A F I G H A U F G E M A C H T H A T D A N N W E R D E N W I
R U W H U D R N A A R E R F B E E A W E S R R F N R E R F A H R E N W A S F U E R W U N D E R B A R
E C D E A E L H G H N E S K A N S E T I M A E C N E S A C H E N I N D E M K A E S T C H E N L A G E
Verblüffenderweise hat die Methode so gut funktioniert, dass wir direkt den Klartext stehen haben. Selbst die 1. Spalte ist an der richtigen Position (was daran lag, dass 25-stellige Kennwort mit "A" beginnt).