0
$\begingroup$

This answer talks about how non-prime numbers would make the algorithm easier to break, not that the algorithm doesn't work full-stop: Why does RSA need p and q to be prime numbers?

Question 1: this implementation uses the number 57, which is not prime as it divides by 3.

  1. Choose p = 13, q = 57, e = 5 and message 'm' = 4
  2. Therefore n = pq = 741 and (p - 1)(q - 1) = 672
  3. encrypt message m as m^e mod n = 4^5 mod 741 = 283
  4. calculate decryption key d as e^-1 mod (p–1)(q–1) = 5^-1 mod 812 = 269
  5. decrypt '283' by 283^d mod n = 283^269 mod 741 = 199 ≠ 4

How does using a non-prime number cause the result to be wrong? I suspect the answer has something to do with the way that an inverse mod calculation looks for prime factors using the Euclidean algorithm, and if n is not the product of two prime numbers then it will give a different answer. But how is (p-1)(n-1) affected by p or q not being prime?

Question 2: p and q are the same prime number:

  1. Choose p = 11, q = 11, e = 3 and message 'm' = 2
  2. Therefore n = pq = 121 and (p - 1)(q - 1) = 100
  3. encrypt message m as m^e mod n = 2^2 mod 121 = 8
  4. calculate decryption key d as e^-1 mod (p–1)(q–1) = 5^-1 mod 100 = 67
  5. decrypt '8' by 8^d mod n = 8^67 mod 121 = 24 ≠ 4

How does using two (prime) identical numbers cause the result to be wrong? For this one I don't know where to start.

$\endgroup$
1
$\begingroup$

A first step is to use the correct value for the totient function $\phi(n),$ which is $432$ and $110$ in your examples.

Even better use the Carmichael function $\lambda(n)$ as described in RSA key generation, which is $36$ and $110.$

With either of these numbers, your encrypted messages are decrypted correctly.

$\endgroup$
1
$\begingroup$

Wanted to add something to @gammatester's answer.
He is correct in saying that your decryption results are wrong because you are using incorrect values for the totient function $\phi(n)$. If you look at the Euler's theorem, you will see that taking a wrong value for $\phi(n)$, will result in a residue ≠ 1 mod $n$ when you do decryption. In this case you will get residue as $m^{k}$ mod $n$, where $k = e.d (= a.\phi(n) + k)$ mod $\phi(n)$. Here $\phi(n)$ is the correct value of the totient function, which you are taking as incorrect in the example above.
It is also not at all secure to use either $p = q$ or one (or both) of $p$ or (and) $q$ to be composite. If you take $p = q$, then your implementation is not backed up by the hardness of the integer factorization problem, no matter how big you take you primes $p$ and $q$ to be. On the other hand, if you take composites instead of primes $p$ or (and) $q$ then you are just making it easier for someone to factorize the modulus value $n = p.q$.
You should not even try to go with these options given security falls apart then.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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