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.
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 would surely suffice.
But then... Lovers do not use someone else’s secret code to whisper
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
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
is Simon Singh’s The Code Book
this page I intend only to describe one or two
programming ideas or experiments, primarily from an entertainment point
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.
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. As long as encryption
keys are not compromised, messages encoded in this way are
To generate a pad programmatically one
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
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.
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. 
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. (And the latter is
definitely due to laziness.)
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
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.
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.
Strictly speaking, the key
should be longer than the
test message. However,
the idea should be clear enough, if the demonstration is a little
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.
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 −
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.
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.
settings were sometimes guessable and sometimes reused.
in: Martin Gardner, Penrose
Tiles to Trapdoor Ciphers (W. H. Freeman, 1989).