here is a signature validation implementation for DSA i wrote years ago, it's joke math.
-- validate a signature
Validate = function(key,sig,msg)
local q,p,g,y = key.q, key.p, key.g, key.y;
local r,s = sig.r, sig.s;
if not ( q and p and g and y and r and s and type(msg) == "string" ) then
return false,"Invalid Input.";
elseif not Sha256 then
return false,"Hash function unavailable 'Sha256'.";
end
-- 0 < r < q, 0 < s < q
local temp = BN.new("0");
if BN.eqAbs(r,temp) ~= 1 or BN.eq(r,q) ~= -1
or BN.eqAbs(s,temp) ~= 1 or BN.eq(s,q) ~= -1 then
return false,"Signature out of range.";
end
-- w = s^-1 % q
local w = BN.modInverse(s,q);
-- u1 = H(m)*w % q
local m = BN.fromHex( Sha256(msg):sub(0,40) ); -- H(m)
local u1 = BN.new("0");
BN.mul( m, w, temp )
BN.div( temp, q, nil, u1 );
-- u2 = r*w % q
local u2 = BN.new("0");
BN.mul( r, w, temp );
BN.div( temp, q, nil, u2 );
-- ((g^u1*g^u2)%p)%q == (((g^u1%q)*(y^u2%q))%p)%q
-- these two operations are about 80% of the work
local gu1 = BN.mpow(g,u1,p); -- (g^u1%q)
local yu2 = BN.mpow(y,u2,p); -- (y^u2%q)
local v = BN.new("0");
BN.mul( gu1, yu2, v ); -- gu1*yu2
BN.div( v, p, nil, temp ); -- %p
BN.div( temp, q, nil, v ); -- %q
return BN.eq(v,r) == 0;
end,