streamalism.org

1. Pregled

U ovom uputstvu istražit ćemo Cezarovu šifru, metodu šifriranja koja prebacuje slova poruke u drugu, manje čitljivu.

Prije svega, proći ćemo metodu šifriranja i vidjeti kako je implementirati u Javi.

Zatim ćemo vidjeti kako dešifrirati šifriranu poruku, pod uvjetom da znamo odmak koji se koristi za njezino šifriranje.

I na kraju, naučit ćemo kako razbiti takvu šifru i tako dohvatiti izvornu poruku iz šifrirane, a da ne znamo korišteni pomak.

2. Cezar Šifra

2.1. Obrazloženje

Prije svega, definirajmo što je šifra. Šifra je metoda za šifriranje poruke s namjerom da je učini manje čitljivom. Što se tiče Cezarove šifre, to je zamjenska šifra koja transformira poruku pomicanjem njezinih slova za zadani pomak.

Recimo da želimo pomaknuti abecedu za 3, pa slovo A pretvorio bi se u pismo D, B do E, C do F, i tako dalje.

Evo potpunog podudaranja između originalnih i transformiranih slova za odmak od 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 C

Kao što vidimo, nakon što transformacija nadiđe slovo Z, vraćamo se na početak abecede, tako da x, Y i Z pretvaraju se u A, B i C, odnosno.

Stoga, ako odaberemo pomak veći ili jednak 26, petlju ćemo barem jednom prebaciti preko cijele abecede. Zamislimo da poruku pomaknemo za 28, što stvarno znači da je pomičemo za 2. Zapravo, nakon prebacivanja za 26, sva slova odgovaraju sebi.

Stvarno, bilo koji ofset možemo transformirati u jednostavniji offset pomoću izvodeći na njemu modulo 26 operaciju:

pomak = pomak% 26

2.2. Algoritam u Javi

Sada, da vidimo kako implementirati Cezarovu šifru u Javu.

Prvo, izradimo razred CezarCipher koji će držati a šifra() metoda uzimajući poruku i pomak kao parametre:

javna klasa CaesarCipher {Šifra niza (String poruka, int pomak) {}}

Ta će metoda šifrirati poruku pomoću Cezarove šifre.

Ovdje ćemo pretpostaviti da su pomaci pozitivni, a poruke sadrže samo mala slova i razmake. Zatim, ono što želimo je pomaknuti sve abecedne znakove za zadani pomak:

StringBuilder rezultat = novi StringBuilder (); za (znak znaka: message.toCharArray ()) {if (znak! = '') {int originalAlphabetPosition = znak - 'a'; int newAlphabetPosition = (originalAlphabetPosition + pomak)% 26; char newCharacter = (char) ('a' + newAlphabetPosition); result.append (newCharacter); } else {rezultat.append (znak); }} vratiti rezultat;

Kao što vidimo, oslanjamo se na ASCII kodove slova abecede da bismo postigli svoj cilj.

Prvo izračunavamo položaj trenutnog slova u abecedi i za to uzimamo njegov ASCII kod i oduzimamo ASCII kod slova a iz toga. Zatim primijenimo pomak na ovaj položaj, pažljivo koristeći modul kako bismo ostali u rasponu abecede. I na kraju, dohvaćamo novi znak dodavanjem novog položaja u ASCII kod slova a.

Pokušajmo sada s ovom implementacijom na poruci "rekao mi je da nikad ne bih mogao naučiti lamu da vozi" s pomakom od 3:

CaesarCipher šifra = nova CaesarCipher (); String cipheredMessage = cipher.cipher ("rekao mi je da nikad ne bih mogao naučiti lamu da vozi", 3); assertThat (cipheredMessage) .isEqualTo ("kh wrog ph l frxog qhyhu whdfk d oodpd wr gulyh");

Kao što vidimo, šifrirana poruka poštuje prethodno definirano podudaranje za pomak od 3.

Sad, ovaj konkretni primjer ima specifičnost da ne premašuje slovo z tijekom transformacije, stoga se ne mora vraćati na početak abecede. Stoga, pokušajmo ponovno s pomakom od 10, tako da će se neka slova preslikati u slova na početku abecede, na primjer t koja će biti preslikana d:

String cipheredMessage = cipher.cipher ("rekao mi je da nikad ne bih mogao naučiti lamu da vozi", 10); assertThat (cipheredMessage) .isEqualTo ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo");

Radi prema očekivanjima, zahvaljujući modulo operaciji. Ta se operacija brine i za veće pomake. Recimo da želimo koristiti 36 kao pomak, što je ekvivalentno 10, modulo operacija osigurava da će transformacija dati isti rezultat.

