ノート:バーナム暗号

バーナム暗号の安全性について

ワンタイムパッドの記述：

> 特記事項

>

> バーナム暗号とは違います

バーナム暗号の記述：

> 特記事項

>

> ワンタイムパッドと違い、絶対的安全性はありません

上記の記述は正しいのでしょうか？ one time pad は Vernam cipher とも言うことが多いと思います（英語版のOne-time padの説明）が、両者の安全性は違うものでしょうか？ Sina 2004年9月19日 (日) 01:56 (UTC)[返信]

one time padとは特別な運用法を前提にした鍵の記録メディアで、Vernam cipherは暗号システムですから両者は同列に比較できません。 Vernam cipherで(テープ状の)one time padを使う事も、使わない事も自由です。手持ちのテキスト(ISBN 0-89412-076-X)にある用語集を参考に引用します。one time padとは単に鍵を一回しか使わない事では無く、正当な受信者であっても再使用できないように鍵を即破棄する事です。例としてCD-Rに乱数を記録した物をone time padとして使用した場合、半分使った時点で敵に盗まれては普通の乱数表と同じですよね？Tuve74 2004年12月20日 (月) 13:59 (UTC)[返信]

one-time pad

A form of key book used in a one-time system, so designed as to permit the destruction of each page of key as soon as it has been used.

Vernam system

A cipher teleprinter system employing a prepared tape of random teleprinter characters used to key another tape containing the plain text to be encrypted.

--以上の署名のないコメントは、Tuve74（会話・投稿記録）さんが 2004年12月20日 (月) 13:59 (UTC) に投稿したものです（Æskja（会話）による付記）。[返信]

元の疑問を出したSinaです。ご意見ありがとうございます。

物としては、one time padは記録メディアであり、Vernam cipherは暗号タイプライタであるので、違うものである。
one time padは単に乱数表ではなく、使用した部分をすぐ破棄できるような作りになっていて一度しか使用しないことを意図したものだけども、Vernam cipherは鍵テープを一度しか使用しないとは限らないものである。

というように読みました。

「one time pad」という言葉は、暗号方式ではなくて記録メディアを指すのか？（「Vernam cipherはone time padか否か」ではなく「Vernam cipherの鍵テープはone time padか否か」とすべきなのか？）、「one time pad」という言葉の語源はどこ？
Vernam cipherの鍵テープは、どう扱うことを想定したものだったか？Vernam cipherでは「鍵テープは繰り返し使用しないこと」が望ましいことだとは意図されていなかったか？

の２点がポイントのように思いました。というのは、

英語版のone time padの歴史の節によると、最初のone time padは、Vernam cipher(one time tape system)で、2番目がpaper pad systemである(1923年頃に独国で採用) 、としている。Vernamの出願に US PAT.1310719 (1919年)があり、その後、Mauborgneがmid-1920sに出願しているらしい。VernamやMauborgneは、one time padという言葉は用いていない。
現代暗号的には「Vernam cipherは、ストリーム暗号の一種で、鍵が偏りのない乱数で作成されていて、鍵を一度しか使用しなければ、one time padとなる」と説明されている。

なので、one time padは、記録メディア(paper pad？)とは限らないかも知れない、Vernam cipherの鍵テープは再使用しないものかもしれない、ようにも思えるためです。Sina 2004年12月23日 (木) 00:22 (UTC)[返信]

one-time padはVernam cipherで使用しても良いし、enciphered codeで使用しても良いのです。ですから「Vernam cipherは、ストリーム暗号の一種で、鍵が偏りのない乱数で作成されていて、鍵を一度しか使用しなければ、one time systemにもなる」と記せば良いと思います。とは言っても専門用語の用法や意義は多数決で決まる事がありますし、私個人は現代（民生）暗号は専門外ですからノートの方にコメントしました。まずはSinaさんが具体的な用法まで踏み込んで加筆されては如何でしょうか？　Tuve74 2004年12月23日 (木) 10:09 (UTC)[返信]

「one time pad」は、記録メディア(paper pad)とは限りませんし、紙でも何でも良いのです完全な乱数コードと鍵（あるいは鍵を生成するもの）の対をさします。Vernam cipherの鍵テープも一度使用したものは再使用し無いほうが安全です（オペレーション毎に生成し廃棄されると聞きますが、このオペレーションが何を指すかは不明です）。例えば、ホワイトノイズから取り出した信号をDVDやCDなどに記録しこれを乱数とします。これを複製し2人あるいは複数人がもっていて、文を乱数で処理します。文の長さ以上の乱数であれば、情報論理的安全性がありますので暗号として使えることになります。ただ、秘密鍵でも言われるのは乱数の生成や鍵生成に問題があれば、話は別です。--Kikukikukikukikukiku 2007年10月27日 (土) 13:25 (UTC)[返信]

こんにちは。one time padやVernam cipherの項を見て加筆/修正したいと思い少し加筆しましたが、事実を確認するのは難しくて、特記事項の部分についてはノートで質問するにとまってます。用語としての整合性や歴史的起源が分かってきたら、また編集したいと思っています。・・・以下、余談的ですが、one time padを適当なブロック暗号の鍵として使用してよいとすると「one time padは理論的に解読不可能（=情報理論的安全性がある）」とは言えなくなると思います。逆に理論的安全性を求めてone time pad（という言葉）が生まれたとすると、one time padは何に使ってもよいものではなくて、Vernam cipherのようなタイプの暗号方式のみに使うものではないかと思えるので、one time padの用法ってよく分からないと感じています。Sina 2004年12月26日 (日) 13:48 (UTC)[返信]

「one time padを適当なブロック暗号の鍵として使用してよい」わけではありません。

この「適当なブロック暗号の鍵として使用」と言うのは（当然のように）複数のブロックに対して同じ鍵が使われる状況を指しているものと考えます。それはワンタイムパッドではありません。

時折「ヴァーナム暗号が唯一の完全暗号（解読不能な暗号）」と言われることがありますが、平文と鍵をXORすることが解読不能足らしめているのではありません。解読不能なのは、平文と同じ長さの鍵（＝真の乱数）を用い且つ其の鍵が二度と用いられない場合に限るのです。そしてそれが「ワンタイムパッド」であり、解読不能と言われる根拠なのです。

一般にブロック暗号は、平文を特定長のブロックに分割し、分割された各ブロックを同じ鍵で暗号化します。当然それは、ワンタイムパッドでは有り得ないのです。

逆に言えば、ブロック暗号であっても分割された各ブロックを毎回違う鍵（＝真の乱数）で暗号化し且つその鍵を二度と用いないのならば、それはワンタイムパッドとなります。そして其の場合には「one time padは理論的に解読不可能（=情報理論的安全性がある）」と言えます。例えば、平文を64bit毎に区切り、それぞれを毎回違う鍵（＝真の乱数）を使ってDESで暗号化した場合です。ただ、それは情報理論的にはヴァーナム暗号（平文を鍵とXORしたもの）と完全に等価であり、何らの優位性を持ちません。

無駄にわざわざ計算量の多いDESを使う必要が無いから、計算量の少ないシンプルなヴァーナム暗号なだけです。そしてワンタイムパッドの概念が無かった当時だからこそ、ヴァーナム暗号に意味があったわけです。なにしろワンタイムパッドでないヴァーナム暗号は事実上、ヴィジュネル暗号と同じなわけですからね。

世界最狂の魔法使いＣray-Ｇ 2008年4月22日 (火) 00:42 (UTC)[返信]

余談にお付き合い下さりありがとうございます。完全暗号であるための条件については、ご説明の通りだと思いますし、ブロック暗号で平文長＞鍵長となる平文を暗号化した場合（同じ鍵で複数ブロックを暗号化した場合など）には情報理論的には安全性ではないのもご指摘の通りだと思います。ただ、DESの場合、ブロック長が64bitで鍵長は56bitですので、たとえ１ブロック毎に違う鍵を使ったとしても平文長＞鍵長という条件は満たされないように思います。また、仮にブロック長64bitで鍵長も64bitのブロック暗号であっても、任意の平文64bitについて、鍵64bitが異なると必ず異なる暗号文64bitが対応することが証明されないと情報理論的に安全性とは言えないようにも思います。ブロック暗号でこのような性質が証明されたものってあるのでしょうか？あるいは証明されてなくてもone time pad的な用法であるので、one time pad といってよいのでしょうか？ one time padの用法について感じた疑問はこのような内容のものでした。が余談なのでこの辺でクローズを。Sina 2008年6月21日 (土) 09:22 (UTC)[返信]

Q1)DESの場合、ブロック長が64bitで鍵長は56bitですので、たとえ１ブロック毎に違う鍵を使ったとしても平文長＞鍵長という条件は満たされないように思います。

