バーナム暗号

テンプレート:出典の明記 バーナム暗号(Vernam cipher)とは、十分に長い乱数を鍵として、平文と鍵をXORすることで暗号文を作成する暗号方式である。ストリーム暗号の1つである。乱数が平文以上の長さである場合には、完全暗号　(暗号文を見ても平文を推測するヒントに全くならない)　となる。

概要

日本以外では、バーナム暗号は、Vernam's One-time Pad（バーナム使い捨て鍵方式あるいはバーナム使い捨て鍵暗号)と呼ばれ、暗号の世界では証明可能安全性を持つ完全秘匿暗号を指す。すなわち、攻撃者の計算能力に制限がないとしても解読不能の暗号であり、このことを無条件安全性という。決定性アルゴリズムからなる今日の一般的な計算量的完全である暗号方式とは異なり、非決定性アルゴリズムからなる。一般にストリーム暗号として解説されることが多いが、Shannon 49の条件定義にはそのような記述があることを知らない。また、ストリーム暗号でなければならない理由もない。

鍵をワンタイムパッドとして運用すれば、ワンタイムパッド暗号である。

その成立要件は単純な2つの式からなる。すなわち、

1. <math>H(\mathit{K}_i) \ge H(\mathit{M}_i)</math>
2. <math>\mathit{K}_i \ne \mathit{K}_{i+1}</math>

つまり、「暗号鍵が平文の不確定性を下回らない不確定性を有すること」及び「2つの異なる平文を1つの暗号鍵で暗号化しない」である。

これに従う限り、暗号化処理はXOR（EOR。排他的論理和）に限らず、より一般化された2を下回らない自然数を法とするベクトル和でも3を下回らない素数を法とする内積でも構わない。もっと言えば、行列の和や積でも構わない。従って、いずれの場合も、暗号化によってデータ量が増えるということはない。

このような暗号システムが今日まで実現しなかった最大の要因は、その成立要件にある。すなわち、バーナム暗号は共通鍵（対称鍵）方式の暗号化方式であり、成立要件の 2 に従えば暗号の度にユニークな暗号鍵が要求される。従ってバーナム暗号を使って暗号通信を行うには暗号通信の都度、新しい暗号鍵も相手に届けられなければならない。

ところが、成立要件の 1 に従えば、暗号鍵の方が平文及び暗号文よりもデータ長が長く、かつ不確定性が大きい訳であるから、もし、そのような暗号鍵が安全に配送できるのであれば、それと同じかそれよりも短い平文も安全に配送できるはずであることになり、暗号化そのものが否定されることになる。

これを「鍵の配送コスト問題」と呼ぶ。

ただし、暗号通信を前提とせず、自らのデータを秘匿保管するためだけの簡単なバーナム暗号は容易に作られる。すなわち、毎回異なる平文で別の平文をXORするなりベクトル和するなり内積するなりすれば良い。目立つが、鍵は真正ランダムビット列であっても良い。暗号化に用いられた鍵の情報が漏洩しない限りにおいて完全秘匿が成立する。しかしながら単純にこれだけでは保管時における暗号鍵と暗号文の関連付けによって後述する使い捨て公開鍵方式同様の重大な脆弱性を持つ。

これまでに不完全ながらバーナム暗号が実現した方式とされるのは使い捨て公開鍵方式と呼ばれる方式である。しかしながら、秘密鍵の配送に公開鍵方式を用いていることから鍵の配送時（つまり通信時）に脆弱性を持つ。更に暗号文保管時において秘密鍵と暗号文との関連付けが必要であることからデータベース等が必要となるが、そのデータベースを守るのはシステム管理者またはデータベース管理者とパスワードであることから、極めて脆弱である。8文字のパスワードのセキュリティは40 bit 程度しかなく、今日ではセキュリティとは言えない（今日の例えば 256 bit の不確定性を持つ鍵（計算量的完全）であっても、それを使うにはパスワードだけで良いことから、実質的に 40 bit の不確定性しかないことは同じである）。データに自由にアクセス可能なシステム管理者の存在は情報漏洩の可能性を否定しえず、やはりセキュリティとは言えないという問題を持つ。

これに対して、今日特に日本で研究が盛んな量子暗号はやはりバーナム暗号の一形態であり、理論的にはそれを実現するものであるが、第一に通信時にしか使えないという問題を持つ。つまり秘密情報の保管には使えない。第二に、通信に関しても、観測されるだけで通信が成立しなくなることから、高機密性と共に即時性を要求されるような暗号通信には使えないという問題を持つ。例えば軍事通信にこれを用いた場合、攻撃者は通信網を破壊することなく容易に通信を遮断することが可能である。しかしながら、それだけの高機密性を要求するのはそのような軍事とか外交においてである。第三に、そのインフラ整備に莫大な投資コストが掛かることが重大な問題であると考えられる。

完全な秘匿通信が可能ではあるもののあまりにも高額であり、かつあまりにも脆弱であることから、インターネットの基幹システムとして普及することはほぼ考えられない。専用線であれば可能かもしれないが、専用線を使うのであれば従来技術（メタルや光）でも十分であるという矛盾が起きる。

不確定性

不確定性は（情報理論的）エントロピーとも呼ばれ、確率の逆数を底を 2 とする対数で表した値で、単位はビットで表される。言い換えれば、「場合の数」をビットで測ったものであると言える。即ち、ある事象 x の発生により得られる情報量（つまり x が起こるかどうかという不確定性）であって、
<math>\log_2 (prob(x))^{-1}</math>
で表される。つまり{0,1}ⁿの平文あるいは真正ランダムビット列はlog₂2ⁿ=nビットの不確定性を持つ。

そこで、一般にxの含まれる確率空間をXとする時、不確定性(uncertainty)は
<math>H(\mathit{X}) = \sum_{x\in X} prob(x) \times \log_2 prob(x)^{-1}</math> となる。

例えば、上記のパスワードの不確定性は、8文字のパスワードで、パスワードで使用可能なキャラクタをアルファベット26文字と数字10文字とすれば、
log₂36⁸=41.3594 bit である。

Gilbert Sandford Vernam (1890 - 1960) と Joseph Mauborgne が発明した。1920年代に出願されている。 彼らは、ワンタイムパッドという名前は用いていないが、これがワンタイムパッドの発明であるとされることが多い。

Vernamの特許

• US Patent 1,310,719 Patented July 22,1919（出願は1918年9月13日）, GILBERT S. VERNAM, AMERICAN TELEPHONE AND TELEGRAPH COMPANY, "SECRET SIGNALING SYSTEM"テンプレート:Asbox