5 replies to this topic

[Simon Prinz]

Hey guys,

currently I am working on a rsa api, but there is a little problem in the encryption part. The decryption is working fine. Here is my method:

function div(a,B)/>
  return (a-math.floor(a/B)/>*B)/>
end
function encrypt(key,m)
  local c = div(math.pow(m,key.e),key.n)
  return c
end

The example key is:

pub = {
  e = 101213,
  n = 108419
}
priv = {
  d = 54917,
  n = 108419
}

If I now want to encrypt 123 [ code: encrypt(pub,123) ], then i get "nan" as the output.

I am at an integer limit? i think the limit was at 2^52 ?

[valithor]

Simon Prinz, on 08 April 2015 - 02:41 AM, said:

Hey guys,

currently I am working on a rsa api, but there is a little problem in the encryption part. The decryption is working fine. Here is my method:

function div(a,B)/>/>/>
  return (a-math.floor(a/B)/>/>/>*B)/>/>/>
end
function encrypt(key,m)
  local c = div(math.pow(m,key.e),key.n)
  return c
end

The example key is:

pub = {
  e = 101213,
  n = 108419
}
priv = {
  d = 54917,
  n = 108419
}

If I now want to encrypt 123 [ code: encrypt(pub,123) ], then i get "nan" as the output.

I am at an integer limit? i think the limit was at 2^52 ?

Your problem is your numbers are becoming too large for CC to handle. Assuming I passed the correct things to the function encrypt you end up passing math.huge or inf to the div function. Subtracting math.huge from itself results in nan.

Edited by valithor, 08 April 2015 - 03:59 AM.

[HPWebcamAble]

Simon Prinz, on 08 April 2015 - 02:41 AM, said:

I am at an integer limit? i think the limit was at 2^52 ?

I can't remember the exact number, but its around there
(I googled it and its literally not documented anywhere)
Lets assume thats it


Your encrypt function:

function encrypt(key,m)
  local c = div(math.pow(m,key.e),key.n)
  return c
end

When you take m^key.e power, that is WAY over 2^52
Your example is m^101213 so...


Here's a working RSA Program (made by Anavrins)
http://pastebin.com/QJ4cEgMN

[Anavrins]

RSA is pretty much impossible in CCLua.
So far my program only generate a 60bits keypair which is nowhere near of something secure.
Plus the encrypt and decrypt operation takes forever even with those small keys.

Your best bet is to use the cryptographic accelerator from Immibis' Peripherals.

[Simon Prinz]

Thanks for your help.
So I am assuming that the aes encryption is a better solution.

But I've got one question on your code. Why are you taking a constant e instead of randomizing it?

[Anavrins]

Well because first of all that's the same constant stuff like OpenSSL and every other RSA implementation uses,
and 0x10001 having a short bit-length and small Hamming weight results in more efficient encryption.

e must also be carefully chosen, it must be higher than 1 and less than the totient of N
the greatest common divisor of e and the totient of N must also be 1.
Choosing a random e most likely won't follow those requirements.

And also, taken from Wikipedia

Quote

When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e., m < n1/e) the result of m*e is strictly less than the modulus n. In this case, ciphertexts can be easily decrypted by taking the eth root of the ciphertext over the integers.

AES would be a better solution as long as you use my fixed version of KillaVanilla's AES here.
But you are still stuck with the problem of sharing keys.
You could use the diffie-hellman key exchange which I also made a proof of concept here.
but again the small numbers makes it very unsecure.
Security is hard in CC

Edited by Anavrins, 09 April 2015 - 06:24 AM.