Hopp rett til oppgåvene

Kva er eit “Cipher”?

Har du nokon gong hatt lyst til å skriva ei hemmeleg melding til ein ven, slik at ingen andre kan forstå ho? Då treng du eit Cipher, eller chiffer på Norsk! Eit chiffer er rett og slett ei metode som gjer vanleg tekst om til “kode” ved å byta ut teikn (ofta bokstavar) med andre teikn. Resultatet ser ut som tull for dei som ikkje veit korleis koden fungerer. Poenget er at berre dei som kjenner nøkkelen (regelen for å byta ut bokstavane) kan gjera koden forståeleg att. Med andre ord: chiffer gjer hemmelege meldingar mogleg, anten det er barndommens lek med hemmeleg språk eller ekte spionar som sender krypterte meldingar. 😄

Det finst mange slag av chiffer – nokre nyttar tal, nokre nyttar symbol, og moderne datakryptering nyttar svært kompliserte algoritmar. Desse kompliserte algoritmane krev svært komplisert matematikk, so me kan sjå på nokre enklare algoritmar fyrst!

Monoalfabetiske Chiffer

Lat oss fyrst sjå på nokre av dei enklaste (og eldste) kodemetodane som finst: monoalfabetiske chiffer.

Monoalfabetisk høyrast kanskje ut som eit vanskeleg ord, men me kan dele det opp: mono tyder “ein”, og alfabetisk handlar om alfabetet.

Altså, monoalfabetiske chiffer er koder der ein brukar eit enkelt “krypteringsalfabet” for heile meldinga. Det vil seia at kvar bokstav i den originale teksten alltid vert bytt ut med den same bokstaven gjennom heile den krypterte meldinga.

For døme, har du bestemt at A skal bytast med X, då vert alle A-ane i teksten gjort om til X.

Cæsar-chiffer

Det klassiske dømet på eit monoalfabetisk chiffer er Cæsar-chifferet (kalla opp etter Julius Cæsar). Dette er i botnen ei regel om å «skifte» alle bokstavane eit visst tal plassar bortover i alfabetet. Visstnok så brukte Cæsar sjølv eit skifte på 3 bokstavar i sine hemmelege meldingar. Det verkar slik at A vert til D, B vert til E, C vert til F, og so vidare gjennom alfabetet. (Når ein går forbi Z, startar ein på A att.) Ei melding som ABC ville dermed verte til DEF om me brukar Cæsars metode.

Slik verkar Cæsar-chifferet i praksis:

• Vel ein nøkkel: Bestem deg for eit hemmeleg tal (til dømes 3) som angir kor mange plassar du skal flytta kvar bokstav.
• Bytt ut kvar bokstav: For kvar bokstav i den opphavlege meldinga, finn bokstaven som ligg så mange plassar etter han i alfabetet (for nøkkel 3 vert A til D, B til E, osv. – hugs å gå rundt til A att etter Z om naudsynt). Eventuelt kan du òg taka med Æ, Ø og Å, men dette vert litt meir komplisert.
• Kryptert melding: Erstatt bokstavane og skriv den nye meldinga med dei “skifte” bokstavane. Vips – du har ein uleseleg, hemmeleg tekst som berre dei med nøkkelen kan forstå!
• For å dekryptera (altså gjera det om til leseleg tekst att) gjer ein berre det motsette skiftet tilbake. Om du veit nøkkelen (t.d. 3), så er det like lett å lesa meldinga ved å flytta bokstavane 3 tilbake i alfabetet.

Monoalfabetiske chiffer er ein fantastisk måte å lære prinsippet bak kryptering. Dei er enkle og syner korleis me kan bruke ei enkel regel (ein nøkkel) til å gjere om ein forståeleg tekst til noko mystisk og uforståeleg – og attende igjen. So neste gong du vil senda ein ven ein hemmeleg bodskap, kan du bruke Cæsar-chifferet! Kanskje de kan lage dykkar eiga variant av Cæsars hemmelege alfabet? 🔐✨

Oppgåver

Oppgåve 1.1 – Cæsar Chiffer Kryptering

No skal me faktisk skriva noko kode! Me skal byrja enkelt med å laga krypteringa, basert på teorien bør det vera ganske rett fram.

