kakke18’s blog

ゆるふわ学生エンジニア

最強の暗号?バーナム暗号

バーナム暗号とは

  • 秘密鍵を使い捨てで用いる共通鍵暗号

  • 1917年にVernamによって、考案

  • 1949年にShannonによって、理論的に解読不可能であることを証明

    → 最強の暗号?

アルゴリズム

バーナム暗号の暗号化、復号には、排他的論理和という演算が用いられています。

排他的論理和

排他的論理和とは、ビット演算といわれる0と1だけの世界での演算です。演算子は⊕と表されます。

a b a⊕b
0 0 1
0 1 0
1 0 0
1 1 1

例えば、a=1010 1010、b=1111 0000とすると、以下のようにa⊕bが計算されます。 f:id:kakke18:20190222014814p:plain

暗号化と復号

平文をm、暗号文をc、秘密鍵をkとします。

暗号化は以下のように定義されます。

c = m ⊕ k

また、復号は以下のように定義されます。

m = c ⊕ k

m = ”hello"、k = aa bb cc dd ee(16進数)として、暗号化、復号をします。

自然言語(普段使っている日本語や英語)をそのままビット演算することは出来ません。そこで、ASCIIコードと呼ばれる文字データを2進数に変換する対応表を用いて変換します。

  1. 平文をASCIIコードによって、16進数に変換

    m' = 68 65 6c 6c 6f

  2. m'とkで排他的論理和を演算

    c = m' ⊕ k = c2 de a0 b1 81

  3. 暗号文cを送信

  4. 暗号文cを受信

  5. cとkで排他的論理和を演算

    m' = c ⊕ k = 68 65 6c 6c 6f

  6. m'をASCIIコードによって、変換

    m = "hello"

1~3まではメッセージの送信側が、4~6まではメッセージの受信側が行う操作です。このようにして、暗号化した文章を送ることが出来ます。鍵であるk(aa bb cc dd ee)は、予め送信側と受信側で共有されている情報で、平文と同じ長さである(同じ長さに加工する)必要があります。

バーナム暗号の安全性

バーナム暗号は、解読不可能である。

「探索すべき鍵数が多くて現実的に解読できない」

→「すべての鍵候補の計算が可能である無限の能力を持つ攻撃者であっても、解読できない」

攻撃者は、暗号文を入手したと仮定します。攻撃者は、その暗号文と同じ長さの候補鍵を用意し、総当たりで暗号文と候補鍵との排他的論理和を取り、復号します。このとき、平文と一致しますが、攻撃者にとってそれが正しい平文であるかは判断が付きません

よって、バーナム暗号の場合、平文・暗号文・鍵という3つの情報のうち2つの情報が特定できなければ、残りの1つは特定できないということです。

バーナム暗号の死角

バーナム暗号は、最高の安全性を持ちますが、様々な課題があるため限定的な場面でしか使用されていません。

  • 鍵の配送

    バーナム暗号の秘密鍵は、平文と同じ長さ以上である必要があります。この鍵を安全に配送できるのであれば、わざわざ平文を暗号化せずともそのまま配送できます。

  • 鍵の同期

    暗号文の送信中に1ビットでも欠けてしまうと、それ以降の復号が正しく行われないため、送信側と受信側で完全に同期していなければなりません。

  • 鍵の生成

    バーナム暗号の秘密鍵はランダムなビット列でなければなりません(上の例では簡略化のためにランダムなビット列にしませんでしたが、これは悪い秘密鍵です)。つまり、長い秘密鍵を作るにはとても手間がかかります。

まとめ

バーナム暗号は、安全性は最強だが、効率性と利便性に欠けているので、あまり使用されていない。