My "RSA Algorithm" code doesn't work for all numbers

Question

I wrote this code but it didn't work for all numbers. (RSA algorithm)

using namespace std;
int main () {
    int x;
    int p = 13;
    int q = 11;
    long n = p * q;
    long φ = (p - 1) * (q - 1);
    long e = φ - 1;
    long d = φ + e;
    cout<<"Plz enter a number.\n";
    cin>>x;
    long y = pow (x,e);
    long a = y % n;
    long b = pow (a,d);
    long c = b % n;
    cout<<"Original = "<<x<<endl;
    cout<<"Encrypted = "<<a<<endl;
    cout<<"Decrypted = "<<c<<endl;
    return 0;
}

For some numbers, encrypted and decrypted show same number, and for larger numbers they show random numbers.

Never ever use `std::pow` when doing integer arithmetic. `std::pow` always computes and returns a floating point value. `long y = std::pow (x,e);` will truncate the returned result. Instead write your own integer power function. Use the equality `(a * b) % m == (a%m * b%m) % m` to avoid integer overflow in your power function. — Richard Critten, Nov 23 '22 at 14:31
How many bits you think you might need to store the integer value equal to pow(x, e), where e.g. x == 2, and e == 119? Why do you try to calculate the power from definition if later on you are invoking modulo operation on it anyway? https://en.wikipedia.org/wiki/Modular_exponentiation — pptaszni, Nov 23 '22 at 14:42
Please [edit] and show some examples of input and expected vs. actual output. And where are your `#include`s? They matter. — Jabberwocky, Nov 23 '22 at 15:16
Are we just going to roll with the non-ASCII variable names? I'm going to start using emoji. — sweenish, Nov 23 '22 at 15:20
also ignoring fact that implantation is wrong (use of floating points), also encoded value must be smaller then `n` which is very small in your case. — Marek R, Nov 23 '22 at 17:33

Bathsheba · Answer 1 · 2022-11-23T16:28:49.793

The short answer is you can't really use pow for either the encryption or decryption stage as firstly it's a floating point function and the result even for integral arguments is not guaranteed to be the best possible return value, and converting to int may truncate.

Secondly, the numbers you get are large, even for quite a small n = pq amd it's likely the integral types are overflowing, with undefined results.

There are faster ways to achieve the result, but one way is to compute the power yourself, bearing in mind that in RSA it is modulo n.

So, rather than

long y = pow(x, e);

followed by y % n, write something like

long y = 1;
for (long i = 0; i < e; ++i){
    y = y * e % n;
}

There are faster ways used by decent RSA implementations, but this one's good for gaining an understanding of the method.

Also, avoid any character in source code for which isalnum will return false.

(I haven't checked your mathematics carefully, particularly the Carmichael totient function, or the modulo multiplicative inverse.)

My "RSA Algorithm" code doesn't work for all numbers

1 Answers1