HGAME 2024 WEEK2 Crypto WP

前言

我很菜，有没做出来的题目，带*号题为复现。

midRSA

题目：

from Crypto.Util.number import *
from secret import flagdef padding(flag):return flag+b'\xff'*(64-len(flag))flag=padding(flag)
m=bytes_to_long(flag)
p=getPrime(512)
q=getPrime(512)
e=3
n=p*q
c=pow(m,e,n)
m0=m>>208print(f'n={n}')
print(f'c={c}')
print(f'm0={m0}')"""
n=120838778421252867808799302603972821425274682456261749029016472234934876266617266346399909705742862458970575637664059189613618956880430078774892479256301209695323302787221508556481196281420676074116272495278097275927604857336484564777404497914572606299810384987412594844071935546690819906920254004045391585427
c=118961547254465282603128910126369011072248057317653811110746611348016137361383017921465395766977129601435508590006599755740818071303929227578504412967513468921191689357367045286190040251695094706564443721393216185563727951256414649625597950957960429709583109707961019498084511008637686004730015209939219983527
m0=13292147408567087351580732082961640130543313742210409432471625281702327748963274496942276607
"""

解题：
给了提示def padding(flag): return flag+b'\xff'*(64-len(flag))说明被消去的数据中可能不存在flag,直接低位补0复原数据。

from Crypto.Util.number import *
m = 13292147408567087351580732082961640130543313742210409432471625281702327748963274496942276607
m0 = m << 208
print(long_to_bytes(m0))
#hgame{0ther_cas3s_0f_c0ppr3smith}

当然你觉得不稳的话可以试试m已知高位攻击,复原出padding后的全部flag

from Crypto.Util.number import *
m = 5468072284345600284522355008479109169075116053402180689979880057809181898595927628842804575369333562845495606668542454369610468082607896606970684163227647print(long_to_bytes(m))
#hgame{0ther_cas3s_0f_c0ppr3smith}

midRSA revenge

题目：

from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(1024)
q=getPrime(1024)
e=5
n=p*q
c=pow(m,e,n)
m0=m>>128print(f'n={n}')
print(f'c={c}')
print(f'm0={m0}')"""
n=27814334728135671995890378154778822687713875269624843122353458059697288888640572922486287556431241786461159513236128914176680497775619694684903498070577307810263677280294114135929708745988406963307279767028969515305895207028282193547356414827419008393701158467818535109517213088920890236300281646288761697842280633285355376389468360033584102258243058885174812018295460196515483819254913183079496947309574392848378504246991546781252139861876509894476420525317251695953355755164789878602945615879965709871975770823484418665634050103852564819575756950047691205355599004786541600213204423145854859214897431430282333052121
c=456221314115867088638207203034494636244706611111621723577848729096069230067958132663018625661447131501758684502639383208332844681939698124459188571813527149772292464139530736717619741704945926075632064072125361516435631121845753186559297993355270779818057702973783391589851159114029310296551701456748698914231344835187917559305440269560613326893204748127999254902102919605370363889581136724164096879573173870280806620454087466970358998654736755257023225078147018537101
m0=9999900281003357773420310681169330823266532533803905637
"""

思路，这回是真的m已知高位攻击
修改上述代码参数即可。

backpack

from Crypto.Util.number import *
import random
from secret import flag
a=[getPrime(32) for _ in range(20)]
p=random.getrandbits(32)
assert len(bin(p)[2:])==32
bag=0
for i in a:temp=p%2bag+=temp*ip=p>>1enc=bytes_to_long(flag)^pprint(f'enc={enc}')
print(f'a={a}')
print(f'bag={bag}')
"""
enc=871114172567853490297478570113449366988793760172844644007566824913350088148162949968812541218339
a=[3245882327, 3130355629, 2432460301, 3249504299, 3762436129, 3056281051, 3484499099, 2830291609, 3349739489, 2847095593, 3532332619, 2406839203, 4056647633, 3204059951, 3795219419, 3240880339, 2668368499, 4227862747, 2939444527, 3375243559]
bag=45893025064
"""

思路：
生成一个32位数对其每一位上的数字（0/1）乘上a中的加到bag中。那咱就逆着来，这个真是运气，因为这个是预期的，如果是backpack revenge中的非预期我是求不出来的。