3. Dešifriraj

3.1. Obrazloženje

Sad, da vidimo kako dešifrirati takvu poruku kad znamo odmak koji se koristi za njezino šifriranje.

Zapravo, dešifriranje poruke šifrirane Cezarovom šifrom može se smatrati šifriranjem negativnim odmakom ili također šifriranjem komplementarnim odmakom.

Dakle, recimo da imamo poruku šifriranu s pomakom od 3, a zatim je možemo šifrirati s pomakom od -3 ili kriptirati s pomakom od 23. U svakom slučaju, dohvaćamo izvornu poruku.

Nažalost, naš algoritam ne podnosi negativne pomake. Imat ćemo problema s pretvaranjem ponovljenih slova na kraj abecede (na primjer s transformiranjem slova a u pismo z s pomakom od -1). Ali, možemo izračunati komplementarni pomak koji je pozitivan, a zatim upotrijebiti naš algoritam.

Pa, kako dobiti ovaj komplementarni pomak? Naivan način za to bio bi oduzimanje originalnog odmaka od 26. Naravno, to će raditi za pomake između 0 i 26, ali u suprotnom će dati negativne rezultate.

To je gdje ponovno ćemo se poslužiti operatorom modula, izravno na originalnom odmaku, prije nego što izvršimo oduzimanje. Na taj način osiguravamo uvijek vraćanje pozitivnog pomaka.

3.2. Algoritam u Javi

Ajmo sada to implementirati u Javi. Prvo ćemo dodati a dešifrirati() metoda za naš razred:

Dešifriranje niza (poruka niza, int pomak) {}

Onda, nazovimo šifra() metoda s našim izračunatim komplementarnim pomakom:

povratna šifra (poruka, 26 - (pomak% 26));

To je to, postavljen je naš algoritam za dešifriranje. Pokušajmo na primjeru s pomakom 36:

String decipheredSentence = cipher.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", 36); assertThat (decipheredSentence) .isEqualTo ("rekao mi je da nikad ne bih mogao naučiti lamu da vozi");

Kao što vidimo, dohvaćamo svoju izvornu poruku.

4. Razbijanje Ceasar šifre

4.1. Obrazloženje

Sad kad smo pokrili šifriranje i dešifriranje poruka pomoću Cezarove šifre, možemo zaroniti u to kako ga razbiti. Odnosno, dešifrirajte šifriranu poruku, a da u početku ne znate upotrijebljeni pomak.

Da bismo to učinili, iskoristit ćemo vjerojatnosti za pronalazak engleskih slova u tekstu. Ideja će biti dešifrirati poruku pomoću pomaka 0 do 25 i provjeriti koji pomak predstavlja distribuciju slova sličnu onoj na engleskim tekstovima.

Da bismo utvrdili sličnost dviju raspodjela, poslužit ćemo se statistikom Hi-kvadrata.

Statistika Hi-kvadrata pružit će broj koji će nam reći jesu li dvije distribucije slične ili ne. Što je manji broj, to su sličniji.

Dakle, izračunat ćemo hi-kvadrat za svaki pomak, a zatim ćemo vratiti onaj s najmanjim hi-kvadratom. To bi nam trebalo dati pomak koji se koristi za šifriranje poruke.

Međutim, moramo to imati na umu ova tehnika nije neprobojna a ako je poruka prekratka ili ako koristi riječi koje nažalost ne predstavljaju standardni tekst na engleskom, mogla bi vratiti pogrešan pomak.

4.2. Definirajte distribuciju osnovnih slova

Pogledajmo sada kako implementirati algoritam lomljenja u Javi.

Prije svega, izradimo a breakCipher () metoda u našem CezarCipher klase, koja će vratiti odmak korišten za šifriranje poruke:

int breakCipher (niz poruka) {}

Zatim, definirajmo niz koji sadrži vjerojatnost pronalaska određenog slova u engleskom tekstu:

double [] englishLettersProbability = {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};

Iz ovog polja moći ćemo izračunati očekivane frekvencije slova u datoj poruci množenjem vjerojatnosti s duljinom poruke:

double [] očekuje seLettersFrequency = Nizovi.stream (englishLettersProbabilities) .map (vjerojatnost -> vjerojatnost * message.getLength ()) .toArray ();

Na primjer, u poruci duljine 100 trebali bismo očekivati ​​pismo a pojaviti 7,3 puta, a slovo e pojaviti se 13 puta.

4.3. Izračunajte Chi-kvadrate

Sada ćemo izračunati Chi-kvadrate dešifrirane distribucije slova poruka i standardne engleske distribucije slova.

