[青少年CTF]crypto-easyrsa2

0x01 题目

附件📎：attachment.rar

-> rsa.py:

from Crypto.Util.number import *
import libnum
import os
flag=b"qsnctf{xxx}"
p = getPrime(1024)
q = getPrime(1024)
n = p*q
g = n+1
m = bytes_to_long(flag+os.urandom(80))
assert m < n
c=(pow(g,p,n*n)*pow(m,n,n*n))%(n*n)
print("c="+str(c))
print("n="+str(n))
print("hint="+str(pow(m,n,n*n)))
'''
c=66678676807819999233055752233012645216556361263550510641458138760242990544877153301370374578704777931232476338305467217987404530347735695779503178036421182225797342139667414033819549735400631841417480498297529049064697503015021854485122852781023739931626312344890150603219610361949715257299757876396121457922011100238200914884518816724570032960792393893693987273449132986383967737661332184245494679249768271219448311009053358014235996071771678629824838455550656184325379070682831449751581704335301991422979670164462996326062181802199457920952884644486857703150690485372324099739728933019077124979301630915161677329073838717624281912453064292050645599587914370539926494875189042257226901095428367557104603484361484689870742875976031491361356906065563995295161550794376980645647256180808032818970477137116813399005614665378240469106976942172004532499389709072629630182831176447909810194979470492503457826783215378012716067168240899950280919812526665449548435470763153364775037634608636124823419727610771754135029066786995448023344714433006189682986009642250012827276182380723006889497445191429315726319860246957758947479783856107618504793372727551573516430116044526115831580866712303531100607806086948676318637464591882028026021699894
n=9708240910053370327647790439860059395697433308093756873635851265001056001241814559377845391403869007592553831023273503888032698234970709669543334556062588508047041830328271866526501975789023731681405580485272835157565865576389655812958754783970253647199760653920473402313707835141798861179370897475214985631140985268832048996867332230888259485268845102594348768694808862929202235718025035375364452457226504332282661544721948483958933549896194659715546983203083340635396852388654958534328589664265477197863480536895984751045258639005062576375047487801340353952725037332762579311892566309845803551721154611198850694889
hint=15613233182045834454837091537129559572463357409242991059275865756502677501292019990524617846342883945144948214709829276773559580662192051939293618469760595488262754840024570932399632204943961192737927090713331302892637093802186982539183237812760391107406086815359176310279873801797511686704386149527196425669143630969466244510968774100698711337342428981824350069495546649268307502745849374929178078452353412848200254646407747588799587978115886917795519466200738109159358526401995002919562778567619465054519031416581299479880372007116699496037030278711691766488713289936605675886647939901724010509966626186564475727816841671677455616145094861581303177900290005836663230730119258137618704988268602601305882212617818941058581025292572301756455201550159396592023107862007183096426767089373770530183377980160792911531980889750702258884476031108148900413001574721663391170784476398364342546870723694831011684688417779531314862780502223430368818401117993567944287408577002359641420517197280983488244636652951398460440637437535272791206065981999378985299071681061261648137126049153466892870715040486561538144454764854960492244624559313669917618145125499556864411590579608146139952070851086592303928435316413295184569669393829843926156275495
'''

0x02 解题

这个题目是公约数分解n的思路，不过推导起来还是有难度的

已知：
$$
\begin{array}{l}
h \equiv m^n \pmod {n^2} \\
c \equiv g^p \cdot m^n \pmod {n^2}
\end{array}
$$
将$g = (n+1), h$代进去。2式变为:
$$
c \equiv (n+1)^p \cdot h \pmod {n^2}
$$
两边同时乘上$h$模$n^2$的逆元$h^{-1}$:
$$
c\cdot h^{-1} \equiv (n+1)^p \pmod {n^2}
$$
需要用到二项式定理。
$$
(a+b)^n = \sum_{r=0}^nC_n^ra^{n-r}b^r = C_n^0a^n + C_n^1a^{n-1}b +\cdots + C_n^ra^{n-r}b^r + \cdots +C_n^nb^n
$$
使用二项式定理分解$(n+1)^p$
$$
(n+1)^p = n^p + C_p^1n^{p-1} + C_p^2n^{p-2} + \cdots + C_p^{p-1}n + 1
$$
其中二项式的系数
$$
C_p^r = \frac{p!}{r!(p-r)!} = \frac{p\cdot (p-1)!}{r!(p-r)!}
$$
来重点看一下中间的项的系数，除了第一项和最后一项，其余的分子都是有一个$p$,

已知$p$是素数，$p $与小于$p$的数都互质。那么，所有分子上的p都无法被约分。

