9 Geheime Botschaften


9.1   Grundsätzliches zur Verschlüsselung
9.2   Transpositions-Verfahren
    9.2.1  Die Caesar-Verschlüsselung
    9.2.2  Die Vigenère-Verschlüsselung
9.3  Das RSA-Verfahren
    9.3.1   Mathematische Grundlagen
    9.3.2   Verschlüsselung mit Modulo-Potenzen
    9.3.3   Die RSA-Schlüssel-Erzeugung
    9.3.4   Sicher??? Aber sicher!!!
9.4   Ich bin klein, mein Herz ist rein...

Zum vorigen Kapitel Zum Inhaltsverzeichnis




9.1   Grundsätzliches zur Verschlüsselung

Ein Grundproblem des Internets besteht darin, dass der Informationsaustausch zwischen zwei Partnern über öffentliche Kanäle läuft, bei denen schwer zu kontrollieren ist, ob ein Dritter "mithört". Sollen die Informationen vor den Augen eines Dritten verborgen bleiben, dann bietet es sich an, sie nicht im Klartext, sondern verschlüsselt zu übersenden. Zu diesem Zwecke gibt es inzwischen eine Menge verschiedener Verfahren.

Bei allen Verschlüsselungsverfahren wird aus der Nachricht M mit Hilfe eines Schlüssels S eine verschlüsselte Botschaft C erzeugt. Statt der Nachricht M wird dann die verschlüsselte Botschaft C übermittelt, womit dem Empfänger die Aufgabe bleibt, aus der verschlüsselten Botschaft C wieder auf die ursprüngliche Nachricht M zu schließen, die Botschaft also zu entschlüsseln. Wenn der Empfänger sich dazu desselben Schlüssels S bedient, der auf Seiten des Senders zum Verschlüsseln benutzt wurde, nennt man das Verschlüsselungsverfahren symmetrisch. Symmetrische Verfahren haben den Vorteil, dass sie einfach zu handhaben sind, weil zum Ver- und zum Entschlüsseln derselbe Algorithmus angewendet wird. Sie erreichen aber in der Regel nicht denselben Grad an kryptografischer Sicherheit wie die "asymmetrischen" Verfahren, bei denen zum Entschlüsseln ein anderer Schlüssel benutzt wird als zum Verschlüsseln. Der Nachteil der asymmetrischen Verfahren liegt darin, dass sie komplizierter anzuwenden sind.

In den folgenden Abschnitten werden mehrere berühmte Verschlüsselungsverfahren vorgestellt: als Beispiel für symmetrische Verschlüsselung dienen das Caesar- und das Vigenère-Verfahren, die asymmetrische Verschlüsselung wird am Beispiel des RSA-Verfahrens erläutert.




9.2   Transposition-Verfahren

Eine naheliegende Grundidee bei der Verschlüsselung von Texten ist es, jeden Buchstaben durch einen anderen zu ersetzen: statt einem 'a' schreibt man z.B. ein 'D', statt einem 'b' z.B. ein 'K' usw. Es wird also jedem Buchstaben des "Klartext-Alphabets" eindeutig und umkehrbar genau ein Buchstabe des "Geheimtext-Alphabets" zugeordnet. Man nennt ein solches Verschlüsselungsverfahren eine Transpositions-Chiffre.

Mathematisch ist das Geheimtext-Alphabet einer Transpositions-Chiffre eine Permutation des Klartext-Alphabets; wer diese Permutation kennt, kann sowohl verschlüsseln als auch entschlüsseln, womit das Verfahren also als symmetrisch erkannt ist. Zur Verdeutlichung werden wir im folgenden die Klartexte stets mit Kleinbuchstaben darstellen, die Geheimtexte hingegen nur in Großbuchstaben.



9.2.1   Die Caesar-Verschlüsselung

Die Caesar-Verschlüsselung ist der klassische Prototyp einer "monoalphabetischen Transpositions-Chiffre": das Geheimtext-Alphabet geht aus dem Klartext-Alphabet durch eine einfache Verschiebung hervor: wenn also 'a' durch 'D' verschlüsselt wird, dann werden 'b' durch 'E', 'c' durch 'F', 'd' durch 'G' verschlüsselt usw. (Wird das Ende des Alphabets erreicht, fängt man wieder am Anfang an.) Insgesamt erhält man also die folgende Übersetzungstabelle:

Klartext a b c d e f g h i j k l m n o p q r s t u v w x y z
Geheimtext D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Da der gleiche Klartext-Buchstabe stets durch den gleichen Geheimtext-Buchstaben dargestellt wird, redet man auch von einer monoalphabetischer Verschlüsselung. Damit lässt sich nun jeder beliebige Klartext verschlüsseln und jeder (mit diesem Verfahren erzeugte) Geheimtext wieder entschlüsseln. Probieren Sie's doch mal:

GDVLVWMDHLQIDFK!

Hier sind gleich noch die trennenden Leerzeichen zwischen den einzelnen Wörtern weggelassen worden. Das ist eine übliche Praxis, um es einem eventuellen Angreifer zu erschweren, "den Code zu knacken". Der legitime Empfänger hingegen, der den Schlüssel ja kennt, kann die Leerzeichen in der entschlüsselten Nachricht leicht wieder rekonstruieren.

Im vorliegenden Beipiel wurde eine Verschiebung um 3 Buchstaben gewählt; jede andere Verschiebung ist aber ebenso möglich. Insgesamt ergeben sich also 25 mögliche Varianten der Caesar-Verschlüsselung. (Die theoretisch ebenfalls mögliche 26. Variante ist aus naheliegenden Gründen nicht besonders beliebt.)


