Inequality_Solving_with_CVP - crypto-writeup-public

https://github.com/rkm0959/Inequality_Solving_with_CVP/

変数を一つ減らすテク

$f(x, y, z, ...) = 0$ となるときに $x$ の次数が1でその具体的な値に興味がなければ、全体を $x$ の係数 $k$ で割って、 $f'(y, z) / k = -x < X$ という不等式にすれば一変数減る
これを大きさのわかっている未知変数を直接求めないテクと名付けた

pbctf2020 | LeaKの解析

NUM (=10)個のインスタンスを集めてCVPしていそう
$(2^{216}a + 2^{40}* b + c)s = h + rd + nt \cdots (\triangle)$ という等式が成り立つ
- （ $k = 2^{216}a + 2^{40}*b + c, b = leak$ と表している
このとき $0 < a, b < 2^{40}, 0 <= d < n$ という不等式がそれぞれ成り立つ
したがって、インスタンスごとの $a, c, t$ の NUM * 3 個と、共通の $d$ 、あわせて31個の未知変数が存在する
また、上記のように、 $a, b, d$ についてそれぞれ不等式がなりたち、またすべての変数を用いて等式がつくれるので、こちらも NUM * 3 + 1 個の

inequality

が成り立つ
行列を作る（縦 $3N + 1$ 、横 $3N + 1$
各行は変数に対応していて、
各列は不等式に対応している

$\begin{pmatrix} r_0 & r_1 & \dots & r_{N} & & & & & & & 1 \ -2^{216}s_0 & & & & 1 \ -s_0 & & & & & 1 \ n & & & & & & 0 \ & -2^{216}s_1 & & & & & 1 \ & -s_1 & & & & & & 1 \ & n & & & & & & & \ddots \ & & \ddots \end{pmatrix}$

おきもち

行列の作り方の考え方

まず、未知変数を横にびろーっと並べて $(d, a_0, c_0, a_1, c_1, \dots, a_N, c_N)$
続いて、（不）等式のうち未知変数を含む辺ができるように行列を作る。行列のある列を切り出した時、縦の長さは未知変数の数に等しくなっている
lowerbound, upperboundを作る
- それぞれ 3N + 1 の大きさの配列
- $lb_i = 2^{40} b_i * s_i - h_i$ where ( $i < N$ )
- $ub_i = 2^{40} b_i * s_i - h_i$ where $i < N$
- $ub_i = 2^{40}$ where $N \le i < 3N+1$
- $ub_{3N} = n$
lowerbound, upperboundはそれぞれの要素が行列の各列の不等式の満たすべきlowerbound, upperboundになっている
例えば1列目は $(\triangle)$ を変形して $dr_0 - 2^{216}a_0s_0 - c_0s_0 + nt_0 = 2^{40}b_0s_0 - h_0$ とした後、左辺を分解して $(d, a_0, c_0, t_0, \dots) \begin{pmatrix}r_0\ -2^{216}s_0 \ -2^{40}s_0 \ n \ 0 \ \vdots \end{pmatrix}$ となる。今回は等式が成り立つので左辺が満たすべき上限下限は揃っていて $2^{40}b_0s_0 - h_0$ になる。 $N$ 列目まで同様
同様に $N+1$ 列目は $(d, a_0, \dots) \begin{pmatrix} 0 \ 1 \ 0 \ \vdots \end{pmatrix} = a_0$ のboundなので、下限は $0$ で上限は $2^{40}$ 程度になる
同様に $3N + 1$ 列目は $d$ のboundなので、下限は $0$ 、上限は $n$ になる

CVPパート

こうして作った行列 $M$ と $lb, ub$ を使った CVP で問題を解く
お気持ちとしては、 $target = \frac{lb + ub}{2}$ として、これにできるだけ近い格子状の点を見つければ良い
$target$ は確かに $lb \le target \le ub$ になるので、これに近い格子上の点は求めたい条件を満たす点だろうと思われる
そして、基底で張られる格子上の点で、こういうboundを満たす点は大体答えだろう、ということになる
ただし、 $target$ の各要素のサイズの乖離が激しい（＝行列の列ごとのサイズの乖離が大きい）と LLL はうまくいかないがちなので（というのも、サイズの大きい要素を小さくするほうが、最小ベクトルを得やすいので、 $target$ の値が小さい列の条件が無視されてしまう）スケーリングをして、サイズを整える
もとの条件では、 $diff_i = ub_i - lb_i$ として、係数 $K_i = \frac{\max(diff)}{diff_i}$ とする感じで、こうすると $target$ の大体の大きさがそろう
- ただし、 $diff_i = 0$ となる場合（inequalityではなくequalityの場合）は、適当な大きい係数をかけている
仮説： $K_i = \frac{\max(target)}{target_i}$ としてもよいのでは？　その場合は条件分岐がなくなってうれしいのでは
ただし、この場合は $diff$ を用いた場合に比べて $K_i$ が大きくなりやすい傾向にある

SECCON 2020 | sharsableを解いてみる

$N = pq$ で、 $d_1, d_2 \simeq N^{0.16}$ で $e_1d_1 + e_2d_2 \equiv 1 \mod \phi(N)$

$c_1 = m^{e_1} \mod N$

$c_2 = m^{e_2} \mod N$

未知変数 $\phi(N), k, d_1, d_2$

(in)equality: $e_1d_1 + e_2d_2 = 1 + k\phi(N), 0 \le d_1, d_2 \le N^{0.16}, 0 \le \phi(N) < N, 0 \le k < N^{0.16}$

theldmoon0602 solution

未知変数 $(k, d_1, d_2)$ として、次の不等式を建てた

