84.

Learn Encryption Techniques with BASIC and C++
(Publisher: Wordware Publishing, Inc.)
Author(s): Gil Held
ISBN: 1556225989
Publication Date: 10/01/98

Previous

Table of Contents

Next

Modular Addition

When you perform modular addition, the value you obtain for a+b is the same as in normal arithmetic when a+b<n. Otherwise, when a+b>n, you would subtract n from the sum. If the result is less than n, you would obtain the modulo sum. Otherwise, you would continue to subtract n from the previous result until a value less than n is obtained. This action is equivalent to dividing by n and using the remainder as the result.

For example:

     8 + 6 + 3 + 9 + 2 + 6 (modulo 9) = 7 

because the sum in normal arithmetic is 34. When divided by 9, you obtain a remainder of 7.

---

Now it can be told!

Many years ago during the era of communism, I was selected to represent the United States at an engineering conference in Moscow. At that time most home telephones of dissidents and refuseniks were monitored by the KGB; however, most public telephones were not, as there were too many even for the resources of the Soviet spy agency. After meeting with dissidents and refuseniks, I agreed to carry a list of public telephone numbers and calling times out of Moscow so those assisting these harassed persons could communicate with them. Because it wouldn’t be smart to simply carry out a list of telephone numbers, those numbers were encoded using modulo 9 arithmetic, and an extra digit was added so that the numbers appeared to represent the combination to a safe or lock. For example:

original telephone number:	4770293
modulo 9 number:	5229706
“safe combination”	522-97-063

Upon return to the free world it was a relatively simple process to convert the “safe combination” back into its telephone number. To do so, all that was required was to add the appropriate digit to each number to obtain nine and discard the last digit. For example, 5 + 4 = 9, so the first digit is restored to its original value of 4. Similarly, 2 + 7 = 9, resulting in the second digit of the restored telephone number reconstructed to its original value of 7.

For several years after I visited Moscow, my “modulo 9” number scheme was transported via tourists and in postcards to inform persons in the United States, the United Kingdom, France, and Israel of public telephone numbers they could call, and the date and time to call.

---

If you perform mod 10 addition, you can simply use the last digit of the answer. Similarly, if you perform mod 100 addition, you can use the last two digits. For example:

     6 + 13 mod 10 = 9,     114 + 8 mod 100 = 2, and     9 + 8 mod 10 = 7 

Note that 9, 19, and 29 all represent the same mod 10 number, while 33, 133, and 233 all represent the same mod 100 number. In such situations it is common to use the symbol “@” for equivalence for each series of numbers. Under modular arithmetic two equivalent numbers can be considered as different names for the same mod n number.

Figure 8.3 illustrates results obtained by the construction of a mod 10 addition table. Note that, similar to the sidebar story about my use of modulo 9 addition to encrypt telephone numbers, you can also use a constant modulo 10 as a scheme for encrypting digits. This is because the use of a constant modulo 10 maps each decimal digit into a different decimal digit, such that the process is reversible. In doing so, the use of a constant modulo 10 becomes your “secret” key and decryption is performed by modulo 10 subtraction. Thus, let me turn your attention briefly to modular subtraction.

Figure 8.3  Modulo 10 addition.

Modular Subtraction

There are several methods you can use to perform modular subtraction. To illustrate these methods, assume you wish to perform the operation (a-b) modulo n. If a>b, you would simply subtract b from a. If a<b, you would add n to a prior to subtracting b. For example, (7–8) modulo 10 is equal to 7+10–8, or 9.

A second method you can use to perform modular subtraction is by adding –b, which is referred to as b’s additive inverse. Returning to our previous example and noting that the additive inverse of a number is the number you have to add to it to obtain zero, you have:

     (7–8) modulo 10 becomes equivalent to 7–(–2) = 9 

In the preceding example note that 8’s inverse is 2, because in mod 10 arithmetic 8 + 2 = 0. Thus, if the secret key was 8 for encryption, you would add 8 mod 10, while decryption would be performed by adding 2 mod 10.

Previous

Table of Contents

Next