streamalism.org

1. Áttekintés

Ebben az oktatóanyagban a Caesar-rejtjelet fogjuk felfedezni, egy olyan titkosítási módszert, amely egy üzenet betűit tolja egy másik, kevésbé olvashatóvá.

Először is átnézzük a titkosítási módszert, és megnézzük, hogyan lehet ezt Java-ban megvalósítani.

Ezután meglátjuk, hogyan lehet megfejteni egy titkosított üzenetet, feltéve, hogy ismerjük a titkosításhoz használt eltolást.

És végül megtanuljuk, hogyan kell feltörni egy ilyen titkosítást, és így visszakeresni az eredeti üzenetet a titkosítottból anélkül, hogy tudnánk a használt eltolást.

2. Caesar Cipher

2.1. Magyarázat

Először határozzuk meg, mi is az a rejtjel. A rejtjel az üzenet titkosítására szolgáló módszer, amelynek célja, hogy kevésbé olvasható legyen. Ami a Caesar-rejtjelet illeti, ez egy helyettesítő rejtjel, amely az üzenetet úgy alakítja át, hogy betűit egy adott eltolással eltolja.

Tegyük fel, hogy az ábécét 3-mal, majd betűvel akarjuk eltolni A betűvé alakulna át D, B nak nek E, C nak nek F, stb.

Itt található az eredeti és az átalakított betűk teljes megfeleltetése 3 eltolás esetén:

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

Ahogy látjuk, ha az átalakulás meghaladja a betűt Z, visszatérünk az ábécé elejére, úgy, hogy x, Y és Z átalakulnak A, B és Cill.

Ezért, ha 26-nál nagyobb vagy egyenlő eltolást választunk, akkor legalább egyszer a teljes ábécé fölé hurokolunk. Képzeljük el, hogy 28-ra tolunk egy üzenetet, ez valójában azt jelenti, hogy 2-vel eltoljuk. Valóban, miután 26-mal eltoltuk, minden betű megegyezik egymással.

Valójában bármely eltolást egyszerűbbé alakíthatjuk modulo 26 műveletet hajt végre rajta:

eltolás = eltolás% 26

2.2. Algoritmus Java-ban

Most nézzük meg, hogyan lehet a Caesar-rejtjelet Java-ban megvalósítani.

Először hozzunk létre egy osztályt CaesarCipher hogy fog tartani a rejtjel() módszer, amely paraméterként üzenetet és eltolást vesz fel:

nyilvános osztály CaesarCipher {Karaktersorozat (karakterlánc-üzenet, int offset) {}}

Ez a módszer a Caesar-rejtjel segítségével titkosítja az üzenetet.

Itt feltételezzük, hogy az eltolások pozitívak, és az üzenetek csak kisbetűket és szóközt tartalmaznak. Ezután azt akarjuk, hogy az összes ábécés karaktert eltoljuk a megadott eltolással:

StringBuilder eredmény = new StringBuilder (); for (char karakter: üzenet.toCharArray ()) {if (karakter! = '') {int eredetiAlphabetPosition = karakter - 'a'; int newAlphabetPosition = (originalAlphabetPosition + offset)% 26; char newCharacter = (char) ('a' + newAlphabetPosition); eredmény.append (newCharacter); } else {eredmény.append (karakter); }} visszatérési eredmény;

Ahogy látjuk, az ábécé betűinek ASCII kódjaira támaszkodunk célunk elérése érdekében.

Először kiszámoljuk az aktuális betű helyzetét az ábécében, és ehhez kivesszük az ASCII kódját, és kivonjuk az ASCII betű kódját a ebből. Ezután az eltolást erre a helyzetre alkalmazzuk, óvatosan a modulo segítségével, hogy az ábécé tartományában maradjon. Végül az új karaktert úgy kapjuk meg, hogy hozzáadjuk az új pozíciót a levél ASCII kódjához a.

