RSA public key encryption
Author
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?
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.
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.
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.
Author
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!
You may also want to check this out: http://www.eskimo.com/~weidai/cryptlib.html
In implementing an encryption algorithm on your own you may inadvertently undermine its security (unless you really know what you’re doing).
In implementing an encryption algorithm on your own you may inadvertently undermine its security (unless you really know what you’re doing).
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.
Author
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.
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
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
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
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]
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 % 251result = 1exponent = 1101result = (1^2 % 251 * 126) % 251 = 126 // 1st digit = 1result = (126^2 % 251 * 126) % 251 = 157 // 2nd digit = 1result = 157^2 % 251 = 51 // 3rd digit = 0result = (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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
