RSA算法的简单实现

原理

$(a):$我们取2个很大的质数$p,q,记n = pq ,w = (p-1)(q-1)$.

(b):$取 e<p ,q,若de = N*(p-1)*(q-1)+1,则我们可以进行如下操作$

(c):$对数C加密,x = C^e \mod n,则x^d \mod n = c^{de} \mod n$

(d):$根据费马小定理,c^{p-1} \mod p = 1,c^{q-1} \mod q = 1,c^w \mod n = 1=〉c^{de-1} \mod n = 1$

$(e):所以c^{de} \mod n = c，因此只需要(n,e),(n,d)两组信息就可以对数据加密和解密,而且由于传递信息只要其中一个,所以不担心解密办法会被破译。$

$(f)$:回到(b),我们怎么求出来d?这里需要用到辗转相除法的变形来计算逆元,具体算法请查阅资料。

算法的简单实现:里面主要有一个辗转相除法的变形和快速求余的算法。

def rev_gcd(a,b):#计算逆元
    an,N = [],a
    while 1:
        divisior = a//b
        a,b = b,a%b
        if b==0:break
        an.append(divisior)
    b1,b2 = 1,0
    for ai in an[::-1]:b1,b2 = b1*ai+b2,b1
    if len(an)%2 ==0:return b1
    else:return N-b1
def create(p,q):
    n = p*q
    e = (p>>1)+(q>>1)
    x = (p-1)*(q-1)
    d = rev_gcd(x,e)
    return n,d,e
def rsa_endecode(c,e,n):#快速求余算法
    u = 1;
    while e:
        if e&1:u = (u*c)%n
        c = (c**2)%n
        e >>=1
    return u
n,d,e  = create(104729,15485863)
c = rsa_endecode(310,e,n)
print(c,rsa_endecode(c,d,n))