RSA非对称加密算法实现

RSA非对称加密算法是一种公开密钥加密算法，其加解密过程中使用的密钥是不同的。下面是RSA加密算法的实现步骤：

1. 选择两个大质数p和q，计算其乘积n=p*q

2. 计算欧拉函数φ(n)=(p-1)*(q-1)

3. 选择一个整数e，满足1<e<φ(n)且e与φ(n)互质，e称为公钥

4. 计算d，使得d*e ≡ 1(mod φ(n))，d称为私钥

5. 将明文M转换为整数m，使得0<=m<n

6. 加密：C ≡ m^e(mod n)，C为密文

7. 解密：m ≡ C^d(mod n)，m为明文

下面是Python代码实现RSA加密算法：

import random

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def generate_keypair(p, q):
    n = p * q
    phi = (p-1) * (q-1)
    e = random.randint(1, phi-1)
    while gcd(e, phi) != 1:
        e = random.randint(1, phi-1)
    d = pow(e, -1, phi)
    return ((n, e), (n, d))

def encrypt(public_key, message):
    n, e = public_key
    return pow(message, e, n)

def decrypt(private_key, ciphertext):
    n, d = private_key
    return pow(ciphertext, d, n)

p = 61
q = 53
public_key, private_key = generate_keypair(p, q)
message = 123456
ciphertext = encrypt(public_key, message)
plaintext = decrypt(private_key, ciphertext)
print("Public key:", public_key)
print("Private key:", private_key)
print("Message:", message)
print("Ciphertext:", ciphertext)
print("Plaintext:", plaintext)

需要注意的是，RSA算法的安全性基于大质数分解的困难性，因此在实际应用中需要选择足够大的p和q来保证算法的安全性。