以前参加した Harekaze mini CTF 2020 の Crypto 問 "Wilhelmina says" の復習です。 LLL (Lenstra-Lenstra-Lovász) を 1 ミリも知らなかったため 1 から勉強しました。そのメモです。

書籍としては 格子暗号解読のための数学的基礎 を読みました。数学的な話を丁寧にやってくれていて読みやすかったです。 この記事では上記問題を解くために必要な背景知識等をまとめるのにとどめ、数学的な話は一切排除します。また具体的な実装にも踏み込みません。あくまで Crypto 問に適用するときにどういったことに注意すればいいかについて主眼を当てます。

LLL アルゴリズム関連の用語

格子

格子とは、ある一次独立なベクトル $\bm{b}_i \in \R^m (1 \le i \le n)$ の整数係数の線形結合全体の集合です。式で書くと、

となります。格子の元を格子ベクトル、格子を成す基底を格子基底と呼びます。また

を格子基底行列と呼びます。

ある格子を成す基底は2次元以上で無数に存在します。これはあるユニモジュラ行列 $T$ を考えた時、

となる $c$ が格子基底となることから示せます (2次元以上でユニモジュラ行列は無限に存在する)。

LLL アルゴリズムは格子とそれを成すある格子基底行列が与えられたときに、その格子を成す格子基底のうちノルムが最小な基底を近似的に計算するアルゴリズムとなります。

逐次最小

格子 $L$ の中で原点を除いて原点から最も近い格子ベクトル TOP $i$ のノルム距離を考えます。式で書くと

これを逐次最小 $\lambda_i$ と呼びます。

最短ベクトル問題 (Shortest Vector Problem, SVP)

最短ベクトル問題 (Shortest Vector Problem, SVP) は $\| \bm{v} \| = \lambda_1(L)$ を満たす格子 $L$ 上の非零格子ベクトル $\bm{v}$ を求める問題です。 この SVP が暗号理論でよく用いられるのですが、SVP は NP-hard であることが知られています。 LLL アルゴリズムはこの逐次最小な格子基底を近似的に求める方法と言い換えられ、 $\| \bm{v} \| = \gamma(n) \lambda_1(L) (\gamma \ge 1)$ となる $\bm{v}$ を効率的に探すことのできるアルゴリズムです。

基底簡約

例えば2次元系で格子基底が $\bm{b}_1 = (1, 0), \bm{b}_2 = (0, 1)$ となる格子を考えてみます。この格子を $L$ とします。 前述通り $L$ を成す格子基底は無数に存在し、例えば $\bm{c}_1 = (1, 2), \bm{c}_2 = (1, 3)$ も格子 $L$ を成します。 実はこのような格子を成す格子基底のうち、この $\bm{b}_1, \bm{b}_2$ はノルムが最小なベクトルとなっています。つまり逐次最小基底です。 $\bm{c}_1, \bm{c}_2$ のような格子基底を与えられたときに逐次最小な基底を求めることを基底簡約と呼びます。

LLL アルゴリズムは本来基底簡約のアルゴリズムなのですが、その過程で SVP を解くことにつながります。

LLL アルゴリズムの概要

LLL アルゴリズムは、雑に説明すると Gram-Schmidt の直交化で計算された基底に対し、ベクトルのノルムが小さくなるように基底を更新していくことで基底簡約を行うアルゴリズムです。 LLL アルゴリズムで簡約された格子基底を $\bm{b}_i$ とすると、

となることが数学的に保証されています。ここで $\alpha$ は $\frac{1}{4} < \delta < 1$ を用いて $\alpha = \frac{4}{4\delta - 1} > \frac{4}{3}$ と表される定数です。 特に、

が成立します。$n$ が大きくなると LLL アルゴリズムで求まる格子基底と最短ベクトルの乖離も大きくなることに注意が必要です。

Crypto 問題への適用

それではこの LLL アルゴリズムが Crypto 問題でどのように使われるかを見ていきましょう。

問題

問題の repository は https://github.com/TeamHarekaze/harekaze-mini-ctf-2020-challenges-public/tree/main/crypto/wilhelmina-says になります。