A1)はい、満たされていません。なので、何をどうやってもDESを用いる限り完全暗号にはなり得ません。

これは、総当りで鍵を試して復号化した平文の中に含まれない文が存在し得る為、少なくとも平文はそれ以外の文であることがわかるからです。例えば全ての鍵候補を総当りで試した中に「ニイタカヤマノボレ」という復号結果が存在しなければ、平文が「ニイタカヤマノボレ」ではないことがわかります。

このことから、先の私の投稿における「それぞれを毎回違う鍵（＝真の乱数）を使ってDESで暗号化した場合」というのは不適切な例です。（DESの鍵長が平文より短いことを失念していました）

Q2)任意の平文64bitについて、鍵64bitが異なると必ず異なる暗号文64bitが対応することが証明されないと情報理論的に安全性とは言えないようにも思います。

A2)はい、その通りです。

これはA1と同様、ある暗号文に対して「あり得ない平文」を得ることを可能たらしめます。重複の量だけ実質的な鍵長が減ることになります。平文空間に対して暗号文空間が半分の場合、鍵のビット数が1少ないのと同じ安全性となります。DESの場合は鍵空間が56ビットなので（重複が無ければ）平文空間64ビットに対して暗号文空間は56bitになります。例え鍵を8文字==8バイト==64ビット与えたとしても（そのうち8ビットは使われないので）256個==8ビットの重複があり暗号文空間は8ビット減って56ビットです。これが実質的な鍵長となります。単なる衝突程度の頻度なら実質鍵長が減るのは1ビット未満になりますが、減っていることは確かです。

Q3)ブロック暗号でこのような性質が証明されたものってあるのでしょうか？

A3)実用的に用いられている中では無いと思います。

証明する為には、平文と鍵と暗号文との間に存在する数学的な関連性に基づいて証明することになります。それがわかっているなら解読が容易になり、その分安全性が低下します。例えばRSA暗号はその関連性がわかっているので安全性が疑問視されています。逆算する方法がわかっていない為にあまり問題視されていませんが。

おっと、もう一つ方法がありましたね。全ての平文と全ての鍵の組み合わせに関して重複が存在しないことを確認すれば証明出来ます。が、それは暗号として無価値です。

Q4)あるいは証明されてなくてもone time pad的な用法であるので、one time pad といってよいのでしょうか？

A4)論文や議論等で用いるのでなければ one time pad と言って差し支えないと考えられます。或いはワンタイムパスワードという言い方もあります。

詳細は本頁に譲りますが、鍵の配送コスト問題から一般的に真の one time pad を用いることはありません。なので one time pad という語が用いられる場合、高い確率で真の one time pad であることが要求されているわけではありません。実用上は、毎回違う鍵を使っているだけの普通のブロック暗号程度の強度で充分な場合がほとんどです。大抵は、興味本位で鍵を盗んで悪さしてやろうという意欲を挫くことが出来れば充分ですので。

もしもそれでは不充分な場合には、DESはもちろんRSA暗号やRC4のような安全性の低い暗号を用いるべきではないはずです。

以上で疑問は解消されたものと思います。

世界最狂の魔法使いＣray-Ｇ 2008年12月12日 (金) 17:18 (UTC)[返信]

著作権に関するお伺い

Sinaと申します。116.80.70.214のアドレスにて下記の編集された方に、お伺いしたいことがあります。

2008年6月20日 (金) 17:29 116.80.70.214 (会話) （5,840 バイト） (バーナム暗号について記載。特記事項の間違いを削除。) (取り消し)

かなりの分量の加筆により記事が充実して大変よいことだと思いますが、116.80.70.214のアドレスを使われている方は、記事中でURLが埋め込まれている「PCR2」の解説ページ[1]の著作権者と同じ人（つまり自分の著作物をWikipedia:自著作物の持ち込みにしたがって問題が無いように書き直されたもの）なのでしょうか。加筆された文章は、このPCR2の解説ページと、その内容・構成がほぼ一致しているので、第三者が行ったのだとしたら著作権違反になっていないかと心配で、この版に加筆推敲することが躊躇われます。ざっと比較した限りでは（翻案だとすると）注意深く言い回しを置き換えられていてますが、ところどころ推敲漏れしているようにも見受けられます。Sina 2008年6月21日 (土) 08:45 (UTC)[返信]

