Berechne die Primzahlen p und q aus dem privaten Exponenten (d), dem öffentlichen Exponenten (e) und dem Modul (n)

Question

Wie berechne ich die Parameter p und q aus e (publickey), d (privater Schlüssel) und Modul?

Ich habe BigInteger Schlüssel zur Hand Ich kann Paste in Code kopieren. Ein öffentlicher Schlüssel, ein privater Schlüssel und ein Modul.

Ich muss die RSA-Parameter p und q daraus berechnen. Aber ich vermute, dass es eine Bibliothek für das gibt, die ich mit Google nicht finden konnte. Irgendwelche Ideen? Vielen Dank.

Dies muss nicht rohe Gewalt sein, da ich nicht nach dem privaten Schlüssel bin. Ich habe gerade ein Altsystem, das ein öffentliches, privates Schlüsselpaar und ein Modul speichert, und ich muss sie in C# holen, um mit RSACryptoServiceProvider zu verwenden.

---

So kommt es auf die Berechnung (p + q) durch

public BigInteger _pPlusq() 
    { 
     int k = (this.getExponent() * this.getD()/this.getModulus()).IntValue(); 

     BigInteger phiN = (this.getExponent() * this.getD() - 1)/k; 

     return phiN - this.getModulus() - 1; 

    } 

aber das scheint nicht zu funktionieren. Können Sie das Problem erkennen? später

---

5 Stunden ... :)

Ok. Wie kann ich eine Zufallszahl aus Zn * (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) in C# auswählen?

Answer 1

Nehmen wir an, und ist klein (das ist der übliche Fall; der traditionelle öffentliche Exponent ist 65537). Nehmen wir auch an, dass ed = 1 mod phi (n), wobei phi (n) = (p-1) (q-1) (dies ist nicht notwendigerweise der Fall, die RSA-Anforderungen sind, dass ed = 1 modLCM (P-1, q-1) undphi (n) ist nur ein Vielfaches von LCM (P-1, q-1)).

