Krypto-Systeme: Vom Chiffrieren und Kodebrechen

In der fragmentarischen Hinterlassenschaft des Heraklit, eines griechischen Philosophen aus vorsokratischer Zeit, den man auch den 'Dunklen' nennt wegen der Vieldeutigkeit mancher seiner Aussagen, findet sich die bemerkenswert hellsichtige Einschätzung vom Krieg oder allgemeiner, dem Streit als Erzeuger aller Dinge.

Eine zutreffende Beurteilung zumindest für die Kryptologie, denn, wie in der geschichtlichen Entwicklung dieser Lehre vom Verschlüsseln und Entschlüsseln oft genug zu sehen ist, gedeihen Geheimschriften, Geheimsprachen und die ungezählten Ideen, Wissen und Informationen aller Art vor einer vermeintlichen oder realen Ausspähung zu schützen, besonders gut auf dem Boden des Krieges, des Wettbewerbs, überhaupt im Umfeld einer wie auch immer begründeten Abschottung nach außen. So erinnert das sich bedingende Hinaufschaukeln von Chiffrieren und Kodebrechen zu immer raffinierteren Verfahren an die gegenseitig abhängige Entwicklung von Angriffsund Verteidigungswaffen. Und noch etwas fällt ins Auge: das Hand-in-Hand-Gehen von Einfallsreichtum und Mechanisierung, d. h. an jede Kreation einer neuen Verschlüsselungsmethode schließen sich sogleich zahlreiche Versuche zu ihrer schematisierten Handhabung an. Die Vorsilbe krypto (griech. kryptos -verborgen, versteckt) deutet an, worum es geht: um Methoden zum Verbergen von Informationen. Entsprechend dem Erfindungsreichtum menschlichen Geistes haben sich auch die Versuche gestaltet, entweder die Inhalte von Nachrichten oder diese selber geheimzuhalten. Die Verfahren reichen von der unsichtbaren Tinte bis zum speziellen Verschlüsselungschip.

Dennoch ist es keinesfalls paradox, wenn am Ende der siebziger Jahre vorgeschlagen wurde, als Konsequenz der sogenannten Public-Key-Verfahren sogar das Geheimste selbst, die Schlüssel, zu enthüllen und sie den Augen einer breiten Öffentlichkeit preiszugeben. Menschliche Kombinationsgabe und Intuition scheinen seitdem nicht mehr gefragt, da, wie es aussieht, allein die geballte Kraft riesiger Rechenanlagen die heute gültigen Verschlüsselungen knacken könnte. Zugleich haben sich die Schwerpunkte der Kryptologie verschoben: vom militärischen zum privat-wirtschaftlichen Bereich. Im Zeitalter der Verarbeitung und Vernetzung von Informationen wird neben einer Sicherung von Daten auch der Schutz vor unbefugten Zugriffen zunehmend bedeutsamer. Daß Paßwörter keineswegs ausreichen, ist vielfach spektakulär aufgezeigt worden. Was liegt näher, als sich nicht nur auf Abwehrmethoden gegen Unberechtigte zu konzentrieren, sondern die Daten selbst zu schützen, diese über Kryptosysteme so zu chiffrieren, daß sie ohne Kenntnis eines speziellen Teils der Schlüsselfunktion wertlos sind? Am Beginn der Geschichte elektronischer Rechenmaschine steht ein Koloß, zusammengesetzt aus Elektronenröhren, zum Zweck der Entschlüsselung militärischer Nachrichten konzipiert und konstruiert: COLOSSUS. Prototyp eines Großrechners, 1942 für den britischen Geheimdienst gebaut, um die Verschlüsselungsparameter der elektromechanisch arbeitenden deutschen Chiffriermaschine ENIGMA aufzudecken. Der Arbeitsweise dieses Gerätes im Prinzip vergleichbar sind auch die Methoden der Verschlüsselung, die heute innerhalb militärischer und ziviler US-KommunikationssySterne, etwa Behörden oder Banken, angewandt werden. Dahinter wirkt ein Algorithmus, der 1977 vom U. S. National Bureau of Standards genormt und unter dem Namen “Data Encryption Standard” (DES) eingeführt wurde. Dazu und zu den Public-Key-Kryptosystemen später mehr. Vorweg werden einige Grundbegriffe der Kryptologie vorgestellt und an Beispielen aus der Geschichte der Kryptologie erklärt.

Klassische Kryptosysteme

Grundsätzlich unterscheidet man zwei Kategorien von Verschlüsselungssystemen: die Transpositionen (Versetzungen) und die Substitutionen (Ersetzungen ). Bei Transpositionen werden die Zeichen der zu verschlüsselnden Information, also der in Umgangssprache formulierte Klartext, blockweise über eine geometrische Figur, den Schlüssel, eingelesen und nach einem speziellen Muster versetzt in den Schlüsseltext ausgelesen. Bei Substitutionen hingegen ersetzt man nach einer bestimmten Vorschrift die Zeichen des Klartextes durch andere Zeichen oder Symbole. Wird für jedes zu ersetzende Zeichen eines Alphabets immer ein bestimmtes Schlüsselzeichen eines anderen Alphabets genommen, heißt die Substitution monoalphabetisch, läßt sich dagegen ein Zeichen durch Ersetzungen aus mehreren anderen Alphabeten chiffrieren, spricht man von einer polyalphabetischen Substitution. Eine Zwischenstufe bilden homophone Substitutionen, dahier zwar monoalphabetisch kodiert wird, andererseits aber zwischen einer begrenzten Anzahl unterschiedlicher Ersetzungszeichen pro Klartextbuchstaben gewählt werden darf. Eine frühe Transpositionsmethode stammt aus dem alten Griechenland. Von den Ephoren, den Mitgliedern der Regierung Spartas, wird berichtet, daß sie, um chiffrierte Depeschen mit ihren Heerführern auszutauschen, die Skytale (griech., Stab) benutzten. Um diesen Holzstab einer genau bestimmten Länge und Dicke wurden schmale Pergamentstreifen in Spiralwindungen gewickelt, anschließend beschrieb man das Pergament in Längsrichtung des Holzes mit einer Nachricht und übergab dann den entrollten Streifen einem Boten. Wer nun die Botschaft richtig lesen wollte, mußte zugleich die Stärke des Holzstabes kennen, da erst ein Stab im richtigen Durchmesser die gleichen Windungen erzeugte, die das Pergament beim Beschriften eingenommen hatte. Typisch für eine Transposition ist auch das nachstehende Beispiel (s. Abb. 1) einer zweidimensionalen Wegtransposition. Der Klartext “DIES IST EINE BOTSCHAFT” wird ohne Leerzeichen zeilenweise von links oben nach rechts unten (oder umgekehrt) in eine 5 x 4-Matrix (Schlüssel) eingetragen. Ausgelesen wird der Schlüssel spaltenweise von rechts unten nach links oben (bzw. umgekehrt). Die versetzten Buchstaben ergeben den Schlüsseltext.

