World Wide CTF 2024

没打这个比赛，后面闲着做了做几道，剩下的以后再看

epsilonDH

题目

from Crypto.Util.number import getStrongPrime, getRandomNBitInteger, bytes_to_long
import os

p = getStrongPrime(1024)
flag = os.getenv("flag", "wwf{<REDACTED>}").encode()

class Epsilon:
    def __init__(self, a, b):
        self.a, self.b = a, b
    
    def __add__(self, other):
        if type(other) == int: other = Epsilon(other, 0)
        return Epsilon(self.a + other.a, self.b + other.b)
    def __radd__(self, other): return self.__add__(other)

    def __mul__(self, other):
        if type(other) == int: other = Epsilon(other, 0)
        return Epsilon(self.a * other.a, self.a * other.b + other.a * self.b)
    def __rmul__(self, other): return self.__mul__(other)

    def __mod__(self, other: int):
        return Epsilon(self.a % other, self.b % other)
    
    def __repr__(self): return f"{self.a} + {self.b}ɛ"

    @staticmethod
    def getRandomBits(n):
        return Epsilon(getRandomNBitInteger(n), getRandomNBitInteger(n))

def powm(b, e, m):
    r = 1
    while e > 1:
        if e & 1:
            r = (r * b) % m
        b = (b * b)  % m
        e >>= 1
    return (b * r) % m

ɛ = Epsilon(0, 1)
g = ɛ.getRandomBits(1024)
m = bytes_to_long(flag)
assert m < p
A = powm(g, m, p)

print(f"{p = }")
print(f"{g = }")
print(f"{A = }")

有

$$g^n=(a^n,na^{n-1}b)$$

很显然可以直接求出n

from Crypto.Util.number import *

class Epsilon:
    def __init__(self, a, b):
        self.a, self.b = a, b

    def __add__(self, other):
        if type(other) == int:
            other = Epsilon(other, 0)
        return Epsilon(self.a + other.a, self.b + other.b)

    def __radd__(self, other):
        return self.__add__(other)

    def __mul__(self, other):
        if type(other) == int:
            other = Epsilon(other, 0)
        return Epsilon(self.a * other.a, self.a * other.b + other.a * self.b)

    def __rmul__(self, other):
        return self.__mul__(other)

    def __mod__(self, other: int):
        return Epsilon(self.a % other, self.b % other)

    def __repr__(self):
        return f"{self.a} + {self.b}ɛ"

    @staticmethod
    def getRandomBits(n):
        return Epsilon(getRandomNBitInteger(n), getRandomNBitInteger(n))


def powm(b, e, m):
    r = 1
    while e > 1:
        if e & 1:
            r = (r * b) % m
        b = (b * b) % m
        e >>= 1
    return (b * r) % m


p = 173924944755645003178406095718617168013285320974193311533464918516351624141198287888308296721497553891802368640344837769848433705383843820088678374708528763495103734488139368870389319280613181418960926879728892929013723036956818870578758055144789952650214552781344528622703875374067812710366180881422848078127
g = (
    153222010878956025592659771364999461265827693159532862299380012549533704470078014065110463612108844661289052080113198166134196684645743591092035461757997498335465019478118882739217108862526250347939116529661007420054504044554198442479469991584947626223020239910145162698053768142977329057860163194054350707249,
    172891042743500566967040288858220451145776247635832845268756172370398885506225014595399937064138727095012954778403481826951857306135326675358326250562011754152669045113179084291737802426967956129601732530346663460456772733886633658030480267226610996560624379249886941665142384623344612516572694197005870648544,
)
A = (
    111358852433093434730054197107140594544307303976075171645711474646957878889456280742672183479878216988442037548855367380131019369757301409440037291726826948896290153981733240859717678222235993520619121828503359668550259222802623131077882382174117682287404839404525320091636778728025592053329591735052259548204,
    45354415949210290456746549581237886628185346518296265188224888250560968013577364380436312628842962917052795341010011570997705657164666282067908433629612354440756444902895692385443905786057605548586533595209894409891955713650856537806150873335015064767898088756645985769501205659617651498842444073593828856739,
)
g = Epsilon(*g)
A = Epsilon(*A)

a = A.a * inverse(g.a, p) % p
b = g.b
m = A.b * inverse(b, p) * inverse(a, p) % p
print(long_to_bytes(m))

Just Lattice

题目

import numpy as np
from secret import flag


