2024-Hgame-week3-wp-crypto

前两周事情不少就没有来打这个比赛，就从第三周开始简单写写题解。

matrix_equation

题目描述：

先走一步，再走一步

题目：

from Crypto.Util.number import *
import hashlib
from secret import p,q,r
k1=getPrime(256)
k2=getPrime(256)
temp=p*2**256+q*k1+r*k2
hint=len(bin(temp)[2:])
flag='hgame{'+hashlib.sha256(str(p+q+r).encode()).hexdigest()+'}'
print(f'hint={hint}')
print(f'k1={k1}')
print(f'k2={k2}')
"""
83
k1=73715329877215340145951238343247156282165705396074786483256699817651255709671
k2=61361970662269869738270328523897765408443907198313632410068454223717824276837
"""

题目给出一个表达式，以及其中k1、k2的值：

$temp = 2^{256}p + k_1q + k_2r$

但是temp并没有给我们，只给了他的数量级是83bit，要求求出p、q、r的和的sha256来作为flag提交。

由于k1、k2、2^256都是256bit的数量级，所以temp的83bit显得很小，就自然联想到用格来求解。也就自然造出了如下格：

$\left( \begin{matrix} 1&&&&2^{256}\\ &1&&&k_1\\ &&1&&k_2\\ &&&1&-1\\ \end{matrix} \right)$

这个格的线性关系是：

$(p,q,r,temp) \left( \begin{matrix} 1&&&&2^{256}\\ &1&&&k_1\\ &&1&&k_2\\ &&&1&-1\\ \end{matrix} \right) = (p,q,r,temp,0)$

依然需要给最后一列配上一个大系数来保证规约出0，然而还有个小问题，就是p、q、r的数量级并不知道，所以前面的配平还不太好弄，如果规约不出的话还需要小爆一下。但是实际上规约后的第一行就是目标向量了。

后面知道还放了个hint说p、q、r数量级都和temp差不多，所以并不需要刻意去配。由于有了这个条件，那么其实p+q+r的数量级也和temp相近，并且注意到题目只需要p、q、r的和，所以其实还可以给格加上一列：

$\left( \begin{matrix} 1&&&&2^{256}&1\\ &1&&&k_1&1\\ &&1&&k_2&1\\ &&&1&-1&\\ \end{matrix} \right)$

这样就能直接在目标向量的最后一列得到p、q、r的和，需要注意的是依然需要取出temp，通过它的长度来判断和的正负。然后会发现似乎答案正负号反了？不过也不重要，就把另一个交上去就行。

exp：

import hashlib
from Crypto.Util.number import *

T = 2^83
k1 = 73715329877215340145951238343247156282165705396074786483256699817651255709671
k2 = 61361970662269869738270328523897765408443907198313632410068454223717824276837
L = Matrix(ZZ,4,6)

T = 2^200
for i in range(4):
    L[i,i] = 1
L[0,-2] = 2^256*T
L[1,-2] = k1*T
L[2,-2] = k2*T
L[3,-2] = -1*T
for i in range(3):
    L[i,-1] = 1
res = L.LLL()[0]
temp = res[3]

if(len(bin(temp)[2:]) == 83):
    sum1 = res[-1]
else:
    sum1 = -res[-1]

flag='hgame{'+hashlib.sha256(str(-sum1).encode()).hexdigest()+'}'
print(flag)

#right is hgame{b8dacfa6e47241cb04f5e15e3a39e32fa18d7265f95d124176c83e5abc7ba855}
#but seems to be hgame{3633c16b1e439d8db5accc9f602f2e821a66e6d80a412e45eb3e1048dffbb0e2}

exRSA

题目描述：

RRRSA

题目：

from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getStrongPrime(1024)
q=getStrongPrime(1024)
phi=(p-1)*(q-1)
e1=inverse(getPrime(768),phi)
e2=inverse(getPrime(768),phi)
e3=inverse(getPrime(768),phi)
n=p*q
c=pow(m,0x10001,n)
print(f'e1={e1}')
print(f'e2={e2}')
print(f'e3={e3}')
print(f'c={c}')
print(f'n={n}')

