Caesar-krypteringen i Java

1. Oversigt

I denne vejledning skal vi udforske Caesar-chifferet, en krypteringsmetode, der skifter bogstaver i en besked for at producere en anden, mindre læsbar.

Først og fremmest gennemgår vi krypteringsmetoden og ser, hvordan vi implementerer den i Java.

Derefter ser vi, hvordan vi kan dechiffrere en krypteret meddelelse, forudsat at vi kender den forskydning, der bruges til at kryptere den.

Og endelig lærer vi, hvordan man bryder en sådan kryptering og dermed henter den originale besked fra den krypterede uden at kende den anvendte forskydning.

2. Caesar-kryptering

2.1. Forklaring

Lad os først definere, hvad en chiffer er. En chiffer er en metode til kryptering af en besked, der har til hensigt at gøre den mindre læselig. Hvad angår Caesar-chifferet, er det en erstatningskryptering, der omdanner en besked ved at flytte dens bogstaver med en given forskydning.

Lad os sige, at vi vil skifte alfabetet med 3 og derefter bogstavet EN ville blive omdannet til bogstav D, B til E, C til F, og så videre.

Her er den komplette matchning mellem originale og transformerede bogstaver til en forskydning på 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

Som vi kan se, når transformationen går ud over bogstavet Z, vi går tilbage til starten af ​​alfabetet, så det x, Y og Z omdannes til EN, B og C, henholdsvis.

Derfor, hvis vi vælger en forskydning større eller lig med 26, sløjfer vi mindst én gang over hele alfabetet. Lad os forestille os, at vi skifter en besked med 28, det betyder virkelig, at vi skifter den med 2. Efter skift med 26 stemmer alle bogstaver efter hinanden.

Virkelig kan vi omdanne enhver forskydning til en enklere forskydning ved udfører en modulo 26-operation på den:

forskydning = forskydning% 26

2.2. Algoritme i Java

Lad os nu se, hvordan du implementerer Caesar-kryptering i Java.

Lad os først oprette en klasse CaesarCipher der holder en chiffer () metode til at tage en besked og en forskydning som parametre:

offentlig klasse CaesarCipher {String cipher (String message, int offset) {}}

Denne metode krypterer meddelelsen ved hjælp af Caesar-krypteringen.

Vi antager her, at forskydninger er positive, og beskeder kun indeholder små bogstaver og mellemrum. Derefter er det, vi ønsker, at skifte alle alfabetiske tegn ved den givne forskydning:

StringBuilder-resultat = nyt StringBuilder (); for (char karakter: message.toCharArray ()) {if (character! = '') {int originalAlphabetPosition = character - 'a'; int newAlphabetPosition = (originalAlphabetPosition + offset)% 26; char newCharacter = (char) ('a' + newAlphabetPosition); result.append (newCharacter); } andet {resultat.append (tegn); }} returner resultat;

Som vi kan se, vi stoler på ASCII-koder i alfabetets bogstaver for at nå vores mål.

Først beregner vi placeringen af ​​det aktuelle bogstav i alfabetet, og for det tager vi dets ASCII-kode og trækker ASCII-kode for bogstavet -en fra det. Derefter anvender vi forskydningen til denne position ved forsigtigt at bruge modulo til at forblive i alfabetområdet. Og endelig henter vi det nye tegn ved at tilføje den nye position til ASCII-bogstavkoden -en.

Lad os nu prøve denne implementering på meddelelsen "han fortalte mig, at jeg aldrig kunne lære en lama at køre" med en forskydning på 3:

CaesarCipher cipher = ny CaesarCipher (); String cipheredMessage = cipher.cipher ("han fortalte mig, at jeg aldrig kunne lære en lama at køre", 3); assertThat (cipheredMessage) .isEqualTo ("kh wrog ph l frxog qhyhu whdfk d oodpd wr gulyh");

Som vi kan se, respekterer den krypterede meddelelse den matchning, der er defineret tidligere for en forskydning på 3.

Nu har dette særlige eksempel specificiteten for ikke at overstige bogstavet z under transformationen, derfor ikke behøver at gå tilbage til starten af ​​alfabetet. Lad os således prøve igen med en forskydning på 10, så nogle bogstaver kortlægges til bogstaver i begyndelsen af ​​alfabetet, som f.eks. t som vil blive kortlagt til d:

String cipheredMessage = cipher.cipher ("han fortalte mig, at jeg aldrig kunne lære en lama at køre", 10); assertThat (cipheredMessage) .isEqualTo ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo");

