一个代码实现Rabin算法加解密python
时间: 2024-03-24 18:38:17 浏览: 13
以下是使用Python实现Rabin算法的加密和解密代码示例:
```python
import random
# 生成质数p和q
def generate_primes():
while True:
p = random.randint(100, 1000)
if is_prime(p):
break
while True:
q = random.randint(100, 1000)
if is_prime(q):
break
return p, q
# 判断是否为质数
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
# 求最大公约数
def gcd(a, b):
while b:
a, b = b, a % b
return a
# 求扩展欧几里得算法
def extended_euclidean_algorithm(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = extended_euclidean_algorithm(b % a, a)
return gcd, y - (b // a) * x, x
# 生成公私钥对
def generate_keys():
p, q = generate_primes()
n = p * q
phi_n = (p - 1) * (q - 1)
while True:
e = random.randint(2, phi_n - 1)
if gcd(e, phi_n) == 1:
break
_, x, y = extended_euclidean_algorithm(e, phi_n)
d = x % phi_n
return (n, e), (n, d)
# 加密
def encrypt(message, public_key):
n, e = public_key
return (message ** 2) % n
# 解密
def decrypt(ciphertext, private_key):
n, d = private_key
x = (ciphertext ** ((p + 1) // 4)) % p
y = (ciphertext ** ((q + 1) // 4)) % q
_, s, t = extended_euclidean_algorithm(p, q)
r1 = (s * p * y + t * q * x) % n
r2 = n - r1
r3 = (s * p * y - t * q * x) % n
r4 = n - r3
return r1, r2, r3, r4
# 测试代码
if __name__ == '__main__':
message = 123
public_key, private_key = generate_keys()
ciphertext = encrypt(message, public_key)
plaintext = decrypt(ciphertext, private_key)
print('明文:', message)
print('密文:', ciphertext)
print('解密结果:', plaintext)
```
注:该代码实现的是Rabin算法的基本版本,存在安全隐患,仅供学习参考。