mbraetz - Kryptographiespielplatz 2.2 FAV MAIL 
  Hill-Chiffre - Der Großvater aller modernen asynchronen Chiffren ae4d13c1968c057e424877984c7608dd





Die Hill-Chiffre wurde 1929 von Lester S. Hill (1891-1961) im Journal American Mathmatical Monthly (Ausgabe 36) veröffentlicht. In seinem Artikel Cryptography in an Algebraic Alphabet beschreibt er das Verfahren.

Der Algorithmus verwendet quadratische Matrizen als Schlüssel. Die Schlüssel zum Ver- und Entschlüsseln sind verschieden und es handelt sich immer um ein Schlüsselpaar. Dies macht die Schlüsselsuche aufwendig und kennzeichnet die Chiffre als asynchrone Chiffre.

Als Schlüssel kommen Matrizen beliebiger Größe in Frage, mindestens aber der Größe [2x2], da es sonst um die einfache Multiplikative Chiffre handelt. Wichtiges Merkmal der gewählten Schlüssel-Matrizen ist die Existenz der jeweiligen inversen Matrix, da es sich bei der inversen Matrix um den zweiten Schlüssel zum Entschlüsseln handelt.

Mathematisch ist also das Produkt der Schlüsselmatrix A (Public Key) mit der inversen Schlüsselmatrix A-1 (Private Key) über den Modul (Größe des Zeichensatzes) gleich der Einheitsmatrix.



A ⊗ A-1 = E


Für die Existenz von inversen Matrizen für die jeweiligen Schlüssel ist die Wahl des Moduls enscheidend. Ist der Modul eine Primzahl haben wir es mit einem Restklassenring zutun. In einem solchen existiert für jedes Element außer der 0 immer ein Inverses.

Das folgende Beispiel verdeutlicht den Fall für Modulo 11 (Restklassenring11):



 ⊗ 1 2 3 4 5 6 7 8 910
112345678910
224681013579
336914710258
448159261037
551049382716
661728394105
773106295184
885210741963
997531108642
1010987654321

Das Produkt von 4 * 3 = 12 mod 11 = 1.

Das heißt, 4 ist invers zu 3 und umgekehrt,
wenn der Modul 11 ist.

Für den Modul 11 gibt es nur (11-1) = 10 Inverse!

Alle Elemente des algebraischen Körpers sind teilerfremd,
wenn dieser auch ein Ring ist.



Handelt es sich beim Modul um keine Primzahl, sondern beispielsweise nur um eine positive ganze Zahl, wie zum Beispiel 10, gibt es deutlich weniger Inverse (Restklassenring10):



 ⊗ 1 2 3 4 5 6 7 8 9
1123456789
2246802468
3369258147
4482604826
5505050505
6628406284
7741852963
8864208642
9987654321

Für den Modul 10 gibt es nur 4 Inverse!
Das sind die Teilerfremden(10) = {1, 3, 7, 9}



Rechnen wir mal ein Beispiel durch:



Zeichensatz
0001020304050607080910111213141516171819202122232425
ABCDEFGHIJKLMNOPQRSTUVWXYZ

(26 Zeichen -> mod=26)

Teilerfremde(26) = {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}

Inverse(26) = {1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25}





Schlüssel A=[ 7 15 ]
 [ 3  4 ]

det(A): 7*4-3*15 = -17

-17 mod 26 = 9



Um zu entscheiden, ob eine Matrix im gewählten Zeichensatz/Modul zulässig ist, prüft man, ob es für die Determinante der Schlüsselmatrix ein Inverses gibt. Die 9 ist in diesem Fall teilerfremd zu 26 und die Matirx ist als Schlüssel zulässig.



2. Schlüssel A-1 =[ 12  7 ]
 [ 17 21 ]

det(A): 12*21-17*7 = 133

133 mod 26 = 3



Nachdem wir nun geklärt haben, dass unsere Schlüssel was taugen, können wir eine Nachricht verschlüsseln. Jedem der Buchstaben ordnen wir den Index aus dem Zeichensatz zu.



HALLOLEUTE
07001111141104201904


Die dem Verschlüsselungsalgorithmus zugrunde liegende Rechenoperation ist:



A ⊗ V = K

hierbei sind A=Schlüsselmatrix, V=Klartextvektor und K=Kryptogrammvektor

    [7]    
   *[0]    
[715][49]mod 26 = [23]
[34][21] [21]


HA [7,0] wird hier also also verschlüsselt in XV [23,21]. Führt man dies konsequent für die ganze Nachricht fort, ergibt sich:



23210825030816141121
XVIZDIQOLV


Der große Vorteil dieser Chiffre ist, dass in jedem Schritt mehrere Zeichen auf einmal, also in einem Block verschlüsselt werden. Je größer die Schlüssel-Matrix, desto stärker die Chiffre, weil die dem Text zugrundeliegenden Muster verwischt werden. Es gibt eine Faustformel für die Stärke der Chiffre, um sie mit modernen Algorithmen zu vergleichen:



NxN-Matrix mit Zeichensatzgröße M:N*log2(M)[bit]
2x2-Matrix mit Zeichensatzgröße 29:2 * log2(29) ≈ 19 bit
5x5-Matrix mit Zeichensatzgröße 26:70% * 5 * log2(26) ≈ 114 bit


Die Chiffre scheint auf den ersten Blick überraschend stark zu sein. Allerdings muss man bedenken, dass es sich bei den zugrunde liegenden Rechenoperationen ausschließlich um lineare Rechenoperationen handelt. Kennt man Teile des Nachtrichttextes, kann man durch Lösen eines linearen Gleichungssystems den Schlüsselsatz ermitteln.


Signatur: Marcel Brätz 20070123 0.9


  © 2000-2015 - mbraetz-webprojects 0.266 sec, 605 kB, 731.1 kB (limit: 120 sec)