Valentine’s Day

    Today is Valentine’s Day. In place of sending her flowers I wrote my sweetheart a love letter. I could have handed her the letter, but instead Emailed it. Of course, it would not be appropriate to reveal the contents of the letter here--or anywhere. However, I confess that it included a little made-up rhyme. Sweethearts tend to be forgiving of such things. It is, as they say, “the thought that counts.” Well, here is the rhyme.

Encrypted Rhyme

    I neglected to mention that in the tradition of lovers through the ages, my sweetheart and I share a secret code. We do not really need one, and if we did Pretty Good Privacy[1] would surely suffice. But then... Lovers do not use someone else’s secret code to whisper their secrets
!

    The need to write in ways that conceal rather than reveal information may be as old as writing--I do not know.
How many children have taught themselves mirror writing, while imagining they have discovered a way of recording secrets? 

Mirror writing

    In any case, this page is not about the history of codes. Nor is it about mathematical research or about quantum computing. Several very good books have been written about codes and codebreaking. Among those I have read, my favorite is Simon Singh’s The Code Book (Doubleday, 1999).

    In this page I intend only to describe one or two amateur programming ideas or experiments, primarily from an entertainment point of view. I have always felt that doing something--experimenting or solving a puzzle--contributes to more durable understanding than just reading about the thing.

     My Valentine’s Day letter used a simple and secure code, a one-time pad.[2] This is similar to the encryption method used by the German side in World War II, which as we know was eventually “broken” by heroic means. However, the successes of Bletchley Park depended in part on knowledge of the Enigma machine, the device that created the cipher. Without this knowledge it would not have been possible to decipher intercepted messages. Operator carelessness was also a factor.[3] As long as encryption keys are not compromised, messages encoded in this way are unbreakable.

    To generate a pad programmatically one uses a pseudo-random number generator, i.e., the random function of a programming language.  This is perhaps the first point of potential failure. Some older random number generators were unsound, and in the worst case generated large cycles of repeating numbers. However, due to improved algorithms and larger word size modern programming languages boast better--more trustworthy--pseudo-random number generators.

    Another advance in the computing art is of course the ease of storing an immense pad. Micro SD cards of multi-gigabyte capacity can easily be purchased at the corner store. One can construct an encryption key and, using one of these amazing microcards, hide it in a crack in the wall. (I have not done that, so please don’t look for cracks in my wall.)

    The Valentine’s Day pad consists of 1000 text files, each containing 1000 lines of 100 characters per line. It is a mere 100 megabytes in size, the tiniest fraction of a micro SD card. In theory, at any character position of any line in any of the one thousand files, each of the printable ASCII characters is equally likely.

MyEnigma User Interface

   
Applications need a user interface--well, most do. Certainly if one has to deal with volumes of gibberish, a friendly interface is desirable. The one that I made for Valentine’s Day was put together in the Netbeans IDE. To encipher a message one can type directly into the program’s text box or paste from the clipboard. The Encode button encrypts the text, using a pad that starts at a random character of a random line of a random file. Similarly the Decode button decrypts it. It is possible to encrypt the encrypted text, and so on, but there wouldn’t be much point in that.



Public Key Cryptography

    Like thousands of others I first came to learn about a new kind of cipher that did not require sending a key, by reading Martin Gardner’s Mathematical Games column in Scientific American, August 1977. [4] The “public key” encryption concept was based on the asymmetry of multiplication and factoring. Multiplication is easy, factoring hard. That much I understood, but the details were shaky. Maybe I did not try hard enough, or possibly I was frightened by big numbers. My initial understanding of RSA was roughly equivalent to my current understanding of Shor’s algorithm.[5] (And the latter is definitely due to laziness.)

Modulo by Doublings    Modular arithmetic makes big numbers smaller. For example, to use Fermat’s theorem a p - 1  ≡ 1(modulo p) it isn’t necessary to compute a to the p 
1th power. If it were, the enterprise would fail.

    MUMPS is not a mathematical language. However, the verbosely commented function definition (left) shows how very few multiplications are needed to compute a modular result, even when the numbers involved are very large.

    At some point I decided to try out RSA using manageable primes and
a very short message. This can be done using a calculator, without programming. However, I used Delphi (Object Pascal) for this study. Delphi and its successors are fine products, but... I have encountered frustration when porting something from an older version to a more recent one. The “encryption studies” Delphi project included some components that are not supported in Embarcadero XE2 and later versions. In practical terms that means I have to drag the old computer from the closet--or lift it, which is worse--and fire up Delphi in order to verify my memory about this part of my story.

    The old computer has something wrong on the motherboard--not the battery, which I replaced. It needs to be “charged up” for a while before it will boot. That is why I am including this irrelevant information. It is charging as I write.

    OK, got it! Had to copy a .dll from the old computer to the folder where the “encryption studies” executable is stored on my current working computer. This problem could probably have been avoided by compiling the .dll into the executable to begin with.

Encryption Studies
   Interesting!  I had forgotten about the DES part... Upon clicking the “Generate” button (lower left), the program finds two 4-digit primes and computes their product.



Generate Primes
    Strictly speaking,  the key should be longer than
the test message. However, the idea should be clear enough, if the demonstration is a little sloppy.


    The demonstration (bottom right of form) consists of numbered steps. Each step has an associated button except step 3, in which the test message is entered.
RSA Demonstration Steps
    For the illustration on the left, I clicked the step 1 and step 2 buttons in turn, to compute R and phi(R), and then to generate suitable values n and m whose product is congruent to 1 (mod phi(R)).

    A default test message is shown in step 3.  Note that to compute phi(R) (the number of numbers between 1 and R 
1 that are relatively prime to R) requires knowledge of the factors of R. phi(R) = (P − 1) ∙ (Q  1).

    Step 4 encodes the message using the public key R and n. While the message is decoded using the private key R and m in the final step.

    Many superior explanations of public key encryption may be found on the Internet, some including simple computational examples. One approach to enhancing understanding, as illustrated here, is to program the computations that make up the steps of the algorithm, bearing in mind that real-world applications of public key encryption require much larger numbers (such that R is not factorable by ordinary means) and hence more sophisticated computational methods.

    One final remark...  If I ever travel on the Trans-Siberian Railway from Moscow to Vladivostok, I will leave all this stuff at home--won’t need it anyway, because my sweetheart will be with me.




[1] http://en.wikipedia.org/wiki/Pretty_Good_Privacy
[2] http://en.wikipedia.org/wiki/One-time_pad
[3] Machine settings were sometimes guessable and sometimes reused.
[4] Reprinted in: Martin Gardner, Penrose Tiles to Trapdoor Ciphers (W. H. Freeman, 1989).
[5] http://en.wikipedia.org/wiki/Shor’s_algorithm