Hopp rett til oppgavene

Hva er en “Cipher”?

Har du noen gang hatt lyst til å skrive en hemmelig beskjed til en venn, slik at ingen andre kan forstå den? Da trenger du et Cipher, eller chiffer på Norsk! Et chiffer er rett og slett en metode som gjør vanlig tekst om til “kode” ved å bytte ut tegn (ofte bokstaver) med andre tegn. Resultatet ser ut som tull for de som ikke vet hvordan koden fungerer. Poenget er at bare de som kjenner nøkkelen (regelen for å bytte ut bokstavene) kan gjøre koden forståelig igjen. Med andre ord: chiffer gjør hemmelige beskjeder mulig, enten det er barndommens lek med hemmelig språk eller ekte spioner som sender krypterte meldinger. 😄

Det finnes mange typer chiffer – noen bruker tall, noen bruker symboler, og moderne datakryptering bruker svært kompliserte algoritmer. Disse kompliserte algoritmene krever svært komplisert matematikk, så vi kan se på noen enklere algoritmer først!

Monoalfabetiske Chiffer

La oss først se på noen av de enkleste (og eldste) kodemetodene som finnes: monoalfabetiske chiffer.

Monoalfabetisk høres kanskje ut som et vanskelig ord, men vi kan dele det opp: mono betyr “én”, og alfabetisk handler om alfabetet.

Altså, monoalfabetiske chiffer er koder der man bruker ett enkelt “krypteringsalfabet” for hele meldingen. Det vil si at hver bokstav i den originale teksten alltid blir byttet ut med den samme bokstaven gjennom hele den krypterte meldingen.

For eksempel, har du bestemt at A skal byttes med X, da blir alle A-ene i teksten gjort om til X.

Cæsar-chiffer

Det klassiske eksempelet på et monoalfabetisk chiffer er Cæsar-chifferet (oppkalt etter Julius Cæsar). Dette er basically en regel om å “skifte” alle bokstavene et visst antall plasser bortover i alfabetet. Visstnok så brukte Cæsar selv et skifte på 3 bokstaver i sine hemmelige meldinger. Det fungerer sånn at A blir til D, B blir til E, C blir til F, og så videre gjennom alfabetet. (Når man går forbi Z, starter man på A igjen.) En melding som ABC ville dermed bli til DEF hvis vi bruker Cæsars metode.

Slik fungerer Cæsar-chifferet i praksis:

• Velg en nøkkel: Bestem deg for et hemmelig tall (for eksempel 3) som angir hvor mange plasser du skal flytte hver bokstav.
• Bytt ut hver bokstav: For hver bokstav i den originale meldingen, finn bokstaven som ligger så mange plasser etter den i alfabetet (for nøkkel 3 blir A til D, B til E, osv. – husk å gå rundt til A igjen etter Z om nødvendig). Eventuelt kan du også ta med Æ, Ø og Å, men dette blir litt mer komplisert.
• Kryptert melding: Erstatt bokstavene og skriv den nye meldingen med de “skiftede” bokstavene. Vips – du har en uleselig, hemmelig tekst som bare de med nøkkelen kan forstå!
• For å dekryptere (altså gjøre det om til leselig tekst igjen) gjør man bare det motsatte skiftet tilbake. Hvis du vet nøkkelen (f.eks. 3), så er det like lett å lese meldingen ved å flytte bokstavene 3 tilbake i alfabetet.

Monoalfabetiske chiffer er en fantastisk måte å lære prinsippet bak kryptering. De er enkle og viser hvordan vi kan bruke en enkel regel (en nøkkel) til å gjøre om en forståelig tekst til noe mystisk og uforståelig – og tilbake igjen. Så neste gang du vil sende en venn en hemmelig beskjed, kan du bruke Cæsar chifferet! Kanskje dere kan lage deres egen variant av Cæsars hemmelige alfabet? 🔐✨

Oppgaver

Oppgave 1.1 - Cæsar Chiffer Enkryptering

