RSA

Alice 买了一个带钥匙的锁，把钥匙自己留在，锁发给 Bob。Bob 把信息放在锁里锁住，然后发给 Alice，Alice 用钥匙打开锁，取出里面的信息。这样没有任何的钥匙交换（key exchange）。也就是说她可以把锁公开出来，任何人都可以用这个锁来发信息给她。而她只要保留这把锁的钥匙就可以。

再用颜色来举例子。

Alice 随机选择一个颜色，例如红色（red），并且有办法找到她的互补色青色（cyan），她把青色作为公钥（public key）公布出去，Bob 把他想发给 Alice 的颜色，例如黄色（yellow），与青色混合，发给 Alice。

Alice 用红色与收到的颜色混合，因为红色加互补色青色等于白色，这样她就能看到 Bob 发给她的颜色，黄色。

而监听者 Eve 只能看到青色和 Bob 发出的黄青混合色，但是他不知道红色的存在，所以他无法知道 Bob 真正发出的是什么颜色。

如果我们想把上面的描述用数学方案表达出来，可以这样。

数学方案

把一段信息转换成整数 \(m\)，取一个公开的\(e\)，选一个随机的\(n\)，得到 \(c = m^e \bmod n\)，把 \(c\) 作为加密信息发出去。得到 \(c\) 的过程计算量很小。但是如果只知道 \(c，e，n\)，去计算 \(m\) 的话，计算量会很大。

但是收到 \(c\) 的人要想办法把 \(c\) 还原成 \(m\)呢？

她需要有一个 \(d\)，使得 \(c^d \bmod n = m\)

整个过程相当于 \(m^{e^d} \bmod n = m\) 即:

\[m^{ed} \bmod n = m\]

这里 \(e\) 是用来加密（encryption），而 \(d\) 就是用来解密（decryption）的。因此，我们需要一种方法来生成 \(e\) 和 \(d\)，使得别人很难知道 \(d\)。

欧几里得发现每一个数都是由质数相乘得到的，并且这些质数是唯一的。

Alice 找到一个大质数 \(p1\)，一个大质数 \(p2\)，两者相乘得到一个超大和数 \(n\)。

\[\phi(ab) = \phi(a) \phi(b)\]

如果 \(n = p1\ p2\)，那么依照欧拉函数（Euler’s totient function）

\[\phi(n) = (p1-1)(p2-1)\]

欧拉定理（Euler’s Theorem）告诉我们：

\[m^{\phi(n)} \equiv 1 \bmod n\]

例如 \(5^{\phi(8)} \equiv 1 \bmod 8\)

我们可以推出：

\[m^{\phi(n)} \equiv 1 \bmod n \Rightarrow m^{k\ \phi(n)} \equiv 1 \bmod n\] \[m^{k\ \phi(n)} \equiv 1 \bmod n \Rightarrow m \cdot m^{k\ \phi(n)} \equiv m \cdot 1 \bmod n \Rightarrow m^{k\ \phi(n)+1} \equiv m \bmod n\]

\(m^{k\ \phi(n)+1} \equiv m \bmod n\) 正是我们想要找的：

\[m^{ed} \equiv m \bmod n\]

即：

\[ed = k \cdot \phi(n)+1\]

只要知道 \(e\)，就能计算出 \(d\)。而 \(d\) 应该是 Alice 的私钥（private key）。

举个例子

Bob 把他的想要发送给 Alice 的信息变成整数 89。

Alice 随机选了两个质数，\(p = 53, q = 59\)，使得：

\[n = p \cdot q = 3127\] \[\phi(n) = (p-1)(q-1) = 52 \cdot 58 = 3016\]

现在我们需要有一个 \(e\)，一个 \(d\)，\(e\) 用来加密，\(d\) 用来解密。

\(e\) 和 \(d\) 需要满足什么条件呢？我们需要：

\[ed \equiv 1 \bmod {(p-1)(q-1)}\]

即

\[ed \equiv 1 \bmod {\phi(n)}\]

那为什么需要满足上述条件呢？

因为在 decrypt 的时候，我们需要 \(d\) 使得 \(m = c^d \bmod n\)

我们要用 \(e\) 把 \(m\) 加密成 \(c\)

因为 \(c = m^e \bmod n\)

所以 \(c^d \bmod n = (m^e \bmod n)^d \bmod n\)

又因为 \((m^e \bmod n)^d \bmod n = m^{ed} \bmod n\)

当 \(m < n\) 时，

\[m^{ed} \bmod n = m^1 \bmod n = m\]

那什么时候 \(m^{ed} \bmod n = m \bmod n\) 呢？

当且仅当 \(ed \equiv 1 \bmod {(p-1)(q-1)}\) 时 （即 \(ed \bmod {(p-1)(q-1)} = 1\)）。

如果 \(ed \equiv 1 \bmod {(p-1)(q-1)}\)，可以推出

\[ed \equiv 1 \bmod {(p-1)}\] \[ed \equiv 1 \bmod {(q-1)}\]

即 \(ed \bmod {(p-1)} = \ ed \bmod {(q-1)} = 1\)

又因为 \(m^k \equiv m^{k \bmod {(p-1)}} \bmod p\)，用 \(ed\) 替换 \(k\)，得到：

\[m^{ed} \equiv m^{ed \bmod {(p-1)}} \bmod p \equiv m \bmod p\] \[m^{ed} \equiv m^{ed \bmod {(q-1)}} \bmod q \equiv m \bmod q\]

依照中国剩余定理（Chinese Remainder Theorem）：

如果 \(n_1 = m^{ed}\), \(n_2 = m\)：

\[m^{ed} \equiv m \bmod p\] \[m^{ed} \equiv m \bmod q\]

并且 \(p\), \(q\) 都为质数，即可得到：

\[m^{ed} \equiv m \bmod n\]

因为 \(ed \equiv 1 \bmod {(p-1)(q-1)}\)，也就是说 \(d\) 是 \(e \bmod {(p-1)(q-1)}\) 的模倒数（Multiplicative Inverse）。

当 \(e\) 与 \((p-1)(q-1)\) 为互质时，\(gcd(e, (p-1)(q-1)) = 1\), 扩展欧几里得算法（ExtendedEuclid） 可以给我们 \(x\), \(y\) 使得 \(ex+(p-1)(q-1)y = 1\)

又因为 \((p-1)(q-1)\) 显然可以整除 \((p-1)(q-1)y\)，所以 \(ex \equiv 1 \bmod {(p-1)(q-1)}\)。而 \(x\) 正是我们要求的 \(d\)。

还有几个问题：

• 为什么扩展欧几里得算法可以帮我们得到 \(x\)?
• 如何选择 \(e\) 呢？

这些问题我们下次再讲。