2024-D3CTF-Crypto-WP

Sym_signin

task.py:

import random
from secret import secret_KEY, flag
from task_utils import *

plain = read_from_binary_file('plain')
#plain = [3960651144, 1150250357, 338717842, 469237546, 46441841, 781222929]

cipher = []

for i in range(len(plain)):
    x = encrypt(message=plain[i], key=secret_KEY, ROUND=8192)
    cipher.append(x)

write_to_binary_file(cipher, 'cipher_test')


plain_flag = bytes_to_uint32_list(flag)
enc_flag = []
temp_key = l6shad(secret_KEY)
for i in range(len(plain_flag)):
    enc_flag.append(encrypt(message=plain_flag[i], key=temp_key, ROUND=8192))
    temp_key = l6shad(temp_key)

write_to_binary_file(enc_flag, 'flag.enc')

task_utils.py:

import hashlib
import struct
S = [0xc, 0x5, 0x6, 0xb, 0x9, 0x0, 0xa, 0xd,
     0x3, 0xe, 0xf, 0x8, 0x4, 0x7, 0x1, 0x2]

P = [0, 8, 16, 24, 1, 9, 17, 25, 2, 10, 18, 26, 3, 11, 19, 27,
     4, 12, 20, 28, 5, 13, 21, 29, 6, 14, 22, 30, 7, 15, 23, 31]

def S_16bit(x: int) -> int:
    result = 0
    for i in range(4):
        block = (x >> (i * 4)) & 0xF
        sbox_result = S[block]
        result |= sbox_result << (i * 4)
    return result

def S_layer(x: int) -> int: 
    return (S_16bit(x >> 16) << 16) | S_16bit(x & 0xffff)

def P_32bit(x: int) -> int:
    binary_result = format(x, '032b')
    permuted_binary = ''.join(binary_result[i] for i in P)

    result = int(permuted_binary, 2)
    return result

def key_schedule(key):
    return ((key << 31 & 0xffffffff) + (key << 30 & 0xffffffff) + key) & 0xffffffff

def enc_round(message: int, key: int) -> int:
    result = message ^ key
    result = S_layer(result)

    result = P_32bit(result)

    return result

def encrypt(message: int, key: int, ROUND: int) -> int:
    ciphertext = message
    for _ in range(ROUND):
        ciphertext = enc_round(ciphertext, key)
        key = key_schedule(key)

    ciphertext = S_layer(ciphertext)
    ciphertext ^= key

    return ciphertext

先逆一下解密流程，补完该补。

import hashlib
import struct
S = [0xc, 0x5, 0x6, 0xb, 0x9, 0x0, 0xa, 0xd,
     0x3, 0xe, 0xf, 0x8, 0x4, 0x7, 0x1, 0x2]

P = [0, 8, 16, 24, 1, 9, 17, 25, 2, 10, 18, 26, 3, 11, 19, 27,
     4, 12, 20, 28, 5, 13, 21, 29, 6, 14, 22, 30, 7, 15, 23, 31]

P_inv = [0, 4, 8, 12, 16, 20, 24, 28, 1, 5, 9, 13, 17, 21, 25, 29,
     2, 6, 10, 14, 18, 22, 26, 30, 3, 7, 11, 15, 19, 23, 27, 31]

#一个 Block 是4字节 
def S_16bit(x: int) -> int:
    result = 0
    for i in range(4):
        block = (x >> (i * 4)) & 0xF
        sbox_result = S[block]
        result |= sbox_result << (i * 4)
    return result

def S_16bit_inv(x: int) -> int:
    result = 0
    for i in range(4):
        block = (x >> (i * 4)) & 0xF
        sbox_result = S.index(block)
        result |= sbox_result << (i * 4)
    return result

def S_layer(x: int) -> int: #32位的字节替换
    return (S_16bit(x >> 16) << 16) | S_16bit(x & 0xffff)

def S_layer_inv(x: int) -> int: #32位的字节替换
    return (S_16bit_inv(x >> 16) << 16) | S_16bit_inv(x & 0xffff)

def P_32bit(x: int) -> int:
    binary_result = format(x, '032b')
    permuted_binary = ''.join(binary_result[i] for i in P)
    result = int(permuted_binary, 2)
    return result

def P_32bit_inv(x: int) -> int:
    binary_result = format(x, '032b')
    permuted_binary = ''.join(binary_result[i] for i in P_inv)
    result = int(permuted_binary, 2)
    return result

def key_schedule(key):
    return ((key << 31 & 0xffffffff) + (key << 30 & 0xffffffff) + key) & 0xffffffff

def key_schedule_inv(key):
    return (key - (key << 31 & 0xffffffff) - (key << 30 & 0xffffffff)) & 0xffffffff

def enc_round(message: int, key: int) -> int:
    result = message ^ key #轮密钥加
    result = S_layer(result) #32位 字节替换
    result = P_32bit(result) #P盒置换
    return result

def dec_round(result: int, key: int) -> int:
    result = P_32bit_inv(result)
    result = S_layer_inv(result)
    message = result ^ key
    return message

def encrypt(message: int, key: int, ROUND: int) -> int:
    ciphertext = message
    for _ in range(ROUND):
        ciphertext = enc_round(ciphertext, key)
        key = key_schedule(key)

    ciphertext = S_layer(ciphertext)
    ciphertext ^= key

    return ciphertext

def decrypt(message: int, key: int, ROUND: int) -> int:
    for _ in range(ROUND):key = key_schedule(key)

    ciphertext = message
    ciphertext ^= key
    ciphertext = S_layer_inv(ciphertext)

    for _ in range(ROUND):
        key = key_schedule_inv(key)
        ciphertext = dec_round(ciphertext, key)

    return ciphertext

def key_ex(num: int) -> int:
    result = 0
    bit_position = 0
    while num > 0:
        original_bits = num & 0b111
        parity_bit = bin(original_bits).count('1') % 2
        result |= (original_bits << (bit_position + 1)
                   ) | (parity_bit << bit_position)
        num >>= 3
        bit_position += 4
    return result


def write_to_binary_file(uint32_list, output_file):
    with open(output_file, 'wb') as f:
        for number in uint32_list:
            # Pack the integer as an unsigned 32-bit integer (using 'I' format)
            packed_data = struct.pack('<I', number)
            f.write(packed_data)

def read_from_binary_file(input_file):
    uint32_list = []
    with open(input_file, 'rb') as f:
        while True:
            # Read 4 bytes (32 bits) from the file
            data = f.read(4)
            if not data:
                break  # End of file reached
            number = struct.unpack('<I', data)[0]
            uint32_list.append(number)

    return uint32_list


