Basic cryptography: SBOEPN DJQIFST. Daniel D. Wheeler; Elisheva Perri.

Basic Cryptography: SBOEPN DJQUIFST

The personal computer is a powerful tool for cryptography. With a bit of simple programming you can encipher secret messages to your friends so securely that it would take the efforts of a mathematical cryptographer to unravel the system. But with the proper keyword a friend can use his computer to decipher and read your message.

There have been several programs for simple cryptography published in the major computer magazines. Some of these programs, unfortunately, have used very weak systems for enciphering the messages. Anyone with a little knowledge of cryptanalytic techniques could break the system and read the messages without knowing the keyword.

This article explains the principles of computer cryptography and demonstrates the use of the Basic random number function for enciphering messages. Versions of the program are included for the Apple II, the TRS-80 Models I and III, IBM PC, and the Atari 400 and 800.

Cryptography by Addition

Letters are represented in computers as numbers. This makes it easy to use the arithmetic operations of Basic to transform the letters. The simplest system is just to add a constant number to the character code for each letter. If the result is too large, subtract the number of characters being used so that the result is again a valid character code. Suppose, for instance, that you want to use three as the constant and that your messages consist of only capital letters. Then each letter in the message will come out as the letter three letters further on in the alphabet. The letter A (ASCII code 65) will appear as D (ASCII code 68), B(66) becomes E(69), and so forth. A the end of the alphabet, X (88) becomes the ASCII code 91. But 90 is Z and 91 is beyond the end of the alphabet. So 26 (the number of characters we are using) is subtracted from 91 to produce 65. Thus X wraps around to the beginning of the alphabet and becomes A.

The Basic statements necessary to do this are quite simple. If the letter to be transformed is stored in the string A$, you can do it with:

100 X = ASC(A$ )

110 X = X + 3

120 IF X > 90 THEN X = X - 26

130 A$ = CHR$ (X)

The ASC(A$ ) function converts the character to a numeric variable so that the arithmetic can be done in the next two statements. The CHR$ (X) function converts the numeric result back into a string.

To decipher the message, change lines 110 and 120 to:

110 X = X - 3

120 IF X < 65 THEN X = X + 26

This system is called a Caesar cipher because Julius Caesar is said to have used it. It may have fooled the Gauls, but now any bright elementary school student (maybe with a hint) can break the system. Part of the title of this article is in the Caesar cipher, but not with an offset of three.

Better Systems

The weakness of the system comes from the use of the constant. There are only 25 possible constants to try and once you figure it out it is easy to decipher the whole message. You can improve the system by changing the offset for each character. You might try adding one to the offset each time you encipher a character and then subtracting 26 from the constant whenever it gets too large. This will produce a cipher that is much more difficult to break.

There are many possible schemes for changing the offset. Any scheme will work to make the cipher more difficult to break. But if the scheme is simple (like adding one) and repeats at fairly short, regular intervals, then it is not very difficult to figure out the pattern and break the cipher. A smart high school student could do it.

What you need is an irregular pattern that doesn't repeat within the length of the messages you are interested in sending. The random number function in Basic provides a very irregular series of numbers. They do repeat eventually, but the cycle is much longer than any messages you will ever send on your computer.

If the random number function were truly random, it would not be useful for our purpose. Once you have enciphered a message, your recipient must be able to generate the same sequence of numbers to decipher the message. Fortunately, most versions of Basic provide some way to "seed' the random function so that it generates the same sequence of numbers.

In Applesoft, for instance, calling the random number function with a negative argument, such as RND (-99), seeds the generator to start at a definite place in the sequence. If you agree beforehand on a number to use as the seed, your friend will be able to decipher your message by generating the same sequence of numbers to use as offsets.

Demonstration Programs

Listings 1, 2, 3, and 4 show programs to demonstrate these techniques for four popular microcomputers. Each of the programs enciphers or deciphers a one-line secret message. Instead of enciphering just the letters of the message, these programs encipher everything: letters, numbers, punctuation marks and even spaces. (The ASCII code for the space is 32. It is just as much a character as any of the others. You must be especially careful in typing the enciphered message to get all the spaces exactly right.)

The program lines in the 100's initialize the random number generator. For the Apple this is simply a matter of calling the random number generator with a negative argument. The variable X in line 130 is included only to make a complete statement; the value stored in X is never used.

