88. | 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

Exponentiation Operations

While it is possible to attempt to raise a number to a large power, doing so will more than likely exhaust the capacity of your computer as there is a finite limit to the size of integers on each computer. Instead of directly raising a number to a power, you can do the modular reduction after each multiply operation. For example, assume you want to compute 123⁷ mod 456. Instead of computing 123 multiplied by itself 7 times and then dividing by 456 to obtain the remainder, let’s do modular reduction after each multiply. That is:

     123² = 123*123 = 15129 mod 456 = 81 mod 456     123³ = 123*81  mod 456 = 9963  mod 456 = 387 mod 456     123⁴ = 123*387 mod 456 = 47601 mod 456 = 177 mod 456     123⁵ = 123*177 mod 456 = 21771 mod 456 = 339 mod 456     123⁶ = 123*339 mod 456 = 41697 mod 456 = 201 mod 456     123⁷ = 123*201 mod 456 = 24723 mod 456 = 99  mod 456

While the preceding method reduces the computation to a series of seven small multiplies and seven small divides, most exponents used with RSA are considerably larger. This means that you would more than likely want to obtain a more efficient method to compute exponents.

To raise a number x to an exponent, you can perform a series of squaring operations. For example:

     123² = 123*123 = 15129 mod 456 = 81  mod 456     123⁴ = 81*81   = 6561  mod 456 = 177 mod 456

While you could continue and square 123 again, obtaining the value of 123⁸, unfortunately the 123⁷ that you require is not a power of 2. However, if you know what 123^x is, then it is relatively easy to compute 123^2x, since you obtain that by squaring 123^x. Similarly, you can compute 123^2x+1, as all you need to do is multiply the result obtained by squaring 123^x (123^2x) by 123. This means you can perform a sequence of squaring operations to obtain the nearest power of two to the exponent you require, and then multiply the result n times, where n is the difference between the exponent you seek and the nearest computed power of 2. For example:

     123⁷ mod 456 = 123² * 123² * 123 * 123 * 123 mod 456     123⁴ mod 456 = 177 mod 456

Then:

     123⁷ mod 456   = 123*123*123*177 mod 456                    = 123*123*339 mod 456                    = 123*201 mod 456                    = 99 mod 456

Note that the preceding method required two squaring and three multiplication operations. You can reduce the number of operations further if you note that 123^a*123^b = 123^a+b. This means given:

     123² mod 456 = 81  mod 456     123⁷ mod 456 = 387 mod 456

you would compute the following:

     123⁶ = 123²*123⁴ = 81.387 mod 456 = 339 mod 456     123⁷ = 123*123⁶ = 123.339 mod 456 = 99 mod 456

Note that in this example you would compute 123² mod 456, 123⁴ mod 456, 123⁶ mod 456, and then multiply the last result by 123. This reduces the number of computations to two squares and two multiplies.

If you convert the exponent to binary, you can compute 123 raised to a sequence of powers. For example, 7 is 111₂ which represents the sequence 1₂, 11₂, 111₂. Note that each successive power concatenates one additional bit of the desired exponent. Also note that each successive power (from the most significant bit position) is either twice the preceding power or once or more than twice the preceding power. Thus, you can raise 123 to the first, third, and seventh power by repeated squaring together with multiplication by 123 for the bits that are 1. For example, commencing with the first power you start with:

     123 mod 456

To obtain the third power, you would multiply 123 by its square, i.e., 123 (123²). To then obtain the seventh power, you would obtain the sixth power (123³)² and multiply by 123. Thus, raising 123 to the seventh power can be accomplished by repeated squaring and, as required, multiplying by 123 for the bits that are 1. Focusing on exponents:

     7 = (((1)² + 1)² +1)

Then you obtain:

     123⁷ = (((123)² * 123)² * 123)

Using the preceding method you can perform exponentiation of a base to an exponent as follows:

1. Commence by setting an initial value to 1.

2. Convert the exponent to binary.

3. Read the binary value of the exponent bit by bit from high order to low order and square your value for each position. If the value of the bit position is 1, then multiply by the base. After each operation, perform modular reduction to maintain a relatively small intermediate result.

Now that you have an appreciation for techniques to facilitate exponentiation, let’s return to the key computation process. It was noted previously that the inverse of 41 mod 3233 is:

     41³²³¹ mod 3233

Note that 3231 is 110010011111₂. This means you can compute 41 raised to the 3231 power by squaring 12 times and multiplying 8 times. Although I will leave it as an exercise for you to compute, let’s assume the answer was x. You would then publish e and n and keep the value x which represents your secret decryption key. Suppose you want to encrypt the famous message ABADABA… Then, the ASCII value of your message m is:

     m = 64656467646564…

To facilitate computations you would break the message into small blocks. For example:

     m₁ = 6465     m₂ = 6467     m₃ = 6465

and so on.

Using the encryption key of 41, the first block would be encrypted as:

     c₁ = 6465⁴¹ mod 3233

Similarly, the second block would be encrypted as follows:

     c₂ = 6467⁴¹ mod 3233

You would continue the same operation on the remaining blocks until you generated the entire encrypted message. As previously discussed, decryption would be performed on a block by block (c₁, c₂…) basis, performing the same exponentiation but using the decryption key whose value is x. Thus:

     m₁ = c₁^x mod 3233     m² = c₂^x mod 3233

and so on.

Table of Contents