第 11 回暗号理論(1)

本日の内容

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

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

11-1. 前回の復習

ポイント

NP とは最適化問題を多く含むなど実用的な問題を多く含む問題のクラスです。ここに含まれる多くの問題は効率のよい(多項式時間の)解法が見つかってません。 NP に含まれる問題に多項式時間のアルゴリズムが存在するか否かは「P=NP問題」と呼ばれ、数学の７大問題の一つとして知られています。

NP は非決定性 Turing 機械で多項式時間で計算できる問題のクラスです。問題一つに対して非決定性 Turing 機械と多項式が一つ対応します。一方、非決定性 Turing 機械は入力を固定すると入力の長さの多項式の長さの論理式で記述でき、その充足可能性を調べることで、受理するかどうかを調べることができます。つまり、あらゆる NP 問題は論理式の充足可能性問題(SAT)に帰着できるため、論理式の充足可能性問題(SAT)は NP 完全問題です(Cook の定理)。 NP 完全問題にはナップザック問題、巡回セールスマン問題、三色問題の他、様々な最適化問題が含まれています。

11-2. 暗号理論(1)

Diffie Hellman 暗号

Diffie Hellman 暗号とは一方向性関数を仮定した暗号モデルです。

シーザー暗号は IBM → HAL など、各文字の順序をいくつかずつずらすものです。この場合の暗号の鍵は文字をいくつずらすかという情報です。これは暗号時の鍵がわかってしまえば復号できてしまいます。

一方、Diffie Hellman 暗号では暗号化鍵がわかっても復号化が難しい暗号を言います。例えば、かけ算は入力の長さに対して、 O(n²) でできる一方、その逆演算である素因数分解は未だに多項式時間でできるアルゴリズムは知られていません。このような性質(逆演算の計算量が大きい)を持つ演算を利用しようと言うモデルがDiffie Hellman 暗号です。無限個のパラメータ k を許す暗号鍵e_k と復号鍵 d_k が次の性質を持つとき、 DH対と言います。

平文空間 P に含まれる任意の平文(文字列) x に対して、 d_k(e_k(x))=x
e_k(x) も d_k(x) も x の長さに対して多項式時間で計算できる。
k から e_k と d_k は k の長さに対して多項式時間で計算できる。
e_k から d_k を知るのが困難

ここで問題なのは 4 番の条件です。困難であることとは、例えば多項式時間で計算できないことなどが条件として考えられます。しかし、 3 番の条件から次の非決定的なプログラムを作ることができます。

k を guess する
k から　e'_k と d'_k を作る
あらかじめ得られた e_k と e'_k が同一かどうか検証する
もし同一なら d'_k を出力し accept 状態に入る
そうでなければ reject 状態に入る

つまり、非決定的には復号鍵は多項式時間で得られてしまいます。これは DH 対の存在を示す(4番の条件を保証する)ことが P≠NP を示すことに帰着することを意味します。このようなこともあり、現在において未だ復号鍵を得るのが困難であることが証明されている DH 対は存在しません。

公開鍵と鍵配布問題

DH 対を満たす暗号鍵があると従来の暗号(古典暗号)で解決し得なかった問題が解決できます。例えば、鍵配布問題です。これは暗号通信を行う際、受信者は復号のための鍵が必要ですが、これをどうやって送信者から受け取るかという問題です。古典暗号では鍵が漏れれば盗聴により解読されてしまいますから、従来は盗聴されない通信路を使って鍵を渡す必要がありました。しかし、この「盗聴されない通信路」があれば、わざわざ盗聴されるような通信路で暗号通信を行う必要はありません。つまり、古典暗号論は自己矛盾を含んでいました。これに対してこの DH 対では次のようにすることで、盗聴される通信路で暗号通信を可能にできます。これを公開鍵暗号と呼びます。

受信者があらかじめ DH 対(e_k, d_k)を作る
e_k を盗聴される通信路で送信者に送る
送信者は e_k を使って受信者へ暗号を送る
受信者は d_k を使って暗号を解読する