Próbáljuk ki ezt a megvalósítást az „azt mondta nekem, hogy soha nem tudnék megtanítani egy lámát vezetni” üzenetre, 3-as eltolással:

CaesarCipher rejtjel = új CaesarCipher (); String cipheredMessage = cipher.cipher ("azt mondta nekem, hogy soha nem taníthatok lámát vezetésre", 3); assertThat (rejtjelezett üzenet) .isEqualTo ("kh wrog ph l frxog qhyhu whdfk d oodpd wr gulyh");

Mint láthatjuk, a rejtjelezett üzenet tiszteletben tartja a 3 eltolására korábban megadott egyezést.

Ennek a konkrét példának az a sajátossága, hogy ne lépje túl a betűt z az átalakítás során, ezért nem kell visszamenni az ábécé elejére. Így próbálkozzon újra 10-es eltolással, hogy néhány betű az ábécé elején lévő betűkhöz legyen hozzárendelve, például t amelyet feltérképeznek d:

String cipheredMessage = cipher.cipher ("azt mondta nekem, hogy soha nem taníthatok lámát vezetésre", 10); assertThat (cipheredMessage) .isEqualTo ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo");

A várakozásoknak megfelelően működik, köszönhetően a modulo működésnek. Ez a művelet nagyobb eltolásokról is gondoskodik. Tegyük fel, hogy 36-at akarunk használni eltolásként, ami egyenértékű 10-vel, a modulo művelet biztosítja, hogy az átalakítás ugyanazt az eredményt adja.

3. Megfejteni

3.1. Magyarázat

Most nézzük meg, hogyan lehet megfejteni egy ilyen üzenetet, amikor tudjuk, hogy az eltolás a titkosításhoz használt.

Ami azt illeti, A Caesar titkosítással titkosított üzenet megfejtése úgy tekinthető, mint egy negatív eltolással történő titkosítás, vagy egy kiegészítő eltolással történő titkosítás is..

Tehát tegyük fel, hogy van egy 3-as eltolással titkosított üzenetünk. Ezután akár -3 eltolással is titkosíthatjuk, vagy pedig 23-as eltolással. Bármelyik módon is, visszakeresjük az eredeti üzenetet.

Sajnos algoritmusunk nem kezeli eleve a negatív eltolást. Problémáink lesznek a betűk konvertálásával az ábécé végére (például a betű átalakítására) a a levélbe z -1 eltolással). Kiszámíthatjuk a komplementer eltolást, amely pozitív, majd használhatjuk algoritmusunkat.

Szóval, hogyan lehet elérni ezt a kiegészítő ellentételezést? Ennek naiv módja az lenne, ha az eredeti eltolást kivonjuk a 26-ból. Természetesen ez 0 és 26 közötti eltolódások esetén működik, de máskülönben negatív eredményt ad.

Ahol A kivonás megint felhasználjuk a modulo operátort, közvetlenül az eredeti eltoláson. Így biztosítjuk, hogy mindig pozitív ellentételezést kapjunk.

3.2. Algoritmus Java-ban

Most valósítsuk meg Java-ban. Először hozzáadunk egy megfejtés() módszer az osztályunkhoz:

Karakterlánc megfejtése (karakterlánc üzenet, int eltolás) {}

Akkor hívjuk a rejtjel() módszer a számított kiegészítő kompenzációnkkal:

visszatérési rejtjel (üzenet, 26 - (offset% 26));

Ennyi, a megfejtő algoritmusunk fel van állítva. Próbáljuk ki a 36-os eltolással ellátott példán:

Karakterlánc megfejtveSentence = rejtjel.megfejtés ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", 36); assertThat (decipheredSentence) .isEqualTo ("azt mondta nekem, hogy soha nem taníthatok lámát vezetésre");

Mint láthatjuk, visszakeresjük eredeti üzenetünket.

4. A Ceasar Cipher törése

