Public key cryptography

Yes, the odds are that this will never happen before the world ends, but what if my message turned into a number just should happen to turn out to be a multiple of one of the secret primes p or q? Would the process fail? Silas? Shonk? Wabulon?



4 comments:

  1. It doesn't break down.

    Everything works modulo n=pq. You always need to choose encode your message M to be an interger < n. If you are worried that M will be zeroed out at some point, it won't, since even p mod(pq) will not be zero.

    ReplyDelete
    Replies
    1. But the proof I saw for the decrypt(encrypt(M)) = M relied on Euler's Theorem, which relied on M being relatively prime to p and q. Is that just because I was seeing a simplified version of the real proof?

      Delete
    2. I thought I responded to this yesterday, but you either didn't publish it or it got lost in transmission.

      Delete
  2. You really want to use Fermat's little theorem (a particular case of Euler's theorem). Read the first proof here, and note that the second proof (which is probably what you saw) is not really a proof at all, for the reason you mentioned.

    ReplyDelete