Der Recherchekompass
[ home | anleitungen | recherchen | hilfe | sitemap | index | suchen ]

Verschlüsselte Botschaften Selbsterstellte Algorithmen

Schön wär's, wenn jemand die Algorithmen "knacken" würde! Anregungen und Kritik schreibe er dann bitte an: mailto:hgm

Die auf dieser Seite aufgeführten Algorithmen wurden von mir entwickelt. Ähnlichkeiten zu existierenden Algorithmen waren nicht gewollt, tun aber dem Lerneffekt keinen Abbruch. Mit der Veröffentlichung fordere ich zu Kritik und Anregungen auf. Davon unbenommen sind sie als Programmierhilfe gedacht und können bei Bedarf kopiert und angepasst werden, vorbehaltlich eventueller Rechte von Dritten.

Auch wenn die Algorithmen getestet und gefundene Fehler nach besten Wissen beseitigt wurden, kann keine Gewährleistung für die Korrektheit der Algorithmen gegeben werden, denn durch Testen kann die Korrektheit eines Programms nicht bewiesen werden, höchstens seine Fehlerhaftigkeit.

Also: Alles ist "AS IS" und Gewährleistungen und Garantien gibt es für gar nichts.
Im Übrigen siehe den Haftungsausschluss (»).

• Erster Versuch:

  (Dezember 2002) Dieser erste hier vorgestellte Algorithmus ist eine Stromchiffre, die Zeichenweise im Counter-Modus arbeitet. Verschlüsselt wird indem ein Zeichen des Klartexts einfach mit einem Zufallswert durch XOR verknüpft wird. Der Zufallswert wird durch einen Pseudozufallsgenerator erzeugt. Dabei wird der "Schlüssel" als Startwert (X) für den Generator verwendet. Da die XOR-Verknüpfung umkehrbar ist, wird mit dem gleichen Algorithmus entschlüsselt. Statt dem Klartext wird dann der Chiffretext übergeben.

  1: function crypt_HGC1(X, EinText) { 2: var AusText = ""; 3: var rndm = 0; 4: 5: var i = 0; 6: while (i < EinText.length) { 7: if (i%2 == 0) { 8: X = (17*X + 1) % 65536; 9: rndm = X & 255; 10: } else 11: rndm = (X >> 8) & 255; 12: if (EinText.charCodeAt(i) == rndm) 13: AusText = AusText + String.fromCharCode(EinText.charCodeAt(i)); 14: else 15: AusText = AusText + String.fromCharCode(EinText.charCodeAt(i)^rndm); 16: i++; 17: } 18: return AusText; 19: }

  Tabelle: JavaScript zur Codierung der HG-Chiffre Nr. 1.

  [notation] [beispiel]

  Dieser Algorithmus lässt sich sehr einfach durch eine einzige Funktion umsetzen, wobei für die Ver- bzw. Entschlüsselung lediglich für die richtige Versorgung der Parameter zu sorgen ist. In der Implementierung des Beispiels wurde eine weitere Funktion realisiert, um den Wert des Schlüssels zu bestimmen, wenn er sowohl als Zahl wie auch als Folge von Buchstaben angegeben wird. Der Schlüssel dient in diesem Verfahren nur zur Bestimmung des Startwertes, die weitere Verschlüsselung ist in sofern nicht mehr vom Schlüssel abhängig. Die Umsetzung des Algorithmus im Einzelnen:

  Schlüssel: Klartext: Dies ist der Klartext.
  Chiffriert:
  Dechiffriert:
  [quelltext] Tabelle: Chiffrierverfahren HGC1, Stromchiffre im Counter-Modus (Zufallszahl).

  Zeile 8 beinhaltet den Pseudozufallszahlengenerator nach der Methode der linearen Kongruenz. Da für zeichenweise Verschlüsselungen aber nur 8 Bit benötigt werden, werden in Zeile 9 die unteren 8 Bit aus der Zufallszahl extrahiert und in Zeile 11 die oberen 8 Bit. Auf diese Weise werden mit jeder Zufallszahl zwei Byte verschlüsselt. Bei der maximalen Periode können somit 131072 Zeichen verschlüsselt werden, bevor sich die Zufallszahlenreihe wiederholt. Die eigentliche Verschlüsselung passiert in Zeile 15, in der das Klartextzeichen mit dem Zufallswert durch XOR verknüpft wird.

  Die Bedingung in Zeile 12 verhindert, dass das Zeichen mit der Ordnungszahl "0" erzeugt wird, durch dieses Zeichen wird in JavaScript ein String beendet, so dass der Rest des Textes verloren gehen würde. In diesen Fällen wird das ursprüngliche Zeichen beibehalten, was sich durchaus negativ auf die Qualität des Verfahrens auswirkt. Weitere Probleme ergeben sich aus der Nutzung von JavaScript bei der Darstellung im Browser (Internet Explorer unter Windows), hier wird beim Auffinden eines einzelnen "Carriage-Return"- oder "Line-Feed"-Zeichens das jeweils Andere hinzugefügt. Um die daraus entstehenden Probleme zu umgehen wird die Steuer- und Sonderzeichen des erzeugten Chiffretext vor der Darstellung mittels der JavaScript-Funktion escape() ersetzt, was bei der Entschlüsselung durch unescape() zurückgesetzt wird. Der Chiffretext wird dadurch leider erheblich länger.

  Die hier dargestellte Implementierung ist zur Verschlüsselung von vorhandenen Texten geeignet. Wird die Schleife (Zeile 6) so organisiert, dass Ereignisse der Ein- bzw. Ausgabe verarbeitet werden, können die Zeilen 7 bis 16 verwendet werden, um - geeignet parametrisiert und ohne Bildung der Zeichenkette - direkt einen Zeichenstrom zu verschlüsseln.

  Zum Brechen der Verschlüsselung kann wirkungsvoll die Methode der "Brutalen-Gewalt" eingesetzt werden, da für die "kurze" Periode von 65536 handelsübliche PCs eingesetzt werden können, um die Lösung zu finden. Und auch ein Klartextangriff wird schnell zum Erfolg führen. Von einem Einsatz dieses Verfahrens für den längerfristigen Schutz kann also nur abgeraten werden. Den Einsatz im Streaming, z.B. von Terminaleingaben, kann schon mal gewagt werden, wenn das Schutzbedürfnis nicht besonders hoch ist und die "Haltbarkeit" der Daten gering (Neuheitswert der Daten ist sehr kurz). Aber selbst dann sollte ein häufiger Schlüsselwechsel stattfinden.
  

  [seitenanfang] [verweise]

   