task.py
from Crypto.Util.number import getStrongPrime
import random

p = getStrongPrime(512)

with open("flag", "rb") as f:
  flag = int.from_bytes(f.read().strip(), "big")
  assert flag < p

t = flag.bit_length()
n = 5
k = 350

xs = [random.randint(2, p-1) for _ in range(n)]
ys = [x * flag % p for x in xs]
zs = [(y >> k) << k for y in ys]

print(f"{t=}")
print(f"{p=}")
print(f"{xs=}")
print(f"{zs=}")

ある 512 bit の素数 $p$ を用意し、 $x_i$ は randint(2, p-1) で生成され、$y_i \equiv x_i \times flag \mod p$ を計算した後、 $y_i$ の下 $k=350$ bit を落としたものを $z_i$ としています。 $t$ (フラグの bit 数), $p$, $x_i (0\le i < 5)$, $z_i (0\le i < 5)$ が与えられ、フラグとなる数値を求める問題です。

これが先述した LLL アルゴリズムとどう関係してくるのでしょうか。

解法

まず問題の式を整理していきます。フラグの数値を $f$ とします。 350 bit 以下の数 $t_i (\ll z_i)$ を使って、 $y_i = z_i + t_i$ とかけます。 また $y_i$ は $x_if$ を $p$ で割った余りなので、 $y_i = x_i f - pq_i$ とも表せます。2式組み合わせると、

となります。

この式を線形計算っぽく書いてみることにします。

ここで変数 $c_0, c_1$ を追加して、右辺の行列を正方行列にしています。$c_0, c_1$ を除けば右辺の行列はすべて given な値となっています (そうなるようにうまく書いてます)。 右辺の行列を格子基底行列とみなすと、この式は格子基底を $(-q_0, -q_1, -q_2, -q_3, -q_4, f, -1)$ の重みで足し合わせると左辺の格子ベクトルとなる、といった見方ができます。 今 $t_i$ は右辺の各種値と比較すると十分小さい値となっているため、 $c_0, c_1$ を適切な大きさの整数とすると、この左辺を求めることは SVP を解くことに対応します。つまりここで LLL アルゴリズムを使うことができるわけです。

$c_0, c_1$ はどのような値にすればいいのかを考えます。最短ベクトルの不等式を再掲すると、$\alpha=2$ として

が成立する必要があるため、 $c_0, c_1$ は最低でもこれを満たす必要があります。 今 $\left| \det L \right| = c_0 c_1 p^5$ なので、右辺は

と計算されます。 左辺のノルムは、$(t_0, \cdots, t_4, fc_0 -c_1)$ で最も大きい値で近似できます。そのため、 $c_0 = 1, c_1 = 2^k$ としてあげれば左辺は $2^k$ 程度になります。 指数部を比較すると、 $k = 350 \le 417.2$ となり不等式が成立していることが計算できます。

このような $c_0, c_1$ を使って実際に LLL アルゴリズムを適用してみます。 SageMath を使用します。

t = 311
p = 10701453001723144480344017475825280248565900288828152690457881444597242894870175164568287850873496224666625464545640813032441546675898034617104256657175267
xs = [
    7891715755203660117196369138472423229419020799191062958462005957463124286065649164907374481781616021913252775381280072995656653443562728864428126093569737,
    9961822260223825094912294780924343607768701240693646876708240325173173602886703232031542013590849453155723572635788526544113459131922826531325041302264965,
    7554718666604482801859172289797064180343475598227680083039693492470379257725537783866346225587960481867556270277348918476304196755680361942599070096169454,
    5460028735981422173260270143720425600672799255277275131842637821512408249661961734712595647644410959201308881934659222154413079105304697473190038457627041,
    8621985577188280037674685081403657940857632446535799029971852830016634247561494048833624108644207879293891655636627384416153576622892618587617669199231771,
]
zs = [
    2445678981428533875266395719064486897322607935804981139297064047499983860197487043744531294747013763946234499465983314356438694756078915278742591478169600,
    6687262023290381303903301700938596216218657180198116459210103464914665663217490218525920847803014050091904359944827298080739698457116239163607201903280128,
    9144515139738671257281335253441395780954695458291758900110092599410878434836587336752247733779617485272269820837813132894795262162555273673307500761317376,
    7005359236736263649027110410188576532095684249796929034336135801107965605961711614006159825405033239188458945408990893269975105260656611838449490684018688,
    4638291797440604671051855904609667375394026160401800326727058461541969151082727684535417653507524951373254537356784859777006179731400955193335900924805120,
]