Die klassische monoalphabetische Substitutionschiffrierung wird nach Julius Cäsar (100-44 v. u. Z.) benannt: In diesem System ersetzt man jeden Buchstaben des Klartextes durch einen im bestimmten Abstand (Schlüssel) folgenden Buchstaben des Alphabets. Am Ende des Alphabets angelangt, wird von vom weitergezählt. Wählt man als Schlüssel das “C” (‘C ist der dritte Buchstabe im Alphabet und gibt daher den Abstand 3 an), sähe der Ausgangstext “KOMME MORGEN” chiffriert folgendermaßen aus: “NRPPH PRUJHQ”. Eine zwar ältere, gleichwohl differenzierte Methode geht auf den griechischen Geschichtsschreiber Polybios (204-122 v. u. Z.) zurück. Sein Verfahren bestand darin, die Buchstaben des Alphabets in eine Matrix zu schreiben, jede Zeile und Spalte mit einem Symbol zu benennen und dann fortlaufend die Buchstaben der Nachricht durch je zwei Symbole, nämlich die Kennung aus Zeile und Spalte zu ersetzen. Polybios beschreibt eine militärische Nutzung seiner Idee als Fackeltelegraphie (1). Ein Buchstabe des Klartextes wird durch zwei gleichzeitig gegebene Fackelsignale symbolisiert, wobei vom Beobachter gesehen, die linke Seite für die Zeile, die rechte Seite für die Spalte steht (s. Abb. 2). Um zum Beispiel das 'B' zu signalisieren, müssen links eine, rechts zwei Fackeln gezeigt werden.

Im Unterschied zu der monoalphabetischen Methode des Polybios ersetzen in einem polyalphabetischen Verfahren verschiedene Symbole den gleichen Buchstaben, bzw. kennzeichnet ein Symbol des verschlüsselten Textes verschiedene Buchstaben der zu übertragenden Botschaft. Als Beispiel dient die Variation eines Schemas, das von Athanasius Kircher (1601-1681) entwickelt wurde. In jenem System sind die Buchstaben des Alphabets in einer 25*25-Matrix (ohne den Buchstaben T) so angeordnet, daß in der ersten Zeile der Matrix das Alphabet in seiner ursprünglichen Reihenfolge steht; in den folgenden Zeilen findet man das Alphabet jeweils um ein Zeichen nach rechts verschoben. Fehlende Zeichen sind im Anschluß an das T eingefügt (s. Abb. 3). Der verschlüsselte Text ergibt sich aus einer Kombination von Klartext und vereinbartem Schlüssel. Nehmen wir an, der Klartext lautet: “KOMME MORGEN MITTAG“ und als Schlüssel wurde “SCHLUESSEL“ gewählt, dann geht die Chiffrierung folgendermaßen vonstatten:

Man sucht in der Zeile über der Tafel den ersten Buchstaben des Klartextes (‘K’) und in der Spalte links neben der Tafel den ersten Buchstaben des Schlüssels ‘S’ auf.

Der erste chiffrierte Buchstabe liegt im Schnittpunkt von Zeile und Spalte (‘B’).

Ist der Klartext länger als der Schlüssel, werden dessen Buchstaben bis zum Erreichen des Klartextendes wiederholt.

Klartext:
K O M M E M O R G E N M I T T A G

Schlüssel:
S C H L U E S S E L S C H L U E S

Schlüsseltext:
B Q T W Y Q F I L P E O Q D N E Y

Wie zu erkennen, erhält ein Buchstabe des Klartextes die verschiedensten Chiffren: ‘M’ wird umgewandelt zu entweder ‘T’, ‘W’, ‘Q’ oder ‘O’. Auf der anderen Seite können sich hinter einem Zeichen des Schlüsseltextes unterschiedliche Klartextzeichen verbergen: ‘Q’ fungiert als Statthalter für ‘O’, ‘M’ oder ’I’.

Der Goldkäfer, eine Kryptoanalyse in der Literatur

“Das Medium ist die Botschaft“ lautet ein Kemsatz des Kommunikationsforschers Marshall McLuhan. Doch gerade zwischen Medium, Nachricht und Information wird in der Kryptologie fein unterschieden, dabei stimmen ihre Definitionen nicht mit denen der Umgangssprache überein. Oft kolportiert wird der Ausspruch eines Hollywood-Filmproduzenten: "Haben Sie eine Botschaft, dann schicken Sie ein Telegramm.“ Enthielte aber das Telegramm nichts weiter als ein gerade dieses Medium nutzendes Gedicht, dann fielen Medium, Botschaft und Information gleichsam zusammen. Niemand besser als Edgar Allan Poe kann die Grundbegriffe der Kryptologie, vor allem die Lösungswege einer Dechiffrierung, die Kryptoanalyse, erklären, hat er doch um dieses Thema herum eine Abenteuergeschichte geschrieben: “The Gold-Bug”. Zum Inhalt: Die Hauptfigur, William Legrand, entdeckt in der Umgebung seines Wohnsitzes auf einer Insel an der Ostküste der USA einen großen, ungewöhnlich gezeichneten Käfer. Um ihn nach Haus zu tragen, wird er in ein Pergament eingewickelt, auf welches der Erzähler fast zur selben Zeit in der Nähe eines alten Bootswracks am Ufer gestoßen war. Durch Zufall wird Legrand gewahr, daß das vermeintlich wertlose Papier eine Geheimschrift enthält, die erst beim Erhitzen zum Vorschein kommt. In einer Ecke des länglichen Pergaments macht Legrand die Zeichnung eines Totenkopfes und in der diagonal gegenüberliegenden Ecke die Umrißlinien einer Ziege aus. Dazwischen identifiziert er folgende Zeichen (siehe Abb. 4).

