Klassískar dulritunaraðferðir

Í fyrri kaflanum lærðum við að dulritun snýst ekki bara um að gera texta ólæsilegan. Við þurfum líka að vita hvaða markmið við höfum, hver lykillinn er og hverju aðferðin verndar.

Núna ætlum við að prófa okkur áfram með einfaldar klassískar dulritunaraðferðir (e. classical ciphers). Þær eru gamlar, skemmtilegar og auðvelt er að reikna með þeim á blaði. Þær eru hins vegar ekki öruggar til að vernda raunveruleg leyndarmál.

Við notum oft enska stafrófið A–Z í dæmunum. Það gerir útreikningana einfaldari og passar við mörg verkefni í gagnaglímum. Íslenska stafrófið inniheldur fleiri stafi, eins og Ð, Þ, Æ og Ö, og því þyrfti að ákveða sérstakar reglur ef við vildum dulrita íslenskan texta með þessum gömlu aðferðum.

Ekki nota þetta til að vernda alvöru leyndarmál

Caesar-dulritun, Atbash, einföld stafaskipti og Vigenère-dulritun eru góð kennsludæmi en slæmar öryggisaðferðir. Ekki nota þær til að geyma aðgangsorð eða senda persónulegar upplýsingar.

Fyrsta hugmyndin: færa stafina til

Caesar-dulritun

Caesar-dulritun (e. Caesar cipher) er ein einfaldasta gerð dulritunar. Hver stafur er færður sama fjölda sæta áfram í stafrófinu. Fjöldinn sem við færum stafina kallast lykill.

Við notum eftirfarandi stafróf:

Venjulegt: ABCDEFGHIJKLMNOPQRSTUVWXYZ

Ef lykillinn er 3 verður:

Venjulegt: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Dulritað:  DEFGHIJKLMNOPQRSTUVWXYZABC

Þá verður A að D, B að E og C að F. Þegar við komum að lokum stafrófsins byrjum við aftur á byrjuninni: X verður A, Y verður B og Z verður C.

Sýnidæmi: HELLO

Við dulritum orðið HELLO með lyklinum 3:

Upprunalegur stafur	H	E	L	L	O
Færður um 3	K	H	O	O	R

Útkoman er því:

HELLO → KHOOR

Til að dulráða færum við stafina þrjú sæti til baka:

KHOOR → HELLO

Taktu eftir að sama orðið L birtist tvisvar og verður að sama stafnum O í báðum tilvikum. Það mynstur verður mikilvægt þegar við reynum að brjóta dulritunina.

Vissir þú?

Heitið kemur frá Júlíusi Caesar, sem er sagður hafa notað tilfærslu um þrjú sæti til að senda hernaðarleg skilaboð. Sú aðferð var líklega nægileg gegn lesendum sem kunnu ekki að lesa, en ekki gegn fólki sem rannsakaði hana kerfisbundið.

Æfing: dulrita og dulráða

Æfing 1

Dulritaðu orðið CAT með Caesar-lykli 3.
Dulráðaðu orðið FDHVDU með Caesar-lykli 3.

Lausn við æfingu 1

Við færum hvern staf þrjú sæti áfram:

C → F
A → D
T → W

Svarið er því FDW.

Við færum hvern staf þrjú sæti til baka:

F → C
D → A
H → E
V → S
D → A
U → R

Svarið er CAESAR.

Við þurftum ekki að prófa öll möguleg orð. Þegar lykillinn var þekktur var nóg að fylgja sömu reglunni aftur á bak.

Lykillinn er lítill

Í Caesar-dulritun getur lykillinn aðeins verið einn af 26 mögulegum tilfærslum. Lykillinn 0 gerir ekkert og lykillinn 26 gerir í raun það sama og 0, þannig að það eru aðeins 25 áhugaverðir möguleikar.

Þetta þýðir að við getum prófað þá alla. Slík aðferð kallast þrautleit (e. brute force): við prófum möguleikana einn af öðrum þar til eitthvað lítur út eins og texti.

