RSA encryption in C++

Question

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?

You are doing `e-1` squarings, so you compute `m^(2^(e-1))` modulo `n`. You'd want `res = (res*m)%n;` for the simple exponentiation by repeated multiplication algorithm. — Daniel Fischer, Aug 22 '13 at 19:05
+1 to @DanielFischer . I was about to go off on modulo-chaining, only to see he already has it, but was missing one loop in the iteration and using the wrong multiplier. Duh. Nice catch! — WhozCraig, Aug 22 '13 at 19:08

score 5 · Accepted Answer · answered Aug 22 '13 at 19:09

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;

score 0 · Answer 2 · edited May 23 '17 at 10:25

0

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

edited May 23 '17 at 10:25

Community

1
1

answered Aug 22 '13 at 18:59

TomF

183
11

I'm not supposed to use an external library. I'm trying this at home now but have to execute it on Fedora at college where there is no internet access. – Frozen Crayon Aug 22 '13 at 19:01
Well then all i can say is implement big int... Anyway it will be goof practice, specially if you are going to fool around with computerized cryptography. – TomF Aug 22 '13 at 19:11

RSA encryption in C++

2 Answers2