1.ProjectEuler Problem182 欧拉计划 182 题

运行代码及结果：
import math


def calculate_rsa_e_sum():
    p = 1009
    q = 3643
    phi = (p - 1) * (q - 1)
    p_minus_1 = p - 1
    q_minus_1 = q - 1

    min_unconcealed = float('inf')
    total_sum = 0
    e_count = 0

    # 优化：仅遍历奇数e（phi为偶数，gcd(e,phi)=1必为奇数）
    for e in range(3, phi, 2):
        if math.gcd(e, phi) != 1:
            continue
        k = e - 1
        g1 = math.gcd(k, p_minus_1)
        g2 = math.gcd(k, q_minus_1)
        current = (1 + g1) * (1 + g2)

        if current < min_unconcealed:
            min_unconcealed = current
            total_sum = e
            e_count = 1
        elif current == min_unconcealed:
            total_sum += e
            e_count += 1

    return min_unconcealed, e_count, total_sum


# 执行计算
min_num, count, sum_e = calculate_rsa_e_sum()
print(f"最小未加密消息数: {min_num}")
print(f"满足条件的e的个数: {count}")
print(f"所有满足条件的e的和: {sum_e}")

题目背景

RSA 加密，公钥(e,N)，N=pq为双素数乘积；统计无效密钥 (e) 的总数量：明文m满足gcd(m,N)=1，加密后me≡m(modN)，即加密等于明文，密钥失效。

分步解题思路

1. 已知参数：p,q为固定素数，N=p×q，φ=(p−1)(q−1)，e∈[1,φ)且gcd(e,φ)=1（合法公钥指数）。
2. 数论推导： me≡m(modp) 且 me≡m(modq) 同时成立时密钥失效； 模p下满足条件的m数目=gcd(e−1,p−1)+1； 模q下满足条件的m数目=gcd(e−1,q−1)+1； 单e对应的无效明文总数：cnt(e)=g1​×g2​，g1​=gcd(e−1,p−1)+1, g2​=gcd(e−1,q−1)+1。
3. 代码实现步骤： ① 预定义题目给定、数值； ② 遍历1<e<φ，筛选满足gcd(e,φ)=1的合法e； ③ 对每个合法e，计算g1​,g2​，累加全部cnt(e)得到最终答案。

核心考点

费马小定理、RSA 公钥指数安全条件、欧几里得求最大公约数。

2、CryptoPals Set5 Challenge39 手动实现 RSA 加解密

运行代码及结果：

def egcd(a, b):
    """扩展欧几里得算法: ax + by = gcd(a,b)，返回(g, x, y)"""
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def invmod(a, mod):
    """求a在模mod下的乘法逆元，不存在则抛异常"""
    g, x, _ = egcd(a, mod)
    if g != 1:
        raise Exception(f'模逆元不存在！gcd({a},{mod})={g}≠1，请更换p/q或e')
    else:
        return x % mod


class RSA:
    def __init__(self, p, q, e=3):
        self.p = p
        self.q = q
        self.n = p * q
        self.phi = (p - 1) * (q - 1)
        self.e = e

        # RSA核心条件前置检查
        if egcd(self.e, self.phi)[0] != 1:
            raise Exception(f'公钥e={e}与φ={self.phi}不互质！\n请更换p/q（推荐）或更换e')

        self.d = invmod(self.e, self.phi)
        self.pub_key = (self.e, self.n)  # 公钥 (e,n)
        self.pri_key = (self.d, self.n)  # 私钥 (d,n)
        print(f"当前RSA最大支持明文数字: {self.n - 1}")

    def encrypt_num(self, m):
        """数字明文加密 m -> c"""
        if m >= self.n or m < 0:
            raise ValueError(f"明文数字{m}超出范围！必须满足 0 ≤ m < {self.n}")
        e, n = self.pub_key
        return pow(m, e, n)

    def decrypt_num(self, c):
        """密文解密 c -> m"""
        d, n = self.pri_key
        return pow(c, d, n)

    def encrypt_str(self, plaintext: str):
        """字符串加密：str→十六进制数字→RSA加密"""
        hex_str = plaintext.encode('utf-8').hex()
        m = int(hex_str, 16)
        return self.encrypt_num(m)

    def decrypt_str(self, cipher_num):
        """数字密文解密：数字→十六进制→原字符串"""
        m = self.decrypt_num(cipher_num)
        hex_str = hex(m)[2:]  # 去掉0x前缀
        # 修复：奇数长度十六进制补前导0
        if len(hex_str) % 2 != 0:
            hex_str = '0' + hex_str
        return bytes.fromhex(hex_str).decode('utf-8')


# ========== 测试1：小素数测试（p=59,q=71,e=3） ==========
if __name__ == "__main__":
    # 验证题目给出的invmod示例
    print("题目invmod示例验证：invmod(17,3120) =", invmod(17, 3120))
    print("-" * 60)

    print("===== 小素数RSA测试(p=59,q=71,e=3) =====")
    p_small = 59
    q_small = 71
    rsa_small = RSA(p_small, q_small, e=3)
    print(f"公钥(e,n): {rsa_small.pub_key}")
    print(f"私钥(d,n): {rsa_small.pri_key}")

    # 数字测试（正常）
    m_test = 42
    c = rsa_small.encrypt_num(m_test)
    m_dec = rsa_small.decrypt_num(c)
    print(f"数字测试：明文={m_test}, 密文={c}, 解密还原={m_dec}")

    # 短字符串测试（长度≤2个字符，确保数字<4189）
    short_text = "Hi"
    c_short = rsa_small.encrypt_str(short_text)
    dec_short = rsa_small.decrypt_str(c_short)
    print(f"短字符串测试：明文={short_text}, 密文={c_short}, 解密还原={dec_short}\n")

    # ========== 测试2：大素数测试（支持长字符串） ==========
    print("===== 大素数RSA测试(p=1009,q=3643,e=3) =====")
    p_big = 1009
    q_big = 3643
    rsa_big = RSA(p_big, q_big, e=3)
    print(f"公钥(e,n): {rsa_big.pub_key}")
    print(f"私钥(d,n): {rsa_big.pri_key}")

    # 长字符串测试（"Hello RSA!" 完全没问题）
    long_text = "Hello RSA!"
    c_long = rsa_big.encrypt_str(long_text)
    dec_long = rsa_big.decrypt_str(c_long)
    print(f"长字符串测试：明文={long_text}")
    print(f"加密后密文: {c_long}")
    print(f"解密还原: {dec_long}")

RSA 基础公式

1. 密钥生成 ① 随机选取两个大素数、； ② N=p⋅q，欧拉函数φ(N)=(p−1)(q−1)； ③ 选公钥e：1<e<φ, gcd(e,φ)=1（常用e=3/65537）； ④ 私钥d：e⋅d≡1(modφ(N))，d是e模φ乘法逆元。
2. 加密：C=me(modN)，m为明文数值；
3. 解密：m=Cd(modN)。

分步实现思路

1. 素数生成：手写简易素性测试（试除法 / 米勒拉宾），生成两个不等大素数p,q；
2. 密钥构造： ① 计算N=(p∗q)、φ=(p−1)∗(q−1)； ② 选定e=3，用扩展欧几里得算法求e模φ的逆元d；
3. 加密流程：明文字符串→转十进制大整数m→pow(m,e,N)得到密文C；
4. 解密流程：密文C→pow(C,d,N)还原整数m→转回原始字符串；

关键细节

• 明文不能大于模数N，超长明文需要分段处理；
• Python 内置pow(a,b,mod)自带快速模幂，直接实现大数幂取模。