ストリーム暗号のソースを表示

'''ストリーム暗号'''（ストリームあんごう、stream cipher）とは、平文を[[ビット]]単位や[[バイト (情報)|バイト]]単位で逐次[[暗号化]]する暗号である。平文を64ビットや128ビットなどの固定長のブロックに分割して暗号化する[[ブロック暗号]]に対比した語である。その構成上、入力が逐次追加されるデータであった場合、ブロック暗号は入力がブロックサイズに達するまで溜まらないと処理を進めることができないのに対し、ストリーム暗号はその必要がないのが特徴である。

== 概要 ==
ストリーム暗号は、鍵ストリーム（key stream）を生成する鍵ストリーム生成部と、鍵ストリームと平文を結合する結合部で構成される。典型的には、共通鍵方式において、ある鍵を初期値として[[擬似乱数]]列を生成し、[[平文]]との[[排他的論理和]] (XOR、<math>\oplus</math>) によって[[暗号文]]を作る。復号時には、同じ鍵（同じ初期値）から生成した擬似乱数列と暗号文との排他的論理和によって平文を得る。
:<math>(m \oplus k) \oplus k = m \oplus (k \oplus k) = m</math>

ストリーム暗号の多くは擬似乱数をデータに先行して生成できるので待ち時間が少ない。また、ブロック暗号では平文がブロックサイズの整数倍ではない場合にパディング処理が必要になるが、ストリーム暗号ではこれが不要であり、常に平文のサイズと暗号文のサイズが等しくなる。処理遅延が少ないことやデータサイズが増加しないことは通信などに利用する場合にメリットとなりうる。

[[暗号利用モード]]のOFB, CFB, CTRなどでブロック暗号を利用するとストリーム暗号を構成できるので、ストリーム暗号専用のアルゴリズムは、ブロック暗号と比べて何かしらの点で特長（メリット）がなければ開発する意味がない。たとえば、近年（[[Advanced Encryption Standard|AES]]の採択以降）はAESを利用する場合よりも高速であることをアピールすることが多い。

ソフトウェアでの、1ビットまたは1バイト単位で扱うというナイーブな実装では性能が悪くなりがちになる。そのため、ある程度まとめて扱うように変形されることも多いことから、それを前提として、[[MUGI]]のように一度の処理で64ビットといったサイズの鍵ストリームを出力し、まとめて暗号化処理することを考慮に入れたアルゴリズムが提案されている。

ストリーム暗号の安全性についての研究はブロック暗号に比べて遅れている。安全性の評価手法の研究には長い時間を要するので、ブロック暗号に基づくストリーム暗号を利用すべきとの意見もある。ブロック暗号をCTRモードで利用した場合、ブロック暗号が擬似ランダム置換であれば、[[計算量的安全性|計算量的に安全]]である。

== 構造 ==
鍵ストリーム生成部は、128ビット程度の秘密鍵を用いて[[擬似乱数]]を生成する。通常のストリーム暗号は共通鍵方式であるが、[[公開鍵暗号|非対称鍵]]方式のストリーム暗号も提案されている。擬似乱数ではなく真の乱数を利用する場合もある。また、一度使用した鍵ストリームを再使用しないように制御する必要があるので、平文ごとに異なる初期値 ([[初期化ベクトル]], IV) を使用する。IVは乱数かカウンタで作る。

鍵ストリーム生成の方法には、専用のアルゴリズムによるものと、ブロック暗号を元にした生成方法とがある。専用アルゴリズムによる鍵ストリーム生成は、フィードバックシフトレジスタに基づくものが多い。フィードバックシフトレジスタは[[シフトレジスタ]]とフィードバック関数で構成される。

フィードバックの構成方法には、暗号文を鍵ストリームにフィードバックしない方式（同期式、外部同期）と、フィードバックする方式（非同期式、自己同期）がある。方式によって、暗号文にビットエラーが生じたときのエラーの伝播が異なる。

;同期式 (Synchronous stream cipher) :送信側・受信側の両方で、平文・暗号文とは独立して鍵シーケンスを生成する。この方式にはビット誤りが発生したときに他のビットに誤りが波及しないという特長がある。しかし、攻撃者が暗号文を操作（たとえばビット反転）すると平文を変更できてしまうというデメリットでもある。場合によっては[[メッセージ認証符号|MAC]]などのメッセージ認証を必要とする。また、同期がずれた場合には再同期の仕組みが別途必要となることから外部同期式ともいう。
;非同期式 (asynchronous stream cipher) :'''自己同期式'''（Self-synchronising stream cipher）ともいい、同期がずれたときでも自動的に再同期できるメリットがある。1ビットの誤りが他のビットにも波及して誤りが拡大するというデメリットもある。しかし、ビット誤りが発生してもレジスタ長だけ経過すれば送信側と受信側のレジスタ値が一致し、同期を自動的に回復させることができる。非同期式の例として暗号利用モードの CFB がある。

