Folgerungen aus Euler und Fermat - RSA Verfahren

Neue Frage »

matheburg Auf diesen Beitrag antworten »
Folgerungen aus Euler und Fermat - RSA Verfahren
Meine Frage:
Hallo,

ich habe für das RSA-Verfahren einige Folgerungen aus Euler und Fermat geschlossen. Es wäre schön, wenn jemanden eine evtl. falsche Schlussfolgerung auffallen würde.
Danke!

Meine Ideen:
Der kleine Satz von Fermat:
Für eine Primzahl p und alle zu p teilerfremden ganzen Zahlen a gilt:
a^p-1 mod p = 1
Folgerungen aus dem kleinen Satz von Fermat:
1. Für eine Primzahl p und alle zu p teilerfremden ganzen Zahlen a gilt: a^p mod p = a
2. Für eine Primzahl p und einem a<p mit der Zykluslänge L in Zp gilt:
a^(L+1) mod p = a
Seien Li die Zyklenlängen aller ai <p in Zp und L = kgv (aller ai) dann gilt:
a^(L+1) mod p = a für alle a < p.
Hierausfolgt die Korrektheit der Verschlüsselung durch Potenzierung und einem Primzahlmodul p.
3. Für eine Primzahl p und alle zu p teilerfremden ganzen Zahlen a gilt:
a^phi(p) mod p = 1


