# Data Type For RSA Encryption

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

## 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
Quote:Original post by Jon
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

Try GMP[."]http://www.swox.com/gmp/].
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 Anuj Seth's Data Encryption Page[."]http://www.anujseth.com/crypto]. 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

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013707
×