DSA for Lua 5.1

LibDSA.lua

--------------------------------------------------------------------------------------------
--	LUA Big Number Library
--		Created by Jayden Koedijk ([email protected])
--		Inspired by the works of Frederico Macedo Pessoa and Marco Serpa Molinaro.
--              Made for Lua 5.1 by Jared Allard <[email protected]>
--	Heavly optimised for the LUA implementation in World of Warcraft, minimizing
--	table creation/seeks and the use of external variables.
--	Numbers are stored as tables containing words of [radix length] decimal digits.
--	[0] being the most significant, [n-1] being the least: 1234567890 = {[0]=123,4567890}.
--	["n"] stores the length of the number, words in indexes >= n may contain zeros, all
--	words are stored as primitive type number.
--	["neg"] indicates if the value is negative, true for negative false for positive, this
--	field should not be nil.
--------------------------------------------------------------------------------------------
BN = {
	RL = 7, -- radix length
	R = 10^7, -- radix

	-- create a new BN (big number)
	new = function(v)
		local neg = string.find(v,"-")==1
		v = v:gsub("[^%d]",""):gsub("^0+","");
		local num = {n=math.ceil(string.len(v)/BN.RL), neg = neg};
		for i = 0,num.n-1 do
			num[i] = tonumber( v:sub( 0-((i+1)*BN.RL), -1-(i*BN.RL) ) );
		end
		return num;
	end,
	fromHex = function(h)
		local result = BN.new("0");
		local temp = BN.new("0");
		for i = 1, string.len(h) do
			BN.smul( result, 16, temp );
			BN.add( {n=1,neg=false,[0]=tonumber( h:sub(i, i), 16 )}, temp, result );
		end
		return result;
	end,

	-- adds a and b into c
	add = function(a,b,c)
		if a.neg ~= b.neg then --[ x+-y == x-y ]
			if a.neg then a,b = b,a; end -- move negative number to b
			b.neg = false; -- flag b as positive
			BN.sub(a,b,c); -- subtract positives
			if b ~= c then b.neg = true; end -- revert flag if b is not a pointer to c.
			return;
		end
		-- actual addition
		local radix = BN.R;
		local carry = 0;
		local n = math.max(a.n,b.n);
		for i = 0, n-1 do
			local s = (a[i] or 0) + (b[i] or 0) + carry;
			if s >= radix then
				s = s - radix;
				carry = 1;
			else
				carry = 0;
			end
			c[i] = s;
		end
		if carry == 1 then
			c[n] = 1;
			c.n = n+1;
		else
			c.n = n;
		end
		c.neg = a.neg;
	end,

	-- subtracts b from a into c
	sub = function(a,b,c)
		if a.neg ~= b.neg then --[ x--y == x+y && -x-y == -(x+y) ]
			local neg = a.neg; -- used to restore flags
			a.neg = false;
			b.neg = false;
			BN.add(a,b,c);
			a.neg = neg; -- revert flags
			b.neg = not neg;
			c.neg = neg;
		elseif a.neg then -- both negative --[ -x--y == y-x ]
			a.neg = false;
			b.neg = false;
			BN.sub(b,a,c);
			if a ~= c then a.neg = true; end -- revert flags
			if b ~= c then b.neg = true; end
		elseif BN.eqAbs(a,b) == -1 then --[ x-y == -(y-x) when y>x ]
			BN.sub(b,a,c);
			c.neg = true;
		else -- a > b, both numbers are positive
			-- actual subtraction
			local radix = BN.R;
			local carry = 0;
			local n;
			for i = 0, a.n-1 do
				local s = (a[i] or 0) - (b[i] or 0) - carry;
				if s < 0 then
					s = radix + s;
					carry = 1;
				else
					carry = 0;
				end
				if s ~= 0 then n = i+1; end
				c[i] = s;
			end
			if not n then -- zero/empty answer
				n = 1;
				c[1] = 0;
			end
			c.n = n;
			c.neg = false;
			-- clear un-used values
			while c[n+1] do
				n = n+1;
				c[n] = nil;
			end
		end
	end,

	-- multiplies a nd b into c
	mul = function(a,b,c)
		--assert( c ~= a and c ~= b ); -- c gets cleared and can not reference an input
		if a.neg ~= b.neg then -- [-a*b == -(a*b)]
			if a.neg then a,b = b,a; end -- move negative number to b
			b.neg = false; -- flag b as positive
			BN.mul(a,b,c); -- multiply positives
			b.neg = true; -- revert flag
			c.neg = true; -- flag c as negative
			return;
		end
		-- actual multiplication
		local radix = BN.R;
		c.neg = false;
		local carry = 0;
		local an = a.n;
		local bn = b.n;
		local fmod = math.fmod;
		for i = 0, (an+bn)-1 do c[i] = 0; end -- clear and zero fill c
		for i = 0, an-1 do
			local ai = a[i];
			for j = 0, bn-1 do
				carry = ( ai * b[j] + carry ) + c[i+j];
				c[i+j] = fmod( carry, radix );
				carry = math.floor( carry / radix );
			end
			if carry ~= 0 then
				c[i+bn] = carry;
				carry = 0;
			end
		end
		-- update n for c, also clear zeros
		for i = (an+bn)-1, 0, -1 do
			if c[i] ~= 0 then
				c.n = i+1;
				return;
			else
				c[i] = nil;
			end
		end
		if not c[0] then
			c[0] = 0;
		end
	end,

	-- equivalent to a = b*(BN.R^n)
	put = function(a,b,n)
		for i = 0, n-1 do a[i] = 0; end
		for i = n+1, a.n do a[i] = nil; end
		a[n] = b;
		a.n = n;
	end,

	-- divide
	div = function(a,b,c,d)
		--assert( a ~= c and a ~= d and b ~= c and b ~= d and c ~= d );
		-- actual division
		local radix = BN.R;
		local temp1 = {n=1,neg=false};
		local temp2 = {n=1,neg=false};
		if not c then c = {}; end
		if not d then d = {}; end
		for i = 0, c.n or 0 do c[i] = nil; end -- clear c
		for i = 0, a.n do d[i] = a[i]; end -- copy a into d
		c.n = 1;
		d.n = a.n;
		c.neg = false;
		d.neg = false;

		while BN.eqAbs( d, b ) ~= -1 do
			if d[d.n-1] >= b[b.n-1] then
				BN.put( temp1, math.floor( d[d.n-1] / b[b.n-1] ), d.n-b.n );
				temp1.n = d.n-b.n + 1 ;
			else
				BN.put( temp1, math.floor( ( d[d.n - 1] * radix + d[d.n - 2] ) / b[b.n -1] ) , d.n-b.n - 1 ) ;
				temp1.n = d.n-b.n;
			end
			temp1.neg = d.neg;
			BN.add( temp1, c, c );
			BN.mul( temp1, b, temp2 );
			temp2.neg = temp1.neg;
			BN.sub( d, temp2, d );
		end

		if d.neg then
			c[c.n-1] = c[c.n-1]-1; -- decr c
			BN.add( b, d, d );
		end

		-- adjustments
		if a.neg and d.neg then -- remainder is negative
			c[c.n-1] = c[c.n-1]+1; -- inc c
			if b.neg then
				b.neg = false;
				BN.sub( b, d, d );
				b.neg = true;
			else
				BN.sub( b, d, d );
			end
		end
		if a.neg ~= b.neg then --[ a/-b | -a/b == -(a/b) ]
			c.neg = true;
		end
		if not c[0] then c[0] = 0; end
	end,

	-- small divide, faster than normal div, (returns remainder as number)
	sdiv = function(a,b,c)
		local radix = BN.R;
		local carry = 0;
		for i = a.n, c.n-1 do c[i] = nil; end -- clear c
		c.n = a.n;
		for i = a.n-1, 0, -1 do
			c[i] = (a[i]/b) + (carry*radix);
			carry = c[i]%1;
			c[i] = math.floor(c[i]);
			if c[i] == 0 then
				c.n = c.n-1;
			end
		end
		return math.floor(0.5+(carry*b));
	end,

	-- small multiplication
	smul = function(a,b,c)
		local radix = BN.R;
		local carry = 0;
		for i = a.n, c.n-1 do c[i] = nil; end -- clear c
		for i = 0, a.n-1 do
			c[i] = (a[i]*b)+carry
			carry = math.floor(c[i]/radix);
			c[i] = c[i]%radix;
		end
		if carry ~= 0 then
			c[a.n] = carry;
			c.n = a.n + 1;
		else
			c.n = a.n;
		end
	end,

	-- modular exponentiation, (b^e)%m
	-- TODO: replace divide's with dedicated modulo's
	mpow = function(b,e,m)
		local result = BN.new("1");
		e = BN.copy(e,BN.new("0"));
		local base = {n=0};
		BN.copy(b,base);
		local temp = BN.new("0");
		while e[0] ~= 0 or e.n > 1 do -- e != 0
			if BN.sdiv( e, 2, e ) == 1 then
				BN.mul( result, base, temp );
				BN.div( temp, m, nil, result );
			end
			BN.mul( base, base, temp );
			BN.div( temp, m, nil, base );
		end
		return result;
	end,

	-- modular multiplicative inverse, fips_186-3, C.1
	modInverse = function(z,a)
		local i = BN.copy(a,BN.new("0"));
		local j = BN.copy(z,BN.new("0"));
		local y1 = BN.new("1");
		local y2 = BN.new("0");
		local r = BN.new("0");
		local q = BN.new("0");
		local y = BN.new("0");
		while j[0] > 0 or j.n > 1 do
			BN.div(i,j,q,r);
			BN.mul(y1,q,y);
			BN.sub(y2,y,y);
			BN.copy(j,i);
			BN.copy(r,j);
			BN.copy(y1,y2);
			BN.copy(y,y1);
		end
		if y2.neg or ( y2[0] == 0 and y2.n == 1 ) then
			BN.add(y2,a,y2);
		end
		return y2;
	end,

	-- -1 = a<b, 0 = a==b, 1 = a>b
	eq = function(a,b)
		if a.neg ~= b.neg then return b.neg and 1 or -1; end -- positive > negative
		if a.neg then return BN.eqAbs(a,b) * -1; end -- both negative so inverse
		return BN.eqAbs(a,b); -- both positive
	end,
	eqAbs = function(a,b)
		if a == b then return 0; end -- same object
		if a.n ~= b.n then return ( a.n > b.n ) and 1 or -1; end
		for i = a.n-1, 0, -1 do
			if a[i] ~= b[i] then return ( a[i] > b[i] ) and 1 or -1; end
		end
		return 0;
	end,

	-- copys a into b
	copy = function(a,b)
		for i = 0, math.max(a.n,b.n)-1 do
			b[i] = a[i];
		end
		b.n = a.n;
		b.neg = a.neg;
		return b;
	end,

	--[[ Unneeded/debugging functions
	-- Bitwise operations
	rshift = function( a, n, b ) BN.sdiv( a, 2^n, b or a ); end,
	lshift = function( a, n, b ) BN.smul( a, 2^n, b or a ); end,
	numBits = function(a)
		local n = 1;
		local two = BN.new("2");
		local temp = BN.new("0");
		local b = BN.new("1");
		while BN.eqAbs(a,b) == -1 do
			BN.mul(b,two,temp);
			BN.copy(temp,b);
		end
		return n;
	end,
	-- Print
	toString = function(a)
		if type(a) ~= "table" then return tostring(a); end
		if a[0] == 0 and a.n == 1 then return "0"; end
		local str = "";
		for i = 0, a.n-1 do
			str = strrep("0",BN.RL-string.len(a[i] or ""))..(a[i] or "")..str;
		end
		return (a.neg and "-" or "")..(str:gsub("^0*",""));
	end,
	--]]
}
local BN = BN;


