(57)【特許請求の範囲】
【請求項１】
対称暗号化を実行するための暗号化装置であって、
暗号キー（Ｋ）に応答して、複数ビット（ｓ）の疑似ランダム数シーケンスからなるキーストリームブロック（Ｓ（ｉ））を生成する生成手段（ＫＳ）と、
暗号文ブロック（Ｃ（ｉ））を生成するために、前記キーストリームブロック（Ｓ（ｉ））を、複数ビット（ｂ）の平文ブロック（Ｐ（ｉ））と結合する結合手段（ＭＸ）とを備え、
前記結合手段（ＭＸ）は、
前記キーストリームブロックＳ（ｉ）の第３の部分（Ｄ（ｉ））を暗号文ブロック（Ｃ（ｉ−１））と乗算する第１の乗算手段と、
前記第１の乗算手段の乗算結果と、前記平文ブロックＰ（ｉ）とを加算する第１の加算手段と、
前記第１の加算手段の加算結果と、前記キーストリームブロック（Ｓ（ｉ））の第１の部分（Ａ（ｉ））とを乗算する第２の乗算手段と、
前記第２の乗算手段の乗算結果と、前記キーストリームブロック（Ｓ（ｉ））の第２の部分（Ｂ（ｉ））とを加算する第２の加算手段と、を有し、
前記キーストリームブロック内のビット数（ｓ）は平文ブロック内のビット数（ｂ）より大きい暗号化装置。
【請求項２】
前記生成手段（ＫＳ）は、暗号化対象の平文データ（Ｐ）の対応する各平文ブロック（Ｐ（ｉ））と結合されるべき、連続したキーストリームブロック（Ｓ（ｉ））を前記疑似ランダム数シーケンスから選択する選択手段を有する請求項１記載の暗号化装置。
【請求項３】
前記結合手段（ＭＸ）は、与えられたキーの基で、平文データの暗号化の際に１回のみ、前記連続したキーストリームブロックの各々を使用するように構成された請求項２記載の暗号化装置。
【請求項４】
前記選択手段は、前記キーストリームブロックの各々を形成するために前記疑似ランダム数シーケンスから非重複ビットシーケンスを選択するよう構成された請求項２または３記載の暗号化装置。
【請求項５】
前記キーストリームブロックＳ（ｉ）は、各平文ブロックＰ（ｉ）の３倍のビット（３ｂ）からなる、請求項１から４のいずれか一項に記載の暗号化装置。
【請求項６】
さらに、各キーストリームブロック（Ｓ（ｉ））を複数のサブブロック（Ａ（ｉ），Ｂ（ｉ），Ｄ（ｉ））に分割する手段を備える、請求項１から５のいずれか一項に記載の暗号化装置。
【請求項７】
前記サブブロックは、暗号化対象の平文ブロック（Ｐ（ｉ））と同数のｂビットを有する請求項６記載の暗号化装置。
【請求項８】
前記生成手段はさらにナンス入力を有する、請求項１から７のいずれか一項に記載の暗号化装置。
【請求項９】
前記ナンス入力を生成するカウンタ（ＣＴ１，ＣＴ２）を有する請求項８記載の暗号化装置。
【請求項１０】
前記生成手段はハッシュ関数発生器を有する請求項８または９記載の暗号化装置。
【請求項１１】
中間キーを生成する複数の独立した前記生成手段（ＫＳｉ）が並列に接続され、暗号化対象の平文ブロック（Ｐ（ｉ））に応じて前記生成手段（ＫＳｉ）を切り替える手段（ＳＷ）とを備える、請求項１から１０のいずれか一項に記載の暗号化装置。
【請求項１２】
第１の中間キー（Ｓ１）を生成する第１の生成手段（ＫＳ１）と、さらに、前記第１の中間キーに応じて第２の中間キー（Ｓ２）を生成する第２の生成手段（ＫＳ２）とを備える請求項１から１０のいずれか一項に記載の暗号化装置。
【請求項１３】
前記第１の中間キーは、暗号化対象の複数の要素から選択された個々の要素に対する暗号キーを含む請求項１２記載の暗号化装置。
【請求項１４】
コンピュータに、対称暗号化を実行させるためのプログラムを記録した記録媒体であって、
前記プログラムは、前記コンピュータを、
暗号キー（Ｋ）に応答して、複数ビット（ｓ）の疑似ランダム数シーケンスからなるキーストリームブロック（Ｓ（ｉ））を生成する生成手段（ＫＳ）と、
暗号文ブロック（Ｃ（ｉ））を生成するために、前記キーストリームブロック（Ｓ（ｉ））を、複数ビット（ｂ）の平文ブロック（Ｐ（ｉ））と結合する結合手段（ＭＸ）として機能させ、
前記結合手段（ＭＸ）は、
前記キーストリームブロックＳ（ｉ）の第３の部分（Ｄ（ｉ））を暗号文ブロック（Ｃ（ｉ−１））と乗算する第１の乗算手段と、
前記第１の乗算手段の乗算結果と、前記平文ブロックＰ（ｉ）とを加算する第１の加算手段と、
前記第１の加算手段の加算結果と、前記キーストリームブロック（Ｓ（ｉ））の第１の部分（Ａ（ｉ））とを乗算する第２の乗算手段と、
前記第２の乗算手段の乗算結果と、前記キーストリームブロック（Ｓ（ｉ））の第２の部分（Ｂ（ｉ））とを加算する第２の加算手段と、を有し、
前記キーストリームブロック内のビット数（ｓ）は平文ブロック内のビット数（ｂ）より大きいこと
を特徴とする、プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、特に（但し限定する意味ではなく）、通信システムやコンピュータネットワーク上での用途のための、例えば、インターネット取引のための安全なチャネルを提供するための暗号化装置および方法、並びに対応する復号装置および方法に関する。
【０００２】
【従来の技術】
近年の暗号は、インターネットのようなネットワーク上での安全な取引用にデータを暗号化する、サイファー(ciphers)として知られているような、暗号化アルゴリズムの使用に依存している。データの秘匿性を保持する主機能に加えて、暗号化システムは、データ保全性(data integrity)の保持を含む幾つかの他の機能を提供することができる。そのために、メッセージの受信者は、そのメッセージが暗号化された後に第三者によって改竄されていないことを検証しうる必要がある。
【０００３】
暗号化アルゴリズムを秘密に保つ必要をなくすために（これは、そのアルゴリズムが市販の商品内に組み込まれている場合には困難な場合がある）、最近のアルゴリズムは、膨大な個数の取りうる値が想定される暗号キーＫを用いる。よって、この暗号化システムの安全性は、そのアルゴリズムの細部ではなく、このキーに依存することになる。
【０００４】
キーに基づくアルゴリズムには、対称すなわち秘密キーアルゴリズムと、非対称すなわち公開キーアルゴリズムの二つの汎用タイプがある。本発明は対称アルゴリズムの方に関する。暗号方式に基づいた対称アルゴリズムの殆どにおいて、暗号キーと復号キーとは同一であり、送信者と受信者は、互いに秘密に通信することができる前提として、キーについての合意しなければならない。また、両者は、そのキーが秘密の状態におかれているということを確かめなければならない。なぜなら、そのシステムの安全性は、第三者がそのキーを知っていることにより、低下するからである。
【０００５】
図１は、暗号化通信の基本原理を示す。平文Ｐとして既知の非暗号化データは、送信者により暗号化アルゴリズムＥと暗号キーＫとを用いて暗号化され、暗号文(ciphertext)Ｃとして知られる暗号データが生成される。数学的には、この演算はＥk（Ｐ）＝Ｃと表せる。暗号文は通信路（チャネル）を介して受信者へ送られ、そこで、復号アルゴリズムＤが適用されて、暗号文から平文が復元される。この演算は、Ｄk（Ｃ）＝Ｐと表せる。機能ＤおよびＥは、Ｄk（Ｅk（Ｐ））＝Ｐという性質を有し、ここではＤをＥの逆変換(inverse)と呼ぶ。互いに異なるが暗号的に関連したキーＫ１，Ｋ２がそれぞれ暗号化と復号に用いられる場合、適当な式表現は、Ｅk1（Ｐ）＝Ｃ、Ｄk2（Ｃ）＝Ｐ、かつ、Ｄk2（Ｅk1（Ｐ））＝Ｐとなる。
【０００６】
対称アルゴリズムは、ブロックサイファーおよびストリームサイファーと総称される二つのカテゴリに分類することができる。一般に、ストリームサイファーは、一度に１ビットずつ平文を処理し、ブロックサイファーよりかなり高速である。例えば、簡単なストリームサイファーでは、平文の各ビットは、キーストリーム生成器により生成された疑似ランダムビットストリームのうちの対応するビットとの間で排他的論理和（ＸＯＲ）がとられる。
【０００７】
ストリームサイファーは、メッセージの秘匿性を保持する主暗号機能を有するが、データ保全性の保持には独立した機能を追加する必要がある。さもなければ、平文における１ビット位置の変更がそのまま暗号文の対応する位置における変更となるからである。したがって、独立した保全性保持機能を実現するためには、回路および／またはメモリの追加が必要となる。
【０００８】
ブロックサイファーは、ブロックとして知られる平文ビットのグループに対して作用する。例えば、典型的なブロックのサイズは６４ビットである。ブロックサイファーが利用されるのは、それが秘密保持性とデータ保全性の両方を与える能力をもつがためである。しかし、ブロックサイファーは、概して、ストリームサイファーに比べて相当速度が遅い。例えば、既知のＤＥＳブロックサイファーは、５６ビットのキーを用いて、６４ビットブロック単位にデータを暗号化する。このキーを用いて、そのキーの１６個の異なる４８ビットのサブセットからなるキースケジュールが生成される。このキースケジュールの全出力を用いて、高度な非線形データランダム化アルゴリズムで各平文ブロックが暗号化される。
【０００９】
ブロックサイファーおよびストリームサイファー並びにそれらの動作モードの概要については、ブルース・シュナイアー(Bruce Shneier)による”アプライド・クリプトグラフィー(Applied Cryptography)”、第２版、第９章、第１８９−２１１頁を参照されたい。
【００１０】
【発明が解決しようとする課題】
本発明は、ブロックサイファーおよびストリームサイファーの利点を組み合わせることを目的としている。
【００１１】
【課題を解決するための手段】
本発明によれば、対称暗号化を実行するための暗号化装置であって、暗号キーに応答して複数ビットの疑似ランダム数シーケンスからなるキーストリームブロックを生成する生成手段と、暗号文ブロックを生成するために、このキーストリームブロックを、複数ビットからなる平文ブロックと結合する結合手段とを備え、前記キーストリームブロック内のビット数は平文ブロック内のビット数より大きい暗号化装置が提供される。
【００１２】
より短いキー列から生成された疑似ランダムシーケンスのブロック単位の使用により、データ秘匿性およびデータ保全性の点でブロックサイファーの利点を保持することができるとともに、ストリームサイファーの速度上の利点をも享受することができる。なぜなら、疑似ランダム数シーケンスの生成は、一般に、ブロックサイファーの動作より高速であり、かつ、前記結合手段がより簡単かつ迅速に実現できるからである。
【００１３】
前記生成手段は、各々、暗号化対象の平文データの対応する平文ブロックと結合されるべき、連続したキーストリームブロックを前記疑似ランダム数シーケンスから選択する選択手段を有することができる。さらに、前記結合手段は、与えられたキーの基で、与えられた平文データの暗号化の際に１回のみ、前記連続したキーストリームブロックの各々を使用するように構成することができる。これによって、もし当該疑似ランダム数生成器が安全と仮定されるならば、無条件にワンタイムパッド(one-time-pad：一度しか使わない暗号表）的な安全性が得られる。換言すれば、当該生成手段は、各平文ブロックを暗号化するための新鮮なキーストリームブロック群を生成することができる。そのキーストリームビットシーケンスは、暗号化対象のデータの長さに依存する。このキーストリームデータの新鮮度によって、前記結合手段を、ブロックサイファーでの対応するデータランダム化手段より簡単かつ高速となしうる。なぜなら、結合手段は、非線形機能であることを必要としないからである。
【００１４】
本装置は、１つのキーストリームブロックを複数のサブブロックに分割する手段を有することができる。このサブブロックは、前記疑似ランダムビットシーケンスの個別のまたは重複した部分を含むことができる。
【００１５】
前記結合手段は、第１の組み合わせを得るために前記キーストリームブロックの第１の部分を平文ブロックと結合する第１の手段と、暗号文ブロックを生成するために前記第１の結合手段の結果を前記キーストリームブロックの第２の部分と結合する第２の手段とを有しうる。ｓビットのキーストリームブロックをｂビットのサブブロック（これは付加的なパディングビット(padding bits)を含んでもよい）に分割することによって、前記結合手段は、例えば、ＧＦ（２b ）の数学的演算により、平文の等長シーケンスをキーストリームサブブロックと結合することができる。
【００１６】
前記生成手段は、暗号キーの入力を受ける疑似ランダム数生成器、または、キーおよびナンス(nonce)の入力を受けるハッシュ関数を有し得る。ナンスとは、３２ビットあるいは６４ビット程度の時系列に変化するバイナリデータであり、過去に一度も現れていない値を示すものである。乱数やカウンタの値などがこれに用いることができる。
【００１７】
本暗号化装置は、中間キーを生成する複数のキーストリーム生成器と、暗号化対象の平文ブロックに応じて前記キーストリーム生成器を切り替える手段とを備え、中間キーシーケンスの並列計算により速度向上を可能とする。
【００１８】
本暗号化装置は、代替的に、ナンス入力を有する前記第１のキーストリーム生成器により生成された第１の中間キーに応答して第２の中間キーを生成する第２のキーストリームを有しうる。ファイルやレコードのような個々の要素に基づいてナンスを生成することにより、第１の中間キーは個々の要素の暗号化を行う。これによって、データベースやディスク暗号化のような用途において個々の要素の暗号化を行うとともに、中間キーのみを共用し、当該秘密キーは暗号化サイトに保持することが可能となる。
【００１９】
本発明によれば、さらに、暗号キーに応じて疑似ランダム数シーケンスを生成するキーストリーム生成器と、前記疑似ランダム数シーケンスから選択されたビットパターンからなるキーストリームブロックを、ビットシーケンスからなる平文ブロックと結合するよう構成された処理回路とを備え、前記キーストリームブロックビットパターンは、平文ブロックビットシーケンスより多いビット数からなる暗号化装置が提供される。
【００２０】
本発明によれば、また、対称復号化を実行する復号装置であって、復号キーに応じて、複数のビットの疑似ランダム数シーケンスからなるキーストリームブロックを生成する生成手段と、平文ブロックを復元するために前記キーストリームブロックを暗号文ブロックと結合する結合手段とを備え、前記キーストリームブロック内のビット数は前記暗号文ブロック内のビット数より多い復号装置が提供される。
【００２１】
本発明は、さらに、対称暗号化を行う方法であって、暗号キーに応じて、複数ビットの疑似ランダム数シーケンスからなるキーストリームブロックを生成し、このキーストリームブロックを、複数のビットの平文ブロックと結合することにより暗号文ブロックを生成し、前記キーストリームブロック内のビット数は前記平文ブロック内のビット数より多い方法を提供する。
【００２２】
本発明は、さらに、対称的に暗号化された暗号文メッセージを復号する方法であって、復号キーに応じて、複数ビットの疑似ランダム数シーケンスからなるキーストリームブロックを生成し、このキーストリームブロックを、複数ビットの暗号文ブロックと結合することにより平文ブロックを生成し、前記キーストリームブロック内のビット数は前記暗号文ブロック内のビット数より多い方法を提供する。
【００２３】
本発明によれば、さらに、対称暗号化を行うためのコンピュータプログラムであって、暗号キーに応じて、複数ビットの疑似ランダム数シーケンスからなるキーストリームを生成する生成手段と、暗号文ブロックを生成するためにこのキーストリームブロックを複数ビットの平文ブロックと結合する結合手段とを備え、前記キーストリームブロック内のビット数は前記平文ブロック内のビット数より多いコンピュータプログラムが提供される。
【００２４】
本発明によれば、また、対称的に暗号化された暗号文メッセージを復号するためのコンピュータプログラムであって、復号キーに応じて、複数ビットの疑似ランダム数シーケンスからなるキーストリームブロックを生成する生成手段と、平文ブロックを生成するためにこのキーストリームブロックを、複数ビットの暗号文ブロックと結合する結合手段とを備え、前記キーストリームブロック内のビット数は前記暗号文ブロック内のビット数より多いコンピュータプログラムが提供される。
【００２５】
【発明の実施の形態】
以下、本発明の実施の形態について、添付の図面を参照して例示説明する。
【００２６】
図２において、本発明による暗号化装置は、中間キーストリーム生成器ＫＳと、混合関数ＭＸto
を有する。
【００２７】
キーストリーム生成器ＫＳ
ＫＳは、暗号キーＫに応じて、疑似ランダム数シーケンスＳの形式で中間キーを生成するよう設計される。ＫＳは、例えば、既知の暗号疑似ランダム数生成器、または、理想的な暗号ハッシュ関数、または、同一入力が与えられたとき常に、予言できない同一のシーケンスを生成するよう保証された任意のデバイスである。例えば、ＷＡＫＥ，ＳＥＡＬまたはＲＣ４のような、既知のストリームサイファー用に使用される疑似ランダム数生成器である。ＫＳはまた、カウンタモードのブロックサイファーまたはカウンタ付きのハッシュ関数であってもよい。疑似ランダム数生成器は非常に長い平文シーケンス（例えばＳＥＡＬアルゴリズムでは６４ＫＢ）を生成することができるが、ハッシュ関数は比較的短いシーケンス（例えば１６０ビット）を生成する。しかし、以下に詳述するように、ハッシュ関数に対して異なる連続した入力を用いることにより、このハッシュ関数は、長い疑似ランダムシーケンスを生成する疑似ランダム数生成器として動作する。
【００２８】
図２に示すように、ＫＳはまた、データのシーケンスとして定義されたナンスＮを受信することができる。この場合、ある特定のキーに対して、特定の値が２度現れる確率が無視できるほど小さい。例えば、ナンスは、特定のキーの基で単一のメッセージの暗号化中に常時カウントアップするカウンタから導出することができる。したがって、メッセージの暗号化中に用いられるナンスの各値は一意である。ナンスの他の例については後述する。
【００２９】
ＫＳの他の実現例として、図３に示すように、キーＫの基で既知のブロックサイファーを用いてナンスＮを暗号化することにより、疑似ランダム数ストリングからなる暗号文Ｓを生成する。代替的に、図４に示すように、キーＫ、ナンスＮおよびパディングビットを連結してハッシュ関数へ入力することにより、中間キーＳとして使用すべきハッシュ値を生成する。いずれの場合も、一旦、現在のストリングが暗号化に利用されたら、他のナンス、例えば前のナンス値を１だけ増加させたものを用いて次の疑似ランダム数ストリングを生成する。
【００３０】
混合関数ＭＸ
再度図２に戻り、中間キーＳは混合関数ＭＸへ入力される。混合関数ＭＸは、平文メッセージＰを受けて、これと疑似ランダム数シーケンスＳとを結合し、暗号文Ｃを生成する。この混合関数ＭＸは、また、前の暗号文出力に依存するフィードバック（帰還）入力Ｆを受けることができる。
【００３１】
図５における、混合関数ＭＸは可逆関数であり、暗号文Ｃと疑似ランダムシーケンスＳとを逆混合関数ＭＸ-1に与えることにより復号が行われ、平文Ｐが復元される。
【００３２】
混合関数ＭＸは、次のような基準に従って、データ秘匿性およびデータ保全性を保持するように設計することができる。
【００３３】
秘匿性：平文の暗号文は、任意のキーの基で、実質的に均一な分布ですべての可能なストリングでありうる。
【００３４】
保全性：変更された平文の暗号文は、任意のキーの基で、すべての取りうる暗号文ストリングの間に実質的に均一に分布する。その結果、Ｓを知らない攻撃者は、その暗号文が何らかの変更を受けた後に平文がどのように変わったかを予言することができない。
【００３５】
これらの条件は数学的には次のように表せる。
【００３６】
秘匿性：Ｐｒｏｂs(MX(P,S)=C)<ｅc, for any P and C
保全性：Ｐｒｏｂs(MX(P,S)^MX(P',S)=D) <ｅi, for any (P,P',D)
ここに、Ｐｒｏｂy(X)は、Ｙの均一な分布に対するＸの確率を表し、演算子”∧”は、ビット単位の排他的論理和（ＸＯＲ）を表す。また、ｅcおよびｅiは、攻撃者がこれらの確率を利用してこの暗号を破ることが計算上不可能なほど小さい。
【００３７】
図６において、データ保全性の検証は、平文メッセージに既知の冗長データを付加しておき、暗号化および対応する復号化の後に当該既知のデータが復元されたことを確認することにより行える。
【００３８】
図７は、平文メッセージＰのｉ番目のブロックを表すｂビット長の汎用化されたブロックＰ（ｉ）を参照して、ナンスまたはフィードバック入力を持たない、図２の装置の動作を説明するためのフロー図である。Ｃ（ｉ）は、ｂビット長の暗号文の対応するブロックを表す。Ｓ（ｉ）は、ｓビット長の疑似ランダム数シーケンスＳのｉ番目のブロックを表す。ステップｓ１において、ＫＳはキーＫに対応する疑似ランダム数シーケンスＳを生成する。一般にこのシーケンスＳのトータル長はキーＫの長さ（ｋビット）より長い。ステップｓ２において、Ｓのｉ番目のブロックは、混合アルゴリズムＭＸにより平文Ｐのｉ番目のブロックと結合され、暗号文Ｃのｉ番目のブロックが生成される。このステップはＰのｎ個の全ブロックに対して繰り返される。例えば、図７及び図８を参照し、平文データのトータル長が６４００ビットであり、ｂ＝６４，ｋ＝６４，かつｓ＝２ｂ＝１２８とすると、ｎ＝１００となり、ｉは１から１００の値をとる。このとき、シーケンスＳは少なくとも１２８００ビットの長さだけなければならない。ステップｓ２はｉの各値について繰り返される。その最初のステップでは、Ｐ（１）すなわちＰの最初の６４ビットをＳ（１）すなわちＳの最初の１２８ビットと結合して、Ｃ（１）すなわち暗号文Ｃの最初の６４ビットブロックを生成する。
【００３９】
ｂビットの平文メッセージより長いｓビットの中間キーを用いることにより、完全なデータ秘匿性が実現できることが情報理論により説明される。データの保全性については、平文と暗号文の各対に対して平均して２の（ｓ−ｂ）乗のキー候補がある。その結果、暗号解読者が平文と暗号文の両方を知っていたとしても、彼は、暗号文に対する何らかの修正に対して平文がどのように変わるかは予言することができない（そうすることの確率である２の（ｓ−ｂ）乗分の１が非常に小さいとして）。例えば、ｓ＝２ｂ、ｂ＝６４ビットの場合、キー候補の個数は２の６４乗となる。
【００４０】
図９は、図５の復号装置の動作を説明するためのフロー図である。
【００４１】
ステップｓ３において、ＫＳはｋビットのキーＫに対応する疑似ランダム数シーケンスＳを生成する。ステップｓ４において、Ｓのｉ番目のブロックは、逆混合アルゴリズムＭＸ-1により、暗号文Ｃのｉ番目のブロックと結合され、平文Ｐのｉ番目のブロックを生成する。このステップは、Ｃのｎ個のブロック全てについて繰り返され、元の平文が復元される。
【００４２】
図１０において、ＭＸ関数の一例は２つの演算関数からなる。その各々は、疑似ランダム入力ブロックＳ（ｉ）の別々の部分に対して動作する。例えば、平文Ｐ（ｉ）の１ブロックはｂビットからなる。Ｓ（ｉ）は２ｂビットのブロックである。Ｓ（ｉ）の最初のｂビットはＡ（ｉ）と表され、最終のｂビットはＢ（ｉ）と表される。よって、Ｓ（ｉ）は、Ａ（ｉ）とＢ（ｉ）の連結(concatenation)すなわちＡ（ｉ）||Ｂ（ｉ）として表すこともできる。Ａ（ｉ）はＧＦ（２b ）内の乗算によりｂビットブロックＰ（ｉ）と結合され、その結果はＧＦ（２b ）内の加算によりＢ（ｉ）と結合される。ここにＧＦ（２b ）内の乗算と加算はガロア体(Galois Field)における計算を示す。このような計算は、リニアフィードバックシフトレジスタを用いてハードウェアで容易に実現できる。ガロア体計算の詳細については、Bruce Schneierによる"Applied Cryptography"、第２版、２５４〜２５５頁を参照されたい。
【００４３】
ＧＦ（２b ）における乗算と除算のためには、値が０である各疑似ランダムシーケンスブロックに対して、当該機能が可逆的であることを保証するために、修正を行う必要がある。この問題は、ａ＊ｃ＝ｂならば、ｃ＝０である場合以外ｂ／ｃ＝ａが成り立つという整数の乗算を例として説明できる。ゼロ値を回避するように乗算器を修正することにより、この問題は解決できる。
【００４４】
この必要な修正は、幾つかの既知の方法によって行うことができる。例えば、ブロックＡ（ｉ）をテストする。もしこれが０であれば、これを既知の数値、例えば１にリセットする。あるいは、そのブロック全体を捨てて、次のブロックを選ぶ。この手順は、キーシーケンス生成器ＫＳで行える。例えば、キーシーケンスブロックＳ（ｉ）が複数のサブブロックＴ（ｉ）・・・Ｚ（ｉ）に分割される場合、各ブロックをＧＦ（２b ）内の乗算／除算を用いた混合関数ＭＸで処理し、ついでサブブロックをチェックしてその値が０であれば１にリセットしなければならないことが知られている。あるいは、サブブロックＴ（ｉ）・・・Ｚ（ｉ）のいずれかが０値を有する場合、ブロックＳ（ｉ）全体を捨てて、疑似ランダム数生成器からの疑似ランダム数シーケンスから次のブロックを選択する。
【００４５】
図１０に示したＭＸ関数は、次式で表すこともできる。
【００４６】
Ｃ（ｉ）＝ＭＸ（Ｐ（ｉ），Ｓ（ｉ））＝（Ａ（ｉ）*Ｐ（ｉ））∧Ｂ（ｉ）
Ｓ（ｉ）＝Ａ（ｉ）||Ｂ（ｉ）；
Ｘ∧Ｙは、ビット単位の排他的論理和（ＸＯＲ）と等価な、ＧＦ（２b ）内の加算を表し、Ｘ＊ＹはＧＦ（２b ）内の乗算を表す。
【００４７】
図１１に、図１０の暗号機能のより詳細な実現例を示す。ＷＡＫＥストリームサイファーに用いられる疑似ランダム数生成器の入力として６４ビットのキーを用い、これにより３２ビットワードのワード列を生成する。４つのこのようなワードは１２８ビットバッファＢＵＦ１２８に格納され、キーストリームブロックＳ（ｉ）となる。この１２８ビットブロックＳ（ｉ）は２つの６４ビットブロックＡ（ｉ）とＢ（ｉ）とに分割される。平文Ｐは、６４ビットの平文バッファＰＢＵＦ内に一度に６４ビットずつ格納される。図１０で説明したように、ＭＸ関数はＧＦ（２64）内の乗算および加算に依存する。
【００４８】
生成された暗号文ブロックＣ（ｉ）は６４ビットの暗号文バッファＣＢＵＦ内に一度に６４ビットずつ格納され、全体の暗号文は、生成された暗号文ブロックの連結すなわち、Ｃ（１）||Ｃ（２）||Ｃ（３）・・・||Ｃ（ｎ）により生成される。ここに、ｎは平文ブロックの総数である。ＷＡＫＥアルゴリズムの詳細およびその参照のためには、Bruce Schneierによる"Applied Cryptography"、第２版、４００〜４０２頁を参照されたい。
【００４９】
図１０及び図１１の暗号化装置への用途に適した、上述の技術を用いた混合関数の他の例は、次式で表すことができる。
【００５０】
ＭＸ（Ｐ（ｉ），Ｓ（ｉ））＝Ａ（ｉ）∧（Ｐ（ｉ）＊Ｂ（ｉ））
必要な共通の情報、特にブロック長ｂおよびＧＦ（２b ）の既約多項式の定義に対して暗号化装置および復号装置が共通にアクセスする限り、ブロック長ｂは動的に変わりうる。しかし、メモリ消費および性能上の制約によっては、大サイズのブロック、例えば１ＭＢを超えるブロックに対する本技術の使用が制限される場合がある。
【００５１】
キーストリームブロックＳ（ｉ）は別個のサブブロックに分割される必要はなく、重なり合うビットシーケンスを含むサブブロックに分割してもよい。例えば、１２８ビットキーストリームブロックＳ（ｉ）は各々４８ビットの１６個のサブブロックに分割される。各サブブロックは、平文ブロックを暗号化するためにＤＥＳアルゴリズムの１ラウンドへの入力として用いることができる。ＤＥＳアルゴリズムについては、Bruce Schneierによる"Applied Cryptography"、第２版、２７０〜２７８頁を参照されたい。
【００５２】
上述した技術を用いる、フィードバック入力を有する混合関数ＭＸの例を図１２〜図１５に示す。前述したように、疑似ランダムシーケンスＳの各ブロックＳ（ｉ）は２つのｂビットブロックに分割され、Ｓ（ｉ）＝Ａ（ｉ）||Ｂ（ｉ）となる。ここに、Ａ（ｉ）とＢ（ｉ）の長さは各々ｂビットである。暗号文Ｃ（ｉ）の各ブロックは、平文ブロックＳ（ｉ）と直前の暗号文ブロックＣ（ｉ−１）との結合であり、Ｃ（ｉ）＝ＭＸ（Ｐ（ｉ），Ｓ（ｉ），Ｃ（ｉ−１））と表される。あらゆる場合、Ｃ（０）は、同一の先頭部を有するメッセージ、例えば標準的電子メールアドレスに基づく暗号への攻撃を防止するために与えられる初期ベクタＩＶである。ＩＶはランダムデータ、例えば時刻スタンプである。
【００５３】
図１２は、次のような混合関数を示す。
【００５４】
C(i)＝MX(P(i),S(i),C(i-1))＝((C(i-1)*A(i))∧P(i))*B(i)
図１３は、次のような混合関数を示す。
【００５５】
C(i)＝MX(P(i),S(i),C(i-1))＝((C(i-1)∧A(i))*P(i))∧B(i)
図１４は、次のような混合関数を示す。
【００５６】
C(i)＝MX(P(i),S(i),C(i-1))＝((C(i-1)*A(i))∧P(i)*B(i))
図１５は、次のような混合関数を示す。
【００５７】
C(i)＝MX(P(i),S(i),C(i-1))＝(C(i-1)∧A(i))*(P(i)∧B(i))
Ｓ（ｉ）は、２ブロックより多く分割することができる。例えば、図１６から図１９を参照すると、長さ３ｂビットの疑似ランダムシーケンスＳ（ｉ）は、各々長さｂビットの３個のブロックＡ（ｉ），Ｂ（ｉ），Ｃ（ｉ）に分割されている。
【００５８】
図１６は、次のような混合関数を示す。
【００５９】
C(i)＝MX(P(i),S(i),C(i-1))＝(((C(i-1)*D(i))∧P(i))*A(i))∧B(i)
図１７は、次のような混合関数を示す。
【００６０】
C(i)＝MX(P(i),S(i),C(i-1))＝(((C(i-1)∧D(i))*P(i))∧A(i))*B(i)
図１８は、次のような混合関数を示す。
【００６１】
C(i)＝MX(P(i),S(i),C(i-1))＝((C(i-1)*D(i))∧(P(i)*A(i)))*B(i)
図１９は、次のような混合関数を示す。
【００６２】
C(i)＝MX(P(i),S(i),C(i-1))＝(((C(i-1)∧D(i))*(P(i)∧A(i)))∧B(i)
図２０において、図１０に示したＭＸ関数の逆関数（ ＭＸ-1）は、２つの演算関数からなる。その各々は、疑似ランダム入力ブロックＳ（ｉ）の別個の部分Ａ（ｉ）およびＢ（ｉ）に対して作用する。例えば、Ｂ（ｉ）はＧＦ（２b ）内の加算によりｂビットのブロックＣ（ｉ）と結合され、その結果はＧＦ（２b ）内の除算によりＡ（ｉ）と結合される。ここに、ＧＦ（２b ）内の除算および加算は、図１０で説明したガロア体内の計算である。
【００６３】
図２１を参照し、図２０の復号関数をより詳細に説明する。ＷＡＫＥストリームサイファーに対する入力として６４ビットのキーＫを用いて、これにより、３２ビットワードのワード列を生成する。この４ワードは、１２８ビットバッファＢＵＦ１２８内に格納され、キーストリームブロックＳ（ｉ）となる。この１２８ビットブロックＳ（ｉ）は、２つの６４ビットブロックＡ（ｉ）およびＢ（ｉ）に分割される。暗号文Ｃは、６４ビット暗号文バッファＣＢＵＦ内に一度に６４ビットずつ格納される。 ＭＸ-1関数は、図２０で説明したように、ＧＦ（２64）内の除算および加算に依存する。
【００６４】
生成された平文ブロックＰ（ｉ）は、６４ビット平文バッファＰＢＵＦ内に一度に６４ビットずつ格納され、平文全体は、生成された平文ブロックの結合、すなわちＰ（１）||Ｐ（２）||Ｐ（３）・・・||Ｐ（ｎ）により生成される。ここに、ｎは平文ブロックの総数である。
【００６５】
ナンス付き暗号化
前述したように、暗号方式がナンスを入力値として用いる場合、このナンスは同一のキー値の生成を回避するように設計される。例えば、図２２において、暗号化装置は、キーシーケンス生成器ＫＳへのナンス入力端を有する。このナンス値は、１からｎまでの計数を行うカウンタＣＴ１により生成される。ここに、ｎは暗号化されるべき平文ブロックの個数である。したがって、ナンスは、暗号化されるべき各平文ブロックに対して一意な値を有する。
【００６６】
有利なことには、もし、ナンスシーケンスが容易に予言できるならば、並列計算が容易となる。例えば、図２３において、並列計算は、２個の独立したキーストリーム生成器ＫＳ１およびＫＳ２により実現される。各カウンタＣＴ１，ＣＴ２は、ブロック番号ｉと同期化されるが、２ブロック毎に１回インクリメントされる。その際、一方のカウンタＣＴ１は、ＫＳ１を駆動して、ブロックシーケンスＳ（１），Ｓ（３），Ｓ（５）・・・Ｓ（ｎ−１）を生成させ、他方のカウンタＣＴ２は、ＫＳ２を駆動して、ブロックシーケンスＳ（２），Ｓ（４），Ｓ（５）・・・Ｓ（ｎ）を生成させる。切り替え（スイッチング）要素ＳＷは、関数ＭＸにより各平文ブロックＰ（ｉ）が正しいブロックＳ（ｉ）と混合されて暗号文ブロックＣ（ｉ）が生成されるように、ＫＳ１とＫＳ２とを切り替える。この切り替え機能の速度は、中間キー生成ステップの速度より大きいので、動作速度の全般的な増加が得られる。この方式を一般化することにより、複数のキーストリーム生成器ＫＳｉ（ｉ＝１，・・・，ｒ）を用いる、倍数ｒの並列計算を実現することができる。その各キーストリーム生成器は、S(((j-1)×ｒ）＋１）のみを生成する。ここに、j=1,...,n/rであり、”×”は整数の乗算を表す。
【００６７】
図２４において、キーストリーム生成器ＫＳ１へのナンス入力Ｎ１を用いて生成された疑似ランダムシーケンスＳ１は、第２のキーストリーム生成器ＫＳ２への入力として用いることができる。ＫＳ２は、第２のナンス入力Ｎ２を受けて、第２のシーケンスＳ２を生成する。よって、２つの中間キーＳ１，Ｓ２が得られる。図２４の構成は、図２５に示したようなディスク暗号化システムとして利用できる。ＫＳ１は、秘密キー(secret key)Ｋとナンス入力Ｎ１とからファイル依存キーＳ１を生成する。これは、時刻スタンプ付きのファイル名と、そのファイルの所有者の識別子との結合したものである。ＫＳ２は、キーＳ１を受け取り、中間キーＳ２を生成する。関数ＭＸがこのキーＳ２を用いることにより、元のファイルデータが暗号化される。これによって、単一のキーで暗号化されたディスク上のセキュリティが増加する。なぜなら、この暗号キーＳ１は、ファイル毎に異なり、マスターキーＫは暗号化サイトで秘密に保持されるからである。
【００６８】
本発明による暗号化および復号装置並びに技術の種々の応用例について、以下に図２６から図３３を参照して説明する。
【００６９】
図２６では、通信システムにおける受信者と送信者とがキーおよび同期カウンタＣＴ１，ＣＴ２を共有することにより、ＫＳは受信者と送信者とで同じ値を生成する。その結果、暗号化された各平文ブロックＣ（ｉ）は、それに対する逆混合関数ＭＸ-1の処理により復号することができる。
【００７０】
図２７において、図２６の通信システムのための暗号方式はソフトウェアで実現できる。送信者と受信者は、例えばOtway-Rees, Kerberosまたは公開キー暗号の場合のDiffie-Hellmanのような既知のキー交換プロトコルを用いて、キーおよび同期カウンタ値を交換する。この詳細は、Bruce Schneierによる"Applied Cryptography"、第２版、５９〜６０頁を参照されたい。図２６に示して上述したＫＳおよびＭＸ関数を実現するための暗号化プログラムコードはメモリＳＭＥＭに格納されている。送信者のＣＰＵは、この暗号化コードを実行することによりメッセージの暗号化を行う。この暗号化されたメッセージは送信者のＩ／Ｏ装置を経由してネットワークＩＮＥＴ上を伝送され、受信者のＩ／Ｏ装置により受信され、復号コードを実行する受信側ＣＰＵにより復号される。この復号コードは、メッセージを復元するものとして前述したＫＳおよびＭＸ-1を実現し、メモリＲＭＥＭに格納されている。ソフトウェアによる実現は、パーソナルコンピュータ、スマートカード、ネットワークルータのような広範な装置への使用、およびカーセキュリティデバイスのような装置のための遠隔コントローラに適している。
【００７１】
図２８において、暗号化および復号化は、例えば、送信側および受信側のＩ／Ｏ装置内に埋め込まれた専用のハードウェア回路としても実現できる。暗号化回路Ｅは、前述したＫＳおよびＭＸ関数を実現する一方、復号回路Ｄは、前述したＫＳおよびＭＸ-1関数を実現する。送信側ＣＰＵは、送信側Ｉ／Ｏ装置へ平文メッセージを送る。このメッセージは、暗号化回路Ｅによりキーおよびカウンタ値を用いて暗号化される。これは、キー交換プロトコルを用いて、通信に先立ち受信側との間で共有されている。暗号化されたメッセージはネットワークＩＮＥＴを経由して送信され、受信側のＩ／Ｏ装置により受信される。このメッセージは、埋め込み復号回路Ｄにより復号され、受信側ＣＰＵによりメモリ内に格納される。専用ハードウェア暗号化／復号回路は、高級スマートカード、スマートカードリーダ、モバイル端末、パーソナルコンピュータ、テレビ、ＤＶＤプレーヤ、等の装置に利用される。
【００７２】
図２９において、放送システムでは、放送局ＢＳＴＮが、番組キーとナンスとを生成する。このナンスは、番組識別子と、その番組が数フレームに分割される際のコンテンツデータのフレーム番号とからなる。このコンテンツデータは、当該キーおよびナンスを用いて暗号化される。例えばデジタルテレビのような需要者装置へキーを送信するためにはキー交換プロトコルが使用される。これは、逆復号関数ＭＸ-1を含んでいる。当該キーと番組識別子と需要者が視聴を希望する番組のフレーム番号とを知ることにより、需要者装置は番組を復号することができる。放送局にあるキーサーバーは、フレーム情報に基づいて中間キーを生成することができる。これにより、番組中に中間フレームキーが需要者装置へ送られる。番組全体を受信するには、第三者はすべてのフレームキーを暗号解読する必要がある。
【００７３】
図３０において、キーの秘匿性を向上させるにはナンスを用いることができる。２つの装置間での最初のキー交換は、キーとナンスの両方を交換する必要がある。しかし、例えばデータの次のフレームを得るためにそのキー値を更新するときには、ナンスだけを交換すればよい。よって、秘密キー（secret key)は１回だけ交換すればよいが、ナンスは、たとえそれが知られてもシステムのセキュリティを低下させることなく、繰り返して交換されうる。システムが、例えばフレーム番号に追従するカウンタのようなナンス更新方法を有する場合、最初のナンスはフレーム同期化のためにのみ必要とされるが、その後のナンスは送信する必要はない。
【００７４】
図３１における、図２５により説明したようなディスク暗号化システムの実現例では、ファイルは異なるキーで暗号化される。その際、各ナンスは、時刻スタンプ付きファイル名と所有者の識別子からなる。ＣＰＵは、メモリＤＭＥＭに格納され、図２５により説明された暗号化アルゴリズムを実行する。秘密キーは、暗号化システムの操作者がスマートカード上に保持する。
【００７５】
図３２は、図２５により説明した暗号化アルゴリズムの、データベース暗号化システムへの他の応用例を示す。このシステムでは、ナンスは、ＩＤと、カテゴリと、改訂番号(revision number)または時刻スタンプとからなる。
【００７６】
図３３は、図２５により説明した暗号化アルゴリズムの、マルチメディア配信システムの用途への他の応用例を示す。ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ上の内容は、秘密キーＫとナンスＮ１とを用いて暗号化される。このナンスは、例えば、日付つきの番組名とバージョン番号とを連結したものである。例えば、図３４においては、幾つかの番組がＤＶＤ−ＲＯＭ上に暗号化される。各番組は、それ自身のキーＳ１の基でマスタキーＫとナンスＮ１とを用いて暗号化される。このナンスＮ１は、ＤＶＤ−ＲＯＭ上の各フィルム（映画）に対して一意である。ＤＶＤ−ＲＯＭのコピーは、無料で需要者へ配信される。需要者は、暗号化されたディスク上のフィルムの１つを再生したい場合、その需要者の要求でキーサーバＫＳ１にコンタクトし、例えばインターネット上でクレジットカードによる適切な支払いをする。キーサーバＫＳ１は、マスタキーＫと番組名と、さらにナンスＮ１を構成するキーサーバに格納されている他のデータとから、その需要者へ送信すべきキーＳ１を算出する。そこで、キー交換プロトコルが開始され、その需要者の装置が適切な中間キーＳ１を受信する。図３５において、需要者の装置は、キーストリーム生成器ＫＳ２への入力として当該キーＳ１を用いて、正しい中間キーＳ２を生成する。したがって、図３３を再度参照すると、要求されたフィルムは、図３５に示した機能を実現するメモリＣＭＥＭ内に格納されている復号プログラムコードを需要者のＣＰＵが実行することにより復元されうる。
【図面の簡単な説明】
【図１】  対称暗号化システムの既知の構成を示す概略ブロック図である。
【図２】  本発明による暗号化装置の基本構成を示す概略ブロック図である。
【図３】  図２に示したキーストリーム生成器ＫＳの一実現例を示す概略ブロック図である。
【図４】  図２に示したキーストリーム生成器ＫＳの他の実現例を示す概略ブロック図である。
【図５】  本発明による復号装置の基本構成を示す概略ブロック図である。
【図６】  データ保全性を検証するためのメッセージフォーマットを示すブロック図である。
【図７】  図２の暗号化装置の動作を説明するためのフロー図である。
【図８】  本発明による暗号文ブロックの生成を説明するための図である。
【図９】  図５の復号装置の動作を説明するためのフロー図である。
【図１０】  混合関数ＭＸの一例を示す概略ブロック図である。
【図１１】  図１０に示した混合関数ＭＸのさらに詳細な実現例を示す概略ブロック図である。
【図１２】  フィードバック付きの混合関数ＭＸの実現例を示す概略ブロック図である。
【図１３】  フィードバック付きの混合関数ＭＸの実現例を示す概略ブロック図である。
【図１４】  フィードバック付きの混合関数ＭＸの他の実現例を示す概略ブロック図である。
【図１５】  フィードバック付きの混合関数ＭＸの他の実現例を示す概略ブロック図である。
【図１６】  フィードバック付きの混合関数ＭＸの他の実現例を示す概略ブロック図である。
【図１７】  フィードバック付きの混合関数ＭＸの他の実現例を示す概略ブロック図である。
【図１８】  フィードバック付きの混合関数ＭＸの他の実現例を示す概略ブロック図である。
【図１９】  フィードバック付きの混合関数ＭＸの他の実現例を示す概略ブロック図である。
【図２０】  図１０に示した混合関数ＭＸに対応する逆混合関数ＭＸ-1の一例を示す概略ブロック図である。
【図２１】  図２０に示した逆混合関数ＭＸ-1のより詳細な実現例を示すブロック図である。
【図２２】  ナンス入力としてのカウンタを有する暗号化装置を示すブロック図である。
【図２３】  並列計算のためのモデルを示すブロック図である。
【図２４】  ＫＳ機能の拡張を説明するためのブロック図である。
【図２５】  ディスク暗号化システムとしての図２４の装置の応用例を示す図である。
【図２６】  通信システムに応用された、ナンスを有する暗号化の一例を示す図である。
【図２７】  図２６の暗号方式のソフトウエアによる実現例を示す図である。
【図２８】  図２６の暗号方式のハードウェアによる実現例を示す図である。
【図２９】  放送に用いられる暗号化システムの一例を示す図である。
【図３０】  ナンスを用いるキー交換を制限することによりキーの秘匿性を向上させる方法を示す概略ブロック図である。
【図３１】  ディスク暗号化システムの一例を示す図である。
【図３２】  データベース暗号化システムの一例を示す図である。
【図３３】  マルチメディア配送システムの一例を示す図である。
【図３４】  図３３のマルチメディアシステム用の暗号ソフトウェアの概略図である。
【図３５】  図３３のマルチメディア配送システムとともに用いるべき需要者装置のための復号ソフトウェアの概略図である。
【符号の説明】
Ｃ  暗号文
Ｄ  復号化
Ｅ  暗号化
Ｆ  フィードバック
Ｋ  キー
Ｎ  ナンス
Ｐ  平文
【図１】
0003901909.tif 000002
【図２】
0003901909.tif 000003
【図３】
0003901909.tif 000004
【図４】
0003901909.tif 000005
【図５】
0003901909.tif 000006
【図６】
0003901909.tif 000007
【図７】
0003901909.tif 000008
【図８】
0003901909.tif 000009
【図９】
0003901909.tif 000010
【図１０】
0003901909.tif 000011
【図１１】
0003901909.tif 000012
【図１２】
0003901909.tif 000013
【図１３】
0003901909.tif 000014
【図１４】
0003901909.tif 000015
【図１５】
0003901909.tif 000016
【図１６】
0003901909.tif 000017
【図１７】
0003901909.tif 000018
【図１８】
0003901909.tif 000019
【図１９】
0003901909.tif 000020
【図２０】
0003901909.tif 000021
【図２１】
0003901909.tif 000022
【図２２】
0003901909.tif 000023
【図２３】
0003901909.tif 000024
【図２４】
0003901909.tif 000025
【図２５】
0003901909.tif 000026
【図２６】
0003901909.tif 000027
【図２７】
0003901909.tif 000028
【図２８】
0003901909.tif 000029
【図２９】
0003901909.tif 000030
【図３０】
0003901909.tif 000031
【図３１】
0003901909.tif 000032
【図３２】
0003901909.tif 000033
【図３３】
0003901909.tif 000034
【図３４】
0003901909.tif 000035
【図３５】
0003901909.tif 000036