又知道$C_p^r$ 是整数，那么可以将$C_p^r = k_rp$
$$
\begin{array}{l}
(n+1)^p &= 1 + n^p + k_1pn^{p-1} + k_2pn^{p-2} + \cdots + k_{p-1}pn \\
&=1 + pq\cdot n^{p-1} + k_1pn^{p-1} + k_2pn^{p-2} + \cdots + k_{p-1}pn \\
&=1 + kpn
\end{array}
$$
将结果代入：
$$
c\cdot h^{-1} = 1 + k_1pn + k_2n^2
$$
将1移到左边
$$
c\cdot h^{-1} - 1 = k_1pn + k_2pqn = pn(k_1 + k2_q) = kpn
$$
最终得到
$$
\frac{c\cdot h^{-1}}{n} = kp
$$
至此，终于找到了$kp$ 而等式左边都是已知，可以通过公约数分解$n$

另外还有一个点，加密指数是 $n $, 模数是$n^2 \varphi(n^2) = p(p-1)q(q-1)=n(p-1)(q-1)$

加密指数与$\varphi(n^2)$不互素，不能直接解，需要再变形一下。
$$
h = m^n + kn^2
$$
两边同时模n
$$
h \equiv m^n \pmod n
$$
最终的解题代码如下：

#sage
from Crypto.Util.number import *
import os
import gmpy2
c=66678676807819999233055752233012645216556361263550510641458138760242990544877153301370374578704777931232476338305467217987404530347735695779503178036421182225797342139667414033819549735400631841417480498297529049064697503015021854485122852781023739931626312344890150603219610361949715257299757876396121457922011100238200914884518816724570032960792393893693987273449132986383967737661332184245494679249768271219448311009053358014235996071771678629824838455550656184325379070682831449751581704335301991422979670164462996326062181802199457920952884644486857703150690485372324099739728933019077124979301630915161677329073838717624281912453064292050645599587914370539926494875189042257226901095428367557104603484361484689870742875976031491361356906065563995295161550794376980645647256180808032818970477137116813399005614665378240469106976942172004532499389709072629630182831176447909810194979470492503457826783215378012716067168240899950280919812526665449548435470763153364775037634608636124823419727610771754135029066786995448023344714433006189682986009642250012827276182380723006889497445191429315726319860246957758947479783856107618504793372727551573516430116044526115831580866712303531100607806086948676318637464591882028026021699894
n=9708240910053370327647790439860059395697433308093756873635851265001056001241814559377845391403869007592553831023273503888032698234970709669543334556062588508047041830328271866526501975789023731681405580485272835157565865576389655812958754783970253647199760653920473402313707835141798861179370897475214985631140985268832048996867332230888259485268845102594348768694808862929202235718025035375364452457226504332282661544721948483958933549896194659715546983203083340635396852388654958534328589664265477197863480536895984751045258639005062576375047487801340353952725037332762579311892566309845803551721154611198850694889
hint=15613233182045834454837091537129559572463357409242991059275865756502677501292019990524617846342883945144948214709829276773559580662192051939293618469760595488262754840024570932399632204943961192737927090713331302892637093802186982539183237812760391107406086815359176310279873801797511686704386149527196425669143630969466244510968774100698711337342428981824350069495546649268307502745849374929178078452353412848200254646407747588799587978115886917795519466200738109159358526401995002919562778567619465054519031416581299479880372007116699496037030278711691766488713289936605675886647939901724010509966626186564475727816841671677455616145094861581303177900290005836663230730119258137618704988268602601305882212617818941058581025292572301756455201550159396592023107862007183096426767089373770530183377980160792911531980889750702258884476031108148900413001574721663391170784476398364342546870723694831011684688417779531314862780502223430368818401117993567944287408577002359641420517197280983488244636652951398460440637437535272791206065981999378985299071681061261648137126049153466892870715040486561538144454764854960492244624559313669917618145125499556864411590579608146139952070851086592303928435316413295184569669393829843926156275495
#c == pow(g,p,n*n)*pow(m,n,n*n)%(n*n)
#pow(g,p,n*n)==pow(n+1,m,n*n)==pow(m*n+1,n*n)
hint1 = gmpy2.invert(hint,n**2)
p = gmpy2.gcd((c*hint1-1)//n, n)
q = n//p
phi_n = (p-1)*(q-1)
d = gmpy2.invert(n,phi_n)
m = pow(hint%n,d,n)
long_to_bytes(m)
'''b"qsnctf{41e1fef9-4039-6930-449a-b53a8b2c27d9}\xcaS\xde\xf3\xd4\x03\xb1\x1d\x7f\xe7\x01k\x0b\xb9R\xc2,\xc8\xf0\xef@\x99.\xce\xfd\x82\xc5\x8b\x0e\xfc\xf2,\xbe\xd4\xecr\x94YO\x16\xce\x8c\x7f`K1\x8ee\xedaR2\x8e\xcd\x1b\xe5v\x9f>\x9b\xd5I\x99\x87\x9c\xdc<\x96\x9c\x19Q2'\x1f\xf3\t\x9d4#\xf7"'''