In 1918 bedacht John Byrne een cryptografisch toestel met twee schijven, dat hij een chaocipher noemde. Hij tekende blauwdrukken, maar slaagde er niet in om het toestel te verkopen aan het Amerikaanse leger. In zijn autobiografie Silent Years uit 1954 liet hij bij wijze van uitdaging verschillende gecodeerde berichten achter, maar niemand slaagde erin om die te ontcijferen. Onlangs, na de dood van Byrne's zoon, schonk de weduwe van zijn zoon de volledige archieven, inclusief een prototype van het toestel, aan het National Cryptologic Museum in Fort Meade, Maryland, VSA. In 2010 publiceerde Moshe Rubin de eerste publieke beschrijving van het chaocipher algoritme.

Hoewel John Byrne een fysiek toestel in gedachten had toen hij het chaocipher uitvond, gebruiken we in de volgende uiteenzetting een vereenvoudigd model waarin we abstractie maken van de schijven. We stellen het alfabet van elke schijf voor als een string van 26 hoofdletters, corresponderend met een permutatie van de 26 letters van het standaardalfabet (A-Z) die rondom de schijf geplaatst worden. De configuratie van de twee schijven in het chaocipher toestel, stellen we dan op de volgende manier voor:

                +            *
     LEFT (ct): HXUCZVAMDSLKPEFJRIGTWOBNYQ
    RIGHT (pt): PTLNBQDEOYSFAVZKGJRIHWXUMC
                --------------------------
      Position: 12345678911111111112222222
                         01234567890123456

Hierbij is het belangrijk om op te merken dat het rechter alfabet (RIGHT) gebruikt wordt om letters uit het originele bericht (plaintext; pt) op te zoeken, terwijl het linker alfabet (LEFT) gebruikt wordt om letters in het gecodeerde bericht (ciphertext; ct) op te zoeken. Let ook op de twee symbolen + en * die boven de alfabetten staan. In de beschrijving van Byrne worden deze zenit en nadir genoemd, als verwijzing naar de eerste en de veertiende positie in de alfabetten. Deze posities zullen een belangrijke rol spelen bij het permuteren van de alfabetten tijdens het coderen en decoderen. Zowel in de voorstelling van het toestel als in de omschrijving van het algoritme zullen we de posities in de alfabetten van links naar rechts nummeren vanaf één.

Overzicht van het chaocipher algoritme

Gegeven twee alfabetten die uitgelijnd zijn ten opzichte van hun respectievelijke zenit-posities, verloopt het coderen van een letter uit het originele bericht in drie stappen:

1. de gecodeerde letter staat in het linker alfabet op dezelfde positie als de originele letter in het rechter alfabet

2. permuteer het linker alfabet

3. permuteer het rechter alfabet

Deze drie stappen worden herhaaldelijk uitgevoerd, totdat alle letters van het originele bericht gecodeerd zijn. Als voorbeeld zullen we nu de letter A coderen, vertrekkende vanaf bovenstaande configuratie van de schijven.

Coderen van een bericht

Om een letter te coderen, zoeken we de positie van de letter op in het rechter (pt) alfabet. De letter die in het linker (ct) alfabet boven de originele letter staat, is de gecodeerde letter. Om bijvoorbeeld de letter A uit ons voorbeeld te coderen, zoeken we de letter in het rechter (pt) alfabet (op positie 13) en nemen we de corresponderende letter die er direct boven staat in het linker (ct) alfabet, wat in dit geval de letter P is. De letter A in het originele bericht wordt dus gecodeerd als de letter P (zie verticale pijl ↓):

                +           ↓*
     LEFT (ct): HXUCZVAMDSLKPEFJRIGTWOBNYQ
    RIGHT (pt): PTLNBQDEOYSFAVZKGJRIHWXUMC
                --------------------------
      Position: 12345678911111111112222222
                         01234567890123456

Nu we de originele letter gecodeerd hebben, kunnen we doorgaan met het permuteren van de twee alfabetten als voorbereiding op het coderen van de volgende letter uit het originele bericht. Hierbij benadrukken we dat het linker en rechter alfabet gepermuteerd worden met kennis van de positie waarop de originele en gecodeerde letters gevonden werden.

Permutatie van het linker alfabet

Een permutatie van het linker alfabet omvat de volgende stappen:

1. roteer het volledige linker alfabet cyclisch, zodat de gecodeerde letter in het zenit komt te staan (positie 1)

