巅峰极客-Final-2022/Crypto/gcd writeup
tags: ctf,crypto,writeup
巅峰极客-Final-2022/Crypto/gcd writeup
我不理解，为什么别人做那么快
1. challenge
下载附件得到test.py
from Crypto.Util.number import *
import libnum
import flag
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q*p
e = 65537
x = inverse(n,(p-1)*(q-1))
c = pow(m,e,n)
print(n,x,c)
'''
n = 1715097516831775561161353747739509313962850384763754284193603064705990003183954750857689649540587082555847904377918426763475079170697690469267290454724999354302036981034615698694153403754870938739225201770934147845874793740053505575413463153429315475539039712818850905666950096326806695688446947957198050957270336443016980023115464136303403780696015358461369838964806435293267645492940773964907954737849962270208167145137818071024789445448292917016422004351584109968952746852305729861258178402122017513103311904147173869605944992973485253275501741635308107788593258463591060922145241960065862813218690280146883588390356662245698217956617720339878472430817614915509896516775918109916920083183701011823993137753987826242193055167215287839864164955881557719443664876504155709359476375455266912247205663953373944852046907623883953483708248467223346798885142046228485310724692353541792975390854356153906879056788972704718688261213
x = 13693034247131001247611357013365838905472128629161269384100755984286945944986882779020879733934334461215591081830359749241927901759168319107452036275703768755532293338513836146556306490425526394420440685291299327486258632666082657664827474947846307949205548526817689180357262646108048851554962291154624349603853599623877095789135051759890435127891210971940795915429197420232561510826760487552089621705187244655827668509013761027910519038664267576214742561936826964572261315984043602119812357324667105678247267841445497640859880436819217418374184256023378843611198818733281625017307272013394628328908242726204785568269
c = 1207106262178445359018459948589897274651891185968586806427714234447059397099330669443037189913958678506147447588787686432870791586266645067569198511010947847769438531195366288233395081813524859121328300315116211130908169351354477893647936383056584771268247471788727296968981371535384241445434057942795625350351461517179136190258136244456887118978348223420158887403238429201791427682781494296473806409015961385580794909106746874670027369932286414096790928966277930586468864071103687837936910843559150279603968747213779555572156135983177121194768041838538456267670795923361920648635769732101772513407467158904982779342496410211785417729464008786654808126619152228029357660596380038858050797654917902576424059433048290426186067840363899227577713800670585547473870112798624948349947633855963137174688403113603549470708467306886181387445601800049442519922530086418265660642841544022198981442640591637598035257382429976435264690303
'''
2. 分析
一种RSA的变种，$N=p^2q$，马上去搜相关论文，经过一段时间尝试，没有找到可用的论文。鉴于题目未给出相关参数的任何限定条件，这题应该不是根据论文改编的。
于是，考虑怎么使用提供的关键条件x = inverse(n,(p-1)*(q-1))，设n0=n/p，即$xn\equiv 1 mod(\phi(n_0))$。我想要把$ed\equiv 1 mod \phi(n)$和上式结合起来，尝试求出d，但尝试了很久也没有结果。
去倒杯水，理一下思路。
因为本题的已知条件相较于常规RSA，仅多出关键条件x = inverse(n,(p-1)*(q-1))，可以想到应该是要据此分解n。
至此，逐渐有了正确的方向。
将$xn\equiv 1 mod(\phi(n_0))$当作一个典型的RSA模型，已知RSA的公钥’n',私钥’x'，可以分解n0吗？
搜索找到相关资料，知道可以根据私钥分解n：
ctfwiki中给出的两个工具似乎不能直接使用，因为我们不知道模$n_0$的值。看来需要自己理解并修改算法，这里简单复述一下根据d分解n的证明：
$$ \begin{align} & de\equiv 1 \mod n \newline & \Rightarrow 令k=de-1, 可以知道k是\phi(n)的倍数 \newline & 因为\phi(n)是偶数，存在r,t: \newline & k=2^tr, (r是奇数，t>=1) \newline & \newline & g^{k}\equiv1\mod n, ( 1\lt g\lt n, gcd(g,n)=1 ) \newline & 则g^{k/2}是上式模n上的平方根，有4组解： \newline & g^{k/2}\equiv \pm1 或\pm x\mod n, (x\equiv 1\mod p且x\equiv -1\mod q) \newline & \newline & 通过\pm x, 可以对n进行分解： \newline & p=gcd(x-1, n) \newline & \end{align} $$
该证明出自 Twenty Years of Attacks on the RSA Cryptosystem
但本题的$nx\equiv 1\mod n_0$中，模为$n_0$, 而我们只知道n，那么本题中可以使用n作为模吗？即$g^k\equiv1\mod n$成立吗？不成立的，证明如下：
$$ \begin{align} & g^k=g^{\phi(n_0)k_0}\equiv 1 \mod pq \newline \Rightarrow & g^{\phi(n_0)}\equiv1\mod pq \newline \Rightarrow & g^{\phi(n_0)}=k_1pq+1 \newline \Rightarrow & g^k=({g^{\phi(n_0)}})^{k_0}=(k_1pq+1)^{k_0} \newline \Rightarrow & 当k_0=1时, g^k=k_1pq+1\mod p^2 \newline & 当k_0\ge2时，g^k=(k_1pq+1)^{k_0}\equiv k_2pq+1\mod p^2 \newline \Rightarrow & g^k-1\equiv k_2pq\mod p^2 \newline & 又 g^k-1\equiv0\mod q \newline \Rightarrow & g^k-1\equiv k_2pq\mod p^2q \newline & 故 g^k\equiv 1 \mod n 不成立，除非k_2\equiv0\mod p \end{align} $$
尽管我们无法套用已知的算法，但在这个过程中，可以发现：
$$ \begin{align} & gcd(g^k-1, p^2q) \newline =& gcd(k_2pq, p^2q) \newline =& pq \end{align} $$
要求gcd(k2,p)=1，但这通常是满足的
3. solver
e = 65537
n = 1715097516831775561161353747739509313962850384763754284193603064705990003183954750857689649540587082555847904377918426763475079170697690469267290454724999354302036981034615698694153403754870938739225201770934147845874793740053505575413463153429315475539039712818850905666950096326806695688446947957198050957270336443016980023115464136303403780696015358461369838964806435293267645492940773964907954737849962270208167145137818071024789445448292917016422004351584109968952746852305729861258178402122017513103311904147173869605944992973485253275501741635308107788593258463591060922145241960065862813218690280146883588390356662245698217956617720339878472430817614915509896516775918109916920083183701011823993137753987826242193055167215287839864164955881557719443664876504155709359476375455266912247205663953373944852046907623883953483708248467223346798885142046228485310724692353541792975390854356153906879056788972704718688261213
x = 13693034247131001247611357013365838905472128629161269384100755984286945944986882779020879733934334461215591081830359749241927901759168319107452036275703768755532293338513836146556306490425526394420440685291299327486258632666082657664827474947846307949205548526817689180357262646108048851554962291154624349603853599623877095789135051759890435127891210971940795915429197420232561510826760487552089621705187244655827668509013761027910519038664267576214742561936826964572261315984043602119812357324667105678247267841445497640859880436819217418374184256023378843611198818733281625017307272013394628328908242726204785568269
c = 1207106262178445359018459948589897274651891185968586806427714234447059397099330669443037189913958678506147447588787686432870791586266645067569198511010947847769438531195366288233395081813524859121328300315116211130908169351354477893647936383056584771268247471788727296968981371535384241445434057942795625350351461517179136190258136244456887118978348223420158887403238429201791427682781494296473806409015961385580794909106746874670027369932286414096790928966277930586468864071103687837936910843559150279603968747213779555572156135983177121194768041838538456267670795923361920648635769732101772513407467158904982779342496410211785417729464008786654808126619152228029357660596380038858050797654917902576424059433048290426186067840363899227577713800670585547473870112798624948349947633855963137174688403113603549470708467306886181387445601800049442519922530086418265660642841544022198981442640591637598035257382429976435264690303
'''
factor n with e*d
actually not be applicable for this challenge
n: module
k: e*d-1
'''
def factor_n_with_ed(n, k):
for g in range(2,n-1):
t = k
while True:
if t % 2 == 0:
x = pow(g, t, n)
y = gcd(x-1, n)
if x>1 and y>1:
return y
else:
break
t = t // 2
k=n*x-1
# factor = Integer(factor_n_with_ed(n, k))
pq = Integer(gcd(pow(2,k,n)-1, n))
assert n % pq == 0
p = n//pq
q = pq//p
assert is_prime(p) and n%p == 0
assert is_prime(q) and n%q == 0
assert p*p*q == n
phi=p*(p-1)*(q-1)
d = inverse_mod(e, phi)
assert (d*e)%phi==1
m=pow(c, d, n)
from Crypto.Util.number import *
flag=long_to_bytes(int(m))
# flag{bs903sk_fbnw34f8_cwn3efh}
flag
4. 总结
题目本身是比较简单的，如果单纯给出$n,e,d$，我肯定能快速解决。但是将e,d形式转变为$n=p^2q，xn\equiv 1\mod \phi(n_0)$，我就被迷惑了。
总结来说，还是密码学题目做得少，手生。