- Rivest–Shamir–Adleman / defined in 1977
- Asymmetric (involves a key-pair, one private, one public)
- Used in SSL to authenticate and to exchange symmetric keys

Encryption:

\[ C = M^e\ \text{mod}\ n \]

Decryption:

\[ M = C^d\ \text{mod}\ n \]

- \(M\) is the message
- \(C\) is the cyphertext
- \(e\) is a public exponent
- \(d\) is a private exponent
- \(n\), the modulus, is the product of two large primes \(p\) and \(q\).

Encryption is like a lock, easy with the key, very hard without it.

The bolt in this case is that **factoring large numbers is hard**.

- Choose two large primes \(p\) and \(q\).
- Compute their product, this is \(n\).
- Calculate Euler’s totient function of \(n\) (denoted \(\phi(n)\)).
- Choose a public exponent \(e\) such that \(1 \lt e \lt \phi(n)\), and that \(e\) is coprime with \(\phi(n)\).
- Compute the private exponent \(d\) such that \(d \times e =\ 1\ \text{mod}\ \phi(n)\) (\(d\) is \(e\)’s multiplicative inverse \(\text{mod}\ \phi(n)\)).

- Choose two large primes \(p\) and \(q\).
- Compute their product, this is \(n\).
- Calculate Euler’s totient function of \(n\) (denoted \(\phi(n)\)).
- Choose a public exponent \(e\) such that \(1 \lt e \lt \phi(n)\), and that \(e\) is coprime with \(\phi(n)\).
- Compute the private exponent \(d\) such that \(d * e =\ 1\ \text{mod}\ \phi(n)\) (\(d\) is \(e\)’s multiplicative inverse \(\text{mod}\ \phi(n)\)).

\[ \begin{align} p &= 7 \\ q &= 13 \\ n &= 91 \\ \phi(n) &= (p - 1)(q - 1) \\ \end{align} \]

\[ \begin{align} \phi(n) &= 72 \\ e &= 17 \\ e \times d &= 1\ \text{mod}\ 72 \\ d &= 17 \end{align} \]

To encrypt a message \(M\), represent it as a number smaller than \(n\) and compute \(C = M^e\ \text{mod}\ n\).

To encrypt a message \(M\), represent it as a number smaller than \(n\) and compute \(C = M^e\ \text{mod}\ n\).

Sending the “message” `213`

, a six-bit number represented as 3 2-bit
couplets. We can represent this in base 10 as \(39\).

\[ \begin{align} C &= 39^{17}\ \text{mod}\ 91 \\ C &= 65 \end{align} \]

Simply undo encryption with \(d\)!

\[ M = C^d\ \text{mod}\ n \]

Simply undo encryption with \(d\)!

\[ M = C^d\ \text{mod}\ n \]

\[ 65^{17}\ \text{mod}\ 91=39 \]

Which, we can de-numerical-ize as 213, left to right, via its
couplets, `10 01 11`

.

Cool, we did it. We’re cryptographers now.

The Chinese Remainder Theorem states that, given a set of congruences such that all \(m\)s are coprime:

\[ x \equiv a_1\ \text{mod}\ m_1 \\ x \equiv a_2\ \text{mod}\ m_2 \\ \vdots \\ x \equiv a_n\ \text{mod}\ m_n \\ \]

we can solve for \(x\) with the congruence:

\[ x \equiv (\sum_{i=1}^n a_i \cdot M_i \cdot M_{i}^{-1})\ \text{mod}\ N \]

- \(M_i\) is \(\cfrac{m_1m_2 \dots m_n}{m_i}\)
- \(M_{i}^{-1}\) is \(M_i\)’s multiplicative inverse modulo \(m_i\)
- \(N\) is the product of all \(m\)s:

\[ \prod^n_{i=1} m_i \]

The CRT lets us break \(C^d\ \text{mod}\ n\) into two congruences, each with prime moduli.

\[ M = C^d\ \text{mod}\ p \\ M = C^d\ \text{mod}\ q \]

Once we do this, we get a smaller exponent through Euler’s Theorem, which tells us that:

\[ a^{x\ \text{mod}\ \phi(p)} \equiv a^x\ (\text{mod}\ p) \]

When \(x\) and \(p\) are coprime.

Which gives us

\[ M \equiv C^{d\ \text{mod}\ \phi(p)}\ (\text{mod}\ p) \\ M \equiv C^{d\ \text{mod}\ \phi(q)}\ (\text{mod}\ q) \]

Which we can then use the CRT to recombine.

When

\[ \begin{align} p &= 13 \\ q &= 17 \\ M &= 39 \\ e &= 19 \\ \end{align} \]

\[ C = 39^{19}\ (\text{mod}\ 221) \]

Which gives us \(91\).

When

\[ \begin{align} p &= 13 \\ q &= 17 \\ M &= 39 \\ e &= 19 \\ \end{align} \]

We have the two congruences through Euler’s Theorem and the CRT:

\[ C \equiv 39^7\ \text{mod}\ 13 \\ C \equiv 39^3\ \text{mod}\ 17 \]

Which we recombine:

\[ C \equiv (39^7 \cdot 17 \cdot 10) + (39^3 \cdot 13 \cdot 4)\ (\text{mod}\ 221) \]

Also giving us \(91\).

We did it! We’re optimizing cryptographers now.

In the optimized example, we’re multiplying 10 (7+3) 39’s, while in
the simple example, we’re **doing it 19 times**.

In reality, \(e\), \(p\), and \(q\) are all **very large numbers**.

A faster way to do multiplication which prefers base 2 to base 10, and shines when used iteratively.

Numbers are transported to “Montgomery Form” and back again for the final result.

Choose a power of two that’s greater than \(m\), this is \(r\).

`= 2 ^ ceiling (logBase 2 (fromIntegral m)) r`

Square \(r\), modulo \(m\). This we’ll call \(r_2\).

`= r * r `mod` m r2`

Compute the multiplicative inverse of \(-m\ \text{mod}\ r\), this is \(m'\)

`= inv (negate m) r m'`

Put \(a\) into “montgomery form” by multiplying \(a * r_2\), this is \(a_m\).

`= a * r2 am`

Do a montgomery reduction of \(a\), this is \(a'\). This routine we’ll call \(\text{reduce}\).

Multiply \(a_m\) by \(m'\ \text{mod}\ r\), I’ll call this \(a_m'\)

`= am * m' `mod` r am'`

Do \(\cfrac{a_m + a_m' * m}{r}\). This temp value we’ll call \(t\).

`= am + am' * m `div` r t`

The result is \(t\) if \(t < m\), otherwise it’s \(t - m\).

`if t < m then t else t - m`

**Compute multiplications in montgomery form.**

Put \(b\) into Montgomery form and then reduce it as well. This is \(b'\).

`= b * r2 bm = reduce bm b'`

compute \(c'\), which is a reduction as well, but this time of \(a' * b'\) instead of \(a\) or \(b\) times \(r_2\).,

`= reduce (a' * b') c'`

Finally, the final result is one last reduction of \(c'\).

`reduce c'`

\(r\), \(r_2\), and \(m'\) can all be precomputed.

Instead of \(\text{mod}\ n\), the product result is divided by \(r\), a power of 2.

**This is a right shift**, which is much faster than quotient estimation.Particularly useful in exponentiation because intermediate results can be left in Montgomery Form.