little_hnp

根据题目描述中的hnp可知，这是一个隐藏数问题，实际上这个形式来源于2022高校密码数学挑战赛。本题需要解一个aes，密钥来自于secret x y z，那么需要通过三种不同的hnp攻击方法获得xyz。

1.获取x

题目给出了若干组如下形式的方程：

但只泄露了 的高8位，格子的思路如下：

题目所给32组数据刚好能够规约出结果，BKZ优于LLL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# part1
A = [3561678147813669042672186969104055553515262226168087322052560790885260761433, 17346407693442644010055116546363960164095133759884497841925887458500171929994, 10970839811545507511408260800883769581649579684426188079142754412064502787585, 109417222922540235139013912297145185193443712852193270682885305502867182588403, 88171850234002600580608014259219586239590114856448092326801813245774395730496, 5113619435362108938262679062561727235116615800676783173565082653599747645155, 54576089683044230333058389148818602636893918880220233916359714009830588044131, 46319652232696496987147414399965164805770427009639155019904825551069668519260, 92142202700489403870481152403139465532735056770434774464930082474517829581964, 9084526539780165183228300902059842905058839285187659313361650962576085292818, 89120115360204223476154240731792191817638074392691790750005020564226279037550, 108874944765319253896194176909539011617418473448207058050594223215460183828033, 48697630410338199345605370644643425030874923782845194702123578264330641464094, 90490831141215467713642375752174358047945797806394912036159392371419919773636, 5407847525945777533863763148921176292074562577253075889320641646783216244238, 95326999116234880776873896438659550308182265903511015349887289749187746932743, 13848646478536701368088661040908693291788138011605835864557858216170511016083, 12688154545015600072136788151484672710661959298941783293908174000377900727747, 103416430654164637952330806792686485956010294787748757584715063906414248209722, 36213989454986448247979083323211284869162879484215027121399406834805531673463, 83477199408920970502661396196378764693640078246444907844363833717275362253336, 54685544287120130615023910691215446521783587675140445694155062634358785975223, 57209914633582227771666953772776413914105217956486621477363100169491699389485, 60722705656546434007907580733214759241271810206392571495455413850603913610651, 62666312072142619643565102615355724228875566515181602729719018682721112131326, 17892029370519322177254795109531838575579273633357811419566887056272012019617, 23387537005911727415991488713130020055341902697712259630978747015670850612866, 57084096974333718635810536400151484653413307540676932220675888461543384910791, 64672020284448913361212245534680048800817888816777270292913433441383929287826, 30879668079119218442051482226185849538064516289533962210948424807374221747937, 67805294126621083377517953883639091568886644480832055617022550683600509359637, 80971248361778969534551851802629859076303703583702628504189145200772632698437]
B = [185, 121, 74, 192, 66, 208, 189, 5, 248, 216, 222, 49, 199, 122, 212, 109, 36, 135, 9, 43, 94, 192, 67, 176, 165, 34, 241, 27, 255, 216, 71, 156]

def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            if BB[ii, jj] == 0:
                a += ' '
            else:
                a += 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

m = 256
s = 8
AAA = [x for x in A]
BBB = [x for x in B]

A = [x for x in AAA]
B = [x for x in BBB]
#B = [x << (m-s) for x in B]
B = [(x << (m-s)) + (1 << (m-s-1)) for x in B]
assert len(A) == len(B)
q = 2^m

n = len(A)-1

AA = [x for x in A]
BB = [x for x in B]
for choice in range(n):
    A = [x for x in AA]
    B = [x for x in BB]
    if A[choice] % 2 != 1:
        continue
    A0 = A[choice]
    A0i = A0.inverse_mod(q)
    B0 = B[choice]
    del A[choice]
    del B[choice]
    assert gcd(A0, q) == 1
    Mt = matrix(ZZ, n+2)
    for i in range(n):
        Mt[i, i]  = -q
        Mt[-2, i] = A0i*A[i] % q
        Mt[-1, i] = A0i*(A[i]*B0 - A0*B[i]) % q
    Mt[-2, -2] = 1
    R = 2^(m-s-1)
    Mt[-1, -1] = R

    L = Mt.BKZ()
    for l in L:
        if l[-1] == R:
            b = vector(l)
            b0 = b[-2]

            x0 = (B0+b0) * A0.inverse_mod(q) % q
            test1 = [bi >> (m-s) for bi in B] 
            test2 = [(ai*x0 % q) >> (m-s) for ai in A]
            if test1 == test2:
                print('get: %d' % x0)
    break

