给21华师CTF新生赛出了几个题，给一下wp.

题目的源码和答案脚本都公开在Github仓库里

顺便庆祝Folivora成立了🎉🎉🎉

Crypto·

这部分应该会按简单->困难的顺序写，然后给一个主观的难度等级（逃

babyFibo·

定级：简单

放出：决赛

题目文件：https://github.com/scnu-sloth/hsctf-2021-freshmen/tree/main/Crypto-babyFibo/release

WP：

一个简单的优化计算题目，求Fibonacci数列的第1000项（s），然后和做了padding的明文xor后生成密文，也就是能“找”出Fibonacci的第1000项（s）的话就可以xor密文拿到明文flag。

优化的方法是简单的动态规划，学过点算法应该就知道了；虽然如果给我的话我会选择直接在sage里面fibonacci(1000)：

1
2
sage: fibonacci(1000)                                                   
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

然后因为是新生赛，所以取了特殊的1000项，可以简单地从网上搜到，比如这里

1
2
3
4
5
6
7
8
9
10
import libnum

c = 43104378128345818181217961835377190975779804452524643191544804229536124095677294719566215359919831933542699064892141754715180028183150724886016542388159082125737677224886528142312511700711365919689756090950704
# from https://blog.csdn.net/weixin_45791152/article/details/104522781
# or `s = fibonacci(1000)` in sage
s = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

m = c^s
flag = libnum.n2s(int(m))
print(flag)

baigeiRSA·

定级：简单

放出：初赛第二批

题目文件：https://github.com/scnu-sloth/hsctf-2021-freshmen/tree/main/Crypto-baigeiRSA/release

WP：

白给，p和q都是128位的，可以用yafu直接分解n，然后就是简单的RSA解密了；不过对新生来说可能需要知道这个大小是可分解的、会用yafu、以及会RSA的解密。介绍RSA的帖子很多了，比如这个，这里就不另外说了。

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

e = 65537
n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257

# from yafu
p = 274539690398523616505159415195049044439
q = 322368694010594584041053487661458382819
assert p*q == n

phi = (p-1)*(q-1)
d = invert(e, phi)
m = pow(c, d, n)
flag = libnum.n2s(int(m))
print(flag)

baigeiRSA2·

定级：简单

放出：初赛第三批

题目文件：https://github.com/scnu-sloth/hsctf-2021-freshmen/tree/main/Crypto-baigeiRSA2/release

WP：

跟上一题类似，而且这里的p是64位更小，可以直接暴力分解n；不同的是这里的n是用5个不同的pi乘出来的，后来比赛中给了一个欧拉函数的hint，根据欧拉函数，φ(n)=∏i=04pi\varphi(n)=\prod_{i=0}^{4}p_i，就求出了普通RSA解密中的φ\varphi了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from gmpy2 import invert
from functools import reduce
import libnum

e = 65537
n = 175797137276517400024170861198192089021253920489351812147043687817076482376379806063372376015921
c = 144009221781172353636339988896910912047726260759108847257566019412382083853598735817869933202168

# from yafu
ps = [
    9401433281508038261,
    10252499084912054759,
    11855687732085186571,
    13716847112310466417,
    11215197893925590897
]
phi = reduce(lambda x, y: (x)*(y-1), [1]+ps)
d = invert(e, phi)
m = pow(c, d, n)
flag = libnum.n2s(int(m))
print(flag)

babyECC2·

定级：中等

放出：决赛

题目文件：https://github.com/scnu-sloth/hsctf-2021-freshmen/tree/main/Crypto-babyECC2/release

WP：

这题“偷”了一下上年的babyECC的代码，但其实漏洞点跟ECC没啥关系的，ECC只是用来唬人的（x）；审源码最后那部分有

1
2
3
# sage
for i in range(len(flag)):
  c.append( (ord(flag[i]) ^^ int(kp[i%2])) & 0xff )

用人话来说就是：如果i是偶数，则ci=mi⨁k0c_i=m^i \bigoplus k_0；如果i是奇数，则ci=mi⨁k1c_i=m^i \bigoplus k_1；也就是说只要知道k0k_0和k1k_1这两个key就可以做解密。根据官网的说明，flag开头只有三种，也就是最起码可以知道m0m_0和m1m_1，由密文可以找出c0c_0和c1c_1，xor一下就有k0k_0和k1k_1了，然后就是写脚本的事情了：

1
2
3
4
5
6
7
8
c = 'ac73a774a25bd512d543dc468542c9428141800dd041d043c918d112850dd515d6128214d1138211d71599'
c = bytes.fromhex(c)
# assume HSCTF{... ...}
key = [c[0]^ord('H'), c[1]^ord('S')]
flag = ''
for i in range(len(c)):
    flag += chr(c[i] ^ key[i%2])
print(flag)

Equation·

定级：防AK

放出：初赛第一批

题目文件：https://github.com/scnu-sloth/hsctf-2021-freshmen/tree/main/Crypto-Equation/release

WP：

本次比赛密码学唯一防AK神题（x），主要考察连分数攻击（或格），就是之前归纳过的东西。题目代码很长，但几乎都是在骗的，主要关注每个while True里的if判断就好（当然还有大小关系：aa和bb的都比xx和yy的大，前者大概是后者的三次方）。