4.1. Magyarázat

Most, hogy áttekintettük az üzenetek rejtjelezését és megfejtését a Caesar-rejtjel segítségével, elmélyülhetünk annak megtörésében. Vagyis megfejteni egy rejtjelezett üzenetet anélkül, hogy eleinte ismerné a használt eltolást.

Ehhez a valószínűségeket felhasználva megtaláljuk az angol betűket a szövegben. Az ötlet az lesz, hogy megfejtjük az üzenetet 0–25 eltolással, és ellenőrizzük, hogy az shift milyen betűeloszlást mutat, hasonlóan az angol szövegekhez.

Két eloszlás hasonlóságának meghatározásához a Chi-négyzet statisztikát fogjuk használni.

A Chi-négyzet statisztika számot ad, amely megmondja, hogy két eloszlás hasonló-e vagy sem. Minél kisebb a szám, annál hasonlóbbak.

Tehát kiszámoljuk a Chi-négyzetet minden eltoláshoz, majd visszaadjuk a legkisebb Chi-négyzetet. Ez megadja nekünk az üzenet titkosításához használt eltolást.

Ezt azonban szem előtt kell tartanunk ez a technika nem golyóálló Ha az üzenet túl rövid lenne, vagy olyan szavakat használna, amelyek sajnos nem reprezentálják a normál angol szöveget, akkor ez rossz eltolást eredményezhet.

4.2. Határozza meg az alaplevelek terjesztését

Most nézzük meg, hogyan lehet megvalósítani a törés algoritmust a Java-ban.

Először hozzuk létre a breakCipher () módszer a mi CaesarCipher osztály, amely visszaadja az üzenet titkosításához használt eltolást:

int breakCipher (karakterlánc üzenet) {}

Ezután definiáljunk egy tömböt, amely annak valószínűségét tartalmazza, hogy egy bizonyos betűt megtaláljon egy angol szövegben:

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};

Ebből a tömbből képes leszünk kiszámolni az adott üzenetben szereplő betűk várható gyakoriságát, megszorozva a valószínűségeket az üzenet hosszával:

double [] várhatóLettersFrequencies = Arrays.stream (englishLettersProbability) .map (valószínűség -> valószínűség * üzenet.getLength ()) .toArray ();

Például egy 100 hosszúságú üzenetben számolnunk kell a betűvel a hogy 7,3-szor jelenjen meg, és a levelet e hogy 13 alkalommal jelenjen meg.

4.3. Számítsa ki a Chi-négyzeteket

Most meg fogjuk számolni a megfejtett üzenetek és standard angol betűk elosztásának Khi-négyzetét.

Ennek eléréséhez importálnunk kell az Apache Commons Math3 könyvtárat, amely egy segédosztályt tartalmaz a Chi-négyzetek kiszámításához:

 org.apache.commons commons-math3 3.6.1 

Amit most meg kell tennünk, az az hozzon létre egy tömböt, amely tartalmazza a kiszámított Chi-négyzeteket minden egyes eltoláshoz 0 és 25 között.

Így minden egyes eltolással megfejtjük a titkosított üzenetet, majd megszámoljuk az abban szereplő betűket.

Végül használjuk a ChiSquareTest # chiSquare módszer a várható és megfigyelt betűeloszlás közötti Chi-négyzet kiszámítására:

kettős [] chiSquares = új kettős [26]; for (int eltolás = 0; eltolás <chiSquares.length; eltolás ++) {String decipheredMessage = megfejtés (üzenet, eltolás); hosszú [] betűFrekvenciák = megfigyeltLettersFrekvenciák (megfejtettMessage); dupla chiSquare = új ChiSquareTest (). chiSquare (várhatóLettersFrequencies, lettersFrequencies); chiSquares [offset] = chiSquare; } return chiSquares;

A observLettersFrequencies () módszer egyszerűen megvalósítja a betűk számát a nak nek z az átadott üzenetben:

