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

AARRRGH

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.

Martyr

for a number that size, you'd need big int library, unless you want to write your own.
miracl is good.

DublinDilbert

dublindude wrote: »

Note I am already using long doubles.

Surely it would have to be an integer (big int or what ever) rather than a floating point value for it to work correctly?

I can't see how it would work with the loss in precision introduced by using floating point values.

AARRRGH

Thanks for your replies.

I've found the answer, Modular Exponentiation

DublinDilbert: I was just using long doubles because they're huge.

DublinDilbert

dublindude wrote: »

DublinDilbert: I was just using long doubles because they're huge.

Ahh ok... if your just interested in the theory of operation, and not a practical implementation, just reduce the number of bits used and use unsigned long's

Mr. CooL ICE

Probably not much use to you, but when I did encryption in Java, I converted every number to a binary reprentation as a boolean array. This let me scale the algorithm I was coding to practically any size I wanted (as long as the algorithm rules allowed the key size).

There are a few downsides though - the class package I made to perform the needed arithmetic operations on the boolean arrays took a long time to code properly. Also, I'm no expert on coding performance, but I reckon my method was highly inefficient