RSA encryption / decryption not returning original message

1
votes

beginner here, trying some RSA encryption. I wrote a python code that returns the right message most of the time, but sometimes encryption and decryption don't return the original message.

I though it was some error in my code, but some online resources are also returning error:

http://extranet.cryptomathic.com/rsacalc/index

https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html

The parameters selected are:

p = 11

q = 269

n = 2959

e = 13

d = 1237

message = 13355

crypt text = 1079

decrypted = 1519

Am I missing some kind of limit to RSA? Some minimum size of parameters for the text?

1
pythonencryptioncryptographyrsa
Could you post your coding attempts - Professor_Joykill

1 Answers

7
votes

Your modulus (n) is 2959. This means that the largest number you can encrypt with this system is 2958.

You're attempting to encrypt the number 13355, which is too large. The result you're getting is equal to 13355 mod 2959, which is 1519.

But why?

The two basic formulae used to implement RSA encryption are as follows:

  1. c = me (mod n), and
  2. m = cd (mod n)

where n is the modulus, m is the plaintext, c is the encrypted ciphertext, e is the public encryption exponent, and d is the private decryption exponent. Since all the arithmetic is performed modulo n, the values of c in Eq. 1 and m in Eq. 2 must be less than n.

What if m is larger than n? Well, in this case we can make the substitution m = m0 + kn, where k is some integer value. From this we get:

c = me (mod n) = (m0 + kn)e (mod n)

If you expand the term (m0 + kn)e, you'll end up with an expression like the following:

(m0 + kn)e = (m0)e + a0(m0)e−1(kn) + a1(m0)e−2(kn)2 + a2(m0)e−3(kn)3 + ... + (kn)e

where the coefficients a0, a1 etc. are binomial coefficients. This looks complicated, but since every term with an n in it is equal to zero (mod n), we're left with me (mod n) ≡ (m0)e (mod n). In other words, the result of attempting to encrypt a value greater than or equal to n is identical to the result of encrypting that number modulo n. So when you thought you were encrypting the number 13355, you were actually encrypting 13355 mod 2959.

Usually this isn't a problem; RSA is generally used to encrypt symmetric keys for use with ciphers like AES, so 2048 bits is more than enough. If you really have to somehow encrypt a value ≥ n, you can use multiple messages. For example, in base 2959, the number 13355 has two "digits" — the first one is 4, and the second is 1519. These numbers could be recombined at the receiving end (4 * 2959 + 1519 = 13355).