打都打了，做都做了，写都写了，就发一下呗

比赛不怎么样，题目嘛，有两道还是可以的（虽然有一道是原题- -）

Crypto1:ddd·

模板题，直接上Wiener就可以秒了

n = 114566998957451783636756389276471274690612644037126335470456866443567982817002189902938330449132444558501556339080521014838959058380963759366933946623103869574657553262938223064086322963492884606713973124514306815995276393344755433548846003574038937940253826360659447735554684257197194046341849089254659225497
e = 35489734227210930185586918984451799765619374486784192218215354633053183935617953856556709715097294481614236703293033675674496036691242573294182072757562322996800390363453350727372642264982749305833933966045097125311467413670410802534093354414115267442785896373815076066721029449240889291057288090241124904705
c = 60503455347700500866544596012233537789678841391057706123172519773588895502922586197178148979273264437566411675346207472455036341903878112074983509557751805365618433536738111588239911292341288514123006967218545943520736254346030465088445419278775539026233686559207400401082452551955780877227801939191694370380

fra = (e/n).continued_fraction()
for i in range(len(fra)):
    k = fra.numerator(i)
    d = fra.denominator(i)

    if k != 0 and (e*d-1) % k == 0:
      try:
        phi = (e*d-1) // k
        p_plus_q = n + 1 - phi
        p_min_q = (p_plus_q^2 - 4*n)^(1/2)
        p = (p_plus_q + p_min_q) // 2
        q = n // p
        assert p*q == n

        phi = (p-1) * (q-1)
        d = e.inverse_mod(phi)
        break
      except:
        continue

print('p = %s' % p)
print('q = %s' % q)
print('d = %s' % d)

m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:])
print(flag)

Crypto2:QAQTAT·

题目：QAQTAT的附件.zip

纯原题，数据都不带改的，不过这文章也比较迷，就贴了几个代码还缺东西的~~（怕不是跟N1学的）~~，所以还是自己撸了一个

先看题目，大概就是有

$\begin{aligned} Q &\in \mathbb{F}_{p^2}^{3 \times 3} \\ T &= Q A Q \\ S &= T A T \\ \end{aligned}$

和

$\begin{aligned} r_1 &\overset{\$}{\leftarrow} [0, p-1] &&G = Q^{r_1} \\ s &\overset{\$}{\leftarrow} [0, p-1] &&D = G^s \end{aligned}$

和

$\begin{aligned} F &= D E D \\ K &= D S D = Q F Q \end{aligned}$

知道 $A$ 、 $T$ 、 $S$ 、 $G$ 和 $F$ ，求 $K$

本来是想着能用 $A$ 、 $S$ 和 $T$ 从矩阵运算的角度恢复 $Q$ ，但观察了一下发现其实 $T$ 是没用的，也就是只知道 $A$ 和 $QAQ$ ，这样是求不出 $Q$ 的

于是问题就转为使用 $G = Q^{r_1}$ 求DLP解 $Q$

Part.1 用G求Q（NG）·

测试了一下， $G$ 的阶大概是（反正就是按之前说的凑几个分圆多项式来试）

$p^4 - 1 = (p^2+1) (p+1) (p-1)$

这个阶有点大，而且不是Smooth的，看起来不能直接解DLP

再来看 $r_1$ ， $r_1$ 的取值是 $[0, p-1]$ ，并不是矩阵群阶的 $p^4 - 1$ ，所以可以考虑在某个子群中去解

题目中的 $p$ 是256 bits，按以前的经验的话，Cado应该可以解 $O(p)$ 规模的DLP

但问题是Cado只能解整数的DLP，所以我的想法是先把一般线性群映射到一个整数的子域中，然后再用Cado去解

首先我们都知道，给定一个矩阵 $M_1$ 和矩阵 $M_2$ ，有

$det(M_1) = det(M_1) det(M_2)$

那么根据题目条件就可以得到

$\begin{aligned} det(T) &= det(Q A Q) = det(A) det(Q)^2 \\ \end{aligned}$

调整一下就是

$\begin{aligned} (det(T) det(A)^{-1})^{1/2} = det(Q) \text{ (in } \mathbb{F}_{p^2} \text{)} \\ \end{aligned}$

进一步推广可以得到，给定一个矩阵 $M$ 和整数 $n$ ，有

$det(M^n) = det(M)^n$

代入题目也就有

