Thread: RSA: Do I need to use a big int package for this?

Hello

I am teaching myself encryption using C.

At the moment I'm implementing RSA. I'm only using prime numbers smaller than 1000.

When it comes to encrypting, and especially decrypting, I'm getting some pretty massive numbers.

For example:

If I encrypt the number 6 using the key pair (79, 1121):

(6 ^ 79) mod 1121 = 693

I then decrypt using the key pair (859, 1121):

(693 ^ 859) mod 1121... Error. My compiler doesn't like 693 ^ 859. The number is too big.

Is there a smart way around this, or do I need to install a big int package?

Note I am already using long doubles.

Any help greatly appreciated.

Thank you.

There's a smart way around this, to wit: reduce often. More precisely, if you are doing anything other than squaring-mod and multiplying-mod, you're not doing it right. Even more precisely, successive squaring gives 693^2, 693^4, 693^8, 693^16, 693^32, etc., reduced of course. Writing the exponent in binary (or using the computer's internal representation of the exponent as same) will allow you to multiply the appropriate squares together to get 693^859.

Holy cow, I hope you're not actually fully calculating 693 ^ 859 and then modding by 1121. You need to be implementing modular exponentiation. I could explain it for you here, but I think its probably best to let Google and Wikipedia do their jobs.

http://en.wikipedia.org/wiki/Modular_exponentiation

The "efficient right-to-left algorithm" is the version I most often see implemented as its very short and straightforward.

Thank you both for your replies.

I'm new to C and cryptorgraphy, so you have both been a great help.

Thanks!