チェビシェフ多項式の2変数への拡張と公開鍵暗号（ElGamal暗号）への応用

Transcription

1 チェビシェフ多項式の 変数への拡張と公開鍵暗号 Ell 暗号 への応用 Ⅰ. チェビシェフ Chbhv Chbhv の多項式 より であるから よって ここで とおくと coθ iθ coθ iθ iθ coθcoθ 4 4 iθ iθ iθ iθ iθ i θ i θ i θ i θ co θ co θ} co θ coθcoθ co θ coθ coθ したがって が成り立つ この漸化式と であることより は の多項式となることがわかる T とおく これをチェビシェフの多項式という ここで であるから とおくと であるから co θ co θ co θ T T T したがって T が成り立つ T T T T T T T θ θ 上記の議論は cohθ についても成り立ち - のとき T co rcco のとき T coh rccoh

2 である - のとき T coh rccoh 上記の事柄は の 次方程式 の 解を とすると となるから とおいても得られる Ⅱ. チェビシェフの多項式の任意の体への拡張 次に 任意の体 K で考える では であるので 次方程式 では の拡大体上で不都合が生じる 次方程式を次のように変えて考える の 次方程式 の 解を とすると 解と係数の関係により ただし この方程式が K 上に解を持たない場合は この 次方程式による K の拡大体を考える とおく は 漸化式 を満たす このとき 逆に は負でない整数 で を定めると 特性方程式方程式 の 解をとするとき となる ちなみに coθ とすると coθ となる は次の性質を満たす 命題

3 b b とし 漸化式 b b b 証明 b 漸化式の特性方程式 の 解をとするとb b の定め方により b は負でない整数 でb を定めるとき また より はこの特性方程式の解であるから b 証明終わり } の漸化式と が の多項式であることより は の多項式となることがわかる よって f とおくと 上記の証明から であるから b f f f b f f f f f f が成り立つことがわかる 第 項の高速計算法 を任意の自然数とするとき を 進法で表す L L ただし i は か の値をとり である バイナリー法 とする は負でない整数 の組が与えられたとき の組は次のように求められる また p よって

4 これより の組から が求まる この つを繰り返し用いると を高速に求めることができる Ⅲ. 次方程式の解への拡張体 K での の 次方程式 ただし の 解をとする ただし この方程式が K 上に解を持たない場合は この 次方程式による K の拡大体を考える 解と係数の関係により このとき が成り立つから は となる ただし は整数 とおく が自然数でなく整数とすることが ポイントである は漸化式 を満たす 逆に は整数 は整数 で を定めると 特性方程式 の 解をとするとき となる は次の性質を満たす 命題

5 w とする b b とし 漸化式 で 証明 b } b b wb b は整数 b を定めるとき b 漸化式の特性方程式 w の 解を µ ν とすると b b b の定め方により w b µ ν である また w はこの方程式の解であるから より b µ ν 証明終わり } の漸化式と が の多項式であることより は の多項式となることがわかる よって とおくと 上記の証明から b b であるから w が成り立つことがわかる また の両辺を で割ると となり これをの方程式と考えたとき と が入れ替わっている このことにより

6 が成り立つことがわかる したがって が成り立つ 具体的に を求めてみると 次のようになる 第 項の高速計算法項の高速計算法項の高速計算法項の高速計算法高速に と が求められることを示す } よって また より ここで

7 であるから よって 4 4 より次の漸化式が成り立つ これらを用いると の組から または の組を求めることができ したがって を高速に求めることができる 周期に関する考察周期に関する考察周期に関する考察周期に関する考察命題命題命題命題 は相異なるとき 異なる の個数と 異なる は個数と等しい 証明証明証明証明 と仮定すると よって したがって ここで は相異なるから

8 したがって 逆も成り立つ ゆえに したがって この 対 対応により 異なる の個数と 異なる の個数は等しい 証明終わり 補題 µ ν µ µν ν µν 集合として } µ ν} 証明 とすると µ ν µ µν ν µν µ ν µ µν ν µν µ ν よって 次方程式 の解と 次方程式 解は一致する したがって } µ ν} 逆は明らか 証明終わり µ ν 命題 4 異なる の個数と 異なる集合 } の個数は等しい 証明 とする より より ここで を用いると

