25 GnuPG und das Geheimnis der großen Zahlen

Inhalt

25 GnuPG und das Geheimnis der großen Zahlen

basiert⁶, zu „knacken“, also einen privaten Schlüssel zu berechnen, wenn man lediglich den öffentlichen Schlüssel kennt. Diese Berechnung ist aber noch nie für Schlüssellängen (1024 Bit und mehr), die in GnuPG verwendet werden, gelungen. Es ist zwar theoretisch möglich, aber praktisch nicht durchführbar! Denn selbst bei genügend vorhandener Zeit (viele Jahre) und Abertausenden von vernetzten Rechnern würde niemals genügen Speicher zur Verfügung stehen, um den letzten Schritt dieser Berechnung durchführen zu können.

Es kann allerdings durchaus möglich sein, dass eines Tages eine geniale Idee die Mathematik revolutioniert und eine schnelle Lösung des mathematischen Problems, welches hinter RSA steckt, liefert. Dies wird aber wohl kaum von heute auf morgen geschehen. Das Bundesamt für Sicherheit in der Informationstechnik (BSI) veröffentlicht von Zeit zu Zeit Prognosen und Einschätzungen, welche Schlüssellängen noch wieviele Jahre für absolute Geheimhaltung benutzt werden sollen. GnuPG überschreitet mit seinen Standardeinstellungen noch weit diese Mindestanforderungen. Wie im vorigen Kapitel schon angerissen, ist die Mathematik der mit Abstand sicherste Teil an der ganzen praktisch angewandten Kryptographie.

Im Folgenden erfahren Sie, wie diese mathematische Methode funktioniert. Nicht in allen Einzelheiten (das würde den Rahmen dieser Anleitung bei weitem sprengen), aber doch so, dass Sie bei etwas Mitrechnen selbst mathematisch korrekt ver- und entschlüsseln können und dabei das „Geheimnis der großen Zahlen“ entdecken.

Man kann diese komplexe mathematische Methode auch als Normalsterblicher und Nichtmathematiker verstehen. Sie müssen nur einfache Additionen und Multiplikationen beherrschen. Wie gesagt: Hier beginnt der Kürteil, und bei der Kür geht es immer etwas mehr zur Sache als im Pflichtprogramm. Letztendlich versteht man dann aber, warum GnuPG sicher ist.

Eine Begriffsklärung vorneweg:

Die Verschlüsselung mit GnuPG basiert auf dem sogenannten RSA-Algorithmus⁷. RSA steht für die Nachnamen von Ron Rivest, Ami Shamir und Ben Adleman, die diesen Algorithmus im Jahr 1978 entdeckt haben. Dieser Algorithmus verwendet einen Typ der Arithmetik, die Rechnen mit Restklassen oder „Modulo-Arithmetik“ heißt.

25.1 Das Rechnen mit Restklassen

Wenn man mit Restklassen rechnet, so bedeutet dies, dass man nur mit dem „Rest“ rechnet, der nach einer ganzzahligen Teilung durch eine bestimmte Zahl übrigbleibt. Diese Zahl, durch die geteilt wird, nennt man den „Modul“ oder die „Modulzahl“. Wenn wir beispielsweise mit dem Teiler oder der Modulzahl 5 rechnen, sagen wir auch, „wir rechnen modulo 5“.

Wie das Rechnen mit Restklassen - auch Modulo-Arithmetik oder Kongruenzrechnung genannt - funktioniert, kann man sich gut klarmachen, wenn man sich das Zifferblattes einer Uhr vorstellt:

Um beispielsweise 3 + 2 zu rechnen, beginnen wir bei der Ziffer 2 und drehen den Zeiger um 3 Striche weiter (oder wir starten bei der 3 und drehen 2 Striche weiter, was natürlich auf dasselbe hinausläuft) Das Ergebnis ist 5.

Zählt man auf diese Weise 7 + 8 zusammen, erhält man 3. Denn 3 ist der Rest, wenn man 15 (also 7 + 8) durch 12 teilt. Um 5 mit 7 zu multiplizieren, beginnt man bei 0 und dreht 7 mal jeweils um 5 Striche weiter (oder auch bei 0 beginnend 5 mal um 7 Striche). In beiden Fällen bleibt der Zeiger bei 11 stehen. Denn 11 ist der Rest, wenn 35 (also 7 * 5) durch 12 geteilt wird.

