#coding=gbk
import math
import random
# 平方乘算法求余数 base^n mod mod
def repeatMod(base, n, mod):
a = 1
while n:
if n&1:
a = (a*base)%mod
base = (base*base)%mod
n = n>>1
return a
# 判断是否为素数（ Miller-Rabbin ）
def IsPrime(BigNum, RoundTime):
temp = BigNum - 1
k = 0
while (temp & 0x1)==0 and temp:
temp = temp >>1
k = k+1
m = temp
while 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 -1
return False
# 生成大素数
def BuildBigPrime():
flag = False
while 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 True
if m % n == 0:
return False
else:
flag = MaxCommDivisor(n, m%n)
return flag
# 求 b mod a b 的逆元
def get_(a, b):
if b == 0:
return 1, 0
else:
k = a // b
x1, y1 = get_(b, a % b)
x, y = y1, (x1 - k * y1)
return x,y
if __name__ == '__main__':
print(" 正在生成大素数 ------")
p = BuildBigPrime()
q = BuildBigPrime()
while p==q:
q = BuildBigPrime()
print("外汇跟单gendan5.com 大素数 p:",p,"\n 大素数 q:",q)
n = p*q
fn = (p-1)*(q-1)
while True:
key1 = random.randint(2**64,2**65)
if MaxCommDivisor(fn, key1):
break
print(" 密钥 1 为 :",key1)
k, key2 = get_(fn,key1)
# 生成的私钥 key2 可能为负数，我们需要 mod fn 来保证其为正数
if key2<0:
key2 = key2 % fn
print(" 密钥 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)