local chars16 = "0123456789ABCDEF"
local chars64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
local sets, bsets = {[4]={},[6]={},[8]={}}, {[4]={},[6]={},[8]={}}
for i=1,16 do sets[4][i]=chars16:sub(i,i) bsets[4][sets[4][i]] = i bsets[4][sets[4][i]:lower()] = i end
for i=1,64 do sets[6][i]=chars64:sub(i,i) bsets[6][sets[6][i]] = i end
for i=1,256 do sets[8][i]=string.char(i-1) bsets[8][sets[8][i]] = i end
local function toString(bi, bits, nb)
    nb = nb or 4
    bits = bits or (#tostring(bi))*3.321928
    local base = 2^nb
    local str = ""
    for i=1,math.ceil(bits/nb) do
        str = sets[nb][tonumber(biginteger.band(bi, base-1)+1)] .. str
        bi = biginteger.shr(bi,nb)
    end
    return str
end
local function fromString(str, nb)
    nb = nb or 4
    local num = biginteger.new(0)
    for i=1,#str do
        num = biginteger.bor(biginteger.shl(num, nb), bsets[nb][str:sub(i,i)]-1)
    end
    return num
end
bigint = {
    serialise = toString,
    unserialise = fromString
}
--RSA
local keyindex = {
    pass = function(self, message)
        return biginteger.modpow(message,self.e,self.m)
    end,
    length = function(self)
        return self.bits
    end,
    serialise = function(self, base) -- base = 16, 64, 256
        if base~=256 and base~=64 and base~=16 then error("Base must be 16, 64 or 256",1) end
        local nb = math.log(base)/math.log(2)
        return (base==256 and "8" or (base==64 and "6" or "4")) ..
                toString(biginteger.new(math.log(self.bits)/math.log(2)),6,nb) ..
                toString(self.e,self.bits,nb) ..
                toString(self.m,self.bits*2,nb)
    end
}
local keymeta = {
    __index = keyindex,
    __tostring = function(self) return self:serialise(64) end
}
local function key(exponent, mod, length)
    return setmetatable({e = exponent, m = mod, bits = length}, keymeta)
end

rsa = {
    --[[    pub, pri = generateKeyPair(bits)
        Arguments:
            bits: numbers of bits to use for the keys, must be a power of 2
        Returns:
            public key object
            private key object
    ]]
    generateKeyPair = function(bits)
        if (math.log(bits)/math.log(2))%1 ~= 0 or bits<4 then error("Unsupported length", 1) end
        local p = biginteger.newProbPrime(bits)
        local q = biginteger.newProbPrime(bits)
        local n = p*q
        local t = (p-1)*(q-1)
        local e = biginteger.newProbPrime(bits)
        local d = biginteger.modinv(e,t)
        return key(e,n,bits), key(d,n,bits)
    end,
    unserialise = function(str)
        local nb = tonumber(str:sub(1,1)) str=str:sub(2)
        if nb~=8 and nb~=6 and nb~=4 then error("invalid input",1) end
        local lens = math.ceil(6/nb)
        local bits = 2^tonumber(fromString(str:sub(1,lens), nb)) str=str:sub(lens+1)
        local ln = math.ceil(bits/nb)
        local e = fromString(str:sub(1,ln), nb)
        local n = fromString(str:sub(ln+1), nb)
        return key(e,n,bits)
    end
}