4. RSA Primzahlen gleich --fehler

RSA Primzahlen gleich --fehler

  • M

    Hallo Forum,

    ich habe eine Frage zu RSA. Ich konnte nirgendwo (in Fachbüchern usw.) gelesen, dass die beiden Primzahlen verschieden sein müssen?

    Mit verschiedenen klappt meine Berechnung!
    Mit gleichen Primzahlen nicht:

    Now encrypt the '25' 25 ^ 409091 % 564001 = 264323
    Now decrypt the '264323' 264323 ^ 11 % 564001 = 179514
    ==> ERROR p1 751 p2 751 --> p1*p2 564001

    Beide Primzahlen p1, p2 = 751.
    e = 11;
    d=409091;
    n=564001;
    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?

    Habe es auch nochmal einfacher nachgerechnet:
    p1, p2 = 19;
    n = 361
    phi = 324
    e = 29
    d = 257
    m = 25 --> Verschlüseeln
    25^257 % 361 = 5
    c= 5 --> Entschlüsseln
    5^29 % 361 = 272
    Es kommt nicht die ursprüngliche 25 heraus, sonder ganz was anderes 272.

    Schön wäre es, wenn jemand auch ne Quelle hat, wo steht dass diese versch. sein müssen.
    Ich bedanke mich schon mal für jeden Hinweis.

    Mfg Mrt 🙂

    0
  • ?

    phi(p^2) = p(p-1)

    0
  • V

    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.

    0
  • ?

    Außerdem ist die Verschlüsselung natürlich gleich zu knacken, wenn p1 = p2.

    0
  • O

    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.

    0
  • V

    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.

    0
  • M

    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-1    p2-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!!

    0
  • V

    frei nach fdgg schrieb:

    http://www.wolframalpha.com/input/?i=phi(361)

    0
  • M

    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)=324

    Theorem 3.8.4 Falls p prim, dann φ(p)=p-1 ,

    da n=p1*p2 wird substituiert φ(n) = φ(p1)*φ(p2) = (19-1)*(19-1).. ?

    0
  • C
    Mod

    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.

    0
  • M

    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!

    0
  • V

    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);

    0
Anmelden zum Antworten