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.
- p - huge Prime Numbers (This is thrown away)
- q - huge Prime Numbers (This is thrown away)
- n - n=p*q - This is the Certificate Modulus
- e - small public "encryption exponent" or Public Key
- d - specially crafted inverse of "e" called the "decryption exponent" or Private Key
- C - Ciphertext
- M - Message - In these cases, the message is encoded as a Number.
- S - Certificate Signature
Now, if you have some Message, you just need to interpret its bytes as a number "M"Message to create a Ciphertext, you'd calculate:
C ≡ Me (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."
Cd ≡ (Me)d ≡ Me*d ≡ M1 ≡ M (mod n)
Private Key "d" can "sign" a document by raising a Message "M" to the "d" Public Key Certificate Exponent:
Md ≡ S (mod n)
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.