Over de Vigenère-code

Inleiding

Op vrijdag 29 maart 2002 stond in het Cultureel Supplement van NRC Handelsblad een artikel getiteld "Het Mysterie van Patjitan". De auteur Rudy Kousbroek schrijft hierin over een grafsteen in een tempeltje aan de Zuidkust van Java. De inscriptie op deze grafsteen is gecodeerd. Generaties hebben vergeefs geprobeerd deze code te ontcijferen. Zo'n tien jaar geleden is het Willem Remmelink gelukt de code te kraken (hij schreef hierover in 1995 een artikel in het Franse tijdschrift Archipel). Kousbroek daagde in zijn artikel in het NRC de lezers uit de code te kraken. Hij verklapt hierbij wel dat het om een code van het type Vigenère gaat. Voor een poëtischer probleemstelling verwijs ik graag naar het artikel van Kousbroek (dat helaas niet op internet staat).

Ik heb de code van de grafsteen gekraakt met behulp van een computer. Mijn resultaten zal ik later presenteren, eerst volgt hier een korte uitleg over de gebruikte coderingssystemen en de methoden om ze te kraken. Verder kunt u op deze pagina door middel van allerlei programmaatjes zelf experimenteren met de verschillende codes. De oplossing van de code van Patjitan vindt u hier (dat document veronderstelt wel enige voorkennis die u in deze pagina kunt opdoen).

Codes van het type Caesar

Werking

De simpelste manier om een tekst te coderen is via substitutie: elke letter van het alfabet wordt met een bepaald aantal tekens verschoven. Deze codering werd al door Caesar gebruikt en is ook naar hem genoemd. Een voorbeeld van zo'n code is: a wordt C, b wordt D, c wordt E, ... x wordt Z, y wordt A, z wordt B (ik zal in de notatie steeds hoofdletters gebruiken voor de gecodeerde tekst en kleine letters voor het origineel). Hierbij hoort de volgende tabel:

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

In deze code zou het woord "coderen" gecodeerd worden met "EQFGTGP". Merk op dat het niet nodig is om van alle letters te specificeren wat ze moeten worden: als je weet wat de a wordt, dan volgt de codering van de rest van de letters hieruit. De codering van de a (in het voorbeeld hierboven dus de C) zou de codeletter genoemd kunnen worden.

Het decoderen van de tekst gaat op een analoge manier: men neme de gecodeerde tekst en schuive elke letter precies zo ver terug als nodig is. Hoever wordt bepaald door de codeletter. Uiteraard zou je ook alle letters juist een aantal plaatsen verder kunnen schuiven; immers, als je alle letters 26 posities naar rechts verschuift, ben je weer terug bij het begin. Het decoderen van een tekst die gecodeerd is met codeletter B komt zo overeen met het coderen met codeletter Z.

Demonstratie

Hieronder kunt u de Caesar-codering proberen. Typ in het linkervak de te (de)coderen tekst in, en vergeet vooral niet de codeletter in te vullen. Als u nu op "Codeer" klikt, verschijnt in het rechtervak de gecodeerde tekst. De spaties in de originele tekst worden gewist, als deze in de codering zouden blijven staan dan zou het (door woorden als "de") wel erg makkelijk worden de code te kraken.

Codeletter:

Kraken

Deze manier van coderen heeft als nadeel dat hij erg makkelijk te kraken is. Men kan namelijk kijken naar de letterfrequenties, die kenmerkend zijn voor een taal. Als in de gecodeerde tekst de letter G het meest voorkomt, dan kan - zeker in langere teksten - worden aangenomen dat deze letter voor de e staat. De rest van de codering laat zich nu eenvoudig afleiden.

Hieronder volgt een programmaatje waarmee voor een tekst de letterverdeling bepaald kan worden. Typ (of knip en plak) de te analyseren tekst (in code) in het tekstvak en klik op "Analyseer". Hierop verschijnt in de vakjes onderaan de letterverdeling. Hieronder staat nog een rij letters. Probeer deze (door middel van het knopje rechts) zo op te schuiven dat de letterverdeling bij gewone taal past (dus een hoog getal bij de e en een laag getal bij de x).

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

