RSA算法详解

前置知识：欧拉定理

进阶知识：Miller Rabin算法（用于生成大素数），蒙哥马利算法（用于加快大数相乘再取模运算）

引入

历史上常规的密码加解密算法的流程如下：

假设甲要给乙发送数据，则需要甲通过一定的加密规则将数据加密，传送给乙，乙再通过一定的解密规则进行解密。

由于可靠性高的密码算法都要公开自己的加解密算法，因此，在数据传输的过程中，密钥的传输成了一个大难题。

因此RSA算法将密钥分为公钥和私钥两个部分，公钥任何人都可以获取到，而私钥只有数据接收方知道，接下来我们看看RSA加解密算法的运作流程。

算法流程

选定两个素数$p$,$q$,令$n=pq,\phi{(n)}=(p-1)(q-1)$
选取一个公钥$e$，满足$1<e<\phi{(n)}$，且$e$与$\phi{(n)}$互质
生成私钥 $d$，满足$ed\equiv1(mod\ \phi{(n)})$
假设要发送的信息为$m$，则加解密规则成立：

$$ m^e\equiv c\pmod{n}\\ c^d\equiv m\pmod{n} $$

可靠性分析

考虑甲向乙发送一串数据，乙只需要向甲传送$n$和$e$,甲就可以将加密完成的$c$发还给乙，由乙来进行解密操作。

考虑第三方攻击者，只可能截获$n$,$e$,$c$，若要获取私钥$d$，则必须计算得$n$分解成的$p$,$q$两数。

而大质数的因式分解所需要的运算量是非常恐怖的。因此，当选定的$n$很大时，RSA算法几乎不可能被破解。

总而言之：RSA利用的是，大数容易相乘，难以分解的特性，使得算法可靠。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#RSA加解密算法实现 @copyright zeroy

p=1000000007
q=998244353
n=p*q
phi_n=(p-1)*(q-1)
E=65537

def qkpow(a,b):
    ans=1
    while b>0:
        if b%2==1:
            ans=ans*a%n
        a=a*a%n
        b=b//2
    return ans

def exgcd(a,b):     
    if b==0:         
        return 1,0,a     
    else:         
        x,y,q=exgcd(b,a%b)        
        x,y=y,(x-(a//b)*y)         
        return x,y,q

# E**D=1(mod phi_n)
def calcD():
    x,y,q=exgcd(E,phi_n)
    return x+phi_n

D=calcD()

# C=m**E%n
def encode(m):
    c=qkpow(m,E)
    return c

# ans=c**D%n
def decode(c):
    return qkpow(c,D)

def main():
    c=encode(234234)
    ans=decode(c)
    print(ans)

main()

正确性证明

RSA算法过程以及正确性证明 - 简书 (jianshu.com)

拓展知识

我们已经知道了RSA算法的流程，也知道了它的正确性，但是还有几个问题需要解决。

既然大数分解十分困难，那我们该如何寻找两个大质数来作为$p$,$q$呢？
加解密运算中涉及到了大量的大数乘法取模，这是运算复杂度最高的部分，有没有一种方法可以优化$AB\equiv C(mod\ N)$运算的速度从而优化密钥生成的速度？

方法是有的。可以采用Miller Rabin算法来对生成的大数进行质数检验，用蒙哥马利算法来优化大数相乘的复杂度，不过这不属于本文的主题，感兴趣的师傅可以自行了解。

引入#

算法流程#

可靠性分析#

代码实现#

正确性证明#

拓展知识#

引入

算法流程

可靠性分析

代码实现

正确性证明

拓展知识