アルゴリズム論特論（塩田）　2020年度教材 第14回（最終回）

  • 出席代わりに、塩田 ( 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}}}$

今日のテーマ

  • 中国剰余アルゴリズムの応用
    1. 離散対数問題の解法（ Pohlig-Hellman 法 ）
    2. 秘密分散法
  • 本講義のまとめ
　前回勉強した中国剰余アルゴリズムを今日は暗号理論へ応用します。 ひとつ目は離散対数問題の困難さに基づく暗号に対する攻撃法、 もうひとつは秘密分散法です。

0. 復習

  1. $p$ を素数、$g$ を $\bmod p$ の生成元、 $y \in \znzc{p}$ とするとき、 離散対数 $x = \log_g y$ は $\bmod (p-1)$ の数である。
  2. $m_1$, $\cdots$ $m_k$ が互いに素な法のとき、「$\bmod m_1\times\cdots\times m_k$ での値」は 「各 $\bmod m_i$ での値」から中国剰余アルゴリズムによって高速に求めることができる。

1. Pohlig-Hellman 法

　$\bmod p$ の離散対数問題を上の (1), (2) を利用して解くアイデアは割とシンプルです。
Algorithm 1（Pohlig-Hellman 法）　
  • 入力：素数 $p$, $\bmod p$ の生成元 $g$, $\znzc{p}$ の要素 $y$
  • 出力：離散対数 $x = \log_g y$
  1. $p-1$ を素因数分解し
    $p-1=q_1^{e_1} \times \cdots \times q_k^{e_k}$
    とする。
  2. 各 $i$ について、次に述べる Alg.2 を用いて
    $x_i = x \,\%\, q_i^{e_i}$
    を求める。
  3. 中国剰余アルゴリズムを用いて連立合同式
    $x \equiv x_i \pmod{ q_i^{e_i}}$
    の解 $x$ を求め、出力する。
　離散対数 $x$ は $\bmod (p-1)$ の数なので、 $p-1$ が互いに素な法 $q_i^{e_i}$ に分解できて $x \,\%\, q_i^{e_i}$ の値が求められれば、 中国剰余アルゴリズムで $x$ が求められる、という展開です。

　ステップ 2° は、式は複雑に見えますが計算自体は単純です。
Algorithm 2（Alg.1 のステップ 2°）　 簡単のため $q_i^{e_i}$ を $q^e$ と書く。
  1. $n=(p-1)/q$ とおく。
  2. $(g^n)^0$, $(g^n)^1$, $\cdots$, $(g^n)^{q-1}$ のリストを作る。
  3. $y^n = (g^n)^a$ を満たす $a$ ( $0 \leqq a \lt q$ ) を、2° のリストと比較して求める。
  4. $\left\{y \times (g^{-1})^a\right\}^{(n/q)} = (g^n)^b$ を満たす $b$ ( $0 \leqq b \lt q$ ) を、2° のリストと比較して求める。
  5. $\left\{y \times(g^{-1})^{a+bq}\right\}^{(n/q^2)} = (g^n)^c$ を満たす $c$ ( $0 \leqq c \lt q$ ) を、2° のリストと比較して求める。
  6. 以下同様にして $x$ の $q$-進展開 $x = a + bq + cq^2 +\cdots$ を求める。
　証明は後回しにして、アルゴリズムの実行例を見てみましょう。
Ex.3　$p=101$, $g=2$, $y=26$ として $x = \log_2 26$ を求めます。 （もちろんこのような小さい数なら全検索でも一瞬で答えが出ます。） $p-1=100=2^2 \times 5^2$ ですから $x \,\%\, 2^2$ と $x \,\%\, 5^2$ を求める部分が肝心なところです。
  1. $x\,\%\, 2^2$ を求める。
    1. $q=2$ なので $n=(p-1)/q=50$.
    2. $(g^{50})^0 = 1$,   $(g^{50})^1 = 100$.
    3. $y^{50} = (g^{50})^{a}$ に $y=26$ を入れて
      $100 = (g^{50})^a$
      となりますが、2° のリストと比較して $a=1$.
    4. $\left\{y \times g^{-1}\right\}^{(50/2)} = (g^{50})^{b} $ に $y=26$, $g^{-1}=51$ を入れて
      $100 = (g^{50})^{b}$
      となりますが、再び 2° のリストと比較して $b=1$.
    5. 従って $x \,\%\, 2^2 = a + b \times 2 = 1 + 1\times 2 = 3$.
  2. $x\,\%\, 5^2$ を求める。
    1. $q=5$ なので $n=(p-1)/q=20$.
    2. $(g^{20})^0 = 1$, $(g^{20})^1 = 95$, $(g^{20})^2 = 36$, $(g^{20})^3 = 87$, $(g^{20})^4 = 84$.
    3. $y^{20} = (g^{20})^{a}$ に $y=26$ を入れて
      $36 = (g^{20})^{a}$
      となりますが、2° のリストと比較して $a=2$.
    4. $\left\{y \times (g^{-1})^2\right\}^{(20/5)} = (g^{20})^{b}$ に $y=11$, $g^{-1}=51$ を入れて
      $87 = (g^{20})^{b}$
      となりますが、再び 2° のリストと比較して $b=3$.
    5. 従って $x \,\%\, 5^2 = a + b \times 5 = 2 + 3\times 5 = 17$.
  3. 中国剰余アルゴリズムを用いて連立合同式
    $x \equiv 3 \pmod{4}$,   $x \equiv 17 \pmod{25}$
    を解いて $x=67$ が得られます。
  4. 検算をしておくと $2^{67} \,\%\,101=26$. 御明算です。
