バーナム暗号 - kisaragiのブログ

バーナム暗号とは

　バーナム暗号はバーナム(Vernam)さんによって考案された共通鍵暗号になります。この暗号はシャノンによって理論的に解読不可能であることが証明されており、高い秘匿性を備えています。

バーナム暗号の長所

　バーナム暗号の最大の長所といえばその安全性の高さだと思います。バーナム暗号がなぜ非常に高い安全性を持っているのか。また、解読不可能とはどういうことなのかは、暗号の仕組みを書いた後にまた書こうと思います。
　バーナム暗号には他にも処理速度が高速であるという長所もあります。これも仕組みをみていただければわかるのですが、とてもシンプルなため処理が高速に行えるようになっています。

バーナム暗号の短所

　バーナム暗号の短所は何と言っても鍵にあります。バーナム暗号は平文と同サイズの秘密鍵を用いらなければなりません。大きな平文をやり取りする場合をそれ相応の鍵が必要です。また、鍵もランダムなものでなくてはならないので、生成だけでも真性乱数を用いるとなるととても手間がかかります。さらに、バーナム暗号の秘密鍵は使い捨てになるので暗号化のたびに使用可能な秘密鍵が減っていくという短所があります。4ビットの平文をやり取りしたら16回しか暗号化が行えないということになります。
　短所はまだあって、鍵の配送も大きな問題となっています。共通鍵暗号なのであらかじめ相手と秘密鍵を共有しておかなければなりません。秘密鍵は他の人に知られてはいけないので安全に配送するにはどうするのかという問題点があります。そもそも秘密鍵が安全に配送できるなら平文を配送できるのではないか。というジレンマ？もあります。

バーナム暗号の仕組み

まず前提として平文をm、秘密鍵をkey、暗号文をcとしておきます。
仕組みは簡単でnビットの平文mとnビットの秘密鍵keyの排他的論理和をとるだけです。式は
c = m ⊕ key
となります。上記の式が暗号化になります。
復号は今度暗号文cと秘密鍵keyとのXORをとるだけです。式は
m = c ⊕ key
となります。

正当性の検証

排他的論理和の特性を活かした正当性の検証というものがあります。
これは同一の値のXORは0になるのを利用したものです。
例　1111 ⊕ 1111 = 0000　や　1010 ⊕ 1010 = 0000
正当性の検証の式としてはこんな感じになります。(暗号技術の全て参照）
Dec(key, Enc(key, m)) = Dec(key, m⊕key) = m ⊕ key ⊕ key = m ⊕ 0 = m
Decは復号、Encは暗号化を表しています。
Encは暗号化なのでm⊕keyとなります。DecはEncとkeyのXORなのでm⊕key⊕keyとなります。同一の値は0になるのでkeyとkeyは打ち消しあって０になります。０とのXORはそのまま値が出てくるのでmが残ります。

実践

実際に暗号化、復号、そして正当性の検証までを行いたいと思います。
問題：m = 1010, key = 0011とした場合の上記３つを求める。
まず暗号化

c = m ⊕ key 
c = 1010 ⊕ 0011
c = 1001

続いて復号

m = c ⊕ key
m = 1001 ⊕ 0011
m = 1010

元の平文に戻りました。
最後に正当性の検証

Dec(key, Enc(key, m)) = Dec(key, m ⊕ key) = Dec(key, 1001)
                                      = Dec(0011, 1001) = 0011 ⊕ 1001
                                  m = 1010

平文mに戻ったので正当性があるということになります。

バーナム暗号がなぜ安全なのか

　バーナム暗号はシャノンによって解読不可能ということが証明されていると冒頭に書きました。これは鍵を総当たりで調べることができない、というような計算的なものではありません。仮に鍵を全て総当たりで調べることができても解読できないということです。ポイントとしては、推測はできても解読はできないという点が挙げられます。
　攻撃者が総当たりで鍵候補と暗号文とのXORをとり復号しようとしてもそれが正しい平文なのか判断できません。これがバーナム暗号が安全であり解読不能であるという理由です。
どういうことかというと
例えば平文mが”A"という文字だった場合。AをASCIIコードでやり取りするとします。Aは0x41なので0100 0001bとなります。
これに対する秘密鍵の候補は同サイズのものなので範囲とすると
0000 0000 ~ 1111 1111になります。
これらの範囲でXORをとって暗号文cをいくら復号しようとしても結果はただ全ビット候補とのXORになりますので、AだけでなくBやCも結果として出てきます。結果、攻撃者は復号結果が正しいものか判断できないので解読不可能となります。
そしてここで先ほどの正当性の検証が少し出てきます。
正当性の検証にはkeyとmの二つの要素が出てきました。つまり平文が正しいか判断するには少なくとも秘密鍵keyを知っておく必要があります。しかし攻撃側は盗んだ暗号文しか知らないので正当性を検証できず攻撃失敗となります。
keyをいくら推測しても、そこから得られた結果は推測に過ぎないので、復号できたとは言えないのです。