Sky's blog

RSA算法研究

Word count: 767 / Reading time: 3 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
故别人可以使用公钥对明文加密
$$
crypto=plain^{e1}\mod n
$$
然后你可以使用私钥对密文解密
$$
plain=crypto^{e2}\mod n
$$

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互质,那么
$$
a^{\phi(n)}\equiv1\mod n
$$

推论1

如果m和n是互质的正整数,那么:
$$
ϕ(mn)=ϕ(m)ϕ(n)
$$

推论2

$$
({a}\times{b})\mod n = (({a}\mod n)\times({b}\mod n))\mod n
$$

RSA的加解密证明

证明:
假设a和b除以n的余数为c1,c2
a和b可以写成
$$
a=nt_1+c_1
$$
$$
b=nt_2+c_2
$$

$$
ab=n^2t_1t_2+nt_1c_2+nt_2c_1+c_1c_2
$$
所以ab除以n的余数为c1c2。
$$
ab/n = nt_1t_2+t_1c_2+t_2c_1 \cdots c_1c_2
$$

$$
ab\mod n = ({a}\mod n)\times({b}\mod n)
$$
有以上定理后,由此可以推导出RSA算法的内在原理:
根据欧拉定理,对于任意z,如果z与n互质,那么:
$$
{z^{ϕ(n)}}\mod n = {z^k}\mod n= 1\mod n
$$
因此
$$
({z^{de}}\mod n)=({z^{kt+1}}\mod n)=({(z^{kt})\times(z)}\mod n)=(({z^{kt}}\mod n)\times(z\mod n))= (z\mod n )
$$
因为
$$
{z^k}\mod n = 1\mod n
$$
上面主要使用了d*e=kt+1以及推论2。
也就是说:
$$
{z^{de}}\mod n = z\mod n
$$
根据2的推论,有
$$
({z^e}\mod n)^d = z\mod n
$$
即d个余数相乘,因为其乘积可能大于n,所以由
$$
({a}\times{b})\mod n = (({a}\mod n)\times({b}\mod n))\mod n
$$
例如令a和b都为5,n为3,可知该结论
故上式可描述为
$$
(z^e\mod n)^d\mod n=(z\mod n) =z
$$

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本质