HGAME 2022 Writeup - Week2

 CTF / HGAME
被浏览 次

HGAME 2022 第二周部分题的 Writeup。

第二周的难度上升了不少，而且遇到了春节，所以就没做多少。。

CRYPTO

RSA Attack

拿到数据，发现 $n$ 这么小，直接去在线网站分解得到 $p$ 和 $q$，然后直接解密即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
import libnum

def Decrypt(e, p, q, c):
    f = (p - 1) * (q - 1)
    d = gmpy2.invert(e, f)
    n = p * q
    m = gmpy2.powmod(c, d, n)
    return libnum.n2s(int(m))

e = 65537
p = 715800347513314032483037
q = 978782023871716954857211
c = 122622425510870177715177368049049966519567512708
print(Decrypt(e, p, q, c))

拿到 flag：hgame{SHorTesT!fLAg}

RSA Attack 2

分成了三个子问题，而 task.py 告诉我们了加密过程。

task1

注意到 $n1$ 和 $n2$ 是不互质的，且都是两个质数相乘，所以取最大公因数即可得到 $q$，然后得到 $p$ 即可，注意 Python 里的整数除法是 // 不是 /，在这里坑了好久。

1
2
3
4
5
6
7
8
9
def task1():
    e = 65537
    n1 = 14611545605107950827581005165327694782823188603151768169731431418361306231114985037775917461433925308054396970809690804073985835376464629860609710292181368600618626590498491850404503443414241455487304448344892337877422465715709154238653505141605904184985311873763495761345722155289457889686019746663293720106874227323699288277794292208957172446523420596391114891559537811029473150123641624108103676516754449492805126642552751278309634846777636042114135990516245907517377320190091400729277307636724890592155256437996566160995456743018225013851937593886086129131351582958811003596445806061492952513851932238563627194553
    c1 = 965075803554932988664271816439183802328812013694203741320763105376036912584995031647672348468111310423680858101990670067065306237596121664884353679987689532305437801346923070145524106271337770666947677115752724993307387122132705797012726237073550669419110046308257408484535063515678066777681017211510981429273346928022971149411064556225001287399141306136081722471075032423079692908380267160214143720516748000734987068685104675254411687005690312116824966036851568223828884335112144637268090397158532937141122654075952730052331573980701136378212002956719295192733955673315234274064519957670199895100508623561838510479
    n2 = 20937478725109983803079185450449616567464596961348727453817249035110047585580142823551289577145958127121586792878509386085178452171112455890429474457797219202827030884262273061334752493496797935346631509806685589179618367453992749753318273834113016237120686880514110415113673431170488958730203963489455418967544128619234394915820392908422974075932751838012185542968842691824203206517795693893863945100661940988455695923511777306566419373394091907349431686646485516325575494902682337518438042711296437513221448397034813099279203955535025939120139680604495486980765910892438284945450733375156933863150808369796830892363
    c2 = 11536506945313747180442473461658912307154460869003392732178457643224057969838224601059836860883718459986003106970375778443725748607085620938787714081321315817144414115589952237492448483438910378865359239575169326116668030463275817609827626048962304593324479546453471881099976644410889657248346038986836461779780183411686260756776711720577053319504691373550107525296560936467435283812493396486678178020292433365898032597027338876045182743492831814175673834198345337514065596396477709839868387265840430322983945906464646824470437783271607499089791869398590557314713094674208261761299894705772513440948139429011425948090
    q = gmpy2.gcdext(n1, n2)[0]
    p = n1 // q
    return Decrypt(e, p, q, c1)

task2

注意到 $e$ 非常的小，而 RSA 加密是 $m^e \equiv c \pmod n$，即 $m^e=n \times k + c,\ k \in Z$，$e$ 很小而 $n$ 很大意味着我们可以枚举 $k$ 来暴力得到 $m$。

1
2
3
4
5
6
7
8
def task2():
    e = 7
    n = 14157878492255346300993349653813018105991884577529909522555551468374307942096214964604172734381913051273745228293930832314483466922529240958994897697475939867025561348042725919663546949015024693952641936481841552751484604123097148071800416608762258562797116583678332832015617217745966495992049762530373531163821979627361200921544223578170718741348242012164115593777700903954409103110092921578821048933346893212805071682235575813724113978341592885957767377587492202740185970828629767501662195356276862585025913615910839679860669917255271734413865211340126544199760628445054131661484184876679626946360753009512634349537
    c = 10262871020519116406312674685238364023536657841034751572844570983750295909492149101500869806418603732181350082576447594766587572350246675445508931577670158295558641219582729345581697448231116318080456112516700717984731655900726388185866905989088504004805024490513718243036445638662260558477697146032055765285263446084259814560197549018044099935158351931885157616527235283229066145390964094929007056946332051364474528453970904251050605631514869007890625
    for k in range(200000000):
        res = gmpy2.iroot(c + n * k, e)
        if (res[1] == 1):
            return libnum.n2s(int(res[0]))

task3

注意到两次 RSA 过程中的 $n$ 和 $m$ 是一样的。

$$ m^{e1} \equiv c1 \pmod n \\ m^{e2} \equiv c2 \pmod n $$

而 $e1$ 和 $e2$ 都是质数，所以有 $gcd(e1,e2)=1$。

