Het Caesarcijfer op Java
1. Overzicht
In deze tutorial gaan we het Caesar-cijfer verkennen, een versleutelingsmethode die letters van een bericht verschuift om een ander, minder leesbaar bericht te produceren.
Allereerst zullen we de coderingsmethode doorlopen en zien hoe we deze in Java kunnen implementeren.
Vervolgens zullen we zien hoe we een versleuteld bericht kunnen ontcijferen, op voorwaarde dat we de offset kennen die is gebruikt om het te versleutelen.
En tot slot zullen we leren hoe we een dergelijk cijfer kunnen breken en zo het originele bericht van het versleutelde bericht kunnen ophalen zonder de gebruikte offset te kennen.
2. Caesarcijfer
2.1. Uitleg
Laten we allereerst definiëren wat een cijfer is. Een cijfer is een methode om een bericht te versleutelen, bedoeld om het minder leesbaar te maken. Wat betreft het Caesar-cijfer, het is een vervangingscijfer dat een bericht transformeert door de letters met een bepaalde offset te verschuiven.
Laten we zeggen dat we het alfabet met 3 willen verschuiven, en dan met de letter EEN zou worden omgezet in letter D, B naar E., C naar F., enzovoorts.
Hier is de volledige overeenkomst tussen originele en getransformeerde letters voor een offset van 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 CZoals we kunnen zien, zodra de transformatie verder gaat dan de letter Z, we gaan terug naar het begin van het alfabet, zodat X, Y en Z worden omgevormd tot EEN, B en C, respectievelijk.
Als we daarom een offset kiezen die groter is dan of gelijk is aan 26, lussen we minstens één keer over het hele alfabet. Laten we ons voorstellen dat we een bericht met 28 verschuiven, dat betekent eigenlijk dat we het met 2 verschuiven. Inderdaad, na het verschuiven met 26 komen alle letters overeen met zichzelf.
Echt, we kunnen elke offset omzetten in een eenvoudigere offset door het uitvoeren van een modulo 26-bewerking:
offset = verschuiving% 262.2. Algoritme in Java
Laten we nu eens kijken hoe we het Caesar-cijfer in Java kunnen implementeren.
Laten we eerst een klas maken CaesarCipher dat zal een cijfer() methode met een bericht en een offset als parameters:
openbare klasse CaesarCipher {Stringcipher (String-bericht, int offset) {}}Die methode zal het bericht versleutelen met behulp van het Caesar-cijfer.
We nemen hier aan dat offsets positief zijn en dat berichten alleen kleine letters en spaties bevatten. Vervolgens willen we alle alfabetische tekens met de opgegeven offset verschuiven:
StringBuilder-resultaat = nieuwe 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 {resultaat.append (teken); }} resultaat retourneren;Zoals we kunnen zien, we vertrouwen op de ASCII-codes van de alfabetletters om ons doel te bereiken.
Eerst berekenen we de positie van de huidige letter in het alfabet, en daarvoor nemen we de ASCII-code en trekken we de ASCII-code van de letter af een van het. Vervolgens passen we de offset toe op deze positie, waarbij we voorzichtig de modulo gebruiken om in het alfabetbereik te blijven. En tot slot halen we het nieuwe karakter op door de nieuwe positie toe te voegen aan de ASCII-lettercode een.
Laten we deze implementatie nu proberen met het bericht "hij vertelde me dat ik een lama nooit zou kunnen leren autorijden" met een offset van 3:
CaesarCipher-cijfer = nieuwe CaesarCipher (); String cipheredMessage = cipher.cipher ("hij vertelde me dat ik een lama nooit zou kunnen leren autorijden", 3); assertThat (cipheredMessage) .isEqualTo ("kh wrog ph l frxog qhyhu whdfk d oodpd wr gulyh");Zoals we kunnen zien, respecteert het gecodeerde bericht de eerder gedefinieerde matching voor een offset van 3.
Dit specifieke voorbeeld heeft de specificiteit om de letter niet te overschrijden z tijdens de transformatie, dus niet terug hoeven te gaan naar het begin van het alfabet. Laten we het dus opnieuw proberen met een offset van 10, zodat sommige letters worden toegewezen aan letters aan het begin van het alfabet, zoals t die zal worden toegewezen aan d:
String cipheredMessage = cipher.cipher ("hij vertelde me dat ik een lama nooit zou kunnen leren autorijden", 10); assertThat (cipheredMessage) .isEqualTo ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo");Het werkt zoals verwacht, dankzij de modulo-bediening. Die operatie zorgt ook voor grotere offsets. Laten we zeggen dat we 36 als offset willen gebruiken, wat gelijk is aan 10, de modulo-bewerking zorgt ervoor dat de transformatie hetzelfde resultaat zal geven.
3. Ontcijferen
3.1. Uitleg
Laten we nu eens kijken hoe we zo'n bericht kunnen ontcijferen als we de offset kennen die wordt gebruikt om het te versleutelen.
Eigenlijk, het ontcijferen van een bericht versleuteld met Caesar-codering kan worden gezien als het coderen met een negatieve offset, of ook als het coderen met een complementaire offset.
Dus, laten we zeggen dat we een bericht hebben versleuteld met een offset van 3. Vervolgens kunnen we het ofwel versleutelen met een offset van -3 of versleutelen met een offset van 23. In beide gevallen halen we het originele bericht op.
Helaas verwerkt ons algoritme geen negatieve offset uit de doos. We zullen problemen ondervinden bij het converteren van letters die teruglopen naar het einde van het alfabet (bijvoorbeeld het transformeren van de letter een in de brief z met een offset van -1). Maar we kunnen de complementaire offset berekenen, die positief is, en vervolgens ons algoritme gebruiken.
Dus, hoe verkrijg je deze complementaire compensatie? De naïeve manier om dit te doen zou zijn om de oorspronkelijke offset af te trekken van 26. Dit werkt natuurlijk voor offsets tussen 0 en 26, maar anders geeft het negatieve resultaten.
Dat is waar we zullen opnieuw de modulo-operator gebruiken, direct op de originele offset, voordat we de aftrekking doen. Zo zorgen we ervoor dat er altijd een positieve compensatie wordt geretourneerd.
3.2. Algoritme in Java
Laten we het nu in Java implementeren. Eerst voegen we een ontcijferen() methode voor onze klas:
String-ontcijfering (String-bericht, int offset) {}Laten we dan de cijfer() methode met onze berekende complementaire offset:
retourcijfer (bericht, 26 - (offset% 26));Dat is alles, ons ontcijferingsalgoritme is ingesteld. Laten we het proberen met het voorbeeld met offset 36:
String decipheredSentence = cipher.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", 36); assertThat (decipheredSentence) .isEqualTo ("hij vertelde me dat ik een lama nooit zou kunnen leren autorijden");Zoals we kunnen zien, halen we ons oorspronkelijke bericht terug.
4. Het Ceasar-cijfer breken
4.1. Uitleg
Nu we het coderen en ontcijferen van berichten met behulp van het Caesar-cijfer hebben behandeld, kunnen we onderzoeken hoe we het kunnen breken. Dat wil zeggen, een gecodeerd bericht ontcijferen zonder eerst de gebruikte offset te kennen.
Om dat te doen, maken we gebruik van de kansen om Engelse letters in een tekst te vinden. Het idee is om het bericht te ontcijferen met behulp van offsets 0 tot 25 en te controleren welke ploeg een letterverdeling geeft die vergelijkbaar is met die van Engelse teksten.
Om de gelijkenis van twee verdelingen te bepalen, gebruiken we de Chi-kwadraat-statistiek.
De Chi-kwadraat-statistiek geeft een getal dat ons vertelt of twee verdelingen vergelijkbaar zijn of niet. Hoe kleiner het aantal, hoe meer ze op elkaar lijken.
Dus we berekenen de Chi-kwadraat voor elke offset en retourneren die met de kleinste Chi-kwadraat. Dit zou ons de offset moeten geven die wordt gebruikt om het bericht te coderen.
Daar moeten we echter rekening mee houden deze techniek is niet kogelvrij en als het bericht te kort is of woorden gebruikt die helaas niet representatief zijn voor een standaard Engelse tekst, kan het een verkeerde offset opleveren.
4.2. Definieer de basisbrievenverdeling
Laten we nu kijken hoe we het breekalgoritme in Java kunnen implementeren.
Laten we eerst een breakCipher () methode in onze CaesarCipher class, die de offset retourneert die wordt gebruikt om een bericht te versleutelen:
int breakCipher (String-bericht) {}Laten we vervolgens een array definiëren met de kansen om een bepaalde letter in een Engelse tekst te vinden:
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};Uit deze array kunnen we de verwachte frequenties van de letters in een bepaald bericht berekenen door de waarschijnlijkheden te vermenigvuldigen met de lengte van het bericht:
dubbel [] verwachtLettersFrequencies = Arrays.stream (englishLettersProbabilities) .map (waarschijnlijkheid -> waarschijnlijkheid * message.getLength ()) .toArray ();In een bericht met een lengte van 100 moeten we bijvoorbeeld de letter verwachten een om 7,3 keer te verschijnen, en de brief e om 13 keer te verschijnen.
4.3. Bereken de Chi-kwadraten
Nu gaan we de chi-kwadraten van de distributie van ontcijferde berichtbrieven en standaard Engelse brievenverdeling berekenen.
Om dat te bereiken, moeten we de Apache Commons Math3-bibliotheek importeren die een utility-klasse bevat om Chi-squares te berekenen:
org.apache.commons commons-math3 3.6.1 Wat we nu moeten doen, is maak een array met de berekende Chi-kwadraten voor elke offset tussen 0 en 25.
We ontcijferen dus het gecodeerde bericht met elke offset en tellen vervolgens de letters in dat bericht.
Ten slotte gebruiken we de ChiSquareTest # chiSquare methode om de Chi-kwadraat tussen de verwachte en waargenomen lettersverdeling te berekenen:
double [] chiSquares = nieuwe double [26]; for (int offset = 0; offset <chiSquares.length; offset ++) {String decipheredMessage = decipher (bericht, offset); long [] lettersFrequencies = waargenomenLettersFrequencies (decipheredMessage); double chiSquare = nieuwe ChiSquareTest (). chiSquare (verwachteLettersFrequenties, lettersFrequenties); chiSquares [offset] = chiSquare; } retourneer chiSquares;De waargenomenLettersFrequencies () methode realiseert eenvoudig een telling van letters een naar z in het doorgegeven bericht:
lang [] observationLettersFrequencies (String bericht) {return IntStream.rangeClosed ('a', 'z') .mapToLong (letter -> countLetter ((char) letter, bericht)) .toArray (); } lange countLetter (char letter, String bericht) {return message.chars () .filter (character -> character == letter) .count (); }4.4. Vind de meest waarschijnlijke compensatie
Zodra alle Chi-kwadraten zijn berekend, kunnen we de offset retourneren die overeenkomt met de kleinste Chi-kwadraat:
int probableOffset = 0; for (int offset = 0; offset <chiSquares.length; offset ++) {System.out.println (String.format ("Chi-Square voor offset% d:% .2f", offset, chiSquares [offset])); if (chiSquares [offset] <chiSquares [probableOffset]) {probableOffset = offset; }} retourneer probableOffset;Hoewel het niet nodig is om de lus met offset 0 in te voeren, omdat we dit als het minimum beschouwen voordat de lus wordt gestart, doen we het om de Chi-kwadraatwaarde af te drukken.
Laten we dit algoritme proberen op het bericht dat is gecodeerd met offset 10:
int offset = algoritm.breakCipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo"); assertThat (offset) .isEqualTo (10); assertThat (algoritm.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", offset)) .isEqualTo ("hij vertelde me dat ik een lama nooit zou kunnen leren rijden");Zoals we kunnen zien, haalt de methode de juiste offset op, die vervolgens kan worden gebruikt om het bericht te ontcijferen en het originele op te halen.
Hier zijn de verschillende Chi-kwadraten berekend voor deze specifieke pauze:
Chi-Square voor offset 0: 210,69 Chi-Square voor offset 1: 327,65 Chi-Square voor offset 2: 255,22 Chi-Square voor offset 3: 187,12 Chi-Square voor offset 4: 734,16 Chi-Square voor offset 5: 673,68 Chi- Vierkant voor offset 6: 223,35 Chi-kwadraat voor offset 7: 111,13 Chi-kwadraat voor offset 8: 270,11 Chi-kwadraat voor offset 9: 153,26 Chi-kwadraat voor offset 10: 23,74 Chi-kwadraat voor offset 11: 643,14 Chi-kwadraat voor offset 12: 328,83 Chi-Square voor offset 13: 434,19 Chi-Square voor offset 14: 384,80 Chi-Square voor offset 15: 1206,47 Chi-Square voor offset 16: 138,08 Chi-Square voor offset 17: 262,66 Chi-Square voor offset 18 : 253,28 Chi-Square voor offset 19: 280,83 Chi-Square voor offset 20: 365,77 Chi-Square voor offset 21: 107,08 Chi-Square voor offset 22: 548,81 Chi-Square voor offset 23: 255,12 Chi-Square voor offset 24: 458,72 Chi-Square voor offset 25: 325,45Zoals we kunnen zien, is die voor offset 10 duidelijk kleiner dan de andere.
5. Conclusie
In dit artikel hebben we het Caesar-cijfer behandeld. We hebben geleerd hoe we een bericht kunnen coderen en ontcijferen door de letters met een bepaalde offset te verschuiven. We hebben ook geleerd hoe we het cijfer kunnen breken. En we hebben alle Java-implementaties gezien waarmee we dat kunnen doen.
De code van dit artikel is te vinden op GitHub.
