coding=gbk

import math
import random

平方乘算法求余数 base^n mod mod

def repeatMod(base, n, mod):

a = 1while n:    if n&1:        a = (a*base)%mod    base = (base*base)%mod    n = n>>1return a

判断是否为素数（Miller-Rabbin）

def IsPrime(BigNum, RoundTime):

temp = BigNum - 1k = 0while (temp & 0x1)==0 and temp:    temp = temp >>1    k = k+1m = tempwhile RoundTime:    a = random.randint(1, BigNum- 2)    b =  repeatMod(a, m, BigNum)    if b == 1 or b==BigNum-1:        return True    for i in range(1,k):        b = repeatMod(b, 2, BigNum) #若b^2^(k-1) mod n ==+-1,则是一个素数        if b == 1 or b==BigNum-1:            return True    RoundTime = RoundTime -1return False

生成大素数

def BuildBigPrime():

flag = Falsewhile not flag:    BigNum = random.randint(2**512,2**513)    if BigNum % 2 !=0 :        flag = IsPrime(BigNum, 10)return BigNum

辗转相除求最大公约数

def MaxCommDivisor(m,n):

if n == 1:    return Trueif m % n == 0:  return Falseelse:    flag = MaxCommDivisor(n, m%n)return flag

#求 b mod a b的逆元
def get_(a, b):

if b == 0:    return 1, 0else:    k = a // b            x1, y1 = get_(b, a % b)    x, y = y1, (x1 - k * y1)return x,y

if name == '__main__':

print("[商品期货](https://www.gendan5.com/futures/cf.html)正在生成大素数------")p = BuildBigPrime()q = BuildBigPrime()while p==q:    q = BuildBigPrime()print("大素数p:",p,"\n大素数q:",q)n = p*qfn = (p-1)*(q-1)while True:    key1 = random.randint(2**64,2**65)    if  MaxCommDivisor(fn, key1):        breakprint("密钥1为:",key1)k, key2 = get_(fn,key1)#生成的私钥key2可能为正数，咱们须要mod fn来保障其为负数if key2<0:     key2 = key2 % fnprint("密钥2为:",key2)m = input("请输出明文：")m = int(m.encode('utf-8').hex(),16)print('\n------加密中----')c = repeatMod(m,key1,n)print("明文为：",m,"\n密文为：",c)print('\n------解密中----')m = repeatMod(c,key2,n)print("密文为：",c,"\n明文为：",m)