The trapdoor algorithm; lock up your data with a public key. David Block.

The Trapdoor Algorithm

Methods of secret writing have been used for centuries to keep communications secure from prying eyes. And for centuries men have been devising means to break the locks, to tear the secrets from these cryptic messages. The first practical electronic computers, the British series called Colossi, were special purpose devices which were used successfully during World War II to decipher the German Geheimschreiber and Enigma messages.

When Alan Turing visited the United States electronic computer EDVAC, the men who proudly explained its workings to him had no idea that he had been working with a functioning computer for years. The secrecy which cloaked that British project continues to this day. From the small amount of information which has been released we can only guess that the operation of the machine involved heuristic methods; the actual decrypting consisted of a search for patterns by the computer, with that search being guided by the operator into paths indicated by intermediate results of the search. This synergistic relationship of man and computer, the trust and best use of these electronic giants, combines the speed and accuracy of digital circuitry with the incredible powers of the human brain. The German cipher machines could not withstand that attack.

It has long been considered axiomatic that no cipher is secure against a determined attack; consequently the publication of the method called the trapdoor algorithm took the cipher experts by surprise. Professor Donald Knuth reports (Seminumerical Algorithms, second edition, p. 386) that this method was discovered by R.L. Rivest, A. Shamir, and L. Adleman in 1977. A trapdoor algorithm is a mathematical function which goes in only one direction. In the case of ciphers, it is the rules for making a ciphered message, rules which do not tell you how to decipher the message. This article will explain how the method is applied and give a worked example, along with Basic programs useful in cryptography.

A practical advantage of the method is that the keys used to make the cipher can be public knowledge. Your agent in a foreign country does not have to memorize the keys but can write them down, since it will not help the enemy to discover them. A serious disadvantage of the method is that it requires for security that the keys be very large numbers. This means that a special computer program is necessary.

The arithmetic of the algorithm can be explained in a few words. You will remember that we are dealing throughout with only whole, positive numbers. First, the process of exponentiation, or raising a number to a power, is just multiplying a number by itself several times. For example, 5 times 5 times 5 is equal to 125. That is called raising 5 to the third power.

Second, the process of modulating a number is just finding the remainder after another number has been subtracted as many times as possible from the first number. Thus 9 mod 2 is 1; 27 mod 12 is 3. If your Basic doesn't have the MOD function, you can do it in one line:

50 IF A > B then A = A-B: GOTO 50: REM A becomes A mod B

