Lua 5.1 does not yet support bitwise operators. The Lua environment I'm using is restricted and provides a bit32 library that allows bitwise operations with 32-bit numbers.
The issue is that I'm trying to backport an algorithm written in Lua 5.4 (poly1305), which you can find here: https://github.com/philanc/plc/blob/master/plc/poly1305.lua And this algorithm uses numbers larger than 32 bits, which makes the result incorrect in my environment.
You can find my backport of poly1305 https://pastebin.com/mfNhDqvw
I've done some research to perform bitwise operations using arithmetic, and I found functional wrappers, but they don't work with numbers larger than 32 bits. Would any of you be able to make them work with 64-bit numbers, or rewrite them completely if necessary?
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
================================================================================
EDIT:
Following the feedback, I would like to add some additional information. Since you're not certain that the algorithm only deals with 32-bit numbers, I have decided to monitor the bitshift operations to demonstrate otherwise. Here are the modifications made to capture the values used in the bitshift operations of this algorithm:
lshift = function(a,b) print("a=["..a.."] b=["..b.."] - a << b = ["..(a << b).."]") return a << b end;
rshift = function(a,b) print("a=["..a.."] b=["..b.."] - a >> b = ["..(a >> b).."]") return a >> b end;
Results on a standard 5.4 lua environnement with text=1234123412341234 and secret32B=12345678123456781234567812345678:
[1] a=[926299444] b=[2] - a >> b = [231574861]
[2] a=[842086455] b=[4] - a >> b = [52630403]
[3] a=[892613426] b=[6] - a >> b = [13947084]
[4] a=[943142453] b=[8] - a >> b = [3684150]
[5] a=[858927412] b=[2] - a >> b = [214731853]
[6] a=[842085427] b=[4] - a >> b = [52630339]
[7] a=[825504562] b=[6] - a >> b = [12898508]
[8] a=[875770417] b=[8] - a >> b = [3420978]
[9] a=[10084375459231865] b=[26] - a >> b = [150268904]
[10] a=[6482263059657534] b=[26] - a >> b = [96593246]
[11] a=[2170453620770289] b=[26] - a >> b = [32342279]
[12] a=[2440835001604485] b=[26] - a >> b = [36371275]
[13] a=[3412223033429668] b=[26] - a >> b = [50846085]
[14] a=[271497234] b=[26] - a >> b = [4]
[15] a=[50524994] b=[26] - a >> b = [0]
[16] a=[17909233] b=[26] - a >> b = [0]
[17] a=[54122885] b=[26] - a >> b = [0]
[18] a=[30232228] b=[26] - a >> b = [0]
[19] a=[3061778] b=[26] - a >> b = [0]
[20] a=[3061783] b=[26] - a >> b = [0]
[21] a=[50524994] b=[26] - a >> b = [0]
[22] a=[17909233] b=[26] - a >> b = [0]
[23] a=[54122885] b=[26] - a >> b = [0]
[24] a=[4258090660] b=[31] - a >> b = [1]
[25] a=[50524994] b=[26] - a << b = [3390674950946816]
[26] a=[50524994] b=[6] - a >> b = [789453]
[27] a=[17909233] b=[20] - a << b = [18779191902208]
[28] a=[17909233] b=[12] - a >> b = [4372]
[29] a=[54122885] b=[14] - a << b = [886749347840]
[30] a=[54122885] b=[18] - a >> b = [206]
[31] a=[30232228] b=[8] - a << b = [7739450368]
[32] a=[1013049923] b=[32] - a >> b = [0]
[33] a=[2538816002] b=[32] - a >> b = [0]
[34] a=[2861859653] b=[32] - a >> b = [0]
[35] a=[1013049923] b=[8] - a >> b = [3957226]
[36] a=[3957226] b=[8] - a >> b = [15457]
[37] a=[15457] b=[8] - a >> b = [60]
[38] a=[60] b=[8] - a >> b = [0]
[39] a=[2538816002] b=[8] - a >> b = [9917250]
[40] a=[9917250] b=[8] - a >> b = [38739]
[41] a=[38739] b=[8] - a >> b = [151]
[42] a=[151] b=[8] - a >> b = [0]
[43] a=[2861859653] b=[8] - a >> b = [11179139]
[44] a=[11179139] b=[8] - a >> b = [43668]
[45] a=[43668] b=[8] - a >> b = [170]
[46] a=[170] b=[8] - a >> b = [0]
[47] a=[92658435] b=[8] - a >> b = [361947]
[48] a=[361947] b=[8] - a >> b = [1413]
[49] a=[1413] b=[8] - a >> b = [5]
[50] a=[5] b=[8] - a >> b = [0]
Inputs on my restricted env are the same, but the results mismatch on large numbers e.g 10084375459231865. I guess it overflows ?
============================ EDIT2
Results on my restricted environnement:
[1] a=[926299444] b=[2] - a >> b = [231574861]
[2] a=[842086455] b=[4] - a >> b = [52630403]
[3] a=[892613426] b=[6] - a >> b = [13947084]
[4] a=[943142453] b=[8] - a >> b = [3684150]
[5] a=[858927412] b=[2] - a >> b = [214731853]
[6] a=[842085427] b=[4] - a >> b = [52630339]
[7] a=[825504562] b=[6] - a >> b = [12898508]
[8] a=[875770417] b=[8] - a >> b = [3420978]
[9] a=[1.0084375459232e+16] b=[26] - a >> b = [40]
[10] a=[6.4822629093887e+15] b=[26] - a >> b = [28]
[11] a=[2.1704535241771e+15] b=[26] - a >> b = [5]
[12] a=[2.4408349692622e+15] b=[26] - a >> b = [11]
[13] a=[3.4122229970584e+15] b=[26] - a >> b = [4]
[14] a=[17266828] b=[26] - a >> b = [0]
[15] a=[34473854] b=[26] - a >> b = [0]
[16] a=[55533743] b=[26] - a >> b = [0]
[17] a=[21780611] b=[26] - a >> b = [0]
[18] a=[60969828] b=[26] - a >> b = [0]
[19] a=[17266828] b=[26] - a >> b = [0]
[20] a=[17266833] b=[26] - a >> b = [0]
[21] a=[34473854] b=[26] - a >> b = [0]
[22] a=[55533743] b=[26] - a >> b = [0]
[23] a=[21780611] b=[26] - a >> b = [0]
[24] a=[4288828260] b=[31] - a >> b = [1]
[25] a=[34473854] b=[26] - a << b = [4160749568]
[26] a=[34473854] b=[6] - a >> b = [538653]
[27] a=[55533743] b=[20] - a << b = [183500800]
[28] a=[55533743] b=[12] - a >> b = [13558]
[29] a=[21780611] b=[14] - a << b = [371245056]
[30] a=[21780611] b=[18] - a >> b = [83]
[31] a=[60969828] b=[8] - a << b = [2723374080]
[32] a=[5053786813] b=[32] - a >> b = [758819517]
[33] a=[1886001423] b=[32] - a >> b = [1886001423]
[34] a=[3133030454] b=[32] - a >> b = [3133030454]
[35] a=[758819517] b=[8] - a >> b = [2964138]
[36] a=[2964138] b=[8] - a >> b = [11578]
[37] a=[11578] b=[8] - a >> b = [45]
[38] a=[45] b=[8] - a >> b = [0]
[39] a=[1886001423] b=[8] - a >> b = [7367193]
[40] a=[7367193] b=[8] - a >> b = [28778]
[41] a=[28778] b=[8] - a >> b = [112]
[42] a=[112] b=[8] - a >> b = [0]
[43] a=[3133030454] b=[8] - a >> b = [12238400]
[44] a=[12238400] b=[8] - a >> b = [47806]
[45] a=[47806] b=[8] - a >> b = [186]
[46] a=[186] b=[8] - a >> b = [0]
[47] a=[2504579774] b=[8] - a >> b = [9783514]
[48] a=[9783514] b=[8] - a >> b = [38216]
[49] a=[38216] b=[8] - a >> b = [149]
[50] a=[149] b=[8] - a >> b = [0]
As you can see, bitshift results are incorrect on large numbers
================= EDIT 3
As you can see on both outputs line 9
- On lua 5.4:
[9] a=[10084375459231865] b=[26] - a >> b = [150268904] - On lua 5.1:
[9] a=[1.0084375459232e+16] b=[26] - a >> b = [40]
On Lua 5.1, a double conversion is done, losing precision. On Lua 5.4, the number is kept as a long number keeping the precision.
So for Lua 5.1 we actually have 10084375459232000 which is incorrect, as it should be 10084375459231865 (last 3 digits wiped and replaced by 0, and rounded)
Any idea to prevent this ?
============ EDIT 4
Still, print(10084375459232000 >> 26) on Lua 5.4 does 150268904 and not 40, so it's not even related to precision. But more likely an issue with doubles ? I'm a bit confused now