Spannend und lehrreich zugleich ist die Analyse. Zuerst muß der Zettel überhaupt als Botschaft erkannt werden. Das Material des Zettels, eben dauerhaftes Pergament und kein leicht verrottendes Papier, das Bootswrack, in dessen Nähe die Nachricht gefunden wurde, die Zeichnungen von Totenkopf und Ziege (‘Zicklein’ heißt auf englisch ‘kid’), alles zusammen läßt Legrand eine Verbindung zu dem berüchtigten Piratenkapitän William Kidd herstellen. Obwohl dieser jahrelang als Seeräuber die Meere unsicher gemacht hatte, besaß er bei seiner Festnahme keinerlei erbeutete Wertsachen, so daß sich bald die Legende von einem verborgenen Schatz ausbreitete. Da das Wortspiel mit dem Namen ‘Kidd’ nur im Englischen möglich ist, folgert Legrand, müssen auch die Symbole auf dem Pergament die Chiffrierung einer in Englisch abgefaßten Nachricht sein. Und im weiteren nimmt er an, Kidd habe die Verschlüsselung selbst vollzogen, dadurch könne eine Chiffrierung vorausgesetzt werden, die der Vorstellungswelt eines Piraten angemessen ist: vermutlich eine einfache Substitution. Erst nach diesen notwendigen Vorüberlegungen beginnt die eigentliche Analyse. Bei seiner Entschlüsselung benutzt Legrand die Häufigkeitsverteilung der Buchstaben in der englischen Sprache und überträgt sie auf den verschlüsselten Text. Danach würde die am häufigsten vorkommende Chiffre dem ’e’ entsprechen, die zweithäufigste dem ‘a’ und so weiter in der Reihenfolge o, i, d, h, n, r, s, t, u, y, c, f, g, l, m, b, k, p, q, x, z. Wenn man bedenkt, daß im Englischen das ‘e’ oft verdoppelt auftritt, erhält die Vermutung ‘8’ stehe für das ‘e’ eine zusätzliche Bestätigung. Berücksichtigt man überdies die Spitzenstellung des Wortes ‘the’ in der Häufigkeitsliste englischer Wörter, stößt man siebenmal auf die gleiche Gruppe von drei Zeichen ‘;48' an deren Ende die ‘8’, das angenommene ‘e’, steht. Lassen wir Legrand selbst zu Worte kommen (2):

“Nehmen wir zum Beispiel doch einmal den vorletzten Fall, wo die Kombination >;48< vorkommt - gar nicht weit vom Ende des Textes. Wir wissen, daß das unmittelbar folgende Semikolon den Anfang eines Wortes darstellt, und von den sechs Charakteren, welche diesem the nachstehen, kennen wir nicht weniger als fünf. Ersetzen wir also diese Charaktere durch die Buchstaben, welche sie nach unserem Wissen vertreten, indem wir für den einen unbekannten einen Zwischenraum freilassen-teeth. Hier können wir es uns sogleich erlauben, das >th< als nicht zu dem mit dem ersten >t< beginnenden Worte gehörig fortzulassen; denn wenn wir das gesamte Alphabet nach dem in die Lücke passenden Buchstaben durchgehen, erkennen wir, daß sich kein Wort bilden läßt, welches dies >th< mit enthalten könnte. Damit haben wir eine weitere Begrenzung, nämlich auf t ee, und wenn wir nun - falls überhaupt nötig - wieder wie zuvor das Alphabet durchgehen, so kommen wir zu dem Worte tree als der einzig möglichen Lesart. Wir haben somit einen weiteren Buchstaben gewonnen, nämlich das ‘r' vertreten durch >(<, und zugleich die Worte the tree nebeneinander.”

Nach dieser Methode entschlüsselt Legrand den gesamten Text. Allerdings ist die Analyse damit längst nicht beendet. Obschon die Nachricht im Klartext bekannt ist, muß ihr Inhalt aber, die eigentliche Information, erst in einer weiteren, diesmal qualitativen Analyse erarbeitet werden. Wenn in Don Siegels Action-Film “Telefon” die Worte “Des Waldes Dunkel zieht mich an, doch muß zu meinem Wort ich stehen und Meilen gehen, bevor ich schlafen kann" per Telefon an die richtigen Adressaten gelangen, werden kaum lyrische Gefühle wachgerufen, im Gegenteil, sogenannte ‘Maulwürfe’ - in Lauerstellung befindliche Agenten - erhalten ihr Kodewort, das sie aktiviert, geplante Mordinstruktionen auszuführen. Man sieht, Nachricht und Information müssen keineswegs identisch sein. Zu welchem Ergebnis Legrand kommt, mag der Interessierte in Poes Geschichte nachlesen.

Computeranalyse - ein Fallbeispiel

Wer benutzt heute noch die monoalphabetische Substitution, wird man fragen, die - wie Poe zeigte - relativ einfach aufzudecken ist? Sehen wir uns daher eine polyalphabetische Verschlüsselung per Computerprogramm an, die unlängst in der “ST Computer”(3) erschienen ist. Das vorgestellte Prinzip beruht darauf, einen Klartext über einen periodisch auftretenden Schlüssel zu kodieren. Hierzu wird fortlaufend der ASCII-Wert eines Klartextbuchstabens zum ASCII-Wert des zugehörigen Schlüsselbuchstabens addiert. Die Modulo-Operation mod 256 sorgt dafür, daß der Rahmen des ASCII-Wertebereiches nicht überschritten wird. Anhand des Beispiels in Abb. 5 kann die Methode nachvollzogen werden.

Obwohl dieses Verschlüsselungsverfahren - im ersten Moment jedenfalls - resistent gegen eine statistische Analyse zu sein scheint, läßt sich auch hier die von Poe demonstrierte Methode erfolgreich einsetzen, unter der Voraussetzung allerdings, daß der Schlüssel aus Wörtern der natürlichen Sprache besteht. Ausgangspunkt ist eine Beschränkung auf die nachstehende Rangfolge der Häufigkeitsverteilung von Buchstaben in der deutschen Sprache: Interpunktionen bzw. Leerzeichen, e, n, i, r, s, t, a. Die zur Analyse notwendige Zählarbeit kann ein Computerprogramm (s. Listing) übernehmen, das nach denselben Prinzipien arbeitet, die auch in der statistischen Sprachanalyse verwendet werden (4). Da ein Schlüsseltextzeichen aus der additiven Kombination zweier Buchstaben der Umgangssprache entstanden ist, brauchen nur sämtlich mögliche Kombinationen daraufhin durchgesehen zu werden, ob und wenn ja, in welcher Zusammensetzung in ihnen die Verbindungen zweier häufig vorkommender Buchstaben zutrifft. In Abb. 6 sind alle Buchstaben-Kopplungen von Klartext und Schlüsselwort aufgelistet, die zu den ersten drei Schlüsseltextzeichen (ASCII-Werte 134’, ‘221’ und ‘207’) führen. In allen drei Fällen tritt jeweils nur eine Kombination der oben angegebenen häufig vorkommenden Buchstaben auf, nämlich ‘A-E’ (Abb. 6 oben), ‘i-t’ (Abb. 6 Mitte) und ‘a-n’ (Abb. 6 unten). Somit hat das Programm die ersten drei Buchstaben von Klartext und Kodewort ausfindig gemacht. Im unteren Teil von Abb. 5 sind alle vom Programm enträtselten Buchstaben aufgeführt. Da man nicht weiß, welcher Buchstabe zum Klartext bzw. zum Schlüsselwort gehört, wäre der nächste Schritt die Zusammenstellung der gefundenen Buchstaben zu sinnvollen Wörtern. Mit etwas Gespür läßt sich im Beispiel leicht das periodische Schlüsselwort ‘Atari ST’ ausmachen; der Klartext resultiert - da man das Prinzip kennt - aus der Subtraktion der ASCII-Werte von Schlüsseltext und Kodewort.

Für schwierigere Fälle sollte das Analyse-Programm so erweitert werden, daß es die gefundenen Buchstaben (aus Klartext und Schlüssel) zu allen möglichen Zweier- oder Dreierkombinationen zusammenstellt und diese anhand einer eingespeicherten Häufigkeitsliste von Bi- oder Trigrammen der deutschen Sprache vergleicht.

Von der ENIGMA zum Data Encryption-Standard

Wie gerade gezeigt, auch polyalphabetische Substitutionen sind zu knacken, es sei denn, man verlängerte das Schlüsselwort und setzte es aus zufällig gewählten Zeichen (möglichst ohne Wiederholungen) zusammen. Beide Bedingungen erfüllte ENIGMA (nach griech. ainigma -Rätsel), die Verschlüsselungsmaschine der deutschen Wehrmacht im Zweiten Weltkrieg. Der gesamte Funkverkehr (im Morsekode) zwischen den deutschen Kommandostellen und der U-Boot-Flotte wurde über die ENIGMA-Maschine verschlüsselt; eine Notwendigkeit, da jeder, den es interessierte, den Funkverkehr mithören konnte. Die ENIGMA rechnet man zu den Rotormaschinen, die auf elektromagnetischem Wege polyalphabetische Substitutionen einzelner Klartextzeichen vornehmen. Vereinfacht gesagt, dabei Details außer acht gelassen (5), waren bei der ENIGMA drei austauschbare Rotoren (Drehscheiben), die aus isoliertem Material bestanden, über ihre jeweils 26 Kontakte (analog der Anzahl von Buchstaben des Alphabets) hintereinandergeschaltet. Jeder Eingangskontakt auf der Vorderseite einer Scheibe war durch diese hindurch mit einem Ausgangskontakt auf der Rückseite verbunden. Im Sinne einer differenzierten Chiffrierung hatte man die Verbindungen nach einer Zufallsauswahl angeordnet. Ein Rotor bildete also eine drehbare Permutationsbox, in welcher alle Eingangssignale an der Ausgangsseite vertauscht (permutiert) ausgegeben werden. Beispielsweise hätte ein Signal, das an Kontakt 1 der Vorderseite ankam, auf der Rückseite des Rotors bei Kontakt 7 ausgehen können. Zudem drehte sich die erste Rotorscheibe nach 26 Eingangssignalen um eine Kontaktstelle weiter. Erreichte sie ihre Ausgangsstellung, rückte daraufhin - nach dem Kilometerzählerprinzip - die zweite Scheibe einen Schritt vorwärts. Nach 26 Bewegungen der zweiten wurde auch die dritte Scheibe um einen Anschlag mitgenommen. Da jeder Rotor eine andere interne Verknüpfung zwischen Eingangs- und Ausgangskontakt besaß, waren insgesamt 26 * 26 * 26 = 17576 verschiedene Verschlüsselungskombinationen möglich. Die Verknüpfungen innerhalb und zwischen den Rotorscheiben symbolisierten also eine polyalphabetische Substitution mit einem Schlüssel der Länge 17576. Erst bei Klartextmeldungen mit mehr als 17576 Buchstaben hätten alle Scheiben der ENIGMA über ihre Ausgangsstellung hinaus die gleichen Stellungskombinationen erneut durchlaufen. Die Dechiffrierung geschah durch den umgekehrten Prozeß, bei gleicher Anfangsstellung der Rotoren wandelte die Maschine den verschlüsselten Text in Klartext um.

