aase69
|
  |
| Joined: 04 Apr 2008 |
| Total Posts: 3794 |
|
|
| 08 Mar 2014 04:03 PM |
Hi guys. I'm trying to script a RSA encrypter/decrypter. To do this I give every letter in the alphabet a number (A=1,B=2,C=3......), and I have some "keys" that I use for this encryption. I call them e, n and d.
e=13 n=1147 d=997
with these keys, I can encrypt and decrypt letters. If I want to encrypt the letter E (5), I use the following:
5^e (Mod n) = 5^13 (Mod 1147) = 346 (Mod 1147)
This gives me the key 346. To decrypt this key, I use the following:
346^d (Mod n) = 346^997 (Mod 1147) = 5 (Mod 1147)
This gives me the number 5, which equals the fifth letter in the alphabet, "E". As you can see, this will do math with VERY big values, which leads me to my problem.
I made a script to do this encryption. It works very well with letters up to "J" (the 10th letter in the alphabet). This is where it goes wrong. Almost every letter after "J" gives a wrong encryption key. This leaves me wondering why does this happen?
I believe the reason is the ridiculously high values Lua is working with. Is high number computing a common issue with Lua ? |
|
|
| Report Abuse |
|
|
mew903
|
  |
| Joined: 03 Aug 2008 |
| Total Posts: 22071 |
|
|
| 08 Mar 2014 04:29 PM |
| The highest number you can get before reaching INF is 2^1023.(insert endless 9s here), if that's what you're asking |
|
|
| Report Abuse |
|
|
aase69
|
  |
| Joined: 04 Apr 2008 |
| Total Posts: 3794 |
|
|
| 08 Mar 2014 04:51 PM |
I think I found why my script had problems. It seems like a number can have a maximum amount of digits in Lua. This will cause huge numbers with many digits to show less decimals, which clearly ruins my script, because I need as many decimals as possible for my encryption to work. I should probably program this in another scripting/programming language.
Thanks for trying to help, anyway! :-) |
|
|
| Report Abuse |
|
|
mew903
|
  |
| Joined: 03 Aug 2008 |
| Total Posts: 22071 |
|
|
| 08 Mar 2014 05:24 PM |
| I wasnt sure what you were asking specifically so I stated what I knew about the situation, so no problemo |
|
|
| Report Abuse |
|
|
|
| 08 Mar 2014 05:37 PM |
Isn't math.huge the biggest number possible?
"Good morning. You have been in suspension for nine nine nine nine nine..." |
|
|
| Report Abuse |
|
|
DrHaximus
|
  |
| Joined: 22 Nov 2011 |
| Total Posts: 8410 |
|
|
| 08 Mar 2014 05:49 PM |
"Isn't math.huge the biggest number possible?"
math.huge+1 |
|
|
| Report Abuse |
|
|
mew903
|
  |
| Joined: 03 Aug 2008 |
| Total Posts: 22071 |
|
|
| 08 Mar 2014 05:50 PM |
@nikola
yes
print(math.huge==2^1024) >true
2^1024 is as high as you can get |
|
|
| Report Abuse |
|
|
Devoi
|
  |
| Joined: 09 Jun 2013 |
| Total Posts: 5387 |
|
| |
|
DrHaximus
|
  |
| Joined: 22 Nov 2011 |
| Total Posts: 8410 |
|
|
| 08 Mar 2014 05:52 PM |
@mew903
2^1025
moron learn math |
|
|
| Report Abuse |
|
|
|
| 08 Mar 2014 06:08 PM |
| They have no problem with high numbers. They have problems against high numbers. |
|
|
| Report Abuse |
|
|
|
| 08 Mar 2014 06:52 PM |
@DrHax
omgomgomgomg haxxxxx |
|
|
| Report Abuse |
|
|
mathchamp
|
  |
| Joined: 22 Oct 2007 |
| Total Posts: 320 |
|
|
| 08 Mar 2014 07:09 PM |
Another issue is that, presumably, Lua is using (double-precision) floating point numbers, and if they get too large they end up being rounded, throwing off your calculations.
For example, type print(2^32 - 1 == 2^32) in the command bar. It should print false. Now type print(2^64 - 1 == 2^64). It will print true, even though analytically they should not be equal.
However, since you're taking a modulus, you can be clever and take advantage of modulus properties so that you never end up calculating a huge number in your code.
Here's a function (_G.expModulo) you can use to take large powers with modulo without running into round-off errors. What it does is recursively split the exponent into two equal parts (if the exponent is odd, it splits it into three parts, two of which are equal and the third is equal to 1), then multiplies them together (which adds the exponents). The modulo operator is applied after each exponentiation to keep the numbers small.
It works due to one of the properties of the modulus (as long as you are using positive integers).
I tested _G.expModulo on your scenario and it worked correctly. It should theoretically run in O(log E) if E is your exponent.
e=13 n=1147 d=997
--with these keys, I can encrypt and decrypt letters. --If I want to encrypt the letter E (5), I use the following:
_G.Encrypt = function(x) return _G.expModulo(x,e,n) end
--This gives me the key 346. --To decrypt this key, I use the following:
_G.Decrypt = function(x) return _G.expModulo(x,d,n) end
_G.expModulo = function(B,E,M) --exponent must be an integer, computes (B^E)%M if E < 0 then error("Exponent must be non-negative.") elseif E == 0 then return 1 elseif E == 1 then return B%M elseif E%2 == 1 then return ((_G.expModulo(B,math.floor(E/2),M))^2 * B)%M --(B^floor(E/2))^2 * B^1 = B^(E-1 + 1) = B^E elseif E%2 == 0 then return ((_G.expModulo(B,E/2,M))^2)%M --(B^(E/2))^2 = B^E else error("Exponent must be integer.") end end
--If your numbers are really big you may need to replace
-- return ((_G.expModulo(B,math.floor(E/2),M))^2 * B)%M
--with the following:
-- return (((_G.expModulo(B,math.floor(E/2),M))^2)%M * B)%M |
|
|
| Report Abuse |
|
|
|
| 08 Mar 2014 09:53 PM |
| uhm its actually 2^1023.9999999999999431999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 |
|
|
| Report Abuse |
|
|
|
| 09 Mar 2014 04:45 AM |
"I should probably program this in another scripting/programming language."
No, other programming languages will have the same problem. Look up "Lua big number library", use that, it will allow for infinite digits and precision (well, at least how much your computer can handle, but that will be MILLIONS of digits, you won't have a problem with this)
AW MAN THIS ISN'T WHERE I PARKED MY CAR |
|
|
| Report Abuse |
|
|