Fermat法とLehman法によるRSA合成数の素因数分解

神奈川大学理学部情報科学科 2014 年度学士論文要旨
指導教員：松尾和人
Fermat 法と Lehman 法による RSA 合成数の素因数分解
宇野将司
1
はじめに
RSA 暗号は、大きな 2 つの素数を掛け合わせた数で
ある RSA 合成数を素因数分解することが困難であるこ
とを安全性の根拠にしている。RSA 暗号について「長
く用いられてきた既知の解法以外に画期的な解法が発見
される可能性は低いと言われているものの、コンピュー
タの計算速度の向上によって、本来秘密にしておかなけ
ればならない秘密鍵を公開鍵から導出することが可能と
なる。」とされてる [4]。1024 ビットのふるい処理を 1
年以内に完了させることが可能となる時期の見積りなど
を踏まえて、
「RSA1024bit については、概ね 2015 年以
降に、危殆化のおそれが高まってくる」としている [4]。
よって RSA 合成数が最低でも 2048 ビット必要とされ
ている。文献 [1] は Fermat 法と Lehman 法に対して、
脆弱な RSA 合成数が存在することを示した。しかし、
Fermat 法と Lehman 法はどちらが有効かどうかは述べ
られていなかった。本研究では、これらの方法で因子の
差に応じて RSA 合成数の因数分解がどの程度の時間が
掛かるかを調べ、どちらの方法が RSA 合成数に対して
有効かを示すことを目的とする。
2
RSA 合成数
RSA 暗号は桁数が大きい RSA 合成数の素因数分解す
ることが困難であることを安全性を根拠にしている暗号
方式である。RSA 合成数は RSA 暗号に使われる合成数
である。RSA 合成数の最低限の大きさは 1024 ビットで
ある。２つの大きな素数（現時点では 2 つともビット数
が同じで、最低限として 512 ビット以上は必要である）
p, q に対して、RSA 合成数は N = pq である。
3
因数分解法
素因数分解することが困難ということを安全性の根拠
にしている RSA 暗号は一般的には安全とされている。し
かし、鍵の生成を誤ると一瞬で素因数分解されてしまう。
例として、因子の差が小さい時に Fermat 法と Lehman
法で簡単に因数分解できる。この Fermat 法と Lehman
法について [2][3] にしたがって説明する。
法を示す。
Algorithm 1 Fermat 法
√
1: for a = ⌈ N ⌉ to N 6+9 do
√
2:
if b = a2 − N は整数 then
3:
return a − b
4: return N
Fermat 法は最悪の場合に試し割り算よりもはるかに効
率が悪い。しかし、Fermat 法にとって最悪の場合とは、
実は試し割り算にとって最も簡単な場合で、その逆も正
しい。Fermat 法を改良した Lehman 法は 2 つの方法を
組合わせて用いる。
3.2
Lehman 法は Fermat 法と試し割り算を組み組合わせ
ることから一般的な数に対応することで、Fermat 法を改
良したものである。試し割り算をし、N が非自明な因子
1
d ≤ N 3 をもつか調べ、持つ場合には、d を出力する。d
を持たなければ試し割り算によって範囲を狭めた
a, k の
√
2 重ループから b = a2 − 4kN に一致すれば非自明な分
解を見つけて終了する。ただし、N > 21 を与えられた
整数とする。Algorithm2 は自然数 N に対する Lehman
法を示す。なお、RSA 合成数に対して, 試し割り算の処
理を行う必要がない。
Algorithm 2 Lehman 法
1:
2:
3:
4:
5:
6:
7:
8:
4
3.1
Fermat 法 [2]
Lehman 法 [3]
1
for d ≤ N 3 do
if n mod d = 0 then
return d
1
for 1 ≤ k ≤ N 3 do
1
√
√
for a = ⌈2 kN ⌉ to ⌊2 kN + 4N√6k ⌋ do
√
if b = a2 − 4kN は整数 then
return gcd(a + b, N )
return N
RSA Factoring Challenge
「RSA Factoring Challenge」とは RSA 社が 1991 年
Fermat 法は分解したい合成数を連続しない平方数の差
から 2007 年までに実際に行っていたコンペのことであ
で表し、2 つの素数の積を求める方法である。合成数 N よ
る。RSA 社は RSA 合成数の大きさに応じて懸賞金を掛
り大きい平方数で最小のものを a2 とする。N = a2 −b2 を
け、最新の計算機環境でどの程度のビット数の整数が素
（a, b は非負の整数）の形に表すことができれば、N =
因数分解可能かを調べていた [5]。数体ふるい法を用い
(a + b)(a − b) と素因数分解できる。
√a − b √> 1 であれ
る事で、
「RSA Factoring Challenge」の中で最も大きい
ば、この分解は非自明である。数列 ⌈ N ⌉, ⌈ N ⌉ + 1, . . .
768
ビットの
RSA 合成数は 2009 年に因数分解された [6]。
から数 a をとって a2 − N が平方数かどうかを調べる「RSA Factoring Challenge」の RSA 合成数の因子に注
ことにする。もしも平方数であれば、それを b2 として、目する。Fermat 法と Lehman 法が有効性を確認するた
N = a2 − b2 = (a + b)(a − b) が得られる。奇数 N が合
め,[7] の RSA-200(663 ビット) 以降の各合成数の因子の
成数であれば、この手続きは a = ⌊ n+9
6 ⌋ に至る前に非自
差を計算を行った。表 1 がその結果である。2005 年に因
明な分解を見つけて必ず終了する。N > 1 を与えられた
数分解された RSA-200 以後は因子のビット数が同じこ
奇数とする。Algorithm1 は、自然数 N に対する Fermat
とから、因子の差は合成数のビット数の半分を超えない
神奈川大学理学部情報科学科 2014 年度学士論文要旨
指導教員：松尾和人
事が表 1 から分かる。RSA-200 以後は同じビット数の因
子が主流である。
表 1: RSA Factoring Challenge の RSA 合成数の因子の
差のビット数
合成数のビット数因子の差のビット数 663bit
332bit
696bit
346bit
704bit
349bit
768bit
381bit
実験
5
Fermat 法と Lehman 法が RSA 合成数に対してどち
らが有効かを調べるため、現在主流である同じビット数
の因子の RSA 合成数に対して Fermat 法と Lehman 法
の因子の差に応じた因数分解時間を計測した。その際、
RSA 合成数はビット数の範囲で最も大きい合成数を使用
した。使用したマシンは Core i7-4820K 3.7GHz、使用
OS は Linux 2.6、使用ソフトは Sage 5.6 である。
5.1
1024 ビットで因子の差が小さい場合
図 1 は因子の差が小さい場合に RSA 合成数の因数分
解に要したグラフである。横軸は差のビット数で、縦軸
は因数分解に掛かった秒数である。RSA 合成数に対して
Lehman で因数分解を試みると、N が大きいため、k = 1
で済む。Lehman 法が k = 1 である間は Fermat 法の for
ループの回数が 2 倍 (時間は 2 倍より多く) 掛かる。実
際に、k=2 に移行するのに 1024 ビットの RSA 合成数だ
と、50 桁の整数の回数の for ループを行うことから RSA
合成数に対しては Lehman 法と比較して Fermat 法が有
効である。
図 2: Fermat 法による 1024 ビットの RSA 合成数の因数
分解の推定年数
6.1
2048 ビットの RSA 合成数の推定
実際に使われる 2048 ビットの RSA 合成数の因子の差
は表 1 から 1020 ビット程度で予想される。その場合に
Fermat 法で因数分解できる推定年数は約 10293 である。
よって、Fermat 法は実用的ではないと言える。しかし、
2048 ビットの RSA 合成数の因子の差が 536 ビット程度
の時には約 7 年半に因数分解できると推定される。以上
のことから鍵生成には細心の注意を払うべきである。
7
まとめ
Fermat 法は RSA 合成数に対して解ける範囲では Lehm
an 法より 2 倍以上の効率があることから、Fermat 法は
Lehman 法より RSA 合成数に対して有効であることを
示した。また、2048 ビットの RSA 合成数を生成を誤る
と Fermat 法で因数分解できることを確認し、具体的な
因数分解に掛かる時間を示した。
参考文献
[1] 沖, 半田, RSA 暗号鍵の Lehman 法による素因数分
解の考察, 2005 年暗号と情報セキュリティシンポジ
ウム予稿集, 3D3-4, 2005
[2] R. Crandall, C. pomerance, 素数全書 (247∼249 ペー
ジ), 朝倉書店，2010 年
[3] R. S. Lehman, Factoring Large Integers, Math.
Comp. 28 (1974), 637-646
図 1: 因子の差が小さい場合の 1024 ビット因数分解
6
Fermat 法で解ける範囲で 1024 ビットの
場合に掛かる推定年数
図 2 は実用的な範囲で因数分解時間を推定したグラフ
である。横軸が因子の差で、縦軸は因数分解に掛かる推
定年数を表す。
[4] 経済産業省, 電子署名及び認証業務に関する法律
の施行状況に係る検討会報告書, 平成 20 年 3 月
http://www.meti.go.jp/policy/netsecurity/
docs/esig/080530_esignreport.pdf
[5] RSA Laboratories, The RSA Factoring Challenge.
Retrieved on 2008-03-10. http://www.emc.com/
domains/rsa/index.htm?id=2092
[6] T. Kleinjung, K. Aoki, J. Franke, A. Lenstra, E.
Thome, J. Bos, P. Gaudry, A. Kruppa, P. Montgomery, D. Osvik, H. te Riele, A. Timofeev, P. Zimmermann, Factorization of a 768-bit RSA modulus.
http://eprint.iacr.org/2010/006
[7] MathWorld: RSA Number, http://mathworld.
wolfram.com/RSANumber.html

Download Report