Implementer kryptering med Cæsar Chiffer ved å bruka ei funksjon som tek inn tekst og eit tal som er «nøkkelen», altså kor mykje alfabetet skal roterast 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

Oppgåve 1.2 – Cæsar Chiffer Dekryptering

Dekryptering er berre å gjera den motsette utrekninga til enkryptering. Du trekkjer frå offset i staden for å leggja til.

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

Andre Monoalfabetiske Chiffer/Ciphers (ex. Atbash)

Det finst andre monoalfabetiske chiffer òg! Ein av dei enklare er den som vert kalla “Atbash” Chiffer.

Korleis verkar Atbash?

Denne er svært enkel, i staden for ein rotasjon så vert bokstavar kartlagde til det motsette alfabetet. Her er ei tabell som syner kartleggingi:

Oppgåve 1.3 - Atbash Chiffer Kryptering og Dekryptering

Det kjekke med Atbash er at sidan kryptering er ein 1 til 1 transformasjon, so fungerer han direkte i revers. Altså, um du har laga krypteringa, so har du óg, automatisk laga dekrypteringa.

Korleis kan dette gjerast i praksis?

Du kan anten trekke frå bokstaven i høve til Z, eller lage ein «Look-up» tabell. Altså, det tyder ei tabell eller ordbok som innhald alle bokstavane frå a til z og kva dei skal verte. Dette kan vera god løysing dersom de vil lage ein annan type kryptering.

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, so hente ut verdiin per bokstav frå oppslagstabellen, so skrive han ut. Kva må du gjera for store og små bokstavar?

Del 2 - Kryptoanalyse av Monoalfabetiske Chiffer

I denne delen skal dykk prøva å laga ein algoritme for å «cracke» ein Cæsar-chiffer, altså taka ein kryptert tekst, deretter, få ut den originale teksten utan å vita nøkkelen.

Dette kan gjerast noko manuelt, eller så kan du prøva å taka i bruk enkel «cryptanalysis». Dette er eit konsept som vi skal sjå djupare på seinare, men for no skal vi berre sjå på ein av dei enklaste måtane: Frekvensanalyse (frequency analysis). Du kan lesa meir om dette konseptet her: Frequency Analysis eller her Wikipedia - frequency analysis.

Denne metoden kan brukast i meir enn berre Cæsar-chiffer, ho kan brukast i meir kompliserte algoritmar også, men Cæsar-chiffer er såpass enkel at frekvensanalyse er triviell.

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

Oppgåve 2.1 – Laga ein frekvenstabell

I ei python-fil, skap ein frekvenstabell av bokstavane i det engelske språket. Du kann prøva å finna denne sjølv, men um du ikkje gidder dette, forstår me det!

Um du absolutt ynskjer å finna den sjølv, kann du gjera som i Oppgåve 2.2, men på ein 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
}

Oppgåve 2.2 – Telja frekvensen av bokstavar i tekst

No skal me laga ein algoritme som skal finna frekvensen av bokstavar i ein gjeven tekst.

Oppgåve 2.3 – Samanlikne frekvensen av ein tekst med den ekte frekvensen

Når du har funne frekvensen til alle bokstavane i teksten, kan du lage ein funksjon som finn «avstanden». Kva meinar me med det?

Du kan sjå føre deg at frekvensen til til dømes E i teksten kjem til å vere eit tal. Du kan finne «avstanden» denne har med den faktiske frekvensen, som er 12.70. Døme: Frekvensen er 9.63, kva er avstanden? Avstanden kjem til å vere den absolutte verdien (negative tal vert positive) mellom desse to verdiane: \(12.70 - 9.63 = 3.07\).

Lag ein funksjon som går igjennom kvar av bokstavane og finn avstanden. Legg deretter alle avstandane saman til ein «total» avstand.

Oppgåve 2.4 – «Knekke» Cæsar-chiffer

No skal me til slutt setje saman alt me har gjort så langt! No skal me «knekke» eit Cæsar-chiffer.

Lag eit program som «knekker» eit Cæsar-chiffer! Utan brukaren si innverknad skal du kunne hive inn ein kryptert tekst og hente ut den dekrypterte teksten utan å trenge ein nøkkel.