15C: Caesar's JVTIVK JRCRU IVTZGV

Oefeningen 15A, 15B, en 15C kunnen in een willekeurige volgorde worden gemaakt.

Cryptografie is de kunst en de wetenschap van het verbergen van de betekenis van informatie, zodat alleen sommige mensen die informatie krijgen. In deze les zullen we één van de eenvoudigste cryptografische methoden introduceren, de Caesarcijfer (ook bekend als de caesarrotatie of kortweg Rot), en je zult een programma leren schrijven om de code te breken. Je doet dat in één keer (in tegenstelling tot les 15A, waar we de oplossing in sub-onderdelen opsplitsten).

Cryptografie
Bij Caesarcijfer wordt elke letter uit het alfabet vervangen door een andere letter. Nauwkeuriger, wanneer je een tekst wilt coderen, moet je een verschuivingsgetal S kiezen, een getal tussen 0 and 25. Dan vervang je elke letter in de tekst door de letter die S posities later in het alfabet staat en waarbij je teruggaat naar het begin van het alfabet wanneer je Z, het einde van het alfabet, hebt bereikt.

Voorbeeld

Stel dat we de geheime boodschap

JOIN ME AT EIGHT BY THE ZOO

willen coderen door middel van de verschuivingswaarde S=2. De encryptieregel zegt dat elke letter zal worden vervangen door degene die twee posities verder in het alfabet voor komt. Bijvoorbeeld, omdat het alfabet is ABCDEFGHIJKL..., zal de eerste letter J vervangen worden door de letter L. Verder zal de O vervangen worden door Q, de I door K, enz. Om de letter te coderen, dienen we terug te gaan naar het begin: na de Y komt de Z, dan de A, dus Ywordt vervangen door A. Evenzo wordt de Z vervangen door de B. De gecodeerde versie van onze geheime boodschap wordt aldus:

LQKP OG CV GKIJV DA VJG BQQ

Wanneer de een of andere spion deze boodschap ziet, zal hij niet onmiddellijk begrijpen waar het over gaat.

Oefening met Kort Antwoord: Spy Coder

Wat is het resultaat van het versleutelen van SPY CODER met de verschuivingswaarde S = 5? (Gebruik hoofdletters.) Wanneer je wilt, kun je een programma schrijven in de console om dit uit rekenen. Het kan later van pas komen.
Jouw antwoord:

Correct!

Coderen

Wanneer je vrienden de boodschap hebben gekregen en zij het geheime verschuivingsgetal S kennen, is het voor hen gemakkelijk om de boodschap te ontcijferen: elke letter moet worden vervangen door degene die S plaatsen eerder in het alfabet voor komt. Bijvoorbeeld, wanneer L moet worden gedecodeerd, ga je twee stappen terug in het alfanet en je vindt J, waarvan ze dan weten dat dat de eerste letter is van de geheime boodschap. Opnieuw moeten ze het alfabet zien als een cirkel, waarbij de Z voor de A komt.

Oefening met Kort Antwoord: Spy Decoder

Wanneer de gecodeerde boodschap HUD is, en de verschuivingswaarde S=6, wat is dan de origineel boodschap? (Gebruik hoofdletters.)
Jouw antwoord:

Correct!

Voor de Bad Guys werken

Je bent ingehuurd door een spion om te helpen bij het ontcijferen van een gecodeerde boodschap waarbij een verschuivingswaarde is gebruikt. Jammer genoeg weet de spion de waarde van S niet. Je gaat statistisch onderzoek gebruiken om een programma te schrijven dat een goede kans geeft de juiste waarde van S op te sporen.

Bij onze methode maken we gebruik van letter frequentie analyse. In het Engels komen sommige letters (zoals de E) vaak voor en sommige heel weinig (zoals de J). Hier volgt een frequentietabel, gebaseerd op het tellen van letters in een grote hoeveelheid tekst.