Aufgaben:

  1. Angriff auf Caesar:

    Obwohl die Caesar-Verschlüsselung sich lange Zeit großer Beliebtheit erfreute, weil sie so einfach anzuwenden war, wurde recht bald klar, dass sie nicht besonders sicher ist: es genügt, für nur einen Klartext-Buchstaben den zugehörigen Geheimtext-Buchstaben zu erraten, dann ist die Verschlüsselung "geknackt". Wie man so etwas macht, erfahren Sie in dem folgenden Text. Er ist unglücklicherweise caesar-chiffriert, und niemand weiß mehr, wie groß die gewählte Verschiebung war. So müssen Sie den Text also erst entschlüsseln, bevor Sie ihn lesen können, um zu erfahren, wie Sie ihn entschlüsseln können ;-)

    Damit die Sache nicht zu leicht ist, wurden alle Trennzeichen entfernt. Wenn Sie aber berücksichtigen, dass die verschiedenen Buchstaben in der deutschen Sprache mit durchaus unterschiedlicher Häufigkeit vorkommen, dann sollte es Ihnen keine all zu großen Schwierigkeiten mehr machen, den Text trotzdem zu dechiffrieren:
         OLDDELYOLCOHPCVKPFROPCNZOPMCPNSPCTXQLWWPOPCECLYDAZDTETZY
         DNSTQQCPYTDEOTPSLPFQTRVPTEDLYLWJDPTXQLWWNLPDLCRPYFPREPDO
         PYSLPFQTRDEPYMFNSDELMPYTXRPSPTXEPIEKFMPDETXXPYFYOTSYKFXE
         PDEXTEOPYMFNSDELMPYRWPTNSKFDPEKPYOTPTYQLDELWWPYSTYCPTNSP
         YOWLYRPYOPFEDNSPYEPIEPYOTPSLPFQTRDEPYDTYODZSLMPYDTPTYOPY
         XPTDEPYQLPWWPYYLNSHPYTRPYGPCDFNSPYPCQZWRXPTDEPYDDNSZYMPT
         XPCDEPYPDDPTOPYYDTPSLMPYDZPTYPYHLSCWTNSLMLCETRPYEPIEGZCW
         TPRPYHTPOPYCZXLYLYEZYQZJWDQZCERLYRGZYRPZCRPDAPCPNOPCLFQC
         FYOKHPTSFYOPCEDPTEPYVPTYPTYKTRPDPPYESWE
    

  2. Zählen oder zählen lassen?

    Sollte es Ihnen die Buchstabenzählerei in der vorigen Aufgabe zu mühsam sein, dann können Sie ja dafür schnell ein Programm schreiben, das den Geheimtext in einem Memo-Feld darstellt und für einen einzugebenden Buchstaben zählt, wie oft er in diesem Text enthalten ist.

    Beachten Sie, dass ein Memo-Feld seinen Text auch zur Laufzeit aus der Zwischenablage laden kann! Sie erreichen die "Clipboard-Funktionen" über das Kontextmenü der Memo-Komponente, also mit der rechten Maustaste.



9.2.2   Die Vigenère-Verschlüsselung

Eine ziemlich leistungsfähige Weiterentwicklung der Caesar-Verschlüsselung ist die Vigenère-Chiffre. Die Grundidee dabei ist, zur Verschlüsselung eines Textes nicht nur eines der 25 möglichen Geheimtext-Alphabete zu benutzen, sondern mehrere. Dazu wird ein "Schlüsselwort" vereinbart, das das jeweils zu benutzende Geheimtext-Alphabet (und damit die jeweils anzuwendenden Verschiebungen) angibt. Ein Beispiel soll das Verfahren verdeutlichen:

Durch die simultane Verwendung mehrerer Caesar-Alphabete wird also die starre Zuordnung zwischen Klartext-Buchstaben und Geheimtext-Buchstaben aufgebrochen, weshalb die Vigenère-Chiffre nicht mehr so einfach zu brechen ist. In der ersten Zeit nach ihrer Erfindung war sie deshalb auch unter Fachleuten als "Le Chiffre Indéchiffrable" bekannt. Spätere Forschungen (z.B. durch Charles Babbage) ergaben aber, dass auch eine Vigenère-Chiffre durch eine geschickte Häufigkeitsanalyse gebrochen werden kann, wobei allerdings der nötige Aufwand meist sehr viel höher ist als bei einer Caesar-Verschlüsselung.


Aufgaben:

  1. Vigenère ist besser als Caesar!

    Die "Stärke" der Vigenère-Verschlüsselung ist in hohem Maße abhängig von der Wahl eines geeigneten Schlüsselwortes. Worauf Sie bei der Anwendung der Vigenère-Chiffre achten müssen, erfahren Sie im folgenden Text. (Er ist mit dem Schlüsselwort "SICHERHEITGEHTVOR" verschlüsselt.):
                 VIUCMXLRMKKZLKAOYJMPPWKBQAHYMJAZFVJRG
                 SEVUKMKJEZLXVCMMUZICDSZMOWAHKHZEINPWK
                 LMVXYMUGGCJWJWJLJAEJXTJVEBSUAMILRRBWW
                 EGRNBNHNAMFLVBSEZMKBA
    

  2. Die Version für Faule....

    Sollte Ihnen die manuelle Entschlüsselung zu mühsam sein, können Sie auch zunächst das nächste Kapitel über "Standard-Datentypen" durcharbeiten und unter den Aufgaben zum Thema "Typ-Umwandlungen" einen "Vigenère-Codec" bauen.... ;-)




9.3   Das RSA-Verfahren

Ein Nachteil aller symmetrischen Verschlüsselungsverfahren besteht darin, dass der Empfänger der verschlüsselten Botschaft stets darauf angewiesen ist, dass er vom Sender den passenden Schlüssel übermittelt bekommt. Dazu ist ein sicherer Übertragungskanal nötig. Wenn wir den aber schon haben, können wir ja gleich auch unsere Botschaft über diesen sicheren Kanal schicken - und dann brauchen wir gar keine Verschlüsselung! Der Transport des Schlüssels vom Sender zu den (möglicherweise vielen!) Empfängern stellt ein großes Problem dar. Beim RSA-Verfahren wird dieses Problem vermieden: hier braucht man keinen sicheren Übertragungskanal für den Transport eines geheimen Schlüssels, weil gar keine geheimen Schlüssel transportiert werden müssen!

