Jump to content
  • Advertisement

Archived

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

AndyTang

RSA public key encryption

This topic is 5771 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
For general links use this search query and append whatever language you want to use. And example would be this C + Assembler library designed to hold integers up to 1600 digits.

Share this post


Link to post
Share on other sites
Thanks you very much, that helped a lot. I was wondering if I could create my own data type to store huge integers, now it seems I can. Thanks again!

Share this post


Link to post
Share on other sites
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.

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!