RSA Two-Key Encryption

So everything in the last seven posts has lead up to this.
The RSA Encryption Algorithm is a mathematical method of generating two encryption keys. You then encrypt a message with one key, and decrypt it using the other key.
This allows you to keep one key private, and publish the other key to the entire world.

Then there are two ways you can use these keys:

1. You look up the public key of your friend, and encrypt a message using their public key. You have guaranteed that no-one can read the message except your friend.
   
2. You encrypt a message using your private key. Everyone can read it, but no-one else but you could have sent it.

So the same technology can be used to keep secrets, and prove identity. Cool.

The Euclidean Algorithm and the Extended Euclidean Algorithm

This is the last trick needed to understand the RSA method. The first algorithm is a quick(-ish) method to find the greatest common divisor between two numbers (a and b). The second algorithm also calculates values of x and y that satisfies the following equation:

$ax + by = gcd(a,b)$

Euler-Fermat Theory and Prime-testing

As mentioned in the last post, Euler-Fermat's Theory states that for any element m in a group:

$m^{\varphi(n)} = 1 \text{ mod } n$

where $\varphi(n)$ is the totient of n.
The totient of a number is simply the number of Integers that are smaller, and coprime (i.e. no common factors).

This allows us to come up with a simple (though not foolproof) test for prime numbers.
If n is a prime number p, then the number of smaller Integers that are coprime, are all of them. Thus $\varphi(p) = p-1$ for a prime number, and $m^{(p-1)} = 1 \text{ mod } p$ should be true for all the numbers m, smaller than p.

Lagrange's Theory of Finite Groups and the Euler-Fermat Theorem.

In my Group Theory post, I stated that once a Set of mathematical elements and a mathematical operation have been proven to satisfy some basic properties, all theories, proofs and facts from the mathematical discipline of Group Theory, would automatically apply.

 Lagrange's Theory of Finite Groups states that any group can only be divided up into subgroups of the same size.

Euler-Fermat's Theorem is an application of this, that says that any number (coprime to n), rasied to a special power (called the totient of n) will give 1 mod n.

The coprime and totient properties of the second theory are a consequence of the structure of the Multiplicative Group of Integers Modulo n.

Euler's Totient Function

As mentioned in the last post, when multiplying Integers mod n, there are some Integers that can't have an inverse. My example was, that it was impossible to multiply 2 by anything, that once divided by 10, gave you a remainder of 1. Likewise for 5. And if an element doesn't have an inverse with respect to some mathematical operation, then that element can't be a member of a Group.