Writeup for MRCTF2021's crypto

比赛前打了疫苗，困得要命，然后神志不清的写了一堆shi，虽然比赛的时候心态炸了，但高质量的题目该复现还得复现

签到题，定义了一个函数，要求提供使得 $f(x_{list})=0$ 的x-list，回答一次给一位 $flag$ ，但之后的不能和之前的重复

直接系数两两交换，其中一个取相反数，然后为了前后不重复再乘一个系数即可

from Crypto.Util.number import *
from hashlib import sha512
from gmpy2 import *
from pwn import *

table = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
# context(log_level='debug')
r = remote("node.mrctf.fun", "10007")

def passpow():
    rev = r.recvuntil("POW: SHA512(")
    r.recv(1)
    suffix = r.recv(8).decode()
    print(suffix)
    r.recvline()
    def f(x):
        hashresult = hashlib.sha512((suffix+x).encode()).hexdigest()
        if hashresult.startswith("11111"):
            return 1
        else:
            return 0
    prefix = util.iters.mbruteforce(f,table,4,'upto')
    r.sendline(str(prefix))

passpow()
r.recvline()
r.recvuntil("N = ")
data = r.recvline(False).strip().decode()[1:-1]
data = data.split(",")
N = []
for i in data:
    N.append(int(i))
# print(len(N))


flag = ''
for j in range(len(N)-1):
    for i in range(0,len(N),2):
        r.sendline(str(-(j+1)*N[i+1]))
        r.sendline(str((j+1)*N[i]))
    r.recvuntil("your gift:")
    ans = r.recvline(False).strip().decode()
    flag += ans
    print(flag)

print(long_to_bytes(int(flag,2)))

# r.interactive()

nomore

小模数RSA，其中 $e\in (9000,10000)$ ， $p,q\in (1000000, 3000000)$ ，给了 $A=(((y%x)^7)%(x%y))^7+y^5+(y+1)/x$ ，一个条件 $secret=e^3+p^3+q^3=(x+y)%7754486886526049041+210729175671163973$ 和 $x$ 的上界

感觉是为了出题而出题，条件给的好僵硬（

因为这里是 $(y+1)/x$ 整除，所以得到 $y+1=k\cdot x$ （这样出题这里好没有说服力啊= =），所以 $y=k\cdot x-1$ ，带入A中化简一下可得 $A=(x-1)^7+(kx-1)^5+k$ ，显然这个玩意是递增的，而且给了 $x$ 的上界，这里可以用二分法得到 $x$ 的值，随后得到 $secret$ ，接着爆破得到 $e,p,q$

from Crypto.Util.number import *
from gmpy2 import *

c = 693282726315
A = 2235930885430590738951770802593215586722001521194365487273377655750584443688709547709496531484159367793509666612116139038917661713102981488722293426038029073850795986080412124312908732573382156365974821471629333126275130148211145598662897276781331183691743094904957217401055325352877284530068805608962270139656431076370452327497416723045785664344412694060886085511378779487559306015113302658964110922621164879307182468690182325142055960562810349297544601157473985262796723316777380726315782859115449976700612343978057140270903396910431420116573138154719798955123904805279320166126412714788508008881174164656203605409187705643395043643983135944514470267283183175620492198093264226038082725867230101096344723124629565311122528005863046865164876192248803940590219355154176343702897505891392317123983475290611327887699795851456183931854177169939743970260837586185988111368384484356413787993370384262996486824251003884057486063787194241555190688935624792041028246639984544749568167915235629185515957106136630401960066317998226671344793061752525215496195839080165952892472180997564802474095868944184005854120238623750555477937802107959321257495435617363809377093354132077991399603767147974592666019334636208414969819333321639542282741932229892501074615920120228860717401055433206357806353717291748096464569063777964784860874773660469621546777686833078007220613545223169043960754010332944526795605043595879174073360317477199909570141202125189377475655277483919081658123820105695508771837612756891055031293872293977244105248233915807603916034288916844336329883443200123825714530812637709561686224468031953278836676202928878535091578725509651544544672494980806630321114490828976895602038151224026672265830787863940762596976124958000977955469148027648603199590311852993367450800166591526272653355552342455506908317529193196174849749103073968182002498580115241030154502931088245539152380579199202750010140022979979488971008874424439325749039212427088023136971891092490697689178097172878439007028844083681030357488034860471042630885195387680286557424780235116405464735985082715745087677866688657626763753940919966662710093619034074861812080778855241391731006

