Lunch & Learn: How to send a secret on a postcard: Public key cryptography with John MacCormick

Computer security graphic

Computers use an ingenious invention called public key cryptography to transmit secrets on the internet, even through public channels that can be observed by anyone. The approach is instrumental today to the secure flow of information on the internet and the whole realm of electronic commerce. There are simple programs that can monitor internet traffic, and even the simplest requests will flow through many, and perhaps dozens of computers. Unsecured transactions can be read by any malicious hacker almost as easily as if you had transmitted the information on a postcard.

In his March 3 Lunch ‘n Learn seminar, Dickinson College Assistant Professor John MacCormick explained how public key cryptography works using some fun and easy-to understand techniques.

Public key cryptography relies upon the use of both public and private keys. The private keys are kept secret, while the public key can be freely shared. The sender encrypts the message using the public key, and the message can be decrypted with the recipient’s private key.

If that sounds confusing, MacCormick lessened the complexity.

In the simplest example, he wrote a single digit on his hand. To that number, which might have been credit card number, he added the last two digits of the phone number of a colleague sitting in the audience. That person, knowing their own phone number, could trivially subtract the known two-digit number and derive the original number. But no one else in the audience knew their shared secret. It is a simple trick, which passed information openly yet securely.

And so, it is trivially possible to communicate a shared secret over an open channel. Everyone heard the transaction, and yet only MacCormick and his colleague knew the number.

In the real world, the algorithm is obviously more complex, but the principle is the same. Securely transmitting information over open lines. Let’s say that the sender wants to send securely the number “7” The public key that everyone knows is 8. And let us assume that the recipient’s private key is “3” We multiple the private key 7 with the public key, getting 56, and we place that number in the public area. The recipient does the same, obtaining 24. Of course, 3×56=168=7×24. And so, the two can share information without sharing their private keys. In real life, of course, the numbers are very large prime numbers, making it nearly impossible for those watching network traffic to decipher the data.

For decades, researchers have sought ways to break the procedure and they have consistently failed, says MacCormick. Back in the 1970s, the original technique used exponents and clock arithmetic rather than simple subtraction or multiplication. It is of course, trivial to crack systems that use small numbers, but MacCormick notes that modern cryptography relies rather on very large numbers, often hundreds of digits long. The result is that cracking the code by brute force would require more time than the universe is old.

In a memorable display, MacCormick performed the same numeric trick using cups of primary colored water. MacCormick noted that Chris Bishop, a researcher for Microsoft at the University of Edinburgh had also proposed this explanation for public key cryptography and was the first to perform this experiment live for audiences. In this case, the shared secret was a color of water. The objective? The sender and receiver each have a private key, in this case a color and volume of water that only they know. By combining their secret from the private cups with the unlimited supply of water in the public cup, he demonstrated that both sender and receiver could share information without the public being able to deduce the shared secret, despite having access to a good bit of information. In this case, the receiver can derive the shared secret, the same color of water, without ever having had access to the original private color.

JMacCormickTimeOut.jpg

John MacCormick, Assistant Professor of Computer Science at Dickinson College, has degrees in mathematics from the University of Cambridge and the University of Auckland, and a doctorate in computer vision from the University of Oxford. He was a research fellow at Linacre College, Oxford from 1999-2000, a research scientist at HP Labs from 2000-2003, and a computer scientist with Microsoft Research from 2003-2007. Professor MacCormick joined the faculty of the Department of Mathematics and Computer Science at Dickinson College in Fall 2007. His current research focuses on computer vision, but he also maintains an interest large-scale distributed computer systems. Currently active research topics include message-passing algorithms for early vision tasks such as stereo vision, and superpixel algorithms for image over-segmentation. Dr. MacCormick is the author of one book, “Stochastic Algorithms for Visual Tracking,” and has filed 15 US patents covering novel computer technologies.

The podcast is available.

This entry was posted in Lunch & Learn, Training and Outreach and tagged , , , , , , , , . Bookmark the permalink.