RSA

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，常用于数据加密和数字签名。它基于两个大素数的乘积因子分解的难题，其中一个素数用于加密，另一个素数用于解密。

下面是RSA加密的基本步骤：

1. 选择两个不同的大素数p和q。
2. 计算n = p * q，其中n是RSA加密的模数。
3. 计算欧拉函数φ(n) = (p-1) * (q-1)，表示小于n且与n互质的正整数的个数。
4. 选择一个整数e，满足1 < e < φ(n)，且e与φ(n)互质。e称为公钥指数。
5. 计算e的模反元素d，满足e * d ≡ 1 (mod φ(n))。d称为私钥指数。
6. 公钥为(n, e)，私钥为(n, d)。
7. 要加密明文m，计算密文c = m^e (mod n)。
8. 要解密密文c，计算明文m = c^d (mod n)。

在实际使用中，RSA加密通常用于加密对称加密算法的密钥，以提供更高的安全性和密钥交换的便利性。

需要注意的是，RSA加密的安全性依赖于大素数的选择和密钥长度的适当设置。通常要选择足够大的素数和密钥长度以保护加密数据免受攻击。此外，RSA加密的性能较慢，因此通常与对称加密算法结合使用，以实现更高效的加密和解密过程。

import random


def generate_keys(p, q):
    # 计算 n = p * q 和 φ(n) = (p-1) * (q-1)
    n = p * q
    phi = (p - 1) * (q - 1)

    # 选择公钥指数 e，满足 1 < e < φ(n) 且 e 与 φ(n) 互质
    e = random.randrange(1, phi)
    while gcd(e, phi) != 1:
        e = random.randrange(1, phi)

    # 计算私钥指数 d，满足 e * d ≡ 1 (mod φ(n))
    d = modular_inverse(e, phi)

    # 返回公钥和私钥
    public_key = (n, e)
    private_key = (n, d)
    return public_key, private_key


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


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 modular_inverse(a, m):
    d, x, y = extended_gcd(a, m)
    if d == 1:
        return x % m
    else:
        raise ValueError("The modular inverse does not exist.")


def encrypt(message, public_key):
    n, e = public_key
    # 加密明文 m，计算密文 c = m^e (mod n)
    ciphertext = pow(message, e, n)
    return ciphertext


def decrypt(ciphertext, private_key):
    n, d = private_key
    # 解密密文 c，计算明文 m = c^d (mod n)
    message = pow(ciphertext, d, n)
    return message


# 示例用法
p = 61  # 第一个大素数
q = 53  # 第二个大素数

public_key, private_key = generate_keys(p, q)

message = 123  # 要加密的明文

# 加密
ciphertext = encrypt(message, public_key)
print("密文:", ciphertext)

# 解密
decrypted_message = decrypt(ciphertext, private_key)
print("解密后的明文:", decrypted_message)