!!! 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|Wikipedia:Prime_number|target='_blank'] (This is thrown away)
* q - huge [Prime Numbers|Wikipedia:Prime_number|target='_blank'] (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" 

!! [Encryption]
If you want to "encrypt" a [Message] to create a [Ciphertext], you'd calculate:
\\
C ≡ M%%sup 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|Wikipedia:modulus|target='_blank']) 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]:
\\
C%%sup d%% ≡ (Me)%%sup d%% ≡ M%%sup e*d %% ≡ M%%sup 1%% ≡ M (mod n)
\\
\\

!! [Digital Signatures]
%%warning
There is a common misconception that signing a [message] is the same as [Encryption] of the [message] with the private key. [Encryption]/[Decryption] and [Digital Signatures]/[Verification] are two different [algorithms]. 
%%

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]:
\\
[M|Message]%%sup d%% ≡ [S|Certificate Signature] (mod [n|Certificate Modulus])
\\
\\

This works because "signer" makes __Public__ "[S|Certificate Signature]", "[M|Message]", "[e|Public Key]", and "[n|Certificate Modulus]." Anyone can verify the signature [S|Certificate Signature] with a simple calculation:
\\
S%%sup e%% ≡ (M%%sup d%%)%%sup e%% ≡ M%%sup e*d%% ≡ M%%sup e*d%% ≡ M%%sup 1%% ≡ 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|Public Key]" is not equal to (e.g. "symmetric" with) "[d|Private Key]".

Reducing everything "mod [n|Certificate Modulus]" 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|Encryption]:
\\
C ≡ M%%sup e%% (mod n)
\\
\\
very quickly, but it is really hard to calculate/[decrypt|Decryption] 
\\
C%%sup d%% ≡ [M|Message] (mod [n|Certificate Modulus])
\\
without knowing "[d|Public Key]"

As we saw earlier, "[d|Public Key]", is derived from factoring "[n|Certificate Modulus]" back to its "p" and "q", which is a tough problem.!! [Verifying Certificate Signatures]
!! More Information
There might be more information for this subject on one of the following:
[{ReferringPagesPlugin before='*' after='\n' }]