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.

Í þessum kafla ætlum við að kynnast einföldum klassískum dulritunaraðferðum (e. classical ciphers). Þær eru gamlar, skemmtilegar og auðvelt er að reikna með þeim á blaði. Þær eru hins vegar ekki til þess fallnar að vernda gögn í dag.

Við notum oft enska stafrófið A–Z, með sínum 26 stöfum, í dæmunum. Það gerir útreikningana einfaldari og rímar við mörgu verkefni í gagnaglímum. Íslenska stafrófið inniheldur, aftur á móti, 10 séríslenska bókstafi, þannig 36 í heildina ef við teljum þá með öllu enska stafrófinu. Við þurfum því að hafa í huga að ef við viljum dulrita íslenskan texta, þarf að heimfæra reglur dulritunarinnar yfir á íslenska stafrófið.

Fyrsta hugmyndin: tilfærsla stafa

Caesar-dulritun

Caesar-dulritun (e. Caesar cipher) er ein einfaldasta gerð dulritunar. Hún felur í sér að hver stafur er færður sama fjölda sæta áfram í stafrófinu. Fjöldinn sem við færum stafina er, í því tilfelli, lykillinn.

Ef við notum enska stafrófið

ABCDEFGHIJKLMNOPQRSTUVWXYZ

og lykillinn er 3, verður dulkóðunin eftirfarandi:

Venjulegt: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Dulritað:  DEFGHIJKLMNOPQRSTUVWXYZABC

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

HELLO → KHOOR

KHOOR → HELLO

Taktu eftir að í ódulritaða orðinu birtist L tvisvar og verður að sama stafnum O í báðum tilvikum í dulritaða textanum. Það mynstur verður mikilvægt þegar kemur að því að brjóta dulritunina.

Æfing: dulrita og dulráða

C → F
A → D
T → W

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

Fáir mögulegir lyklar

Í Caesar-dulritun getur lykillinn aðeins verið einn af 26 mögulegum tilfærslum, þar sem stafrófið inniheldur 26 stafi. 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), þ.e. þegar við prófum alla möguleikana, einn af öðrum, þar til eitthvað lítur út eins og texti.

GEIWEV IV WOIQQXMPIKX

G → F, E → D, I → H, W → V, E → D, V → U

G → E, E → C, I → G, W → U, E → C, V → T

G → D, E → B, I → F, W → T, E → B, V → S

G → C, E → A, I → E, W → S, E → A, V → R

GEIWEV IV WOIQQXMPIKX
CAESAR ER SKEMMTILEGT

ROT13

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.

Fury vf sha

Fury vf sha → Shel is fun

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

Atbash

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

Venjulegt: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Atbash:    ZYXWVUTSRQPONMLKJIHGFEDCBA

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

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

HELLO → SVOOL

Atbash hefur ekki leynda lykiltölu eins og Caesar-dulritun. Reglan er alltaf sú sama og því getur hver sem þekkir Atbash notað hana.

Æfing

GSV XZG RH LM GSV ILLU

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

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

THE CAT IS ON THE ROOF

Umskipti með eigin lykli

Í grunninn skilgreina Caesar og Atbash mjög einfaldar reglur til að varpa einu stafrófi yfir í annað, þ.e. að fyrir hvern staf í stafrófinu veljum við annan staf í stafrófinu sem við skrifum í staðinn. Við þurfum þó ekki að einskorða okkur við svo formfastar reglur þegar kemur að slíkri vörpun. Við getum einfaldlega ákvarðað, fyrir alla bókstafina, í hvaða staf þeir breytast, eins og A verður X, B verður K, o.s.frv.

Til að skilgreina slíka vörpun getum við skrifað upprunalega stafrófið í eina röð, og þær breytingar sem verða á hverjum staf í röðina fyrir neðan, eins og t.d.

Stafróf:    ABCDEFGHIJKLMNOPQRSTUVWXYZ
Breytist í: QWERTYUIOPASDFGHJKLZXCVBNM

Seinni línan er þá lykill dulritunarinnar, enda nægir hún til að dulrita og dulráða. Lykilstafrófið notar ávallt sömu stafi og venjulega stafrófið, en í annarri röð. Lykillinn skilgreinir hvernig stafirnir breytast. Í þessu dæmi verður t.d.

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