"""
e1=5077048237811969427473111225370876122528967447056551899123613461792688002896788394304192917610564149766252232281576990293485239684145310876930997918960070816968829150376875953405420809586267153171717496198336861089523701832098322284501931142889817575816761705044951705530849327928849848158643030693363143757063220584714925893965587967042137557807261154117916358519477964645293471975063362050690306353627492980861008439765365837622657977958069853288056307253167509883258122949882277021665317807253308906355670472172346171177267688064959397186926103987259551586627965406979118193485527520976748490728460167949055289539
e2=12526848298349005390520276923929132463459152574998625757208259297891115133654117648215782945332529081365273860316201130793306570777735076534772168999705895641207535303839455074003057687810381110978320988976011326106919940799160974228311824760046370273505511065619268557697182586259234379239410482784449815732335294395676302226416863709340032987612715151916084291821095462625821023133560415325824885347221391496937213246361736361270846741128557595603052713612528453709948403100711277679641218520429878897565655482086410576379971404789212297697553748292438183065500993375040031733825496692797699362421010271599510269401
e3=12985940757578530810519370332063658344046688856605967474941014436872720360444040464644790980976991393970947023398357422203873284294843401144065013911463670501559888601145108651961098348250824166697665528417668374408814572959722789020110396245076275553505878565603509466220710219260037783849276475397283421068716088638186994778153542817681963059581651103563578804145156157584336712678882995685632615686853980176047683326974283896343322981521150211317597571554542488921290158122634140571148036732893808064119048328855134054709120877895941670166421664806186710346824494054783025733475898081247824887967550418509038276279
c=1414176060152301842110497098024597189246259172019335414900127452098233943041825926028517437075316294943355323947458928010556912909139739282924255506647305696872907898950473108556417350199783145349691087255926287363286922011841143339530863300198239231490707393383076174791818994158815857391930802936280447588808440607415377391336604533440099793849237857247557582307391329320515996021820000355560514217505643587026994918588311127143566858036653315985177551963836429728515745646807123637193259859856630452155138986610272067480257330592146135108190083578873094133114440050860844192259441093236787002715737932342847147399
n=17853303733838066173110417890593704464146824886316456780873352559969742615755294466664439529352718434399552818635352768033531948009737170697566286848710832800426311328560924133698481653594007727877031506265706341560810588064209681809146597572126173303463125668183837840427667101827234752823747483792944536893070188010357644478512143332014786539698535220139784440314481371464053954769822738407808161946943216714729685820896972467020893493349051243983390018762076812868678098172416465691550285372846402991995794349015838868221686216396597327273110165922789814315858462049706255254066724012925815100434953821856854529753
"""

三组低解密指数的情况，用的是扩展的wiener攻击，wiki上对于原理介绍的很清晰就不在这里展开了，可以参考：

扩展维纳攻击 - CTF Wiki (ctf-wiki.org)

然后拿la佬博客里的板子打就可以：

RSA | Lazzaro (lazzzaro.github.io)

exp：

from Crypto.Util.number import *
import gmpy2

e1=5077048237811969427473111225370876122528967447056551899123613461792688002896788394304192917610564149766252232281576990293485239684145310876930997918960070816968829150376875953405420809586267153171717496198336861089523701832098322284501931142889817575816761705044951705530849327928849848158643030693363143757063220584714925893965587967042137557807261154117916358519477964645293471975063362050690306353627492980861008439765365837622657977958069853288056307253167509883258122949882277021665317807253308906355670472172346171177267688064959397186926103987259551586627965406979118193485527520976748490728460167949055289539
e2=12526848298349005390520276923929132463459152574998625757208259297891115133654117648215782945332529081365273860316201130793306570777735076534772168999705895641207535303839455074003057687810381110978320988976011326106919940799160974228311824760046370273505511065619268557697182586259234379239410482784449815732335294395676302226416863709340032987612715151916084291821095462625821023133560415325824885347221391496937213246361736361270846741128557595603052713612528453709948403100711277679641218520429878897565655482086410576379971404789212297697553748292438183065500993375040031733825496692797699362421010271599510269401
e3=12985940757578530810519370332063658344046688856605967474941014436872720360444040464644790980976991393970947023398357422203873284294843401144065013911463670501559888601145108651961098348250824166697665528417668374408814572959722789020110396245076275553505878565603509466220710219260037783849276475397283421068716088638186994778153542817681963059581651103563578804145156157584336712678882995685632615686853980176047683326974283896343322981521150211317597571554542488921290158122634140571148036732893808064119048328855134054709120877895941670166421664806186710346824494054783025733475898081247824887967550418509038276279
c=1414176060152301842110497098024597189246259172019335414900127452098233943041825926028517437075316294943355323947458928010556912909139739282924255506647305696872907898950473108556417350199783145349691087255926287363286922011841143339530863300198239231490707393383076174791818994158815857391930802936280447588808440607415377391336604533440099793849237857247557582307391329320515996021820000355560514217505643587026994918588311127143566858036653315985177551963836429728515745646807123637193259859856630452155138986610272067480257330592146135108190083578873094133114440050860844192259441093236787002715737932342847147399
N=17853303733838066173110417890593704464146824886316456780873352559969742615755294466664439529352718434399552818635352768033531948009737170697566286848710832800426311328560924133698481653594007727877031506265706341560810588064209681809146597572126173303463125668183837840427667101827234752823747483792944536893070188010357644478512143332014786539698535220139784440314481371464053954769822738407808161946943216714729685820896972467020893493349051243983390018762076812868678098172416465691550285372846402991995794349015838868221686216396597327273110165922789814315858462049706255254066724012925815100434953821856854529753


alpha2 = 768/2048
M1 = int(gmpy2.mpz(N)**(3./2))
M2 = int( gmpy2.mpz(N) )
M3 = int(gmpy2.mpz(N)**(3./2 + alpha2))
M4 = int( gmpy2.mpz(N)**(0.5) )
M5 = int( gmpy2.mpz(N)**(3./2 + alpha2) )
M6 = int( gmpy2.mpz(N)**(1.+alpha2) )
M7 = int( gmpy2.mpz(N)**(1.+alpha2) )
D = diagonal_matrix(ZZ, [M1, M2, M3, M4, M5, M6, M7, 1])
B = Matrix(ZZ, [ [1, -N,   0,  N**2,   0,      0,      0,    -N**3],
                [0, e1, -e1, -e1*N, -e1,      0,   e1*N,  e1*N**2],
                [0,  0,  e2, -e2*N,   0,   e2*N,      0,  e2*N**2],
                [0,  0,   0, e1*e2,   0, -e1*e2, -e1*e2, -e1*e2*N],
                [0,  0,   0,     0,  e3,  -e3*N,  -e3*N,  e3*N**2],
                [0,  0,   0,     0,   0,  e1*e3,      0, -e1*e3*N],
                [0,  0,   0,     0,   0,      0,  e2*e3, -e2*e3*N],
                [0,  0,   0,     0,   0,      0,      0, e1*e2*e3] ]) * D

L = B.LLL()

v = Matrix(ZZ, L[0])
x = v * B**(-1)
phi_ = (e1*x[0,1]/x[0,0]).floor()
d = inverse_mod(65537, phi_)
print(long_to_bytes(int(pow(c,d,N))))

#hgame{Ext3ndin9_W1en3r's_att@ck_1s_so0o0o_ea3y}

HNP

题目描述：

1	hidden number problem

题目：

from Crypto.Util.number import *
from secret import flag

def encrypt(m,p,t):
    return [(ti*m)%p for ti in t]

m=bytes_to_long(flag[:63])
length=m.bit_length()+8
p=getStrongPrime(length)
n=32
t=[getRandomRange(0,p) for _ in range(n)]
enc=encrypt(m,p,t)
res=[i%(2**n+1) for i in enc]

print(f'p={p}')
print(f't={t}')
print(f'res={res}')

