1. 暗号の基礎

ここでは、暗号の実際的運用に基づいて、簡単に話をしようと思う。

近年、ネット上で秘密にしておきたい情報のやり取りが盛んになり、 クレジットカード決済だけではなく、様々な分野で暗号が使われるようになった。 暗号の様々な活用方法が考えられるが、とりあえず、Web上でログインする場合の、破られにくい暗号を使ったログイン方法を模索し、提供することを目的として、 考えていくことにする。（他の活用もあるが、勉強のし易さの観点から、とりあえずの目標を立ててみたという浅い考えである。 目標があれば、何を学習したらよいかの方向性が決まり、モチベーションも上がるだろう。）

暗号には多くの種類があるが、

  1. 共通キー暗号
  2. 公開キー暗号

と大別される。

1.1 共通キー暗号

共通キー暗号は古くから存在する一般的な暗号であり、長い歴史がある。 しかし、ほとんどの古くからある暗号は最近のコンピュータによって簡単に解読できることがわかり、近年、コンピュータによっても簡単に解読されない様々な方法が考案されてきた。 そこで、古い暗号については他書で勉強してもらうことにし、近年の暗号についてのみ話をしよう。

1977年にData Encryption Standard(DES)がアメリカ政府により発表され、しばらく国際標準として使われていたが、 1997年から1999年にかけて解読が試みられ22時間程度で破られたために米国立標準技術研究所(NIST)によって新規暗号方法が公募され、 新たな暗号システムRijndael（ラインダール）がAdvanced Encryption Standard (AES)としてNISTにより2000年10月に採択、2001年11月に一般公表、 2002年5月米国政府の標準として有効になった。AESは「高等暗号化標準」とでも訳せるが、通称AESであり、米国政府が認定した暗号化の先進的方法論である。

現在、AESが国際標準として一般的に使われ、DESは非推奨となっている。 また、AESはいくつかのプログラム上のバグを突いた攻撃に会ってきたが、根本的な解読はいまだに成功していないらしい。

しかし、破られないと思われていたDESが解読された事実を鑑みると、 将来においてAESが制限時間内（恐らく数年程度の時間内に企業秘密の暗号が解読されるとしたら問題だが、 数十年から数百年後に解読されても既に情報が陳腐化して無価値となっているだろうという意味での制限時間内）に破られないという保証はない。

今のところ、AESが制限時間内に破られたという報告はなく、あと十数年は大丈夫だろうという考えのもとに、一般的に利用されている。 しかし、常に最新の情報を収集し、AESに取って代わるものが発表されれば、すぐに対応することが重要であろう。

1.1.1 鍵配送問題

共通キー暗号の欠点は、どうやって共通キーを秘密裡に関連する人同士で共有するのかが最大の難点となっている。 共通キーを信頼できる他に送信する場合、ネット上で通信を傍受されると、そこでもう暗号は破られてしまい、暗号の意味をなさないことになる。

別の暗号方式で暗号化し共通キーを送信しても、別の暗号方式の共通キーを送信する必要が発生し、そこで傍受されれば同じことになる。

USBメモリーに共通キーを保存し、直接手渡しや郵送の手段を取るしかなくなるが、 コンピュータを介さない手間が発生し煩雑になることと、必ずしも秘密が厳守されるとは限らないという新たな問題に直面する。

そこで登場するのが公開キー暗号である。

(DESやAESの詳しい解説はここでは割愛するが、後述する予定。)

1.2 公開キー暗号

公開キー暗号はRSA暗号に代表され、公開キーと秘密キーの2つのキーで暗号化と復号化を行うものである。 近年は、暗号キーのビット数が少なくて済むということで、楕円暗号方式に主流が移りつつあるが、 まず、RSA暗号の基礎を学習することにしよう。

1.2.1 RSA暗号の基礎

1977年に発案され、発案者3人の名前の頭文字からRSA暗号と呼ばれる。

RSA暗号は、巨大な2つの素数 $p$ と $q$ の積 $n$ の素因数分解が非常に困難であることを根拠としている。 コンピュータで計算して数百年以上の処理時間がかかるだろうという前提であったが、 最近の様々な新しい計算手法の登場とともに、1000ビット程度の素因数分解は比較的短時間に処理できることがわかり、 1000ビット以上の素数つまり2000ビット以上のRSAキー $n$ を使うことが推奨されている。

公開キーは、組み {$e,n$} であり、$e$ は $(p-1)(q-1)$ と互いに素な任意の正の整数である。
秘密キーは、 $p$ と $q$ および $ed \mod (p-1)(q-1)=1$ となる正の整数 $d$ である。

暗号化は、 $x$ を平文とし、 $y$ を暗号文とすると、

$$ y=x^e \mod n \tag{1.1} $$

で暗号化され、

$$ x=y^d \mod n \tag{1.2} $$

で復号される。

$p,q$ および $d$ は秘密であり、 $d$ は $p,q$ がわからない限り求めることができないとされている。

