Overview#
RSA has many contributions to
Encryption and
Cryptography not the least of which is the
Public-Key Cryptography Standards (
PKCS).
Math and programing#
People sometimes wonder if math has any relevance to programming.
Certificates give a very practical example of applied math.
Our Example Certificate tells us that we should use the RSA algorithm to check the signature. RSA found a clever way to combine ideas spanning 2,000 years of math development to come up with a beautifully simple algorithm:
- Pick two huge prime numbers "p" and "q."
- Multiply them to get "n = p*q." Next, you pick a small public exponent "e" which is the "encryption exponent" and a specially crafted inverse of "e" called "d" as the "decryption exponent." You then make "n" and "e" public and keep "d" as secret as you possibly can and then throw away "p" and "q" (or keep them as secret as "d").
It is really important to remember that "e" and "d" are inverses of each other.
Now, if you have some Message, you just need to interpret its bytes as a number "M"
If you want to "encrypt" a
Message to create a
Ciphertext, you'd calculate:
C ≡ M
e (mod n)
- This means that you multiply "M" by itself "e" times.
- The "mod n" means that we only take the remainder (e.g. modulus
) when dividing by "n."
For example, 11 AM + 3 hours ≡ 2 (PM) (mod 12 hours).
The recipient knows
Private Key "d" which allows them to invert the message to recover the original
Message:
C
d ≡ (Me)
d ≡ M
e*d ≡ M
1 ≡ M (mod n)
Just as interesting is that the person with
Private Key "d" can "sign" a document by raising a
Message "M" to the "d"
Public Key Certificate Exponent:
Md ≡
S (mod
n)
This works because "signer" makes Public "S", "M", "e", and "n." Anyone can verify the signature S with a simple calculation:
Se ≡ (Md)e ≡ Me*d ≡ Me*d ≡ M1 ≡ M (mod n)
Public key
Cryptography algorithms like
RSA are often called
Asymmetric Key Cryptography because the encryption key, in our case, "
e" is not equal to (e.g. "symmetric" with) "
d".
Reducing everything "mod n" makes it impossible to use the easy techniques that we were used to such as normal logarithms.
The magic of RSA works because you can calculate/Encrypt:
C ≡ Me (mod n)
very quickly, but it is really hard to calculate/decrypt
Cd ≡ M (mod n)
without knowing "d"
As we saw earlier, "d", is derived from factoring "n" back to its "p" and "q", which is a tough problem.
There might be more information for this subject on one of the following: