RSA Cryptography

Cryptography (how we keep messages secure) uses Mathematics and Prime Numbers in particular.

In essence it is a lot easier to multiply primes together than to work out what primes were multiplied to make a number.

The same applies to computers but the numbers involved are much bigger.

RSA

The RSA algorithm (named after its creators Rivest, Shamir and Adleman) relies on that idea.

It is a public-key / private-key encryption algorithm that uses prime numbers like this:

• Key Generation: two distinct prime numbers, p and q, are selected. They are usually very large and randomly chosen. They are kept secret but from them we create three numbers (we see how soon):
  • n = p × q
  • e for the public key
  • d for the private key
• Encryption: The message is divided into blocks and converted into number form. Each block is then multiplied by itself e times followed by "mod n" (see modulo function).
• Decryption: To decrypt the encrypted message, each encoded block number is multiplied by itself d times followed by "mod n", and we get back the original number. Do this for each block and we have the original numbers and message.

The public key encodes the message strongly.

But only the private key can decode it easily.

You can try it at RSA Interactive

Step by Step

Let's do the actual steps using some small numbers (but when used for secure communications the numbers are 100s of digits long).

Create Keys

• Choose two distinct prime numbers p and q: let's use 11 and 17
• Calculate n = pq = 11×17 = 187
• Calculate Euler's Totient Function φ(n) = (p−1)(q−1) = (11−1)(17−1) = 160
• Choose an e (the encryption number) that is less than φ(n) and coprime to φ(n):

  Numbers less than 160 that are coprime to 160 include 7, 11, 13 and more. Let us choose 7

• Choose d (the decode number) so that (de) mod φ(n) = 1
  • Let's try e=2: (2×7) mod 160 = 14 mod 160 = 14 (not 1)
  • Let's try e ≈ 1607, say 22: (22×7) mod 160 = 154 mod 160 = 154 (not 1)
  • Let's try e=23: 23×7 mod 160 = 161 mod 160 = 1  

We now have our keys:

• Public Key: 23,187
• Private Key: 7,187

Encode The Message

Our message is really simple: hi

• Break the message into blocks: h and i
• Turn each block into a number (let's use Unicode* values): 104 and 105
• For each number m calculate m^e mod n where "mod" is the modulus function

  104⁷ mod 187 = 179

  105⁷ mod 187 = 96

• Send that message: "179,96"

Decode The Message

• For each number we receive k calculate k^d mod n

  179²³ mod 187 = 104

  96²³ mod 187 = 105

• Convert 104,105 to text: hi

Wow, it works!

 *Unicode is a standard for turning characters (letters, numbers, punctuation, etc.) into numbers. In Unicode a=97, b=98, etc. You could use any system you want really, such as a=1, b=2, etc.