Python实现模重复平方的算法和实现RSA公钥密码算法 Python

有了之前进制转换和字符串的坑这次写起来挺顺的233
先贴一下模重复平方法的数学实现，一个很明显的递推。
我觉得编程实现递推关系的时候，是可以无视其数学意义和数学关系（比如这个位置到底是aj还是aj+1并不重要），只看这个数和上一个数之间的数量关系就好了。 【Python实现模重复平方的算法和实现RSA公钥密码算法】如果说哪里要注意一下大概是最后的边界吧，判断是否到达二进制数的末尾，用len（n）来返回长度判断。第一次用了if i!=n[-1] 显然有问题，因为n这个字符串不是0就是1

文章图片

文章图片

文章图片

实现代码：

def test(m, n, e): n = bin(int(n)) n = n.replace('0b', '') n = n[::-1] a = [1] b = [int(e)] m = int(m)cum = 0 for i in n: if int(i) > 0: a.append(a[cum]*b[cum] % m) else: a.append(a[cum] % m) if cum < len(n): b.append(b[cum] * b[cum] % m) cum = cum + 1print(a[cum])m =input("请输入模数m: ") b =input("请输入幂: ") a =input("请输入底数: ") test(m, b, a)

至于RSA，按照步骤来就好了，根据扩展欧几里得和刚刚的模重复平方。

def ex_gcd(a, b): s = [0, 1, 0] t = [0, 0, 1] r = [a, b] r.append(r[0] % r[1]) q = [0, 0, r[0] // r[1]]n = 3 while 1: q.append(r[n - 2] // r[n - 1]) r.append(r[n - 2] % r[n - 1]) s.append(s[n - 2] - (q[n - 1] * s[n - 1])) t.append(t[n - 2] - (q[n - 1] * t[n - 1])) if r[n] == 0: break n = n + 1return s[n]def test(m, n, e): n = bin(int(n)) n = n.replace('0b', '') n = n[::-1] a = [1] b = [int(e)] m = int(m)cum = 0 for i in n: if int(i) > 0: a.append(a[cum]*b[cum] % m) else: a.append(a[cum] % m) if cum < len(n): b.append(b[cum] * b[cum] % m) cum = cum + 1return a[cum]def RSA(p, q, e): fn = (p - 1) * (q - 1) d = ex_gcd(e, fn) % fn n = p*q print('φ(n)='+str(fn)+'n='+str(n)) print("Ke＝(n, e) ＝ ("+str(n)+','+str(e)+')') print("Kd＝(n, d) ＝ (" + str(n) + ',' + str(d) + ')') a = int(input('请输入密文的编码： ')) print("Ke＝(n, e) ＝ ("+str(n)+','+str(e)+')'+'加密编码'+str(a)+'得：') # c＝(“de”) e (mod n)＝ 827(mod 143); c = test(n, e, a) print('得到密文：'+str(c))#解密部分 c = input("需要解密的密文： ") e = test(n, d, c) print("解密得到明文："+str(e))print('这里是模重复平方法： ') m = input("请输入模数m: ") b = input("请输入幂: ") a = input("请输入底数: ") x = test(m, b, a) print(x)print("这里是RSA公钥秘钥算法： ") p = int(input("请输入第一个大整数p： ")) q = int(input("请输入第二个大整数q： ")) e = int(input("请输入公钥e: ")) RSA(p, q, e)