We learnt about the basics of cryptography when we learnt about ciphers and secrets. These involve symmetrical cryptography, meaning that the person doing the enciphering and the person doing the deciphering bothe used the same key. It’s great, but shared secrets have always been the challenge of encryption:
- How do we share the key?
- If the key is too simple and it can be cracked. If it is too complex they can be forgotten or stolen, or the secret can become bigger than the message.
- If a key is stolen then the attacker can both read and write messages.
Asymmetric Cryptography
So how do we communicate confidentially without a shared secret? Enter asymmetric cryptography. Two keys, one for encrypting and one decrypting.
Merkle opened a bag of sorts, but mathematicians at Stanford were also looking at the problem. This is a good time to mention that we are moving from algorithms to maths. Instead of following a procedure, we’ll be using functions for the encryption. Why is this? Maths has a lot of hard problems, hard problems that very smart people have been trying to solve for many years, sometimes hundreds of years. It also has problems that are a lot easier to do in one direction than the other. This suits us, because we want it to be fast to encrypt and for authorised decryption, but we want it to take bad guys a long time, a very long time to decrypt. It also offers more assurance of security, in that the difficulty in solving the problem can be calculated.
The general pattern for modern encryption is:
- Convert the message to a number
- Encrypt it
- Send it
- Decrypt it
- Convert to letters
One wayness is a feature we can create with maths, but it is difficult for everyone to decrypt, good guys and bad guys – the symmetry is not broken. So we need something called a trapdoor one way function.
This is where asymmetrical encryption comes in, it uses a different key for encryption and decryption – public and private keys. Everyone has access to the public key and can encrypt a message, but the public key can not decrypt the message – only the private key can decrypt. The public key can also decrypt messages that are encrypted by the private key.
RSA Algo
Rivest, Shamir and Adleman created RSA encryption. The RSA algorithm is quite simple. The devil is in the details.
| Encrypt | Decrypt |
 |  |
- where x = plain text
- e = encryption key
- d = decryption key
- n = modulus
- y = cipher text
RSA Key Gen
The trick is in generating the inputs, and it is done like this:
- Choose two primes, p and q
- Multiply p and q to obtain the modulus, which must be long enough for the message eg at least 4 digits for my name. n = p.q
- Calculate the super secret ‘m’ (the Euler Totient), m = (p-1)(q-1)
- Pick an encryption key, it can be any co-prime of m (a co-prime is a number that only shares 1 as a factor with another number.
- Calculate the decrypt key, d – the inverse of emod(m)
- Keep: e, d, n
- Destroy: p, q, m
Reflection
This is quite amazing. The actual maths is not difficult to apply, yet the result is very powerful, asymmetrical encryption, amazing.
Keen to find out more about the two way encryption, surely a message encrypted by the private key is not secure since it can be decrypted by anyone with the public key. There must be some sort of encryption used that is determined by the person with the public key – maybe a Merkle Puzzle of sorts?
Head over to RSA Practice for some practice keygen, encryption and decryption