2.获取y

这部分是泄露了低8位，所以算式会稍微有些区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# part2
q = 115792089237316195423570985008687907853269984665640564039457584007913129639747
A = [46504565744057869379592149118750005180204315285587793650459698458291497313095, 58007957093934046182693035826219870499452741234326847327688846747059237094075, 50185124619087453830679170251457196445767905313509337058697814870412730362947, 13460057838246434192804076595664204927155595158673092664009965681276162112064, 1701081975560116286696366369808334022446618430663926380667987754925635360535, 26884871731419084105623632272724863769910293366201375037286643905133449526668, 86148369125917615329995354501659454507150263427394081644953922899405044908942, 86965847264933041291798488655625963084424620038983026175910367027955449692128, 51359332101276868450990110421905601457823984827989287103931757850844231666586, 48796757902016638482644909388959646721244669665114474829651238484065619118952, 100070448202859232758452766870542683109402601193511866026529530855112793822109, 96580256984898125874774601478072811945116066886633284314860596683569097605765, 38808894076998102467847013020946201384521577320197543440467015636483307894892, 4134554141092625841029701614640247691101835437566908306546904884177729072687, 74873085435488619613395208820994521773265984299598688734149106712561237976724, 15654842239708870234259249156913701671624803564647865424705391694462101457862, 88322093034453332197643606249439750127876581478584569790806716889277489637972, 22499556277754006237442593359493863007223009260764163505327306701416065559119, 67089035688878297307085968283413144678391442218184879365509351597884743967932, 27674630243557284124557851587722479960748242794492773619925160133318279977692, 9119521864491019262790789925266797995577993021425216600126182732190292182948, 101288882073195598657612116292233377922026161322404160341330451374348438098216, 67804446744028818432860934046262550895247933787912806120088242004054790700495, 26086948144209799352019678059923693118044934151861294461002114985645656470189, 38144657569843600236424138168852321656171547769351620499893335164030638528328, 29607623036881080673594862278805535156351844098214001235565521439825687173709, 73322408962909922161031457562287596779866102699954700495813418822123077110802, 71841446787131237842866428647552570448973984694577468650052516966413175250298, 1230436323839997562475731649322922330998915952913300933165504728647309839568, 107223013661981482036189531938571461516528131559156846625598018135279924645933, 40439925178577390217639900040814034803597438472158408491211685077053585300286, 26978587850306490903937574562860250724695533954879823140348556476663322417613, 82195886203427304567763311291077205482622324404366375181470500496565215770146]
b = [115, 240, 228, 198, 160, 178, 214, 160, 96, 140, 89, 186, 159, 102, 192, 93, 135, 30, 17, 9, 138, 224, 109, 116, 76, 116, 180, 196, 121, 187, 210, 208, 14]

T = 2^s
Ti = T.inverse_mod(q)

assert len(A) == len(b)
AAA = [x for x in A]
bbb = [x for x in b]

Z = sorted(list(zip(AAA, bbb)), reverse=True)
A = [x[0] for x in Z]
b = [x[1] for x in Z]
S = 2^(m-1)
b = [x + S for x in b]
n = len(A)-1

