ADFGVX och fraktionering

År 1918 stod den tyska militären inför ett kritiskt problem: allierade kryptoanalytiker knäckte deras fältkoder snabbare än de hann ersättas. Ett nytt och starkare chiffer behövdes akut inför våroffensiven 1918.

Överste Fritz Nebel utvecklade ADFGVX-chiffret, som kombinerade två klassiska tekniker på ett sätt som aldrig tidigare hade gjorts inom militär kryptografi.

Chiffret har fått sitt namn efter de sex bokstäverna i chiffertexten: A, D, F, G, V, X. Bokstäverna valdes medvetet eftersom deras representationer i morsekod skiljer sig mycket från varandra.

Det minimerade överföringsfel via fältradio. Om en bokstav förväxlades med en annan kunde ett helt meddelande förstöras, så konstruktörerna valde bokstäver vars morsemönster var så lätta som möjligt att skilja åt.

Det första steget är substitution med hjälp av en Polybius-kvadrat på 6×6. De 36 rutorna innehåller alfabetets 26 bokstäver och siffrorna 0–9, placerade i en nyckelbestämd ordning. Rad- och kolumnrubrikerna är de sex bokstäverna A, D, F, G, V, X.

Varje klartecken ersätts med två bokstäver: rad- och kolumnrubriken för dess ruta. Om H till exempel finns på rad A, kolumn F blir det "AF".

Efter substitutionen skrivs den fördubblade chiffertexten in i ett rutnät med lika många kolumner som nyckelns längd. Ett andra nyckelord bestämmer kolumnernas ordning.

Kolumnerna läses av i alfabetisk ordning efter nyckelbokstäverna. Det omarrangerar de substituerade paren, bryter upp återstående mönster och skapar ett chiffer som står emot både frekvensanalys och mönstermatchning.

Fraktionering är tekniken att dela upp varje klartecken i flera chiffertextsymboler innan de transponeras. I ADFGVX blir varje bokstav två symboler (rad och kolumn), som sedan blandas oberoende av varandra.

Det innebär att de två "halvorna" av en klartextbokstav hamnar på olika platser i den slutliga chiffertexten, vilket gör det omöjligt att analysera substitution och transposition var för sig.

Rena substitutionschiffer (som Playfair) är sårbara för frekvensanalys. Rena transpositionschiffer (som räckschiffer) är sårbara för anagram. Genom att kombinera dem hanteras båda svagheterna.

ADFGVX gör frekvensanalys svårare genom att fraktionera och transponera de substituerade symbolerna. För att knäcka transpositionen måste man känna till substitutionsnyckeln, och omvänt.

Den franske kryptoanalytikern Georges Painvin knäckte ADFGVX-chiffret i juni 1918, bara några dagar före den tyska offensiv som det skulle skydda. Det betraktas som en av första världskrigets mest briljanta bedrifter inom kryptoanalys.

Painvins metod utnyttjade mönster i meddelanden som skickades samma dag med samma nyckel. Genom att jämföra chiffertexter av liknande längd kunde han identifiera kolumngränser och arbeta bakåt genom transpositionen.

Painvins genombrott gav de allierade underrättelser som bidrog till att hejda den tyska våroffensiven. Offensiven misslyckades delvis på grund av det informationsövertag som uppstod när ADFGVX knäcktes.

Historien visade att även sinnrika chifferkonstruktioner kan knäckas när den operativa säkerheten är bristfällig. Tyskarna återanvände nycklar och skickade för många meddelanden under kort tid, vilket gav Painvin det material han behövde.

Vid kolumntransposition skriver du klartexten på rader under ett nyckelord och läser sedan kolumnerna i alfabetisk ordning efter nyckelordets bokstäver. Nyckelordet "KEY" ger kolumnordningen 2-1-3 (E kommer före K, som kommer före Y).

Resultatets kolumner flätar samman den ursprungliga texten på ett sätt som förstör lokala mönster. Vid dekryptering skriver du tillbaka chiffertexten i kolumner i samma ordning och läser den rad för rad.

Varje lager i ett klassiskt chiffer hanterar en annan svaghet. Substitution döljer bokstävernas identitet, medan transposition döljer deras position. Tillsammans skapar de ett chiffer som kräver att båda lagren angrips samtidigt.

Denna princip att kombinera konfusion (substitution) och diffusion (transposition) formaliserades senare av Claude Shannon och blev den teoretiska grunden för moderna blockchiffer som AES.

Före ADFGVX använde tyskarna ADFGX, en enklare variant med fem bokstäver som inte innehöll siffror i sin Polybiusruta. ADFGVX utökade rutan till 6x6 för att inkludera alla 10 siffror, vilket möjliggjorde kryptering av numeriska data.

Att ADFGX utökades till ADFGVX var ett svar på de allierades begränsade framgångar mot ADFGX. Genom att lägga till siffror ökade nyckelutrymmet och frekvensanalys av digrafer blev svårare, eftersom mönstren fördelades över fler symbolpar.

ADFGVX kombinerade substitution med en Polybiusruta och kolumntransposition och använde fraktionering för att fläta samman dem. Alfabetet med sex bokstäver valdes för att minimera överföringsfel i morsekod.

Trots sin sofistikerade konstruktion knäckte Painvin chiffret genom att utnyttja återanvändning av nyckeln. Chiffret visade både styrkan i att kombinera klassiska tekniker och den avgörande betydelsen av säker hantering.