"""
p=11306299241774950053269547103284637414407835125777245204069367567691021928864773207548731051592853515206232365901169778048084146520829032339328263913558053
t=[3322008555255129336821309701482996933045379792432532251579564581211072677403244970423357912298444457457306659801200188166569132560659008356952740599371688, 8276764260264858811845211578415023343942634613522088631021199433066924291049858607045960690574035761370394263154981351728494309737901121703288822616367266, 9872291736922974456420418463601129094227231979218385985149661132792467621940722580745327835405374826293791332815176458750548942757024017382881517284991646, 4021521745142535813153669961146457406640791935844796005344073886289668464885011415887755787903927824762833158130615018326666118383128627535623639046817799, 24569151076141700493541155834378165089870615699969211988778938492838766214386066952596557490584021813819164202001474086538804476667616708172536787956586, 3218501156520848572861458831123822689702035242514803505049101779996231750875036344564322600086861361414609201214822262908428091097382781770850929067404210, 3563405987398375076327633444036492163004958714828685846202818610320439306396912425420391070117069875583786819323173342951172594046652017297552813501557159, 4914709045693863038598225124534515048993310770286105070725513667435983789847547225180024824321458761262390817487861675595466513538901373422149236133926354, 10800566112999947911006702454427389510409658644419749067440812458744391509925306994806187389406032718319773665587324010542068486131582672363925769248595266, 623364920052209790798128731089194813138909691039137935275037339503622126325928773037501254722851684318024014108149525215083265733712809162344553998427324, 4918421097628430613801265525870561041230011029818851291086862970508621529074497601678774921285912745589840510459677522074887576152015356984592589649844431, 7445733357215847370070696136653689748718028080364812263947785747353258936968978183471549706166364243148972154215055224857918834937707555053246184822095602, 9333534755049225627530284249388438694002602645047933865453159836796667198966058177988500184073454386184080934727537200575457598976121667373801441395932440, 5010854803179970445838791575321127911278311635230076639023411571148488903400610121248617307773872612743228998892986200202713496570375447255258630932158822, 6000645068462569819648461070140557521144801013490106632356836325002546400871463957228581143954591005398533252218429970486115490535584071786260818773166324, 8007260909124669381862034901556111245780505987082990804380814797200322228942432673939944693062470178256867366602331612363176408356304641672459456517978560, 10179739175373883376929532026389135792129233730601278687507041429438945598523995700184622359660605910932803141785598758326254886448481046307666042835829725, 8390072767717395701926289779433055672863880336031837009119103448675232362942223633129328309118158273835961567436591234922783953373319767835877266849545292, 7875011911562967874676113680693929230283866841475641162854665293111344467709424408623198370942797099964625447512797138192853009126888853283526034411007513, 5293772811020012501020124775214770193234655210319343058648675411115210453680753070042821835082619634341500680892323002118953557746116918093661769464642068, 2613797279426774540306461931319193657999892129844832159658771717387120246795689678231275371499556522396061591882431426310841974713419974045883021613987705, 9658126012133217804126630005236073513485215390812977974660029053522665282550965040288256074945246850744694519543358777252929661561636241161575937061521711, 2982535220844977621775139406357528876019349385634811795480230677982345697183586203669094998039995683973939721644887543907494963824968042199353945120367505, 107289984878191849357180490850397539311037762262082755398160292401340078782643246498566039415279868796667596686125847400130898160017838981308638814854641, 120993130590874228473811314869823704699012435303134640953201808807618070048912918046616664677916248813062043597607873728870402493717351447905456920806865, 2253040652771796284266254261719805768102740653097446325869783812201171144150768875885963729324915714812719138247784194752636928267712344736198611708630089, 8650007272154283057350664311505887535841268767424545016901418989555620869091145651216448723200240914143882774616678968725523914310965356875681207295242434, 9628747829107584650014156079928108801687158029086221730883999749044532846489666115473993005442192859171931882795973774131309900021287319059216105939670757, 10846936951522093706092027908131679912432689712451920718439096706435533926996215766191967052667966065917006691565771695772798711202812180782901250249613072, 1606865651227988736664127021678689299989045439998336603562232908863405778474520915170766771811336319655792746590981740617823564813573118410064976081989237, 6239063657591721097735049409610872941214078699330136826592958549212481802973973104374548555184907929255031570525343007518434357690480429981016781110249612, 1855365916387114620581029939707053701062476745235578683558063796604744448050278138954359506922875967537567359575662394297579958372107484276360920567730458]
res=[2150646508, 1512876052, 2420557546, 2504482055, 892924885, 213721693, 2708081441, 1242578136, 717552493, 3210536920, 2868728798, 1873446451, 645647556, 2863150833, 2481560171, 2518043272, 3183116112, 3032464437, 934713925, 470165267, 1104983992, 194502564, 1621769687, 3844589346, 21450588, 2520267465, 2516176644, 3290591307, 3605562914, 140915309, 3690380156, 3646976628]
"""