AA = [x for x in A]
bb = [x for x in b]
for choice in range(n):
    A = [x for x in AA]
    b = [x for x in bb]

    A0 = A[choice]
    A0i = A0.inverse_mod(q)
    b0 = b[choice]
    del A[choice]
    del b[choice]
    assert gcd(A0, q) == 1

    Mt = matrix(ZZ, n+2)
    for i in range(n):
        Mt[i, i]  = -q
        Mt[-2, i] = A0i*A[i] % q
        Mt[-1, i] = A0i*Ti*(A[i]*b0 - A0*b[i]) % q
    Mt[-2, -2] = 1
    R = 2^(m-s-1) + 2^(m-s-2)
    Mt[-1, -1] = R

    L = Mt.BKZ(block_size=Mt.rank())

    for l in L:
        if l[-1] == R:
            B = vector(l)
            B0 = B[-2]
            x0 = (T*B0+b0) * A0i % q
            test1 = [bi for bi in bbb] 
            test2 = [(ai*x0 % q) & ((1<<s) - 1) for ai in AAA]

            if test1 == test2:
                print('get: %d' % x0)
    break

3.获取z

和获取x思路一致，但是每条方程只泄露4个比特，这就导致算式数量增多，也就是矩阵维数会变得很大，所以在规约的时候只能用BKZ并且要调整block_size稍大一点，所以这部分的求解需要用到高性能cpu，否则会很慢，我用的AMD Ryzen 9 7950X这个核心大概需要4分钟，普通笔记本估计要10分钟以上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
m = 256
s = 4
A = [56666422659665306957613341966104139188430887040369382699811066965734652038579, 41608423494025514337106193470276163502869431432921281068110444274310186909892, 95312645577996377489331859379729367791539181995403307071242251663306260824059, 114007089082826788908311397311915638668862713690403097281136795912671634293903, 77470602549297888428039543840134276433567854766634294661906479236200644990851, 67265570384781545307301479187933437206481537999752352862466291209724038113997, 101015220564168271842813302532972922828562060680762307341661161853013181455988, 73596220918173964622453801478597395507613363519777836354319778006747628725943, 80276240092293162850897330969848557221924558822619435206166856373482558821153, 60387041856575123107349887176488814324533329129026453912394888320971261329267, 37588667650535221417005569007639921039223353621264869144904381190769978830432, 30201673227033963823582196954697293400001560479877858941307825349312312395908, 46517796724693810353256110303591718873843585558937781709113232176049614134229, 110476911183528409932385631377040635032167229294859921626233104995069707326026, 33913880276956766352570275848477001195330941450588079882929631222080051897977, 108738411950576541236703456832793461013595057668683247592686862598082364613770, 87211442745029489881514515811064102429019356351722823450170249465088775249507, 39600946693670273230261533720839589755726946308581706825676138619972092199256, 4979886914346369664911891403751631037886315717549974065878536283157637402320, 22272529908653383795002294860870129574984518813560375272257703512940569602004, 100135751785995415247695765442899140606914076750888419237400306294448451415863, 85613534858376605408667291532701284666560850915689941354202786014968649139457, 38496246133430733988750968353732662162312705079114417415163071485082991344590, 55980481790171446152748793757788577465044360548729573345122559743628093363153, 71280277172994137969689292719624075379102489317199533126561191722460505314026, 110446223482446943024326135434573497276437669060614612856002207641927747194266, 16456085922385532110267651711339329146652084370610067373716816178321924748791, 101653629730678493695114228522885120593522618541788967122785214737946157867999, 74467527492811608068163160348674720595757862332879609098404557441577413104820, 41884843126443673947662657085537596879702074001592844509379139860812151553968, 29815687077578101251522932333124915023192910276895021601688368611558697857638, 44840628789800333625015337751638405696233468515566263356197320268202190223769, 102427595787595418722722430130631701884337456325150921017413824991597185452849, 2975107125099035075044003816426206055437890428466365543585422202932381886186, 94699511483779321185024950255977801474453881858185354369860946591141828290326, 31810607567540037649472765223870019465281477418301020106850480432511306591757, 75713781109794200255529510371465092460190607870508383754795316160075282283862, 55429849762380955520557448208384572772400405309708977900727750338226215580736, 71351843550447097631722656769410630908972124288367169285559142896305583201390, 84145371680533342029399999651802676680665442500082991947093355443249540103162, 18059328520840928370924328960454198116073475240703647573736616851363995779497, 83839387396741626377342400188482404639827411621171844172874897800772466334269, 25788978353065311499638204532308969267343091396798096623404684254370926606489, 46416171203559401945669998573205329748734005210989064607057470628982156110053, 42839223735347899899704913105525407073907314464785013094063759450820513757342, 88826657766811054515837039931572449230721258604658317309512814974116100196733, 53796508595019468595537500010909399217450133587528313928622717009905225347437, 56531378551320964008977461547054273860909442858252049481923559030063639435057, 48217679285988263588226655808041000825638438349841115697751615792350031644869, 64424297190010710116212288045994884168253983939992794298642423963632550451160, 46474911280506479688705284230861217499981118516937627597481370505066926962182, 64032029526907010327735757773865326038078238679652707012855320952596919166618, 5529383900219431454017233184818428510888383480088262580036064976358985800985, 69322608357555546086372761692837205200171798855109065251575534608627560525776, 76098979682650954216202311601813089916970156784884278240596741668163729505020, 91674126062289237651839995587104059408995800143522837051179562018281051100557, 90571390404208688843585603192800843878382529323359914123528861146103857760661, 72012664155317843790423022518639753138262519729890141457716216773019826138388, 66863180243825712563555363518892364864799935770917594234609418534062748300787, 5838945753982677965177087293687053018953448675487050703226841119623778529018, 4440280122867898274880560103713163505203269339591832639427292037957483435863, 113585052040012311817152621651926546174704034369418207806360593735979071392560, 96503008028224334771028807273628056037391407459560685791940303889130903300826, 67050454088005224845748627326789053425990922831763041158174139321910165797537, 56354656300386637831392267891729486882144501924180334206591055551662859511145, 108875538744684454340615686969559999736352047181969993978724550037003168200211, 105856150301241056513738964497224079598648612469774416566110150235952602587129, 103072133631485922917570773603973545510240103328265914435430955113182187850847, 105071449786380370702657927006338895312230491406739601631939501577997184496876, 101559564666645844079948496433098525970583827093303201782110972272082979410831, 45696832977481706385123240351386677526237953026854755659089774125668886575190, 92930863035601609905246064160817660898443604755800516139761871009073979122573, 7136157467487063026530735850363136522687472196852313490264738121297870888865, 62220552837071854508303645903133799707167271140998125870619424819338409845248, 71964156627499707284955744986659480338185350890617779236004729406075442337650, 56432954135882530785013240455908855171502152827770214700998108134515682426307, 24818258540494883741910232014072726664585493319546426193565346084848631309292, 68946604449180849807706382163388201284725162066731407078323925073762784383918, 78305860067531640486978712479618549593532447916095131216323237767823095149213, 40019412274222034245452650116905171509558126077504657023971877193155638952620, 6226049816877252622825028481234412013581804081798123571329306780957341285518, 72008834916679466207298598830558721788070004796890262626592503036925690499953, 24120184417962346330989331701326680837413020607663960631051474032512470756250, 106358126840983882959473879360172954895361540456426525458062716824086971706859, 96125062326106069117227627865988038851006615609777159985287487409738006940292, 33054514553432552301350757403482219452773112411443533998213496297361397155535, 41581969631676286214097564630767898944747546622643163224140263014954932195321, 22904365609725269502635057676962583581851475921482302591306344959978794545764, 64290237869656947632842147827818163107378784367086448814380499121557877108860, 30680084243764095315357070546550118749025091482163732007754607769361116153541, 13691292022145271355849518605344621718116294468846185203111794890637243685470, 25132284761110457596793743234989234799586919369754843892751414241493192284491, 12389505381820778753642609476404562621082110924974170017133920070419933455780, 71535924312884292159182314202796515340797288002505186265430063222078901533504, 12742977582401193716850400144097310370558409977576217736024733304490605337769, 75139886864475235332970108571588085544527733256425836467715638485512421268158, 106812400623906721014312287501764424395430875573845869345085033374152396156108, 91345106193584221920864389152087560188260652160092982315871571692181571481755, 65785148879985691725045496265911886841068140761050563941336015575029243383380, 1452703135528066004669796386925101704795733053841911703671961494738444465175, 44818107645190027629062089844645267760294751459286511227307352668787518517867, 26767624780451051554599928370950639364780468287039403780345758419855142782301, 73520682616655688427241752929498638616275480985470608873569998909405046919540]
B = [11, 14, 12, 1, 13, 15, 1, 14, 12, 12, 15, 6, 2, 15, 13, 15, 6, 6, 11, 12, 2, 9, 3, 15, 0, 14, 10, 10, 13, 10, 6, 13, 6, 9, 0, 4, 9, 0, 15, 5, 2, 13, 12, 12, 5, 11, 3, 3, 12, 13, 5, 5, 14, 15, 12, 10, 9, 6, 8, 5, 8, 4, 12, 1, 15, 1, 14, 11, 11, 14, 6, 10, 6, 3, 14, 10, 10, 14, 5, 15, 6, 4, 13, 1, 5, 4, 7, 4, 13, 7, 0, 14, 6, 7, 2, 14, 1, 14, 6, 9, 14, 4, 13]

