RSA 生成公私鑰時質數是怎麼選的？

01-25

具體的說比如openssl keygen時，是怎麼找質數的？假設個人計算機能力算不出太大的質數，是不是可以窮舉已知的大質數形成攻擊呢？

謝邀…

這題真沒想像的那麼簡單啊朋友們…事實上，下面三個問題的答案應該是完全不一樣的：

質數是怎麼選的？
Diffie-Hellman密鑰交換協議、ElGamal加密演算法、DSA簽名演算法中的質數是怎麼選的？
RSA生成公鑰時質數是怎麼選的？

前面幾位前輩的答案基本圍繞著「質數是怎麼選的」這個問題回答的。實際上，RSA生成公鑰、私鑰時所用的質數生成方法以「質數是怎麼選的」為基礎，但是後面還有不少需要注意的事項。既然我最近一直在用Bouncy Castle開發密碼學庫（為了避免打廣告的嫌疑，這個密碼學庫的鏈接和簡單的介紹我就不放了，有興趣的知友們可以在評論下面留言，如果確實需要我就在評論裡面給鏈接），我就以Bouncy Castle裡面RSA質數的選法為例，拋磚引玉地講解一下RSA質數的生成方法。

————————分割線————————

0. 說明

本文包含了很多源代碼，若想詳細分析答案，建議在瀏覽器端閱讀。
本文引用的Java JDK源代碼版本為：Java JDK 1.8.0_60
本文引用的Bouncy Castle源代碼版本為：Bouncy Castle JDK15on:1.54
本文源代碼閱覽工具為：InetlliJ IDEA 2016.2.2

————————分割線————————

1. 質數的個數

在我的知乎電子書《質數了不起》[1]中提到：

德國數學家高斯（Johann Carl Friedrich Gauss）和法國數學家勒讓德（Adrien-Marie Legendre）等大數學家都有下述猜想，然而並沒有找到嚴謹的證明。
當無限增長時，不超過x的質數個數與x/ln x之比趨近於1。（ln x是x的自然對數）。
這個猜想後來被稱為『質數定理』，簡單來說就是：前x個正整數中大約有x/lnx個質數。（這裡感謝 @haoshu zhao 、@胡鞍鋼同學的指正，這裡標註用十進位表示是多餘的… 原標註：注意這裡的x要用十進位表示）
在質數定理提出後的大約200年，法國數學家阿達馬（Jacques Hadamard）和比利時數學家瓦列-普金（Charles-Jean-Gustave-Nicholas de la Vallée-Poussin）才利用複變函數論在1896年首次證明了質數定理。雖然現在數學家們已經找到了不應用複變函數論證明質數定理的方法，但是所有已知的證明都非常複雜，遠非原始結論這樣清晰和簡潔。

我們就用這個定理分析一下給定位數的質數個數到底有多少個。假定我們要求某個質數的位數要達到二進位的n位，那麼這個數最大不會大於2^n，小於2^n質數的個數約為2^n / (n log e)。n位二進位數最小不會小於2^{n-1}，小於2^{n-1}的質數個數約為2^{n-1} / ((n - 1) log e)。因此，二進位位數恰好為n的質數個數總計為：

$frac{2^n}{n log e}-frac{2^{n-1}}{(n-1) log e}approxfrac{(n-1)2^n-frac{n}{2}2^n}{n(n-1) log e}=frac{n-2}{n(n-1) log e}2^{n-1}$

也就是說，二進位位數恰好為n的質數總個數與位數n的關係仍然是指數級的（只不過數量級小了O(n)）。因此，雖然二進位位數恰好為n的質數總個數和二進位位數恰好為n的所有整數個數相比少了一些，但是數量級是一樣的。隨著n的增大，質數個數也呈指數級增大，想遍歷一定位數下質數的個數對當前計算機來說仍然是非常困難的。

————————分割線————————

2. 如何判斷一個數是否為質數？

還是引用我知乎電子書《質數了不起》[1]中的論述：

1976年，卡內基梅隆大學的計算機系教授Miller提出了一個基於廣義黎曼猜想的質數確定判別法[32]。然而，廣義黎曼猜想還沒有得到證明，因此Miller所提出的判別法暫時還無法使用。後來，以色列耶路撒冷希伯來大學的Rabin教授對判別法進行了修改，提出了不依賴於廣義黎曼猜想的質數概率判別法[33]。因Miller和Rabin對此判別法都做出了突出的貢獻，這一判別法被命名為『Miller-Rabin質數判別法』。現今，Miller-Rabin質數判別法是最為常用的質數判別法，廣泛用於密碼學方案中的大質數選取步驟中。

我們來看看在Java JDK 8中用的是什麼演算法：

