---
tags: crypto, ctf
---

# 格子を利用した(擬)NTRU暗号の解読: 巅峰极客·网络安全技能挑战赛 - NTURE

## お断り

* タイトルにある通り格子を利用したNTRU"っぽい"ものの解読をします、NTRU暗号自体の解読はありません、NTRUは年内に出来たらやりたいです
* 扱うCTFなんですが、中国のCTFである事から正式名称がよくわかりませんでした。ひとまず会場跡地っぽいサイトから拾って翻訳をかけてタイトルに付けましたが誤っている可能性があります(問題名はおそらく合ってます)
* Writeupで扱う格子の知識は掻い摘んで説明しますが~~記法が複雑で書くのが面倒くさい~~解読の本質から逸れる部分があるので格子関連の用語の定義とかは各自ググってほしいです
* 格子の基底簡約(縮小)を行うアルゴリズムが出てきますがなぜそれが有効なのかの説明はしません(~~証明が面倒くさい~~)

## Writeup

### outline

NTRU暗号っぽいが多項式では無くただの整数が使われている暗号が与えられる。秘密鍵f,g を並べたベクトルは、公開鍵h, pと0, 1から構成されるベクトル(1, h)と(0, q)を基底に持つ2次元格子行列上の格子点になる上、これら2つの基底に比べてかなり小さいことが期待されるのでこの格子をGauss(Lagrange)の基底簡約アルゴリズムで簡約すると、その内の短い方が秘密鍵となるので後は復号するだけ

### Problem

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


def generate():
    p = getStrongPrime(2048)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        return (p, f, g, h)


def encrypt(plaintext, p, h):
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    c = (r * h + m) % p
    return c


p, f, g, h = generate()
c = encrypt(flag, p, h)
with open("cipher.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")

まず法となる2048bitの素数 $p$ を生成し、それの半分(1024bit)以下のbit数である $f$ , 更にそれよりbit数が小さい(768bit)素数 $g$ を生成する。これらのパラメータを利用して $h :\equiv f^{-1}g \mod p$ となる数 $h$ を用意する。これらの内 $p, h$ が公開鍵、 $f, g$ が秘密鍵となる。

暗号化は次のように行われている。
平文 $m$ に対して $p$ の半分以下のbitである数 $r$ をランダムに取ってきて $c \equiv rh + m \mod p$ を計算し、これが暗号文になる。
(余談だが、このアルゴリズムではplain RSAとは異なり、公開鍵が固定でも同じ平文から異なる暗号文が出力される)

このソースコードでは提供されていないが、この暗号は次のようにして復号出来る。
$a :\equiv cf \mod p$ を計算する。この $a$ に対し $m \equiv af^{-1} \mod g$ となる。

復号については本当にそうなるかを調べておく。
まず $a$ を計算する。

$$
a :\equiv cf \equiv rfh + fm \equiv gr + fm \mod p
$$

ここで3番目の式は $h\equiv f^{-1}g \mod p$ から $fh \equiv g \mod p$ を利用した。
さてここで各数字のbit数に注目すると $gr$ は768+1024=1792bitが上限であり、 $fm$ は 1024+<平文のbit数>になる。ということは平文が十分(128文字より)短ければ $gr + fm$ は $p$ で法を取るまでもなく $p$ より小さいと期待出来るので単純に $cf$ を $p$ で割った余りと同じになる。
後は $g$ が素数なので $f, g$ は互いに素であるから $f^{-1} \mod g$ が存在し、これを $a$ に掛けて $a \equiv f^{-1}gr + m \mod g$ となるので $g$ で剰余を取る事で $m$ だけが残る。

したがって公開鍵 $p, h$ から $f, g$ を求める事が出来れば復号は出来る( $f, g$ が秘密鍵なので当然といえば当然)。

### 格子基底簡約

暗号理論の最先端では"格子"というものが扱われる事がある。これは基底の整数係数線形結合で張られるベクトル全体の集合を指す。そしてこの基底を並べた行列で格子を表すことがある。
実は1つの格子を表す行列は複数存在する。格子に関する問題を解くという実用の面ではこの行列には"良し悪し"が存在する。大まかに言えば良い基底行列は直交しており、悪い基底行列は基底同士の向きが近いという特徴がある。

そして格子が貼るベクトルの集合の中で最も短い非零ベクトルを求める問題がある。これを最短ベクトル問題(SVP)と呼ぶのだが、所謂良い基底ではこれが求めやすい。
後述するGaussのアルゴリズムにより2次元格子では厳密解を求める事が出来るがそれ以上の次元になるとNP困難であると言われている。そこで現れたのが"格子点中で出来るだけ短いベクトルを探す"というような問題だが、これはLLLアルゴリズムというものが1980年頃に考案され、実用に足るぐらい短いベクトルを導出出来る。
RSA問題攻略でお馴染みのCoppersmith's Attackはこいつを利用している。

なお、いずれのアルゴリズムも正確には短いベクトルを求めているのでは無く、同一格子を示す"良い"基底を導出し、その内の最も短いものを出力している(基底は非零ベクトルからなるのでそれの内最も短いものを係数を1とし残りの係数を0とすれば格子上の点になる)。

