ストリーム暗号

提供: miniwiki
2018/8/19/ (日) 17:44時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索

ストリーム暗号（ストリームあんごう、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などでブロック暗号を利用するとストリーム暗号が構成できるので、ストリーム暗号専用アルゴリズムは、ブロック暗号と比べて何かしらの点で特長（メリット）がなければ存在する意味がない。たとえば、近年（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 などがある。

標準

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

安全性

ストリーム暗号の安全性の条件として、次の5項目があげられる。

  • 統計的乱数性
  • 非線形性
  • 無相関性
  • 長周期性
  • 線形複雑度（linear complexity）

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

安全性の根拠：

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

歴史

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

自己同期式のストリーム暗号は、ブレーズ・ド・ヴィジュネルが考案している。

参考文献

  • Thomas Beth, Fred Piper, "The Stop-and-Go Generator", EUROCRYPT'1984, pp. 88-92.

関連項目


テンプレート:Cryptography navbox



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ストリーム暗号&oldid=116254」から取得