$\begin{aligned} det(G) = det(Q^{r_1}) = det(Q)^{r_1} \text{ (in } \mathbb{F}_{p^2} \text{)} \\ \end{aligned}$

此时得到的 $det(Q)$ 和 $det(Q)^{r_1}$ 都在 $\mathbb{F}_{p^2}$ 中，不太好调Cado

所以接下来需要继续转化到整数域中

而总所周知， $\mathbb{F}_{p^2}$ 的乘法阶是

$p^2 - 1 = (p+1) (p-1)$

所以其中会存在一个阶为 $p-1$ 的子域，而这个子域就是 $\mathbb{F}_p$

所以下一步就是计算

$\begin{aligned} det(Q)^{p+1} &\text{ (in } \mathbb{F}_{p} \text{)} \\ (det(Q)^{r_1})^{p+1} &\text{ (in } \mathbb{F}_{p} \text{)} \end{aligned}$

然后把这两个东西扔进Cado，解出 $r_1$

参考代码

from Crypto.Util.number import *
from hashlib import sha256

p =  72887242108660141996862343556330151015969690949835567252527194788428065480383
Fp2.<i> = GF(p^2, modulus=x^2+1)
M = MatrixSpace(Fp2, 3, 3)

pk = 
F =  
ct =  

A, T, S, G = pk
A, T, S, G = [M(_) for _ in (A, T, S, G)]

q = (T.det() / A.det()).sqrt()
qr = G.det()
print('q : %s' % q)
print('qr: %s' % qr)
print()

assert q^(p^2-1) == 1
q2 = q^(p+1)
qr2 = qr^(p+1)
print('q2 : %s' % q2)
print('qr2: %s' % qr2)
print()

assert q2^(p-1) == 1
ell = factor(p-1)[-1][0]
print('python ./cado-nfs.py --dlp --ell=%s %s' % (ell, p))
print('./cado-nfs.py /tmp/cado.uk1u7t16/p75.parameters_snapshot.0 target=%s,%s' % (q2, qr2))
print()

'''
Info:root: logbase = 304696016520446393317161686962074865294826214137917338567738734523574665662
Info:root: target = 69539078488567937608985101051387436762138475277560049981799274660043570663398
Info:root: log(target) = 1999310381690393087630108846033111172391824881803166118494733 mod ell
Info:root: target = 7338238082910510652369676077633982917766537629883448309816702584486633778449
Info:root: log(target) = 1512679493712481161447294550172458486619271913625485125969046 mod ell
1999310381690393087630108846033111172391824881803166118494733,1512679493712481161447294550172458486619271913625485125969046
'''

lq, lqr = 1999310381690393087630108846033111172391824881803166118494733, 1512679493712481161447294550172458486619271913625485125969046

r1 = lqr * lq.inverse_mod(ell) % ell
cofac = (p-1) // ell
assert pow(q2, r1 * cofac, p) == pow(qr2, cofac, p)

r2 = discrete_log(Zmod(p)(pow(qr2, ell, p)), Zmod(p)(pow(q2, ell, p)))
r = crt([r1, r2], [ell, cofac])
assert pow(q2, r, p) == qr2
assert q^r == qr

接着会发现解出来的这个r1并不满足q^r == qr

原因是我上面拿的 $p - 1$ 并不是 $det(Q)^{p+1}$ 的准确阶

令 $det(Q)^{p+1}$ 的准确阶为 $\varphi$ 、上面解出来的是 $r_1'$ 的话，准确的 $r_1$ 就应该是