Beim Rechnen mit Restklassen addieren und teilen wir Zahlen also nach den normalen Regeln der Alltagsarithmetik, verwenden dabei jedoch immer nur den Rest nach der Teilung. Um anzuzeigen, dass wir nach den Regeln der Modulo-Arithmetik und nicht nach denen der üblichen Arithmetik rechnen, schreibt man den Modul (Sie wissen schon - den Teiler) dazu. Man sagt dann zum Beispiel „4 modulo 5“, schreibt aber kurz „4 mod5“.

Bei Modulo-5 zum Beispiel hat man dann eine Uhr, auf deren Zifferblatt es nur die 0, 1, 2, 3 und 4 gibt. Also:

4 mod5 + 3 mod5 = 7 mod5 = 2 mod5

Anders ausgedrückt, ist in der Modulo-5 Arithmetik das Ergebnis aus 4 plus 3 gleich 2. Wir können also auch schreiben:

9 mod5 + 7 mod5 = 16 mod5 = 1 mod5

Wir sehen auch, dass es egal ist, in welcher Reihenfolge wir vorgehen, weil wir nämlich auch schreiben können:

9 mod5 + 7 mod5 = 4 mod5 + 2 mod5 = 6 mod5 = 1 mod5

Denn 4 ist dasselbe wie 9, und 2 dasselbe wie 7, da wir uns ja nur für den jeweiligen Rest nach der Teilung durch 5 interessieren. Daran wird deutlich, dass wir bei dieser Art der Arithmetik jederzeit 5 oder ein Vielfaches von 5, wie 10, 15 und so weiter nehmen können, und das Ergebnis stets dasselbe ist.

Das funktioniert auch beim Multiplizieren (Malnehmen).

Ein Beispiel:

4 mod5 * 2 mod5 = 8 mod5 = 3 mod5

Ebenso können wir schreiben:

9 mod5 * 7 mod5 = 63 mod5 = 3 mod5

da wir einfach 60, also 5 * 12, abziehen können.

Man könnte aber auch schreiben:

9 mod5 * 7 mod5 = 4 mod5 * 2 mod5 = 8 mod5 = 3 mod5

denn 4 entspricht 9, und 2 entspricht 7, wenn wir nur den Rest nach Teilung durch 5 betrachten.

Widerum stellen wir fest, dass es egal ist, wenn wir das Vielfache von 5 einfach weglassen.

Da dadurch alles einfacher wird, machen wir das, bevor wir Zahlen addieren oder multiplizieren. Das bedeutet, dass wir uns lediglich um die Zahlen 0, 1, 2, 3 und 4 kümmern müssen, wenn wir mit der Modulo-5 Arithmetik rechnen. Denn wir können ja alles, was durch 5 teilbar ist, weglassen. Dazu noch drei Beispiele:

5 mod11 * 3 mod11 = 15 mod11 = 4 mod11

2 mod7 * 4 mod7 = 1 mod7

13 mod17 * 11 mod17 = 7 mod17

Das letzte Beispiel wird klar, wenn man bedenkt, dass in normaler Arithmetik gerechnet 13 * 11 = 143 und 143 = 8 * 17 + 7 ist.

25.2 RSA-Algorithmus und Rechnen mit Restklassen

Computer speichern Buchstaben als Zahlen. Alle Buchstaben und Symbole auf der Computertastatur werden in Wirklichkeit als Zahlen gespeichert, die zwischen 0 und 255 liegen.

Wir können also eine Nachricht auch in eine Zahlenfolge umwandeln. Nach welcher Methode (oder Algorithmus) dies geschieht, wird im nächsten Abschnitt beschrieben. Darin stellen wir Ihnen die Methode vor, nach der die Verschlüsselung mit GnuPG funktioniert: den RSA Algorithmus. Dieser Algorithmus wandelt eine Zahlenfolge (die ja eine Nachricht darstellen kann) so in eine andere Zahlenfolge um (Transformation), dass die Nachricht dabei verschlüsselt wird. Wenn man dabei nach dem richtigen Verfahren vorgeht, wird die Nachricht sicher kodiert und kann nur noch vom rechtmäßigen Empfänger dekodiert werden. Das sind die Grundlagen des RSA Algorithmus:

