The New Turing Omnibus Chapter 37 Public Key Cryptography
Murray kindly volunteered to shepherd this meeting so we began by discussing "The Big Picture" and talking through his notes on the chapter.
We briefly discussed the history of cryptography prior to Public Key Cryptography; in particular, the use of frequency analysis to break substitution ciphers, recommending Simon Singh's "The Code Book" and the historic vulnerability of key exchange.
We then decided to tackle the first problem in the chapter, working through encrypting and decrypting the letter S with a given private key.
We first derived a public key from the private key and values for w and m using the algorithm provided in the book. We then used only this public key to encrypt our message (the single letter S in ASCII).
We then decrypted this message using the private key but immediately hit a problem in the algorithm: how do we calculate the modular multiplicative inverse of w (for that is what w^-1 represents)?
Thankfully, Tom knew an algorithm to derive this from w known as the Extended Euclidean algorithm and so he heroically took to the whiteboard to work through it for our given value of w:
(Note the look of distant triumph.)
With this in place, we could now perform the decryption algorithm and decode our ciphertext back into the letter S:
This involved solving a particularly easy subset-sum problem and we discussed how the particular structure of our private key (as a sequence of numbers, each one greater than the sum of all preceding it) made this easy for us to calculate. This also gave us some intuition why this particular type of subset-sum problem was proven vulnerable to an attack.
With our text decrypted, we walked through the proof that explained how we were able to derive the plain text message using our private key in terms of our public key:
Chris demonstrated his subset-sum solver written in his programming language Sentient. He discussed some of his design goals with Sentient and his progress so far.
- We raised concerns that this was a very maths-heavy chapter and that people got lost along the way;
- We suggested mixing up the chapters so that people don't get intimidated by the maths but also reiterated the importance of speaking out when stuck or confused;
- It was suggested that it would be nice if there was more collaboration outside the meetings but also discussed the trade-off that increased commitment put members off joining in the past.
Thanks to Leo and Geckoboard for hosting, Murray for shepherding, Tom for working through the Extended Euclidean algorithm on the whiteboard, Chris for his subset-sum solver and all those who contributed snacks.