Public key cryptography

By -
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?



Comments

  1. John Goes12:30 AM

    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. gcallah11:00 AM

      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. John Goes3:01 PM

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

      Delete
  2. John Goes1:58 PM

    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

Post a Comment

Popular posts from this blog

Libertarians, My Libertarians!

By -
Cruel to be kind means that I love you . Because, while I think you are mistaken, your hearts are in the right place -- yes, even you, Silas --  unlike some people . This Breitbart fellow (discussed in the link above), by all appearances, deliberately doctored a video of Shirley Sherrod to make her remarks appear virulently racist, when they had, in fact, the opposite import. I heard that at a recent Austrian conference, some folks were talking about "Callahan's conservative turn." While that description is not entirely inaccurate, I must say that a lot of these people who today call themselves conservative give me the heebie-jeebies.
Read more

"Pre-Galilean" Foolishness

By -
 I am currently reading The Master and His Emissary , which appears to be an excellent book. ("Appears" because I don't know the neuroscience literature well enough to say for sure, yet.) But then on page 186 I find: "Asking cognition, however, to give a perspective on the relationship between cognition and affect is like asking astronomer in the pre-Galilean geocentric world, whether, in his opinion, the sun moves round the earth of the earth around the sun. To ask a question alone would be enough to label one as mad." OK, this is garbage. First of all, it should be pre-Copernican, not pre-Galilean. But much worse is that people have seriously been considering heliocentrism for many centuries before Copernicus. Aristarchus had proposed a heliocentric model in the 4th-century BC. It had generally been considered wrong, but not "mad." (And wrong for scientific reasons: Why, for instance, did we not observe stellar parallax?) And when Copernicus propose...
Read more