An Introduction to the Art and Science of Enciphering, Encrypting, Concealing, Hiding, and Safeguarding Described Without any Arcane Skullduggery but not Without Cunning Waggery for the Delectation and Instruction of Ms. Doyle's Second Period Number Theory Colloquium
The reader might, after picking up this paper, be wondering who the rather unhappy looking character is on the title page. That is Mr. X, a cunning cryptanalyst with very shady intentions and the resources of any CIA agent worth his salt. Now that introductions are over with, we can get down to this public-key cryptography business. It turns out that the math we learned in our number theory class for public-key cryptography can be used in other cryptographic schemes as well. One possible drawback of public-key cryptography is that each person must know the public key of every person they want to be able to send secure messages to. For instance, if Ms. Doyle has nineteen students in a hypothetical number theory class and wants to send a secure message M to all of them, she has to have nineteen public keys (e_i, n_i) in her computer. If each of those students wants to be able to send messages to any other person in the class, they all have to have nineteen public keys in their computers as well. An alternative to this is to have one central location with all twenty public keys, but then anyone wishing to send any secure message must go and get the needed public key each time. Of course, Mr. X does have ways to defeat the good-natured encryption purposes of Ms. Doyle and her pupils, but the second appendix, not this paper, is partly devoted to a description of his methods. We strongly suggest that the reader refer to that appendix after reading this paper.
A slightly different message-sending scheme, known as Shamir's no-key algorithm, can eliminate the need for publicly available public keys altogether. If Leif, who has a public key (e_L, n_L) and an unpublished private key (d_L, n_L), wants to send a message to Marty, who has a public key (e_M, n_M) and a private key (d_M, n_M), but doesn't know his public key, he can encrypt the message with his own public key and send the encrypted message C to Marty, where
Then Marty encrypts the message with his public key and sends the twice-encrypted message D back, where
which Leif then decrypts using his own private key (d_L, n_L) to obtain a once-encrypted message S, essentially encrypted with Marty's public key (e_M, n_M) as follows:
He sends S back to Marty, who can use his private key to decrypt and read the real message M by using his private key:
This scheme requires more messages to be sent (four, to be exact), but nobody has to know anybody else's keys. (Beutelspacher, 126) Even if some public keys are known, it is not a problem as long as both people exchanging messages remember to encrypt first with the public key then decrypt with the private key.
An interesting variation is RSA key exchange, which is the system implemented by Zimmermann's PGP (see the second appendix for a somewhat more complete description of PGP). This system doesn't actually encrypt the entire message with the public key. What it does instead is make up a one-time cipher (which is essentially a random number a_1 generated using a specific random number seed s_1) and encrypt the message M using the one-time numbers. Then the keys to the one-time cipher (a_1 and s_1) are encrypted using the public key e, and both the encrypted one-time key and the encrypted message are sent together. The main advantage of this algorithm is speed; the conventional one-time encryption runs faster on a computer than public-key encryption.
A rather inane system of creating public and private keys using public communications is the Diffie-Hellman key exchange, in which both people communicating agree on a common key to use, rather than one user choosing a key and forcing the other to use it as well. The mathematical trick with this system is to allow two people who do not share a common secret (such as both parties knowing a single private key) to determine a secret key with only public communications. Since we believe this algorithm is completely pointless, we do not include the mathematics, but the reader is invited to find a complete description in other sources. (Beutelspacher, 124)
We also attempted to implement the RSA algorithm ourselves. The main challenge we faced was to make the computer do math with numbers larger than those the computer could handle at one time (the computer can only accurately compute integer results smaller than about 4 200 000 000). That is, the computer can do math with numbers no larger than 32 bits normally, but we wanted to be able to make 500 or 1000 bit keys and compute exponential values with them. We essentially had to relearn how to do math digit by digit; for a mostly complete explanation of the mathematics of addition and multiplication digit by digit, refer to the appropriate appendix. We believe that we were able to make algorithms which did this correctly, but they never ran correctly. It probably has something to do with Windows 95.
Postscript: We really did learn much about implementing public-key cryptography, even if we did not manage to implement it ourselves. If the reader does not believe us, refer to the appendices and reread the paper.
That is a good question. Most people think very little about the processes of addition and multiplication once they get past the fifth grade and learn how to perform arithmetic in base 10 without trouble. One of the biggest (perhaps the biggest) problems we came across was the task of performing precise arithmetic on long strings of integers in a base other than base 10 (we chose base 256, as an example). For our purposes, we need to define a way to write two integers in any base b. Consider two such integers a and b of any length m and n, respectively, which we will define as:
where
Now that that's over, we need to return to the second grade when Mrs. Brandon used to write those really big base 10 numbers on the chalkboard and add them magically together like:
8709 + 23 ------ 8732
which we call long addition. Of course, long addition is actually quite complicated and involves much more thinking for most people when we switch out of base 10 into another base.
So how do we actually add? The process is basically to line up the numbers so that the ones digits match and the b's digits match and the b2's digits match, and so on. Once that is accomplished, start from the ones digit and proceed to the left, adding each pair of corresponding digits along with the carry from the previous addition. Wait a minute—what was that about a carry? Well, since each digit in the summation must be between 0 and b (including zero but not including b), we need to mod each summation by b and then put the greatest integer of the summation divided by b into the carry, which is added into the next summation. This is obviously a recursive process, and we can define it mathematically using a lot of piece wise functions. For our purposes on the computer, we define the addition of any two integers a and c (as defined above) in any integer base b as
where
and
Let that sink in for a while and then continue on with multiplication.
Whew! Now that we have addition down, we need to turn to the next question: how does one multiply two numbers? The answer, in this case is not simply to whip out one's TI and punch in four times five, hit enter, and get the wonderful answer of twenty. To multiply in any base, we must think back to the fourth grade, where Mrs. Badgett wrote things on the chalkboard like:
9541
x 23
-------
28623
+ 190820
----------
219443
which is known as long multiplication. Long multiplication can be thought of as a matrix of numbers to be added together. Each row in the matrix is obtained by isolating one of the digits of the bottom number being multiplied (23, in this case) and applying an algorithm to that number and all of the digits in the top number. When all digits in the bottom number have been used, the rows in the matrix are summed to get the final answer. This process can be represented mathematically by the following equations:
where
and
If all these equations were comprehensible, then we have succeeded. If not, try doing some example additions and multiplications in base 10 or a different base (16 is convenient). Reread this after the examples and see if it makes sense. It does to us, but we wrote this. We leave to the reader the more complex but probably just as interesting tasks of division and subtraction.
In a good implementation of public-key cryptography, such as Philip Zimmermann's PGP (Pretty Good Privacy) software, an encrypted message is as good as impossible to crack directly. However, there are ways to slip around the encryption, ways not directly related with the RSA algorithm at all. One of these ways is by impersonation. That is, if Ms. Doyle were to encrypt a message with Leif's public key, only he would be able to read it, but if Mr. X were to publish a different public key under Leif's name, and Ms. Doyle were tricked into using that, Mr. X could then read that message. If Mr. X wished, he could then re-encrypt the message with Leif's real public key and send it on to him, so no one would know that the message had been intercepted. PGP has safeguards against this very occurrence. There are ways of verifying people's public keys, to be sure that they are in fact from that person. PGP will print out a signature for a given key, a fraction of the key that is easier to read than the entire key but still long enough to be almost certainly unique. It would then be easy for Ms. Doyle to contact Leif in person, so that she knows she is in fact talking to Leif, and exchange signatures. Sometimes this is not practical, so PGP has a system of certifying public keys. That is, if Ms. Doyle knew Jen and trusted her public key and her judgment, and Jen knew Leif and his public key, Jen could take Leif's public key, certify it, and give it to Ms. Doyle. Ms. Doyle could then be sure that she had Leif's real public key, without ever having to actually meet him to verify it.
There are also things a user must keep in mind when managing his or her private keys. Every person who uses a public key cryptography system has to have files on a computer somewhere which contain the user's private keys as well as his or her trusted public keys. Zimmermann warns against keeping those files (called keyrings) on any computer connected to a network or a timeshared computer. The keyrings themselves are kept encrypted by a pass phrase known only to the user, so the main consideration is not that someone may be able to decrypt the keyrings, but that the software may leave the decrypted keyrings in memory, and another user could, with the right program, grab them. By keeping the keyrings encrypted, they are safe from any sort of direct attack, like cryptanalysis or a brute-force password guesser or even a physical assault on the computer, but there are ways to weasel around the security if the user isn't careful: a poorly chosen pass phrase, stray bits left in memory, or leaving the keyrings on a public computer.
There are several other little details in a complete public-key cryptography system that, if ignored, could make the whole system insecure. Mr. X could infect Leif's computer with a virus which interferes with the encryption software, or give him an altered version of the program which is less secure. Leif could avoid this by being careful about viruses (a good idea anyway) and getting his software only directly from the source or from a trusted friend. If Leif encrypts repetitive data to send to Ms. Doyle, it may make it easier for Mr. X to decrypt it. For that reason, Zimmermann's software always compresses the data it sends before encrypting it, which reduces any repetition. (On a small but interesting tangent, it is interesting to note that Mr. X may have equipment known as TEMPEST, which can determine what is on Leif's computer screen from the radio signals emitted from it and the video cable. For that reason, good software will never actually print on the screen Leif's pass phrases, the data before being encrypted, or any data which could help Mr. X decrypt the message.)
It should be fairly obvious by now that although the public-key cryptography system and its variations are essentially unbreakable by any potential Mr. X's that happen to be eavesdropping, methods do exist for Mr. X to obtain the information he desires by stepping outside of the public-key system and resorting to his own espionage technology.
All characters used in this number theory paper are purely fictional and not intended to be related in any way to any person, living or dead. Mr. X is a character used from Albrecht Beutelspacher's wonderful book cited in the bibliography, and the extensively over-vocabularized introductory clause on the cover page was taken from the aforementioned wonderful book's title page.
Beutelspacher, Albrecht. Cryptography. J. Chris Fisher, trans. Washington, D.C. : The Mathematical Association of America, Incorporated, 1994.
Rosen, Kenneth H. Elementary Number Theory and Its Applications. Third edition. New York : Addison-Wesley Publishing Company, 1993.
Check out encryption in action at http://rsa.com/, home site of the original creators' company. Ravest, Shamir, and Adleman have a patent on the most popular public key encryption algorithm used today. This is encryption in real life. Be sure to look at the RSA Cryptography FAQ for some good information.
Pretty Good Privacy, Secure Shell, and the GNU Privacy Guard are all popular encryption tools in use today. If you use telnet on a regular basis, I strongly suggest looking in to using a secure shell instead.
http://distributed.net/ has organized a brute-force approach to RSA Labs' encryption contest. Winning computers can get money for breaking codes (pretty cool !).
Created and published