Nå skal vi faktisk skrive noe kode! Vi skal begynne enkelt med å lage enkrypteringen, basert på teorien bør det være ganske straightforward.

Implementer enkryptering med Cæsar Chiffer ved å bruke en funksjon som tar inn tekst og et tall som er “nøkkelen”, altså hvor mye alfabetet skal roteres med.

def caesar_cipher(text, shift):
    result = ""
    for char in text:
        if char.isalpha():
        # finn ut startpunktet basert på store og små bokstaver
        start = ord('A') if char.isupper() else ord('a')
        # Den vanskelige shifte-utregningen
        result += chr((ord(char) - start + shift) % 26 + start)
    else:
        result += char
    return result

Oppgave 1.2 - Cæsar Chiffer Dekryptering

Dekryptering er bare å gjøre den motsatte utregningen til enkryptering. Du trekker fra offset i stedet for å legge til.

def caesar_decrypt(text, shift):
    return caesar_cipher(text, 26 - shift)

Andre Monoalfabetiske Chiffer/Ciphers (ex. Atbash)

Det finnes andre monoalfabetiske chiffer også! En av de enklere er den som kalles “Atbash” Chiffer.

Hvordan fungerer Atbash?

Denne er svært enkel, i stedet for en rotasjon så kartlegges bokstaver til det motsatte alfabetet. Her er en tabell som viser kartleggingen:

Oppgave 1.3 - Atbash Chiffer Enkryptering og Dekryptering

Det kjekke med Atbash er at siden enkryptering er en 1 til 1 transformering, så fungerer den direkte i revers. Altså, hvis du har lagd enkrypteringen så har du også, automatisk lagd dekrypteringen.

Hvordan kan dette gjøres i praksis?

Du kan enten trekke fra bokstaven i forhold til Z, eller lage en “Look-up” table. Altså, det betyr en tabell eller dictionary som inneholder alle bokstavene fra a til z og hva de skal bli. Dette kan være god løsning hvis dere vil lage en annen type enkryptering.

letters = {
    'a': 'z'
    'b': 'y'
    'c': 'x'
    'd': 'w'
    # ... legg til resten av bokstavene nedover
}

Ved hjelp av denne tabellen kan du gå igjennom bokstav for bokstav, så hente ut verdien per bokstav fra lookup-tabellen, så skrive den ut. Hva må du gjøre for store og små bokstaver?

Del 2 - Kryptoanalyse av Monoalfabetiske Chiffer

I denne delen skal dere prøve å lage en algoritme for å “cracke” en Cæsar chiffer, altså ta en kryptert tekst, deretter, få ut den orginale teksten uten å vite nøkkelen.

Dette kan gjøres noenlunde manuelt, eller så kan du prøve å ta i bruk enkel “cryptanalysis”. Dette er et konsept som vi skal se dypere på senere, men for nå skal vi bare se på en av de enkleste måtene: Frekvensanalyse (frequency analysis). Du kan lese mer om dette konseptet her: Frequency Analysis eller her Wikipedia - frequency analysis.

Denne metoden kan brukes i mer en bare cæsar-chiffer, den kan brukes i mer kompliserte algoritmer også, men cæsar-chiffer er såpass enkel at frekvensanalyse er trivielt.

In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers.

Frequency analysis is based on the fact that, in any given stretch of written language, certain letters and combinations of letters occur with varying frequencies. Moreover, there is a characteristic distribution of letters that is roughly the same for almost all samples of that language. For instance, given a section of English language, E, T, A and O are the most common, while Z, Q, X and J are rare. Likewise, TH, ER, ON, and AN are the most common pairs of letters termed bigrams or digraphs), and SS, EE, TT, and FF are the most common repeats. The nonsense phrase ETAOIN SHRDLU represents the 12 most frequent letters in typical English language text.

In some ciphers, such properties of the natural language plaintext are preserved in the ciphertext, and these patterns have the potential to be exploited in a ciphertext-only attack.

