For those who understand El Gamal signature scheme . U may have known the verification process of the signature :

y^a *a^b (mod p ) = g^M (mod p)

We have to compute both side of the equation. If they are equal, the signature is verified.

but i have issue computing g^M since M after MD5 hashing is a 128 bit number. IT seems g to the power of M is computational infeasible

!!!!!!!!!!!!!!!!

Any one have solution for it ?

Below is my code. the number are just taken as example:

package Server;

import java.math.*;

public class Checkup {

BigInteger left,right,

one=new BigInteger("1"),

p=new BigInteger("17"),

k=new BigInteger("11"),

g=new BigInteger("7"),

m,a,b,y,x;

int k1=k.intValue(),x1,a1,b1,m1,left1,right1;

public Checkup(String str,String xx){

m = new BigInteger(str,16);

x = new BigInteger(xx);

x1=x.intValue();

}

boolean Docheck(){

a=(g.pow(k1)).remainder(p);

y=(g.pow(x1)).remainder(p);

b=m.subtract(x.multiply(a)).divide(k).remainder(p. subtract(one));

a1=a.intValue();b1=b.intValue();m1=m.intValue();

left = y.pow(a1).multiply(a.pow(b1)).remainder(p);

right= g.pow(m1).remainder(p);

left1=left.intValue();

right1=right.intValue();

if(left1==right1)

return true;

return false;

}

}