RSA 公钥密码系统背后的数学原理-编程阁

介绍

RSA 是一种非对称的公开密钥算法，它需要一对公钥和私钥，消息发送者使用公钥对消息进行加密，消息接收者使用私钥对消息进行解密。这个算法的特殊之处在他的加密、解密算法和公钥都是公开的，只有私钥是保密的，而试图破解的人即使拿到公钥和加密的消息，在知道加密、解密算法的情况下，依然无法对消息进行解密。下面我们看看它的加密、解密算法长什么样。

RSA 算法

p\ pp和q\ qq是两个非常大的素数，n=p×q\ n=p \times qn=p×q，a\ aa和b\ bb是正整数，满足a×b≡1(mod φ(n))\ a \times b \equiv 1 (mod\ \varphi(n))a×b≡1(modφ(n))，φ(n)\ \varphi(n)φ(n)表示小于n\ nn且与n\ nn互素的正整数个数。这里，b\ bb和n\ nn就是公钥，对外公开，a\ aa就是私钥，对外保密。假设消息明文为x\ xx，密文为y\ yy，x\ xx和y\ yy是小于n\ nn的正整数，则：
加密函数为：e(x)=xb mod n\ e(x)=x^b\ mod\ ne(x)=xbmodn
解密函数为：d(y)=ya mod n\ d(y)=y^a\ mod\ nd(y)=yamodn
这个算法要能按照预期工作，必须保证两点：

解密后的消息和原来的消息一样，也就是x=d(e(x))\ x=d(e(x))x=d(e(x))
根据公开的b\ bb和n\ nn无法破解保密的a\ aa

在介绍证明方法前，我们先来看一个简化的例子：
假设p=3，q=5，n=15\ p=3，q=5，n=15p=3，q=5，n=15，小于 15 且与 15 互素的正整数有：1、2、4、7、8、11、13、14，也就是一共有 8 个，所以φ(15)=8\ \varphi(15)=8φ(15)=8，找到a=11，b=3\ a=11，b=3a=11，b=3满足a×b=33≡1(mod 8)\ a\times b=33 \equiv 1 (mod\ 8)a×b=33≡1(mod8)，所以在这里例子里，公钥就是 15 和 3，私钥就是 11。当某个明文消息x=12\ x=12x=12，加密的过程是y=123 mod 15=1728 mod 15=3\ y=12^3\ mod\ 15=1728\ mod\ 15=3y=123mod15=1728mod15=3。接收者得到密文 3 后解密的过程是：311 mod 15=177147 mod 15=12\ 3^{11}\ mod\ 15=177147\ mod\ 15=12311mod15=177147mod15=12，可以看到解密后的 12 和原先的明文是一模一样的。

这里用的是简化的例子，实际上p\ pp和q\ qq是两个非常大的素数，比如说现在的 RSA 算法要求n\ nn是 1024 位甚至 2048 位，也就是21024\ 2^{1024}21024和22048\ 2^{2048}22048，对于那么大的数字，寻找素数p\ pp和q\ qq以及计算n\ nn并不困难，但是对给定的n\ nn做素因数分解成p\ pp和q\ qq是极其困难的，同样的，因为φ(n)\ \varphi(n)φ(n)的计算也依赖于p\ pp和q\ qq，所以计算出φ(n)\ \varphi(n)φ(n)也非常困难，而a×b≡1(mod φ(n))\ a \times b \equiv 1 (mod\ \varphi(n))a×b≡1(modφ(n))，所以要根据n\ nn和b\ bb计算出a\ aa也就几乎是不可能的。

证明方法介绍

最后我们看下x=d(e(x))\ x=d(e(x))x=d(e(x))的证明，这里介绍的是《应用近世代数》（见参考资料）一书中的证明方法，这个方法只需要用到 Euler 定理，比较容易看懂，过程如下：
∵e(x)=xb mod n∴e(x)=(xb−cn) mod n∴d(e(x))=(xb−cn)a mod n∴d(e(x))=xab mod n∵ ab≡1(mod φ(n))∴ab=tφ(n)+1∴d(e(x))=xtφ(n)+1 mod n \because e(x)=x^b\ mod\ n\\ \therefore e(x)=(x^b-cn)\ mod\ n\\ \therefore d(e(x))=(x^b-cn)^a\ mod\ n\\ \therefore d(e(x))=x^{ab}\ mod\ n\\ \because \ ab \equiv 1 (mod\ \varphi(n))\\ \therefore ab=t\varphi(n)+1\\ \therefore d(e(x))=x^{t\varphi(n)+1}\ mod\ n∵e(x)=xbmodn∴e(x)=(xb−cn)modn∴d(e(x))=(xb−cn)amodn∴d(e(x))=xabmodn∵ab≡1(modφ(n))∴ab=tφ(n)+1∴d(e(x))=xtφ(n)+1modn
也就是说只需要证明xtφ(n)+1 mod n=x\ x^{t\varphi(n)+1}\ mod\ n=xxtφ(n)+1modn=x就可以了，分两种情况讨论：
当x\ xx和n\ nn互素：
根据 Euler 定理：xφ(n)≡1 mod n\ x^{\varphi(n)} \equiv 1\ mod\ nxφ(n)≡1modn，所以xtφ(n)+1 mod n=x\ x^{t\varphi(n)+1}\ mod\ n=xxtφ(n)+1modn=x
当x\ xx和n\ nn不是互素：
则x=sp\ x=spx=sp
根据 Euler 函数，
φ(n)=(p−1)(q−1)φ(q)=q−1 \varphi(n)=(p-1)(q-1)\\ \varphi(q)=q-1φ(n)=(p−1)(q−1)φ(q)=q−1
再根据 Euler 定理，
x(q−1)=(sp)q−1≡1 mod qxtφ(n)=xt(p−1)(q−1)≡1 mod q∴xtφ(n)=rq+1∴xtφ(n)+1=xtφ(n)⋅x=rqx+x=rqsp+x=rsn+x≡x mod n∴xtφ(n)+1 mod n=x x^{(q-1)}=(sp)^{q-1} \equiv 1\ mod\ q\\ x^{t\varphi(n)}=x^{t(p-1)(q-1)} \equiv 1\ mod\ q\\ \therefore x^{t\varphi(n)}=rq+1\\ \therefore x^{t\varphi(n)+1}=x^{t\varphi(n)}\cdot x=rqx+x=rqsp+x=rsn+x \equiv x\ mod\ n\\ \therefore x^{t\varphi(n)+1}\ mod\ n=xx(q−1)=(sp)q−1≡1modqxtφ(n)=xt(p−1)(q−1)≡1modq∴xtφ(n)=rq+1∴xtφ(n)+1=xtφ(n)⋅x=rqx+x=rqsp+x=rsn+x≡xmodn∴xtφ(n)+1modn=x
证毕。可以看到在有了 Euler 定理后，配上一些技巧性的操作，就可以比较容易地证明x=d(e(x))\ x=d(e(x))x=d(e(x))，也就是保证了解密后的消息和原来的消息一样。下面我们看下 Euler 定理长什么样。

Eurler 函数和 Eurler 定理

Eurler 函数

若n\ nn是一个正整数，φ(n)\ \varphi(n)φ(n)表示小于n\ nn且与n\ nn互素的正整数个数。当n\ nn是一个素数时，显然有φ(n)=n−1\ \varphi(n)=n-1φ(n)=n−1，若n\ nn的素因数分解是n=p×q\ n=p \times qn=p×q，则φ(n)=(p−1)(q−1)\ \varphi(n)=(p-1)(q-1)φ(n)=(p−1)(q−1)，证明方法见参考资料。