ストリーム暗号あんごう

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

概要がいよう

ストリーム暗号あんごうは、鍵かぎストリーム（key stream）を生成せいせいする鍵かぎストリーム生成せいせい部ぶと、鍵かぎストリームと平文へいぶんを結合けつごうする結合けつごう部ぶで構成こうせいされる。典型てんけい的てきには、共通きょうつう鍵かぎ方式ほうしきにおいて、ある鍵かぎを初期しょき値ちとして擬似ぎじ乱数らんすう列れつを生成せいせいし、平文へいぶんとの排他はいた的てき論理ろんり和わ (XOR、 $\oplus$ ) によって暗号あんごう文ぶんを作つくる。復号ふくごう時じには、同おなじ鍵かぎ（同おなじ初期しょき値ち）から生成せいせいした擬似ぎじ乱数らんすう列れつと暗号あんごう文ぶんとの排他はいた的てき論理ろんり和わによって平文へいぶんを得える。

(m\oplus k)\oplus k=m\oplus (k\oplus k)=m

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

暗号あんごう利用りようモードのOFB, CFB, CTRなどでブロック暗号あんごうを利用りようするとストリーム暗号あんごうを構成こうせいできるので、ストリーム暗号あんごう専用せんようのアルゴリズムは、ブロック暗号あんごうと比くらべて何なにかしらの点てんで特長とくちょう（メリット）がなければ開発かいはつする意味いみがない。たとえば、近年きんねん（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以外いがいでも構かまわないが、基本きほん的てきには強度きょうどが変化へんかするなどということはないのであまり意味いみはない。

鍵かぎストリーム生成せいせい部ぶと結合けつごう部ぶを別べつの装置そうちにした場合ばあい、前者ぜんしゃは安全あんぜんに保管ほかん・運用うんようする必要ひつようがあるが、後者こうしゃは通信つうしん装置そうちに組くみ込こむことが可能かのうになる。暗号あんごう装置そうちを通信つうしん装置そうちと結合けつごうする際さいには注意ちゅういが必要ひつようなので、これを省略しょうりゃくできることはメリットとなる。

種類しゅるい

ここでは、使用しようする擬似ぎじ乱数らんすう列れつ生成せいせい器きのタイプ別べつに種類しゅるい分わけする。

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）」など）。

用途ようと

ストリーム暗号あんごうは、平文へいぶんがいつ何なにバイト発生はっせいするか不ふ確定かくていなアプリケーションによく採用さいようされる。例たとえば、音声おんせい暗号あんごう化か（秘話ひわ）などの秘匿ひとく通信つうしんである。

ウェブブラウザで使用しようされる暗号あんごう化か通信つうしん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 - RFC 2246 (TLS), WEP, WPA, CRYPTREC (128bit-RC4だけ)
KCipher-2 - ISO/IEC 18033, CRYPTREC
ChaCha20 - RFC 7539

安全あんぜん性せい

鍵かぎストリームの重複じゅうふく使用しようの危険きけん性せい

ストリーム暗号あんごうは、鍵かぎストリームを重複じゅうふくして使用しようしないことを前提ぜんていとした暗号あんごうアルゴリズムである。そのコンセプトは、鍵かぎストリームとして推測すいそく不可能ふかのうな乱数らんすう列れつを想定そうていしているバーナム暗号あんごうと同おなじである。ストリーム暗号あんごうは、平文へいぶんごとに異ことなる初期しょき化かベクトル (IV) を使用しようする必要ひつようがあるが、IVが重複じゅうふくして設定せっていされた場合ばあい、鍵かぎストリームも重複じゅうふくして使用しようされることとなるため、その危険きけん性せいを以下いかに例れいとして示しめす。

平文へいぶんメッセージ $m$ と鍵かぎストリーム $k$ から暗号あんごう文ぶんメッセージ $c$ を生成せいせいする場合ばあい、次つぎの式しきで表現ひょうげんできる。

$m\oplus k=c$

次つぎに、異ことなる平文へいぶんメッセージ $m'$ と鍵かぎストリーム $k$ （重複じゅうふくして使用しよう）から暗号あんごう文ぶんメッセージ $c'$ を生成せいせいする場合ばあいは、次つぎの式しきとなる。

$m'\oplus k=c'$

ここで、暗号あんごう解読かいどく者しゃが暗号あんごう文ぶんメッセージ $c$ と暗号あんごう文ぶんメッセージ $c'$ を入手にゅうしゅしたという前提ぜんていとする。この時とき、

$c\oplus c'=(m\oplus k)\oplus (m'\oplus k)=m\oplus m'\oplus k\oplus k=m\oplus m'$

となるため、暗号あんごう解読かいどく者しゃは暗号あんごう文ぶんメッセージ $c$ と $c'$ の排他はいた的てき論理ろんり和わをとった値ねを求もとめると、平文へいぶんメッセージ $m$ と $m'$ の排他はいた的てき論理ろんり和わを得えることができる。

仮かりに、平文へいぶんメッセージ $m$ の全部ぜんぶ又または一部いちぶが暗号あんごう解読かいどく者しゃに知しられていた場合ばあい（例たとえば、文末ぶんまつに必かならず「ハイルヒトラー」が記載きさいされている等ひとし）、暗号あんごう解読かいどく者しゃに平文へいぶんメッセージ $m'$ の内容ないようを推定すいていするための手てがかりを与あたえることになる。

なお、ブロック暗号あんごうの場合ばあいも、暗号あんごう利用りようモードのOFB, CFB, CTRを利用りようするとストリーム暗号あんごうが構成こうせいできるので、同様どうようの危険きけん性せいが生しょうじる。