flag = 0
for k in range(1000):
    upper = 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    lower = 0
    while(upper - lower > 1):
        x = (upper + lower) >> 1
        ans = (x-1)**7 + (k*x-1)**5 + k
        if(ans == A):
            print("Ans Found!")
            print(k,x)
            flag = 1
            break
        elif(ans > A):
            upper = x
        else:
            lower = x
    if(flag):
        break

y = k*x - 1
secret = (x + y) % 7754486886526049041 + 210729175671163973
my_prime = []
for i in range(1000001,min(3000000,iroot(secret,3)[0]),2):
    if(isPrime(i)):
        my_prime.append(i)
print("Prime ready! Found",len(my_prime),"primes.")

flag = 0
for e in range(9001,10001,2):
    for p in my_prime:
        ans = iroot(secret - e**3 - p**3,3)
        if(ans[1]):
            print("Ans Found!")
            q = ans[0]
            print(e,p,q)
            flag = 1
            break
    if(flag):
        break

n = p * q
phi = (p-1) * (q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)

Common_Prime_RSA

paper

如题， $p=2ag+1,q=2bg+1$ ，其中 $g=N^{\beta}$ ，$\beta_1=0.2247,\beta_2=0.3247$

第一部分， $g$ 显然是个比较小的数，直接coppersmith就能拿到，接着来考虑分解 $N$ ，显然 $N=p\cdot q=(2ag+1)(2bg+1)=4abg^2+2g(a+b)+1$ ，则

$$\frac{N-1}{2g}=2gab+(a+b)$$

但由于 $\beta=0.2247<0.5$ ，导致 $g<a,b$ ，我们假设 $\frac{N-1}{2g}=2gu+v$ ，则 $v=a+b-2gc,u=ab+c$ ，那么 $x^{u2g}\equiv x^{ab2g+c2g}\equiv x^{c2g}\pmod{N}$ ，即 ${x^{2g}}^u={x^{2g}}^c$ ，所以我们可以使用 $bsgs$ 算法来得到 $c$ ，因为题目中 $p$ 与 $q$ 较为接近，所以上述的 $a$ 与 $b$ 也比较接近，我们知道 $a\cdot b≈u≈\frac{N}{(2\cdot g1)^2}$ ，根据对勾函数的性质， $x≈y\in (\sqrt{u},\sqrt{2u})$ ，随后即可得到 $c$ 较为精确的答案区间

from Crypto.Util.number import *
from gmpy2 import *

n1 = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49
c1 = 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156
e1 = 3

'''
kbits = int(1024*0.2247)
m0 =  0x436f6d6d6f6e207072696d652052534120697320612076617269616e74206f66205253410000000000000000000000000000000000000000000000000000000000416e642074686520636f6d6d6f6e20666163746f722067206973206c61726765207072696d6520616e6420703d3267612b3120713d3267622b31
PR.<x> = PolynomialRing(Zmod(n))
f = ((m0 + x*2**464)^e1) - c1
f = f.monic()
g1 = f.small_roots(X=2^kbits,beta=1)[0]
print(g1)
'''