2. verwijder de letter op positie zenit+1 (dit is de letter rechts van het zenit) uit het alfabet, waardoor er op die positie tijdelijk een gat ontstaat

3. schuif alle letters op posities zenit+2 tot en met nadir (zenit+13) één positie op naar links

4. plaats de verwijderde letter op de positie van de nadir (zenit+13)

Laten we de bovenstaande stappen eens uitvoeren op het linker (ct) alfabet uit ons voorbeeld. Bij het uitvoeren van stap (1) roteren we het volledige alfabet zodat de gecodeerde letter P in het zenit komt te staan:

           +            *
LEFT (ct): PEFJRIGTWOBNYQHXUCZVAMDSLK

Bij het uitvoeren van stap (2) verwijderen we de letter op positie zenit+1 (dit is de letter E) waardoor tijdelijk een gat ontstaat. Daardoor ziet het alfabet er op dit moment als volgt uit:

           +            *
LEFT (ct): P.FJRIGTWOBNYQHXUCZVAMDSLK

Voor stap (3) schuiven we alle letters op posities zenit+2 (F) tot en met nadir (Q) één positie op naar links, waardoor de reeks FJRIGTWOBNYQ als een volledig blok één positie naar links opschuift. Het alfabet ziet er nu als volgt uit:

           +            *
LEFT (ct): PFJRIGTWOBNYQ.HXUCZVAMDSLK

In de laatste stap (4) plaatsen we de verwijderde letter (E) terug in het alfabet op de positie van de nadir:

           +            *
LEFT (ct): PFJRIGTWOBNYQEHXUCZVAMDSLK

Dit is het nieuwe gepermuteerde linker (ct) alfabet.

Permutatie van het rechter alfabet

Het permuteren van het rechter alfabet gebeurt analoog aan de permutatie van het linker alfabet, met kleine maar significante verschillen. De permutatie bestaat nu uit de volgende stappen:

1. roteer het volledige rechter alfabet cyclisch, zodat de originele letter in het zenit komt te staan (positie 1)

2. roteer het volledige rechter alfabet nu nog één keer cyclisch naar links (de letter uiterst links schuift zo cyclisch op naar de positie uiterst rechts), waardoor een nieuwe letter in het zenit komt te staan

3. verwijder de letter op positie zenit+2 uit het alfabet, waardoor er op die positie tijdelijk een gat ontstaat

4. schuif alle letters op posities zenit+3 tot en met nadir (zenit+13) één positie op naar links

5. plaats de verwijderde letter op de positie van de nadir (zenit+13)

Laten we ook bovenstaande stappen eens uitvoeren op het rechter (pt) alfabet uit ons voorbeeld. Bij het uitvoeren van stap (1) roteren we het volledige alfabet zodat de originele letter A in het zenit komt te staan:

            +            *
RIGHT (pt): AVZKGJRIHWXUMCPTLNBQDEOYSF

In stap (2) roteren we het volledige alfabet nog één keer naar links, waardoor de letter V in het zenit komt te staan (vergeet deze extra stap dus niet bij het permuteren van het rechter (pt) alfabet):

            +            *
RIGHT (pt): VZKGJRIHWXUMCPTLNBQDEOYSFA

Daarna, in stap (3), verwijderen we de letter twee posities rechts van het zenit (dit is de letter K) tijdelijk uit het alfabet. Daardoor ziet het alfabet er op dit moment als volgt uit:

            +            *
RIGHT (pt): VZ.GJRIHWXUMCPTLNBQDEOYSFA

Voor stap (4) schuiven we alle letters rechts van het gat tot en met nadir één positie op naar links, waardoor de reeks GJRIHWXUMCP één positie naar links opschuift:

            +            *
RIGHT (pt): VZGJRIHWXUMCP.TLNBQDEOYSFA

Als laatste stap, stap (5), plaatsen we de verwijderde letter (K) terug in het alfabet op de positie van de nadir:

            +            *
RIGHT (pt): VZGJRIHWXUMCPKTLNBQDEOYSFA

Op dit moment hebben we dus twee nieuwe gepermuteerde alfabetten:

                +            *
     LEFT (ct): PFJRIGTWOBNYQEHXUCZVAMDSLK
    RIGHT (pt): VZGJRIHWXUMCPKTLNBQDEOYSFA