Die Verschlüsselung durch die ENIGMA wäre eigentlich nicht durch eine statistische Analyse der Buchstabenhäufigkeiten zu knacken gewesen, da jeder Buchstabe des Klartextes mit gleicher Wahrscheinlichkeit von jedem Buchstaben des Alphabets kodiert wurde. Trotzdem gelang es dem englischen Geheimdienst, den Kode zu knacken, zum einen, weil ihm über verschiedene Quellen einiges über die ENIGMA bekannt war, beispielsweise die Bedienungsanleitung und das Verdrahtungsschema der drei ursprünglichen Rotoren, zum anderen half die analytische Fähigkeit der eingesetzten Mathematiker, unter ihnen Alan Turing, die zum ersten Mal auf die Rechenkraft einer elektronischen Rechenmaschine, COLOSSUS, zurückgreifen konnten (6). Wie anders auch als mit Hilfe von Rechenautomaten hätte die immense Zahl von Verschlüsselungsmöglichkeiten durchprobiert werden können [Laut einer Meldung im ST-Magazin 1989/4 (S. 10) ist ein Simulationsprogramm der ENIGMA für ATARI ST-Besitzer bei der Firma “SSG-System-Entwicklung” erhältlich]. Machen wir einen Sprung ins Jahr 1977. Es ist das Jahr, in dem erstmals eine Verschlüsselungsmethode als Standard anerkannt und niedergelegt wurde: der Data Encryption Standard (DES). Die Rotormaschinen haben längst ausgedient, ihre Aufgaben sollen Computerprogramme oder in Mikrochips eingelagerte Verschlüsselungslogiken übernehmen. Was bei der ENIGMA noch auf elektrischmechanischem Wege vollzogen wurde, wird nun Software-Modulen übertragen. Gleichwohl hat sich das Prinzip der Verschlüsselung nicht grundlegend verändert, die Arbeitsweise des Algorithmus’ jedoch, der dem DES zugrunde liegt, ist weitaus komplizierter geworden. Klartext und Schlüssel werden blockweise in immer neuen Variationen durcheinandergeschüttelt, vertauscht und verknüpft, so daß am Ende auch der geschickteste Analysator verzweifelt aufgegeben haben sollte. Jedenfalls hofften dies die Entwickler, vornehmlich Programmierer der Firma IBM. Am ehesten läßt sich der Ablauf innerhalb des DES an einem Schaubild verdeutlichen (s. Abb. 7). Zwei große Prozesse bestimmen den gesamten Ablauf: einmal das löfache Durcheinanderwürfeln des Klartextes und zum zweiten die gleichzeitige löfache Gewinnung neuer Teilschlüssel, die jede Verwirbelung der Klartextzeichen mit beeinflussen.

Beginnen wir mit der Verschlüsselung des Klartextes (Abb. 7 links oben). Da das Programm ausschließlich Binärdaten blockweise verarbeitet, muß der Klartext zunächst binär kodiert werden. Aus dem kodierten Datenmaterial greift sich das Programm dann jeweils einen Block von 64 Bits heraus und unterwirft ihn einer ersten Permutation. Dies geschieht ähnlich wie bei der Vertauschung der Zeichen zwischen Vorder- und Rückseite des Rotors bei der ENIGMA. Im IP-Modul (Initial Permutation) werden die 64 Bits des zu bearbeitenden Datenblocks nach einem festen Muster vertauscht: So wechselt zum Beispiel das Bit aus Position 1 an die Stelle von Bit 58, Bit 64 zu Bit 7 usw. [Sämtliche Tabellen des DES (Permutations-, Substitutionsmodule, Linksverschiebung) sind in Abb. 8 aufgeführt.] Nach Abschluß der Permutation erfolgt eine Trennung der Binärdaten in zwei 32-Bit-Blöcke. Während der linke Block und eine Kopie des rechten Blocks eine Weile ungeschoren bleiben, wartet auf den rechten eine Folge von Permutationen und Substitutionen. Im Expansionsmodul E werden die Bits des rechten Blocks vertauscht und zugleich auf 48 Bits erweitert [einige Eingangsbits landen dabei auf mehreren Ausgangspositionen (s. Abb. 8)]. Nun ist es Zeit, sich der Verschlüsselung des Schlüssels zuzuwenden (s. Abb. 7 rechts oben). Eingeben darf man ein 64 Bits langes Schlüsselwort, welches sogleich in der Permutationsmatrix PCI (Permuted Choice) permutiert, auf 56 Bits verkürzt und im Anschluß daran auf zwei Blöcke zu je 28 Bits aufgeteilt wird. Jeder der beiden 28-Bit-Vektoren unterliegt einer Linksverschiebung im Modul LS (Left Shift), wobei sich der Verschiebungsfaktor in den einzelnen Moduln LSI - LS 16 im Verlauf der 16 Iterationen ändert (s. Abb. 8). Die Ergebnisse eines Verschiebungspaares werden zusammengeführt und gehen als 56-Bit-Block in die Permutationsmatrix PC2 ein. PC2 vertauscht die Bitpositionen und entfernt 8 Stellen, somit verläßt ein 48-Bit-Vektor dieses Modul und vereint sich mit den 48 Bits, die nach der Bearbeitung durch die Expansionsmatrix E auf der Datenseite (linke Seite Abb. 7) bereits warten. Die Vereinigung geschieht in einer bitweisen Addition modulo 2.

