DSA (Digital Signature Alghoritm) implementation - key generation

Question

I have to implement DSA for university and I have a problem with finding number q which is prime factor of p - 1 where p is prime number. I was trying to write some wierd loops but it only worked for small p values. With 512 bit long prime it would take ages I guess. I implement using Java and BigInteger library.

EDIT:

   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

I'm not sure what you're doing but this code illustrates my comments. It typically runs in less than 0.5 seconds on my laptop.

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

The bounds on q, p, and k are quick and dirty and should be cleaned up.