【回答】お問い合わせありがとうございます。どちらも私の著作物または私の著作物を基にして書かれたものです。言い回し云々の件は、まことに申し訳ないことですが、正直のところその時々の気分で書いてますので、仰られるような面倒なものではありません。
リンクがPCR2だけである件については、実はもうひとつ興味を持っている技術があります。ただ、私自身での検証ができていないのでまだリンクを設けてありません。PCR2は私自身が検証済みの技術なのでリンクをはりました。
その技術は数式を無限に設定可能であることによってバーナム暗号を実現するものです。しかしながら、私自身も以前そのような方式を検討したことがあるのですが、私の能力ではどうやっても実質的に有限個の組み合わせしかできず、諦めたものです。今回は発表されているのが数学科の先生なのでとても興味深く推移を見ています。公表されている内容によれば数か月以内に特許を出願してからアルゴリズムを公開されるとのことなので、現在待ち状態です。
今日現在、私の興味を引く技術はその2者だけです。--以上の署名のないコメントは、116.80.70.214（会話/Whois）さんが 2008年6月22日 (日) 16:02 (UTC) に投稿したものです（Æskja（会話）による付記）。[返信]

IP:116.80.70.214（会話 / 投稿記録 / 記録 / Whois）さんの加筆箇所には出典がなく、独自研究のおそれもあったため、除去致しました。--Æskja（会話） 2016年7月16日 (土) 01:00 (UTC)[返信]

PCR2の紹介リンクの削除

記事の内容を充実させてもらった点に関しては大変喜ばしいことだと思いますし、セキュリティーに関して見落としがちな指摘もあり百科事典として大変有用なことだと考えます。

しかしながらPCR2の紹介ページを見たところ、優秀な擬似乱数発生アルゴリズムを用いているらしいことはわかりましたが、完全暗号になっているという説明になっていないように見受けられるのです。

ヴァーナム暗号は、平文と同じ長さの真の乱数とXORする暗号です。そして平文と同じ長さの真の乱数ではない場合には完全暗号ではありませんし、ヴァーナム暗号でもありません。例えば擬似乱数とXORする暗号ではRC4があります。もっとも、RC4には致命的な欠陥があるのでナンですが………

そして、擬似乱数では完全暗号にならない理由とは、擬似乱数が循環するからではなく、そして一様ではないからでもなく、擬似乱数の「不確定性」が種（シード）の「不確定性」でしかないからです。決して、乱数から種を推測出来るからではありません。もしも擬似乱数生成器の種が2048bits（RC4と同じ）だった場合、2048bitsの種を全て試行すれば、その中のどれかが平文であり、その中に含まれない全てが平文ではないことがわかります。

さらにその擬似乱数を暗号文に添付するとなれば、もう何をか云わんをや。擬似乱数を添付した時点で、擬似乱数の「不確定性」はゼロになります。その後にその擬似乱数を秘密鍵で何回加工しようとも、その「加工された擬似乱数」は、秘密鍵のビット数の総和の「不確定性」しか持ち得ません。

つまり、その擬似乱数がどれだけ優秀であろうとも、推測出来なかろうとも、周期性が無かろうとも、全く関係無く「秘密鍵のビット数」分の「不確定性」しかないわけです。

もしも万一「秘密鍵のビット数が長いから」というのであれば、それは計算量的安全であり、平文の長さが秘密鍵より長くなった時点で完全暗号ではなくなります。

完全暗号であるには、有り得る全ての秘密鍵（ヴァーナム暗号では平文と同じ長さの真の乱数列）を試行すると有り得る全ての平文が現れることが条件です。もしもそれが10バイトであるのなら、必ず「I love you」と「I hate you」と「I kill you」と、そして「Yes We Can」が、全て平文候補にあがることです。これら以外でも、10バイトで表される何かが一つでも平文候補に挙がらなかったなら、それは完全暗号ではありません。つまり完全秘匿性が無い、ということになります。※10バイト程度なら大抵は鍵長より短いので完全秘匿性が期待出来るわけですが（苦笑）

PCR2の発明者の誤解は、1バイトの不確定性と乱数列全体の不確定性とを混同していたことではないかと推測します。

以上のことから、PCR2は完全暗号ではなく、残念ながら百科事典（特にヴァーナム暗号の頁）に載せるべき暗号ではないものと思われます。

とりあえず削除しますが、出来るならPCR2の紹介リンクを貼った方にもご理解をいただきたいものと思います。反論なり納得いただけた旨なりの返信をいただければ幸いと存じます。

世界最狂の魔法使いＣray-Ｇ 2008年12月21日 (日) 08:37 (UTC)[返信]