RSA MPrime broken when the values are too high in Python

Question

My RSA MPrime is having problem decrypting when the primes value are too high

My decryption code is below:

def descripto(msg, d, num, N):
    ds = []
    ms = []
    MSG = 0
    for n in range(0, len(num)):
        ds.append(d % (num[n]-1))
    for n in range(0, len(num)):
        ms.append(pow(msg, ds[n]) % num[n])
    for n in range(0, len(num)):
        MSG = MSG + (N/num[n]) * ms[n] * pow(int(N/num[n]), -1, int(num[n]))

    MSG = MSG % N
    return int(MSG)

N is the product of all num numbers (the primes). msg is a random number. d is the private key.

Some tests:

Primes: [1181, 1543, 149]
Phi: 269294880
Public Key: <271520167, 7>
Private Key: <271520167, 230824183>
Message: 132
Crypto message: 30346111
Uncrypto message: 132

Primes: [1181, 1543, 149, 2143]
Phi: 576829632960
Public Key: <581867717881, 11>
Private Key: <581867717881, 314634345251>
Message: 583
Crypto message: 424678919465
Uncrypto message: 583

Primes: [27361, 27449, 27481, 149]
Phi: 3054254636851200
Public Key: <3075227812833541, 7>
Private Key: <3075227812833541, 436322090978743>
Message: 108
Crypto message: 171382426877952
Uncrypto message: 44

Primes: [27361, 27449, 149]
Phi: 111144637440
Public Key: <111903781261, 7>
Private Key: <111903781261, 79389026743>
Message: 113
Crypto message: 38799834195
Uncrypto message: 113

Primes: [27361, 27449, 27481]
Phi: 20636855654400
Public Key: <20639112837809, 7>
Private Key: <20639112837809, 2948122236343>
Message: 19477
Crypto message: 4955135338363
Uncrypto message: 19574

Primes: [1181, 1543, 149, 2143, 7]
Phi: 3460977797760
Public Key: <4073074025167, 11>
Private Key: <4073074025167, 314634345251>
Message: 5
Crypto message: 48828125
Uncrypto message: 5

Primes: [1181, 27449, 149, 2143, 7]
Phi: 61606302589440
Public Key: <72457426388081, 11>
Private Key: <72457426388081, 44804583701411>
Message: 5
Crypto message: 48828125
Uncrypto message: 5

The encryption algorithm is ok, and the decryption also seems ok. I know I used a small variety of numbers in tests, but the problem doesn't lies here. It just seems to have trouble when it uses over 3 primes over 10000, and I guess it's because the computer can't handle such high numbers. Also, you can see "the apple doesn't fall far from the tree" when the decryption fails. Can anyone confirm?

Is this python 2 or python 3? If python 3 you need to use `//` for integer division, not `/`. There should be no reason to use `int()` anywhere in this. — President James K. Polk, Apr 22 '21 at 01:03
@PresidentJamesK.Polk it's P3 but still using this changes (tested) there will return the same results — Akari Oozora, Apr 22 '21 at 01:33

score 1 · Accepted Answer · answered Apr 22 '21 at 10:58

It looks like you're using Python 3.8 or later (otherwise you'll get an error with the negative exponent when calling pow().

In Python version 3, the / operator denotes floating-point division, which will give you a double-precision floating-point result. You don't want that.

Try replacing N/num[n] with N//num[n] (using the integer division operator //). And get rid of the int casts. They're unnecessary.

score 0 · Answer 2 · answered Apr 22 '21 at 00:27

0

Yes those numbers multiplied might exceed the maximum value for an int which is probably 64-bit. Yet in Python 3 the size for an int is unbounded so it depends on the machine. See this post for more information.

answered Apr 22 '21 at 00:27

Oscar Umhin

44
1
3

RSA MPrime broken when the values are too high in Python

2 Answers2