Alg.2 の証明　$x$ の $q$-進展開を $x=a + bq + cq^2 + dq^3 + \cdots$ とします。
3°)　$x = a + qA$ と書けますので
$y^n = (g^x)^n=g^{(a+qA)n}=g^{an} \times g^{qnA}=(g^n)^a \times (g^{p-1})^A$
フェルマの小定理より $g^{p-1}=1$ ですから
$y^n =(g^n)^a$
となります。
4°)　今度は $x = a +bq + q^2B$ と書けますので
$x(n/q)=a(n/q) + bn + (nq)B=a(n/q) + nb + (p-1)B$
従って
$y^{(n/q)} = (g^x)^{(n/q)} = g^{a(n/q)} \times g^{nb} \times (g^{p-1})^B=(g^a)^{(n/q)} \times (g^n)^b$
$(g^a)^{(n/q)}$ を左辺へ移せば
$\left\{y \times(g^{-1})^a\right\}^{(n/q)} = (g^n)^b$
5°)　同様の計算で
$\left\{y \times(g^{-1})^{a+bq}\right\}^{(n/q^2)} = (g^n)^c$,
$\left\{y \times(g^{-1})^{a+bq+cq^2}\right\}^{(n/q^3)} = (g^n)^d$, $\cdots$
となり、$c$, $d$, $\cdots$ が順番に求まります。(証明終)
Th.4　$p-1$ の素因数分解がわかっているとき、 Pohlig-Hellman 法の計算量は、$Q=\max_i q_i$ として $\max(O(Q), O(\log^3 p))$.
証明　高速べき乗法、逆数計算、中国剰余アルゴリズムの計算量は高々 $O(\log^3 p))$ であり、 Alg.2 におけるリストとの比較が $O(Q)$ です。(証明終)
Cor.5　$p-1$ が小さい素因数しか持たなければ、 $\bmod p$ の離散対数は Pohlig-Hellman 法によって高速に求めることができる。
※　従って、$\bmod p$ の離散対数を利用する暗号では $p-1$ が大きな素因数を持つような $p$ を選択する必要があります。

2. 秘密分散

　秘密分散とは次の要請を満たす仕組みのことです。
秘密分散の要請
  1. 秘密にしたい情報 $x$ から $t$ 個の部分情報
    $x_1$, $x_2$, $\cdots$, $x_t$
    を作る。
  2. $t$ 個の部分情報のうち $k$ 個があれば元の情報 $x$ を計算できる。
  3. $t$ 個の部分情報のうち $k-1$ 個以下しか無ければ元の情報 $x$ は計算できない。
このとき、$t$ を分割数、$k$ を閾(しきい)値と呼ぶ。
　例えば、暗号化された企業秘密の復号鍵が $x$ であるとし、 $t$ 人の重役にはその部分情報だけを教えておくとします。 重役のうち $k$ 人が合意すれば復号ができますが、 $k-1$ 人以下の合意では復号できない、 そういう仕組みです。
中国剰余アルゴリズムを利用した設計
  1. $x$ は約 $N$-ビットの情報とする。
  2. $N/k$-ビット強の、互いに素な $t$ 個の法  $m_1$, $m_2$, $\cdots$, $m_t$  を作る。
  3. $x_i = x \,\%\, m_i$ とする。
要請(2)を満たすこと　$k$ 個の $x_i$ から中国剰余アルゴリズムを用いて連立合同式
$y \equiv x_i \pmod{m_i}$
の解 $y$ を求めれば、$y$ を定める法のビット長は
$(N/k) \times k = N$ 強
ゆえ、$y$ は元の $x$ に等しくなります。

要請(3)を満たすこと　$k-1$ 個以下の $x_i$ から連立合同式
$y \equiv x_i \pmod{m_i}$
の解 $y$ を求めても、$y$ を定める法のビット長は
$(N/k) \times (k-1)$
以下ゆえ、$y$ の情報はまだ約 $N/k$-ビット以上不足しています。

※　実用に当たってはもう少し複雑な設計をすることが多いですが、 基本的なアイデアはこれと同じです。

参考

  • 暗号ライブラリ crypto.py ... 以下のプログラムに引用
  • Pohlig-Hellman 法デモプログラムPH.py
実行例
幾つまでの素数を小さいと考えますか ( 100 以上 ) : 1000
素数 p のビット数を指定してください ( 10 以上 ) : 1024

