代码实现RSA,参数p、q选取3位的十进制数;
时间: 2024-03-05 21:52:58 浏览: 100
好的,下面是用Python实现RSA算法并选取3位十进制数作为p和q的示例代码:
```python
import random
# 生成3位素数
def generate_prime():
while True:
p = random.randint(100, 999)
if is_prime(p):
return p
# 判断是否为素数
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
# 求最大公约数
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
# 扩展欧几里得算法求模反元素
def mod_inverse(a, m):
if gcd(a, m) != 1:
return None
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
return u1 % m
# 加密
def encrypt(m, e, n):
return pow(m, e, n)
# 解密
def decrypt(c, d, n):
return pow(c, d, n)
# 主函数
def main():
# 生成两个3位素数p和q
p = generate_prime()
q = generate_prime()
print("p =", p)
print("q =", q)
# 计算n和phi(n)
n = p * q
phi_n = (p-1) * (q-1)
# 选择e和计算d
e = 17
d = mod_inverse(e, phi_n)
# 输出公钥和私钥
print("公钥为:(n={}, e={})".format(n, e))
print("私钥为:d =", d)
# 加密和解密
m = 123
c = encrypt(m, e, n)
decrypted_m = decrypt(c, d, n)
print("加密后的密文为:", c)
print("解密后的明文为:", decrypted_m)
if __name__ == '__main__':
main()
```
这个示例代码中,我们使用了Python内置的pow函数来进行快速幂运算,计算加密和解密结果。你可以根据需要自行调整。
阅读全文