DSA（数字签名算法）实施 - 密钥生成

Question

我必须为大学实施 DSA，我在查找数字 q 时遇到问题，它是 p - 1 的质因数，其中p是质数。我试图编写一些奇怪的循环，但它只适用于较小的 p 值。使用 512 位长质数，我猜这需要很长时间。我使用 Java 和 BigInteger 库实现。

编辑：

   public BigInteger[] generatePAndQ(){

    BigInteger q = BigInteger.probablePrime(160, new Random());
    BigInteger k = BigInteger.valueOf(2); // k = 2

    BigInteger probablyPrime = q.multiply(k).add(BigInteger.ONE); // probablyPrime = q * k + 1
    while(!isPrime(probablyPrime)){
        q = BigInteger.probablePrime(160, new Random());
        probablyPrime = q.multiply(k).add(BigInteger.ONE);
    }

    BigInteger[] qAndP = new BigInteger[2];
    qAndP[0] = q;
    qAndP[1] = probablyPrime;

    return  qAndP;
}

Answer 1

我不确定你在做什么，但这段代码说明了我的意见。它通常在我的笔记本电脑上运行不到 0.5 秒。

import java.math.BigInteger;
import java.security.SecureRandom;

public class Main {

    public static BigInteger[] generatePAndQ() {
        SecureRandom random = new SecureRandom();

        final int pSizeInBits = 512;
        final int qSizeInBits = 160;
        BigInteger q = BigInteger.probablePrime(qSizeInBits, random);
        BigInteger k = BigInteger.ONE.shiftLeft(pSizeInBits - qSizeInBits); // k = 2**(pSizeInBits - qSizeInBits);

        BigInteger probablyPrime = q.multiply(k).add(BigInteger.ONE); // probablyPrime = q * k + 1
        while (!probablyPrime.isProbablePrime(50)) {
            q = BigInteger.probablePrime(qSizeInBits, random);
            probablyPrime = q.multiply(k).add(BigInteger.ONE);
        }

        BigInteger[] qAndP = new BigInteger[2];
        qAndP[0] = q;
        qAndP[1] = probablyPrime;

        return qAndP;
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        final BigInteger[] pAndQ = generatePAndQ();
        double elapsed = (System.nanoTime() - start) / 1e9;
        System.out.printf("q=%d%np=%d%nTime: %f (seconds)%n", pAndQ[0], pAndQ[1], elapsed);
    }
}

q、p 和 k 的界限很快而且很脏，应该清理。

DSA（数字签名算法）实施 - 密钥生成

DSA (Digital Signature Alghoritm) implementation - key generation

java

cryptography

dsa