--
--  Adaptation of the Secure Hashing Algorithm (SHA-244/256)
--  Found Here: http://lua-users.org/wiki/SecureHashAlgorithm
--
--  Using an adapted version of the bit library
--  Found Here: https://bitbucket.org/Boolsheet/bslf/src/1ee664885805/bit.lua
--

local MOD = 2^32
local MODM = MOD-1

local function memoize(f)
	local mt = {}
	local t = setmetatable({}, mt)
	function mt:__index(k)
		local v = f(k)
		t[k] = v
		return v
	end
	return t
end

local function make_bitop_uncached(t, m)
	local function bitop(a, b)
		local res,p = 0,1
		while a ~= 0 and b ~= 0 do
			local am, bm = a % m, b % m
			res = res + t[am][bm] * p
			a = (a - am) / m
			b = (b - bm) / m
			p = p*m
		end
		res = res + (a + b) * p
		return res
	end
	return bitop
end

local function make_bitop(t)
	local op1 = make_bitop_uncached(t,2^1)
	local op2 = memoize(function(a) return memoize(function(b) return op1(a, b) end) end)
	return make_bitop_uncached(op2, 2 ^ (t.n or 1))
end

local bxor1 = make_bitop({[0] = {[0] = 0,[1] = 1}, [1] = {[0] = 1, [1] = 0}, n = 4})

