Some mathematical ideas from modular arithmetic used in RSA

In order to understand how RSA works you need to understand some rules of modular arithmetic. Proofs of these rules are not included here and if you want to know more go and read a good maths text book. The laws are simply summarised to make understanding the RSA section in the parent document a little easier.

Modular arithmetic is an arithmetic of integers; whole numbers greater or equal to zero (i.e. negative whole numbers are ignored). Modular arithmetic is much like normal arithmetic but it is carried out with a restricted set of numbers defined by a modulus.

Lets consider arithmetic in modulus 5 (mod 5 for short). The set of numbers used in mod 5 are the numbers {0,1,2,3,4}, if you were counting in mod 5 you would count up from 0 to 4 but instead of continuing to 5 the 'next' number is 0, and it is on this idea of a cyclic rather than a linear progression of numbers that modular arithmetic is based. Thus any integer expressed in mod 5 is transformed to the remainder of that number when divided by 5, i.e.

Numbers transformed to mod 5:

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 0
6 -> 1
7 -> 2
8 -> 3

Modular Multiplication

   | 0 1 2 3 4 
 --------------
 0 | 0 0 0 0 0
 1 | 0 1 2 3 4
 2 | 0 2 4 1 3
 3 | 0 3 1 4 2
 4 | 0 4 3 2 1
 

There are some important ideas in modular multiplication that should be mentioned:

Identity

The identity is that number which when multiplied by any other number leaves it unchanged. 1 is the multiplicative identity since multipying any number by 1 leaves that number unchanged, thus for mod 5:
1*1 mod 5 = 1
2*1 mod 5 = 2
3*1 mod 5 = 3 .. etc

Inverse

The number N has an inverse M if N multiplied by M gives the identity. Thus for mod 5:
3*2 mod 5 = 1
hence 2 is the inverse of 3 for multiplication in mod 5.

Relative primality and multipicative inverses

In the above example all the numbers except zero have multiplicative inverses. This is not necessarily the case for modular multiplication with other moduli. It is found that for modular multiplication in modulus N a number M in the set {1 .... N-1} will have an inverse if and only if it is relatively prime to N. This means that N and M have no common factors except 1. In mod 5, since 5 is a prime number, it by necessity has no common factors with any number and hence all the numbers from 1 to 4 have inverse with respect to multiplication mod 5. Zero can never have an inverse in modular multiplication.

Euler's totient function

This is an important function in modular arithmetic and for mod N is represented as J(N) in these notes. J(N) is the number of relatively prime numbers to N in the set {1 ... N-1}. Thus it indicates how many of these numbers have inverses for multiplication in mod N. J(N) can be calculated from the prime factors of N.

Prime factors and the fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every known positive composite (non-prime) integer n can be expressed as the product of a unique collection of positive primes, these are the prime factors of n. For instance 12 can be expressed as 2*2*3. This is of importance in modulat arithmetic because the Euler's totient function for mod N can be calculated from the prime factors of N as follows:
J(N) = N*[(1-(1/P1))(1-(1/P2))(1-(1/P3))...(1-(1/PM))]
where P1 to PM are the prime factors of N.

Modular exponentiation and Euler's totient function

Just as we carried out multiplication mod N we can also do exponentiation mod N. Exponentiation will be represented by the symbol "^" in these notes (i.e. "3^2" mean "3 squared"). Condider 3^2 mod 5. 3^2 = 9 and 9 in mod 5 transforms to 4. We can also do successive exponentiations i.e. (3^3 mod 5)^2 mod 5 = (3^3)^2 mod 5 . In regular arithmetic, successive exponentiations are equal to a single exponentiation where the exponent is the product of the successive exponents, i.e. (3^3)^2 = 3^6 since 3*2 = 6. For modular exponents we might expect be able to manipulate successive exponetiations in an equivalent way using modular multiplication. Consider (3^3)^2 mod 5 = 4, Multiplying the successive exponents, 3*2 = 6, which in mod 5 transforms to 1, however while 3^6 mod 5 = 4 as we expect, 3^1 mod 5 = 3, so manipulating successive exponents in mod 5 doesn't work. In fact it is found that successive modular exponentiations can be manipulated using modular multiplication, but that for exponentiation in mod N, successive exponents must be multiplied in mod J(N). Thus in the above example;
(3^3)^2 mod 5 becomes 3^(3*2 mod J(5)) mod 5 which since J(5) = 4, is 3^2 mod 5 = 4
giving 4 as expected.

Hopefully if you've read and understood the above you should have no trouble with following the maths behind RSA.