結合部は、典型的にはXORなどで平文と鍵ストリームを結合する。理論的には、暗号文に原文あるいは鍵ストリームの痕跡が現れず、何らかの逆関数が存在するような可逆な関数であればXOR以外でも構わないが、基本的には強度が変化するなどということはないのであまり意味はない。<!--XOR以外に、加算や[[特別計算法|特別な表]]を用いた方式もある。--><!--ストリーム暗号の概念が確立される以前の暗号方式である特別計算法にリンクするのはいかがなものか？-->

鍵ストリーム生成部と結合部を別の装置にした場合、前者は安全に保管・運用する必要があるが、後者は通信装置に組み込むことが可能になる。暗号装置を通信装置と結合する際には注意が必要なので、これを省略できることはメリットとなる。<!-- カスケードにより、安全性を向上できる。-->

== 種類 ==
ここでは、使用する[[擬似乱数]]列生成器のタイプ別に種類分けする。

=== LFSR ===
擬似乱数列生成器として、[[線形帰還シフトレジスタ]] (LFSR; Linear Feedback Shift Register) を用いた方法が知られている。LFSRはハードウェアを用いて容易に実装することができる。しかし、LFSRは数学的に容易に解析可能であるため、そのまま暗号に使用することは推奨されない。相関攻撃 (Correlation attack) の餌食となる。非線形なFSRを使うものもある（NFSR; Nonlinear Feedback Shift Register）。
*コンバイナ型：複数のLFSRを非線形関数で結合した方式
*フィルタ型：LFSRの全状態をFilterに入れる方式。
: 例：よく研究対象にされている方式としてTOYOCRYPTがある。
*クロック制御型：LFSRを非連続的動作させる方式。一つのLFSRを他のLFSRのクロックで制御する。
: 例：ベス&パイパーによる stop-and-go generator (Beth and Piper, 1984)、[[GSM]]音声暗号化で使っている[[A5/1]]。

=== その他 ===
==== ストリーム暗号用に設計されたもの ====
[[RC4]]やSEAL（[[:en:SEAL (cipher)]] ）、[[Salsa20]](ChaCha20)など。

==== 暗号論的擬似乱数生成器 ====
一般的な[[暗号論的擬似乱数生成器|暗号論的擬似乱数列生成器]]を使うこともある（一般的には計算量の点で利点が無いが、他の部分により重い計算があるなど、それが問題にならない場合。例えば [[:en:Blum–Goldwasser cryptosystem]] の内部に、[[Blum-Blum-Shub]]を利用するストリーム暗号、という構造が含まれている）。

==== カオス ====
[[カオス理論|カオス]]に基づく擬似乱数生成器の利用も提案されている（[[梅野健]]の提案による「Vector Stream Cipher（VSC）」など）。
<!-- 単にリストならば暗号理論のリストに記述すればよいか。
* LFSR型
<コンバイナ型> 非線形コンバイナ
** ジェフ型 Geffe 相関攻撃に弱い
** ダイナミック型
<フィルタ型> 非線形FSR (LFSRが一つの場合)
** TOYOCRYPT
<マルチプレクサ型>
** ジェニング型 Jennings 
** EBU型
** MPT型
<クロック制御型>
** ベスパイパー型 Stop&Go
** 交互型
<閾値型>
<自己クロック制御型>
<加算型>
** A5
* 状態遷移型
** RC4
** SEAL,SCREAM
** SOBER
** PANAMA,MULTI-SO1,MUGI
 -->

== 用途 ==
ストリーム暗号は、平文がいつ何バイト発生するか不確定なアプリケーションによく採用される。例えば、[[音声暗号化]]（[[秘話]]）などの[[秘匿通信]]である。

[[ウェブブラウザ]]で使用される暗号化通信[[Secure Sockets Layer|SSL]]の暗号方式としてRC4が (オプションとして) 採用されている。[[無線LAN]] (WEP,WPA) でもRC4が使用される。他に、[[携帯電話]]用に [[A5/1]], A5/2 などがある。

== 標準 ==
暗号標準として採用（または推奨）されているストリーム暗号には次のものがある。

* OFB, CFB, CTR - [[ISO/IEC_18033]]（ブロック暗号利用モード）
* SNOW 2.0 - ISO/IEC_18033
* [[MUGI]] - ISO/IEC_18033, [[CRYPTREC]]
* MULTI-SO1 - ISO/IEC_18033 (MOF), CRYPTREC
* [[RC4]] - {{IETF RFC|2246}} (TLS), WEP, WPA, CRYPTREC (128bit-RC4だけ)
* [[KCipher-2]] - [[ISO/IEC 18033]], [[CRYPTREC]]
* [[Salsa20|ChaCha20]] - {{IETF RFC|7539}}