Die Daten treten jetzt in das Herzstück der gesamten Verschlüsselungsprozedur ein: in die Substitutionsmoduln S1 bis S8. Was passiert hier? Nach vollzogener Vereinigung der beiden 48-Bit-Blöcke (einer von der Daten-, der andere von der Schlüsselseite; s. o.) wird der Ergebnisblock umgehend in 8 Teile zu je 6 Bits zerlegt. Jeder 6er-Block taucht in eine Substitutionsbox ein und bestimmt selbst durch seine spezifische Bitanordnung, in welcher 4er-Bitfolge er sein S-Modul verläßt. Gesetzt den Fall, die 6er-Bit-Folge 111101 kommt an der S-Box S7 an, dann würde die Umwandlung in einen 4-Bit-Vektor nach folgendem Muster ablaufen: Die beiden äußeren Bits 11 (binär 11 = dezimal 3) bestimmen die Zeile 3 einer 4 * 16-Matrix, die 4 inneren Bits 1110 (binär 1110=14 dezimal) die Spalte 14. Man erhält den dezimalen Wert 3, der als 4-Bit-Block 0011 von der Substitutionsbox S7 ausgegeben wird (s. Abb. 8). Dieser Teil im Verschlüsselungsprozeß heißt nichtlinear, weil die Substitution vom Wert eines jeweiligen Bitmusters abhängt, das auf der Eingangsseite des S-Moduls ankommt. Jede der 8 Substitutionsboxen reagiert zudem mit einer spezifischen Matrix auf die Eingangswerte der 6-Bit-Blöcke. Nach Verlassen der S-Moduln werden die 4er-Blocke zu einer 32-Bit-Folge zusammengezogen und in der Permutationsmatrix P wieder durchgeschüttelt. Endlich tritt der linke 32-Bit-Datenblock in Aktion, der, aus dem IP-Modul entlassen, solange im Wartestand verweilt hat. Der linke Block wird bitweise modulo 2 zum 32-Bit-Vektor aus dem P-Modul addiert. Diese Addition (32 bit) und die Kopie des rechten 32-Bit-Daten-blocks, der sich ebenfalls im Wartezustand befand, bilden die neuen Eingangsvektoren für den zweiten Durchgang, der unterhalb des IP-Moduls beginnt. Parallel dazu, auf der Schlüsselseite unterhalb PCI (Abb. 7 rechts oben), startet auch dort ein neuer Durchlauf, mit dem Ziel, einen veränderten Teilschlüssel zu generieren. Insgesamt werden beide Prozeduren (Datenseite und Schlüsselseite) 16mal ausgeführt, danach die beiden vorläufigen 32-Bit-Endblöcke ein letztes Mal vertauscht, zusammengefügt, in der inversen Permutationsmatrix gemischt, bis endlich ein 64-Bit-Schlüsseltextblock als Resultat erscheint. Der nächste 64-Bit-Datenblock kann eingelesen und verschlüsselt werden. Zur Entschlüsselung benutzt man die gleiche Prozedur - nur verlaufen die 16 Iterationen in umgekehrter Reihenfolge.

Hat nun der Kampf zwischen Chiffreuren und Kryptoanalytikem ein Ende gefunden, erfolgreich für die ersteren? Diese Wertung drängt sich geradezu auf in Anbetracht der verwickelten Methode des DES. Doch was die einen Maschinen verschlüsseln, das können andere entschlüsseln. Und so geht der Kampf weiter. Theoretisch jedenfalls. Schließlich besitzt der DES-Algorithmus eine Achillesferse: seine Beschränkung auf einen aktiven Schlüsselvektor der Länge 58 Bits. Zu vernachlässigen, aber immerhin erwähnenswert, man kennt vier ‘schwache Schlüssel’, (in hexadezimaler Schreibweise: 01 01 01 01 01 01 01 01; FE FE FE FE FE FE FE FE; 1F 1F 1F 1F 0E 0E 0E 0E; E0E0E0E0F1 Fl Fl Fl), bei denen nach zweimaliger Verschlüsselung wieder der Klartext erscheint. Daneben sind weitere (über 250) Schlüssel bekannt, deren Teilschlüssel weniger als die verlangten 16 verschiedenen Werte annehmen (7). Infolge der totalen Verknüpfung sämtlicher Schlüssel- und Klartext-Bits verspricht eine sprachstatistische Analyse des Schlüsseltextes keinerlei Erfolg. Will man den Kode brechen, bedarf es einer Überprüfung aller möglichen Schlüssel. Das wären 2 hoch 56 verschiedene Konstellationen. In einer 1977 veröffentlichten Studie entwarfen die beiden Standford-Wissenschaftler Whitfield Diffie und Martin E. Heilman eine theoretische Maschine, die imstande wäre, einen Klartext über alle Schlüssel zu chiffrieren und das jeweilige Ergebnis mit dem bekannten zum Klartext gehörenden Schlüsseltext zu vergleichen. Die Maschine bestünde aus einer Million Spezialchips, deren jeder eine Million verschiedene Schlüssel pro Sekunde testen würde. Ließe man jeden Chip parallel einen anderen Schlüsselbereich bearbeiten, könnte die Maschine ihre Arbeit innerhalb eines Tages abschließen. Auch wenn sich eine solche Maschine zur Zeit nicht realisieren läßt, sind doch zumindest Wege aufgezeichnet, die Festigkeit der DES-Methode zu erschüttern. Im übrigen reduziert sich die Anzahl möglicher Schlüssel beträchtlich, wenn man annimmt, daß die Schlüsselwörter aus dem Sprachraum einer Umgangssprache gewählt werden. Noch ein Punkt bleibt festzuhalten. Erst auf drängende Nachfrage wurden einige wenige Konstruktionskriterien der S-Module, also die Intentionen, warum eine S-Box welche Substitution ausführt, veröffentlicht. Ebenso fehlt eine schlüssige Begründung für den ausdrücklichen Wunsch des National Bureau of Standards auf Verkürzung der Paßwortlänge auf 64 bzw. 56 Bits, schließlich hatte IBM im Entwurf 128 Bits vorgesehen. Vielleicht, so meinen Kritiker, hat sich das National Bureau of Standards über die S-Module eine Hintertür geschaffen. um an die Paßwörter der Benutzer zu kommen. Zwar konnte dies bis heute nicht nachgewiesen, aber auch nicht ausgeschlossen werden. Immerhin, eine Fourier-Analyse von DES-Eingangs- und Ausgangswerten zeigt ausgeprägte Muster, obgleich eigentlich völlig zufällig verteilte Werte zu erwarten wären. Wie alle konventionellen Kryptosysteme verliert der DES für einen Anwender augenblicklich an Wirksamkeit, wenn der Schlüssel in die falschen Hände gerät. Hier setzen nun die Public-Key-Systeme an.