Das RSA-Verfahren ist eines der bekanntesten Verschlüsselungsverfahren. Obwohl es inzwischen schon über 20 Jahre alt ist, gilt es nach wie vor als sicher, sofern man sich bei der Schlüsselgenerierung hinreichend Mühe gibt. Die Erfinder des Verfahrens (R.Rivest, A.Shamir und L.Adleman) erhielten 1983 ein Patent, das allerdings inzwischen ausgelaufen ist; damit ist der RSA-Algorithmus (zumindest in seiner elementaren Form) frei benutzbar. Es lohnt sich also, dieses Verfahren einmal näher unter die Lupe zu nehmen.

Das RSA-Verfahren ist ein asymmetrisches Verschlüsselungsverfahren, d.h.: zum Verschlüsseln und zum Entschlüsseln werden verschiedene Schlüssel benutzt. Im Gegensatz zu den symmetrischen Verfahren geht die Initiative zur Installierung einer verschlüsselten Kommunikation stets vom Empfänger aus: er muss sich sein persönliches RSA-Schlüsselpaar herstellen, das aus einem "öffentlichen Schlüssel" (zum Verschlüsseln von an ihn gerichteten Botschaften) und einem "privaten Schlüssel" (zum Entschlüsseln solcher Botschaften) besteht:
Das RSA-Verfahren beruht auf zahlentheoretischen Grundlagen. Dies verheißt nichts Gutes, gehört doch die Zahlentheorie zu den tiefsinnigeren Gebieten der Mathematik. Trotzdem kann man - bei Aufwendung einiger Mühe und hinreichender Zähigkeit - zumindest die Grundlagen des Verfahrens verstehen. Und dies wiederum ist wichtig, damit man bei der Benutzung eines RSA-basierten Verschlüsselungsverfahrens keine dummen Fehler macht. Die genaue Mathematik des Verfahrens liegt allerdings jenseits des in der Schule erreichbaren Horizonts. Daher wollen wir uns hier hauptsächlich darum bemühen, ein stark vereinfachtes Bild davon zu entwerfen, wie der Algorithmus eigentlich "funktioniert".

Obwohl Verschlüsselungsverfahren in der Regel Texte verschlüsseln sollen, wollen wir uns hier nur mit der Verschlüsselung von natürlichen Zahlen beschäftigen. Dies ist keine wesentliche Einschränkung: man kann jeden Text in eine Zahl kodieren, indem man z.B. einfach die ASCII-Nummern der Zeichen (als jeweils 3-stellige Dezimalzahlen) hintereinanderhängt und diesen Ziffernwurm als eine zwar sehr große, aber doch natürliche Zahl interpretiert. Vorerst wollen wir uns aber die zusätzliche Einschränkung auferlegen, dass die zu verschlüsselnden Zahlen nicht gar so groß sein sollen. Wir sind ja nicht so besonders gut im Kopfrechnen...



9.3.1   Mathematische Grundlagen

Das mathematische Fundament sind die Modulo-Mengen, die Sie schon in einem früheren Kapitel kennengelernt haben. Nehmen wir zum Beispiel die Modulo-Menge zum Modul n = 10, also M10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, und betrachten wir darin die Potenzen eines jeden Elements:
Jedes Element der Modulomenge produziert einen solchen Potenzen-Zyklus. Die Zyklen sind verschieden lang, aber interessanterweise kommen nur die Längen 1, 2 und 4 vor. Verifizieren Sie das, indem Sie die Zyklen für die fehlenden Elemente von M10 von Hand ausrechnen! Was ändert sich, wenn wir einen anderen Modul n nehmen? Probieren Sie es mal mit n = 15! Ist das immer so? Probieren Sie es mal mit n = 21! Wenn Sie Lust zu eigenen Forschungen haben, versuchen Sie mal rauszukriegen, ob es da eine Gesetzmäßigkeit gibt, und wie sie gegebenenfalls aussieht - ehe Sie weiterlesen!

Nach einer umfangreichen Serie von Experimenten drängt sich die Vermutung auf, dass es eine stattliche Anzahl von Modulomengen gibt, für die alle Elemente einen zugehörigen Zyklus produzieren. Für die in diesen Fällen auftretenden Zykluslängen gilt, dass es eine kleinste zugehörige Zahl k < n gibt, so dass alle Zyklen-Längen Teiler dieser Zahl k sind. Die folgende Tabelle enthält z.B. die Zyklen für den Modul 22:

Exponenten e :  1 2 3 4 5 6 7 8 9 10 11
Potenzen ae für 
alle a Î M22\{0}: 
1 1 1 1 1 1 1 1 1 1 1
2 4 8 16 10 20 18 14 6 12 2
3 9 5 15 1 3 9 5 15 1 3
4 16 20 14 12 4 16 20 14 12 4
5 3 15 9 1 5 3 15 9 1 5
6 14 18 20 10 16 8 4 2 12 6
7 5 13 3 21 15 17 9 19 1 7
8 20 6 4 10 14 2 16 18 12 8
9 15 3 5 1 9 15 3 5 1 9
10 12 10 12 10 12 10 12 10 12 10
11 11 11 11 11 11 11 11 11 11 11
12 12 12 12 12 12 12 12 12 12 12
13 15 19 5 21 9 7 3 17 1 13
14 20 16 4 12 14 20 16 4 12 14
15 5 9 3 1 15 5 9 3 1 15
16 14 4 20 12 16 14 4 20 12 16
17 3 7 9 21 5 19 15 13 1 17
18 16 2 14 10 4 6 20 8 12 18
19 9 17 15 21 3 13 5 7 1 19
20 4 14 16 12 20 4 14 16 12 20
21 1 21 1 21 1 21 1 21 1 21