Æfing 2

Dultextinn er:

FDHVDU LV VNHPPWLOHJW

Hann var búinn til með Caesar-dulritun. Prófaðu mismunandi lykla og finndu skilaboðin.

Lausn við æfingu 2

Hér er auðvelt að prófa lykil 3 á fyrsta orðinu:

F → C
D → A
H → E
V → S
D → A
U → R

Fyrsta orðið verður CAESAR, svo lykillinn 3 virðist líklegur. Þegar við beitum honum á allan textann fáum við:

FDHVDU LV VNHPPWLOHJW
CAESAR IS SKEMMTILEGT

Við fundum ekki lykilinn með því að giska á persónulegt leyndarmál. Við prófuðum einfaldlega alla litlu möguleikana þar til einn gaf skiljanlegan texta.

ROT13: Caesar með hálfu stafrófi

ROT13 er sérstakt tilvik af Caesar-dulritun. Þar er hver stafur færður 13 sæti áfram:

A ↔ N
B ↔ O
C ↔ P
...
M ↔ Z

Stafrófið er 26 stafir að lengd og 13 er helmingurinn. Ef við beitum ROT13 tvisvar komum við aftur að upphaflega textanum:

HELLO → URYYB → HELLO

Þetta gerist vegna þess að við færum samtals 26 sæti.

Vissir þú?

ROT13 var lengi notað á fréttahópum og spjallsvæðum til að fela skemmdarverk, brandara eða lausnir á gátum. Lesandinn gat afkóðað textann með einum hnappi. Það var þægileg leið til að forðast óviljandi uppljóstranir, en alls ekki öryggi.

Sýnidæmi: tvöfalt ROT13

Ef við fáum:

Fury vf sha

og beitum ROT13 fáum við:

Fury vf sha → Shel is fun

Til dæmis verða fyrstu fjórir stafirnir svona:

F → S
u → h
r → e
y → l

Hér þarf að gæta þess að vinna staf fyrir staf rétt. Bilið milli orðanna helst óbreytt.

Í þessu dæmi var textinn viljandi valinn til að sýna að stafaskipti breyta ekki bilum. Í raunverulegum verkefnum er betra að nota Python eða CyberChef til að forðast innsláttarvillur.

Aðeins A–Z í dæmunum

ROT13-forrit sem gerir ráð fyrir enska stafrófinu veit ekki sjálfkrafa hvað á að gera við ð, þ eða æ. Það þarf að ákveða hvort stafirnir séu látnir standa, fjarlægðir eða settir í eigið stafróf.

Atbash: stafrófið speglað

Í stað þess að færa stafina ákveðinn fjölda sæta getum við speglað stafrófið. Það kallast Atbash.

Venjulegt: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Atbash:    ZYXWVUTSRQPONMLKJIHGFEDCBA

Þá verður A að Z, B að Y, C að X og svo framvegis.

Sýnidæmi: HELLO með Atbash

H → S
E → V
L → O
L → O
O → L

Þess vegna:

HELLO → SVOOL

Atbash hefur enga sérstaka leynda lykiltölu. Reglan er alltaf sú sama og því getur hver sem þekkir Atbash notað hana.

Vissir þú?

Heitið Atbash er dregið af fyrstu og síðustu stöfunum í hebreska stafrófinu: alef–tav–bet–shin. Aðferðin er meira en tvö þúsund ára gömul og kemur meðal annars fyrir í gömlum textum þar sem hún var notuð til að fela ákveðin nöfn eða orð.

Æfing: speglaðu stafrófið

Æfing 3

Dulráðaðu eftirfarandi Atbash-texta:

GSV XZG RH LM GSV ILLU

Lausn við æfingu 3

Við notum töfluna:

A ↔ Z, B ↔ Y, C ↔ X, ..., G ↔ T, H ↔ S, I ↔ R, L ↔ O, M ↔ N

Nú tökum við orðin eitt í einu:

GSV → THE
XZG → CAT
RH  → IS
LM  → ON
GSV → THE
ILLU → ROOF

