说明：本文中拦截者充当了超级nb的拦截角色，任何你通过互联网发送的信息都能被他看见
从欧几里得到RSA加密
这是第一次手打blog，emm有什么做的不好的地方后面会改进的
因为这个RSA加密，勾起了我的兴趣啊这个加密怎么这么好玩，虽然感觉有点难度啊但是我觉得不错啊不错。crypto是有趣的（虽然我也不知道以后会不会从事这个密码专项吧但是加解密的时候就感觉好好玩）
开胃菜：RSA 加密解密全过程（30 秒版）
先不抠任何原理，看一遍全程发生了什么。三个出场人物：接收者（收信的）、发送者（寄信的）、拦截者（互联网上啥都能截到）。
第 1 步：接收者造一对钥匙（自己在家完成，全程不联网）
选两个质数 p=3、q=11，算出模数 n = 33（一会儿公开）；
再算出私钥 d = 7（死死藏住，一秒都不出门）。
第 2 步：接收者把「锁」广播出去
公钥 = (n=33, e=3)，谁想要都有。拦截者截到也无所谓——锁开不了锁。
第 3 步：发送者用锁加密
明文 m=4 → 密文 c = 4³ mod 33 = 31，把 31 发出去。
第 4 步：接收者用私钥解密
31⁷ mod 33 = 4 → 明文回来了。
换成公式就是
先造 p、q → n = p × q
算出欧拉函数 → Φ = (p - 1)(q - 1)
再找一对数 (e, d) 满足: e、d 都与 Φ 互质, 且 e×d mod Φ = 1
(说人话: 找一对 ed, 让 ed 除以 Φ 余 1)
然后我们找到了e和d之后选择其中一把作为公钥发送出去，另一个则作为私钥保存在本地。这里我们一般选择e当作公钥ps:一般来说我们发到公网的公钥为了使得发送者加密方便，我们会选择小一点的那个数作为其中公钥部分发送出去，常见公钥为65537
接下来发送者会接收到公钥组合(n, e)
然后就会使用以下算法进行加密:我们假定m为明文 ， c是密文
$m^e \bmod n = c$
然后发送者将密文发送给接受者
接受者收到密文之后，就会拿手上的私钥组合 (n, d) 进行解密：
$c^d \bmod n = m$
这样就算是完成了一次拦截者无法解密的加密过程了
全程在网络上飞行的只有锁和密文，两样都被拦截者拿到也拆不出明文——因为解密需要的 7 ——私钥d，从头到尾只存在接收者自己的电脑里。
至于 d=7 是怎么算出来的、为什么 31⁷ 恰好变回 4——这就是后面 1.05、1.06 要讲的故事。先记住结果，我们再回头再说。
0：什么是加密
简单来说就是你只想要对方知道这条信息，但是这条消息有概率会被别人截获，如果没有加密，截获者就可以直接看到你的消息，我们称之为 明文 ，你为了不让别人知道你的信息，你把你的消息的每个字母都往右挪三位：
hello --> khoor 解密：khoor往左挪三位 --> hello
这就是加密
0.05：密钥
像上面的向右挪三位，就是密钥。
密钥：顾名思义，就是一把加密解密密文的钥匙（可能不是同一把）
0.1：对称加密
像上面这样的加密（凯撒加密），密文解密的过程就是明文加密过程的逆过程，也就是说，一旦你知道了这个密文是怎么被加密的，你就能轻而易举的把密文给解密了。因为加密密钥和解密密钥是同一把钥匙，那如果这样的话，截获者如果广泛涉猎各种对称密码学，就或许能找到这把密钥，很多加密数据都会变得不安全，为了解决这一问题，我们引入了：
0.2：非对称加密
所谓的非对称加密，就是加密用一把密钥，解密用另一把密钥。我们知道，如果要把加密信息传到那边去，对方想要解密，那么就必定需要一把解密密钥，但是如果我们连同解密密钥一起上传过去，那么拦截者就同样会收到，我们不可能为了传一把钥匙而造一把新的钥匙——密钥分发难题。解密密钥从来不需要传递——因为它根本不是对方「知道」的，而是对方「自己造」的
也就是说：接收者本身就有一套自己保存在本地的解密系统，不需要经过互联网。
那我们上传的是什么？——是锁（公钥），截获者就算截获到了公钥这个锁，也没有解密的钥匙（解密密钥），这也是为什么非对称加密的保密性会更好。
而此外，私钥并不是在发送者手上的，相反，它本身就在接收者手上。这样的话，流程就是：
私钥 公钥(锁) --->
接受者-----------------公 网------------发送者
私钥解密 <---公钥(锁)加密后的密文
这样的话，我们就满足了私钥保存在本地。
1：什么是RSA加密
简单来说，RSA加密是非对称加密的一种，本质上是基于欧几里得、扩展欧几里得和裴蜀定理的一个集大成者的加密算法。
但是在这之前，我们一边看这个加密一边了解知识
第一步：造锁
选两个质数 p = 3, q = 11
相乘作为模数 n = p × q = 33 （锁的一部分）
利用欧拉函数 φ = (p-1)(q-1) = 20 (见1.05)
找一个公开指数(和φ互质就行, 不必是质数) e = 3 （锁的另一部分）
为什么 e 要和 φ 互质：不互质 d 根本不存在（乘法逆元不存在）
通过寻找 d s.t. 3 × d ≡ 1 (mod20) --> d = 7
为什么d是这么找出来的？见1.1欧几里得
这个d就是私钥
然后我们发出去的是 (n = 33 , e = 3) 这个是锁
自己的 d p q φ 则是私钥要藏好
然后我们把锁运到发送者
第二步：加密
明文 m = 4
密文 c = $m^e \bmod n = 4^3 \bmod 33 = 64 \bmod 33 = 31$
其实这里的加密逻辑可能有误区，我们要了解 1.1欧几里得算法 ，当这个e变得超级大了之后，我们不可能做到平方完了再mod，我们站在了巨人的肩膀上，知道了其实我们可以边乘边mod，也就是：
$4^1 \bmod 33 = 4$
$4×4 \bmod 33 = 16$
$16×4 \bmod 33 = 31$
(如果接下来还有的话就是31×4mod33)
第三步：解密
m = $c^d \bmod n = 31^7 \bmod 33 = 4$
(如果这个次方过大了可以用快速幂)快速幂：指的是把c^d中的d变成二进制格式巴拉巴拉我还不是很懂那么下次补充，但是也不用知道因为在python中pow就是用快速幂的
pow(base, exp, mod)
解出来就是明文了
1.05：欧拉函数
Q:为什么要使用欧拉函数？
A:φ 决定了 e 的逆元 d——也就是 e·d ≡ 1 (mod φ) 里的那个 d
欧拉函数 φ (n) = 从 [ 1 , n ] 之间与 n 互质的数的个数互质就是最大公约数 = 1
e.g. φ (8) = 4 (1,3,5,7)
如何计算 φ (n)？
当 n ∈ 质数 ： 那么对于任意的 [ 1 , n ] 有且只有 n 不是
因此 φ(n) = n - 1
如果 n = p×q (pq均为质数)
那么 φ(n) = (p - 1)×(q - 1)
e.g 15 = 3 × 5
和15互质的数有 1,2,4,7,8,11,13,14一共8个
φ(15) = (3 - 1)×(5 - 1) = 8
1.06：欧拉定理——解密为什么必然成立
警告，以下内容十分有九分的看不懂，以后再慢慢了解吧这个看的头都大了
结论，整条证明就一行：
$$c^d = (m^e)^d = m^{ed} = m^{1+k\varphi} = m \cdot (m^\varphi)^k = m \cdot 1 = m$$
即：若 gcd(a, n) = 1，则 $a^{\varphi(n)} \equiv 1 \pmod n$。（如果 a 和 n 互质，那么 a 的 φ(n) 次方除以 n 的余数一定是1）
1.06.1：费马小定理
(欧拉定理的质数特例）：p 质数时 $a^{p-1} \equiv 1 \pmod p$。（p 是质数的时候 φ(p) = p−1 ，因此才会有 $a^{p-1} \equiv 1 \pmod p$ ）
看起来吓人，其实每一步只有一条规则。分开来看，抽象式和具体数字（p=3, q=11 → n=33, φ=20, e=3, d=7, m=4, c=31）并排：
第 0 步：ed = 1 + k·φ 是 d 的出生证明
d 的定义就是 $e \cdot d \equiv 1 \pmod{\varphi}$。而「≡ 1 (mod φ)」翻译成人话：ed 减 1 是 φ 的倍数。给这个倍数起名叫 k：
$$e \cdot d = 1 + k\varphi$$
本例：$3 \times 7 = 21 = 1 + 1 \times 20$，即 k = 1。（k 具体是几不重要，后面会看到为什么）
第 1 步：c^d = m^{ed}——代入，无魔法
加密做的就是 $c = m^e$，所以算 $c^d$ 时把 c 换回真身。幂的幂 = 指数相乘：
$$(m^e)^d = m^{e \cdot d}$$
本例：$31^7 ≡ (4^3)^7 ≡ 4^{21}$⚠️ 注意这里的等号其实是同余号 ≡：严格说 31 ≠ 64（4³ 算出来是 64），31 只是 64 除以 33 的余数，两者相差正好一个 33——在 mod 33 的世界里它们是同一个居民。而 0.4 节那条「积的余数 = 余数的积」保证了：余数的幂 ≡ 幂的余数，所以把 64 换成 31 去乘方，结果一点不变。
第 2 步：拆指数——同底数幂相乘，指数相加
$$m^{1+k\varphi} = m^1 \times m^{k\varphi} = m \cdot m^{k\varphi}$$
本例：$4^{21} = 4 \times 4^{20}$
第 3 步：幂的幂——指数相乘
$$m^{k\varphi} = (m^\varphi)^k$$
本例：$4^{20} = (4^5)^4$
第 4 步：欧拉定理（全链条唯一的新知识）
$$m^\varphi \equiv 1 \pmod{n} \qquad (\gcd(m,n)=1 \text{ 时})$$
直觉：与 n 互质的那 φ 个数，在乘法 mod n 下组成一个封闭小团体——任意两个成员相乘还在团体里。让 m 反复乘进去，等于在团体里绕圈，转 φ 圈必然回到起点 1。
本例实测：$4^5 = 1024 = 31 \times 33 + 1 \equiv 1 \pmod{33}$，所以 $4^{20} = (4^5)^4 \equiv 1$。
于是：$(m^\varphi)^k \equiv 1^k = 1$
——k 是几根本无所谓，1 的任何次方都是 1。这就是第 0 步说「k 不重要」的原因。
第 5 步：收尾
$$m \times (m^\varphi)^k \equiv m \times 1 = m \quad \blacksquare$$
全链对照表
| 步骤 | 规则 | 抽象 | 具体 |
| 0 | d 的定义 | $ed = 1 + k\varphi$ | $21 = 1 + 1 \times 20$ |
| 1 | 代入 + 幂的幂 | $c^d = m^{ed}$ | $31^7 = 4^{21}$ |
| 2 | 指数相加 | $m^{ed} = m \cdot m^{k\varphi}$ | $4^{21} = 4 \times 4^{20}$ |
| 3 | 指数相乘 | $m^{k\varphi} = (m^\varphi)^k$ | $4^{20} = (4^5)^4$ |
| 4 | 欧拉定理 | $(m^\varphi)^k \equiv 1$ | $4^5 \equiv 1 \Rightarrow (4^5)^4 = 1$ |
| 5 | 收尾 | $m \times 1 = m$ | $4$ ✓ |
老师给的笔记补充
若 $(a, N) = 1$，欧拉定理给 $a^{\varphi(N)} \equiv 1 \pmod N$。
任取整数 k，两边同取 k 次方：$a^{k\varphi(N)} \equiv 1 \pmod N$。
两边再同乘 a：
$$a^{k\varphi(N)+1} \equiv a \pmod N \quad \cdots (* )$$
然后解密一步到位——设有 e、d 满足 $e \cdot d \equiv 1 \pmod{\varphi(N)}$，即 $ed = k'\varphi(N) + 1$。把 (*) 里的 k 换成 k′：
$$a^{ed} \equiv a \pmod N$$
令 $c = a^e \bmod N$（加密），则：
$$c^d \equiv_N (a^e \bmod N)^d \equiv_N a \quad \blacksquare$$
1.10：欧几里得
核心算法 $$\gcd(a, b) = \gcd(b, \, a \bmod b)$$ 就一句话，a和b的最大公约数＝b和a模b的最大公约数 因此在体量超级大的数面前，我们可以利用递归来快速找到最大公约数，代码如下：def gcd(a, b):
while b != 0: #其实可以直接写 while b:
a, b = b, a % b
return a
1.11：扩展欧几里得
裴蜀定理：gcd(a, b) 不是孤立数字——它一定可以由 a 和 b 凑出来：存在整数 x、y 使 a·x + b·y = gcd(a, b)。
推论（最重要）：gcd(a, b) = 1 ⟺ 存在 x、y 使 a·x + b·y = 1（互质和能凑出 1是同一件事）。
扩展欧几里得：公式化求系数——下坡就是 1.10 那个队列滚动，唯一升级是回程时做代入合并（子问题的解代回上一层，重组出本层系数）：
如果 13x + 5y = 1 , 想要找到 x 和 y
(13, 5) → (5, 3) → (3, 2) → (2, 1) → (1, 0) 停, gcd = 1
接下来做倒推
第①步: 1 = 3 − 2
2 碍事 → 查 2 的配方: 2 = 5 − 3, 代入
1 = 3 − (5 − 3) = 2×3 − 5 配方: {3:2, 5:−1}
第②步: 3 碍事 → 查 3 的配方: 3 = 13 − 2×5, 代入
1 = 2×(13 − 2×5) − 5
= 2×13 − 4×5 − 5
= 2×13 − 5×5 配方: {13:2, 5:−5}
第③步: 只剩 13 和 5 了 → 完工!
def egcd(a, b):
if b == 0:
return a, 1, 0 # 底: a·1 + 0·0 = a
g, x, y = egcd(b, a % b) # 子问题: b·x + (a%b)·y = g
return g, y, x - (a//b)*y # 回程: 代入 a%b = a-(a//b)·b, 合并同类项
用 (797, 521) 跑一遍：机器吐出 a = −168, b = 257，即 797×(−168) + 521×257 = 1。
（验证：521×257 = 133897，797×168 = 133896，差 = 1 ✓）
它们在本篇的三处岗位：
- 造锁时找 d——一般情况
d = egcd(e, φ) 的 x（小数字可以目测，大数字全靠它） - 1.06 第 0 步
ed = 1 + k·φ能成立，前提这样的 d 存在——由裴蜀推论担保 - easyrsa3 共模攻击的主角：egcd(797, 521) 凑出指数 1 → m = c₁ᵃ·c₂ᵇ
裴蜀保证解存在，egcd 把解算出来；普通欧几里得 管 公约数，扩展版 管 系数。
第二节：常见的RSA破译方式
1：给出 e p q c 求 m
题目：CTFshow babyrsa
e = 65537
p = 104046835712664064779194734974271185635538927889880611929931939711001301561682270177931622974642789920918902563361293345434055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873283332371986860194245739423508566783663380619142431820861051179
q = 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120354497987945911021170842457552182880133642711307227072133812253341129830416158450499258216967879857581565380890788395068130033931180395926482431150295880926480086317733457392573931410220501
c = 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589873830973301898523644744951545345404578466176725030290421649344936952480254902939417215148205735730754808467351639943474816280980230447097444682489223054499524197909719857300597157406075069204315022703894466226179507627070835428226086509767746759353822302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194
那我们如何利用python对其进行解密呢？
pow(a, b, c) # 正常用法: a 的 b 次方, 再 mod c → $a^b mod c$
pow(a, -1, c) # 指数为 -1 时触发特殊语义: 求 a 的乘法逆元
n = p * q #先计算出n
phi = (p - 1) * (q - 1) #欧拉函数求Φ
d = pow(e, -1, phi) #找一个d s.t. d*e ≡ 1 (modΦ)
#现在我们得到了私钥 d ，接下来就是对其进行解密
m = pow(c, d, n) #明文 = c^d modn
print('明文:', m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()) #转成字符串
flag{b4by_R5A}
2.给出 e , n , c 求 m
题目源自于easyrsa1
为什么只给出了e,n,c就能求m呢？求phi不应该要先求出pq吗？那肯定是题目暗藏玄机了
e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009
我们注意到这一次给到的n比较小，我们完全可以通过factordb.com(网站)或者sympy.factorint(n)
from sympy import factorint # 只需要 import 这一个
fact = factorint(n) # 返回一个字典: {质数: 出现次数}
print(fact) # easyrsa1 会输出 {某大质数: 1, 另一大质数: 1}
p, q = list(fact.keys()) # 把两个质数取出来, 接四件套
flag{fact0r_sma11_N}
3.共质数攻击，给出公共的e和n1,n2,c1,c2求m
题目源自于easyrsa2
e = 65537
n1 = 23686563925537577753047229040754282953352221724154495390687358877775380147605152455537988563490716943872517593212858326146811511103311865753018329109314623702207073882884251372553225986112006827111351501044972239272200616871716325265416115038890805114829315111950319183189591283821793237999044427887934536835813526748759612963103377803089900662509399569819785571492828112437312659229879806168758843603248823629821851053775458651933952183988482163950039248487270453888288427540305542824179951734412044985364866532124803746008139763081886781361488304666575456680411806505094963425401175510416864929601220556158569443747
c1 = 1627484142237897613944607828268981193911417408064824540711945192035649088104133038147400224070588410335190662682231189997580084680424209495303078061205122848904648319219646588720994019249279863462981015329483724747823991513714172478886306703290044871781158393304147301058706003793357846922086994952763485999282741595204008663847963539422096343391464527068599046946279309037212859931303335507455146001390326550668531665493245293839009832468668390820282664984066399051403227990068032226382222173478078505888238749583237980643698405005689247922901342204142833875409505180847943212126302482358445768662608278731750064815
e = 65537
n2 = 22257605320525584078180889073523223973924192984353847137164605186956629675938929585386392327672065524338176402496414014083816446508860530887742583338880317478862512306633061601510404960095143941320847160562050524072860211772522478494742213643890027443992183362678970426046765630946644339093149139143388752794932806956589884503569175226850419271095336798456238899009883100793515744579945854481430194879360765346236418019384644095257242811629393164402498261066077339304875212250897918420427814000142751282805980632089867108525335488018940091698609890995252413007073725850396076272027183422297684667565712022199054289711
c2 = 2742600695441836559469553702831098375948641915409106976157840377978123912007398753623461112659796209918866985480471911393362797753624479537646802510420415039461832118018849030580675249817576926858363541683135777239322002741820145944286109172066259843766755795255913189902403644721138554935991439893850589677849639263080528599197595705927535430942463184891689410078059090474682694886420022230657661157993875931600932763824618773420077273617106297660195179922018875399174346863404710420166497017196424586116535915712965147141775026549870636328195690774259990189286665844641289108474834973710730426105047318959307995062
不难发现这里的n和c都超级大但是e是一样的(也说明不了什么)但是如果这道题可以解出来，就是说这里的漏洞就在于pq肯定有一个同时是n1和n2的子质数。也就是
n1 = p × q1
n2 = p × q2
也就是说n1和n2的最大公约数＞1，而这个最大公约数也就是这道题的公共质数。
单独看每个 n 都是 2048 位坚不可摧，但两个模数之间有血缘关系——gcd 这个求公共因子的免费工具把它们一起葬送。
from math import gcd
e = int(input('e:'))
n1 = int(input('n1:'))
n2 = int(input('n2:'))
c1 = int(input('c1:'))
c2 = int(input('c2:'))
g1 = gcd(n1,n2) #g1就是n1和n2的最大公约数
q1 = n1 // g1
phi1 = (g1 - 1)*(q1 - 1)
d1 = pow(e , -1 , phi1)
m1 = pow(c1, d1, n1)
print(m1)
print(m1.to_bytes((m1.bit_length() + 7) // 8, 'big').decode())
当然以上的代码只是解出了m1，但是没有解出m2（其实解m2的格式也是一样的只不过我在写代码的时候运气好发现只要解出m1就直接得到答案了）
flag{m0_bv_hv_sv}
4.共模攻击
出自easyrsa3
Common Modulus Attack 是RSA中经典的攻击方式。如果同一份明文被同一个模数、两个不同的公钥 e 加密了两次，那么即使不知道私钥 d 也可以直接还原出明文。
e1 = 797
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c1 = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930
e2 = 521
c2 = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849
出题人的失误：同一把锁 n 配两把不同 e、锁同一份 m——参数冗余直接泄密。
原理（小数字演示，全程不需要欧拉定理）
同一个明文 m、同一把锁 n，被两把不同的"拧法"各锁了一次：
c1 = m^e1 (mod n)
c2 = m^e2 (mod n)
前提：e1 和 e2 互质（真题的 797 和 521 就是一对）。
核心只有一行代数——幂相乘，指数相加：
c1^a × c2^b = m^(e1·a) × m^(e2·b) = m^(e1·a + e2·b)
注意 (e1·a)、(e2·b) 以及总和 e1·a + e2·b 都在指数上，别看错
想让它变回 m，只要凑指数 = 1：找 a、b 使 e1·a + e2·b = 1——这就是裴蜀定理和扩展欧几里得的岗位（裴蜀保证必然有解，egcd 告诉我们怎么求解）。
小数字实战（每个数都能手算）
加密: c1 = 4³ mod 33 = 31 ← 同一个 4 被拧了 3 圈
c2 = 4⁷ mod 33 = 16 ← 又被拧了 7 圈
凑指数: egcd(3,7) = (1, −2, 1) → 3×(−2) + 7×1 = 1, 所以 a=−2, b=1
攻击: c1^(−2) × c2^1 = 31^(−2) × 16 ≡ 4 ✓ 原明文
指数账本：$(4^3)^{-2} \times (4^7)^1 = 4^{-6+7} = 4^1 = 4$
c1 的 −2 次方 = 把「拧 3 圈」倒拧 2 遍；c2 的 1 次方 = 正拧 7 圈。一倒一正，净效果 = 正好 1 圈 = 原地。 这就是共模攻击的全部直觉：两个密文是同一个明文被拧了不同圈数的状态，egcd 帮你算出「倒几圈 + 正几圈 = 回到原位」。
负圈圈（负指数）怎么走？——倒着拧 = 乘它的逆元。Python 的 pow(c1, -2, 33) 自动帮你做这一步（内部就是 egcd），所以脚本一行搞定。
「可是攻击者根本不知道 m 是谁、也不知道拧了几圈啊？」
答：不需要知道。
- 圈数（e1, e2）根本不是秘密——印在锁上，是公开的
- 攻击者操作的是状态（密文），不是账本：c1^a × c2^b 的指数含义自动是「净旋转 e1a+e2b = 1 圈」——不管被拧的是什么东西，净转 1 圈 = 回到原始状态
- 实证：三个不同的未知明文，同一套配方全部还原（攻击代码里根本没出现 m）：
(31, 16) → 4 (13, 28) → 7 (16, 31) → 25
这就是 1.06 视角澄清的共模版：m^(e1a+e2b) = m 对所有 m 同时成立——攻击者不用替 m 说话，公式替它说。
真题脚本
e1 = 797
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c1 = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930
e2 = 521
c2 = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849
def egcd(a, b):
if b == 0: return a, 1, 0
g, x, y = egcd(b, a % b)
return g, y, x - (a//b)*y
g, a, b = egcd(e1, e2) # → (1, -168, 257)
m = pow(c1, a, n) * pow(c2, b, n) % n
print(m.to_bytes((m.bit_length() + 7) // 8, 'big').decode())
flag{sh4r3_N} —— flag 又把考点写在脸上了：两把公钥共享同一个 N。
收尾对照：三道题，攻击原料全是公开的
| 题 | 公开原料里的缺陷 | 巧合类型 |
| easyrsa1 | n 本身太小 | 构造缺陷——造锁偷工减料 |
| easyrsa2 | 两个 n 有公共质因子 | 生成缺陷——随机数复用 |
| easyrsa3 | 同一 n 配两个 e 锁同一 m | 使用缺陷——协议设计失误 |
第三节：复盘 / 教训
我只想说这个RSA真是有点难度哦我又是问AI又是找资料又是找老师，虽然这只是CTFshow里面小小的一块内容，但是我觉得还是来看看吧看看吧，学习RSA的过程其实也挺有趣的（除了在学的时候头晕晕的）。而且这个RSA其实我才做了四道题目啊这后面有一亿道题目做完真的要累死了，接下来我可能会休息会做点web或者misc吧啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊这什么神人密码啊，为什么要我学数论啊啊啊啊啊啊啊啊啊啊啊啊啊啊(bushi)，十分有九分的有意思啊喂，希望我对crypto的热爱可以就此开始吧！！！！！！！
- 学到：RSA 四种入门攻击 = 四种「使用缺陷」（参数直接给 / n 太小 / 共享质数 / 参数冗余）
- 教训：概念要分清——欧拉函数是计数器、欧拉定理是引擎、egcd 是计算器，混着叫会晕
特别鸣谢：萦梦Soraaaaaaaaaaa（虽然也没有问什么问题qwq）、韩扬老师（虽然只是聊了几句话哈哈哈）、王圣宝老师（提供了关键的欧拉函数的公式）、胡斌老师（推荐我去找在RSA这个方面很厉害的王老师，当然老师本人也非常厉害！）、GLM5.3flash,deepseekv4flash,以及超强的claudeAgent（三位老师也是一直在指导我呢）
——Cola_CaO
2026.9.13