Es kommen also Zyklen der Länge 10, 5, 2 und 1 vor. Für den Modul n = 22 ist damit offenbar k = 10.

Wenn Sie sich die letzte Spalte der obigen Tabelle anschauen, dann sollte Ihnen auffallen, dass sie mit der ersten übereinstimmt: es ist also ak+1 = a für alle a Î M22. Diese Gleichung ist (mit einem passenden k) auch in vielen anderen Modulomengen erfüllt, aber leider nicht in allen: es gibt auch Modulomengen, in denen manche Elemente a sich nicht in Zyklen reproduzieren! Genaueres dazu erfahren Sie in Aufgabe 7!



Aufgaben:

  1. Rechnen in Modulomengen

    Beim Rechnen in Modulomengen kann man es sich oft einfacher machen als beim Rechnen in Z. Man muss nur wissen wie!

    1. Gilt (a + b) mod n = (a mod n) + (b mod n) ?
      Prüfen Sie das für n = 12 (wie bei der Uhr!) nach, und zwar in den Fällen a = 14, b = 17 sowie a = 21, b = 17 ! Formulieren Sie dann eine korrekte Rechenregel!

    2. Geben Sie auch gleich noch die entsprechende Regel für die Multiplikation an und prüfen Sie sie in einigen Beispielen nach!

    3. Richtige Mathematiker würden natürlich versuchen, diese Regeln zu beweisen, aber das ist Ihnen sicher zu schwer. Oder? Im Grunde müssten Sie dazu ja nur verstanden haben, was "modulo" eigentlich bedeutet...
    Lösungvorschlag


  2. Potenzrechnung in Modulomengen

    Speziell bei der Potenzrechnung gerät man recht schnell aus dem Rechenbereich des Taschenrechners hinaus. Wie viel ist 12345 mod 157? Das überfordert selbst den Windows-TR! Ein üblicher Berechnungstrick ist, den Exponenten in eine Summe aus Zweier-Potenzen zu zerlegen:
        12345 = 12332+8+4+1 = 12332 * 1238 * 1234 * 1231. (§)
    Wenn man sich nun eine Tabelle der Potenzen 123(2i) mod 157 erstellt, dann lässt sich der Term (§) leicht berechnen:

    Exponent e Rechnung mod 157 123e mod 157
    1 1231 => 123
    2 1232 = 15129 => 57
    4 1234 = (1232)2 => 572 = 3249 => 109
    8 1238 = (1234)2 => 1092 = 11881 => 106
    16 12316 = (1238)2 => 1062 = 11236 => 89
    32 12332 = (12316)2 => 892 = 7921 => 71

    Ab der dritten Zeile wird jeweils in der mittleren Zelle das Ergebnis der darüberstehenden Zeile benutzt! Mit Hilfe dieser Tabelle erhält man dann also:

      12345 mod 157 =
      12332 * 1238 * 1234 * 1231 mod 157 =
      ( 71   *  106  * 109  * 123) mod 157 =
      [(71 * 106) mod 157] * [(109 * 123) mod 157] mod 157 =
      147 * 62 mod 157 = 8.

    Mit dieser Methode können Sie alle Modulo-Potenzen mit bis zu 4-stelliger Basis mit Ihrem normalen TR berechnen. Probieren Sie's mal:
    Was ist 23456 mod 249 ?
    Lösungvorschlag


  3. Streifzug durch die Welt der Potenz-Zyklen

    Das Programm Modzyk gibt zu jedem eingegebenen Modul n (mit 1 <= n <= 255) die Zyklen der Potenzen aller positiven Elemente der Modulomenge Mn aus. Es werden die Zyklenlängen bestimmt, und es wird aufgelistet, welche Zyklenlänge wie häufig vorkommt. Bearbeiten Sie mit Hilfe des Programms die folgenden Probleme:

    1. Bei manchen Modulwerten n enthält die Modulomenge Elemente, die sich nicht als Potenz ihrer selbst reproduzieren lassen. Suchen Sie mindestens 5 Beispiele für solche Module. Können Sie ein mathematisches Kriterium angeben, wie man schon dem Modul ansehen kann, ob die Modulomenge solche "seltsamen" Elemente enthält oder nicht?

    2. Unter den Modulomengen ohne "seltsame" Elemente sind solche besonders interessant, die möglichst viele möglichst lange Zyklen haben. Suchen Sie dafür ebenfalls 5 Beispiele. Können Sie auch hier ein Kriterium angeben, wie man dem Modul ansehen kann, ob die zugehörigen Menge von diesem Typ ist?

    3. Es gibt besondere Modulomengen Mn, für deren maximale Zykluslänge k gilt: k = n-1. Welche Module sind das?
Lösungvorschlag




9.3.2   Verschlüsselung mit Modulo-Potenzen

Bleiben wir für ein konkretes Beispiel zunächst noch einmal bei der Menge M22. Wenn man also für ein beliebiges Element a aus dieser Menge die Potenzen a2, a3, a4,... usw. bildet, dann legt man einen möglicherweise ziemlich chaotischen Weg quer durch diese Menge zurück. Aber für alle a gilt, dass ihre 11. Potenz wieder das Startelement a liefert! Und die 21. (31., 41., 51,...) auch, denn jede weitere 10er-Serie von Multiplikationen mit a produziert ja lediglich einen zusätzlichen Umlauf, der stets wieder zum Anfangselement zurückführt, also: Aufgrund der Rechenregeln für Potenzen in Modulomengen gilt nun aber auch: Und an dieser Stelle hatten Rivest, Shamir und Adleman eine gute Idee: man kann die Bildung der 21. Potenz in zwei Verfahrensabschnitte unterteilen, zwischen denen man eine "Pause" macht:
  1. Man berechnet zuerst die Zahl b = a3 mod 22.
  2. Dann berechnet man die Zahl c = b7 mod 22.
