アルゴリズム論特論（塩田） 2020年度教材 第10回
- 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
- 件名は「アルゴリズム論特論第１０回出席」としてください。
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
今日のテーマ
- 素因数分解アルゴリズムのいろいろ
- RSA 暗号に使ってはいけない危険な鍵
RSA暗号は素因数分解問題の困難さに安全性の根拠を置いていますが、
一定の条件を満たす合成数に対しては高速に実行できる素因数分解アルゴリズムがいくつか知られています。
鍵を生成する際にはそれらの攻撃法への対策を施す必要がある、というお話です。
今日は $n=p \times q$ は RSA modulus を表すものとします。
すなわち、$n$ は大きな 2 つの異なる素数 $p$, $q$ ( $p \lt q$ ) を掛けた合成数とします。
1. フェルマ法
Lemma 1 $n$ を知っている者にとって、$p$, $q$ を知ることと、
$n = t^2 - s^2$
を満たす正整数 ( $0 \lt s \lt t \lt \frac{n}{2}$ ) を知ることは同値である。
証明 $\Rightarrow$ ) $p$, $q$ は奇素数ですから
$\displaystyle{t=\frac{p+q}{2}}$, $\displaystyle{s=\frac{q-p}{2}}$
は正整数であり、
$t^2-s^2=(t-s)(t+s)=p \times q = n$.
となります。また $p \lt q$ から
$\displaystyle{0 \lt s \lt t=\frac{p+q}{2}} \lt q = \frac{n}{p} \lt \frac{n}{2}$.
$\Leftarrow$ ) $n=t^2-s^2$, $0 \lt s \lt t \lt \frac{n}{2}$ であれば
$n=(t-s)(t+s)$, $ 0 \lt t-s \lt t+s \lt n$
なので
$t-s =p$, $t+s=q$
となります。(証明終)
相加・相乗平均の関係から
$\displaystyle{t=\frac{p+q}{2} \geqq \sqrt{\,p\,q} = \sqrt{n}}$
ですから、$t$ は $\sqrt{n}$ の切り上げから探索し始めればよく、
次のようなアルゴリズムが考えられます。
Algorithm 2（フェルマ法）
- 入力：RSA modulus $n$
- 出力：$n$ の素因子 $p$, $q$
- $t=\lceil \sqrt{n} \ \rceil$ ( $\sqrt{n}$ の切り上げ )
- $x=t^2-n$
- $s=\lfloor \sqrt{x} \ \rfloor$ ( $\sqrt{x}$ の切り捨て )
- $s^2 \neq x$ ならば $t=t+1$ として 2° へ。
- $p=t-s$, $\ q=t+s$ を出力。
やってみよう $n=2701$ に対してフェルマ法を実行してみましょう。
$\sqrt{2701}=51.971\cdots$ より $t$ の初期値は $52$ で
$t = 52$ のとき $x = 52^2 - 2701 = 3, s = 1, x \neq s^2$
$t = 53$ のとき $x = 53^2 - 2701 = 108, s = 10, x \neq s^2$
$t = 54$ のとき $x = 54^2 - 2701 = 215, s = 14, x \neq s^2$
$t = 55$ のとき $x = 55^2 - 2701 = 324, s = 18, x = s^2$
よって
$p = t - s = 37$, $q = t + s = 73$
$p\mbox{ ≒ }q$ であれば $s$ が小さいので
$\displaystyle{t^2 = n + s^2 \mbox{ ≒ } n}$
となり、$t$ はすみやかに見つかります。
Prop.3 $p\mbox{ ≒ }q$ のとき Alg.2 は高速に $n$ を素因数分解する。
次の例では、1024ビット中、上位504ビットが一致するような 2 つの素数を $p$, $q$ として選んでいます。
フェルマ法を使えば RSA modulus はわずか 9000 個弱の $t$ を検索するだけで素因数分解されています。
Ex.4
素数 p, q のビット数を設定してください。
1024
p と q の差のビット数を設定してください。
520
n = 14149196112247687514027611690732581057503952470709895321388545930824272461201638826590827469315424651523954054382523215566934126979677087970726960197577030999103905968384920488016638041291848046473345848556962223449508878431484461476374272525529947067142190420240413070585979486301904692717454949880813932823442524095614486334454675925145812635243647435580822261952074675533389645899770658475187265610495308115447728317882907660075844673403666542377724402705012882290844170647248595447494740840022084750323565027630771483439556225960734255218999654870501172885973827476094508630332215229005524065867117983516852518541 ( 2047 ビット )
Fermat 法 開始
p = 118950393493454604519592318493413137610691467733052763094120425109015480242836760706582304494291938693713118619402131067177626273768646807372589711103532727492278092426469001325987271423168242480212037196980248091240710081028224993861297478298291257999087827691720198271118490686182430877712824180627090189037
q = 118950393493454604519592318493413137610691467733052763094120425109015480242836760706582304494291938693713118619402131067177626273768646807372589711103535593528215019842954436134049006570412739240738283604621704252231626584784795519989965761597769923483650893988583717495699602504463088564579506924418561871393
検算 :
p * q = 14149196112247687514027611690732581057503952470709895321388545930824272461201638826590827469315424651523954054382523215566934126979677087970726960197577030999103905968384920488016638041291848046473345848556962223449508878431484461476374272525529947067142190420240413070585979486301904692717454949880813932823442524095614486334454675925145812635243647435580822261952074675533389645899770658475187265610495308115447728317882907660075844673403666542377724402705012882290844170647248595447494740840022084750323565027630771483439556225960734255218999654870501172885973827476094508630332215229005524065867117983516852518541
ステップ数 : 8631
計算時間 = 30.10787606239319 sec.
大きな整数の平方根は倍精度実数の sqrt では求められませんので、
例えば次のニュートン法を用いて計算します。
Algorithm 5（ニュートン法）
- 入力：自然数 $n$
- 出力：$n$ の平方根の切り捨て
def mysqrt(n):
if n < = 1:
return n
s = n
while s * s > n:
s = (s + n//s) // 2
return s
数値解析で実数のニュートン法を習いましたね。方程式 $f(x)=0$ の近似解は数列
$\displaystyle{x_{k+1}=x_k - \frac{x_k}{f'(x_k)}}$
を作って求めました。$\sqrt{n}$ は $f(x)=x^2-n=0$ の解で、そのとき上の数列は
$\displaystyle{x_{k+1}=x_k + \frac{x_k^2-n}{2x_k}=\frac{1}{2}\left(x_k+\frac{n}{x_k}\right)}$
となります。除算を整数商に代えたものが
Alg.5 です。
Ex.6
n = 9956894514697920852 ( 64 bit )
Step 0 : s = 9956894514697920852
Step 1 : s = 4978447257348960426
Step 2 : s = 2489223628674480214
Step 3 : s = 1244611814337240108
Step 4 : s = 622305907168620057
Step 5 : s = 311152953584310036
Step 6 : s = 155576476792155033
Step 7 : s = 77788238396077548
Step 8 : s = 38894119198038837
Step 9 : s = 19447059599019546
Step 10 : s = 9723529799510028
Step 11 : s = 4861764899755525
Step 12 : s = 2430882449878786
Step 13 : s = 1215441224941440
Step 14 : s = 607720612474815
Step 15 : s = 303860306245599
Step 16 : s = 151930153139183
Step 17 : s = 75965076602359
Step 18 : s = 37982538366715
Step 19 : s = 18991269314429
Step 20 : s = 9495634919358
Step 21 : s = 4747817983966
Step 22 : s = 2373910040558
Step 23 : s = 1186957117429
Step 24 : s = 593482753008
Step 25 : s = 296749765032
Step 26 : s = 148391659099
Step 27 : s = 74229378923
Step 28 : s = 37181757882
Step 29 : s = 18724773827
Step 30 : s = 9628261807
Step 31 : s = 5331196948
Step 32 : s = 3599431402
Step 33 : s = 3182836172
Step 34 : s = 3155572503
Step 35 : s = 3155454726
Step 36 : s = 3155454723
answer = 3155454723
Prop.7 Alg.5 の計算量は $O(\log^3 n)$.
証明 終盤までは $s$ がほとんど半分半分になっていきますので (
Ex.6 参照 )、ループ回数は $O(\log n)$ で、
ループの中の計算は乗算と除算１回ずつゆえ。(証明終)
2. 拡張フェルマ法
フェルマ法は $p \mbox{ ≒ } q$ のときに有効な素因数分解法でした。
これを拡張して、例えば $q \mbox{ ≒ } \frac{5}{3}p$ のように、
$q$ が $p$ の単純な有理数倍に近いときに有効な素因数分解法を提案することができます。
Algorithm 8（拡張フェルマ法） ( $q \mbox{ ≒ } \frac{5}{3}p$ のときに有効な version )
- 入力：RSA modulus $n$
- 出力：$n$ の素因子 $p$, $q$
- $t=\lceil \sqrt{15n} \ \rceil$ ( $\sqrt{n}$ の切り上げ )
- $x=t^2-15n$
- $s=\lfloor \sqrt{x} \ \rfloor$ ( $\sqrt{x}$ の切り捨て )
- $s^2 \neq x$ ならば $t=t+1$ として 2° へ。
- $(t-s)$ が $3$ の倍数なら
$q=(t-s)/3$, $\ p=(t+s)/5$,
そうでなければ
$q=(t+s)/3$, $\ p=(t-s)/5$
を出力。
証明 今度は $t^2 - s^2 = 15n$ を満たす $t$, $s$ を求めていますので、
$(t-s)(t+s) = ( 3 q ) \times ( 5 p)$
であり、$t \mbox{ ≒ } \sqrt{n}$ と $3q \mbox{ ≒ } 5p$ から
$t-s \mbox{ ≒ } t+s$, $3q \mbox{ ≒ } 5p$
従って
$(t-s,t+s) = ( 3q, 5p )$ or $(5p, 3q)$
となります。(証明終)
Ex.9
p : 1024-bit
q : 1024-bit
q - (5 * p / 3) : 525-bit
n ( 2048-bit ) = 16952692284993692985505233474629517997084855158821331882501997552397722663495061401665413093414109700469766041803629671693592264408739443958936812684248435264906552801571856422815269153229578857022747232247385694443459768234492860009759223259724723071407594037193442631715415396817775635520436357270877328557733425215015707787466227584240610907289578118600666702708502212534644234100967349569684747828920301486133020280515561497977664646611748435738984139938550722814945934103901543922051342595406648535098819668544550554380102678110934099192181157726441439499835953927292513404525947646747256330166123231736515154003
p ( 1024-bit ) = 100854426630645299560723523560299679558944549103404260671551471472352614885413128672590859740154426488665351618661225827544948257552466045434885112459804403647240015057762631211384922332997660735356221802083230189032341173530787023481523525242451866450627052238209807080564430539801704340399281579541097941379
q ( 1024-bit ) = 168090711051075499267872539267166132598240915172340434452585785787254358142355214454318099566924044147775586031102043045908247095920776742391475187433108226358074243257511679313897197492949300170823576182592252005270617116193058529417245273189173513847692343375881367227642071453307205778650489313116415292657
35.012639 sec.
※ 一般に $a$, $b$ が互いに素な奇数で $q \mbox{ ≒ } \frac{a}{b}p$ のときにも、
Alg.8 の $15$ を $ab$ に換えるだけで $n$ が素因数分解できます。
もう少し工夫すれば $a$, $b$ のどちらかが偶数の場合にも拡張できます。
3. p-1 法
次は p-1 法と呼ばれる素因数分解法です。
Lemma 10 $m!$ が $p-1$ の倍数となる $m$ が必ず存在する。
証明 $p-1$ の素因数分解を
$p-1=r_1^{e_1} \times r_2^{e_2} \times \cdots \times r_k^{e_k}$
とすれば $\displaystyle{m=\max_{1 \leqq i \leqq k}\,(r_i^{e_i})}$ でOKです。(証明終)
例えば $p=181$ なら $p-1=180=2^2 \times 3^2 \times 5^1 = 4 \times 5 \times 9$ ですから $m=9!$ は $180$ の倍数になります。
( 本当は既に $6!$ が $180$ の倍数ですが。)
Cor.11 $\gcd(b,n) = 1$ ならば、ある $m$ が存在して $\gcd(b^{m!} - 1, n) \geqq p$.
証明 L'a 10 の $m$ を取れば、フェルマの小定理により
$\displaystyle{b^{m!}=(b^{p-1})^{m!/(p-1)} \equiv (1)^{m!/(p-1)} \equiv 1 \pmod p}$
従って $b^{m!}-1$ と $n=pq$ の $\gcd$ は $p$ 以上になります。(証明終)
これを利用すると次のような素因数分解法が作れます。
Algorithm 12（ p-1 法）
- 入力：RSA modulus $n$
- 出力：$n$ の素因子 $p$, $q$
while True:
$b =$ ( $2$ 以上 $n$ 未満の乱数 )
$m = 1$
while $m \lt$ ( $m$ の上限 ) :
$m = m + 1$
$b = b^m \,\%\, n$
$d = \gcd(b - 1, n)$
if $d = n$ :
break
elif $d \gt 1$ :
$p = d$, $q = n / p$ を出力
内側ループの中の $b$ は、(最初の $b$)$^{m!} \ \%\, n$ ですから、いつかは $\gcd(b - 1, n) \geqq p$ となります。
ただ、運悪く $\gcd(b - 1, n) = n$ となってしまったらこれ以上ループを回しても仕方が無いので最初に戻って $b$ を取り換えます。
Prop.13 Alg.12 は $p-1$ が小さな素因数しか持たないときに有効である。
証明 $p-1$ が小さな素因数しか持たなければ
L'a 10 の $m$ が比較的小さいので。(証明終)
Ex.14
p - 1 の素因数の上限を決めてください。
10000
RSA modulus n のビット数を設定してください。
2048
n = 27725514686523991152703953656443670394994073094079645621104755273492645150601240648134150236982652922644626095274478124530942923726138884894271831233978292385908421670492181977083202012992669321035433852427029919124612285929546778661688704782112093489476315801125649203215749705949748618343520621724552088918136145796793931399781258710793350529005598033651389634070676952371300954422005164380443384006833044077234976719258158544523128068260205354651320360457395843325934732338783691009760806692065711082908764969525657975813309170377642676035630023146488103867727178594215357570883370704693697349854992528661816872049 ( 2048-bit )
p - 1 法 開始しました。
p = 7314773654684679278511813336641222875365390312518900577846521616118628647247955238057332917608153594084214617336148266561608460418924712980369334633055654870332106042639709994807294794574090020175061139333027589944222004847630200104791390643642891124645346703699876592158885283889152000000000000000000000000001 ( 1030-bit )
q = 3790344854863341007511803659094356698406937334029337036027634566111944040780085305476017487785592216781012933384463213230076009840334541563748223507582054435962745739792535656430403644599191791853700285800436786151243611525943176895261924461381731471222896255336495178933087592245697349854992528661816872049 ( 1019-bit )
b = 19690964316362281109544103760720011330076798215089788552611979157791660127896609462932975127626785794787261978406482100311509629429934159971988017915483170917054379189603160844231641133453497105520455337785193425287008785558477180302251375047077146866855034717767869211047768879244163005136921963971912082839064966113602001895712566328414051838000265893189983251088860228640088378627632268936045818760185918295420944254409360815852042630683579077715124185935852094337114742503297930102303004298278398027334882214901964511499444280919413661175368679891421550315859125310255871540692202568104940786804715423989012023148
m = 7321
検算 :
p * q = 27725514686523991152703953656443670394994073094079645621104755273492645150601240648134150236982652922644626095274478124530942923726138884894271831233978292385908421670492181977083202012992669321035433852427029919124612285929546778661688704782112093489476315801125649203215749705949748618343520621724552088918136145796793931399781258710793350529005598033651389634070676952371300954422005164380443384006833044077234976719258158544523128068260205354651320360457395843325934732338783691009760806692065711082908764969525657975813309170377642676035630023146488103867727178594215357570883370704693697349854992528661816872049
計算時間 = 8.425666332244873
4. RSA 暗号に使ってはいけない危険な鍵
p-1 法は $p-1$ が小さな素因数しか持たないときに有効でした。
同様に、 $p+1$ が小さな素因数しか持たないときに有効な p+1 法という素因数分解法もあります。
（その仕組みを理解するにはもっと代数学の知識が要ります。）
RSA 暗号を破ろうとする人は、
たくさんのコンピュータを用意して、
パラメータを変えた拡張フェルマ法や、p-1 法、p+1 法を仕込んで $n$ を素因数分解しようとします。
うち 1 つでも答えが出たら暗号は破れるのですから。
そこで、RSA 暗号の鍵を作るときは最低限、次の条件を満たすようにしなければなりません。
- $p$ と $q$ の比が単純な分数に近くにならないようにする。
- $p-1$, $q-1$ が大きな素因数を持つようにする。
- $p+1$, $q+1$ が大きな素因数を持つようにする。
まとめ
- 特定の条件を満たす合成数に対して有効な素因数分解法がいくつもある。
- RSA 暗号の鍵を生成する際にはそれらの素因数分解法に対する対策を立てなければならない。
自宅学習の例
- サンプルプログラムを動かしてみる。
- フェルマ法、p-1 法などを自作してみる。
- 4. のセキュリティ対策 (1), (2), (3) は具体的にどう実現するか考えてみる。
戻る