long [] observLettersFrequencies (String üzenet) {return IntStream.rangeClosed ('a', 'z') .mapToLong (letter -> countLetter ((char) letter, message)) .toArray (); } long countLetter (char betű, String üzenet) {return message.chars (). szűrő (karakter -> karakter == levél) .szám (); }

4.4. Keresse meg a legvalószínűbb eltolást

Miután az összes Chi-négyzet kiszámítottuk, visszaadhatjuk a legkisebb Chi-négyzetnek megfelelő eltolást:

int valószínűOffset = 0; for (int offset = 0; offset <chiSquares.length; offset ++) {System.out.println (String.format ("Chi-Square a% d eltoláshoz:% .2f", offset, chiSquares [offset])); if (chiSquares [offset] <chiSquares [probableOffset]) {probableOffset = eltolás; }} return valószínûOffset;

Bár nem szükséges a ciklust a 0 eltolással megadni, mivel azt a ciklus megkezdése előtt a minimumnak tekintjük, a Chi-négyzet értékének kinyomtatásához tesszük.

Próbálja ki ezt az algoritmust a 10. eltolással titkosított üzeneten:

int offset = algoritmus.breakCipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo"); assertThat (offset) .isEqualTo (10); assertThat (algoritmus.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", offset)) .isEqualTo ("azt mondta nekem, soha nem tudtam lámát vezetésre tanítani");

Mint láthatjuk, a módszer lekéri a helyes eltolást, amelyet azután meg lehet értelmezni az üzenetet, és lekérni az eredetit.

Itt vannak az adott töréshez kiszámított különböző Chi-négyzetek:

Chi-Square a 0 eltoláshoz: 210.69 Chi-Square az 1. eltoláshoz: 327.65 Chi-Square a 2. eltoláshoz: 255.22 Chi-Square a 3. eltoláshoz: 187.12 Chi-Square a 4. eltoláshoz: 734.16 Chi-Square az 5. eltoláshoz: 673.68 Chi- Négyzet a 6-os eltoláshoz: 223,35 Khi-négyzet a 7-es eltoláshoz: 111,13 Khi-négyzet a 8-as eltoláshoz: 270,11 Khi-négyzet a 9-es eltoláshoz: 153,26 Khi-négyzet a 9-es eltoláshoz: 23,74 Khi-tér a 11-es eltoláshoz: 23,74 Khi-négyzet a 11-es eltoláshoz: 643,14 Kji-négyzet a 12. eltolás: 328,83 Khi-tér a 13. eltoláshoz: 434,19 Khi-négyzet a 14. eltoláshoz: 384,80 Khi-tér a 15. eltoláshoz: 1206,47 Khi-tér a 16. eltoláshoz: 138,08 Khi-tér a 16. eltoláshoz: 138,08 Khi-tér a 17. eltoláshoz: 262,66 : 253,28 Khi-négyzet a 19. eltoláshoz: 280,83 Khi-tér a 20. eltoláshoz: 365,77 Khi-négyzet a 21. eltoláshoz: 107,08 Khi-tér a 22. eltoláshoz: 548,81 Khi-négyzet a 23. eltoláshoz: 255,12 Khi-tér a 24. eltoláshoz: 255,12 Ksi-négyzet eltoláshoz 24: 458,72 Chi-Square a 25. ellentételezéshez: 325.45

Mint láthatjuk, a 10. ellentételezés egyértelműen kisebb, mint a többi.

5. Következtetés

Ebben a cikkben kitértünk a Caesar-rejtjelre. Megtanultuk, hogyan kell titkosítani és megfejteni az üzenetet úgy, hogy betűit eltoljuk egy adott eltolással. Megtanultuk azt is, hogyan kell megtörni a rejtjelet. És láttuk az összes Java-implementációt, amely lehetővé teszi számunkra ezt.

A cikk kódja a GitHub oldalon található.