Sie selbst haben bei der Installation von Gpg4win während der Eingabe Ihrer Passphrase zwei große Primzahlen erzeugt, ohne es zu bemerken (dieser werden mit p und q bezeichnet). Nur Sie -­ oder in der Praxis Ihr Computer -­ kennen diese beiden Primzahlen, und Sie müssen für ihre Geheimhaltung sorgen.

Es werden daraus nun drei weitere Zahlen erzeugt:

Die erste Zahl

ist das Ergebnis der Multiplikation der beiden Primzahlen, also ihr Produkt. Dieses Produkt wird als Modulus und dem Buchstaben n bezeichnet. Dies ist der Modul mit dem wir später immer rechnen werden.

Die zweite Zahl

ist der sogenannte öffentliche Exponent und eine Zahl an die bestimmte Anforderungen gestellt werden (teilerfremd zu (p-1)(q-1)); sie wird mit e bezeichnet. Häufig wird hier 3, 41 oder 65537 benutzt.

Die dritte Zahl

wird errechnet aus dem öffentlichem Exponent (der zweiten Zahl) und den beiden Primzahlen. Diese Zahl ist der geheime Exponent und wird mit d bezeichnet. Die komplizierte Formel zur Berechnung lautet:

d = e^-1 mod(p - 1)(q -1)

Die erste und die zweite Zahl werden veröffentlicht ­- das ist Ihr öffentlicher Schlüssel. Beide werden dazu benutzt, Nachrichten zu verschlüsseln. Die dritte Zahl muss von Ihnen geheimgehalten werden ­- es ist Ihr geheimer Schlüssel. Die beiden Primzahlen werden danach nicht mehr benötigt.

Wenn eine verschlüsselte Nachricht empfangen wird, kann sie entschlüsselt werden mit Hilfe der ersten (n) und der dritten Zahl (d). Nur der Empfänger kennt beide Schlüsselteile ­- seinen öffentlichen und seinen geheimen Schlüssel. Der Rest der Welt kennt nur den öffentlichen Schlüssel (n und e).

Die Trick des RSA Algorithmus liegt nun darin, dass es unmöglich ist, aus dem öffentlichen Schlüsselteil (n und e) den geheimen Schlüsselteil (d) zu errechnen und damit die Botschaft zu entschlüsseln - denn: Nur wer im Besitz von d ist, kann die Botschaft entschlüsseln.

25.3 RSA Verschlüsselung mit kleinen Zahlen

Wir verwenden hier erst einmal kleine Zahlen, um deutlich zu machen, wie die Methode funktioniert. In der Praxis verwendet man jedoch viel größere Primzahlen, die aus ­zig Ziffern bestehen.

Nehmen wir die Primzahlen 7 und 11. Damit verschlüsseln wir Zahlen ­- oder Buchstaben, was für den Computer dasselbe ist - nach dem RSA Algorithmus.

Und zwar erzeugen wir zunächst den öffentlichen Schlüssel

Die erste Zahl

ist 77, nämlich das Ergebnis der Multiplikation der beiden Primzahlen, 7 und 11. 77 dient uns im weiteren Verlauf als Modulus zur Ver- und Entschlüsselung.

Die zweite Zahl

ist der öffentliche Exponent. Wir wählen hier 13.

Die dritte Zahl

ist der geheime Schlüssel. Sie wird in einem komplizierten Verfahren errechnet, welches wir jetzt erklären:

Zunächst ziehen wir von unseren Primzahlen 7 und 11 jeweils die Zahl 1 ab (also 7 - 1 und 11 - 1) und multiplizieren die beiden resultierenden Zahlen miteinander. In unserem Beispiel ergibt das 60: ( 7 - 1 ) * ( 11 - 1) = 60. 60 ist unsere Modulzahl für die weiterführende Berechnung des geheimen Schlüssels (sie ist aber nicht mit dem eigentlichen Modulus 77 zu verwechseln).

