Merry CryptoMath !!!!!!

　この記事は CTF Advent Calendar 2021 の25日目の記事です。昨日の記事はSatokiさんによる【文学】 Flagを読むで、面白いフラグを紹介してくれたりLeetについて説明してくれました。

　ところで、最初はアドカレに参加するつもりはなかったのですが、激寒ギャグをしまっておくのもあれだということでCVPの記事を書くことにしました。そのためこの記事を枕にして寂しい夜を過ごすともっと寂しくなる一方です。
　ババイでバイバイバイ（そういえば学会の予稿提出が迫って研究がめちゃめちゃ忙しいのですが、なんで記事なんて書いてるんでしょうか）

　別に難しかったり物珍しい内容の記事ではありません（ギャグがメインなため）。学び全集中の呼吸勢はブラウザバックしてもいいししなくてもいいです。

　あとなんでCVP？って感じるかしれませんが僕も知りません。ふるつき先生に聞いてください。

クリスマスについて

クリスマス 　キリストの降誕祭。十二月二十五日。
　① ―イブ　クリスマス前夜祭。
　② ―カード　クリスマスを祝っておくる絵入りのカード。
　③ ―カロル　クリスマスを祝う賛美歌。
　④ ―ケーキ　クリスマス用の飾りケーキ。
　⑤ ―ツリー　クリスマスのときに立てて飾る常緑樹。
　⑥ ―プレゼント　クリスマスの贈り物。

　ウキウキで布団に入ってサンタクロースの正体を暴くべく頑張って寝たフリをするものの、眠くなっちゃっていつの間にか次の日の朝になって、肌を刺すような寒さに耐えながらクリスマスツリーの下に広がるプレゼントを夢中になって開封する。そんな小さい頃の記憶はないんですがクリスマスはいいですね。

CVP

　格子 $\Lambda$ について、目標ベクトル $w \in \mathrm{span}(\Lambda)$ との距離が最も近い $v \in \Lambda$ を見つける問題を Closest Vector Problem (CVP) とします。

　CVP は一般に多項式時間で厳密解を求めるアルゴリズムが存在しないことが知られています。そのため、暗号理論の観点で結構注目されています。

　しかし（？！） CVP は SVP よろしく近似解法があります。

Kannan’s embedding method

　埋め込み法とか呼ばれてるやつです。CVP と uSVP の同値性が目に見えてわかるので、Babai のアルゴリズム（後述）よりも個人的に好きです。

　uSVP（正確には uSVP$_ \gamma$）というのは、格子の逐次最小について $\gamma \lambda _ {1} < \lambda _ {2}$ みたいなのが成り立つ格子での SVP です。単に SVP と思ってもらって構いません。　

　考える格子を $\Lambda = \mathcal{L}(B) \subseteq \mathbb{Z}^n$ として、目標ベクトル $w \in \mathbb{Z}^n$、CVP の解ベクトルを $v = \sum v_ i b_ i$ とします。（つまり全部整数格子で考える）

　まあ実際のところ暗号の文脈で出てくる格子点は計算機で扱う都合上、与えられる入力として面倒くさいものを考えても有限少数なので、簡単に線形同値な格子が作れますし別に問題ないです。

　また、目標ベクトル $w$ と解ベクトル $v$ の差 $e = w - v$ のノルム $||e||$ も小さいと仮定します。
　このとき、ある正数 $M \in \mathbb{Z}$ を使って次のような行列を構成します。 $$ B’ = \begin{pmatrix} B & \mathbf{0}\\ w & M \end{pmatrix} $$

　$||e||$ が十分小さい時、この行列から生成される格子 $L = \mathcal{L}(B’)$ の SVP がまさに $\begin{pmatrix} e & M \end{pmatrix}$ になります。
　ちなみに具遺体的な $||e||$ の大きさですが、$L$ の逐次最小について $||e|| < \lambda_ 1 / 2$ が成り立っていることが条件です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


print("---------- generate ---------------------------")
B = random_matrix(ZZ, 3, 3, algorithm='echelonizable', rank=3)
for i in range(3):
	for j in range(3):
		B[i, j] *= randint(10, 100)

e = random_matrix(GF(2), 1, 3)
print("e =", e)

v = matrix(ZZ, randint(-100, 100) * B[0] + randint(-100,100) * B[1] + randint(-100, 100) * B[2])
print("v =", v)
w = v + matrix(ZZ, e)
print("w =", w)

M = 1
B = block_matrix([[B, matrix([0, 0, 0]).transpose()], [w, M]])

print("")
print("---------- solve ---------------------------")

print(B)
B = B.LLL()

e = matrix(B[0][0:3])

print("e =", e)
print("v =", w - e)

Babai’s algorithm

　ババイです。実は難しくないです。

　この名前を聞くとBaba is youを思い出すのですが人の名前がついたアルゴリズム名で遊ぶのは最悪なのでやめておきます。Baba is youやったことないし。

　で、アルゴリズムの解説に入るのですが次の操作をやるだけです。

CVPの目標ベクトルを $w = \sum a_ i b_ i$ とします。
$n$ 次元の格子を、$n - 1$ 次の $W \subset \Lambda$ とその直行補空間 $W^\perp$ に分割します。
$W$ 上の超平面 $U$ について、$U + y_ 1$ が $w$ と最も近くなるように $y_ 1$ を選びます。この $y_ 1$ は $y_ 1 = \lfloor l_ n \rceil b_ n$ で決定できます。
$w$ の超平面 $U$ 上の直行射影を改めて $w$ として、上の操作を $W$ で改めて行い $y_ 2$ を得ます。
この１〜４の操作をどんどん次元を落としながら再帰的に繰り返し、$y_ 1,\ y_ 2,\ \cdots,\ y_ n$ を得ます。
$y = \sum y_ i$ が求めたかった一番最初の $w$ の最近ベクトル $y$ となります。

コード書くの、怠惰すぎてやめちゃった。簡単ですし適当にググると出てきます。

最後に

有名ガチプロCTFerが素晴らしい記事を生やしている中、自分はこんなカスみたいな記事を錬成していていいのか……という感じです。それなのにここまで読んでいただいて本当に感謝です。それではよいお年を！