• Zweiter Versuch:

  (Januar 2003) Bei diesem Algorithmus wird eine Blockchiffre erstellt, welche auf dem ersten Versuch basiert. Die Bestimmung der Zufallszahl wird ebenfalls durch den bereits bekannten Algorithmus für eine lineare Kongruenz durchgeführt. Im wesentlichen gilt das gleiche wie für HGC1, allerdings geht der erzeugte Chiffreblock in die Erzeugung der nächsten Zufallszahl ein (CFB).

  1: function crypt_HGC2(X, EinText, encrypt) { 2: var AusText = ""; 3: var Temp = 0; 4: 5: if (EinText.length % 2 != 0) 6: EinText = EinText + " "; 7: 8: var i = 0; 9: while (i < EinText.length) { 10: var Block = 0; 11: 12: Block = (EinText.charCodeAt(i++) << 8) + EinText.charCodeAt(i++); 13: 14: X = (17*X + 1) % 65536; 15: 16: Temp = Block ^ X; 17: if (encrypt) X = Temp; 18: else X = Block; 19: 20: AusText = AusText + String.fromCharCode((Temp >> 8) & 255); 21: AusText = AusText + String.fromCharCode(Temp & 255); 22: } 23: return AusText; 24: }

  Tabelle: JavaScript zur Codierung der HG-Chiffre Nr. 2.

  [notation] [beispiel]

  Auch in diesem Fall kann die Verschlüsselung wie auch die Entschlüsselung durch die gleiche Funktion durchgeführt werden, sofern für das Cipher-Feedback die "kryptografische Richtung" (Zeile 1: encrypt) bekannt ist. Wie auch beim HGC1 ist dieser Algorithmus stark durch die diskrete Programmierung der Blocklänge auf Grund des bekannten Modulus im Pseudozufallszahlengenerator (Zeile 14) geprägt. Erweiterungen der Blocklänge hätten somit zwangsläufig Veränderungen des Programms zur Folge. Zur Bestimmung des Schlüssels wird die gleiche Funktion wie oben verwendet, wodurch der Schlüssel sowohl als Zahl als auch als Zeichenfolge angegeben werden kann. Die Umsetzung des Algorithmus im Einzelnen:

  Schlüssel: Klartext: Dies ist der Klartext.
  Chiffriert:
  Dechiffriert:
  [quelltext] Tabelle: Chiffrierverfahren HGC2

  Da es sich bei diesem Verfahren um eine Blockchiffre handelt ist zu Beginn ein Padding des Textes auf ein Vielfaches der Blocklänge (hier 2 Byte) durchzuführen (Zeilen 5 & 6). Zur Verschlüsselung des Textes werden jeweils 2 Byte zu einem Block zusammengefasst (Zeile 12) um dann in Zeile 16 mit der Zufallszahl aus Zeile 14 per XOR verknüpft zu werden. Der Block wird in den Zeilen 20 und 21 zeichenweise ausgelesen und am Ausgabetext angehängt. Das Cipher-Feedback wird in den Zeilen 17 und 18 realisiert. Bei der Verschlüsselung wird der verschlüsselte Block als nächster Eingangswert für den Zufallszahlengenerator verwendet und bei der Entschlüsselung entsprechen der Block vor den Entschlüsselung.

  Da sich aus der Nutzung von JavaScript und der Darstellung im Browser (Internet Explorer unter Windows) Probleme mit dem Handling des Stringendes ergeben, werden bei der Rückgabe der Verschlüsselung mittels der JavaScript-Funktion escape() alle Sonderzeichen (Escape-Character) durch ihre ASCII-Zahlenwerte mit vorangestelltem % ersetzt. Entsprechend wird diese Codierung bei der Entschlüsselung durch die Funktion unescape() zurückgeführt. Der Chiffretext wird dadurch leider erheblich länger. Das Problem entsteht insbesondere durch das Erzeugen von Stringendezeichen die bei der Darstellung besonders behandelt werden.

  Auch bei diesem Verfahren kann zum Brechen der Verschlüsselung kann wirkungsvoll die Methode der "Brutalen-Gewalt" eingesetzt werden, da für die "kurze" Periode von 65536 handelsübliche PCs eingesetzt werden können, um die Lösung zu finden. Allerdings erhöht sich durch den Cipher-Feedback-Modus die erforderliche Zeit. Hier kann aber genutzt werden, dass Textzeichen in natürlichen Sprachen in der Regel nur Ordnungszahlen bis 128 aufweisen (Ausnahme im Deutschen: Ä, ä, Ö, ö, Ü, ü, ß) und somit das oberste Bit durch die Zufallszahl entsteht. Hierdurch kann gezielt nach Zufallswerten bestimmter Höhe gefahndet werden, dadurch reduziert sich der Aufwand. Ist der Anfang erst einmal gemacht, ist der Rest nicht viel schwieriger als beim HGC1. Dieses Verfahren lässt sich leicht zu einer Stromchiffre abwandeln.
  

  [seitenanfang] [verweise]

   

