RSA 密码体制简记

RSA 密码体制定义

设 $n=p q$ ,其中 $p, q$ 为素数。设 $P=C=\mathbb{Z}_{n}$ ,且定义 $K={(n, p, q, a, b): a b \equiv 1 \bmod \phi(n)}$ 。对于 $k=(n, p, q, a, b), x, y \in \mathbb{Z}_{n}$ ,定义加密和解密分别为:
$$
e_{k}(x)=x^{b} \bmod n,\quad d_{k}(y)=y^{a} \bmod n
$$
值 $(n, b)$ 组成了公钥,$(p, q, a)$ 组成了私钥。

安全性

RSA 密码体制的安全性基于相信加密函数 $e_{k}(x) \equiv x^{b} \bmod n$ 是一个(陷门)单向函数 [1] 。允许解密的陷门是分解 $n=p q$ 。

若知道这个分解,则可计算 $\phi(n)=(p-1)(q-1)$ ,由于 $a b \equiv 1 \bmod \phi(n)$ ,即 $a \equiv b^{-1} \bmod \phi(n) $ ,进而可以利用扩展 Euclidean 算法 [2] 来计算解密指数 $a$ 。

[1] 单向函数:一个函数容易计算但难于求逆。陷门单向函数:一个单向函数在具有特定的陷门知识后容易求逆。
[2] 扩展 Euclidean 算法:欧几里得算法的扩展,可以用来求模的逆元。 百度词条

加解密示例

假定 $p=101, q=113$ ,则 $n=11413, \phi(n)=100 \times 112=11200$ 。若 Bob 选取 $b=3533$ ,则可计算 $a=b^{-1} \equiv 6597 \bmod 11200$ 。于是 Bob 发布公钥 $(n, b)$ ,保留私钥 $(p, q, a)$ 。

若 Alice 想加密明文 $x=9726$ 并发送给 Bob 密文 $y$ ,她将计算 $y=9726^{3533} \bmod 11413 \equiv 5761$ 。

Bob 收到密文 $y$ 后利用私钥中的解密指数来计算 $x=5761^{a}=5761^{6597} \bmod 11413 \equiv 9726$ 。