CODEWITHSUNDEEP
c++mathencryptionrsa
Frozen Crayon
Frozen Crayon

Reputation: 5400

RSA encryption in C++

I want to encrypt (RSA) a character to an integer using its ASCII value. Eg. 'a' is encrypted as 48.

For encryption: c=pow(m,e)%n where c is cipher text, m is the plain text and (e,n) is the public key.

If pow(m,e) is large say 67^7, it won't fit in int or long. But if I use double, I cannot use it with modulus % operator. So I wrote this function for encryption using a for loop:

int encrypt(int m, int e, int n)
{
    int res=m, i;
    for(i=0; i<e-1;i++)
        res=(res*res)%n;
    return res;
}

It worked for 67^7mod11 which is 67 but then I came to know it's not actually correct. Where have I gone wrong?

Upvotes: 2

Views: 3093

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183978

Your loop

for(i=0; i<e-1;i++)
    res=(res*res)%n;

squares e-1 times modulo n, that means it computes m^(2^(e-1)) modulo n. To compute m^e modulo n with the simple algorithm, use

for(i = 0; i < e-1; ++i)
    res = (res*m) % n;

instead.

For a somewhat faster algorithm when the exponent is larger, you can use exponentiation by repeated squaring:

res = 1;
while (e > 0) {
    if (e % 2 != 0) {
        res = (m*res) % n;
    }
    m = (m*m) % n;
    e /= 2;
}
return res;

Upvotes: 5

TomF
TomF

Reputation: 183

Usually when using encryption parameters you use "big int" instead of int's. Exactly for that reason.

There are some suggestions here: Bigint (bigbit) library

Upvotes: 0

Related Questions