g1 = 1328458990599515056771144217738449144496664370133586446617480019409757
v1 = ((n1 - 1) // (2*g1)) % (2*g1)
u1 = ((n1 - 1) // (2*g1)) // (2*g1)
left = (((2 * iroot(n1,2)[0]) // (2*g1)) - v1) // (2*g1)
right = (((3 * iroot(2*n1,2)[0]) // (4*g1)) - v1) // (2*g1)

dic = {}
b = pow(114514,2*g1,n1)
base = pow(b,left,n1)
D = iroot(right - left,2)[0]+1
step = pow(b,D,n1)
for i in range(D):
    dic[base] = i
    base = base * step % n1
print("baby step ready")

base = pow(b,u1,n1)
step = inverse(b,n1)
for i in range(D):
    if(base in dic):
        print("ans found!")
        print(i,dic[base])
        c = left+ i + D * dic[base]
        break
    base = base * step % n1

A = u1 - c
B = v1 + c * 2 * g1
C = iroot(B**2 - 4*A,2)[0]
x = (B+C) // 2
y = B-x
p1 = x*g1*2+1
q1 = y*g1*2+1
assert p1 * q1 == n1
phi1 = (p1-1) * (q1-1)
e1 = 65537
d1 = inverse(e1,phi1)
c1 = 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5
g2 = pow(c1,d1,n1)

n2 = 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd
c2 = 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111
e2 = 65537

A = ((n2 - 1) // (2*g2)) // (2*g2)
B = ((n2 - 1) // (2*g2)) % (2*g2)
C = iroot(B**2 - 4*A,2)[0]
x = (B+C) // 2
y = B-x
p2 = x*g2*2+1
q2 = y*g2*2+1
assert p2 * q2 == n2
phi2 = (p2-1) * (q2-1)
d2 = inverse(e2,phi2)
m = pow(c2,d2,n2)
flag = long_to_bytes(m)
print(flag)

strange_GCD

paper

给出了9组公钥，满足 $N=P\cdot Q_i+R_i$ ，其中 $P$ 是444位、 $Q$ 是444位、 $R$ 是333位，那么显然只要求出 $P$ 、 $Q$ 其中一个即可，因为
$$
\begin{equation}\begin{split}
Q_1\cdot N_2-Q_2\cdot N_1&=Q_0(Q_1P+R_1)-Q_1(Q_0P+R_2) \\
&=Q_0R_1-Q_1R_0 \\
&≈Q_{bits}\cdot P_{bits}
\end{split}\end{equation}
$$
所以我们构建这样的一个格子：
$$
M=
\begin{bmatrix}
2^{P_{bits}} & x_1 & x_2 & \cdots &x_n \\
&-x_0 \\
&&-x_0 \\
&&&\ddots \\
&&&&-x_0
\end{bmatrix}
$$
所以一定存在一个向量 $\vec{v}=(Q_0,Q_2,\cdots,Q_n)$ 满足 $\vec{v}\cdot M=(Q_0·2^P_{bits},Q_0N_1-Q_1N_0,…,Q_0N_n-Q_nN_0)$ ，那么就能得到 $Q_{list}$ ，自然就能分解 $N$ ，正常解密即可

from Crypto.Util.number import *
from gmpy2 import *

N = [8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 9663141503982563384103774905603769762205667685102275298721284964403449121449261483138514307090449027807047697811539118959328065885920230514670112839967221129701708335087378871176539521374006686377418843364889059913595942583737991465545688834167085579154677350865488342245644093471665857007588133415608450554035129609049971856915687905, 7080633525505006454857949889380886258474613936169915325357991912983821798902257837234148311383635716165386646093418183743215120431715933036921480432793786600194625124412063608565640368381660643929081066605712749838630092722581230189543696229548387666046034403406721477818265752443487173947232032487026509033018565048660685068628813900, 6348260112940191945095264085450804431350547836448100928568733296493334845533262312663784701113046746633754397388581143523779371919889446537883618910341310362947454041409541741124231406605654693961025815677260091930522280737378333554694234586235628097018111636491016261274584391201625445101930372416766825601778759258114504767453644116, 5453076441876067965962987075376616480678826248967242473452690159966124023105342358461519279607336831463834252487811766366887983597918775466645199024629945952612311092154451713992362747056489054444283302530500475646346968235522866557033556131387030809018889094871163097069588840212411234716020934787724757538389436231926479459435139729, 8539092301764573132139384894241535432591998166686651428176862041680365196821019488767353225937458669267710968146783359781905669306801237140282934737328995064410005908343087032652676207615356474601039341695241288937409773110450995503958663731870314493254162942656333393836208952363635746218345484752702086447693272390570444229475023063, 6519174659211289290465989985638494640591837577268694359892571134942820094011179335155100770258746122812579164176239810640710311061280175847537113068566174335469669480601670136633042879486860594176408555229541384726863069317134887988109513500264430505092783429319336134768414472691544453196941818593187717904852926051114502346647888426, 6961711680362025924587083752271982856615461409839316941574792747717174299272141804413488210456939607971950020060573061131683587521057101549266612028332060247289306929784809695126285828514889617483817766102136513569391338432827451306976412448973958662677599051104723480081915666230391091496248279567627159875132838397868850500912784991, 5464727156582411007360377345208743900616053705663005668786499961992377236151787056734059201141143278419642045996194426551642956434137382420547801325331080754615348522599387497424727626522195285281557448617564720973185851757117201639221059630112719699600469361046245232476531622290326229811709079901764559526124144866364301870192468062]
C = [800378461059400239726680783421062702546581299113618553895453491207714321944554499622887232532612118204284779120928524046451494597619154079853122057618867592408424421335915888671560524092660578952242621890439766919785431411789789232309134048322721650012432166587969915464252995890054635969469155870141839815222805619769926841873928532, 8685468246369062574820183134847029157229023858170863526469628501966638181721681547114662091162797572149161013458000532984909663639626346493828947027439012131912176125653717020650233650230608573276523862941298063827867869000918623143520066067119099918633173584693454642685133071154989133688921507896223776765538029556643440655490373815, 4635611296372235589362291842711945807825964919968727011796279830725567747087132786100965922682161492876463568645940638975728831156672106717718242995621775763972524561170035488180440169190421072680121175269363490806991700969253196228364471655905426168859215651384013432550900570720981720919343406680667172355882395426739478340888619526, 742099161415136628218807400531862454374875770332166710320711769923774839345990297388615457974047093967700994503615622499139058644697776431451063778211507061619987487339659448529973693084099004007650792690143707738139278995489030445825999666762580518420739517354868021396496747289677543653758101688499365196709600349831855157276274803, 4273006447766599851029197343910625305964779588947130545729882009677080459892767902139074897266046998378948193319329776150920821074305998905666368175737032487336505440974393061632257356697260043478850055918798196360043557336723402834256592984312957607731622934368169520289756716653736422872196593367101920308166527352079412344590114695, 1337615323422531101514598853478737615483725265103339849469231329210692205474781484172946466402355800190175297435923447189337380569240535257395618353403524999296122247241720498058900285176383928871155893061316083476812641934026019749574784965397208046520128690081232283708190247657782663414534596381371506499151016470118707739609022847, 6153442337491399463730666360630451953223069596225489087488144486112604050064388945200405772892415725900338512969888610774357818442533883395713661512978158729825590405567077341407532331228257558692149544940358814513930330757334104407683768945074261746314376336567331685071086776886141587264981001140113933152084084711732651014186070962, 3604640305526232611907645024550062043296875756707299105733076926046725900367109300556792007038226350415916164581084668832286944703572581980333135146219609212135443758296278947833224676930513359604019639508959092586550129343133801670578311053639151186604019506764426302411065588655525183584977810609190948096510237056027272167828516985, 2085633143403792178757363870459578017278494765962824809917819295576034993395441252397370078671500834434293581806342828037037877739374959864038090394888141183851040814572501861997433316552606005140700519616064369570511427453278726929921212633252656552135711332324923683242632912449218888750151556281762432994484741408165895663710356342]

M = [[1<<334]+N[1:]]
for i in range(len(N)-1):
    M.append([0]*(i+1)+[-N[0]]+[0]*(len(N)-i-2))
# print(M)

'''
M = [
    [34996011596528190789960035633881941845650710894291398982812329702559247987190014771576210832368861184, 9663141503982563384103774905603769762205667685102275298721284964403449121449261483138514307090449027807047697811539118959328065885920230514670112839967221129701708335087378871176539521374006686377418843364889059913595942583737991465545688834167085579154677350865488342245644093471665857007588133415608450554035129609049971856915687905, 7080633525505006454857949889380886258474613936169915325357991912983821798902257837234148311383635716165386646093418183743215120431715933036921480432793786600194625124412063608565640368381660643929081066605712749838630092722581230189543696229548387666046034403406721477818265752443487173947232032487026509033018565048660685068628813900, 6348260112940191945095264085450804431350547836448100928568733296493334845533262312663784701113046746633754397388581143523779371919889446537883618910341310362947454041409541741124231406605654693961025815677260091930522280737378333554694234586235628097018111636491016261274584391201625445101930372416766825601778759258114504767453644116, 5453076441876067965962987075376616480678826248967242473452690159966124023105342358461519279607336831463834252487811766366887983597918775466645199024629945952612311092154451713992362747056489054444283302530500475646346968235522866557033556131387030809018889094871163097069588840212411234716020934787724757538389436231926479459435139729, 8539092301764573132139384894241535432591998166686651428176862041680365196821019488767353225937458669267710968146783359781905669306801237140282934737328995064410005908343087032652676207615356474601039341695241288937409773110450995503958663731870314493254162942656333393836208952363635746218345484752702086447693272390570444229475023063, 6519174659211289290465989985638494640591837577268694359892571134942820094011179335155100770258746122812579164176239810640710311061280175847537113068566174335469669480601670136633042879486860594176408555229541384726863069317134887988109513500264430505092783429319336134768414472691544453196941818593187717904852926051114502346647888426, 6961711680362025924587083752271982856615461409839316941574792747717174299272141804413488210456939607971950020060573061131683587521057101549266612028332060247289306929784809695126285828514889617483817766102136513569391338432827451306976412448973958662677599051104723480081915666230391091496248279567627159875132838397868850500912784991, 5464727156582411007360377345208743900616053705663005668786499961992377236151787056734059201141143278419642045996194426551642956434137382420547801325331080754615348522599387497424727626522195285281557448617564720973185851757117201639221059630112719699600469361046245232476531622290326229811709079901764559526124144866364301870192468062], 
    [0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, -8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216]
]
M = Matrix(ZZ,M)
ans = M.LLL()[0]
'''

ans = (4599191779324727072633164871296325902208765537352604303273175255453504312615500983406477011435819405305852059674048438016100668090246407849496908743817335622801573073136122188609246369046057261291320848819844418920893230598376364951805862565686868625621955071425273509220849374947161975251582041718784, 104098035638581595369723778375711537486830709046687306114704921816239533823901066113680320504395210089789340199402154288158599251547931748565815387310900885326892681968536308019715590493310968628489043723240348362149053110811668282038727688689374505928586075094912392544924601844136642390813222425809, 1102834391862716869946827309486981604079530638763397950737361315055931768373793498250981455412829162997772327814660070857951309312894092377859437366989526531813223828179941289064128320123411973263239142716310770401174174815638810202859450962632995611863799694649198457635953086959463939627719575381012, 753994729336183961852361196205654448289304004519434287316796470222521627865083763102251102951626213588497716067551706990220346381353586508856365765536744873026409087910505560761761024675350156647185336440841519838638415417607956807382719719007131540587566462617043290548957627028678429439567176392108, -71708524916293121808333775279085691365967960919759775147913431698619192878017855212957980666806523648996086462040461850162074426038300683815953081712090679643498963889027587516137252350693864785830427057530016147319149926968346502476418390469709928547235995568090970863872980806983047965126211827423, -1031944069356990593465028628753183012193322903943969718261363844383250576817774501764794204795605186147444430878687291921605373814843580367545369212301939780213941922732623750390324618190490307261983930269957183493345355165692496865409582827167136484989492550271511982793001065621702409883049993239817, -1960547215826715829528682564527292643865866291188443591530567078511330848396016229325567425830200701694380104625201031396661972809519249893882531604307311435727272867042265335921514343841646164420771255718802644103398765492144311189111408831887333483581772033575516358581006829893858562536866631199694, -1402335387560657499009395932180425308829816453818907356038567333645529829409747360872073366794556975860774421104509218449157997408918101385420918273310166387609041772539330599075043569860214109051067579537008367501834723009929827486300772678346407596106869832512579102180928086682172345775047825906065, 6492859743402427013224957526773612476031280993044690607784160057686880229209831538939045987606076773313125546427811186808795218860181360435151657439459135171731642225975056613348164819235317913083153227881911185574679170305638348499347070097938480392885289493284095645409615468925393679398090634630)
Q = []
Q.append(ans[0]>>333)
for i in range(1,len(ans)):
    Q.append(-(ans[i]-Q[0]*N[i])//N[0])

P = N[0] // Q[0]

flag = b''
e = 0x1337
for i in range(len(C)):
    flag += long_to_bytes(pow(C[i],inverse(e,(P-1)*(Q[i]-1)),(P*Q[i])))[-5:]
    print(flag)

strange_CRT

paper

二元的coppersmith，首先有 $e\cdot dq=1\pmod{q-1}$ ，即 $e\cdot dq-k\cdot(q-1)-1=0$ ，即 $e\cdot dq+k-1=k\cdot q$ ，因为 $dq$ 只有40位，所以 $dq$ 和 $k$ 都比较小，我们设 $f(x,y)=ex+y$ ，一定存在一个根 $(dq,k-1)$ ，我们使用 $x-shifted$ 方法构造方程组，

$$
B_P(4)=
\begin{bmatrix}
N^2X^3 \\
eNX^3 & -NX^2Y \\
e^2X^3 & -2eX^2Y & XY^2 \\
e^3X^3 & -3e^2X^2Y & 3eXY^2 & -Y^3
\end{bmatrix}
$$
随后找到根 $(dq,k-1)$ ，即可分解 $N$ 了

from Crypto.Util.number import *
from gmpy2 import *

n = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097
m = 114514

'''
beta = 0.34
delta = 0.02
amplification = 2048
X = int(pow(n,delta) * (5/2))
Y = int(pow(n,(beta+delta)) * (5/2))
M = []
M.append([n*n*X*X*X,0,0,0])
M.append([e*n*X*X*X,-n*X*X*Y,0,0])
M.append([e*e*X*X*X,-2*e*X*X*Y,X*Y*Y,0])
M.append([e*e*e*X*X*X,-3*e*e*X*X*Y,3*e*X*Y*Y,-Y*Y*Y])
M = Matrix(M)
A = M.LLL()[0]
p = []
p.append(A[0]//(X**3))
p.append(A[1]//(X^2*Y))
p.append(A[2]//(X*Y^2))
p.append(A[3]//(Y^3))
R.<x,y> = ZZ[]
f = x**3*p[0] + x**2*y*p[1] + x*y**2*p[2] + y**3*p[3]
f.factor()

(-1) * (144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717*x + 636751972323*y) * (22360612316620576265962363998986325309879295954423979763235633587165509772463851121464450246995467551277856854280313242339679743870302000793124620978436719868879086932947083203923324893801655101558128409321266258664105566594644972878236716985754511292295147466953475408456421662883470405599945529089115443773171753380747253399676451061853675376543473713650224588466737340581901289431253330538396922770846601154595827366651699780258116005162252520473266535156064285895366446187694020122502168871153774940666139567620938830703125690675687869510298889906793*x^2 + 267647155976378743685890593144685469708715653490308593667201283907775452606689307120817149553958120371639890271685148603015657241238590179583153694790949220206995033824074078242830758458739742301161015368049847345525661233185551949155450470189603595130241004416639482696460716023144193868351704190287775402159037407591606868297555272291534131071*x*y - 1177035497855139471300150596073079881470359423070664560562543221821780066461677777154411563960425838478371703085673516387654415520557027*y^2)
'''

k = 144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717 + 1
dq = 636751972323
q = (e * dq + k - 1) // k
p = n // q
assert n == p * q
phi = (p-1) * (q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)

Writeup for MRCTF2021's crypto

friendly_sign-in

nomore

Common_Prime_RSA

strange_GCD

strange_CRT