//BigInteger.java第856行至第884行 boolean primeToCertainty(int certainty, Random random) { int rounds = 0; int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2; // The relationship between the certainty and the number of rounds // we perform is given in the draft standard ANSI X9.80, "PRIME // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES". int sizeInBits = this.bitLength(); if (sizeInBits &< 100) { rounds = 50; rounds = n &< rounds ? n : rounds; return passesMillerRabin(rounds, random);//用到了Miller-Rabin判別 } if (sizeInBits &< 256) { rounds = 27; } else if (sizeInBits &< 512) { rounds = 15; } else if (sizeInBits &< 768) { rounds = 8; } else if (sizeInBits &< 1024) { rounds = 4; } else { rounds = 2; } rounds = n &< rounds ? n : rounds; return passesMillerRabin(rounds, random) passesLucasLehmer();同樣也要調用Miller-Rabin判別 }

從演算法名就可以看出，Java JDK中使用的演算法為Miller-Rabin質數判別法。至於判別法本身在此就不多做論述了，感興趣的知友們可以參考《質數了不起》中的引用[33]了解演算法的執行過程和演算法複雜度。

————————分割線————————

3. 如何選擇一個質數？

這個過程有一點複雜，最簡單的思路為：先隨機選擇一個給定位數的奇數，然後用質數判別法判斷其是否為質數。如果不是，則重新選擇。但是，根據「質數定理」，給定一個數x，小於x的質數個數約為x / ln x，也就是說，給定一個數，其為質數的概率約為1 / ln x。就算給定的數是個奇數，其概率也只能上升到2 / ln x。如果質數要求是2048位，那麼隨機取一個奇數，其能通過質數檢驗的概率約為

$frac{2}{2048 log e} approx 0.22\%$

（這裡感謝 @sunoru 同學的指正，原始計算有誤）。也就是說，差不斷要選500次才能有一次通過質數判斷。為了進一步提高效率，Java JDK實現了2個方法，一種方法適用於當給定位數比較小的情況，另一種方法適用於當給定位數比較大的情況。Java JDK規定，當給定位數小於95位時，用第一種方法；當給定位數大於等於95位時，用第二種方法：

//BigInteger.java 第651行至第666行 public BigInteger(int bitLength, int certainty, Random rnd) { BigInteger prime;

if (bitLength &< 2) throw new ArithmeticException("bitLength &< 2"); prime = (bitLength &< SMALL_PRIME_THRESHOLD ? smallPrime(bitLength, certainty, rnd)//小於門限用smallPrime : largePrime(bitLength, certainty, rnd));//大於門限用largePrime signum = 1; mag = prime.mag; } // Minimum size in bits that the requested prime number has // before we use the large prime number generating algorithms. // The cutoff of 95 was chosen empirically for best performance. private static final int SMALL_PRIME_THRESHOLD = 95;//這就是95位的門限

smallPrime函數的原理是：先用某種方法挑一個數，然後判斷其是否能通過primeToCertainty函數的驗證，如果不能通過則重新選取。smallPrime函數的源代碼在BigInteger.java的第700行至第733行，其中第729行至第731行用到了質數判定函數：

// Do expensive test if we survive pre-test (or it"s inapplicable) if (p.primeToCertainty(certainty, rnd)) return p;

largePrime函數的原理是：先用某種方法挑一個數，用數篩法篩這個數，看是不是存在明顯的合數，如果沒有，再判斷得到的指數是否能通過primeToCertainty函數的驗證，返回通過primeToCertainty函數的驗證的數（感謝 @大濕的指正，largePrime中所調用類BitSieve的第203行同樣調用了primeToCertainty函數）：

//BigInteger.java 第738行至第763行 /** * Find a random number of the specified bitLength that is probably prime. * This method is more appropriate for larger bitlengths since it uses * a sieve to eliminate most composites before using a more expensive * test. */ private static BigInteger largePrime(int bitLength, int certainty, Random rnd) { BigInteger p; p = new BigInteger(bitLength, rnd).setBit(bitLength-1); p.mag[p.mag.length-1] = 0xfffffffe;


    // Use a sieve length likely to contain the next prime number

    int searchLen = getPrimeSearchLen(bitLength);

    BitSieve searchSieve = new BitSieve(p, searchLen);

    BigInteger candidate = searchSieve.retrieve(p, certainty, rnd);//上面3行代碼就用了數篩法篩掉合數，從而選擇質數

while ((candidate == null) || (candidate.bitLength() != bitLength)) { p = p.add(BigInteger.valueOf(2*searchLen)); if (p.bitLength() != bitLength) p = new BigInteger(bitLength, rnd).setBit(bitLength-1); p.mag[p.mag.length-1] = 0xfffffffe; searchSieve = new BitSieve(p, searchLen); candidate = searchSieve.retrieve(p, certainty, rnd); } return candidate; }

————————分割線————————

3. 如何選擇一個滿足RSA安全性的質數？

