WANGXUYIN

RSA算法

RSA算法的可靠性利用的是没有高效的手段对数字进行分解质因数。

数学相关

质数

回想了下，是小学知识。

范围: 大于1的自然数。

只能够被1和自身整除的数是质数。

20以内的质数:

从1开始 枚举,结合九九乘法表进行计算得到:

2,3, 5,7,11,13,17,19

分解质因数:将数字写成质数相乘的形式。任意一个大于1的正整数，都可以写成一系列质数的积。

比如 45 = 5 3 3

分解质因数方法:木有高效的方法。

小学时分解质因数方法:死记硬背20以内的质数，根据能被2，3，5，11整除的数的特点，结合滚瓜烂熟的九九乘法表，对较小的数进行分解，即根据已有数学经验与逻辑进行分解。

互质关系

两个正整数，除了1以外，没有其他公因数(公约数),这两个数就是互质关系。不是质数也可以构成互质关系，比如14和25。

互质关系能轻松得到一些结论:

1.任意两个质数，一定构成互质关系，因为均只能被1和他们本身整除，不存在其他公约数。比如11和19.
2.一个数是质数，另一个数只要不是该质数的倍数，两者即构成互质关系，因为其中1个数只能被1和本身整除，另一个数真要保证不被这个质数本身整除即不是该质数倍数则能构成互质关系。比如5和12。
3.两个数中，如果较大的是质数，则构成互质关系，即质数与比他本身小的任意数都构成互质关系，因为较大的数只包含1和本身为约数，比如97和任何比其小的数。
4.1和任意自然数都是互质关系。比如1和6.
5.P是大于1的整数，则P和p-1构成互质关系，比如，32个31.
6.p是大于1的奇数，则p和p-2构成互质关系，比如33和31.

欧拉函数

问题:

给定任意正整数n,在小于n的正整数中，有多少个数与n构成互质关系?

计算这个值的方法叫做 欧拉函数 ，以φ(n)表示。

比如在1到10之间有多少个数与10构成互质关系，我们枚举可以得到1，3，7，9与10构成互质关系即φ(10) = 4. .......10*(1-1/2)*(1-1/5)=4,验证下避免做错小学题丢人...

φ(n)的计算方式:

1.如果n=1,则φ(1) = 1。根据上面第四条结论1与任何自然数构成互质关系得出。
2.n是质数，则φ(n) = n - 1。根据上面的第三条结论得出。
3.如果n是某个质数(p)的(k)次方，即n=p^k(p是质数，k是大于等于1的整数)则 φ(n) = φ(p^k) = p^k - p^(k-1).
比如φ(27) = φ(3^3) = 3^3 - 3^(3-1) = 3^3 - 3^2 = 27 - 9 = 18 。这种情况即n与不能被P整除的数构成互质，而能被P整除且小于n的共有p^(k-1)个，即1*p,2*p,3*p ...,p^(k-1)*p,因为前提P本身为质数，所以只需要把这些数去除剩下的就是与n互质的数。
对于
φ(n) = φ(p^k) = p^k - p^(k-1) 
还可以将该式子提取公因式 p^k 写成积的形式：
φ(n) = φ(p^k) = p^k - p^(k-1) = p^k(1-1/p) 。

4.如果n可以被分解成两个互质的整数之积，即n = p1 * p2，p1与p2互质（不一定都是质数），那么φ(n) = φ(p1 * p2) = φ(p1) * φ(p2).即积的欧拉函数等于各个互质因子的欧拉函数之积。例如 φ(90) = φ(9*10) = φ（9）* φ（10） = 6 * 4 = 24. 这个要证明需要 
中国剩余定理(孙子定理)https://baike.baidu.com/item/%E5%AD%99%E5%AD%90%E5%AE%9A%E7%90%86/2841597

5.因为任何一个大于1的正整数，都可以写成一系列质数的积，即
n = p1^k1 * p2^k2 * p3^k3 ...*pr^kr
根据第四条结论推断:
φ(n) = φ(p1^k1) * φ(p2^k2) * φ(pr^kr)
在根据第三条推断
φ(n) = φ(p1^k1) * φ(p2^k2) * φ(pr^kr) = p1^k1 * p2^k2 ...* pr^kr *(1-1/p1)*(1-1/p2) ...*(1-1/pr).
同时可写为

φ(n) = n(1-1/p1)(1-1/p2)...(1-1/pr)
这就是欧拉函数的通用公式。
比如 3435 可写为(因式分解) 3435 = 5 * 3 * 229 那么比3435小与3435 构成 互质的数共有 3435 * （1-1/3） * (1-1/5) * (1-1/229) 个。（举例选数运气真背，我是谁，我在哪，我为什么要选我的手机尾号举例子，玛德，光在想229是不是质数了...）

欧拉函数的用处在于欧拉定理 ：

两个互质的正整数 a 和 n ，n的欧拉函数可以让下面的等式成立:

a^φ(n) mod n = 1

即a的φn次方 除以 n 的余数 为1.

比如 3和5互质 5的欧拉函数 φ(5) = 4， 3^4 / 5 = 81 / 5余数为 1。

证明:这道题我不会做。

根据上面推断的第2条，如果n是质数，φ(n) = n-1,可得出欧拉定理的一个特殊情况:

a与质数p互质，φ(p) = p-1,此时欧拉定理可以写作:

a^(p-1) mod p = 1 （费马小定理）

