RSA加密原理

同余运算

符号约定：

• a≡b(mod m)表示a,b对模m同余
• (a, b)=c表示整数a和b的最大公约数为c
• [a, b]=c表示整数a和b的最小公倍数为c

定理1： 整数a,b对模m同余的充要条件是 a-b能被m整除（即m|a-b）。

推论： a≡b(mod m)的充要条件是a=mt+b（t为整数）。

定理2： 同余关系具有反身性、对称性与传递性，即

1）a≡a (mod m);

2）若a≡b (mod m), 则b≡a (mod m);

3）若a≡b (mod m), b≡c (mod m)，则a≡c (mod m).

定理3： 若a≡b(mod m), c≡d (mod m),则

1）a+c≡b+d (mod m);

2）a-c≡b-d (mod m);

3）ac≡bd (mod m).

推论： 若a≡b(mod m),n为自然数，则an≡bn (mod m)。

定理4： 若ca≡cb(mod m), (c,m)=d, 且a,b为整数，则a≡b(mod m/d).

推论： 若ca=cb(mod m), (c,m)=1,且a,b为整数，则a≡b(mod m).

定理5： 若a≡b (mod m),a≡b (mod n),则a≡b(mod [m,n]).

推论： 若a≡b(mod mi), i=1,2,…,n，则a≡b (mod [m1,m2,…,mn]).

同余运算总结：

欧拉定理

定义： 若对任意的自然数m，用记号ф(m)表示0,1,2,…,m-1中与m互素的数的个数，则称ф(m)为欧拉函数。

欧拉定理： 若(a,n)=1，则$a^{\varphi (n)}\equiv 1(modn)$

证明：

将1~n中与n互质的φ(n)个数按顺序排布：
$$x_1,x_2,\dots ,x_{\varphi (n)}$$
我们考虑这么一些数：
$$m_1=a\ast x_1,m_2=a\ast x_2,\dots ,m_{\phi (n)}=a\ast x_{\varphi (n)}$$

1）这些数中的任意两个都不模n同余
反证法：假设如果有$m_i\equiv m_j(modn)$（这里假定mi更大一些），就有：
$m_i-m_j=a(x_i-x_j)=qn$，即n能整除$a(x_i-x_j)$。
但是a与n互质，a与n的最大公因子是1，而$x_i-x_j<n$，因而$a(x_i-x_j)$不可能被n整除，矛盾。
也就是说这些数中的任意两个都不模n同余，φ(n)个数有φ(n)种余数。

2）这些数除n的余数都与n互质
反证法：假设某个余数与n有公因子r，不妨设$a\ast x_i=pn+qr=r(\dots \dots )$，故$a\ast x_i$与n有公因子r，不互质，显然这是不可能的。那么这些数除n的余数，都在$x_1,x_2,x_3,\dots \dots ,x_{\varphi (n)}$中，因为这是1~n中与n互质的所有数，而余数又小于n.

由1）和2）可知，数$m_1,m_2,m_3\dots \dots m_{\phi (n)}$（如果将其次序重新排列）必须相应地同余于$x_1,x_2,x_3\dots \dots x_{\phi (n)}$.
故得出：$$m_1\ast m_2\ast \cdots \ast m_{\phi (n)}\equiv x_1\ast x_2\ast \cdots \ast x_{\phi (n)}(modn)$$

即$$a^{\phi (n)}\ast (x_1\ast x_2\ast \cdots \ast x_{\phi (n)})\equiv x_1\ast x_2\ast \cdots \ast x_{\phi (n)}(modn)$$

或者为了方便：$K(a^{\phi (n)}-1)\equiv 0(modn)$，这里$K=x_1\ast x_2\ast \cdots \ast x_{\phi (n)}$。

可知$K(a^{\phi (n)}-1)$被n整除。但K中的因子$x_1,x_2,\dots ,x_n$都与n互质，所以K与n互质。那么$a^{\phi (n)}-1$必须能被n整除，即$a^{\phi (n)}-1\equiv 0(modn)$，即$a^{\phi (n)}\equiv 1(modn)$，得证。

推论（费马小定理）： 若p是素数，a与p互质，则
$$a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

推论： 若p是素数，则
$$a^p\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

定理1： 若p是素数，则
$$\varphi (p^a)=p^a-p^{a-1}$$

定理2： 若(m,n)=1,则φ(mn)=φ(m)φ(n)。

推论： 若正整数$m_1,m_2,\dots m_k$两两互素，则$\phi (m_1{m}_2\dots m_k)=\phi (m_1)\phi (m_2)\dots \phi (m_k)$.

定理3： 若m的标准分解式为
$$m=p_1^{a_1}{p}_2^{a_2}...p_k^{a_k}$$
则
$$\varphi (m)=p_1^{a_1-1}{p}_2^{a_2-1}\dots p_k^{a_k-1}(p_1-1)(p_2-1)\dots (p_k-1)$$

RSA加密算法

公钥密钥产生

1. 随意选择两个大的质数p和q，p不等于q，计算N=pq。
2. 根据欧拉函数，求得r=φ(N) = (p-1)(q-1)
3. 随机选择一个整数 e，条件是1<e<r，且e与r互质
4. 求得 e 关于模 r 的模反元素，命名为d。（所谓"模反元素"就是指有一个整数d，可以使得ed被φ(n)除的余数为1。ed ≡ 1 (mod φ(N))）
5. 将 p 和 q 的记录销毁。

(N,e)是公钥，(N,d)是私钥。

加密消息

假设Bob想给Alice送一个消息m，他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：
$$n^e\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}N)$$
计算c并不复杂。Bob算出c后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：
$$c^d\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}N)$$
得到n后，她可以将原来的信息m重新复原。

解密原理

我们需要证明
$$c^d\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}N)$$
根据加密规则得
$$c=n^e-kN$$
代入最终要证明的规则
等同于求证
$$(n^e-kN{)}^d\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}N)<=>n^{ed}\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}N)$$

由于ed ≡ 1 (mod φ(N))，所以ed=hφ(N)+1，代入求证式得
$$n^{h\varphi (N)+1}\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}N)$$

接下来分两种情况证明上式：

(1) n与N互质

根据欧拉定理有
$$n^{\varphi (N)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}N)$$
于是
$$(n^{\varphi (N)}{)}^h\ast n\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}N)$$
原式得证

(2) n与N不互质

则n=kp或n=kq。

以n=kp为例，又N=pq，且n<N，则k<q且k与q互质，n=kp与q互质。

于是根据欧拉定理有
$$(kp{)}^{q-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}q)$$
进一步得到
$$[(kp{)}^{q-1}{]}^{h(p-1)}\times kp\equiv kp(\mathrm{m}\mathrm{o}\mathrm{d}q)$$
即
$$(kp{)}^{ed}\equiv kp(\mathrm{m}\mathrm{o}\mathrm{d}q)$$
可以改写成
$$(kp{)}^{ed}=tq+kp$$
由于等式左边必然能被p整除，所以等式右边的t必然也能被p整除，假设t=sp。则

$$(kp{)}^{ed}=spq+kp$$
即
$$n^{e\cdot d}=sN+n$$
原式得证。

RSA算法的可靠性

密钥生成过程中一共产生了6个数，p,q,N,φ(N),e,d.

其中公钥用到了(N, e), 密钥用到了(N, d), 只有公钥是对外部已知的，有无可能在已知N和e的情况下推导出d？

1. ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

2. φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

3. n=pq。只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。

RSA加密算法的缺点

虽然RSA加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以，RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，RSA也有一些缺点：

• 产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；
• 分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢。

参考链接：