CWI Blogs

Keeping Secrets!

Tuesday, August 26, 2014 - 4:00pm
Author(s): Related Group(s):

The main objective of cryptography, a field of study for both mathematicians and computer scientists, is to provide a way for two people (often characterized as Alice and Bob) to be able to send a message over an insecure channel in such a way that an opponent (often called Oscar) cannot understand the message if it is intercepted.  In some cases this is achieved by using previously agreed upon code words or symbols.  In others, it means that Alice and Bob have agreed upon a particular technique for disguising their message.  This technique is referred to as a cryptosystem.  One example of a simple cryptosystem is the shift cipher.  Each letter in the message is replaced with one a previously determined number of letters away.  For example, if Alice and Bob agreed to a shift of 4 and Alice needs to send Bob the message “Attack at dawn” she would actually send “EXXEGO EX HEAR”.  To make it a bit more challenging on Oscar she would probably remove the spaces in her message.   When Bob gets this message, he knows that he has to shift the letters in it back by 4 places.

The shift cipher is an example of a private key cryptosystem.  Its security is heavily dependent on keeping the type of system used and the exact key used a secret between Alice and Bob.  It also requires that at some point Alice and Bob agree on the key in a secure environment.  Sometimes, it’s important for Bob to be able to communicate with an Alice he’s never met or collaborated with before.  He has to assume that Oscar is always listening in so Bob might choose to use a type of system called public key cryptography.

Public Key cryptography used keys that have two parts:  a public half of the key that bob publishes for all to see (even Oscar) and a private half that he keeps to himself.  These two halves are generally numbers or sets of numbers that are based on very, very large prime numbers.  If Alice needs to send Bob a message, she converts her message into numbers (perhaps 1=a, 2=b, etc.) and performs the calculations specified by the information in Bob’s public half of the key.  She sends to new and improved message to Bob.  The calculations used by Alice are very difficult to reverse-engineer. Thus, if Oscar intercepts the message he cannot backtrack to the original message even though he knows what calculations AND which public key numbers Alice used.  The only way to get the original message back is to do a second set of different calculations using…you guessed it…that number that Bob keeps secret.

This public key cryptography concept can sound very complicated and many people assume that it uses extremely high level mathematics.  The reality, though, is that the two major components are quite simple and accessible for most students.  They are:

  • Prime numbers:  When Bob makes part of his key he will find two very large prime numbers and multiply them together.  Easy!
  • Modular Arithmetic:  Sometime this is referred to as clock arithmetic.  11pm + 5 hours is not 16 am or even 16 pm.  When we get to 12 we start over to we say 11pm + 5 hours is 4am.  In modular arithmetic we might say that in “mod 12”, 11+5 = 4.

For more information on some simple ways of creating secret messages, check out the following links:

  • http://simonsingh.net/books/the-code-book/  The Code Book by Simon Singh discusses codes throughout history and explains the mathematical and scientific ideas behind them in a very accessible and engrossing manner.
  • http://www.cryptoclub.org/  This link is geared for a youthful audience but it has many cool interactive features that allow you to type a message and either encrypt or decrypt it.
  • http://www.nsa.gov/  This link is for when you’re ready for the big leagues!

Author(s)

Department Chair, Math
208.562.3132