时间戳

首页 > 解决方案 > DSA（数字签名算法）实施 - 密钥生成

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

问题描述

我必须为大学实施 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;
}

标签： javacryptographydsa

解决方案

我不确定你在做什么，但这段代码说明了我的评论。它通常在我的笔记本电脑上运行不到 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 的边界快速而肮脏，应该清理。

推荐阅读