www.matematikk.org
Trinn 11-13Elever Trinn 11-13Lærer Trinn 11-13Foresatt

Klassisk kryptografi

Har du noen hemmeligheter? Kanskje er det noen du vil dele dem med? Kanskje noen som er langt borte, så du må sende dem som brev eller tekstmelding? Hva om noen andre åpner brevet, eller leser tekstmeldinga? Hvis dette er noe du gjerne vil unngå, bør du lære deg litt om kryptografi, eller hemmelig skrift.

Kryptografi kan gjøre deg istand til å skrive ned meldinger på en slik måte at bare de du ønsker kan lese dem.

Utskifting eller substitusjon

La oss ta et veldig enkelt eksempel. Anna og Bente er enige om at når de sender tekstmeldinger til hverandre, så skal de alltid skrive B hver gang de mener A, og C når de mener B osv. (Å erstattes med A). Dermed blir meldinga MATEMATIKK ER GØY kamuflert til NBUFNBUUJLL FS HÅZ. Dette synes Anna og Bente er nyttig, for de vil jo ikke at noen som tjuvlåner telefonen deres skal vite hva de egentlig synes om matematikk. Men dette var jo ganske enkelt, da. Noen med litt fantasi, eller noen som har drevet med litt kryptografi selv, kan lett gjennomskue dette systemet. Du kan variere dette systemet ved å forskyve alfabetet slik at A, B, C erstattes med henholdsvis C, D og E osv., som i tabellen under

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  Æ  Ø  Å

C  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

I dette eksemplet forskyver vi alfabetet to plasser til høyre. Hvis vi erstatterer A, B, C med K, L, M osv. forskyver vi ti plasser til høyre. Slike koder kalles Cæsar-koder, og antall plasser vi forskyver med kalles nøkkelen. Hvis vi kaller nøkkelen n, er er altså n = 2 og n = 10 i eksemplene. I alt er det 28 måter å gjøre dette på i en norsk tekst, siden A kan erstattes med hvilken som helst av de andre bokstavene, og hele systemet er bestemt av hva A erstattes med.

Hvis noen gjetter at Cæsar-koden er brukt, men ikke vet nøkkelen, kan de prøve alle muligheter. Hvis meldingen PTR N RTWLJS er snappet opp, kan man prøve med n = 1, 2, 3 osv. og man finner lett hva meldingen er.

PTR N RTWLJS: kryptotekst
OSQ M QSVKIR: n=1
NRP L PRUJHQ: n=2
MQO K OQTIGP: n=3
LPN J NPSHFO: n=4
KOM I MORGEN: n=5

Vi trenger altså en metode med flere nøkler. Her er en mulighet: Skriv hver bokstav i alfabetet på en lapp, tilsammen 29 lapper, krøll dem sammen og bland godt. Så trekker du en og en lapp, bokstaven som står på den første lappen erstatter du A med, bokstaven som står på den andre lappen erstatter du B med, osv.

Nå får du veldig mange forskjellige nøkler: Den første bokstaven trakk du tilfeldig av 29 muligheter, den andre tilfeldig blant 28 muligheter osv. Tilsammen er det da 292827...321 mulige forskjellige nøkler. Dette blir et tall med over 30 sifre, og selv om du tester 1 million nøkler i sekundet, må du holde på 10000 ganger universets levealder for å prøve alle mulighetene. Et eksempel: bruk følgende kode (hver bokstav erstatttes med bokstaven under).

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  Æ  Ø  Å

Q  A  Z  W  S  X  E  D  C  R  F  V  T  G  B  Y  H  N  U  J  M  I  K  O  L  P  Ø  Å  Æ

Da blir LANGE MATEMATIKKTIMER forvandlet til VQGES TQJSTQJCFFJCTSN. Selv om du nå ikke kan prøve ut alle mulige nøkler, er det ikke så vanskelig å knekke dette kryptosystemet heller, og finne den opprinnelige meldingen. Grunnen er at noen bokstaver er mer vanlige enn andre. I en lang norsk tekst er ca 12% av bokstavene E, mens Q, X, Z og C tilsammen utgør mindre enn 1%. Dette kan vi utnytte. Hvis vi har snappet opp en lang tekst (eller flere korte kryptert med samme nøkkel), kan vi telle og finne ut hvilken bokstav som forekommer oftest. Det er en god sjanse for at denne bokstaven erstatter E. De andre mest vanlige bokstavene er N, R, S, T og A. Straks du har gjettet de mest vanlige, kan du begynne å gjette deg fram til de andre, ved å prøve å danne ord. Med litt tålmodighet, kommer man fram til den riktige teksten. Teknikken kalles frekvensanalyse. Eksemplet med LANGE MATEMATIKKTIMER er i korteste laget for frekvensanalyse, selv om vi kan observere at teksten inneholder 3 E-er, men ingen Q, X, Z eller C.