素数生成中 ...
素数 p = 2258968316115259531236612710706864812801625388363886419505487896413704583382991502282273274396238423791479079706354652138857156035724251041017314131706386506243212885895864440421288806441673565124738377440599931624404714724436345388982983221338004707455459667648391257564119040000000000000000000000000000000001 ( 1028 bits )
p-1 の素因数分解 : [[2, 103], [3, 44], [5, 34], [7, 23], [11, 9], [13, 5], [17, 7], [19, 9], [23, 2], [29, 4], [31, 8], [37, 2], [41, 4], [43, 3], [47, 2], [59, 4], [61, 1], [67, 2], [71, 2], [73, 3], [79, 3], [83, 3], [89, 2], [97, 2], [103, 2], [107, 1], [109, 1], [137, 3], [139, 1], [149, 1], [151, 1], [157, 1], [191, 2], [193, 1], [197, 1], [211, 1], [251, 1], [277, 1], [283, 1], [311, 1], [313, 1], [397, 2], [431, 1], [443, 1], [467, 2], [487, 1], [547, 1], [571, 1], [577, 1], [613, 1], [673, 1], [701, 1], [709, 1], [733, 1], [823, 1], [829, 1], [877, 1], [911, 1]]
原始根計算中 ...
法 p の原始根 g = 159
y = 1943412200448161918272568217533643089770088552943561076336928801170280559986331456354647684839103722023539802628445305860905081943843100543472541651688514044940541280534877898440948956393472313659302626371316904753224162963024582322222499495423165610101288208763360644310367191450243764378192801308195283457103
離散対数 x = log_g(y) を求める

Pohlig-Hellman 法開始
x mod 2^103 = 5546254845206667923759569927658
x mod 3^44 = 623422219145647624879
x mod 5^34 = 297568777965974945791837
x mod 7^23 = 9869616109269471215
x mod 11^9 = 399376899
x mod 13^5 = 278834
x mod 17^7 = 23314227
x mod 19^9 = 168405771692
x mod 23^2 = 53
x mod 29^4 = 565123
x mod 31^8 = 4133224832
x mod 37^2 = 437
x mod 41^4 = 1365962
x mod 43^3 = 12125
x mod 47^2 = 2074
x mod 59^4 = 11326329
x mod 61^1 = 40
x mod 67^2 = 1014
x mod 71^2 = 1521
x mod 73^3 = 57437
x mod 79^3 = 181408
x mod 83^3 = 56253
x mod 89^2 = 1329
x mod 97^2 = 4278
x mod 103^2 = 5556
x mod 107^1 = 1
x mod 109^1 = 21
x mod 137^3 = 404201
x mod 139^1 = 34
x mod 149^1 = 128
x mod 151^1 = 33
x mod 157^1 = 121
x mod 191^2 = 14224
x mod 193^1 = 104
x mod 197^1 = 123
x mod 211^1 = 35
x mod 251^1 = 161
x mod 277^1 = 139
x mod 283^1 = 233
x mod 311^1 = 303
x mod 313^1 = 167
x mod 397^2 = 109496
x mod 431^1 = 143
x mod 443^1 = 209
x mod 467^2 = 55302
x mod 487^1 = 110
x mod 547^1 = 418
x mod 571^1 = 509
x mod 577^1 = 383
x mod 613^1 = 405
x mod 673^1 = 152
x mod 701^1 = 672
x mod 709^1 = 447
x mod 733^1 = 550
x mod 823^1 = 331
x mod 829^1 = 791
x mod 877^1 = 756
x mod 911^1 = 383

解 x = 282945460895527248767774214278626004388782417161647738940816527628105549780903800388503639268434179365851215172611796975330277345628219402987915858847886590202863615333843354922913148900588899813039393526360685247918722028252311161290922503287073025949555047784437168071142090421783191565901080536317963369962
検算 : g^x = 1943412200448161918272568217533643089770088552943561076336928801170280559986331456354647684839103722023539802628445305860905081943843100543472541651688514044940541280534877898440948956393472313659302626371316904753224162963024582322222499495423165610101288208763360644310367191450243764378192801308195283457103
y = 1943412200448161918272568217533643089770088552943561076336928801170280559986331456354647684839103722023539802628445305860905081943843100543472541651688514044940541280534877898440948956393472313659302626371316904753224162963024582322222499495423165610101288208763360644310367191450243764378192801308195283457103
計算時間 = 5.345960378646851

3. 本講義のまとめ

  • 計算量が $\log$ で書けるアルゴリズムは高速に実行できる。
  • 例えば加法・減法の計算量は $\log$ オーダー、乗法・除法の計算量は $\log^2$ オーダー。
  • 公開鍵暗号の設計・運用では高速なアルゴリズムが使われる。
    • 拡張ユークリッドアルゴリズム
    • 法演算
    • 高速べき乗
    • 素数判定
    • 素数生成
    • 中国剰余アルゴリズム etc.
  • 公開鍵暗号の攻撃には困難と考えられている問題を解く必要がある。
    • 素因数分解問題
    • 離散対数問題 etc.
  • 素因数分解問題、離散対数問題には「解きやすい場合」があるので、 鍵の生成時にはそれらの場合を避けなければならない。
　アルゴリズム論特論の講義はこれで終了です。試験はありません。 課題の最終締め切りは 8月3日(月) 12:00 とします。まだ提出していない人は頑張りましょう。

戻る