Da bismo to postigli, morat ćemo uvesti biblioteku Apache Commons Math3 koja sadrži klasu korisnosti za izračunavanje Chi-kvadrata:

 org.apache.commons commons-math3 3.6.1 

Ono što sada moramo učiniti je stvorite niz koji će sadržavati izračunate Chi-kvadrate za svaki pomak između 0 i 25.

Stoga ćemo šifriranu poruku dešifrirati pomoću svakog odstupanja, a zatim prebrojati slova u toj poruci.

Napokon ćemo upotrijebiti ChiSquareTest # chiSquare metoda za izračunavanje hi-kvadrata između očekivane i promatrane raspodjele slova:

dvostruki [] chiSquares = novi dvostruki [26]; for (int offset = 0; offset <chiSquares.length; offset ++) {String decipheredMessage = dešifriranje (poruka, pomak); dugačka [] slovaFrekvencije = promatraneFrekvencije slova (dešifrirana poruka); dvostruki chiSquare = novi ChiSquareTest (). chiSquare (očekuje sePovećanjaFrekvencije, slovaFrekvencije); chiSquares [pomak] = chiSquare; } vratiti chiSquares;

The opaženeLettersFrequences () metoda jednostavno realizira broj slova a do z u proslijeđenoj poruci:

long [] obserLettersFrequences (string poruka) {return IntStream.rangeClosed ('a', 'z') .mapToLong (pismo -> countLetter ((char) slovo, poruka)) .toArray (); } dugo countLetter (slovo sa znakom, niz poruka) {return message.chars () .filter (znak -> znak == slovo) .count (); }

4.4. Pronađite najvjerojatniji pomak

Jednom kada se izračunaju svi hi-kvadrati, možemo vratiti pomak koji odgovara najmanjem hi-kvadratu:

int probableOffset = 0; for (int offset = 0; offset <chiSquares.length; offset ++) {System.out.println (String.format ("Hi-kvadrat za pomak% d:% .2f", pomak, chiSquares [offset])); if (chiSquares [offset] <chiSquares [probableOffset]) {probableOffset = offset; }} return probableOffset;

Iako nije potrebno unijeti petlju s pomakom 0, jer smatramo da je minimum prije pokretanja petlje, to činimo kako bismo ispisali njezinu vrijednost Hi-kvadrat.

Pokušajmo s ovim algoritmom na poruci šifriranoj pomakom 10:

int offset = algoritam.breakCipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo"); assertThat (offset) .isEqualTo (10); assertThat (algoritam.dešifriranje ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", offset)) .isEqualTo ("rekao mi je da nikad ne bih mogao naučiti lamu da vozi");

Kao što vidimo, metoda dohvaća ispravan pomak, koji se zatim može koristiti za dešifriranje poruke i dohvaćanje izvornog.

Evo različitih Chi-kvadrata izračunatih za ovaj određeni odmor:

Hi-kvadrat za pomak 0: 210,69 Hi-kvadrat za pomak 1: 327,65 Hi-kvadrat za pomak 2: 255,22 Hi-kvadrat za pomak 3: 187,12 Hi-kvadrat za pomak 4: 734,16 Hi-kvadrat za pomak 5: 673,68 Chi- Kvadrat za pomak 6: 223,35 Hi-kvadrat za pomak 7: 111,13 Hi-kvadrat za pomak 8: 270,11 Hi-kvadrat za pomak 9: 153,26 Hi-kvadrat za pomak 10: 23,74 Hi-kvadrat za pomak 11: 643,14 Hi-kvadrat za pomak pomak 12: 328,83 Hi-kvadrat za pomak 13: 434,19 Chi-kvadrat za pomak 14: 384,80 Chi-kvadrat za pomak 15: 1206,47 Hi-kvadrat za pomak 16: 138,08 Hi-kvadrat za pomak 17: 262,66 Hi-kvadrat za pomak 18 : 253,28 Chi-Square za ofset 19: 280,83 Chi-Square za offset 20: 365,77 Chi-Square za offset 21: 107,08 Chi-Square za offset 22: 548,81 Chi-Square za offset 23: 255,12 Chi-Square za ofset 24: 458,72 Chi-Square za ofset 25: 325,45

Kao što vidimo, onaj za pomak 10 očito je manji od ostalih.

5. Zaključak

U ovom smo članku pokrili Cezarovu šifru. Naučili smo kako šifrirati i dešifrirati poruku pomicanjem njezinih slova za zadani pomak. Također smo naučili kako razbiti šifru. I vidjeli smo sve implementacije Jave koje nam to omogućuju.

Kôd ovog članka možete pronaći na GitHubu.