Caesarova šifra - Caesar cipher

v kryptografie, a Caesarova šifra, také známý jako Caesarova šifra, šifra řazení, Caesarův kód nebo Caesarův posun, je jedním z nejjednodušších a nejznámějších šifrování techniky. Je to typ substituční šifra ve kterém každé písmeno v prostý text je nahrazen písmenem o určitém pevném počtu pozic dolů abeceda. Například s posunem doleva o 3, D bude nahrazen A, E stal by se B, a tak dále. Metoda je pojmenována po Julius Caesar, který jej použil ve své soukromé korespondenci.[1]
Krok šifrování prováděný Caesarovou šifrou je často začleněn jako součást složitějších schémat, například Vigenèrova šifra, a stále má moderní aplikace v ROT13 Systém. Stejně jako u všech jednošifrových substitučních šifer je Caesarova šifra snadno rozbitná a v moderní praxi nenabízí v podstatě žádnou zabezpečení komunikace.
Příklad
Transformaci lze znázornit zarovnáním dvou abeced; šifrovací abeceda je prostá abeceda otočená doleva nebo doprava o určitý počet pozic. Například zde je Caesarova šifra používající rotaci doleva o tři místa, což odpovídá posunu doprava o 23 (parametr shift se používá jako klíč ):
Prostý: ABCDEFGHIJKLMNOPQRSTUVWXYZ Šifra: XYZABCDEFGHIJKLMNOPQRSTUVW
Při šifrování vyhledá osoba každé písmeno zprávy v řádku „prostý“ a zapíše odpovídající písmeno v řádku „šifra“.
Prostý text: RYCHLE HNĚDÁ LÍŠKA SKOČÍ NAD LENIVÝM PSEM Šifrovací text: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD
Dešifrování se provádí obráceně, s pravým posunem o 3.
Šifrování lze také reprezentovat pomocí modulární aritmetika nejprve transformací písmen na čísla podle schématu A → 0, B → 1, ..., Z → 25.[2] Šifrování dopisu X posunem n lze matematicky popsat jako,[3]
Dešifrování se provádí podobně,
(Existují různé definice pro modulo provoz. Ve výše uvedeném případě je výsledek v rozsahu 0 až 25; tj. pokud X + n nebo X − n nejsou v rozsahu 0 až 25, musíme odečíst nebo přidat 26.)
Náhrada zůstává v celé zprávě stejná, takže šifra je klasifikována jako typ monoabetická substituce, naproti tomu polyalfabetická substituce.
Historie a použití
Caesarova šifra je pojmenována po Julius Caesar, který podle Suetonius, používal jej s posunem tří (A stává se D při šifrování a D se stává A při dešifrování) k ochraně zpráv vojenského významu. Zatímco Caesar's bylo první zaznamenané použití tohoto schématu, je známo, že byly použity jiné substituční šifry dříve.[4][5]
„Kdyby měl cokoli důvěrného, aby to řekl, napsal to šifrou, tedy tak, že změnil pořadí písmen abecedy, aby nebylo možné rozeznat ani slovo. Pokud si to někdo přeje dešifrovat a dostat se na jejich to znamená, že musí nahradit čtvrté písmeno abecedy, konkrétně D, za A, a tak za ostatní. “
— Suetonius, Život Julia Caesara 56
Jeho synovec, Augustus, také používal šifru, ale se správným posunem o jednu a neobtočila se na začátek abecedy:
„Kdykoli psal šifrou, psal B pro A, C pro B a zbytek písmen na stejném principu, přičemž pro Z. použil AA.“
— Suetonius, Augustův život 88
Existují důkazy, že Julius Caesar používal i složitější systémy,[6] a jeden spisovatel, Aulus Gellius, odkazuje na (nyní ztracené) pojednání o svých šiferách:
„Existuje dokonce velmi důmyslně napsané pojednání od gramatika Probusa o tajném významu písmen ve složení Caesarových listů.“
— Aulus Gellius, Podkrovní noci 17.9.1–5
Není známo, jak účinná byla v té době Caesarova šifra, ale je pravděpodobné, že byla přiměřeně bezpečná, v neposlední řadě proto, že většina Caesarových nepřátel by byla negramotný a další by předpokládali, že zprávy byly napsány v neznámém cizím jazyce.[7] V té době neexistuje žádný záznam o žádných technikách řešení jednoduchých substitučních šifer. Nejstarší dochované záznamy se datují k dílům z 9. století z Al-Kindi v Arab svět s objevem frekvenční analýza.[8]
Caesarova šifra s posunem o jednu je použita na zadní straně mezuzah zašifrovat Boží jména. Může to být pozdržení z dřívější doby, kdy židovští lidé nesměli mít mezuzot. Samotná písmena kryptogramu obsahují nábožensky významné „božské jméno“, které Ortodoxní víra drží síly zla pod kontrolou.[9]
V 19. století se část osobních reklam v novinách někdy používala k výměně zpráv šifrovaných pomocí jednoduchých šifrovacích schémat. Kahn (1967) popisuje případy milenců zapojených do tajné komunikace šifrované pomocí Caesarovy šifry Časy.[10] Ještě v roce 1915 byla používána Caesarova šifra: ruská armáda ji použila jako náhradu za složitější šifry, které se ukázaly jako příliš obtížné pro jejich jednotky; Němec a Rakušan kryptoanalytici neměli s dešifrováním svých zpráv žádné potíže.[11]

