アルゴリズム論特論(塩田)第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$ の合同を表すとします。
  1. $x \equiv 0$ のとき
    $x^{ed} \equiv 0^{ed} \equiv 0 \equiv x$
    となって成り立ちます。
  2. $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 の暗号は「公開鍵暗号」になるでしょうか。 提出はしなくて良いですが、次回までに考えておいてください。