Hgame_week_2_writeup

CRYPTO

midRSA

题目存在非预期，m0即可解出结果

from Crypto.Util.number import *
m0=13292147408567087351580732082961640130543313742210409432471625281702327748963274496942276607
print(long_to_bytes(m0))

hgame{0ther_cas3s_0f_c0ppr3smith}

midRSA revenge

Coppersmith 攻击,已知明文前几位,可用sagemath中的small_roots进行求解。

from Crypto.Util.number import *

def copper(high_m, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    m = high_m + x
    M = m((m^5 - c).small_roots()[0])
    print((int(M)))

n = 27814334728135671995890378154778822687713875269624843122353458059697288888640572922486287556431241786461159513236128914176680497775619694684903498070577307810263677280294114135929708745988406963307279767028969515305895207028282193547356414827419008393701158467818535109517213088920890236300281646288761697842280633285355376389468360033584102258243058885174812018295460196515483819254913183079496947309574392848378504246991546781252139861876509894476420525317251695953355755164789878602945615879965709871975770823484418665634050103852564819575756950047691205355599004786541600213204423145854859214897431430282333052121
c = 456221314115867088638207203034494636244706611111621723577848729096069230067958132663018625661447131501758684502639383208332844681939698124459188571813527149772292464139530736717619741704945926075632064072125361516435631121845753186559297993355270779818057702973783391589851159114029310296551701456748698914231344835187917559305440269560613326893204748127999254902102919605370363889581136724164096879573173870280806620454087466970358998654736755257023225078147018537101
m0= 9999900281003357773420310681169330823266532533803905637
high_m = m0 << 128
m=copper(high_m, n, c)
print(long_to_bytes(m))

hgame{c0ppr3smith_St3re0typed_m3ssag3s}

backpack

题目存在非预期，由enc即可解出

from Crypto.Util.number import long_to_bytes 
enc=871114172567853490297478570113449366988793760172844644007566824913350088148162949968812541218339
print(long_to_bytes(enc))

hgame{M@ster_0f ba3kpack_m4nag3ment!}

backpack revenge

背包问题，分析代码，发现p的每一位即是否要将对应的a位放入bag，运用LLL算法攻击还原p,sagemath中有LLL算法实现。

import hashlib

a = [74763079510261699126345525979, 51725049470068950810478487507, 47190309269514609005045330671, 64955989640650139818348214927, 68559937238623623619114065917, 72311339170112185401496867001, 70817336064254781640273354039, 70538108826539785774361605309, 43782530942481865621293381023, 58234328186578036291057066237, 68808271265478858570126916949, 61660200470938153836045483887, 63270726981851544620359231307, 42904776486697691669639929229, 41545637201787531637427603339, 74012839055649891397172870891, 56943794795641260674953676827, 51737391902187759188078687453, 49264368999561659986182883907, 60044221237387104054597861973, 63847046350260520761043687817, 62128146699582180779013983561, 65109313423212852647930299981, 66825635869831731092684039351, 67763265147791272083780752327, 61167844083999179669702601647, 55116015927868756859007961943, 52344488518055672082280377551, 52375877891942312320031803919, 69659035941564119291640404791, 52563282085178646767814382889, 56810627312286420494109192029, 49755877799006889063882566549, 43858901672451756754474845193, 67923743615154983291145624523, 51689455514728547423995162637, 67480131151707155672527583321, 59396212248330580072184648071, 63410528875220489799475249207, 48011409288550880229280578149, 62561969260391132956818285937, 44826158664283779410330615971, 70446218759976239947751162051, 56509847379836600033501942537, 50154287971179831355068443153, 49060507116095861174971467149, 54236848294299624632160521071, 64186626428974976108467196869]
bag = 1202548196826013899006527314947
n = len(a)
L = matrix.zero(n + 1)

for row, x in enumerate(a):
    L[row, row] = 2
    L[row, -1] = x

L[-1, :] = 1
L[-1, -1] = bag
res = L.LLL()
print(res.row(0).list()[:-1])
res=res.row(0).list()[:-1]
result = ''
for i in res:
    if i == 1:
        result = '1'+result
    else:
        result = '0'+result
print(int(result,2))
p=int(result,2)
flag='hgame{'+hashlib.sha256(str(p).encode()).hexdigest()+'}'
print(flag)

其中将矩阵第一行的1，-1置换时，-1对应0还是1都有可能。

hgame{04b1d0b0fb805a70cda94348ec5a33f900d4fd5e9c45e765161c434fa0a49991}

babyRSA

由gift可以解出e，e=73561，在求e对于phi的逆元时，发现报错。e与phi不互素，并且GCD(e,phi)=e,GCD(e,p-1)=e,GCD(e,q-1)=1。用sagemath中的nthroot解出。

from Crypto.Util.number import *

p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841
gift=9751789326354522940

d=inverse(0x10001,p-1)
res=pow(gift,d,p)
e=res-114514
print(e)#e=73561
n=p**4*q
phi=(p**4-p**3)*(q-1)
print(GCD(e,phi))#73561
print(GCD(e,p-1))#73561
print(GCD(e,q-1))#1

e=73561
result = Zmod(n)(c).nth_root(e, all=True)
for i in result:
    plain=long_to_bytes(int(i))
    if b"hgame{" in plain:
        print(plain)
        break

hgame{Ad1eman_Mand3r_Mi11er_M3th0d}