writeup-for-2021-CISCN
Contents
国赛初赛, 第一次参加国赛, 除了第一道恶心的古典, 其他题目还是做的挺有意思的
一共六道题, 出了四道题, 剩下一道古典(呕了), 一道AES
还可以吧, 记录一下, 虽然有些部分以前做过, 但还是学到了新东西的
0x00 classic
滚了, 等真密码👴👴的wp,
2021 / 5 /18 看了别的爷爷博客, 好家伙套娃爆破 ADFGX + 凯撒 +栅栏(话说是ADFGX这个顺序吗)
0x01 move
problem
1 | from Crypto.Util.number import * |
analyses
啊这,看到题目马上就想起刚结束不久的虎符的simultaneous了,当时那题没解出来恼火了好久。还好那个时候写wp写的够详细了,回去再看一遍又仿佛明白了一切hhh
跟着虎符那样就能分解$n$了,得到了$p,q$之后,再看看后面的加密
看到add() mul()
, ECC没错了,吸取以前的教训,做ECC先看关系式是怎样的,从加法的那几行可以看出,这里用的椭圆曲线就是常用的那种,而且$a = 0$, 有一个点$E(c)$很容易就能算出参数$b$
通过分解出的$p$,我们就能造出曲线$y^2 = x^3 + b \mod p$, 阶为$p + 1$,椭圆曲线的乘法就是一个环,乘完一个阶就转回来了,所以只需要求$d = e^{-1} \mod p+1$ 就可以有$e \cdot d \cdot E(flag) = E(flag) $
最后把点转回来就完事了
exp
1 | n = 80263253261445006152401958351371889864136455346002795891511487600252909606767728751977033280031100015044527491214958035106007038983560835618126173948587479951247946411421106848023637323702085026892674032294882180449860010755423988302942811352582243198025232225481839705626921264432951916313817802968185697281 |
0x02 imageencrypt
problem
1 | import random |
analyses
这题做的时候没好好分析,有些结果没追究到底是为啥,拿到了就开始爆破了,现在好好分析一下。
这里模拟了一个图片的加密,加密会有一个范围在$[0,1)$的六位小数初始值$x0$,以及一个咱们不知道的参数$r$,但是这个参数有一个hint,len(str(r)) == 3
,不过这个hint一开始误导我了。。。
先来看看具体的加密过程。加密大概可以分为两个过程
- bitstream生成
- 根据bitstream key1 key2对图片进行加密
bitstream生成
bitstream的生成跟两个变量有关$x0,r$,确定的这两个参数那么生成的bitstream将会一模一样,我们可以根据生成bitstream的函数写出这两个变量的一个关系
$$
x_{n+1} \approx r \cdot x_n (3 - x_n) \\
r \approx {x_{n+1} \over x_n(3-x_n)} \tag 1
$$
也就是说我们只需要确定两个$x$就能大概的算出$r$了,先记为$(1)$,后面有用
而bitstream是根据生成的序列$x_1,x_2,…x_n$来生成的,具体是这样
$$
bin(x_1) | bin(x_2)|…|bin(x_n)
$$
这里的$|$是拼接,而且$bin(x_i)$在长度不够16的时候会在前面填充0到长度为16
加密
我们把bitstream每两位看成一个$X$,也就是说比特流是这样的->$X_1,X_2,…X_n$,显然$X$的范围是$[0,3]$
再说加密过程之前,得先了解一个小知识(~a ^ a )
会把$a$的所有位都置为1
好了,现在来看整个加密过程
这里的图片其实就是一个范围在$[0,256]$的数的序列$m_1,m_2,m_3,…,m_n$
一块公式直接搞定加密!(公式里的-m都是m的反码的意思)
$$
m_i =
\begin{cases}
m_i \oplus key_1 , X_i =0 \\
-m_i \oplus key_1, X_i = 1 \\
m_i \oplus key_2, X_i = 2 \\
-m_i \oplus key_2, X_i = 3
\end{cases}
$$
所以整个加密就是由bitstream来决定使用哪个密钥和操作
题目给了三个图片数据$M_1,C_1,C_2$,要求$M_2$
这里我们计算$M_1 \oplus C_1$,如果是不取反的操作,那么异或出来的就是key,$m_i \oplus key \oplus m_i = key$
如果是进行了取反操作的,那么异或出来的就是key的反码,$-m_i \oplus m_i \oplus key = -key $
所以最后整个图片异或下来,出现的数据只会有四个数字
1 | [78, 177, 78, 177, 169, 78, 86, 86, 78, 177, 78, 169, 78, 78, 78, 177, 78, 177, 177, 169, 78, 86, 177, 169, 78, 177, 86, 78, 86, 169, 169, 169, 177, 169, 169, 169, 86, 169, 78, 78, 78, 78, 177, 177, 177, 78, 177, 78, 177, 169, 78, 86, 169, 78, 86, 177, 78, 86, 177, 177, 169, 78, 86, 169, 177, 86, 78, 177, 86, 169, 169, 177, 86, 177, 86, 78, 169, 169, 86, 86, 177, 78, 86, 78, 86, 78, 169, 169, 86, 86, 78, 169, 86, 169, 169, 86, 177, 86, 169, 169, 177, 177, 86, 86, 78, 169, 177, 78, 78, 169, 177, 169, 177, 78, 86, 86, 86, 78, 177, 78, 86, 86, 78, 78, 177, 78, 177, 169, 177, 86, 169, 177, 177, 78, 169, 78, 78, 169, 86, 177, 177, 78, 169, 78, 177, 78, 86, 177, 86, 86, 78, 86, 86, 86, 86, 86, 86, 177, 78, 177, 177, 169, 177, 86, 78, 177, 169, 177, 78, 86, 86, 86, 78, 78, 177, 86, 177, 78, 169, 78, 169, 169, 169, 86, 86, 78, 86, 169, 86, 78, 169, 169, 177, 86, 177, 169, 78, 78, 78, 78, 86, 177, 169, 78, 86, 177, 86, 78, 177, 78, 86, 86, 169, 86, 177, 78, 86, 86, 78, 177, 177, 169, 177, 86, 177, 86, 86, 169, 177, 169, 177, 78, 78, 169, 86, 86, 78, 177, 177, 169, 177, 78, 86, 177, 78, 177, 86, 169, 86, 86, 86, 169, 86, 177, 86, 177] |
[169,177,86,78]
,而169对应的反码是86,177对应78
现在问题来了,有了这个能干嘛
能否通过这四个数字还原回bitstream呢,我们知道bitstream是决定使用哪个密钥的,而密钥的使用顺序我们是知道的(我们只是不知道哪个是key1 哪个是key2),我们可以一一假设一下,也就8种组合
key1 | key2 | ~key1 | ~key2 | |
---|---|---|---|---|
86 | 78 | 169 | 177 | |
86 | 177 | 169 | 78 | |
169 | 177 | 86 | 78 | |
169 | 78 | 86 | 177 | |
78 | 169 | 177 | 86 | |
78 | 86 | 177 | 169 | |
177 | 86 | 78 | 169 | |
177 | 169 | 78 | 86 | |
Xi | 00 | 10 | 01 | 11 |
每种组合中,每个数字都对应一个$X_i$,我们就能利用数字的顺序,还原出这种组合下所用的bitstream,也就是还原出
$$
\hat X_1 , \hat X_2 , … ,\hat X_i
$$
这里用$\hat X$而不是$X$就是因为还原出的不一定是对的,只有上面的8种情况中的1种才有可能对
因为$X \approx 22000 \cdot x$上面的$(1)$
$$
r \approx {x_{n+1} \over x_n(3-x_n)} \approx {X_{n+1} \over X_n(3 - X_n) }\cdot {1 \over 22000}
$$
随便找了几个组合试了下算$r$,发现都在$[0,2]$中,再根据提示len(r) == 3
,$r$应该是个一位小数,比如$0.5,1.3$这种(一开始我以为是3位数,几百的那种,让我懵了好久艹
现在,我们可以通过确定一种组合,来确定对应的$r$和$bitstream$,但是加密$M_2$用的bitstream比加密$M_1$的长,所以想继续往下算bitstream,我们还需要$x0$
前面我们知道,$x0$是六位的小于1的小数,也就是说一共也就$1000000$种可能,我们可以利用猜的$x0$和算出来的$r$来生成bitstream,看得到的bitstream和我们算$r$的bitstream是否相等来爆破$x0$,8种组合试完也就$8000000$,十分钟不到就能解决。
爆破出$x0$,所有参数都可以对应的确定下来了。
剩下的就是重新算一次bitstream,直到长度够用来解密$C_2$,解密就完事了
exp
1 | # python2 |
0x03 homo
problem
1 | from poly import * |
还有个poly.py我到最后都没有用上。。就不放上来了
analyses
这题有两部分
- 第一部分。让我们猜服务端生成的64bit随机数,512次机会,猜错了会告诉你随机数是什么,猜对了就继续,如果一共猜对200次以上就可以进入下一部分
- 第二部分。白给的同态加密
第一部分 MT19937
其实这里考的就是 MT19937,这是python.random库用的伪随机数生成算法,状态有限,知道624*32 bit之后就能完全的算出后续的随机数。
还记得第一次解出MT19937就是我第一次比赛做密码,2020 N1CTF - VSS ,这道题当时做了一整场,始终没有做出来。看了wp才了解MT19937这种东西,不过也知道了一个可以用来预测随机数的库-> randcrack , 当我们得到了624*32bit之后,就能利用这个库算出后续的随机数
而这里刚好够,一共512次机会,前312次错误刚好可以得到312*64 bit也就是624*32 bit,后面的200次机会就可以每次都猜中了。
第二部分 同态加密
说是同态加密。。。但我好像没用到里面的知识?
服务端提供了解密,我们是有密文的,按理来说直接给密文就行了,但是题目限制了提交上去解密的密文不能是flag的密文
考虑到整个过程都是$\mod q$的,直接给密文加上q就行了。。。
2021/5/18
吃饭的时候想着为啥题目是同态加密, 突然想到这玩意不就是个r-lwe吗, 本来密文有噪音就是可以的, 直接给c0,c1都加上1就行了, 噪音够小是不会影响解密的!
exp
1 | from pwn import * |
0x04 oddaes
不会。。。差分分析,一直都每学会过,等一个wp学习
0x05 rsa
problem
1 | from flag import text,flag |
analyses
白给签到。
- $e$过小导致直接开$e$次方得$m$
- 共模攻击
- 已知$p$高位
都是基础,不详细写了
exp
1 | from Crypto.Util.number import long_to_bytes |
Author: K1rit0
Link: http://tearsjin.github.io/2021/05/16/writeup-for-2021-CISCN/
License: 知识共享署名-非商业性使用 4.0 国际许可协议