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?

  • 3
    factor 4802, are you sure the $n=4802$ – kelalaka Oct 21 at 17:07
  • 1
    did you click to the link and see the factors? see Text book RSA – kelalaka Oct 21 at 17:12
  • 1
    $q =8$, must be prime too. – kelalaka Oct 21 at 17:17
  • 1
    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 at 19:42
  • 1
    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 at 21:56
up vote 3 down vote accepted

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

In your example $n=4082$ 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 – Kais Oct 21 at 18:45
  • 1
    you took p =q, there I said distinct primes. – kelalaka Oct 21 at 18:46
  • My bad, I missed that .. sorry. – Kais Oct 21 at 18:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.