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

はじめに

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

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

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

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

離散対数問題を理解するために質問ですが、「とある整数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は同じ情報を共有することができました。