DH 対の性質から、盗聴者は e_k と暗号文を得ても解読できません。また、さらに、古典暗号では n 人の相手とやり取りするには n 個の鍵が必要でしたが、この公開鍵暗号では n 人に同じ暗号鍵を渡しても相互には暗号文は解読できません。

さらに、復号鍵を持っているのは本人だけという性質を利用して電子署名というメッセージの認証など、従来の暗号では考えられなかったようなアプリケーションも多く考案されています。

ナップザック暗号

ここではNP完全問題のナップザック問題を応用して作られた DH暗号ナップザック暗号を紹介します。

ナップザック問題は以下のような問題でした。

インスタンス

荷物のサイズの集合 $X = {x_{1}, x_{2}, ..., x_{n}}$
ナップザックのサイズ S

質問

$S = \sum_{x \in Y} x$ を満たす $Y \subseteq X$ が存在するか？

ナップザック暗号とはナップザック問題において、送りたい情報(0,1 の列)に対応して各荷物を入れるか入れないかを決めることでナップザックのサイズを決定し、ナップザックのサイズを暗号文として送るものです。当然、普通にナップザック問題を解く速いアルゴリズムは知られてませんから、何の工夫もしないと復号を効率よくできません。そのため、落とし戸(Trapdoor)という特殊な情報を用いて、復号を効率よくできるようにします。

そこで、Super increasing vector という特殊なナップザック問題のインスタンスを考えます。

定義

$A = (a_{1}, a_{2}, ..., a_{n})$ が super increasing vector であるとは、各 a_k に対して次が成り立つことです。

a_{k} > \sum_{i = 1}^{k - 1} a_{i}

例11-1

1, 2, 4, 8
1, 3, 5, 12

このような super increasing vector に対しては、大きい数から順に入るか入らないかを決めることで、 O(n) 時間で袋に入る荷物を決定できます。

例11-2

11=8+2+1

準備数の合同

a と b が法 p の下で合同 $a \equiv b (mod p)$: a を p で割った余りと b を p で割った余りが等しい。

これは以下を満たすので同値関係になります。

$a \equiv a (mod p)$ (反射律)
$a \equiv b (mod p) \Rightarrow b \equiv a (mod p)$ (対称律)
$a \equiv b (mod p) ⋀ b \equiv c (mod p) \Rightarrow a \equiv c (mod p)$ (推移律)

ナップザック暗号の手順

ここでは Merkle, HellMan 型のナップザック暗号を紹介します。 Super increasing vector A=(a₁,...,a_n) に対して、 2a_n< M なる整数 M と、 M と互いに素な数 u、さらに、拡張ユークリッドの互除法(後述)により $u v \equiv 1 (mod M)$ を満たす v を用意します。公開鍵を B=(b₁,...,b_n) は ua_i を M で割った余りを小さい順に並べたものとします。

n 桁の 0,1 の列 (p₁,...,p_n) をこの暗号で送る場合、各 p_i が 1 の b_i を合計したものを送ります。解読は次のように行います。

送られてきた暗号文に対して、 v をかけ、 M で割った余り r を求めます。
r に対して、元の super increasing vector A でナップザック問題を解きます(O(n))。

例11-3

super increasing vector A=(1,2,4,8)
M=17, u=3, v=6
公開鍵 B=(3,6,7,12) (7は 8*3 を 17 で割った余り。 12 は 4*3)
0110 というメッセージを送るとき、暗号文は 6+7=13 となる
受け取った暗号 13 に対して、 13*6/17 = 4...10
10 = 2+8 より、公開鍵の 2 と 8 に対応した部分が 1 である bit 列、つまり 0110 が受け取ったメッセージ。

ナップザック暗号の安全性

