RSA加密算法中的加密部分附上解释和示例代码

RSA加密算法是一种公钥密码体制，常用于数据加密和数字签名。它的加密部分有以下步骤：

1. 选择两个不同的质数p和q，计算它们的乘积n=p*q。
2. 计算欧拉函数φ(n)=(p-1)*(q-1)。
3. 选择一个小于φ(n)且与φ(n)互质的整数e作为公钥。
4. 计算私钥d，使得d*e=1(mod φ(n))。
5. 将明文M转化为整数m，满足0≤m<n。
6. 计算密文C=m^e(mod n)。

示例代码如下：

import random

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

def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

def mod_inv(a, m):
    def egcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            g, y, x = egcd(b, a % b)
            return g, x, y - (a // b) * x
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    else:
        return x % m

def generate_keypair(p, q):
    if gcd(p, q) != 1:
        raise Exception('p and q should be coprime')
    n = p * q
    phi_n = phi(n)
    e = random.randrange(1, phi_n)
    while gcd(e, phi_n) != 1:
        e = random.randrange(1, phi_n)
    d = mod_inv(e, phi_n)
    return ((e, n), (d, n))

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

# Example usage:
p = 61
q = 53
public_key, private_key = generate_keypair(p, q)
message = 123456
ciphertext = encrypt(message, public_key)
print('Public key:', public_key)
print('Private key:', private_key)
print('Message:', message)
print('Ciphertext:', ciphertext)