RSA Primzahlen gleich --fehler
-
mrtc15 schrieb:
Werte sind nach J.Buchmann "Einf. i. d. Kryptographie" (3. Aufl. 9.3.1 und 8.5) berechnet. Die "zwei" Primzahlen sollten nur "zufällig" gewählt werden. Geht man dann implizit davon aus, dass diese dann auch versch. sind?
Ja, denn der Test, ob n eine Quadtratzahl ist, und das Wurzelziehen, geschehen instant.
Aber daß es damit nicht klappt, wurdert mich auch. Muß mal nachrechnen...
edit: Zu spät. fdgg hats.
-
Außerdem ist die Verschlüsselung natürlich gleich zu knacken, wenn p1 = p2.
-
Das Verfahren funktioniert mit 2 gleichen Zahlen perfekt. Das Problem ist nur, dass sqrt(n) ein wesentlich einfacheres Problem ist als Primzahlzerlegung (auch in finiten Körpern).
Weiß man allerdings nicht, dass beide Primzahlen gleich sind (was bei zufällig gewählten 200Bit-Zahlen mit Wahrscheinlichkeit ~0 eintritt), dann tut es der Sicherheit des Verfahrens auch keinen Abbruch.
-
otze schrieb:
Weiß man allerdings nicht, dass beide Primzahlen gleich sind (was bei zufällig gewählten 200Bit-Zahlen mit Wahrscheinlichkeit ~0 eintritt), dann tut es der Sicherheit des Verfahrens auch keinen Abbruch.
Naja, doch, schon.
Wenn der Knackversuch eine Faktorisierungsmethode nimmt, die benötigt, daß n quadratfrei ist http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/quadraticgrad.pdf , ist die Quadatzahl schon schlecht. Aber auch sonst wüde ich Quadratzahlen nicht trauen. Allzu möglich, daß manche Verfahren ausgerechnet auf denen zu Schnellfunden http://en.wikipedia.org/wiki/Fermat's_factorization_method führen.
-
otze schrieb:
Das Verfahren funktioniert mit 2 gleichen Zahlen perfekt. ...
Jetzt mal abgesehen von der "Knackbarkeit"...
Warum klappt dann die Entschlüsselung nicht, wenn mit 2 gleichen Zahlen perfekt?
p1 = 19
p2 = 19
n= p1p2 = 361
phi = p1-1p2-1 = 324
e = 29 | 1 < e < phi und gcd(e, phi)=1
d = 257 | 1 < d < phi und d*e ≡ 1 % phi--> ENcrypt
m = 25
c = 25^29 % 361 = 340
--> DEcrypt
c = 340
m = 340^257 % 361 = 272
340 ≠ 25
d und e habe ich doch korrekt bestimmt?
Falls ich mich vertippt habe, sorry! Das gleiche Verfahren mit zwei versch. Primzahlen funzt????
Vlt. sind die Kriterien für e und d bei zwei gleichen Primzahlen anders?Ich danke im voraus!!
-
frei nach fdgg schrieb:
-
Ok, also gibt es bei dem (φ) wohl Tippfehler...
Kapitel 9.3.1 aus dem besagten Buch:
Zusätzlich wählt Bob eine natürliche Zahl e mit
1 < e < φ(n) = (p1-1)*(p2-1) und gcd(e, (p1-1)(p2-1) )
Wenn p1=19 und p2=19, dann sind doch (19-1)(19-1)=(18^2)=324Theorem 3.8.4 Falls p prim, dann φ(p)=p-1 ,
da n=p1*p2 wird substituiert φ(n) = φ(p1)*φ(p2) = (19-1)*(19-1).. ?
-
mrtc15 schrieb:
da n=p1*p2 wird substituiert φ(n) = φ(p1)*φ(p2) = (19-1)*(19-1).. ?
Nein, phi erfüllt nicht phi(a*b) = phi(a)*phi(b) für beliebige Zahlen a und b. Das gilt nur dann, wenn gcd(a,b) = 1 ist.
-
Jo ich danke. Es lag an dem phi, ergo doch nix mit subtituieren.
Summiere nun alle i von 1 bis m --> gcd(i, m) = 1Gracias!
-
mrtc15 schrieb:
Jo ich danke. Es lag an dem phi, ergo doch nix mit subtituieren.
Summiere nun alle i von 1 bis m --> gcd(i, m) = 1
Gracias!//assert(isPrime(p));
//assert(isPrime(q));
if(p==q) phi=p*(p-1);
else phi=(p-1)*(q-1);