Problem in implementing DSA in Java without Cryptography Library

Hello I have very strange problem and maybe some of you could help my. I am implementing DSA signature algorithm in Java but I cannot use any of existing libraries to do this except of generating SHA-1 hash function from java.security. My code is generating each of the required numbers but there is a problem with verifying the signature. Here is my code:

    public class Key {
        int primeCenterie = 20;
        BigInteger q;
        BigInteger p;
        BigInteger g;
        BigInteger y;
        BigInteger x;
        BigInteger k;
        Random rand = new Random();
        Key() {        }
        public void generateKey() {
            q = new BigInteger(160, primeCenterie, rand);
            p = generateP(q, 512);
            g = generateG(p, q);
            do {
                x = new BigInteger(q.bitCount(), rand);
            } while (x.compareTo(BigInteger.ZERO) == -1 || x.compareTo(g) == 1);
            y = g.modPow(x, p);
            System.out.println("p:" + p);
            System.out.println("q:" + q);
            System.out.println("g:" + g);
            System.out.println("private key  (x):" + x);
            System.out.println("public key  (y):" + y);
        }
       private BigInteger generateP(BigInteger q, int l) {
            if (l % 64 != 0) {
                throw new IllegalArgumentException(" zle l ");
            }
            BigInteger pTemp;
            BigInteger pTemp2;
            do {
                pTemp = new BigInteger(l, primeCenterie, rand);
                pTemp2 = pTemp.subtract(BigInteger.ONE);
                pTemp = pTemp.subtract(pTemp2.remainder(q));
            } while (!pTemp.isProbablePrime(primeCenterie));
            return pTemp;
        }
        private BigInteger generateG(BigInteger p, BigInteger q) {
            BigInteger aux = p.subtract(BigInteger.ONE);
            BigInteger pow = aux.divide(q);
            BigInteger g;
            do {
                g = new BigInteger(au开发者_开发问答x.bitLength(), rand);
            } while (g.compareTo(aux) == -1 && g.compareTo(BigInteger.ZERO) == 1);
            return g.modPow(pow, aux);
        }
        public BigInteger generateR() {
            BigInteger r = g.modPow(x, p).mod(q);
            System.out.println("r:" + r);
            return r;
        }
        public BigInteger generateS(BigInteger r, byte[] data) {
            MessageDigest md;
            BigInteger s = BigInteger.ONE;
            try {
                md = MessageDigest.getInstance("SHA-1");
                md.update(data);
                BigInteger hash = new BigInteger(md.digest());
                System.out.println("Hash:" + hash);
                s = (x.modInverse(q).multiply(hash.add(x.multiply(r)))).mod(q);
            } catch (NoSuchAlgorithmException ex) {
                Logger.getLogger(DSA.class.getName()).log(Level.SEVERE, null, ex);
            }
            System.out.println("s:" + s);
            return s;
        }
        boolean verify(byte[] data, BigInteger r, BigInteger s) {
            if (r.compareTo(BigInteger.ZERO) <= 0 || r.compareTo(q) >= 0) {
                return false;
            }
            if (s.compareTo(BigInteger.ZERO) <= 0 || s.compareTo(q) >= 0) {
                return false;
            }
            MessageDigest md;
            BigInteger v = BigInteger.ZERO;
            try {
                md = MessageDigest.getInstance("SHA-1");
                md.update(data);
                BigInteger hash = new BigInteger(md.digest());
                BigInteger w = s.modInverse(q);
                BigInteger u1 = hash.multiply(w).mod(q);
                BigInteger u2 = r.multiply(w).mod(q);
                v = ((g.modPow(u1, p).multiply(y.modPow(u2, p))).mod(p)).mod(q);
            } catch (NoSuchAlgorithmException ex) {
                Logger.getLogger(DSA.class.getName()).log(Level.SEVERE, null, ex);
            }
            System.out.println("v:" + v);
            System.out.println("r:" + r);
            return v.compareTo(r) == 0;
        }
    }

I am generating R and S using generateR() and generateS(BigInteger r, byte[] data) functions. Data is text of my message converted to bytes. And when I send exactly the same byte array and generated S and R to verify function it returns false. R and V aren’t identical but they should. What I am doing wrong :)?? I was using this c# code as an example: http://www.koders.com/csharp/fidE9EF01A91C00DF066F023DD2EECA23856B922537.aspx?s=mdef%3Afile and description at Wikipedia http://en.wikipedia.org/wiki/Digital_Signature_Algorithm