== 安全性 ==

=== 鍵ストリームの重複使用の危険性 ===
ストリーム暗号は、鍵ストリームを重複して使用しないことを前提とした暗号アルゴリズムである。そのコンセプトは、鍵ストリームとして推測不可能な乱数列を想定している[[バーナム暗号]]と同じである。ストリーム暗号は、平文ごとに異なる初期化ベクトル (IV) を使用する必要があるが、IVが重複して設定された場合、鍵ストリームも重複して使用されることとなるため、その危険性を以下に例として示す。

平文メッセージ<math>m</math>と鍵ストリーム<math>k</math>から暗号文メッセージ<math>c</math>を生成する場合、次の式で表現できる。

<math>m \oplus  k= c</math>

次に、異なる平文メッセージ<math>m'</math>と鍵ストリーム<math>k</math>（重複して使用）から暗号文メッセージ<math>c'</math>を生成する場合は、次の式となる。

<math>m' \oplus k = c'</math>

ここで、暗号解読者が暗号文メッセージ<math>c</math>と暗号文メッセージ<math>c'</math>を入手したという前提とする。この時、

<math>c \oplus c' =(m \oplus k)\oplus(m' \oplus k)= m    \oplus  m'\oplus k \oplus k= m \oplus m'</math>

となるため、暗号解読者は暗号文メッセージ<math>c</math>と<math>c'</math>の排他的論理和をとった値を求めると、平文メッセージ<math>m</math>と<math>m'</math>の排他的論理和を得ることができる。

仮に、平文メッセージ<math>m</math>の全部又は一部が暗号解読者に知られていた場合（例えば、文末に必ず「ハイルヒトラー」が記載されている等）、暗号解読者に平文メッセージ<math>m'</math>の内容を推定するための手がかりを与えることになる。

なお、ブロック暗号の場合も、[[暗号利用モード]]のOFB, CFB, CTRを利用するとストリーム暗号が構成できるので、同様の危険性が生じる。

=== ストリーム暗号の安全性の条件 ===
ストリーム暗号の安全性の条件として、次の5項目があげられる。<!-- ゴーリッシュの基準 -->
* 統計的乱数性
* 非線形性
* 無相関性
* 長周期性
* 線形複雑度（linear complexity）

鍵ストリーム生成部は、通常、内部状態を記憶するレジスタがあり、レジスタ長が安全性の上限の一つとなる。レジスタの初期値を決める秘密鍵の長さも安全性の上限を決める。（これらの長さは安全性の上限を決めるのであって下限ではない。）

安全性の根拠：
* 鍵ストリームとして、擬似乱数ではなくいわゆる真の乱数を使用し、一度使用した乱数列は絶対に再使用しない[[ワンタイムパッド]]として運用した場合、[[情報理論的安全性]]をもつ。しかし、平文と同じ長さの乱数列を事前に生成して共有しておく必要があるなど、運用的に高価であり広くは採用されていない。
* 鍵ストリーム生成部にブロック暗号を部品として使用し、ストリーム暗号の安全性をブロック暗号の安全性に帰着させるものがある。
* ブロック暗号のCTRモードは、ブロック暗号が擬似ランダム関数とみなせるのならば計算量的安全性をもつが、[[誕生日のパラドックス]]からブロック長 ''n'' に対して <math>2^{n/2}</math> ブロック程度の出力で自然乱数と識別可能である。

== 歴史 ==
[[排他的論理和]]（[[XORゲート|XOR]]）をとる、という構造は[[バーナム暗号]]そのものと言えるが、バーナム暗号は情報理論の発達以前ということもあり（一般にバーナム暗号の原文献とされる特許明細では）乱数列の生成法について、明確に定義されていない。

自己同期式のストリーム暗号は、ブレーズ・ド・ヴィジュネルが考案している。{{節スタブ}}
<!-- 乱数式ができたのはいつ？2005年には、ISOでの標準化もなされている。-->

== 参考文献 ==
* Thomas Beth, Fred Piper, "The Stop-and-Go Generator", EUROCRYPT'1984, pp. 88-92.

== 関連項目 ==
* [[暗号理論]]
* [[音声暗号化]]
* [[換字式暗号]]
* [[共通鍵暗号]]
* [[ブロック暗号]]
<!--
== 外部リンク ==
* -->

{{cryptography navbox|stream}}

{{DEFAULTSORT:すとりいむあんこう}}
[[Category:暗号技術]]
[[Category:ストリーム暗号|*]]
[[Category:数学に関する記事]]