还是一如既往的菜，没啥长进啊。题目肯定是不算难的，但就是不会，还是太懒了，抓紧学起来！
baby_RSA
from Crypto.Util.number import *
nbit = 512
flag='****************************'
p=getPrime(nbit)
q=getPrime(nbit)
e=65537
n=p*q
m= bytes_to_long(bytes(flag.encode()))
P = pow(m,p,n)
Q = pow(m,q,n)
N=P*Q
phi_N=(P-1)*(Q-1)
d=inverse(e,phi_N)
dP=d%(P-1)
print('n = ',n)
print('N = ',N)
print('dP = ',dP)
n = 114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
N = 1159977299277711167607914893426674454199208605107323826176606074354449015203832606569051328721360397610665453513201486235549374869954501563523028914285006850687275382822302821825953121223999268058107278346499657597050468069712686559045712946025472616754027552629008516489090871415609098178522863027127254404804829735621706042266140637592206366042515190385496909533329383212542170504864473944657824502882014292528444918055958758310544435120502872883857209880723535754528096143707324179005292445100655695427777453144657819474805882956064292780031599790769618615908501966912635232746588639924772530057835864082951499028
dP = 33967356791272818610254738927769774016289590226681637441101504040121743937150259930712897925893431093938385216227201268238374281750681609796883676743311872905933219290266120756315613501614208779063819499785817502677885240656957036398336462000771885589364702443157120609506628895933862241269347200444629283263
看到出现了dp，套个dp的爆破脚本解出P、Q来：
for i in range(1,e):
if (dP*e-1)%i == 0:
if (N%((dP*e-1)//i+1)) == 0:
P = (dP*e-1)//i+1
Q = N // P
print(P)
print(Q)
#P = 37269067352457630263351774206178494913957088859822110344334922741582406663357663275001777826744534556652993452577088773275825539553907027527722045884489297259984687894496505265384077983882580247333972954704644517469999916574893996324149548980338301147983367163067556434434982470623587914250041142380667816331
#Q = 31124398373258967647259273958463995255448332282733968391096762136494537693158180734634142626374694999391960402681114664140356232930100613919064790135723294710984789809295862966052914533841176463683069225072916170624016363164528353386087305805869313783193076760778433672011918504199905552973276891160558444988
然后根据题目得到下面两个关系式：
$P \equiv m^p \space mod \space n$
$Q \equiv m^q \space mod \space n$
各种推导，但我这个数学思维就是不行，没推出来。
$把n拆开，并利用费马小定理，m^{p-1} \equiv 1mod p（根本没想到，还是不熟悉），分别得到：$
$P \equiv m^p \space mod \space p
\equiv mm^{p-1} \space mod \space p \equiv m \space mod \space p\Rightarrow P = m + k_1 p $
$同理，Q \equiv m^q \space mod \space q \equiv m \space mod \space q \Rightarrow Q = m + k_2q $
$两式子相乘$
$ \Rightarrow PQ = m^2 + (k_1p+k_2q)m + kn $
$\Rightarrow PQ \equiv -m^2 + (P+Q)m \space mod \space n $
$我想知道为什么m^2前面带了负号。\
这里(k_1p+k_2q) \approx (P+Q)$
然后构造多项式直接求解m：
P = ...
Q = ...
n = ...
R.<m> = Zmod(n)[]
f = -m**2+(P+Q)*m-P*Q#这里的加减号不能错了
m = f.monic().small_roots()
'''
#或者这样构造
PR.<m> = PolynomialRing(Zmod(n))
'''
print(m)
#m = 152099310694956022622926857538598513541723670773227126074246760446874272165452073476477
#显然p、q是远大于m的，这就是为什么上面的推导可以近似等于
#print(long_to_bytes(m))
#b'NKCTF{Th1S_a_babyRSA_y0u_are_tql!!!}'
ezRSA
from Crypto.Util.number import *
from secret import flag
m1 = bytes_to_long(flag[:len(flag)//3])
m2 = bytes_to_long(flag[len(flag)//3:])
def gen():
prime_list = []
for i in range(4):
prime_list.append(getPrime(512))
return sorted(prime_list)
prime_list = gen()
p,q,r,t = prime_list[0],prime_list[3],prime_list[1],prime_list[2]
e = 65537
n = p*q*r*t
phi = (p-1)*(q-1)*(r-1)*(t-1)
c1 = pow(m1,e,p*q)
p1 = getPrime(512)
q1 = getPrime(512)
N = p1*q1
c2 = pow(m2,p1,N)
c3 = pow(m2,q1,N)
print(f'n = {n}')
print(f'phi = {phi}')
print(f'c1 = {c1}')
print(f'N = {N}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
'''
n = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505626165666334675100147790578546682128517668100858766784733351894480181877144793496927464058323582165412552970999921215333509253052644024478417393146000490808639363681195799826541558906527985336104761974023394438549055804234997654701266967731137282297623426318212701157416397999108259257077847307874122736921265599854976855949680133804464839768470200425669609996841568545945133611190979810786943246285103031363790663362165522662820344917056587244701635831061853354597
phi = 8836130216343708623415307573630337110573363595188748983290313549413242332143945452914800845282478216810685733227137911630239808895196748125078747600505622503351461565956106005118029537938273153581675065762015952483687057805462728186901563990429998916382820576211887477098611684072561849314986341226981300596338314989867731725668312057134075244816223120038573374383949718714549930261073576391501671722900294331289082826058292599838631513746370889828026039555245672195833927609280773258978856664434349221972568651378808050580665443131001632395175205804045958846124475183825589672204752895252723130454951830966138888560
c1 = 78327207863361017953496121356221173288422862370301396867341957979087627011991738176024643637029313969241151622985226595093079857523487726626882109114134910056673489916408854152274726721451884257677533593174371742411008169082367666168983943358876017521749198218529804830864940274185360506199116451280975188409
N = 157202814866563156513184271957553223260772141845129283711146204376449001653397810781717934720804041916333174673656579086498762693983380365527400604554663873045166444369504886603233275868192688995284322277504050322927511160583280269073338415758019142878016084536129741435221345599028001581385308324407324725353
c2 = 63355788175487221030596314921407476078592001060627033831694843409637965350474955727383434406640075122932939559532216639739294413008164038257338675094324172634789610307227365830016457714456293397466445820352804725466971828172010276387616894829328491068298742711984800900411277550023220538443014162710037992032
c3 = 9266334096866207047544089419994475379619964393206968260875878305040712629590906330073542575719856965053269812924808810766674072615270535207284077081944428011398767330973702305174973148018082513467080087706443512285098600431136743009829009567065760786940706627087366702015319792328141978938111501345426931078
'''
n由四个大素数组成，加密只使用p和q，给了n、e、phi的值，在佬的提示下找了个know_phi的脚本，这里不贴了github上有，解出四个因数来，注意选择最小的和最大的作为p、q：
p = 8420341711111386139826589531912136886697864041156239432418101990860951057225344962981814097328105109563572968937589482777359728076364540186966659710593563
q = 10834231423967940002221004300639472879422266804796466209639481015717927053785699849888626682293072249949761634253205413288361321778947376683555990557548843
进一步解出m1来：
b'NKCTF{it_i5_e45y_th4t_Kn0wn'
接下来由题可以得到两个式子：
$c2 \equiv m_2^{p_1} \space mod \space N $
$c3 \equiv m_2^{q_1} \space mod \space N $
$非常之熟悉吧，和上面的baby一模一样，同理推导 $
$c2 = m_2 + k_1p_1 $
$c3 = m_2 + k_2q_1 $
$\Rightarrow c2c3 = -m_2^2+(c2+c3)m \space mod \space N$
就是因为这部分，导致两道题都没能做出来😥
R.<m> = Zmod(N)[]
#或者PR.<m> = PolynomialRing(Zmod(N))
f = -m**2+(c2+c3)*m-c2*c3
m = f.monic().small_roots(X=2^432,beta = 0.5,epsilon=0.01)
#X=2^432，前面求出m1，求得位数为215，所以m2的位数430，但为什么设为432
print(m)
#m = 4134704395865052635910135198384991632904826868184178486449854532897025132606910716694129086727413635889097150181468673789907726717
#print(long_to_bytes(m))
#b'_phi_4nd_N_dec0mp0ses_N_w1th_th3_s4m3_c0mm0n_n_but_pq}'
综上，flag：
NKCTF{it_i5_e45y_th4t_Kn0wn_phi_4nd_N_dec0mp0ses_N_w1th_th3_s4m3_c0mm0n_n_but_pq}
解释：epsilon=0.01，表示小根搜索算法中搜索到的所有小根的误差上界为 $\epsilon$。也就是说，如果 $r$ 是 $m(x)$ 在模 $X$ 意义下的一个小根，那么 $|r| < X^{1/2} \cdot \epsilon$。
ezMath
from Crypto.Util.number import getPrime, bytes_to_long
from secret import BITS, hints, flag
p = getPrime(BITS)
q = getPrime(BITS)
n = p * q
print(f'n = {n}')
e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(f'c = {c}')
print('Give you some boring pows:')
for i in range(len(hints)):
print(hints[i])
'''
n = 369520637995317866367336688225182965061898803879373674073832046072914710171302486913303917853881549637806426191970292829598855375370563396182543413674021955181862907847280705741114636854238746612618069619482248639049407507041667720977392421249242597197448360531895206645794505182208390084734779667749657408715621
c = 324131338592233305486487416176106472248153652884280898177125443926549710357763331715045582842045967830200123100144721322509500306940560917086108978796500145618443920020112366546853892387011738997522207752873944151628204886591075864677988865335625452099668804529484866900390927644093597772065285222172136374562043
Give you some boring pows:
...
'''
给了n、c、e以及一大堆的等式，不知道怎么利用。
看了佬们的wp后，发现其实还是跟推导有关😔
从给的数据里选择两组，两组满足底数相同，结果为平方关系，如下面这组：
pow(6,141997416965295486849546892322458652502850390670128808480582247784728456230996812361056958004801816363393016360646922983916999235770803618904474553309200419301820603229504955218189709387942156848904968053547462302189568831762401075340100029630332409419313772378068180267756675141584884876543484516408660699471038, n) = 9
pow(6,163378867981477210016607618217525067516899896304907822758749135410592905658324027908854458465871295591148114728316034699358213461728042658497873130073105697195541220650688132150216266657024774867846925219967805863946774978900772828496605795631400777090954141000078238226487076065753781167791598816872139973922682, n) = 3
进行推导：
$a^{e_1} \equiv a^{2e_2} \space mod \space n \Rightarrow a^{2e_2-e_1} \equiv 1 \space mod \space n $
$由欧拉定理，a^{\phi(n)} \equiv 1 \space mod \space n
\Rightarrow 2e_2-e_1 = k \phi(n) $
$这里带上k（有点疑惑）$
多找几组，对$2*e_2-e_1$部分求gcd得到$\phi(n)$。
pow(5,159624441075769368394142197503800917105605266793330527400563601282696932962732683048452274321445695181246055818189076528484173940458256745774766217433996778905066039826859919029954611118842967545793750205189398662362981005947945407568116603784658538931110792205205160154125544664182868277733116044735541284338342, n) = 9
pow(5,172192380036714150788905270808196199818277334366508682218739812159577144024191963252552116624193235000074634457087111471641800814071769221933018962135503876997163938949365614056098717522475180216291316295788774044033481065993544994610614082708563841846852650913646728169671510827052772868386414581035580266356334, n) = 3
pow(7,156359509651684605051402965560382969488421316701585527115005130492947292379802933549188085059602557600903593831240316597311439285149968787780538126741092612405335349622445040578126369183536683733294143156965518222696624206221060030916594302284630706642066420353822195108928341123726471513256217857861184609387726, n) = 9
pow(7,170559914324671769117535654836487226009685359320636182075960576764702323732727088502920021993271666209903403463612731506055433486417625242935904916789051793747298593847158174830184596554822038310041512771676833824200302666130102306284852931958549925702330464987955245647072909056824574486147965487598401928881026, n) = 3
e = 0x10001
n = ...
c = ...
e1 = [..., ..., ...]
e2 = [..., ..., ...]
res = []
for i in range(3):
res.append(2*e2[i]-e1[i])
phi1 = gcd(res[0],res[1])
phi2 = gcd(phi1,res[2])
d = inverse(e,phi2)
m = pow(c,d,n)
print(long_to_bytes(m))
我验证了一下，如果只用两组e1和e2，也能得到flag，多用几组或许能更准确？
ez_polynomial
#sage
from Crypto.Util.number import *
flag = list(bytearray(''))
p = getPrime(16)
R.<y> = PolynomialRing(GF(p))
while True:
P1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
Q1 = R.random_element(degree=(ZZ.random_element(len(flag), 2*len(flag))))
if P1.is_irreducible() and Q1.is_irreducible():
P = P1
Q = Q1
break
e = 65537
N = P*Q
S.<x> = R.quotient(N)
c = S(flag) ^ e
print("P:" + str(p) + "\n")
print("N:" + str(N) + "\n")
print("C:" + str(c))
#P:40031
#N:24096*y^93 + 38785*y^92 + 17489*y^91 + 9067*y^90 + 1034*y^89 + 6534*y^88 + 35818*y^87 + 22046*y^86 + 12887*y^85 + 445*y^84 + 26322*y^83 + 37045*y^82 + 4486*y^81 + 3503*y^80 + 1184*y^79 + 38471*y^78 + 8012*y^77 + 36561*y^76 + 19429*y^75 + 35227*y^74 + 10813*y^73 + 26341*y^72 + 29474*y^71 + 2059*y^70 + 16068*y^69 + 31597*y^68 + 14685*y^67 + 9266*y^66 + 31019*y^65 + 6171*y^64 + 385*y^63 + 28986*y^62 + 9912*y^61 + 10632*y^60 + 33741*y^59 + 12634*y^58 + 21179*y^57 + 35548*y^56 + 17894*y^55 + 7152*y^54 + 9440*y^53 + 4004*y^52 + 2600*y^51 + 12281*y^50 + 22*y^49 + 17314*y^48 + 32694*y^47 + 7693*y^46 + 6567*y^45 + 19897*y^44 + 27329*y^43 + 8799*y^42 + 36348*y^41 + 33963*y^40 + 23730*y^39 + 27685*y^38 + 29037*y^37 + 14622*y^36 + 29608*y^35 + 39588*y^34 + 23294*y^33 + 757*y^32 + 20140*y^31 + 19511*y^30 + 1469*y^29 + 3898*y^28 + 6630*y^27 + 19610*y^26 + 11631*y^25 + 7188*y^24 + 11683*y^23 + 35611*y^22 + 37286*y^21 + 32139*y^20 + 20296*y^19 + 36426*y^18 + 25340*y^17 + 36204*y^16 + 37787*y^15 + 31256*y^14 + 505*y^13 + 27508*y^12 + 20885*y^11 + 32037*y^10 + 31236*y^9 + 7929*y^8 + 27195*y^7 + 28980*y^6 + 11863*y^5 + 16025*y^4 + 16389*y^3 + 570*y^2 + 36547*y + 10451
#C:3552*x^92 + 6082*x^91 + 25295*x^90 + 35988*x^89 + 26052*x^88 + 16987*x^87 + 12854*x^86 + 25117*x^85 + 25800*x^84 + 30297*x^83 + 5589*x^82 + 23233*x^81 + 14449*x^80 + 4712*x^79 + 35719*x^78 + 1696*x^77 + 35653*x^76 + 13995*x^75 + 13715*x^74 + 4578*x^73 + 37366*x^72 + 25260*x^71 + 28865*x^70 + 36120*x^69 + 7047*x^68 + 10497*x^67 + 19160*x^66 + 17939*x^65 + 14850*x^64 + 6705*x^63 + 17805*x^62 + 30083*x^61 + 2400*x^60 + 10685*x^59 + 15272*x^58 + 2225*x^57 + 13194*x^56 + 14251*x^55 + 31016*x^54 + 10189*x^53 + 35040*x^52 + 7042*x^51 + 29206*x^50 + 39363*x^49 + 32608*x^48 + 38614*x^47 + 5528*x^46 + 20119*x^45 + 13439*x^44 + 25468*x^43 + 30056*x^42 + 19720*x^41 + 21808*x^40 + 3712*x^39 + 25243*x^38 + 10606*x^37 + 16247*x^36 + 36106*x^35 + 17287*x^34 + 36276*x^33 + 1407*x^32 + 28839*x^31 + 8459*x^30 + 38863*x^29 + 435*x^28 + 913*x^27 + 36619*x^26 + 15572*x^25 + 9363*x^24 + 36837*x^23 + 17925*x^22 + 38567*x^21 + 38709*x^20 + 13582*x^19 + 35038*x^18 + 31121*x^17 + 8933*x^16 + 1666*x^15 + 21940*x^14 + 25585*x^13 + 840*x^12 + 21938*x^11 + 20143*x^10 + 28507*x^9 + 5947*x^8 + 20289*x^7 + 32196*x^6 + 924*x^5 + 370*x^4 + 14849*x^3 + 10780*x^2 + 14035*x + 15327
唯一写出来的题，还是因为之前写过这种题，不然爆0了。。。
在之前的文章里写过，相关知识不说了。
sage上对N进行多项式分解得到P、Q两个多项式：
R.<y> = PolynomialRing(GF(40031))
N = R("...")
print(N.factor())
然后就是常规思路求d求flag：
e = 65537
phi_n = (40031^40-1)*(40031^53-1)
d = inverse_mod(e, phi_n)
flag = pow(C,d,N)
print(flag)
#输出：
#125*y^32 + 83*y^31 + 109*y^30 + 97*y^29 + 51*y^28 + 114*y^27 + 100*y^26 + 95*y^25 + 116*y^24 + 117*y^23 + 66*y^22 + 95*y^21 + 103*y^20 + 110*y^19 + 49*y^18 + 104*y^17 + 116*y^16 + 48*y^15 + 110*y^14 + 95*y^13 + 51*y^12 + 86*y^11 + 97*y^10 + 72*y^9 + 95*y^8 + 101*y^7 + 87*y^6 + 123*y^5 + 70*y^4 + 84*y^3 + 67*y^2 + 75*y + 78
提取系数，转ASCII码，发现是逆序的，再倒一下就行：
flag = "..."
flag = flag.split('+')
res = ''
for i in flag:
res += chr(int(i.split('*')[0]))
print(res)
print(res[::-1])
#}Sma3rd_tuB_gn1ht0n_3VaH_eW{FTCKN
#NKCTF{We_HaV3_n0th1ng_But_dr3amS}
eZ_Bl⊕ck
from Crypto.Util.strxor import strxor as xor
import os
from secret import flag
def round(s, k):
l, r = s[:16], s[16:]
l_, r_ = xor(xor(r, k), l), l
return l_ + r_
def encode(s, k):
t = s
for i in range(8):
t = round(t, k[i])
return t
r = os.urandom(32)
print(r)
key = [os.urandom(16) for _ in range(8)]
print(encode(r, key))
m = flag.strip(b'NKCTF{').strip(b'}').replace(b'-',b'')
print(encode(m, key))
#b"t\xf7\xaa\xac\x9d\x88\xa4\x8b\x1f+pA\x84\xacHg'\x07{\xcc\x06\xc4i\xdd)\xda\xc9\xad\xa9\xe8\x1fi"
#b"'{<z}\x91\xda\xc5\xd5S\x8b\xfa\x9f~]J\x0f\xf4\x9a\x1e\xe0\xef\x129N\xe7a\x928+\xe0\xee"
#b'8\x1f"\x83B4\x86)\xce\xebq3\x06\xa0w\x16U\x04M/w\xa1\x8f;)M\xdd~\x11:\xe3\xb3'
不知道怎么推，块加密类的题练的少，要加强练习了。
分组密码的Feistel结构，没学过。
加密过程简单描述就是，将明文分组左右等长的两部分，两部分数据会经过n轮迭代，每轮迭代的规则一样，即使用相同的轮函数。且每轮迭代会使用密钥$K_i$，同样，每轮迭代使用的$K_i$也是不同的。这只是大致的过程，还有不少细节部分。
Feistel结构的迭代典型次数为16，可以看到题目中是8次。
通过分析可以知道，先要通过r和r与key进行加密的结果来得到key。
隔了几天，回顾这道题，终于搞懂了：
$首先把r的左半部分记作l_0，右半部分记作r_0，把r与key加密的结果记作enc$
$按照题目的推理规则可以逐步得到下面的等式：$
$l_1 = l_0 \bigoplus r_0 \bigoplus k_0$
$ r_1 = l_0 $
$按顺序推导八轮，最终可以得到如下关系：$
$enc_l = r_0 \bigoplus k_0 \bigoplus k_1 \bigoplus k_3 \bigoplus k_4 \bigoplus k_6 \bigoplus k_7 $
$enc_r = r_0 \bigoplus l_0 \bigoplus k_0 \bigoplus k_2 \bigoplus k_3 \bigoplus k_5 \bigoplus k_6$
$推导过程我是在纸上写的，有点丑，不贴了。。。$
$将enc_l中的key整体记作k_l，enc_r中的key整体记作k_r，$
$我对于此处的理解是，并不是把k_l与题目的key的左半部分等同起来（实际也不相等）$
$这里的k_l只是作一个定义，因为在后面m与key进行轮加密的过程中，最终也会得到$
$与上面enc两行相同结构的结构（这里把m和key加密的结果记作c）：$
$c_l = m_r \bigoplus k_l$
$c_r = m_r \bigoplus m_l \bigoplus k_r$
如此一来便能解了：
from Crypto.Util.strxor import strxor as xor
r = b"t\xf7\xaa\xac\x9d\x88\xa4\x8b\x1f+pA\x84\xacHg'\x07{\xcc\x06\xc4i\xdd)\xda\xc9\xad\xa9\xe8\x1fi"
enc = b"'{<z}\x91\xda\xc5\xd5S\x8b\xfa\x9f~]J\x0f\xf4\x9a\x1e\xe0\xef\x129N\xe7a\x928+\xe0\xee"
c = b'8\x1f"\x83B4\x86)\xce\xebq3\x06\xa0w\x16U\x04M/w\xa1\x8f;)M\xdd~\x11:\xe3\xb3'
r_l = r[:16]
r_r = r[16:]
enc_l = enc[:16]
enc_r = enc[16:]
key_l = xor(enc_l,r_r)
key_r = xor(enc_r,xor(r_l,r_r))
c_l = c[:16]
c_r = c[16:]
m_r = xor(c_l,key_l)
m_l = xor(xor(key_r,c_r),m_r)
m = m_l+m_r
print(m)
#b'1ccd5ceec96d4caf8ce59a512b3d0655'
import uuid
flag = '1ccd5ceec96d4caf8ce59a512b3d0655'
print(uuid.UUID(flag))
#1ccd5cee-c96d-4caf-8ce5-9a512b3d0655
这里uuid搞不懂。
easy_high
from Crypto.Util.number import *
flag = ''
p, q = getPrime(1024), getPrime(1024)
N = p * q
p0 = p ^ (bytes_to_long(flag)<<444)
m = bytes_to_long(flag)
c = pow(m, 65537, N)
print('c=',c)
print('N=',N)
print('p0=',p0)
#c= 4881545863615247924697512170011400857004555681758106351259776881249360423774694437921554056529064037535796844084045263140567168171628832384672612945806728465127954937293787045302307135365408938448006548465000663247116917564500525499976139556325841597810084111303039525833367199565266613007333465332710833102978756654324956219855687611590278570749890543277201538208370370097424105751568285050703167350889953331829275262932104042040526209179357770495596739361176548337593674366015027648541293309465113202672923556991818236011769228078267484362980348613669012975963468592763463397575879215173972436831753615524193609612
#N= 17192509201635459965397076685948071839556595198733884616568925970608227408244870123644193452116734188924766414178232653941867668088060274364830452998991993756231372252367134508712447410029668020439498980619263308413952840568602285764163331028384281840387206878673090608323292785024372223569438874557728414737773416206032540038861064700108597448191546413236875600906013508022023794395360001242071569785940215873854748631691555516626235191098174739613181230094797844414203694879874212340812119576042962565179579136753839946922829803044355134086779223242080575811804564731938746051591474236147749401914216734714709281349
#p0= 149263925308155304734002881595820602641174737629551638146384199378753884153459661375931646716325020758837194837271581361322079811468970876532640273110966545339040194118880506352109559900553776706613338890047890747811129988585025948270181264314668772556874718178868209009192010129918138140332707080927643141811
基本上是分析这一行：
p0 = p ^ (bytes_to_long(flag)<<444)
可以知道flag左移444位后（低位补0）与$p$异或得到$p_0$，那么$p$的低444位与$p_0$是相同的。等于是知道了p的低444位，未知位数达到580位，在之前的文章里提到，当p、q位数是1024bit时，未知位数不能超过454bit过多。所以至少还得知道p的126位才能使用copper。
在p、q相近的情况下对n直接开方取高位作p的高位，但这里不成立，故行不通。
另寻他路：以flag的格式，最长也就那么长，转整数后也不会很大，可以试一下：
flag = b"NKCTF{ajdnaosdhiasdsfisdjdihadiasdhoadhsiodaj}"
print(bytes_to_long(flag))
res = 183876783844719951164006751402861139015367850881248806466142942786265188461121827081223474428956250940320606845
print(res.bit_length())
#367
flag是我随便打的，看到也才367位，实际肯定比这短，所以未知位数是小于454位的，故$p_0$的高位部分与p也相同，到这就可以解了。
p_low = p0 - ((p0>>444)<<444)#低444位
p_high = p0>>898 #高126位
#未知位数恰好454位
#sage
PR.<x> = PolynomialRing(Zmod(N))
f = (p_high<<898) + x*(2**444) + p_low
res = f.monic().small_roots(X=2^454,beta=0.4)
print(res)
#x = 8996514515788824631645217678983870972689906544773849929777173576310649928527740139864048823998116829780535762155750526515388194925404594
p = (p_high<<898) + x*(2**444) + p_low
q = N // p
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,N)
print(long_to_bytes(m))
#b'NKCTF{F10wrs_hVe_r3strDay}'
我看佬的脚本是使未知位数为400，我试了下最大未知位数，也能解。还有一个地方，small_roots()函数里的参数，beta=等于0.2、0.3、0.5都不能解出来。还有如果加上epsilon=0.02，也能解，但会比不加慢一两秒。
佬的脚本里，beta等于0.2、0.3、0.4、0.5都能解，加不加epsilon也都能解。
这个参数的确定我还不太理解，迟早得彻底弄清楚。
complex_matrix
from Crypto.Util.number import *
import gmpy2 as gy
flag = ''
k = 400
p, q = getPrime(741), getPrime(741)
N = p * q
phi = (p-1) * (q-1)
_flag = bytes_to_long(flag)
p, q = getPrime(1024), getPrime(1024)
d_array = [getPrime(k) for _ in range(4)]
e_array = [inverse(i, phi) for i in d_array]
c = pow(_flag, 65537, N)
print('N:',N)
print('e:',e_array)
print('c:',c)
#N: 71841248095369087024928175623295380241516644434969868335504061065977014103487197287619667598363486210886674500469383623511906399909335989202774281795855975972913438448899231650449810696539722877903606541112937729384851506921675290984316325565141178015123381439392534417225128922398194700511937668809140024838070124095703585627058463137549632965723304713166804084673075651182998654091113119667582720831809458721072371364839503563819080226784026253
#e: [65128799196671634905309494529154568614228788035735808211836905142007976099865571126946706559109393187772126407982007858423859147772762638898854472065889939549916077695303157760259717113616428849798058080633047516455513870697383339784816006154279428812359241282979297285283850338964993773227397528608557211742425548651971558377656644211835094019462699301650412862894391885325969143805924684662849869947172175608502179438901337558870349697233790535, 58756559706647121529575085912021603170286163639572075337348109911506627489265537716060463072086480156516641723700802217411122982693536541892986623158818442274840863016647800896033363360822503445344748132842451806511693779600370832206455202293028402486647422212959763287987847280322100701242139127654031151565924132562837893975505159702015125483479126108892709063135006366792197127007229210558758401679638300464111782814561428899998471531067163715, 34828685390969672139784723764579499920301439564705391196519314224159563070870933754477650614819514127121146216049444888554338415587165719098661141454627820126445291802801256297252654045398330613075575527685542980264993711077876535643646746742646371967302159565887123638001580042027272379341650995728849759541960087953160211696369079708787543303742132161742979856720539914370868829868891655221361545648778590685232034703220732697083024449894197969, 26717968456600556973167180286909817773394160817933525240720067057464671317174201540556176814203780603153696663101158205367554829261808020426363683474848952397963507069306452835776851274959389849223566030857588019845781623271395012194869024566879791449466064832273531795430185178486425688475688634844530106740480643866537205900809400383304665727460014210405339697947582657505028211149470787536144302545259243549176816653560626044921521516818788487]
#c: 39297018404565022956251803918747154798377576057123078716166221329195959669756819453426741569480551313085435037629493881038383709458043802420338889323233368852331387845200216275712388921820794980987541224782392553528127093154957890356084331463340193478391679540506421250562554424770350351514435220782124981277580072039637811543914983033300225131364246910828188727043248991987332274929827173923543187017105236008487756190002204169623313222748976369
拓展winner攻击：
from Crypto.Util.number import *
debug = True
isdigit = lambda x: ord('0') <= ord(x) <= ord('9')
def my_permutations(g, n):
sub = []
res = []
def dfs(s, prev):
if len(s) == n:
res.append(s[::])
for i in g:
if i in s or i < prev:
continue
s.append(i)
dfs(s, max(prev, i))
s.remove(i)
dfs(sub, 0)
return res
class X3NNY(object):
def __init__(self, exp1, exp2):
self.exp1 = exp1
self.exp2 = exp2
def __mul__(self, b):
return X3NNY(self.exp1 * b.exp1, self.exp2 * b.exp2)
def __repr__(self):
return '%s = %s' % (self.exp1.expand().collect_common_factors(), self.exp2)
class X_Complex(object):
def __init__(self, exp):
i = 0
s = '%s' % exp
while i < len(s):
if isdigit(s[i]):
num = 0
while i < len(s) and isdigit(s[i]):
num = num*10 + int(s[i])
i += 1
if i >= len(s):
self.b = num
elif s[i] == '*':
self.a = num
i += 2
elif s[i] == '/':
i += 1
r = 0
while i < len(s) and isdigit(s[i]):
r = r*10 + int(s[i])
i += 1
self.b = num/r
else:
i += 1
if not hasattr(self, 'a'):
self.a = 1
if not hasattr(self, 'b'):
self.b = 0
def WW(e, d, k, g, N, s):
return X3NNY(e*d*g-k*N, g+k*s)
def GG(e1, e2, d1, d2, k1, k2):
return X3NNY(e1*d1*k2- e2*d2*k1, k2 - k1)
def W(i):
e = eval("e%d" % i)
d = eval("d%d" % i)
k = eval("k%d" % i)
return WW(e, d, k, g, N, s)
def G(i, j):
e1 = eval("e%d" % i)
d1 = eval("d%d" % i)
k1 = eval("k%d" % i)
e2 = eval("e%d" % j)
d2 = eval("d%d" % j)
k2 = eval("k%d" % j)
return GG(e1, e2, d1, d2, k1, k2)
def R(e, sn): # min u max v
ret = X3NNY(1, 1)
n = max(e)
nn = len(e)
l = set(i for i in range(1, n+1))
d = ''
u, v = 0, 0
for i in e:
if i == 1:
ret *= W(1)
d += 'W(%d)' % i
nn -= 1
l.remove(1)
u += 1
elif i > min(l) and len(l) >= 2*nn:
ret *= G(min(l), i)
nn -= 1
d += 'G(%d, %d)' % (min(l), i)
l.remove(min(l))
l.remove(i)
v += 1
else:
ret *= W(i)
l.remove(i)
d += 'W(%d)' % i
nn -= 1
u += 1
if debug:
print(d)
return ret, u/2 + (sn - v) * a
def H(n):
if n == 0:
return [0]
if n == 2:
return [(), (1,), (2,), (1, 2)]
ret = []
for i in range(3, n+1):
ret.append((i,))
for j in range(1, i):
for k in my_permutations(range(1, i), j):
ret.append(tuple(k + [i]))
return H(2) + ret
def CC(exp, n):
cols = [0 for i in range(1<<n)]
# split exp
texps = ('%s' % exp.exp1.expand()).strip().split(' - ')
ops = []
exps = []
for i in range(len(texps)):
if texps[i].find(' + ') != -1:
tmp = texps[i].split(' + ')
ops.append(0)
exps.append(tmp[0])
for i in range(1, len(tmp)):
ops.append(1)
exps.append(tmp[i])
else:
ops.append(0)
exps.append(texps[i])
if exps[0][0] == '-':
for i in range(len(exps)):
ops[i] = 1-ops[i]
exps[0] = exps[0][1:]
else:
ops[0] = 1
# find e and N
l = []
for i in range(len(exps)):
tmp = 1 if ops[i] else -1
en = []
j = 0
while j < len(exps[i]):
if exps[i][j] == 'e':
num = 0
j += 1
while isdigit(exps[i][j]):
num = num*10 + int(exps[i][j])
j += 1
tmp *= eval('e%d' % num)
en.append(num)
elif exps[i][j] == 'N':
j += 1
num = 0
if exps[i][j] == '^':
j += 1
while isdigit(exps[i][j]):
num = num*10 + int(exps[i][j])
j += 1
if num == 0:
num = 1
tmp *= eval('N**%d' % num)
else:
j += 1
if tmp == 1 or tmp == -1:
l.append((0, ()))
else:
l.append((tmp, tuple(sorted(en))))
# construct h
mp = H(n)
for val, en in l:
cols[mp.index(en)] = val
# print(cols)
return cols
def stirling(k):
return factorial(k)/(factorial(k//2)^2)
def calcAlpha(n):
if n % 2 == 1:
fz = (2*n + 1) * 2^n - 4*n*stirling(n-1)
fm = (2*n - 2) * 2^n + 8*n*stirling(n-1)
else:
fz = (2*n + 1) * 2^n - (2*n + 1)*stirling(n)
fm = (2*n - 2) * 2^n + (4*n + 2)*stirling(n)
return fz/fm
def EWA(n, elist, NN, alpha):
mp = H(n)
var('a')
S = [X_Complex(n*a)]
cols = [[1 if i == 0 else 0 for i in range(2^n)]]
for i in mp[1:]:
eL, s = R(i, n)
cols.append(CC(eL, n))
S.append(X_Complex(s))
alphaA,alphaB = 0, 0
for i in S:
alphaA = max(i.a, alphaA)
alphaB = max(i.b, alphaB)
D = []
for i in range(len(S)):
D.append(
int(NN^((alphaA-S[i].a)*alpha + (alphaB - S[i].b)))
)
kw = {'N': NN}
for i in range(len(elist)):
kw['e%d' % (i+1)] = elist[i]
if debug:
print("The lattice: ")
print(Matrix(cols).T)
print("The matrix D: ")
print([N^((alphaA-S[i].a)*alpha + (alphaB - S[i].b)) for i in range(len(S))])
B = Matrix(ZZ, Matrix(cols).T(**kw)) * diagonal_matrix(ZZ, D)
L = B.LLL(0.5)
v = Matrix(ZZ, L[0])
x = v * B**(-1)
phi = int(x[0,1]/x[0,0]*elist[0])
return phi
def attack(NN, elist, alpha):
for i in range(1, len(elist)+1):
var("e%d" % i)
var("d%d" % i)
var("k%d" % i)
g, N, s = var('g'), var('N'), var('s')
phi = EWA(len(elist), elist, NN, alpha)
return phi
def example(N,e):
from Crypto.Util.number import long_to_bytes, getPrime, bytes_to_long
import uuid
def rsa(e, n):
m = uuid.uuid4().hex.encode()
c = pow(bytes_to_long(m), e, n)
return m.decode(), c
# p = getPrime(1024)
# q = getPrime(1024)
# The modulus in RSA
NN = N
# The exponent in RSA
# e = 0x10001
# m, c = rsa(e, NN)
# print("The plaintext is:", m)
# Theoretical upper bound in paper, but it is much smaller when actual test
alpha = calcAlpha(3)
print("Alpha: ",alpha)
elist = e
phi = attack(NN, elist, alpha)
if phi != 0:
print("Found Phi: ", phi)
return phi
N=...
n=N
e=[...]
c=...
phi=example(N,e)
d=inverse(65537,ZZ(phi))
long_to_bytes(ZZ(power_mod(c, d, n)))
ez_LargeCG
from gmpy2 import next_prime
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import random
from secret import flag
def init():
primes = []
p = 1
while len(primes) < 100:
p = next_prime(p)
primes.append(int(p))
return primes
def genMyPrimeA(bits):
while True:
g = 2
while g < 2 ** bits:
g *= random.choice(primes)
g += 1
if isPrime(g):
return g
def genMyPrimeB(bits):
while True:
g = 2
while g < 2 ** bits:
g *= random.choice(primes)
g -= 1
if isPrime(g):
return g
def gen(st, n, a, b, c, d):
A = [st + 2023, st + 2024, st + 2025]
for i in range(6**666):
A.append((a * A[-3] + b * A[-2] + c * A[-1] + d) % n)
return A
primes = init()
p1 = getPrime(256)
print(p1)
q1 = 1
while p1 > q1:
q1 = genMyPrimeA(256)
print(q1)
p2 = getPrime(256)
q2 = 1
while p2 > q2:
q2 = genMyPrimeB(256)
n1 = p1 * q1
n2 = p2 * q2
print(f'n1 = {n1}')
print(f'n2 = {n2}')
r = getPrime(512)
print(f'r = {r}')
A = gen(bytes_to_long(flag), r, p1, q1, p2, q2)
print(f'A[-3] = {A[-3]}')
print(f'A[-2] = {A[-2]}')
print(f'A[-1] = {A[-1]}')
# n1 = 39755206609675677517559022219519767646524455449142889144073217274247893104711318356648198334858966762944109142752432641040037415587397244438634301062818169
# n2 = 30725253491966558227957591684441310073288683324213439179377278006583428660031769862224980605664642101191616868994066039054762100886678504154619135365646221
# r = 7948275435515074902473978567170931671982245044864706132834233483354166398627204583162848756424199888842910697874390403881343013872330344844971750121043493
# A[-3] = 6085327340671394838391386566774092636784105046872311226269065664501131836034666722102264842236327898770287752026397099940098916322051606027565395747098434
# A[-2] = 1385551782355619987198268805270109182589006873371541520953112424858566073422289235930944613836387546298080386848159955053303343649615385527645536504580787
# A[-1] = 2529291156468264643335767070801583140819639532551726975314270127875306069067016825677707064451364791677536138503947465612206191051563106705150921639560469
涉及到光滑数、矩阵快速幂。
对于n1，通过分析q的生成过程，可以知道是p-1光滑；对于n2，可以知道是p+1光滑，可以分别分解得到因数：
from gmpy2 import *
def Pollard(n):
a=2
while True:
for i in range(2,80000):
a=pow(a,i,n)
for j in range(80000,104729+1):
a=pow(a,j,n)
if j % 15 ==0:
d = gcd(a-1,n)
if(1<d<n):
return(d)
a+=1
n1 = 39755206609675677517559022219519767646524455449142889144073217274247893104711318356648198334858966762944109142752432641040037415587397244438634301062818169
q1 = Pollard(n1)
p1 = n1 // q1
print(p1,q1)
#p1 = 92946439027877993602295703905130336736159270745389239059083263513478865293549
#q1 = 427721675251610827084310512123962488210068003845592404231631542730839819224381
#p2=288551157776490110472645044398395422160196115791981535735903775378294599329633
#q2=106481130516780473105954611077340189174861459077145246394800660809527032990637
def gen(st, n, a, b, c, d):
A = [st + 2023, st + 2024, st + 2025]
for i in range(6**666):
A.append((a * A[-3] + b * A[-2] + c * A[-1] + d) % n)
return A
接着通过分析gen函数，四阶LCG问题，构建矩阵：
$A =
\left[
\begin{matrix}
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0 \
a & b & c & d \
0 & 0 & 0 & 1
\end{matrix}
\right]
\Rightarrow A*
\left(
\begin{matrix}
s_1 \
s_2 \
s_3 \
1
\end{matrix}
\right) =
\left(
\begin{matrix}
s_2 \
s_3 \
s_4 \
1
\end{matrix}
\right)$
a = q1
b = p1
c = q2
d = p2
r = 7948275435515074902473978567170931671982245044864706132834233483354166398627204583162848756424199888842910697874390403881343013872330344844971750121043493
s1 = 6085327340671394838391386566774092636784105046872311226269065664501131836034666722102264842236327898770287752026397099940098916322051606027565395747098434
s2 = 1385551782355619987198268805270109182589006873371541520953112424858566073422289235930944613836387546298080386848159955053303343649615385527645536504580787
s3 = 2529291156468264643335767070801583140819639532551726975314270127875306069067016825677707064451364791677536138503947465612206191051563106705150921639560469
S = Vector(GF(r),[s1,s2,s3,1])
A = matrix(GF(r),[[0,1,0,0],[0,0,1,0],[a,b,c,d],[0,0,0,1]])
flag = A^(-6^666)*S
print(long_to_bytes(ZZ(flag[0]-2023)))
#NKCTF{y0u_kN0w_r5A_&_LCg_&_Ma7r1X_s0_w3ll!!!}
参考：2023 nkctf crypto wp - App1e_Tree - 博客园 (cnblogs.com)
(1条消息) NKCTF2023 Crypto 部分wp_无趣的浅的博客-CSDN博客
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com