Sky's blog

RSA算法研究

字数统计: 621阅读时长: 2 min
2017/06/21 Share

RSA算法原理

1.选定密钥长度
2.生成n(n是两个大质数p、q的积,n的二进制表示时所占用的位数就是之前选定的密钥长度)
3.随机选定一个e1(要求e1与(p-1)(q-1)互质)
4.选择一个e2(要求(e2
e1)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

点击赞赏二维码,您的支持将鼓励我继续创作!
CATALOG
  1. 1. RSA算法原理
  2. 2. RSA论证
    1. 2.1. 密钥长度
    2. 2.2. 欧拉定理及推论
      1. 2.2.1. 欧拉定理
      2. 2.2.2. 推论1
      3. 2.2.3. 推论2
    3. 2.3. RSA的加解密证明
    4. 2.4. RSA本质