In een realistisch scenario zou het toestel nu klaarstaan om de volgende letter van het originele bericht te coderen. Het coderingsproces verloopt op dezelfde manier voor de opeenvolgende letters van het originele bericht: (a) zoek de positie van de letter in het rechter alfabet, (b) bepaal de corresponderende gecodeerde letter in het linker alfabet en (c) permuteer de twee alfabetten.

Coderen van een langer bericht

Nu we uitgelegd hebben hoe een letter uit een origineel bericht gecodeerd wordt, is het tijd om te oefenen zodat je jezelf kan overtuigen dat je de procedure correct begrepen hebt: codeer een bericht dat bestaat uit een reeks opeenvolgende letters op basis van twee gegeven alfabetten bij de start van de procedure. De alfabetten waarmee we zullen beginnen, zijn dezelfde die we hierboven ook al gebruikt hebben:

                +            *
     LEFT (ct): HXUCZVAMDSLKPEFJRIGTWOBNYQ
    RIGHT (pt): PTLNBQDEOYSFAVZKGJRIHWXUMC

Het bericht dat moet gecodeerd worden is:

    WELLDONEISBETTERTHANWELLSAID

Je hebt het algoritme begrepen als je het volgende gecodeerde bericht bekomt:

    OAHQHCNYNXTSZJRRHJBYHQKSOUJY

Om te kunnen debuggen, zijn hier alle alfabetten die je tijdens het uitvoeren van het algoritme zou moeten gegenereerd hebben:

Merk op dat je de gecodeerde tekst verticaal kan uitlezen als de letters uiterst links in de kolom met het linker alfabet, en dat je de originele tekst verticaal kan uitlezen als de letters uiterst rechts in de kolom met het rechter alfabet. Deze eigenschap is een direct gevolg van de procedure die gebruikt wordt bij het permuteren van de alfabetten, en kan gebruikt worden om je implementatie van de procedure te controleren.

Decoderen van een bericht

Het decoderen van een met de chaocipher gecodeerd bericht verloopt identiek als het coderen van een bericht. Het enige verschil zit hem in het feit dat de letters bij het decoderen moeten opgezocht worden in het linker (ct) alfabet, met de corresponderende originele letter in het rechter (pt) alfabet. Het permuteren van de alfabetten verloopt volledig identiek als bij het coderen.

Opgave

Definieer een klasse Disk waarmee een schijf die gebruikt wordt in een chaocipher toestel kan voorgesteld worden. Bij het aanmaken van een schijf (Disk) moet een permutatie van het standaardalfabet (String) doorgegeven worden. Als er geen String wordt doorgegeven die bestaat uit een permutatie van het standaardalfabet, dan moet een Error opgeworpen worden met de boodschap invalid alphabet. Voorts moet je op een schijf $$s$$ (Disk) minstens de volgende methoden kunnen aanroepen:

• Een methode toString waaraan geen argumenten moeten doorgeven worden. De methode moet het alfabet van schijf $$s$$ teruggeven (String; in hoofdletters).

• Een methode locate waaraan een letter $$l$$ (String) moet doorgegeven worden. De methode moet de positie (Number) teruggeven waarop letter $$l$$ voorkomt in het alfabet van schijf $$s$$. De methode mag geen onderscheid maken tussen hoofdletters en kleine letters.

• Een methode letter waaraan een getal $$i$$ (Number; $$1 \leq i \leq 26$$) moet doorgegeven worden. De methode moet de letter (String; als hoofdletter) teruggeven die voorkomt op positie $$i$$ in het alfabet van schijf $$s$$.

• Een methode rotate waaraan een getal $$r$$ (Number) moet doorgegeven worden. De methode moet het alfabet van schijf $$s$$ $$|r|$$ keer cyclisch roteren. Als $$r > 0$$ dan moet het alfabet naar links geroteerd worden. Als $$r < 0$$ dan moet het alfabet naar rechts geroteerd worden. De methode moet een verwijzing naar schijf $$s$$ teruggeven.

• Een methode roll waaraan twee getallen $$a, b \in \mathbb{N}$$ (Number; $$1 \leq a < b \leq 26$$) moeten doorgegeven worden. De methode moet eerst de letter op positie $$a$$ uit het alfabet van schijf $$s$$verwijderen, waardoor op die positie tijdelijk een gat ontstaat. Daarna moet de methode alle letters rechts van het gat tot en met positie $$b$$ één positie naar links opschuiven, en tenslotte de verwijderde letter terugplaatsen op positie $$b$$ in het alfabet van schijf $$s$$. De methode moet een verwijzing naar schijf $$s$$ teruggeven.