Þessi tegund dulritunar kallast umskipti (e. substitution cipher), þ.e. þar sem hverjum staf er skipt út fyrir annan staf.

Prófum að nota lykilinn að ofan til að dulrita HELLO:

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

Við endum þá með dulritaða textann

HELLO → ITSSG

ITSSG VGKSR

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

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

V → W
G → O
K → R
S → L
R → D

HELLO WORLD

Veikleiki umbreytinga

Í dæminu hér að ofan sjáum við að í orðinu HELLO er sami stafurinn L í þriðja og fjórða sæti. Í dulritaða textanum ITSSG er einnig sami stafurinn S í sömu sætum.

Þetta er einn stærsti veikleiki þessarar tegundar dulritunar. Þó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.

Þrátt fyrir að gríðarlega mörg lykilstafróf séu í boði (u.þ.b. 400 kvaðrilljónir), eru tungumál ekki handahófskennd. Í íslensku, ensku og öðrum tungumálum koma sumir stafir og stafasamsetningar mun oftar fyrir en aðrar.

Í 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 langt dulrit getum við notað þessar upplýsingar til að giska á lykilinn.

Tíðnigreining

Tíðnigreining (e. frequency analysis) köllum við þá aðferð að telja hversu oft stafir, orð eða mynstur koma fyrir í texta. Tíðnigreiningin er náttúrulega háð því hvaða texti er notaður við greininguna, en oft er notast við texta sem endurspeglar algenga málnotkun. English Letter Frequency Counts: Mayzner Revisited er dæmi um tíðnigreiningu. Hún vann með texta sem innihélt um 700 milljarða af rúmlega 95.000 ólíkum orðum. Tíðni bókstafanna má sjá í eftirfarandi töflu.

Tíðnigreiningin sýndi einnig að algengustu orðin eru the, of og and. Algengustu stafapörin eru th, he, in og er og algengustu þrenndirnar eru the, and og ing.

Íslensk orðtíðnibók gefur okkur tíðni stafa í íslensku, sem sjá má í eftirfarandi töflu.

Tíðnigreining er eitt helsta vopnið sem við höfum til að brjóta dulritun með umskiptum. Þar sem umskipti virka þannig að hverjum staf er ávallt skipt út fyrir sama staf, viðhelst tíðni stafa, stafapara, stafaþrennda, o.s.frv. í dulritaða textanum. Þannig getur tíðnigreining á dulritaða textanum leiðbeint okkur um hvaða stöfum hefur líklega verið skipt út fyrir aðra.

Þegar við stöndum frammi fyrir texta sem okkur grunar að hafi verið dulritaður með umskiptum, getum við unnið eftir þessu ferli.

1. Framkvæmum tíðnigreiningu stafa á dulritinu.
2. Berum saman tíðnigreininguna á dulritinu við tíðnigreiningu á málinu sem við höldum að textinn sé skrifaður í. Giskum á að algengasti stafurinn sé einnig algengur stafur í tungumálinu og skoðum hvað kemur út úr því.
3. Leitum að stuttum orðum, sérstaklega tveggja og þriggja stafa orðum og berum saman við algeng orð.
4. Notum þekkt mynstur til að fylla út fleiri stafi.
5. Prófum ágiskanirnar í öllum textanum og leiðréttum ef augljósar villur koma upp.

from collections import Counter

text = open("words.txt", encoding="utf-8").read().lower()
counts = Counter(c for c in text if c.isalpha())
total = sum(counts.values())

for c, n in counts.most_common():
    print(f"{c}: {n / total * 100:.2f}%")

Það er mikilvægt að hafa í huga að tíðnigreining er fjarri því að vera fullkomin. Dulritaði textin gæti, til dæmis, innihaldið óvenjumikið magn af sjaldgæfum stöfum sem skekkja niðurstöðurnar. Almenna reglan er þó sú að því lengri sem textinn er, því áreiðanlegri er tíðnigreiningin.

ZIT YSQU OL IORRTF OF ZIT YOST