xcrgneipcpanhxhugtfjtcrnpcpanhxhxhiwthijsnduiwtugtfjtcrnduatiitghdgvgdjehduatiitghxcprxewtgitmiiwtbtiwdsxhjhtsphpcpxsidqgtpzxcvraphhxrparxewtghugtfjtcrnpcpanhxhxhqphtsdciwtupriiwpixcpcnvxktchigtirwdulgxiitcapcvjpvtrtgipxcatiitghpcsrdbqxcpixdchduatiitghdrrjglxiwkpgnxcvugtfjtcrxthbdgtdktgiwtgtxhprwpgpritgxhixrsxhigxqjixdcduatiitghiwpixhgdjvwaniwthpbtudgpabdhipaahpbeathduiwpiapcvjpvtudgxchipcrtvxktcphtrixdcdutcvaxhwapcvjpvttippcsdpgtiwtbdhirdbbdclwxatofmpcsypgtgpgtaxztlxhtiwtgdcpcspcpgtiwtbdhirdbbdcepxghduatiitghitgbtsqxvgpbhdgsxvgpewhpcshhttiipcsuupgtiwtbdhirdbbdcgtetpihiwtcdchtchtewgphttipdxchwgsajgtegthtcihiwtbdhiugtfjtciatiitghxcinexrpatcvaxhwapcvjpvtitmixchdbtrxewtghhjrwegdetgixthduiwtcpijgpaapcvjpvteapxcitmipgtegthtgktsxciwtrxewtgitmipcsiwthtepiitgchwpktiwteditcixpaidqttmeadxitsxcprxewtgitmidcanpiiprz

Oppgave 2.1 - Lage en frekvenstabell

I en python fil, opprett en frekvens-tabell av bokstavene i det engelske språket. Du kan prøve å finne denne selv, men hvis du ikke gidder dette, forstår vi dette!

Hvis du absolutt ønsker å finne den selv, kan du gjøre som i Oppgave 2.2, men på en veldig stor tekst.

english_letter_frequency = {
    'E': 12.70, 
    'T': 9.06, 
    'A': 8.17, 
    'O': 7.51, 
    'I': 6.97, 
    'N': 6.75, 
    'S': 6.33, 
    'H': 6.09, 
    'R': 5.99, 
    'D': 4.25, 
    'L': 4.03, 
    'C': 2.78, 
    'U': 2.76, 
    'M': 2.41, 
    'W': 2.36, 
    'F': 2.23, 
    'G': 2.02, 
    'Y': 1.97, 
    'P': 1.93, 
    'B': 1.29, 
    'V': 0.98, 
    'K': 0.77, 
    'J': 0.15, 
    'X': 0.15, 
    'Q': 0.10, 
    'Z': 0.07
}

Oppgave 2.2 - Telle frekvensen av bokstaver i tekst

Nå skal vi lage en algoritme som skal finne frekvensen av bokstaver i en gitt tekst.

Oppgave 2.3 - Sammenligne frekvensen av en tekst med den ekte frekvensen

Når du har funnet frekvensen til alle bokstavene i teksten kan du lage en funksjon som finner “avstanden”. Hæ? Hva menes med det?!

Du kan se for deg at frekvensen til for eksempel E i teksten kommer til å være et tall. Du kan finne “avstanden” denne har med den faktiske frekvensen, som er 12.70. Eksempel: Frekvensen er 9.63, hva er avstanden? Avstanden kommer til å være den absolutte verdien (negative tall blir positive) mellom disse to verdiene: \(12.70 - 9.63 = 3.07\).

Lag en funksjon som går igjennom hver av bokstavene å finner avstanden. Legg deretter alle avstandene sammen til en “total” avstand.

Oppgave 2.4 - “Cracke” Cæsar-chiffer

Nå skal vi til slutt sette sammen alt vi har gjort så langt! Nå skal vi “cracke” en Cæsar-chiffer.

Lag et program som “cracker” en Cæsar-chiffer! Uten bruker-innflytelse skal du kunne hive inn en kryptert tekst å hente ut den dekrypterte teksten uten å trenge en nøkkel.