85. | Learn Encryption Techniques with BASIC and C++

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

Table of Contents

Modular Multiplication

To continue your examination of modular arithmetic, let me turn your attention to modular multiplication. Figure 8.4 contains a modular 10 multiplication table, indicating the mod 10 values obtained by multiplying each row value by each column value, mod 10. For example, 8*8 mod 10 is 64 mod 10, which is 6 with a remainder of 4 when divided by 10, producing a result of 4.

Figure 8.4 Modulo 10 multiplication.

If you examine the multiplication table illustrated in Figure 8.4, you will note that multiplication by 1, 3, 7, and 9 will work as an encryption key since each multiplication results in a one-to-one substitution of the digits. You will also note that multiplication by 0, 2, 4, 5, 6, and 8 will not work as an encryption key. For example, if you attempted to encrypt by multiplying by 2, half the numbers would be duplicates and result in the loss of information. Thus, you would not be able to correctly decrypt using a multiplier of 2.

If you select an appropriate multiplier using modular 10 multiplication, it becomes possible to both encrypt and correctly decrypt data. Concerning the decryption process, similar to modular arithmetic addition, you can undo the effect of modular multiplication by multiplying by an inverse. Here the inverse is known as the multiplicative inverse.

In ordinary arithmetic the multiplicative inverse of x is 1/x, which results in a fraction when x is an integer. In modular arithmetic, the set of numbers you work with are all integers. Thus, the multiplicative inverse of x, which is written as x^-1, is the number by which you multiply x to obtain 1.

For example, consider 5^-1 mod 4. This means what number multiplied by 5 mod 4 results in a value of 1. Because 5 mod 4 has a value of 1, this is a relatively simple problem whose answer is 1. However, as you will note later in this chapter, finding the multiplicative inverse can become a daunting task.

Returning to Figure 8.4 which contained the modulo 10 multiplication table, only the numbers 1, 3, 7, and 9 have multiplicative inverses modulo 10. For example, 7 is the multiplicative inverse of 3, while 9 is the multiplicative inverse of 1. Thus, encryption could be performed by multiplying by 3 while decryption could be performed by multiplying by 7. Note that both 1 and 9 are their own inverses. Thus, similar to modular addition, modular multiplication could be used to encrypt and decrypt, although you do have to be careful of the manner by which you select digits.

Finding the Multiplicative Inverse

The ability to find a multiplicative inverse in modular arithmetic can be difficult, especially when n is large. For example, if n was a 50-digit number you could spend a considerable period of trial and error time searching for an inverse. Fortunately, the Euclidean algorithm can be used to find the inverse as, given x and n, the algorithm finds the number y such that x*y mod n = 1.

The reason multiplicative inverses are important is the fact that they are the only numbers that do not share any common factor other than 1. This means they are in mathematical terms relatively prime numbers. For example, from Figure 8.4 the numbers 1, 3, 7, 9 are the only ones with multiplicative inverses. That is, the largest integer that divides both 3 and 7 is 1. Similarly, the largest integer that divides both 7 and 9 is also 1. In comparison, 2, 4, 6, and 8 do not have a multiplicative inverse modulo 10, and are not relatively prime to 10. For example, 2 divides 4, 6, and 8. This means that you can use mod n multiplication by any number x relatively prime to n as an encryption key since you can multiply x to encrypt and x^-1 to decrypt. Although whether or not the scheme is secure remains to be determined, this means encryption can occur via multiplication by x mod n, while decryption can occur by multiplying the enciphered data by x^-1 mod n.

The key, again no pun intended, to the use of numbers that have multiplicative inverses is to use relatively large prime numbers. Thus, prior to moving forward, let’s review prime numbers.

Prime Numbers

A prime number is a number greater than 1 that can be divided evenly only by itself and 1. The first 20 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71. The fundamental Theorem of Arithmetic indicates that primes are the building blocks of the positive integers. In fact, every positive integer is a product of prime numbers. Such products are referred to as composites. Thus, there are three types of natural numbers: primes, composites, and unity.

The ancient Greeks proved mathematically that there are an infinite number of primes and that they are irregularly spaced. During the late 1990s the use of primes in public key cryptology resulted in thousands of persons searching for larger primes. Through the use of specialized software, a prime consisting of 895,932 digits was discovered in 1997.

Three of the more interesting types of primes are Mersenne primes, twin primes, and Sophie Germain primes. Mersenne primes are primes of the form 2^⊥p-, and are the easiest type of number to check for on a binary computer. Although 36 Mersenne primes have been discovered, several regions of numbers between previously identified primes have not been completely searched, and it is not known if the largest is the 36th.
Twin primes are primes of the form p and p=2, and differ by two. A Sophie Germain prime is an odd prime p for which 2p+1 is also a prime. This category of primes was named after Sophie Germain who provided the first case of Fermat’s Last Theorem, i.e., xⁿ + yⁿ = zⁿ has no solutions in non-zero integers for n>2 for exponents divisible by such primes.

Table of Contents