第 5 回暗号理論(2)

本日の内容

5-1. 前回の復習
5-2. 暗号理論(2)

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

5-1. 前回の復習

関数の計算は簡単だけれども逆関数の計算は簡単ではないような関数を一方向関数と言います。かけ算はO(n²)でできますが、素因数分解は現在多項式時間のアルゴリズムは知られていません。但し、本当に一方向関数であることを証明すること、つまり、逆関数が多項式時間でないことを証明することは P=NP 問題を示すことにつながるので、基本的には難しいことと思われています。

この一方向という性質を利用した新しい暗号のパラダイムが Diffie, Hellman による公開鍵暗号システムです。これは古典暗号理論で重大な問題であった鍵配布問題を解決します。つまり、暗号鍵から逆関数である復号鍵を作るのが困難であれば、暗号鍵を盗聴されても暗号を解読されません。そのため、受信者があらかじめ暗号鍵と復号鍵を作成し、暗号鍵を通常の通信路に送ることで鍵を配布できます。

このような公開鍵暗号系としていくつかの候補が示されました。ナップザック暗号は NP 完全問題を変形して暗号にしたものです。もとは NP 完全問題ですが、変形のしかたが悪く、多項式時間で解けてしまいました。一方、 RSA 暗号は二素数の積を公開するものです。安全性についてはよくわかっておらず、とりあえず素因数分解が解ければ解けてしまう、つまり素因数分解よりやさしいことだけ分かっています。前回は RSA 暗号で 1 bit の情報が洩れることと暗号が破れることが等価、つまり RSA 暗号が安全な限り 1 bit も情報が洩れないことを示しました。

5-2. 暗号理論(2)

暗号の安全性

公開鍵暗号システムを作るには DH 対を用意する必要がありますが、これには一方向性関数の存在を示す必要があるため、正攻法（一方向性関数であることを証明で示す）は非常に難しいです。そのためいくつか別の方法が考えられています。

難しいと思われている問題を変形する: ナップザック暗号がこれにあたりますが、変形しても難しさが変わらない保証はありません。世間的には難しい問題と同等と思われますが、基本的には「虎の威を借る狐」に過ぎず、もともとの難しい問題より優しいことしかわかりません。変形をうまくしないと reducibility などの安全性を示すことが難しくなります。
あることが易しく解ければ解読できるが、その解決法が知られていない: これも上記と同様、「あること」より難しくないことしかわかりません。 RSA 暗号などがここに含まれます。「RSA が素因数分解の困難さに帰着している」と誤解されていることもありますが、RSA が解けても素因数分解が解けないことはあり得ます。但し、 RSA は一部の bit が解読されることと、全体が解読されることの等価性が示されている分だけ、若干ましと言えます。
難しい問題から Reducibility が示されている: 暗号 Y に対して、その暗号に対する解読機を仮定した時、別の難しい問題 X が解けることを示せたり、その難しい問題を変形して暗号解読に帰着できたりすると、 $(難問 X) \leq^{p} (暗号 Y)$ が示せることになり、解読が少なくとも難問 X 以上に難しいことが示せます。このタイプの暗号として、 RABIN 暗号と EPOC 暗号があります。これら両方とも素因数分解より易しくないことが示されています。今回は EPOC 暗号について説明します。

準備

フェルマーの小定理

p を素数とした時、p と互いに素な任意の a に対して以下が成り立ちます。

a^{p} \equiv a (mod p)

または

a^{p - 1} \equiv 1 (mod p)

これは前に紹介したオイラーの定理において n が素数だった場合にあたります。

証明

p が素数の時、組み合わせの数 $(\begin{matrix} p \\ k \end{matrix})$ (1≤k≤p-1) は p の倍数

実際定義により $(\begin{matrix} p \\ k \end{matrix}) = \frac{p!}{k! (p - k)!}$ において、 k も p-k もともに p より小さいので、 k! も (p-k)! も p を割る素因数を含んでいない。一方、分子の p! は p を素因数に含んでいるので、全体として p の倍数となる。

定理を帰納法により示す

二項定理を考える。

{(a + b)}^{p} = a^{p} + (\begin{matrix} p \\ 1 \end{matrix}) a^{p - 1} b + ... + (\begin{matrix} p \\ p - 1 \end{matrix}) a b^{p - 1} + b^{p}

これを p の法のもとで考えると、上記の指摘により以下が得られる。

