ASIS CTF Finals 2022 | rhyton

#ASIS_CTF_Finals_2022

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def gen_rhyton(nbit, delta, L):

    p, q = [getPrime(nbit) for _ in '01']
    n = p * q
    D = int(n ** (1 - delta))   
    phi = (p - 1) * (q - 1)

    V = [getRandomRange(1, n - 1) for _ in range(L)]
    U = [phi * v // n for v in V]

    W, i = [], 0
    while True:
        w = getRandomRange(phi * V[i] - U[i] * n - D, phi * V[i] - U[i] * n + D)
        if abs(phi * V[i] - U[i] * n - w) < D and w < n:
            W.append(w)
            i += 1
        if i == L:
            break
    return (p, q, U, V, W)

def encrypt(msg, p, q):
    m, n = bytes_to_long(msg), p * q
    assert m < p * q
    e = 65537
    return pow(m, e, n)

nbit, delta, L = 512, 0.14, 110
p, q, U, V, W = gen_rhyton(nbit, delta, L)

enc = encrypt(flag, p, q)

print(f'n = {p * q}')
print(f'V = {V}')
print(f'W = {W}')
print(f'enc = {enc}')

RSAだが、 の が110個ほども与えられている。

これはHidden Number Problemなのだが気がついていなくてInequality_Solving_with_CVPで解いた

import ast

with open("output.txt") as f:
    n = ast.literal_eval(f.readline().strip().split(" = ")[1])
    V = ast.literal_eval(f.readline().strip().split(" = ")[1])
    W = ast.literal_eval(f.readline().strip().split(" = ")[1])
    c = ast.literal_eval(f.readline().strip().split(" = ")[1])

delta = 0.14
D = int(n ** (1 - delta))
# k = 2 * len(V) // 8
k = 35
print("k =", k)
V = V[:k]
W = W[:k]


load("./rkm.sage")
# v = (phi, e_1, ..., e_k, t_1, ..., t_k)
M = block_matrix([
    [matrix(ZZ, 1, k, V), 0, 1],
    [matrix.identity(ZZ, k), matrix.identity(ZZ, k), 0],
    [n  * matrix.identity(ZZ, k), 0, 0],
])
lb = W + [-D for _ in range(k)] + [0]
ub = W + [D for _ in range(k)] + [n]

result, weights, fin = solve(M, lb, ub)
phi = int(fin[0])

d = pow(65537, -1, phi)
m = pow(c, d, n)
print(m)