AさんがBさんに暗号文を送ることを考える。

  1. BさんはRSA暗号の公開キー {$e,n$} と秘密キー $d$ を作成し、公開キーをAさんに教えた。
  2. Bさんの公開キー {$e,n$} を使って、Aさんは式(1.1)で作成した暗号文 $y$ をBさんに送った。
  3. BさんはAさんから貰った暗号文 $y$ を式(1.2)で復号し、平文 $x$ を得、BさんはAさんの秘密の内容を知ることができた。
  4. Cさんはネット上でやり取りするAさんとBさんの通信を傍受していた。
  5. CさんはBさんの公開キー {$e,n$} とAさんが送った暗号文 $y$ を入手することに成功した。
  6. Cさんは復号するための $d$ がわからないため、すぐに暗号文を解読できなかった。
  7. Cさんは $n$ の素因数分解プログラムをスーパーコンピュータを使って実行したが、数十年たっても計算が終わらなかった。
  8. Cさんは数十年も前のAさんからBさん宛ての暗号文が既に陳腐化した情報であることを知り、莫大な費用を投じてしまったことを悔やんだ。

ということで、暗号を解読できないわけではないが、解読に膨大な時間がかかることで情報が陳腐化し、 秘密情報を盗まれた者は大した損害もなく、盗んだ者は解読するのに膨大な費用をかけた割には得しないという結末になるということで、 重要な秘密情報を時間というファクターで保護することができる。

このRSA暗号を使って暗号化する手順は、巨大整数のべき乗計算と剰余を求める問題であり、 様々な効率の良い計算法を使ってもいくらか骨の折れる計算となる。 そこで登場するのが、より高速で処理できる1.1で紹介した共通キー暗号であり、 共通キーをRSA暗号で暗号化して送ることにより鍵配送問題は解決する。

しかしながら、実のところ、暗号化しないでも簡単に鍵配送問題を解決する方法として、RSA発表の1年前に公表された ディフィー・ヘルマン鍵交換法（Diffie–Hellman key exchange、DH法）と呼ばれる方法があり、現在においても幅広く活用されている。

[文字単位の暗号化について]

様々なところでRSAの解説がなされているが、文字単位で変換して解説してあるものが多い。 しかし、現実には文字単位の変換がなされるRSAプログラムは存在せず、大きな文字セットを一つの塊として変換する。

なぜなら、文字単位の変換による暗号化は簡単に破ることができ、暗号としては全く意味を持たないからである。 （公開キー暗号の場合の宿命で、公開キーを使って、各文字コードに対応する変換テーブルを普通の低レベルのPCを使ってもほんのわずかな時間で作成でき、復号のための秘密キーを知らなくても、そのテーブルを逆にたどれば暗号解読がほぼ瞬時に成功する。 それゆえ、解説書では1文字づつRSA変換する様子を示しながら解説するが、現実の暗号化で1文字づつの変換は行なわない。）

しかし、多くの解説書でそのことが明記されていないものが多いので、誤解している人も多いに違いない。 かく言う私も一時期誤解していた。

平文 $x$ のサイズは十分に大きくなければならず（おそらく $n$ と同程度か少し小さいぐらい）、サイズが不足している場合、パディングという手法で不足分を埋め、変換することを行なう。

1.2.2 ディフィー・ヘルマン鍵交換法（DH法）

1976年に、Whitfield Diffie氏とMartin E. Hellman氏によって考案され、初めて公開キー暗号という新しい概念が導入された。

この方法は、暗号化とは異なるものであるが、他人に知られることなく秘密キーを共有できるものであり、 離散対数問題と呼ばれることに準拠したもので、巨大な素数を扱うことにより解読困難と言われている。

アリスとボブが互いに鍵の交換をすることを考える。
まず、値の大きな素数 $p$ と その生成元 $g$ をアリスとボブどちらでもよいが公開する。 （生成元については後述。 $1 \lt g \lt p$ となる整数であるが、 $g=2$ とする場合が多いらしい。）

  1. アリスは秘密の数 $a$ を適当に乱数で決める。（ $1 \lt a \lt p-1$ かつ $g^a \gt p$ ）
  2. ボブは秘密の数 $b$ を適当に乱数で決める。（ $1 \lt b \lt p-1$ かつ $g^b \gt p$ ）
  3. アリスは $A=g^a \mod p$ を計算してボブに送信する。
  4. ボブは $B=g^b \mod p$ を計算してアリスに送信する。
  5. アリスは $K_A=B^a \mod p$ を計算する。
  6. ボブは $K_B=A^b \mod p$ を計算する。

さて、

$$ K_A=B^a \mod p=g^{ab} \mod p=K_B $$

が成立するので、アリスとボブは共通キー $K=K_A=K_B$ を入手できたことになる。

さて、ここで第3の登場人物イブが悪意をもって通信を盗聴していた。
イブが入手できたのは、 $p,g,A,B$ の4つである。 この4つのパラメータから共通キー $K$ を求めることができるのだろうか？

まず、 $A=g^a \mod p$ で $A,g,p$ は既知であるから、この式から $a$ を求めるのであるが、 実はこの問題は「離散対数問題」と呼ばれる超難問なのである。簡単に求める方法はまだ発見されていない。