Šifry Caesar dnes najdete v dětských hračkách, jako jsou tajné dekodéry. Caesarův posun o třináct se také provádí v ROT13 algoritmus, jednoduchá metoda obfuscating textu široce nalezený na Usenet a používá se k zakrytí textu (například vtipné pointy a příběh) spoilery ), ale není vážně používán jako metoda šifrování.[12]
The Vigenèrova šifra používá Caesarovu šifru s jiným posunem na každé pozici v textu; hodnota posunu je definována pomocí opakujícího se klíčového slova. Pokud je klíčové slovo tak dlouhé jako zpráva, je vybráno v náhodný, nikdy se nestane známým nikomu jinému a nikdy se znovu nepoužije, toto je jednorázová podložka šifra, která se ukázala jako nerozbitná. Podmínky jsou tak obtížné, že se jich v praxi nikdy nedosáhne. Klíčová slova kratší než zpráva (např. „Kompletní vítězství "používá Konfederace Během americká občanská válka ), zavést cyklický vzor, který by mohl být detekován statisticky pokročilou verzí frekvenční analýzy.[13]
V dubnu 2006 uprchlík Mafie šéf Bernardo Provenzano byl zajat v Sicílie částečně proto, že některé z jeho zpráv, neobratně napsaných ve variantě Caesarovy šifry, byly přerušeny. Provenzanova šifra používala čísla, takže „A“ by se psalo jako „4“, „B“ jako „5“ atd.[14]
V roce 2011 byl Rajib Karim ve Spojeném království usvědčen z „teroristických trestných činů“ poté, co použil šifru Caesar ke komunikaci s bangladéšskými islámskými aktivisty, kteří diskutovali o spiknutí s cílem vyhodit do povětří British Airways letadla nebo narušit jejich IT sítě. I když strany měly přístup k mnohem lepším šifrovacím technikám (sám Karim použil PGP pro ukládání dat na počítačových discích) se rozhodli použít vlastní schéma (implementované v Microsoft Excel ), odmítající sofistikovanější kódový program zvaný Mujahedeen Secrets „protože„ kaffíři “nebo nevěřící o tom vědí, takže musí být méně bezpečný“.[15] To představovalo aplikaci bezpečnost prostřednictvím neznáma.
Prolomení šifry
Dešifrování posun | Prostý text kandidáta |
---|---|
0 | exxegoexsrgi |
1 | dwwdfndwrqfh |
2 | cvvcemcvqpeg |
3 | buubdlbupodf |
4 | zaútočit |
5 | zsszbjzsnmbd |
6 | yrryaiyrmlac |
... | |
23 | haahjrhavujl |
24 | gzzgiqgzutik |
25 | fyyfhpfytshj |
Caesarovu šifru lze snadno rozbít i v a scénář pouze pro šifrovaný text. Lze uvažovat o dvou situacích:
- útočník ví (nebo hádá), že byla použita nějaká jednoduchá substituční šifra, ale ne konkrétně, že se jedná o Caesarovo schéma;
- útočník ví, že se používá Caesarova šifra, ale nezná hodnotu posunu.
V prvním případě lze šifru rozbít pomocí stejných technik jako pro obecnou jednoduchou substituční šifru, například frekvenční analýza nebo vzorová slova.[16] Při řešení je pravděpodobné, že si útočník rychle všimne pravidelnosti řešení a odvodí, že konkrétním použitým algoritmem je šifra Caesar.

Ve druhém případě je prolomení schématu ještě přímočařejší. Jelikož existuje jen omezený počet možných směn (25 v angličtině), lze je každý postupně otestovat v a útok hrubou silou.[17] Jedním ze způsobů, jak to udělat, je napsat úryvek ciphertextu do tabulky všech možných posunů[18] - technika někdy známá jako „dokončení holé součásti“.[19] Uvedený příklad je pro ciphertext "EXXEGOEXSRGI"; holý text je okamžitě rozpoznatelný okem při posunu o čtyři. Dalším způsobem pohledu na tuto metodu je, že pod každým písmenem ciphertextu je celá abeceda vypsána obráceně, počínaje tímto písmenem. Tento útok lze zrychlit pomocí sada proužků připravená s abecedou zapsanou v obráceném pořadí. Pruhy jsou poté zarovnány tak, aby tvořily šifrový text podél jednoho řádku, a holý text by se měl objevit v jednom z ostatních řádků.
Dalším přístupem hrubou silou je vyrovnání frekvenčního rozdělení písmen. Pomocí grafu četnosti písmen v cifrovaném textu a znalosti očekávaného rozdělení těchto písmen v původním jazyce prostého textu může člověk snadno zjistit hodnotu posunu při pohledu na posun konkrétních rysů grafu. Toto je známé jako frekvenční analýza. Například v anglickém jazyce jsou frekvence písmen v holém textu E, T, (obvykle nejčastější) a Q, Z (obvykle nejméně časté) jsou zvláště výrazné.[20] Počítače to dokážou také měřením toho, jak dobře odpovídá skutečné rozdělení frekvence očekávanému rozdělení; například statistika chí-kvadrát může být použito.[21]
Pro prostý text v přirozeném jazyce bude obvykle existovat pouze jedna věrohodná dešifrování, i když pro extrémně krátké prosté texty je možných více kandidátů. Například ciphertext MPQY mohl, věrohodně, dešifrovat buď "doupě„nebo“znát„(za předpokladu, že holý text je v angličtině); podobně,“ALIIP„do“panenky„nebo“kolo"; a "AFCCP„do“rozjařený„nebo“jásot"(viz také vzdálenost unicity ).
Díky šifře Caesar neposkytuje šifrování textu vícekrát žádné další zabezpečení. Důvodem je, že dvě šifrování, řekněme, se posunují A a posunout B, bude ekvivalentní jedinému šifrování s posunem A + B. Z matematického hlediska tvoří sada šifrovacích operací pod každým možným klíčem a skupina pod složení.[22]
Viz také
Poznámky
- ^ Suetonius, Vita Divi Julii 56.6
- ^ Luciano, Dennis; Gordon Prichett (leden 1987). „Cryptology: From Caesar Ciphers to Public-Key Cryptosystems“. The College Mathematics Journal. 18 (1): 2–17. CiteSeerX 10.1.1.110.6123. doi:10.2307/2686311. JSTOR 2686311.
- ^ Wobst, Reinhard (2001). Kryptologie odemčena. Wiley. p. 19. ISBN 978-0-470-06064-3.
- ^ „Praskání kódu“. Ústřední zpravodajská služba. Citováno 21. února 2017.
- ^ Singh, Simon (2000). Kniha zákonů. Kotva. str.289-290. ISBN 0-385-49532-3.
- ^ Reinke, Edgar C. (prosinec 1962). "Klasická kryptografie". Klasický deník. 58 (3): 114.
- ^ Pieprzyk, Josef; Thomas Hardjono; Jennifer Seberry (2003). Základy počítačové bezpečnosti. Springer. p. 6. ISBN 3-540-43101-2.
- ^ Singh, Simon (2000). Kniha zákonů. Kotva. str.14–20. ISBN 0-385-49532-3.
- ^ Alexander Poltorak. "Mezuzah a astrologie". chabad.org. Citováno 2008-06-13.
- ^ Kahn, David (1967). Codebreakers. str. 775–6. ISBN 978-0-684-83130-5.
- ^ Kahn, David (1967). Codebreakers. str. 631–2. ISBN 978-0-684-83130-5.
- ^ Wobst, Reinhard (2001). Kryptologie odemčena. Wiley. p. 20. ISBN 978-0-470-06064-3.
- ^ Kahn, David (1967). Codebreakers. ISBN 978-0-684-83130-5.
- ^ Leyden, John (2006-04-19). „Šéf mafie zrušen neohrabaným krypto“. Registrace. Citováno 2008-06-13.
- ^ „BA džihádista spoléhal na šifrování z doby Ježíše. Registrace. 2011-03-22. Citováno 2011-04-01.
- ^ Beutelspacher, Albrecht (1994). Kryptologie. Mathematical Association of America. str. 9–11. ISBN 0-88385-504-6.
- ^ Beutelspacher, Albrecht (1994). Kryptologie. Mathematical Association of America. s. 8–9. ISBN 0-88385-504-6.
- ^ Leighton, Albert C. (duben 1969). "Tajná komunikace mezi Řeky a Římany". Technologie a kultura. 10 (2): 139–154. doi:10.2307/3101474. JSTOR 3101474.
- ^ Sinkov, Abraham; Paul L. Irwin (1966). Elementární kryptoanalýza: Matematický přístup. Mathematical Association of America. str. 13–15. ISBN 0-88385-622-0.
- ^ Singh, Simon (2000). Kniha zákonů. Kotva. str.72–77. ISBN 0-385-49532-3.
- ^ Savarese, Chris; Brian Hart (2002-07-15). „Caesarova šifra“. Citováno 2008-07-16.
- ^ Wobst, Reinhard (2001). Kryptologie odemčena. Wiley. p. 31. ISBN 978-0-470-06064-3.
Bibliografie
- F. L. Bauer, Dešifrovaná tajemství, 2. vydání, 2000, Springer. ISBN 3-540-66871-3.
- David Kahn, The Codebreakers: The Story of Secret Writing, Přepracované vydání. 1996. ISBN 0-684-83130-9.
- Chris Savarese a Brian Hart, Caesarova šifra, 1999