暗号化とは
通信の内容が、当事者以外には理解できないように、普通の文字･記号を一定の約束で他の記号に置き換えたもの。
| |
|
鍵 K |
→ |
鍵 K |
|
|
|
|
↓ |
|
↓ |
|
|
| 文書(平文) |
→ |
暗号器 |
→ |
復号器 |
→ |
文書(平文) |
なお、公開鍵暗号では、暗号化鍵と復号鍵が別になる。
暗号化
暗号化には、1文字単位で暗号化するものと、
文書を一定の長さのブロックに区切り、ブロックごとに暗号化するもの(ブロック暗号)がある。
1文字単位で暗号化するもの
- シーザ暗号：ジュリアスシーザが考案したとされる暗号。アルファベットを何文字分かシフトする。
何文字シフトするか、が鍵になる。
たとえば、IBM を １文字前にシフトすると HAL となる。なお、狭義シーザ暗号は、3文字後にシフトしたもの。
- シフト暗号：シーザ暗号を複雑にしたもの。アルファベットを数字に対応させ、平文と鍵の和を暗号文とする。
たとえば、IBM が平文で、鍵が NEC ならば、
- おのおのを A=1,B=2,…,Z=26 という対応により数字にする。
- 上の操作で IBM = 9 2 13 、NEC = 14 5 3 となるので、各桁を足して、(9+14) (2+5) (13+3)
より、23 7 16 が得られる。
- 23 7 16 をアルファベットに戻すと、WGP が得られる。これが暗号文。
- 換字暗号：アルファベットのすべての文字を別のアルファベットに対応させる。
シーザ暗号より複雑で破られにくそうだが、文字の出現確率自体をいじっていないので、
文字出現頻度からハッキングできる。
- ストリーム暗号：前もって鍵の系列を作成しておき、暗号化するたびに鍵を変えて行くもの。
防衛庁や、PHSなどに使われている。代表的な製品は RSA社の RC4。
ブロック暗号
- DES(Data Encryption Standard)：IBM が1977年に発表。暗号化したい文を一定長のブロックに分け、
鍵 K を用いて各ブロックを暗号化する。復号も同じ鍵 K を使う。
基本的なアルゴリズムは、ブロックを前後で2つに分け(L、Rとする)、以下の操作Aを繰り返す。
繰り返し回数を段数という。
操作A
- 鍵 K を用いて Rをシフトする。この結果を f(R,K) とかく。
- L と f(R,K) で XOR をとる。
- 2. でできたLと元のRを交換する。
いわゆるDES は段ごとに鍵を変えて、16段この操作を行なう。
復号は、暗号化とまったく逆の操作を行なえば良い。
また、DESの改良型、TDES(Triple DES) では、DES を3回行なう。
- FEAL32：NTTが1987年に発表。32 は、段数のこと。初期バージョンのFEAL4、FEAL8などは破られ、
結局32段にまでなってしまった。
- IDEA：Ascom Tech社が1987年に発表。PGP(Pretty Good Privacy)というフリーの暗号化ソフトに使われている。
- RC5：RSA社が1994年に発表。Netscape Navigator に使われている。
- GOST：旧ソ連が開発。詳細は未発表。近日中に発表される。基本アルゴリズムは DES と同様だが、
各段で使用する鍵の系列を複数持つ事により、DESよりも破られにくくなっている。
- その他：日本の各社がいろいろな暗号を発表している。
MULTI2(日立製作所)、Misty(三菱電機1989)、SXAL･MBAL(ローレルインテリジェントシステムズ)、ENCRIP(NEC)など。
暗号攻撃法
暗号の攻撃法には以下のものがある。
- 同じ鍵で暗号化された、いくつかの平文とその平文に対する暗号文が分かっているとき、鍵を解読する。
- 暗号文だけから平文を解読する。できれば鍵も解読する。
- 任意の平文に対してそれに対応する暗号文が入手できるとき、鍵を解読する。
- 任意の暗号文に対してそれに対応する平文が入手できるとき、鍵を解読する。
公開鍵暗号
公開鍵暗号は、暗号化鍵と復号鍵が異なるものである。したがって、相手に暗号化鍵を教える際に他人に漏れても、
直ちに暗号を解読されるという事態にはならない。
その意味で、対称鍵暗号より優れているが、スピードが遅いのが難点。
今日では、対称鍵暗号の鍵を相手に送るのに主に使われている。
基本的なアルゴリズムは以下の通り。(以下、私の勝手な解釈。)
ＡがＢに平文を暗号化して送るとする。
- まず、平文を W とする。
- Ｂは、一方向関数 f を用意する。
一方向関数とは、
全単射だが逆関数を f からだけでは事実上計算できない(計算に非常に時間がかかる)もの。
- Ｂは、f に対応する｢鍵｣ k を使って f と f の逆関数 g を前もって計算しておく。
ここで言う｢鍵｣とは、いわゆる暗号理論における鍵とは違った意味。
- f を公開鍵とし、Ａは f(W) を送信する。
- Ｂは、自分だけが知る秘密鍵 g を使って gf(W) = W を計算し、平文を得る。
ここで問題となるのは、送り手が誰かを受け取り側が確認できないこと。
だが、これは、以下のように電子署名をすることで解決できる。
- まず、平文を W とする。
- Ａは、一方向関数 F を用意し、Ｂは、一方向関数 f を用意する。
- Ａは、F に対応する｢鍵｣ K を使って F と F の逆関数 G を前もって計算しておく。
Ｂは、f に対応する｢鍵｣ k を使って f と f の逆関数 g を前もって計算しておく。
G は Ａだけが知っている秘密鍵、g は Ｂだけが知っている秘密鍵である。
なお、K と k は違うものなので、f から G を計算したり、F から g を計算したりはできない。
- F と f を公開する。
- Ａは、Ｂの公開鍵 f と、自分の秘密鍵 G を使って f(G(W)) を送信する。
- Ｂは、自分の秘密鍵 g とＡの公開鍵 F を使って Fg(f(G(W))= W を復元する。
第三者はg が分からないため、f(G(W))を傍受できても復元できない。
Ｂは G が分からないため、G(W) を偽造できない。
これで、送り手が誰かを確認できるようになった。
アルゴリズムは分かったが、ではそんなに都合の良い一方向関数があるか。
一方向関数
- 素因数分解を利用する。
有名なのが、RSA暗号
- 離散対数問題を利用する
- 有理数体上での楕円関数曲線を利用する
- ナップザック問題を利用する
主な公開鍵暗号
一方向関数として採用されているものを併記してある。
- Diffie-Hellman：離散対数問題を利用
- RSA：素因数分解を利用
- Rabin：素因数分解を利用
- Merkle-Hellman：ナップザック問題を利用
- ElGamal：離散対数問題を利用
- 楕円曲線：楕円曲線を利用
KPS(Key Predistribution System)
公開鍵自体の偽造などを防ぐため、公開鍵自体をどうやって送り手に送るかが問題になる。
KPSは公開鍵をe-mailアドレスなどを用いて、送り手が識別しやすく、偽造しにくくしたもの。
暗号化アルゴリズムを複雑にして、逆関数を求められないように工夫してある。
キーエスクロー
鍵を紛失、焼失した場合など、暗号を復号する手段がなくなるのを防ぐため、
というより、凶悪犯罪を政府機関が捜査するときの障害を取り除けるように、
秘密鍵も公開鍵も、どこかの機関が管理することを、政府は要求している。
鍵自体を保存するのではなく、鍵生成の種、アルゴリズムなどを別々の機関が保存、管理し、
いざというときは、それらの情報から鍵を生成できるようにしたもの。
エスクローという言葉のイメージが悪いので、キーリカバリーシステムとも言う。
表紙に戻る