# LLL入門してみた！

どうもDiKOです。
これは[CTF Advend Calennder 2021](https://adventar.org/calendars/6914)の16日目の記事です.
前回はXornetさんの[RSA暗号攻撃で他でも使える n のこと](https://project-euphoria.dev/blog/27-rsa-attacks/)でした。
RSA暗号運用でやってはいけないnのことの応用版といった感じでとても勉強になりました！！

---
## はじめに
今回は[NTRU暗号（簡単版）](https://xz.aliyun.com/t/7163)と[Harekaze mini CTF 2020](https://github.com/TeamHarekaze/harekaze-mini-ctf-2020-challenges-public/tree/main/crypto/wilhelmina-says)の問題を通してLLL（格子基底簡約）に入門していきます.

まず、このお題を選んだ経緯ですが、LLLは色々な暗号方式の解読に適用できるらしいということは聞いており、ずっと気になっていました。格子やSVP、CVPについては勉強していて、格子作ってLLLでSVP求めるんやな！完全に理解したわ！...と思っていたのですが、いざ問題を解こうとすると格子の作り方が分かりません。こんな時はプロのWriteupの出番や！と思ってみると「まず、このような格子を用意します。（格子バーン！）」

**？？？？**

これは僕が数弱過ぎるだけですが、どうやってその格子作ったの？？となり先に進めないでいました。

そこで、この記事では**格子を作る過程**に重点をおいて書いていこうと思います。
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$:crown:
この記事を書く上で、後ろの席の頭の良い:t-rex:に助けてもらったので感謝しています。これからも宜しくお願いします。

**それではやっていきましょう！**

---
こんなタイトルの記事なので格子について何も知らない方もいるかと思い、まずは格子に関する知識を簡単に紹介します。知っている人は問題のところまで飛んでください！
数学的なところは間違いがあるかも知れないので違うよ！ってところは　[DiKO](https://twitter.com/d1k0b3o)までリプをください。

## 格子(Lattice)
格子は一次独立なベクトル$v_i\in \mathbb{R}^m (1\leq i\leq n)$の整数係数の線型結合で表すことができる集合全体のことをいいます。
$$
L(v_1,v_2,...,v_n) =\sum_{i=1}^n a_i*v_i = a_1*v_1+a_2*v_2+...+a_n*v_n\quad a_i \in \mathbb{Z}
$$

同じ格子を張る基底ベクトルは無数に存在します。

### 格子上の困難な問題
様々な暗号方式でこれらの問題に帰着することができ、これを解くことで暗号が解けることがあるみたいです。また、格子は基底ベクトルの数によって次元数が決まるのですが、その次元数が大きい程難しい問題になるみたいです。

#### 最短ベクトル問題(Shortest Vector Problem:SVP)
格子$L$からベクトル$v$のノルム$||v||$が最小となるような非ゼロな最短ベクトル $v\in L$を見つける問題

#### 最近ベクトル問題(Closest Vector Problem:CVP)
格子$L$に含まれないベクトル$w$が与えられた時、ベクトル$w$に対して$||v-w||$が最小となるようなベクトル$w$に最も近いベクトル$v\in L$を見つける問題

### LLL(Lenstra-Lenstra-Lovasz)
LLLは入力としてある格子基底を与えると、基底ベクトルのノルムが小さくなるように更新（基底簡約）していくアルゴリズムです。
格子の次元が小さい場合、LLLはその過程でSVPを効率的に求めることができます。

他にはGaussian Reduction、BKZとかがあるみたいです。

---

いざ、問題を見ていきます。
## NTRU暗号（簡易版）
**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")

**OUTPUT**

h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757

## 格子の作り方
さてさて、本題です。

### 既知の値を使って格子を作れそうな箇所を探す
まず、既知の変数と未知の変数を全て列挙して格子を作れそうな箇所を探します。既知の値は分かりやすいように**大文字**にします。
既知の値は、公開鍵$H,P$と暗号文$C$の３つ、
未知の値は、秘密鍵$f,g$と平文$m$の３つです。
これらの変数を使って式を立てられるところを探します。
すると、$H$についての式、
$$
H = f^{-1}*g \mod P
$$
があります。
この式をグッと睨むと格子が見えればいいのですが、見えないのでもう少し見やすくします。
$\mod p$ の式なので、$a\div b = q \cdots r \to a=b*q+r$のように変形できることを利用して形を変えてみます。この時、既知変数が左辺に来るようにします。
$$
\begin{eqnarray}
&H& = f^{-1}*g \mod P\\
&f*H& = g \mod P \\
&f*H& = k*P + g\\
&f*H& - k*P = g
\end{eqnarray}
$$
ここで、**既知の変数と未知の変数が別れるようにベクトル表示**すると
$$
(H,P)
\begin{pmatrix}
f\\
-k
\end{pmatrix}
= g
$$
となります。秘密鍵は$f,g$なので、$f$ が求まるように$1*f+0*(-k)=f$を追加すると
$$
\begin{pmatrix}
H&P\\
1&0
\end{pmatrix}
\begin{pmatrix}
f\\
-k
\end{pmatrix}=
\begin{pmatrix}
g\\
f
\end{pmatrix}
$$
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$**known**$\quad$ **unknown** $\quad$**want**
となります。
実は**左側の行列に既知変数、真ん中のベクトルに未知変数、=の右側に見つかって欲しい変数を含んだベクトル**が来るようにしています。
既知変数のみでできた左側の行列
$$
\begin{pmatrix}
H&P\\
1&0
\end{pmatrix}
$$
これを転置したものが格子基底行列となっているのですが、もう１つ考えることがあります。
それは、**値のbit長**です。

（**既知変数のbit長＞欲しい変数のbit長**）の場合にLLLで解けそう！となるみたいです。
既知の変数のbit長を見ると$H$:2046bit,$P$:2048bitであり、
wantの変数のbit長は$f$:1024bit, $g$:768bitで、条件を満たしていそうです。

それでは下のようなsageのプログラムを書いて**LLLで殴って**フラグをGetできるか試します！

from Crypto.Util.number import *
H = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
P = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
C = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757

def decrypt(c,f,g,h,p):
    a = (f*c)%p
    m = (a*inverse(f,g))%g
    return m

M = matrix([
    [H,P],
    [1,0]
])
M = M.transpose()
Ml = M.LLL()

for LL in list(Ml):
    g,f = LL
    if int(f).bit_length()==1024 and int(g).bit_length()==768:
        m = decrypt(C,f,g,H,P)
        print(long_to_bytes(m))

結果は、、、

出ました！　**LLL完全に理解した！！**

---
## Harekaze mini CTF 2020
さて、**LLLを完全に理解した**ところでもう一問解いていきます。
問題はHarekaze mini CTF 2020からお借りして[Wilhelmina says](https://github.com/TeamHarekaze/harekaze-mini-ctf-2020-challenges-public/tree/main/crypto/wilhelmina-says)を解きます。

**PROBLEM**

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=}")

**OUTPUT**

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

まず、既知の変数と未知の変数を整理します。

**既知の変数**
T:311 (flagのbit長)
P:〜 (強素数：512bit)
N:5 (配列の長さ)
K:350 (切り捨てるbit数)
XS=(X0,X1,X2,X3,X4) (512bit乱数)
ZS=(Z0,Z1,Z2,Z3,Z4) (それぞれ,510,511,512,512,511bit) ysのそれぞれについて下位kbitを切り捨てたもの

**未知の変数**
f:flag (311bit)
ys=(y0,y1,y2,y3,y4) ( $y_i=X_i*f\mod P$ ) (<512bit)

式を探すと、
$$
y_i = X_i*f\mod P \quad(1)
$$
$$
Z_i = (y_i >> k)<<k \quad(2)
$$
が見つかります。２つ目の式は下位$K$bitを切り捨てる操作なので切り捨てられた分を$t_i$とすると
$$
y_i = Z_i + t_i \quad(3)
$$
と書くことができます。
(1)と(3)の式から
$$
\begin{eqnarray}
Z_i + t_i &=& X_i*f \mod P\\
X_i*f &=& P*q_i + Z_i + t_i\\
X_i*f &-& P*q_i - Z_i = t_i
\end{eqnarray}
$$
のように式変形することができます。($q_i=\lfloor X_i*f\div P \rfloor$です。)
iは0~4なので全て書き出してみると
$$
\begin{eqnarray}
X_0*f &-& P*q_0 - Z_0 = t_0\\
X_1*f &-& P*q_1 - Z_1 = t_1\\
X_2*f &-& P*q_2 - Z_2 = t_2\\
X_3*f &-& P*q_3 - Z_3 = t_3\\
X_4*f &-& P*q_4 - Z_4 = t_4
\end{eqnarray}
$$
となります。これをベクトル表示すると
$$
\begin{pmatrix}
X_0&-P&0 &0 &0 &0 &-Z_0\\
X_1&0 &-P&0 &0 &0 &-Z_1\\
X_2&0 &0 &-P&0 &0 &-Z_2\\
X_3&0 &0 &0 &-P&0 &-Z_3\\
X_4&0 &0 &0 &0 &-P&-Z_4
\end{pmatrix}
\begin{pmatrix}
f\\
q_0\\
q_1\\
q_2\\
q_3\\
q_4\\
1
\end{pmatrix}=
\begin{pmatrix}
t_0\\
t_1\\
t_2\\
t_3\\
t_4
\end{pmatrix}
$$
と書けます。flagであるfが欲しいので$1*f=f$を追加すると
$$
\begin{pmatrix}
X_0&-P&0 &0 &0 &0 &-Z_0\\
X_1&0 &-P&0 &0 &0 &-Z_1\\
X_2&0 &0 &-P&0 &0 &-Z_2\\
X_3&0 &0 &0 &-P&0 &-Z_3\\
X_4&0 &0 &0 &0 &-P&-Z_4\\
1 &0 &0 &0 &0 &0 &0
\end{pmatrix}
\begin{pmatrix}
f\\
q_0\\
q_1\\
q_2\\
q_3\\
q_4\\
1
\end{pmatrix}=
\begin{pmatrix}
t_0\\
t_1\\
t_2\\
t_3\\
t_4\\
f
\end{pmatrix}
$$
となり、この既知変数のみでできた行列を転置したものが格子基底行列になります。
厳密にはスケーリングという操作をした方がいいのですが、今回はflagが求められてしまうのでスケーリングについてはまた勉強したら記事にします。
それでは早速作った格子を**LLLで殴っていきましょう**。

from Crypto.Util.number import *
T=311
P=10701453001723144480344017475825280248565900288828152690457881444597242894870175164568287850873496224666625464545640813032441546675898034617104256657175267
X=[7891715755203660117196369138472423229419020799191062958462005957463124286065649164907374481781616021913252775381280072995656653443562728864428126093569737, 9961822260223825094912294780924343607768701240693646876708240325173173602886703232031542013590849453155723572635788526544113459131922826531325041302264965, 7554718666604482801859172289797064180343475598227680083039693492470379257725537783866346225587960481867556270277348918476304196755680361942599070096169454, 5460028735981422173260270143720425600672799255277275131842637821512408249661961734712595647644410959201308881934659222154413079105304697473190038457627041, 8621985577188280037674685081403657940857632446535799029971852830016634247561494048833624108644207879293891655636627384416153576622892618587617669199231771]
Z=[2445678981428533875266395719064486897322607935804981139297064047499983860197487043744531294747013763946234499465983314356438694756078915278742591478169600, 6687262023290381303903301700938596216218657180198116459210103464914665663217490218525920847803014050091904359944827298080739698457116239163607201903280128, 9144515139738671257281335253441395780954695458291758900110092599410878434836587336752247733779617485272269820837813132894795262162555273673307500761317376, 7005359236736263649027110410188576532095684249796929034336135801107965605961711614006159825405033239188458945408990893269975105260656611838449490684018688, 4638291797440604671051855904609667375394026160401800326727058461541969151082727684535417653507524951373254537356784859777006179731400955193335900924805120]
N=5
K=350

M = matrix([
    [X[0],-1*P,0   ,0   ,0   ,0   ,-1*Z[0]],
    [X[1],0   ,-1*P,0   ,0   ,0   ,-1*Z[1]],
    [X[2],0   ,0   ,-1*P,0   ,0   ,-1*Z[2]],
    [X[3],0   ,0   ,0   ,-1*P,0   ,-1*Z[3]],
    [X[4],0   ,0   ,0   ,0   ,-1*P,-1*Z[4]],
    [1   ,0   ,0   ,0   ,0   ,0   ,0      ]
])
M = M.transpose()
Ml = M.LLL()
for LL in list(Ml):
    z0,z1,z2,z3,z4,f = LL
    if int(f).bit_length()==T:
        print(long_to_bytes(abs(f)))

結果は、、、

出ました！！！　これはもう**LLL完全に理解**したのでは！！

## 最後に
ここまでお読みいただきありがとうございます。LLLは[習得](https://project-euphoria.dev/blog/27-rsa-attacks/#:~:text=%E6%8A%95%E7%A8%BF%E3%81%95%E3%82%8C%E3%81%9F%E3%82%89%E3%80%81%E3%81%9D%E3%81%AE%E8%A8%98%E4%BA%8B%E3%82%92%E3%81%8D%E3%81%A3%E3%81%8B%E3%81%91%E3%81%ABCTF%E3%83%97%E3%83%AC%E3%82%A4%E3%83%A4%E3%83%BC%E5%85%A8%E5%93%A1%E3%81%A7LLL%E3%82%92%E7%BF%92%E5%BE%97)できたでしょうか？
2問解ければ、**LLLの入門は成功**したのではないでしょうか？僕は１問解けただけでも嬉しかったです。しかもプロ達のLLL問のWriteupが読めるようになりました。これはデカい！
このAdvent CalenderをきっかけにLLLの壁を１つ突破できてとてもいい機会になりました。ありがとうございました！

XornetさんいわくSECCON CTF2021は格子問題が多く出ていたみたいなのでそのうち挑戦してみたいと思います！！

明日は[y011d4](https://twitter.com/y011d4)さんが2021年面白かったCrypto問 or LLL問100本(？)ノック or NSUCRYPTO参加記について書いてくれます。
どれも面白そうで楽しみです。

---
## 参考資料
### 今思うと分かりやすい参考資料
[【初心者向け】CTFでとりあえず使いたい人向けの格子入門【kurenaif】](https://youtu.be/Uktq1RYVtbo)
[[English] How to use lattice in CTF? - SECCON 2020 sharsable writeup by Kurenaif](https://youtu.be/g6EruH_29ew)
[出来るだけ数学を回避したLLL入門](https://github.com/Xornet-Euphoria/lll4b/blob/master/lll4b.pdf)
[LLLでCrypto問題を解く](https://project-euphoria.dev/blog/10-lll-for-crypto/)
[格子を利用した(擬)NTRU暗号の解読: 巅峰极客·网络安全技能挑战赛 - NTURE](https://hackmd.io/@Xornet/BJHt36lBP)
[LLL アルゴリズムの Crypto 問への適用](https://blog.y011d4.com/20210102-lll-basic/)
[LLLで殴る【yoshi-camp 2020 Spring備忘録】](https://ptr-yudai.hatenablog.com/entry/2020/03/12/223338)
[LLLを理解するぞ](https://mitsu1119.github.io/blog/post/post1/lll/)

### そのうち分かりやすくなるかも知れない本
格子暗号解読のための数学的基礎
耐量子計算機暗号