Encryption:
\[ C = M^e\ \text{mod}\ n \]
Decryption:
\[ M = C^d\ \text{mod}\ n \]
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.
\[ \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 \]
\[ \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\).
r = 2 ^ ceiling (logBase 2 (fromIntegral m))Square \(r\), modulo \(m\). This we’ll call \(r_2\).
r2 = r * r `mod` mCompute the multiplicative inverse of \(-m\ \text{mod}\ r\), this is \(m'\)
m' = inv (negate m) rPut \(a\) into “montgomery form” by multiplying \(a * r_2\), this is \(a_m\).
am = a * r2Do 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' = am * m' `mod` rDo \(\cfrac{a_m + a_m' * m}{r}\). This temp value we’ll call \(t\).
t = am + am' * m `div` rThe result is \(t\) if \(t < m\), otherwise it’s \(t - m\).
if t < m
then t
else t - mCompute multiplications in montgomery form.
Put \(b\) into Montgomery form and then reduce it as well. This is \(b'\).
bm = b * r2
b' = reduce bmcompute \(c'\), which is a reduction as well, but this time of \(a' * b'\) instead of \(a\) or \(b\) times \(r_2\).,
c' = reduce (a' * b')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.