0
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ factor 4802, are you sure the $n=4802$ $\endgroup$ Commented Oct 21, 2018 at 17:07
  • 1
    $\begingroup$ did you click to the link and see the factors? see Text book RSA $\endgroup$ Commented Oct 21, 2018 at 17:12
  • 1
    $\begingroup$ $q =8$, must be prime too. $\endgroup$ Commented Oct 21, 2018 at 17:17
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 21, 2018 at 19:42
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 21, 2018 at 21:56

1 Answer 1

Reset to default
3
$\begingroup$

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()

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Commented Oct 21, 2018 at 18:45
  • 1
    $\begingroup$ you took p =q, there I said distinct primes. $\endgroup$ Commented Oct 21, 2018 at 18:46
  • $\begingroup$ My bad, I missed that .. sorry. $\endgroup$ Commented Oct 21, 2018 at 18:48

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.