De letter die nu boven de a staat is nu de codeletter om de code te ontcijferen.

Codes van het type Vigenère

Werking

Omdat codes van het type Caesar zo makkelijk gekraakt kunnen worden (uiteraard is het zonder computer wel iets lastiger), is in de 16^e eeuw door Blaise de Vigenère een betere codering bedacht. Deze codering lijkt wel een beetje op de Caesar-codering. Nu nemen we echter in plaats van een codeletter een codewoord. Dit codewoord wordt boven de originele tekst geschreven. Elke letter wordt nu volgens een Caesar-codering gecodeerd, met als codeletter de letter die erboven staat. Een voorbeeld: we nemen als codewoord "LOPEN" en coderen de tekst "de schat ligt twintig stappen van de boom". Eerst schrijven we het codewoord boven de originele tekst:

LO PENLO PENL OPENLOP ENLOPEN LOP EN LOPE
de schat ligt twintig stappen van de boom

Voor het coderen gebruiken we de volgende codeertabellen:

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

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

Nu wordt de eerste letter, de d, gecodeerd met codeletter L. Dit levert een O op. De tweede letter, de e, wordt gecodeerd met codeletter O, hetgeen een S oplevert. Zo gaan we verder en we vinden de codering
OSHGULHAMTEHLMAEWVWGLDEIAGOCHRMCDQ

Ook het decoderen gaat analoog aan de Caesar-manier. Elke letter wordt opgezocht in de corresponderende tabel. Ook kan voor alle letters de decodeerletter worden bepaald. Het decodeerwoord van "LOPEN" is samengesteld uit de decodeerletters en luidt "PMLWN".

Demonstratie

Hieronder kunt u de Vigenère-codering proberen. Als codewoord kunt u woorden tot een lengte van 12 tekens opgeven. De besturing gaat hetzelfde als bij het Caesar-programma.

Codewoord:

Kraken

Het kraken van codes van het type Vigenère is niet zo eenvoudig als het kraken van een Caesar-code (en dat was de bedoeling van meneer de Vigenère ook). De letterfrequenties in de code zijn namelijk afkomstig van meerdere coderingen. Het idee om de Vigenère-codering te kraken is nu om de tekst te splitsen in deelteksten, die elk gecodeerd zijn volgens de Caesar-methode. Hiertoe moeten we eerst weten hoe lang het codewoord is. Weten we dit eenmaal, dan kunnen we weer de frequentieanalyse loslaten op de deelteksten.

We bepalen nu dus eerst de lengte van het codewoord. Hiertoe maken we gebruik van een eigenschap van de Nederlandse taal. Als je twee Nederlandse teksten onder elkaar zet, blijkt het aantal overeenkomende letters op dezelfde positie ongeveer 6% te bedragen. Bij willekeurige letters is dit percentage slechts 3%. In het volgende voorbeeld is het aantal overeenkomende letters twee, inderdaad zo'n 6% (maar het wordt pas betrouwbaar bij langere teksten).

deschatligttwintigstappenvandeboom
oomdeschatligttwintigstappenvandeb
................x..........x......

Merk op dat dit aantal overeenkomsten niet verandert als we deze tekst volgens de Caesar-methode coderen: gelijke letters worden gelijke letters. We gaan deze grootheid nu voor een Vigenère-code bepalen, met een verschuiving zoals in het voorbeeld. Als we de tekst precies de lengte van het codewoord (of een veelvoud daarvan) naar rechts verplaatsen, dan zijn twee tekens die onder elkaar staan met dezelfde codeletter (Caesar) gecodeerd, en is de kans dat ze gelijk zijn dus 6%. Verplaatsen we de tekst niet een veelvoud van de lengte van het codewoord, dan zijn twee letters die onder elkaar staan met een verschillende codeletter gecodeerd en is de kans dat ze gelijk zijn dus maar zo'n 3%.

