第 12 回暗号理論(2)

本日の内容

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

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

12-1. 前回の復習

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

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

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

12-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 に対しても同様に定理が成り立つ。

フェルマー商

フェルマーの小定理から、 x^(p-1) - 1 は常に p の倍数であることが分かっています。これを p で割った商をフェルマー商と言います。

法 p² の離散対数問題

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

アルゴリズム

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 (g^{p - 1} - 1) (mod p^{2})

ここで、 $c^{p - 1} - 1$ と、 $g^{p - 1} - 1$ は、フェルマーの小定理から p の倍数なので、どちらも p で割った商を考えると、次が得られます。

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

ここで、拡張ユークリッドの互除法を使い、 $x \frac{g^{p - 1} - 1}{p} \equiv 1 (mod p)$ となる x を求めれば、次により m を求めることができます。

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

中国剰余定理

中国の算術書『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれているそうです。

定理

$m_{1}, ..., m_{n}$ が互いに素である時、

{\begin{matrix} x \equiv a_{1} (mod m_{1}) \\ x \equiv a_{2} (mod m_{2}) \\ ... \\ x \equiv a_{n} (mod m_{n}) \end{matrix}

を満たす x は $0 \leq x < \prod_{j = 1}^{n} m_{j}$ の範囲で一意に見つかる。

証明

もし、上記を満たすものとして、 x と y という異なる二つの数が存在するとする。すると、 x-y について、全て $x - y \equiv 0 (mod m_{i})$ が成り立つため、 x-y は $m_{1}, ..., m_{n}$ の公倍数になる。したがって、もし存在するなら、 0 から $\prod_{j = 1}^{n} m_{j}$ の間には一つしかない。また、任意の整数 k について $x + x \prod_{j = 1}^{n} m_{j}$ はこの条件を満たす。

存在については次の計算法による。

計算法

$x \equiv a_{i} (mod m_{i})$ について、 mi で割ったら ai 余るけど、他の mj すべてでは、割りきれるような数 yi を考える。

すると、求めるx は yi の総和で表すことができる。

x = \sum_{i = 1}^{n} y_{i}

各 i に対して、以下を満たす $p_{i}, q_{i}$ は拡張ユークリッドの互除法により計算できます。

p_{i} m_{i} + q_{i} \frac{\prod_{j = 1}^{n} m_{j}}{m_{i}} = 1

これを片々 $a_{i}$ 倍して、移項すると次を得ます。

y_{i} = a_{i} q_{i} \frac{\prod_{j = 1}^{n} m_{j}}{m_{i}} = - a_{i} p_{i} m_{i} + a_{i}

これは、両辺が整数であることに注意すると、 $m_{i}$ で割ると $a_{i}$ 余りますが、それ以外の $m_{j}$ では割り切れることを意味しています。

したがって、これを各 i に対して和を取ったものは条件を満たします。

x = \sum_{i = 1}^{n} a_{i} q_{i} \frac{\prod_{j = 1}^{n} m_{j}}{m_{i}}

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 が得られることを意味しています。

一方、 $r n + 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 しかありませんし、 φ(n)は n より小さく、 p を約数に含みます。したがって、gcd(n,φ(n))=h と置くと、これは n 未満の n の約数となります。つまり、この h を求められれば、n を素因数分解できることになります。さて、任意の r,s に対するrn+sφ(n) は一つのパラメータ t と n と φ(n) の最大公約数 h により、 th と表せます。よって、任意の r に対してある t が存在し、以下が成り立ちます。

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

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

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

第 12 回 暗号理論(2)