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$
    – kelalaka
    Commented Oct 21, 2018 at 17:07
  • 1
    $\begingroup$ did you click to the link and see the factors? see Text book RSA $\endgroup$
    – kelalaka
    Commented Oct 21, 2018 at 17:12
  • 1
    $\begingroup$ $q =8$, must be prime too. $\endgroup$
    – kelalaka
    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$
    – fgrieu ♦
    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$
    – fgrieu ♦
    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$
    – user6039980
    Commented Oct 21, 2018 at 18:45
  • 1
    $\begingroup$ you took p =q, there I said distinct primes. $\endgroup$
    – kelalaka
    Commented Oct 21, 2018 at 18:46
  • $\begingroup$ My bad, I missed that .. sorry. $\endgroup$
    – user6039980
    Commented Oct 21, 2018 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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