Wir suchen jetzt eine Zahl, die multipliziert mit dem öffentlichen Schlüssel die Zahl 1 ergibt, wenn man mit dem Modul 60 rechnet:

13 mod60 * ? mod60 = 1 mod60

Die einzige Zahl, die diese Bedingung erfüllt, ist 37, denn

13 mod60 * 37 mod60 = 481 mod60 = 1 mod60

37 ist die einzige Zahl, die multipliziert mit 13 die Zahl 1 ergibt, wenn man mit dem Modul 60 rechnet.

Wir verschlüsseln mit dem öffentlichen Schlüssel eine Nachricht

Nun zerlegen wir die Nachricht in eine Folge von Zahlen zwischen 0 und 76, also 77 Zahlen, denn sowohl Verschlüsselung als auch Entschlüsselung verwenden den Modul 77 (das Produkt aus den Primzahlen 7 und 11).

Jede einzelne dieser Zahlen wird nun nach der Modulo-77 Arithmetik 13 mal mit sich selbst multipliziert. Sie erinnern sich: die 13 ist ja unser öffentlicher Schlüssel.

Nehmen wir ein Beispiel mit der Zahl 2: sie wird in die Zahl 30 umgewandelt, weil 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 8192 = 30 mod77 sind.

Ein weiteres Beispiel: 75 wird in die Zahl 47 umgewandelt, denn 75 wird 13 mal mit sich selbst multipliziert und durch 77 geteilt, so dass der Rest 47 entsteht.

Wenn man eine solche Rechnung für alle Zahlen zwischen 0 und 76 durchführt und die Ergebnisse in eine Tabelle einsetzt, sieht diese so aus:

In der linken Spalte stehen die 10er-Stellen, in der oberen Zeile die 1er-Stellen.

Wir entschlüsseln eine Nachricht mit dem privaten Schlüssel

Um das Beispiel mit der 2 von oben umzukehren, also die Nachricht zu dekodieren, multiplizieren wir 30 (die umgewandelte 2) unter Verwendung der Modulzahl 77 37 mal mit sich selbst. Sie erinnern sich: 37 ist der geheime Schlüssel.

Diese wiederholte Multiplikation ergibt eine Zahl die 2 mod77 ergibt. Das andere Beispiel: die Zahl 47 mod77 wird zur Zahl 75 mod77 dekodiert.

Tabelle 25.3 zeigt die genaue Zuordnung der 77 Zahlen zwischen 0 und 76.

Um eine Zahl mit Tabelle 25.3 zu transformieren, gehen wir nach der gleichen Methode vor wie bei Tabelle 25.3. Ein Beispiel: 60 wird transformiert in die Zahl in Zeile 60 und Spalte 0. Also wird 60 zu 25 transformiert.

Das überrascht nicht, denn wenn wir davon ausgehen, dass wir bei der Umwandlung von 25 mit Hilfe von Tabelle 25.3 als Ergebnis 60 erhalten, dann sollten wir auch bei der Transformation von 60 mit Hilfe von Tabelle 25.3 zum Ergebnis 25 gelangen. Dabei haben wir den öffentlichen Schlüssel, 13, zur Umwandlung bzw. Kodierung einer Zahl verwendet, und den geheimen Schlüssel 37, um sie zurückzuwandeln bzw. zu dekodieren. Sowohl für die Verschlüsselung als auch für die Entschlüsselung haben wir uns der Modulo-77 Arithmetik bedient.

Zusammenfassung

Wir haben...

• durch den Computer zwei zufällige Primzahlen erzeugen lassen;
• daraus das Produkt und den öffentlichen und den geheimen Subkey gebildet;
• gezeigt, wie man mit dem öffentlichen Schlüssel Nachrichten verschlüsselt;
• gezeigt, wie man mit dem geheimen Schlüssel Nachrichten entschlüsselt.

Diese beiden Primzahlen können so groß gewählt werden, dass es unmöglich ist, sie einzig aus dem öffentlich bekannt gemachten Produkt zu ermitteln. Das begründet die Sicherheit des RSA Algorithmus.