Function to generate K:

        public BigInteger generateK(BigInteger q){
            BigInteger tempK;
            do {
                tempK = new BigInteger(q.bitLength(), rand);
            } while (tempK.compareTo(q) != -1 && tempK.compareTo(BigInteger.ZERO) != 1);
            return tempK;
        }

---

Finally!! Here is me code that works:

public class Key {
   int primeCenterie = 20;
   BigInteger q;
   BigInteger p;
   BigInteger g;
   BigInteger y;
   BigInteger x;
   BigInteger k;
   Random rand = new Random();

Key() {}

public void generateKey() {
    q = new BigInteger(160, primeCenterie, rand);
    p = generateP(q, 512);
    g = generateG(p, q);
    do {
        x = new BigInteger(q.bitCount(), rand);
    } while (x.compareTo(BigInteger.ZERO) != 1 && x.compareTo(q) != -1);
    y = g.modPow(x, p);
}

private BigInteger generateP(BigInteger q, int l) {
    if (l % 64 != 0) {
        throw new IllegalArgumentException("L value is wrong");
    }
    BigInteger pTemp;
    BigInteger pTemp2;
    do {
        pTemp = new BigInteger(l, primeCenterie, rand);
        pTemp2 = pTemp.subtract(BigInteger.ONE);
        pTemp = pTemp.subtract(pTemp2.remainder(q));
    } while (!pTemp.isProbablePrime(primeCenterie) || pTemp.bitLength() != l);
    return pTemp;
}
private BigInteger generateG(BigInteger p, BigInteger q) {
    BigInteger aux = p.subtract(BigInteger.ONE);
    BigInteger pow = aux.divide(q);
    BigInteger gTemp;
    do {
        gTemp = new BigInteger(aux.bitLength(), rand);
    } while (gTemp.compareTo(aux) != -1 && gTemp.compareTo(BigInteger.ONE) != 1);
    return gTemp.modPow(pow, p);
}

public BigInteger generateK(BigInteger q) {
    BigInteger tempK;
    do {
        tempK = new BigInteger(q.bitLength(), rand);
    } while (tempK.compareTo(q) != -1 && tempK.compareTo(BigInteger.ZERO) != 1);
    return tempK;
}
public BigInteger generateR() {
    k = generateK(q);
    BigInteger r = g.modPow(k, p).mod(q);
    return r;
}

public BigInteger generateS(BigInteger r, byte[] data) {
    MessageDigest md;
    BigInteger s = BigInteger.ONE;
    try {
        md = MessageDigest.getInstance("SHA-1");
        md.update(data);
        BigInteger hash = new BigInteger(md.digest());
        s = (k.modInverse(q).multiply(hash.add(x.multiply(r)))).mod(q);
    } catch (NoSuchAlgorithmException ex) {
        Logger.getLogger(DSA.class.getName()).log(Level.SEVERE, null, ex);
    }
    return s;
}

boolean verify(byte[] data, BigInteger r, BigInteger s) {
    if (r.compareTo(BigInteger.ZERO) <= 0 || r.compareTo(q) >= 0) {
        return false;
    }
    if (s.compareTo(BigInteger.ZERO) <= 0 || s.compareTo(q) >= 0) {
        return false;
    }
    MessageDigest md;
    BigInteger v = BigInteger.ZERO;
    try {
        md = MessageDigest.getInstance("SHA-1");
        md.update(data);
        BigInteger hash = new BigInteger(md.digest());
        BigInteger w = s.modInverse(q);
        BigInteger u1 = hash.multiply(w).mod(q);
        BigInteger u2 = r.multiply(w).mod(q);
        v = ((g.modPow(u1, p).multiply(y.modPow(u2, p))).mod(p)).mod(q);
    } catch (NoSuchAlgorithmException ex) {
        Logger.getLogger(DSA.class.getName()).log(Level.SEVERE, null, ex);
    }
    return v.compareTo(r) == 0;
}}

Small mistakes but still mistakes;)

@crazyscot Thanks for your help:D

---

I don't think you're computing R and S correctly - see the Signing section of the WP page you linked to.

• R should be g^k mod p mod q for a freshly generated random k.
• Similarly, in computing S you should be taking the modInverse of the same k - not x.