Door nu voor een gecodeerde tekst voor verschuiving van 1, 2, 3, ... te bepalen hoeveel overeenkomsten er zijn, kunnen we bepalen wat de lengte van het codewoord waarschijnlijk wel zal zijn. Het onderstaande programma berekent voor de ingevoerde tekst de hoeveelheden overeenkomsten voor en verschuiving van 1 t.m. 12 (langere codewoorden worden meestal niet gebruikt).

Verschuiving	1	2	3	4	5	6	7	8	9	10	11	12
Overeenkomsten

Hierboven moet een duidelijke piek ontstaan bij een bepaalde verschuiving (en al zijn veelvouden). Als deze piek niet duidelijk is, dan is de originele tekst niet lang genoeg om gebruik te kunnen maken van deze statistiek, en zullen we de lengte van het codewoord moeten gokken.

Stel nu dat de lengte van het codewoord n is. We verdelen nu de gecodeerde tekst over n kortere codes (subcodes), die elk volgens de Caesar-methode gecodeerd zijn, en die we dus via de letterverdeling kunnen kraken. Dit uitdelen gaat als volgt: de eerste letter gaat naar subcode 1, de tweede naar subcode 2, enzovoorts tot en met de n-de letter. De letter na de n-de letter gaat weer naar subcode 1. Ik zal deze gang van zaken proberen te verduidelijken met een voorbeeld. We hebben de tekst "de schat ligt twintig stappen van de boom" met het codewoord "LOPEN" gecodeerd tot
OSHGULHAMTEHLMAEWVWGLDEIAGOCHRMCDQ.
Via de bovenstaande methode zouden we bepaald of gegokt moeten hebben dat de lengte van het codewoord 6 is. De code wordt nu als volg verdeeld over de subcodes:

Subcode 1:	OHLWAM
Subcode 2:	SAMGGC
Subcode 3:	HMALOD
Subcode 4:	GTEDCQ
Subcode 5:	UEWEH
Subcode 6:	LHVIR

Deze subcodes zouden via frequentieanalyse gekraakt moeten worden. Dit is waarschijnlijk voor het bovenstaande voorbeeld niet mogelijk, omdat de teksten te kort zijn. (Voor korte teksten is een Vigenère-codering dus heel geschikt!)

Hieronder volgt nog een programmaatje om een code "uit te delen" over subcodes. Hierbij moet uiteraard worden opgegeven om hoeveel subcodes het gaat. Dit programma werkt voor maximaal 12 subcodes.

Lengte van codewoord:
Code:

Subcode 1:	Subcode 7:
Subcode 2:	Subcode 8:
Subcode 3:	Subcode 9:
Subcode 4:	Subcode 10:
Subcode 5:	Subcode 11:
Subcode 6:	Subcode 12:

Deze subcodes kunnen worden gekraakt door middel van frequentieanalyse. Voor elke subcode volgt hieruit (als het goed is) een codeletter. Deze letters vormen samen het codewoord, waarmee de code gekraakt kan worden.

Casus NRC

Klik hier voor de uitwerking van het bovenstaande voor de grafsteen uit het NRC Handelsblad.

Voor een andere tekst die met de Vigenère code gecodeerd is, zie Simon Singh's pagina.

Bronvermelding

• Rudy Kousbroek, Het Mysterie van Patjitan. In: NRC Handelsblad, Cultureel Supplement, vrijdag 29 maart 2002.
• The Code Book, Simon Singh. Een uitstekend inleidend werk over allerlei codes, met leuke verhalen eromheen!

Als u naar aanleiding van het bovenstaande vragen heeft (of als het niet werkt), mag u mij gerust e-mailen. Mijn e-mailadres is T.J.Dijkema@gmail.com.