Setting the random number seed on the IBM PC is a trivial process, as the RANDOMIZE function allows automation of the seed generation. By omitting an argument in the RANDOMIZE command in line 110, the PC will return with the default input statement, Random Number Seed (-32768 to 32767)? You may then input your cipher base value. The message is input with an INKEY command, so backspacing is impossible. It should also be noted that messages for enciphering must be input in upper case, for proper decoding. The rest of the program follows other Microsoft versions closely.

There is no instruction to initialize the RND() function in TRS-80 Level II Basic, but it can be done with POKEs into memory. Lines 130-150 show how to do it. POKEs can only be done with numbers smaller than 256. The instructions in lines 140 and 150 break the larger seed (stored in N) into two parts, each less than 256.

We couldn't figure out how to seed the RND() function in Atari Basic, so we'll show you how to write your own random function. The initial seed must be a decimal fraction between zero and one. In lines 110-140 the program gets a number and then divides by 100,000 to make it a fraction.

The lines in the 200's allow you to select whether the message will be enciphered (by adding the random numbers) or deciphered (by subtracting the random numbers).

The next section of the program (300's) allows you to enter your message. For the Atari this is a straight-forward INPUT statement. Then the loop in lines 340-360 converts the characters to the numeric (ASCII code) values and stores them in the array IN(). But neither the Apple nor the TRS-80 allows commas within input strings. The comma is used to separate multiple items in the input. Since we wanted to include the comma as an allowable character we used the single character input commands. These car GET on the Apple and INKEY$ on the TRS-80. The program loop starting at line 330 accepts single characters, converts them to numeric form, and stores the ASCII codes in the integer array IN%().

When the message is completely entered, the program goes to the section either to encipher (400's) or decipher (500's) the message. There are 59 possible characters from "space' (ASCII 32) to Z (ASCII 90). To encipher the message we should add a random integer up to 59 to each of the character codes. This is easy on the TRS-80.

The RND() function with arguments larger than one returns integers in the range from one to the value of the argument. Thus RND(59) returns integers from 1 to 59. These are added to the character codes in line 420. Line 430 subtracts 59 if the result is out of the allowable range. Line 430 converts the numeric code to a character and prints it. The loop in lines 410-450 repeats this for each character in the message.

The Apple RND() function returns decimal fractions between zero and one. To convert to a random integer we multiply by 59 and use the INT() function to make the result an integer. This appears in line 420. The rest of the loop is exactly the same as for the TRS-80.

In the Atari version we don't use the built-in RND() function. We store the seed for our own random function in the variable N. To get each successive random number we multiply N by 997 and take the fractional part of the result to use as the random number and to store in N for generating the next number. Line 420 does this by calculating 997*N and subtracting the integer part to leave the fractional part. Then N is used in line 430 as a random number in the range zero to one, just as in the Apple version.

The section to decipher the message (lines in the 500's) is exactly the same as the enciphering section except that the additions and subtractions are reversed. It will restore an enciphered message to its original form.

Extending the Demonstration Programs

These demonstration programs are not intended for practical use. They can, however, be extended to meet your cryptographic needs. You will certainly want to put in a loop so that your messages can be more than one line long. You will probably want the output written on disk or cassette so the person receiving your message won't have to type the random-appearing enciphered text. Output to a modem for telephone communication is another possibility. Your imagination is the only limit.

Breaking Random Ciphers

You might think that the ciphers based on random number generators would be impossible to break. After all, the enciphered message looks just like a random sequence of characters. There is no pattern to give clues to the content of the message. During World War II the Germans were confident that their machine cipher was secure. But first the Poles and then the British were able to break it. Churchill was reading Hitler's war dispatches--sometimes even before they got to Hitler.

The method requires that the cryptographer be able to guess a word in the message. For instance, if the message looks as though it was intended as a letter, it is likely to begin "Dear . . .' The cryptographer subtracts the ASCII codes for "Dear' from the message to recover part of the sequence of the random number generator. It is possible to figure out from a few numbers where the random number generator is in its sequence. Then it is a simple matter to generate the entire sequence and decipher the whole message. If the first attempt doesn't work, the cryptographer tries other probable words in all possible positions in the message.

There are techniques for enciphering messages that are resistant to the probable word method. If you have a serious security problem you should get a commercially available, tested system. But for most personal computer users the ciphers based on the Basic random function provide a reasonable degree of security. Unless your lover's spouse is a mathematician, you'll be able to keep your letters secret with Basic random ciphers.

Table: Listing 1. Apple II version of the random cipher program.

Table: Listing 2. TRS-80 version of the random cipher program.

Table: Listing 3. Atari version of the random cipher program.

Table: Listing 4. IBM PC version of the random cipher program.

Table: Sample Run.