When running the rsaKeygen() function, the key it makes is always length 19, and increasing the size of the p and q generation ranges causes the program to hang. Code:
function rsaKeygen()
p = math.random(50000,100000)
while not isprime(p) do
p = math.random(1,1000)
end
q = math.random(1,1000)
while not isprime(q) do
q = math.random(50000,100000)
end
local n = p*q
totientN = carmichael(n)
e = 2^16+1
local d = 1%totientN/e
p,q,totientN = nil,nil,nil
return e,d,n
end
I have tried to increase the ranges for p and q, however that causes the program to hang, and in my pkcs1_v1_5_pad(message,key_size) function, 19 is not a long enough key to work for any reasonable-sized plaintext. pkcs function:
function pkcs1_v1_5_pad(message,key_size)
print(key_size)
local block_size = key_size/8
local message_length = #message
local padding_length = block_size - message_length - 3
if padding_length < 0 then
error("Message is too long for the given key size")
end
local padding = string.rep("\x00",padding_length)
local padded_message = string.char(0x00)..string.char(0x02)..padding..string.char(0x00)..message
return padded_message
end
Lua seems to generally use 64 bit numbers, way too small for something like RSA. note that 63 bits means about 19 digits. This means that you need to use a BigInt library or a cryptographic library. If you look at this RSA lib you see that most of the code is devoted to implementing bigint operations. Beware that it is unlikely that such code is resistant against e.g. side channel attacks.
When going over 63 bits you will get into weird situations as basically all ops are modulus 2^64 and interpreted as signed 2-complement numbers. This could be cause of the long wait.
The other possible reason is of course that the isprime function is not efficiently implemented. This can even be slow on native systems for large enough key sizes.
I'd also try and count up from a specific random value, otherwise your RNG will continuously be asked for new random values to test. Random number generation is relatively slow compared to checking if a possibly even number is prime.
This is not really something that Lua has been designed for; it makes more sense to call a function within OpenSSL for RSA operations.