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.

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.

The Power of an Example – Modular Mathematics

Recently I took a class of students on a Physics excursion. On the trip there, I observed some of them working a Maths C assignment on modular multiplication. I knew a bit of mod mathematics from my programming experience, and was able to help them on some of the tougher concepts, but something a student said, instantly cleared up some aspects of Group Theory that I had been struggling with for years.