Der Satz von Euler:
Für teilerfremde Zahlen m und n gilt:
m^phi(n) mod n = 1.
Folgerungen aus dem Satz von Euler:
1. Für teilerfremde Zahlen m und n gilt:
m^(phi(n)+1) mod n = m.
2. Für zwei Primzahlen p und q und m<pq gilt für jedes k:
m^(k(p-1(q-1)+1) mod pq = m.
3. Für zwei Primzahlen p und q und m<pq gilt für jedes k:
m^(k*kgv(p-1,q-1))+1 mod pq = m.
Hieraus folgt die Korrektheit von RSA
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

1. gilt sogar für alle Zahlen; das ist sehr oft die Formulierung des kleinen Fermat?
2. Was ist eine Zykluslänge? Schaut nach multiplikativer Ordnung aus.
3. Ist phi die Eulersche-phi-Funktion? Dann gilt dass natürlich da für eine Primzahl p.

1. Ja.
2 Das ist richtig, folgt aber nicht direkt aus dem oberen, dafür brauchts noch den chin. Restsatz.
3. Ja.

Zitat:
Hieraus folgt die Korrektheit von RSA

Ja. Und welche Quelle für den Algorithmus hattest du denn, der ja anscheinend mal sinnvollerweise die Carmichaelfunktion stat der Euler-Funktion verwendet?
matheburg Auf diesen Beitrag antworten »

Hi, danke für die Antwort!
Ich habe als Quelle vor allem selbst angefertigte Tabellen.

Aber wenn wir schon bei RSA sind. Grundsätzlich lässt sich ja auch mit einem Primzahlmodul verschlüsseln. Ärgerlicherweise gilt hier phi(p) = p-1 und dadurch kann dann direkt aus einem e das d berechnet werden. Dieses Verfahren ist dann wohl nicht als asymmetrisches Verfahren zu verwenden(wohl aber als (langsames) symmetrisches Verfahren).

Meine Frage wäre nun, welche Moduln n sind überhaupt möglich? Beispiel: n = 20 wäre nicht möglich, da dann z.B. der Klartext m= 6 nicht mehr zu entschlüsseln wäre.

Ist es richtig, dass grundsätzlich nur Primzahlen und alle Zahlen die aus einem Produkt von verschiedenen Primzahlen (gibt es dafür einen Fachausdruck?) bestehen möglich sind?
Das würde auch erklären warum RSA zwei Primzahlen multipliziert und nicht addiert (denn z.B. 7+13 = 20), obwohl eine Zerlegung einer großen Zahl als Summe zweier Primzahlen sicher genauso schwer wie die Faktorisierung ist.
Captain Kirk Auf diesen Beitrag antworten »

Ich kann dir nicht folgen.

Zitat:
Grundsätzlich lässt sich ja auch mit einem Primzahlmodul verschlüsseln.

Und wie?

Zitat:
Ist es richtig, dass grundsätzlich nur Primzahlen und alle Zahlen die aus einem Produkt von verschiedenen Primzahlen (gibt es dafür einen Fachausdruck?) bestehen möglich sind?

Wofür?
matheburg Auf diesen Beitrag antworten »

Nochmal...
ich habe im Anhang ein Bild von der Tabelle angehängt. Mit Zyklus meine ich die roten Werte L.

Um einen Klartext x zu entschlüsseln müsste das d jeweils mit der Info über die entsprechende Zykluslänge L bestimmt werden.
Beispiel: x=9 -> L=2 und d wäre dann e * d mod L = 1.
Das wäre natürlich zu aufwendig also verwendet man das kgv(aller L). In diesem Beispiel also 4.
Das ist doch von der Überlegung korrekt oder?
Ist die multiplikative Ordnung mit meiner sogenannten Zykluslänge identisch?
matheburg Auf diesen Beitrag antworten »

Sorry jetzt hatte ich schon ein neues Fass aufgemacht.

Mit einem Primzahlmodul lässt sich wie folgt verschlüsseln:

c = m^e mod p. Genau wie im RSA-Verfahren auch. Nur wenn ich das e und p veröffentliche, kann man problemlos daraus das d zum entschlüsseln berechnen. Weil in diesem Fall meine sogenannte Zykluslänge L = p-1 ist. Und mit dem Wissen ließe sich ja mit e*d mod L = 1 direkt das d berechnen.

Wenn ich aber das e und p nicht veröffentliche, wäre es für hinreichende große Werte natürlich sicher, aber dann halt kein asymmetrisches, sondern nur ein symmetrisches Verfahren mit dem Schlüssel (e,d,p).


Wofür andere Werte für n verwenden?
Man könnte doch genauso als Modul das Produkt aus drei verschiedenen Primzahlen verwenden. Das würde auch gehen und wäre wohl sicherer als RSA - bringt aber nichts, da es 1. komplizierter würde und 2. RSA bei richtiger Anwendung schon sicher genug ist.

Dennoch ist es doch eine interessante theoretische Frage, ob man als Schlüssel denn nicht auch die Summe von zwei Primzahlen, also n=p+q verwenden kann.
Und m.E. ist die Antwort: Nein das geht nicht, weil dann nicht immer jeder Klartext wieder entschlüsselt werden kann(z.B. für das Modul n = 7+13 = 20).
 
 
Captain Kirk Auf diesen Beitrag antworten »

Der Schlüssel d wird unabhängig vom Klar- oder Geheimtext berechnet.
d hängt nur von n und e ab.

Zitat:
Ist die multiplikative Ordnung mit meiner sogenannten Zykluslänge identisch?

Nur zu n teilerfremde Zahlen haben eine multiplikative Ordnung. Dann sind die beiden Begriffe wohl identisch.

Zitat:
Das wäre natürlich zu aufwendig also verwendet man das kgv(aller L).

Wer ist dieser man hier?
Captain Kirk Auf diesen Beitrag antworten »

Zu deinem zweiten Post:

Zitat:
c = m^e mod p. Genau wie im RSA-Verfahren auch. Nur wenn ich das e und p veröffentliche, kann man problemlos daraus das d zum entschlüsseln berechnen. Weil in diesem Fall meine sogenannte Zykluslänge L = p-1 ist. Und mit dem Wissen ließe sich ja mit e*d mod L = 1 direkt das d berechnen. Wenn ich aber das e und p nicht veröffentliche, wäre es für hinreichende große Werte natürlich sicher, aber dann halt kein asymmetrisches, sondern nur ein symmetrisches Verfahren mit dem Schlüssel (e,d,p).

Wenn du e und p nicht veröffentlichst wie soll man damit arbeiten?

Zitat:
Man könnte doch genauso als Modul das Produkt aus drei verschiedenen Primzahlen verwenden. Das würde auch gehen und wäre wohl sicherer als RSA - bringt aber nichts, da es 1. komplizierter würde und 2. RSA bei richtiger Anwendung schon sicher genug ist.

Das ist falsch. Die Sicherheit von RSA hängt an der Schwierigkeit N zu faktoriseren.
Die Schwierigkeit des Faktorisierens einer Zahl hängt im wesentlichen nur von der Größe des kleinsten Primteilers ab. Daher wären drei Primfaktoren kontraproduktiv.
Mathematisch komplizierter würde es dagegen nicht. Wenn die Primfaktorzerlegung einer Zahl n bekannt ist ist die Berechnung von schnell erledigt.
2. Darüber liese sich streiten. Die Sicherheit hängt wesentlich von der Größe der verwendeten Primzahlen ab. Die Frage ist auch nach Sicherheit bzgl, verwendeter Rechenleistung. (Daher verwendet man i.d.R RSA nur zur Schlüsselgenerierung für symmetrische Verfahren mit denen man dann die wirkliche Information verschlüsselt oder zur Authentifizierung)
matheburg Auf diesen Beitrag antworten »

Der Schlüssel d wird aber nur unabhängig vom Klartext berechnet, weil man das kgv aller rot eingetragener Werte L der Tabelle verwendet.
Es ist in der Tabelle doch zu erkennen, dass z.B. x=9 den Zyklus 9,6,9,6,9,6,... hat. Also eine Zykluslänge von 2. Um für x=9 und z.B. e=3 das d zu berechnen müsste man e*d mod 2 = 1 berechnen. Also ist z.B. d=1 ein gültiger Schlüssel für x=9.
Praktikabel wäre das natürlich nicht, also nimmt man das kgv(aller L), denn das gilt dann für jeden Klartext m.
Wer man ist? carmichael! Das ist doch gerade die Idee von Carmichael.
matheburg Auf diesen Beitrag antworten »

"Die Sicherheit des Faktorisierens einer Zahl hängt im wesentlichen nur von der Größe des kleinsten Primteilers ab. Daher wären drei Primfaktoren kontraproduktiv.

Da muss ich Widersprechen. Wenn n = P*q*r für drei große Primzahlen, dann wäre n eben noch lange nicht faktorisiert, nur weil ich einen der Faktoren kenne.
Ist doch auch klar, denn:
Angenommen n ist eine riesige Zahl mit n=p*q die noch nicht faktorisiert wäre. Dann müsste ich nach der Argumentation oben ja nur n mit einer kleinen Primzahl r multiplizieren und schon wäre das ganze n unsicher. Nur durch die Kenntnis von r könnte man nicht auf p und q schließen.

Insgesamt würde RSA damit schon langsamer werden und das ist ja auch das größte Problem an dem Verfahren.
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Wer man ist? carmichael! Das ist doch gerade die Idee von Carmichael.
Sicher nicht. Wie kommst du drau?. Weil ich vorher Carmichael-Funktion geschrieben hab? Auch mit der Carmichael-Funktion kann man das d unabhängig vom Klartext berechnen.
Mal ganz abgesehen davon, dassein Schlüssel d=1 ziemlich bescheurt wäre.

Und wenn du dein d abhängig vom kKartext berechnest ist es kein RSA mehr, dann ist es was anderes.

Zitat:
Da muss ich Widersprechen. Wenn n = P*q*r für drei große Primzahlen, dann wäre n eben noch lange nicht faktorisiert, nur weil ich einen der Faktoren kenne.

Das habe ich nicht behauptet.
Ich sprach auch nicht von vollstandigem Faktorisieren, nur von Faktoriserien.

Zitat:
Insgesamt würde RSA damit schon langsamer werden und das ist ja auch das größte Problem an dem Verfahren.

Das hinzumultplizieren bringt keinerlei zusätzlichen Sicherheitsgewinn aber hohe Kosten an Rechenleistung.
matheburg Auf diesen Beitrag antworten »

Zitat:
Original von Captain Kirk
[QUOTE]Wer man ist? carmichael! Das ist doch gerade die Idee von Carmichael.
Sicher nicht. Wie kommst du drau?. Weil ich vorher Carmichael-Funktion geschrieben hab? Auch mit der Carmichael-Funktion kann man das d unabhängig vom Klartext berechnen.
Mal ganz abgesehen davon, dassein Schlüssel d=1 ziemlich bescheurt wäre.

Die kleinen Werte kommen ja dadurch zustande, dass das n so klein gewählt wurde. Mit der Carmichael Funktion kann das d unabhängig vom Klartext berechnet werden. Das ist richtig. Genauso kann das d mit Euler unabhängig vom Klartext berechnet werden. Das ist alles richtig.
Nur warum wird denn das kgv(p-1,q-1) berechnet. Das ist doch eine spannende Frage! Und das hängt doch eben mit den unterschiedlichen Zyklenlängen zusammen, die ich in der Tabelle rot eingetragen habe. Es gilt: kgv(meine roten Zyklenlängen) = kgv(p-1,q-1).
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »