Hardware exponentiation

When doing expontiation between two integers modulus n, computer hardware optimizes this operation in a way that's not immediately obvious. Normally, one would simply multiply the base by itself by the number of times of the exponent and then do remainder division on the modulus.

However, it's important to note that this is extremely inefficient and, often times, it's also impractical since the numbers will quickly grow so large that it's difficult for the hardware to properly represent them accurately. The solution to this is the following optimization:

Generating large random prime numbers

One of the most powerful features of modern computers is their ability to generate relatively large prime numbers very quickly. To do this, they usually employ the following algorithm:

The is_prime function should be an implementation of the Miller-Rabin test, which is the industry standard for testing the primality of large numbers.

The Miller-Rabin primality test

The Miller-Rabin primality test is an extension of the Miller primality test. Specifically it uses a relatively small number of randomly chosen odd integers that are smaller than N (where N is the number being tested for primality), usually N. If and only if all these tests pass (i.e. they claim that N is prime), then we're to assume that N is prime. The probability of a large number N passing the primality test despite not being prime, when 10 different numbers are randomly chosen to be used, is at most 0.00000095367431640625 (i.e (1/4)¹⁰).

The Miller primality test

The Miller primality test is an extension of Fermat's Little Theorem.

Specifically, it says that to test a large number N for primality, we are to follow the following steps:

1. Choose a number a smaller than N. This number is a
2. Compute a^N
3. Divide the result from the above step by N and check the remainder of that division (i.e. do modulus division). If the remainder is not 1 then the number is composite (i.e. not prime) and stop. If it is 1 but N is odd, it is composite. If it is 1 but N is even, continue to the next step. Keep note of the remainder of this division (i.e. the 1) for later
4. Divide N by 2. This new number is N'
5. Compute again a^N' and then do modulus division against N. Keep note of the remainder again for later. This remainder is to be considered BEFORE in the sequence that we're keeping note of, compared to the 1 calculated in step 3.
6. Check if N' is odd. If it is, stop. If not, repeat from step 4 onwards, with N' being the new N.

Once the algorithm above is followed, you should have a sequence of numbers that you kept note of. This sequence will determine whether N is indeed prime.

The sequence needs to end in 1. If it does not, N is composite.
Any number in the sequence before 1 has to be another 1 or N-1. If it is, N is likely prime (although there are false positives!).

Diffie Hellman key exchange

Diffie Hellman key exchange is a key exchange algorithm that relies on both parties sharing information with each other, in such a way that they end up calculating the exact same number, without said number becoming publicly available, even if the connection is being eavesdropped on the entire time.

The algorithm relies on mathematical principles that boil down to number theory. Let Alice and Bob be two parties that wish to negociate a secret key with each other over an insecure channel and Eve, an eavesdropper on said channel, is recording all of their communications with each other.

To use Diffie Hellman, Alice and Bob must first agree on two public numbers: a prime number P and a generator number G which is a primitive root of P (P being prime and G being a primitive root of P are very important properties).

A number g is a primitive root of N if, for every number a coprime number to N (i.e. any number that doesn't share a common divisor with N) is congruent to a power of g modulo N. That is, g is a primitive root modulo N if for every integer a coprime to N, there is some integer k for which g^k ≡ a (mod N)

Examples of primitive roots modulo N

1. For N=2 we have generator 1.
2. N=3 we have 2.
3. N=5 we have 2, 3
4. N=7 we have 3, 5
5. N=11 we have 2, 6, 7, 8
6. N=13 we have 2, 6, 7, 11
7. N=17 we have 3, 5, 6, 7, 10, 11, 12, 14
8. N=19 we have 2, 3, 10, 13, 14, 15
9. N=23 we have 5, 7, 10, 11, 14, 15, 17, 19, 20, 21
10. N=29  we have 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
11. N=31 we have 3, 11, 12, 13, 17, 21, 22, 24

Actual algorithm

After picking a prime P and a number G primitive root modulo P (from the table above), Alice picks a random starting number that she keeps private to herself named secret_Alice . Let's assume she picks 23. Bob will do the same and pick a secret number secret_Bob which will be 14. Neither Bob nor Alice will share their secret numbers with each other.

For the sake of this example, we shall assume that Alice and Bob chose to use N=17 and G=6 (both N and G are public at all times).
Alice will calculate 6²³ modulo 17=789730223053602816 modulo 17=14
Alice will send this number 14 to Bob (public information).

Bob will do the same and calculate 6¹⁴ modulo 17=78364164096 modulo 17=9.
Bob will send Alice the number 9.

Alice will then calculate 9²³ modulo 17=8862938119652501095929 modulo 17 = 2

Bob will then calculate 14(public information)^{14 (Bob's secret number)} modulo 17=11112006825558016 modulo 17=2
2 is the secret that both Bob and Alice will end up calculating. Eve has no way, just by knowing the N=17, G=6 and the 14 and 9 numbers sent over the insecure channel, how to calculate this number.

Since the number 2 was never sent over the encrypted channel directly, Eve will not know it.

For security's sake, it is recommended that N be at least 2048 bits long.

RSA Algorithm

RSA is a public key algorithm that relies on using the principles of number theory to encrypt messages in such a way that only a specific person, owning a specific private key, can decrypt said message.

Let's assume Alice wishes to send Bob a message that only Bob knows how to decrypt. In order to do so, Bob must have previously made public his personal public RSA key, which consists of two numbers: a large modulus N and another number e such that 

(m^e)^d≡ m (mod n).