Die Darstellung mit verschiedenen Basiszahlen

Inhalt

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 rechte 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 1 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 1 und 2 konstruiert.

2. Diese Darstellung zur Basis 4 wandeln wir in eine Darstellung zur Basis 10 um, damit wir zur Verschlüsselung die Tabelle 1 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 1 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 1 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 2 und erhält die Sequenz 4, 35, 8. Und das entspricht, als Zahlenfolge genau der ursprünglichen Nachricht.

Anhand der Tabellen 1 und 2 können wir ebensogut Nachrichten unter Verwendung des geheimen Schlüssels (d.h. erst Tabelle 2 benutzen) verschlüsseln, dann mit dem öffentlichen Schlüssel (d.h. Tabelle 1 als zweites benutzen) dekodieren und damit unsere ursprüngliche Zahl wieder herstellen. Das bedeutet -­ wie wir bereits im Handbuch „Gpg4win für Einsteiger“ gesehen haben --, 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.

Wie Sie gesehen haben, ist die ganze Angelegenheit zwar im Detail kompliziert, im Prinzip aber durchaus nachvollziehbar. Sie sollen schließlich nicht nur 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 kann sie auch noch zu lesen...

Die Darstellung mit verschiedenen Basiszahlen

Inhalt