# RSA encryption/decryption process is not working correctly

I'm trying to apply the RSA cryptosystem to encrypt a byte M=72, using predefined modulus n, public key exponent e and private key d.

(n, e, d, p, q) = (4802, 5, 59, 43, 8)

In order to accomplish that, I used the following code on Python console:

C=(M**e)%n
M=(C**d)%n
print M

• the first instruction encrypts the byte as C: using the RSA encryption mathematical expression (** stands for exponentional, and % for modulus in Python programming language)
• the second decrypts C to get M back: using the RSA decryption mathematical expression.

However, the output shows:

2816

which means that M was incorrectly computed as '2816', although I'm pretty sure that all the values of n, e, d, p and q respect the RSA public key algorithm specification.

Does anyone have any idea?

• factor 4802, are you sure the $n=4802$ Oct 21 '18 at 17:07
• did you click to the link and see the factors? see Text book RSA Oct 21 '18 at 17:12
• $q =8$, must be prime too. Oct 21 '18 at 17:17
• On top of the answer: A) n is some million (.. dozens words "million" suppressed) million times too small to provide security. B) M=(C**d)%n won't work even if you increase n by a million million. See modular exponentiation or/and use the three-argument form of pow. C) With the question's textbook RSA, a message guess can be checked; think of e.g. a name on the class roll. See encryption padding.
– fgrieu
Oct 21 '18 at 19:42
• On B): because no computer has enough memory to store C**dexactly for n large enough for security, which implies nearly as large Cand d. Modular reduction must be applied as the exponentiation is performed. Three-arguments pow does, but (C**d)%ndoes not. On A): n needs to be MUCH larger, otherwise it can be factored and an adversary can then decipher just as easily as the legitimate recipient. On C): with the question's textbook RSA, if you know that the name of a student is enciphered, you can encrypt each name on the class roll and see which matches the ciphertext.
– fgrieu
Oct 21 '18 at 21:56

The RSA definition requires $$n = p q$$ where $$p$$ and $$q$$ are distinct primes.

In your example $$n=4802$$ has a factorization as;

$$n = 2 \cdot 7^4$$ with 10 divisors. Also, your $$q=8$$ is not a prime.

Here a working example for you with fips.186-4 standard, or see $$\lambda$$ versus $$\varphi$$ in RSA;

• Select two distinct random primes; $$p = 47, q = 43$$
• compute $$n = 47*43 = 2021$$
• compute $$\lambda(n)=\operatorname{lcm}(p-1,q-1)= \operatorname{lcm}(62,42)= 966$$
• select $$e$$;
• $$e=3$$;
• $$gcd(3,966) = 3 \neq 1$$ chose another;
• $$e=5$$
• check $$gcd(5,966) = 1$$, ok.
• $$d = 773$$ by $$d = e^{-1} \bmod{\lambda(n)}$$

As noted by Fgrieu on the comments, make sure that you are using efficient methods. For example;

• For finding prime numbers probabilistic Miller–Rabin primality test, should be enough. Note that Miller–Rabin primality test is probabilistic; composite output is always true, prime output has probability defined by the number iterations.
• For modular multiplication there are various chocies as $$2^k$$-ary sliding window algorithm used by GNU GMP, left-to-right or right-to-left modular multiplications.
• Modular inverse by the extended-gcd algorithm.

Calculating with Wolfram Alpha

One can use the highlighted text to enter at WolframAlpha with your paramaters:

• $$\lambda(n):$$ CarmichaelLambda(2021) result is 966
• $$gcd(5,966):$$ gcd(5,966) result is 1
• $$d:$$ 5^-1 mod CarmichaelLambda(2021) result is 773
• encrypt $$m=65:$$ 65^5 mod 2021 result is c=168
• decrypt $$c=168:$$ 168^773 mod 2021 result is 65

Note: if you are using textbook RSA then change CarmichaelLambda() with phi()

• Unfortunately I'm facing the same problem given: (n, e, d, p, q) = (289, 77, 133, 17, 17) and M=72. n is prime as well as p and q. Moreover I verified that (e * d) mod ((p-1)*(q-1)) = (77×133) mod (16×16) = 1 Oct 21 '18 at 18:45
• you took p =q, there I said distinct primes. Oct 21 '18 at 18:46
• My bad, I missed that .. sorry. Oct 21 '18 at 18:48