现在是 10.30 晚，离招新网站拉闸还有 1 天的时间，做不动 Crypto 只好滚来写 WP
[🤖] Crypto做题指南
最好拿的 flag
cnss{Welcome_to_the_world_of_crypto}
好像还有很多东西不会咧(；´д｀)ゞ
[😋] 大大超人的代码 I
求乘法逆元，exGCD 或者费马小定理二选一皆可
$$
i \equiv b \times a^{-1} \pmod n
$$
cnss{you yi ge ren qian lai mai gua. lue lue lue lue lue. sa ri lang, sa ri lang. ei, hua qiang, hua qiang}
[😋] 大大超人的代码 II
显然题目中的 cnt 就是 $\varphi(num)$
我超 第一次知道 factordb 这个网站
我超 第一次见面 factordb 就给我摆烂(；′⌒`)
我记得有一个大整数分解算法叫做 Pollard-Rho，显然我是不会写的，洛谷上只能抄袭题解 C++ 的代码
然后我从网上下载的CTF工具包里翻出一个叫做 yafu 的分解工具
yafu 也分解得毫无规律，一些是素数，一些又不是，害得我一个个检查再分解
当时人都给整傻了，检查又再分解了几次，都还是错误的flag
最后找到一个超强的在线分解网站：
https://www.alpertron.com.ar/ECM.HTM
Code:
from hashlib import md5
from math import gcd
n =42884020547169390364057708512857160494285905714049130207174574321294001570717794624065180823944268300615872241601579039570417514768021539120794827687319577302185669966605784385135475359835440522138098740956869698753641542827169807498060060203204623056652296548672193678604201527271552258183411014527366217548194668469156210293296924920396661175084847772705813725399053734267798263155285086152337660486536186646844672457165552673635686438518233777750910982014487846162409685706645584022613739678475494110418588076015804320630926293482802728176941310074063709832881421592093809601385355979927053037564815022569532301725889642648753691270079271760325794402609541247330395378653665694056501747438163292250560881807911461231726101015329450977148586716650828721964825603783645451441758913032780302842678209454303821607654073090650401139540242325808963472494771631432989047762098809264580664019379523293624441137658106554812934798531301113822034790852090529061101693937747989599304386879458074169786212163676139153571980665024887827190167719665028793495590181448050849517686984259984456749798664352548534304800162670309538117876068852938462001997080070145586746296815514664296506732662997084432462415745714170644890474456380187175650685331337577272850596655499330349676234958852437039128355237654047269
Prime = [726469,1248059,3488777,4003333,7324349,13943177,14429917,40264613,117077309,416211353, 925020799,1291513693,4297172359,6945055903,14980192757,31896490931,34448261957,42273263297,334972370143,409576292549]
ans = n
for i in Prime:
if ans % i: print("awsl")
ans = ans // i * (i - 1)
flag = md5(str(ans).encode()).hexdigest()
print('Flag is cnss{' + flag + '}')
cnss{7b4a23cf05fc166e2f5e6798d737cb83}
[😋] EZRSA
零基础只会写RSA不懂攻击的选手当然要去网上翻资料辣
Code:
import gmpy2, libnum
N = 17122915166265113628936084259612311876364779252333817653908064563012403283413723801149226058776045562431863561527598029708484050735340376592692944196636066937254842628374596659520832392883941088961925998112268354069528298108259950738233300271339429579172788606259082714089126140552788081701431773946954101521880287079138683872063436125499187482930254182605546821908768554127091588674102227605591868183216588952297634056187432224500652151699978753316630287127751214117068167697654397115835061787620207935678045116272234790320727737354518224845334305441037073149880267837099939565780539222758100209016162314144630920799
e = 3
c = 16926458617386458077637050106018850896006879092288192701331681605474802210713231004923465605065133301881405183688853792875133217926741592214428875953305593414362683885848278980412814134018268287018200015497631362139676275057736654215717198437649465165438442373537289011460247398965575656801213891887710880496787600356785377725103473390014610976378061619695088235473509
for k in range(100000):
res, flag = gmpy2.iroot(c + k*N, 3)
if flag:
print(res)
exit(0)
cnss{面对恐惧的最好办法就是消除恐惧}
我超，忘记保存就关机了，3道题的writeup没了
艹，又得重写一遍
[😋] True Random
题目就是一堆随机、异或等操作，写个 exp 逆向操作一遍即可
Code：
import random
seeds = [6756, 949, 8167, 2246, 9307, 4748, 9651, 1460, 3867, 5744, 5815, 713, 1057, 5614, 4024, 8075, 3862, 732, 279, 5308, 7815, 2251, 5533, 6324, 6786, 8549, 4421, 6651, 7409, 4880, 6246, 1249, 192, 4099, 1704, 3678, 7520, 1378, 2642, 9154, 5690, 8621, 1717, 4992, 8903, 1608, 3214, 2565, 3146, 2521, 2070, 1047, 5784, 8682, 1057, 1091, 8655, 2957, 8591, 1284, 9162, 2974, 9395]
res = [0, 8, 221, 50, 176, 21, 79, 19, 208, 117, 8, 51, 171, 156, 247, 101, 60, 46, 152, 162, 182, 29, 16, 102, 154, 22, 117, 65, 21, 121, 197, 170, 2, 217, 118, 201, 15, 132, 246, 21, 1, 250, 7, 45, 130, 124, 231, 200, 103, 7, 63, 86, 159, 211, 168, 82, 11, 60, 173, 209, 168, 191, 255, 101]
ans = []
for i in range(0, len(seeds)):
random.seed(seeds[i])
rands = []
for j in range(0, 4):
rands.append(random.randint(0, 255))
ans.append(res[i+1] ^ rands[i % 4] ^ res[i])
#del rands[i % 4]
#print(str(rands))
for i in ans:
print(chr(i), end="")
cnss{Trust me!This is turely random!!!!TURELY RANDOMMMMMM!!!!!}
[😋] 基地遭到攻击
一开始的时候看这道题的代码比较丑，跳过了这道题
这道题主要就是这句话不懂让我迟迟没做，个人觉得应该把 for 循环里的 st[] 去掉
仔细分析，题目的操作大致是这样：
dec_to_ter 和 ter_to_dec 分别表示将一个数转化成 3 进制且不足 5 位高位补 0，将一个 3 进制数转化成 10 进制
然后把 msg 按照 3 个字符为一组进行拆分，每一段转化成如下 st 串：
$$
0\ \text{XXXXX XXXXXX XXXXXX}
$$
其中 XXXXX 表示对应字符的 ord 值，这样 st 串的长度是 16，再按照 4 个为 1 组进行拆分，每组内的数字转化成 10 进制记作index，再在 dic 中查找下标为 index 的字符，并添加到 cy 串中
题目最后给出了 cy 串，看懂题后只需要再逆向操作回去即可
据说这道题就是仿照 base64 但把二进制改成三进制
Code:
cy = 'eJ:zwWufwZuYwHsvelcawj9le^jxwCMb7HjhwZuYwJMz7JVl7Hugq^3j7Zob1)qQeZuke7Hj7J:n4RZze^jU1x-ge%Ige%IuqHjmeCHzwRMte^nge(ZhqHqkqKWue%MO0987'
dic = '0987654321qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM!@#$%^&*-=+:;(){}<>'
def dec_to_ter(num):
l = []
while True:
num, reminder = divmod(num, 3)
l.append(str(reminder))
if num == 0:
return "".join(l[::-1]).zfill(5)
def dec_to_ter2(num):
l = []
while True:
num, reminder = divmod(num, 3)
l.append(str(reminder))
if num == 0:
return "".join(l[::-1]).zfill(4)
def ter_to_dec(st):
num = 0
for i in range(len(st)):
num += 3**(len(st) - i - 1) * int(st[i])
return num
def find(x):
for i in range(len(dic)):
if dic[i] == x:
return i
flag= ''
for i in range(len(cy) // 4):
x = ''
for j in range(4):
t = i * 4 + j
x += dec_to_ter2(find(cy[t]))
flag += chr(ter_to_dec(x[1:6]))
flag += chr(ter_to_dec(x[6:11]))
flag += chr(ter_to_dec(x[11:16]))
print(flag)cnss{This_is_a_strange_switch_of_Base}
[(😋+😗)/2] Smooth Criminal
题意很简单明了：
$$
g^x \equiv h \pmod p
$$
求 $x$ 显然是个离散对数问题，但求大整数的离散对数不是一件困难的事吗
我们知道 $\text{BSGS}$ 可以用于求解离散对数，其时间复杂度是 $\mathcal O (\sqrt n)$
貌似没法解决，难道还有更快的方法？
https://www.ruanx.net/pohlig-hellman/
显然我不会
不过听说有个工具叫做 Sagemath，可以支持上述骚算法
发现了一个宝藏网站：https://sagecell.sagemath.org/
亲测前几次打开需要科学上网，自从这题开始这个宝藏网站共计为我算出了 $\color{Red}{4}$ 道题的 flag
因为没保存，又得重敲一遍代码(；′⌒`)
再long_to_bytes()即可
cnss{You_have_got_Pohilg_Hellman!}
[😗] ECDLP
为了做这题专门学了一下ECC椭圆加密算法的大致原理，我口胡一下：
选取一个基点(生成元)G，和一个私钥k，
计算公钥K = kG，并公布
- 加密：
- $C_1 = M + rK$
- $C_2 = rG$
- 解密：
- 计算$C_1 – kC_2 = M + rkG – krG = M$
其中上面的加法和乘法运算都是基于椭圆曲线上的，而其安全性正是源于计算公钥的k是ECDLP问题，即椭圆曲线上的离散对数问题，不过有意思的是其实ECDLP的困难目前还没有得到数学上的证明，因此事实上它目前还只是一个假设
然后问题来了
今天又费力看了一遍，囿于数学知识水平还是有一些疑惑
大致意思是设点 P 的阶为 n，即 nP = O∞，
将n进行唯一分解为 $p_1^{r_1}p_2^{r_2}p_3^{r_3}…p_s^{r_s}$，计算出 $l_i$ 满足下面的程组，i = 1,2,3…s
最后再使用中国剩余定理合并出key，这我懂，但中间的一些细节我就不明白了
这样$p_i \times P_0 = nP = 0 \infty$
然后为什么 $l_i \times P = Q$啊？？？
还有
看原英文教程也不太明白
图中红圈的等式是为何成立的
参考链接：
ECC2 (200) · Hackademia Writeups (gitbooks.io)
https://www.codercto.com/a/26932.html
[😗] 大大超人的代码Ⅲ
为了做这道题浪费了我大半天的国庆节10.1
做题思路已经向 NamelessOier 汇报过了，蒟蒻只会打暴力辣
这题的 f 是把 $b^x$ 的所有值插入集合中，然后求最早的 $a^x$ 也在集合中的x的值，根据费马小定理，
$$
a^{p-1} \equiv b^{p-1} \equiv 1 \pmod p
$$
这样的 x 肯定是存在的，然后这题的 k1, k2 应该相当于数据生成器，主要是要加速 f 函数的计算
因为不是所有的数都能在集合中生成一个完全剩余系，能生成的就很好办，答案直接是 1，不能生成的就是麻烦的地方，我记得当时在百度上查到资料 $a^x = 1$ 中的 x 一定是 p-1 的因子
然而我得知这和原根有关(誒由于当时没有打省选，多项式这块就没有涉猎
然后我把程序改了一下，把 p 改成了 131，然后观察 f() 对应的输出值
通过打表发现，从小到大枚举p-1的因子，最小的因子 d 满足 $a^d≡b^x$ 有解，那么该 d 就是答案 p – 1 一共有81920个因子，复杂度上限是 $10000\times 81920\times O(离散对数计算一次)$，但实际上大部分的 f 返回值是 1，这时候只需要 $O(\log^2 p)$ 来计算，所以实际上跑得还挺快的，2min 就出解了
代码如下，数论垃圾的我做题太难了
Code:
p = 941958815880242161
phi = p - 1
v = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
c = [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
res = []
cnt = 0
def dfs(dep, num):
if dep == 14:
res.append(num)
return
d = 1
dfs(dep+1, num)
for i in range(1, c[dep]+1):
d = d * v[dep]
dfs(dep+1, num*d)
def ksm(a, b):
ret = 1
while b:
if b&1: ret = ret * a % p
a = a * a % p
b >>= 1
return ret
def f(a, b):
#print("f({},{})".format(a, b))
if a == 0 or b == 0:
return 0
ok = 1
for i in v:
if ksm(b, phi//i) == 1:
ok = 0
break
if ok: return 1
for i in res:
t = ksm(a, i)
try:
x = discrete_log(mod(t,p),mod(b,p))
#print(i)
return i
except:
continue
print("RE")
exit(0)
return 0
dfs(0, 1)
res.sort()
print(len(res))
flag = 0
mask = (1 << 128) - 1
k1, k2 = (12345678987654321, 98765432123456789)
for i in range(1000):
s = ""
for j in range(10):
k1, k2 = ((k1 * k1 + k2) & mask, (k2 * k2 + k1) & mask)
s += str(f(k1 % p, k2 % p))
#print(s)
flag ^^= int(s)
print("i = {}".format(i))
print("k1 = {} k2 = {}".format(k1, k2))
print("flag = {}".format(flag))
#print(int(s))
print("Flag is cnss{%d}" % flag)
cnss{490340709191995056161967738}
[😗] 那个男人！！！
一开始拿到题，我超，看不懂题，鸽了
看懂题了，写了个暴力破解 sha256 的程序，成功连上了题目
我超，就给我 num 和 res，Con 数组又不知道，怎么解出secret啊？
我超，原来 num 和 res 可以得到无限组数据
我超，一个一个手输入数据好烦啊，它还有断线机制
我超，原来要用 pwntools 啊，可惜我 pwn 还没入门
我超，装 pwntools 还真不简单，主要是我的 Ubuntu 太垃圾了
我超，装好 pwntools 后 remote 读入数据好难啊，调试了半天
最后发现读入数据成功还是个概率问题，因此我在读入过程中加入了 $try$
题目思路即是 Gauss 消元，
如上图所示列出 n 个方程组，未知数为 secret 和 Con[0..t-1]
把洛谷以前写的板子粘下来再把除法全部换成乘以逆元就可以了
由于不知道未知数的个数，索性来个 $200$ 个
后来拿到 flag 发现 $8 * len(flag) = 296$，是我低估了flag的长度
Code：
from Crypto.Util.number import bytes_to_long, getPrime
from hashlib import sha256
import random
import string
from os import urandom
from pwn import *
import time
def exgcd(a, b): # 扩展欧几里得算法
if b == 0: return (1, 0)
x, y = exgcd(b, a % b)
return (y, x - a // b * y)
def Inv(a, p):
inv, t = exgcd(a, p)
return inv % p
def pass_sha256(sub_proof, digest):
table = string.ascii_letters + string.digits
for x in table:
for y in table:
for z in table:
for w in table:
if sha256((x + y + z + w + sub_proof).encode()).hexdigest() == digest:
#print(x + y + z + w)
#exit(0)
return x + y + z + w
io = remote("162.14.80.217", 9999)
s = io.recvuntil(':').decode()
print(s)
XXXX = pass_sha256(s[18:s.find(')')], s[s.find('=')+3:s.find('\n')])
io.send(XXXX.encode())
io.recv()
s = io.recv().decode()
p = eval(s[s.find('=')+2:s.find('\n')])
print("Get p = {}".format(p))
num = []
res = []
n = 200
cnt = 0
while 1:
io.sendline(b'1')
s = io.recv().decode()
try:
a = s[s.find('(')+1:s.find(',')]
b = s[s.find(',')+2:s.find(')')]
num.append(eval(a))
res.append(eval(b))
cnt += 1
print("cnt = {}".format(cnt))
except:
pass
if cnt == n: break
#print(num[i-1], res[i-1])
#io.recv()
a = []
for i in range(n):
a.append([])
a[i].append(1)
t = num[i]
for j in range(n-1):
a[i].append(t)
t = t * num[i] % p
a[i].append(res[i])
for i in range(n):
for j in range(i + 1, n):
div = a[j][i] * Inv(a[i][i], p) % p
for k in range(i, n + 1):
a[j][k] -= div * a[i][k] % p
a[j][k] %= p
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
a[i][n] -= a[j][n] * a[i][j] % p
a[i][n] %= p
a[i][n] = a[i][n] * Inv(a[i][i], p) % p
print("Ans = {}".format(a[0][n]))
io.sendline(b'2')
io.sendline(str(a[0][n]))
while 1:
try:
print(io.recv().decode())
except:
break
for i in range(n):
print("x[{0:}] = {1:}".format(i, a[i][n]))
诶呀从现在开始网站关闭了，我没有 flag 了
而且题目标题也没有难度表情了
RSA I
一开始迟迟没有思路，后来感觉这题和RSA的关系不大，因为p,q无法硬分解出来，但又好像是解题必须的
题意可简化理解为已知 $p \oplus q$ 和 $p \times q$，求 $p, q$，只不过题目为了增加难度还把 p, q 的前后半段进行了翻转再异或，这个只需要在草稿本上画一画哪些位和哪些位相对应即可
于是可以尝试搜索+剪枝
依次从高位到低位按位搜索p，q，根据异或关系，
知道p的高位便可确定q的对应低位，知道q的高位便可确定p的对应低位
- 剪枝1：如果当前已经 $p \times q \gt n$，剪枝
- 剪枝2：如果没搜到的位都填 1，都 $p \times q \lt n$，剪枝
事实证明果真 TLE
第二天早上突然醒悟，思索着如果 $p, q$ 的低 $i$ 位已经确定，那么 $p \times q \pmod {2^i}$ 也会确定，这才是效率最好的剪枝
即剪枝3：
if new_p * new_q % MOD != n % MOD:
continueCode：
n = 128966867931621017951402141152350515585922701101703171805286229280649080647456092995914584397246443887423499663793458719282451496996613304284219288980124348105720917541598445131650977064828807037484823828553004028415721038165820372738002173903655842610359239877763360519229606532878770232406532771135170997013
BIT = 512
res = 5334584593664858319670147545831540027620360712512679965236952968664258458326815898964419736009663358894095508398927605649898980377954463431300198964796146
s = bin(res)[2:].zfill(BIT)
res = int(s[0:BIT//2]+s[BIT//2:][::-1], 2)
# if len(s) < BIT:
# res = int(s[0:(BIT//2)-1]+s[(BIT//2)-1:][::-1],2)
# else:
# res = int(s[0:BIT//2]+s[BIT//2:][::-1],2)
print(res)
dig1 = [1, 1, 0, 0]
dig2 = [1, 0, 1, 0]
def dfs(dep, p, q, pad):
#print("dep = {} p = {} q = {}".format(dep, p, q))
#print("p = {} q = {}".format(bin(p)[:20], bin(q)))
if dep == BIT//2:
print(p, q)
exit(0)
t = BIT - dep + 1
bit1 = (res >> (dep-1)) & 1
bit2 = (res >> (t - 1)) & 1
new_pad = pad ^ (1 << (dep-1))
new_pad ^= 1 << (t - 1)
MOD = 1 << t
for i in range(4):
new_p = p | (dig1[i] << (dep - 1))
new_q = q | (dig2[i] << (dep - 1))
new_p |= (bit2^dig2[i]) << (t-1)
new_q |= (bit1^dig1[i]) << (t-1)
if new_p * new_q > n:
continue
if (new_p+new_pad) * (new_q+new_pad) < n:
continue
if new_p * new_q % MOD != n % MOD:
continue
dfs(dep-1, new_p, new_q, new_pad)
dfs(BIT, 0, 0, (1<<BIT)-1)分解出p, q后面的就不用说了
RSA II
题目给出了 n, e, c，结合题目名称可知这是RSA加密
扔到 factordb 上分解竟然分出来了（偷乐ヾ(✿ﾟ▽ﾟ)ノ
RSA 解密得到明文
$$
m = 3096333133178411455670950335505149941615742941960431025413876344055153398844911737
$$
裹上 cnss{} 交上去喜提 flag 错误
出题人提示数字的含义不一定是数字嘛
结合前面做题的经验，这么大的数字可以 long_to_bytes 试试，得到
b'https://files.catbox.moe/eami99.py'
我超 套娃题目
然后我苦苦搜寻题目的解决办法，终于在一个隐秘的网站找到了它
貌似这是short padding attack + Coppersmith
CTF中的RSA基本套路(3) – 食兔人的博客 (ycdxsb.cn)
写在最后：
- 本文由 $\color{Red}\text{21-信软-LRL52原创撰写}$
- 暑假虽然就了解 CNSS 了，但被前面的 Web、Re 题给劝退了，后来是做凌睿题目学习了 RSA 算法的实现，才发现原来还是能做下 CNSS 的 Crypto 题目，然而发现之后过了2天就关闭夏令营了，当时为了做 CNSS 上面的一道题，还专门去洛谷学习了下二次剩余的 Cipolla 算法，然而学完后晚上网站就拉闸了，紧接着就是正式招新，密码学零基础的我就跟着题目开始做，在做题的过程中边学边做，还是学会了很多新知识吧，比如factordb、ECC 椭圆加密算法、python Crypto 库的使用、Sagemath 的基本用法、pwntools 交互等，当然还有其它方向的知识，CNSS Recruit 2021 带给我了我无数个夜深人静做题的冥冥苦思，也有无数次看见flag 正确上分的成就感和激动，衷心希望能与最好的年华与 CNSS 相遇！
- 萌新能力有限，其中 ECDLP 和 RSA II 两题目前还不太能理解，其余题目都是自己独立求解并敲出 exp 来的
期间做凌睿的题也学习了下 Bloom 过滤器、语义安全性与优势，实现了 RSA 加密+消息验证码+数字签名的安全传输方案，复现了基于 DLP 和零知识的数字签名技术- 写于 $2021.10.29 – 11.1$，
2023.7.5为了测试图床造了现在的重制修改版