RSA - ein Public-Key-Kryptosystem

Von Diffie und Heilman, den Kritikern des DES. stammt auch die Idee, ein Kryptosystem zu schaffen, in dem der leidige geheime Schlüsselaustausch entfällt.

Mehr noch, sie führten sogenannte ‘öffentliche' Schlüssel indie Diskussion ein. Ihre Skizzen sehen zweierlei Arten von Schlüsseln vor: einen geheimen Schlüssel (Sg), der beim Absender verbleibt, und einen öffentlich preisgegebenen (Sö). Stellen wir uns folgende Situation vor: Der Besitzer beider Schlüssel (A) hält den Schlüssel Sg (zum Entschlüsseln) in geheimer Verwahrung, den Schlüssel Sö (zum Verschlüsseln) läßt er, etwa in einem Katalog oder Telefonbuch, veröffentlichen. Nun können alle, die sich diesen Schlüssel heraussuchen, eine Nachricht mit Sö verschlüsseln und an A senden, aber nur dieser wäre in der Lage, den Text zu dechiffrieren. Auch der umgekehrte Weg ist denkbar: A chiffriert eine Nachricht mit seinem geheimen Schlüssel Sg. Der Empfänger dekodiert die Nachricht mit dem veröffentlichten Schlüssel Sö. Das Chiffrat von A wirkt wie eine Unterschrift, da ja nur der Besitzer von Sö die Chiffrierung hat vornehmen können. Diffies und Heilmans Vorschläge in ein praktikables Verfahren umgesetzt haben 1978 drei Wissenschaftler des MIT Laboratory for Computer Science in Cambridge, nach deren Nachnamen-Initialen auch die Methode benannt wird: RSA-System (von Roland Rivest, Adi Shamir und Leonard Adleman). Eine relativ einfache Überlegung liegt dem Verfahren zugrunde: Ohne Probleme läßt sich aus zwei großen Primzahlen p und q ein Produkt n bilden, andererseits gibt es kein Verfahren, auf direktem Wege aus n die beiden Primfaktoren zurückzugewinnen. Um die notwendige Sicherheit zu gewährleisten, müssen die beiden Primzahlen mindestens in der Größenordnung von 100 Dezimalstellen gewählt werden.

' Kryptoanalyse
' am Beispiel der Verschlüsselung aus ST-Computer 11/88, S. 74
'
' Klartext, Schluesselwort (Kodewort) 
klartext$="Ein Text als Test"
kodetext$ = "Atari STAtari STA" 
klar_l%=LEN(klartext$)
DIM klar%(klar_l%,127)
DIM klar$(klar_l%)
DIM krypt%(klar_l%)
'
' Tabelle der haeufigsten Buchstaben
tab_l%=8
DIM tab%(tab_l%)
FOR i%=1 TO tab_l%
	READ tab$
	tab%(i%)=ASC(tab$)
NEXT i%
DATA " ",e,n,i,r,s,t,a
'
' Chiffrierung
FOR i%=1 TO LEN(klartext$)
	krypt%(i%)=(ASC(MID$(klartext$,i%,1))+ASC(MID$(kodetext$,i%,1))) MOD 256 
	krypt$=krypt$+CHR$(krypt%(i%))
NEXT i%
'
' Analyse 
CLS
PRINT "Schluesseltext: ";krypt$
PRINT "Klartext:       ";klartext$
PRINT "Schluessel:     ";kodetext$
FOR i%=1 TO klar_l% 
	zeile%=5
	FOR j%=32 TO 127
		klar%(i%,j%)=(krypt%(i%)+256-ASC(CHR$(j%))) MOD 256 
		FOR k%=1 TO tab_l%
			IF UPPER$(CHR$(j%))—UPPER$(CHR$(tab%(k%))) 
				FOR l%=1 TO tab_l%
					IF UPPER$(CHR$(klar%(i%,j%)))=UPPER$(CHR$(tab%(1%))) 
						klar$(i%)=CHR$(j%)
						IF klar$(i%)=" " 
							klar$(i%)="_"
						ENDIF
						PRINT AT(i%+16,zeile%);klar$(i%)
						INC zeile%
					ENDIF 
				NEXT l%
			ENDIF 
		NEXT k%
	NEXT j%
	PRINT 
NEXT i%

Zur Verdeutlichung dient ein Beispiel, das von den Autoren selber stammt (8). Die mathematischen Hintergründe werden bei der Wiedergabe des Beispiels vernachlässigt, nur der Vorgang des Ver-und Entschlüsselns soll erläutert werden. Die angenommenen Primzahlen sind unrealistisch klein gehalten, sie dienen eben nur dazu, den Ablauf nachvollziehbar zu machen. Gegeben seien die Primzahlen p = 47, g = 59 und das Produkt n = p x q = 2773. Man berechnet dann die Eulersche Funktion phi(n), die angibt, wieviele Zahlen unterhalb von n keinen gemeinsamen Teiler mit n haben. Der Rechenvorgang ist einfach, da phi(n) gleich dem Produkt der Primfaktoren von n ist, wobei jeder Primfaktor um 1 vermindert wird. Da n per Definition aus den Primfaktoren p und q besteht, gewinnt man phi(n) nach der Formel: phi(n) = (p-1)x(q-1) = 2668. Im nächsten Schritt wird der Verschlüsselungsexponent e bestimmt. Dies ist eine beliebige Zahl zwischen 1 und n, für die gilt, daß sie zu phi(n) keinen gemeinsamen Teiler (außer 1) besitzt: z. B. e = 17. Zuletzt braucht man die magische Zahl d, die die Gleichung e x d mod phi(n) = 1 erfüllt: d = 157.

