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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
| def f(r, x, n): """ 计算 x 的 r 次方模 n """ a = x b = r c = 1 while b != 0: while b % 2 == 0: b = b // 2 a = (a * a) % n if b % 2 != 0: b = b - 1 c = (c * a) % n return c
def Enclid(n, d): """ 计算模逆运算 """ a = n b = d t = 0 v = 1 w = 0 while True: r = a % b if r != 0: q = (a - r) // b a = b b = r w = v v = t - q * v t = w else: break if b == 1: if v >= 0: return v else: return n + v else: return 0
def gcd(a, b): """ 计算最大公约数 """ r = a % b while True: r = a % b if r != 0: a = b b = r else: break if b == 1: return 1 else: return b
def rsa(): """ RSA 加密算法 """ p = int(input("输入两个素数:(p、q)\n")) q = int(input()) n = p * q fn = (p - 1) * (q - 1)
e = int(input("输入e:\n")) while True: if gcd(fn, e) == 1: break else: e = int(input("必须满足gcd(fn,e)=1\n"))
d = Enclid(fn, e)
if d == 0: print("出错了!\n") else: print("公钥(%d,%d)\n" % (e, fn)) print("私钥:(%d,%d)\n" % (d, fn))
m = int(input("Enc: 输入明文:\n")) while m >= p * q: print("错误!明文需要小于p*q=%d!\n" % (p * q)) m = int(input())
print("密文:%d\n" % f(e, m, n))
print("解密:m=%d\n" % f(d, f(e, m, n), n))
print("RSA加密算法\n") print("姓名: W1ndys\n") print("学号: 10000001\n")
rsa()
input("按Ctrl+C退出")
|