{(a + b)}^{p} \equiv a^{p} + b^{p} (mod p)

よって以下が得られる。

1^{p} = 1

2^{p} = {(1 + 1)}^{p} \equiv 1^{p} + 1^{p} \equiv 2 (mod p)

以下、任意の a に対しても同様に定理が成り立つ。

法 p² の離散対数問題

法 p² の離散対数問題は容易に解ける。つまり、 $c \equiv g^{m} (mod p^{2})$ に対して、 c, g, p から m が容易に見つかる。

アルゴリズム

c^{p - 1} \equiv g^{m (p - 1)} = {(g^{p - 1})}^{m} (mod p^{2})

......(1)

一方、フェルマーの小定理より以下が成り立つ。

g^{p - 1} \equiv 1 (mod p)

ここで、この式に対して法 p² の下で考えると、ある d に対して以下が得られる。

g^{p - 1} \equiv 1 + d p (mod p^{2})

......(2)

これを (1) 式に代入すると以下のようになる。

c^{p - 1} \equiv {(1 + d p)}^{m} (mod p^{2})

これを展開する。

\equiv 1 + (\begin{matrix} m \\ 1 \end{matrix}) d p + (\begin{matrix} m \\ 2 \end{matrix}) d^{2} p^{2} + ... (mod p^{2})

第三項以降は p² で割り切れるので、結局以下が得られる。

c^{p - 1} \equiv 1 + m d p (mod p^{2})

ここで (2) を代入すると以下が得られる。

c^{p - 1} - 1 \equiv m d p \equiv m (g^{p - 1} - 1) (mod p^{2})

ここで、 $x (g^{p - 1} - 1) \equiv 1 (mod p^{2})$ となる x はユークリッドの互除法を用いると容易に見つかるので、以下のように離散対数問題が解ける。

x (c^{p - 1} - 1) \equiv m (mod p^{2})

EPOC 暗号

EPOC 暗号では 2 素数 p, q が秘密鍵になります。そして、 n=p²q と n と互いに素な g が公開鍵になります。平文 m に対して、暗号文は乱数 r (0< r < n) に対して、以下のように求めます。

c = g^{m + n r} mod n

復号法

$c \equiv g^{m + n r} (mod n)$ ならば、ある y に対して以下が成り立ちます。

g^{m + n r} = n y + c = p^{2} q y + c

したがって、 $c \equiv g^{m + n r} (mod p^{2})$ となります。

これに対する離散対数問題は上に示したように解け、 $x \equiv m + n r \equiv m (mod p)$ なる x が求まります。

安全性の証明

次に、 EPOC 暗号の解読機を仮定して n の素因数分解が可能なことを示し、暗号が素因数分解以上に難しいことを示します。まず、 n のオイラー関数 φ(n) に対して、以下が成り立ちます。

g^{φ (n)} \equiv 1 (mod n)

従って、暗号文に対して、任意の s で次が成り立ちます。

c \equiv c 1^{s} \equiv g^{m + n r} g^{s φ (n)} \equiv g^{m + n r + s φ (n)} (mod n)

暗号解読機が存在するとすると、この式に関して、 r と s は自由に選べるので、任意の r, s で m が得られることを意味しています。

一方、 rn+sφ(n) において、 r, s が任意の時、これは gcd(n,φ(n)) の任意の倍数になります。 n のオイラー関数は $φ (n) = n (1 - \frac{1}{p}) (1 - \frac{1}{q}) = p (p - 1) (q - 1)$ となります。 n の素因数は p と q しかありませんので、 gcd(n,φ(n))=p となります。つまり、　rn+sφ(n) は一つのパラメータ t により、 tp と表せます。よって、任意の r に対してある t が存在し、以下が成り立ちます。

g^{m + r n} \equiv g^{m + t p} (mod n)

つまり EPOC 暗号が破られるということは、暗号解読機によって g^z mod n という暗号文に対して、 z を p で割った余り y が求まるということです。ここで、 z を n より小さい数からランダムに選ぶことを考えます。 n より小さい数で $z \equiv y (mod p)$ となる z を選んだとき、 z=y となる確率は 1/pq 程度です。よって、 p, q が十分大きければ z≠y となります。この時、 z-y は p の倍数なので、 gcd(n,z-y)=p となるので、ユークリッドの互除法で n と z-y の最大公約数を求めると p が求まります。つまり、 n が素因数分解できることが示せました。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 5 回 暗号理論(2)