SHA hash function gives a negative output

Question

I'm trying to implement DSA signature algorithm and I'm stuck on a problem. I'm using the java.security MessageDigest class, here's the code:

MessageDigest md;
md = MessageDigest.getInstance("SHA-1");
md.update(text.getBytes());
return new BigInteger(md.digest());

Text is a random String object. Problem is that this code gives me negative values of hash, which is not accepted by the algorithm. Am I doing something wrong? Thanks in advance.

P.S. By the way, I've also tried to implement DSA without using BigIntegers, is this possible? I've not found the L and N values lesser than 1024 and 160, so I have no idea what values should I take and what hash-function should I use. Will be very thankful to hear the answers on these questions.

so what do you expect? BigInteger is just a byte[] w/ methods to work upon. The external byte[] representation of MessageDigest and BigInteger have no touching point. — bestsss, Jun 15 '11 at 11:52
@bestsss so how to transform digest to BigInteger? And maybe any thoughts on the P.S. part of my question? Thanks for you answer. — Egor, Jun 15 '11 at 12:01
why are you reimplementing DSA? Normally you should use system-provided functionality; reimplementing crypto is dangerous as it may lead to subtle security bugs. — crazyscot, Jun 15 '11 at 12:04
@crazyscot This is my homework at the university, I'm told not to use the built in classes.. — Egor, Jun 15 '11 at 12:10
if you strictly need a positive (or zero) BigInteger call abs(). You lose one bit in this case, alternatively you can add the absolutely min value to the result to make sure it's always positive. I just dont see your problem: what's the purpose of the algorithm that needs some random sequence, then hashed and then used as integer? If you just need to represent the hash value in some way, there are better options than BigInteger. — bestsss, Jun 15 '11 at 12:11
I do not second any of the above comments. The only problem with your code is that you should have used new BigInteger(1, md.digest()). — class stacker, Dec 22 '12 at 12:04

Martijn Courteaux · Accepted Answer · 2012-12-27T22:45:35.717

3

MessageDigest md;
md = MessageDigest.getInstance("SHA-1");
md.update(text.getBytes());
return new BigInteger(1, md.digest()); // use this 1 to tell it is positive.

Then you can convert your hash to a String using:

String hash = biginteger.toString(16);

Then optionally prepend the leading zeros.

String zeros = String.format("%032d", 0);
hash = zeros.substring(hash.length()) + hash;

edited Dec 27 '12 at 22:45

answered Jun 15 '11 at 11:56

Martijn Courteaux

67,591
47
198
287

1

First, there is no MessageDigest.toString(base) method, and this is the reason for the question in the first place I'd say. The second code snippet above should use BigInteger.toString(16) instead. Second, there is absolutely no need to pad zeroes. Not even the worst digest function would return a hash value with four consecutive bits of value zero. – class stacker Dec 22 '12 at 12:02
Yep, you are right, I fixed it. And about the padding, that is also why I wrote "eventually". – Martijn Courteaux Dec 22 '12 at 16:59
@MartijnCourteaux I'm sorry for the second part of my comment. Hashes _can_ generate eight consecutive zeroes. I was sure they wouldn'tr but have been proven wrong. – class stacker Dec 27 '12 at 20:07
@ClassStacker: Oh, wait. Eventually means "at the end". I meant to write something like "optionally". – Martijn Courteaux Dec 27 '12 at 22:45

score 3 · Answer 2 · answered Jun 15 '11 at 11:57

Why are you surprised? MessageDigest#digest() returns evenly distributed 160 bits of data. They are typically represented as hexadecimal string, but if you convert them to integer, the most significant bit designates the sign. Check out this code:

System.out.println(new BigInteger(new byte[]{(byte) 255}));  //-1

score 1 · Answer 3 · answered Jun 15 '11 at 11:56

You are passing the bytes returned to the BigInteger constructor. While the types match, I'm not sure what you want to accomplish here. From the BigInteger JavaDoc:

Translates a byte array containing the two's-complement binary representation of a BigInteger

score 0 · Answer 4 · answered Jun 15 '11 at 12:03

0

Don't re-invent the wheel, esp for cryptography -- use java.security.Signature or a higher-level library.

answered Jun 15 '11 at 12:03

jkraybill

3,339
27
32

SHA hash function gives a negative output

4 Answers4