Z → t
I → h
T → e

the YSQU OL hORReF OF the YOSe

the YSQU is hiRReF iF the YiSe

ZIT YSQU OL IORRTF OF ZIT YOST

Z → t
I → h
T → e
O → i
L → s

the YSQU is hiRReF iF the YiSe

Y → f
S → l
Q → a
U → g

the flag is hiRReF iF the file

ZIT YSQU OL IORRTF OF ZIT YOST
the flag is hidden in the file

Vigenère-dulritun

Við höfum nú séð hvernig Caesar-dulritun virkar, þar sem við notum sama tilfærslulykil á hvern einasta staf í textanum okkar. Eins og við komumst að er auðvelt að brjóta slíka dulritun. En hvað ef við gætum gert ferlið aðeins flóknara? Hvað ef við myndum ekki alltaf nota sömu tilfærsluna, heldur skipta um tilfærslu fyrir hvern staf?

Vigenère-dulritun (e. Vigenère cipher) gerir nákvæmlega þetta. Í stað þess að nota eina fasta tölu sem lykil, notar þessi aðferð heilt orð sem lykil. Hver stafur í lyklinum segir okkur þá til um hversu mikið við eigum að færa samsvarandi staf í upprunalega textanum, rétt eins og í Caesar-dulritun. Við erum í raun að beita mörgum mismunandi Caesar-tilfærslum í röð.

Til að gera þetta breytum við stöfunum í lyklinum í tölur. Ef við miðum við enska stafrófið byrjum við að telja á núlli: A jafngildir 0, B er 1, C er 2, og svo framvegis upp í Z sem er 25.

Segum sem svo að við notum lykilinn LEMON til að dulrita textann ATTACKATDAWN.

Fyrst skrifum við textann okkar niður og endurtökum svo lykilinn undir honum aftur og aftur þar til það nær yfir allan textann:

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

Nú tökum við fyrsta stafinn í textanum, A, og fyrsta stafinn í lyklinum, L. Stafurinn L er tólfti stafurinn í stafrófinu (ef við byrjum að telja á núlli, þar sem A=0), svo lykillinn er 11. Við færum A áfram um 11 sæti og fáum L.

Næsti stafur er T og lykilstafurinn er E. Stafurinn E jafngildir 4 (A=0, B=1, C=2, D=3, E=4). Við færum T áfram um 4 sæti: U, V, W, X. Útkoman er því X.

Þannig höldum við áfram með hvern staf:

A fært um L (11) → L
T fært um E (4)  → X
T fært um M (12) → F
A fært um O (14) → O
C fært um N (13) → P

Þegar við höfum farið í gegnum alla stafina fæst endanlegi dulritaði textinn okkar:

ATTACKATDAWN → LXFOPVEFRNHR

Sögulega séð var oft notuð sérstök tafla, kölluð Tabula Recta eða Vigenère-taflan, til að fletta upp þessum tilfærslum á fljótlegan hátt í stað þess að telja í huganum.

Nú þegar við vitum hvernig á að dulrita, hvernig förum við að því að dulráða texta ef við þekkjum lykilinn? Það er nákvæmlega sama ferli, nema í öfuga átt.

IITNFZ

Dulrit: I I T N F Z
Lykill: B I R D B I

I fært til baka um B (1)  → H
I fært til baka um I (8)  → A
T fært til baka um R (17) → C
N fært til baka um D (3)  → K
F fært til baka um B (1)  → E
Z fært til baka um I (8)  → R

IITNFZ → HACKER

RIJVS UYVJN

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

R fært til baka um K (10) → H
I fært til baka um E (4)  → E
J fært til baka um Y (24) → L  (hér förum við framhjá A og byrjum aftur á Z)
V fært til baka um K (10) → L
S fært til baka um E (4)  → O

U fært til baka um Y (24) → W
Y fært til baka um K (10) → O
V fært til baka um E (4)  → R
J fært til baka um Y (24) → L
N fært til baka um K (10) → D

HELLO WORLD

Hvers vegna er Vigenère ekki nóg?