Skilaboðin eru því:

THE CAT IS ON THE ROOF

Þetta sýnir líka að Atbash er sín eigin dulráðning: sama tafla er notuð í báðar áttir.

Stafaskipti með eigin lykli

Caesar og Atbash nota mjög einfaldar reglur. Við getum búið til mun fleiri möguleika með því að nota annað stafróf sem lykil.

Við skrifum venjulega stafrófið efst og lykilstafrófið fyrir neðan:

Venjulegt: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Lykill:    QWERTYUIOPASDFGHJKLZXCVBNM

Þetta lykilstafróf notar sömu stafi og venjulega stafrófið, en í annarri röð. Til dæmis verður:

A → Q
B → W
C → E
D → R
E → T

Þetta kallast stafaskipti (e. substitution): hver stafur er skipt út fyrir annan staf. Við getum notað lykilstafrófið til að dulrita HELLO:

H → I
E → T
L → S
L → S
O → G

Niðurstaðan er:

HELLO → ITSSG

Hér er lykillinn ekki talan 3, heldur allt lykilstafrófið.

Sýnidæmi: mynstrið lifir áfram

Í HELLO er sami stafurinn L í þriðja og fjórða sæti. Í dultextanum ITSSG er sami stafurinn S á sömu sætum.

Mynstrið er því:

HELLO  →  1 2 3 3 4
ITSSG  →  1 2 3 3 4

Þetta er veikleiki. Þótt lykillinn geti verið einn af mjög mörgum mögulegum stafrófum breytir aðferðin ekki mynstrum orðanna. Tvítekinn stafur verður alltaf sami dulritaði stafurinn.

Æfing 4

Notaðu sama lykilstafróf og hér að ofan til að dulráða:

ITSSG CGJSF

Lausn við æfingu 4

Við leitum að hverjum dulrituðum staf í neðri línunni og lesum samsvarandi staf í efri línunni:

Lykill:    Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Venjulegt: 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

Fyrsta orðið verður:

I → H
T → E
S → L
S → L
G → O

ITSSG verður því HELLO.

Annað orðið verður:

C → W
G → O
J → R
S → L
F → D

Heildarskilaboðin eru:

HELLO WORLD

Af hverju er þetta samt hægt að brjóta?

Þótt við getum búið til ótrúlega mörg lykilstafróf eru tungumál ekki handahófskennd. Í íslensku, ensku og öðrum tungumálum koma sumir stafir og stafasamsetningar mun oftar fyrir en aðrir.

Í enskum texta er E til dæmis mjög algengur stafur. Algeng orð eru oft stutt, eins og THE, OF, TO og AND. Ef við fáum nógu langan dultexta getum við notað þessar upplýsingar til að giska á lykilinn.

Tíðnigreining

Tíðnigreining (e. frequency analysis) er aðferð þar sem við teljum hversu oft stafir eða mynstur koma fyrir. Hún er ein elsta og mikilvægasta leiðin til að greina einföld stafaskipti.

Vinnuferlið er oft svona:

Telja hvaða dulritaðir stafir koma oftast fyrir.
Giska á að algengasti stafurinn sé algengur stafur í tungumálinu.
Leita að stuttum orðum, sérstaklega tveggja og þriggja stafa orðum.
Nota þekkt mynstur til að fylla út fleiri stafi.
Prófa giskanirnar í öllum textanum og leiðrétta þær.

Sýnidæmi: hvað segir orðið okkur?

Segjum að við sjáum þetta í dultexta:

ZIT YSQU OL IORRTF OF ZIT YOST

Við vitum ekki lykilinn, en við getum skoðað mynstrið:

ZIT kemur tvisvar fyrir.
YSQU og YOST byrja á sama staf.
OL er tveggja stafa orð.
IORRTF hefur tvítekinn staf í miðjunni.

Ef við giskum á að ZIT sé algenga orðið THE, fáum við:

Z → T
I → H
T → E

Þá verður textinn að hluta:

THE YSQU OL IORRTF OF THE YOST

Ef OL er orðið IS, fáum við líka O → I og L → S:

THE YSQU IS IORRTF OF THE YOST

Núna er hægt að halda áfram með orðamynstur og samhengi. Ef við þekkjum efnið eða búumst við ákveðnu svari verður vinnan enn auðveldari.

Vissir þú?

Al-Kindi, arabískur fræðimaður á 9. öld, skrifaði eina elstu þekktu lýsinguna á tíðnigreiningu. Hann benti á að hægt væri að bera saman tíðni stafa í dultexta við tíðni stafa í venjulegu tungumáli.

Æfing: greindu mynstrið

Æfing 5

Í eftirfarandi dultexta er sama stafaskiptalykill notaður allan tímann:

ZIT YSQU OL IORRTF OF ZIT YOST

Við vitum að skilaboðin fjalla um einhvern fána. Hvað gæti fyrsta orðið ZIT verið? Prófaðu þá að skipta út stöfunum sem þú finnur og sjáðu hvort þú komist lengra.

Lausn við æfingu 5

Algengasta þriggja stafa orðið í ensku er oft THE, og ZIT kemur tvisvar fyrir sem sjálfstætt orð. Við prófum því:

ZIT → THE

Þá vitum við að:

Z → T
I → H
T → E

Við getum nú notað samhengi og vísbendinguna um fána til að prófa algeng orð:

ZIT    → THE
YSQU   → FLAG
OL     → IS
IORRTF → HIDDEN
OF     → IN
YOST   → FILE

Þetta gefur okkur stafaskiptin:

Z → T, I → H, T → E
Y → F, S → L, Q → A, U → G
O → I, L → S
R → D, F → N

Þegar við setjum allt saman fáum við:

ZIT YSQU OL IORRTF OF ZIT YOST
THE FLAG IS HIDDEN IN THE FILE

Við þurftum ekki að þekkja allan lykilinn í upphafi. Hvert rétt orð gaf okkur nýtt stafapar sem hjálpaði við næsta orð. Ef einhver giska hefði ekki passað alls staðar hefðum við tekið hana til baka.

Tíðnigreining er því ekki töfraaðferð sem gefur alltaf svar í einu skrefi. Hún gefur okkur vísbendingar sem við prófum, metum og leiðréttum.

Góð greining má afturkalla

Þegar við erum að prófa gisk er sniðugt að skrifa niður lykilinn í töflu. Þá getum við tekið eina ákvörðun til baka ef hún reynist röng, í stað þess að byrja alveg upp á nýtt.

Vigenère-dulritun: fleiri en ein Caesar-regla

Caesar-dulritun notar sama tilfærslulykil á hverjum staf. Hvað ef við skiptum um tilfærslu í hvert skipti?

Vigenère-dulritun (e. Vigenère cipher) gerir einmitt þetta. Hún notar lykilorð og beitir mismunandi Caesar-tilfærslu eftir stöfunum í lykilorðinu.

Við skulum nota lykilorðið LEMON og textann ATTACKATDAWN:

Texti:   A T T A C K A T D A W N
Lykill:  L E M O N L E M O N L E

Lykilorðið er endurtekið þar til það nær yfir allan textann. Fyrsti stafur lykilsins L færir fyrsta staf textans, næsti stafur E færir næsta staf og svo koll af kolli.

Ef við notum stafrófstöfluna A=0, B=1, ..., þá verður:

A með L → L
T með E → X
T með M → F
A með O → O
C með N → P

Þegar við höldum áfram fæst:

ATTACKATDAWN → LXFOPVEFRNHR

Við höfum ekki enn farið í modulo-stærðfræði. Í bili nægir að hugsa um þetta sem töflu þar sem við finnum röð textastafs og dálk lykilstafs.

Vissir þú?

Vigenère-dulritun var lengi kölluð le chiffre indéchiffrable, „ómögulega dulmálið“. Hún var þó síðar brotin með því að skoða endurtekningar og áætla lengd lykilorðsins. Heitið „ómögulegt“ reyndist því heldur bjartsýnt.

