Caesars chiffer

Historik och tillämpning

Caesar-chiffret är uppkallat efter Julius Caesar, som enligt Suetonius ' Life of the Twelve Caesars använde det med skift 3 för att skydda militära meddelanden. Även om Caesar var den första registrerade personen som använde detta schema, är det känt att andra substitutionschiffer har använts tidigare.

Om han hade något konfidentiellt att överföra, skrev han ner det med chiffer, det vill säga han ändrade ordningen på bokstäverna i alfabetet så att det var omöjligt att urskilja ett enda ord. Om någon ville tyda det och förstå dess innebörd, då var han tvungen att ersätta den fjärde bokstaven i alfabetet, nämligen D, för A, och så vidare, med andra bokstäver.
Gaius Suetonius Tranquill The Life of the Tolv Caesars , Bok ett, kap. 56 [3]

Hans brorson, Augustus , använde också detta chiffer, men flyttade åt höger efter ett, och det upprepade inte till början av alfabetet:

Närhelst han skrev med chiffer skrev han B för A, C för B och resten av bokstäverna på samma princip, och använde AA för X.
Gaius Suetonius Tranquill The Life of the Twelve Caesars , Bok två, kap. 88 [3]

Det finns bevis för att Julius Caesar också använde mer komplexa system [4] .

Det är inte känt hur effektivt Caesars chiffer var på den tiden, men det var förmodligen någorlunda säkert, inte minst eftersom de flesta av Caesars fiender var analfabeter och många antog att meddelandena var skrivna på ett okänt främmande språk [5] . Det finns inga bevis från den tiden angående metoder för att bryta enkla substitutionschiffer. Det tidigaste bevarade rekordet av frekvensanalys är Al-Kindis arbete från 800-talet om upptäckten av frekvensanalys [6] .

Caesar-chifferet, förskjutet med ett, används på baksidan av mezuzan för att kryptera Guds namn . Detta kan vara ett kvarhållande från en tidig tid då det judiska folket inte fick ha mezuzah [7] .

På 1800-talet användes ibland den personliga delen av annonser i tidningar för att utbyta meddelanden krypterade med enkla chiffer. Kahn (1967) beskriver fall där amatörer ägnade sig åt hemlig kommunikation krypterad med hjälp av Caesar-chifferet i The Times [8 ] . Ännu senare, 1915, fann Caesar-chifferet användning: den ryska armén använde det som ett substitut för mer komplexa chiffer som visade sig vara för svåra för trupperna; de tyska och österrikiska kryptoanalytikerna hade små svårigheter med att tyda dessa meddelanden [9] .

Caesar-chifferet med 13 skift används också i ROT13- algoritmen , en enkel textobfuskeringsmetod som ofta används på Usenet , och används mer som ett sätt att dölja spoilers än som en krypteringsmetod [10] . Vigenère-chifferet använder ett Caesar-chiffer med olika skiftningar vid varje position i texten; skiftvärdet definieras med ett upprepande nyckelord. Om nyckelordet är lika långt som meddelandet, genereras slumpmässigt, hålls hemligt och används endast en gång - ett sådant schema kallas ett engångsblockschema  - och detta är det enda krypteringssystemet för vilket absolut kryptografisk styrka har bevisats [11 ] .

Nyckelord som är kortare än budskapet (som "Complete Victory" som användes av konfederationen under det amerikanska inbördeskriget ) introducerar ett cykliskt mönster som kunde upptäckas med en förbättrad version av frekvensanalys [12] .

I april 2006 fångades den flyktige maffiabossen Bernardo Provenzano på Sicilien delvis på grund av kryptoanalys av hans meddelanden, skrivna med en variant av Caesar-chifferet. I Provenzano-chifferet ersattes bokstäverna först med siffror - serienumren på bokstäverna i alfabetet, och Caesar-chifferet användes redan på den resulterande siffrorna - så att när den skiftades med 3 skrevs "A" som "4", "B" - som "5" och så vidare [13] .

Ofta, för bekvämligheten med att använda Caesar-chifferet, används två skivor med olika diametrar monterade på en gemensam axel med alfabet ritade längs skivornas kanter. Inledningsvis roteras skivorna så att varje bokstav i alfabetet på den yttre skivan står mitt emot samma bokstav i alfabetet på den lilla skivan. Om vi ​​nu roterar den inre skivan med flera tecken, så får vi en överensstämmelse mellan symbolerna för den yttre skivan och den inre - Caesar-chifferet. Den resulterande disken kan användas för både kryptering och dekryptering [14] .

Till exempel, om det inre hjulet roteras så att symbolen A för den yttre skivan motsvarar symbolen D för den inre skivan, då får vi ett chiffer med en förskjutning på 3 åt vänster.

Bryter chiffret

Caesar-chifferet kan lätt brytas även om knäckaren bara känner till chiffertexten. Två situationer kan övervägas:

1. Knäckaren vet (eller antar) att ett enkelt substitutionschiffer användes, men vet inte att det är ett Caesar-schema.
2. Knäckaren vet att ett Caesar-chiffer användes, men vet inte värdet av skiftet.

I det första fallet kan chifferet brytas med samma metoder som för det enkla substitutionschifferet, såsom frekvensanalys , etc. Med dessa metoder kommer knäckaren sannolikt snabbt att märka regelbundenhet i lösningen och inse att chiffret är som används är Caesars chiffer.

I det andra fallet är det ännu lättare att bryta chiffer. Det finns inte många alternativ för skiftvärden (26 för engelska), alla kan kontrolleras med brute force [15] . Ett sätt att göra detta är att skriva ut ett stycke chiffertext i en kolumn med alla möjliga skift, en teknik som ibland kallas "att fullborda en enkel komponent" [16] . Betrakta ett exempel för chiffertexten "EXXEGOEXSRGI"; klartexten känns omedelbart igen av ögat på fjärde raden.

