网鼎杯-Qualifier-2022/玄武组/Crypto/crypto557(new_stream) Writeup

1. challenge

附件下载：https://pan.baidu.com/share/init?surl=Rar0fxHzpDiL4bK8AP2Zbw 提取码：GAME

new_stream.py

from Crypto.Util.number import *
import random
from secret import flag
f = open("output.txt","w")

for i in range(18):
    p = getPrime(256)
    x = random.randint(2, p-1)
    tmp = bytes_to_long(flag)
    enc = []
    for j in range(size(tmp)):
        r = random.randint(2, p-1)
        if tmp%2:
            enc += [pow(x, r, p)]
        else:
            enc += [r]
        tmp //= 2
    
    f.write("p = " + str(p) + "\n")
    f.write("enc = " + str(enc) + "\n")

output.txt 太长了，本文就不贴出来了。

2. 分析

阅读代码，进行了18轮加密。

每一轮都重新生成随机数$x_i$，对flag的每一bit $m_{j}$，生成随机数$r_{ij}$进行加密： $$ c_{ij}=\left{ \begin{aligned} & x_i^{r_{ij}} \mod p, & m[j]%2==1 \
& r_{ij}, & m[j]%2 == 0 \end{aligned} \right. $$

我首先尝试了一下能否对每一轮的 $x_i^{r_{ij}} \mod p$，根据多组(m, c)还原出x，尝试无果。

大概是还原不出来$x_i$了，于是考虑能否根据数论的一些性质，将$x_i^{r_{ij}} \mod p$和$r_{ij}$区分开来。

因为之前做过一道二次剩余相关的题目VolgaCTF2020Qualifier Crypto Guess writeup，所以我尝试了二次剩余：

在GF(p)上，有(p-1)/2个二次剩余。

所以$x_i$ 有一半的可能满足： $$ x_i^{\frac{p-1}{2}} \equiv 1 \mod p \
\Rightarrow (x_i^{\frac{p-1}{2}})^{r_{ij}} \equiv 1 \mod p \
\Rightarrow c_{ij}^{r_{ij}} \equiv 1 \mod p $$

即，如果某一轮的$x_i$是p的二次剩余，则该轮使用模幂加密的密文都是p的二次剩余。而，对任意随机数$r_{ij}$是不满足该特点的。

根据这一特点，因为我们有18组数据，可以分析出flag每一位二进制bit的奇偶性的统计学规律。

我们可以生成一些数据验证一下。

import random

p = random_prime(2L**256,2L**255)
x1 = random.randint(2, p-1)
print(f"x  is quadratic residue?: {pow(x1,(p-1)//2,p)==1}")

r = []
for i in range(18):
    r.append(random.randint(2, p-1))    
c = []
for i in range(18):
    c.append(pow(x1, r[i], p))

print("---------")
for i in range(len(c)):
    print(f"ci is quadratic residue?: {pow(c[i], (p-1)//2, p)==1}")
print("---------")
for i in range(len(c)-1):
    print(f"ri is quadratic residue?: {pow(r[i], (p-1)//2, p)==1}")

x  is quadratic residue?: True
---------
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
ci is quadratic residue?: True
---------
ri is quadratic residue?: False
ri is quadratic residue?: False
ri is quadratic residue?: True
ri is quadratic residue?: True
ri is quadratic residue?: False
ri is quadratic residue?: True
ri is quadratic residue?: False
ri is quadratic residue?: False
ri is quadratic residue?: False
ri is quadratic residue?: True
ri is quadratic residue?: False
ri is quadratic residue?: False
ri is quadratic residue?: False
ri is quadratic residue?: True
ri is quadratic residue?: False
ri is quadratic residue?: True
ri is quadratic residue?: True

首先我想要确定哪些轮次的x是p的二次剩余，因为x为非二次剩余的轮次，明文的奇偶性没有统计学规律。

统计每一轮密文是二次剩余的概率

  • 对于x是p的二次剩余的轮次，概率应约等于$p(bin(m[i])==1)*1/2+p(bin(m[i])==0)\approx 3/4 $
  • 对于x不是p的二次剩余的轮次，概率应约等于$p(bin(m[i])==1)*1/2+p(bin(m[i])==0)*1/2 \approx 1/2$

因而可以得知x是p的二次剩余的轮次。

对于这些轮次，对x是p的二次剩余的轮次，统计每一位密文在这些轮次上是二次剩余的概率，明文的奇偶性有明显的统计学规律：

  • 明文的二进制bit为奇数，密文必然是p的二次剩余
  • 明文的二进制bit为偶数，密文有1/2的概率是二次剩余

3. exp

import json
from Crypto.Util.number import *

def load():
    cipher = []
    p = [] 
    lines = open("output.txt", "rb").readlines()
    for i in range(0, len(lines), 2):
        p.append(Integer(lines[i].strip(b"p = ").strip(b"\n")))
        cipher.append(json.loads(lines[i+1].strip(b"enc = ").strip(b"\n")))
    return cipher, p

def quadratic_residue_round(cipher, p):
    count = []
    for i in range(18):
        c = 0
        for j in range(len(cipher[0])):
            if pow(cipher[i][j], (p[i]-1)//2, p[i])==1:
                c += 1
        count.append(c)
    print(f"quadratic_residue count of : {count}")

    # the round that x is quadratic residue
    q_round = []
    for i in range(18):
        if count[i] > len(cipher[0])*2//3:
            q_round.append(i)
    print(f"these rounds has quadratic residue x: {q_round}")
    return q_round

def guess_flag(cipher, p, q_round):
    binary = []
    for i in range(len(cipher[0])):
        odd = True
        for j in q_round:
            if pow(cipher[j][i], (p[j]-1)//2, p[j])!=1:
                odd = False
                break
        if odd:
            binary.insert(0, '1')
        else:
            binary.insert(0, '0')
    return binary

cipher, p = load()
q_round = quadratic_residue_round(cipher, p)
binary = guess_flag(cipher, p, q_round)
flag=long_to_bytes(int("".join(binary), 2))
print(flag)

quadratic_residue count of : [247, 244, 236, 252, 180, 254, 256, 168, 247, 247, 174, 243, 242, 253, 167, 159, 256, 242]
these rounds has quadratic residue x: [0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 16, 17]
b'flag{c8b10fb7-95f8-47a2-bfb3-b9489ad39711}'

本文同步发表于