RSA 加密算法 / RSA algorithm

import secrets

print("************程序功能************")
print("求RSA加密算法")
print("********************************")
print("Reference books: 《现代密码学（第二版）》")
print("Reference books: https://blog.csdn.net/jijianshuai/article/details/80582187")
print("Reference books: https://baike.baidu.com/item/RSA%E7%AE%97%E6%B3%95/263310?fromtitle=RSA&fromid=210678&fr=aladdin#reference-[5]-10613-wrap")
print("Completion time：2021-6-4")
print("Last modification time ：2021-6-4",'\n')
print("--------------------------------------------------------")

P = secrets.randbelow(2**1024)
if (P%2 == 0):
        P = P+1
Q = secrets.randbelow(2**1024)
if (Q%2 == 0):
        Q = Q+1

#求模逆
def moni(X,Y):
    #第1步
    n1 = Y
    n2 = X
    b1 = 0
    b2 = 1

    #第2步
    q = n1//n2   #注意用//表示整数除法
    r = n1-q*n2

    #第3步
    while (r != 0):
        n1 = n2
        n2 = r
        t = b2
        b2 = b1-q*b2
        b1 = t

        q = n1//n2
        r = n1-q*n2

    #第4步
    ans = b2 % Y
    if (n2 == 1):
        return (ans)
    else:
        return (0)
        
#高幂模
def gaomimo(a,b,P):
    c = 1
    if (b == 0):
        return (c)
    while(1):
        if (b%2 != 0):
            b = b-1
            c = (c*a) % P
            if (b == 0):
                return (c)
        else:
            b = b//2
            a = (a*a) % P
    

#米勒-拉宾素性检验
def judge_sushu(P):
    if (P==2 or P==3):
        return (1)

    s = 1
    while(1):
        if((P-1)%(2**s) == 0):
            s = s+1
        else:
            s = s-1
            break
    m = (P-1)//(2**s)

    judge = 0
    for b in range(1,(P-1),int((P-1)/10)):
        r = 0
        z = gaomimo(b,m,P)
        if(z == 1 or z == P-1):
            judge = judge + 1
            continue
        else:
            while(1):
                if (r == s-1):
                    return(0)
                else:
                    r = r+1
                    z = gaomimo(z,2,P)
                    if(z == P-1):
                        continue
    return(1)

print("生成大素数中......")
while(judge_sushu(P) == 0):
    P = P+2
while(judge_sushu(Q) == 0):
    Q = Q+2
#print(P,"\n",Q)


#计算公共模数
N = P * Q

#欧拉函数
oula = (P-1)*(Q-1)

print("分配公钥及私钥中......")
#计算公钥E
E = min(P,Q)

D = 0
while(D == 0):
    E = E - 2
    while(judge_sushu(E) == 0):
        E = E-2

    #计算私钥D
    D = moni(E,oula)
#print(D)

print("加密中......")
#公钥加密
M = 2
C = gaomimo(M,E,N)

#私钥加密
M = gaomimo(C,D,N)

print("初始明文为：2",'\n')
print("公钥为：",E,'\n')
print("私钥为：",D,'\n')
print("公共模数为：",N,'\n')
print("密文为：",C)