感想
这可能是我打的第一个参与度比较高的国外的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
import sys
def generator(g, x, p):
return pow(g, x) % p#实际上就是pow(g,x,p)
def encrypt(plaintext, key):
cipher = []
for char in plaintext:
cipher.append(((ord(char) * key*311)))
return cipher
def is_prime(p):
v = 0
for i in range(2, p + 1):
if p % i == 0:
v = v + 1
if v > 1:
return False
else:
return True
def dynamic_xor_encrypt(plaintext, text_key):
cipher_text = ""
key_length = len(text_key)
for i, char in enumerate(plaintext[::-1]):#将字符串反转后异或加密
key_char = text_key[i % key_length]
encrypted_char = chr(ord(char) ^ ord(key_char))
cipher_text += encrypted_char
return cipher_text
def test(plain_text, text_key):
p = 97
g = 31
if not is_prime(p) and not is_prime(g):
print("Enter prime numbers")
return
a = randint(p-10, p)
b = randint(g-10, g)
print(f"a = {a}")
print(f"b = {b}")
u = generator(g, a, p)
v = generator(g, b, p)
key = generator(v, a, p)
b_key = generator(u, b, p)
shared_key = None
if key == b_key:
shared_key = key
else:
print("Invalid key")
return
semi_cipher = dynamic_xor_encrypt(plain_text, text_key)
cipher = encrypt(semi_cipher, shared_key)
print(f'cipher is: {cipher}')
if __name__ == "__main__":
message = sys.argv[1]
test(message, "trudeau")题目给出的另一个附件如下：
a = 89
b = 27
cipher is: [33588, 276168, 261240, 302292, 343344, 328416, 242580, 85836, 82104, 156744, 0, 309756, 78372, 18660, 253776, 0, 82104, 320952, 3732, 231384, 89568, 100764, 22392, 22392, 63444, 22392, 97032, 190332, 119424, 182868, 97032, 26124, 44784, 63444]分析
分析代码可以知道有一个share_key，把它求出来（很简单，不知道他为什么要把pow(a,b,p)包装成一个新的函数）然后通过cipher里面每一个元素除以share_key和311得到一个串，跟text_key进行一个异或（dynamic_xor_encrypt）再对得到的plaintext进行反转。
解题
先求share_key:
u = pow(g, a, p)
v = pow(g, b, p)
key = pow(v, a, p)
b_key = pow(u, b, p)
if key == b_key:
shared_key = key求出share_key之后就可以将cipher除以share_key和311得到一个串：
temp = [x//shared_key//311 for x in cipher]将temp与text_key进行一个异或，其中text_key="trudeau"得到一字符串后反转就可以得到flag：
s = ''
text_key = "trudeau"
for i in range(len(temp)):
s += chr(ord(temp[i])^ord(text_key[i%len(text_key)]))
print(s[::-1])总体代码如下：
p = 97
g = 31
a = 89
b = 27
cipher = [33588, 276168, 261240, 302292, 343344, 328416, 242580, 85836, 82104, 156744, 0, 309756, 78372, 18660, 253776, 0, 82104, 320952, 3732, 231384, 89568, 100764, 22392, 22392, 63444, 22392, 97032, 190332, 119424, 182868, 97032, 26124, 44784, 63444]
u = pow(g, a, p)
v = pow(g, b, p)
key = pow(v, a, p)
b_key = pow(u, b, p)
if key == b_key:
shared_key = key
temp = [chr(x//shared_key//311) for x in cipher]
s = ''
text_key = "trudeau"
for i in range(len(temp)):
s += chr(ord(temp[i])^ord(text_key[i%len(text_key)]))
print(s[::-1])运行可得flag：
picoCTF{custom_d2cr0pt6d_dc499538}C3
加密代码：
import sys
chars = ""
from fileinput import input
for line in input():
chars += line
lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"
out = ""
prev = 0
for char in chars:
cur = lookup1.index(char)
out += lookup2[(cur - prev) % 40]
prev = cur
sys.stdout.write(out)题目给出的另外一个附件内容如下：
DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl可以知道附件是chars加密得到的，分析代码后写出解密代码如下：
chipher = 'DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl'
lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"
chars = ''
prev = 0
for i in range(len(chipher)):
cur = lookup2.index(chipher[i])
chars += lookup1[(cur + prev)%40]
prev = (cur + prev)%40
print(chars)运行代码可得：
#asciiorder
#fortychars
#selfinput
#pythontwo
chars = ""
from fileinput import input
for line in input():
chars += line
b = 1 / 1
for i in range(len(chars)):
if i == b * b * b:
print chars[i] #prints
b += 1 / 1会发现解出来是一串缺少参数chars内容的代码，猜测这里的chars就是上面求解出来的chars，拼接上一条代码再进行修改后得到如下代码：
chipher = 'DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl'
lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"
chars = ''
prev = 0
for i in range(len(chipher)):
cur = lookup2.index(chipher[i])
chars += lookup1[(cur + prev)%40]
prev = (cur + prev)%40
b = 1 / 1
for i in range(len(chars)):
if i == b * b * b:
print(chars[i],end='')
b += 1 / 1运行得到的字符串包裹上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的原理，我们可以得到以下式子：
$$
\begin{aligned}
2^e\equiv c_2\pmod{n}\\
4^e\equiv c_4\pmod{n}\\
8^e\equiv c_8\pmod{n}
\end{aligned}
$$
可得：
$$
\begin{aligned}
c_2^2\equiv c_4\pmod{n}\\
c_2^3\equiv c_8\pmod{n}
\end{aligned}
$$
即：
$$
\begin{aligned}
c_2^2-c_4=k_1n\\
c_2^3-c_8=k_2n
\end{aligned}
$$
在一般情况下，有\((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 *
import gmpy2
from Crypto.Util.number import *
io = remote("地址",端口)
#get pow(2,e,n)
data = io.recv()
print(data)
io.sendline(b'E')
data = io.recv()
print(data)
io.sendline(chr(2).encode())
data = ((io.recv().split(b' ')[11]).split(b'\n')[0]).decode()
c2 = int(data)
#get pow(4,e,n)
io.sendline(b'E')
data = io.recv()
print(data)
io.sendline(chr(4).encode())
data = ((io.recv().split(b' ')[11]).split(b'\n')[0]).decode()
c4 = int(data)
#get pow(8,e,n)
io.sendline(b'E')
data = io.recv()
print(data)
io.sendline(chr(8).encode())
data = ((io.recv().split(b' ')[11]).split(b'\n')[0]).decode()
c8 = int(data)
n = gmpy2.gcd(c2**2-c4,c2**3-c8)
print(n)
for e in range(100000):
if pow(2,e,n)==c2:
print(e)第二步：通过选择密文攻击得到password（OpenSSL中用于解密的key）
由于不能直接解密password（后面将里面的数记为\(c\)），而从一般通过Oracle选择密文攻击的题目，我们可以知道他应该也不能解密\(c+kn,k\in \mathbb{Z}\)，我们考虑通过解密\(c\cdot 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
import numpy as np
MOD = 7514777789
points = []
for line in open('encoded.txt', 'r').read().strip().split('\n'):
x, y = line.split(' ')
points.append((int(x), int(y)))
GF = galois.GF(MOD)
matrix = []
solution = []
for point in points:
x, y = point
solution.append(GF(y % MOD))
row = []
for i in range(len(points)):
row.append(GF(x**i%MOD))
matrix.append(GF(row))
open('output.bmp', 'wb').write(bytearray(np.linalg.solve(GF(matrix), GF(solution)).tolist()[:-1]))由代码可以知道我们需要求解如下方程：
$$
\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.