根据扩展欧几里得算法，存在 $e1 \times s1 + e2 \times s2 = gcd(e1,e2)$

根据以上式子对 $m$ 进行推导：

$$ \begin{aligned} m &= m^{e1 \times s1 + e2 \times s2} \\ &= (m^{e1})^{s1} + (m^{e2})^{s2} \\ &\equiv c1^{s1} + c2^{s2} \pmod n \\ \end{aligned} $$

所以用扩展欧几里得算法求出 $s1$ 和 $s2$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def task3():
    n = 18819509188106230363444813350468162056164434642729404632983082518225388069544777374544142317612858448345344137372222988033366528086236635213756227816610865045924357232188768913642158448603346330462535696121739622702200540344105464126695432011739181531217582949804939555720700457350512898322376591813135311921904580338340203569582681889243452495363849558955947124975293736509426400460083981078846138740050634906824438689712748324336878791622676974341814691041262280604277357889892211717124319329666052810029131172229930723477981468761369516771720250571713027972064974999802168017946274736383148001865929719248159075729
    e1 = 2519901323
    c1 = 3230779726225544872531441169009307072073754578761888387983403206364548451496736513905460381907928107310030086346589351105809028599650303539607581407627819797944337398601400510560992462455048451326593993595089800150342999021874734748066692962362650540036002073748766509347649818139304363914083879918929873577706323599628031618641793074018304521243460487551364823299685052518852685706687800209505277426869140051056996242882132616256695188870782634310362973153766698286258946896866396670872451803114280846709572779780558482223393759475999103607704510618332253710503857561025613632592682931552228150171423846203875344870
    e2 = 3676335737
    c2 = 940818595622279161439836719641707846790294650888799822335007385854166736459283129434769062995122371073636785371800857633841379139761091890426137981113087519934854663776695944489430385663011713917022574342380155718317794204988626116362865144125136624722782309455452257758808172415884403909840651554485364309237853885251876941477098008690389600544398998669635962495989736021020715396415375890720335697504837045188626103142204474942751410819466379437091569610294575687793060945525108986660851277475079994466474859114092643797418927645726430175928247476884879817034346652560116597965191204061051401916282814886688467861
    s = gmpy2.gcdext(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if (s1 < 0):
        s1 = -s1
        c1 = gmpy2.invert(c1, n)
    if s2 < 0:
        s2 = -s2
        c2 = gmpy2.invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    return libnum.n2s(int(m))

得到 flag：hgame{RsA@hAS!a&VArIETY?of.AttacK^mEThodS^whAT:other!AttACK|METHOdS~do@you_KNOW}

REVERSE

xD MAZE

直接扔到 IDA 里，反编译后发现逻辑类似在一维数轴上跳跃，问怎么样能 28 步全在特定的点上。

声明了一个大小为 4096 的数组，值为 32 则该点可以走，35 则不行。

写了个 DFS 来跑 flag：

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
#include <cstdio>
#include <iostream>
using namespace std;
int data[4096];
void db(int n, int x) {
  static int t = 0;
  for (int i = 0; i < n; i++) data[t + i] = x;
  t += n;
}
int d[] = {512, 64, 8, 1};
char flag[30];
bool dfs(int now, int step) {
  if (now >= 4096) return 0;
  if (data[now] != 32) return 0;
  if (step >= 28) return 1;
  bool f = 0;
  for (int i = 0; i < 4; i++) {
    flag[step] = '0' + i;
    f |= dfs(now + d[i], step + 1);
    if (f) break;
  }
  return f;
}
int main() {
  db(2, 32), db(63, 35), db(1, 32), db(7, 35), db(1, 32), db(511, 35);
  db(1, 32), db(63, 35), db(1, 32), db(63, 35), db(2, 32), db(511, 35);
  db(2, 32), db(63, 35), db(1, 32), db(7, 35), db(1, 32), db(511, 35);
  db(2, 32), db(7, 35), db(1, 32), db(511, 35), db(2, 32);
  db(7, 35), db(1, 32), db(7, 35), db(1, 32), db(7, 35), db(1, 32), db(7, 35);
  db(2, 32), db(63, 35), db(1, 32), db(511, 35), db(1, 32), db(511, 35);
  db(2, 32), db(511, 35), db(1, 32), db(63, 35), db(1, 32), db(63, 35);
  db(1, 32);
  dfs(0, 0);
  printf("hgame{%s}", flag);
}

拿到 flag：hgame{3120113031203203222231003011}

WEB

webpack-engine

开始点按钮玩，喜闻乐见的上当了环节

然后直奔源码，发现没关 source map，找到了 Fl4g_1s_her3.vue

里面发现 YUdkaGJXVjdSREJ1ZEY5bU1ISTVaWFJmTWw5RGJFOXpNMTlUTUhWeVkyVmZiVUJ3ZlE9PQo=

BASE64 解密一次得到 aGdhbWV7RDBudF9mMHI5ZXRfMl9DbE9zM19TMHVyY2VfbUBwfQ==

继续 BASE64 解密就拿到 flag。

得到 flag：hgame{D0nt_f0r9et_2_ClOs3_S0urce_m@p}

To be continued…

 上一页