$-e_1d_1 - e_2d_2 + k(N+1) = ks - 1$ （ただし $\phi(N) = pq - (p+q) + 1 = pq - s + 1$ としている
$0 \le k, d_1, d_2 \le N^{0.16}$

import json

def babai_closest_vector(M, G, target):
    small = target
    for i in reversed(range(M.nrows())):
        c = ((small * G[i]) / (G[i] * G[i])).round()
        small -=  M[i] * c
    return target - small

with open("params.json") as f:
    data = json.load(f)

n = data["n"]
e1, c1 = data["A"]
e2, c2 = data["B"]

K = floor(n^0.16)

# v = (k, d1, d2)
M = matrix(ZZ, [
    [n+1, -e1, -e2], # -e1d1 - e2d2 + k(N+1) = ks - 1 
    [  1,   0,   0], # 0 <= k <= N^0.16
    [  0,   1,   0], # 0 < d1 <= N^0.16
    [  0,   0,   1], # 0 < d2 <= N^0.16 
])

ub = [floor(3 * n^0.5 * n^0.16), K, K, K]
lb = [0, 0, 0, 0]
target = [(u + l) // 2 for u, l in zip(ub, lb)]

size = max(target)
weights = []

for i in range(len(ub)):
    w = size // target[i]
    M[i] *= w
    target[i] *= w
    weights.append(w)

B = M.transpose().LLL()
G = B.gram_schmidt()[0]
closest = babai_closest_vector(B, G, vector(target))

for i in range(len(weights)):
    print(closest[i] // weights[i])

d1 = closest[-2] // weights[-2]
d2 = closest[-1] // weights[-1]

m = pow(c1, d1, n) * pow(c2, d2, n) % n
print(bytes.fromhex(hex(m)[2:]))

yoshiking solution

from sage.modules.free_module_integer import IntegerLattice

# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff


def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()

    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))

    if weight == None:
        weight = num_ineq * max_element

    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return

    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return

    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return

    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []

    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight

    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)

    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
    ## recover your result
    return result, applied_weights

from json import loads

data = loads(open("./output").read())
n = data["n"]
e1 = data["A"][0]
c1 = data["A"][1]
e2 = data["B"][0]
c2 = data["B"][1]

# (-k + x, d1, d2)
B = matrix(ZZ, [
    [n, 0, 0],
    [e1, 1, 0],
    [e2, 0, 1],
])

lb = [-2^680, 0, 0]
ub = [0, 2^164, 2^164]
#lb = [-int(n ** 0.66), 0, 0]
#ub = [0, int(n ** 0.16), int(n ** 0.16)]

res, wights = solve(B, lb, ub)

d1 = res[1] // wights[1]
d2 = res[2] // wights[2]

k_phi = e1 * d1 + e2 * d2 - 1

from Crypto.Util.number import long_to_bytes
if gcd(e1, k_phi) == 1:
    d = inverse_mod(e1, k_phi)
    print(long_to_bytes(pow(c1, d, n)))
if gcd(e2, k_phi) == 1:
    d = inverse_mod(e2, k_phi)
    print(long_to_bytes(pow(c2, d, n)))

HITCON CTF 2019 Quals | not so hard RSAを解いてみる

10個のRSAのインスタンスが与えられていて、 $d$ が共通で、 $d$ は465bitで $N^{0.5}$ くらい

$N_i = p_iq_i, e_i \equiv d^{-1} \mod \phi(N_i)$

theoldmoon0602 solution

$\phi(N_i) = p_iq_i - s_i + 1$ と置き直して、等式

$e_id = 1 + k_i (p_iq_i - s_i + 1)$ とする

未知変数: $(d, k_0, k_1, \dots, k_9)$ として

(in)equality:

* $-de_i + k_i(N + 1) = k_is_i - 1 \le 2^{465} * 3 * N^{0.5}$

* $0 \le d, k_0, \dots, k_9 \le 2^{465}$

import ast

# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = mat.LLL()
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff

with open("data") as f:
    data = ast.literal_eval(f.read().strip())

NS = [d[0] for d in data]
es = [d[1] for d in data]
cs = [int(d[2], 16) for d in data]

dmin = 2^464
dmax = 2^465

n = len(es)
# (d, k_0, k_1, ..., k_9)
M = matrix(ZZ, 2*n+1, n+1)
lb = [0 for _ in range(2*n + 1)]
ub = [0 for _ in range(2*n + 1)]

M[n, 0] = 1               # d  < 2^{465}
lb[n] = dmin
ub[n] = dmax
for i in range(n):
    N, e = NS[i], es[i]
    smin = int(2*(N)^(0.5))
    smax = int(3*(N/2)^(0.5))
    kmin = (e * dmin - 1) / (N - smin + 1)
    kmax = (e * dmax - 1) / (N - smax + 1)

    # kmin * smin < -ed + k(N+1) = k*s - 1 < kmax * smax
    M[i, 0] = -e
    M[i, i+1] = N + 1

    lb[i] = floor(kmin * smin - 1)
    ub[i] = ceil(kmax * smax - 1)

    # kmin < k < kmax
    M[n+i+1, i+1] = 1
    lb[n+i+1] = floor(kmin)
    ub[n+i+1] = ceil(kmax)

# (..., d, k_0, k_1, ..., k_9)
target = [(u + l) // 2 for u, l in zip(ub, lb)]
size = max(target)
weights = []

for i in range(len(ub)):
    w = size // target[i]
    M[i] *= w
    target[i] *= w
    weights.append(w)

print("[+] CVP....")
closest = Babai_CVP(M.transpose(), vector(target))
d = closest[n] // weights[n]

m = pow(cs[0], d, NS[0])
print(bytes.fromhex(hex(m)[2:]))

AeroCTF 2021 | horcrux

↑に書いた