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
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的原理，我们可以得到以下式子：

$$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 *
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 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
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.