前置知识:欧拉定理

进阶知识:Miller Rabin算法(用于生成大素数),蒙哥马利算法(用于加快大数相乘再取模运算)

引入

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

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

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

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

算法流程

  1. 选定两个素数\(p\),\(q\),令\(n=pq,\phi{(n)}=(p-1)(q-1)\)
  2. 选取一个公钥\(e\),满足\(1<e<\phi{(n)}\),且\(e\)与\(\phi{(n)}\)互质
  3. 生成私钥 \(d\),满足\(ed\equiv1(mod\ \phi{(n)})\)
  4. 假设要发送的信息为\(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算法的流程,也知道了它的正确性,但是还有几个问题需要解决。

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

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