この暗号システムは NP 完全問題を利用しているにもかかわらず、 1982 年に Shamir が多項式時間で破るアルゴリズムを与えました。もともと、真の NP 完全問題であるナップザック問題が解ければ、この暗号は破れますが、逆は言えてませんでした。つまり reducibility としては $(ナップザック暗号) \leq^{p} (ナップザック問題)$ しか言えてませんでした。つまり、ナップザック暗号はナップザック問題より易しいことしかわかってません。ですから、このタイプのナップザック暗号が解読されることと P=NP 問題が未解決なのとはなんら矛盾することはありません。

Shamir のアルゴリズムは公開鍵 B から u と M に拘らず、暗号解読可能な条件を満たす別の super　increasing vector を計算により求めるというものです。

準備

列ベクトル X∈{0,1}ⁿ を平文と考えます。暗号文 c は鍵と平文の内積 BX と考えます。この時、法 M の下で次が成り立ちます。

r \equiv v c \equiv v B X \equiv A X (mod M)

Super increasing vector に対するナップザック問題は O(n) で解け、解は唯一です。また、 AX の値は M 未満なので、 $r \equiv A X (mod M)$ だけではなく、 $r = A X$ が成り立ちます。

暗号文が最終的にもともとの super increasing vector でナップザック問題が唯一解で解けるということは、公開されている鍵においても常に唯一解が存在するということを意味しています。これは、公開鍵に対して、別の係数と法で全く異なる super increasing vector に変換しても性質は変わりません。 Shamir のアイディアは公開鍵に対して、別の super increasing vector に変換する係数 u と法 M を見つけようと言うものです。 super increasing vector の要素は少なくとも法 M の 1/2 以下でなければならず、他にも厳しい制約があります。従って、もし、適切な u と M が見つかれば uB の各要素は M/2 より小さいはずです。ここで、各要素を u 倍して M で割った余りを求めると、原点から傾き b_i の直線が M まで伸びては下からまた伸びるというのこぎり型のグラフになります。これが n 本書けますが、注目したいのは n 本とも下の方にいるような場合です。ここで、さらに super increasing vector の一部もまた super increasing vector ですので、狭い範囲に集中するか否かという候補を見つけるのに、 n 本すべてに注目せずに、定数個の要素に注目しても同様の議論ができます。

次にグラフを 1/M に縮小することを考えます。つまり係数 x として、 0 から 1 までの実数を考え、各 b_i に対して b_ix の小数部分の値を考えるようにします。すると、 u, M という二つのパラメータを、 x のみの一つのパラメータにできます。この x に対して、各 b_ix が 0 付近にかたまるところをみつけ、その付近の値に対して super increasing vector の条件が成り立つ不等式を満たすかどうかを整数線形計画法で解きます。

例11-4

B=(3,6,7,12) に対して、3u が折り返してきて 0 の付近に来るのは、u=M/3, 2M/3 の時になります。候補として、 u=M/3 を考えると、 6u, 7u, 12u とも 0 に近い値になります。次に、 1/M に縮小した状況を考えます。 x=1/3 近辺では 3x-1, 6x-2, 7x-2, 12x-4 がのこぎり型の斜辺の式になります。ここで x=0.35 とすると、 0.05, 0.1, 0.45, 0.2 と super increasing vector の条件を満たします。 u/M=0.35 となる整数の組 (u,M) として (7, 20) と置きます。すると $u B = (21, 42, 49, 84) \equiv (1, 2, 9, 4) (mod M)$ と確かに super increasing vector となります(但し、元の super increasing vector とは大小関係は対応しているが異なる)。これを使うと、暗号文に対して 7 倍して、 20 で割った余りを求め、この super increasing vector を使うことで解読できます。

結局このナップザック暗号は super increasing vector という厳しい制約と、係数をかけて余りを求めるだけという単純な手法により、解読されてしまいました。この後も、ナップザック問題を利用した暗号は開発されていますが、優れたものはできていません。

RSA暗号

RSA 暗号とは次のようなものです。ふたつの大きな素数 p,q に対して、積を n とします。また、φ(n)=(p-1)(q-1) とし、 φ(n) と互いに素な任意の数 e を選びます。さらに $e d \equiv 1 (mod φ (n))$ となる数 d を求めます。公開する鍵は e と n で、復号鍵は d と n です。これも DH 暗号になります。

