Внедрение DSA (Digital Signature Alghoritm) - генерация ключей - PullRequest
Новая
       45

Внедрение DSA (Digital Signature Alghoritm) - генерация ключей

0 голосов
/ 14 декабря 2018

Мне нужно внедрить 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;
}

1 Ответ

0 голосов
/ 14 декабря 2018

Я не уверен, что вы делаете, но этот код иллюстрирует мои комментарии.Обычно он работает менее чем за 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 быстрые и грязные и должны быть очищены.

...