local function bxor(a, b, c, ...)
	local z = nil
	if b then
		a = a % MOD
		b = b % MOD
		z = bxor1(a, b)
		if c then z = bxor(z, c, ...) end
		return z
	elseif a then return a % MOD
	else return 0 end
end

local function band(a, b, c, ...)
	local z
	if b then
		a = a % MOD
		b = b % MOD
		z = ((a + b) - bxor1(a,b)) / 2
		if c then z = bit32_band(z, c, ...) end
		return z
	elseif a then return a % MOD
	else return MODM end
end

local function bnot(x) return (-1 - x) % MOD end

local function rshift1(a, disp)
	if disp < 0 then return lshift(a,-disp) end
	return math.floor(a % 2 ^ 32 / 2 ^ disp)
end

local function rshift(x, disp)
	if disp > 31 or disp < -31 then return 0 end
	return rshift1(x % MOD, disp)
end

local function lshift(a, disp)
	if disp < 0 then return rshift(a,-disp) end
	return (a * 2 ^ disp) % 2 ^ 32
end

local function rrotate(x, disp)
    x = x % MOD
    disp = disp % 32
    local low = band(x, 2 ^ disp - 1)
    return rshift(x, disp) + lshift(low, 32 - disp)
end

local k = {
	0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
	0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
	0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
	0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
	0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
	0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
	0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
	0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
	0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
	0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
	0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
	0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
	0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
	0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
	0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
	0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
}

