アルゴリズム論特論（塩田）第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 の暗号は「公開鍵暗号」になるでしょうか。
答えは自分で考えてから

戻る / 次へ