$(r_q' \pmod \varphi) + k \varphi,\ (0 \le k \le (p - 1) / \varphi)$

中的一个，所以最后求 $\varphi$ 然后枚举即可

参考代码

fpm1 = [_[0] for _ in list(factor(p-1))]
fs = []
for f in fpm1:
  if q2^((p-1) // f) == 1:
    fs += [f]
p2 = (p-1) // product(fs)
r = r % p2
for i in range(product(fs)):
  if q^r == qr:
    break
  r = r + p2
print('r = %s' % r)
assert q^r == qr

就满足了

接下来我的想法是，可以像解RSA那样，对 $G = Q^{r_1}$ 解密

但实际发现不太行，其中一个原因是需要解一般线性群的AMM，有点复杂

Part.2 用D求s·

目前已经可以解DLP了，那不妨换个思路

首先从

$F = D E D$

中可以得到

$\begin{aligned} det(F) &= det(D E D) = det(E) det(A)^2 \\ \end{aligned}$

其中 $E$ 已知，就是

$\begin{aligned} (det(F) det(E)^{-1})^{1/2} = det(D) = det(G)^s \text{ (in } \mathbb{F}_{p^2} \text{)} \\ \end{aligned}$

按照Part.1的方法就可以求到 $s$

所以就可以计算 $D = G^s$ ，然后

$k = D S D$

解密即可

参考代码

from Crypto.Util.number import *
from hashlib import sha256

def enc(pt, G, A, T, S, p):
    s = randint(0,p-1)
    D = G^s
    E = A*T*A
    F = D*E*D
    K = list(D*S*D)
    key = sum(K[0])+sum(K[1])+sum(K[2])
    mask = int(sha256(str(key).encode()).hexdigest(),16)
    ct = pt ^^ mask
    return ct, F


def dec(ct, Q, F, p):
    K = Q*F*Q
    key = sum(K[0])+sum(K[1])+sum(K[2])
    mask = int(sha256(str(key).encode()).hexdigest(),16)
    pt = ct ^^ mask
    return pt

p =  72887242108660141996862343556330151015969690949835567252527194788428065480383
Fp2.<i> = GF(p^2, modulus=x^2+1)
M = MatrixSpace(Fp2, 3, 3)

pk =  ([(17721183402259872020800275954210023274983052570120081248291897425608931477093*i + 32398110280895896734010284949974832063887503132353681078977206899204202173789, 54531634495057046991515273558305428867102201405617856305008554208336946545276*i + 53559176432820530464958340934397135653021175198597495321065224929188410347695, 27719945502856754481236098196014205483081586087367078493933408080194499938927*i + 1450628736387393873166171805424299538505476789523674611289973478290718453200), (57242423786686483363839647362581564383925732392730073374546590355998555747077*i + 573726326354574516128249317235875704460857319673337707555095009277545125755, 33631043256657770245013631632455702904903259491780484310654749784948198388976*i + 17344746653834202604930860577508757708688427949046279718508635007113840369042, 37771390186920740637371383242878514021347606565375600086363978842439775164973*i + 60264754185911116825495147907207494752330900415794996812483089251259003404228), (1163730453993018743008743150834548760986076138562570206571825145859591284352*i + 69245390362211526197537288211735612650619880945856387683074182933575799994162, 11137807706588795799057940108843238078078690609437386007163034291855328303661*i + 50795522649623533714787572047531722836395032085224035511036953078383612475598, 14354786571703727534706086386589187674076604263117377684131521866407943036307*i + 63028649680815097939155846824928638616844025040257105384123424769274942520895)], [(22137116252880790433838296157765927318220905592359967466680754349755815464341*i + 35503968364379821899511866562472775961434113516937033217642581531414863539290, 38346074307552448152239080224505166810289185210503265380269711384969731945517*i + 9333819647786551924409858116441570177115099865486742684028611902450000042407, 24608192510515673607042276468532809071945836783394960695059783085937608049755*i + 27099766371861599260580052331632986107092105438254563604629919595057370886149), (57539731529782952718529369617033412770127782205874818027724894673104814770991*i + 12431864123786174601413168140961685219607645783666490625760143190724674574386, 33510082449726132893492104159133966168598115972734064630878005553829725389082*i + 30594711977745700371548334707069524826346332947574826081979927125841475148328, 8911862104171403632946802970568635607253840071000107875759139060453368618583*i + 51594672749496705581452789883241278156858476777167382827032876227546058970732), (58105830161247358431125768499050987088161417325586965601350797391396603985470*i + 10949064084676782939947256128733523229613253182051362970560478801614590446300, 6665352489343222248969975791152178151760060704226637217535985452272551528693*i + 16163109497937280055564868323730465088174193174761590036929535644203224067166, 26147088265849488467397913386934580340556987670869413865359802108333761377560*i + 14170094609019059182842713618319151553137248441974849089555832123638494739417)], [(60066006389024369318961505483331049048095679333675437984483948643792214278503*i + 67617085525047580942273623886038114942547589259839196477555874755427651308048, 38692305959834079988532869421062338838072016075793686080934562521314366274998*i + 21104829450473981189549299039898127784065322316764325995863199136802573514, 7207625628360021282792621977024027446511231977201394776410095364976996279450*i + 23039079766688651678553952766794875180844089420934577132338235904018762773928), (10808368042897084491009063074724200907600038030639153659288985642861405920614*i + 33955795465220353002933680692690511153845418737513482128237117905262919879043, 21645210772494061734726430463955231707074915293749580279327741388687068110310*i + 62225984739450865202997071369617271241348810092608626482294704825641320606694, 14572118842071162051223076904993643512402905544627821044103215186921277812496*i + 63504547636870837320642724540312613748726280369811190421219651308407770510674), (6529211642735966744323364626486352288002532267939478445216264742350974653419*i + 43426895500365913698127867498420593427453574994051597107529725996420257433857, 66636149494607064863031794353485502915121295051850619450321561966293398587284*i + 51049172134567530748763269555600518661288880531459625871071308764595168859033, 42297258788816007263333796194491196601979606573843177791726417124128570106777*i + 45527674821983322767637713856131638914194577467349514130179266972864796164733)], [(47645610858583239528541540288030905132801730740336899517917521534427703920375*i + 13272393664089987551368548207128885229248289454405159277755757369580866096516, 60503024931869977830369448001966194434192750710631225090391559259672930497207*i + 22742672333325631628906219543935772962495637869131049729874762344108069789046, 18239371575343144081671835175136676417172797381923442300525086630600561560114*i + 53605095942301227312866863441233162082087535371838738595931070092230378325532), (49652795839344946948771531270341537200526957150620826334216871981974859849848*i + 72788891932812016325514298655742330969740202920835574638161526839627026310392, 58465406030985457122487065262985150103086610852826560192123766406670919681919*i + 41631921368744416558173670147590406285376603436284660888096365325833457519047, 2867068797023070369258694926242485369317317985428997150826022662547346928319*i + 199536555238705400453079146297641296197748614855192340202929119323998667173), (19319782936524636558881137449470396788888469756320580071801690941326971557928*i + 34694728896207512382372151140975478616355941017631874070450334268575015485538, 60420266086997924618637147844041161464210208935194926422677077391866663978425*i + 13672363312837218411993834816309940812825734002380106434784905443915361955247, 56317025568717741728727542740124505299029374963112095990350877412868385510001*i + 56960621295573230601502052571104746367180500789238336757504091383665514782189)])
F =  [(36081831373398765496490121898118275331597167308301671911642273861563666664545*i + 20818485079783326431414952124332440995164298376805349071762867760925654560129, 2080527476644284459469754065728582261439110792635520661740429151724797376184*i + 22485923248080983391383279592637691489160934672854638306617785344436031827838, 15544373162545014827602222261755865080947187122261471926061663568794038512828*i + 65994932829738499994169748656063604384011854387402875895186473718226656419067), (3553534440103543686958858303956716887328727627636404431097647427819509340361*i + 41182149981825439188243414995474733005799065992663037326956422731949977723727, 11444151159046255413538671703716370245288291793592500278345001664024824339590*i + 1802783416049323926195923226865768221398255563865542946492803065162093093803, 15739175840903697568714274177182938758189586472507039731239155962622285528109*i + 38249065906628598713138583591858150126778794837077688369911160900556744463900), (14364753807737302773559096493138893453118094354943941768609481298414054855231*i + 16290236676179704559365899211744462983770375364688247022596145726641137243214, 3863306473986430132042752882629555431418515741358351198972027547882636615940*i + 1209446834271293681961506708684952401569936830292701272655835127315444154958, 21868026584808712490812183410257662299067350008298604021123682243508255905173*i + 12828201007038003022201361213007595366913298546122923089499182187938898042596)]
ct =  96910798667771988374291172958072220832574586618080134344021393928577220469428

A, T, S, G = pk
A, T, S, G, F = [M(_) for _ in (A, T, S, G, F)]
E = A*T*A

g = G.det()
d = (F.det() / E.det()).sqrt()
print('g: %s' % g)
print('d: %s' % d)
print()

assert g^(p^2-1) == 1
g2 = g^(p+1)
d2 = d^(p+1)
print('g2: %s' % g2)
print('d2: %s' % d2)
print()

assert d2^(p-1) == 1
ell = factor(p-1)[-1][0]
print('python ./cado-nfs.py --dlp --ell=%s %s' % (ell, p))
print('python ./cado-nfs.py /tmp/cado.64exrynt/p75.parameters_snapshot.0 target=%s,%s' % (g2, d2))
print()

'''
Info:root: logbase = 304696016520446393317161686962074865294826214137917338567738734523574665662
Info:root: target = 7338238082910510652369676077633982917766537629883448309816702584486633778449
Info:root: log(target) = 1512679493712481161447294550172458486619271913625485125969046 mod ell
Info:root: target = 62293888073992148988194529486263475524049321397778589371047734157559281409320
Info:root: log(target) = 1893362376328569617143789212271139497863536748895463892996491 mod ell
1512679493712481161447294550172458486619271913625485125969046,1893362376328569617143789212271139497863536748895463892996491
'''

lg, ld = 1512679493712481161447294550172458486619271913625485125969046,1893362376328569617143789212271139497863536748895463892996491

s1 = ld * lg.inverse_mod(ell) % ell
cofac = (p-1) // ell
assert pow(g2, s1 * cofac, p) == pow(d2, cofac, p)

s2 = discrete_log(Zmod(p)(pow(d2, ell, p)), Zmod(p)(pow(g2, ell, p)))

s = crt([s1, s2], [ell, cofac])
assert pow(g2, s, p) == d2

fpm1 = [_[0] for _ in list(factor(p-1))]
fs = []
for f in fpm1:
  if g2^((p-1) // f) == 1:
    fs += [f]
print(fs)
p2 = (p-1) // product(fs)
s = s % p2
for i in range(product(fs)):
  if g^s == d:
    break
  s = s + p2
print('s = %s' % s)

D = G^s
K = list(D*S*D)
key = sum(K[0])+sum(K[1])+sum(K[2])
mask = int(sha256(str(key).encode()).hexdigest(),16)
pt = ct ^^ mask
flag = bytes.fromhex(hex(pt)[2:])
print(flag)

Crypto3:Another leak of LCG·

题目：Another+leak+of+LCG的附件.zip

题目不长

首先根据LCG的关系有

$S_{i+1} \equiv a S_i + b \pmod M$

令seed是 $S_0$ ，就是

$S_i \equiv a^i S_0 + (\sum_{k=0}^{i-1} a^k) \cdot b \pmod M$

不妨令

$\begin{aligned} A_i &= a^i \\ B_i &= (\sum_{k=0}^{i-1} a^k) \cdot b \end{aligned}$

可以简化表达为

$S_i \equiv A^i S_0 + B_i \pmod M$

接下来题目给了64个连续的LCG数据，但是每个数据都只知道几个比特，题目输出也是一堆，但是先不要慌

看一下M并不是素数，而是模 $2^\ell$ ，就有个漏洞

那么就可以采用分治的算法，首先把关系改成（可以自己验算一下，是成立的）

$S_i \equiv A^i S_0 + B_i \pmod {2^k},\ k = 1, 2, \cdots, \ell$

调整一下，即

$S_0 \equiv A^{-i} (S_i - B_i) \pmod {2^k}$

然后在这里从 $k=1$ 开始，如果在64个数据中泄露了某个 $S_i$ 的最低位（第 $0$ 位）比特，不妨令这一位为 $b_i$ ，那么就可以根据

$S_0 \equiv A^{-i} (b_i - B_i) \pmod {2}$

恢复 $S_0$ 的第 $0$ 位比特

再然后在 $k\ge2$ 时，如果在64个数据中泄露了某个 $S_i$ 的第 $k-1$ 位，不妨令这一位为 $b_i$ ，由于 $k$ 是从小到大遍历，那么 $S_0 \pmod {2^{k-1}}$ 已知，就可以先计算

$S_i \equiv A^i S_0 + B_i \pmod {2^{k-1}}$

再计算

$S_0 \equiv A^{-i} ((2^{k}b_i + S_i \pmod {2^{k-1}}) - B_i) \pmod {2^k}$

得到 $S_0 \pmod {2^{k}}$

所以理论上如果64个数据恰好每一位的数据都有泄露的话，通过这样的分治就可以简单地恢复 $S_0$

但实际并不是如此，统计发现有一些位是未知的

于是最后还需要做一步剪枝，在遇到未知的位时，先把这一位设置成 $0$ 和 $1$ ，让它按两个分支去走，然后在下面的分支中通过64个数据中已知的位判断是否产生矛盾，如果有矛盾的话就把这个分支剪切掉

我自己使用的判断矛盾的方法是，用那些有多个数据泄露的位，通过判断每个数据得到的 $S_0$ 对应的位是否都相同，如果相同就保留，否则剪掉

看文字听拗口的，可以看代码

参考代码

LENGTH = 512
RATIO = 0.02024
M = 2**LENGTH
with open('./../output.txt') as f:
  exec(f.read())

data = []
for i in range(LENGTH):
  tmp = []
  for j in range(len(x)):
    xji = x[j][::-1][i]
    if xji != '*':
      tmp += [(int(xji), j)]
  data += [tmp]
  print(i, tmp)
print()

A = [pow(a, i, M) for i in range(1, len(x)+1)]
B = [b * sum([pow(a, k, M) for k in range(i)]) % M for i in range(1, len(x)+1)]

def gao(s0, i):
  if i >= LENGTH-1:
    #print('GET: %s' % s0)
    return [s0]

  ress = []
  if data[i] == []:
    #print(i, bin(s0))
    res = gao(s0, i+1)
    if res == []:
      #print(i, bin(2^i + s0))
      ress += gao(2^i + s0, i+1)
    ress += res

  res = set()
  for di in data[i]:
    Mi = 2^(i+1)
    sim1 = (A[di[1]] * s0 + B[di[1]]) % (2^i)
    s0i = (di[0]*2^i + sim1 - B[di[1]]) * pow(A[di[1]], -1, Mi) % Mi
    res.add(s0i)
  res = list(res)
  #print(i, res)
  if len(res) == 1:
    ress += gao(res[0], i+1)
  return ress

seeds = gao(0, 0)
print(seeds)

for seed in seeds:
  m = c ^^ seed
  flag = bytes.fromhex(hex(m)[2:])
  print(flag)

虽然我代码考虑了多解，但解出来好像还是不对（不知道我问题还是他问题- -）

最后解出来有一字节是\xe3，猜一下是0nce然后就正确了

类比一下，这题其实和之前看到的RSA泄露 $p \oplus q$ 的题挺像的

Crypto4:easyCrypto·

题目：easyCrypto的附件.zip

今年网鼎杯刚出过，多进程爆一下就分解了

分解完后可以得到

$c \equiv (1 + Pn)^m \pmod {n^3}$

二项式定理搞一下就是

$\begin{aligned} c &\equiv C_{n^3}^0 (Pn)^0 + C_{n^3}^1 (Pn)^1 + C_{n^3}^2 (Pn)^2 \\ &\equiv 1 + m P n + \frac{m(m-1)}{2} (Pn)^2\pmod {n^3} \end{aligned}$

整理一下

$\begin{aligned} \frac{c - 1}{P} &\equiv mn + \frac{m (m-1)}{2} P n^2 \\ &\equiv mn + (m^2 - m) \frac{P n^2}{2} \pmod {n^3} \end{aligned}$

这东西明显小于 $n^3$ ，所以就是

$\frac{c - 1}{P} = mn + (m^2 - m) \frac{P n^2}{2}$

也就是

$\frac{c - 1}{P n} = m + (m^2 - m) \frac{P n}{2}$

令 $A = \frac{Pn}{2}$ ，就是

$A m^2 - (A-1) m - \frac{c - 1}{P n} = 0$

解个方程就可以解出 $m$ 了

参考代码

from sage.all import *
from sage.parallel.multiprocessing_sage import parallel_iter
from tqdm import tqdm

# https://tover.xyz/p/2024-wdb-RSA/#Part-4-%E5%A4%9A%E8%BF%9B%E7%A8%8B%E7%9A%84%E5%B7%B2%E7%9F%A5p%E9%AB%98%E4%BD%8D%E5%88%86%E8%A7%A3
def gao(n, ph, pl=1, pbits=512):
  global tqdm
  hbits = Integer(ph).nbits()
  lbits = Integer(pl).nbits()
  PR = PolynomialRing(Zmod(n), 'x')
  x = PR.gen()
  f = ph * 2**(pbits-hbits) + x * 2**lbits + pl
  f = f.monic()
  # p:512 ph:262
#roots = f.small_roots(X=2**(pbits-hbits-lbits+1), beta=0.48, epsilon=0.0106)
  roots = f.small_roots(X=2**(pbits-hbits-lbits+1), beta=0.48, epsilon=0.0103)
  if roots:
    pm = Integer(roots[0])
    p = ph * 2**(pbits-hbits) + pm * 2**lbits + pl
    if n % p == 0:
      q = n // p
      print()
      print('p = %d' % p)
      print('q = %d' % q)
      return p, q
  return None


def mgao(n, ph, T=16, gmax=262):
  hbits = Integer(ph).nbits()
  gbits = gmax - hbits
  ph = ph << gbits
  N = 2**gbits
  for i in tqdm(range(N//T + 1)):
    pars = []
    for j in range(T):
      pars += [((n, ph+(T*i+j), 1, 512), {})]
    res = list(parallel_iter(T, gao, pars))
    for r in res:
      if r[1] != None:
        return r[1]

ph = 115314121469787984258489158421056136177545051135641551928888818017665807264468
n = 135133139540786818977969958456509467902948924003478556140490841984247464940261764739984274397650928404945721248284577232814352745333641188749824519153271662051302477973525156608141358709265683759057060630360909926255299541198485901065352661702656282587105799982740927802530997159098015074633017964344230291287
#mgao(n, ph)

p = 13352463043552409670211183534740157814546713901105410408023687926498813469217507846107364405269402732967687839808637375591530105677153038557366731161035343
q = 10120465347855011176216116854406657716210971137988515839650722657457130494685812171761795141588424375299868315964294503826721743852498238577704636503052409
P = (p - q) & ((1 << 130) - 1)
c = 1836794759996264077871820946090708779709415760553736759453665641907562256633157424959089180650539327925671892742819931875681606982615287882656254828326465758462357812873839261469783652663796071814218493268788421243190729887313099383264588659922912876424206670310928514588754069909128149471326084547056385690037197908766053620702238356084124023146075698878494434053246157524775269473152458661801907641122308756667762880284617915774590075511686821816948174618196839335059944389423693187930672934293905608970421003536691336581450927887931599275461176935079227494931457562345640133982771901848553204154760760399724074615092290799119053032875792219794072963200108352944441876206386518960615891547166767499506114294860833404421893612197040731184031783165365621722947731966143226777081983415797778111715332055871302609049501876860012070502369090417942239749695034267695710324328867728296996779

c = (c-1) * Integer(P).inverse_mod(n**3) % (n**3)
assert c % n == 0
c = c // n
assert P % 2 == 0
A = (P * n) // 2

PR = PolynomialRing(ZZ, 'x')
x = PR.gen()
f = A * x**2 - (A-1) * x - c
m = f.roots()[0][0]
flag = bytes.fromhex(hex(m)[2:])
print(flag)

Crypto5:Mypow·

题目：Mypow的附件.zip

首先分解，现有

$h = 2p + 7q$

平方再开方

$|2p - 7q| = \sqrt{2^2p^2 - 2 \cdot 2 \cdot 7 n + 7^2} = \sqrt{h^2 - 4 \cdot 2 \cdot 7 n}$

实际得出来的是 $7q - 2p$ ，所以分解

$q = \frac{(7q - 2p) + (2p +7q)}{14}$

然后Mypow就是省略了一次奇数操作

1 2	assert Mypow(1997, 1996, 197) == Mypow(1997, 1997, 197) assert Mypow(1997, 1997, 197) == pow(1997, 1996, 197)

所以实际的e是next_prime(666) - 1即672

最后就是一个AMM，套模板即可

参考代码

n = 36443283250594259606482132779262570582448178589602577809591307671554949253094255209079689901493052116793388954529442162972106210862341856282788030374324677114528044629385805693771773377070021111949953333360526159026822968061585876873187059674130307295006486032106471182393880915860569773206853864515489855553
h = 57792516722001523643789088224096258172899052039145876393373730235406451592173971020702024058282699663364267742428240581839287357212741266617791207580236457
c = 24482128269957355675512496312977308128712253968496848873519792376434347925427116612997489113223781321628516365811583310346553402215907938918891908853234881284620764982626375301219763593402089309909155204943747718536894186749932544428588048770663458669109073657836937287831725958017345747881678942488157429000

ppq = h
pmq = (h^2 - 4*2*7*n)^(1/2)
assert (ppq + pmq) % 14 == 0
q = (ppq + pmq) // 14
p = n // q
assert p * q == n
p = Integer(p)
q = Integer(q)
print(p)
print(q)

from Crypto.Util.number import *
phi = (p-1) * (q-1)

# https://tover.xyz/p/n-root-in-F/
load('nth.py')
e = 673 - 1
checker = genHeaderChecker('DASCTF')
print(e)
res = nthRSA_n(c, e, [p], checker=checker)

总结·

不如闲鱼