Seltsame Ergebnisse beim erw. eukl. Algorithums

[LOM32]

Hallo!

Ich beschäftige mich zusammen mit einem Kumpel mit RSA Verschlüsselung, und soweit haben wir das auch kapiert.
Bei der Berechnung des privaten Schlüssels sind wir aber auf ein Problem gestoßen.
Um "d", also den Entschlüsselungsexponenten auszurechnen, bedient man sich ja des erweiterten Euklidischen Algorithmuses. Eigentlich ist das Ganze auch nicht sonderlich schwer, aber wir kriegen ab und zu für "d" negative Werte raus, mit denen das Verfahren auch nicht funktioniert.

Beispiel:
p=5
q=11
->N=55
-> phi(N)=40
wähle e=3

Dann würde ich d so ausrechnen:

So, mit diesem "d" kappt die ganze Sache aber nicht. Diese kleine Form rechnet auch etwas ganz Anderes aus...
Ich habe schon mit etlichen Mathematik- und Informatik-Lehrern gesprochen - ohne Erfolg, keiner hat eine Idee.

Würde mich freuen, wenn mir jemand helfen kann!

mfg
LOM32

 

[Elderan]

Hallo,

Ich habe schon mit etlichen Mathematik- und Informatik-Lehrern gesprochen - ohne Erfolg, keiner hat eine Idee.

Hmm schon komisch, dass das kein Mathelehrer weiß. Haben die im Studium nicht aufgepasst oder Bastel-Mathematik studiert (Elementar Mathematik).
Naja bei manchen Mathe-Lehrern bezweifelt man wirklich, dass die mal Hochschulmathematik hatten, k.a. ob man noch irgendwie anders (Mathe)-Lehrer werden kann.


Und zwar arbeitest du im sogenannten Restklassenring, und so komisch es sich anhört, dort ist -13 = 27 = 67 = 107 (oder mathematisch korrekter [-13] = [27] = [67] = [107], wobei [x] für die Restklasse steht, den x module 40 lässt, d.h. in [x] sind alle Elemente enthalten, die den selben Rest lassen, wobei x nur ein Representant ist. In [27] sind somit alle Elemente der Form 27 + 40*k, wobei k eine ganzzahlige Zahl ist. Das sind natürlich die selben Elemente, als wenn man -13 + 40*k schreiben würde).

Und zwar arbeitest du im Restklassenring Z/40Z, d.h. du musst alle Zahlen 'modulo 40' rechnen, und -13, 27, 67 und 107 lassen alle den selben Rest bei der Teilung durch 40 und zwar 27 (oder korrekter: 40 teilt 27- (-13), bzw. 40 teilt 107-67 usw.).

Wie bekommt man nun den den Exponenten d:
Entweder Google: -13%40 oder 40-13 rechnen.

 

[LOM32]

Danke für die schnelle Antwort, Elderan!
Ich werde mich jetzt erst mal da durchwurschteln.

Tja, was die Lehrer angeht... sie haben salle irgendwie um den heißen Brei herumgeredet, so "vielleicht ist e schlecht gewählt" oder so. Andere kannten den erweiterten eukl. Algorithmus gar nicht.

Naja was solls, Danke jedenfalls!
mfg
LOM32

 

[jmc]

Wenn du schon ein solch ein schönes Beispiel hast warum schaust du dir denn das nicht einfach an?
Es hat für jede funktion ja einen super für sich selbst sprechenden Titel und das Form wird mit RSA_keys(this.form) gestartet.

 

[Elderan]

Hallo,
@jmc: Ich denk mal ihm ging es mehr ums Verständnism, warum d=27 ist, obwohl man bei euklidischen Algorithmus -13 als 'd' erhält.


Und zwar sucht man ein d, welches:
ed = 1 mod phi

erfüllt, wobei hier = für Kongruenzzeichen steht.

Die Idee ist, man weiß, dass e und phi teilerfremd sind (weil man e so wählen muss), also ggT(e, phi) = 1.

Mit dem eukl. Algo. bekommt man eine Darstellung:
ggt(e, phi) = 1 = r*e + s*phi

Jetzt betrachtet man:
1 mod phi = r*e + s*phi mod phi

Wenn man nun r*e + s*phi mod phi betrachtet, so kann man die einzelnen Summanden betrachten und s*phi mod phi = 0 (logisch, b*phi hat kein Rest bei der Teilung durch phi).
Also muss r*e mod phi = 1 gelten, womit das r hier das gesuchte d wäre.

Da es egal ist, wann man modulo rechnet, gilt auch ( (r mod phi) * (e mod phi) ) mod phi = 1

Somit lässt sich r=-13 auch als r=27 schreiben.



Auf der verlinkten Seite ist aber ein kleiner Fehler:

Dann wird ein zufälliger Wert e ermittelt, der kleiner n und teilerfremd (relativ prim) zu (p-1) * (q-1) ist.

Meistens wird ein festes e verwendet, z.B. e=2^16+1, und es wird solange nach passenden p und q gesucht, bis e teilerfremd zu phi ist.