jspωiki
RSA Cryptography

## 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"

### Encryption#

If you want to "encrypt" a 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."
For example, 11 AM + 3 hours ≡ 2 (PM) (mod 12 hours).

### Decryption#

The recipient knows Private Key "d" which allows them to invert the message to recover the original Message:
Cd ≡ (Me)d ≡ Me*d ≡ M1 ≡ M (mod n)

#### Digital Signatures#

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:
MdS (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)

### Asymmetric Key Cryptography#

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
CdM (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.