Der erweiterte euklidische Algorithmus

Gesucht ist die Vielfachsummendarstellung, die man mit dem erweiterten euklidischen Algorithmus berechnen kann. Mit ihrer Hilfe findet man d den privaten Schlüssel, zum Entschlüsseln von Nachrichten.
Um nun den erweiterten euklidischen Algorithmus anzuwenden legt man sich erst einmal eine Tabelle mit vier Spalten an.

Die erste Spalte wird q genannt und enthält in der ersten Zeile keinen Wert. In der zweiten Spalte, die g genannt wird, werden in die erste Zeile der Wert von j(n) und in die zweite Zeile e eigegeben. In der dritten Zeile, die y genannt wird (weil sie am Ende einen der Faktoren der Vielfachsummendarstellung ausgibt) in die erste Zeile 1 und in die zweite 0 hineingeschrieben. In der vierten Spalte, die x genannt wird (weil sie nach der Berechnung den zweiten Faktor ausgibt, der dann am Ende d ist) steht in der ersten Zeile 0 und in der zweiten 1. In der Spalte q ist die erste und zweite Zeile noch leer.

Man geht nun wie folgt vor:
In der zweiten Spalte muß man den Wert von j(n) durch den Wert von e teilen und nur das ganzzahlige Ergebnis in die dritte Zeile der ersten Spalte (q) schreiben.
Danach errechnet man den Rest, der dabei zurück bleibt, aus und schreibt ihn in die dritte Zeile der zweiten Spalte (g).
Als nächstes muss man, um die dritte Zeile in der dritten Spalte auszurechnen, von der Zahl aus der ersten Zeile (q) der dritte Spalte, das Produkt von der Zahl aus der dritten Spalte der zweiten Zeile (g) und die Zahl aus der dritten Zeile der erste Spalte (q) subtrahieren.
Die vierte Spalte entsteht dann genauso wie die dritte nur, dass man statt der Zahlen aus der dritten Spalte die Zahlen aus der vierten Spalte (x) nimmt.
Um die anderen Zeilen auszurechnen muss man das oben beschriebene Verfahren anwenden, nur, dass jetzt mit der neu ausgerechneten Zeile weiter gerechnet wird.

Ein Beispiel dazu:

e=31 und (n)=79.

q

g

y

x
  -  79    1    0
  -  31    0    1
   2  17    1   -2
   1  14   -1    3
   1    3    2   -5
   4    2  -9  23
   1    1 11 -28


q ist die Anzahl, wie oft e in j(n) passt.
j(n) und e werden immer weiter verkleinert, bis der Rest 1 herauskommt.
In der Vielfachsummendarstellung ist y nun der Faktor vor j(n) und x ist der gesuchte Faktor d, der vor e steht.
Um die dritte Zeile auszurechnen, wäre also folgendes gerechnet worden: Für die


1.Spalte:  79 / 31=2

2.Spalte:  79 mod 31=17

3.Spalte:  1-(2*0)=1

4.Spalte:  0-(2*1)=-2

So kommt man auf die Ergebnisse in der dritten Zeile und so geht es dann mit den nächsten Zeilen weiter.

Die Vielfachsummendarstellung wäre in diesem Fall nun:

11*79-(-28)31=1

Um die Werte aus der Tabelle abzulesen, schreibt man den Endwert aus y hin und geht in der Spalte nach oben, wo dann ganz oben (also an erster Stelle) die 1 steht. Von dort geht man nach links und liest die Zahl ab, die für y der Faktor ist. Genauso macht man es mit dem x.(Dort steht die 1 in der 2. Zeile.)

Man weiß nun wie groß d ist. Es ist: -28.

Da die Bedingung

0<d<79

ist, rechnet man zu d den Wert von j(n) dazu, da man später bei der Ver- und Entschlüsselung nur mit modulo j(n) arbeitet.
Nun hat man endlich seinen geheimen Schlüssel d=51, mit dem man Verschlüsseltenachrichten entschlüsseln kann.

Der unten stehende Quellcode wurde in Delphi 4 verfasst und beschreibt, wie man innerhalb eines Programmes diesen erweiterten Euklitschen Algorithmus und damit d für einen berechnen lässt:


Weitere Themen:

Das RSA-Verfahren

Die Sicherheit des RSA-Verfahrens

Beweis des RSA-Verfahrens

Die Geschichte des RSA-Verfahrens

Prinzip des Quadrierens und Multiplizierens

Der Satz von Euler

Die Eulersche j-Funktion

Das asymmetrische Kryptosystem

Wie kommt man zum Projekt "Das RSA-Verfahren"


zurück zur Informatik-Hauptseite
zurück zur JLS-Startseite