RSA算法原理
1.选定密钥长度
2.生成n(n是两个大质数p、q的积,n的二进制表示时所占用的位数就是之前选定的密钥长度)
3.随机选定一个e1(要求e1与(p-1)(q-1)互质)
4.选择一个e2(要求(e2e1)mod((p-1)*(q-1))=1)
5.公开(n,e1)为公钥
6.保留(n,e2)为私钥
至此:明文:plain,密文:crypto
故别人可以使用公钥对明文加密
然后你可以使用私钥对密文解密
RSA论证
密钥长度
目前来看1024位以上的RSA尚且是安全的,密钥长度越长越安全,因为由2个大质数相乘得到n容易
但由一个大数n拆分出2个质数非常难
密钥长度越长(即n越大),分解起来就越困难(显而易见)
目前看来,想要靠暴力拆解大数n,需要的时间是显然不可能的(远远超过数据本身价值)
欧拉定理及推论
首先是欧拉定理(Euler’s theorem)
n是一个正整数,ϕ(n) = 总数(总数为从1~n-1,与n互质的整数的个数)
举例:1
2比如5这个数,那么1,2,3,4,都与5互质,所以ϕ(5)=4
再比如6这个数,只有1,5与它互质,所以ϕ(6)=2
那么容易得到,对于一个质数p,ϕ(p)=p-1
欧拉定理
如果n是一个正整数,a是任意一个非0整数,且n和a互质,那么
推论1
如果m和n是互质的正整数,那么:
推论2
RSA的加解密证明
证明:
假设a和b除以n的余数为c1,c2
a和b可以写成
故
所以ab除以n的余数为c1c2。
即
有以上定理后,由此可以推导出RSA算法的内在原理:
根据欧拉定理,对于任意z,如果z与n互质,那么:
因此
因为
上面主要使用了d*e=kt+1
以及推论2。
也就是说:
根据2的推论,有
即d个余数相乘,因为其乘积可能大于n,所以由
例如令a和b都为5,n为3,可知该结论
故上式可描述为
RSA本质
就用一句话概括:
(原数字乘方求余数得到,然后对余数再乘方求余数后得到原来数字的过程)
即a乘方求余数,得到b
再对b乘方求余数,得到c
最后a=c