Caesar-krypteringen i Java

1. Oversikt

I denne opplæringen skal vi utforske Caesar-krypteringen, en krypteringsmetode som skifter bokstaver i en melding for å produsere en annen, mindre lesbar.

Først og fremst vil vi gå gjennom krypteringsmetoden og se hvordan vi implementerer den i Java.

Så får vi se hvordan vi kan dechiffrere en kryptert melding, forutsatt at vi kjenner forskyvningen som ble brukt til å kryptere den.

Og til slutt vil vi lære å bryte en slik kryptering og dermed hente den originale meldingen fra den krypterte uten å kjenne forskyvningen som brukes.

2. Caesar Cipher

2.1. Forklaring

La oss først definere hva en kryptering er. En kryptering er en metode for å kryptere en melding, og har til hensikt å gjøre den mindre lesbar. Når det gjelder Caesar-krypteringen, er det en erstatningskryptering som forvandler en melding ved å skifte bokstavene med en gitt forskyvning.

La oss si at vi vil skifte alfabetet med 3 og deretter bokstav EN ville bli forvandlet til bokstav D, B til E, C til F, og så videre.

Her er fullstendig samsvar mellom originale og transformerte bokstaver for en forskyvning 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 transformasjonen går utover bokstaven Z, vi går tilbake til starten av alfabetet, slik at X, Y og Z blir forvandlet til EN, B og C, henholdsvis.

Derfor, hvis vi velger en forskyvning større eller lik 26, sløyfer vi, minst én gang, over hele alfabetet. La oss forestille oss at vi skifter en melding med 28, det betyr egentlig at vi skifter den med 2. Faktisk, etter å ha skiftet med 26, samsvarer alle bokstavene med seg selv.

Virkelig kan vi forvandle hvilken som helst forskyvning til en enklere forskyvning av utføre en modulo 26-operasjon på den:

forskyvning = forskyvning% 26

2.2. Algoritme i Java

La oss nå se hvordan du implementerer Caesar-krypteringen i Java.

La oss først lage en klasse CaesarCipher som vil holde en kryptering () metode for å ta en melding og en forskyvning som parametere:

public class CaesarCipher {String cipher (String message, int offset) {}}

Denne metoden vil kryptere meldingen ved hjelp av Caesar-krypteringen.

Vi antar her at forskyvninger er positive og meldinger bare inneholder små bokstaver og mellomrom. Så, det vi ønsker er å skifte alle alfabetiske tegn ved den angitte forskyvningen:

StringBuilder-resultat = nytt 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); } annet {resultat.append (tegn); }} returner resultat;

Som vi kan se, vi stoler på ASCII-kodene i alfabetets bokstaver for å nå vårt mål.

Først beregner vi posisjonen til gjeldende bokstav i alfabetet, og for det tar vi ASCII-koden og trekker ASCII-koden for bokstaven. en fra det. Deretter bruker vi forskyvningen til denne posisjonen, ved å bruke modulo forsiktig for å forbli i alfabetområdet. Og til slutt henter vi den nye karakteren ved å legge den nye posisjonen til ASCII-koden en.

La oss nå prøve denne implementeringen på meldingen "han fortalte meg at jeg aldri kunne lære en lama å kjøre" med en forskyvning på 3:

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

Som vi kan se, respekterer den krypterte meldingen samsvaret som ble definert tidligere for en forskyvning på 3.

Nå har dette spesifikke eksemplet spesifisiteten til ikke å overstige bokstaven z under transformasjonen, derfor ikke å måtte gå tilbake til starten av alfabetet. La oss derfor prøve igjen med en forskyvning på 10 slik at noen bokstaver blir kartlagt til bokstaver i begynnelsen av alfabetet, som t som vil bli kartlagt til d:

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

Det fungerer som forventet, takket være modulo-operasjonen. Den operasjonen ivaretar også større forskyvninger. La oss si at vi vil bruke 36 som offset, som tilsvarer 10, modulo-operasjonen sørger for at transformasjonen vil gi det samme resultatet.

3. Dechifrere

3.1. Forklaring

La oss nå se hvordan vi kan tyde en slik melding når vi vet at forskyvningen ble brukt til å kryptere den.

Faktisk, å dechiffrere en melding som er kryptert med Cæsarsiffer kan sees på som å kryptere den med en negativ forskyvning, eller også kryptere den med en komplementær forskyvning.

La oss si at vi har en melding kryptert med en forskyvning på 3. Deretter kan vi enten kryptere den med en forskyvning på -3 eller kryptere den med en forskyvning på 23. Uansett henter vi den opprinnelige meldingen.

Dessverre håndterer algoritmen vår ikke negativ forskyvning ut av boksen. Vi får problemer med å konvertere bokstaver som går tilbake til slutten av alfabetet (for eksempel å transformere bokstaven en inn i brevet z med en forskyvning på -1). Men vi kan beregne den komplementære forskyvningen, som er positiv, og deretter bruke algoritmen vår.

Så hvordan får man denne komplementære forskyvningen? Den naive måten å gjøre dette på vil være å trekke den opprinnelige forskyvningen fra 26. Selvfølgelig vil dette fungere for forskyvninger mellom 0 og 26, men ellers vil det gi negative resultater.

Det er hvor vi bruker modulo-operatøren igjen, direkte på den opprinnelige forskyvningen, før vi gjør subtraksjonen. På den måten sørger vi for alltid å returnere en positiv motregning.

3.2. Algoritme i Java

La oss nå implementere det i Java. Først legger vi til en tyde () metode til vår klasse:

Strengdekryptering (strengmelding, int-offset) {}

La oss så kalle kryptering () metode med vår beregnede komplementære forskyvning:

retur chiffer (melding, 26 - (forskyvning% 26));

