PicoCTF2024 Crypto部分WP
感想
这可能是我打的第一个参与度比较高的国外的CTF,前面四道没什么难度,但是被flag_printer卡了很久,估计一时半会忘不掉这道题.
interencdec
签到题
密文如下
YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclgyZzBOMm8yYXpZNWZRPT0nCg== |
显然是Base64编码,解码得到结果如下:
b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrX2g0N2o2azY5fQ==' |
去除b''之后进行Base64解码结果如下:
wpjvJAM{jhlzhy_k3jy9wa3k_h47j6k69} |
进行一次偏移量为7的凯撒解密可以得到flag:
picoCTF{caesar_d3cr9pt3d_a47c6d69} |
Custom encryption
题目给出加密代码如下:
from random import randint |
题目给出的另一个附件如下:
a = 89 |
分析
分析代码可以知道有一个share_key
,把它求出来(很简单,不知道他为什么要把pow(a,b,p)
包装成一个新的函数)然后通过cipher
里面每一个元素除以share_key
和311得到一个串,跟text_key
进行一个异或(dynamic_xor_encrypt
)再对得到的plaintext
进行反转。
解题
先求share_key
:
u = pow(g, a, p) |
求出share_key
之后就可以将cipher
除以share_key
和311得到一个串:
temp = [x//shared_key//311 for x in cipher] |
将temp
与text_key
进行一个异或,其中text_key="trudeau"
得到一字符串后反转就可以得到flag:
s = '' |
总体代码如下:
p = 97 |
运行可得flag:
picoCTF{custom_d2cr0pt6d_dc499538} |
C3
加密代码:
import sys |
题目给出的另外一个附件内容如下:
DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl |
可以知道附件是chars
加密得到的,分析代码后写出解密代码如下:
chipher = 'DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl' |
运行代码可得:
#asciiorder |
会发现解出来是一串缺少参数chars
内容的代码,猜测这里的chars
就是上面求解出来的chars
,拼接上一条代码再进行修改后得到如下代码:
chipher = 'DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl' |
运行得到的字符串包裹上picoCTF{}
即可得到flag:
picoCTF{adlibs} |
rsa_oracle
这道题考点较多,但是算是模板题,所以难度不算高.
分析
首先题目给了个预言机(Oracle),通过交互我们可以发现可以通过这个Oracle对一些东西进行加密或者解密,而文件中给出了一个password.enc文件,从题目描述中的“After some intensive reconassainance they found out that the bank has an oracle that was used to encrypt the password”可以知道password.enc里面的数据是通过Oracle中内置的RSA的参数进行加密的,但是我们并不能将password.enc的数据直接丢进Oracle里面得到password,故我们考虑使用选择密文攻击得到password。得到password之后,我们通过hint2:OpenSSL can be used to decrypt the message. e.g openssl enc -aes-256-cbc -d ...
(或者通过message.enc里面的格式)可以知道需要通过OpenSSL解密message.enc得到flag,而密码就是password.enc解密得到的。
解题
第一步:先通过选择明文攻击得到Oracle中的RSA加密的参数
由RSA的原理,我们可以得到以下式子: \[ 2^e\equiv c_2\pmod{n}\\4^e\equiv c_4\pmod{n}\\8^e\equiv c_8\pmod{n} \] 可得: \[ c_2^2\equiv c_4\pmod{n}\\c_2^3\equiv c_8\pmod{n} \] 即: \[ c_2^2-c_4=k_1n\\c_2^3-c_8=k_2n \] 在一般情况下,有\((c_2^2-c_4,c_2^3-c_8)=n\)
自此,我们得到了\(n\),现在要得到\(e\),猜测\(e\)小于\(100000\),使用上面求出的\(c_2\)(或者\(c_4,c_8\))进行爆破,就得到了\(e\)。
该步代码如下:
from pwn import * |
第二步:通过选择密文攻击得到password(OpenSSL中用于解密的key)
由于不能直接解密password(后面将里面的数记为\(c\)),而从一般通过Oracle选择密文攻击的题目,我们可以知道他应该也不能解密\(c+kn,k\in Z\),我们考虑通过解密\(c*s^e\ mod\ n\)来得到我们需要的东西。
解密之后可以得到\(s\)倍的\(m\)(这里\(m\)就是解密后的password
),乘上\(inv(s,n)\)再模\(n\)(这里\(inv(a,b)\)表示\(a\)模\(b\)的乘法逆元)就可以还原出password
了(需要long_to_bytes
)
核心代码:
io.sendline(str(c*pow(2,e,n)%n).encode()) |
第三步
通过OpenSSL对message.enc通过aes_256_cbc
算法进行解密,命令大致如下:
openssl enc -aes-256-cbc -d -in (这里是message.enc的路径) -out flag.txt -k (这里是password) |
就可以得到flag了.
flag_printer
算法优化题,卡了好久,感觉这题不应该出现在Cryptography里面.
题目给出了一个30.8MB的文本文件,里面有1769611组数,还给出了一个python源码如下:
import galois |
由代码可以知道我们需要求解如下方程: \[ \left[ \begin{matrix} x_0^0&x_0^1&x_0^2&\cdots&x_0^{n-1}\\ x_1^0&x_1^1&x_1^2&\cdots&x_1^{n-1}\\ x_2^0&x_2^1&x_2^2&\cdots&x_2^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ x_{n-1}^0&x_{n-1}^1&x_{n-1}^2&\cdots&x_{n-1}^{n-1}\\ \end{matrix} \right] \left[ \begin{matrix} \alpha_0\\\alpha_1\\\alpha_2\\\vdots\\\alpha_{n-1} \end{matrix} \right] = \left[ \begin{matrix} y_0\\y_1\\y_2\\\vdots\\y_{n-1} \end{matrix} \right] \] 可以看到,左式的\(n\times n\)矩阵是一个范德蒙德矩阵,所以优先考虑范德蒙德方程组求解,找到Björck-Pereyra算法,后面发现在Python中需要分配11.4TB的内存,并不能解决问题。
再观察矩阵可以发现对于任意\(x_i(i=0,1,2,\cdots,n-1)\),有:\(\alpha_0x_i^0+\alpha_1x_i^1+\alpha_2x_i^2+\cdots+\alpha_{n-1}x_i^{n-1}=y_i\)
可以知道,这显然可以利用拉格朗日插值法,得到的函数应为:\(f(x)=\alpha_0x^0+\alpha_1x^1+\alpha_2x^2+\cdots+\alpha_{n-1}x^{n-1}\)
但是一般的拉格朗日插值法时间复杂度太高,不能达到我想要的效果(实际上如果是硬跑的话还是可以跑出flag的),故考虑FFT(快速傅里叶变换),但是可惜的是我对算法的学习不深,并不知道怎么写FFT.