def bytes_to_uint32_list(byte_string, fill_value=None):
    uint32_list = []

    remainder = len(byte_string) % 4
    if remainder != 0:
        padding_bytes = 4 - remainder
        if fill_value is not None:
            byte_string += bytes([fill_value] * padding_bytes)

    for i in range(0, len(byte_string), 4):
        data_chunk = byte_string[i:i+4]
        number = struct.unpack('<I', data_chunk)[0]
        uint32_list.append(number)

    return uint32_list


def l6shad(x):
    # Convert the 24-bit integer x to a bytes object (3 bytes)
    x_bytes = x.to_bytes(3, 'big')
    sha256_hash = hashlib.sha256(x_bytes).hexdigest()
    last_six_hex_digits = sha256_hash[-6:]
    print(last_six_hex_digits)
    result_int = int(last_six_hex_digits, 16)

    return result_int

分析：

单次加密大致流程:

(轮密钥加-> 字节替换 -> P盒置换)*8192 + 字节替换 + 轮密钥加

轮密钥用一次迭代一次，这个加密也是相当的ez啊，可以考虑使用slide_attack 去打，但仔细观察发现tem_key = l6shad(secret_KEY)，原key可能32位，但是经过这个16shad函数，只有256^{3}的复杂度，虽然轮数比较多，但也不是不能接受，直接开爆。

(因为Python的变量判别等一系列原因，Python开爆效率比较低，这里直接上C++开128线程跑了，半小时就能出结果)

#include <iostream>
#include <bitset>
#include <thread>

int S[] = { 0xc, 0x5, 0x6, 0xb, 0x9, 0x0, 0xa, 0xd, 0x3, 0xe, 0xf, 0x8, 0x4, 0x7, 0x1, 0x2 };
int P[] = { 0, 8, 16, 24, 1, 9, 17, 25, 2, 10, 18, 26, 3, 11, 19, 27, 4, 12, 20, 28, 5, 13, 21, 29, 6, 14, 22, 30, 7, 15, 23, 31 };

int S_16bit(unsigned int x) {
    unsigned int result = 0;
    for (int i = 0; i < 4; i++) {
        int block = (x >> (i * 4)) & 0xF;
        int sbox_result = S[block];
        result |= sbox_result << (i * 4);
    }
    return result;
}

int S_layer(unsigned int x) {
    return (S_16bit(x >> 16) << 16) | S_16bit(x & 0xffff);
}

int P_32bit(unsigned int x) {
    std::bitset<32> binary_result(x);
    std::string permuted_binary;

    for (int i = 31; i > -1; i--) {
        permuted_binary += std::bitset<1>(binary_result[P[i]]).to_string();
    }
    //std::cout << "Pin:" << permuted_binary << std::endl;
    return std::bitset<32>(permuted_binary).to_ulong();
}

int key_schedule(unsigned int key) {
    return ((key << 31 & 0xffffffff) + (key << 30 & 0xffffffff) + key) & 0xffffffff;
}

int enc_round(unsigned int message, unsigned int key) {
    unsigned int result = message ^ key;
    result = S_layer(result);
    result = P_32bit(result);
    return result;
}

int encrypt(unsigned int message, unsigned int key, unsigned int ROUND) {
    unsigned int ciphertext = message;
    unsigned int result;
    for (int i = 0; i < ROUND; i++) {
        ciphertext = enc_round(ciphertext, key);
        key = key_schedule(key);
    }

    ciphertext = S_layer(ciphertext);
    //std::cout << "S:" << ciphertext << std::endl;
    //std::cout << "K:" << key << std::endl;
    result = ciphertext ^ key;

    return result;
}

void solve(int k) {
    unsigned int c = 1018399591;
    std::cout << "k=" << k << std::endl;
    for (unsigned int key = 11047257 + 1024 * k; key < 11047257 + 1024 * (k + 1); key++) {//1 << (6 * 4)

        unsigned int enc = encrypt(1952658276, key, 8192);
        if (enc == c) {
            std::cout << key << std::endl;
            std::cout << key << std::endl;
            std::cout << key << std::endl;
            std::cout << "find it!" << std::endl;

        }
    }
}

int main() {
    std::thread thread_arr[128];
    for (int i = 0; i < 128; i++) {
        thread_arr[i] = std::thread(solve, i);
    }
    for (int i = 0; i < 128; i++) {
        thread_arr[i].join();
    }
    return 0;
}

这里用"d3ct"作为flag头加密，拿去和密文做比较就可以（摁猜）。

Half hour later:

from task_utils import *
from Crypto.Util.number import *
key = 11047257
flag = b''
c = read_from_binary_file('flag.enc')
for i in c:
	dec = decrypt(message=i, key=key, ROUND=8192)
	key = l6shad(key)
	flag+=(long_to_bytes(dec)[::-1])
print(flag)

*myRSA:

Oh, MyGod!

task:

from random import randint
from gmpy2 import *
from Crypto.Util.number import *


class LFSR:
    def __init__(self, seed, length):
        self.mask = 0b10000100100100100100100100100100100100100100100100100100100100100100100100100100100100110
        self.length = length
        self.lengthmask = 2**self.length - 1
        self.state = seed

    def next(self):
        i = self.state & self.mask

        self.state = (self.state << 1) & self.lengthmask
        lastbit = 0
        while i != 0:
            lastbit ^= i & 1
            i = i >> 1
        self.state ^= lastbit
        return lastbit


seed = randint(0, 2**89)
lfsr = LFSR(seed, 89)


def get_bits(n):
    s = ""
    for _ in range(n):
        s += str(lfsr.next())
    return s


bits = 256
a = [get_bits(bits) for _ in range(8)]
b = [get_bits(bits) for _ in range(8)]

p1 = next_prime(int(b[1], 2)) #256
q1 = next_prime(int(b[0] + "".join(a[2:]), 2)) #

p2 = next_prime(int(a[1], 2))
q2 = next_prime(int(a[0] + "".join(b[2:]), 2))

N1 = p1 * q1
N2 = p2 * q2

'''
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, N2)
'''
print(bin(q1)[2+256:2+256+888])
print(bin(q2)[2+648+256:])
#print(f"{N1 = }")
#print(f"{N2 = }")
#print(f"{c = }")

