-2

I coded a small example of RSA in Python. When filling p and q, I mistakenly put in two numbers that were not prime numbers. And it worked fine anyway.

My question is, why is it so important for RSA to take prime number as inputs?

Milodupipo
  • 19
  • 4
    It shouldn't work, because you don't get that $\phi(pq)=(p-1)(q-1)$. What were your $p,q,e,$ and $d$? – TonyK Aug 12 '23 at 14:09
  • Technology has advanced so much that cracking a code can almost always be cracked. But the key to overcoming this is that the decryption needs quite a lot of time to be done. And then another code is made that, like the previous one, requires so much time to be decoded. This is what the large prime numbers are for (both primality and factorization are very laborious to do with large numbers, but the primes are more useful). – Piquito Aug 12 '23 at 14:14
  • @Piquito: Cracking a code can almost always be cracked? I suppose so, if by "quite a lot of time" you mean "longer than the expected lifetime of the universe". – TonyK Aug 13 '23 at 23:56
  • @TonyK Off-topic , but the universe won't die ! With enough time , every code could be cracked assuming we can verify whether a particular plaintext is the correct one. In the case of RSA , this is easy. If we have the factors , we can be sure. But what about substitution codes ? There might be several plausible messages , which one is the correct ? – Peter Aug 15 '23 at 16:18
  • By the way , RSA is an unlucky system and it is astonishing that it is used in practice at all considering that it has not even be proven that the enemy is helpless if he/she cannot factor the public number. – Peter Aug 15 '23 at 16:23

1 Answers1

0

"Working" and "easy to break" are different. RSA works as a cryptographic system because it's hard to factor the product of two large primes. A large number that has many prime divisors is easier to factor.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • But RSA simply doesn't work if $p$ and $q$ are not prime! – TonyK Aug 13 '23 at 23:55
  • @TonyK Indeed. I saw your comment on the post after the OP accepted my answer. I think the point I made answers the spirit of the question. I wonder what the OP's program did that they claimed "worked". I don't quite know what to do with this accepted answer. – Ethan Bolker Aug 13 '23 at 23:59
  • I suspect that OP computed $\phi(pq)$ by other means, and got lucky when their data didn't break the fragile system that they had created. – TonyK Aug 14 '23 at 00:09
  • I tried to find the values I used last time but I could not find them (indeed RSA does not work when I use something else than prime numbers). I probably made another mistake as @TonyK said. Anyway, both of your answers are fine to me. Thanks ! – Milodupipo Aug 14 '23 at 06:53
  • Would RSA work at all with , say , three huge prime factors ? I am not an expert of this method , so I am not sure whether the semiprimeness is not anyway crucial for RSA to work. – Peter Aug 15 '23 at 16:26
  • @Peter The elementary number theory behind the RSA algorithm might be modified to work with three factors. Figuring it out would be a nice exercise. But there would be no advantage. Two large prime factors about the same size is what makes their product hard to factor (for practical purposes impossible with current technology). – Ethan Bolker Aug 15 '23 at 17:25