しかし、近年の計算理論の進化に伴い、DH法の弱点を突く攻撃法が数多く存在するため、 楕円曲線を使ったElliptic Curve Diffie-Hellman法（ECDH）などが推奨されつつある。

DH法の欠点としてよく知られる「中間者攻撃」というものもあり、使用に際しては注意を要する。

1.2.3 生成元

表1.1　 $g^a \mod p \quad (p=11)$ の表
$g \diagdown a$12345678910
11111111111
224851097361
33954139541
44593145931
55349153491
66 3 7 9 10 5 8 4 2 1
77 5 2 3 10 4 6 9 8 1
88 9 6 4 10 3 2 5 7 1
99 4 3 5 1 9 4 3 5 1
1010 1 10 1 10 1 10 1 10 1

上の表は素数11を法とする、 $g$ のべき乗の剰余計算を行なったものである。 $g=2,6,7,8$ のとき、 $1 \sim 10$ の全ての数が一回ずつ出現する。このような挙動を示す数のことを生成元という。

素数によって生成元は異なるが、多くの素数で2を生成元とするものが多いので、 $g=2$ とするDH法の採用が多いらしい。 もちろん、生成元2を持たない素数も存在するので注意が必要である。

1.2.4 剰余（mod）の数学

前節で剰余のべき乗の計算が登場した。より理解を深めるため、少しだけ数学的な話をしておくことにする。

割り算の余りを求めることを剰余（mod）と言い、整数 $x$ を整数 $y$ で割った商を $z$ 、余りを $r$ とすると、

\begin{eqnarray} r & = & x \mod y \tag{1.3} \\ x & = & yz + r \tag{1.4} \end{eqnarray}

と書ける。ここで、

\begin{eqnarray} r' & = & x' \mod y \tag{1.5} \\ x' & = & yz' + r' \tag{1.6} \end{eqnarray}

とすると、

\begin{eqnarray} x \pm x' & = & y(z \pm z')+(r \pm r') \tag{1.7}\\ xx' & = & y[yzz'+r'z +rz']+rr' \tag{1.8} \end{eqnarray}

なので、

\begin{eqnarray} (x \pm x') \mod y & = & (r \pm r') \mod y \tag{1.9}\\ xx' \mod y & = & rr' \mod y \tag{1.10} \end{eqnarray}

が導かれ、加算と乗算の法則が成り立つ。

少し、見にくくなったので、合同式を使うことにしよう。

$$ x \equiv r \quad ( \; {\rm mod} \; y \; ) \\ $$

この式は、 $y$ で割った余りが等しいとき、 $x$ と $r$ は法 $y$ について合同（congruence）であると言うことを示している。

\begin{eqnarray} x & \equiv & r \quad ( \; {\rm mod} \; y \; ) \notag\\ x' & \equiv & r' \quad ( \; {\rm mod} \; y \; ) \notag \end{eqnarray}

が成り立つとき、

\begin{eqnarray} x \pm x' & \equiv & r \pm r' \quad ( \; {\rm mod} \; y \; ) \tag{1.11}\\ xx' & \equiv & rr' \quad ( \; {\rm mod} \; y \; ) \tag{1.12} \end{eqnarray}

が成立する。割り算に関しては、少し難しい問題があるので、後述する予定。

ところで、任意の正の整数 $n$ に対し、

$$ x^n \equiv r^n\quad ( \; {\rm mod} \; y \; ) \tag{1.13} $$

も成立することが簡単に導ける。

よって、このことから、1.2.2の $K_A=B^a \mod p$ の計算は、

\begin{eqnarray} B & \equiv & g^b \quad ( \; {\rm mod} \; p \; ) \notag\\ K_A & \equiv & B^a \quad ( \; {\rm mod} \; p \; ) \notag\\ & \equiv & (g^b)^a \quad ( \; {\rm mod} \; p \; ) \notag\\ & \equiv & g^{ab} \quad ( \; {\rm mod} \; p \; ) \notag\\ & \equiv & K_B \quad ( \; {\rm mod} \; p \; ) \notag \end{eqnarray}

よって、

$$ K_A = K_B \notag $$

と簡単に証明できる。

減算の意味

(1.7,9,11)式で $-$ 記号が出てきたが、負の整数をどう取り扱うべきかここで議論しておこうと思う。

$x-x' \equiv 0 \quad ( \; {\rm mod} \; y \; )$ のとき、

$$ x-x' = ym $$

と書け、任意の整数 $m$ で $y$ の整数倍であることを意味する。また、 $z=-x'$ とすると、

$$ x+z = ym $$

よって、

$$ z = ym -x $$

と書ける。よって、 $m=0$ のとき、 $z = -x $ となるが、 $m=1$ の場合、 $z=y-x$ となる。

つまり、

$$ -1 \equiv y-1 \quad ( \; {\rm mod} \; y \; ) $$

負数に対して、法 $y$ の整数倍を足すことで等価な正の整数に変換できるため、減算して負になってかまわないことになる。

もう少しだけ突っ込んだ解説は、合同式と基本定理.pdfに記述した。



作成日: 更新日:


back    next