local function str2hexa(s)
	return (string.gsub(s, ".", function(c) return string.format("%02x", string.byte(c)) end))
end

local function num2s(l, n)
	local s = ""
	for i = 1, n do
		local rem = l % 256
		s = string.char(rem) .. s
		l = (l - rem) / 256
	end
	return s
end

local function s232num(s, i)
	local n = 0
	for i = i, i + 3 do n = n*256 + string.byte(s, i) end
	return n
end

local function preproc(msg, len)
	local extra = 64 - ((len + 9) % 64)
	len = num2s(8 * len, 8)
	msg = msg .. "\128" .. string.rep("\0", extra) .. len
	assert(#msg % 64 == 0)
	return msg
end

local function initH256(H)
	H[1] = 0x6a09e667
	H[2] = 0xbb67ae85
	H[3] = 0x3c6ef372
	H[4] = 0xa54ff53a
	H[5] = 0x510e527f
	H[6] = 0x9b05688c
	H[7] = 0x1f83d9ab
	H[8] = 0x5be0cd19
	return H
end

local function digestblock(msg, i, H)
	local w = {}
	for j = 1, 16 do w[j] = s232num(msg, i + (j - 1)*4) end
	for j = 17, 64 do
		local v = w[j - 15]
		local s0 = bxor(rrotate(v, 7), rrotate(v, 18), rshift(v, 3))
		v = w[j - 2]
		w[j] = w[j - 16] + s0 + w[j - 7] + bxor(rrotate(v, 17), rrotate(v, 19), rshift(v, 10))
	end

	local a, b, c, d, e, f, g, h = H[1], H[2], H[3], H[4], H[5], H[6], H[7], H[8]
	for i = 1, 64 do
		local s0 = bxor(rrotate(a, 2), rrotate(a, 13), rrotate(a, 22))
		local maj = bxor(band(a, b), band(a, c), band(b, c))
		local t2 = s0 + maj
		local s1 = bxor(rrotate(e, 6), rrotate(e, 11), rrotate(e, 25))
		local ch = bxor (band(e, f), band(bnot(e), g))
		local t1 = h + s1 + ch + k[i] + w[i]
		h, g, f, e, d, c, b, a = g, f, e, d + t1, c, b, a, t1 + t2
	end

	H[1] = band(H[1] + a)
	H[2] = band(H[2] + b)
	H[3] = band(H[3] + c)
	H[4] = band(H[4] + d)
	H[5] = band(H[5] + e)
	H[6] = band(H[6] + f)
	H[7] = band(H[7] + g)
	H[8] = band(H[8] + h)
end

local function sha256(msg)
	msg = preproc(msg, #msg)
	local H = initH256({})
	for i = 1, #msg, 64 do digestblock(msg, i, H) end
	return str2hexa(num2s(H[1], 4) .. num2s(H[2], 4) .. num2s(H[3], 4) .. num2s(H[4], 4) ..
		num2s(H[5], 4) .. num2s(H[6], 4) .. num2s(H[7], 4) .. num2s(H[8], 4))
end

--------------------------------------------------------------------------------------------
--	http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
--	Uses the (Big Number) BN library for calculations.
--	Uses sha256 for hashing.
--------------------------------------------------------------------------------------------
LibDSA = {

	-- 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 first 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,

	-- generate a signature
	-- this function is not needed by users and should not be packaged
	Sign = function(key,x,msg)
		local q,p,g,y = key.q, key.p, key.g, key.y;
		if not ( q and p and g and y and x and type(msg) == "string" ) then
			return false,"Invalid Input.";
		end

		local r = BN.new("0");
		local s = BN.new("0");
		local m = BN.fromHex( sha256(msg):sub(0,40) ); -- H(m)
		local temp1 = BN.new("0");
		local temp2 = BN.new("0");

		repeat
			-- seed k
			local k = BN.new((math.random()..math.random()..math.random()):gsub("0%.",""));
			-- (g^k %p)%q
			temp1 = BN.mpow( g, k, p );
			BN.div( temp1, q, nil, r );

			-- restart if r is 0
			if r[0] ~= 0 or s.n >= 1 then
				-- (k^-1) * (H(m) + x*r) % q
				k = BN.modInverse(k,q); -- k^-1%q
				BN.mul( x, r, temp1 ); -- x*r
				BN.div( temp1, q, nil, temp2 ); -- (x*r)%q
				BN.add( m, temp2, temp2 ); -- m+((x*r)%q)
				BN.mul( k, temp2, temp1 ); -- (k^-1%q)*(m+((x*r)%q))
				BN.div( temp1, q, nil, s ); -- s = ((k^-1%q)*(m+((x*r)%q)))%q
			end
		until s[0] ~= 0 or s.n >= 1; -- restart if s is 0

		return {r=r,s=s};
	end,
}

--------------------------------------------------------------------------------------------
-- Test
--------------------------------------------------------------------------------------------

function DSA_test()
	-- values generated using OpenSSL
	local key = { -- public key
		q = BN.fromHex("e12271ec020adfe604bceafa55610a000f1f6c9f"),
		p = BN.fromHex("b53316faa1f842a44bebefa177674cb6cde6ba7894f33eff55522a73cbdb4b6390789dcb6b305c5970939e7c041859e7fd411ab747803663f8b94110ecb86b4b"),
		g = BN.fromHex("3f9b423021dc91663693a48f38c84d3986ccfd0a0c91ec578e83806275f07db1cae9170190b5d739863f7af1a7c38f381b53e7ef75be08d38eab3de5d61a8f88"),
		y = BN.fromHex("9341ba0b2aaa9a1e8d9dd1f5f58d83dd1b9fbaab39a026dbbe1e746ced9d1468c244e9e512353fe5909a3b1adb109c46c408780405a7711773047c2d85d6aa10")
	};
	local msg = "hello world";

	-- validate test
	local sig = {
		r = BN.fromHex("3bde3048d29076582dba3db7c72a242934aacf61"),
		s = BN.fromHex("813d6cd6e2196f029ccc19054c3f18ccd4201c40")
	};
	print("Pregenerated Signature Result: ",LibDSA.Validate(key,sig,msg));

	-- sign test
	local x = BN.fromHex("3fa4d6629e2688807b87eddb93c601e71eb5dbf9"); -- private key
	local sig,err = LibDSA.Sign(key,x,msg);
	print("Signature Generation: ", err or "okay.");
	print("Generated Signature Result: ",LibDSA.Validate(key,sig,msg));
end

DSA_test()

return LibDSA

Any particular reason you removed the original author names ?
-- Created by Jayden Koedijk ([email protected])
-- Inspired by the works of Frederico Macedo Pessoa and Marco Serpa Molinaro.
-- Made for Lua 5.1 by RainbowDashDC [email protected]

@mooreatv Not 100% sure what happened to the first two lines (this was awhile ago...), but the 3rd line is me (name change). RainbowDashDC was my old alias I no longer go under.

EDIT: Looking at the revision history, I removed it for whatever reason. Hm.