In 1929 vond Lester S. Hill1 een polygrafische substitutieversleuteling uit die op lineaire algebra gestoeld is. Het was de eerste polygrafische versleuteling waarmee het praktisch (hoewel ternauwernood) mogelijk was om meer dan drie symbolen tegelijkertijd te verwerken.
Onderstaande bespreking van hoe de Hill-versleuteling werkt, veronderstelt elementaire kennis van matrices. Je kunt dit paneel openklappen voor een samenvatting van de belangrijkste termen, notaties en bewerkingen.
Als $$\mathbf{A}$$ een $$m \times n$$ matrix is en $$\mathbf{B}$$ een $$n \times p$$ matrix \[ \mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} \,, \hspace{10mm} \mathbf{B} = \begin{pmatrix} b_{11} & b_{12} & \cdots & b_{1p} \\ b_{21} & b_{22} & \cdots & b_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{np} \end{pmatrix} \] dan is de matrixvermenigvuldiging $$\mathbf{C} = \mathbf{AB}$$ gedefinieerd als de $$m \times p$$ matrix \[ \mathbf{C} = \begin{pmatrix} c_{11} & c_{12} & \cdots & c_{1p} \\ c_{21} & c_{22} & \cdots & c_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \cdots & c_{mp} \end{pmatrix} \] zodat \[ c_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj} \] voor $$i = 1, \ldots, m$$ en $$j = 1, \ldots, p$$. De matrixvermenigvuldiging is dus enkel gedefinieerd als en slechts als het aantal kolommen van $$\mathbf{A}$$ gelijk is aan het aantal rijen van $$\mathbf{B}$$ (in dit geval $$n$$).
We gebruiken de notatie $$\mathcal{M}_n(\mathbb{Z})$$ voor de verzameling van alle vierkante $$n \times n$$ matrices met gehele getallen als elementen. Binnen $$\mathcal{M}_n(\mathbb{Z})$$ is de vermenigvuldiging van elke twee matrices gedefinieerd. De eenheidsmatrix van $$\mathcal{M}_n(\mathbb{Z})$$ noteren we als $$\mathbf{I}$$: een matrix met enen (1) op de hoofddiagonaal en nullen (0) op alle andere posities.
Een matrix $$\mathbf{A} \in \mathcal{M}_n(\mathbb{Z})$$ is omkeerbaar als er een matrix $$\mathbf{A}^{-1} \in \mathcal{M}_n(\mathbb{Z})$$ bestaat waarvoor geldt dat \[ \mathbf{A}\mathbf{A}^{-1} = \mathbf{A}^{-1}\mathbf{A} = \mathbf{I} \] We zeggen dan dat $$\mathbf{A}^{-1}$$ de inverse matrix is van matrix $$\mathbf{A}$$, maar niet alle matrices zijn omkeerbaar.
Een $$n$$-component vector $$v$$ is een $$n \times 1$$ matrix met $$n$$ rijen en slechts één kolom. De matrixvermenigvuldiging $$w = \mathbf{A}v$$ van een matrix $$\mathbf{A} \in \mathcal{M}_n(\mathbb{Z})$$ en een $$n$$-component vector $$v$$ is altijd gedefinieerd en levert opnieuw een $$n$$-component vector $$w$$ op. Als $$\mathbf{A}$$ omkeerbaar is, dan geldt ook dat $$\mathbf{A}^{-1}w = v$$.
Elke letter wordt voorgesteld door zijn positie in het alfabet: A=0, B=1, ..., Z=25. Er wordt geen onderscheid gemaakt tussen hoofdletters en kleine letters, en er wordt altijd modulo2 26 gerekend met gehele getallen.
Om een klare tekst te coderen, wordt elk blok van $$n$$ letters geïnterpreteerd als een $$n$$-component vector. Die vector wordt modulo 26 vermenigvuldigd met een omkeerbare $$n \times n$$ matrix $$\mathbf{A}$$. Om de cijfertekst te decoderen, wordt elk blok van $$n$$ letters modulo 26 vermenigvuldigd met de inverse matrix $$\mathbf{A}^{-1}$$.
De matrix $$\mathbf{A}$$ die bij het coderen gebruikt wordt, vormt de sleutel van de Hill-versleuteling. Die matrix moet willekeurig gekozen worden uit de omkeerbare matrices van $$\mathcal{M}_n(\mathbb{Z})$$ (modulo 26). Stel bijvoorbeeld dat $$n=3$$ en dat we deze sleutel uit $$\mathcal{M}_3(\mathbb{Z})$$ gebruiken: \[ \mathbf{A} = \begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \] Om de klare tekst Hill Cipher te coderen, schrappen we eerst alle karakters die geen letter zijn: HILLCIPHER (voor de eenvoud zullen we vanaf nu alle letters in hoofdletters zetten). Daarna vullen we de 10 letters van deze tekst aan met twee extra letters (bijvoorbeeld X) zodat de lengte een veelvoud wordt van $$n = 3$$: HILLCIPHERXX. Nu kunnen we de tekst opdelen in blokken van $$n=3$$ letters: HIL-LCI-PHE-RXX.
We leggen uit hoe het eerst blok HIL kan gecodeerd worden tot een blok van drie nieuwe letters. Omdat H=7, I=8 en L=11 kan dit blok voorgesteld worden als de 3-component vector \[ v = \begin{pmatrix} 7 \\ 8 \\ 11 \end{pmatrix} \] De gecodeerde 3-component vector $$w$$ wordt dan berekend als \[ w = \mathbf{A}v = \begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix}\ \begin{pmatrix} 7 \\ 8 \\ 11 \end{pmatrix} = \begin{pmatrix} 245 \\ 329 \\ 441 \end{pmatrix} = \begin{pmatrix} 11 \\ 17 \\ 25 \end{pmatrix}\!\!\!\!\!\mod{26} \] Omdat 11=L, 17=R en 25=Z correspondeert deze gecodeerde 3-component vector met het blok LRZ in de cijfertekst. De overige blokken worden op een analoge manier gecodeerd, waardoor de klare tekst HIL-LCI-PHE-RXX gecodeerd wordt als de cijfertekst LRZ-SVK-CJL-BNK (waarbij we enkel ter illustratie koppeltekens tussen de blokken geplaatst hebben).
Om de cijfertekst LRZSVKCJLBNK te decoderen, delen we die eerst terug op in blokken van $$n=3$$ letters: LRZ-SVK-CJL-BNK. Bij het decoderen gebruiken we de inverse matrix van de sleutel \[ \mathbf{A}^{-1} = \begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix}^{-1}\!\!\!\!\mod{26} = \begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix} \] Het eerste blok van de cijfertekst wordt dan gedecodeerd als \[ v = \mathbf{A}^{-1}w = \begin{pmatrix} 8 & 5 & 10 \\ 21 & 8 & 21 \\ 21 & 12 & 8 \end{pmatrix}\ \begin{pmatrix} 11 \\ 17 \\ 25 \end{pmatrix} = \begin{pmatrix} 423 \\ 892 \\ 635 \end{pmatrix} = \begin{pmatrix} 7 \\ 8 \\ 11 \end{pmatrix}\!\!\!\!\!\mod{26} \] wat zoals verwacht terug het blok HIL oplevert.
Opgave
Definieer drie klassen waarmee Hill-versleuteling kan uitgevoerd worden: Matrix, Blok en Hill.
Matrix
De klasse Matrix kan gebruikt worden om te werken met $$m \times n$$ matrices over $$\mathbb{Z}_{26}$$. Daarbij betekent $$\mathbb{Z}_{26}$$ dat er altijd modulo3 26 gerekend wordt met gehele getallen. Bij het aanmaken van een nieuwe matrix (Matrix) moet een arrayvoorstelling van de matrix doorgegeven worden: een array (Array) met de $$m$$ rijen van de matrix die van boven naar onder opgelijst worden, waarbij elke rij voorgesteld wordt als een array (Array) met de $$n$$ elementen (Number) van de rij die van links naar rechts opgelijst worden. Hierbij mag er altijd van uitgegaan worden dat er een geldige arrayvoorstelling van een matrix wordt doorgegeven, zonder dat dit expliciet moet gecontroleerd worden. De elementen van de arrayvoorstelling moeten niet per se in het interval $$[0, 26[$$ liggen. Een matrix (Matrix) is onveranderlijk, dus na het aanmaken wijzigt die nooit meer.
Voorts moet een matrix $$\mathbf{A}$$ (Matrix) minstens de volgende getters4 (of objecteigenschappen) aanbieden:
-
Een getter rijen die het aantal rijen (Number) van matrix $$\mathbf{A}$$ teruggeeft.
-
Een getter kolommen die het aantal kolommen (Number) van matrix $$\mathbf{A}$$ teruggeeft.
-
Een getter matrix die een nieuwe arrayvoorstelling van matrix $$\mathbf{A}$$ teruggeeft. Deze arrayvoorstelling moet alle elementen modulo 26 voorstellen (dus binnen het interval $$[0, 26[$$).
-
Een getter isVector die een Booleaanse waarde (Boolean) teruggeeft om aan te geven of $$\mathbf{A}$$ een vector is.
-
Een getter isVierkant die een Booleaanse waarde (Boolean) teruggeeft om aan te geven of $$\mathbf{A}$$ een vierkante matrix is.
-
Een getter isEenheid die een Booleaanse waarde (Boolean) teruggeeft om aan te geven of $$\mathbf{A}$$ een eenheidsmatrix is.
-
Een getter blok. Als matrix $$\mathbf{A}$$ geen vector is dan moet er een Error opgeworpen worden met de boodschap ongeldige vector. Anders moet de blokvoorstelling (Blok; zie verder) van de vector teruggegeven worden.
Op een $$m_A \times n_A$$ matrix $$\mathbf{A}$$ (Matrix) moet een methode maal kunnen aangroepen worden waaraan een argument $$\mathbf{B}$$ moet doorgegeven worden. Deze methode moet een nieuwe matrix (Matrix) teruggeven die correspondeert met het product $$\mathbf{A}\mathbf{B}$$, als die matrixvermenigvuldiging gedefinieerd is. Dat laatste is enkel het geval als $$\mathbf{B}$$ een $$m_B \times n_B$$ matrix $$\mathbf{B}$$ (Matrix) is waarvoor geldt dat $$m_B = n_A$$. Als dat niet het geval is dan moet een Error opgeworpen worden met de boodschap ongeldige matrixvermenigvuldiging.
Blok
De klasse Blok kan gebruikt worden om te werken met blokken uit de Hill-versleuteling. Blokken kunnen als string (String; een reeks van $$n$$ letters) en als vector (Matrix; een matrix met $$n$$ rijen en slechts één kolom) voorgesteld worden. Bij het aanmaken van een nieuw blok (Blok) moet de stringvoorstelling van het blok doorgegeven worden. Hierbij mag er altijd van uitgegaan worden dat de gegeven stringvoorstelling enkel uit letters bestaat — zowel hoofdletters als kleine letters zijn toegelaten — zonder dat dit expliciet moet gecontroleerd worden. Een blok (Blok) is onveranderlijk, dus na het aanmaken wijzigt het nooit meer.
Op een blok $$v$$ (Blok) moet een methode toString kunnen aangeroepen worden (zonder argumenten), die een stringvoorstelling (String) van blok $$v$$ teruggeeft waarin alle letters voorgesteld worden als hoofdletters.
Daarnaast moet een blok $$v$$ (Blok) ook een getter5 (of objecteigenschap) vector aanbieden die de vectorvoorstelling (Matrix) van blok $$v$$ teruggeeft.
Hill
De klasse Hill kan gebruikt worden om sleutels voor te stellen waarmee je berichten kunt coderen en decoderen volgens de Hill-versleuteling. Het is niet nodig om zelf de inverse van een sleutel te berekenen (als die al bestaat), want bij het aanmaken van een nieuwe sleutel (Hill) moeten twee matrices (Matrix) doorgegeven worden: de matrix $$\mathbf{A}$$ die gebruikt wordt om te coderen en de matrix $$\mathbf{B}$$ die gebruikt wordt om te decoderen. Als $$\mathbf{A}$$ of $$\mathbf{B}$$ geen vierkante $$n \times n$$ matrix is (Matrix; voor dezelfde dimensie $$n$$) of als $$\mathbf{B}$$ niet de inverse matrix is van $$\mathbf{A}$$ ($$\mathbf{A}\mathbf{B} = \mathbf{I}$$) dan moet er een Error opgeworpen worden met de boodschap ongeldige sleutel.
Op een sleutel $$s$$ (Hill) moet je minstens de volgende methoden kunnen aanroepen:
-
Een methode codeer waaraan een klare tekst $$t$$ (String) moet doorgegeven worden. De methode heeft ook nog een optionele parameter aanvulling waaraan een hoofdletter (String; standaardwaarde X) kan doorgegeven worden die gebruikt wordt om bij het coderen de tekst aan te vullen totdat zijn lengte een veelvoud is van de dimensie $$n$$ van sleutel $$s$$. De methode moet de cijfertekst (String; in hoofdletters) teruggeven die je bekomt door klare tekst $$t$$ te coderen volgens de Hill-versleuteling met sleutel $$s$$.
-
Een methode decodeer waaraan een cijfertekst $$t$$ (String) moet doorgegeven worden die gecodeerd werd volgens de Hill-versleuteling met sleutel $$s$$. De methode moet de tekst (String; in hoofdletters) teruggeven die je bekomt door cijfertekst $$t$$ te decoderen volgens de Hill-versleuteling met sleutel $$s$$.
Voorbeeld
> const A = new Matrix([[32, -2, -25], [39, 16, -42], [72, 69, -11]])
> A.rijen
3
> A.kolommen
3
> A.matrix
[[6, 24, 1], [13, 16, 10], [20, 17, 15]]
> A.isVector
false
> A.isVierkant
true
> A.isEenheid
false
> A.blok
Error: ongeldige vector
> B = new Matrix([[8, 57, 62], [73, 34, 47], [-31, -14, 34]])
> B.rijen
3
> B.kolommen
3
> B.matrix
[[8, 5, 10], [21, 8, 21], [21, 12, 8]]
> B.isVector
false
> B.isVierkant
true
> B.isEenheid
false
> B.blok
Error: ongeldige vector
> A.maal(new Matrix([[1, 2], [3, 4]]))
Error: ongeldige matrixvermenigvuldiging
> A.maal(3)
Traceback (most recent call last):
Error: ongeldige matrixvermenigvuldiging
> const C = A.maal(B)
> C.rijen
3
> C.kolommen
3
> C.matrix
[[1, 0, 0], [0, 1, 0], [0, 0, 1]]
> C.isVector
false
> C.isVierkant
true
> C.isEenheid
true
> C.blok
Error: ongeldige vector
> const blok = new Blok("HIL")
> blok.toString()
"HIL"
> const vector = blok.vector
> vector.matrix
[[7], [8], [11]]
> vector.isVector
true
> vector.isVierkant
false
> vector.isEenheid
false
> vector.blok.toString()
"HIL"
> new Hill(new Matrix([[1, 2], [3, 4]]), new Matrix([[5, 6], [7, 8]]))
Error: ongeldige sleutel
> sleutel = new Hill(new Matrix([[3, 3], [2, 5]]), new Matrix([[15, 17], [20, 9]]))
> sleutel.codeer("Hill Cipher")
"TCOZESONLP"
> sleutel.decodeer("TCOZESONLP")
"HILLCIPHER"
> sleutel = new Hill(A, B)
> sleutel.codeer("Hill Cipher")
"LRZSVKCJLBNK"
> sleutel.decodeer("LRZSVKCJLBNK")
"HILLCIPHERXX"