RSA模幂运算的python实现
时间: 2023-10-16 15:06:35 浏览: 42
RSA模幂运算的Python实现代码如下:
```python
def mod_exp(base, exponent, modulus):
result = 1
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % modulus
exponent = exponent >> 1
base = (base * base) % modulus
return result
```
其中,`base`表示底数,`exponent`表示指数,`modulus`表示模数。函数返回结果为 `base ^ exponent mod modulus`。该函数使用了快速幂算法,时间复杂度为 O(log n)。
相关问题
模幂python编程
在Python编程中,模幂(Modular Exponentiation)是一个常见的数学运算,特别是在处理大数和算法设计中,尤其是在计算模意义下的幂运算,如RSA加密算法、扩展欧几里得算法等。模幂操作是快速幂算法(Fast Exponentiation)的应用,它可以显著提高计算效率,因为普通乘法的时间复杂度为O(n),而快速幂可以通过分治策略降低到O(log n)。
Python提供了内置的`pow()`函数来执行模幂运算,其基本语法如下:
```python
result = pow(base, exponent, modulus)
```
- `base`: 要进行幂运算的底数。
- `exponent`: 指数,表示要对底数进行多少次乘法。
- `modulus`: 取余数的操作数,结果会限制在模数范围内。
例如,如果你想要计算10的3次方然后取模7,你可以这样写:
```python
res = pow(10, 3, 7)
print(res)
```
快速幂的具体实现通常会用到递归或循环,核心思想是将指数不断对2取余,然后在每次迭代中只计算一次底数的平方,直到剩余的指数为1或0。
编程实现快速模幂运算公钥密码算法
下面是一个使用Python语言实现快速模幂运算公钥密码算法的示例代码:
```python
import random
# 模幂运算函数
def mod_exp(base, exponent, modulus):
result = 1
while exponent > 0:
# 如果指数是奇数,则先乘上一个base
if exponent % 2 == 1:
result = (result * base) % modulus
# 将指数除以2,同时将base平方
exponent = exponent // 2
base = (base * base) % modulus
return result
# 生成公钥和私钥函数
def generate_key_pair(p, q):
n = p * q
phi = (p - 1) * (q - 1)
# 选择一个与phi互质的整数e
e = random.randrange(1, phi)
while gcd(e, phi) != 1:
e = random.randrange(1, phi)
# 计算e的逆元d
d = mod_inverse(e, phi)
# 返回公钥和私钥
return ((n, e), (n, d))
# 求最大公约数函数
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# 求模反元素函数
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(plaintext, public_key):
n, e = public_key
# 将明文转换成整数
plaintext_int = int.from_bytes(plaintext.encode(), "big")
# 对明文进行加密
ciphertext_int = mod_exp(plaintext_int, e, n)
# 将密文转换成字节串
ciphertext = ciphertext_int.to_bytes((ciphertext_int.bit_length() + 7) // 8, "big")
return ciphertext
# 解密函数
def decrypt(ciphertext, private_key):
n, d = private_key
# 将密文转换成整数
ciphertext_int = int.from_bytes(ciphertext, "big")
# 对密文进行解密
plaintext_int = mod_exp(ciphertext_int, d, n)
# 将明文转换成字节串
plaintext = plaintext_int.to_bytes((plaintext_int.bit_length() + 7) // 8, "big").decode()
return plaintext
# 测试代码
p = 61
q = 53
public_key, private_key = generate_key_pair(p, q)
plaintext = "Hello, world!"
ciphertext = encrypt(plaintext, public_key)
decrypted_plaintext = decrypt(ciphertext, private_key)
print("公钥:", public_key)
print("私钥:", private_key)
print("明文:", plaintext)
print("密文:", ciphertext)
print("解密后的明文:", decrypted_plaintext)
```
这个示例代码实现了一个基于RSA算法的公钥密码系统,可以对任意长度的明文进行加密和解密。生成公钥和私钥时,需要选择两个大质数p和q,并计算n=pq和phi=(p-1)(q-1),然后选择一个与phi互质的整数e作为公钥,计算e的逆元d作为私钥。加密时,将明文转换成整数,使用公钥进行加密,并将密文转换成字节串。解密时,将密文转换成整数,使用私钥进行解密,并将明文转换成字符串。
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)