'''
N1 = 11195108435418195710792588075406654238662413452040893604269481198631380853864777816171135346615239847585274781942826320773907414919521767450698159152141823148113043170072260905000812966959448737906045653134710039763987977024660093279241536270954380974093998238962759705207561900626656220185252467266349413165950122829268464816965028949121220409917771866453266522778041491886000765870296070557269360794230165147639201703312790976341766891628037850902489808393224528144341687117276366107884626925409318998153959791998809250576701129098030933612584038842347204032289231076557168670724255156010233010888918002630018693299
N2 = 15100254697650550107773880032815145863356657719287915742500114525591753087962467826081728465512892164117836132237310655696249972190691781679185814089899954980129273157108546566607320409558512492474972517904901612694329245705071789171594962844907667870548108438624866788136327638175865250706483350097727472981522495023856155253124778291684107340441685908190131143526592231859940556416271923298043631447630144435617140894108480182678930181019645093766210388896642127572162172851596331016756329494450522133805279328640942549500999876562756779916153474958590607156569686953857510763692124165713467629066731049974996526071
c = 4814924495615599863001719377787452659409530421473568305028025012566126400664362465878829645297418472853978736123334486954531551369698267539790007454131291197238666548347098462574649698959650399163371262093116196849478966536838813625531493756454672767925688817717023571267320336512019086040845336203876733170680765788230657626290346741730982737645243576591521512217549028162039336681342312618225110504010746912604698079363106352791499951364510694837846064947033912634697178711135807010770985698854383359436879061864935030256963597840531276583023488437671584864430423908673190679945703404235633491522955548722332086120
print(N2.bit_length())
'''

011001100010011001111110001110110010011011100110001001011111111100100111110001010100001100010100101101010101100001011101111111000011111100000011101010010010110001101100000101101000011110101101011111011001101010100101111100011001110100010000111000111100011100011001100010100010110011000101010111000100000100001111010001101111001111010010010101101100101010110000011100100011101101001011110010100100100111101110000000010011010000000011010100101010110111000101001010110001100000001110110100010110011100011101010111001000001111010011011001011110001101011100110111000110000101110000110110111110001001000000101000111000110101111010001101011111000111101111101000010000011100100111011010100100011010001010001110111010100111100100011110011001110111111001000100010111101001010001111110110010101000011110010110010010010010001111111010011110011111111010000011010000011111011101111001011100111111111010
01100110001001100111111000111011001001101110011000100101111111110010011111000101010000110001010010110101010110000101110111111100001111110000001110101001001011000110110000010110100001111010110101111101100110101010010111110001100111010001000011100011110001110001100110001010001011001100010101011100010000010000111101000110111100111101001001010110110010101011000001110010001110110100101111001010010010011110111000000001001101000000001101010010101011011100010100101011000110000000111011010001011001110001110101011100100000111101001101100101111000110101110011011100011000010111000011011011111000100100000010100011100011010111101000110101111100011110111110100001000001110010011101101010010001101000101000111011101010011110010001111001100111011111100100010001011110100101000111111011001010100001111001011001001001001000111111101001111001111111101000001101000001111101110111100101110111100010101

一眼丁真论文 : https://eprint.iacr.org/2023/1562.pdf

以及一眼丁真代码都在里面了，

LFSR , shared bits ，找找看哪里共享了：

2048位的模，256、2048-256位的因子，888位的共享(最大888)。可能888都不到，，大致确定之后就可以开整。

爆改了一下就可以拿来用了:

import random
import time
import logging
from sage.crypto.util import random_blum_prime
# modulus_bit_length = 2048 ， alpha = 0.125 , gamma = 888/2048 , beta1 = 648/2048 , beta2 = 0
def generate_gifp_instance(modulus_bit_length, alpha, gamma, beta1, beta2, seed=None, max_attempts=10):
    """
    Generate two RSA instances with the same modulus length and a shared bit. 
    :param modulus_bit_length: The bit length of the modulus.
    :param alpha: The ratio of the bit length of the larger prime to the modulus bit length.
    :param gamma: The ratio of the bit length of the shared bit to the modulus bit length.
    :param beta1: The ratio of the bit length of the smaller prime in the first RSA instance to the modulus bit length.
    :param beta2: The ratio of the bit length of the smaller prime in the second RSA instance to the modulus bit length.
    :param seed: The seed for the random number generator. If not provided, the current time's microsecond is used.
    :param max_attempts: The maximum number of attempts to generate RSA instances.
    :return: A list of the first RSA instance's primes, a list of the second RSA instance's primes, the shared bit, and the seed.
    """
    N1 = N2 = attempts = 0
    while attempts < max_attempts:
            # If the seed parameter is not provided, use the current time's microsecond as the seed.
        if seed is None:
            seed = int(time.time() * 1e6)
        set_random_seed(seed)
        if beta2<beta1:
            tmp=beta2
            beta2=beta1
            beta1=tmp
        else:
            beta1=beta1
            beta2=beta2
        share_bit_length = int(modulus_bit_length * gamma)
        beta1_bit_length = int(modulus_bit_length * beta1)
        beta2_bit_length = int(modulus_bit_length * beta2)
        share_bit = ZZ(randint(2**(share_bit_length - 1)+1, 2**share_bit_length - 1))
        p_bit_length = int(modulus_bit_length * (1-alpha))
        q_bit_length = int(modulus_bit_length * alpha)
        MSB4p1 = ZZ(randint(2**int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*gamma-modulus_bit_length*beta1-1)+1, 2**int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*gamma-modulus_bit_length*beta1) - 1))
        MSB4p2 = ZZ(randint(2**int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*gamma-modulus_bit_length*beta2-1)+1, 2**int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*gamma-modulus_bit_length*beta2) - 1))
        p1 = random_blum_prime(MSB4p1*2**int(modulus_bit_length*gamma+modulus_bit_length*beta1) + share_bit* 2**(beta1_bit_length)+2**(beta1_bit_length - 1), MSB4p1*2**int(modulus_bit_length*gamma+modulus_bit_length*beta1) + share_bit* 2**(beta1_bit_length)+2**beta1_bit_length - 1)
        p2 = random_blum_prime(MSB4p2*2**int(modulus_bit_length*gamma+modulus_bit_length*beta2) + share_bit* 2**(beta2_bit_length)+2**(beta2_bit_length - 1), MSB4p2*2**int(modulus_bit_length*gamma+modulus_bit_length*beta2) + share_bit* 2**(beta2_bit_length)+2**beta2_bit_length - 1)
        q1 = random_blum_prime(2**(q_bit_length - 1), 2**q_bit_length - 1)
        q2 = random_blum_prime(2**(q_bit_length - 1), 2**q_bit_length - 1)
        N1 = p1 * q1
        N2 = p2 * q2
        desired_solution = (int(bin(p1)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta1):],2)* 2**int(beta2*modulus_bit_length-beta1*modulus_bit_length)-int(bin(p2)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta2):],2),int(bin(MSB4p1)[2:],2)-int(bin(MSB4p2)[2:],2),q2)
        if N1.nbits() != modulus_bit_length or N2.nbits() != modulus_bit_length:
            attempts += 1
            seed = int(time.time() * 1e6)
            print(f"Regenerated seed: {seed}")
        else:
            print(f"Geenerated gifp instance successfully with seed: {seed}")
            print(f'share_bit: {bin(share_bit)[2:]}')
            print(f'p1: {p1}')
            print(f'MSB4p1: {bin(MSB4p1)[2:]}')
            print(f'share_bit4p1: {bin(p1)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*gamma-modulus_bit_length*beta1):2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta1)]}')
            print(f'LSB4p1: {bin(p1)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta1):]}')
            print(f'q1: {q1}')
            print(f'N1: {N1}')
            print(f'p2: {p2}')
            print(f'MSB4p2: {bin(MSB4p2)[2:]}')
            print(f'share_bit4p2: {bin(p2)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*gamma-modulus_bit_length*beta2):2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta2)]}')
            print(f'LSB4p2: {bin(p2)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta2):]}')
            print(f'q2: {q2}')
            print(f'N2: {N2}')
            print(f"The desired solution is (x0, y0, z0, w0) = {(int(bin(p1)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta1):],2)* 2**int(beta2*modulus_bit_length-beta1*modulus_bit_length)-int(bin(p2)[2+int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*beta2):],2),int(bin(MSB4p1)[2:],2)-int(bin(MSB4p2)[2:],2),q2,p2)}")
            return [p1, q1, N1], [p2, q2, N2], share_bit, desired_solution
    logging.warning(f"Failed to generate RSA instances after {max_attempts} attempts.")
    return None