Det fungerer som forventet takket være modulo-operationen. Denne operation tager også sig af større forskydninger. Lad os sige, at vi vil bruge 36 som offset, hvilket svarer til 10, modulo-operationen sikrer, at transformationen giver det samme resultat.

3. Afkode

3.1. Forklaring

Lad os nu se, hvordan man dechifrerer en sådan besked, når vi kender forskydningen, der bruges til at kryptere den.

Faktisk, dechifrering af en meddelelse krypteret med Caesar-chiffer kan ses som kryptering af den med en negativ forskydning eller også kryptering af den med en komplementær forskydning.

Så lad os sige, at vi har en besked krypteret med en forskydning på 3. Derefter kan vi enten kryptere den med en forskydning på -3 eller kryptere den med en forskydning på 23. Uanset hvad henter vi den oprindelige besked.

Desværre håndterer vores algoritme ikke negativ offset uden for boksen. Vi har problemer med at konvertere bogstaver, der går tilbage til slutningen af ​​alfabetet (for eksempel at transformere brevet -en ind i brevet z med en forskydning på -1). Men vi kan beregne den komplementære forskydning, som er positiv, og derefter bruge vores algoritme.

Så hvordan opnås denne supplerende forskydning? Den naive måde at gøre dette på ville være at trække den oprindelige forskydning fra 26. Selvfølgelig vil dette fungere for forskydninger mellem 0 og 26, men ellers vil det give negative resultater.

Det er her Vi bruger modulo-operatøren igen direkte på den oprindelige forskydning, før vi foretager subtraktionen. På den måde sikrer vi altid, at vi returnerer en positiv forskydning.

3.2. Algoritme i Java

Lad os nu implementere det i Java. Først tilføjer vi en dechiffrere () metode til vores klasse:

String-afkodning (strengbesked, int-offset) {}

Lad os så kalde kryptering () metode med vores beregnede supplerende offset:

return cipher (meddelelse, 26 - (offset% 26));

Det er det, vores afkodningsalgoritme er oprettet. Lad os prøve det på eksemplet med offset 36:

String decipheredSentence = cipher.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", 36); assertThat (decipheredSentence) .isEqualTo ("han fortalte mig, at jeg aldrig kunne lære en lama at køre");

Som vi kan se, henter vi vores oprindelige besked.

4. Breaking the Ceasar Cipher

4.1. Forklaring

Nu hvor vi har dækket kryptering og dechiffrering af meddelelser ved hjælp af Caesar-krypteringen, kan vi dykke ned i, hvordan vi kan bryde det. Det vil sige, dechiffrere en krypteret meddelelse uden først at kende den anvendte forskydning.

For at gøre det bruger vi sandsynlighederne til at finde engelske bogstaver i en tekst. Ideen vil være at dechiffrere meddelelsen ved hjælp af forskydninger 0 til 25 og kontrollere, hvilket skift der præsenterer en brevfordeling svarende til den i engelske tekster.

For at bestemme ligheden af ​​to distributioner bruger vi Chi-kvadratstatistikken.

Chi-kvadratstatistikken giver et tal, der fortæller os, om to distributioner er ens eller ikke. Jo mindre antallet er, jo mere ens er de.

Så vi beregner Chi-firkanten for hver forskydning og returnerer derefter den med den mindste Chi-firkant. Dette skal give os den forskydning, der bruges til at kryptere beskeden.

Det skal vi dog huske på denne teknik er ikke skudsikker og hvis meddelelsen er for kort eller bruger ord desværre ikke repræsenterer en standard engelsk tekst, kan den returnere en forkert forskydning.

4.2. Definer distribution af basisbogstaver

Lad os nu se, hvordan vi implementerer den brudende algoritme i Java.

Lad os først og fremmest oprette en breakCipher () metode i vores CaesarCipher klasse, som returnerer forskydningen, der bruges til at kryptere en besked:

int breakCipher (streng besked) {}

Lad os derefter definere et array, der indeholder sandsynlighederne for at finde et bestemt bogstav i en engelsk tekst:

dobbelt [] 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};

Fra denne matrix kan vi beregne de forventede frekvenser af bogstaverne i en given meddelelse ved at gange sandsynlighederne med længden af ​​meddelelsen:

dobbelt [] expectLettersFrequences = Arrays.stream (englishLettersProbabilities) .map (probability -> probability * message.getLength ()) .toArray ();

For eksempel, i en meddelelse med længde 100, skal vi forvente brevet -en vises 7,3 gange og brevet e vises 13 gange.

4.3. Beregn Chi-firkanterne