さて、長くなったがこのLLLアルゴリズムに代表されるような基底簡約によって問題が解ける事がある。今回はその良い例である。

#### この暗号への適用

$h$ の定義から $fh \equiv g \mod p$ であるから $fh - g = k_gp$ となる整数 $k_g$ が存在する。単純に移項すると $fh - k_gp = g$ となる。
ここで2つの基底 $(1, h), (0, q)$ から格子を構成すると次のような表現行列 $M$ が得られる。

$$
M = \left[
\begin{array}{rrr}
1 & h \\
0 & p
\end{array}
\right]
$$

これに対してベクトル $(f, -k_g)$ を左から掛けると $(f, fh - k_gp) = (f, g)$ となる。
これは $(f, g) = f(1, h) + (-k_g)(0, p)$ であることから2つの基底の整数係数線形結合であり、 $(f, g)$ は $M$ によって表現される格子上に存在する。

さて、改めて2つの基底のノルムを考えてみるといずれも $p$ のbit数である2048bitになる。それに比べて $f, g$ は1024bit, 768bit程度であるので遥かに小さい数字であることがわかる。つまりもし $M$ で表現される格子点の中で短いベクトルを見つけることが出来れば、これに一致する可能性がある。よってこの格子におけるSVPを解く事を目標にする。

### Gauss/Lagrangeのアルゴリズム

※Gaussのアルゴリズムと言ってるところもあればLagrangeのアルゴリズムと言っているところもあったので併記してます(私が見た中での初出はGaussだった)。

Gauss/Lagrangeのアルゴリズムという基底簡約のアルゴリズムが存在する。こいつは2つの基底からなる格子の中で最も短い2つのベクトルを"厳密解で"導出出来るという凄いアルゴリズムである。
今回の問題では前述の格子が2つの基底から成っているのでこのアルゴリズムを適用できる。

(ここに具体的なアルゴリズムを擬似コードか何かで書こうと思ったが飽きたので参考文献3, 4辺りを参照してください、ついでにcodeの欄にPythonでの私の実装例リンクがあります。やっていることはEuclid互除法的にベクトルをどんどん小さくしていっている感じです)

## Code

※自作パッケージ(xcrypto)にガウスの基底簡約アルゴリズムはあるのでそちらは省略(下記リンクにあります)
* <https://github.com/Xornet-Euphoria/xctf/blob/master/src/xcrypto/lattice.py>

from xcrypto import gaussian_reduction, Vector, dump_num


def decrypt(p, h, f, g, e):
    a = (f*e) % p
    m = (a*pow(f, -1, g)) % g

    return m


if __name__ == '__main__':
    h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
    p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
    c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757

    v, u = Vector([1, h]), Vector([0, p])

    sv, _ = gaussian_reduction(v, u)
    f, g = sv.unpack()

    print(f, g)
    m = decrypt(p, h, f, g, c)
    dump_num(m)

## Flag

`flag{c3bb1f88-2c0b-48fc-9902-beada6d50df6}`

## 感想

厳密解では無く出来るだけ小さい基底を持ってくるアルゴリズムとして有名なLLLを利用したCoppersmith's Attackはこれまで触った事がありましたが、実際格子をどう利用してるかはブラックボックスでわかりませんでした。
今回はそれとは別の暗号, アルゴリズムではありますがこうして格子を利用した攻撃を自分で実装出来てよかったです。
次の目標はLLLの実装と多次元格子の簡約を自前のアルゴリズムで行って問題を解く事です。幸いプロの方々が"日本語"で参考記事を色々書いているのでそれを読んでいこうと思います(とは言いながら最終的に英語の文献に頼る事になる)。
あとはNTRUの解読をする問題を探して解けたら嬉しいです。これも結構難易度が高いと思うので年内を目標にしていきます。
ついでにまだ格子の理論に入りたてで理解が甘い部分が多々あるのでここも埋めていきたいです(Minkowskiの定理辺りから怪しい)。

## 参考文献

1. [从一道CTF题初探NTRU格密码](https://xz.aliyun.com/t/7163): 今回のWriteupの大半は実質この記事の和訳(by Google翻訳)
2. [現代暗号への招待 - サイエンス社](https://www.saiensu.co.jp/search/?isbn=978-4-7819-1262-2&y=2010): 暗号の入門書であるが、最終章である15章に格子の話が載ってる
3. [LLLを理解するぞ - みつみつみつですか？](https://mitsu1119.github.io/blog/post/post1/lll/): 格子関連の用語はここがわかりやすい、ついでにGauss/Lagrangeのアルゴリズムも載ってる
4. [Lattice reduction - Wikipedia](https://en.wikipedia.org/wiki/Lattice_reduction): Gauss/Lagrangeのアルゴリズム(とLLL)について
5. [NTRUEncrypt - Wikipedia](https://en.wikipedia.org/wiki/NTRUEncrypt): 問題とは直接関係無いが今回の暗号がNTRUの簡略版という事が分かる