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

• 04-26-2008
MrSteve
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.
• 04-26-2008
tabstop
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.
• 04-27-2008
arpsmack
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.
• 04-27-2008
MrSteve
Thank you both for your replies.

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

Thanks!