Nu skal vi beregne Chi-firkanterne af dekrypteret meddelelsesbrevefordeling og standardfordeling af engelske bogstaver.

For at opnå dette skal vi importere Apache Commons Math3-biblioteket, der indeholder en hjælpeklasse til beregning af Chi-firkanter:

 org.apache.commons commons-math3 3.6.1 

Hvad vi skal gøre nu er at opret en matrix, der indeholder de beregnede Chi-firkanter for hver forskydning mellem 0 og 25.

Således dechifrerer vi den krypterede besked ved hjælp af hver forskydning og tæller derefter bogstaverne i den besked.

Endelig bruger vi ChiSquareTest # chiSquare metode til at beregne Chi-kvadratet mellem den forventede og observerede bogstavfordeling:

dobbelt [] chiSquares = nyt dobbelt [26]; for (int offset = 0; offset <chiSquares.length; offset ++) {String decipheredMessage = decipher (meddelelse, offset); lange [] bogstaverFrekvenser = observeredeLetterFrekvenser (decipheredMessage); dobbelt chiSquare = ny ChiSquareTest (). chiSquare (forventetLettersFrekvenser, bogstaverFrekvenser); chiSquares [offset] = chiSquare; } returner chiSquares;

Det observeretLettersFrekvenser () metode realiserer simpelthen et antal bogstaver -en til z i den videregivne besked:

lang [] observeretLettersFrequences (strengbesked) {return IntStream.rangeClosed ('a', 'z') .mapToLong (bogstav -> countLetter ((char) bogstav, besked)) .toArray (); } lang countLetter (tegn bogstav, streng besked) {return message.chars () .filter (tegn -> tegn == bogstav). antal (); }

4.4. Find den mest sandsynlige forskydning

Når alle Chi-firkanter er beregnet, kan vi returnere forskydningen, der matcher den mindste Chi-firkant:

int probableOffset = 0; for (int offset = 0; offset <chiSquares.length; offset ++) {System.out.println (String.format ("Chi-Square for offset% d:% .2f", offset, chiSquares [offset])); hvis (chiSquares [offset] <chiSquares [probableOffset]) {probableOffset = offset; }} returner sandsynlig Offset;

Selvom det ikke er nødvendigt at indtaste sløjfen med forskydning 0, da vi anser det for at være minimumet, før sløjfen startes, gør vi det for at udskrive dens Chi-kvadratværdi.

Lad os prøve denne algoritme på beskeden krypteret ved hjælp af offset 10:

int offset = algoritme.breakCipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo"); assertThat (offset) .isEqualTo (10); assertThat (algoritme.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", offset)) .isEqualTo ("han fortalte mig, at jeg aldrig kunne lære en lama at køre");

Som vi kan se, henter metoden den korrekte forskydning, som derefter kan bruges til at dechifrere meddelelsen og hente den oprindelige.

Her er de forskellige Chi-firkanter beregnet til denne særlige pause:

Chi-Square for forskydning 0: 210.69 Chi-Square for forskydning 1: 327.65 Chi-Square for forskydning 2: 255.22 Chi-Square for forskydning 3: 187.12 Chi-Square for forskydning 4: 734.16 Chi-Square for forskydning 5: 673.68 Chi Kvadrat til forskydning 6: 223,35 Chi-Kvadrat til forskydning 7: 111,13 Chi-Kvadrat til forskydning 8: 270,11 Chi-Kvadrat til forskydning 9: 153,26 Chi-Kvadrat til forskydning 10: 23,74 Chi-Kvadrat til forskydning 11: 643,14 Chi-Kvadrat til offset 12: 328.83 Chi-Square for offset 13: 434.19 Chi-Square for offset 14: 384.80 Chi-Square for offset 15: 1206.47 Chi-Square for offset 16: 138.08 Chi-Square for offset 17: 262.66 Chi-Square for offset 18 : 253.28 Chi-Square for forskydning 19: 280.83 Chi-Square for forskydning 20: 365.77 Chi-Square for forskydning 21: 107.08 Chi-Square for forskydning 22: 548.81 Chi-Square for forskydning 23: 255.12 Chi-Square for forskydning 24: 458.72 Chi-Square for forskydning 25: 325,45

Som vi kan se, er den ene for offset 10 klart mindre end de andre.

5. Konklusion

I denne artikel dækkede vi Caesar-krypteringen. Vi lærte at kryptere og dechiffrere en besked ved at flytte dens bogstaver med en given forskydning. Vi lærte også at bryde krypteringen. Og vi så alle Java-implementeringer, der tillader os at gøre det.

Koden til denne artikel kan findes på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found