def gen(q, n, N, sigma):
    t = np.random.randint(0, high=q // 2, size=n)
    s = np.concatenate([np.ones(1, dtype=np.int32), t])
    A = np.random.randint(0, high=q // 2, size=(N, n))
    e = np.round(np.random.randn(N) * sigma**2).astype(np.int32) % q
    b = ((np.dot(A, t) + e).reshape(-1, 1)) % q
    P = np.hstack([b, -A])
    return P, s


def enc(P, M, q):
    N = P.shape[0]
    n = len(M)
    r = np.random.randint(0, 2, (n, N))
    Z = np.zeros((n, P.shape[1]), dtype=np.int32)
    Z[:, 0] = 1
    C = np.zeros((n, P.shape[1]), dtype=np.int32)
    for i in range(n):
        C[i] = (np.dot(P.T, r[i]) + (np.floor(q / 2) * Z[i] * M[i])) % q
    return C


q = 127
n = 3
N = int(1.1 * n * np.log(q))
sigma = 1.0

P, s = gen(q, n, N, sigma)


def prep(s):
    return np.array([int(b) for char in s for b in f"{ord(char):08b}"], dtype=np.int32)


C = enc(P, prep(flag), q)
P = P.tolist()
C = C.tolist()
print(f"{P=}")
print(f"{C=}")

可以发现t很小直接爆破即可

s是私钥，解密算法就是$C\cdot s$

from Crypto.Util.number import long_to_bytes
import numpy as np

n = 3
q = 127

P=[[54, -22, -60, -8], [45, -26, -16, -62], [83, -8, -32, -30], [106, -46, -25, -21], [23, -22, -20, -25], [102, -40, -46, -42], [111, -16, -60, -50], [35, -9, -4, -41], [22, -61, -22, -7], [46, -10, -35, -20], [89, -54, -12, -3], [58, -43, -4, -10], [18, -56, -47, -52], [16, 0, -54, -31], [45, -28, -41, -40]]
C=[[18, 33, 115, 66], [52, 88, 94, 117], [111, 44, 32, 14], [0, 33, 10, 56], [54, 34, 107, 121], [50, 69, 33, 29], [70, 116, 96, 17], [67, 80, 59, 21], [58, 49, 73, 27], [5, 47, 29, 87], [9, 30, 70, 70], [97, 18, 24, 47], [105, 31, 92, 66], [7, 12, 45, 17], [26, 78, 63, 69], [48, 37, 23, 31], [105, 22, 44, 48], [36, 44, 13, 89], [0, 100, 102, 50], [24, 11, 28, 34], [89, 64, 71, 75], [64, 101, 75, 10], [29, 95, 96, 16], [34, 71, 40, 4], [52, 7, 64, 57], [117, 94, 101, 30], [20, 97, 15, 37], [108, 36, 66, 118], [104, 91, 85, 78], [73, 38, 74, 93], [115, 120, 53, 96], [50, 21, 42, 11], [29, 120, 105, 63], [51, 88, 85, 100], [9, 70, 76, 65], [111, 85, 112, 55], [18, 42, 44, 110], [71, 97, 14, 110], [101, 57, 119, 100], [38, 106, 117, 18], [7, 77, 22, 92], [103, 31, 81, 106], [58, 48, 89, 49], [116, 43, 51, 83], [15, 51, 6, 26], [18, 105, 118, 123], [0, 18, 108, 83], [106, 63, 10, 17], [11, 33, 53, 87], [66, 43, 39, 54], [15, 64, 121, 79], [28, 0, 2, 110], [38, 110, 37, 98], [31, 37, 122, 34], [40, 42, 32, 56], [90, 40, 105, 90], [65, 39, 96, 52], [56, 111, 111, 66], [77, 24, 75, 91], [60, 26, 73, 38], [102, 5, 40, 7], [41, 10, 66, 116], [119, 18, 41, 23], [28, 102, 71, 37], [78, 99, 70, 105], [100, 4, 80, 47], [52, 105, 43, 104], [54, 83, 74, 113], [12, 87, 84, 20], [24, 96, 39, 63], [17, 44, 72, 124], [77, 121, 28, 100], [32, 94, 88, 114], [77, 51, 116, 63], [69, 125, 69, 45], [11, 108, 105, 57], [105, 15, 123, 19], [43, 17, 33, 75], [99, 116, 97, 106], [2, 82, 9, 6], [4, 21, 47, 39], [35, 23, 62, 110], [9, 77, 114, 45], [37, 112, 120, 92], [10, 115, 85, 90], [72, 96, 25, 15], [57, 59, 68, 121], [66, 33, 30, 91], [57, 111, 75, 78], [11, 29, 22, 120], [102, 20, 31, 46], [23, 41, 99, 109], [37, 88, 36, 88], [73, 33, 27, 16], [96, 70, 4, 121], [44, 33, 59, 28], [77, 112, 80, 34], [6, 6, 84, 122], [118, 64, 49, 68], [69, 4, 22, 96], [45, 6, 59, 73], [71, 98, 105, 3], [106, 118, 23, 26], [106, 60, 27, 116], [8, 38, 112, 63], [38, 123, 125, 108], [56, 57, 102, 20], [70, 92, 105, 95], [98, 51, 94, 62], [59, 75, 86, 26], [104, 125, 54, 37], [33, 24, 2, 46], [48, 37, 8, 113], [30, 6, 37, 21], [81, 104, 34, 83], [115, 117, 59, 3], [71, 41, 60, 105], [7, 31, 44, 7], [19, 4, 7, 56], [86, 70, 120, 112], [13, 70, 32, 1], [59, 23, 47, 75], [78, 125, 113, 111], [66, 54, 61, 122], [75, 41, 91, 89], [66, 82, 72, 1], [3, 73, 59, 19], [105, 81, 20, 42], [46, 75, 105, 101], [21, 106, 67, 7], [21, 99, 52, 21], [35, 119, 86, 60], [34, 104, 109, 86], [81, 92, 16, 70], [72, 16, 54, 94], [89, 21, 12, 99], [20, 119, 94, 95], [60, 26, 97, 114], [63, 35, 122, 66], [57, 33, 81, 47], [48, 101, 99, 9], [11, 6, 85, 118], [120, 88, 108, 8], [22, 36, 88, 64], [90, 103, 50, 11], [65, 21, 27, 73], [84, 85, 125, 92], [79, 45, 80, 1], [14, 25, 7, 59], [107, 16, 86, 109], [75, 106, 38, 30], [81, 74, 9, 81], [38, 13, 95, 41], [53, 46, 99, 121], [26, 103, 50, 11], [31, 34, 64, 68], [114, 104, 43, 60], [54, 50, 120, 113], [24, 8, 42, 116], [11, 1, 87, 92], [15, 114, 93, 108], [6, 96, 44, 4], [28, 100, 46, 59], [31, 76, 26, 46], [85, 67, 74, 122], [27, 3, 5, 41], [81, 102, 51, 85], [104, 124, 84, 25], [114, 58, 73, 62], [45, 30, 1, 101], [3, 91, 49, 6], [104, 87, 113, 21], [118, 0, 46, 57], [50, 62, 107, 32], [64, 124, 100, 79], [27, 101, 76, 110], [120, 20, 7, 124], [81, 118, 84, 126], [85, 96, 117, 100], [98, 44, 10, 42], [81, 5, 4, 122], [94, 46, 64, 28], [83, 0, 105, 32], [115, 56, 117, 46], [39, 108, 119, 107], [90, 77, 95, 102], [70, 18, 32, 91], [88, 57, 64, 24], [61, 99, 32, 56], [122, 16, 92, 114], [113, 113, 23, 10], [39, 89, 94, 65], [1, 25, 122, 117], [63, 8, 122, 64], [22, 8, 1, 66], [51, 49, 85, 119], [91, 121, 126, 75], [125, 107, 126, 31], [101, 48, 18, 4], [7, 50, 67, 106], [40, 126, 36, 50], [60, 26, 73, 38], [106, 3, 17, 27], [100, 42, 85, 21], [22, 5, 8, 63], [3, 11, 50, 35], [57, 61, 68, 85], [43, 31, 120, 0], [9, 101, 35, 72], [68, 105, 105, 121], [82, 120, 82, 53], [117, 70, 9, 80], [0, 58, 70, 17], [39, 83, 96, 111], [47, 78, 105, 120], [85, 57, 122, 40], [64, 13, 2, 60], [81, 120, 0, 25], [99, 80, 14, 31], [1, 60, 86, 25], [35, 107, 115, 28], [52, 101, 39, 72], [6, 77, 58, 80], [27, 124, 29, 87], [30, 46, 106, 22], [99, 77, 51, 93], [18, 95, 20, 99], [47, 102, 126, 35], [29, 80, 112, 120], [80, 9, 36, 44], [74, 14, 44, 103], [31, 66, 99, 20], [108, 76, 102, 112], [84, 105, 110, 14], [113, 41, 104, 123], [22, 15, 25, 94], [62, 8, 89, 90], [3, 83, 1, 93], [74, 96, 49, 30], [37, 112, 15, 48], [62, 52, 98, 60], [120, 50, 55, 37], [46, 25, 94, 26], [102, 41, 71, 36], [23, 82, 104, 91], [67, 78, 83, 83], [95, 123, 58, 106], [111, 92, 70, 96], [16, 99, 118, 88], [101, 31, 17, 76], [105, 67, 76, 111], [67, 60, 78, 123], [33, 50, 63, 20], [110, 3, 126, 37], [65, 73, 43, 113], [109, 88, 71, 104], [34, 39, 122, 75], [108, 102, 15, 93], [23, 62, 97, 108], [49, 50, 121, 35], [125, 61, 92, 119], [106, 37, 41, 21], [116, 60, 64, 75], [81, 36, 28, 28], [110, 120, 27, 105], [115, 11, 44, 13], [57, 13, 115, 89], [8, 43, 45, 79], [23, 116, 74, 110], [97, 33, 44, 116], [103, 19, 4, 42], [118, 104, 2, 54], [116, 92, 97, 125], [107, 5, 64, 41], [69, 20, 42, 71], [78, 74, 65, 107], [83, 50, 38, 114], [29, 93, 19, 119], [91, 58, 29, 21], [54, 30, 45, 65], [52, 91, 123, 39], [123, 122, 17, 55], [56, 54, 4, 56], [89, 76, 50, 122], [126, 100, 78, 35], [3, 111, 124, 57], [25, 48, 56, 104], [63, 59, 33, 96], [22, 87, 46, 25], [8, 56, 26, 36], [103, 96, 101, 80], [53, 3, 64, 5], [11, 79, 24, 18], [74, 94, 89, 1], [12, 120, 3, 42], [33, 1, 106, 58], [123, 63, 37, 4], [121, 126, 112, 88], [112, 36, 108, 87], [109, 23, 104, 95], [36, 111, 99, 80], [88, 65, 120, 71], [88, 106, 76, 112], [52, 57, 120, 126], [64, 22, 42, 46], [51, 35, 5, 33], [59, 41, 83, 33], [76, 31, 36, 91], [12, 49, 102, 92], [29, 3, 70, 70], [63, 84, 126, 1], [24, 23, 43, 44], [107, 9, 28, 47], [43, 91, 22, 14], [90, 0, 83, 84], [108, 108, 12, 73], [92, 86, 100, 77], [50, 56, 80, 12], [111, 36, 27, 25], [21, 20, 72, 58], [9, 79, 112, 107], [110, 74, 19, 38], [8, 38, 79, 6], [90, 13, 122, 123], [45, 115, 47, 14], [8, 12, 0, 45], [58, 117, 25, 68], [120, 47, 21, 67], [55, 13, 22, 54], [43, 108, 91, 87], [70, 97, 15, 29], [62, 74, 58, 122], [73, 88, 90, 78], [31, 13, 116, 23], [65, 75, 79, 123], [22, 61, 15, 80], [70, 101, 34, 26], [98, 5, 9, 23], [45, 68, 18, 92], [114, 112, 14, 40], [2, 82, 9, 6], [68, 108, 30, 48], [5, 80, 14, 49], [51, 123, 112, 61], [38, 45, 18, 21], [68, 59, 29, 0], [70, 101, 86, 11], [0, 58, 57, 125], [78, 56, 55, 38], [81, 40, 19, 5], [70, 50, 66, 82], [52, 0, 14, 96], [96, 49, 106, 107], [83, 13, 17, 71], [20, 32, 26, 0], [3, 109, 35, 107], [48, 86, 19, 6], [93, 85, 73, 51], [60, 33, 5, 124], [38, 43, 64, 28], [35, 38, 94, 105], [82, 87, 99, 106], [18, 74, 97, 79], [101, 20, 61, 89], [116, 79, 19, 62], [4, 79, 115, 116], [52, 99, 77, 125], [31, 49, 80, 47], [92, 82, 35, 32], [23, 59, 101, 102], [119, 56, 3, 98], [26, 89, 39, 72], [84, 68, 106, 83], [55, 55, 32, 73], [14, 61, 54, 88], [54, 11, 39, 34], [10, 90, 116, 47], [26, 12, 68, 68], [90, 94, 18, 15], [115, 124, 3, 59], [32, 0, 112, 53], [123, 38, 112, 11], [3, 57, 109, 124], [11, 108, 105, 57], [73, 126, 112, 21], [110, 70, 13, 19], [103, 126, 50, 10], [48, 106, 15, 51], [79, 2, 73, 10], [22, 89, 40, 52], [71, 75, 111, 81], [107, 22, 102, 50], [15, 6, 0, 120], [69, 69, 63, 63], [93, 39, 108, 101], [97, 39, 6, 49], [49, 92, 57, 22], [70, 61, 103, 123], [116, 64, 37, 73], [116, 79, 94, 16], [7, 117, 18, 35], [22, 47, 107, 38], [118, 10, 63, 96], [11, 69, 103, 14], [84, 99, 84, 98], [30, 92, 51, 97], [120, 121, 9, 76], [73, 25, 116, 14], [21, 21, 52, 78], [35, 124, 20, 89], [49, 29, 15, 39], [17, 4, 87, 108], [22, 43, 100, 72], [105, 104, 8, 88], [114, 71, 1, 7], [62, 46, 55, 112], [92, 44, 118, 81], [3, 67, 22, 5], [30, 35, 119, 70], [22, 3, 95, 18], [9, 94, 97, 52], [87, 53, 61, 66], [2, 68, 73, 24], [41, 126, 51, 56], [116, 124, 76, 45], [37, 79, 99, 26], [69, 23, 17, 109], [14, 82, 93, 32], [52, 119, 107, 41], [50, 58, 73, 62], [34, 79, 27, 42], [22, 48, 14, 55]]

P = np.array(P)
C = np.array(C)
b = P[:, 0].reshape(-1, 1)
A = -P[:, 1:]
T = []
for i in range(q//2):
    for j in range(q//2):
        for k in range(q//2):
                T.append([i,j,k])
for t in T:
    t = np.array(t).reshape(-1, 1)
    e = (b - np.dot(A, t))%q
    e = e.T.tolist()[0]
    if all(i in [0,1,125,126] for i in e):
        s = np.concatenate([np.ones(1, dtype=np.int32), (t.T)[0]])
        break

M = (np.dot(C, s) % q).tolist()
m = ''
for i in M:
    if i>=np.floor(2*q / 3) or i<=np.floor(q / 3):
        m+='0'
    else:
        m+='1'
print(long_to_bytes(int(m,2)))

twister

题目

from dataclasses import dataclass
from cmath import exp
import secrets
import time
import os

FLAG = os.getenv("FLAG") or "test{flag_for_local_testing}"


@dataclass
class Wave:
    a: int
    b: int

    def eval(self, x):
        theta = x / self.a + self.b
        return ((exp(1j * theta) - exp(-1j * theta)) / 2j).real

ALL_WAVES = [Wave(a, b) for a in range(2, 32) for b in range(7)]

class MaximTwister:
    """
    Next-generation PRNG with really **complex** nature.
    More reliable than /dev/random cuz doesn't block ever.
    """

    def __init__(self, state=None):
        if state is None:
            state = (1337, [secrets.randbits(1) for _ in ALL_WAVES])

        self.point = state[0]
        self.waves = [wave for wave, mask in zip(ALL_WAVES, state[1]) if mask]

    def get_randbit(self) -> int:
        result = 0
        for wave in self.waves:
            # you would never decompose a sum of waves 😈
            result += round(wave.eval(self.point))
        # especially if you know only the remainder, right? give up
        result %= 2
        self.point += 1

        return result

    def get_randbits(self, k: int) -> int:
        return int("".join(str(self.get_randbit()) for _ in range(k)), 2)

    def get_token_bytes(self, k: int) -> bytes:
        return bytes([self.get_randbits(8) for _ in range(k)])


print("*** BUG DESTROYER ***")
print("You encounter: 😈 SEGMENTATION FAULT 😈")
opponent_hp = int(time.time()) * 123
days_passed = 0

random = MaximTwister()

while True:
    print(
        f"🕺 You ({10-days_passed} days till release) -- 😈 SEGMENTATION FAULT ({opponent_hp} lines)"
    )
    print(f"Day {days_passed + 1}. You can:")
    print("1. Make a fix")
    print("2. Call a senior")
    choice = input("> ").strip()
    if choice == "1":
        damage = random.get_randbits(32)
        opponent_hp -= damage
        if opponent_hp <= 0:
            print(
                f"You commited a fix deleting {damage} lines. Miraculously, it worked!"
            )
            break
        else:
            print(f"You commited a fix deleting {damage} lines. The bug remained 😿")
    elif choice == "2":
        print("You called a senior. It's super effective! The bug is destroyed.")
        break
    else:
        print(
            f"You spent {random.get_randbits(4)} hours doing whatever {choice} means."
        )

    print("A day has passed. You couldn't fix the bug.")
    days_passed += 1

    if days_passed == 10:
        print("It's release date! The bug is still there. You're fired.")
        exit()

print("The bug is gone! You got a raise.")
print(
    "In your new office you see a strange door. It is locked. You try to guess the password from the digital lock:"
)
password = input("> ")
if bytes.fromhex(password) == random.get_token_bytes(16):
    print("Somehow, you guessed the password! The room opens before you.")
    print("You see a mysterious text:", FLAG)
    print(
        "What could it mean?... You turn around and see your boss right behind you..."
    )
    print("BAD ENDING")
else:
    print("Incorrect. Well, let's get back to work...")
    print("GOOD ENDING")

我们可以输入9个1拿到9*32bits的输出

观察prng

calss Wave就是正弦波

故我们有

$$\sum^{210}_{i=0}t_i[\sin(\frac{1337}{a_i}+b_i)]\mod 2$$

$$\sum^{210}_{i=0}t_i[\sin(\frac{1338}{a_i}+b_i)]\mod 2$$

$$\vdots$$

$$\sum^{210}_{i=0}t_i[\sin(\frac{1625}{a_i}+b_i)]\mod 2$$

其中$t_i\in (0,1)$我们只有$t_i$未知，联合造格即可拿到state，带回去即可预测随机数

from dataclasses import dataclass
from cmath import exp
import secrets

@dataclass
class Wave:
    a: int
    b: int

    def eval(self, x):
        theta = x / self.a + self.b
        return ((exp(1j * theta) - exp(-1j * theta)) / 2j).real()


ALL_WAVES = [Wave(a, b) for a in range(2, 32) for b in range(7)]
n = len(ALL_WAVES)
t = [
    978415038,
    2717408903,
    2077497754,
    1558465923,
    2369257102,
    1700802112,
    2472228067,
    1213872079,
    1289580618,
]
T = "".join([bin(i)[2:].zfill(32) for i in t])
B = matrix(ZZ, n + 1, n + 1)
U = 7
for i in range(n):
    B[i, i] = 2
    B[-1, i] = 1
    B[i, -1] = round(ALL_WAVES[i].eval(1337)) * U
B[-1, -1] = int(T[0]) * U
for j in range(len(T[1:])):
    C = matrix(ZZ, n + 1, 1)
    for i in range(n):
        C[i, -1] = round(ALL_WAVES[i].eval(1338 + j)) * U
    C[-1, -1] = int(T[1:][j]) * U
    B = block_matrix([[B, C]])
for i in range(498 - n):
    C = matrix(ZZ, 1, 498)
    C[0, 210 + i] = 2 * U
    B = block_matrix([[B], [C]])

L = B.BKZ()
for l in L:
    if all(i == 0 for i in l[-288:]) and all(i == 1 or i == -1 for i in l[:-288]):
        print(l)
        break
state = [(-i + 1) // 2 for i in l[:-288]]

class MaximTwister:
    """
    Next-generation PRNG with really **complex** nature.
    More reliable than /dev/random cuz doesn't block ever.
    """

    def __init__(self, state=None):
        if state is None:
            state = (1337, [secrets.randbits(1) for _ in ALL_WAVES])

        self.point = state[0]
        self.waves = [wave for wave, mask in zip(ALL_WAVES, state[1]) if mask]

    def get_randbit(self) -> int:
        result = 0
        for wave in self.waves:
            # you would never decompose a sum of waves 😈
            result += round(wave.eval(self.point))
        # especially if you know only the remainder, right? give up
        result %= 2
        self.point += 1

        return result

    def get_randbits(self, k: int) -> int:
        return int("".join(str(self.get_randbit()) for _ in range(k)), 2)

    def get_token_bytes(self, k: int) -> bytes:
        return bytes([self.get_randbits(8) for _ in range(k)])
    
R = MaximTwister([1337, state])
[R.get_randbits(32) for _ in range(9)]
R.get_token_bytes(16)
# b"Rtk\xc9\xc9i\xabm\x87\x0c\x8c\x84\xd3\x17\x1e\xea"

Modnar

题目

chall.py

import random
import time
from secret import flag

def get_random_array(x): 
    y = list(range(1,x))
    random.Random().shuffle(y)
    return y

my_seed = bytes(get_random_array(42))
random.seed(my_seed)
my_random_val = random.getrandbits(9999)
print(f"my seed: {my_seed.hex()}")

start = time.time()
ur_seed = bytes.fromhex(input("Enter your seed! > "))
if ur_seed == my_seed:
    print("Hey that's my seed! No copying >:(")
    exit()
if time.time() - start > 5:
    print("Too slow I've already lost interest in seeds -_- ")
    exit()

random.seed(ur_seed)
ur_random_val = random.getrandbits(9999)

print(flag) if my_random_val == ur_random_val else print("in rand we trust.")

random.py (只展现改动的地方)

######## 128
def seed(self, a=None, version=1):
        """Initialize internal state from a seed.

        The only supported seed types are None, int, float,
        str, bytes, and bytearray.

        None or no argument seeds from current time or from an operating
        system specific randomness source if available.

        If *a* is an int, all bits are used.

        For version 2 (the default), all of the bits are used if *a* is a str,
        bytes, or bytearray.  For version 1 (provided for reproducing random
        sequences from older versions of Python), the algorithm for str and
        bytes generates a narrower range of seeds.

        """

        if version == 1 and isinstance(a, (str, bytes)):
            a = a.decode('latin-1') if isinstance(a, bytes) else a
            x = ord(a[0]) << 7 if a else 0
            for c in map(ord, a):
                x = ((1000003 * x) ^ c) & 0xFFFFFFFFFFFFFFFF
            x ^= len(a)
            a = -2 if x == -1 else x

        elif version == 2 and isinstance(a, (str, bytes, bytearray)):
            if isinstance(a, str):
                a = a.encode()
            a = int.from_bytes(a + _sha512(a).digest())

        elif not isinstance(a, (type(None), int, float, str, bytes, bytearray)):
            raise TypeError('The only supported seed types are: None,\n'
                            'int, float, str, bytes, and bytearray.')

        super().seed(a)
        self.gauss_next = None

可以看出seed的初始化从version2改成了version1

我们可以把异或看成加上一个小值，展开式子直接造格即可

(格写的有点随便，不一定每次拿到的数据都可以打出来)

from Crypto.Util.number import *

def f(a):
    a = a.decode("latin-1") if isinstance(a, bytes) else a
    x = ord(a[0]) << 7 if a else 0
    for c in map(ord, a):
        x = ((1000003 * x) ^^ c) & 0xFFFFFFFFFFFFFFFF
    x ^^= len(a)
    a = -2 if x == -1 else x
    return a

seed = "190d1d1301042203292321121e271c0a0b25200506171110182807021609151f24080f1b260e0c141a"

T = 2^8
t = f(bytes.fromhex(seed))
tt = t
n = 41
t ^^= n
M = matrix(ZZ, n + 2)
for i in range(n + 2):
    M[i, i] = 1
    if i < n:
        M[i, -1] = 1000003 ^ (n-i-1) if i != 0 else 1000003 ^ n * 2 ^ 7 + 1000003 ^ (n-1)
M[-2, -2] = 2 ^ 8
M[-2, -1] = -t
M[-1, -1] = 2 ^ 64
M[:, -1] *= T
for L in M.LLL():
    seed = b''
    c = t
    if L[-2] == -256: L=[-i for i in L]
    if L[-1] == 0 and L[-2] == 256:
        tmp = L[:-2]
        for i in range(len(tmp)):
            tmpc = (c - tmp[n-i-1]) % 2^64
            s = tmpc ^^ c
            seed += long_to_bytes(s)
            c = (c ^^ s) * inverse(1000003,2^64) % 2^64
        seed = seed[::-1]
        if f(seed) == tt:
            print(seed)

*Subathon

chall.py

from notaes import notAES
from os import urandom
from time import time


# ugh standard flag shenanigans yada yada
key = urandom(16)
cipher = notAES(key)

from secret import flag
flag_enc = cipher.encrypt(flag.encode())
print(f'{flag_enc = }')


# time for the subathon!
st = time()
TIME_LEFT = 30
while time() - st < TIME_LEFT:
    print("=================")
    print("1. Subscrib")
    print("2. Play rand gaem")
    print("3. Quit")
    print("=================")
    choice = str(input())
    if choice == "1":
        print("Thank you for the sub!!")
        TIME_LEFT += 30
    elif choice == "2":
        print("Guess the number!")
        ur_guess = int(input(">> "))
        my_number = int.from_bytes(cipher.encrypt(urandom(16)), "big")
        if ur_guess != my_number:
            print(f"You lose, the number was {my_number}")
        else:
            print("Omg you won! Here's the flag")
            print(flag)
    else:
        break
print("The subathon's over! Hope you had fun!!")

notaes.py

#!/usr/bin/env python3
# https://github.com/boppreh/aes/blob/master/aes.py, definitely unaltered


s_box = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0x93, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)



def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = s_box[s[i][j]]


def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]


def inv_shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3]

def add_round_key(s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]


# learned from https://web.archive.org/web/20100626212235/http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


def mix_single_column(a):
    # see Sec 4.1.2 in The Design of Rijndael
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)


def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])