Ett annat sätt att tillämpa denna metod är att skriva alfabetet under varje bokstav i chiffertexten, med början på den bokstaven. Metoden kan påskyndas genom att använda förberedda alfabetremsor. För att göra detta måste du vika remsorna så att chiffertexten bildas på en rad, sedan i någon annan rad kommer vi att se den vanliga texten.

En annan metod för brute-force cracking är att kontrollera bokstavsfrekvenser . Genom att rita in frekvensen av bokstäver i chiffertexten, och känna till den förväntade spridningen av bokstäver för vanlig text på språket i fråga, kan man enkelt bestämma skiftningen genom att titta på skiftningen av några funktioner i diagrammet. Denna metod är känd som frekvensanalys . Till exempel, i en engelsk text är frekvenserna för bokstäverna E , T , (vanligtvis den vanligaste) och Q , Z (vanligtvis sällsyntare) särskilt olika [17] . Denna process kan automatiseras genom att datorprogrammet utvärderar hur väl den faktiska frekvensfördelningen matchar den förväntade fördelningen. Till exempel kan ett chi-kvadrattest [18] användas .

För vanlig text på naturligt språk kommer det troligen bara att finnas ett avkodningsalternativ. Men om du använder mycket korta meddelanden, finns det fall då flera dekrypteringsalternativ med olika skift är möjliga. Till exempel kan chiffertexten "MPQY" avkodas som antingen "aden" eller "vet" (förutsatt att klartexten är skriven på engelska). På liknande sätt kan "ALIIP" dechiffreras som "dockor" eller som "hjul"; "AFCCP" som "jolly" eller som "heja" (se även unikt avstånd ).

Kryptering flera gånger förbättrar inte säkerheten på något sätt, eftersom användningen av skiftchiffer a och b är likvärdig med användning av skiftchiffer a + b. I matematiska termer bildar kryptering med olika nycklar en grupp [19] .

Anteckningar

1. ↑ Luciano D. , Prichett G. Kryptologi : Från Caesar Ciphers till Public-Key Cryptosystems  // The College Mathematics Journal - Mathematical Association of America , Taylor & Francis , 1987. - Vol. 18, Iss. 1. - S. 2-17. — ISSN 0746-8342 ; 1931-1346 - doi:10.2307/2686311
2. ↑ Wobst, 2007 , s. 19.
3. ↑ 1 2 Life of the Twelve Caesars, 1964 .
4. ↑ Reinke E. C. Klassisk kryptografi  // Klass . j. (Class. Assoc. Middle West South) - Classical Association of the Middle West and South , 1962. - Vol. 58, Iss. 3. - S. 113-121. — ISSN 0009-8353 ; 2327-5812
5. ↑ Pieprzyk J. , Hardjono T. , Seberry J. Fundamentals of Computer Security  (engelska) - Springer Science + Business Media , 2003. - P. 6. - 677 sid. — ISBN 978-3-540-43101-5
6. ↑ Singh, 1999 , sid. 14–20.
7. ↑ Alexander Poltorak. Mezuzah och astrologi . chabad.org . Hämtad 13 juni 2008. (obestämd)
8. ↑ Kahn, 1967 , s. 775–6.
9. ↑ Kahn, 1967 , s. 631–2.
10. ↑ Wobst, 2007 , s. tjugo.
11. ↑ Fomichev, 2003 , sid. 239-246.
12. ↑ Kahn, 1967 .
13. ↑ Leyden, John . Maffiaboss avskaffad av klumpigt krypto , The Register  (19 april 2006). Hämtad 13 juni 2008.
14. ↑ Reynard, Robert. Secret Code Breaker: En kryptanalytikers handbok  . - 1996. - S. 92-51. - ISBN 1-889668-00-1 ).
15. ↑ Beutelspacher, Albrecht Kryptologi  (neopr.) . - Mathematical Association of America , 1994. - S.  8 -9. - ISBN 0-88385-504-6 .
16. ↑ Sinkov A. Elementär krypteringsanalys  (engelska) : A Mathematical Approach - Mathematical Association of America , 1998. - P. 13-15. — 232 sid. — ISBN 978-0-88385-622-2
17. ↑ Singh, 1999 , sid. 72–77.
18. ↑ Savarese, Chris; Brian Hart. Caesar Cipher (15 juli 2002). Hämtad: 16 juli 2008. (obestämd)
19. ↑ Wobst, 2007 , s. 31.

Litteratur

• Gaius Suetonius Tranquill . De tolv kejsarnas liv = De vita XII caesarvm. - M . : Förlag "Nauka", 1964. - 374 sid. - (Litterära monument).
• Kahn D. The Codebreakers  (engelska) : The Story of Secret Writing - Macmillan , 1967. - 1164 sid. — ISBN 978-0-684-83130-5
• Singh S. The Code Book , Histoire des codes secrets  (engelska) : The Science of Secrecy from Ancient Egypt to Quantum Cryptography, De l'Égypte des pharaons à l'ordinateur quantique - NYC : Doubleday , Knopf Doubleday Publishing Group , 1999. — 416 sid.
• Fomichev V. M. Diskret matematik och kryptologi : Föreläsningskurs / ed. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - 397 sid. — ISBN 978-5-86404-185-7
• Wobst R. Cryptology Unlocked  (engelska) / A. Shafir - Chichester : John Wiley & Sons Ltd , 2007. - 554 sid. — ISBN 978-0-470-06064-3

Länkar

• Caesar-chiffer  - implementering av Caesar-chifferet på olika språk hos Rosetta Code .
• Caesar chiffer - kryptering och dekryptering

Ordböcker och uppslagsverk	Britannica (online)