def create_lattice(pr, shifts, bounds, order="invlex", sort_shifts_reverse=False, sort_monomials_reverse=False):
    """
    Creates a lattice from a list of shift polynomials.
    :param pr: the polynomial ring
    :param shifts: the shifts
    :param bounds: the bounds
    :param order: the order to sort the shifts/monomials by
    :param sort_shifts_reverse: set to true to sort the shifts in reverse order
    :param sort_monomials_reverse: set to true to sort the monomials in reverse order
    :return: a tuple of lattice and list of monomials
    """
    print(f"Creating a lattice with {len(shifts)} shifts (order = {order}, sort_shifts_reverse = {sort_shifts_reverse}, sort_monomials_reverse = {sort_monomials_reverse})...")
    if pr.ngens() > 1:
        pr_ = pr.change_ring(ZZ, order=order)
        shifts = [pr_(shift) for shift in shifts]

    monomials = set()
    for shift in shifts:
        monomials.update(shift.monomials())

    shifts.sort(reverse=sort_shifts_reverse)
    monomials = sorted(monomials, reverse=sort_monomials_reverse)
    L = matrix(ZZ, len(shifts), len(monomials))
    for row, shift in enumerate(shifts):
        for col, monomial in enumerate(monomials):
            L[row, col] = shift.monomial_coefficient(monomial) * monomial(*bounds)

    monomials = [pr(monomial) for monomial in monomials]
    return L, monomials

def log_lattice(L):
    """
    Logs a lattice.
    :param L: the lattice
    """
    #for row in range(L.nrows()):
    #    print(L[row,:])
    for row in range(L.nrows()):
        r = ""
        for col in range(L.ncols()):
            if L[row, col] == 0:
                r += "_ "
            else:
                r += "X "
        print(r)
def reduce_lattice(L, delta=0.8):
    """
    Reduces a lattice basis using a lattice reduction algorithm (currently LLL).
    :param L: the lattice basis
    :param delta: the delta parameter for LLL (default: 0.8)
    :return: the reduced basis
    """
    print(f"Reducing a {L.nrows()} x {L.ncols()} lattice...")
    return L.LLL(delta)

def reconstruct_polynomials(B, f, modulus, monomials, bounds):
    """
    Reconstructs polynomials from the lattice basis in the monomials.
    :param B: the lattice basis
    :param f: the original polynomial (if set to None, polynomials will not be divided by f if possible)
    :param modulus: the original modulus
    :param monomials: the monomials
    :param bounds: the bounds
    :return: a list of polynomials
    """
    print(f"Reconstructing polynomials (divide_original = {f is not None}, modulus_bound = {modulus is not None})...")
    print(f"Reconstructing polynomials with bounds: {bounds}")
    polynomials = []
    for row in range(B.nrows()):
        norm_squared = 0
        ww = 0
        polynomial = 0
        for col, monomial in enumerate(monomials):
            if B[row, col] == 0:
                continue
            norm_squared += B[row, col] ** 2
            ww += 1
            assert B[row, col] % monomial(*bounds) == 0
            polynomial += B[row, col] * monomial // monomial(*bounds)

        # Equivalent to norm >= modulus / sqrt(w)
        if modulus is not None and norm_squared * ww >= modulus ** 2:
            print(f"Row {row} is too large, ignoring...")
            continue

        if f is not None and polynomial % f == 0:
            print(f"Original polynomial divides reconstructed polynomial at row {row}, dividing...")
            polynomial //= f

        if polynomial.is_constant():
            print(f"Polynomial at row {row} is constant, ignoring...")
            continue

        polynomials.append(polynomial)

    print(f"Reconstructed {len(polynomials)} polynomials")
    return polynomials

def find_roots_univariate(x, polynomial):
    """
    Returns a generator generating all roots of a univariate polynomial in an unknown.
    :param x: the unknown
    :param polynomial: the polynomial
    :return: a generator generating dicts of (x: root) entries
    """
    if polynomial.is_constant():
        return

    for root in polynomial.roots(multiplicities=False):
        if root != 0:
            yield {x: int(root)}