def inv_mix_columns(s):
    # see Sec 4.1.3 in The Design of Rijndael
    for i in range(4):
        u = xtime(xtime(s[i][0] ^ s[i][2]))
        v = xtime(xtime(s[i][1] ^ s[i][3]))
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v

    mix_columns(s)


r_con = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)

def bytes2matrix(text):
    """ Converts a 16-byte array into a 4x4 matrix.  """
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    """ Converts a 4x4 matrix into a 16-byte array.  """
    return bytes(sum(matrix, []))

def xor_bytes(a, b):
    """ Returns a new byte array with the elements xor'ed. """
    return bytes(i^j for i, j in zip(a, b))

def pad(plaintext):
    """
    Pads the given plaintext with PKCS#7 padding to a multiple of 16 bytes.
    Note that if the plaintext size is a multiple of 16,
    a whole block will be added.
    """
    padding_len = 16 - (len(plaintext) % 16)
    padding = bytes([padding_len] * padding_len)
    return plaintext + padding


def split_blocks(message, block_size=16, require_padding=True):
        assert len(message) % block_size == 0 or not require_padding
        return [message[i:i+16] for i in range(0, len(message), block_size)]


class notAES:
    """
    Class for AES-128 encryption

    This is a raw implementation of AES, without key stretching or IV
    management. Unless you need that, please use `encrypt` and `decrypt`.
    """
    rounds_by_key_size = {16: 10, 24: 12, 32: 14}
    def __init__(self, master_key):
        """
        Initializes the object with a given key.
        """
        assert len(master_key) in notAES.rounds_by_key_size
        self.n_rounds = notAES.rounds_by_key_size[len(master_key)]
        self._key_matrices = self._expand_key(master_key)

    def _expand_key(self, master_key):
        """
        Expands and returns a list of key matrices for the given master_key.
        """
        # Initialize round keys with raw key material.
        key_columns = bytes2matrix(master_key)
        iteration_size = len(master_key) // 4

        i = 1
        while len(key_columns) < (self.n_rounds + 1) * 4:
            # Copy previous word.
            word = list(key_columns[-1])

            # Perform schedule_core once every "row".
            if len(key_columns) % iteration_size == 0:
                # Circular shift.
                word.append(word.pop(0))
                # Map to S-BOX.
                word = [s_box[b] for b in word]
                # XOR with first byte of R-CON, since the others bytes of R-CON are 0.
                word[0] ^= r_con[i]
                i += 1
            elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
                # Run word through S-box in the fourth iteration when using a
                # 256-bit key.
                word = [s_box[b] for b in word]

            # XOR with equivalent word from previous iteration.
            word = xor_bytes(word, key_columns[-iteration_size])
            key_columns.append(word)

        # Group key words in 4x4 byte matrices.
        return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]

    def encrypt_block(self, plaintext):
        """
        Encrypts a single block of 16 byte long plaintext.
        """
        assert len(plaintext) == 16

        plain_state = bytes2matrix(plaintext)

        add_round_key(plain_state, self._key_matrices[0])

        for i in range(1, self.n_rounds):
            sub_bytes(plain_state)
            shift_rows(plain_state)
            mix_columns(plain_state)
            add_round_key(plain_state, self._key_matrices[i])

        sub_bytes(plain_state)
        shift_rows(plain_state)
        add_round_key(plain_state, self._key_matrices[-1])

        return matrix2bytes(plain_state)
    
    def encrypt(self, plaintext):
        plaintext = pad(plaintext)
        ciphertext = b""
        for i in range(0, len(plaintext), 16):
            ciphertext += self.encrypt_block(plaintext[i:i+16])
        return ciphertext