Third, prime numbers are only those numbers which are measured only by themselves and by 1. Nine can be measured by 3 (divided into 3's with no remainder) so it is not prime. Twenty-nine cannot be divided evently into any smaller number of groups, so 29 is a prime number. (As an aside, consider the illogicality of saying that 3 divided into 9 is 3. On reflection it is apparent that what is meant is that 9 can be divided into 3 groups of 3.)

Now we are ready for the trapdoor algorithm. Take two prime numbers, which we shall name P and Q. Multiply these numbers and call the result N. Now subtract one from P and one from Q. Call this new pair R and S, and find their greatest common divisor (GCD), the largest number which measures each of them evenly.

The next step is to multiply the GCD by the product of R and S. The result of adding one to this product may, surprisingly enough, turn out to be the product of another pair of prime numbers. Call this new pair D and E. One of these numbers if your private key, D. The other number and N make up your public key.

To send a message to someone, convert the message into groups of numbers. Then raise each group to the E power and modulate it with his N. When he receives the cipher he will divide it into groups, raise each group to his D power and modulate with N. It will then be a simple matter for him to convert the resulting numbers back into the original message.

The reason this is called the trapdoor algorithm is that when the numbers chosen are sufficiently large, it is practically impossible to calculate D, even though you know what E and N are. In this case sufficiently large has been defined as numbers containing 200 digits. To calculate D would require factoring N, a process which would take over three million years worth of CPU time on a Cray-1 computer. Thus Messers Rivest, Shamir, and Adelman have come up with a method of encrypting messages via computer which depends for its security only upon safeguarding the private key, D.

There have been indications that publication of research on advances in ciphers has been discouraged by government agencies. In the case of this trapdoor algorithm an additional difficulty has been the fact that the high precision arithmetic required, calls for computer programs not generally available. The development of the following trivial example was possible through the use of special abilities of the muMath/muSimp program. That program was developed by Albert Rich and David Stoutmeyer of The Software House in Honolulu and is distributed by Microsoft in versions for CP/M, Apple II, and TRS-80 Models I and III. A practical example with a 200-digit N could be worked out in a reasonably, short time only by using a large mainframe computer with a computer algebra program. MuMath is reviewed in detail in the October '82 issue of Creative Computing.

Although the muMath program can work with numbers containing over 600 digits, the pair of prime numbers we start with must be small because, as we shall see, the intermediate steps in the algorithm will produce numbers much larger than the primes we start with. We begin our example by generating the prime numbers between 2 and 100, using the Basic program in Listing 1.

This is an implementation of the process called the Sieve of Eratosthenes, based on that ancient Greek mathematician's observation that multiples of prime numbers cannot themselves be prime numbers. (The Greek mathematicians did not consider 1 to be a number and of course did not admit the existence of 0. How can nothing exist?)

The table, which contains intermediate results as well as the pair of keys associated with each candidate for N, shows us that several combinations of the prime numbers we are investigating are unusable. Several pairs, such as 19 and 29, do not produce keys. Other pairs, such as 19 and 37, produce a key so large that we cannot handle it with muMath. The result of raising 999 to the 2333 power is a number containing almost 7000 digits. We shall choose the pair of keys, 37, 109, resulting from the pair of primes 29, 37.

The message to be enciphered must be transformed into numbers. We shall assign two-digit values to the letters: A=11, B=12, . . ., Z=36. Spaces will be given the value 37. See Figure 1. (In an actual case, a more secure cipher would be obtained by not using a regular order for numbering the letters.)

Listing 3 can be used to do the conversion, but we must now abandon Basic because the precision arithmetic required would call for slow and complicated Basic programs.

Working With muMath

Figures 2 and 3, which show muMath at work, require a little explanation. The machine prompt, the symbol telling the operator that the program is waiting for a command, is the question mark. The operator uses a colon for assignment and a semicolon to request a printout, with a left bracket to indicate exponentiation. The commercial at symbol (@) is a variable equal to the last answer the machine gave.

Figure 2 shows the process of enciphering and deciphering the first group, 132, in detail. The first four lines show the values muMath has been given for D, E, and N. Lines 7 and 8 show that raising 132 to the 37th power yields a 79-digit number, which is then reduced mod 1073 to the cipher group 169. The work sheet goes on to reverse the process, calculating the 243-digit result of raising the code group 169 to the 109th power, then reducing that answer mod 1073 to 132, thereby recovering the original message group.

Figure 3 shows the process applied to the entire message in a more compact form, without printing out the intermediate values.

This example of ciphering shows the mathematical operations of the method, but the short key numbers used destroy security. Anyone knowing the key numbers N and E could factor N quickly, using the method in Listing 2, and so recover D. A little experimentation would show him that the message had been divided into groups of three digits: only when he calculated groups of three raised to D, mod N, would he recover a range of about 26 two digit numbers. Worse still, a cryptographer looking at the cipher message would know immediately that some type of polyalphabetic substitution had been used. The methods of solving that type of cipher are well known and do not depend on a knowledge of the key. With a longer message, repetitions and frequency counts would provide valuable clues.

Returning to the trapdoor algorithm, I have one further point to make. The method requires obtaining D and E from P and Q. The security of the method depends on choosing P*Q=N large enough that N cannot possibly be factored in a reasonable time. But D and E were obtained by factoring GCD{P-1){Q-1)+ 1, a number which will approach N in size. It looks, then, as though we shall find it as hard to select our keys as it would be for someone else to break our cipher. And as Table 1 illustrates, we could choose P and Q unwisely, in which case we would lose the labor we expend in trying to factor a prime number.

Table: Listing 1.

Table: Figure 1.

Table: Figure 2.

Table: Figure 3.

Table: Listing 2.

Table: Listing 3.

Table: Table 1.