def find_roots_groebner(pr, unknown_modular, polynomials,bounds):
    """
    Returns a generator generating all roots of a polynomial in some unknowns.
    Uses Groebner bases to find the roots.
    :param N1: the modulus of the first RSA instance
    :param N2: the modulus of the second RSA instance
    :param pr: the polynomial ring
    :param desired_solution: the desired root (x0, y0, z0, w0), just used for debug
    :param unknown_modular: unknown modular M^m*N1^t, just used for debug
    :param polynomials: the reconstructed polynomials
    :param bounds: the bounds
    :return: a generator generating dicts of (x0: x0root, x1: x1root, ...) entries
    """
    gens = pr.gens()
    s = Sequence(polynomials, pr.change_ring(QQ, order="lex"))
    for ii in range(len(s)):
        print(f"Polynomials in Sequence: {s[ii]}")

    while len(s) > 0:
        start_time_gb=time.time()
        G = s.groebner_basis()
        print(f"Sequence length: {len(s)}, Groebner basis length: {len(G)}")
        if len(G) == len(gens):
            end_time_gb=time.time()
            print(f'The time taken by gb is {end_time_gb-start_time_gb}')
            print(f"Found Groebner basis with length {len(gens)}, trying to find roots...")
            roots = {}
            for ii in range(len(G)):
                print(f"Groebner basis {G[ii]}")
            for polynomial in G:
                vars = polynomial.variables()
                if len(vars) == 1:
                    for root in find_roots_univariate(vars[0], polynomial.univariate_polynomial()):
                        roots |= root

            if len(roots) == pr.ngens():
                yield roots
                return

            return
        else:
            # Remove last element (the biggest vector) and try again.
            s.pop()

def eliminate_N2(f, modular):
    pr = ZZ["x", "y", "z"]
    x, y, z= pr.gens()
    tmp_poly=0
    for mono in f.monomials():
        if f.monomial_coefficient(mono)%modular==0:
            tmp_poly+=mono*f.monomial_coefficient(mono)
        else:
            tmp_poly+=mono*(f.monomial_coefficient(mono)% modular)
    return tmp_poly



def modular_gifp(unknown_modular, f, M, N1, N2, m, t, X, Y, Z):
    """
    Computes Generalized Implicit Factorization Problem.
    More information: Feng, Yansong and Nitaj, Abderrahmane and Pan, Yanbin, "Generalized Implicit Factorization Problem"
    :param desired_solution: the desired root (x0, y0, z0, w0), just used for debug
    :param unknown_modular: unknown modular M^m*N1^t, just used for debug
    :param f: the polynomial
    :param M: 2^(|\beta1-\beta2|*n)
    :param N1: the modulus of the first RSA instance
    :param N2: the modulus of the second RSA instance
    :param m: the number of shifts
    :param s: a parameter
    :param t: a parameter
    :param X: the bound for x
    :param Y: the bound for y
    :param Z: the bound for z
    :param W: the bound for w
    :return: a generator generating small roots of the polynomial
    """
    f = f.change_ring(ZZ)

    pr = ZZ["x", "y", "z"]
    x, y, z = pr.gens()

    print("Generating shifts...")

    shifts = []

    modular = M^m*N1^t

    print(f'modular is {modular}')
    N2_inverse = inverse_mod(N2, modular)
    print(f'N2^{-1}: {N2_inverse}')
    for ii in range(m + 1):
        for jj in range(m - ii + 1):
            g = (y*z) ** jj * f ** (ii) * M ** (m - ii) * N1 ** max(t - ii, 0)
            print(f'Initial polynomial shift: {g}')
            shifts.append(g)
            print(f'Add shift: {g}')

    print('Generating lattice for gifp')
    L, monomials = create_lattice(pr, shifts, [X, Y, Z])
    log_lattice(L)
    print('Reduce the lattice')
    start_time_LLL=time.time()
    L = reduce_lattice(L)
    end_time_LLL=time.time()
    print(f'The time taken by LLL is {end_time_LLL-start_time_LLL}')
    log_lattice(L)

    polynomials = reconstruct_polynomials(L, f, unknown_modular, monomials, [X, Y, Z])
    for poly in polynomials:
        print(f'Polynomials after reconstructing from short vectors: {poly}')

    for roots in find_roots_groebner(pr, unknown_modular, polynomials,[X, Y, Z]):
        yield roots[x], roots[y], roots[z]

def attack_gifp_instance(modulus_bit_length, alpha, gamma, beta1, beta2, m=1, seed=None, t=None):
    """
    Attack an GIFP instance with parameters
    :param modulus_bit_length: the bit length of the modulus
    :param alpha, gamma, beta1, beta2: parameters for the GIFP instance
    :param m: a given parameter for controlling the lattice dimension (default: 3)
    :param seed: The seed for the random number generator. If not provided, the current time's microsecond is used.
    :param t: a parameter
    :return: 1 if attack succeeds else 0
    """
    if beta2<beta1:
        tmp=beta2
        beta2=beta1
        beta1=tmp
    else:
        beta1=beta1
        beta2=beta2
    x, y, z = ZZ["x", "y", "z"].gens()
    #N1_list, N2_list, share_bit, desired_solution = generate_gifp_instance(modulus_bit_length, alpha, gamma, beta1, beta2, seed, max_attempts=10)
    N1 = 11195108435418195710792588075406654238662413452040893604269481198631380853864777816171135346615239847585274781942826320773907414919521767450698159152141823148113043170072260905000812966959448737906045653134710039763987977024660093279241536270954380974093998238962759705207561900626656220185252467266349413165950122829268464816965028949121220409917771866453266522778041491886000765870296070557269360794230165147639201703312790976341766891628037850902489808393224528144341687117276366107884626925409318998153959791998809250576701129098030933612584038842347204032289231076557168670724255156010233010888918002630018693299#N1_list[2]
    N2 = 15100254697650550107773880032815145863356657719287915742500114525591753087962467826081728465512892164117836132237310655696249972190691781679185814089899954980129273157108546566607320409558512492474972517904901612694329245705071789171594962844907667870548108438624866788136327638175865250706483350097727472981522495023856155253124778291684107340441685908190131143526592231859940556416271923298043631447630144435617140894108480182678930181019645093766210388896642127572162172851596331016756329494450522133805279328640942549500999876562756779916153474958590607156569686953857510763692124165713467629066731049974996526071#N2_list[2]
    N1_list = [926811193643434749652052036902780747582254462279473779]
    print('Generating polynimial f')
    f = x*z + 2**(int(beta2*modulus_bit_length)+int(gamma*modulus_bit_length))*y*z+N2
    print(f'Polynomial f: {f}')
    X = Integer(2 ** int(beta2*modulus_bit_length))
    Y = Integer(2 ** int(modulus_bit_length*1-modulus_bit_length*alpha-modulus_bit_length*gamma-modulus_bit_length*beta1))
    Z = Integer(2 ** int(alpha * modulus_bit_length))
    M = Integer(2 ** int(modulus_bit_length*beta2-modulus_bit_length*beta1))
    print(f'M = {M}')
    t = round((1 - sqrt(alpha)) * m) if t is None else t
    unknown_modular = M ** m * N1 ** t
    print(f"Trying m = {m}, t = {t}...")
    gb_tmp = []
    for x0, y0, z0 in modular_gifp(unknown_modular, f, M, N1, N2, m, t, X, Y, Z):
        v = int(f(x0, y0, z0))
        if v == 0:
            p2 = N2/z0
            q2 = z0
            p1 = N2/z0+x0+y0*(2**int(gamma*modulus_bit_length+beta2*modulus_bit_length))
            q1 = N1/p1
            if p1 is not None and q1 is not None and p2 is not None and q2 is not None :
                print(f"Succeeded!")
                print(f"Found p1 = {p1}")
                print(f"Found q1 = {q1}")
                print(f"Found p2 = {p2}")
                print(f"Found q2 = {q2}")
                return 1
    else:
        print(f"Failed!")
        return 0


modulus_bit_length, alpha, gamma, beta1, beta2, m = 2048, 0.125, 0.43359375, 0.31640625, 0, 6
result = attack_gifp_instance(modulus_bit_length, alpha, gamma, beta1, beta2, m)
print(result)

但是注意到，原论文给的板子是半自动的，得手动去解后面gb基生成的东西，这里m=6也弄不出好的结果，得调到12、14这样力大砖飞，然后从gb基生成的有效信息里找N的分解才可以。

板子选手，立正！

到这里我就不想做下去也不想看了，估计比赛的时候哪里参数没调对，结果出不来跑了半小时放弃。之后有新的发现再来更新。

*d3matrix1:

task:

from sage.all import *
import hashlib
from Crypto.Cipher import AES
from flag import flag
p = 2**302 + 307
k = 140
n = 10
alpha = 3

GFp = GF(p)
def pad(m):
    return m + (16-(len(m)%16))*bytes([16-(len(m)%16)])
def keygen():
    E = random_matrix(GFp , n , n)
    while E.rank() != n:
        E = random_matrix(GFp , n , n)
    Alist = []

    for i in range(k):
        A = random_matrix(ZZ , n , n , x=0 , y = alpha)
        A = Matrix(GFp , A)
        while A.rank() != n:
            A = random_matrix(ZZ , n , n , x=0 , y = alpha)
            A = Matrix(GFp , A)
        Alist.append(A)
    E_1 = E**(-1)
    Dlist = []
    for i in range(k):
        D = E * Alist[i] *E_1
        Dlist.append(D)
    return Alist , Dlist , E
# 求 Alist 
Alist , Dlist , E= keygen()
save(Dlist ,"Dlist.sobj")
Asumlist = []
for i in range(k):
    tempsum = 0
    for x in range(n):
        for y in range(n):
            tempsum += int(Alist[i][x,y])
    Asumlist.append(tempsum)
print(Asumlist)
key = hashlib.sha256(str(Asumlist).encode()).digest()
aes = AES.new(key = key , mode = AES.MODE_ECB)
flagc = aes.encrypt(pad(flag))
print(flagc)

#b'\x83\x1a)LB\xa6\xfb\xacS\xfa\xd03Q\x83c\xcd\xe6K\xbeI\xfc\x90_\xde=`nM&z\xca\x81\xcf\xdd\xde\x0c\x1b\xf8[C\xdc%\x97\xb2\xa4\xb4\xf6T'

没做出来，也没思路，赛后交流时间，打听到：

利用

A*(k*E)A^{-1}=kE

利用展平的技巧去找到公钥矩阵子集和满足这个，用BKZ来恢复矩阵，听得云里雾里的，有时间再实验吧。

d3matrix2:

由Nep的师傅zealot解出，这里借记、分享。

task:

from sage.all import *
from random import randint , shuffle
import hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from flag import flag
p = 2**1105 - 1335
k = 99
n = 24
alpha = 2

GFp = GF(p)
def pad(m):
    return m + (16-(len(m)%16))*bytes([16-(len(m)%16)])
def genmatrix(x , y):
    M = random_matrix(ZZ , n , n , x = x , y = y+1)
    M = Matrix(GFp , M)
    while M.rank()!=n:
        M = random_matrix(ZZ , n , n , x = x , y = y+1)
        M = Matrix(GFp , M)
    return M
def keygen():
    Alist = []
    for i in range(k):
        A = genmatrix(0 , alpha)
        Alist.append(A)
    D = genmatrix(0 , alpha)

    E = random_matrix(GFp , n , n)
    while E.rank() != n:
        E = random_matrix(GFp , n , n)

    E_1 = E**(-1)
    _Alist = []
    for i in range(k):
        _A = E * Alist[i]*D *E_1
        _Alist.append(_A)
    return _Alist , (E , D , Alist)

def enc(pk , m):
    rangelist = list(range(k))
    shuffle(rangelist)
    c = pk[rangelist[0]]
    for i in range(k-1):
        c *= pk[rangelist[i+1]]

    key = hashlib.sha256(str(rangelist).encode()).digest()
    aes = AES.new(key = key , mode = AES.MODE_ECB)
    flagc = aes.encrypt(pad(m))
    return c , flagc

pk , sk = keygen()
save(pk ,"pk.sobj")
c , flagc = enc(pk , flag)

save(c , "c.sobj")
print(flagc)
#b'lD\xfc\xf4\xdb+\xcd\xbd\xff\x1a!C\x0e\x16\t\xa7:<\x94<\xac(M(i\xee\xf9B\xc7\xea}\x1b\x86\xf8e\xff\xa8<\xc2\xf0\x02P\xd8%$\xc3\xe9-'

pk.sobj

c.sobj

注意到题目给的c矩阵，里面藏了Alist的子集，我们得找到用了写A矩阵，通过乘逆矩阵消掉密文中的一个A，密文的迹会变小，否则变大，通过这个规律可以观察得到我们想要的未知密钥位，

pk=load('pk.sobj')
c=load('c.sobj')
p = 2**1105 - 1335
k = 99
n = 24

F=GF(p)
res=[]

def traverse(res,c):
        print(res)
        if len(res)==k:
                print('result found:',res)
                return
        ctrace=c.trace()
        for j in range(len(pk)):
                if j not in res:
                        tmp=(pk[j]^-1)*c
                        if tmp.trace()<c.trace():
                                traverse(res+[j],tmp)


traverse([],c)

