Affiene code

Zo gebruik je de affiene code

1. 1. Kies een modus en vul je tekst in. Coderen zet klare tekst om in versleutelde tekst; Decoderen draait dat om.
2. 2. Stel de sleutel in. Vul a in, de vermenigvuldiger, en b, de verschuiving. a moet een van de 12 waarden zijn die onder de velden staan — klik op een waarde om hem te gebruiken. b mag elk geheel getal zijn; het wordt modulo 26 genomen.
3. 3. Lees de uitwerking. Het paneel onder het resultaat geeft beide formules voor je sleutel, de inverse van a en de rekensom van elke letter.
4. 4. Geen sleutel? Probeer ze allemaal. Vink in de decodeermodus Probeer alle 312 sleutels aan. De resultaten worden gerangschikt op hoe goed hun lettertellingen bij het Engels passen, en Deze sleutel gebruiken laadt er een.

De formule van de affiene code

Nummer de letters vanaf nul: A = 0, B = 1 … Z = 25. Om een letter x te versleutelen, vermenigvuldig je hem met a, tel je b op en houd je de rest over na deling door 26: E(x) = (a·x + b) mod 26. Om een letter y te ontsleutelen, maak je die stappen in omgekeerde volgorde ongedaan — trek b af en vermenigvuldig dan met a⁻¹, de modulaire inverse van a: D(y) = a⁻¹·(y − b) mod 26. De inverse is het getal dat, vermenigvuldigd met a, een rest van 1 overlaat. Voor a = 5 is dat 21, omdat 5 × 21 = 105 = 4 × 26 + 1.

Waarom slechts 12 waarden van a werken

Vermenigvuldigen met a mag nooit twee letters op dezelfde plek laten uitkomen, anders zou decoderen twee antwoorden hebben. Dat gebeurt zodra a een factor gemeen heeft met 26 = 2 × 13. Bij a = 2 bijvoorbeeld komen A (0) en N (13) allebei op b uit, omdat 2 × 13 = 26, en dat is 0 mod 26. Dus a moet oneven zijn en mag niet 13 zijn, waardoor de twaalf getallen hieronder overblijven — precies degene die een inverse modulo 26 hebben. Met 26 keuzes voor b zijn dat 12 × 26 = 312 sleutels, waarvan er één (a = 1, b = 0) niets verandert.

Uitgewerkt voorbeeld: a = 5, b = 8

Met a = 5 en b = 8 wordt AFFINE CIPHER versleuteld tot IHHWVC SWFRCP — het voorbeeld van de tool. De letters van AFFINE, uitgewerkt:

Om te decoderen vermenigvuldigt de tool met a⁻¹ = 21. De I (8) wordt 21 × (8 − 8) = 0, en dat is A; de H (7) wordt 21 × (7 − 8) = −21, en dat is 5 mod 26, oftewel F. Negatieve waarden zijn in deze stap normaal — mod 26 betekent alleen dat je 26 optelt of aftrekt totdat het getal tussen 0 en 25 ligt.

Twee bekende codes zijn verkapte affiene codes. Met a = 1 is de formule x + b, een Caesarverschuiving van b; met a = 25 en b = 25 is het de Atbash-code, het alfabet achterstevoren gelezen.

Zo kraak je een affiene code

Met slechts 311 sleutels die iets veranderen, is de botste aanval ze allemaal te proberen, wat de brute-forceoptie in een fractie van een seconde doet. Het lastige is het antwoord herkennen, dus de tool rangschikt elk resultaat met een chi-kwadraatvergelijking van zijn lettertellingen met typisch Engels. Bij een zin of meer komt de juiste sleutel bovenaan; bij een korte uitdrukking misschien niet — voor IHHWVC SWFRCP alleen staat de ware sleutel (5, 8) op de vierde plaats — dus lees de lijst door in plaats van de eerste regel te vertrouwen.

Cryptanalisten kunnen het met algebra beter. De affiene code is een monoalfabetische substitutie — elke letter wordt steeds dezelfde letter — dus frequentieanalyse suggereert welke versleutelde letters voor E en T staan, en twee van zulke gissingen geven twee vergelijkingen. Onder de sleutel hierboven wordt E (4) tot C (2) en T (19) tot Z (25), dus 4a + b ≡ 2 en 19a + b ≡ 25 (mod 26). De eerste van de tweede aftrekken geeft 15a ≡ 23; vermenigvuldigen met 7, de inverse van 15, geeft a ≡ 161 ≡ 5, en dan b ≡ 2 − 20 ≡ 8. Twee letters bekende klare tekst leveren de hele sleutel op.

Veelgestelde vragen

Wat is een affiene code?

Een substitutiecode die het getal x van elke letter omzet in (a·x + b) mod 26, zodat elke letter met a wordt vermenigvuldigd en daarna met b wordt verschoven. De sleutel is het paar (a, b). Omdat een bepaalde letter altijd dezelfde versleutelde letter wordt, is hij monoalfabetisch — een sterker ogende verwant van de Caesarcode, en niet moeilijker te kraken.

Waarom moet a relatief priem zijn met 26?

Decoderen vermenigvuldigt met de inverse van a modulo 26, en die inverse bestaat alleen als a en 26 geen gemeenschappelijke factor hebben. Hebben ze er wel een, dan worden twee verschillende letters dezelfde letter en kan het bericht niet met zekerheid worden teruggelezen. Dat sluit elk even getal en 13 uit, waardoor 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 en 25 overblijven.

Hoe vind ik de modulaire inverse van a?

Zoek het getal tussen 1 en 25 dat, vermenigvuldigd met a, een rest van 1 overlaat bij deling door 26. Voor a = 7 is dat 15, omdat 7 × 15 = 105 = 4 × 26 + 1. Met slechts twaalf gevallen lees je ze het snelst uit de tabel hierboven af; bij grote moduli vindt het uitgebreide algoritme van Euclides de inverse rechtstreeks.

Hoeveel sleutels heeft de affiene code?

312 — twaalf keuzes voor a maal 26 keuzes voor b. Eén ervan, a = 1 met b = 0, laat de tekst ongewijzigd, dus 311 versleutelen echt. Dat is weinig genoeg om elke sleutel in een middag met de hand te proberen, en met een computer in een oogwenk.

Is de Caesarcode een soort affiene code?

Ja. Met a = 1 wordt de formule x + b, een Caesarverschuiving van b; ROT13 is a = 1, b = 13. Ook Atbash is affien, met a = 25 en b = 25. Beide zitten tussen de 312 sleutels die de brute force probeert.

Is de affiene code veilig?

Nee. Hij valt voor brute force, voor frequentieanalyse en voor slechts twee letters bekende klare tekst, zoals de algebra hierboven laat zien. Het is uitstekende oefening in modulair rekenen, maar voor alles wat ertoe doet heb je moderne versleuteling nodig.