题目给出了32组等式：

$c_i = t_im \quad(mod\;p) \quad(mod\;2^{32}+1)$

其中唯一不知道的数是大小为63字节的m，要求解出m来。

既然明明白白说是HNP了，那就把模等式先展开成等式，得到：

$c_i = t_im +r_ip + s_i(2^{32}+1)$

注意到，由于先模p再模2^32+1，所以系数si其实是一个小量，其期望数量级是511bit(p//2的数量级)减去32bit。这也就是说，目标向量里可以出现的是m和si两个小量，然后就造出如下格：

$\left( \begin{matrix} 1&&t_1&t_2&\cdots&t_{32}\\ &1&-c_1&-c_2&\cdots&-c_{32}\\ &&p\\ &&&p\\ &&&&\ddots\\ &&&&&p\\ &&2^{32}+1&&&&1\\ &&&2^{32}+1&&&&1\\ &&&&\ddots&&&&\ddots\\ &&&&&2^{32}+1&&&&1\\ \end{matrix} \right)$

这个格具有的线性关系是：

$(m,1,r_1,r_2,...,r_{32},s_1,s_2,...,s_{32}) \left( \begin{matrix} 1&&t_1&t_2&\cdots&t_{32}\\ &1&-c_1&-c_2&\cdots&-c_{32}\\ &&p\\ &&&p\\ &&&&\ddots\\ &&&&&p\\ &&2^{32}+1&&&&1\\ &&&2^{32}+1&&&&1\\ &&&&\ddots&&&&\ddots\\ &&&&&2^{32}+1&&&&1\\ \end{matrix} \right) = (m,1,0,0,...,0,s_1,s_2,...,s_{32})$

然后就是中间配上大系数，保证规约出0，并且配平就好。

exp：

from Crypto.Util.number import *

p=11306299241774950053269547103284637414407835125777245204069367567691021928864773207548731051592853515206232365901169778048084146520829032339328263913558053
t=[3322008555255129336821309701482996933045379792432532251579564581211072677403244970423357912298444457457306659801200188166569132560659008356952740599371688, 8276764260264858811845211578415023343942634613522088631021199433066924291049858607045960690574035761370394263154981351728494309737901121703288822616367266, 9872291736922974456420418463601129094227231979218385985149661132792467621940722580745327835405374826293791332815176458750548942757024017382881517284991646, 4021521745142535813153669961146457406640791935844796005344073886289668464885011415887755787903927824762833158130615018326666118383128627535623639046817799, 24569151076141700493541155834378165089870615699969211988778938492838766214386066952596557490584021813819164202001474086538804476667616708172536787956586, 3218501156520848572861458831123822689702035242514803505049101779996231750875036344564322600086861361414609201214822262908428091097382781770850929067404210, 3563405987398375076327633444036492163004958714828685846202818610320439306396912425420391070117069875583786819323173342951172594046652017297552813501557159, 4914709045693863038598225124534515048993310770286105070725513667435983789847547225180024824321458761262390817487861675595466513538901373422149236133926354, 10800566112999947911006702454427389510409658644419749067440812458744391509925306994806187389406032718319773665587324010542068486131582672363925769248595266, 623364920052209790798128731089194813138909691039137935275037339503622126325928773037501254722851684318024014108149525215083265733712809162344553998427324, 4918421097628430613801265525870561041230011029818851291086862970508621529074497601678774921285912745589840510459677522074887576152015356984592589649844431, 7445733357215847370070696136653689748718028080364812263947785747353258936968978183471549706166364243148972154215055224857918834937707555053246184822095602, 9333534755049225627530284249388438694002602645047933865453159836796667198966058177988500184073454386184080934727537200575457598976121667373801441395932440, 5010854803179970445838791575321127911278311635230076639023411571148488903400610121248617307773872612743228998892986200202713496570375447255258630932158822, 6000645068462569819648461070140557521144801013490106632356836325002546400871463957228581143954591005398533252218429970486115490535584071786260818773166324, 8007260909124669381862034901556111245780505987082990804380814797200322228942432673939944693062470178256867366602331612363176408356304641672459456517978560, 10179739175373883376929532026389135792129233730601278687507041429438945598523995700184622359660605910932803141785598758326254886448481046307666042835829725, 8390072767717395701926289779433055672863880336031837009119103448675232362942223633129328309118158273835961567436591234922783953373319767835877266849545292, 7875011911562967874676113680693929230283866841475641162854665293111344467709424408623198370942797099964625447512797138192853009126888853283526034411007513, 5293772811020012501020124775214770193234655210319343058648675411115210453680753070042821835082619634341500680892323002118953557746116918093661769464642068, 2613797279426774540306461931319193657999892129844832159658771717387120246795689678231275371499556522396061591882431426310841974713419974045883021613987705, 9658126012133217804126630005236073513485215390812977974660029053522665282550965040288256074945246850744694519543358777252929661561636241161575937061521711, 2982535220844977621775139406357528876019349385634811795480230677982345697183586203669094998039995683973939721644887543907494963824968042199353945120367505, 107289984878191849357180490850397539311037762262082755398160292401340078782643246498566039415279868796667596686125847400130898160017838981308638814854641, 120993130590874228473811314869823704699012435303134640953201808807618070048912918046616664677916248813062043597607873728870402493717351447905456920806865, 2253040652771796284266254261719805768102740653097446325869783812201171144150768875885963729324915714812719138247784194752636928267712344736198611708630089, 8650007272154283057350664311505887535841268767424545016901418989555620869091145651216448723200240914143882774616678968725523914310965356875681207295242434, 9628747829107584650014156079928108801687158029086221730883999749044532846489666115473993005442192859171931882795973774131309900021287319059216105939670757, 10846936951522093706092027908131679912432689712451920718439096706435533926996215766191967052667966065917006691565771695772798711202812180782901250249613072, 1606865651227988736664127021678689299989045439998336603562232908863405778474520915170766771811336319655792746590981740617823564813573118410064976081989237, 6239063657591721097735049409610872941214078699330136826592958549212481802973973104374548555184907929255031570525343007518434357690480429981016781110249612, 1855365916387114620581029939707053701062476745235578683558063796604744448050278138954359506922875967537567359575662394297579958372107484276360920567730458]
res=[2150646508, 1512876052, 2420557546, 2504482055, 892924885, 213721693, 2708081441, 1242578136, 717552493, 3210536920, 2868728798, 1873446451, 645647556, 2863150833, 2481560171, 2518043272, 3183116112, 3032464437, 934713925, 470165267, 1104983992, 194502564, 1621769687, 3844589346, 21450588, 2520267465, 2516176644, 3290591307, 3605562914, 140915309, 3690380156, 3646976628]

T = 2^(63*8)
K = 2^1000
L = Matrix(ZZ,2*len(res)+2,2*len(res)+2)
L[0,0] = 1
L[1,1] = 1
for i in range(len(res)):
    L[0,i+2] = t[i]
    L[1,i+2] = -res[i]
    L[i+2,i+2] = p
    L[i+len(res)+2,i+2] = (2^32+1)
    L[i+len(res)+2,i+len(res)+2] = 1
Q = diagonal_matrix([1] + [T] + [K]*len(res) + [2^24]*len(res))
L = L * Q
L = L.LLL()
L = L / Q
print(long_to_bytes(abs(int(L[0][0]))))

#hgame{H1dd3n_Numb3r_Pr0bl3m_has_diff3rent_s1tuati0n}