平文 x を暗号化するには x^e を n で割った余り c を求め、この c を送ります。復号は c^d を n で割った余りを求めると、 x になります。これはオイラーの定理によるものです。

オイラーの定理

n の素因数分解を $n = {p_{1}}^{e_{1}} ... {p_{k}}^{e_{k}}$ とするとき、オイラー関数を次のように定義する。

φ (n) = n (1 - \frac{1}{p_{1}}) ... (1 - \frac{1}{p_{k}})

このとき、 n と互いに素な任意の数 x に対して次が成り立つ。

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

$e d \equiv 1 (mod φ (n))$ なので、ある y に対して、 ed=yφ(n)+1 となります。したがって以下が成り立ちます。

c^{d} \equiv {(x^{e})}^{d} = x^{e d} = x^{y φ (n) + 1} = {(x^{φ (n)})}^{y} x \equiv 1^{y} x = x (mod n)

これにより RSA 暗号が正しく復号されることが分かります。また、現時点で e と n から d を求める方法は n を素因数分解することにより求められますので、 $(RSA 暗号) \leq^{p} (素因数分解)$ となることは分かります。しかし、この n の素因数分解以外に d を求めるのに有効な方法が知られてませんので、今のところ安全に利用できます。

準備ユークリッドの互除法

ユークリッドの互除法は入力のふたつの自然数 x, y に対して、相互に割り余りを求めていくと gcd(最大公約数) が求まるというアルゴリズムです。例えば、 48 と 27 の場合、次のようになります。

48 / 27 = 1 ... 21
27 / 21 = 1 ...  6
21 /  6 = 3 ...  3
 6 /  3 = 2 ...  0

この余りが 0 になる直前の余り 3 が 48 と 27 の gcd になるというものです。ここではこのユークリッドの互除法の性質について調べます。以下 (x>y) を仮定します。

定理

(x と y の gcd) と ((x を y で割った余り) と y の gcd) は等しい

証明

x と y の gcd を d と置く。 x を y で割った時、商が a、余りが b だった時次のように表せる。

x = a y + b

x が d で割り切れるので右辺は d で割り切れる必要がある。一方、 y も d で割り切れるので、右辺が d で割り切れるには b が d で割り切れなければならない。

(x を y で割った余り) と y が共に d で割り切れることが分かったが、次に、この d が最大であることを示す。もし、共に d より大きな数 e で両方共割り切れたと仮定する。 y も b も e で割り切れる。したがって、 x=ay+b より右辺は e で割り切れるので、 x も e で割り切れてしまう。そのため、 x と y の gcd が d であるという仮定に矛盾する。

定理

ユークリッドの互除法の時間計算量は x と y の長さに比例した時間 (O(n))

証明

x を y で割った時、余りは必ず x/2 以下となります。つまり、毎回扱う数は二進数で少なくとも一桁ずつ減っています。したがって、プログラムの実行時間は高々 x と y の長さになります。

拡張ユークリッドの互助法

ユークリッドの互助法の手順を書き下すと以下のようになります。

y / x = a ... b
x / b = c ... d
b / d = e ... f
...
p / q = r ... gcd

これを余りを主体にして書き直すと次のようになります。

y - ax = b
x - cb = d
b - ed = f
...
p - qr = gcd

これを上から b, d, f へと順々に代入していきます。

y - ax = b
x - c(y - ax) = d
(y - ax) - e(x - c(y - ax)) = f
...
Ax + By = gcd

各式は(余り)-(古い余り)(新しい商)=(新しい余り) という形になっています。各余りが x と y の線型結合で書けるとすると、新しい余りも又、 x と y の線型結合になります。結局最終的に Ax + By = gcd という式が得られます。もし、 x と y が互いに素であれば、これは法を y とすることで、次の A が得られたことになります。

A x \equiv 1 (mod y)

