『暗号のおはなし』：第3章まとめ

2012-09-26   treby   技術メモ   このエントリーをはてなブックマークに追加

Amazon.co.jp：暗号のおはなし―情報セキュリティの基盤 (おはなし科学・技術シリーズ)

  1. 第1章　暗号とは
  2. 第2章　DESからAESへ
  3. 第3章　鍵配送方式と公開鍵暗号
  4. 第4章　デジタル署名と認証方式
  5. 第5章　ネットワーク暗号に向けて
  6. 第6章　暗号のひろがり
  7. 第7章　ヒューマンクリプト

本記事では第3章の要約を載せる。なお、記事中の図はすべて本書より引用した。

古典的鍵配送方式

AliceからBobへのメッセージは通常、複数のノードを通って伝えられる。ノード数がnならばn+1本のリンクを通る。ここで、暗号の使い方は以下の二通りが考えられる。

  • リンク暗号……リンクごとに暗号化・復号をする方式。中継局（ノード）で平文が現れるという問題がある。
  • エンド-エンド暗号……AとBの秘密鍵K_ABで暗号化し、AからBに届くまでの間ずっと暗号化されたままの方式。

今後は、エンド-エンド暗号を考える。

秘密鍵を用いた暗号を使う上で大事なのは鍵配送方式である。これの最も古典的な考え方は鍵管理センターをもうけてそこに鍵の配送を依頼する方法である。

鍵管理センターとネットワークの書くユーザの間ではネットワーク加入時などに予め個別に秘密鍵を共有する。こうすることで鍵管理センターとユーザの間に安全な通信路を確保できる。ユーザ間で秘密鍵を共有する場合、鍵管理センター経由で共有すればよい。

この方式の問題点は、ユーザ数が多いと秘密鍵の管理が大変になることである。よって、小規模なネットワークでは適用可能であるが、インターネットのような莫大な数のユーザがいるケースでは適用しづらい。

公開鍵暗号方式

公開鍵暗号方式（非対称暗号方式）……暗号化鍵を公開する方式。1976年にディフィとヘルマンにより初めて公表された。暗号化鍵と復号鍵が異なり、しかも暗号化鍵から復号鍵を求めるのが困難ならば、暗号化鍵は公開することができる。なお、公開鍵暗号方式に対してDESなどのように暗号化鍵と復号鍵が同じものを共通鍵暗号方式（対称鍵暗号方式）という。

公開鍵暗号通信システム

耐タンパー装置を用いたIDに基づく暗号方式

IDに基づく暗号方式……名前（ユーザID）そのものを公開鍵のように使える暗号方式。「郵便受けに名前が書いてあるような」場合がこれにあたる。誰でもマンションなどの郵便受けに封書を入れることはできるが、取り出せるのは部屋の主のみである。これも一種の公開鍵暗号方式といえる。

耐タンパー装置……不正に情報を読み出したり、書き換えたりするのが難しい装置。

耐タンパー装置を用いるID暗号方式

  • K_0 …… システム全体に共通の秘密鍵。これが漏れるとシステムが破綻する。
  • K_A …… 所有者の秘密鍵。ユーザIDをK_oで暗号化することで生成する。

ただし、この方式も同じユーザ間の場合、いつも同じ秘密鍵を利用して通信することとなりセキュリティ上好ましくない。そこで各暗号通信のはじめにランダムに選んだ秘密鍵K_wを送り、その後の通信をK_wで行うといった対策がなされる。

RSA暗号

耐タンパー装置が破られても被害が全体には及ばない公開鍵暗号方式には数学的手法を用いた方式がある。

RSA暗号 …… 1977にリベスト(R.L.Rivest)、シャミア(A.Shamir)、エードルマン(L.Adleman)によって発明された数学的手法を用いた公開鍵暗号方式。

一方向性関数 …… 平文Mから暗号文C=f(M)を計算するのが簡単で、逆にCからM=f^-1(C)を計算するのが非常に難しい関数。数学的手法を用いた公開鍵暗号方式に用いられる。

BobからAliceへのRSA暗号通信の手順

  1. Aliceは10進数155桁(512ビット)程度の二つの素数p_Aとq_Aをランダムに選び、その積n_A = p_A * q_A を計算する。
  2. k_A = LCM(p_A – 1, q_A – 1)を計算し、k_Aと最大公約数が1となる正整数e_Aを一つ選び、e_Aとn_Aの組(e_A, n_A)を公開鍵ファイルにAliceの公開鍵として登録する。
  3. [e_A * d_A] mod k_A = 1となるd_Aを計算し、これを秘密鍵として秘密に保管する。
  4. Bobは公開鍵ファイルからAliceの公開鍵(e_A, n_A)を調べる。
  5. Bobは平文Mを0以上n_A – 1以下の整数で表し、それをe_A乗し、n_Aで割った余りC=[M^(e_A)] mod n_Aを計算し、それを暗号文としてAliceに送る。
  6. Aliceは受け取った暗号文Cをd_A乗し、n_Aで割った余り[C^(d_A)] mod n_A を計算して復号を行う。

RSA暗号の安全性は巨大な合成数の素因数分解が難しいところに依存している。なお、RSA暗号の処理にはAESの100〜1000倍の時間がかかる。

DH鍵共有方式とエルガマル暗号

エルガマル暗号 …… ディフィ・ヘルマンの鍵共有方式(DH鍵共有方式)を利用した公開鍵暗号。DH鍵共有方式では離散対数問題の難しさを利用している。