RSA加密中公钥e的选取规则与实用验证方法咨询

架构老林

2026-10-1

RSA公钥e合规性验证实用方法

首先澄清你查到的规则的表述误差，先明确e的正确取值核心要求：

取值范围为 1 < e < φ(n)，你查到的第一条规则的大小关系写反了，其中的𝑑(𝑒) 𝑑(𝜑𝑛)属于输入错误，实际要求为gcd(e, φ(n)) = 1（e和φ(n)的最大公约数为1）
第二条规则的本质和互质要求等价：e的所有质因数都不在φ(n)的质因数集合内，就是两者互质的另一种表述

实用验证方法

1. 小数值手工校验法

适合φ(n)数值不大的测试场景：

第一步：对φ(n)做质因数分解，提取所有不重复的质因子，例如φ(n)=20的质因子是2、5
第二步：校验待选e的范围是否落在(1, φ(n))的开区间内，不满足直接判定不合规
第三步：校验e能不能被φ(n)的任意一个质因子整除，只要能被其中一个整除就不合规，全部不能整除则合规

示例：φ(n)=20，e=7，范围符合要求，且7不能被2或5整除，合规；e=10能被2和5整除，不合规。

2. 工程开发代码校验法

适合生产环境大整数RSA场景，效率远高于质因数分解：
直接用欧几里得算法（辗转相除法）计算e和φ(n)的最大公约数，判断是否等于1即可，以下是Python实现示例：

import math

def check_e_valid(e: int, phi_n: int) -> bool:
    # 先校验取值范围
    if e <= 1 or e >= phi_n:
        return False
    # 校验是否互质
    return math.gcd(e, phi_n) == 1

该方法可以直接支持RSA常用的1024位、2048位及以上的大整数校验，性能无压力。