Wir haben gesehen, dass die Rechnerei sogar in diesem einfachen Beispiel recht kompliziert geworden ist. In diesem Fall hat die Person, die den Schlüssel öffentlich gemacht hat, die Zahlen 77 und 13 als öffentlichen Schlüssel bekanntgegeben. Damit kann jedermann dieser Person mit der oben beschriebenen Methode -­ wie im Beispiel der Tabelle 25.3 -­ eine verschlüsselte Zahl oder Zahlenfolge schicken. Der rechtmäßige Empfänger der verschlüsselten Zahlenfolge kann diese dann mit Hilfe der Zahl 77 und dem geheimen Schlüssel 37 dekodieren.

In diesem einfachen Beispiel ist die Verschlüsselung natürlich nicht sonderlich sicher. Es ist klar, dass 77 das Produkt aus 7 und 11 ist.

Folglich kann man den Code in diesem einfachen Beispiel leicht knacken. Der scharfsinnige Leser wird auch bemerkt haben, dass etliche Zahlen, zum Beispiel die Zahl 11 und ihr Vielfaches (also 22, 33 etc.) und die benachbarten Zahlen sich in sich selbst umwandeln.

Das erscheint als ein weiterer Schwachpunkt dieser Verschlüsselungsmethode: man könnte annehmen, dass die Sicherheit des Algorithmus dadurch beeinträchtigt würde. Doch stellen Sie sich nun vor, das Produkt zweier grosser Primzahlen, die auf absolut willkürliche Art und Weise gewählt werden, ergäbe

114,381,625,757,888,867,669,235,779,976,146,612,010,
218,296,721,242,362,562,561,842,935,706,935,245,733,
897,830,597,123,563,958,705,058,989,075,147,599,290,
026,879,543,541

Hier ist überhaupt nicht mehr ersichtlich, welche die beiden zugrunde liegenden Primzahlen sind. Folglich ist es sehr schwierig, aufgrund des öffentlichen Schlüssels den geheimen Schlüssel zu ermitteln. Selbst den schnellsten Computern der Welt würde es gewaltige Probleme bereiten, die beiden Primzahlen zu errechnen.

Man muss die Primzahlen also nur groß genug wählen, damit ihre Berechnung aus dem Produkt so lange dauert, dass alle bekannten Methoden daran in der Praxis scheitern. Außerdem nimmt der Anteil der Zahlen, die in sich selbst transformiert werden -­ wie wir sie oben in den Tabellen 25.3 und 25.3 gefunden haben - stetig ab, je größer die Primzahlen werden. Von Primzahlen in der Grössenordnung, die wir in der Praxis bei der Verschlüsselung verwenden, ist dieser Teil ist so klein, dass der RSA Algorithmus davon in keiner Weise beeinträchtigt wird.

Je größer die Primzahlen, desto sicherer die Verschlüsselung. Trotzdem kann ein normaler PC ohne weiteres das Produkt aus den beiden großem Primzahlen bilden. Kein Rechner der Welt dagegen kann aus diesem Produkt wieder die ursprünglichen Primzahlen herausrechnen -­ jedenfalls nicht in vertretbarer Zeit.

25.4 Die Darstellung mit verschiedenen Basiszahlen

Um zu verstehen, wie Nachrichten verschlüsselt werden, sollte man wissen, wie ein Computer Zahlen speichert und vor allem, wie sie in unterschiedlichen Zahlenbasen dargestellt werden können.

Dazu machen wir uns zunächst mit den Zahlenpotenzen vertraut.

Zwei hoch eins, das man als 2¹ darstellt, ist gleich 2; zwei hoch drei, dargestellt als 2³, ist 2 * 2 * 2 = 8; zwei hoch zehn, dargestellt als 2¹⁰, ist 2*2*2*2*2*2*2*2*2*2 = 1024.

Jede Zahl hoch 0 ist gleich 1, zum Beispiel 2⁰ = 1 und 5⁰ = 1. Verallgemeinert bedeutet dies, dass eine potenzierte Zahl so oft mit sich selbst multipliziert wird, wie es die Hochzahl (Potenz) angibt.

Das Konzept einer Zahlenbasis veranschaulicht zum Beispiel ein Kilometerzähler im Auto: das rechte Rad zählt nach jedem Kilometer eine Stelle weiter und zwar nach der vertrauten Abfolge der Zahlen

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, ...

