用python语言实现rsa加密算法

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，它由三名美国密码学家罗恩·里维斯特、伦纳德·阿德尔曼和马丁·肖洛姆于1977年发明。在Python中实现RSA，你需要了解基本原理并编写一些核心函数。

以下是简单的RSA加密算法步骤和Python实现：

1. **生成密钥对**：选择两个大素数p和q，计算n=p*q，然后取欧拉函数φ(n)=(p-1)*(q-1)，选择e（小于φ(n）且与φ(n)互质的整数），d为e的模逆元，即满足(d*e)%φ(n)=1。

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def mod_inv(e, phi):
    d, _, _ = egcd(e, phi)
    if d == 1:
        return d

2. **公钥和私钥**：公钥是(n, e)，私钥是(n, d)。

3. **加密**：将明文m转换成整数，然后加密为c=m^e mod n。

4. **解密**：解密过程就是加密过程的逆运算，即(c^d) mod n。

def encrypt(plaintext, public_key):
    n, e = public_key
    ciphertext = pow(int(plaintext), e, n)
    return ciphertext

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

注意，这只是一个简化的版本，实际应用中还需要处理字符编码、大数计算和安全性问题等。同时，RSA算法的性能并不适合大量数据加密，因为它的加密/解密速度相对较慢。