现在是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就是$\phi(num)$

我超 第一次知道factordb这个网站

我超 第一次见面factordb就给我摆烂(;′⌒`)

我记得有一个大整数分解算法叫做$\text{Pollard-Rho}$,显然我是不会写的,洛谷上只能抄袭题解C++的代码

然后我从网上下载的CTF工具包里翻出一个叫做yafu的分解工具

image-20211030233106114

yafu也分解得毫无规律,一些是素数,一些又不是,害得我一个个检查再分解

当时人都给整傻了,检查又再分解了几次,都还是错误的flag

最后找到一个超强的在线分解网站:

https://www.alpertron.com.ar/ECM.HTM

image-20211030233909392

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不懂攻击的选手当然要去网上翻资料辣

image-20211030232449445

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!!!!!}

[😋] 基地遭到攻击

一开始的时候看这道题的代码比较丑,跳过了这道题

img这道题主要就是这句话不懂让我迟迟没做,个人觉得应该把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)$

貌似没法解决,难道还有更快的方法?

image-20211031195850053

https://www.ruanx.net/pohlig-hellman/

显然我不会

不过听说有个工具叫做Sagemath,可以支持上述骚算法

发现了一个宝藏网站:https://sagecell.sagemath.org/

亲测前几次打开需要科学上网,自从这题开始这个宝藏网站共计为我算出了$\color{Red}{4}$道题的flag

因为没保存,又得重敲一遍代码(;′⌒`)

image-20211031200615572

long_to_bytes()即可

image-20211031200704991

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的困难目前还没有得到数学上的证明,因此事实上它目前还只是一个假设

然后问题来了

image-20211031201241712

今天又费力看了一遍,囿于数学知识水平还是有一些疑惑

大致意思是设点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 \equiv l_i \pmod {p_i^{r_i}}$

最后再使用中国剩余定理合并出key,这我懂,但中间的一些细节我就不明白了

简析ECC攻击方法之Pohlig-Hellman

这样$p_i \times P_0 = nP = 0 \infin$

简析ECC攻击方法之Pohlig-Hellman

然后为什么$l_i \times P = Q$啊???

还有

image-20211101160822507

image-20211101160832179

为什么第二张图左边能剩下$z_1p_i$,不是$p_i \times P_0 = nP = 0 \infin$就没了吗??

看原英文教程也不太明白

image-20211101161137883

图中红圈的等式是为何成立的

参考链接:

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的因子

然而我得知这和原根有关(誒由于当时没有打省选,多项式这块就没有涉猎img

然后我把程序改了一下,把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就出解了

代码如下,数论垃圾的我做题太难了

image-20211031214328246

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消元,

image-20211101101944758

如上图所示列出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]))

image-20211101001449810

诶呀从现在开始网站关闭了,我没有flag了

而且题目标题也没有难度表情了

RSA I

一开始迟迟没有思路,后来感觉这题和RSA的关系不大,因为p,q无法硬分解出来,但又好像是解题必须的

题意可简化理解为已知p xor 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:
    continue

Code:

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

image-20211101110626657

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$

昨日的月光悄然退场,曦阳已经渐亮