Calcola i numeri primi eq dall'esponente privato (d), dall'esponente pubblico (e) e dal modulo (n)

Question

Come si calcolano i parametri peq da e (chiave pubblica), d (chiave privata) e modulo?

Ho i tasti BigInteger a portata di mano riesco a copiare incolla nel codice. Un publickey, un privatekey e un modulo.

Ho bisogno di calcolare i parametri RSA p e q da questo. Ma sospetto che ci sia una biblioteca per quello che non sono riuscito a trovare su google. Qualche idea? Grazie.

Questo non deve essere forza bruta, dal momento che io non sono dopo la chiave privata. Ho solo un sistema legacy che memorizza una coppia di chiavi pubblica, privata e un modulo e ho bisogno di farli in C# da utilizzare con RSACryptoServiceProvider.

---

Quindi si tratta di calcolare (p + q) da

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; 

    } 

, ma questo non sembra funzionare. Riesci a individuare il problema?

---

5 ore più tardi ... :)

Ok. Come posso selezionare un numero casuale di Zn * (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) in C#?

Answer 1

Supponiamo che e sia piccolo (questo è il caso comune, l'esponente pubblico tradizionale è 65537). Supponiamo anche che ed = 1 mod phi (n), dove phi (n) = (p-1) (q-1) (questo non è necessariamente il caso, i requisiti RSA sono che ed = 1 mod lcm (p-1, q-1) ephi (n) è soltanto un multiplo di lcm (p-1, q-1)).

Ora avete ed = k * phi (n) +1 per qualche intero k . Dal d è inferiore a phi (n), lo sai che k < e. Quindi hai solo un piccolo numero di k da provare. In realtà, phi (n) è vicino a n (la differenza essendo dell'ordine di sqrt (n); in altre parole, quando scritto nel bit, la metà superiore del phi (n) è identico a quello di n) in modo da poter calcolare k ' con: k' = round (n/d). k' è molto vicino alla k (cioè | K'-k | < = 1) finché la dimensione di e è non più di metà della dimensione di n.

Dato k, si ottiene facilmente phi (n) = (ED-1)/k.Succede che:

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

Pertanto, ottieni p + q = n + 1 - phi (n). Hai anche pq. E 'tempo di ricordare che per tutti i numeri reali un e b, un e b sono le due soluzioni dell'equazione quadratica X - (a + b) X + ab. Quindi, data p + q e pq, p e q sono ottenuti risolvendo l'equazione quadratica:

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

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

Nel generi caso l, e e d può avere dimensioni arbitrarie (possibilmente superiore n), perché tutto ciò che RSA bisogno è che ed = 1 mod (p-1) e ed = 1 mod (q-1). Esiste un metodo generico (e veloce) che assomiglia un po 'al test di primalità di Miller-Rabin. È descritto nello Handbook of Applied Cryptography (capitolo 8, sezione 8.2.2, pagina 287). Questo metodo è concettualmente un po 'più complesso (comporta l'esponenziazione modulare) ma può essere più semplice da implementare (perché non esiste una radice quadrata).

Answer 2

C'è una procedura per recuperare p e q da n, e e d descritto NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Key Establishment Schemes Using Integer Factorization Cryptography nell'Appendice C.

I passi sono:

1. Lasciate k = de - 1. Se k è dispari, quindi andare al passo 4.
2. Write k come k = 2 ^{t r}, dove r è il massimo intero dispari dividendo k e t ≥ 1. O in termini più semplici, dividere ripetutamente il numero k per 2 fino a raggiungere un numero dispari.
3. Per i = 1 a fare:
   1. generare un intero casuale g nell'intervallo [0, n-1].
   2. Let y = g ^r mod n
   3. Se y = 1 oy = n - 1, quindi andare al passo 3.1 (cioè ripetere questo ciclo).
   4. Per j = 1-t - 1 fare:
      1. Let x = y mod n
      2. Se x = 1, andare a (esterno) Fase 5.
      3. Se x = n - 1, andare al passo 3.1.
      4. Lasciate y = x.
   5. Sia x = y mod n
   6. Se x = 1, passare al punto (esterno) 5.
   7. Continua
4. uscita “fattori primi non trovato "e basta.
5. Let p = GCD (y - 1, n) e sia q = n/p
6. uscita (p, q) come i fattori primi.

Recentemente ho scritto un'implementazione in Java. Non direttamente utile per C# mi rendo conto, ma forse può essere facilmente portato:

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

Questo codice utilizza alcune definizioni helper/metodi:

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

ho implementato il method descritto da Thomas Pornin.

La classe BigInteger è Chew la versione C# di Keong TAN (verificare CodeProject commenti per correzioni di bug)

/// 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

ho adattato il Java code provided by Duncan in C#, se qualcuno è interessato:

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

Questo utilizza la classe standard System.Numerics.BigInteger.

Questo è stato testato dalla seguente prova di unità:

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