(See https://en.wikipedia.org/wiki/RSA_(cryptosystem) for a more detailed version of this article) # What does it let you do? In this encryption scheme, there are two people, one holding both keys, who I will call the "KeyMaster", and someone else who I will call the "MemberOfPublic". ## Send secret messages without having to pre-share a key - The KeyMaster creates a pair of keys, one called the Public key and another called the Private key. - The KeyMaster then posts the public key publicly for all to use and keeps the private key secret. - Any MemberOfPublic can use the public key to encrypt a message. The encrypted message can be posted publicly, but only the KeyMaster, who has the secret private key will be able to decrypt the original message. ## Sign messages to prove you sent them - Using the same keys as before, the KeyMaster can post a message and a signed version of the message in such a way that any MemberOfPublic can verify the KeyMaster really did sign it. - This is useful for things like posing a message that says "Alice owes Bob $1". If we can be sure that Alice is really the one who posted this message, this can be a credible "I Owe You". We need to be sure that its impossible for Bob to post this message, and the digital signing lets us do that! # How it works Mathematically ## Primes $p,q$; $N=pq$ and $\varphi(N)=(p-1)(q-1)$ . - The KeyMaster finds two large primes $p$ and $q$ . - *Example:* $p=7$, $q=13$ - The KeyMaster calculates $N=pq$. - *Example:* $N = p \times q = 7 \times 13 = 91$ - The security of the algorithm is based on the hypothesis that given $p$ and $q$ it is easy to calculate $N=pq$, but that given $N$ it is difficult to factor and get $p$ and $q$ individually. - The KeyMaster calculates $\varphi(N)=(p-1)(q-1)$ - *Example:* $\varphi(N)=(p-1)(q-1)=(7-1)(13-1)=72$ - $\varphi$ is the Euler Totient Function with counts the number of relatively prime numbers to a given integer. "Relatively prime" also called "co-prime" just means they don't have any common factors (for example 3 and 5 are coprime, but 4 and 6 are not coprime because they have 2 as a common factor.) As an equation: $\varphi(i)=\text{number of numbers less than i which are also co-prime with i.}$ - *Why is $\varphi(N)=(p-1)(q-1)$?* Since $N=pq$ is a product of two primes, all the numbers except multiples of $p$ and $q$ are co-prime. e.g. for $N=91$ everything except for multiples of $7$ and $13$ are co-prime (i.e. anything except $7,14,21,28,35,42,49,56,63,70,77,84,91$ or $13,26,39,52,65,78,91$. which are the multiples of $7$ and $13$ respectively) There are $q$ multiples of $p$ which are $\leq N$, and $p$ multiples of $q$ which are $\leq N$, and $N$ is double counted. This shows $\varphi(N) = pq - p - q + 1 = (p-1)(q-1)$ ## Public Key: Encryption with the encryption exponent $e$ - The KeyMaster chooses a number $e$ which is co-prime with $\varphi(N)$ . - $e$ is called the *encryption exponent*. - Example: When, $\varphi(N) = 72$ we can choose $e=5$ - The public key is the pair of numbers $e,N$ . The KeyMaster publishes this key publically. - *Example:* The public key is $e=5,N=91$ - Note: All the other details, like what is $p,q,\varphi(N)$ is, are kept secret by the KeyMaster - To encrypt a *message* $M$ (which is an integer between $1$ and $N$) any MemberOfPublic can use the public key to calculate the *code word* $C$ (also an integer between $1$ and $N$) by the formula: $ C = M^e \text{ mod }N $ - *Example:* To send the message $M=9$ , we would compute $C = 9^5 \text{ mod } 91$ which turns out to be $C = 81$ . - The message $C$ can then be sent from the MemberOfPublic to the KeyMaster by posting it publicly. e.g. by posting on a bulletin board or by posting on the internet. - Only the KeyMaster (who knows the secret information $p,q$ and $\varphi(N)$) will be able to take the codeword $C$ and recover the original message $M$ . Anyone else won't be able to do this (unless they can factor $N$ into $pq$ , which is believed to be a hard problem!) ## Decrypting: How to recover the message $M$ from $C$. - The KeyMaster uses their knowledge of $p,q$ to compute the inverse of the encryption exponent $e$ working mod $\varphi(N)$ . i.e. they find an value $d$ , called the *decryption exponent* so that $ed = 1 \text{ mod }\varphi(N)$ - The pair $d,N$ is called the "Private Key" (sometimes people say just $d$ on its own is the private key because $N$ is already included in the public key)​ . This is always possible as long as $e$ is relatively prime with $\varphi(N)$. By Euler's algorithm, we can find $\alpha,\beta$ so that $\alpha e + \beta \varphi(N) = 1$, and then we can see that $d = \alpha \text { mod }\varphi(N)$ works! - *Example*: By using Euler's algorithm we can see that $-43\times 5 +3 \times 72 = 1$ , so then $d=-43 \text{ mod }72 = 29$ is our decryption exponent. - Note that if you only knew $N$ but not $p$ and $q$ , you would not be able to do this, because you don't know $\varphi(N)=N-p-q+1$ and can't do this! - The decryption exponent $d$ is sometimes called the *private key*. - To decode a coded message $C$, the KeyMaster computes: $M = C^d \text{ mod N}$ - *Example:* When $C=81$ and $d=29$ we compute $81^29 \text{ mod }91 = 9$, which recovers the original message. ## Another use: Signing Messages Another use of the encryption scheme is that the KeyMaster can "sign" a message using the private key $d,N$ in such a way that any MemberOfPublic can use the public key $e,N$ to verify the message. Since only the KeyMaster has the the private key $d$ , this means that nobody else could have faked this message (unless they are able to factor $N$ ) The way this is done is completly symmetric to the secret messages approach. - The KeyMaster has a message $M$. They compute the *signature* of $M$ which is: $C = M^{d} \text{ mod }N$ - The KeyMaster then posts the message $M$ and signature $C$ publicly. (e.g. on a bulletin board or on the internet). - Any MemberOfPublic can verify that it really way the KeyMaster who posted $M$ (and not an imposter!) but verifying that $C^{e} = M \text{ mod }N$ ## Why does this work? The mathematical thing to be proven is that with the setup above, that $C = M^e \text{ mod }N$ if and only if $M = C^d \text{ mod }N$ . To see this it suffices to show that $ M = \left(M^e\right)^d \text{ mod }N = M^{ed} \text{ mod } N$ we will "divide" both sides by $M$ and we will actually prove that $M^{ {ed} -1 } = 1 \text{ mod }N$ To see this, we will prove that $M^{ {ed} -1 } = 1 \text{ mod }p$ and $M^{ {ed} -1 } = 1 \text{ mod }q$. (Because then, by a [[Chinese remainder theorem (simple case)]] it follows since $N=pq$ that it must be $1 \text{ mod }pq$ too.) These two statements are complelety symmetric; any proof that $M^{ed-1}=1\text{ mod }p$ will also work to prove that $M^{ed-1} = 1\text{ mod }q$. So lets just focus on proving $M^{ed-1} = 1 \text{ mod }p$. To prove this, we will use [[Fermat's Little Theorem]] (aka the FlT): $a^{p} = a \text{ mod }p$ holds for any $a$ and prime $p$ . To see how the FlT is used, note that because $ed - 1 = 0\text{ mod }\varphi(N)$ we can find a $c$ so that$ed - 1= c(p-1)(q-1)=p\left( c(q-1) \right) - c(q-1)$ and then we have that $\begin{align} M^{ed-1} &= \left( M^p \right)^{c(q-1)} M^{-c(q-1)}\\ \text{ (by FlT) }&= M^{c(q-1)}M^{-c(q-1)}\\&= 1 \text{ mod }N\end{align}$ where we replaced $M^p$ by $M$ in the second line due Fermat's Little Theorem.