このようにかけて 1 になる値は、法 y における x の逆元を求めることとなり重要です。これは RSA 暗号の復号鍵を求める以外にもさまざまな応用があります。このようにユークリッドの互除法の計算結果を記憶しておいて、入力値の線型結合で gcd を表すための係数を求める計算を拡張ユークリッドの互除法と言います。

RSA 暗号の安全性

本来暗号の安全性を示すには、与えられた資源での解読の不能性を示すべきですが、計算の不能性を示すのは Lower Bound を示すことであり、非常に難しい問題です。そのため、別のアプローチが取られます。それは難しい問題からの reducibility です。つまり、もし、対象となる暗号に対して解読機が作られたと仮定した時、その解読機を使うと別の難しい問題を解くことが可能になることを示します。これが示せれば、暗号の解読がその別の難しい問題と同程度以上であることが示せます( $(難問) \leq^{p} (暗号)$ )。

しかし、 RSA に関してはこのようなことは示されていません。これからお話することは、RSA の暗号の 1 bit の解読の難しさです。これは 1 bit だけを解読する解読機があったと仮定すると、 RSA を解読できることを示します。一部だけ解ければ、全体が解けるという結果は、脆弱なように見えますが、実際は reducibility により、 $(RSA) \leq^{p} (RSA の 1bit)$ を示していることになります。 $(RSA の 1bit) \leq^{p} (RSA)$ は自明なので、 $(RSA の 1bit) \equiv^{p} (RSA)$ を示していることになります。つまり、 RSA が安全である限り、 1 bit だけ情報が洩れることが無いことを示します。

$(RSA) \leq^{p} (RSA の 1bit)$

公開暗号鍵 E(x)=x^e mod N に対して、 E(x) から x の上位 1 bit が分かると仮定して、乱数を使って RSA 暗号が高い確率で解読できるアルゴリズムを示します。

暗号文 y=E(x) (x は秘密) が与えられたとします。このとき、乱数 a を選び、 a^ey mod N = yE(a) は計算できます。これは実際には E(ax) を求めていることになります。ここで、1bit 解読機を使って、 a₁, a₂ を ax mod N の上位が 0 となるように選びます。

証明のアイディアは a₁x と a₂x の gcd を拡張ユークリッド互除法により求めることにより、 x を求めます。以下、 RSA の暗号鍵越しにユークリッドの互除法を行う方法を示します。

大小関係: a₁x と a₂x の大小関係は E(a₁x - a₂x)= E(a₁-a₂)y に解読機を使うと求められます。解読機を使うと a₁x - a₂x の上位 bit がわかります。 (a₁x - a₂x) = (a₁ - a₂)x より、 a₁x > a₂x なら、共に上位が 0 なので、引き算の結果も上位が 0 になります。一方 a₁x < a₂x であれば、上位が 1 になります。
割算: ka₂x が a₁x を越えない最大の k は、 ka₂x と a₁x の大小関係を使い、バイナリサーチを行うことで、 n の長さの多項式時間で k が求まります。この時余りは (a₁ - ka₂)x となります。なお、ランダムに a₁ と a₂ を選んだ時、 a₁x と a₂x が互いに素になる確率は 6/π²≒ 60% 程度になるそうです。

これにより、暗号文に y に対して、 1bit 解読機があれば a₁x を a₂x で割った商が求まり、余りは暗号化した状態で求まります。これを繰り返すことで、最終的に gcd が暗号化された形で求まります。これが 1 かどうかは 1 や 0 の暗号文は容易に求まりますので、簡単に判定できます。結局、拡張ユークリッドの互除法を使うと高い確率で A a₁x + B a₂x = 1 となる A, B は平文のまま求まります(割算の商は暗号化せずに求まるため)。つまり次の式が成り立ちます。

(A a_{1} + B a_{2}) x \equiv 1 (mod N)

このうち、 A a₁ + B a₂ は実際に求められるので、再度この値と N とで拡張ユークリッドの互除法を通常の方法で行うことで、 x を求めることができます。

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

第 11 回 暗号理論(1)