Der Witz an der Sache ist: egal, wie wir a aus M wählen, stets gilt c = a! Dies lässt sich im Fall von M22 leicht mit Hilfe der obigen Tabelle für verschiedene Werte von a nachprüfen.

Nun ja, das ist zwar schön, aber was hat das eigentlich mit Verschlüsselung zu tun? Rivest, Shamir und Adleman haben die obigen mathematischen Zusammenhänge nun folgendermaßen interpretiert:
Nehmen wir mal an, dass mir irgend jemand per E-Mail die Botschaft a = 15 senden will. Um diese Nachricht geheim zu halten, teile ich ihm mit, er möge sie RSA-verschlüsselt schicken, und ich teile ihm dafür meinen öffentlichen Schlüssel mit, bestehend aus dem Modul n = 22 und dem Verschlüsselungsexponenten e = 3. Der Entschlüsselungsexponent d = 7 ist der geheime Schlüssel: nur wer diesen hat, kann die verschlüsselte Nachricht entschlüsseln.

Der Absender der geheimen Botschaft rechnet also:
Der Absender schickt mir dann die (verschlüsselte) Botschaft "9". Wenn ich diese empfange, rechne ich:
was die ursprüngliche unverschlüsselte Botschaft ist! Und solange ich meinen Schlüssel d = 7 geheim halte, weiß nur ich, wie man aus der verschlüsselten Botschaft die ursprüngliche, unverschlüsselte berechnen kann!

Leider ist es in diesem Fall ziemlich schwer, den Entschlüsselungsexponenten geheim zu halten. Wenn nämlich ein mathematisch gut informierter Hacker mitbekommt, dass ich meine Nachrichten RSA-verschlüsselt mit dem Modul 22 und dem Verschlüsselungsexponenten e = 3 erhalte, dann kann er sich den (eigentlich geheimen!) Entschlüsselungsexponenten auch selbst ausrechnen:
  1. Er bestimmt die maximale Zykluslänge in M22, z.B. mit dem oben bereitgestellten Programm "Modzyk". Ohne große Mühe erfährt er: k = 10.

  2. Er sucht aus der Zahlenreihe (11, 21, 31, 41, 51,....) diejenigen Zahlen heraus, die durch den Verschlüsselungsexponenten 3 teilbar sind. Die erste solche Zahl ist 21. Diese Zahl dividiert er durch den Verschlüsselungsexponenten 3 und erhält als Ergebnis dann den gesuchten Entschlüsselungsexponent, in diesem Fall 7.
Leider hat der Hacker recht. Enttäuschend, nicht wahr? So viel Aufwand um ein Verfahren, das sich nun als so leicht knackbar erweist! Wie kann man da von einer "sicheren Verschlüsselung" reden? Irgendwie scheint das noch nicht die ganze Wahrheit über RSA zu sein....



Aufgaben:

  1. Kryptologische Grundübungen

    Für eine RSA-Verschlüsselung sei der öffentliche Schlüssel (n, e) = (249, 5) allgemein bekannt, den geheimen Schlüssel (d = 33) kennen aber nur Sie.

    1. Welche verschlüsselte Nachricht erhalten Sie, wenn die unverschlüsselte "37" ist?

    2. Sie erhalten die verschlüsselte Botschaft "15". Entschlüsseln Sie sie!

    Lösungvorschlag


  2. Sind Sie ein guter Hacker?

    Sie erfahren, dass Ihr Nachbar seine E-Mail mit RSA verschlüsselt, und zwar mit dem Modul 46 und dem öffentlichen Schlüssel 5. Können Sie daraus den geheimen Schlüssel berechnen?
    Lösungvorschlag





9.3.3   Die RSA-Schlüssel-Erzeugung

Beim "echten" RSA-Algorithmus werden die Schlüssel nach einem etwas anderen Verfahren erzeugt. Dabei spielt die "Euler'sche Φ-Funktion" eine große Rolle, aber wir wollen uns hier nicht mit den zahlentheoretischen Details belasten. Die folgenden Überlegungen sollten Ihnen zeigen, dass im Wesentlichen das gleiche passiert wie in unserer obigen "RSA-Simulation".

Der von Rivest, Shamir und Adleman angegebene Algorithmus zur Generierung der Schlüssel lautet folgendermaßen:
  1. Man wählt zwei (große) Primzahlen p und q.
  2. Man berechnet den Modul n = p * q und die Zahl Φ = (p-1) * (q-1).
  3. Man wählt aus dem Intervall [2; Φ-1] eine ganze Zahl e, die teilerfremd zu Φ ist.
  4. Man berechnet die (eindeutig bestimmte) Zahl d aus dem Intervall [2; Φ-1], für die gilt: e * d @ 1 mod Φ.
  5. Der öffentliche Schlüssel ist dann das Paar (n, e), der private Schlüssel ist d.
Als erstes bemerken wir, dass durch die Bauart des Moduls n als Produkt von genau 2 Primzahlen die Existenz von vielen langen Zyklen in der zugehörigen Modulomenge Mn sichergestellt wird. Um die zunächst etwas mysteriöse Rolle der Zahl Φ zu verstehen, führen wir die Schlüssel-Generierung einmal mit kleinen Zahlen durch:
  1. Wir wählen p = 7 und q = 11.
  2. Wir berechnen n = p * q = 7 * 11 = 77 und Φ = (p-1) * (q-1) = 6 * 10 = 60
  3. Sodann wählen wir aus dem Intervall [2; 59] eine ganze Zahl, die teilerfremd ist zu 60. Das ist nicht ganz einfach, weil 60 ziemlich viele Teiler hat, aber bei e = 7 werden wir dann doch noch fündig.
  4. Schließlich müssen wir d so wählen, dass das Produkt d*e bei Division durch Φ den Rest 1 lässt. Damit muss d*e also eine der Zahlen 61, 121, 181, 241,... sein. Keine der angegebenen Zahlen ist durch 7 teilbar, aber wenn wir weiter suchen, werden wir fündig: 301 läßt bei Division durch 60 den Rest 1, und es ist durch 7 teilbar: 301 = 7 * 43. Also ist d = 43 die gesuchte Zahl.
  5. Der öffentliche Schlüssel ist also (n; e) = (77; 7), der geheime Schlüssel ist d = 43.
