Hill Chiffre

Kategorisierung:

Herkunft / Verwendung:

Die Hill-Chiffre wurde von Lester S. Hill 1929 erfunden und basiert auf linearer Algebra. Zur Verschlüsselung wird der Schlüssel in eine n*n-Matrix geschrieben, mit der jeweils wiederholt n Zeichen des Geheimtextes verschlüsselt werden. Geheimtexte, deren Länge nicht durch n teilbar sind, werden mit X aufgefüllt. Diese überflüssigen X am Ende müssen nach der Entschlüsselung wieder gestrichen werden.

Für die Entschlüsselung ist es nötig, eine inverse Matrix der Schlüsselmatrix zu berechnen, was nicht immer möglich ist. Die Menge der verfügbaren Schlüssel hängt auch von gemeinsamen Teilern ab, so dass Alphabetlängen, die einer Primzahl entsprechen, aufgrund der verminderten Teiler ideal geeignet sind. Die Schlüssellängen müssen den Quadraten der Matrix entsprechen, wodurch Schlüssellängen von 4 (2x2), 9 (3x3), 16 (4*4) und 25 (5*5) ideal sind. Evtl. werden Schlüssel entsprechend gekürzt.

Beschreibung des Algorithmus

Als Erstes bestimmt man die Kantenlänge des Quadrates, dass zur Anwendung kommt. Hier nimmt man einfach diejenige, die mit der Länge des Schlüssels abgebildet werden kann. Apfelstrudel hat z. B. 12 Zeichen, mögliche Quadratzahl ist damit 9, also ist die Kantenlänge 3.

Dann wird der Klartext solange mit X aufgefüllt, bis seine Länge durch die Kantenlänge teilbar ist. Beispielklartext z. B. hat 16 Zeichen, fehlen noch 2 zu 18, damit es durch 3 teilbar wird. Also werden 2 X angefügt.

Dann werden die Buchstaben von Klartext und Schlüssel in Zahlen kodiert, wobei gilt: A=0, B=1 ... Z=25.

Die Zahlen aus Klartext und Schlüssel werden in zwei Matrizen geschrieben und diese miteinander multipliziert. Auf die Ergebnismatrix wird dann Modulo 26 angewendet und die daraus resultierenden Zahlen wieder in Buchstaben überführt, was den Chiffretext ergibt.

Zum Dechiffrieren wird die aus dem Schlüssel stammende Matrix invertiert und mit der Matrix des Chiffrats multipliziert und die Ergebnismatrix danach Modulo 26 genommen. Die sich daraus ergebenen Zahlen werden in Buchstaben überführt und damit der Klartext wiederhergestellt.

Beispiel

Klartext:	Beispielklartext
Schlüssel:	Apfelstrudel
Chiffrat:	WKNFRDHFVHMDTOFSPQ

Chiffrieren:
	
Apfelstrudel
123456789012

A  p  f  e  l  s  t  r  u
0  15 5  4  11 18 19 17 20	

B  e  i  s  p  i  e  l  k  l  a  r  t  e  x  t  x  x
1  4  8  18 15 8  4  11 10 11 0  17 19 4  23 19 23 23

Verschlüsselungsmatrix:

 /        \ 
| 0  15 5  |
| 4  11 18 |
| 19 17 20 |
 \        / 
 
Klartextmatrix:

 /                 \ 
| 1  18 4  11 19 19 |
| 4  15 11 0  4  23 |
| 8  8  10 17 23 23 |
 \                 / 
 
Matrizen-Multiplikation:

 /        \       /                 \       /                        \ 
| 0  15 5  |     | 1  18 4  11 19 19 |     | 100 265 215 85  175 460  |
| 4  11 18 |  *  | 4  15 11 0  4  23 |  =  | 192 381 317 350 534 743  |
| 19 17 20 |     | 8  8  10 17 23 23 |     | 247 757 463 549 889 1212 |
 \        /       \                 /       \                        / 

Modulo 26 Operation:

 /                        \               /                 \ 
| 100 265 215 85  175 460  |             | 22 5  7  7  19 18 | 
| 192 381 317 350 534 743  |  mod 26 ->  | 10 17 5  12 14 15 | 
| 247 757 463 549 889 1212 |             | 13 3  21 3  5  16 | 
 \                        /               \                 / 

22 10 13 5  17 3  7  5  21 7  12 3  19 14 5  18 15 16 
W  K  N  F  R  D  H  F  V  H  M  D  T  O  F  S  P  Q

Dechiffrieren:

Verschlüsselungsmatrix:
	
 /        \                    /        \ 
| 0  15 5  |                  | 18 19 7  |
| 4  11 18 |  invertieren ->  | 2  9  20 |
| 19 17 20 |                  | 15 25 18 |
 \        /                    \        / 

Matrizen-Multiplikation:

 /        \       /                 \       /                       \ 
| 18 19 7  |     | 22 5  7  7  19 18 |     | 677 434 368 375 643 721 |
| 2  9  20 |  *  | 10 17 5  12 14 15 |  =  | 394 223 479 182 264 491 |
| 15 25 18 |     | 13 3  21 3  5  16 |     | 814 554 608 459 725 933 |
 \        /       \                 /       \                       / 

Modulo 26 Operation:

 /                       \               /                 \ 
| 677 434 368 375 643 721 |             | 1  18 4  11 19 19 | 
| 394 223 479 182 264 491 |  mod 26 ->  | 4  15 11 0  4  23 | 
| 814 554 608 459 725 933 |             | 8  8  10 17 23 23 | 
 \                       /               \                 / 

1  4  8  18 15 8  4  11 10 11 0  17 19 4  23 19 23 23
B  E  I  S  P  I  E  L  K  L  A  R  T  E  X  T  X  X

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (DeCoder / Encoder / Solver-Tool)

Quellen und weiterführende Links

Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 71
Gómez, Joan: Geheimsprachen und Decodierung, Librero Verlag 2016, S. 74
Fumy, Walter und Rieß, Hans Peter: Kryptographie: Entwurf, Einsatz und Analyse..., Oldenbourg Verlag 1988, S. 67
Kahn, David: The Codebreakers - The Story of Secret Writing, Macmillan Verlag 1968, S. 404