Caesarova šifra v Jave
1. Prehľad
V tomto výučbe sa budeme zaoberať šifrou Caesar, šifrovacou metódou, ktorá posúva písmená správy tak, aby vznikla iná, menej čitateľná.
Najskôr si prejdeme šifrovaciu metódu a uvidíme, ako ju implementovať v Jave.
Potom uvidíme, ako dešifrovať zašifrovanú správu, za predpokladu, že poznáme offset použitý na jej šifrovanie.
A nakoniec sa naučíme, ako takúto šifru prelomiť a tak získať pôvodnú správu zo zašifrovanej bez znalosti použitého offsetu.
2. Caesarova šifra
2.1. Vysvetlenie
Najskôr si definujme, čo je to šifra. Šifra je metóda šifrovania správy, ktorej cieľom je znížiť jej čitateľnosť. Pokiaľ ide o šifru Caesar, ide o substitučnú šifru, ktorá transformuje správu posunutím jej písmen o daný posun.
Povedzme, že chceme posunúť abecedu o 3, potom o písmeno A by sa transformoval do písmena D, B do E, C. do F, a tak ďalej.
Tu je úplná zhoda medzi originálnymi a transformovanými písmenami pre posun o 3:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B CAko vidíme, akonáhle transformácia presiahne písmeno Z, vrátime sa na začiatok abecedy, takže X, Y. a Z sa transformujú na A, B a C., resp.
Preto, ak zvolíme posunutie väčšie alebo rovné 26, urobíme slučku aspoň raz v celej abecede. Predstavme si, že posunieme správu o 28, čo v skutočnosti znamená, že ju posúvame o 2. Po posunutí o 26 sa všetky písmená skutočne zhodujú.
Naozaj môžeme akýkoľvek posun transformovať na jednoduchšie posunutie o vykonávanie operácie modulo 26 na ňom:
offset = offset% 262.2. Algoritmus v Jave
Teraz sa pozrime, ako implementovať šifru Caesar v Jave.
Najskôr vytvorme triedu CaesarCipher že bude držať a šifra () metóda prijímajúca správu a offset ako parametre:
verejná trieda CaesarCipher {reťazcová šifra (reťazcová správa, int offset) {}}Táto metóda zašifruje správu pomocou šifry Caesar.
Tu budeme predpokladať, že vyrovnania sú kladné a správy obsahujú iba malé písmená a medzery. Potom chceme posunúť všetky abecedné znaky o daný posun:
Výsledok StringBuilder = nový StringBuilder (); for (char character: message.toCharArray ()) {if (character! = '') {int originalAlphabetPosition = character - 'a'; int newAlphabetPosition = (originalAlphabetPosition + offset)% 26; char newCharacter = (char) ('a' + newAlphabetPosition); result.append (newCharacter); } else {vysledok.append (znak); }} vrátiť výsledok;Ako vidíme, pri dosahovaní nášho cieľa sa spoliehame na kódy ASCII abecedných písmen.
Najskôr vypočítame pozíciu aktuálneho písmena v abecede a za to vezmeme jeho kód ASCII a odčítame kód ASCII písmena a od toho. Potom použijeme posun na túto pozíciu a opatrne použijeme modulo, aby sme zostali v rozsahu abecedy. A nakoniec získame nový znak pridaním novej pozície do písmenového kódu ASCII a.
Vyskúšajme teraz túto implementáciu v správe „povedal mi, že nikdy nemôžem naučiť lamu šoférovať“ s posunom 3:
Šifra CaesarCipher = nová CaesarCipher (); String cipheredMessage = cipher.cipher ("povedal mi, že lamu nikdy nemôžem naučiť šoférovať", 3); assertThat (cipheredMessage) .isEqualTo ("kh wrog ph l frxog qhyhu whdfk d oodpd wr gulyh");Ako vidíme, šifrovaná správa rešpektuje zhody definované skôr pre posun o 3.
Tento konkrétny príklad má teraz tú zvláštnosť, že nesmie presiahnuť písmeno z počas transformácie, a preto sa nemusíte vracať na začiatok abecedy. Skúsme to teda znova s odsadením 10, aby sa niektoré písmená namapovali na písmená na začiatku abecedy, napríklad t ktoré budú namapované na d:
String cipheredMessage = cipher.cipher ("povedal mi, že lamu nikdy nemôžem naučiť šoférovať", 10); assertThat (cipheredMessage) .isEqualTo ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo");Funguje podľa očakávaní vďaka prevádzke modulo. Táto operácia sa postará aj o väčšie vyrovnania. Povedzme, že chceme použiť 36 ako offset, čo je ekvivalent 10, operácia modulo zabezpečí, že transformácia prinesie rovnaký výsledok.
3. Dešifrovať
3.1. Vysvetlenie
Teraz sa pozrime, ako dešifrovať takúto správu, keď poznáme offset použitý na jej šifrovanie.
V skutočnosti rozlúštenie správy šifrovanej šifrou Caesar sa dá považovať za šifrovanie so záporným posunom alebo za šifru s doplnkovým posunom.
Povedzme teda, že máme správu zašifrovanú s posunom 3. Potom ju môžeme zašifrovať posunom -3 alebo ju zašifrovať posunom 23. Či tak alebo onak, načítame pôvodnú správu.
Náš algoritmus, bohužiaľ, nespracováva negatívne posuny po vybalení z krabice. Budeme mať problémy s prevodom opakovania písmen na koniec abecedy (napríklad s transformáciou písmen) a do listu z s posunom -1). Môžeme však vypočítať doplnkový posun, ktorý je kladný, a potom použiť náš algoritmus.
Ako teda získať tento doplnkový offset? Naivným spôsobom by bolo odpočítanie pôvodného posunutia od 26. To samozrejme bude fungovať pre kompenzácie medzi 0 a 26, ale inak prinesie negatívne výsledky.
To je kde pred vykonaním odpočtu znova použijeme operátor modulo, priamo na pôvodnom ofsetu. Týmto spôsobom zabezpečíme, aby sa vždy vrátil pozitívny ofset.
3.2. Algoritmus v Jave
Poďme to teraz implementovať do Javy. Najskôr pridáme a dešifrovať () metóda do našej triedy:
Dešifrovanie reťazca (reťazcová správa, int offset) {}Potom, nazvime to šifra () metóda s našim vypočítaným doplnkovým posunom:
návratová šifra (správa, 26 - (offset% 26));To je všetko, náš dešifrovací algoritmus je nastavený. Skúsme to na príklade s posunom 36:
Reťazec decipheredSentence = cipher.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", 36); assertThat (decipheredSentence) .isEqualTo („povedal mi, že lamu nikdy nemôžem naučiť šoférovať“);Ako vidíme, načítame našu pôvodnú správu.
4. Prelomenie Ceasarovej šifry
4.1. Vysvetlenie
Teraz, keď sme pokryli šifrovanie a dešifrovanie správ pomocou šifry Caesar, môžeme sa ponoriť do toho, ako ju rozbiť. To znamená dešifrovať šifrovanú správu bez toho, aby ste najskôr poznali použitý offset.
Aby sme to dosiahli, využijeme pravdepodobnosť nájdenia anglických písmen v texte. Myšlienkou bude dešifrovať správu pomocou posunov 0 až 25 a skontrolovať, aký posun predstavuje distribúciu písmen podobnú anglickým textom.
Na určenie podobnosti dvoch rozdelení použijeme štatistiku Chi-kvadrát.
Štatistika chí-kvadrát poskytne číslo, ktoré nám hovorí, či sú dve distribúcie podobné alebo nie. Čím menšie číslo, tým viac sú si podobné.
Takže pre každý offset vypočítame chí-kvadrát a potom vrátime ten s najmenším chi-kvadrátom. Toto by nám malo poskytnúť posun, ktorý sa používa na šifrovanie správy.
Musíme si to však uvedomiť táto technika nie je nepriestrelná a ak je správa príliš krátka alebo používa slová, ktoré, žiaľ, nereprezentujú štandardný anglický text, môže vrátiť nesprávny ofset.
4.2. Definujte distribúciu základných písmen
Pozrime sa teraz, ako implementovať algoritmus prerušenia v jazyku Java.
Najskôr si vytvorme a breakCipher () metóda v našom CaesarCipher triedy, ktorá vráti posun použitý na šifrovanie správy:
int breakCipher (reťazcová správa) {}Potom definujme pole obsahujúce pravdepodobnosti nájdenia určitého písmena v anglickom texte:
double [] englishLettersProbabilities = {0,073, 0,009, 0,030, 0,044, 0,130, 0,028, 0,016, 0,035, 0,074, 0,002, 0,003, 0,035, 0,025, 0,078, 0,074, 0,027, 0,003, 0,077, 0,063, 0,093, 0,027, 0,013, 0,016, 0,005, 0,019, 0,001};Z tohto poľa budeme schopní vypočítať očakávané frekvencie písmen v danej správe vynásobením pravdepodobností dĺžkou správy:
double [] expectLettersFrequencies = Arrays.stream (englishLettersProbabilities) .map (pravdepodobnosť -> pravdepodobnosť * message.getLength ()) .toArray ();Napríklad v správe o dĺžke 100 by sme mali očakávať písmeno a sa objaví 7,3-krát a písmeno e sa objaví 13-krát.
4.3. Vypočítajte chí-štvorce
Teraz budeme počítať Chi-štvorce dešifrovanej distribúcie písmen správ a štandardnej distribúcie anglických písmen.
Aby sme to dosiahli, budeme musieť importovať knižnicu Apache Commons Math3, ktorá obsahuje triedu nástrojov na výpočet chí-kvadrátov:
org.apache.commons commons-math3 3.6.1 Teraz musíme urobiť vytvorte pole, ktoré bude obsahovať vypočítané chí-štvorce pre každý posun medzi 0 a 25.
Takto dešifrujeme zašifrovanú správu pomocou každého posunutia a potom spočítame písmená v tejto správe.
Nakoniec použijeme ChiSquareTest # chiSquare metóda na výpočet chí-kvadrátu medzi očakávaným a pozorovaným rozdelením písmen:
double [] chiSquares = nový double [26]; for (int offset = 0; offset <chiSquares.length; offset ++) {String decipheredMessage = decipher (message, offset); long [] lettersFrequencies = ObservedLettersFrequencies (decipheredMessage); dvojitý chiSquare = nový ChiSquareTest (). chiSquare (expectLettersFrequencies, lettersFrequencies); chiSquares [offset] = chiSquare; } vrátiť chiSquares;The ObservedLettersFrequencies () metóda jednoducho realizuje počet písmen a do z v odovzdanej správe:
long [] ObservedLettersFrequencies (String message) {return IntStream.rangeClosed ('a', 'z') .mapToLong (letter -> countLetter ((char) letter, message)) .toArray (); } long countLetter (char letter, String message) {return message.chars () .filter (character -> character == letter) .count (); }4.4. Nájdite najpravdepodobnejší offset
Po vypočítaní všetkých chí-štvorcov môžeme vrátiť offset zodpovedajúci najmenšiemu chi-štvorcu:
int pravdepodobnyOffset = 0; for (int offset = 0; offset <chiSquares.length; offset ++) {System.out.println (String.format ("Chi-Square pre offset% d:% .2f", offset, chiSquares [offset]))); if (chiSquares [offset] <chiSquares [probableOffset]) {probableOffset = offset; }} return probableOffset;Aj keď nie je potrebné zadávať slučku s posunom 0, pretože to považujeme za minimum pred spustením slučky, urobíme to preto, aby sme vytlačili jej hodnotu chí-kvadrát.
Vyskúšajme tento algoritmus na správe zašifrovanej pomocou posunu 10:
int offset = algorithm.breakCipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo"); assertThat (offset) .isEqualTo (10); assertThat (algorithm.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", offset)) .isEqualTo ("povedal mi, že nikdy nemôžem naučiť lamu šoférovať");Ako vidíme, metóda načíta správny offset, ktorý sa potom dá použiť na dešifrovanie správy a na získanie pôvodného.
Tu sú rôzne chí-štvorce vypočítané pre tento konkrétny zlom:
Chi-Square pre posun 0: 210,69 Chi-Square pre posun 1: 327,65 Chi-Square pre posun 2: 255,22 Chi-Square pre posun 3: 187,12 Chi-Square pre posun 4: 734,16 Chi-Square pre posun 5: 673,68 Chi Štvorec pre offset 6: 223,35 Chi-Square pre posun 7: 111,13 Chi-Square pre posun 8: 270,11 Chi-Square pre posun 9: 153,26 Chi-Square pre posun 10: 23,74 Chi-Square pre posun 11: 643,14 Chi-Square pre offset 12: 328,83 Chi-Square pre posun 13: 434,19 Chi-Square pre posun 14: 384,80 Chi-Square pre posun 15: 1206,47 Chi-Square pre posun 16: 138,08 Chi-Square pre posun 17: 262,66 Chi-Square pre posun 18 : 253,28 Chi-Square pre posun 19: 280,83 Chi-Square pre posun 20: 365,77 Chi-Square pre posun 21: 107,08 Chi-Square pre posun 22: 548,81 Chi-Square pre posun 23: 255,12 Chi-Square pre posun 24: 458,72 Chi-štvorec pre offset 25: 325,45Ako vidíme, ten pre posun 10 je zjavne menší ako ostatné.
5. Záver
V tomto článku sme sa venovali šifre Caesar. Naučili sme sa, ako šifrovať a dešifrovať správu posunutím jej písmen o daný posun. Tiež sme sa naučili, ako prelomiť šifru. A videli sme všetky implementácie Java, ktoré nám to umožňujú.
Kód tohto článku nájdete na GitHub.
