Search code examples
javaencryptionbigintegerdsapari

DSA Signature Verification and BigInteger class

I have been given a (very) simple DSA problem, and have already found the key and other variables. To verify the signature I need to somehow translate the equation:

V = [(y^u1*h^u2)mod p] mod q

into a BigInteger operation. Is this even possible on java? I have been using modPow successfully so far however all problems so far have been in the form:

r.modPow(exponent, modulus);

I have no idea how to do the above equation (in particular the bold part) via BigInteger and I'm wondering if it's even possible. Does anyone have any ideas?

How would I go about putting this equation through Pari if BigInteger can't do it?

Solution

  • I think you just need to use the identity that

    (a*b) mod p == ((a mod p)*(b mod p)) mod p

    So to calculate yu1 × hu2 mod p:

    1. calculate yu1 mod p, using modPow,
    2. calculate hu2 mod p, using modPow,
    3. multiply together the results of steps 1 and 2,
    4. reduce the result of step 3 mod p.

    Step 4 is necessary because the results of steps 1 and 2 may multiply together to produce a value greater than p.