Verschlüsselungen nach Hill



Im Jahr 1929 veröffentlichte der amerikanische Mathematiker Lester Sanders Hill (1890 - 1961) den Artikel Cryptography in an Algebraic Alphabet [1], in dem er erstmals mathematische Methoden in die Kryptographie einführte.

Dazu codierte er zunächst die 26 (Klein-)Buchstaben des lateinischen Alphabets durch eine einfache Substitution gemäß der folgenden Tabelle. (Die von ihm konkret gewählte Zuordnung der Buchstaben zu den Zahlen von 0 bis 25 ist aber für das grundsätzliche Vorgehen unerheblich, man kann also auch die systematische Zuordnung "a" entspricht "0", "b" entspricht "1" usw. bis "z" entspricht "25" benutzen.)

abcde fghij klmno pqrst uvwxy z
52322010 15841825 0161373 11961224 2117142211 9

Zur schnelleren Decodierung ist die folgende Tabelle nützlich

01234 56789 10l1121314 1516171819 2021222324 25
kpcoh arngz eysmw flviq duxbt j

Jeder Buchstabe kann damit als ein Element des Restklassenringes Z/(26) der ganzen Zahlen modulo 26 aufgefaßt werden. Auf diese Weise lassen sich dann mit den Buchstaben Additionen und Multiplikationen ausführen.

Das von Hill vorgestellte Verschlüsselungsverfahren benutzt nun als Schlüssel eine frei wählbare invertierbare n x n-Matrix A über diesem Restklassenring.

Für n = 2 beispielsweise seien a11, a12, a21, a22 die Koeffizienten einer derartigen Matrix. Dann wird immer ein Paar (x1, x2) aufeinander folgender Buchstaben des Klartextes zu einem Paar (y1, y2) von Buchstaben des Geheimtextes verschlüsselt, indem in die folgenden linearen Gleichungen eingesetzt wird.

y1 = a11*x1 + a12*x2
y2 = a21*x1 + a22*x2

Sind dann b11, b12, b21, b22 die Koeffizienten der zu A inversen Matrix B, so ermittelt man bei der Entschlüsselung aus dem Geheimtextpaar (y1, y2) das zugehörige Klartextpaar (x1, x2), indem man in die folgenden Gleichungen einsetzt

x1 = b11*y1 + b12*y2
x2 = b21*y1 + b22*y2

Für beliebige Werte von n arbeitet man entsprechend mit linearen Gleichungssystemen von n Gleichungen mit n Unbekannten, wobei man immer einen Block aus n Buchstaben gleichzeitig ver- bzw. entschlüsselt.

Die folgenden konkreten Gleichungssysteme für n = 4 wurden als Beispiel von Hill in seiner Arbeit angegeben.

y1 = 8*x1 + 6*x2 + 9*x3 + 5*x4
y2 = 6*x1 + 9*x2 + 5*x3 + 10*x4
y3 = 5*x1 + 8*x2 + 4*x3 + 9*x4
y4 = 10*x1 + 6*x2 + 11*x3 + 4*x4

x1 = 23*y1 + 20*y2 + 5*y3 + 1*y4
x2 = 2*y1 + 11*y2 + 18*y3 + 1*y4
x3 = 2*y1 + 20*y2 + 6*y3 + 25*y4
x4 = 25*y1 + 2*y2 + 22*y3 + 25*y4

Soll nun der Klartext

DIESERKLARTEXTISTJETZTZUVERSCHLUESSELN

verschlüsselt werden, so teilt man die Buchstaben in Viererblöcke ein und wandelt sie gemäß der oben angegebenen Tabelle in Zahlen um (im letzten Block wurden zwei Buchstaben "P" und "B" willkürlich als Füller ergänzt):

20,18,10,12   10,6,0,16   5,6,24,10   22,24,18,12   24,25,10,24   9,24,9,21   17,10,6,12   2,4,16,21   10,12,12,10   16,7,1,23

Jetzt wertet man Block für Block das erste Gleichungssystem aus (alle Rechnungen erfolgen modulo 26) und erhält so die Blöcke des Geheimtextes:

2,10,2,24   14,14,8,18    4,18,25,0   22,12,14,12   6,9,4,24    12,5,20,1   24,4,11,6   3,0,9,18   24,16,24,6   8,4,9,19

Diese Zahlenfolge kann man leicht mit der zweiten oben angegebenen Tabelle in eine Buchstabenfolge decodieren und erhält so den endgültigen Geheimtext:

CECT  WWGI  HIJK XSWS  RZHT  SADP   THYR  OKZI  TLTR  GHZQ

Mit dem zweiten Gleichungssystem kann man natürlich die Zahlenfolge des Geheimtextes auch wieder entschlüsseln.


Beispiele für Kryptogramme, die mit dem Hill-Verfahren verschlüsselt wurden, finden sich hier und hier.


Für den Fall n = 6 konstruierte Hill gemeinsam mit Louis Weisner ein mechanisches Gerät, mit dem die Ver- und Entschlüsselung automatisiert werden konnte. Dieses Gerät ist als US-Patent[2] angemeldet.


[1] Hill, Lester Sanders, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly, Vol. 36, No. 6 (1929), 306 - 312.
(http://w08.middlebury.edu/INTD1065A/Lectures/Hill%20Cipher%20Folder/Hill1.pdf)

[2] US-Patent Nr. 1845947
(http://www.google.com/patents?vid=1845947)

[3] Hill, Lester Sanders, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly, Vol 38 (1931), 135 - 154.
Autor: Udo Hebisch
Datum: 11.04.2011