DSA algorithm in java : check and advice
<p>If one of you is familiar with the DSA algorithm, could you check if I understood correctly the algorithm ? Or at least answer the 2 questions that follow ? I based my work on the <a href="https://en.wikipedia.org/wiki/Digital_Signature_Algorithm" rel="nofollow" title="Wikipedia DSA article">Wikipedia DSA article</a>.</p>

<p>I tried to make the code as clear as I could for reading.</p>

<pre><code>public static class KeyGenerator {
    private final BigInteger TWO = new BigInteger("2");
    private final BigInteger P, Q, G;

    public KeyGenerator(int pLength) {
        this.Q = generateQ();
        this.P = generateP(Q,pLength);
        this.G = generateG(P,Q,TWO);
    }

    private BigInteger generateQ() {
        return BigInteger.probablePrime(160, new Random());
    }

    private BigInteger generateP(BigInteger Q, int l) {
        //l should be multiple of 64
        if(l%64!=0) throw new InvalidParameterException("64 should divide l");

        //P is prime and P mod Q == 1 ( i.e. P-1 = Q*Z )
        BigInteger P = BigInteger.probablePrime(512, new Random());//We generate a potential random P
        BigInteger remainder = P.mod(Q);//We calculate the remainder
        P = P.subtract(remainder).add(BigInteger.ONE);//We make P being P = Q*Z + 1 by removing the remainder
        while(!P.isProbablePrime(100)) {P = P.add(Q);}//Z++ until P = Q*Z + 1 is primal

        //P has to be l bits (l = 512 or 1024 generally)
        if(P.bitCount()&gt;l) {return generateP(Q,l);}
        return P;
    }

    private BigInteger generateG(BigInteger P, BigInteger Q, BigInteger H) {
        //G is H^((P-1)/Q) mod P with H being any value 1&lt;H&lt;Q
        BigInteger G = H.modPow(P.subtract(BigInteger.ONE).divide(Q),P);
        if(G.compareTo(BigInteger.ONE)&lt;=0) return generateG(P, Q, H.add(BigInteger.ONE));//G must be &gt;1
        return G;
    }

    public KeyPair generateKeyPair() {
        BigInteger privateKey = new BigInteger(159, new Random());//private key should be &lt;Q, but Q is 160 bits.
        //public key is G^X mod P where X is the private key
        BigInteger publicKey = G.modPow(privateKey,P);
        return new KeyPair(privateKey, publicKey);
    }

}

public static class SignatureMaker {

    ...

    public Signature sign(String message) {
        BigInteger K = new BigInteger(159,new Random());//Random K &lt; Q
        BigInteger R = G.modPow(K, P).mod(Q);//R = G^K mod P mod Q
        if(R.compareTo(BigInteger.ZERO)==0) {return sign(message);}//R should be &gt;0
        BigInteger M = new BigInteger(DigestUtils.sha1(message));//M = sha1(message) (i.e. M = H(m))
        BigInteger S = K.modInverse(Q).multiply(M.add(privateKey.multiply(R))).mod(Q);//S = K^-1*(H(m)+X*R) mod Q
        if(S.compareTo(BigInteger.ZERO)==0) {return sign(message);}//S should be &gt;0
        return new Signature(R, S);
    }
}

public static class SignatureChecker {

    ...

    public boolean check(String message, Signature signature) {
        BigInteger R = signature.R;
        BigInteger S = signature.S;
        if(R.signum()&lt;1 || R.compareTo(Q)&gt;=0 || S.signum()&lt;1 || S.compareTo(Q)&gt;=0) return false;//0&lt;R&lt;Q and 0&lt;S&lt;Q
        BigInteger W = S.modInverse(Q);//W = S^-1 mod Q
        BigInteger M = new BigInteger(DigestUtils.sha1(message));//M = sha1(message) i.e. M = H(m)
        BigInteger U1 = M.multiply(W).mod(Q);//U1 = (H(M)*W) mod Q
        BigInteger U2 = R.multiply(W).mod(Q);//U2 = (R*W) mod Q
        BigInteger V = G.modPow(U1, P).multiply(publicKey.modPow(U2, P)).mod(P).mod(Q);//V = (G^U1 mod P)*(Y^U2 mod P) mod P mod Q
        return V.compareTo(R)==0;//Valid only if V==R
    }
}
</code></pre>

<p>I ran some tests and it seems to work, but it doesn't mean I didn't make any mistake.</p>

<ul>
<li><p>I'm especially unsure of the calculation of <code>S</code> during the <code>sign</code>,    and <code>V</code> during the <code>check</code> because I couldn't make the exact formula    that was written in Wikipedia.</p></li>
<li><p><strong>[Solved in comments]</strong> I also totally don't get why the algorithm in Wikipedia asks for <code>mod P mod Q</code> during the verification. Normally, mod P mod Q should return the same result as mod Q...</p></li>
</ul>

<p>If you see possible improvement, I'll gladly take it too.</p>

<p>Thanks a lot !</p>