ストリーム暗号
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ストリーム暗号（-あんごう、Stream cipher）とは、平文をビット単位あるいはバイト単位などで逐次、暗号化する暗号である。これに対して、平文を64ビットや128ビット等の一定サイズ毎に暗号化する暗号はブロック暗号といい、ストリーム暗号とブロック暗号とに大別される共通鍵暗号と、公開鍵暗号とで現代暗号の主要な暗号方式をなす。
目次 |
[編集] 概要
ストリーム暗号は、鍵ストリーム（key stream）を生成する鍵ストリーム生成部と、鍵ストリームと平文を結合する結合部からなる暗号で、典型的には、秘密鍵をシードとして擬似乱数を生成し、平文とXORして暗号文を作り、復号時には、同じくシードから擬似乱数を生成して暗号文とXORすることで平文を得るものである。
平文を一文字入力して暗号文の一文字が得られる暗号はストリーム暗号であり、古典暗号や機械式暗号の多くが該当する。例えばシーザー暗号などの単一換字式暗号やヴィジュネル暗号、エニグマ暗号機の暗号方式などはストリーム暗号に分類される。古典暗号でストリーム暗号でないのは、綴字換字式暗号や転置式暗号などである。逆に現代暗号では、DES,AES等ブロック暗号が多い。ストリーム暗号は、通信などストリーム暗号の特徴が生かされる用途に利用されている。
ブロック暗号はブロック単位で暗号化するため、ブロックサイズ分のデータが揃うまで暗号化処理を開始できないが、ストリーム暗号は、1bitあるいは1byteなどの単位で処理を行うため、待ち時間が少ない。また、ブロック暗号では、平文がブロックサイズの整数倍ではない場合に必要なパディング処理も、ストリーム暗号では不要であり、常に平文サイズ＝暗号文サイズとなる。処理遅延が少ないこと、データサイズが増加しないことは通信などに利用する場合にメリットとなりうる。
しかしながら、暗号利用モードのOFBやCFBでブロック暗号を利用するとストリーム暗号が構成できるため、ストリーム暗号専用アルゴリズムは、ブロック暗号と比べて何かしらの点で特徴(メリット)がなければ存在する意味がない。 この点、ストリーム暗号は、ソフトウェア実装すると一度の暗号化処理で1bitあるいは1byteしか扱えないため性能が悪くなりがちである。ハードウェア実装した場合には、回路規模が小さく、処理速度が高いものがある。しかし、安全性については、ブロック暗号と比べてストリーム暗号の研究は遅れていて、安全性の評価手法の研究には長い時間を要するため、ブロック暗号ベースのストリーム暗号を利用すべきとの意見もある。
[編集] 構造
鍵ストリーム生成部は、128bit程度の秘密鍵を用いて擬似乱数を生成する。通常、共通鍵方式であるが、公開鍵暗号方式(非対称暗号)のストリーム暗号も提案されている。擬似乱数ではなく、真の乱数を利用する場合もある(バーナム暗号)。また、一度使用した鍵ストリームは、再使用しないように制御する必要がある為、平文毎に異なるIVを使用する。IVは乱数かカウンタで作る。
鍵ストリーム生成のアルゴリズムとしては、専用のアルゴリズムによるものと、ブロック暗号を元にした生成方法がある。専用アルゴリズムによる鍵ストリーム生成部は、フィードバックシフトレジスタにもとづくものが多い。シフトレジスタとフィードバック関数から構成される。
フィードバックの構成方法に、暗号文を鍵ストリームにフィードバックする方式（同期式、外部同期）と、フィードバックしない方式（非同期式、自己同期）がある。暗号文がビットスリップしたときのエラーの伝播が異なる。
- 同期式（Synchronous stream cipher） - 送信側・受信側とも、平文・暗号文とは独立して鍵シーケンスを生成する。bitエラーが発生したときに他のbitにエラーが波及しないという特徴がある。逆に、攻撃者が暗号文を操作（例：bit反転）することで、平文を変更できてしまうというデメリットにもなる。場合によってはMACなどのメッセージ認証が必要となる。また同期がずれた場合には、再同期の仕組みが別途必要となる。外部同期式ともいう。
- 非同期式（asynchronous stream cipher）- 自己同期式（Self-synchronising stream cipher）とも呼ばれ、同期がずれたときでも自動的に再同期できるメリットがある。エラーが発生してもレジスタ長だけ経過すると送信・受信側のレジスタ値が一致し、同期を自動的に回復させることができる。しかし1bitエラーが他のbitにも波及し、エラーが拡大するというデメリットもある。非同期式の例として暗号利用モードの CFB がある。
結合部は、XORなどで平文と鍵ストリームを結合する。stub
鍵ストリーム生成部と結合部を別の装置にすると、前者はセキュアに保管運用する必要があるが、後者は通信装置に組み込み可能になる。暗号装置を通信装置と結合する際には注意が必要なので、メリットとなる。
[編集] 種類
[編集] 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)
[編集] 状態遷移型
RC4やSEALのような、状態変数を逐次更新することで、鍵ストリーム生成する方式もある。stub
[編集] 用途
ストリーム暗号は、平文がいつ何バイト発生するか不確定なアプリケーションによく採用される。例えば、秘匿通信（秘話）である。
Webブラウザで使用される暗号化通信SSLの暗号方式としてRC4が採用（オプション）されている。無線LAN（WEP,WPA）でもRC4が使用される。他に、携帯電話用に A5/1, A5/2 などがある。
[編集] 標準
暗号標準として採用(or推奨)されているストリーム暗号には次のものがある。
- OFB,CFB,CTR --- ISO/IEC_18033（asブロック暗号利用モード）
- SNOW 2.0 ------ ISO/IEC_18033
- MUGI ---------- ISO/IEC_18033, CRYPTREC
- MULTI-SO1 ----- ISO/IEC_18033(as MOF), CRYPTREC
- RC4 ----------- RFC 2246 (TLS), WEP, WPA, CRYPTREC(128bit-RC4のみ)
[編集] 安全性
ストリーム暗号の安全性の条件としては：
- 統計的乱数性
- 非線形性
- 無相関性
- 長周期性
- 線形複雑度（linear complexity）
などがあげられる。
鍵ストリーム生成部は、通常、内部状態を記憶するレジスタがあり、レジスタ長が安全性の上限の一つとなる。レジスタの初期値を決める秘密鍵のサイズも安全性の上限を決める。これらのサイズは安全性の上限を決めるのであって下限ではない。
安全性の証明については：
- 鍵ストリームとして完全なランダムシーケンスを採用すると、OTP(One Time Pad)となって情報理論的安全性を持つ。しかし、平文と同じ長さの乱数が必要であり、OTPは広くは採用されていない。
- 鍵ストリーム生成部にブロック暗号を部品として使用し、ストリーム暗号の安全性をブロック暗号の安全性に帰着させるものがある。
[編集] 歴史
自己同期式のストリーム暗号は、ブレーズ・ド・ヴィジュネルが考案している。stub
[編集] 参考文献
- Thomas Beth, Fred Piper, "The Stop-and-Go Generator", EUROCRYPT'1984, pp88-92.