Krypteringsteknikken vi har beskrevet her kalles substitusjon, eller utskifting, siden man bytter ut hver bokstav i alfabetet med en annen.

Permutasjon, eller ombytting

En annen vanlig teknikk er permutasjon, eller ombytting. Her er bokstavene i den krypterte teksten de samme som i den ukrypterte meldinga, men de kommer i en annen rekkefølge. For eksempel: Teksten SNU MEG kan bli GEM UNS. Det er vanlig å dele teksten i blokker, der alle blokkene har samme størrelse. For eksempel, la blokkstørrelsen være 4, en mulig permutasjon er ABCD -> DACB. Altså: Den første bokstaven i blokka erstattes med den fjerde, den andre erstattes med den første osv. Teksten

KAN DU PERMUTERE NÅ

deles opp i blokker

KAND UPER MUTE RENÅ

og så permuterer vi hver blokk etter oppskriften over, og får

DKNA RUEP EMTU ÅRNE.

Ved å velge store blokkstørrelser, kan vi lett få mange forskjellige nøkler. Men også nå kan det være mulig å knekke koden (dvs. å dekryptere uten å kjenne nøkkelen), ved å utnytte egenskaper ved språket. Eksempler på slike egenskaper kan være: Noen bokstaver forekommer ofte sammen, andre bokstaver forekommer aldri sammen, for eksempel kommer ingen andre konsonanter enn J og V etter H, og doble vokaler eller dobbel H, J, eller V forekommer ikke på norsk (med unntak for egennavn.)

De teknikkene som er nevnt her er ganske enkle, men ved å kombinere disse teknikkene på forskjellige måter kan du lage mer kompliserte systemer. Du kan for eksempel lage en kode der du først bruker en substitusjon på bokstav nummer 1, 3, 5, 7, 9 ... i teksten, og så bruker en annen substitusjon på bokstav nummer 2, 4, 6, 8 ... . Deretter deler du den nye teksten i blokker på for eksempel 10 bokstaver og gjør permutasjoner på disse blokkene. Dette vil bli tilstrekkelig komplisert til at mange amatører vil få problemer. Profesjonelle med tilgang på datamaskiner og riktige programmer vil imidlertid lett kunne knekke også dette systemet.

Kryptografi brukes oftest idag i forbindelse med digitale signaler. Språklige meldinger blir gjerne oversatt av datamaskiner til meldinger på formen 010100110100111, lange rekker med 0-ere og 1-ere. De samme teknikkene med utskifting og ombytting brukes også da. Siden 0 og 1 er de eneste tegnene som blir brukt, og vi dermed får få muligheter for utskifting, kan man gjøre utskifting av blokker istedet, for eksempel kan 0110 erstattes med 1010. Tallsystemet som bestå av bare 0-ere og 1-ere kan du lese mer om i en annen tekst her, det kalles det binære tallsystemet.

Systemene vi har sett på her har en felles forutsetning, nemlig at det finnes en nøkkel som den som krypterer og den som skal dekryptere kjenner til, og at ingen andre kjenner nøkkelen. Som navnet Cæsar-koder indikerer er dette en klassisk teknikk. I teksten om offentlig-nøkkel kryptografi skal vi se på en annen type kryptografi, som er mindre enn 30 år gammel. Med denne type kryptografi kan du sende krypterte meldinger til noen uten at dere på forhånd har utvekslet nøkler.

Publisert: 19.09.2007

Skrevet av

Aslak Bakke Buan

Institusjon

NTNU

Tilsvarende emner behandles også i

Begrep

  • Kryptografi

    Læren om den hemmelige skriften, om hvordan en koder meldinger slik at de ikke kan leses av andre, og om hvordan en kan prøve å avsløre hemmelig skrift.