Die RSA Verschlüsselungsformel lautet ja m^e(Mod (p-1)*(q-1))
Meine Frage:
Muss m^e größer sein als (p-1)*(q-1)?
Sorry, ich kann hier nicht weiterhelfen, da ich in diesem Bereich bislang nur mit vorgefertigten Programmen (Steganos) arbeite.
kann ich nicht beantworten, sorry
fg Longwolf
tut mir leid, keine Ahnung
Hallo,
da bin ich glatt überfordert.
Wenn du mir ne e-Mail-Adresse nennst oder weißt, wie man hier Dateien anhängt, kann ich dir aber eine Seite aus „Kryptografie“ von Klaus Schmeh zusenden, die deine Frage vielleicht indirekt beantwortet.
Gruß
Georg Korger
Nein, die Formel lautet
(m^e) mod ((p-1)*(q-1))
und m muß kleiner sein als N = (p-1)*(q-1)
Muss leider passen, bin nur Interessierter.
Kein Ahnung, mit den mathematischen Grundlagen der Verschlüsselung kenne ich mich nicht sonderlich aus - mich interessiert eher die Praxis.
Gruß m.
Hallo Hans,
Vereinfacht entspricht das der Frage:
muß a > b sein bei a mod b?
(hier hat man a=m^e und b=(p-1)*(q-1))
Natürlich nicht.
Eine Bedingung existiert allerdings:
e und (p-1)*(q-1) müssen „relatively prime“ sein, d.h. ihr größter gemeinsamer Teiler muß 1 sein.
Das trifft z.B. bei den Zahlen 15 und 28 zu, bei 15 und 27 nicht.
Für maximale Sicherheit sollten p und q möglichst gleiche Länge haben.
Ein sehr empfehlenswertes Buch über Cryptography (Einführung)ist:
„Applied Cryptography“, Bruce Schneier, Wiley Verlag.
Es lohnt sich auf jeden Fall, sich es mal zumindest anzuschauen.
Ich hoffe, ich konnte helfen.
Gruß
Zusatz:
In der Regel ist es zwar so, daß m^e > (p-1)*(q-1) ist, aber man muß bedenken, daß z.B. 15 mod 4 äquivalent zu
3 mod 4 ist.
Es würde also auch nichts helfen, sowas zu verlangen…
Hallo Hans
Hier ein Ausschnitt aus meinen Schulungsunterlagen:
4.5 RSA
Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröf-fentlicht hatten, versuchten die drei Mathematiker Rivest, Shamir und Adleman die Annah-men von Diffie und Hellmann zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stiessen sie schliesslich auf eines, wo sie keinerlei Angriffs-punkte fanden. Hieraus entstand dann RSA. Das Verfahren wurde 1977 entwickelt und ba-siert auf der Idee, dass die Faktorisierung einer grossen Zahl, also ihre Zerlegung in (mindes-tens zwei) Faktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen trivial ist. Wenn nun eine Nachricht einem Emp-fänger verschlüsselt zugeleitet werden soll, generiert dieser einen öffentlichen Schlüssel. Der Nachrichtenabsender verwendet diesen öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese „dekodieren“, da nur er die „Zusammensetzung“, den „Werdegang“ des von ihm erzeugten (öffentlichen) Schlüssels kennt.
Die Sicherheit basiert auf der exponentiellen Funktion y = f(x) = x^e mod n , die mit angemessener Aufwand berechnet werden kann. Die inverse Funktion x = f^-1(y) ist jedoch extrem aufwändig zu berechnen.
4.5.1 Schlüssel generieren
-
Schritt: Auswahl von zwei grossen Primzahlen p und q.
Um die maximale Sicherheit zu bekommen, sollten p und q ungefähr gleich lange sein, z.B. 1024 Bit -
Schritt: Das Produkt berechen n = p * q
-
Schritt: Bestimmen einer zufälligen Integer-Zahl
e
Abschliessend kann ich die Frage nicht beantworten.
Geschätzter Hans
Abschliessend kann ich die Frage nicht beantworten.
Viele Grüsse
Ka
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hallo Hans Bauer,
am 26.06.2013 schrieben Sie als [email protected] u.a. mir mit dem
gleichen Betreff:
…
HB> Die RSA Verschlüsselungsformel lautet ja m^e(Mod (p-1)*(q-1))
HB> Meine Frage:
HB> Muss m^e größer sein als (p-1)*(q-1)?
…
Vorab, ich kann RSA nicht beweisen. (Ob ich dazu einmal komme, weiß ich
nicht.)
m^e wird ja nie berechnet. Insofern ist Ihre Frage theoretisch.
Vielen Dank für Ihre Frage. Sie hat mich veranlasst meine pgp-Theorie-Seite
http://mavoe.de/PGPtheorie.htm
kurz wieder anzusehen. Dort lautet die RSA-Formel etwas anders als bei
Ihnen:
V(k) = k ** e mod n
mit n = p * q
(die Berechnung von e ist etwas komplizierter)
In meinem Punkt „2.1.3.6 Beispiel, 2. Teil“ ist
k = 21075
e = 50253
und
n = 67519
k sollte auch 0 oder 1 sein können. Dann müsste Ihre Frage mit Nein
beantwortet werden.
Mein ganzes Beispiel habe ich aber jetzt nicht noch einmal
nachvollzogen, um Ihnen zu antworten.
Mit Wer-weiss-was-freudigen Grüßen
mavoe
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (MingW32)
iEYEARECAAYFAlHOlGMACgkQY9UWFseCBCgYlACfc/z8ik7TUNVlKa3D3Ri+EEDA
RRoAnjdqX/ziHnwr+ZijQiGe94Oo2rFv
=eocZ
-----END PGP SIGNATURE-----