todo

*Rolypoly

from sage.all import GF, PolynomialRing, ZZ, save
from hashlib import sha256
from Crypto.Cipher import AES

n = 1201
q = 467424413

K = GF(q)
PR = PolynomialRing(K, names=('t',)); (t,) = PR._first_ngens(1)
R = PR.quotient(PR.ideal([t**n-1 ]))
PR2 = PolynomialRing(R,2 , names=('x', 'y',)); (x, y,) = PR2._first_ngens(2)

def SamplePoly():
    p = R.zero()
    for i in range(0,n):
        p += ZZ.random_element(0,q)*t**i
    return p

def SampleSmallPoly():
    sp = R.zero()
    for i in range(0,n):
        sp += ZZ.random_element(0,4)*t**i
    return sp

def r2int(r):
    out = 1
    for ri in r.coefficients():
        out *= int(sum([j for j in ri.lift().coefficients()]))
    return out

def keyGen():
    ux = SampleSmallPoly()
    uy = SampleSmallPoly()
    X10 = SamplePoly()
    X01 = SamplePoly()
    X00 = -X10*ux - X01*uy
    return (ux,uy,X00,X10,X01)

def Encrypt(m, key):
    _,_,X00,X10,X01 = key
    Ctx = X00 + X10*x + X01*y
    r = SamplePoly() + SamplePoly()*x + SamplePoly()*y
    Ctx = Ctx*r
    for i in range(0,3):
        for j in range(0,3-i):
            Ctx += 4*SampleSmallPoly()*x**i*y**j
    return (Ctx + m, r2int(r))

             
flag = b"wwf{??????????????????????????????????????}\x05\x05\x05\x05\x05"
gkey = keyGen()
pubkey = gkey[2:]
r0 = SampleSmallPoly()
Ctx, r = Encrypt(r0, gkey)
rk = sha256(str(r).encode()).digest()
flag_enc = AES.new(key=rk, mode=AES.MODE_ECB).encrypt(flag)
save([flag_enc, pubkey, Ctx], "output.sobj")

todo

*Amineo

from secrets import randbits
from hashlib import sha256
import os

flag = os.getenv("flag", "wwf{<REDACTED>}").encode()
assert len(flag) == 32

p = 0xffffffffffffffffffffffffffffff53
Nr = 4

bSEED = b"AMINEO"
A = int.from_bytes(sha256(b"A" + bSEED).digest(), "big") % p
B = int.from_bytes(sha256(b"B" + bSEED).digest(), "big") % p

Ci = [int.from_bytes(sha256(b"C" + bSEED + str(r).encode()).digest(), "big") % p for r in range(Nr)]
Di = [int.from_bytes(sha256(b"D" + bSEED + str(r).encode()).digest(), "big") % p for r in range(Nr)]
Ei = [int.from_bytes(sha256(b"E" + bSEED + str(r).encode()).digest(), "big") % p for r in range(Nr)]
Fi = [int.from_bytes(sha256(b"F" + bSEED + str(r).encode()).digest(), "big") % p for r in range(Nr)]
Gi = [int.from_bytes(sha256(b"G" + bSEED + str(r).encode()).digest(), "big") % p for r in range(Nr)]
Hi = [int.from_bytes(sha256(b"H" + bSEED + str(r).encode()).digest(), "big") % p for r in range(Nr)]

def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

class Amineo:
    def __init__(self, nr):
        self.nr = nr
        self.k = pow(3, -1, p - 1)
    
    def H(self, S):
        x, y = S
        x += A*y**2
        y += pow(x, self.k, p)
        x += B*y

        return x % p, y % p

    def M(self, S, r):
        x, y = S
        return Ci[r]*x + Di[r]*y + Ei[r] % p, Fi[r]*x + Gi[r]*y + Hi[r] % p

    def encrypt(self, S):
        Se = S.copy()
        for r in range(self.nr):
            Se = self.H(self.M(Se, r))

        return list(Se)

if __name__ == "__main__":
    print("I dont trust you but I guess you don't either...")

    try:
        user_B = bytes.fromhex(input("Give me 2 RANDOM blocks of 16 bytes (hex) >"))
        assert len(user_B) == 32
    except:
        print("I KNEW YOUD TRY TO CHEAT IF I GAVE YOU ANY CONTROL !!!")
        print("GET OUT OF HERE !!!")
        exit()

    S = [int.from_bytes(user_B[i:i+16], "big") % p for i in range(0, len(user_B), 16)]

    print("I dont trust you I'll add my part ...")
    tamper_idx = randbits(1)
    S[tamper_idx] *= randbits(128) % p

    enc = Amineo(Nr)
    OTP = enc.encrypt(S)

    print("Just to be sure I mean ... More random never hurts right ? :) ")
    OTP[0] *= randbits(128)
    OTP[1] *= randbits(128)
    OTP[0] %= p
    OTP[1] %= p

    OPTb = b"".join(int.to_bytes(OTP[i], 16, "big") for i in range(2))
    print("Here you go... :", xor(flag, OPTb).hex())

todo