#result found: [29, 36, 93, 58, 19, 7, 27, 41, 17, 56, 14, 96, 53, 30, 47, 74, 70, 85, 16, 4, 23, 92, 25, 34, 15, 42, 84, 76, 98, 62, 91, 28, 86, 6, 12, 87, 89, 37, 97, 94, 2, 57, 59, 95, 52, 66, 68, 8, 20, 64, 43, 46, 24, 90, 81, 39, 35, 54, 13, 73, 75, 67, 44, 83, 38, 78, 5, 80, 18, 31, 63, 55, 32, 49, 48, 0, 3, 10, 60, 72, 71, 33, 50, 9, 26, 51, 79, 22, 65, 21, 82, 77, 61, 45, 11, 40, 69, 88, 1]
import hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
res=[29, 36, 93, 58, 19, 7, 27, 41, 17, 56, 14, 96, 53, 30, 47, 74, 70, 85, 16, 4, 23, 92, 25, 34, 15, 42, 84, 76, 98, 62, 91, 28, 86, 6, 12, 87, 89, 37, 97, 94, 2, 57, 59, 95, 52, 66, 68, 8, 20, 64, 43, 46, 24, 90, 81, 39, 35, 54, 13, 73, 75, 67, 44, 83, 38, 78, 5, 80, 18, 31, 63, 55, 32, 49, 48, 0, 3, 10, 60, 72, 71, 33, 50, 9, 26, 51, 79, 22, 65, 21, 82, 77, 61, 45, 11, 40, 69, 88, 1]
enc=b'lD\xfc\xf4\xdb+\xcd\xbd\xff\x1a!C\x0e\x16\t\xa7:<\x94<\xac(M(i\xee\xf9B\xc7\xea}\x1b\x86\xf8e\xff\xa8<\xc2\xf0\x02P\xd8%$\xc3\xe9-'

key = hashlib.sha256(str(res).encode()).digest()
aes = AES.new(key = key , mode = AES.MODE_ECB)
flag = aes.decrypt(enc)
print(flag)

我对着范数、行列式、一堆奇奇怪怪的分析了半天，到最后选择去预习迹了

*enctwice:

task:

import os
import secret
from random import seed, choice
from Crypto.Cipher import ChaCha20,AES
from Crypto.Util.number import *
from string import ascii_letters, digits
from hashlib import sha256

D3 = 300

def proof_of_work():
    seed(os.urandom(8))
    proof = ''.join([choice(ascii_letters + digits) for _ in range(20)])
    digest = sha256(proof.encode('latin-1')).hexdigest()
    print('sha256(XXXX + {}) == {}'.format(proof[4:], digest))
    msg = input('Give me XXXX >')
    if msg != proof[:4]:
        return False
    return True

def pad(msg):
    need = (0x20) - (len(msg) & (0x1F))
    return msg + bytes([need]) * need

def unpad(msg):
    need = msg[-1]
    for i in msg[-need:]:
        assert i == need
    return msg[:-need]

