# 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 on other sites
Well, a) you don't use floating point numbers. and b) you write yourself a nice large integer class. Makes life easy :P

##### 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 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 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 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 on other sites
Check wikipedia

Also look into addition chain exponentiation.

And don't forget the big number libraries.
From,
Nice coder

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628379
• Total Posts
2982344

• 10
• 9
• 15
• 24
• 11