第一个是a0x0=b0y0a_0x_0=b_0y_0，注意一下这个式子的格式已经给出了a0a_0和b0b_0的（注意aa和bb的都比xx和yy的大）最小公倍数（LCM）（由于gcd(x0,y0)=1gcd(x_0, y_0)=1），令n0=a0x0=b0y0n_0=a_0x_0=b_0y_0的话就是：

LCM(a0,b0)=n0LCM(a_0, b_0) = n_0

既然拿到了n0n_0，分别除一下a0a_0和b0b_0，就有x0x_0和y0y_0了：

1
2
3
4
5
# sage
# Part 0
nn = lcm(a0, b0)
x0 = nn//a0
y0 = nn//b0

第二个是a1x1−b1y1=1a_1x_1-b_1y_1=1，熟悉的话应该可以看出这是个扩展欧几里得算法（egcd）的格式，即a1x1−b1y1=gcd(x1,y1)a_1x_1-b_1y_1=gcd(x_1, y_1)，对a1a_1和a2a_2做一下egcd就可以恢复x1x_1和y1y_1了，因为数据就是这样生成的（x），实际真正while出来的数据我也不能保证可不可以egcd（应该需要一个证明），不过其实不重要，因为下一Part的方法也可以解这一个的

1
2
3
4
5
# sage
# Part 1
_, x1, y1 = xgcd(a1, b1)
x1 = abs(x1)
y1 = abs(y1)

第三个是a2x2−b2y2≤y2a_2x_2-b_2y_2 \le y_2，本题真正防AK的地方（：，这其实是一个“简单”的用格解的格式，参考之前的归纳，然后观察一下这个大小关系，其实和RSA的Wiener攻击中的ed−kN=k(1−(p+q))+1ed-kN=k(1-(p+q))+1是很类似的，毕竟之前也提过这两个方法是相通的（逃），

给一下大小关系，令N=2l2N = 2^{l_2}、a2x2−b2y2=sa_2x_2-b_2y_2 = s的话，有：

a2,b2≈N3x2,y2,s≈Na_2, b_2 \approx N^3 \\ x_2, y_2, s \approx N \\

于是就可以构造格的表达式：

(x2,−y2)∗[1a20b2]=(x2,s)(x_2, -y_2)* \begin{bmatrix} 1 & a_2 \\ 0 & b_2 \\ \end{bmatrix} = (x_2, s)

记上面这个东西是vL=wvL=w的话，可以计算∥w∥≈N\|w\| \approx N，σ(L)≈N1.5\sigma(L) \approx N^{1.5}，∥w∥<σ(L)\|w\| < \sigma(L)，就ww大概率是LL的最短向量了，LLL一下可以求出ww，然后v=wL−1v=wL^{-1}，求出vv，绝对值一下求出x2x_2和y2y_2。

上面那个其实只是理想的情况，现实的情况，直接说结论的话就是，做完绝对值后的x2′x_2'和y2′y_2'其实还要乘上一个g=gcd(x2,y2)g=gcd(x_2, y_2)才是真正的x2x_2和y2y_2，关于gg的话，如果是随机的数据的话其实都不会太大的（吧），但最后有hint提示了gg的范围了，其实直接爆破就好了，爆破的时候如果爆出来的对应出来可以每个都是可见字符string.printable就是成功了（详见脚本）；

用连分数的方法其实也类似（要乘gg），但好像更麻烦，因为我没写连分数的脚本就略了

最终exp：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# sage
import libnum
import string

a0 = 30188147721117215781129100297502653147720244598096
b0 = 21570432690338300962113223428601821765217196091704
a1 = 2644612157538919571387894485245174170571484040764
b1 = 2439650961154362725659337213967574551053744888261
a2 = 3549540394738386267390659328154240007562582898045
b2 = 3396047733146044072945509494632282291396398974799

# Part 0
nn = lcm(a0, b0)
x0 = nn//a0
y0 = nn//b0

# Part 1
_, x1, y1 = xgcd(a1, b1)
x1 = abs(x1)
y1 = abs(y1)

# Part 2
M = matrix([
  [1, a2],
  [0, b2]
])
L = M.LLL()
w = L[0]

v = M.solve_left(w)
# guess gcd(x2, y2)
for g in range(1, 10000):
  x2 = abs(v[0]) * g
  mx2 = libnum.n2s(int(x2))
  yes = True
  for m in mx2:
    if not chr(m) in string.printable:
      yes = False
      break
  if yes:
    y2 = abs(v[1]) * g
    my2 = libnum.n2s(int(y2))
    yes = True
    for m in my2:
      if not chr(m) in string.printable:
        yes = False
        break
    if yes:
      #print(x2, y2)
      break
else:
  print('more gcd')
  exit(-1)

# get flag
res = [x0, y0, x1, y1, x2, y2]
res = [libnum.n2s(int(x)) for x in res]
flag = ''
for r in res:
  for m in r:
    flag += chr(m)
print(flag)

果然这道题0解（逃

Misc·

phone_call·

定级：中等

放出：初赛第三批

题目文件：https://github.com/scnu-sloth/hsctf-2021-freshmen/tree/main/Misc-phone_call/release

WP：

就是生成了一组电话音做压缩包的密码，“听出来”每个音对应得数字解压就好；但实际做的时候不应该是听的，而是拉到Audacity（或Au之类的音频软件）里面，调到频谱图，然后拿每个音对应的上下两条频率查DTMF的表：