• Dritter Versuch:

  (Februar 2003) JavaScript legt es nahe, Stromchiffren umzusetzen, so ist auch HGC3 eine solche. Zur Verschlüsselung des Klartextes wird eine Zufallszahl mittels linearer Kongruenz ermittelt, diese wird - zusammen mit einem Zeichen des Schlüssels - mit dem nächsten Klartextzeichen verknüpft. Dieser Wert geht auch in die Bestimmung des nächsten Zufallswertes ein. Es handelt sich somit um eine Stromchiffre im Electronic Codebook- (ECB) mit gleichzeitigem Cipher-Feedback-Modus (CFB). Der Algorithmus verwendet im Gegensatz zu den vorangegangenen Algorithmen eine andere Bildung des Startwertes.

  1: function crypt_HGC3(key, EinText, encrypt) { 2: var AusText = ""; 3: var Sign, i, X = 255; 4: 5: for (i=0; i < key.length; i++) 6: X = (X * key.charCodeAt(i)) % 65536; 7: 8: i = 0; 9: while (i < EinText.length) { 10: X = (17*X + 1) % 65536; 11: 12: Sign = EinText.charCodeAt(i) ^ ((X>>8)&255); 13: Sign = Sign ^ key.charCodeAt(i%key.length); 14: 15: if (encrypt) X = X ^ Sign; 16: else X = X ^ EinText.charCodeAt(i); 17: 18: AusText = AusText + String.fromCharCode(Sign); 19: i++; 20: } 21: return AusText; 22: }

  Tabelle: JavaScript zur Codierung der HG-Chiffre Nr. 3.

  [notation] [beispiel]

  Der Schlüssel wird als Zeichenkette interpretiert und in den Zeilen 5 und 6 wird zunächst der Startwert für den Zufallszahlengenerator anhand des Schlüssels bestimmt. Dazu werden die Ordnungszahlen der Buchstaben miteinander multipliziert, dabei wird der Wert in der Größenordnung des Modulus gehalten. Vorteil dieser Vorgehensweise: Der Startwert ist vom ganzen Schlüssel abhängig; die Wahrscheinlichkeit, dass es sich um einen Wert kleiner 10.000 handelt, ist nicht mehr größer als der umgekehrte Fall.

  Schlüssel: Klartext: Dies ist der Klartext.
  Chiffriert:
  Dechiffriert:
  [quelltext] Tabelle: Chiffrierverfahren HGC3, Stromchiffre im Electronic Codebook- (ECB) plus Cipher-Feedback-Modus (CFB).

  Die eigentliche Verschlüsselung findet innerhalb der Schleife (Zeilen 9 bis 20) statt. Die Zeile 10 realisiert den bereits bekannten Zufallszahlengenerator, mit dem Zufallszahlen gemäß der linearen Kongruenz ermittelt werden. Die Verschlüsselung (bzw. Entschlüsselung) wird in den Zeilen 13 und 14 durchgeführt. Dabei wird in Zeile 13 zunächst das Textzeichen mit dem Zufallswert mittels XOR verknüpft, wobei die oberen acht Bit für die Verknüpfung genommen werden. In Zeile 14 wird das erhaltene Ergebnis nochmals mit einem Zeichen des Schlüssels "überschlüsselt". Dabei ist der Schlüssel als eine beliebig lange Wiederholung des Schlüsselwortes zu verstehen (vgl. Vigenère-Chiffre).

  Die Zeilen 15 und 16 sorgen für das Feedback der Chiffre in die Bestimmung der Verschlüsselung des nächsten Zeichen. Durch den Parameter encrypt wird so gesteuert, dass bei der Entschlüsselung das Chiffrezeichen nach der Verknüpfung genommen wird und bei der Entschlüsselung davor. Da ein Chiffrezeichen nur maximal den Wert 255 hat, wird dieser mit dem vorangegangene Zufallswert verknüpft. Man beachte, dass in diesem Fall die Chiffre in die unteren acht Bit eingeht, während bei der Verschlüsselung die oberen acht Bit genutzt wurden.

  Eine Analyse der Chiffrezeichen anhand des obersten Bits, kann nicht mehr zur Ableitung der Folge der Zufallszahlen herangezogen werden, da die jeweils nächste Zufallszahl vom Chiffrezeichen abhängt und somit eine Reihenfolge durcheinander gebracht wird. Das Bilden des Koinzidenzindex nach Friedman zeigt, das die erzeugte Chiffre - zumindest bei nicht zu großen Texten - in der Größenordnung der zufälligen Verteilung (0,0039) liegt und damit deutlich unter dem für natürliche Sprachen [1]. Problematisch bleibt weiterhin der Umstand, dass das oberste Bit eines Chiffrezeichens in der Regel weder vom Schlüssel noch vom Textzeichen sondern aus dem Zufallswert stammen dürften. Da zudem die Position eines Chiffrezeichen innerhalb des Textes der des zugehörigen Klartextzeichens entspricht, dürfte ein Klartextangriff Erfolg versprechend sein.
  

  [seitenanfang] [verweise]

   

Anmerkungen zur Notation:

Zur Beschreibung der Algorithmen wurde die Notation von JavaScript verwendet, so dass die Algorithmen wie hier beschrieben in eine HTML-Seite zu übernehmen sein sollten. In JavaScript muss die ganzzahlige Division mittels der Funktion Math.floor() aus der normalen Division gebildet werden. Die Ermittlung des jeweiligen Restes einer ganzzahligen Division (modulo) wird durch "%" ausgedrückt. Wertzuweisungen an eine Variable werden durch ein einfaches Gleichheitszeichen gekennzeichnet, bei Vergleichen wird das Gleichheitszeichen verdoppelt ("=="). Wichtige boolesche Operatoren sind:

Logisch:
	&&	UND		||	ODER		!	NICHT
Bitweise:
	&	UND		|	ODER		^	XOR
	<<	Links-Shift		>>	Rechts-Shift