Der Modul n = 77 ist nun so klein, dass wir die Schlüsselberechnung zum Vergleich auch mit Hilfe der maximalen Zykluslänge k durchführen können: mit dem Programm "Modzyk" können Sie leicht verifizieren, dass für die Modulomenge M77 k = 30 ist. Nach jeweils 30 Potenzierungsschritten kommen wir also stets zum Startelement zurück. Also muss das Produkt d*e eine der Zahlen 31, 61, 91, 121,..., 271, 301, 331,.... sein. Man sieht, dass das Exponentenpaar (e; d) = (7; 43) eine mögliche Lösung ist, weil 301 in der Zahlenreihe vorkommt. Man sieht aber auch, dass es (zumindest in diesem Fall) noch eine weitere Lösungen gibt: wegen 91 = 7 * 13 ist das Exponentenpaar (e; d') = (7; 13) ebenfalls ein Schlüsselpaar!

Überprüfen wir die erhaltenen Schlüssel zumindest einmal an einem Beispiel: als Nachricht wählen wir a = 38. Die verschlüsselte Nachricht ist dann:

    b = ae mod n = 387 mod 77 = 114 415 582 592 mod 77 = 3

Wenn wir zum Entschlüsseln den RSA-Exponenten d = 43 nehmen, dann erhalten wir:

    c = bd mod n = 343 mod 77 = 328 256 967 394 537 077 627 mod 77 = 38

und das ist die originale Nachricht! Die erhalten wir aber auch, wenn wir "unseren" Exponenten d' zum Entschlüsseln benutzen:

    c = bd' mod n = 313 mod 77 = 1 594 323 mod 77 = 38

Das RSA-Verfahren liefert also zum gewählten Verschlüsselungsexponenten nicht unbedingt den optimalen Entschlüsselungsexponenten, nämlich den kleinsten! Der "RSA-Entschlüsselungs-Schlüssel" d ist aber einer der möglichen Entschlüsselungs-Schlüssel, die wir (theoretisch!) über die maximale Zykluslänge k berechnen können.

Beim ernsthaften Einsatz von RSA arbeitet man nun mit sehr viel größeren Modulen n als wir es bisher getan haben. Dann wächst aber der Aufwand für die Bestimmung der maximalen Zykluslänge k schnell ins Absurde. Für genügend große Module n kann daher kein Hacker mehr k bestimmen, um damit d aus (k div e) zu berechnen (siehe auch 9.3.4!). Nicht ohne Grund wurde beim Programm "Modzyk" der Bereich der zugelassenen Module n auf das Intervall [1..255] eingeschränkt! Sie bemerken die Zunahme des Rechenaufwandes schon recht deutlich, wenn Sie das Laufzeitverhalten des Programms für Module am Anfang und am Ende dieses Intervalls vergleichen. Für eine sichere Verschlüsselung ist es daher nicht zu umgehen, sich mit den nur "fast optimalen" Schlüsseln des originalen RSA-Algorithmus zufrieden zu geben, die uns die Zahlentheoretiker über die Euler'sche Φ-Funktion zugänglich machen.

Sogar die RSA-Schlüsselgenerierung selbst ist für große Module n nicht mehr mit dem Taschenrechner alleine zu bewältigen; sie wird notwendigerweise zu einer Aufgabe für Spezialprogramme, welche mit so großen Zahlen korrekt (d.h. ohne Rundungsfehler!) umgehen können. Mit Hilfe eines solchen Programms kann man RSA-Schlüssel wählbarer Länge herstellen. Dabei sucht das Programm zunächst für p und q "passende" Primzahlen und berechnet dann aus diesen die eigentlichen RSA-Verschlüsselungsparameter. Wenn Sie zum Beispiel für p und q zwei in Hex-Darstellung mindestens 50 bzw. 52 Byte lange Primzahlen haben wollen, dann dauert die Generierung eines Satzes von RSA-Schlüsseln auf (m)einem 700-MHz-Pentium3-Notebook knapp eine Minute, wobei die meiste Zeit für die Suche nach den Primzahlen gebraucht wird. Sie könnten dann zum Beispiel den folgenden RSA-Parametersatz erhalten:
      p = (0000A800 612D0AB0 026450E5 97C7F2FD 737F3C38 EB631224 34962979
           187696AE 3231A751 0EB65729 AFA4F950 8513473B 9FB90BD7)

      q = (E5D9FBA4 46A7D320 A849A22F ADFE7238 BE2C9CD3 31B9260D 0956F41E
           6E13DEE5 3B256AA3 4E0C8E18 61616CDA 7C72D990 6C8195AF)

      n = (000096D7 6463D7A1 290AA262 C832A5E3 A3C8099A 60356D16 116993A9
           95BAA188 84914A10 F7A967F4 48613C14 9B973E75 F1261E70 648D55C5
           4A7DE4B0 A2AFAA29 FABAE025 493E4FA5 5D623085 3A5E00D9 162029D3
           F7A5918E 1380DC22 84C7A36A 59EEDAE6 8EBA3AF9)

      e = (0000009B E60A1DAB)

      d = (00001334 1369E1BC 8E1AE39B 2E884403 5D716024 0D2F0F24 BDEBE176
           B463EA82 0793FBA5 6C73B9CA 1CA11DD7 D8E8DF8A 14815115 EEC25F8A
           0CCB7DE8 9892F0FB B2CD6EA8 A8A7AEB4 3712283A 59CC69D8 5206DD67
           CF33AF2E 10C22DDE 2BCC6086 E2C0D44C FB948E89

In dezimaler Schreibweise haben p und q jeweils über 120 Stellen, n hat 246 Dezimalstellen. Man sieht, dass Schlüssel dieser Größenordnungen durchaus ohne größere Probleme auf derzeit üblichen Computern erzeugt werden können. Wichtig für die Praxis ist, dass die Hilfszahlen p, q und Φ geheim bleiben. Um dies zu gewährleisten, sollte man sie gleich nach der Generierung der Schlüssel "wegwerfen"! Dies verursacht keinerlei Probleme, weil sie für den normalen Betrieb ja nicht mehr gebraucht werden. Dann muss man nur noch darauf achten, dass der geheime Schlüssel nicht in falsche Hände gerät.

Und wie wird nun tatsächlich ver- und entschlüsselt? Genau wie in unseren obigen Simulationen:
Jetzt ist es allerdings höchste Zeit, dass wir wirklich mal einen Text ver- und entschlüsseln, also z.B.:
    RSA ist cool!
    Erstaunlich ist, dass man das Verfahren
    verstehen kann, und es trotzdem sicher ist.
Die Zahl A konstruieren wir nun als eine Hex-Zahl, deren einzelne Byte die ASCII-Nummern der einzelnen Zeichen unseres zu verschlüsselnden Textes auflisten. Man erhält:
      A = (52534120 69737420 636F6F6C 210D0A45 72737461 756E6C69 63682069
           73742C20 64617373 206D616E 20646173 20566572 66616872 656E200D
           0A766572 73746568 656E206B 616E6E2C 20756E64 20657320 74726F74
           7A64656D 20736963 68657220 6973742E)
Das erste Byte "52h" ist die ASCII-Nummer des Buchstabens "R", das folgende "53h" kodiert das "S", usw. Beachten Sie im vierten Block die Bytes "0Dh 0Ah"! Wissen Sie noch, was das bedeutet?
Mit dem obigen öffentlichen Schlüssel (n, e) erhält man nun aus A die zu übermittelnde verschlüsselte Nachricht B = Ae mod n:
      B = (00007799 1529C7EF 1A0A773C 59817398 1E051E4C 7C469588 26CA1342
           ADFFD9B0 8603C160 81E2B1C5 4021195C 00A01335 444F6474 00DB69A4
           9AED1567 89A710C5 4109FACD FF9C09B0 4AC0CEA2 96367930 52500384
           C7F37A76 C5DB2CBF F5F97985 A7764E4F 239F514E)
Diese verschlüsselte Nachricht wird nun zum Empfänger geschickt, der sie dann mit seinem geheimen Schlüssel d entschlüsselt. Mit C = Bd mod n erhält er:
      C = (52534120 69737420 636F6F6C 210D0A45 72737461 756E6C69 63682069
           73742C20 64617373 206D616E 20646173 20566572 66616872 656E200D
           0A766572 73746568 656E206B 616E6E2C 20756E64 20657320 74726F74
           7A64656D 20736963 68657220 6973742E)
was punktgenau dasselbe ist wie A! Nun muss er nur noch die Bytes dieser Zahl als ASCII-Nummern von Textzeichen interpretieren lassen, und dann bekommt er die Nachricht:
    RSA ist cool!
    Erstaunlich ist, dass man das Verfahren
    verstehen kann, und es trotzdem sicher ist.
So weit, so gut. Aber wer macht die ganze Rechnerei mit diesen hunderte von Dezimalstellen langen Zahlen? Nun, zum Beispiel das Programm PrettyGoodPrivacy (kurz: "PGP") von Phil Zimmermann. Mit diesem Freeware-Programm, können Sie im Prinzip jeden E-Mail-Client um eine sichere RSA-Verschlüsselung erweitern. Phil Zimmermann hat dem Programm eine ausführliche Dokumentation beigefügt, in der er nicht nur genau beschreibt, wie es in der Praxis zur Zusammenarbeit mit Ihrem E-Mail-Client überredet werden kann, sondern auch, wie es intern arbeitet. Sie ahnen es sicher schon: im Detail ist das alles noch viel komplizierter als wir es bisher dargestellt haben, -- aber wir wollen hier nun doch einen Schlussstrich ziehen. Wer es noch genauer wissen will, soll die (sehr gute!) Dokumentation von Phil Zimmermann lesen.



9.3.4   Sicher??? Aber sicher!!!

Zum Schluss wollen wir noch kurz der Frage nachgehen, warum das RSA-Verfahren wirklich sicher ist. Natürlich wird die Sicherheit der Verschlüsselung von der Schlüssellänge abhängen: wenn wir nur 2-stellige Primzahlen für p und q verwenden, genügt etwas mathematischer Sachverstand und eine Taschenrechner, um aus dem öffentlichen den geheimen Schlüssel zu errechnen, wie wir ja oben schon gesehen haben! Die heiße Frage ist: Wie groß muss denn mein Modul n eigentlich sein? Sind z.B. meine im vorigen Abschnitt angegebenen Schlüssel (mit einem n mit über 240 Dezimalstellen) "gut genug"?

Zur Beurteilung der Sachlage wollen wir die Zeit abschätzen, die ein Hacker investieren muss, wenn er aus meinem öffentlichen Schlüssel (n, e) meinen geheimen Schlüssel d errechnen wollte. Dies wäre einfach, wenn er die Faktorisierung n = p * q kennen würde. Eine hinreichend große Zahl zu faktorisieren, ist aber mit einem immensen Aufwand verbunden, speziell dann, wenn sie keine kleinen Primfaktoren, sondern nur zwei sehr große hat.

Nehmen wir mal an, das p und q nur etwa jeweils 100 Dezimalstellen haben. Zwischen 1 und 10100 gibt es weit mehr als 1097 Primzahlen. (Dies folgt aus einem Satz der Zahlentheorie, nach dem sich die Anzahl der Primzahlen im Intervall [1..n] für große n immer mehr dem Wert von (n / (ln n)) annähert.) Selbst wenn der Hacker die Sache gut vorbereitet hat, indem er sich zuvor eine vollständige(!) Tabelle dieser Primzahlen besorgt hat, muss er immerhin mehr als 1097 Probe-Divisionen ausführen. Angenommen, sein Rechner hat eine Taktfrequenz von 10 GigaHertz, und für jede Probe-Division wäre nur ein Taktzyklus nötig, dann würde er für diesen Job also etwa 1097/1010 Sekunden brauchen; das sind deutlich mehr als 1079 Jahre! Zum Vergleich: das Alter des Universums wird auf etwa 1010 Jahre geschätzt...

Derzeit übliche Prozessoren brauchen für eine "Probe-Division" sicher weit mehr als den veranschlagten einen Taktzyklus. Und die benötigte Primzahl-Tabelle übersteigt bei weitem die Speicherkapazität des gesamten Internets! Im Detail sind die Annahmen für die obige Abschätzung für den Hacker so absurd optimistisch, dass innerhalb der nächsten 10 Jahre auch der besessenste Fortschrittsgläubige kaum mehr wagen wird, eine entsprechende RSA-Verschlüsselung mit einem solchen "Brut force"-Angriff knacken zu wollen. Andere ("intelligentere") Angriffe auf RSA-verschlüsselte Geheimnisse sind zwar schon häufig erforscht worden, aber es sind bisher keine Methoden bekannt geworden, die das Ergebnis wesentlich schneller liefern, ohne dabei von Fehlern der RSA-Anwender zu profitieren. Zu Recht redet man also beim RSA-Verfahren sehr bildhaft von "starker Kryptographie"!

Wohlgemerkt: allen Beteiligten ist klar, was man tun müsste, um einen RSA-Code zu knacken, und die Algorithmen sind nicht einmal besonders kompliziert! Der Schutz besteht darin, dass diese Algorithmen zwar effektiv, aber nicht effizient sind, d.h.: sie werden das Ergebnis sicher liefern, aber der Hacker wird nicht so viel Geduld aufbringen (können), darauf zu warten! An dieser Situation wird sich wahrscheinlich erst dann etwas Wesentliches ändern, wenn die "Quantencomputer" serienreif werden. Aber wer darauf warten will, braucht auch viel Geduld: bisher gibt es nur vereinzelte Labormuster, die nicht mehr als ein paar Bit manipulieren können. (Stand 2003)




9.4   Ich bin klein, mein Herz ist rein...

Wozu braucht ein unbescholtener Bürger eigentlich starke Kryptographie? Oft hört man das Argument: "Warum soll ich so ein kompliziertes System anwenden? Ich habe nichts zu verbergen, und wer meine E-Mails lesen will, soll sie halt lesen!" Wer so spricht, hofft darauf, mit diesem vordergründig einleuchtenden Argument den wirklichen Grund für seine Ignoranz hinreichend kaschiert zu haben, nämlich die eigene geistige Trägheit. Seien Sie aber gewarnt: irgend wann taucht doch mal die Notwendigkeit für eine sichere Verschlüsselung auf, und dann werden Sie froh sein, wenn Sie die Zeit vorher dazu genutzt haben, sich mit dem zugegebenermaßen nicht ganz einfachen System vertraut zu machen!

Auf öffentlichen Kanälen vertrauliche Informationen austauschen - diese Aufgabe wird in der Zukunft in vielen Varianten immer wichtiger werden: Bankgeschäfte, Steuerklärung, Bestellungen und Bezahlung von Waren und Dienstleistungen - all das können Sie derzeit schon über das Internet erledigen, und die Liste der Möglichkeiten wird täglich länger. Zum Beispiel bereitet schon manche Stadtverwaltung den Boden dafür, dass die Bürger in Zukunft den Kontakt zu den einzelnen Ämtern und Dienststellen über Online-Formulare knüpfen können. Ohne wirkungsvolle Verschlüsselung wäre das alles nicht vertrauenswürdig machbar. Da kann es nicht schaden, wenn man sich mit etwas Sachkenntnis wappnet, auch um kompetent entscheiden zu können, welche dieser Dienste man benutzt und welche lieber nicht. Wohl dem, der den Unterschied zwischen "http:" und "https:" kennt, und der die Angaben des Web-Seiten-Anbieters zur verwendeten Verschlüsselungstechnik verstehen, einschätzen und werten kann!

Phil Zimmermann geht in seiner PGP-Dokumentation noch einen Schritt weiter: für ihn ist die Möglichkeit der sicher verschlüsselten Kommunikation ein elementares Bürgerrecht, auf das niemand verzichten sollte, selbst wenn er es derzeit nicht wahrnimmt. Wir alle sollten die Zeit nützen und dafür sorgen, dass ernsthaft private Kommunikation eine für alle Bürger frei verfügbare Möglichkeit bleibt - ehe der Gesetzgeber uns dies verbietet! Mit der Begründung der Terrorismusbekämpfung hat gerade in den letzten Jahren manche Regierung die Bürgerrechte massiv eingeschränkt - wohl in guter Absicht, aber nicht immer mit dem nötigen Augenmaß. Im Hinblick auf die Verschlüsselung können Sie derzeit noch Fakten schaffen, ehe ein Gesetz den Einsatz starker Kryptographie für private Zwecke verbietet und ausschließlich den Geheimdiensten vorbehält!



Zum vorigen Kapitel Zum Inhaltsverzeichnis