I’ve always thought that the RSA and Diffie–Hellman public key encryption algorithm systems are beautiful in their complex simplicity. While there are countless articles out there explaining how to implement them, I have never really found one that I think describes the math behind then in a simple way, so I thought I’d give a crack at it.
Both algorithms are derived from 3 math axioms:p^(x ) mod x = p (e.x. 12^(17 ) mod 17 = 12)
p^(x-1) mod x = 1 (e.x. 12^(17-1) mod 17 = 1 )
p^((x-1)*(y-1) ) mod (x*y) = 1 (e.x. 12^((13-1)*(17-1) ) mod (13*17) = 1 )
p^((x-1)*(y-1)+1) mod (x*y) = p (e.x. 12^((13-1)*(17-1)+1) mod (13*17) = 12)
(p^(x*y) mod m) === ((p^x mod m)^y mod m)
With these 3 axioms we have everything we need to explain how RSA works. To execute an RSA exchange, encrypted from Bob and decrypted by Alice, the following things are needed.
The variable | Variable name | Who has it | Who uses it | Description |
---|---|---|---|---|
Prime Numbers 1 and 2 | Prime1, Prime2 | Alice | Alice | Alice will use these to derive variables PubKey, PrivKey, and Modulo. In our examples we use small numbers, but in reality, very large primes will be used, generally of at least 256 bit size. |
Public key | PubKey | Alice, Bob | Bob | Alice sends this to Bob so he can encrypt data to her. Bob uses it as an exponent in a modexp. |
Private key | PrivKey | Alice | Alice | Alice uses this to decrypt what Bob sends her. Alice uses it as an exponent in a modexp. |
Modulo | Modulo | Bob, Alice | Bob, Alice | Alice sends this to Bob. They both use it as a modulo in a modexp |
Payload Data | Payload | The data bob starts with and turns into EncryptedPayload. Alice derives Payload back from EncryptedPayload |
Payload^((Prime1-1)*(Prime2-1)+1) mod (Prime1*Prime2) = Payload
PubKey*PrivKey=(Prime1-1)*(Prime2-1)+1
Payload^(PubKey*PrivKey) mod Modulo = Payload
(Payload^PubKey mod Modulo)^PrivKey mod Modulo = Payload
However, there is 1 caveat that I didn’t cover which makes the encryption that what we currently have weak. The calculation of PubKey and PrivKey from Prime1 and Prime2 needs to follow some rather specific complex rules to make the keys strong. Without this, an attacker may be able to figure out Prime1 and Prime2 from the Modulo and PubKey, and could then easily derive PrivKey from it. I generally see the PubKey as 65535, or another power of 2 minus 1.