25 GnuPG and the mystery of large numbers

Cryptography for non-mathematicians

There have been several attempts at ’cracking’ the RSA algorithm on which GnuPG is based1, i.e. to calculate a private key when only the public key is known. However, this type of calculation has never been successful for the key lengths (1024 Bit and above) that are used in GnuPG. While it might be possible on a theoretical level, it is practically impossible since even with plenty of time (many years) and thousands of networked computers, there would never by sufficient storage to complete the last steps of this calculation.

At the same time, it is entirely possible that one day an ingenious mathemtatical idea will provide a solution to the mathematical issues behind RSA. However, this is unlikely to happen anytime soon.

From time to time the German Federal Agency for Security in Information Technology (BSI) publishes forecasts and assessments with regards to how long certain key lengths can likely be used for absolute security guarantee. GnuPG’s standard settings far exceed these minimum requirements. As touched upon in the previous chapter, the mathemetical elements form by far the most secure portion of practically applied cryptography.

1Here we use RSA as an example, since it is easier to understand than the ElGamal algorithm, which is used as a pre-setting to GnuPG.

143

The Gpg4win Compendium 3.0.0-beta1

Chapter 25. GnuPG and the mystery of large numbers

The following discussion will show you how this mathematical method works. While not all details will be covered - as this would be far beyond the scope of this manual - with some effort on your part it will enable you to make correct en/decryption calculations and thus discover the “mystery of big numbers”.

Even non-mathematicians and mortals can understand this complex mathematical method. All that is required is a good grasp of simple additions and multiplication processes. It may be compared to the concept of a free skate, because the free skate is really much more about substance than the short program which is much heavier on the required elements. But most importantly, it will help you to understand why GnuPG is so secure.

But first let us get some terminology out of the way:

An algorithm is a mathemetical method for modifying or transforming data or information.

Arithmetics is the method by which numbers are added and multiplied.

Encryption using GnuPG is based on the so-called RSA algorithm2. RSA is derived from the last names of Ron Rivest, Ami Shamir und Ben Adleman, who discovered this algorithm in 1978. This algorithm uses a type of arithmetic which is called arithmetic with residue classes or “modular (or modulo) arithmetic” .

2RSA is actually optional since due to patent reasons the ElGamal algorithm, which is based on the more difficult to explain problem of discrete logarithm, is used as the standard.

144

The Gpg4win Compendium 3.0.0-beta1

Chapter 25. GnuPG and the mystery of large numbers

25.1 Calcualting with residue classes

Calculating with residue classes means only calculating the “residue” (or remainder) which remains after an integer division by a whole number. This number, by which the division is carried out, is called the “module” or “modular number”. If we calculate with the factor or the modular number 5, for example, this is called “arithmetic modulo 5”.

For in allustration of how arithmetic with residue classes - also called modular or congruence arithmetic - works, imagine the face of a clock:

This clock is an example of arithmetic modulo 12 (hence the factor is also 12) — a clock with an ordinary dial, except that it has a 0 where one would expect to see the 12. Using this example we can describe modulo arithmetic by simply moving the imaginary dial.

For example, to calculate 3 + 2, we begin at digit 2 and turn the dial by three digits (or start at 3 and turn by two digits, which works out to the same). The result is 5.

Using the same method to add 7 + 8, the result is 3. Why? 3 is the residual that results when dividing 15 (i.e. 7 + 8) by 12. To multiply 5 by 7, start at 0 and move forward by 5 digits each time for seven times (or begin by 0 and move forward by 7 digits 5 times). In both cases the dial stops at 11 because 11 is the residual obtained from dividing 35 (i.e.7 5) by 12.

145

The Gpg4win Compendium 3.0.0-beta1

Chapter 25. GnuPG and the mystery of large numbers

Therefore, by using arithmetic with residue classes we add and divide numbers according to the conventional rules of everyday arithmetics, while always only using the residual that remains after the division. The modulus (the factor) is added to indicate that the rules of modular arithmetic rather than conventional arithmetic are applied, hence we would say, for example, “4 modulo 5”, or in short “4 mod 5”.

A modulo 5 for example would be represented by a clock with only 5 numbers (0, 1, 2, 3, 4), hence:

4 mod 5 + 3 mod 5 = 7 mod 5 = 2 mod 5

Said another way, using arithmetic modulo 5 the result of adding 4 and 3 would be 2.

Another example of modulo 5 arithmetics:

8 mod 5 + 6 mod 5 = 14 mod 5 = 4 mod 5

You can see that it doesn’t matter in which sequence you proceed, because you could also write:

8 mod 5 + 6 mod 5 = 3 mod 5 + 1 mod 5 = 4 mod 5

3 is the same as 8, and 1 the same as 6, since you are only interested in the respective residual that remains after the division by the factor of 5.

The last examples highlight the fact that by using this type of arithmetic, you can add a whole-number multiple of the module number (here 5) at any time, but the result will always be the same.

146

The Gpg4win Compendium 3.0.0-beta1

Chapter 25. GnuPG and the mystery of large numbers

This pattern also works for multiplication.

An example:

4 mod 5 2 mod 5 = 8 mod 5 = 3 mod 5

You can also write:

9 mod 5 7 mod 5 = 63 mod 5 = 3 mod 5

since you can simply deduct 60, hence 5 12.

But you could also write:

9 mod 5 7 mod 5 = 4 mod 5 2 mod 5 = 8 mod 5 = 3 mod 5

because 4 corresponds with 9 and 2 corresponds with 7, if you examine only the residual after a division by 5.

Again, we see that it does not matter if we simply leave out the multiple of five.

Since this makes everything much simpler, we will do this before adding or multiplying numbers. This means that we only need to concern ourselves with numbers 0, 1, 2, 3, 4 when doing arithmetic modulo 5, as we can leave out all that is divisible by 5.

Three more examples:

I. 5 mod 11 3 mod 11 = 15 mod 11 = 4 mod 11

II. 2 mod 7 4 mod 7 = 1 mod 7

III.13 mod 17 11 mod 17 = 7 mod 17

The last example becomes clear when one considers that using conventional arithmetic 13 11 = 143 and 143 = 8 17 + 7.

147