und so weiter. Jedesmal, wenn das rechte Rad wieder 0 erreicht, zählt das Rad links davon eine Stelle hoch. Und jedesmal, wenn dieses zweite Rad die 0 erreicht, erhöht das Rad links davon um eins ...und so weiter.

Nach dem gleichen Prinzip stellen wir ja auch unsere normale Zahlen mit den Ziffern 0 bis 9 dar.

entspricht 578.

Hier haben wir die „5“ stellvertretend für fünfhundert, „7“ für siebzig und „8“ für acht. In diesem Fall ist die Basis 10, eine für uns vertraute Basis.

Also steht die rechte Ziffer für die Einer der betreffenden Zahl (d.h. sie wird mit 1 multipliziert), die Ziffer links davon steht für die Zehner (d.h. wird mit 10 multipliziert), die nächste Ziffer wiederum für die Hunderter (d.h. sie wird mit 100 multipliziert) und so weiter. Da wir Zahlen normalerweise zur Basis 10 darstellen, machen wir uns nicht die Mühe, die Basis extra anzugeben. Formal würde man dies bei der Zahl 55 mit der Schreibweise 55₁₀ anzeigen, wobei die tiefgestellte Zahl die Basis anzeigt.

Wenn wir nicht zur Basis 10 darstellen, so müssen wir dies mit Hilfe einer solchen tiefgestellten Basiszahl anzeigen.

Angenommen, die Anzeige des Kilometerzählers hätte statt der Ziffern 0 bis 9 nur noch 0 bis 7. Das rechte Rädchen würde nach jedem Kilometer um eine Ziffer höher zählen, wobei die Zahlenfolge so aussehen würde:

0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, und so weiter.

Unser Tacho zur Basis 8 stellt zum Beispiel folgende Zahl dar:

356

Die 6 auf dem rechten Rädchen zählt einzelne Kilometer, also 6 Kilometer.
Die 5 auf dem Rädchen daneben für 5 * 8, also 40 Kilometer.
Die 3 links steht für je 64 Kilometer pro Umdrehung, also hier 3 * 8 * 8 Kilometer.

So rechnet man also mit Zahlen zur Basis 8. Ein Beispiel: 728 bedeutet 7 * 8 + 2, und das ist gleich „58“. Bei dieser Art der Darstellung steht die „2“ aus der 72 für 2, aber die „7“ steht für 7 * 8.

Größere Zahlen werden schrittweise genauso aufgebaut, so dass 453₈ eigentlich 4 * 64 + 5 * 8 + 3 bedeutet, was 299 ergibt.

Bei 453₈ steht die „3“ für 3, die „5“ für 5 * 8 und die „4“ für 4 * 64, wobei sich die „64“ wiederum aus 8 * 8 herleitet.

Im angeführten Beispiel werden die Ziffern, von rechts nach links gehend, mit aufsteigenden Potenzen von 8 multipliziert. Die rechte Ziffer wird mit 8 hoch 0 (das ist 1) multipliziert, die links daneben mit 8 hoch 1 (das ist 8), die nächste links davon mit 8 hoch 2 (das ist 64) und so weiter.
Wenn man Zahlen zur Basis 10 darstellt, gibt es keine höhere Ziffer als 9 (also 10 minus 1). Wir verfügen also über keine Ziffer, die 10 oder eine größere Zahl darstellt. Um 10 darzustellen, brauchen wir zwei Ziffern, mit denen wir dann die „10“ schreiben können.
Wir haben also nur die Ziffern 0 bis 9.

So ähnlich ist es, wenn wir mit der Basiszahl 8 rechnen: dann haben wir nur die Ziffern 0 bis 7. Wollen wir zu dieser Basis eine höhere Zahl als sieben darstellen, müssen wir wieder zwei Ziffern verwenden. Zum Beispiel „9“ schreibt man als 11₈, „73“ schreibt man als 111₈.

