I have a homework that includes handling user login and register. For that the teacher told us to use the RSA Algorithm to encrypt the passwords of the users. My problem is with the RSA. I am trying to write it to encrypt only 1 integer and after that I will write a new method that encrypts a string. So at this moment, my code works for some integers and for others it fails pretty bad. This is the header file

#ifndef _RSA_
#define _RSA_

#include <cmath>
#include <string>

// A class that defines the RSA algorithm
class RSA {
    private:
        int p, q, n, z, d = 0, e;

    public:
        RSA();
        int gcd(int a, int b);
        int encrypt(int m);
        int decrypt(int c);
    
};

#endif

And this is the file where I implement those functions.

#include "./RSA.h"

RSA::RSA() {
    this->p = 3;
    this->q = 11;
    this->z = (this->p - 1) * (this->q - 1);
    this->n = this->p * this->q;

    for (this->e = 2; this->e < this->z; this->e  ) {
        if (this->gcd(this->e, this->z) == 1) {
            break;
        }
    }

    for (int i = 0; i <= 9;   i) {
        int x = (i * this->z)   1;
        if (x % this->e == 0) {
            this->d = x / this->e;
            break;
        }
    }
}

int RSA::gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int RSA::encrypt(int m) {
    return (int)pow(m, e) % this->n;
}

int RSA::decrypt(int c) {
    return (int)pow(c, d) % this->n;
}

Now I am going to provide you with some numbers that work and some numbers that do not work. Saying that the numbers work I mean that after I decrypt the result of encrypt method I get the initial number. It works for 1,2,6,7,8,9,10(it returns 10 for encrypted part and 10 for decrypted), 11(same as 10), 12(same as 11), 13, 14, 15, 16. I tested numbers in the range [1, 17] and it failed for 3,4,5,17. It returns completely random numbers for this 4 numbers. Also, I tried it on other number ranges and the result was the same.

CodePudding user response：

Even with small numbers like that it's easy to exceed the limits of int with exponentiation. If you make your own pow, it should apply the modulo after every step:

// computes x**y % n
int custom_pow(int x, int y, int n) {
    int res = 1;
    for(;y;y--) {
        res = (res*x) % n;
    }
    return res;
}