アルゴリズム論特論(塩田)第8回 (1) 前回の宿題
戻る / 次へ
$\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}}}$
前回の宿題
まずは復習から。
Lemma 1(第7回 Lemma 16) $p$ を素数とし、$p-1$ と互いに素な 2 つの自然数 $e$, $d$ が
$ed \equiv 1 \pmod{(p-1)}$
を満たすとする。このとき任意の整数 $x$ について
$x^{ed} \equiv x \pmod{p}$
が成り立つ。
Prop.2(第7回 Prop. 17) Lemma 1 の状況下で次のような暗号システムが設計できる。
- 平文集合は $P=\{\,0,1,\cdots,p-1\,\}$
- 暗号文集合も $C=\{\,0,1,\cdots,p-1\,\}$
- 暗号化関数 $E:P\rightarrow C$ は $E(x)=x^e \,\%\, p$
- 復号関数 $D:C\rightarrow P$ は $D(y)=y^d \,\%\, p$
- 暗号化鍵は $(e,p)$
- 復号鍵 は $(d,p)$
ただし、 $\%$ は Python 風に非負の最小剰余を返すとする。
宿題 $p$, $e$, $d$ をもっと巨大にしたとき、
Prop.2 の暗号は「公開鍵暗号」になるでしょうか。
答えは自分で考えてから
宿題 $p$, $e$, $d$ をもっと巨大にしたとき、
Prop.2 の暗号は「公開鍵暗号」になるでしょうか。
答え
暗号方式と公開鍵・暗号文から復号文が計算可能か、というのが問題です。
復号鍵 $d$ は、$e$ と $p-1$ を入力として拡張ユークリッドアルゴリズムを実行すれば高速に求められるので、
この暗号は公開鍵暗号には成り得ません。
ダメなものを教えてもらったって仕方が無い、と思ったかもしれませんが、
この命題を発展させて人類初の公開鍵暗号が実現されました。