拉宾公钥密码算法实现

---

（一） 算法原理

---

1.1 密钥生成

1.2 加密步骤

1.3 解密步骤

---

（二） 算法设计

---

2.1 密钥生成的设计与实现

# 生成一个大素数p
def generate_p():while True:# 使得p也在150位,p = 2t + 1时p为强素数，即t=p/2-1t = sympy.randprime(10**149, 10**150 / 2 - 1)if sympy.isprime(t):p = 2 * t + 1if len(str(p)) == 150 and sympy.isprime(p) and (p % 4 == 3):breakreturn p

2.2 加密的设计与实现

# 快速幂模运算（大指数的模运算），计算a^e mod m
def fastExpMod(a, e, m):a = a % mres = 1while e != 0:# if e & 1的判断是一种位运算，用于检查整数e的最低位是否为1。在二进制表示中，如果一个整数的最低位（最右边的位）是1，那么这个数就是奇数；如果最低位是0，那么这个数就是偶数。因此，if e & 1的判断常用于检查e是否为奇数。如果e & 1的结果为1，那么e就是奇数；如果结果为0，那么e就是偶数# 如果e是奇数，a^e=a^(e-1)*a,a^(e-1)可通过循环进行平方计算，还差个a直接乘进resif e & 1:res = (res * a) % me >>= 1  # 右移一位,相当于将 e 除以 2# a, a^2, a^4, a^8, ... , a^(2^n)a = (a * a) % mreturn res# 加密
def encode(m, n):c = m**2 % nreturn c

2.3 解密的设计与实现

# 孙子定理
def theorem(b1, b2, p, q):M1 = qM2 = p# M1 mod p的逆M1_ = gmpy2.invert(M1, p)M2_ = gmpy2.invert(M2, q)# p mod q的逆x = (b1 * M1 * M1_ + b2 * M2 * M2_) % (p * q)return x# 求解二次同余式
def calc_b(p, a):k = (p + 1) // 4b = fastExpMod(a, k, p)return b# 解密，有4个解，其中1个解为真正的明文
def decrypt(p, q, a):b1 = calc_b(p, a)b2 = calc_b(q, a)x1 = theorem(b1, b2, p, q)x2 = theorem(b1, -b2, p, q)x3 = theorem(-b1, b2, p, q)x4 = theorem(-b1, -b2, p, q)return [x1, x2, x3, x4]

---

（三）测试

---

3.1 完整源码

import sympy
import gmpy2# 生成一个大素数p
def generate_p():while True:# 使得p也在150位,p = 2t + 1时p为强素数，即t=p/2-1t = sympy.randprime(10**149, 10**150 / 2 - 1)if sympy.isprime(t):p = 2 * t + 1if len(str(p)) == 150 and sympy.isprime(p) and (p % 4 == 3):breakreturn p# 快速幂模运算（大指数的模运算），计算a^e mod m
def fastExpMod(a, e, m):a = a % mres = 1while e != 0:# if e & 1的判断是一种位运算，用于检查整数e的最低位是否为1。在二进制表示中，如果一个整数的最低位（最右边的位）是1，那么这个数就是奇数；如果最低位是0，那么这个数就是偶数。因此，if e & 1的判断常用于检查e是否为奇数。如果e & 1的结果为1，那么e就是奇数；如果结果为0，那么e就是偶数# 如果e是奇数，a^e=a^(e-1)*a,a^(e-1)可通过循环进行平方计算，还差个a直接乘进resif e & 1:res = (res * a) % me >>= 1  # 右移一位,相当于将 e 除以 2# a, a^2, a^4, a^8, ... , a^(2^n)a = (a * a) % mreturn res# 加密
def encode(m, n):c = m**2 % nreturn c# 孙子定理
def theorem(b1, b2, p, q):M1 = qM2 = p# M1 mod p的逆M1_ = gmpy2.invert(M1, p)M2_ = gmpy2.invert(M2, q)# p mod q的逆x = (b1 * M1 * M1_ + b2 * M2 * M2_) % (p * q)return x# 求解二次同余式
def calc_b(p, a):k = (p + 1) // 4b = fastExpMod(a, k, p)return b# 解密，有4个解，其中1个解为真正的明文
def decrypt(p, q, a):b1 = calc_b(p, a)b2 = calc_b(q, a)x1 = theorem(b1, b2, p, q)x2 = theorem(b1, -b2, p, q)x3 = theorem(-b1, b2, p, q)x4 = theorem(-b1, -b2, p, q)return [x1, x2, x3, x4]def main():m = 42443p = generate_p()q = generate_p()n = p * qc = encode(m, n)m_c = decrypt(p, q, c)print("m = %s\n密文c = %s\n明文m = %s" % (m, c, m_c))returnif __name__ == "__main__":main()

3.2 运行结果