RSA program encrypts and decrypts numbers up to a certain range only

Question

If I give sample inputs as p=61,q=53 and if I give a message value that lies between 1 and 21 for this particular prime set my program successfully encrypts and decrypts the message back to the correct original message. But if I give input as p=61,q=53 and message value is greater than 21 it is not able decrypt the message back to the correct original message.

And It's not just these particular prime numbers set. It's for any pair of prime numbers that only a certain range of message values get encrypted and decrypted correctly. So why is that? Can any one suggest on how to solve this?

class RSA
{
    private:
    long int p,q;
    long int msg,cipherMsg,plainMsg;
    long int n,totient;
    long int  publicKey,privateKey;

    public:
    RSA();
    void ComputeKeys(long int p1,long int p2,long long int message);
    void EncryptMessage();
    void DecryptMessage();

};
RSA :: RSA()
{
    p=0;q=0;
    n=0;totient=0;
    publicKey=0;privateKey=0;
    msg=0;cipherMsg=0;plainMsg=0;
}

void RSA :: EncryptMessage()
{
    int y=1;
    cout<<"Encrypting Message....."<<endl;
    for(long int i=1;i<=publicKey;i++)
    {
        y=y*msg;
    }
    msg=y;
    cout<<"m^e:"<<msg<<endl;
    cipherMsg= msg%n;
    cout<<"Encryption Complete!"<<endl;
    cout<<"Cipher Message:"<<cipherMsg<<endl;
}

void RSA :: DecryptMessage()
{
    long int y= 1,tmp;
    cout<<"Decrypting Message...."<<endl;
    for(long int i=1;i<=privateKey;i++)
    {
        y=y*cipherMsg;
        tmp=y;
        y=fmod(y,n);
    }

    cout<<"c^d:"<<tmp<<endl;
    plainMsg=y;
    cout<<"Decryption Complete!"<<endl;
    cout<<"Original Message:"<<plainMsg<<endl;
}

int main()
{
    RSA obj;
    cout<<"\t------RSA Cryptography------"<<endl;
    obj.ComputeKeys(61,53,21);

    return 0;
}

(Note, I have not posted my ComputeKeys() method for proprietary reasons. But I believe this where I need to do modifications.)

The values you stated as being problematic are inputs to the function `ComputeKeys`, which you don't want to post. What sort of help do you expect? We have no idea what that function does. All I see is a constructor where everything is initialised to zero. Looks fine to me, except using `fmod` on integers. That's pretty crazy. — paddy, Dec 16 '15 at 02:41
Why are you using `fmod`? That's highly likely to cause problems if `y` or `m` exceed a value of 53 bits. Also `m^e` would make rather a large value for any publickey that is bigger than a tiny value - likewise for `c^d`. — Mats Petersson, Dec 16 '15 at 02:51

score 2 · Answer 1 · edited May 23 '17 at 12:30

It looks like integer overflow to me. Right now, you're computing x^y, and only when you're done, taking that result mod m.

You normally want to take advantage of the fact that you can take the modulus at each step along the way to minimize the size needed to avoid overflows.

Code for a modular power function can look something like this:

template <class T>
T mul_mod(T a, T b, T m) { 
    if (m == 0) return a * b;

    T r = T();

    while (a > 0) {
        if (a & 1)
            if ((r += b) > m) r %= m;
        a >>= 1;
        if ((b <<= 1) > m) b %= m;
    }
    return r;
}

template <class T>
T pow_mod(T a, T n, T m) {
    T r = 1;

    while (n > 0) {
        if (n & 1)
            r = mul_mod(r, a, m);
        a = mul_mod(a, a, m);
        n >>= 1;
    }
    return r;
}

Depending on the types and values you use, this can still overflow, but for a given type, it'll produce correct results for much larger values than a naive version.

Also note that this does the raising to a power by repeated squaring, making it much more practical when dealing with larger numbers (basically, it's O(log N) instead of O(N), N=modulus).

I've posted a more complete implementation in another answer.

RSA program encrypts and decrypts numbers up to a certain range only

1 Answers1