RSA算法的程序实现
时间: 2023-07-10 07:15:32 浏览: 47
RSA算法是一种非常常见的加密算法,其实现程序如下:
1. 选择两个质数p和q,计算N=p*q;
2. 计算欧拉函数φ(N)=(p-1)*(q-1);
3. 选择一个整数e,满足1<e<φ(N),且e与φ(N)互质;
4. 计算d=e^-1 mod φ(N),即d为e的模φ(N)的乘法逆元;
5. 公钥为(N,e),私钥为(N,d);
6. 加密:对明文M进行加密,得到密文C=C^e mod N;
7. 解密:对密文C进行解密,得到明文M=M^d mod N。
以下是一个简单的Python实现:
```python
import random
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
d, x, y = extended_gcd(b, a % b)
return (d, y, x - (a // b) * y)
def generate_keypair(p, q):
n = p * q
phi = (p - 1) * (q - 1)
# choose e such that 1 < e < phi and gcd(e, phi) = 1
e = random.randrange(1, phi)
g = gcd(e, phi)
while g != 1:
e = random.randrange(1, phi)
g = gcd(e, phi)
# compute d = e^-1 mod phi
d = extended_gcd(e, phi)[1]
d = d % phi
return ((n, e), (n, d))
def encrypt(pk, plaintext):
n, e = pk
cipher = [pow(ord(char), e, n) for char in plaintext]
return cipher
def decrypt(pk, ciphertext):
n, d = pk
plain = [chr(pow(char, d, n)) for char in ciphertext]
return ''.join(plain)
if __name__ == '__main__':
# generate key pair
p = 61
q = 53
public_key, private_key = generate_keypair(p, q)
print("Public key:", public_key)
print("Private key:", private_key)
# encrypt and decrypt message
message = "Hello, World!"
print("Message:", message)
ciphertext = encrypt(public_key, message)
print("Ciphertext:", ciphertext)
plaintext = decrypt(private_key, ciphertext)
print("Plaintext:", plaintext)
```
在这个实现中,我们使用了两个质数p和q来生成RSA密钥对,并用公钥加密明文,用私钥解密密文。在这个例子中,我们使用了p=61和q=53这两个质数生成密钥对,并用密钥对对"Hello, World!"这个明文加密和解密。