(O+P)ut

アウトプット



(O+P)ut

エンジニアのアウトプット

【入門/暗号】離散対数問題とは?

スポンサーリンク

はじめに

主に公開鍵暗号の方式で活用される離散対数問題。辞書にて以下のように解説されています。

離散対数問題とは、ある計算の結果から簡単に逆算ができないような数学上の問題の一つで、整数のべき乗(冪乗)を素数で割った余りを求める計算を用いるもの。

本記事ではそこから「具体的にどういう問題?」「なぜ暗号の世界で利用されているの?」という観点で深掘りし、分かりやすく説明してみました。

離散対数問題とはどういう問題?

離散対数問題を理解するために質問ですが、「とある整数aを冪乗した時、とある整数bで割った余りはいくつか?」という問題と「整数aを何乗すれば整数bで割った余りがcになるか?」という問題、どちらが簡単に見えるでしょうか。

これを具体的な問題にしたのが以下。xとyはどちらが簡単に求めれるでしょうか?尚、A mod B は AをBで割った時の余りです。

x=2^{555} \rm{mod} \> 9973
2^{y} \rm{mod} \> 9973 =1248

直感的にはどちらも大変そうに見えますが、実はxを求めることはそこまで大変ではありません。

というのも以下のパターンのみを計算しておけば
x=2^{1} \rm{mod} \> 9973
x=2^{2} \rm{mod} \> 9973
x=2^{4} \rm{mod} \> 9973
x=2^{8} \rm{mod} \> 9973
x=2^{16} \rm{mod} \> 9973
x=2^{32} \rm{mod} \> 9973
x=2^{64} \rm{mod} \> 9973
x=2^{128} \rm{mod} \> 9973
x=2^{256} \rm{mod} \> 9973
x=2^{512} \rm{mod} \> 9973
555は以下のように巾乗の和に分類することができて
2^{555}=2^{512} \times 2^{32} \times 2^{8} \times 2^{2} \times 2^{1}
modの世界ではそれぞれの掛け算の結果をかけ合わせればいいので
( (  \textbf{a}\>\rm{mod} \> \textbf{m})\times(\textbf{b} \>\rm{mod} \> \textbf{m})) \> \rm{mod} \> \textbf{m} = ( \textbf{a} \times \textbf{b} ) \> \rm{mod} \> \textbf{m}
計算回数自体は冪乗部分が巨大(100桁以上)になっても少なく抑えれます。

一方で以下を満たすyを求めるためにはしらみつぶしに演算していく以外に効率的な方法が見つかっていないため、桁数が巨大になると値を求めるのに天文学的な時間がかかります。
2^{y} \rm{mod} \> 9973 =1248

ここで離散対数問題を一般的に記述すると

素数pと整数g,yが与えられた時に
\textbf{y}=\textbf{g}^{\textbf{x}} \rm{mod} \> \textbf{p}
を満たすxを求めよ

となります。上で上げた通り、xを求めるのは大変ですがxが与えられた場合にその式を満たしているかどうかを判定するのはそこまで大変ではありません。

なぜ暗号の世界で利用されているのか?

暗号システムにおいて、この「xを求めるのは大変だけどxの検証は簡単」という性質は役立ちます。
例えばですが、AとBが秘密の情報をこっそり共有したい場合を想定します。

Aは秘密鍵aを決め、K_{A} = g^{a} \rm{mod} \> pを計算した上でK_{A}のみをBに渡します。
逆にBは秘密鍵bにてK_{B} = g^{b} \rm{mod} \> pを計算した上でK_{B} をAに渡します。

Aは自身が保持しているaとBからもらったK_{B}を利用したK_{B}^{a}=(g^{b})^{a} \rm{mod} \> pが計算できます。そして、この値はB側でもK_{A}^{b}=(g^{a})^{b} \rm{mod} \> pと計算ができ、結果的には同じ値になります。よってAとBは同じ情報を共有することができました。

ここでこの情報が秘密情報として扱えるかどうかは「K_{A}K_{A}gpが盗聴できた時にaまたはbを求めることができるか?」という問いにかかっています。

そしてこの形はまさに先程の離散対数問題と一致するので「求めることはかなり難しい」というわけです。

素数pと整数g,yが与えられた時に
\textbf{y}=\textbf{g}^{\textbf{x}} \rm{mod} \> \textbf{p}
を満たすxを求めよ

ちなみに上で上げた方式は「Diffie-Hellman鍵共有」と呼び、一般的にpは300桁以上かつgは2や5が採用されます。

終わりに

離散対数問題とは「巾乗の結果の割り算は比較的簡単なのに、何乗したらその値になるのかは難しい」という性質を持つ問題です。そしてこの一方方向性は、暗号の世界で利用されていることを解説しました。

本記事が離散対数問題の理解の一助になれば幸いです。

以上、ご参考になれば幸いです。