Zo is, bijvoorbeeld, de frequentie van L .0402=4.02%, en dat betekent dat in een doorsnee engelse tekst 4.02% van de letters L zijn.

Noem de juist-waarde van een letter de waarde ervan in de tabel hierboven. Definieer dan in onze statistische methode de juist-waarde van een zin als de som van de juist-waarde van elk van de letters. Zo is bijvoorbeeld de juist-waarde van de string GOOD

juist-waarde("GOOD") = .0202 + .0751 + .0751 + .0425 = .2129

Nu is het idee van frequentie analyse dat strings met een hogere juist-waarde waarschijnlijker een engelse tekst weergeven. Wanneer bijvoorbeeld, de spion de gecodeerde boodschap "JRRG" ziet, dan is het zowel mogelijk dat de originele tekst "GOOD" is met verschuivingswaarde S=3, als "IQQF" met S=1. Maar de juist-waarde van "IQQF" is

juist-waarde("IQQF") = .0697 + .0009 + .0009 + .0223 = .0938

en omdat .0938 < .2129, dient je programma de conclusie te trekken dat het meer waarschijnlijk is dat GOOD de juiste boodschap is dan IQQF.

Strings meten met behulp van zijn juist-waarde is niet perfect. Stel dat de geheime boodschap JAZZ was en de geheime verschuivingswaarde S=10, zodat de gecodeerde tekst TKJJ was. Wanneer je TKJJ in je programma invoert dan zal ook S=10 aan bod komen, met JAZZ als een mogelijkheid met juist-zijn van .0846, maar de beste is S=5, waarbij hoort OFEE met een juist-zijn van .3514 als de beste gok voor de geheime boodschap. Je programma geeft dus het niet engelse woord OFEE. (Frequentie analyse van dit type werkt beter naarmate de geheime boodschap langer is.)

Programmeeroefening: Auto-Decryption

Schrijf een programma met de volgende specificaties. Eerst moet het één regel tekst, de gecodeerde boodschap, invoeren. Deze bestaat uit hoofdletters en spaties. Je programma moet proberen de boodschap te decoderen door alle mogelijke 26 waarden van de verschuiving S toe te passen. Uit deze 26 mogelijkheden moet je degene printen met de hoogste juist-waarde.

Om het je gemakkelijker te maken zullen we de variabele letterGoodness voor je definieren. Het is een lijst van lengte 26 met daarin de waarden van de frequentietabel hierboven,

letterGoodness = [.0817,.0149,.0278,.0425,.1270,.0223,.0202,...

Klik hier voor wat algene adviezen.

Je moet een account aanmaken en inloggen om een vraag te kunnen stellen.

print(letterGoodness) #testing... it's predefined # verwijder dit commentaar en type hier je code

Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Meer acties... Geschiedenis Reset code to default Help

De oplossing hierboven wordt een brute force oplossing genoemd omdat je alle 26 mogelijkheden probeert. Je kunt het ook handmatig oplossen wanneer je dat zou willen. Aan de andere kant zijn moderne cryptographische protocollen, zo ontworpen dat bruce force solutions falen, zelfs als je zeer snelle computers gebruikt om alle mogelijkheden uit te proberen.

Wanneer je wilt kun je dit decodeer systeem preciezer maken. Je kunt aandacht besteden aan andere engelstalige statistische gegevens, zoals "welke letters komen in paren naast elkaar voor" of "welke letters komen het vaakst bij het begin van een woord voor". Dit is ook nuttig voor meer algemene substitution ciphers, waar letters andere letters vervangen, maar niet op een cyclische manier. Voor zulke systemen werkt brute force niet, omdat er 26*25*...*1 mogelijke substitution ciphers zijn, wat neer komt op ongeveer 4 * 10²⁶ (veertig quadriljard).

Deze les is klaar! Als je wilt kun je je vrienden een gecodeerde boodschap sturen om dat te vieren.