AAA = [x for x in A]
BBB = [x for x in B]


A = [x for x in AAA]
B = [x for x in BBB]
B = [(x << (m-s)) + randint(0, (1<<(m-s))-1) for x in B]
assert len(A) == len(B)
q = 2^m

n = len(A)-1
AA = [x for x in A]
BB = [x for x in B]
for choice in range(n):
    A = [x for x in AA]
    B = [x for x in BB]
    if A[choice] % 2 != 1:
        continue
    A0 = A[choice]
    A0i = A0.inverse_mod(q)
    B0 = B[choice]
    del A[choice]
    del B[choice]
    assert gcd(A0, q) == 1
    Mt = matrix(ZZ, n+2)
    for i in range(n):
        Mt[i, i]  = -q
        Mt[-2, i] = A0i*A[i] % q
        Mt[-1, i] = A0i*(A[i]*B0 - A0*B[i]) % q
    Mt[-2, -2] = 1
    R = 2^(m-s-1)
    Mt[-1, -1] = R
    
    L = Mt.BKZ(block_size = 28)

    for l in L:
        if l[-1] == R:
            b = vector(l)
            b0 = b[-2]
            x0 = (B0+b0) * A0.inverse_mod(q) % q
            test1 = BBB
            test2 = [(ai*x0 % q) >> (m-s) for ai in AAA]

            if test1 == test2:
                print('get: %d' % x0)
    break

block_size我选取了28，在测试的时候选取25发现出不了，因此再稍微加一点。

4.解AES

1
2
3
4
5
6
7
8
9
10
from Crypto.Cipher import AES
from Crypto.Util.number import *

x = 80894527713686705071002739476859399489995408997139964746730066805048451766071
y = 98898469313641499500896146398219768802603949220366063599597841309427897612653
z = 95734616889198769749359730283416405421230182774636752744567175201992927509949
c = b'\xda\xfc\xb7\x93\xfb\x9d\xbe\x82\xb3\xb5\x87`]}\x0b*\xd53AR\x8bb\xfeQ,\xd9\xff\xf6\n\xa2\x1b)H\\\xf24>E\xac+\x01\xf3)F\x8c\xee\xb8j\x18zb\xa8\x8b\xba\xbc\xbb\x03\xbb}\xb6\x8cO#\xeb\x0c\xce\xbd\x07\x8aWP\x90\xf2\xaep\x02\x11{\xdf\xc5'
key = long_to_bytes(x^y^z)
aes = AES.new(key,mode=AES.MODE_ECB)
print(aes.decrypt(c))