這個問題回答起來也有點麻煩。RSA中涉及到2個質數：p和q，而且還涉及到公鑰e和私鑰d。只要p和q是質數就夠了嗎？答案是否定的。實際上，RSA中的質數還需要滿足很多條件，簡單列舉如下：

（1）RSA中的質數p和質數q不能離得太近

密碼學家D. Coppersmith於1996年指出[2]：如果合數N的質因子p和質因子q離得很近，則存在快速演算法將N分解。現在一般認為，如果合數N的位數為n，那麼|p-q|要同時滿足

$log |p-q|> n/2-100; log |p-q| > n/3$

（2）RSA中的e不能太小

同樣是密碼學家D. Coppersmith，其於1990年指出[3]：用於RSA的指數e不能太小，否則存在快速演算法計算得到私鑰d。這個定理要用到格密碼學的著名演算法LLL。再次就不多做展開了… 不過需要注意的是，由於加密演算法要計算m^e，如果e太大的話加密過程可能會比較慢。現在一般認為令e=65537是比較合適的。

（3）RSA中的d不能太小

密碼學家M. Wiener於1990年指出[4]：用於RSA的私鑰d不能太小，否則存在快速演算法得到私鑰d。現在一般認為，如果合數N的位數為n，那麼d的值要滿足

$d > 2^{n/2}$

（4）RSA中的合數N非相鄰形式（Non-Adjacent Form，NAF）權重不能太小

密碼學家O. Schirokauer於2010年指出[5]：如果N的NAF表述權重略小，則應用數篩法可能會快速對N進行質因數分解。現在一般要求N的NAF表述權重要大於N/4。

綜合上述問題，我們才能得到RSA質數的選取方法，大致流程如下：

給定RSA所要求N的位數n，選擇一個大於65537的公鑰e。
隨機選擇一個長度為(n + 1) / 2的質數。如果(n + 1) / 2小於95，則用smallPrime函數選取，否則用largePrime函數選取。
選擇一個長度為n - (n + 1) / 2 = (n - 1) / 2的質數q，如果(n - 1) / 2小於95，則用smallPrime函數選取，否則用largePrime函數選取。
求|p-q|，如果差值位數過小，則回到2，重新選取p。
計算N = pq，判斷N的位數是否確實為n，如果不是，則回到2，重新選取p。
計算N的NAF權重，如果過小，則回到2，重新選取p。
求e在Z_N群下的逆元d，如果d過小，則回到2，重新選取p。
返回RSA的參數p、q、e、d等。

————————分割線————————

4. 源代碼參考

Bouncy Castle中的RSAKeyPairGenerator.java給出了RSA質數的完整選取方法，具體代碼為第31行至第151行。我適當進行了中文標記。