Det er det, vår dekrypteringsalgoritme er satt opp. La oss 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 meg at jeg aldri kunne lære en lama å kjøre");

Som vi kan se, henter vi vår opprinnelige melding.

4. Breaking the Ceasar Cipher

4.1. Forklaring

Nå som vi har dekket kryptering og dechiffrering av meldinger ved hjelp av Caesar-krypteringen, kan vi dykke inn i hvordan vi kan bryte den. Det vil si, dechiffrere en kryptert melding uten å vite den brukte forskyvningen først.

For å gjøre det, bruker vi sannsynlighetene for å finne engelske bokstaver i en tekst. Tanken vil være å tyde meldingen ved å bruke forskyvning 0 til 25 og sjekke hvilket skifte som gir en bokstavfordeling som ligner på engelske tekster.

For å bestemme likheten mellom to distribusjoner, bruker vi Chi-kvadratstatistikken.

Chi-kvadratstatistikken vil gi et tall som forteller oss om to distribusjoner er like eller ikke. Jo mindre tallet er, desto mer like er de.

Så vi beregner Chi-firkanten for hver forskyvning og returnerer den med den minste Chi-firkanten. Dette skal gi oss forskyvningen som brukes til å kryptere meldingen.

Vi må imidlertid huske på det denne teknikken er ikke skuddsikker og hvis meldingen er for kort eller bruker ord som dessverre ikke er representativ for en standard engelsk tekst, kan den gi en feil forskyvning.

4.2. Definer distribusjon av basisbokstaver

La oss nå se hvordan vi implementerer den bruddalgoritmen i Java.

La oss først lage en breakCipher () metode i vår CaesarCipher klasse, som vil returnere forskyvningen som brukes til å kryptere en melding:

int breakCipher (strengmelding) {}

La oss deretter definere en matrise som inneholder sannsynlighetene for å finne en bestemt bokstav 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 matrisen vil vi kunne beregne forventede frekvenser av bokstavene i en gitt melding ved å multiplisere sannsynlighetene med lengden på meldingen:

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

For eksempel, i en melding med lengde 100, bør vi forvente brevet en skal vises 7,3 ganger, og brevet e skal vises 13 ganger.

4.3. Beregn Chi-kvadratene

Nå skal vi beregne Chi-kvadratene av dekryptert melding bokstav distribusjon og standard engelsk bokstaver distribusjon.

For å oppnå det, må vi importere Apache Commons Math3-biblioteket som inneholder en verktøyklasse for å beregne Chi-firkanter:

 org.apache.commons commons-math3 3.6.1 

Det vi trenger å gjøre nå er å lag en matrise som inneholder de beregnede Chi-kvadratene for hver forskyvning mellom 0 og 25.

Dermed vil vi tyde den krypterte meldingen ved hjelp av hver forskyvning, og deretter telle bokstavene i den meldingen.

Til slutt bruker vi ChiSquareTest # chiSquare metode for å beregne Chi-kvadratet mellom forventet og observert bokstavfordeling:

dobbel [] chiSquares = ny dobbel [26]; for (int offset = 0; offset <chiSquares.length; offset ++) {String decipheredMessage = decipher (message, offset); lange [] bokstaverFrekvenser = observerteBrevFrekvenser (decipheredMessage); dobbel chiSquare = ny ChiSquareTest (). chiSquare (forventet bokstaverFrekvenser, bokstaverFrekvenser); chiSquares [offset] = chiSquare; } returner chiSquares;

De observerte bokstaverFrekvenser () metoden realiserer ganske enkelt et antall bokstaver en til z i den sendte meldingen:

lang [] observerteLettersFrequences (strengmelding) {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. Finn den mest sannsynlige forskyvningen

Når alle Chi-firkantene er beregnet, kan vi returnere forskyvningen som samsvarer med den minste Chi-firkanten:

int sannsynlig Offset = 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 sannsynlig Offset;

Selv om det ikke er nødvendig å angi sløyfen med forskyvning 0, da vi anser det som minimum før vi starter sløyfen, gjør vi det for å skrive ut Chi-kvadratverdien.

La oss prøve denne algoritmen på meldingen kryptert med 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 meg at jeg aldri kunne lære en lama å kjøre");

Som vi kan se, henter metoden riktig forskyvning, som deretter kan brukes til å tyde meldingen og hente den opprinnelige.

Her er de forskjellige Chi-kvadratene beregnet for denne spesielle pause:

Chi-Square for offset 0: 210.69 Chi-Square for offset 1: 327.65 Chi-Square for offset 2: 255.22 Chi-Square for offset 3: 187.12 Chi-Square for offset 4: 734.16 Chi-Square for offset 5: 673.68 Chi- Kvadrat for forskyvning 6: 223.35 Chi-Kvadrat for forskyvning 7: 111.13 Chi-Kvadrat for forskyvning 8: 270.11 Chi-Kvadrat for forskyvning 9: 153.26 Chi-Kvadrat for forskyvning 10: 23.74 Chi-Kvadrat for forskyvning 11: 643.14 Chi-Kvadrat for 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 offset 19: 280.83 Chi-Square for offset 20: 365.77 Chi-Square for offset 21: 107.08 Chi-Square for offset 22: 548.81 Chi-Square for offset 23: 255.12 Chi-Square for offset 24: 458.72 Chi-Square for forskyvning 25: 325.45

Som vi kan se, er den for forskyvning 10 klart mindre enn de andre.

5. Konklusjon

I denne artikkelen tok vi for oss Caesar-krypteringen. Vi lærte å kryptere og dechiffrere en melding ved å skifte bokstavene med en gitt forskyvning. Vi lærte også å bryte krypteringen. Og vi så alle Java-implementeringene som lar oss gjøre det.

Koden til denne artikkelen finner du på GitHub.


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