Archived

This topic is now archived and is closed to further replies.

AndyTang

RSA public key encryption

Recommended Posts

Hi, I am trying to create an application that uses RSA public key encryption to sens things over the internet. Unfortunately, the amount of data precision is very limited - the use of someting like 47 to the power of 5127 can easily overflow a computer using long or double. Anyone had any experience with this type of encryption. Any suggestions or alternative methods to use?

Share this post


Link to post
Share on other sites
Every RSA implementation I''ve come across has used some form of custom number manipulation. The two most common would be string-math, where the numbers are stored as strings and manipulated, or as arrays of longs, which are manipulated to emulate a larger number. When I get to work I''ll post some links.


This post qualifies for 100 per cent Canadian Content under the rulings of the Canadian Internet Commission and the Federal Ministry of Communication. There are four Americans who worked on this post, but they all have landed immigrant status, and have signed CRTC affidavits swearing that they drink beer, eat back bacon, drive snowmobiles and wear toques. Any resemblance between the Content of this post and the content of any American post is purely coincidental and not the intention of the poster or the various Internet Agencies of the Canadian Government who have screened these posts prior to bulk erasing in accordance with the policies of the Federal Internet Identity Board.

Share this post


Link to post
Share on other sites
quote:
Original post by jediknight219
You aren''t really trying to take 47 to the power of 5127, are you? That''s a really, really, really big number. And for the purposes of RSA there''s an algorithm for a^b % c that doesn''t need numbers nearly that big.



As a matter of fact I do
Think about what you said about a^b % c, you need to do a^b first, so if ''a'' is 47 (text or character) and ''b'' is 5127 (decryption key) then you have, voila 47^5127 before you can modula it. You might be right if there is a easier calculation cause my algebramaths is a bit rusty.

Share this post


Link to post
Share on other sites
umm, how big?
Well 2^1024 yields:
3.231700607131100730071487668867e+616

So there are that many possible keys if it is 1024 bits long. I would imagine it would be overkill for most every-day encryption. But I am not an expert on this.

Phriction

Share this post


Link to post
Share on other sites
All right, I wanted to make sure that was what you were doing before I told you something you already knew.

I'll start with a fairly simple example (small exponent):

126^13 % 251
126^13 = 2017516459574609153391845376 (imagine how big 47^5127 would be)
2017516459574609153391845376 % 251 = 171

If you want to talk about the theory, we'll get into that later, but for now, the algorithm:

base^exponent % n
1. result = 1
2. Take the binary representation of your exponent
3. Loop through each of the digits starting with the first.
a. If the digit is 1, result = (result^2 % n * base) % n
b. If the digit is 0, result = result^2 % n


Example: 126^13 % 251
result = 1
exponent = 1101
result = (1^2 % 251 * 126) % 251 = 126 // 1st digit = 1
result = (126^2 % 251 * 126) % 251 = 157 // 2nd digit = 1
result = 157^2 % 251 = 51 // 3rd digit = 0
result = (51^2 % 251 * 126) % 251 = 171 // 4th digit = 1
^^^


And it never uses any numbers bigger than n^2.

And a 1024 bit key? 300+ digits
2^1024 = 17976931348623159077293051907890247336179769789423065727343008
11577326758055009631327084773224075360211201138798713933576587
89768814416622492847430639474124377767893424865485276302219601
24609411945308295208500576883815068234246288147391311054082723
7163350510684586298239947245938479716304835356329624224137216



[edited by - jediknight219 on November 1, 2002 6:17:46 PM]

Share this post


Link to post
Share on other sites
The largest number, in decimals, that a 1024 bit number can be, is 21024. I'll leave calculating that up to you, because it's pretty ridiculously huge.

[EDIT: I see that while I was away but before I hit the "Submit" button, a whole lot of other people said the same thing!]

[edited by - TerranFury on November 1, 2002 7:45:11 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by jediknight219
All right, I wanted to make sure that was what you were doing before I told you something you already knew.

And it never uses any numbers bigger than n^2.

[edited by - jediknight219 on November 1, 2002 6:17:46 PM]


Thanks for that, that''s quite clever. Did you by chance tol a maths degree or did you had to do research for this. This is good stuff thankx

Share this post


Link to post
Share on other sites
quote:
Original post by TerranFury
The largest number, in decimals, that a 1024 bit number can be, is 21024. I''ll leave calculating that up to you, because it''s pretty ridiculously huge.




Actually it''s 21024-1

Share this post


Link to post
Share on other sites
quote:
Original post by AndyTang
Thanks for that, that's quite clever. Did you by chance tol a maths degree or did you had to do research for this. This is good stuff thankx


Computer Science degree. That little tidbit came from a lecture in a Cryptography class. I'm kind of surprised I remembered it.

[edited by - jediknight219 on November 1, 2002 8:51:45 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by jediknight219
[quote]Original post by AndyTang
Thanks for that, that''s quite clever. Did you by chance tol a maths degree or did you had to do research for this. This is good stuff thankx


Computer Science degree. That little tidbit came from a lecture in a Cryptography class. I''m kind of surprised I remembered it.

[edited by - jediknight219 on November 1, 2002 8:51:45 PM]

I never learnt that in my Crptography class, or maybe I just werent awake for it

Anyway, I had a look at the Cryto website and it keeps mentioning things like ''potentially unsafe'' - what does this mean, how unsafe can it be and in what way.

Share this post


Link to post
Share on other sites