class MYENC:
    def __init__(self):
        self.CHACHA_KEY = os.urandom(32)
        self.AUTH_DATA = os.urandom(32)
        self.AES_KEY = os.urandom(32)
        self.P = getPrime(256)
        self.LIMIT = 2**250
        self.X = getPrime(251)
        self.LEGAL = "0123456789ABCDEF"
    
    def hash(self, r, s, ct):
        # L = |AUTH|CT|AUTH_LEN|CT_LEN
        L = self.AUTH_DATA + ct + long_to_bytes(len(self.AUTH_DATA), 16) + long_to_bytes(len(ct), 16)
        res = 0
        for i in range(0, len(L), 32):
            res = (res + bytes_to_long(L[i:i+32]) + 2**256) * r % self.P
        return (res + s) % self.LIMIT
    
    def encrypt1(self, msg):
        msg = pad(msg)
        nonce = os.urandom(12)
        cipher = ChaCha20.new(key = self.CHACHA_KEY, nonce = nonce)
        ct = cipher.encrypt(bytes([0]) * 32 + msg)
        r, s, ct = bytes_to_long(ct[:16]), bytes_to_long(ct[16:32]), ct[32:]
        tag = self.hash(r, s, ct)

        return ct, tag, nonce
        
    def encrypt2(self, msg):
        msg = pad(msg)
        iv = os.urandom(16)
        cipher = AES.new(key = self.AES_KEY, mode = AES.MODE_OFB, iv = iv)
        ct = cipher.encrypt(msg)
        return ct, iv
    
    def encrypt_msg(self, msg):
        assert len(msg) < 32
        ct1, tag, nonce = self.encrypt1(msg)
        ct2, iv = self.encrypt2(msg)
        print(tag.bit_length())
        return ct1 + long_to_bytes(tag + bytes_to_long(ct2) * self.X) + iv + nonce

    # enc = ct1 | tag + ct2*X | iv | nonce 
    #一阶段目标是拿到: enc = ct1 | ct2 | iv | nonce 
    # assert len(msg) < 32
    def decrypt1(self, msg, tag, nonce):
        cipher = ChaCha20.new(key = self.CHACHA_KEY, nonce = nonce)
        pt = cipher.decrypt(bytes([0]) * 32 + msg)
        r, s, pt = bytes_to_long(pt[:16]), bytes_to_long(pt[16:32]), pt[32:]
        assert tag == self.hash(r, s, msg)

        return unpad(pt)
    
    def decrypt2(self, msg, iv):
        cipher = AES.new(key = self.AES_KEY, mode = AES.MODE_OFB, iv = iv)
        pt = cipher.decrypt(msg)
        return unpad(pt)
    
    def verify_msg(self, msg):
        ct1, val, iv, nonce = msg[:32], bytes_to_long(msg[32:-28]), msg[-28:-12], msg[-12:]
        tag, ct2 = val % self.X, long_to_bytes(val // self.X)
        pt1 = self.decrypt1(ct1, tag, nonce)
        pt2 = self.decrypt2(ct2, iv)
        for i, j in zip(pt1, pt2):
            assert i == j
        return "Valid message!"
    
    def change_X(self, msg):
        for i in msg:
            assert  i in self.LEGAL
        try:
            new_X = eval(msg)
        except:
            new_X = eval("0x" + msg)
        print(f'new_X = {new_X}')
        new_X = getPrime(new_X)
        print(new_X.bit_length())
        if new_X < self.LIMIT:
            return  "Invalid X!"
        self.X = new_X
        return "Valid X!"

#一阶段 ， 可以控制加密机 和 控制X
#二阶段 ， 可以打Oracle Attack

#encrypt1 chacha pad
#encrypt2 AES OFB pad

if __name__ == "__main__":
    
    #if not proof_of_work():
    #    exit()
    
    myenc = MYENC()
    
    cnt = 7
    print(f"Now, you have {cnt} chances to modify the encryption or encrypt your own message.")
    print(f"Good luck!")
    
    for i in range(cnt):
        type = input("> ")
        if "encrypt" in type : #加密
            try:
                msg = bytes.fromhex(input("input your message >").replace(" ","").strip())[:31]
                res = myenc.encrypt_msg(msg)
                print(res.hex())
            except:
                print("Invalid message!")
        
        elif "change X" in type :  #改变
            try:
                msg = input("input your X >")[:2]
                res = myenc.change_X(msg)
                print(res)
            except:
                print("Invalid X!")
    
    flag = secret.flag
    enc_flag = myenc.encrypt_msg(flag)
    print(f"Here is your flag:")
    print(enc_flag.hex())
    
    print(f"Now, feel free to verify your encrypted message!")
    
    while(True):
        msg = input(">")
        if msg == "exit" :
            break
        try:  #验证
            msg = bytes.fromhex(msg.replace(" ","").strip())
            res = myenc.verify_msg(msg)
            print(res)
        except:
            print("Invalid message!")

分析:

密文结构:enc = ct1 | ct2*X + tag | iv | nonce 
ct1由chacha20流密码算法加密，但是ct1有hash校验无法修改
ct2由OFB分组模式的AES加密，ct2有机会可以动

一阶段:

• 给我们七次交互的机会去选择Change X or Get encryptplain。
• 还给了flag的密文。

二阶段:

• 无限次的交互，提供我们校验加解密是否合法的函数。

注意到ct2 * X,有个冷不丁的X在里面，我们就不知道ct2了，唯一的机会在一阶段的交互里面，那么我们就可以通过AGCD的方法，通过 ct2*X + tag ，这个集，拿到 X。

注意到第二部分用的是zip去校验密文的解密结果，如果说ct2的unpad合法，这个校验的比较还是过得去的，返回的结果将会是valid message，那么这里就是一个正常的Padding Oracle Attack了

所有的分析看起来那么合理，那么美好，这就是送分题了，结果写脚本发现，**！change X好像只能改到256bit！how to AGCD?赛后一问发现:

盖伦发发！开头藏了一个D3可以改到300bit，使得AGCD能够求出X，听到这个消息我差点晕了。

接下来就正常地写脚本就好:

solution:

from Crypto.Util.number import *
from pwn import *

def SDA_solver(xs, rho):
    # 1. Construct lattice
    t = len(xs) - 1
    B = Matrix(ZZ, t+1, t+1)
    for i in range(t+1):
        B[i, i] = -xs[0]
        if i == 0:
            B[0, i] = 2^(rho+1)
        else:
            B[0, i] = xs[i]
    # 2. LLL and find p
    v = B.LLL()[0]
    q0 = v[0] // 2^(rho+1)
    p = xs[0] // q0
    return p,q0


def generate_testcase(rbits, pbits):
    rbit = int(rbits)
    pbit = int(pbits)
    p = getPrime(pbit)
    ns = [p*getPrime(pbit) + getPrime(rbit) for i in range(6)]
    return p, ns

def send_payload(payload):
    io.recvuntil(b'>')
    io.sendline( ( payload.hex() ).encode() )
    res = io.recvline()
    if res == b'Invalid message!\n':
        return 0
    else:
        return 1

def getPad(D,index):
    ct2_B = 0

    if D==[]:
        return ct2_B
    count = len(D)-1

    for i in D:
        ct2_B += ((i^^(32-index)) << (8*count))
        count -= 1

    return ct2_B

def My_decrypt(D,ct2):
    key = 0
    for i in range(32):
        key += D[(31-i)] << i*8
    msg = long_to_bytes(ct2^^key)
    print(f'find it : {msg}')

def Padding_Oracle(ct1,ct2,tag,X,nonce,iv):
    
    D_iv = []
    for index in range(31,-1,-1):
        ct2_F = (ct2 >> (32-index)*8) << (32-index)*8
        orinl_char = (ct2 >> (31-index)*8) & 0xff
        ct2_B= getPad(D_iv,index)
        for test in range(256):
            if test == orinl_char and index == 31:
                continue
            pad_num_control = 32 - index
            ct2_ = ct2_F + (test << (31-index)*8) + ct2_B

            payload = ct1 + long_to_bytes(tag + X*ct2_) + iv + nonce
            if send_payload(payload):
                D_iv.insert(0,pad_num_control^^test)
                print(f'index : {index}')
                print(len(D_iv))
                break

    My_decrypt(D_iv,ct2)

io = remote('115.159.221.202',11110)
#proof

io.recvuntil(b'> ')
io.sendline(b'change X')
io.recvuntil(b'input your X >')
io.sendline(b'D3')

ns = []
for _ in range(6):
    io.recvuntil(b'> ')
    io.sendline(b'encrypt')
    io.recvuntil(b'input your message >')
    payload = b'Love March 7th'.hex()
    io.sendline(payload.encode())
    data = io.recvline().decode()[:-1]
    ns.append(int(data[32*2:2*(32+70)],16))

io.recvuntil(b'Here is your flag:\n')
flag_enc = io.recvline().decode()[:-1]

print(flag_enc)
ns.insert(0,int(flag_enc[32*2:2*(32+70)],16))

print(len(ns))
X,ct2 = SDA_solver(ns, 250)

ct1 = bytes.fromhex(flag_enc[:2*32])
tag = int(flag_enc[32*2:2*(32+70)],16) - X*ct2
iv = bytes.fromhex(flag_enc[2*(32+70):2*(32+70+16)])
nonce = bytes.fromhex(flag_enc[2*(32+70+16):2*(32+70+16+12)])

if isPrime(X) != 1:
    print('try again!')
    io.close()
    exit()
print('ok! Game start!')

Padding_Oracle(ct1,ct2,tag,X,nonce,iv)

赛后总结：

痛风两个周，生不如死，躺在床上我时常在想要不要继续学习密码学知识，继续走下去收获不到钱，也没有机会像别的方向选手一样有那么多的机会去干一笔大的，而且越学下去越发觉好像Everything is meanless。

这把打完发现很多东西，原来都是有机会的，而且也不复杂，有点不甘心，丢了很多分，这些大部分分析都是赛时做出来的，就差临门一脚，不太甘心，想了想这把还是得多开了，那么这场就当做第一把复活赛了。认真看题，平时积累，总有能出力的时候。