a = [3245882327, 3130355629, 2432460301, 3249504299, 3762436129, 3056281051, 3484499099, 2830291609, 3349739489, 2847095593, 3532332619, 2406839203, 4056647633, 3204059951, 3795219419, 3240880339, 2668368499, 4227862747, 2939444527, 3375243559]
bag = 45893025064key = 0
for i in reversed(a):if bag >= i:key = (key << 1) + 1bag -= ielse:key <<= 1
enc = 871114172567853490297478570113449366988793760172844644007566824913350088148162949968812541218339
# key = 3772829031flag = enc ^ key
from Crypto.Util.number import *
print(long_to_bytes(flag))

BabyRSA

题目：

from Crypto.Util.number import *
from secret import flag,e
m=bytes_to_long(flag)
p=getPrime(64)
q=getPrime(256)
n=p**4*q
k=getPrime(16)
#64位
gift=pow(e+114514+p**k,0x10001,p)
c=pow(m,e,n)
print(f'p={p}')
print(f'q={q}')
print(f'c={c}')
print(f'gift={gift}')
"""
p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841
gift=9751789326354522940
"""

先找e

gift=pow(e+114514+p**k,0x10001,p)

这个看着长其实可以还原成

gift=pow(e+114514,0x10001,p)

因为和p有关的都被约去了

#gift=pow(e+114514,0x10001,p)
#gift=pow(e1,0x10001,p)
import gmpy2p=14213355454944773291
gift=9751789326354522940
e = 0x10001
d=gmpy2.invert(e,p-1)
e1 = pow(gift, d, p)
e=e1-114514
print(e)
# e=73561

获得了e后，我们发现e|p-1, e|q-1

这时我们可以使用lazzzaro佬的脚本

#脚本1
#Sage
e = 73561
p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841for mp in GF(p)(c).nth_root(e, all=True):for mq in GF(q)(c).nth_root(e, all=True):m = crt([ZZ(mp), ZZ(mq)], [p, q])try:res = bytes.fromhex(hex(m)[2:])if res.isascii():print(res)except:pass

复现时不太懂，
又找到了Kicaky_Mu师傅的wp
以及他的脚本

from Crypto.Util.number import *
import gmpy2p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841n = p**4*q
phi = p**3*(p-1)*(q-1)
e=73561
res = Zmod(n)(c).nth_root(e, all=True)
for m in res:flag = long_to_bytes(int(m))if b"hgame" in flag:print(flag)break
#hgame{Ad1eman_Mand3r_Mi11er_M3th0d}

师傅说，他的想法是找到n环内c的剩余类中，可以开e次方根的数，遍历之后获得获得flag，他的代码似乎更简洁和容易理解，好棒啊。

*backpack

题目：

from Crypto.Util.number import *
import random
import hashliba=[getPrime(96) for _ in range(48)]
p=random.getrandbits(48)
assert len(bin(p)[2:])==48
flag='hgame{'+hashlib.sha256(str(p).encode()).hexdigest()+'}'bag=0
for i in a:temp=p%2bag+=temp*ip=p>>1print(f'a={a}')
print(f'bag={bag}')"""
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
"""

原谅我的浅薄，才发现这是一道背包题。
找到了lazzzaro神的脚本和讲解

from sage.all import *ct =1202548196826013899006527314947  # public key
pk =[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]# ciphertext
print(ct)
print(len(pk))
n = len(pk)# Sanity check for application of low density attack
d = n / log(max(pk), 2)
print(CDF(d))
assert CDF(d) < 0.9408M = Matrix.identity(n) * 2last_row = [1 for x in pk]
M_last_row = Matrix(ZZ, 1, len(last_row), last_row)last_col = pk
last_col.append(ct)
M_last_col = Matrix(ZZ, len(last_col), 1, last_col)M = M.stack(M_last_row)
M = M.augment(M_last_col)X = M.BKZ()sol = []
for i in range(n + 1):testrow = X.row(i).list()[:-1]if set(testrow).issubset([-1, 1]):for v in testrow:if v == 1:sol.append(0)elif v == -1:sol.append(1)breaks = sol
print(s)
1202548196826013899006527314947
48
0.5004362519031288
[1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1]

直接求100001001000111000110010100010101011010000101111不行
那就逆一下得到111101000010110101010001010011000111000100100001
转换成10进制268475474669857
然后根据源代码中的

p=random.getrandbits(48)
assert len(bin(p)[2:])==48
flag='hgame{'+hashlib.sha256(str(p).encode()).hexdigest()+'}'

得到解题代码：

import hashlib
p = 268475474669857
assert len(bin(p)[2:])==48
flag='hgame{'+hashlib.sha256(str(p).encode()).hexdigest()+'}'
print(flag)