java中大素数生成算法

时间：2024-04-04 09:30:21

目前的公开** 算法大部分基于大整数分解、有限域上的离散对数问题和椭 圆曲线上的离散对数问题，这些数学难题的构建大部分都需 要生成一种超大的素数，尤其在经典的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算法的一个变形改进。
java中大素数生成算法

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

相关文章