p = 47 (geheim)
q = 59 (geheim)
n = 2773 (öffentlich)
phi(n) = 2668 (geheim)
e = 17 (öffentlich)
d = 157 (geheim)

Jeder kann nun mit dem öffentlich bekanntgegebenen Exponenten e seine Botschaften chiffrieren. Dazu wird der Klartext in Zahlen umgewandelt, in diesem Fall erhält das Leerzeichen die Zahl 00, A die Zahl 01, B = 02 usw.

Klartext: MELDUNG
Klartext in Zahlen: 13 05 12 04 21 14 07

Da n (= 2773) zwischen 10 hoch 3 und 10 hoch 4 liegt, können zwei Buchstaben zu einem Block zusammengefaßt und gegebenenfalls mit Leerzeichen (Nullen) aufgefüllt werden.

1305 1204 2114 0700

Die Verschlüsselungsfunktion hat die Form:

Fv = Klartext hoch e mod n
1305 hoch 17 mod 2773 = 0813;
1204 hoch 17 mod 2773 = 0232 usw.

Der verschlüsselte Text erhält also folgende Zahlenwerte:

0813 0232 1644 0700

Nur wer die magische Zahl d kennt, in aller Regel allein der Adressat, vermag die Verschlüsselung zu dechiffrieren. Mit folgender Funktion:

Fe = Schlüsseltext hoch d mod n
813 hoch 157 mod 2773 = 1305;
232 hoch 157 mod 2773 = 1204 usw.

Bereits an diesem Beispiel ist zu ersehen, daß im Verlauf der Rechnung schnell sehr große Zahlen entstehen, die nur mit speziellen Computerprogrammen (etwa stochastischen Algorithmen, s. dazu ein Listing im Informatik-Duden S. 580) zu bewältigen sind. Prinzipiell ist der RSA-Kode einfach zu brechen, man muß nur die beiden Primfaktoren ermitteln, die der veröffentlichten Zahl n zugrunde liegen. Allerdings - der schnellste bislang bekannte Algorithmus zum Zerlegen von Zahlen in ihre Primfaktoren benötigt für ein n mit 200 Dezimalstellen etwa 4*10 hoch 9 Jahre bei 1 Million Operationen pro Sekunde (9). Noch scheint das RSA-Verfahren das bislang einzige der Public-Key-Systeme zu sein, das noch nicht zu Fall gebracht werden konnte. Andere Verfahren, die unter dem Etikett ‘Falltür-Rucksack-Kodes’ bekannt wurden, galten als extrem sicher, bis sie 1985 geknackt wurden.

Mit Heraklit begann der Artikel und soll auch mit ihm schließen. “Panta rhei”, hat er geschrieben, “alles fließt”, nichts ist beständig - vielleicht nur die Unbeständigkeit. Und wer weiß, wie lange es diesmal dauern wird, bis die Kraft menschlicher Ideen im Wechselspiel von Abwehr und Attacke die Waagschale wieder zur anderen Seite neigen wird. Als Zugabe für alle Heim-Kryptoanalytiker ein Kryptogramm von Karl Heinz Koch, die “Schneckenphilosophie” (10).

Dr. A. Ebeling

Anmerkungen:

Ausführliche Beschreibungen zahlreicher Kryptosysteme und ihrer mathematischen Grundlagen findet man bei P. Hörster (s. (4)); eine detaillierte Besprechung der ENIGMA und des DES bei A. K. Dewdney, in: Spektrum der Wissenschaft, 1988/12, S. 8-11 und 1989/1, S. 6-10.

Computerprogramme zur Kryptologie sind abgedruckt u. a. in:

• Chip 1982/12, S. 30-32

(kurze BASIC-Programme zur Cäsar-Verschlüsselung und zum Playfair-Vei fahren);

• Computer Persönlich 1985/25, S. 61-63 (BASIC-Programm zur polyalphabetischen Substitution);

• P. M. Computerheft 1988/Jan-Feb, S. 62-64 (BASIC-Programme zum Verschlüsseln mit Zufallszahlen)

• Chip 1988/11, S. 244-252 (ein Turbo-Pascal-Programm zum Verschlüsseln von Disketten nach dem DES-Veifahren)

• ST Computer 1988/11, S.74-75 (Modula2-Programm zur polyalphabetischen Verschlüsselung), s. (3)

• c't 1989/4, S.186-196 (C-Programm für RSA-Verfahren mit ‘longest-Integer’)

Literatur:

(1) Oberliesen, R.:
“Information, Daten und Signale. Geschichte technischer Informationsverarbeitung ”,
Rowohlt, Reinbek 1987, S. 34 f.

(2) Poe, E. A.:
"Detektivgeschichten", dtv klassik,
München 1989, S. 157 f.

(3) Rabich, D.
“Dateien schnell verschlüsselt”,
ST Computer, 1988/11, S. 74-75

(4) Hörster, P.: “Kryptologie”,
Bibliographisches Institut, Mannheim 1987,
S. 107 ff.

(5) Dewdney, A. K.:
“Computer-Kurzweil”, in:
Spektrum der Wissenschaft, 1988/12, S. 8-11

(6) s. Rudolph, R.:
"Wer kennt Alan Turing?”,
in: c’t, 1988/3, S. 100-107; s. auch (5)

(7) s. (4) S. 127 ff.

(8) s. (4) S. 181 f. und Duden “Informatik”, 1988, S. 313 f.

(9) s. (4) S. 183

(10) Koch, K. H.:
“Kryptogramme", Hugendubel,
München 1985, S. 45

---

---