title: Problem in implementing DSA in Java without Cryptography Library
body: <p>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:
  <pre><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(aux.bitLength(), rand);
              } while (g.compareTo(aux) == -1 &amp;&amp; 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) &lt;= 0 || r.compareTo(q) >= 0) {
                  return false;
              }
              if (s.compareTo(BigInteger.ZERO) &lt;= 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;
          }
      }
  </pre></code>
  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:
  <a href="http://www.koders.com/csharp/fidE9EF01A91C00DF066F023DD2EECA23856B922537.aspx?s=mdef%3Afile" rel="nofollow">http://www.koders.com/csharp/fidE9EF01A91C00DF066F023DD2EECA23856B922537.aspx?s=mdef%3Afile</a>
  and description at Wikipedia 
  <a href="http://en.wikipedia.org/wiki/Digital_Signature_Algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Digital_Signature_Algorithm</a></p>
  
  <p>Function to generate K:
  <pre><code>
          public BigInteger generateK(BigInteger q){
              BigInteger tempK;
              do {
                  tempK = new BigInteger(q.bitLength(), rand);
              } while (tempK.compareTo(q) != -1 &amp;&amp; tempK.compareTo(BigInteger.ZERO) != 1);
              return tempK;
          }
  </pre></code></p>