Computer speichern Zahlen als eine Folge von Nullen und Einsen. Man nennt dies Binärsystem oder Rechnen mit der Basiszahl 2, weil wir nur die Ziffern 0 und 1 verwenden. Stellen Sie sich vor, wir würden die Kilometer mit einem Tachometer zählen, auf dessen Rädchen sich nur zwei Ziffern befinden: 0 und 1. Die Zahl 10101₂ zum Beispiel bedeutet im Binärsystem

1 * 16 + 0 * 8 + 1 * 4 + 0 * 2 + 1 = 21

In der Computerei verwendet man auch Gruppen von acht Binärziffern, das wohlbekannte Byte. Ein Byte kann Werte zwischen 0 - dargestellt als Byte 00000000₂ - und 255 - dargestellt als Byte 11111111₂ - annehmen. Ein Byte stellt also Zahlen zur Basis 256 dar.

Zwei weitere Beispiele:

10101010₂ = 170

00000101₂ = 5

Da der Computer die Buchstaben, Ziffern und Satzzeichen als Bytes speichert, schauen wir uns an, welche Rolle dabei die Darstellung zur Basis 256 spielt.

Nehmen wir die Silbe „un“. Das „u“ wird im Computer als 117 gespeichert und das „n“ als 110.

Diese Zahlenwerte sind für alle Computer standardisiert und werden ASCII-Code genannt. Um alle Zahlen und Symbole darstellen zu können, benötigen wir auf dem Computer die 256 Zahlen von 0 bis 255.

Wir können also die Silbe „un“ durch die Zahl 117 * 256 + 110 darstellen.
Entsprechend würde man die Buchstabenfolge „und“ mit der Zahl 117 * 65536 + 110 * 256 + 100 darstellen, denn das „d“ wird durch 100 repräsentiert.
Wir haben hier also Zahlen und Symbole, die auf der Computertastatur als normale Zahlen zur Basis 10 stehen, intern durch Zahlen zur Basis 256 repräsentiert.

Entsprechend können wir aus jeder Nachricht eine große Zahl machen. Aus einer langen Nachricht wird also eine gewaltig große Zahl. Und diese sehr große Zahl wollen wir nun nach dem RSA Algorithmus verschlüsseln.

Wir dürfen allerdings dabei die Zahl, zu der die Nachricht verschlüsselt wird, nicht größer werden lassen als das Produkt der Primzahlen (Modulus). Ansonsten bekommen wir Probleme, wie wir gleich noch sehen werden.

Da die folgende Prozedur mehrere Schritte umfaßt, fassen wir sie zunächst zusammen und verfolgen dann die Einzelschritte:

1. Die Nachricht aba, cad, ada wandeln wir - wie gesehen - in Zahlen um.
2. Diese Darstellung zur Basis 4 wandeln wir in eine Darstellung zur Basis 10 um, damit wir zur Verschlüsselung die Tabelle 25.3 benutzen können, in denen die Zahlen ja auch auf 10er-Basis dargestellt werden. Dabei entsteht eine kodierte Nachricht zur Basis 10.
3. Um die Kodierung im Vergleich zum „Klartext“ zu erkennen, rechnen wir die zur Basis 10 kodierte Nachricht auf die Basis 4 zurück und wandeln sie dann wieder in eine Buchstabensequenz.
4. So entsteht aus der Nachricht aba, cad, ada die verschlüsselte Nachricht dbb, ddd, dac.

Und nun ausführlich:

1. Die Nachricht aba, cad, ada wandeln wir - wie gesehen - in Zahlen um. Angenommen, wir beschränken uns bei den Nachrichten auf die 4 Buchstaben a, b, c und d. In diesem - wirklich sehr einfachen - Beispiel können wir die vier Buchstaben durch die Zahlenwerte 0, 1, 2 und 3 darstellen, und haben dann

   a = 0, b = 1, c = 2  und  d = 3

   . Wir wollen nun die Nachricht „abacadaca“ verschlüsseln. Wir kodieren diese Nachricht mit Hilfe der Primzahlen 7 und 11, mit dem öffentlichen Schlüssel 77 und 13 und dem dazugehörenden geheimen Schlüssel 37. Dieses Beispiel kennen wir bereits aus dem früheren Kapitel: wir haben damit die Tabellen 25.3 und 25.3 konstruiert.
