Satz von Euler

Guten Tag,

da ich mich grade ein wenig mit der allseits bekannten RSA-Verschlüsslung beschäftige, bin ich auf die Tatsache gestoßen, dass der Satz von Euler verwendet wird/werden muss. Das einzige was sich mir noch nicht ganz erschließt, ist die Frage nach dem Zweck des anwendens und was genau der Satz von Euler aussagt und warum er für weitere Rechnungen gebraucht wird.

Also sollte sich jemand damit schonmal beschäftigt haben oder auch nur wissen was der "Satz von Euler" aussagt wäre ich euch enorm dankbar.

otze

http://de.wikipedia.org/wiki/Satz_von_Euler

der Kern von RSA ist das sowohl zum ver- als auch entschlüsseln die Potenz der Eingabe genommen wird. Wenn dein RSA-Schlüssel (e,d,n) ist und du den Wert x verschlüsseln willst, gilt:

Verschlüsseln:
z=x^e (mod n)
Entschlüsseln:
x=z^d=(xd)^e=x(d*e) (mod n)

das gilt natürlich nur für besondere d und e. Dafür brauchen wir den Satz von Euler um rauszufinden welche das sind.

Die Aussage vom Satz von Euler ist , dass x^(phi(n))=1 ist. Und damit
x^(phi(n)+1)=x (mod n).

d und e müssen also die Eigenschaft haben, dass ihre Multiplikation zu so einer Zahl zerlegt werden kann:

d*e=t*phi(n)+1

setzt man das ein erhält man:
x^(d*e)=x(t*phi(n)+1)=(x^(phi(n)t)*x (mod n)

Nun Satz von Euler angewendet:
(x^(phi(n)t)*x=(1^t)*x=x (mod n)

Wichtig für den RSA ist, dass man n=p*q wählt, wobei p und q große Primzahlen sind. Denn dann lässt sich phi(n) einfach berechnen: phi(n)=phi(p*q)=(p-1)*(q-1).
Kennt der Angreifer p und q nicht, hat er ein Problem. dann muss er nämlich n faktorisieren, was irrsinnig lange dauert.

e kannst du dann fast beliebig wählen, außer dass e Teilerfremd zu phi(n) sein muss. d muss nun so gewählt werden dass: e*d = 1 mod phi(n).

Sollte dir irgendwas unklar sein, zum Beispiel wie Ganzzahlmultiplikationen von Werten >1 wieder 1 ergeben können, dann musst du dich erstmal durch ne Menge Algebra wühlen

OK,

also mir ging es jetzt nur um den Satz von Euler.. Den Rest habe ich soweit verstanden. Also sagt Euler im groben aus, dass d und e das richtige "Verhältniss" zueinander haben um genutzt zu werden?

SeppJ

devman33 schrieb:

OK,

also mir ging es jetzt nur um den Satz von Euler.. Den Rest habe ich soweit verstanden. Also sagt Euler im groben aus, dass d und e das richtige "Verhältniss" zueinander haben um genutzt zu werden?

Der Satz von Euler sagt, dass das Verfahren überhaupt funktioniert, denn aus Euler folgt
x=(x^d)e (mod n) = x^(d*e) (mod n)
dann wenn
d*e=t*phi(n)+1

Der Satz macht also eine Aussage darüber, welche Voraussetzungen an die Zahlen d und e gestellt werden müssen, damit es überhaupt möglich ist, eine Zahl durch Potenzieren mit d zu verschlüsseln und hinterher durch Potenzieren mit e wieder das Original zu erhalten.

otze

devman33 schrieb:

also mir ging es jetzt nur um den Satz von Euler.. Den Rest habe ich soweit verstanden. Also sagt Euler im groben aus, dass d und e das richtige "Verhältniss" zueinander haben um genutzt zu werden?

Jein. Das ist die Anwendung des Satzes.

Der Satz von Euler trifft eigentlich erstmal nur eine Aussage über Potenzen in endlichen Gruppen:

Wenn wir eine endliche multiplikative Gruppe G haben, dann gilt für alle x aus G: x^|G|=1.

Mehr sagt der Satz nicht aus. RSA verwendet ihn dann nur sehr trickreich.