アルゴリズム論特論（塩田）第7回 (4) RSA暗号設計のための補題
前へ / 戻る / 次へ
$\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}}}$
RSA暗号設計のための補題
Lemma 16 $p$ を素数とし、$p-1$ と互いに素な 2 つの自然数 $e$, $d$ が
$ed \equiv 1 \pmod{(p-1)}$
を満たすとする。このとき任意の整数 $x$ について
$x^{ed} \equiv x \pmod{p}$
が成り立つ。
証明 以下、$\equiv$ は法 $p$ の合同を表すとします。
- $x \equiv 0$ のとき
$x^{ed} \equiv 0^{ed} \equiv 0 \equiv x$
となって成り立ちます。
- $x \not\equiv 0$ のとき
まずフェルマの小定理より
$x^{p-1} \equiv 1$.
ここで条件より
$ed=1 + k(p-1)$
と置けますので、
$x^{ed} \equiv x^{1 + k(p-1)} \equiv x \times (x^{p-1})^k \equiv x \times 1^k \equiv x$.
(証明終)
べき乗剰余を用いた暗号
Prop.17 Lemma 16 の状況下で次のような暗号システムが設計できる。
- 平文(ひらぶん)集合は $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 風に非負の最小剰余を返すとする。
証明 Lemma 16 より $D(E(x)) = x^{ed} \,\%\, p = x$ となるので。(証明終)
Ex.18 $p=307$, $e=37$, $d=91$ とします。
$ed = 3367 =306 \times 11 + 1 \equiv 1 \pmod{306}$
ですから Lemma 16 の仮定が満たされています。
平文 $x=2$ を暗号化すると
$y=E(x) = 2^{37} \,\%\, 307 = 163$.
これを復号すると
$D(y) = 163^{91} \,\%\, 307 = 2$
となり $x$ に戻っています。
宿題
もちろんこんな小さな数では全検索で復号鍵の $d$ を見つけられてしまいますので暗号にはなりませんが、
大きな数を用いるとどうでしょうか。
宿題 $p$, $e$, $d$ をもっと巨大にしたとき、Prop.17 の暗号は「公開鍵暗号」になるでしょうか。
提出はしなくて良いですが、次回までに考えておいてください。