Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- --------------------------------------------------------------------------------------------
- -- LUA Big Number Library
- -- Created by Jayden Koedijk (elcius@gmail.com)
- -- Inspired by the works of Frederico Macedo Pessoa and Marco Serpa Molinaro.
- -- 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.
- --------------------------------------------------------------------------------------------
- --[[
- -- 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 = 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(a,disp) -- Lua5.2 insipred
- if disp < 0 then return lshift(a,-disp) end
- return math.floor(a % MOD / 2^disp)
- end
- local function lshift(a,disp) -- Lua5.2 inspired
- if disp < 0 then return rshift(a,-disp) end
- return (a * 2^disp) % MOD
- 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
- --------------------------------------------------------------------------------------------
- -- LUA Digital Signature Algorithm Library
- -- Created by Jayden Koedijk (elcius@gmail.com)
- -- http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
- -- Uses the (Big Number) BN library for calculations.
- -- Uses sha256 for hashing.
- --------------------------------------------------------------------------------------------
- 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,
- }
- local BN = BN;
- 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(this)
- -- values generated using OpenSSL
- local key = { -- public key
- q = this.BN.fromHex("e12271ec020adfe604bceafa55610a000f1f6c9f"),
- p = this.BN.fromHex("b53316faa1f842a44bebefa177674cb6cde6ba7894f33eff55522a73cbdb4b6390789dcb6b305c5970939e7c041859e7fd411ab747803663f8b94110ecb86b4b"),
- g = this.BN.fromHex("3f9b423021dc91663693a48f38c84d3986ccfd0a0c91ec578e83806275f07db1cae9170190b5d739863f7af1a7c38f381b53e7ef75be08d38eab3de5d61a8f88"),
- y = this.BN.fromHex("9341ba0b2aaa9a1e8d9dd1f5f58d83dd1b9fbaab39a026dbbe1e746ced9d1468c244e9e512353fe5909a3b1adb109c46c408780405a7711773047c2d85d6aa10")
- };
- local msg = "hello world";
- -- yeild
- -- sleep(0)
- -- validate test
- local sig = {
- r = this.BN.fromHex("3bde3048d29076582dba3db7c72a242934aacf61"),
- s = this.BN.fromHex("813d6cd6e2196f029ccc19054c3f18ccd4201c40")
- };
- print("Pregenerated Signature Result: ", this.Validate(key,sig,msg));
- -- sign test
- local x = this.BN.fromHex("3fa4d6629e2688807b87eddb93c601e71eb5dbf9"); -- private key
- local sig,err = this.Sign(key,x,msg);
- print("Signature Generation: ", err or "okay.");
- -- yeild
- sleep(0)
- print("Generated Signature Result: ", this.Validate(key,sig,msg));
- end,
- BN = BN,
- }
- return LibDSA
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement