[Crypto学习笔记] 代数类题目
发布时间：
目录
前置概念
希尔伯特不可约性定理
若P上的任意多项式g(x)无法分解多项式f(x): \(f(x) \nmid g(x))\), 则称f(x)是不可约多项式, 也作素多项式, 不可约多项式存在性质如下:
设\(f(x) \in P[x]x\), 若对任意满足\(g(x),f(x) \in P[x]\), 且 $$f(x) g(x)h(x)\(必有\)f(x) g(x)\(或\)f(x) h(x)$$; - 对于\(f(x), g(x) \in P[x]\), 若\((f(x), g(x))=1\), 则称f(x)与g(x)互素 [^不可约多项式]
xctf2024
hide_in_the_ring
题目
from Crypto.Util.number import *
from secret import flag
assert flag.startswith(b"flag{") and flag.endswith(b"}")
assert len(flag) == 45
PR.<x> = PolynomialRing(GF(2))
G = x^256 + x^255 + x^254 + x^251 + x^250 + x^246 + x^245 + x^243 + x^242 + x^240 + x^239 + x^238 + x^236 + x^235 + x^234 + x^233 + x^232 + x^230 + x^229 + x^221 + x^220 + x^218 + x^213 + x^210 + x^208 + x^207 + x^203 + x^200 + x^198 + x^197 + x^194 + x^192 + x^191 + x^190 + x^189 + x^185 + x^184 + x^180 + x^179 + x^178 + x^177 + x^175 + x^174 + x^173 + x^172 + x^171 + x^170 + x^169 + x^167 + x^165 + x^164 + x^161 + x^160 + x^159 + x^157 + x^154 + x^151 + x^149 + x^148 + x^144 + x^142 + x^139 + x^138 + x^137 + x^133 + x^132 + x^130 + x^129 + x^126 + x^125 + x^123 + x^122 + x^120 + x^119 + x^118 + x^117 + x^115 + x^114 + x^113 + x^112 + x^109 + x^108 + x^107 + x^106 + x^105 + x^103 + x^101 + x^99 + x^98 + x^97 + x^94 + x^91 + x^90 + x^89 + x^88 + x^83 + x^82 + x^80 + x^79 + x^73 + x^71 + x^68 + x^67 + x^65 + x^61 + x^59 + x^58 + x^56 + x^55 + x^54 + x^51 + x^49 + x^48 + x^46 + x^44 + x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^34 + x^33 + x^32 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^23 + x^22 + x^15 + x^14 + x^13 + x^12 + x^10 + x^8 + x^7 + x^4 + x^3 + x + 1
assert G.is_irreducible()
PRq = GF(2^256, 'x', modulus = G)
msg = bytes_to_long(flag)
f = 0
i = 0
while(msg != 0):
f += (msg & 1) * x^i
i += 1
msg >>= 1
print(PRq(f))
F = x^249 + x^248 + x^246 + x^244 + x^243 + x^242 + x^239 + x^238 + x^237 + x^232 + x^230 + x^229 + x^228 + x^226 + x^225 + x^223 + x^222 + x^221 + x^220 + x^218 + x^217 + x^215 + x^214 + x^207 + x^206 + x^204 + x^202 + x^201 + x^200 + x^198 + x^197 + x^196 + x^193 + x^191 + x^188 + x^186 + x^185 + x^184 + x^183 + x^177 + x^172 + x^171 + x^170 + x^169 + x^167 + x^166 + x^165 + x^164 + x^162 + x^161 + x^160 + x^158 + x^156 + x^155 + x^154 + x^151 + x^148 + x^146 + x^145 + x^144 + x^143 + x^142 + x^140 + x^139 + x^135 + x^134 + x^132 + x^131 + x^126 + x^122 + x^121 + x^120 + x^119 + x^115 + x^113 + x^110 + x^109 + x^107 + x^106 + x^105 + x^104 + x^103 + x^102 + x^101 + x^100 + x^98 + x^94 + x^93 + x^92 + x^90 + x^89 + x^87 + x^84 + x^81 + x^80 + x^79 + x^77 + x^75 + x^74 + x^71 + x^70 + x^68 + x^67 + x^66 + x^65 + x^64 + x^62 + x^60 + x^59 + x^57 + x^55 + x^54 + x^53 + x^52 + x^51 + x^50 + x^49 + x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^40 + x^39 + x^38 + x^35 + x^34 + x^30 + x^28 + x^27 + x^24 + x^23 + x^20 + x^18 + x^17 + x^16 + x^13 + x^12 + x^11 + x^10 + x^7 + x^5 + x^4 + x^3 + 1
解析
题目主要在一个模为2的多项式环上的多项式G进行运算, 其中多项式G是不可约的[^不可约多项式], 将flag以二进制形式从低到高逐位加给\(n * x^i\).得到多项式F.
要解决问题需要重新构造多项式环, 可以直接抄代码:
EXP
from sage.all import *
from Crypto.Util.number import *
import itertools
from tqdm import tqdm
PR = PolynomialRing(GF(2), 'x')
x = PR.gen()
G = x**256 + x**255 + x**254 + x**251 + x**250 + x**246 + x**245 + x**243 + x**242 + x**240 + x**239 + x**238 + x**236 + x**235 + x**234 + x**233 + x**232 + x**230 + x**229 + x**221 + x**220 + x**218 + x**213 + x**210 + x**208 + x**207 + x**203 + x**200 + x**198 + x**197 + x**194 + x**192 + x**191 + x**190 + x**189 + x**185 + x**184 + x**180 + x**179 + x**178 + x**177 + x**175 + x**174 + x**173 + x**172 + x**171 + x**170 + x**169 + x**167 + x**165 + x**164 + x**161 + x**160 + x**159 + x**157 + x**154 + x**151 + x**149 + x**148 + x**144 + x**142 + x**139 + x**138 + x**137 + x**133 + x**132 + x**130 + x**129 + x**126 + x**125 + x**123 + x**122 + x**120 + x**119 + x**118 + x**117 + x**115 + x**114 + x**113 + x**112 + x**109 + x**108 + x**107 + x**106 + x**105 + x**103 + x**101 + x**99 + x**98 + x**97 + x**94 + x**91 + x**90 + x**89 + x**88 + x**83 + x**82 + x**80 + x**79 + x**73 + x**71 + x**68 + x**67 + x**65 + x**61 + x**59 + x**58 + x**56 + x**55 + x**54 + x**51 + x**49 + x**48 + x**46 + x**44 + x**42 + x**41 + x**40 + x**39 + x**38 + x**37 + x**34 + x**33 + x**32 + x**30 + x**29 + x**28 + x**27 + x**26 + x**25 + x**23 + x**22 + x**15 + x**14 + x**13 + x**12 + x**10 + x**8 + x**7 + x**4 + x**3 + x + 1
assert G.is_irreducible()
PRq = GF(2**256, 'x', modulus = G)
# res = x**255 + x**254 + x**249 + x**247 + x**242 + x**241 + x**240 + x**239 + x**238 + x**232 + x**230 + x**229 + x**226 + x**225 + x**224 + x**223 + x**222 + x**221 + x**220 + x**218 + x**215 + x**211 + x**209 + x**206 + x**205 + x**204 + x**203 + x**202 + x**195 + x**193 + x**191 + x**190 + x**188 + x**184 + x**183 + x**180 + x**179 + x**178 + x**177 + x**174 + x**173 + x**172 + x**171 + x**170 + x**167 + x**166 + x**165 + x**164 + x**160 + x**159 + x**154 + x**152 + x**151 + x**149 + x**148 + x**147 + x**144 + x**142 + x**141 + x**140 + x**138 + x**135 + x**134 + x**130 + x**128 + x**126 + x**124 + x**123 + x**120 + x**118 + x**113 + x**112 + x**110 + x**109 + x**108 + x**106 + x**103 + x**102 + x**100 + x**99 + x**98 + x**97 + x**96 + x**94 + x**93 + x**89 + x**87 + x**86 + x**85 + x**81 + x**78 + x**77 + x**76 + x**74 + x**73 + x**71 + x**69 + x**66 + x**63 + x**62 + x**58 + x**55 + x**51 + x**45 + x**40 + x**38 + x**36 + x**35 + x**34 + x**33 + x**32 + x**31 + x**30 + x**28 + x**26 + x**25 + x**23 + x**21 + x**17 + x**13 + x**12 + x**10 + x**9 + x**8 + x**7 + x**3
res = x**249 + x**248 + x**246 + x**244 + x**243 + x**242 + x**239 + x**238 + x**237 + x**232 + x**230 + x**229 + x**228 + x**226 + x**225 + x**223 + x**222 + x**221 + x**220 + x**218 + x**217 + x**215 + x**214 + x**207 + x**206 + x**204 + x**202 + x**201 + x**200 + x**198 + x**197 + x**196 + x**193 + x**191 + x**188 + x**186 + x**185 + x**184 + x**183 + x**177 + x**172 + x**171 + x**170 + x**169 + x**167 + x**166 + x**165 + x**164 + x**162 + x**161 + x**160 + x**158 + x**156 + x**155 + x**154 + x**151 + x**148 + x**146 + x**145 + x**144 + x**143 + x**142 + x**140 + x**139 + x**135 + x**134 + x**132 + x**131 + x**126 + x**122 + x**121 + x**120 + x**119 + x**115 + x**113 + x**110 + x**109 + x**107 + x**106 + x**105 + x**104 + x**103 + x**102 + x**101 + x**100 + x**98 + x**94 + x**93 + x**92 + x**90 + x**89 + x**87 + x**84 + x**81 + x**80 + x**79 + x**77 + x**75 + x**74 + x**71 + x**70 + x**68 + x**67 + x**66 + x**65 + x**64 + x**62 + x**60 + x**59 + x**57 + x**55 + x**54 + x**53 + x**52 + x**51 + x**50 + x**49 + x**46 + x**45 + x**44 + x**43 + x**42 + x**41 + x**40 + x**39 + x**38 + x**35 + x**34 + x**30 + x**28 + x**27 + x**24 + x**23 + x**20 + x**18 + x**17 + x**16 + x**13 + x**12 + x**11 + x**10 + x**7 + x**5 + x**4 + x**3 + 1
res = PR(res)
flag_0 = b'flag{' + b'\x00' * 39 + b'}'
f_0 = bytes_to_long(flag_0)
f_0 = ZZ(f_0).digits(2)
f_0 = PR(f_0)
Gl = G.list()
n = 8 * 45
m = len(Gl)
A = [[0 for j in range(n-m)] for i in range(n)]
for i in range(m):
for j in range(n-m):
A[i+j][j] = Gl[i]
A = matrix(GF(2), A)
def to_vec(f):
f_list = f.list()
v = vector(GF(2), f_list + [0] * (n - len(f_list)))
return v
v0 = to_vec(res)
v1 = to_vec(f_0)
vdiff = v1 - v0
my_check = [i for i in range(n) \
if (0 <= i < 8) or (i % 8 == 7) or (i >= (39+1)*8)]
Acheck = A[my_check, :]
vdiffcheck = vector(GF(2), [vdiff[i] for i in my_check])
# vdiffcheck = vdiff[my_check]
x0 = Acheck.solve_right(vdiffcheck)
K = Acheck.right_kernel().matrix()
for v in tqdm(itertools.product(range(2), repeat=K.nrows())):
v = vector(GF(2), v)
x = x0 + v * K
v_ = A * x + v0
f_show = ZZ(v_.list(), 2)
f_show_msg = long_to_bytes(int(f_show))
if all(32 <= x < 128 for x in f_show_msg):
print("AOLIGEI!!!", f_show_msg)
pass
# 69318it [00:11, 4720.11it/s]AOLIGEI!!! b'flag{W0W!!_U_r3c0v3r_fl4g_fr0m_qu0ti3nt_Ring}'
# 131072it [00:43, 3025.41it/s]
楚慧杯
qaqtat
再次碰上了小鸡块师傅的题目, 比赛时间1天, 凭个人实力实在无法做出, 故赛后来慢慢复盘.
题目
from Crypto.Util.number import *
from hashlib import sha256
from secret import flag
m = bytes_to_long(flag)
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 = getPrime(256)
Fp2.<i> = GF(p^2, modulus=x^2+1)
M = MatrixSpace(Fp2, 3, 3)
while True:
Q = M.random_element()
A = M.random_element()
if Q*A != A*Q:
break
T = Q*A*Q
S = T*A*T
r1 = randint(0,p-1)
G = Q^r1
pk = (list(A), list(T), list(S), list(G))
ct, F = enc(m, G, A, T, S, p)
print("p = ",p)
print("pk = ", pk)
print("F = ", list(F))
print("ct = ", ct)
"""
p = 72887242108660141996862343556330151015969690949835567252527194788428065480383
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进行两次变换:
\[\begin{matrix} E = Q * A * Q \\ S = T * A * T \end{matrix}\]其中