9 また より よって と補題により } } 逆は明らか よって } } したがって この 対 対応により 異なる の個数と 異なる } の個数は等しい 証明終わり ここで の個数! 異なる 異なる } であるから が相異なるとき さらに であるから 異なる の個数 6 異なる の個数 の個数 異なる 異なる の個数 それぞれの異なる個数の最小公倍数異なる の個数 体 K の位数 を体 K とその拡大体にうまく配置できれば 異なる 数 程度まで延長できる可能性がある の個数 の個数を 体 K の位 p として 任意の整数 について p を満たすとき p を周期という ここでは 正の周期だけを考える 周期のうち最小なものを 基本周期という このとき 次の定理が成り立つ 定理すべての周期は基本周期の倍数である 証明基本周期を T とし T でないある周期を p とすると p>t より 整数 を用いて ptr r<t と表されるから rp-t となる Tp は共に周期であるから r pt p よって r> とすると r は周期となり r<t より T が最小の周期であることに反する したがって r となるから pt ゆえに p は T の倍数である 証明終わり

10 これより 基本周期は任意の周期の約数であるといえる したがって つの周期が求められれば その周期を素因数分解することにより 基本周期の候補が見つかる 異なる の個数は 基本周期である 体から零元 を除けば群をなすから 異なる の個数は 拡大体の位数 - の約数である さらに 異なる の個数は 異なる の個数と等しいから 基本周期は 拡大体の位数 - の約数である 7 6 実装例 の既約多項式 を用いて体を構成する 7 はメルセンヌ素数である この体 上で公開鍵暗号を作成するとき この体の位数は 7 であるから ⅰ 体が拡大されず 位数が 7 のとき 体の位数 - 7 ⅱ 拡大体の位数が 7 のとき 拡大体の位数 ⅲ 拡大体の位数が 7 のとき 拡大体の位数 - } の 次方程式 で 個の の乱数の組で実験したところ あった 7 周期が の約数であるものは 個あり その内 周期が 7 であるものは 6765 個 周期が 7 の約数であるものは 個 7 7 周期が の約数であるものは 5 個 あり その内 7 7 周期が であるものは 8486 個 7 7 周期が である を用いるのが良いと思われる チェビシェフ多項式との関係 の 次方程式 において とおくと この方程式は を解に持ち 因数分解すると となるから } 次方程式 から作られる多項式を f とし この 次方程式から作られる多項式を とす g ると g f

11 となる この式と f f f より g f f f f g g g と示されるので 新たな多項式が求まった訳ではない Ⅳ 公開鍵暗号の作成 次方程式の解の場合で示す 次方程式の解の場合も同様である 暗号文受信者の初期設定. 乱数 および体 K 上の乱数 を生成する ただし 乱数 は周期が最大となるようにとり は 周期以下の数とする. 初期条件 で 高速計算法により w を計算する. w を公開する が秘密鍵であり w が公開鍵である の既約多項式による拡大体上では であり 他の式も に注意して変形する 暗号文送信者の作業. 乱数 および体 K 上の乱数 v を生成する ただし 乱数 v は周期が最大となるようにとり は周 期以下の数とする. 初期条件 v で 高速計算法により を計算する. 初期条件 w で 高速計算法によりp q を計算する 4. 平文を M とし pq をブロック暗号の秘密鍵として M をブロック暗号化したものと を送信する 暗号文受信者の復号処理. 初期条件 で 高速計算法によりp q を計算する. pq をブロック暗号の秘密鍵として暗号文を復号し M を得る Ⅴ デジタル署名 次方程式の解のとき が 次方程式 の解のとき より よって

12 また すなわち これより 4 よって 4 この恒等式は 三角関数では cococo co co co に対応する この三角関数の恒等式を使う方法は 石井雅治氏の電子署名についての論文 [] より得た f とおくと f f f f } f } f } 4 f が成り立つ f f Schorr 署名の変形 f を送信者の公開鍵とする が送信者の秘密鍵である 送信者は 文書 M に対して秘密の乱数 を選び 次の 文書 M と を合わせた文書のハッシュ値 および を計算する ただし の計算は整数の四則演算で行う f hm od 周期 が M の署名である このとき より f f f f } f } f } 4

