java中大素数生成算法

心已赠人 2022-02-22 02:40 179阅读 0赞

目前的公开密钥 算法大部分基于大整数分解、有限域上的离散对数问题和椭 圆曲线上的离散对数问题，这些数学难题的构建大部分都需 要生成一种超大的素数，尤其在经典的RSA算法中，生成的素数的质量对系统的安全性有很大的影响。

## 1.原理 ##

费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。  
基于此可以快速判断一个大整数是否为素数。

Miller-Rabin算法：Fermat算法的一个变形改进。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70]

## 2. BigInteger中的API ##

public static BigInteger probablePrime(int bitLength, Random rnd)

结果是素数的概率为1-2^(-100)，貌似内部使用了Miller-Rabin算法。  
先不论这个概率问题，生成100个2048位的素数耗时141475ms  
调用DHCryptUtils.randomPrime(2048)10次的时间已经达到了143614ms。  
再来看这个概率问题，1-2^(-100)已经很接近于1。  
如果还想提高这个概率，可以调用

public boolean isProbablePrime(int certainty)

certainty表示判断的准确率为1-2^(-certainty)

Random r = new Random();
                BigInteger bigInteger = BigInteger.probablePrime(2048, r);
                while(!bigInteger.isProbablePrime(256)){
                    bigInteger = BigInteger.probablePrime(2048, r);
                }

## 3. DH的KeyPairGenerator如何生成P和Q ##

一步一步进断点之后，发现了DSAParameterGenerator中的方法generatePandQ  
certainty的取值和生成素数的长度有关系

byte var11 = -1;
            if (var1 <= 1024) {
                var11 = 80;
            } else if (var1 == 2048) {
                var11 = 112;
            }

我这里需要的2048位，因此certainty为112。

内部生成素数的方法：

BigInteger var14 = null;
    
                while(true) {
                    BigInteger var13;
                    BigInteger var16;
                    do {
                        var0.nextBytes(var9);
                        var14 = new BigInteger(1, var9);
                        var16 = (new BigInteger(1, var5.digest(var9))).mod(TWO.pow(var2 - 1));
                        var13 = TWO.pow(var2 - 1).add(var16).add(ONE).subtract(var16.mod(TWO));
                    } while(!var13.isProbablePrime(var11));
    
                    var16 = ONE;
    
                    for(int var15 = 0; var15 < 4 * var1; ++var15) {
                        BigInteger[] var17 = new BigInteger[var7 + 1];
    
                        BigInteger var19;
                        BigInteger var20;
                        for(int var18 = 0; var18 <= var7; ++var18) {
                            var19 = BigInteger.valueOf((long)var18);
                            var20 = var14.add(var16).add(var19).mod(var10);
                            byte[] var21 = var5.digest(toByteArray(var20));
                            var17[var18] = new BigInteger(1, var21);
                        }
    
                        BigInteger var24 = var17[0];
    
                        for(int var25 = 1; var25 < var7; ++var25) {
                            var24 = var24.add(var17[var25].multiply(TWO.pow(var25 * var6)));
                        }
    
                        var24 = var24.add(var17[var7].mod(TWO.pow(var8)).multiply(TWO.pow(var7 * var6)));
                        var19 = TWO.pow(var1 - 1);
                        var20 = var24.add(var19);
                        BigInteger var26 = var20.mod(var13.multiply(TWO));
                        BigInteger var12 = var20.subtract(var26.subtract(ONE));
                        if (var12.compareTo(var19) > -1 && var12.isProbablePrime(var11)) {
                            BigInteger[] var22 = new BigInteger[]{var12, var13, var14, BigInteger.valueOf((long)var15)};
                            return var22;
                        }
    
                        var16 = var16.add(BigInteger.valueOf((long)var7)).add(ONE);
                    }
                }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70]: /images/20220222/7c3aace347224ff38cf715ecc01538e7.png