近似最近ベクトル探索と埋め込み法を用いた格子に依⁰る素因数分解法の実装報告
>100 Views
February 14, 26
スライド概要
RSA暗号の安全性を支える素因数分解問題に対して, 1991年以降Schnorrは格子を用いた素因数分解法を提案している． 2022年, YanらはSchnorrの素因数分解法における格子の変形を提案し, 量子計算による最適化手法を用いた数値実験を報告している． 2023年, 山口らは古典的なアニーリング計算を使用し, Yanらの方法を基に55ビット以下のRSA型の合成数の素因数分解に成功したと報告している． 本稿では, 格子を用いた素因数分解法の古典計算機上での実装報告を行う． 具体的には, YanらによるSchnorrの素因数分解法における格子の変形とパラメータ設定を基準に, 最近ベクトル問題の近似解の探索のために, 既存の格子アルゴリズムである最近ベクトルの数え上げ法と埋め込み法を適用する． 90ビット以下のRSA型の合成数に対して, 30程度までの階数を持つ格子を用いた素因数分解に成功し, その処理時間や素因数分解で必要な関係式の探索の成功確率について報告する．
立教大学大学院で，格子基底簡約アルゴリズムに関する研究をしています． 趣味でゲーム開発も行ってます． C++ | Go | Python | SageMath | Asir | Bash NTL | Eigen | DXライブラリ Visual Studio
関連スライド
各ページのテキスト
近似最近ベクトル探索と埋め込み法を用いた 格子による素因数分解法の実装報告 ◎ 佐藤 新 1 Aurélien Auzemery2 2 片山 瑛 1 安田 雅哉 1 1 立教大学 University of Limoges 2024 年 2 月 16 日（金） ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 1 / 17
1 2 3 4 5 研究背景と本研究の目的 格子を用いた素因数分解法 平方差法 Schnorr による方法 Yan らによる格子の変形 格子を用いた素因数分解法の実装報告 まとめ 参考文献 ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 2 / 17
研究背景 1991 年以降度々, Schnorr は格子を用いた素因数分解法を提案 [3, 4, 5, 6] ▶ ▶ 平方差法の関係式探索を, ある格子上の近似最近ベクトル問題に帰着 階数 90 の格子を利用して, 47 ビット合成数の素因数分解を報告 [5] 2021 年, Ducas は格子による関係式探索を試行実験 [1, 2] ▶ ▶ 合成数のサイズが大きくなると, 関係式探索の成功確率が低くなると指摘 RSA 暗号で利用する合成数に対して, 数体篩法より非効率だろうと示唆 2022 年, Yan らは格子による関係式探索で✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿ 量子計算による最適化手法を利用 [8] ▶ 48 ビットまでの合成数に対し, 関係式を数個見つけることに成功 ▶ 55 ビットまでの RSA 型合成数の素因数分解を報告 2023 年, 山口らは格子による関係式探索で古典アニーリング計算を利用 [9] ✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿ ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 3 / 17
本研究の目的 1 2 格子を用いた素因数分解法の古典計算機上での実装報告 ▶ 既存アルゴリズムで, どの程度のサイズの合成数の素因数分解が可能か報告 ▶ 数体篩法などの素因数分解法より高速になりうるか議論 実験的な計算量の振る舞いを解析 ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 4 / 17
平方差法における概念 pi : i 番目に小さい素数 (i ≥ 1) Pℓ = {p0 = −1, p1 , . . . , pℓ }: 因子基底 (ℓ ≥ 1) 定義 1 (pℓ -平滑) M ∈ Z が pℓ -平滑であるとは, M が Pℓ の元だけで素因数分解できるときをいう. 定義 2 (pℓ -平滑な関係対) (u, v) ∈ Z2 が pℓ -平滑な関係対である def ⇐⇒ ∃ej , e′j ∈ Z≥0 s.t. u = gcd(u, N ) = 1 =⇒ Qℓ Qℓ e′ −ej j j=0 pj e j j=0 pj , u − vN = e′ Qℓ j j=0 pj . = (u − vN )u−1 ≡ 1 (mod N ) ⇝ 以降, 平滑な関係対 (u, v) については簡単のためgcd(u, N ) = 1 を仮定 ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 5 / 17
平方差法の処理手順 1 2 平滑な関係対の探索 N を素因数分解したい合成数とする．因子基底 Pℓ に対し (ℓ + 2) 個の異なる pℓ 平滑な関係対 (ui , vi ) を見つけ Q Q e′ e ui = ℓj=0 pj i,j , ui − vi N = ℓj=0 pj i,j とする（格子を利用した探索法は後述） 非自明な素因子の探索 Pℓ+2 このとき, ∃ (t1 , t2 , . . . , tℓ+2 ) ̸= 0 s.t. i=1 ti (e′i,j − ei,j ) ≡ 0 (mod 2). Q P m ′ X := ℓj=0 pj j ∈ Z mj := 21 ℓ+2 t (e − e ) ∈ Z i i,j i,j i=1 とすると X2 = Qℓ+2 Qℓ i=1 e′ −ei,j i,j j=0 pj t i ≡ 1 (mod N ) より, gcd(X ± 1, N ) が N の非自明な素因子を与えることが期待 ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 6 / 17
Schnorr の格子と平滑な関係対の探索 (1/2) Schnorr による格子と CVP の構成 ▶ N : 素因数分解したい合成数 ▶ p , . . . , p : n 番目までの小さい素数 1 n ▶ c > 0: 与えられた調整パラメータ √ log p1 √ 0 0 log p2 Rn,c := .. .. . . 0 0 ··· ··· .. . 0 0 .. √ . log pn ··· N c log p1 b c N log p2 .1 = .. .. . bn c N log pn の行ベクトルで生成される格子 L = L(Rn,c ) 上で t := 0 · · · 0 N c log N ∈ Rn+1 を目標ベクトルとする最近ベクトル問題 (CVP) を考える. ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 7 / 17
Schnorr の格子と平滑な関係対の探索 (2/2) Schnorr の格子 L = L(Rn,c ) の性質 定理 3 (Schnorr [6, Section 3]) ▶ b := ▶ u := i=1 ei bi ：格子 L 上の格子ベクトル (ei ∈ Z) Pn Q Q −ej ej ∈Z ej <0 pj ej >0 pj , v := 特に ∥b − t∥2 ≥ ln (uv) + N 2c ln u 2 vN N 2c ≫ ln(uv) =⇒ ∥b − t∥2 ≳ N 2c ln u 2 . vN 平滑な関係対の探索の近似 CVP への帰着 b ≈ t のとき |u − vN | が小さくなる ⇝ u − vN が pℓ -平滑になる可能性高まる ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 8 / 17
Yan らによる格子の変形
N ∈ Z, cj > 0,m p1 , . . . , pn ∈ Z は先程と同じ設定
f (i) :=
σ(i)
2
(1 ≤ i ≤ n, σ : {1, . . . , n} → {1, . . . , n} はランダムな n 次の置換)
f (1)
0
0
f (2)
Bn,c = ..
...
.
0
0
⌊10c log p1 ⌉
⌊10c log p2 ⌉
..
..
..
.
.
.
c
· · · f (n) ⌊10 log pn ⌉
···
···
0
0
の行ベクトルで生成される格子 Ln,c := L(Bn,c ) 上で
t = 0 · · · 0 ⌊10c log N ⌉ ∈ Zn+1
を目標ベクトルとする CVP を考える.
Pn
定理 3 と同様に, 102c ≫ i=1 ei f (i) で b ≈ t のとき |u − vN | が小さくなる
⇝ u − vN が pℓ -平滑になる可能性高まる
◎ 佐藤, Auzemery, 片山, 安田
格子による素因数分解法の実装報告
2024 年 2 月 16 日（金）
9 / 17
適用アルゴリズムと実装方法 Yan らによる格子 Ln,c = L(Bn,c ) 上の近似 CVP 求解で pℓ -平滑な関係対を探索 近似 CVP 求解において, 次の 2 つの方法を適用： 1 近似最近ベクトルの数え上げ法 数え上げ前に NTL ライブラリ [7] 内の関数 LLL を用いて 0.99-LLL 簡約 数え上げ上界はBabai 法で得られた近似解 x に対して r := ∥x − t∥ と設定 ▶ ∥b − t∥ ≤ r なる b ∈ L n,c を数え上げる. ▶ ▶ 2 埋め込み法 ⊤ B 0 n,c ▶ B̄ を基底行列として持つ格子 L̄n,c := L B̄n,c を考える n,c := t 1 ⋆ ▶ ▶ t に近いベクトル u ∈ Ln,c は, (t, 1) − (u, 0) = (t − u, 1) ∈ L̄n,c の形で L̄n,c 上の最 短ベクトルの近似解として埋め込まれる． 数え上げ前に同様の方法で基底を簡約し, 数え上げ上界も同様に r で設定 ∥b∥ ≤ r なる b ∈ L̄n,c \ {0} を数え上げ ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 10 / 17
実験結果 (1/3)：格子素因数分解法の処理時間と成功確率 実験方法 RSA 型の合成数 N を格子素因数分解法で分解 Yan らの格子 Ln,c = L(Bn,c ) 上の CVP 近似解から, pℓ -平滑な関係対を探索 ▶ 実験パラメータ：c = 5.0, ℓ = 2n2 を固定．各 N に対し実験的に最良の n を選択 ▶ ▶ 実験結果 埋め込み法は Intel Xeon Gold 5222 CPU @ 3.80 GHz のシングルコア上で, 数え上げ法は Intel Core i7-1355U @ 1.70 GHz 上でそれぞれ実験 ▶ 埋め込み法で, 約 1 日半で 90 ビット合成数の素因数分解に成功 ▶ 一方, N のビット長が増大すると, L n,c 上の CVP 近似解による pℓ -平滑な関係対探索の成 功確率は急激に減少 ▶ 合成数 N の ビット長 m 50 60 70 80 90 近似最近ベクトルの数え上げ法 格子階数 n 成功確率 処理時間 20 3.3% 11.3 秒 24 0.83% 2.9 分 28 0.23% 22.3 分 32 0.049% 3.7 時間 – – – ◎ 佐藤, Auzemery, 片山, 安田 格子階数 n 18 20 25 28 29 格子による素因数分解法の実装報告 埋め込み法 成功確率 10.1% 3.5% 2.3% 0.78% 0.14% 処理時間 36 秒 7.0 分 54.0 分 4.1 時間 35.3 時間 2024 年 2 月 16 日（金） 11 / 17
実験結果 (2/3)：本実験で利用した格子の階数について 因子基底サイズを ℓ = 2n2 と設定 ⇒ 格子の階数は n = O(m/ log m) で十分 ▶ ▶ CVP 近似解の数え上げ法：n ≈ 1.45m/ log m（例：m = 47 なら n ≈ 18） 埋め込み法：n ≈ 2.2m/ log m − 8（例：m = 47 なら n ≈ 17） (Cf., Schnorr は ℓ = n と設定し, m = 47 に対し n = 90 を利用 [5]) ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 12 / 17
実験結果 (3/3)：平滑な関係対探索の成功確率について CVP 近似解による平滑な関係対の探索成功確率は m に関して指数的に減少 ⇝ 1 つの平滑な関係対を見つけるのに, 指数回数分の格子の取り直しが必要 ⇝ 格子素因数分解法の計算量は, m に関して指数時間の振る舞い （これは格子の構成にのみ依存し, 計算機アーキテクチャに依存しない） ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 13 / 17
まとめ 格子を用いた素因数分解法を古典計算機上で実験 Yan らの格子上の CVP 近似解の探索により, 平滑な関係対を探索 CVP 近似解を求めるのに, 数え上げ法と埋め込み法を採用 ▶ 合成数 N のビット長 m に対し, 格子の階数は n = O(m/ log m) を選択 ▶ 埋め込み法で, 約 1 日半で 90 ビット合成数の素因数分解に成功（n = 29 を利用） （Cf., これまでは 55 ビットまでの実装報告 [9]） ▶ ▶ 今回の実験結果から得られた知見 ▶ ビット長 m が増大すると, CVP 近似解から得られる平滑な関係対探索の成功確率 は指数的に減少 ⇝ 格子を用いた素因数分解法は指数時間計算量の振る舞い （これは古典・量子計算機の違いに依らない） ⇝ 準指数時間計算量の数体篩法より非効率 ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 14 / 17
参考文献 I [1] Léo Ducas. Testing Schnorr’s factoring claim in SageMath. https://github.com/lducas/SchnorrGate. [2] Léo Ducas. Schnorr’s approach to factoring via lattices. RISC seminar, 2021. https://projects.cwi.nl/crypto/risc_materials/2021_05_20_ducas_ slides.pdf. [3] Claus Peter Schnorr. Factoring integers and computing discrete logarithms via Diophantine approximation. In Advances in Computational Complexity Theory, pages 171–181, 1991. ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 15 / 17
参考文献 II [4] Claus Peter Schnorr. Average time fast SVP and CVP algorithms: Factoring integers in polynomial time. Rump session at EUROCRYPT 2009, 2009. https: //eurocrypt2009rump.cr.yp.to/e074d37e10ad1ad227200ea7ba36cf73.pdf. [5] Claus Peter Schnorr. Factoring integers by CVP algorithms. Number Theory and Cryptography: Papers in Honor of Johannes Buchmann on the Occasion of His 60th Birthday, pages 73–93, 2013. [6] Claus Peter Schnorr. Fast factoring integers by SVP algorithms, corrected. Cryptology ePrint Archive, Paper 2021/933, 2021. https://eprint.iacr.org/2021/933. ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 16 / 17
参考文献 III [7] Victor Shoup. NTL: A Library for doing Number Theory. http://www.shoup.net/ntl/. [8] Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, et al. Factoring integers with sublinear resources on a superconducting quantum processor. arXiv preprint arXiv:2212.12372, 2022. [9] 山口純平, 伊豆哲也, and 國廣昇. 格子と最適化手法を用いた素因数分解法の実験報告, 2023. 情報処理学会研究報告. ◎ 佐藤, Auzemery, 片山, 安田 格子による素因数分解法の実装報告 2024 年 2 月 16 日（金） 17 / 17