Eins og við sáum í dæminu hér að ofan er Vigenère-dulritunin mun sterkari en hefðbundin Caesar-dulritun og önnur umskipti. Ástæðan fyrir því er sú að sami upprunalegi stafurinn getur orðið að ólíkum dulritsstöfum, allt eftir því hvar hann lendir í textanum. Til dæmis gæti stafurinn A orðið að L í eitt skipti, en að E eða O í næsta skipti, algjörlega háð því hvaða lykilstafur er notaður nákvæmlega á þeim tímapunkti. Þetta gerir hefðbundna tíðnigreiningu ónothæfa.

En ákveðnir gallar leynast þó í hönnun dulritunarinnar. Alla jafna er lykilorðið mjög stutt, samanborið við lengd skilaboðanna, og það því endurtekið oft við dulritunina.

Ef greiningaraðili fær nógu langan dulritaðan texta í hendurnar getur hann tekið eftir endurteknum stafavenslum. Út frá fjarlægðinni milli þessara endurtekninga er hægt að giska á hversu langt lykilorðið er. Þegar lengd lykilorðsins er fundin (segjum til dæmis að hún sé 5 stafir), þá getur greiningaraðilinn skipt dulritinu upp í 5 mismunandi hópa. Hver þessara hópa var í raun dulritaður með nákvæmlega sömu Caesar-tilfærslunni! Þar með er einfaldlega hægt að beita venjulegri tíðnigreiningu á hvern hóp fyrir sig.

Þetta er frábært dæmi um mjög mikilvæga grunnreglu í allri dulritun: jafnvel þótt aðferð virðist fela einföld mynstur vel við fyrstu sýn, þá getur hún samt lekið mikilvægum upplýsingum (og mynstrum) ef hún er notuð á mikið magn gagna eða ef lykillinn er endurtekinn of oft.

Umröðun

Allar þær aðferðir sem við höfum rætt fram að þessu eiga það sameiginlegt að þær byggja á því að skipta einum staf út fyrir annan. Þær breyta því hvaða stafur stendur á ákveðnum stað í textanum. En það er til önnur mjög einföld hugmynd að dulritun, sem er sú að breyta engum stöfum, heldur einfaldlega breyta röðinni á þeim. Þessi tegund dulritunar kallast umröðunardulritun (e. transposition cipher).

Segjum að við viljum senda skilaboðin THEHIDDENFLAGISINTHISFILE. Við ákveðum að nota umröðunardulritun með fjórum dálkum og skrifum þá textann okkar niður línu fyrir línu, þannig að hver lína hafi fjóra stafi.

Þar sem skilaboðin okkar innihalda 25 stafi passa þau ekki nákvæmlega í 4 dálka (næsta margfeldi af 4 er 28). Til þess að taflan gangi upp, þ.e. allir dálkarnir jafn langir, fyllum við upp í síðustu línuna með auka stöfum, í okkar tilfelli X. Þetta er kallað fylling (e. padding).

Þá lítur uppsetningin svona út

T H E H
I D D E
N F L A
G I S I
N T H I
S F I L
E X X X

Til að smíða dulritið okkar, lesum við núna textann upp úr töflunni dálk fyrir dálk (ofan frá og niður) í stað þess að lesa hann línu fyrir línu:

TINGNSE HDFITFX EDLSHIX HEAILX

Athugum að hér hefur engum staf verið breytt, T er ennþá T og H er ennþá H. Þeir hafa aðeins skipt um sæti. Sá sem fær þessi skilaboð og veit að textanum var upprunalega skipt í fjóra dálka, getur einfaldlega skrifað dulritið aftur upp ofan frá og niður í fjóra dálka (þar sem hver dálkur er \(28 / 4 = 7\) stafir að lengd), og lesið síðan skilaboðin sín línu fyrir línu til að fá aftur THEHIDDENFLAGISINTHISFILEXXX. Einnig má oft sjá fjölda dálka á fjölda „orða“ í dulritinu, eins og í tilfellinu hér að ofan, en stundum er dulritið skrifað sem einn langur strengur, án bila.

Æfing

TSDM HSIM EWSN POAX ARDX

T H E P A
S S W O R
D I S A D
M I N X X

THEPASSWORDISADMINXX