0%

0CTF 2021 划水小记

周末事情太多,就看了两道简单题

Checkin#

1
2
3
4
5
$ nc 111.186.59.11 16256
Show me your computation:
2^(2^10839575) mod 18430349691130984455653758459763818735123125315616520868044937078564476220884826010073662755433151553014915091221715272584999168440833812257356157301435273413022448333856092986075794460810348537912091730922337038551649739290135460889939415385861839125461043205821543512247526910812418671832464041927757236703 = ?
You have 10 seconds. gogogo!
Your answer:

需要在十秒内获得这个结果,考察的是一个快速的模指数运算

原理在这里:

image-20210705145917040

自己手写算法的话在我自己的机器上Python最快要40s左右,如果要加速的话其实用其他语言写一遍就行了,可以用C语言调大数运算的库实现,如下:

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
from pwn import *
from tqdm import tqdm
context.log_level = 'debug'
import gmpy2

def fast_mod(e,n):
i_2 = 2**(2**0)
result = 1
for _ in tqdm(range(1,e)):
i_2 = (i_2 << 1 ) % n
result = (result * i_2) % n
return (result % n)

p = remote("111.186.59.11",16256)

print(p.recvline())
line = p.recvline()
e = int(line.split(b"^")[2].split(b")")[0])
n = int(line.split(b"mod")[1].split(b"=")[0])
print(e,n)
# result = gmpy2.powmod(2,2**e,n)
result = fast_mod(e,n)
print(result)
p.recv()
p.sendline(str(result))
p.interactive()

对应的C++实现可以看这里checkin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <gmp.h>

void main(int argc, char **argv){
int intpow = atoi(argv[1]);
const char *str = argv[2];
mpz_t a,b,c,d,base;
mpz_init_set_ui(base,2U);
//No way around this. You must initialize every mpz_t type whenever you want to use them.
mpz_inits(a,b,c,d,NULL);
mpz_set_ui(a,2U);
mpz_set_str(c,str,10);
mpz_pow_ui(b,base,intpow);
//Just change the numbers I guess.
mpz_powm(d,a,b,c); //d will give you the answer.
gmp_printf("%Zd\n",d); //Do you need this o.o
}

但是比较鸡贼的是gmpy2包里貌似是实现的对应的算法:gmpy2.powmod(2,2**e,n)可以在5s左右算完,挠头

Guthib#

这个是比较有意思的一道题目

1
https://github.com/awesome-ctf/TCTF2021-Guthib

如果在repo里去除了敏感信息,并且gc了,但是之前在Github里提交过对应的commit的话,信息仍然会存在Github上,只是我们无法通过正常途径找到对应的commit

看到的方法有两种:

  1. 第一个是直接去爆破commit的前4个字符
  2. 第二个是使用githubapi找到所有和repo相关的eventscurl https://api.github.com/repos/awesome-ctf/TCTF2021-Guthib/events\?page\=6,在events返回的结果中使用sha关键字查找所有的commit即可

最后的找到commit如下:https://github.com/awesome-ctf/TCTF2021-Guthib/commit/da883505ed6754f328296cac1ddb203593473967

坚持原创技术分享,您的支持将鼓励我继续创作!