Knowing You’re Right, But The Answer Is Wrong: Can You Spot My Little Error?

Knowing You’re Right, But The Answer Is Wrong: Can You Spot My Little Error?

Yesterday, I taught public key encryption, and it is one of my favouriate topics to teach. Why? Because it is at the fundamental core of cybersecurity, and we rely on it for trust on the Internet. Without, it, we would be connecting to completely untrusted Web sites, and where our communications could be spied upon by anyone who could monitor our data packets. It basically saved the Internet!

And, so, I like to give live demos where I drop down into a Python console and ask students to pick values for me and where I can show that the methods work. Yesterday, I outlined the RSA method, and where I ask for two prime numbers: p and q, and then compute N = p.q, and PHI=(p-1)(q-1). I then pick e (the encryption exponent) so that it does not share a factor with PHI. Next d (the decryption exponent) is computed from e^{-1} (mod PHI). The encryption is then easy as C=M^e (mod N), and the decryption is M1=C^d (mod N). The values of M and M1 should be the same. But when I demo’ed live, it didn’t work:

Doh! My message was “25”, and I promised the students I would show them some magic, and reveal the value of “25”. But, no, it was “4”.

I stared at it for as long as I could with a live audience (of students) present (about 30 seconds), but I couldn’t see where I had gone wrong. I could feel my professor’s powers of magic draining away. I was shocked, as every time I do this, the magic of RSA works. I began to doubt myself!

Could I have used a value for the message that was greater than N? No, N is 77, and our message is only 25. Could we have slipped up with picking e? No, 13 does not share factors with PHI. Could I have miscalculated d? No, Python 3 gives me a new function of pow(e,-1,PHI). Did I use the wrong value for the mod in the computation of d? No, I used PHI. I scanned back and forward in the little time I had to fix it.

Luckily, in the little break in the teaching, I spotted my error. Can you?

I don’t want to spoil your fun in debugging this, but if you want the answer, it is here.