13 すなわち f f f f f } f f } f } 4 f が成り立つ f f } f } 4 送信者は 受信者に文書 M とその署名 を送る 4 受信者は ハッシュ hm および f f を求め そしての左辺を計算し それが に等しければ文書 M の署名が確認され 受信者は M が送信者のもの確信する Ell 署名の変形 f を送信者の公開鍵とする が送信者の秘密鍵である 送信者は 文書 M に対して周期と互いに素な秘密の乱数 を選び 次の 文書 M と を合わせた文 書のハッシュ値 hm を計算する ただしの計算は整数の四則演算で行う また はユーク リッドの互除法で計算できる f hm od 周期 が M の署名である このとき であるから このとき より すなわち f f f f } f } f } 4 f f f f f f f } f f } f } 4 f f が成り立つ f f } f } f } 4 送信者は 受信者に文書 M とその署名 を送る 4 受信者は ハッシュ hm および f f f を求め そしての左辺を計算し それが に 等しければ文書 M の署名が確認され 受信者は M が送信者のものと確信する Schorr 署名の変形の方が Ell 署名の変形より 送信者側は互除法による逆元の計算がなく 受信者 側は指数の計算が少ないため 効率が良い

14 次方程式の解への拡張次方程式の解への拡張次方程式の解への拡張次方程式の解への拡張 が 次方程式 の解のとき とおくと } } ここで であるから より であるから を得る よって

15 は任意の整数 について成り立つから の に - を に - を代入すれば の に - を代入すれば の に - を代入すれば 4 より 5 6 したがって のとき 56 より が で表されるから これを 4 に代入すれば についての恒等式が得られる Schorr Schorr Schorr Schorr 署名の変形署名の変形署名の変形署名の変形 w を送信者の公開鍵とする が送信者の秘密鍵である 送信者は 文書 M に対して秘密の乱数 を選び 次の および と文書 M とを合わせた文書のハッシュ値 および を計算する ただし の計算は整数の四則演算で行う hm od 周期 が M の署名である ただし となるように をとる 送信者は 受信者に文書 M とその署名 を送る 4 受信者は ハッシュ値 hm を求める そして w w を求め さらに P Q D D Q P Z Q P W

16 を求める このとき次の等式が成り立てば 文書 M の署名が確認され 受信者は M が送信者のものと確信する } DW D Z D Z } DZ D W D W 上記の恒等式の証明上記の恒等式の証明上記の恒等式の証明上記の恒等式の証明 より } } } したがって } } このとき w w が成り立つから w } } w w w w ここで X Y とおき さらに w w とおくと Y X 同様にして X Y また Y X X X Y Y 4 より Y X 5 Y X 6 が成り立つから D D とおき 56 の右辺をそれぞれ PQ とすると Q P DX

17 DY P Q また 4の両辺にD をかけて DX D DX D } D DY DYD DY D } D DX となるから Z DX W DY とおけば 恒等式が得られる Ell 署名の変形も 次方程式の場合と同様に設計できる Ⅵ 今後の課題. や が有限体 K の拡大体にあるとき がどのような条件を満たせば周期が最大になるか不明で ある 体 K およびその拡大体の位数から 考えられる周期をすべて求め 最大周期未満の周期になる を除外するのがよいであろう. 次方程式 や 次方程式 が解かれて やが求められると 離散対数問題に帰着する 次方程式や 次方程式が指数時間でしか解けない体 K が望ましい の既約 多項式による拡大体上では 次式の平方完成ができないため 解の公式は適用できない. 通常の離散対数問題では 準指数時間の解読法が存在するようだが この方法に準指数時間の攻撃法が存 在すれば この方法は暗号化 復号化に時間がかかるため この方法は無意味である この辺りは不明で ある 参考文献 [] 石井雅治 冪剰余環上の Chbhv 多項式の周期性と電子署名 日本応用数理学会論文誌 Vol.8No