Jetzt haben Sie ed = k * phi (n) +1 für eine ganze Zahl k. Da d ist kleiner als phi (n), Sie wissen, dass k < e. Sie haben also nur eine kleine Anzahl von k zu versuchen. Eigentlich phi (n) liegt nahe n (die Differenz in der Größenordnung von sqrt wobei (n), mit anderen Worten, wenn schrieb in Bits, die obere Hälfte der phi (n) ist identisch mit dem von n) so können Sie k ' mit berechnen: k' = rund (ed/n). k‘ ist sehr nahe an k (d.h. | k'-k | < = 1), solange die Größe der e ist nicht mehr als die Hälfte der Größe von n.

Bei k Sie leicht phi (n) erhalten = (ed-1)/k.Nun ist es so, dass:

phi (n) = (p-1) (q-1) = pq - (p + q) + 1 = n + 1 - (p + q)

So erhalten Sie p + q = n + 1 - phi (n). Sie haben auch pq. Es ist Zeit, sich daran zu erinnern, dass für alle reellen Zahlen ein und b, ein und b sind die beiden Lösungen der quadratischen Gleichung X - (a + b) X + ab. So, da p + q und pq, p und q werden durch Lösen der quadratischen Gleichung erhalten:

p = ((p + q) + sqrt ((p + q) -4 * pq))/2

q = ((p + q) - sqrt ((p + q) -4 * pq))/2

Im Gattungen l Fall e und d können beliebige Größen aufweisen (möglicherweise mehr als n), weil alles, was RSA muss, ist, dass ed = 1 mod (p-1) und ed = 1 mod (q-1). Es gibt eine generische (und schnelle) Methode, die ein bisschen wie der Miller-Rabin-Primalitätstest aussieht. Es ist in der Handbook of Applied Cryptography (Kapitel 8, Abschnitt 8.2.2, Seite 287) beschrieben. Diese Methode ist konzeptuell etwas komplexer (sie beinhaltet eine modulare Exponentiation), ist aber möglicherweise einfacher zu implementieren (weil es keine Quadratwurzel gibt).

Answer 2

Es gibt ein Verfahren p und q von n, e und d in NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Key Establishment Schemes Using Integer Factorization Cryptography im Anhang C beschrieben zu erholen

Die Schritte beteiligt sind:

1. Lassen Sie k = de - 1. Wenn k ungerade ist, dann gehe zu Schritt 4.
2. Write k als k = 2 ^t r, wobei r der größte ungerade ganze Zahl ist Dividieren k und t ≥ 1. Oder teilen Sie einfach k wiederholt um 2, bis Sie eine ungerade Zahl erreichen.
3. Für i = 1- tun:
   1. Generieren einer zufälligen ganzen Zahl g im Bereich [0, N-1].
   2. y = g r mod n
   3. Wenn y y = 1 oderLet = n - 1, dann 3.1 zu Schritt gehen (d.h. diese Schleife wiederholen).
   4. Für j = 1 bis t - 1 tun:
      1. Let x = y mod n
      2. Wenn x = 1, gehe zu (äußeren) Schritt 5.
      3. Wenn x = n - 1, mit Schritt 3.1 fortfahren.
      4. Lassen Sie y = x.
   5. Let x = y 2 mod n
   6. Wenn x = 1, gehe zu (äußere) Schritt 5.
   Weiter
4. Output „Primfaktoren nicht gefunden "und aufhören.
5. Let p = GCD (y - 1, n) undq = n/p
6. Output (p, q) als die Primfaktoren lassen.

Ich schrieb vor kurzem eine Implementierung in Java. Nicht direkt nützlich für C# Mir ist klar, aber vielleicht kann es leicht portiert werden:

// Step 1: Let k = de – 1. If k is odd, then go to Step 4 
BigInteger k = d.multiply(e).subtract(ONE); 
if (isEven(k)) { 

    // Step 2 (express k as (2^t)r, where r is the largest odd integer 
    // dividing k and t >= 1) 
    BigInteger r = k; 
    BigInteger t = ZERO; 

    do { 
     r = r.divide(TWO); 
     t = t.add(ONE); 
    } while (isEven(r)); 

    // Step 3 
    Random random = new Random(); 
    boolean success = false; 
    BigInteger y = null; 

    step3loop: for (int i = 1; i <= 100; i++) { 

     // 3a 
     BigInteger g = getRandomBi(n, random); 

     // 3b 
     y = g.modPow(r, n); 

     // 3c 
     if (y.equals(ONE) || y.equals(n.subtract(ONE))) { 
      // 3g 
      continue step3loop; 
     } 

     // 3d 
     for (BigInteger j = ONE; j.compareTo(t) <= 0; j = j.add(ONE)) { 
      // 3d1 
      BigInteger x = y.modPow(TWO, n); 

      // 3d2 
      if (x.equals(ONE)) { 
       success = true; 
       break step3loop; 
      } 

      // 3d3 
      if (x.equals(n.subtract(ONE))) { 
       // 3g 
       continue step3loop; 
      } 

      // 3d4 
      y = x; 
     } 

     // 3e 
     BigInteger x = y.modPow(TWO, n); 
     if (x.equals(ONE)) { 

      success = true; 
      break step3loop; 

     } 

     // 3g 
     // (loop again) 
    } 

    if (success) { 
     // Step 5 
     p = y.subtract(ONE).gcd(n); 
     q = n.divide(p); 
     return; 
    } 
} 

// Step 4 
throw new RuntimeException("Prime factors not found"); 

Dieser Code verwendet ein paar Helfer Definitionen/Methoden:

private static final BigInteger ONE = BigInteger.ONE; 
private static final BigInteger TWO = BigInteger.valueOf(2); 
private static final BigInteger ZERO = BigInteger.ZERO; 

private static boolean isEven(BigInteger bi) { 
    return bi.mod(TWO).equals(ZERO); 
} 

private static BigInteger getRandomBi(BigInteger n, Random rnd) { 
    // From http://stackoverflow.com/a/2290089 
    BigInteger r; 
    do { 
     r = new BigInteger(n.bitLength(), rnd); 
    } while (r.compareTo(n) >= 0); 
    return r; 
} 

Answer 3

ich die method umgesetzt von Thomas Pornin beschrieben.

Die BigInteger Klasse ist Keong TAN C# Version Chew (Codeproject Kommentare für Fehlerbehebungen überprüfen)

/// EXAMPLE (Hex Strings) 
    /// N(MODULUS) = "DB2CB41E112BACFA2BD7C3D3D7967E84FB9434FC261F9D090A8983947DAF8488D3DF8FBDCC1F92493585E134A1B42DE519F463244D7ED384E26D516CC7A4FF7895B1992140043AACADFC12E856B202346AF8226B1A882137DC3C5A57F0D2815C1FCD4BB46FA9157FDFFD79EC3A10A824CCC1EB3CE0B6B4396AE236590016BA69" 
    /// D(PRIVATE EXPONENT) = "18B44A3D155C61EBF4E3261C8BB157E36F63FE30E9AF28892B59E2ADEB18CC8C8BAD284B9165819CA4DEC94AA06B69BCE81706D1C1B668EB128695E5F7FEDE18A908A3011A646A481D3EA71D8A387D474609BD57A882B182E047DE80E04B4221416BD39DFA1FAC0300641962ADB109E28CAF50061B68C9CABD9B00313C0F46ED" 
    /// E(PUBLIC EXPONENT) = "010001" 
    /// RESULTS: 
    /// DP = "899324E9A8B70CA05612D8BAE70844BBF239D43E2E9CCADFA11EBD43D0603FE70A63963FE3FFA38550B5FEB3DA870D2677927B91542D148FA4BEA6DCD6B2FF57" 
    /// DQ = "E43C98265BF97066FC078FD464BFAC089628765A0CE18904F8C15318A6850174F1A4596D3E8663440115D0EEB9157481E40DCA5EE569B1F7F4EE30AC0439C637" 
    /// INVERSEQ = "395B8CF3240C325B0F5F86A05ABCF0006695FAB9235589A56759ECBF2CD3D3DFDE0D6F16F0BE5C70CEF22348D2D09FA093C01D909D25BC1DB11DF8A4F0CE552" 
    /// P = "ED6CF6699EAC99667E0AFAEF8416F902C00B42D6FFA2C3C18C7BE4CF36013A91F6CF23047529047660DE14A77D13B74FF31DF900541ED37A8EF89340C623759B" 
    /// Q = "EC52382046AA660794CC1A907F8031FDE1A554CDE17E8AA216AEDC92DB2E58B0529C76BD0498E00BAA792058B2766C40FD7A9CC2F6782942D91471905561324B" 

    public static RSACryptoServiceProvider CreateRSAPrivateKey(string mod, string privExponent, string pubExponent) 
    { 
     var rsa = new RSACryptoServiceProvider 
     { 
      PersistKeyInCsp = false 
     }; 
     var n = new BigInteger(mod, 16); 
     var d = new BigInteger(privExponent, 16); 
     var e = new BigInteger(pubExponent, 16); 

     var zero = new BigInteger(0); 
     var one = new BigInteger(1); 
     var two = new BigInteger(2); 
     var four = new BigInteger(4); 


     BigInteger de = e*d; 
     BigInteger modulusplus1 = n + one; 
     BigInteger deminus1 = de - one; 
     BigInteger p = zero; 
     BigInteger q = zero; 

     BigInteger kprima = de/n; 

     var ks = new[] {kprima, kprima - one, kprima + one}; 

     bool bfound = false; 
     foreach (BigInteger k in ks) 
     { 
      BigInteger fi = deminus1/k; 
      BigInteger pplusq = modulusplus1 - fi; 
      BigInteger delta = pplusq*pplusq - n*four; 

      BigInteger sqrt = delta.sqrt(); 
      p = (pplusq + sqrt)/two; 
      if (n%p != zero) continue; 
      q = (pplusq - sqrt)/two; 
      bfound = true; 
      break; 
     } 

     if (bfound) 
     { 
      BigInteger dp = d%(p - one); 
      BigInteger dq = d%(q - one); 

      BigInteger inverseq = q.modInverse(p); 

      var pars = new RSAParameters 
      { 
       D = d.getBytes(), 
       DP = dp.getBytes(), 
       DQ = dq.getBytes(), 
       Exponent = e.getBytes(), 
       Modulus = n.getBytes(), 
       P = p.getBytes(), 
       Q = q.getBytes(), 
       InverseQ = inverseq.getBytes() 
      }; 
      rsa.ImportParameters(pars); 
      return rsa; 
     } 

     throw new CryptographicException("Error generating the private key"); 
    } 

Answer 4

ich die Java code provided by Duncan in C# angepasst haben, wenn jemand interessiert:

public static void RecoverPQ(
     BigInteger n, 
     BigInteger e, 
     BigInteger d, 
     out BigInteger p, 
     out BigInteger q 
     ) 
    { 
     int nBitCount = (int)(BigInteger.Log(n, 2)+1); 

     // Step 1: Let k = de – 1. If k is odd, then go to Step 4 
     BigInteger k = d * e - 1; 
     if (k.IsEven) 
     { 
      // Step 2 (express k as (2^t)r, where r is the largest odd integer 
      // dividing k and t >= 1) 
      BigInteger r = k; 
      BigInteger t = 0; 

      do 
      { 
       r = r/2; 
       t = t + 1; 
      } while (r.IsEven); 

      // Step 3 
      var rng = new RNGCryptoServiceProvider(); 
      bool success = false; 
      BigInteger y = 0; 

      for (int i = 1; i <= 100; i++) { 

       // 3a 
       BigInteger g; 
       do 
       { 
        byte[] randomBytes = new byte[nBitCount/8 + 1]; // +1 to force a positive number 
        rng.GetBytes(randomBytes); 
        randomBytes[randomBytes.Length - 1] = 0; 
        g = new BigInteger(randomBytes); 
       } while (g >= n); 

       // 3b 
       y = BigInteger.ModPow(g, r, n); 

       // 3c 
       if (y == 1 || y == n-1) { 
        // 3g 
        continue; 
       } 

       // 3d 
       BigInteger x; 
       for (BigInteger j = 1; j < t; j = j + 1) { 
        // 3d1 
        x = BigInteger.ModPow(y, 2, n); 

        // 3d2 
        if (x == 1) { 
         success = true; 
         break; 
        } 

        // 3d3 
        if (x == n-1) { 
         // 3g 
         continue; 
        } 

        // 3d4 
        y = x; 
       } 

       // 3e 
       x = BigInteger.ModPow(y, 2, n); 
       if (x == 1) { 

        success = true; 
        break; 

       } 

       // 3g 
       // (loop again) 
      } 

      if (success) { 
       // Step 5 
       p = BigInteger.GreatestCommonDivisor((y - 1), n); 
       q = n/p; 
       return; 
      } 
     } 
     throw new Exception("Cannot compute P and Q"); 
    } 

Diese verwendet die standardmäßige System.Numerics.BigInteger-Klasse.

Dies wurde durch den folgenden Unit-Test getestet:

BigInteger n = BigInteger.Parse("9086945041514605868879747720094842530294507677354717409873592895614408619688608144774037743497197616416703125668941380866493349088794356554895149433555027"); 
BigInteger e = 65537; 
BigInteger d = BigInteger.Parse("8936505818327042395303988587447591295947962354408444794561435666999402846577625762582824202269399672579058991442587406384754958587400493169361356902030209"); 
BigInteger p; 
BigInteger q; 
RecoverPQ(n, e, d, out p, out q); 
Assert.AreEqual(n, p * q);