バーナム暗号の意味と広く使われていない理由

基本的な暗号方式の1つであるバーナム暗号(Vernam cipher)について、意味と欠点(広く使われていない理由)を解説します。

バーナム暗号とは

例として、$A$ さんが $B$ さんに $3$ ビットのメッセージ $m=001$ を送ることを考えます。

準備:
事前に送りたいメッセージの長さと同じ長さの乱数列 $r$ を作成し、2人で共有しておきます。
例えば $r=011$ としましょう。

暗号化:
送信者 $A$ さんは、$m=001$ と $r=011$ の排他的論理和(各桁をそれぞれ足し算して、$2$ で割った余りにする演算)を計算します。この場合、結果は $c=010$ となります。

復号
受信者 $B$ さんは、$c=010$ と $r=011$ の排他的論理和を計算します。この場合、結果は $001$ となり、もとのメッセージ $m$ を得ることができました。

なぜうまくいくのか

$B$ さんは必ずもとのメッセージ $m$ を得ることができます。

なぜなら、排他的論理和を $\oplus$ と書くと、$m\oplus r\oplus r=m$ となるからです。
$A$ さんが $m\oplus r$ を送り、$B$ さんが $m\oplus r$ と $r$ の排他的論理和を計算するので、$m$ に戻ります。

攻撃者が暗号化されたメッセージ $c$ を盗み見ても、メッセージ $m$ の情報を得ることはできません。

$r$ が完全にランダムに生成されていれば、$c=m\oplus r$ も完全にランダムなメッセージになるため、$c$ から $m$ の情報を得ることはできません。

しかし、バーナム暗号には欠点があるため、実際には広く使われていません。

バーナム暗号の欠点1

バーナム暗号では事前の準備で、送りたいメッセージと同じ長さの乱数列 $r$ を共有する必要があります。

$100$ ビットの情報を暗号化して送りたい場合、事前に $100$ ビットの乱数列を共有しておく必要があります。これは大変です。このように「$r$ をどうやって共有するか」という問題が残ってしまいます。

バーナム暗号の欠点2

さらに、バーナム暗号ではメッセージを送るたびに別の乱数列 $r$ を使う必要があります。

もし「一回頑張って $r$ を共有すれば(同じ長さの)メッセージが何回でも送れる」という状況なら、バーナム暗号は嬉しいかもしれません。しかし、同じ $r$ でいろいろなメッセージを送ると暗号文からもとのメッセージの情報がバレてしまうおそれがあります。

例えば、$m_1$ と $m_2$ を同じ $r$ で暗号化すると、暗号文は
$m_1\oplus r$ と $m_2\oplus r$
となります。これらの排他的論理和を計算すると、$m_1\oplus m_2$ となり、暗号文から $m_1\oplus m_2$ が計算できます。

そして、実際のメッセージは一様分布ではなく、例えば「$000$ と $111$ がよく送信される」というように、分布が偏っています(「こんにちは」は送信されやすいけど「ここにちわ」は送信されにくい、みたいなイメージです)。上記の例の状況で例えば $m_1\oplus m_2$ が $111$ だとバレてしまうと「$m_1$ と $m_2$ の片方が $000$ でもう片方が $111$ だな」と推測されてしまいます。

このため、$r$ は $1$ 回使うたびに捨てて、もう一度別の乱数列を共有する必要があります(使い捨てパッド)。

次回は 仮数部、指数部、基数:意味と計算方法 を解説します。

スポンサーリンク

スポンサーリンク

学校では教えてくれない点数アップ5つの作戦
具体例で学ぶ数学の作成者が、数学の勉強法について徹底的にまとめました。

誤植がございましたら @mathwordsnet までご連絡をお願いいたします。
ページ上部へ戻る