已知d与φ(n)能否计算e？验证反向推导的正确性

在RSA密码体系中，e和d的核心关系是满足 e*d ≡ 1 mod φ(n)，这本质是模逆元求解问题，所以已知d和φ(n)是可以计算出e的，具体细节如下：

• 计算逻辑和由e求d完全对称：只要d和φ(n)互质（这是RSA的必要前提——因为d是e的逆元，所以e与φ(n)互质，推导可得d也必然与φ(n)互质），就能通过扩展欧几里得算法求出e的一个有效解。
• e的解不唯一：所有满足条件的e都可以表示为 e = e₀ + k*φ(n)（k为任意整数），实际应用中会选择1 < e < φ(n)范围内的最小正整数解（比如常用的65537就是这类标准小指数）。
• 举个直观例子：若φ(n)=20，d=3，求解3e≡1 mod20，可得最小正整数解e=7（3×7=21≡1 mod20），而7+20=27、7+40=47等也都是合法解，但实际会优先选用7这类小值。

内容的提问来源于stack exchange，提问作者Yuna