2. Diese Darstellung zur Basis 4 wandeln wir in eine Darstellung zur Basis 10 um, damit wir zur Verschlüsselung die Tabelle 25.3 benutzen können, in denen die Zahlen ja auch auf 10er-Basis dargestellt werden. Weil wir vier Buchstaben für die Nachricht verwenden, rechnen wir zur Basis 4. Für die Rechnung modulo 77 müssen wir die Nachricht in Stücke von je drei Zeichen Länge zerlegen, weil die größte dreiziffrige Zahl zur Basis 4 die 333₄ ist. Zur Basis 10 hat diese Zahl den Wert 63. Würden wir stattdessen die Nachricht in vier Zeichen lange Stücke zerlegen, würde die Zahl zu Basis 4 den Wert 76 übersteigen und es würden unerwünschte Doppeldeutigkeiten entstehen.
   Folglich würde die Nachricht in dreiziffrigen Stücken nun

   aba, cad, aca

   ergeben. Geben wir den Zeichen nun ihre Zahlenwerte und vergessen dabei nicht, dass die Stücke dreiziffrige Zahlen zur Basis 4 darstellen. Da wir die Buchstaben durch die Zahlen a = 0, b = 1, c = 2, d = 3 darstellen, wird die Nachricht zu:

   010₄, 203₄, 020₄

   Zur Basis 10 wird diese Nachricht durch die Zahlenfolge 4, 35, 8 dargestellt. Warum? Nehmen wir zum Beispiel das mittlere Stück 203₄:

   3 * 4^0,	also  3 * 1,	also  3
   0 * 4^1,	also  0 * 4,	also  0
   2 * 4^2,	also  2 * 16,	also  32

3. Jetzt können wir zur Verschlüsselung die Tabelle 25.3 benutzen, die ja zur Basis 10 berechnet wurde. Diese Tabelle benutzen wir, weil wir mit dem schon bekannten Schlüsselpaar arbeiten wollen. Dabei entsteht eine kodierte Nachricht zur Basis 10. Zum Verschlüsseln der Nachricht nehmen wir jetzt Tabelle 25.3 zur Hilfe. Die Nachricht wird nun zu der Zahlenfolge 53, 63, 50 (zur Basis 10).

   

4. Wiederum zur Basis 4 konvertiert, entsteht die verschlüsselte Nachricht. Wird sie nun wieder zur Basis 4 konvertiert, ergibt die Nachricht nun 311₄, 333₄, 302₄. Konvertiert man diese zu einer Buchstabensequenz, erhält man dbb, ddd, dac, was sich nun erheblich von der ursprünglichen Nachricht unterscheidet. Man kehrt nun also den Prozeß um und transformiert die Zahlenfolge 53, 63, 50 mit Tabelle 25.3 und erhält die Sequenz 4, 35, 8. Und das entspricht, als Zahlenfolge genau der ursprünglichen Nachricht. Anhand der Tabellen 25.3 und 25.3 können wir ebensogut Nachrichten unter Verwendung des geheimen Schlüssels (d.h. erst Tabelle 25.3 benutzen) verschlüsseln, dann mit dem öffentlichen Schlüssel (d.h. Tabelle 25.3 als zweites benutzen) dekodieren und damit unsere ursprüngliche Zahl wieder herstellen. Das bedeutet, dass der Inhaber des geheimen Schlüssels damit Nachrichten unter Verwendung des RSA Algorithmus verschlüsseln kann. Damit ist bewiesen, dass sie eindeutig nur von ihm stammen können.

Fazit:

Wie Sie gesehen haben, ist die ganze Angelegenheit zwar im Detail kompliziert, im Prinzip aber durchaus nachvollziehbar. Sie sollen schließlich nicht einer Methode einfach nur vertrauen, sondern ­- zumindest ansatzweise ­- ihre Funktionsweise durchschauen. Sehr viele tiefergehende Details sind leicht in anderen Büchern (z.B.: R. Wobst, „Abenteuer Kryptologie“) oder im Internet zu finden.

E-Mails zu schaffen macht, ist er durchaus so lange damit beschäftigt, dass er dann keine Lust mehr haben dürfte diese auch noch zu lesen...

25 GnuPG und das Geheimnis der großen Zahlen

Inhalt