k = 350
n = 5

# 格子基底行列 L の生成
tmp_matrix = [[0 for _ in range(n+2)] for _ in range(n+2)]
for i in range(n):
    tmp_matrix[i][i] = p
for i in range(n):
    tmp_matrix[n][i] = xs[i]
for i in range(n):
    tmp_matrix[n+1][i] = zs[i]
tmp_matrix[n][n] = 1
tmp_matrix[n+1][n+1] = 2**k
L = Matrix(ZZ, tmp_matrix)

B = L.LLL()  # LLL アルゴリズムによる基底簡約
f = B[0][n]  # fc_0 = f
tmp = hex(abs(f))[2:]
if len(tmp) % 2 == 1:
    tmp = tmp.zfill(len(tmp)+1)
flag = bytes.fromhex(tmp)
print(flag)

HarekazeCTF{H0chmu7_k0mm7_v0r_d3m_F411}

このようにしてフラグを求めることができました。

おまけ

この問題において、本当に $n=5$ つも $x_i, z_i$ の組は必要だったのでしょうか。 $n$ を一般化して先程の不等式を考えます。このとき左辺は変わらず $2^k$ 程度となります。 右辺の指数部を計算すると

となります。

左辺の指数部が $k = 350$ であることを考えると、不等式が成立するのは $n \ge 3$ のときになります。

実際に $n$ を可変にして計算してみます。

for n in range(1, 6):
    tmp_matrix = [[0 for _ in range(n+2)] for _ in range(n+2)]
    for i in range(n):
        tmp_matrix[i][i] = p
    for i in range(n):
        tmp_matrix[n][i] = xs[i]
    for i in range(n):
        tmp_matrix[n+1][i] = zs[i]
    tmp_matrix[n][n] = 1
    tmp_matrix[n+1][n+1] = 2**k
    L = Matrix(ZZ, tmp_matrix)
    tmp = hex(abs(L.LLL()[0][n]))[2:]
    if len(tmp) % 2 == 1:
        tmp = tmp.zfill(len(tmp)+1)
    flag = bytes.fromhex(tmp)
    print(n, flag)

1 b'f8\x17u\x8c\xa5\xd5\xbfJTd&\xa8O"rU\x82\xd7\xef\x94\xf8o\xf2\xde\xd4\xef\xf1\xd12i\xe5'
2 b"\x06\x81\x9f-\xbfo\x8d,\x07\x15_QTq\xa6\xb0\x0f\xe2KC\x92i\xda'7\xa8\xcd\xd5\xb3\xd8\x90VIu\xb0\xf1\xb3b\xeb\xe0\x826\x83"
3 b'HarekazeCTF{H0chmu7_k0mm7_v0r_d3m_F411}'
4 b'HarekazeCTF{H0chmu7_k0mm7_v0r_d3m_F411}'
5 b'HarekazeCTF{H0chmu7_k0mm7_v0r_d3m_F411}'

となり、実際 $n < 3$ では答えが正しく求まっていないことがわかります。 この問題に限って言えば、 $n=3$ でも十分に答えを求められたというわけです。

まとめ

Crypto 問で SVP に落とし込めるような問題は、

• 次元がそこまで大きくない
• Given な値の線形和で、それらの値より十分に小さい非自明なベクトルを書き表せることが保証されている

といった特徴を持っています。必要なときは最短ベクトルが満たす不等式を考え、格子基底行列に適宜定数を与えることで柔軟に問題を解くことができます。