【密码学】RSA算法过程-求解密钥

1、密钥的计算获取过程

密钥的计算过程为:首先选择两个质数p和q,令n=p*q。

令k=ϕ(n)=(p−1)(q−1),原理见2的分析

选择任意整数d,保证其与k互质

取整数e,使得[de]k=[1]k。也就是说de=kt+1,t为某一整数。

2、RSA加密算法原理解析

下面分析其内在的数学原理,说到RSA加密算法就不得不说到欧拉定理。

    欧拉定理(Euler’s theorem)是欧拉在证明费马小定理的过程中,发现的一个适用性更广的定理。
    首先定义一个函数,叫做欧拉Phi函数,即ϕ(n),其中,n是一个正整数。
    ϕ(n)=总数(从1到n−1,与n互质整数)
    比如5,那么1,2,3,4,都与5互质。与5互质的数有4个。ϕ(5)=4
    再比如6,与1,5互质,与2,3,4并不互质。因此,ϕ(6)=2
    对于一个质数p来说,它和1, 2, 3, …, p – 1都互质,所以ϕ(p)=p−1。比如ϕ(7)=6,ϕ(11)=10

欧拉定理叙述如下:

欧拉定理:如果n是一个正整数,a是任意一个非0整数,且n和a互质。那么,a^ϕ(n)−1可以被n整除。

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

推论2:[ab]n=[[a]n[b]n]n

证明:假设a和b除以n的余数为c1,c2。a和b可以写成a=nt1+c1,b=nt2+c2。那么,ab=n2t1t2+nt1c2+nt2c1+c1c2。因此ab除以n的余数为c1c2。即[ab]n=[a]n[b]n。

有以上定理后,由此可以推导出RSA算法的内在原理。

根据欧拉定理,对于任意z,如果z与n互质,那么:

[z^ϕ(n)]n=[z^k]n=[1]n

因此,

[z^(de)]n=[z^(kt+1)]n=[z^(kt)*z]n=[z^kt]n*[z]n= [z]n 因为[z^k]n = [1]n

上面主要使用了de=kt+1以及推论2。也就是说:

[z^(de)]n=[z]n

根据2的推论,有

([z^e]n)^d=[z]n

即d个余数相乘,因为其乘积可能大于n,所以由[ab]n=[[a]n[b]n]n,例如令a和b都为5,n为3,可知该结论

故上式可描述为[([z^e]n)^d]n=[z]n=z,就是原数字乘方求余数,然后再乘方求余数后得到原来数字的过程,得证。

公开的加密方式,私有的解密方式。RSA安全的关键在于很难对一个大的整数进行因子分解。

3、练习习题

按照RSA算法,若选两个奇数p=5,q=3,公钥e=7,则私钥d为:()

答案解析:

按RSA算法求公钥和密钥:
(1)选两质数p=5,q=3;
(2)计算n=p×q=5×3=15;
(3)计算(p-1)×(q-1)=8;
(4)公钥e=7,则依据ed=1 mod(p-1)×(q-1),即7d=1 mod 8。

结合四个选项,得到d=7,即49 mod 8=1。

4、Python代码实现

p =5
q = 3
e = 7
n = q*p
mod_value = (p-1)*(q-1)
# 依据 ed = 1 mod (p-1)*(q-1)
# d 现在是我们需要确定的密钥,那么逆推就是 e*d % ((p-1)*(q-1)) == 1,那么就输出d的值,因为它就是我们需要求得的密钥值
for d in range(0,n):
    if (e*d)%mod_value==1:
        print d

result >> 7
上一篇:SqlServer查看锁表与解锁


下一篇:【Unity3D】计算二维向量夹角(-180到180)