PWNHUB春季赛2022

2022-04-26

此次hash，佩奇师傅和我一起参加了pwnhub春季赛，卷了两天还是不敌Nu1L，0ops等超级战队，最终获得第七。不管怎么说，被两位师傅带飞，真是太开心了2333，自己也学到很多东西，以后继续加油。这里记录crypto和misc（hash’s wp）。

Crypto

rootRSA

n是素数

e与phi不互素，公因子为2，考虑直接在求逆元的时候phi除2，

$ed=k\frac{φ}{2}+1=>c^d=m^{k\frac{φ}{2}+1}$n

$m^{\frac{φ}{2}}$只有可能是1或-1，$=>c^d=m~or~n-m$

import gmpy2
from Crypto.Util.number import *
n=12550665024378930760414751134790360813045951256998070524733380516320863892820588959446247471740157454369275132333022529896652239978885827346520768307232891
e=16
c=763948541935065669070177590784664764389876210884755820620803919845599976738581612129194042330620496257282174257848945066377803831435064827047454497131887
phi=n-1
d=gmpy2.invert(e,phi//2)
m=pow(c,d,n)
print(long_to_bytes(m))

#flag{9eea787de20e84cba3eed5bf99730bd0}

ezmat

前一半是Hidden Subset Sum Problem

过程不是很懂，或许可以参考这篇文章

#sage
import ast

f = open('output.txt','r')
p = eval(f.readline()[3:])
h = eval(f.readline()[3:])

m = len(h)
n = 60

# orthogonal lattice
B = matrix(h).T.augment(matrix.identity(m)).stack(vector([p] + [0] * m))
nr = m - n
print("start BKZ", B.dimensions())
# ortho = B.LLL()[:nr, 1:]
ortho = B.BKZ()[:nr, 1:]
print(ortho)
# print(ortho * A.T)  # first nr rows are zeros
# exit()

R = ortho.T.augment(matrix.identity(m))

# print('after')
# print((A*R)[:,:nr])
# print('after nr')
# print((A*R)[:,nr:])
# exit()

R[:, :nr] *= 2 ^ 10
print("start LLL", R.dimensions())
# R = R.BKZ(algorithm="NTL")
R = R.LLL()

print("=" * 10)

goodvecs = []
for row in R:
    if any([x != 0 for x in row[:nr]]):
        continue
    if all(-1 <= x <= 1 for x in row):
        goodvecs.append(row[nr:])
        print(row[nr:])
print("gvecs", len(goodvecs))


def is_good(v):
    if all([x == 0 for x in v]):
        return None
    if all([0 <= x <= 1 for x in v]):
        return tuple(v)
    if all([-1 <= x <= 0 for x in v]):
        return tuple(-v)

print("find 01 basis")

from itertools import product
from tqdm import tqdm

avecs = set()
for v in goodvecs:
    if all(0 <= x <= 1 for x in v):
        avecs.add(tuple(v))
        bestvec = v
print(len(avecs))
for v1 in tqdm(goodvecs):
    for v2 in goodvecs:
        for coef in product([-1, 0, 1], repeat=3):
            vv = coef[0] * v1 + coef[1] * v2 + coef[2] * bestvec
            if any([x < 0 for x in vv]):
                vv = -vv
            if all([0 <= x <= 1 for x in vv]) and sum(vv) != 0:
                avecs.add(tuple(vv))
    if len(avecs) == n:
        break

print(len(avecs))
avecs = list(avecs)
AT = matrix(ZZ, avecs).T
x = AT.change_ring(Zmod(p)).solve_right(vector(h)).change_ring(ZZ)

from Crypto.Util.number import *

for i in range(60):
 temp=list(AT.T[i])
 bin_m1 = ''.join(list((map(str, temp[:167])))).rjust(168,'0')
 print(long_to_bytes(int(bin_m1,2)))

#flag{634b9828-aa75-11

第二部分相当于RSA在矩阵上的实现，实际上只需找一个矩阵乘法循环群在GF(p)上的阶，即|GL~n~(p)|

最终得到一个类似于数域上phi的表达式

$ord|\prod_{i=0}^{n-1}(p^n-p^i)$

直接照着RSA的过程做就行

#sage
from Crypto.Util.number import *
f = open('output.txt','r')
p = eval(f.readline()[3:])
w = eval(f.readline()[3:])
M =eval(f.readline()[4:])
M=Matrix(GF(2),M)
phi=1
for i in range(330):
 phi*=2^330-2^i
e=65537
g=GCD(e^100,phi)
d=inverse(e,phi//g)
m=M^d

for i in range(330):
 temp=list(m[i])
 bin_m1 = ''.join(list((map(str, temp[:167])))).rjust(168,'0')
 print(long_to_bytes(int(bin_m1,2)))

#ec-ad2c-00155d24943f}

ezRSA

实际上就是一个椭圆曲线群上的RSA问题，为啥这么喜欢出非数域群上的RSA

所以只需要将n进行分解即可

根据方程$y^2=x^3+(p+q)x+p^2+\frac{q-1}{2}(mod~n)$

两边同时乘q，消掉n后把q除掉得到等式

$(2x+1)q-(2(y^2-x^3)+1)=0(mod~p)$

p为1024bits，q是512bits，直接copper就行

最后需要求模n下椭圆曲线群的阶，猜的话直接猜p下阶和q下阶的乘积就行

翻paper找到的阶数#E~n~=#E~p~×#E~q~

1024比特素数域下的阶有点难跑，差不多整了一个小时吧

#sage
import gmpy2
x,y=(338555080220637081961629108201515088631648910827927160728143665306856840891283037339677849661861227903908933145477264046446986150577658634798201036502060805774599658207669111688439996110692201008037849119605962378316457201998475046620515963725786423440494993922281942396227626532022005579340476627086260000576524772862121364339849726687865874619472513654142054490221489754144358483093331358263771080584662872680106076787261957704707055652825959314984924849600101, 936859805496385391559236776246883920797971062581544240268575675825570737296851006237870839271568976317212531276234406232945021531066674291887782791534409966305833225084692612867437424551505174720475931132798839349207246806850341280754752239303350596733681932273450149927797735966407187594725231158980098119489003450563623494155562513634618466910170109518754662675054081897025489520391417883488720972781393802142478712026232107041683271177224983497203599032383279)
n=988000511804778695813521569460767024014375863209856154754147082419975777208656083311740358048468580712106204105426217752071608551112269505247365548210006567296850568411531004204795967810292432041395592133501302461324005142940183488044983348152371980166614840414803124031222965874472013554869981954785271467321919039144942853506143787908194930700818770224752026306092706366253640515130802157497666497193713819097381223915943111321812676982912146706199692543488639
e = 0x10001
PR.<t>=PolynomialRing(Zmod(n))
f=(2*x+1)*t-(2*(y^2-x^3)+1)
f=f.monic()
q=int(f.small_roots(X=2^512,beta=0.66,epsilon=0.05)[0])
p=n//q
E = EllipticCurve(Zmod(n), [p+q, p^2+(q-1)//2])
ord1=6855192886546913083681222574678665050135391949965285975146135828115325275541697293384823154969044166686748375254337473827633716503099373916062802135744940
ord2=144124392727693582180721020059571309401371450244791136032830630083498715102652723003947343817176211175903247642131045942369687053495080809769954262316918844452268262450578732948830901662726788794480021021018409168738053922485515917280245423459001897063629559133512702989322938763296063139634992297531810955826
phi=ord1*ord2
d=gmpy2.invert(e,phi)
A=E(x,y)
print(d*A)

#flag{0f02b65a-ab26-11ec-829c-00155d24943f}

Misc

眼神得好

用stegsolve分析，利用Stereogram Solver进行像素偏移，偏移足够大以后发现flag。

被偷的flag

这题做了一大半，最后没出非常可惜QWQ。

开局一张jpg，直接用stegsolve在每个通道查看，发现了二维码，扫码得到部分信息：1e:))}

发现数据段有zip，所以直接进行一波foremost分离，得到压缩包和一套字典，显然用字典攻击可以得到密码，解压得到txt和一个pyc。

txt包含零宽字符，在线网站解得字符Unc

小明发现叔叔的桌子上一张字条，上面写着[绝密]，便悄悄偷了过来。拆开了纸条并进行了查看，竟然真的是flag，flag居然就在这里！。为了隐藏自己的行为，小明把纸条揣进兜里，丢到了洗衣机，然后把flag分成了4部分藏了起来。叔叔回来后找不到纸条了，就去查看了监控，发现是小明拿走了纸条。小明随后拿出经过洗衣机摧残的纸条，打开发现上面的文字都模糊了。上面写着："flag{32145(‌‌‌‌‍‍‍‍****-*‌‌‌‌‍‬‬***U****:‌‌‌‌‍‬‌))}"。你能帮叔叔找到flag吗。

一直到这步我都是对的，下一步纯属知识面的问题，拿到pyc第一想法肯定是反编译，但实际上他是一个pyc隐写…参考博客，总之直接用stegosaurus提取出extra字符：VqtS-HZ&*

这里有个小坑，工具暂未支持py3.9版本，切换了成3.7,成功解决。

之后用base85解密得到字符 base64(

32145联系题目可知是Polybius，32对应m，14对应d，意思是md5

综上所述，flag{md5(base64(Uncle:))}