Sýnidæmi: afkóða með lykilorði

Við fáum dultextann:

LXFOPVEFRNHR

og lykilorðið:

LEMON

Við endurtökum lykilorðið:

Dultexti: L X F O P V E F R N H R
Lykill:   L E M O N L E M O N L E

Nú færum við hvern dultextastaf til baka um tilfærsluna sem samsvarandi lykilstafur segir til um:

L með L → A
X með E → T
F með M → T
O með O → A
P með N → C

Eftir að hafa haldið áfram með alla rununa fáum við:

LXFOPVEFRNHR → ATTACKATDAWN

Æfing: Vigenère

Æfing 6

Dultextinn er:

RIJVS UYVJN

Lykilorðið er KEY. Afkóða skal textann með Vigenère-aðferðinni. Bil eru ekki hluti af lykilreikningnum.

Lausn við æfingu 6

Við endurtökum lykilorðið yfir stafina:

Dultexti: R I J V S U Y V J N
Lykill:   K E Y K E Y K E Y K

Við notum lykilstafina sem tilfærslur og færum dultextann til baka:

R með K → H
I með E → E
J með Y → L
V með K → L
S með E → O
U með Y → W
Y með K → O
V með E → R
J með Y → L
N með K → D

Svarið er:

HELLO WORLD

Hér skiptir máli að lykilorðið byrjar aftur á K eftir hvern hóp af þremur stöfum. Ef við færum lykilinn um einn staf á röngum stað verður allur afgangurinn rangur.

Hvers vegna er Vigenère ekki nóg?

Vigenère er sterkari en Caesar vegna þess að sami stafur getur orðið að ólíkum dultextastöfum. Til dæmis getur A orðið að L, E eða öðrum staf eftir því hvaða lykilstafur er notaður.

En lykilorðið er oft endurtekið. Ef lykilorðið er stutt mun sama mynstrið birtast aftur og aftur í dultextanum. Með nægilega löngum skilaboðum getur greiningaraðili:

fundið endurtekningar,
giskað á lengd lykilorðsins,
skipt dultextanum í hópa,
beitt tíðnigreiningu á hvern hóp.

Þetta er gott dæmi um mikilvæga reglu í dulritun: aðferð sem felur einföld mynstur að hluta getur samt lekið mynstrum þegar hún er notuð á mörg gögn eða með endurteknum lykli.

Hliðarspor: umröðun í stað stafaskipta

Hingað til höfum við skipt einum staf út fyrir annan. Önnur einföld hugmynd er að breyta aðeins röðinni á stöfunum. Þetta kallast umröðunardulritun (e. transposition cipher).

Til dæmis getum við fyllt skilaboðið MEETATNOON upp í 12 stafi með tveimur X-stöfum og skrifað það niður í tvo dálka:

M E
E T
A T
N O
O N
X X

Ef við lesum núna línu fyrir línu fáum við dultextann:

MEANOXETTONX

Stafirnir hafa ekki breyst — þeir hafa aðeins skipt um stað. Sá sem þekkir regluna getur skrifað dultextann aftur í tveggja dálka töflu og lesið hann dálk fyrir dálk til að fá MEETATNOONXX.

Stafaskipti og umröðun eru ólík

Í stafaskiptum breytist hvaða stafur er á hverjum stað. Í umröðun breytist hvar stafurinn er. Söguleg dulmál blanda stundum þessum hugmyndum saman.

Æfing: lesa í réttri röð

Æfing 7

Skilaboð voru skrifuð í tveggja dálka töflu og síðan lesin línu fyrir línu:

M E A N O X
E T T O N X

Lesið textann upp á nýtt með því að lesa dálkana ofan frá og niður, fyrst vinstri dálkinn og síðan þann hægri.

Lausn við æfingu 7

Fyrst lesum við vinstri dálkinn:

M E E T A T

Síðan lesum við hægri dálkinn:

N O O N X X

Þegar við setjum dálkana saman fáum við:

MEETATNOONXX

Síðustu tveir X-stafirnir voru bara fylling til að gera töfluna rétthyrnda. Skilaboðin eru því MEET AT NOON.

Lærdómurinn er að röð aðgerðanna skiptir máli. Í gagnaglíma þurfum við að átta okkur á því hvernig taflan var fyllt og hvernig hún var lesin.

Vissir þú?

Spartverjar notuðu aðferð sem kallast scytale, þar sem leðurreim var vafið utan um sívalning. Textinn var skrifaður eftir reiminni og varð ólæsilegur þegar hún var tekin af. Sá sem átti sívalning með réttri þvermálsstærð gat vafið reiminni aftur og lesið skilaboðin.

Hvernig nálgumst við klassískt dulritunarverkefni?

Þegar við fáum óþekktan dultexta þurfum við ekki að byrja á flóknustu hugmyndinni. Við getum farið kerfisbundið yfir einföld atriði:

Skoðum stafina. Eru þetta bara A–Z, eða eru líka tölur, tákn og bil?
Skoðum lengdina. Er textinn mjög stuttur eða nógu langur til að mynstur sjáist?
Leitum að endurtekningum. Koma sömu orð eða stafaraðir fyrir aftur?
Prófum algengar aðferðir. Caesar, ROT13, Atbash og einföld stafaskipti eru eðlilegir fyrstu möguleikar.
Teljum stafi. Tíðni getur gefið vísbendingar.
Skráum tilgátur. Ef ein breyting passar ekki alls staðar getum við tekið hana til baka.
Notum verkfæri þegar textinn verður langur. Python, CyberChef og einföld orðalista- eða tíðniforrit geta sparað okkur mikla handavinnu.

Lokaverkefni: hvaða aðferð?

Æfing 8

Þú færð eftirfarandi gögn:

1. KHOOR ZRUOG
2. SVOOL DVIOW
3. LXFOPVEFRNHR
4. ZIT YSQU OL IORRTF OF ZIT YOST

Hvað myndir þú prófa fyrst á hverju dæmi og hvers vegna?

Lausn við æfingu 8

KHOOR ZRUOG lítur út eins og Caesar-dulritun með lykli 3: HELLO WORLD.
SVOOL DVIOW passar við Atbash: HELLO WORLD.
LXFOPVEFRNHR er runa án bila og líkist klassíska Vigenère-dæminu. Ef lykilorðið LEMON er gefið fæst ATTACKATDAWN.
Síðasta dæmið er lengra og inniheldur endurtekin orðamynstur. Þar væri eðlilegt að prófa einföld stafaskipti og tíðnigreiningu. Það er ekki jafn öruggt að giska á eina aðferð strax; við þurfum að nota mynstrin sem vísbendingar.

Aðalatriðið er ekki að kunna fjórar töfraformúlur utan að. Aðalatriðið er að geta skoðað gögn, sett fram tilgátu og prófað hana á skipulegan hátt.

Samantekt

Í þessum kafla lærðum við að:

Caesar-dulritun færir alla stafi sama fjölda sæta.
ROT13 er Caesar-dulritun með tilfærslu um 13.
Atbash speglar stafrófið.
Stafaskipti nota annað stafróf sem lykil.
Tvítekin stafamynstur lifa oft áfram í einföldum stafaskiptum.
Tíðnigreining notar tíðni stafa, orðamynstur og samhengi til að finna veikleika.
Vigenère-dulritun notar endurtekið lykilorð til að breyta tilfærslunni milli stafa.
Umröðunardulritun breytir röð stafanna fremur en stafunum sjálfum.
Þessar aðferðir eru frábærar til að læra af en eiga ekki að vernda raunveruleg leyndarmál.

Við höfum nú séð hvers vegna lyklar og mynstur skipta máli. Í næsta kafla kynnumst við þeirri stærðfræði sem liggur undir mörgum nútímalegri dulritunaraðferðum: leifum, modulo-reikningi og margföldunarandhverfum.