学一点有趣的数论知识
在探究RSA算法的原理之前，我们先来学习一点有趣的数论知识（数学分支之一，主要研究整数的性质）。你会发现一些简单的数学知识竟然背后有如此神奇的魔力。
质数
说起质数，想必大家不陌生了，一个大于1的整数除了其本身和1之外，不存在因数则被称为质数或者是素数。比如2、3、5、7等。在小学课堂里，我们可能只是记住了这个概念，但是这里我谈下自己的一些思考帮助大家理解，质数就好比是构成数字的基本元素，想想看，氢分子仅由两个氢原子（组成一个氢分子）构成，那么一个非质数的6=3*2 即表示为6是由两个“3”元素或3个“2”元素构成。其中“3”或者“2”是不可以继续拆分的元素（3，2都是质数）。所以对一个非质数进行因式分解过程就好比对一个物体进行深入解剖，拆分至不可拆分的元素为止。这样看来，数学家们提出这些数学概念，其实也是一种对数字世界的认识和思考的概括，和我们日常生活理解周边事物方式也是相似的。
互质关系
知道了质数，我们再看看互质关系，那么什么是互质呢？就是说两个数没有相同的因数称为互质关系。我们对6进行因数分解，拆分到质数的乘积即6＝3* 2而 35=5*7,这两者没有相同的因数则称6与35互质，就好像氢气分子只是由氢原子构成，而氧气分子只是由氧原子构成，这二者这间没有相同的原子就是一种互质的体现。
所以互质只是一个数和数之间有没有相同的因数关系的体现(公约数也称公因数)，和两者是不是质数是没有关系的。当然质数之间必然是互质关系，因为它们都是构成数字的不同元素。数学上来表示a,b互质一般用gcd(a,b)=1来表示。即a和b的最大公约数是1.
欧拉的思考之欧拉定理与欧拉函数
质数和互质的关系是不是很容易理解？但是大数学家欧拉先生可绝不仅仅停步于此，数学家嘛总爱问一下抽象概括性的问题，希望找寻规律比如
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到10之中，有多少个数与10构成互质关系？）
如果能找到规律，无论数字如何千变万化10位数还是100000位数，我们都能根据准则轻易计算数互质关系的数量。你发现了没有，数字也是一片世界，真是一花一世界一叶一如来啊！好了回归正传，对于这个问题欧拉先生给出了他的答案。他是这样作答的：
首先呢上述问题可以简化为一个函数来描述即：\Phi(n)
这也是数学家老毛病在他们看来任何问题就是对函数的求解。既然这个函数由欧拉提出来的，那么我们就称他为欧拉函数.还好这个函数简单只有一个变量，即给定的正整数n。接下来就要分析这个n
欧拉函数
n=1的情况
n＝1的时候这个问题极其简单：
\Phi(n)＝1
因为1与任何数包含他自身都构成互质关系。1本身也是质数且不作为其他数的因数，因为任何数乘以1都是其本身
n是质数的情况
大家想想看n是质数，其自身就不存在因数了，而那些与他非互质关系(存在公约数)的数进行因式分解后一定都会有一个因数与n相等。比如n＝3为一个质数，那么6＝3*2与3是非互质关系，因为存在公约数3。所以我们发现与n非互质关系的数都是n的倍数即(kn)，因为kn>=n所以与n互质的数都小于n即
\Phi(n)＝n-1
n不是质数的情况
还记得我们前面提到的质数吗，他可是构成数字的元素呀，所以如果n不是质数，那么他一定可以被因式分解拆分成多个质数的乘积。比如24=6*4=3*8=2*2*2*3 比如6=2*3，这些质数因数相互乘积也可以形成如下情况：
n演变为两个互质的数的乘积
我们把相同质数因数进行相乘，很容易将一个非质数分解为两个互质关系的数的乘积，比如24=6*4=2*2*2*3＝3*8
从简单的情况来考虑，即n被拆分为两个互质关系的数的乘积：
即
n=p*q
p与q互质，那么根据剩余定理:
\Phi \left( pq\right) =\Phi(p)*\Phi(q)
至于如何证明呢？说实话我也不清楚。在我理解看来，与24互质的数都有这样一个特点：他进行因式分解后其因数不包含有3与2（因为8=2*2*2）。所以与3互质的数定义为集合A，且个数为
\Phi \left( 3\right)
与8互质的数定义为集合B，且个数为
\Phi \left( 8\right)
这AB两组的数字可以在组与组间两两进行组合乘积，构成与24互质的数。所以两组数字个数相乘就可以知道乘积的组合个数，也就知道与24互质的个数了。这样的证明并不严谨但姑且可以先记住。
另外还需要记住欧拉函数是一个积性函数,也就是n如果为多个互质的数构成即(n=a*b*c*d.... )，那么
\Phi \left( n\right)=\Phi \left( a\right) *\Phi \left( b\right)....
n演变为质数的多次方
也就是n为某一个质数的倍数，比如27=3*3*3=3^3 27就是3的倍数。那么小于27且存在非互质关系的数一定都是3的倍数也就是：1*3、2*3,3*3...9*3 共计9个， 所以3^3 - 9 ＝3^3 - 3^2 .所以归纳一下也就是说如果p是质数，求与p^n 互质的数的个数，只要将如下的数
(1*p)、(2*p)、(3*p)、....(p^n-1 *p) 进行剔除，剩余的都将与p^n （切记p是质数）互质所以我们得出：
\Phi \left( p^{k}\right)=p^{k}-p^{k-1}＝p^{k}(1-\dfrac {1}{p} )
当k＝1的时候即
\Phi \left( p\right)=p-1
又回到了之前n为质数的情况下的表达式。这里我们也看到数学追求简洁和普适性的思想，再繁杂的规律都可以变成一个简洁抽象的表达式。
n演变为多个不同质数的积
比如24=6*4=3*8=2*2*2*3，因为质数之间就是互质关系而且质数的多次方也是互质关系所以
我们把24演变一下：24=2^3 * 3即把相同的质数进行合并为质数的多次方。这样2^3 与3是互质关系(质数的多次方之间也都是互质关系)，于是当我们求与24互质的数的个数时候，就可以套用之前公式即：
\Phi \left(24\right)=\Phi \left( 2^{3}*3\right)=\Phi \left(2^3\right)*\Phi \left(3\right)=(2^{3}-2^{3-1})(3-1) =8
再进一步归纳因为p1、 p2...pm等都是质数且
n = p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}
则由于欧拉函数是积性函数，那么：
\Phi \left(n\right)=\Phi \left( p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}\right) =\Phi \left( p_{1}^{k_{1}}\right)* \Phi \left( p_{2}^{k_{2}}\right)*...\Phi \left( p_{m}^{k_{m}}\right)
由上一小节n为质数的多次方的结论
\Phi \left( p^{k}\right)=p^{k}-p^{k-1}＝p^{k}(1-\dfrac {1}{p} )
可以得出：
\Phi \left( p_{1}^{k_{1}}\right)* \Phi \left( p_{2}^{k_{2}}\right)*...\Phi \left( p_{m}^{k_{m}}\right)=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{m}^{k_{m}}*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}} )
则
\Phi \left(n\right)=n*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}})
此时我们仍然计算24互质个数则
\Phi \left(24\right)=\Phi \left( 2^{3}*3\right)=\Phi \left(2^3\right)*\Phi \left(3\right)=24*(1-\dfrac {1}{2})(1-\dfrac {1}{3})＝8
欧拉函数的总结
上面说的那么多其实归结起来就是这样一个道理：当我们去求小于某个数范围内与其互质的数的个数时候，无非就是把n分为质数还是非质数。
-
对于质数：
\Phi \left(n\right)=n-1 -
对于非质数：
我们都可以将非质数进行因式分解形成多个质数的乘积，我们把相同的因数进行归并，即将2*2*3*5=2^2 *3*5），使得n的乘积因子都为互质关系，这样就可以套用如下公式
\Phi \left(n\right)=n*(1-\dfrac {1}{p_{1}} )*(1-\dfrac {1}{p_{2}})...(1-\dfrac {1}{p_{m}})
欧拉定理
知道了欧拉函数，接下来我们再理解一个同余概念，简单来说也就是25除以3的余数为1，而1除以2的余数为1，则我们称25与1对于模3同余数，用人话来说就是25和1 除以2得到的余数都一样。求余数的过程在数学里的黑话叫取模。所以才有上面那么拗口的说法。但是不要紧，数学喜欢简单不啰嗦，于是搞出了如下的表达式来表达上述说法：
25\equiv 1\left( mod\ 3\right)
也就是说
25 \% 3 = 1\%3=1
注意到了吗？上述表达式也可以这样表述，即25除以3得到的余数为1.围绕着同余这个概念，欧拉大师结合他的欧拉函数活脱脱就搞出了个欧拉定理，我们来看看他有什么发现？
如果两个正整数a与n互质，则通过n的欧拉函数可以得出
a^{\Phi \left(n\right)}\equiv 1\left( mod\ n\right)
如果n为质数则n的φ(n)（小于p的整数范围内与p互质关系的个数）等于n-1，则欧拉定理可以写成：
a^{n-1}\equiv 1\left( mod\ n\right)
而这样一个同余表达式又叫做费尔马小定理
另外根据取模运算的规则：
a^{b}\%p = ((a \% p)^{b}) \% p
我们还可以得出
（a^{\Phi \left(n\right)})^{k}\equiv 1\left( mod\ n\right)
因为
(a^{\Phi \left(n\right)})^{k} \% n=（a^{\Phi \left(n\right)}\%n)^{k}\%n=1^k\%n =1
我们举个例子：比如
{\Phi \left(10\right)}＝{\Phi \left(2*5\right)}={\Phi \left(2\right)}*{\Phi \left(5\right)}=(2-1)*(5-1)=4
所以根据欧拉定理：因为9与10互质所以
9^{\Phi \left(10\right)}=9^4\equiv 1\left( mod\ 10\right)
于是(9^4 )^k 除以10都余1。
模反元素
如果a与n互质，则必然能够找到一个数使得
ab\equiv 1\left( mod\ n\right)
则b称为a的模反元素，我们可以通过欧拉定理来给予证明
a^{\Phi \left(n\right)}=1\left( mod\ n\right)
a^{\Phi \left(n\right)}= a*a^{\Phi \left(n\right)-1}\equiv 1\left( mod\ n\right)
模反元素的概念对后续在已知道公钥情况下，计算合适的私钥是有很重要的意义的。
掌握了这些数学知识，你可能觉得这些东西似乎很孤立，看不到任何作用和价值，不过接下来我们来看看RSA是怎么运作的，你就会发现这些看似毫无作用的东西是如何产生价值的。
RSA究竟如何运作？
RSA 实现方式：
- 找出两个很大的且不相等的质数P和Q
- 求出他们的乘积n=p*q
- 才有欧拉函数计算小于n范围内与n互质的个数。这一结果我们姑且定义为为m，因为p与q互质所以
m={\Phi \left(n\right)} = {\Phi \left(p*q\right)}=(p-1)*(q-1) - 在1<e<M选取一个整数e，要求e与m互质。
- 寻找一个整数d，使得
E*D \equiv 1(mod\ M)
这也就是我们前面提及的模反元素的知识，因为e与m互质，则必然能够找到d使得上述表达式成立。 - 到此为止，我们完成了公私秘钥对的创建工作，即(e,n)是公钥，(d,n)是私钥。更准确的来说n被称为模数，e称为公开指数，而d称为私密指数。
- 此时我们有一串明文信息x，则我们使用公钥E加密即x^E mod n =y,y为加密后的数据
- 当我们拿到y通过私钥d执行Y^d mod n = x即可解密。
从加解密的表达式可以看出在，数学原理上公钥和私钥其实并没有什么差异。你可以用公钥加密、私钥解密，也可以用私钥加密，公钥进行解密。但是对于密码学来说，对公钥和私钥会有不同的要求。
另外需要注意的是这里明文数值不能大于等于N，否则解密的结果并不会等于明文。
RSA有效性证明
因为加密的公式为：
x^e mod n = y
而解密公式为
y^d mod n = x
从上面表达式可以看出在数学原理上公钥和私钥其实并没有什么差异。你可以用公钥加密、私钥解密，也可以用私钥加密，公钥进行解密。
所以根据：
y=x^e - kn
且因为Y^D mod N = x 所以
y^D \equiv x (mod\ n)
所以确定能否加解密的过程本质就是证明：
（x^e - kn)^d \equiv x (mod\ n)（1.1）
而根据二项式定理
[图片上传失败...(image-ca75c7-1530364603810)]
（x^e - kn)^d 展开后演变为
x^ed-m_{1}x^{e(d-1)}kn+m_{2}x^{e(d-2)}(kn)^2...m_{n}(kn)^{d}
你会发现二项式展开后，唯有x^ed 没有包含n，因此结合模运算加法运算规则(a + b) % p = (a % p + b % p) % p ，要想证明1.1的表达式，则必然证明：
x^{ed} \equiv x (mod\ n)
由于
ed \equiv 1 (mod\ {\Phi \left(n\right)})
所以
ed=h{\Phi \left(n\right)})+1
则从证明
x^{ed} \equiv x (mod\ n) 演变为证明
x^{h{\Phi \left(n\right)}}*x\equiv x (mod\ n)
如果x与n 互质则根据欧拉定理
x^{{\Phi \left(n\right)}}\equiv 1 (mod\ n)
基于在欧拉定理中提及的，根据取模运算规则可以得出
x^{h{\Phi \left(n\right)}}\equiv 1 (mod\ n)
仍然是基于取模运算乘法规则，我们又可以得出
x^{h{\Phi \left(n\right)}}x\equiv x (mod\ n)
这样原式得到证明。
那么如果x与n不互质的情况下，因为n=p*q且p和q都是质数，所以n的因数只有p和q了，因为x与n不互质，那么我们可以认为：
x=k_{1}p 0 < u< q
或者
x=k_{2}q 0 < k
请注意k值的取值范围，这里要牢记一点明文值必须大于0且小于n值。
这里我们先姑且定义
x=kq
0 < k< p
那么因为p与q都是质数，根据k<p 我们可以认为k与p是互质的，而p本身就是质数，所以根据费尔马小定理（n
为质数，a与n互质，如果有所遗忘可以回到前面查看相关说明。）
a^{n-1}\equiv 1\left( mod\ n\right)
那么
(kq)^{p-1}\equiv 1\left( mod\ p\right)
根据费尔马定理我们推得出来的表达式
a^{\Phi \left(n\right)}\equiv 1\left( mod\ n\right)
得出
((kq)^{p-1})^{h*(q-1)}\equiv 1\left( mod\ p\right)
也就是
(kq)^{h*(q-1)(p-1)}\equiv 1\left( mod\ p\right)
根据取模运算的运算定义：
给定一个正整数p，任意一个整数n，一定存在等式 ：
n = kp + r ；
其中 k、r 是整数，且 0 ≤ r < p，则称 k 为 n 除以 p 的商，r 为 n 除以 p 的余数。
得出
(kq)^{h*(q-1)(p-1)} = 1+u*p
这里的u为任意整数，这时候两边都乘以kq
(kq)^{h*(q-1)(p-1)}*kq = 1+u*k*q*p
因为n=pq x=kq那么
(x)^{\Phi \left(n\right)+1} = x+u*k*n
还是根据之前取模运算定义得出
(x)^{h\Phi \left(n\right)+1}\equiv x\left( mod\ n\right)
即原式得到了证明。
RSA的安全性理论
之所以RSA是安全的，很大程度取决于n值是否足够大以至于在已知公钥e和模数n的情况下仍然难以找出d。根据之前的谈及的密钥对计算方式：
E*D \equiv 1(mod\ M)
要想算出D就必须计算出M 而M = (p-1)(q-1) ，n=p*q则要算出M就需要知道p和q，即从一个庞大的数中分离出两个也很大的质数。大数的素因数分解被认为是一个困难的问题，即使是现代的计算机也非常难于处理，所以许多加密系统的原理都是建基于此。
目前最安全的做法是选择使用rsa-2048，随着2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性。这里的2048表示的是模数N
的二进制位为2048位。而一般公钥世面上普遍选择65535，这是安全性和计算速度之间的综合考虑下选择出来的一个比较妥当的数值。因为加解密函数都是在做大数的指数运算，所以在工程方面会尽量考虑公钥加解密的执行速度，毕竟公钥是被外部使用的。
此外还记得前面提到rsa加密的明文数值大小不能大于N，或者其位数不能超过N的位数的限制。一旦超过密文解密后和原文数据不相匹配，这时候就需要采用分段加密技术。而另一方面明文的值也不能为0或1，-1因为这样导致密文也是0，1或者-1。另外也有一个问题即如果用私钥解密一段非法数据，那么得到是解密失败还是一个毫无意义的解密内容呢？这时候需要采用 rsa padding技术。对这个概念理解可以参考浅谈RSA Padding这篇文章。
总结
通过学习一些简单的数论知识即质数、欧拉函数、模反元素等概念后，我们也了解RSA算法大致过程，总的来说公私密钥对需要计算如下几个数据：
- 很大的质数 p
- 很大的质数 q
- 两个质数乘积：n = p*q
- 小于n范围内，与n互质的数个数：φ(n)
- 0~φ(n) 中的某个与φ(n)互质的数E
- E的模反元素D
RSA的安全性不仅仅建立于大数质因数分解困难这一理论基础上，在工程上如何对上述这些数值的选取也是很大的学问。通过对rsa学习让我对工程和理论之间的关系理解上更进一步。理论确定了方向的可行性，而工程实践则要确保在有限资源下，理论结果是可以应用起来解决特定规模的问题。而在加密算法领域，一旦工程实践出现偏差，往往就容易产生安全漏洞，尽管算法理论证明是安全的。比如rsa中p q值的选择等。这里我罗列几个工程问题有兴趣的童鞋可以再进一步做探索：
-
如何确定一个数是质数？RSA周边——大素数是怎样生成的？
-
如何选取安全的p q值，可以参考RSA 生成公私钥时质数是怎么选的？
-
如何快速找到模反元素即D
-
另外，加密解密公式是需要做大数值的指数计算，所以如何快速进行指数计算呢？
网友评论