Sign in to follow this  
JonW

Data Type For RSA Encryption

Recommended Posts

Hi, I'm implementing RSA encryption and decryption with C++. My code looks like the following: double n = 3233; int nPublicKey = 17; int nPrivateKey = 2753; double encrypt(int value) { return fmod(pow(value, nPublicKey), n); } double decrypt(int value) { return fmod(pow(value, nPrivateKey), n); } Using the double data type, I can't even encrypt the number 123, which is relatively small compared to the numbers I want to encrypt. How can I handle such large data values? Thanks! [Edited by - JonW on July 13, 2006 12:44:11 PM]

Share this post


Link to post
Share on other sites
Most crypto algorithms manipulate octet(byte) streams. The keys themselves are usually stored in octet form as well.

As well, unless you have some particular reason for wanting to implement RSA from scratch (which I'm hoping isn't for security reasons), I'd recommend you check out a library like crypto++. Encryption code is quiet difficult to get right.

Share this post


Link to post
Share on other sites
Solution: Compute a^b (mod n) more efficiently. Under almost no circumstances do you actually want to compute a^b in its entirety and then mod by n, you would waste way too much space and computation. The easy way to calculate it is to realize that (x * y * z) % n == (((x * y) % n) * z) % n, so you just do this:

int PowerMod(int value, int exponent, int modulus)
{
if(exponent == 1)
return value;
else if(exponent & 1)
return PowerMod((value * value) % modulus, exponent >> 1, modulus);
else
return (value * PowerMod((value * value) % modulus, exponent >> 1, modulus)) % modulus;
}


Example of this algorithm: let exponent = 10, value = a, modulus = n, so you get
PowerMod(a, 10, n) ==
PowerMod(a^2, 5, n) ==
PowerMod(a^4, 2, n) * a^2 ==
PowerMod(a^8, 1, n) * a^2
== a^8 * a^2 == a^10 (all this is mod n, I just omitted that to make it clearer)

This algorithm runs in O(log2(exponent)) time and memory. There is another more complicated algorithm that runs in O(log2(exponent)) time and O(1) memory. You can also do this algorithm non-recursively (i.e. iteratively), but you must keep a stack of the values. For your case, your keys are so small that the log2(exponent) memory overhead is completely insignificant.

Share this post


Link to post
Share on other sites
Here's a nice algorithm I particularly like for calculating y^x (mod n). This is the exact same algorithm as the one above, but iterative and (IMO) easier to understand. The algorithm is not O(log base-2(n)), but precisely O((3/2)log base-2(n)).


long modExpt(long y, long x, long n) {
int a = x;
int b = 1;
int c = y;


while (a != 0) {
if (a & 1) { // Check if a is even
a = a / 2;
c = (c * c) % n;
}
else {
a = a - 1;
b = (b * c) % n;
}
}
return b;
}

Share this post


Link to post
Share on other sites
[indent]Quote:[i]Original post by Jon[/i]
Hi,

I'm implementing RSA encryption and decryption with C++. My code looks like the following:

double n = 3233;

int nPublicKey = 17;
int nPrivateKey = 2753;

double encrypt(int value)
{
return fmod(pow(value, nPublicKey), n);
}

double decrypt(int value)
{
return fmod(pow(value, nPrivateKey), n);
}

Using the double data type, I can't even encrypt the number 123, which is relatively small compared to the numbers I want to encrypt. How can I handle such large data values?

Thanks!

Jon Woyame[/indent]

Try [url="http://www.swox.com/gmp/"]GMP[/url][[url="http://www.swox.com/gmp/]."]http://www.swox.com/gmp/].[/url]
It's a library that allows you to deal with abitrary length integers (which is needed when implementing RSA). It also include functions for finding primes and testing for primes.

You might also consider check out [url="http://www.anujseth.com/crypto/"]Anuj Seth's Data Encryption Page[/url][[url="http://www.anujseth.com/crypto]."]http://www.anujseth.com/crypto].[/url] He has alot of information on RSA, big numbers, and primes. The big number section of his site has links to other abitrary length integer libraries, like NTL (harder to use than GMP in my opinion) and the RSA reference implementation release by RSA Security Inc.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this