public AsymmetricCipherKeyPair generateKeyPair() { AsymmetricCipherKeyPair result = null; boolean done = false;


    //

    // p and q values should have a length of half the strength in bits

    //

    int strength = param.getStrength();

    int pbitlength = (strength + 1) / 2;

    int qbitlength = strength - pbitlength;

    int mindiffbits = (strength / 2) - 100;//mindiffbits為|p-q|位數的限制，首先要大於n/2 - 100
    if (mindiffbits &< strength / 3)
    {
        mindiffbits = strength / 3;//其次，mindiffibts還要滿足大於n/3
    }

    int minWeight = strength &>&> 2;//限定N的NAF Weight
    // d lower bound is 2^(strength / 2)，即私鑰d要大於2^{n/2}

    BigInteger dLowerBound = BigInteger.valueOf(2).pow(strength / 2);

    // squared bound (sqrt(2)*2^(nlen/2-1))^2，這是限定p和q的平方值不能越界

    BigInteger squaredBound = ONE.shiftLeft(strength - 1);

    // 2^(nlen/2 - 100)

    BigInteger minDiff = ONE.shiftLeft(mindiffbits);
    while (!done)

    {

        BigInteger p, q, n, d, e, pSub1, qSub1, gcd, lcm;
        e = param.getPublicExponent();
        p = chooseRandomPrime(pbitlength, e, squaredBound);
        //

        // generate a modulus of the required length

        //

        for (; ; )

        {

            q = chooseRandomPrime(qbitlength, e, squaredBound);

// p and q should not be too close together (or equal!)，p和q不能離得太近（更不能相等！） BigInteger diff = q.subtract(p).abs(); if (diff.bitLength() &< mindiffbits || diff.compareTo(minDiff) &<= 0) { continue; } // // calculate the modulus // n = p.multiply(q); if (n.bitLength() != strength)//判斷N=pq是否滿足給定的位數 { // // if we get here our primes aren"t big enough, make the largest // of the two p and try again // p = p.max(q); continue; } /* * Require a minimum weight of the NAF representation, since low-weight composites may * be weak against a version of the number-field-sieve for factoring. * * See "The number field sieve for integers of low weight", Oliver Schirokauer. */ if (WNafUtil.getNafWeight(n) &< minWeight) { p = chooseRandomPrime(pbitlength, e, squaredBound);//這裡就是NAF權重了，可以看到Bouncy Castle給出了引用 continue; } break; } if (p.compareTo(q) &< 0) { gcd = p; p = q; q = gcd; } pSub1 = p.subtract(ONE); qSub1 = q.subtract(ONE); gcd = pSub1.gcd(qSub1); lcm = pSub1.divide(gcd).multiply(qSub1); // // calculate the private exponent // d = e.modInverse(lcm); if (d.compareTo(dLowerBound) &<= 0)//私鑰d不能太小，否則重新選取 { continue; } else { done = true; } // // calculate the CRT factors // BigInteger dP, dQ, qInv; dP = d.remainder(pSub1); dQ = d.remainder(qSub1); qInv = q.modInverse(p); result = new AsymmetricCipherKeyPair( new RSAKeyParameters(false, n, e), new RSAPrivateCrtKeyParameters(n, e, d, p, q, dP, dQ, qInv)); } return resu< }

以上，才是（至今為止）RSA質數的正確選法。未來，數學家們或者密碼學家們若發現了其它漏洞，還可能進一步修改RSA質數的選擇方法。

————————分割線————————

5. 參考文獻

[1] 劉巍然. 質數了不起. 知乎出版社. 中國, 北京, 2016, 《質數了不起：知乎劉巍然作品 (知乎「一小時」系列)》劉巍然, 知乎書評簡介電子書下載 Kindle電子書.

[2] Coppersmith D. Finding a small root of a bivariate integer equation; factoring with high bits known. EUROCRYPT 1996. pp. 178-189, ACM, 1996.

[3] Coppersmith D., Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10: 233–260, 1997.

[4] Wiener M. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory. 36: 553–558, 1990.

[5] Schirokauer O. The number field sieve for integers of low weight. Mathematics of Computation, 79(269): 583-602, 2010.

做RSA演算法作業的時候，我是這樣做的：

1、先準備幾千個小素數的一個表。2,3,5,7,11,13......

2、隨機生成一個大數X，1024位，設為奇數。

3、遍歷小素數表，要是X能整除其中的元素，就計算X = X + 2，然後重複，最後得到與小素數表所有數都互質的X。

4、對X進行Miller-Rabin素性檢驗，8次。如果X沒有通過檢驗，回到第2步。否則認為X是素數。

5、用上述步驟得到的p，q，生成密鑰對，e預先定義為0x10001。隨機生成一個數，進行加密解密，比對結果。

######

主要是通過Miller-Rabin演算法進行素數檢測，Miller-Rabin檢查通過則素數的概率為3/4，8次都通過則素數的概率為0.9999847....。

5的目的是為了多一層保障，畢竟前面的概率不是100%。如果p，q有一個是合數，則加密解密失敗。之前在4中只檢測6次，然後在10000次的測試中，5失敗了一次，然後改成了8。

3的目的是為了提高4通過對概率，因為4的計算量還比較大。

3，4都有一些trick可以提高速度。

因為是作業所以對安全性沒什麼要求，速度的話還可以。

看了酥大的回復之後基本懂了，但是還是有點不解怎麼能秒篩出2048位的素數（自己想了想演算法，貌似不可能實現啊），就自己debug了一下這句：

BigInteger candidate = searchSieve.retrieve(p, certainty, rnd);

他的流程是：隨機取一個2048位大數p和一個足夠長的length，構造一個數列

然後自p開始，用事先準備的64*150*2以內的小素數去篩他（這個小素數注釋說是按經驗選的），篩完之後，再次用primeToCertainty來檢驗。

如果這個數列沒素數，就再開一個數列

Prime number theorem揭示了素數的分布規律：

This means that for large enough N, the probability that a random integer not greater than N is prime is very close to 1/log(N).

可以發現就算密鑰長度到達如今商業標準中的2048位的量級，所滿足要求的素數還是茫茫多，因此枚舉是不可能的。。一般的做法是生成隨機數之後進行素性檢驗，直到找到一個是素數的隨機數為止。（並不是任意一個素數對都能當做RSA的密鑰，需要排除掉那些被數學家們仔細分析過的弱密鑰）

演算法總結：判斷一個數是否為素數

這個博客寫的不錯

雖然可以證明任意長度的自然數序列中沒有一個素數，但既使數字到了100位，每100個數中平均會有1個素數，這就多到足以給地球上的每一個原子分配一對。

判斷一個數是否是素數，有非常高效快速的方法，但把兩個素數相乘以後的積給你，讓你分解，那你就要算到地老天荒了。

Miller Rabin演算法