Definieer ook nog een klasse Chaocipher waarmee toestellen kunnen voorgesteld worden waarmee je berichten kunt coderen en decoderen volgens het chaocipher algoritme. Bij het aanmaken van een toestel (Chaocipher) moeten twee permutaties van het standaardalfabet doorgegeven worden, die respectievelijk de beginconfiguratie van de linker- en de rechterschijf van het toestel vastleggen. Voorts moet je op een toestel $$t$$ (Chaocipher) minstens de volgende methoden kunnen aanroepen:

• Een methode toString waaraan geen argumenten moeten doorgeven worden. De methode moet een stringvoorstelling (String) met de huidige configuratie van toestel $$t$$ teruggeven, in het formaat zoals het gebruikt werd bij de uiteenzetting van het chaocipher algoritme. Hierbij moeten de twee alfabetten steeds in hoofdletters weergegeven worden.

• Een methode encode waaraan een bericht (String) moet doorgegeven worden dat enkel bestaat uit letters. De methode moet de gecodeerde versie van het bericht teruggeven (String; in hoofdletters). Tijdens het coderen moeten de schijven van toestel $$t$$ gepermuteerd worden, zoals dat het geval is bij het chaocipher algoritme.

• Een methode decode waaraan een gecodeerd bericht (String) moet doorgegeven worden dat enkel bestaat uit letters. De methode moet het originele bericht teruggeven (String; in hoofdletters). Tijdens het decoderen moeten de schijven van toestel $$t$$ gepermuteerd worden, zoals dat het geval is bij het chaocipher algoritme.

Voorbeeld

>>> const disk = new Disk("HXUCZVAMDSLKPEFJRIGTWOBNYQ")
>>> disk.toString()
"HXUCZVAMDSLKPEFJRIGTWOBNYQ"
>>> disk.locate("P")
13
>>> disk.letter(13)
"P"
>>> disk.rotate(5).toString()
"VAMDSLKPEFJRIGTWOBNYQHXUCZ"
>>> disk.roll(5, 18).toString()
"VAMDLKPEFJRIGTWOBSNYQHXUCZ"

>>> new Disk("ABCDEFGHIJKLM")
Error: invalid alphabet

>>> let cipher = new Chaocipher("HXUCZVAMDSLKPEFJRIGTWOBNYQ", "PTLNBQDEOYSFAVZKGJRIHWXUMC")
>>> console.log(cipher.toString())
            +            *
 LEFT (ct): HXUCZVAMDSLKPEFJRIGTWOBNYQ
RIGHT (pt): PTLNBQDEOYSFAVZKGJRIHWXUMC
            --------------------------
  Position: 12345678911111111112222222
                     01234567890123456
>>> cipher.encode("WELLDONEISBETTERTHANWELLSAID")
"OAHQHCNYNXTSZJRRHJBYHQKSOUJY"
>>> console.log(cipher.toString())
            +            *
 LEFT (ct): YFJBGMTKWNOQXCHIDVALZRSPUE
RIGHT (pt): JIBMESWKYZXUCOPRTLNHFAGVQD
            --------------------------
  Position: 12345678911111111112222222
                     01234567890123456

>>> let cipher = new Chaocipher("HXUCZVAMDSLKPEFJRIGTWOBNYQ", "PTLNBQDEOYSFAVZKGJRIHWXUMC")
>>> console.log(cipher.toString())
            +            *
 LEFT (ct): HXUCZVAMDSLKPEFJRIGTWOBNYQ
RIGHT (pt): PTLNBQDEOYSFAVZKGJRIHWXUMC
            --------------------------
  Position: 12345678911111111112222222
                     01234567890123456
>>> cipher.decode("OAHQHCNYNXTSZJRRHJBYHQKSOUJY")
"WELLDONEISBETTERTHANWELLSAID"
>>> console.log(cipher.toString())
            +            *
 LEFT (ct): YFJBGMTKWNOQXCHIDVALZRSPUE
RIGHT (pt): JIBMESWKYZXUCOPRTLNHFAGVQD
            --------------------------
  Position: 12345678911111111112222222
                     01234567890123456

Bronnen

• Rubin M (2010). Chaocipher revealed: the algorithm. ¹