Substitutionsciffer – definition, Cæsar-chiffer og frekvensanalyse
Lær om substitutionscifre: definition, Cæsar-chiffer og hvordan frekvensanalyse afslører krypterede beskeder. Historie, eksempler og knækmetoder.
Et substitutionschiffer (ofte også kaldet substitutionsciffer) er en enkel form for kryptografi, hvor hvert bogstav i en klartekst erstattes af et andet bogstav efter en bestemt regel. Reglen kan være så enkel som "flyt hvert bogstav tre pladser frem i alfabetet" eller en vilkårlig blanding af bogstaver — så længe hver klartekstbogstav altid bliver byttet til det samme chifferbogstav.
Hvordan det virker
I en monoalfabetisk substitutionschiffer benyttes ét fast erstatningsalfabet: hver forekomst af et givet bogstav i klarteksten bliver udskiftet med samme bogstav i chifferteksten. For eksempel kan en regel være at erstatte:
- A → D, B → E, C → F, … (et simpelt skub af alfabetet)
- Eller en vilkårlig ombytning: A → Q, B → X, C → M, …
Et simpelt eksempel på en substitutionsmetode er Cæsar-chifferet, hvor man skubber alle bogstaver et fast antal pladser i alfabetet (klassisk er skubbet 3 pladser: A → D, B → E osv.). Substitutionschiffer kan også være mere komplicerede typer som homofone substitutioner (hvor et klartekstbogstav kan blive kodet som flere mulige chifferbogstaver) eller polygrafiske skemaer (der arbejder med par eller grupper af bogstaver).
Eksempel på Cæsar-chiffer
Ved et Cæsar-chiffer med skub på 3 bliver ordet "Hej" til "Khj" (H → K, e → h, j → m osv.). Cæsar-chifferet er let at bryde, fordi der kun findes 25 mulige skift for det latinske alfabet — man kan simpelthen prøve dem alle.
Frekvensanalyse — hvordan man bryder et substitutionschiffer
Substitutionschifrer er svage mod en metode, der kaldes frekvensanalyse. Ideen er, at bogstaver i et givet sprog forekommer med forskellige hyppigheder. I engelsk er f.eks. E det mest almindelige bogstav efterfulgt af T, A, O, I, N, og i dansk er E også særligt hyppig sammen med fx R, N, T. Når et langt nok stykke tekst er krypteret med en simpel substitution, bevares disse frekvensmønstre — blot med andre bogstaver.
Grundlæggende fremgangsmåde ved frekvensanalyse:
- Tæl hvor ofte hvert chifferbogstav forekommer i den krypterede tekst.
- Sammenlign fordelingen med kendte bogstavfrekvenser for det sprog, du tror teksten er skrevet på (fx engelsk eller dansk) og lav et første gæt: dét chifferbogstav, der forekommer hyppigst, kan svare til E.
- Se på ordmønstre og korte ord: to-bogstavs- og tre-bogstaver-ord (fx "og", "en", "the", "and") og gentagne mønstre (som dobbelt-bogstaver) kan bekræfte eller afkræfte gæt.
- Brug digrafer og trgrafer (almindelige par og tripletter som "TH", "HE", "IN" i engelsk) til yderligere spor.
- Iterer: indfør enkelte korrektioner, se om resultatet giver meningsfulde ord, og ret til indtil hele teksten læses.
For korte beskeder er frekvensanalyse ofte upræcis, fordi statistikken er for lille. For meget lange tekster bliver den derimod pålidelig. Kryptogrammer (meddelelser skjult med et substitutionschiffer) er et almindeligt puslespil i aviser og blade netop fordi denne teknik gør det muligt at løse dem uden kendskab til nøglen.
Svagheder og moderne alternativer
Enkle substitutionschifrer er ikke sikre til beskyttelse af fortrolige eller vigtige oplysninger. Der findes forbedringer (fx homofone eller polialfabetiske systemer) som kan gøre frekvensanalyse sværere, men de ægte sikre metoder i dag bygger på moderne kryptografi — matematiske systemer som symmetrisk kryptering (f.eks. AES) og asymmetrisk kryptering (f.eks. RSA) — og ikke på simple substitutionsregler.
Afslutningsvis er substitutionschifrer fremragende til undervisning, historiske studier og puslespil, fordi principperne er lette at forstå og de giver mulighed for at lære grundlæggende idéer i kryptografi og analyse. Til praktisk informationssikkerhed skal man dog vælge moderne, velstuderede metoder.
Eksempel
Lad os antage, at den ændrede meddelelse er:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVVMUIMWERGMIWXMJMGCMGCSMWXSJOMIQXLIVIQIVIVIXQSVVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMSCMWMSWVIRCIGXMWYMXXLIYSPH KTYI dette eksempel bruges store bogstaver til ukendte bogstaver, og små bogstaver bruges til at angive bogstaver, som vi kender eller kan gætte os til.
Ved at tælle bogstaverne op kan vi se, at det mest almindelige bogstav er I, som vi gætter på er et e. X er også ret almindeligt, og XLI findes mange gange; vi gætter på, at dette er den mest almindelige gruppe på tre bogstaver på engelsk.
E er det næstmest almindelige bogstav. Vi har allerede et gæt på e og t, så vi gætter på, at E er a. Vi har nu:
heVeTCSWPeYVaWHaVSReQMthaYVaOeaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM WQhMGhMtQaReWGPSReHMtQaRaRaKeaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUeMWMWaRGMeWtMJMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWWHaPSWYSWeWeaVtheStheVtheVtheRGaPeRRQeQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha PPtheaCCeaVaWGeSJKTVVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWMYRMWtSGSWRMHMHeVatMSWMMGSTPHhaVHPFKPaKPaZeZeNTCMteVJSVhMRSCMWMSWMSWVVeRCeGtMWMWYMttheYSPH KTYVi kan nu komme med nogle flere gæt: heVe kan være her; Rtate kan være state, og athattMZe kan være athattime. Hvis vi udfylder disse gæt, får vi:
herTCSWPeYraWHarSseQithaYraYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ GSTrseaYreatCriUeiWasGieWtiJiGiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiWiSWresCeGtiWYittheYSPH KTYDet giver os mulighed for at gætte flere gæt, som fører til flere, indtil vi har gættet alt:
herpå en stor rose med grav og storslået luft og bragte rosen med sig fra en glaskuffert, som den var lukket inde i, og det var en smuk karabæus og på det tidspunkt ukendte naturforskere, der naturligvis fik store priser på det videnskabelige område, og der var omkring sorte pletter, som var omgivet af en række sorte pletter, som var en enkelt udstr på ryggen og langs den anden side af ryggenog på den anden side var skællene overordentligt hårde og blanke med en tydelig forbrændingog vægten af insektet var meget bemærkelsesværdigog når man tager alle ting i betragtning, kunne man næppe bebrejde Jupiter for hans mening om den gyldne insekt.På dette tidspunkt kan vi indsætte mellemrum og tegnsætning:
Her rejste le grand sig med en alvorlig og statelig mine og bragte mig billen fra
en glasmontre, hvori den var indkapslet. Det var en smuk scarabæus, og på
det tidspunkt var den naturligvis ukendt for naturforskere; en stor gevinst
set fra
et videnskabeligt
synspunkt. Der var to runde sorte pletter nær den ene ende af ryggen og
en lang plet
nær den anden. Skællene var overordentlig hårde og blanke og lignede
poleret guld. Insektets vægt var meget bemærkelsesværdig,
og alt taget i betragtning kunne jeg næppe bebrejde Jupiter for
hans mening om det. (Guldbuggen)
Hvis vi havde gættet forkert, ville vi have fundet ud af det på et tidspunkt og kunne gå tilbage og gætte på ny.
Spørgsmål og svar
Q: Hvad er en substitutionskryptering?
A: Et substitutionschiffer er en form for kryptografi, hvor man bruger en regel til at erstatte hvert bogstav i en besked med et andet bogstav fra alfabetet.
Q: Hvordan fungerer en substitutionskryptering?
A: I en substitutionskryptering bruges en regel til at erstatte hvert bogstav i beskeden med et andet bogstav fra alfabetet, et ad gangen.
Q: Hvad er et eksempel på en tabel, der bruges i en substitutionskryptering?
A: Tabellen i teksten giver en regel for en substitutionskryptering, der kan bruges til at erstatte hvert bogstav med et andet bogstav fra alfabetet.
Q: Hvad er Cæsar-chifferet?
A: Cæsar-chifferet er et eksempel på et substitutions-chiffer.
Q: Er substitutionschifre sikre nok til vigtige beskeder?
A: Nej, substitution ciphers er ikke sikre nok til at bruge til vigtige beskeder.
Q: Hvordan kan substitutionschifre brydes?
A: Erstatningschifre kan brydes ved hjælp af frekvensanalyse, som leder efter almindelige bogstaver i den ændrede besked, som sandsynligvis er de mest almindelige bogstaver på engelsk.
Q: Hvad er en almindelig gåde, der involverer at bryde kryptogrammer?
A: At bryde kryptogrammer, som er beskeder, der er skjult med en substitutionschiffer, er en almindelig gåde, der ofte findes i aviser.
Søge