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]

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.

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.

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)).