欧拉定理是RSA加密算法的核心。

模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

即满足 a*b mod n = 1 b就是a的模反元素。

欧拉定理可证明模反元素必然存在:

a^φ(n) mod n = a *a^(φ(n)-1) mod n = 1

RSA 加密方式

##### 密钥的生成

第一步 随机选择两个不相等的质数p和q,所以一定构成互质关系。

这里选97 和 229

第二步 计算p和q的乘积n。

n = pq =97 * 229 = 22213

第三步 计算n的欧拉函数 φ(n)

φ(22213) = φ(97 229) = φ(97) φ(229) =（97-1）（229-1）= 96 228 = 21888

第四步 随机选择一个整数e,e满足条件 1 < e < φ(n) ,e与φ(n)互质。

我就选e=21887吧

第五步 计算e的模反元素d

即ed mod φ(n) = 1的数

改写

ed - 1 = k φ(n)

等价于

ex+φ(n)y =1

已知 e = 21887, φ(22213) = 21888

21887x+21888y=1

我他么数选的太难了,反正就是"扩展欧几里得算法"求解就是了，当然，我要说的是PHP是最好的编程语言:

<?php
for($x=30000;$x<=50000;$x++){
  $y = (1-21887*$x)/21888;
  if(is_int($y)){
     echo $x."\n";
     echo $y."\n";
     die();
   }
}

我就这么开心的算了一组解:

x = 43775, y=-43773 即d=43775

第六步 将n和e封装成公钥，n和d封装成私钥。

所以现在:

公钥(22213,21887)

私钥(22213,43775)

RSA 公钥和私钥就生成了。

加密和解密

加密要用公钥:

这里用刚生成的公钥(22213,21887)对m进行加密，m必须是整数，且小于n(22213)，字符串分段转unicode即可。

所谓加密就是算出以下式子中的c.

m^e mod n =c 即m的e次方除以n的余数。

假设我们要加密 "A" 转数字 65。

65^21887 mod 22213 65的21887次方除以22213的余数 ，

PHP大法好:

<?php
echo bcmod(bcpow(65,21887),22213);

得到C=7860。

解密要用私钥:

当我们拿到密文内容7860,用私钥(22213,43775)解密:

下面的等式一定成立:

c^d mod n = m ，即c的d次方除以 n 余数为m即加密前的明文.现在 c即密文7860,n=22213,d=43775,解密即求m，明文:

也就是7860^43775 mod 22213 = m (m =?) ，m也就是上面的明文65,可以计算验证下,不对你砍我。

重要的事情说三遍，PHP大法好:

<?php
echo bcmod(bcpow(7860,43775),22213);//65

加密解密的过程就是这样。

证明上面的解密过程一定能还原m,即证明c^d mod n = m 一定成立(证明过程转自ruanyifeng.com)：

　cd ≡ m (mod n)

因为，根据加密规则

　　ｍe ≡ c (mod n)

于是，c可以写成下面的形式：

　　c = me - kn

将c代入要我们要证明的那个解密规则：

　　(me - kn)d ≡ m (mod n)

它等同于求证

　　med ≡ m (mod n)

由于

　　ed ≡ 1 (mod φ(n))

所以

　　ed = hφ(n)+1

将ed代入：

　　mhφ(n)+1 ≡ m (mod n)

接下来，分成两种情况证明上面这个式子。

（1）m与n互质。

根据欧拉定理，此时

　　mφ(n) ≡ 1 (mod n)

得到

　　(mφ(n))h × m ≡ m (mod n)

原式得到证明。

（2）m与n不是互质关系。

此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。

以 m = kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：

　　(kp)q-1 ≡ 1 (mod q)

进一步得到

　　[(kp)q-1]h(p-1) × kp ≡ kp (mod q)

即

　　(kp)ed ≡ kp (mod q)

将它改写成下面的等式

　　(kp)ed = tq + kp

这时t必然能被p整除，即 t=t'p

　　(kp)ed = t'pq + kp

因为 m=kp，n=pq，所以

　　med ≡ m (mod n)

原式得到证明。

RSA算法加密 的安全可靠性

密钥生成的过程中共产生6个数字:

p,q,n，φ(n),e,d，公钥是公开的用于加密，由n和e组成，其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，用于自己解密，一旦d泄漏，就等于私钥泄漏。

是否可靠就在于能否通过公开信息n,e推出d。

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

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

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

也就是说，n被分解质因数就能得到d,成功获取私钥。

对于一些比较小的数，最开始我们提到了我们分解质因数的方式实际是枚举。对于一些比较小的数还好，我们可以通过计算机来枚举破解，比如

n=1389838782556614468794064557539356473141171394217910311

e=65537

组成的公钥，我们能够算（枚举）出来:

p=1152497169371634301857542543

q=1205936829601398332841241577

推出 d=295561028312121944116802381945412767177035108281094065

这个例子实际是通过 http://factordb.com来秒杀的，这个网站存储了一些枚举值供查询。

这个公钥实际是 reflector 3 这款软件注册license所用的公钥，现在有了私钥，所以，拿去，你们要的破解版。

对于较大的数，分解质因数基本是无法完成的事情:

2009年被公布的被分解的数字:

123018668453011775513049495838496272077285356959533479219732245215172640050726365751874520299786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
=
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

232个10进制位，768个2进制位，而如今我们大多数时候都是使用2048(二进制)位RSA密钥对。所以基本可以认为是RSA是绝对安全的。