(57)【要約】数学的システムにおいて数値計算を実行する方法は、この数学的システムを複数の離散的な項で表現することと、計算に固定小数点の変数を使用することと、数値のディジットのうちのサブセットを抽出することとを含む。ディジットのサブセットは、乱数又は擬似乱数を表現することが可能である。当該数学的システムは、カオス的システムのような、例えば正のリヤプノフ指数を有するシステムのような、複数の非線形微分方程式にてなるシステムであるか、あるいは、ロジスティックマップ、アノーソフ又はエノンマップのような離散的マッピングであることが可能である。本方法は、ストリーム暗号及びブロック暗号を含む暗号化及び復号化アルゴリズムと、ディジタル署名を発生するシステムと、ハッシュ関数と、ＭＡＣ（メッセージ認証コード）関数とに適用可能である。当該数学的システムに対する解の周期的な挙動に対するテストが提供される。
2004530919.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法であって、当該方法は、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップとを含み、上記結果として得られる数は、
−  ａ．上記数学的システムに対する解の少なくとも一部と、
−  ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
当該方法はさらに、
−  ｉ．上記結果として得られる数のディジットのうちのサブセットと、
−  ｉｉ．上記結果として得られる数から導出された数のディジットのうちのサブセットと
の少なくとも一方を表現するデータのセットを抽出するステップを含む方法。
【請求項２】
上記データのセットは擬似乱数を表現する請求項１記載の方法。
【請求項３】
上記計算は少なくとも第１及び第２の固定小数点の数を含み、各固定小数点の数は小数点分離記号を有し、上記第１の固定小数点の数の小数点分離記号は上記第２の固定小数点の数の小数点分離記号の位置とは異なる位置に位置決めされる請求項１又は２記載の方法。
【請求項４】
上記計算を実行するステップは、上記第１及び第２の固定小数点の数の小数点分離記号を、選択された位置に位置決めすることを含む請求項３記載の方法。
【請求項５】
上記少なくとも１つの関数は非線形である請求項１乃至４のうちの任意の請求項に記載の方法。
【請求項６】
上記結果として得られる数は、
−  整数と、
−  浮動小数点の数と、
−  固定小数点の数と
で構成されるグループから選択された変数として表現される先行する請求項のうちの任意の請求項に記載の方法。
【請求項７】
上記数学的システムは、
−  微分方程式と、
−  離散的マッピングと
の少なくとも一方を含む先行する請求項のうちの任意の請求項に記載の方法。
【請求項８】
上記微分方程式は、
−  偏微分方程式と、
−  常微分方程式と
の少なくとも一方を含む請求項７記載の方法。
【請求項９】
上記離散的マッピングは、
−  領域を保存するマップと、
−  領域を保存しないマップと
の少なくとも一方を含む請求項７記載の方法。
【請求項１０】
上記数学的システムは、少なくとも１つの状態変数Ｘを決定する少なくとも１つの非線形関数を含む請求項７又は９記載の方法。
【請求項１１】
上記数学的システムは、複数の非線形マッピング関数にてなるセットを含む請求項１０記載の方法。
【請求項１２】
上記マップは、
−  次式の形式を有するロジスティックマップと、
【数１】
2004530919.tif 000076
−  次式の形式を有するアノーソフマップと、
【数２】
2004530919.tif 000077
−  次式の形式を有するエノンマップと
【数３】
2004530919.tif 000078
のうちの少なくとも１つを含む請求項９乃至１１のうちの任意の請求項に記載の方法。
【請求項１３】
上記数学的システムは少なくとも１つの非線形微分方程式を含む請求項１乃至８のうちの任意の請求項に記載の方法。
【請求項１４】
上記数学的システムは、複数の非線形微分方程式にてなるセットを含む請求項１３記載の方法。
【請求項１５】
上記数学的システムは少なくとも１つの正のリヤプノフ指数を有する請求項７乃至１４のうちの任意の請求項に記載の方法。
【請求項１６】
数学的計算の間に少なくとも１回だけ少なくとも１つのリヤプノフ指数を計算することを含む請求項７乃至１４のうちの任意の請求項に記載の方法。
【請求項１７】
上記少なくとも１つの非線形微分方程式は、少なくとも１つの独立変数ｔの関数である少なくとも１つの状態変数Ｘを決定する請求項１３乃至１６のうちの任意の請求項に記載の方法。
【請求項１８】
上記複数の非線形微分方程式にてなるセットはローレンツシステムである請求項１４乃至１７のうちの任意の請求項に記載の方法。
【請求項１９】
上記ローレンツシステムは、次式の微分方程式、
【数４】
2004530919.tif 000079
【数５】
2004530919.tif 000080
【数６】
2004530919.tif 000081
から構成され、Ｘ＝（ｘ，ｙ，ｚ）は状態変数であり、ｔは独立変数であり、σ、ｒ及びｂはパラメータである請求項１８記載の方法。
【請求項２０】
上記計算を実行するステップは、少なくとも１つの以前の解Ｘｍ，ｍ≦ｎ＋１と、独立変数ｔのステップ長ΔＴｎとに基づいて解Ｘｎ＋１を反復して計算することにより、
−  上記非線形微分方程式と、
−  上記複数の非線形微分方程式にてなるセットのうちの上記複数の非線形微分方程式との少なくとも一方を数値積分することを含む請求項１３乃至１９のうちの任意の請求項に記載の方法。
【請求項２１】
上記積分するステップは、上記状態変数Ｘの少なくとも１つの初期条件Ｘ０とステップ長の初期値ΔＴ０とを提供することを含む請求項２０記載の方法。
【請求項２２】
上記計算を実行するステップは、上記非線形マッピング関数を数値的に反復することを含む請求項１０乃至１２のうちの任意の請求項に記載の方法。
【請求項２３】
上記反復するステップは上記状態変数Ｘの少なくとも１つの初期条件Ｘ０を提供することを含む請求項２２記載の方法。
【請求項２４】
上記ローレンツシステムの離散化された定式化において、解Ｘｎ＋１は、ステップ長ΔＴ＝（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）を使用して、
【数７】
2004530919.tif 000082
【数８】
2004530919.tif 000083
【数９】
2004530919.tif 000084
のように計算され、
Δｔｘ，ｎはｘｎ＋１の計算に使用されるステップ長であり、
Δｔｙ，ｎはｙｎ＋１の計算に使用されるステップ長であり、
Δｔｚ，ｎはｚｎ＋１の計算に使用されるステップ長である請求項２０又は２１記載の方法。
【請求項２５】
上記ステップ長ΔＴは上記計算を通じて一定である請求項２０乃至２４のうちの任意の請求項に記載の方法。
【請求項２６】
各積分ステップにおいて、上記ステップ長ΔＴの要素（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）のうちの少なくとも１つは、上記計算に関連する少なくとも１つの数の関数である請求項２０乃至２５のうちの任意の請求項に記載の方法。
【請求項２７】
各積分ステップにおいて、上記ステップ長ΔＴの要素（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）のうちの少なくとも１つは、上記数学的システムに対する解である少なくとも１つの解Ｘｍの関数である請求項２６記載の方法。
【請求項２８】
各積分ステップにおいて、上記ステップ長ΔＴの要素（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）のうちの少なくとも１つは、少なくとも１つの与えられたステップ長ΔＴｍの関数である請求項２６又は２７記載の方法。
【請求項２９】
暗号化鍵及び復号化鍵から選択される鍵は、上記数学的システムにおける少なくとも１つの変数の少なくとも１つの値を決定するために使用される先行する請求項のうちの任意の請求項に記載の方法。
【請求項３０】
上記鍵は上記初期条件Ｘ０の少なくとも一部を決定するために使用される請求項２９記載の方法。
【請求項３１】
上記鍵は上記ステップ長の初期値ΔＴ０の少なくとも一部を決定するために使用される請求項２９又は３０記載の方法。
【請求項３２】
上記鍵は少なくとも１つのパラメータの少なくとも一部を決定するために使用される請求項２９乃至３１のうちの任意の請求項に記載の方法。
【請求項３３】
上記鍵は公開鍵である請求項２９乃至３２のうちの任意の請求項に記載の方法。
【請求項３４】
上記鍵は秘密鍵である請求項２９乃至３２のうちの任意の請求項に記載の方法。
【請求項３５】
上記計算から結果として得られる複数の数を抽出することを含む先行する請求項のうちの任意の請求項に記載の方法。
【請求項３６】
上記抽出するステップは、上記結果として得られる数のｋビットから導出された少なくとも１つの数を抽出することを含む先行する請求項のうちの任意の請求項に記載の方法。
【請求項３７】
上記抽出するステップは、上記結果として得られる数の最下位のｋビットを抽出することを含む先行する請求項のうちの任意の請求項に記載の方法。
【請求項３８】
ｋは８、１６、３２、６４及び１２８よりなるグループから選択された値である請求項３６又は３７記載の方法。
【請求項３９】
複数の数が抽出される請求項３６乃至３８のうちの任意の請求項に記載の方法。
【請求項４０】
上記抽出されたデータのセットは、
−  算術演算と、
−  論理演算と
の少なくとも一方によって操作され、結合されたデータのセットを取得する、先行する請求項のうちの任意の請求項に記載の方法。
【請求項４１】
−  上記抽出されたデータのセットと、
−  上記結合されたデータのセットと
の少なくとも一方は元のデータと結合され、上記元のデータが暗号化される請求項４０記載の方法。
【請求項４２】
−  抽出されたデータのセットと、
−  上記結合されたデータのセットと
の少なくとも一方は暗号化されたデータと結合され、上記暗号化されたデータが復号化されて元のデータが取得される請求項４０記載の方法。
【請求項４３】
上記データを結合することはＸＯＲ演算を含む請求項４０乃至４２のうちの任意の請求項に記載の方法。
【請求項４４】
上記計算は、ブロック暗号の暗号化及び復号化システムにおいて平文のブロックを表現するデータに対して作用する、先行する請求項のうちの任意の請求項に記載の方法。
【請求項４５】
上記抽出されたデータのセットは、ブロック暗号の暗号化及び復号化システムにおいて、平文のブロックに対する少なくとも１つの演算を定義するために使用される先行する請求項のうちの任意の請求項に記載の方法。
【請求項４６】
上記データを結合することは、暗号化のための上記元のデータと上記結合されたデータのセットとの加算を含み、かつ復号化のための上記暗号化されたデータからの上記結合されたデータのセットの減算を含む請求項４１乃至４５のうちの任意の請求項に記載の方法。
【請求項４７】
上記データを結合することは、暗号化のための上記元のデータからの上記結合されたデータのセットの減算を含み、かつ復号化のための上記結合されたデータのセットと上記暗号化されたデータとの加算を含む請求項４１乃至４５のうちの任意の請求項に記載の方法。
【請求項４８】
上記抽出されたデータのセットは、暗号化鍵及び復号化鍵の少なくとも一方として使用される請求項１乃至４７のうちの任意の請求項に記載の方法。
【請求項４９】
上記抽出されたデータのセットは、暗号化鍵及び復号化鍵の少なくとも一方を発生するために使用される請求項１乃至４７のうちの任意の請求項に記載の方法。
【請求項５０】
上記抽出されたデータのセットは、ディジタル署名を表現するデータの発生に使用される先行する請求項のうちの任意の請求項に記載の方法。
【請求項５１】
上記抽出されたデータのセットは、ディジタルデータへの電子透かしの埋め込みに使用される先行する請求項のうちの任意の請求項に記載の方法。
【請求項５２】
上記計算は、所定のレジスタ幅を有する電子処理装置を備えた電子装置上で実行される先行する請求項のうちの任意の請求項に記載の方法であって、
−  上記レジスタ幅より大きいビット幅の少なくとも１つの整数を、高々上記レジスタ幅に等しいビット幅をそれぞれ有する少なくとも２つのサブナンバーとして表現するステップと、
−  上記計算の少なくとも１つを上記サブナンバーの各々に対するサブ計算として実行し、高々上記処理装置のレジスタ幅に等しい、より小さなビット幅の整数として表された少なくとも２つの部分的結果に到達するステップと、
−  上記部分的結果を連結して、上記少なくとも１つの計算の結果の表現を発生させるステップとを含む方法。
【請求項５３】
少なくとも１つの関数を含む数学的システムにおいて数値計算を実行するコンピュータプログラムであって、当該コンピュータプログラムは、
−  数学的システムの少なくとも１つの変数を固定小数点の数として表現することと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行することと、
−  上記計算から、結果として得られる数を取得することとに適応化され、上記結果として得られる数は、
−  ａ．上記数学的システムに対する解の少なくとも一部と、
−  ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
当該コンピュータプログラムはさらに、
−  ｉ．上記結果として得られる数のディジットのうちのサブセットと、
−  ｉｉ．上記結果として得られる数から導出された数のディジットのうちのサブセットと
の少なくとも一方を表現するデータのセットを抽出することに適応化されたコンピュータプログラム。
【請求項５４】
請求項５３記載のコンピュータプログラムがロードされた、コンピュータが読み取り可能なデータキャリア。
【請求項５５】
請求項５４記載のコンピュータが読み取り可能なデータキャリアに動作可能に接続されたコンピュータであって、上記プログラムを実行するプロセッサ手段を備えたコンピュータ。
【請求項５６】
数学的システムにおける計算から導出されている抽出されたデータのセットを含む信号であって、上記抽出されたデータのセットに到達することを目的として、
−  上記数学的システムは複数の離散的な項で表現され、
−  上記数学的システムの少なくとも１つの変数は固定小数点の数として表現され、
−  上記計算は、固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように実行され、かつ、
−  結果として得られる数は上記計算から取得され、上記結果として得られる数は、
−  ａ．上記数学的システムに対する解の少なくとも一部と、
−  ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
それによって、上記抽出されたデータのセットは、
−  ｉ．上記結果として得られる数のディジットのうちのサブセットと、
−  ｉｉ．上記結果として得られる数から導出された数のディジットのうちのサブセットと
の少なくとも一方を表現する信号。
【請求項５７】
平文と、数学的システムにおける計算から抽出された少なくとも１つのデータのセットとの組み合わせとして導出されている暗号化されたデータのセットを含む信号であって、上記抽出されたデータのセットに到達することを目的として、
−  上記数学的システムは複数の離散的な項で表現され、
−  上記数学的システムの少なくとも１つの変数は固定小数点の数として表現され、
−  上記計算は、固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように実行され、かつ、
−  結果として得られる数は上記計算から取得され、上記結果として得られる数は、
−  ａ．上記数学的システムに対する解の少なくとも一部と、
−  ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
それによって、上記抽出されたデータのセットは、
−  ｉ．上記結果として得られる数のディジットのうちのサブセットと、
−  ｉｉ．上記結果として得られる数から導出された数のディジットのうちのサブセットと
の少なくとも一方を表現する信号。
【請求項５８】
少なくとも１つの独立変数に関連した少なくとも１つの状態変数を決定する少なくとも１つの非線形関数を含む数学的システムに対する解における周期的な挙動を検出する方法であって、当該方法は、
−  上記数学的システムを複数の離散的な項で表現することと、
−  電子装置において計算を実行して、結果として得られる数を取得することとを含み、上記結果として得られる数は上記数学的システムに対する解の少なくとも一部を表現し、
当該方法は、
−  選択された解を上記電子装置のメモリにおけるアレーＡに記憶することを含み、上記アレーは有限個数ｎ＋１個の解を記憶するように適応化され、
当該方法は、
−  現在の解と、
−  上記アレーに記憶された上記解の特定の１つと
の少なくとも一方が、上記アレーに記憶された他の解と実質的に同一であるか否かを決定することを含む方法。
【請求項５９】
選択された解のみが上記メモリに記憶される請求項５８記載の方法。
【請求項６０】
上記アレーにおける各エントリは、アレーレベルＡｉ，０≦ｉ≦ｎ毎に増大している経過時間を有する解を含む請求項５８又は５９記載の方法であって、
−  選択された解を上記アレーに記憶する上記ステップにおいて、現在の解をアレーＡにおける０番目のレベルに記憶し、これにより、上記アレーＡにおける０番目のレベルで記憶された古い値に上書きすることと、
−  ０番目の予め決められた基準が満たされているとき、上記０番目のレベルが上記現在の解によって上書きされる前に上記古い値を上記アレーＡにおける１番目のレベルへ移動することとを含み、
上記アレーにおける第１のレベル及びそれ以上の各レベルｉに対しては、
−  レベルｉに対するｉ番目の予め決められた基準が満たされているとき、ｉ番目のレベルがｉ−１番目のレベルから移動される値によって上書きされる前に、ｉ番目のレベルで記憶された古い値を上記アレーＡにおけるｉ＋１番目のレベルへ移動することを含み、
ｎ番目のレベルが更新されるとき、ｎ番目のレベルで以前に記憶された古い値を廃棄することを含む方法。
【請求項６１】
上記アレー内の各レベルｉに対して、ｉ番目のレベルに記憶された古い値がｉ＋１番目のレベルへ移動されることなく上記古い値が新しい値によって上書きされている回数を計数することをさらに含み、予め決められた回数だけ古い値が移動されなかったときにｉ番目の予め決められた基準は満たされる請求項６０記載の方法。
【請求項６２】
上記予め決められた回数は、上記アレーＡのすべてのレベルで同一である請求項６１記載の方法。
【請求項６３】
上記予め決められた回数は、上記アレーＡの各レベル間で変化する請求項６１記載の方法。
【請求項６４】
上記アレーＡのｉ番目のレベルに対する上記予め決められた回数は、上記アレーに記憶された少なくとも１つの値に依存する請求項６１又は６３記載の方法。
【請求項６５】
上記決定するステップは所定のテスト基準が満たされたときのみ実行される請求項５８乃至６４のうちの任意の請求項に記載の方法。
【請求項６６】
上記テスト基準は、少なくとも１つの状態変数の符号が変化するときに満たされる請求項６５記載の方法。
【請求項６７】
上記少なくとも１つの独立変数の１つに関して少なくとも１つの状態変数の少なくとも１つの導関数を計算することをさらに含み、上記テスト基準は、上記少なくとも１つの導関数の符号の変化が発生するときに満たされる請求項６６記載の方法。
【請求項６８】
テスト値を、
−  上記少なくとも１つの状態変数と、
−  上記導関数と
の少なくとも一方から計算することをさらに含み、上記テスト基準は上記テスト値に基づく請求項６６及び６７記載の方法。
【請求項６９】
擬似乱数を発生する方法であって、当該方法は、
Ｉ）数学的システムを複数の離散的な項で表現することと、
ＩＩ）上記数学的システムの少なくとも初期条件を表現するシード値を定義することと、
ＩＩＩ）上記数学的システムの少なくとも１つの変数を固定小数点の数として表現することと、
ＩＶ）電子装置において、固定小数点の数として表現された上記少なくとも１つの変数を含む計算を実行し、かつ上記計算から、結果として得られる数を取得し、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
当該方法は、
Ｖ）上記計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出することを含む方法。
【請求項７０】
上記擬似乱数は、上記計算の間に発生した上記少なくとも１つの数のｋ個のディジットから導出された数として抽出される請求項６９記載の方法。
【請求項７１】
上記擬似乱数は、上記少なくとも１つの数の最下位のｋ個のディジットから導出された数として抽出される請求項７０記載の方法。
【請求項７２】
所定量の擬似乱数が発生されるまでステップＩＶ）及びステップＶ）を反復するステップを含む請求項６９乃至７１のうちの任意の請求項に記載の方法。
【請求項７３】
スペアのシード値として、所定量の擬似乱数が発生されて上記電子装置のメモリに記憶される請求項６９乃至７２のうちの任意の請求項に記載の方法。
【請求項７４】
請求項５８乃至６８のうちの任意の請求項に記載のステップをさらに含む請求項６９乃至７３のうちの任意の請求項に記載の方法であって、
上記決定するステップが、
−  現在の解と、
−  特定の解と
の少なくとも１つが他の解と同一であることを示すとき、
上記擬似乱数の発生を中断する、すなわちステップＩＶ）及びステップＶ）の反復を中断することと、
上記スペアのシード値をステップＩＩ）においてシード値として使用することと、
上記擬似乱数の発生を再開する、すなわちステップＩＶ）及びステップＶ）の反復を再開することとを含む方法。
【請求項７５】
上記擬似乱数の発生を再開するステップに先行して、新たなスペアのシード値として、所定量の擬似乱数を発生して上記電子装置のメモリに記憶することをさらに含む請求項７４記載の方法。
【請求項７６】
ステップＩＶ）及びステップＶ）がステップＩＩ）における新たなシード値を用いて開始されると、アレーＡの各レベルはステップＩＶ）に先行してリセットされる請求項６９乃至７５のうちの任意の請求項に記載の方法。
【請求項７７】
請求項１乃至４７のうちの任意の請求項に記載のステップをさらに含む請求項６９乃至７６のうちの任意の請求項に記載の方法。
【請求項７８】
元のデータのセットを、暗号化されたデータにセットに暗号化する方法であって、
Ａ）以下のステップ、すなわち、
Ｉ）数学的システムを複数の離散的な項で表現するステップと、
ＩＩ）上記数学的システムの少なくとも初期条件を表現する暗号化鍵を定義するステップと、
ＩＩＩ）上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
ＩＶ）固定小数点の数として表現された上記少なくとも１つの変数を含む計算を実行し、かつ、上記計算から、結果として得られる数を取得するステップであって、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現するステップと
Ｖ）上記計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出するステップと
を実行することによって、擬似乱数を発生するステップと、
Ｂ）上記元のデータ及び上記擬似乱数を、
ｉ．算術演算と、
ｉｉ．論理演算と
の少なくとも一方によって操作し、結合されたデータのセットを取得するステップとを含み、上記結合されたデータのセットは暗号化されたデータである方法。
【請求項７９】
ステップＡ）に先行して、上記元のデータのサブセットが上記データのセットから分離され、ステップＢ）は上記データのサブセットに対して実行される請求項７８記載の方法。
【請求項８０】
請求項６０記載のステップをさらに含み、上記元のデータのセット全体を共同で構成する複数のサブセットが暗号化されるまで上記請求項６０記載のステップを反復する請求項７９記載の方法。
【請求項８１】
上記擬似乱数は、計算の間に発生した上記少なくとも１つの数のｋ個のディジットから導出された数として抽出される請求項７８乃至８０のうちの任意の請求項に記載の方法。
【請求項８２】
上記擬似乱数は、計算の間に発生した上記少なくとも１つの数の最下位のｋ個のディジットから導出された数として抽出される請求項７８乃至８０のうちの任意の請求項に記載の方法。
【請求項８３】
所定量の擬似乱数が発生されるまでステップＩＶ）及びステップＶ）を反復するステップを含む請求項７８乃至８２のうちの任意の請求項に記載の方法。
【請求項８４】
スペアの暗号化鍵として、所定量の擬似乱数が発生されて上記電子装置のメモリに記憶される請求項８０乃至８３のうちの任意の請求項に記載の方法。
【請求項８５】
請求項５８乃至６８のうちの任意の請求項に記載のステップをさらに含む請求項８４記載の方法であって、
上記決定するステップが、
−  現在の解と、
−  特定の解と
の少なくとも１つが他の解と同一であることを示すとき、
−  上記擬似乱数の発生を中断する、すなわちステップＩＶ）及びステップＶ）の反復を中断することと、
−  上記スペアの暗号化鍵をステップＩＩ）において暗号化鍵として使用することと、
−  上記擬似乱数の発生を再開する、すなわちステップＩＶ）及びステップＶ）の反復を再開することとを含む方法。
【請求項８６】
上記擬似乱数の発生を再開するステップに先行して、新たなスペアの暗号化鍵として、所定量の擬似乱数を発生して上記電子装置のメモリに記憶することをさらに含む請求項８５記載の方法。
【請求項８７】
ステップＩＶ）及びステップＶ）がステップＩＩ）における新たなシード値を用いて開始されると、アレーＡの各レベルはステップＩＶ）に先行してリセットされる請求項７８乃至８６のうちの任意の請求項に記載の方法。
【請求項８８】
請求項１乃至４７のうちの任意の請求項及び／又は請求項５８乃至６８のうちの任意の請求項に記載のステップをさらに含む請求項７８乃至８７のうちの任意の請求項に記載の方法。
【請求項８９】
請求項７８乃至８８のうちの任意の請求項に記載の方法によって暗号化されている、暗号化されたデータのセットを復号化する方法であって、
ａ）請求項７８記載のステップＡ）を実行することで、請求項７８記載のステップＶ）において抽出されたものと同じ擬似乱数を抽出するステップと、
ｂ）上記暗号化されたデータ及び上記擬似乱数を、
−  算術演算と、
−  論理演算と
の少なくとも一方によって操作し、元のバージョンのデータ、すなわち復号化されたバージョンのデータを取得するステップとを含む方法。
【請求項９０】
ステップａ）に先行して、上記暗号化されたデータのセットから上記暗号化されたデータのサブセットが分離され、上記データのサブセットは請求項７８記載の方法によって暗号化され、
上記復号化する方法は、上記データのサブセットに対してステップａ）及びステップｂ）を実行することを含む請求項８９記載の方法。
【請求項９１】
上記暗号化されたデータのセット全体を共同で構成する複数のサブセットが復号化されるまで、請求項９０記載のステップを反復することを含む請求項９０記載の方法。
【請求項９２】
上記暗号化されたデータを復号化するときに、元のデータを暗号化する以前のシーケンスの間と同一の方法で請求項８３乃至８７のうちの任意の請求項に記載のステップを適用することをさらに含む請求項８９乃至９１のうちの任意の請求項に記載の方法。
【請求項９３】
請求項１乃至４７のうちの任意の請求項及び／又は請求項５８乃至６８のうちの任意の請求項に記載のステップをさらに含む請求項８９乃至９２のうちの任意の請求項に記載の方法。
【請求項９４】
データのセットを暗号化しかつ復号化するコンピュータプログラムであって、上記コンピュータプログラムは暗号化モード及び復号化モードで実行するように適応化され、上記コンピュータプログラムはさらに、
ｉ）以下のステップ、すなわち、
−  数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を含む計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップであって、上記結果として得られる数は、
ａ．上記数学的システムに対する解の一部と、
ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現するステップと、
−  計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出するステップと
を実行することにより、擬似乱数を再現可能な方法で発生し、
ｉｉ）上記データ及び上記擬似乱数を、
−  算術演算と、
−  論理演算と
の少なくとも一方によって操作し、結合されたデータのセットを取得するように適応化され、
−  上記コンピュータプログラムが暗号化モードで実行されている場合、上記結合されたデータのセットは上記データの暗号化されたバージョンを表現し、
上記コンピュータプログラムが復号化モードで実行されている場合、上記結合されたデータのセットは上記データの復号化されたバージョンを表現するコンピュータプログラム。
【請求項９５】
上記擬似乱数を発生するステップは、請求項１乃至４７のうちの任意の請求項に記載のステップをさらに含む請求項９４記載の方法。
【請求項９６】
上記操作するステップは、請求項７８乃至９３のうちの任意の請求項の請求項によって定義されかつ適用された操作に含まれる任意のステップを含む請求項９４又は９５記載の方法。
【請求項９７】
請求項９４乃至９６のうちの任意の請求項に記載のコンピュータプログラムがロードされた、コンピュータが読み取り可能なデータキャリア。
【請求項９８】
請求項９７記載のコンピュータが読み取り可能なデータキャリアに動作可能に接続されたコンピュータであって、上記プログラムを実行するプロセッサ手段を備えたコンピュータ。
【請求項９９】
擬似乱数を発生する方法であって、当該方法は、１つのインスタンスにおいて、
Ｉ）数学的システムを複数の離散的な項で表現することと、
ＩＩ）上記数学的システムの少なくとも初期条件を表現するシード値を定義することと、
ＩＩＩ）上記数学的システムの少なくとも１つの変数を固定小数点の数として表現することと、
ＩＶ）固定小数点の数として表現された上記少なくとも１つの変数を含む計算を実行して、結果として得られる数を取得することとを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の一部と、
ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
Ｖ）計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出することを含み、
ステップＩ）乃至Ｖ）を複数のインスタンスで並列に実行する方法。
【請求項１００】
上記複数のインスタンスのそれぞれで少なくともステップＩＶ）を実行する間に、上記複数のインスタンス間でデータを送信することを含む請求項９９記載の方法。
【請求項１０１】
上記複数のインスタンスのそれぞれでステップＶ）を実行する間に、上記複数のインスタンス間でデータを送信することをさらに含む請求項９９又は１００記載の方法。
【請求項１０２】
上記各インスタンスにおいてステップＶ）で抽出された複数の擬似乱数を、
−  算術演算と、
−  論理演算と
の少なくとも一方を使用して共通の擬似乱数に結合することを含む請求項９９乃至１０１のうちの任意の請求項に記載の方法。
【請求項１０３】
少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法であって、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップとを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現し、
上記計算を実行するステップは、
−  少なくとも１つの以前の解Ｘｍ，ｍ≦ｎ＋１に基づいて解Ｘｎ＋１を反復して計算することを含み、これにより、上記計算を実行するステップは、状態変数Ｘの少なくとも１つの初期条件Ｘ０に基づいて開始され、
当該方法はさらに、
−  暗号鍵を上記計算への入力として提供することを含み、これにより上記暗号鍵は初期条件Ｘ０の発生に使用される方法。
【請求項１０４】
データのセットを識別するための識別値を決定する方法であって、当該方法は少なくとも１つの関数を含む数学的システムにおいて数値計算を実行することを含み、当該方法は、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップであって、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現するステップとを含み、
これにより、上記データのセットの少なくとも一部の表現は上記計算において使用され、
当該方法はさらに、
−  上記結果として得られる数の少なくとも一部を上記識別値として抽出することを含む方法。
【請求項１０５】
上記計算のためのシード値として暗号鍵が使用される請求項１０４記載の方法。
【請求項１０６】
上記数学的システムは、
−  微分方程式と、
−  離散的マッピングと
の少なくとも一方を含む請求項１０４又は１０５記載の方法。
【請求項１０７】
上記微分方程式は、
−  偏微分方程式と、
−  常微分方程式と
の少なくとも一方を含む請求項１０６記載の方法。
【請求項１０８】
上記離散的マッピングは、
−  領域を保存するマップと、
−  領域を保存しないマップと
の少なくとも一方を含む請求項１０６記載の方法。
【請求項１０９】
上記数学的システムは、少なくとも１つの状態変数Ｘを決定する少なくとも１つの非線形関数を含む請求項１０６又は１０８記載の方法。
【請求項１１０】
上記非線形マッピング関数は、ｘｎ＋１＝λｘｎ（１−ｘｎ）の形式のロジスティックマップを含み、λはパラメータであり、ｘｎ＋１は上記計算の（ｎ＋１）番目のステージにおける状態変数ｘの値であり、ｘｎは上記計算のｎ番目のステージにおける状態変数ｘの値である請求項１０９記載の方法。
【請求項１１１】
上記ロジスティックマップはｘｎ＋１＝λｘｎ（１−ｘｎ）＋ε（ｘｎ−ｍｎ）の形式に変形され、λ及びεはパラメータであり、ｘｎ＋１は上記計算の（ｎ＋１）番目のステージにおける状態変数ｘの値であり、ｘｎは上記計算のｎ番目のステージにおける状態変数ｘの値であり、ｍｎは上記データのセットのｎ番目の部分の表現を含む請求項１１０記載の方法。
【請求項１１２】
暗号鍵は、λ、ε及び状態変数ｘの初期値ｘ０のうちの少なくとも１つを少なくとも部分的に決定するために使用される請求項１１０又は１１１記載の方法。
【請求項１１３】
上記数学的システムは、複数の非線形マッピング関数にてなるセットを含む請求項１０４のうちの任意のものに記載の方法。
【請求項１１４】
上記複数のマッピング関数にてなるセットは、
−  次式の形式を有するアノーソフマップ、
【数１０】
2004530919.tif 000085
及び、
−  次式の形式を有するエノンマップ
【数１１】
2004530919.tif 000086
の少なくとも一方を含む請求項１１３記載の方法。
【請求項１１５】
上記数学的システムは少なくとも１つの非線形微分方程式を含む請求項１０４乃至１０７のうちの任意の請求項に記載の方法。
【請求項１１６】
上記数学的システムは、複数の非線形微分方程式にてなるセットを含む請求項１１５記載の方法。
【請求項１１７】
上記数学的システムは少なくとも１つの正のリヤプノフ指数を有する請求項１０４乃至１１６のうちの任意の請求項に記載の方法。
【請求項１１８】
数学的計算の間に少なくとも１回だけ少なくとも１つのリヤプノフ指数を計算することを含む請求項１０４乃至１１７のうちの任意の請求項に記載の方法。
【請求項１１９】
上記少なくとも１つの非線形微分方程式は、少なくとも１つの独立変数ｔの関数である少なくとも１つの状態変数Ｘを決定する請求項１１５乃至１１８のうちの任意の請求項に記載の方法。
【請求項１２０】
上記複数の非線形微分方程式にてなるセットはローレンツシステムを含む請求項１１６乃至１１９のうちの任意の請求項に記載の方法。
【請求項１２１】
少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法であって、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記関数の少なくとも１つの選択された変数の範囲を制限するステップとを含み、上記範囲は、上記範囲によって制限されない場合に上記選択された変数が上記関数によって有したであろう値を除外するように十分に狭く、
上記方法は、
−  計算を実行して、結果として得られる数を取得するステップを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現し、
上記方法は、
−  計算の結果として得られる上記選択された変数の値が上記範囲を超えているとき、上記選択された変数に上記範囲内の値を割り当てるステップを含む方法。
【請求項１２２】
上記方法は擬似乱数発生方法の一部である請求項１２１記載の方法。
【請求項１２３】
上記擬似乱数発生方法は暗号化及び復号化の少なくとも一方に使用する擬似乱数を発生する請求項１２２記載の方法。
【請求項１２４】
上記数学的システムは少なくとも１つの正のリヤプノフ指数を有する請求項１２１乃至１２３のうちの任意の請求項に記載の方法。
【請求項１２５】
少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法であって、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を整数として表現するステップと、
−  上記整数内に仮想小数点分離記号を配置するステップとを含み、これにより上記整数は実数を表現し、
上記方法は、
−  整数として表現された上記少なくとも１つの変数を含む計算を実行して、結果として得られる数を取得するステップを含み、上記結果として得られる数は整数として表され、
上記方法は、
−  上記整数における上記仮想小数点分離記号の位置を訂正するステップと、
−  上記結果として得られる数に想像上の分離記号を配置するステップと
の少なくとも一方を実行することにより、上記結果として得られる数における上記仮想小数点分離記号を、予め決められた位置に位置決めするステップを含む方法。
【請求項１２６】
少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法であって、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップとを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも１つの関数、特に非線形関数を含む数学的システムにおいて数値計算を実行する方法に関する。この数学的システムは、カオス的挙動を呈する複数の微分方程式にてなる非線形なシステムであることが可能である。本発明はまた、暗号化及び復号化方法に適用可能な擬似乱数発生器に関し、かつこのような暗号化及び復号化方法に関する。計算を実行するためには、好適には電子装置が使用される。
【背景技術】
【０００２】
暗号法は、データへの無許可のアクセスを防止しながら当該データを記憶しかつ送信できるようにするためにデータを変換することに関連した科学及び技術の範囲を含む、一般に使われる用語である。暗号法により、データは、そのデータに係る意図された１人又は複数の受信者以外の誰にも理解できないようにされる。従って、暗号法は、技術の進歩が大量のデータの安全な伝送及び記憶を必要とするのに伴い、著作権保護を含む知的財産権の保護においてますます重要な役割を果たす。
【０００３】
暗号化及び復号化アルゴリズムでは、特定のデータ変換は、アルゴリズムへの入力、いわゆる鍵に依存する。データの送信者及び受信者が適正な鍵セットを有する場合、送信者及び受信者はデータを正しく暗号化しかつ復号化することができるが、第三者はいずれも、暗号化されたデータへアクセスできることがあっても、彼女又は彼が適正な鍵を所有していないために、暗号化されたデータの正しく復号化されたバージョンを目にすることはできない。
【０００４】
一般に、暗号化されるデータのセットは“平文”又は“元のデータ”と呼ばれ、このデータのセットの復号化されたバージョンは“暗号文”又は“暗号化されたデータ”と呼ばれる。
【０００５】
対称暗号アルゴリズムの２つのタイプに、いわゆる“ブロック暗号法”といわゆる“ストリーム暗号法”がある。両方のタイプのアルゴリズムは対称鍵を使用する。すなわち、暗号化及び復号化に使用される鍵は等しいか、あるいは自明な関係にある。ブロック暗号は、元のデータのセットを、与えられたサイズの、例えば１ブロック毎に６４ビットの複数のブロックに分割する暗号アルゴリズムである。各ブロックに対して数学的演算及び論理演算が実行され、これにより、所定量の元のデータは、通常は、擬似ランダムデータの複数のブロックに変換される。正しい復号化鍵を用いて復号化が開始される場合、元のデータを、暗号化に使用される数学的演算及び論理演算を反転することによって復元（re-call）することが可能である。
【０００６】
（同期的な）ストリーム暗号法では、擬似乱数発生器は鍵に基づいて擬似乱数のシーケンスを発生する。このシーケンスは鍵ストリームと呼ばれる。鍵ストリームは、算術演算及び／又は論理演算によって、元のデータのセットのうちの複数のサブセットと混合される。データのサブセットの和は、暗号化される元のデータを定義する。混合したことの結果は、暗号化されたデータになる。暗号化されたデータのセットは、暗号化されたデータから擬似ランダムシーケンスが抽出されるように手順を反復することで元の復号化されたデータに到達することによって、復号化可能である。
【０００７】
平文は、多くの場合、
【数１】
2004530919.tif 000003
の記号によって表され、“排他的論理和”演算子とも呼ばれるいわゆるＸＯＲ演算子である論理演算子を使用して鍵ストリームと混合される。ＸＯＲは、２つの１ビット引数から１ビットの結果を発生させる。可能なすべての組み合わせは、次式のようになる。
【０００８】
【数２】
2004530919.tif 000004
【数３】
2004530919.tif 000005
【数４】
2004530919.tif 000006
【数５】
2004530919.tif 000007
【０００９】
平文及び擬似ランダム鍵ストリームに対してＸＯＲ演算子を利用することが、暗号文を生じさせる。復号化中に同一の鍵ストリームが発生され、このとき鍵ストリーム及び暗号文に対してＸＯＲ演算子が利用され、結果的に元の平文が発生される。同一の鍵ストリームは、暗号化のための鍵ストリームが最初に基礎とした鍵を使用することによってのみ発生されうる。
【００１０】
さらに、いわゆる公開鍵システムが開発され、こうしたシステムは１対の非対称鍵、すなわち異なる２つの鍵である公開鍵と秘密鍵とによって特徴付けられる。このようなシステムでは、通常は公開鍵が暗号化に使用され、通常は秘密鍵が復号化に使用される。秘密鍵と公開鍵は、所定の方法で互いに対応する。暗号化に使用された鍵を復号化に使用することはできず、その逆もまたできない。従って、公開鍵は、元のデータのアクセス可能性に関する安全性を脅かすことなく公開可能である。そのため、暗号化されたデータをコンピュータ通信ネットワークを介して伝送するときには、データの受信者はまず、公開鍵及び秘密鍵を含む鍵のセットを発生する。次いで、公開鍵は例えばデータの送信者へ提供され、それに対して秘密鍵は安全な場所に記憶される。データの送信者は公開鍵を利用して元のデータを暗号化し、暗号化されたデータは次に受信者へ転送される。受信者がこの暗号化されたデータを受信すると、先に暗号化に利用された公開鍵に対応している秘密鍵が復号化システムに提供され、復号化システムは、上記暗号化されたデータを処理することで、復号化された元のデータに到達する。公開鍵システムは主として、例えばブロック暗号又はストリーム暗号において利用される鍵の伝送に使用され、このブロック暗号又はストリーム暗号が次にデータの暗号化及び復号化を実行する。
【００１１】
本発明による方法は、複数の暗号方法に適用可能であり、特に、ストリーム暗号アルゴリズム、ブロック暗号アルゴリズム、ハッシュ関数、及びＭＡＣ（メッセージ認証コード）関数に適用可能であるが、この限りではない。このような方法、関数及びアルゴリズムは、再現可能な方法で擬似乱数を発生可能な擬似乱数発生器、すなわち、２つの異なるサイクルで擬似乱数発生器への入力として同じ鍵が使用されるとき、結果的にこの２つの異なるサイクルで同じ数値が発生されるような方法で擬似乱数を発生可能な擬似乱数発生器を含むことがある。
【００１２】
擬似乱数を発生するため、カオス的システム、すなわちカオス的な挙動を示す複数の非線形微分方程式の系（システム）又は複数のマッピング（写像）の系（システム）の数値解を利用することが提案されている。“カオス的”という用語は、厳密な数学的意味では連続な系のコンテキストにおいてのみ使用可能である。しかしながら、本願明細書では、少なくとも１つの正のリヤプノフ指数を有する離散的な系又は有限な系も、“カオス的”であると呼ぶ。
【００１３】
カオス的システムは、標準的には少なくとも１つの状態変数Ｘを決定している。こうしたシステムの数値解法は、標準的には複数の反復又は積分のステップを実行することを含んでいる。カオス的システムでは、与えられた瞬間における解Ｘｎは、初期条件Ｘ０での小さなずれが結果的に解Ｘｎでの巨大なずれをもたらすように初期条件Ｘ０に依存する。このシステムはしばしば、初期条件に対して敏感であると呼ばれる。従って、擬似乱数発生器、すなわちカオス的システムを数値的に解くアルゴリズムが、擬似乱数の再現可能なストリームを与えるためには、正確な初期条件Ｘ０が知られている必要がある。このように、カオス的システムに依存する暗号アルゴリズムでは、カオス的システムの数値解法に使用される初期条件Ｘ０は、暗号システムのユーザによって入力された鍵から導出され、これにより、例えばデータの暗号化及び復号化のために、擬似乱数の同一のストリームが発生可能となる。
【００１４】
リヤプノフ指数は、隣接する２つの軌道、すなわち解曲線の発散又は収束の速さを測る尺度となり、様々なタイプの解の安定性を決定するために、すなわちその解が例えば周期的であるかそれともカオス的であるかを決定するために使用可能である。リヤプノフ指数は、基準軌道と変位された軌道との比較に基づいてこのような尺度を提供する。基準軌道は初期条件ｘ０の反復で表され、変位された軌道は初期条件ｘ０＋ｙ０の反復で与えられる。ここで、ｙ０は無限に小さい長さのベクトルであり、変位の初期値を表す。変位の初期値に係る向きの初期値は、ｕ０＝ｙ０／│ｙ０│で与えられる。この表記法を使用すると、リヤプノフ指数ｈ（ｘ０，ｙ０）は次式のように定義される。
【００１５】
【数６】
2004530919.tif 000008
【００１６】
ここでｙｎは、ｘ０のｎ番目の反復によって与えられる、変位された軌道の、基準軌道からのずれである。次元が１より大きいシステムの場合、複数のリヤプノフ指数のセット又はスペクトルであって、各々がある特定方向への軌道の発散又は収束を特徴付けるものが存在する。従って、システムが自由度Ｎを有していれば、これはＮ個のリヤプノフ指数を有することになる。しかしながら、これらは必ずしも別個のものではない。あらゆる実際的状況において、正のリヤプノフ指数はカオスを表す。ハイパーカオス（hyperchaos）と呼ばれる不規則な挙動のタイプは、２つ以上の正のリヤプノフ指数によって特徴付けられる。リヤプノフ指数の数値計算は、ティー．エス．パーカー（T. S. Parker）及びエル．オー．チュア（L. O. Chua）によるカオス的システムの実用数値アルゴリズム（Practical Numerical Algorithms for Chaotic Systems）の７３−８１ページに提案された方法に従って実行してもよい。
【００１７】
ハイパーカオス的なシステムよりさらに不規則なシステムはいわゆる乱流を呈し、これは、正のリヤプノフ指数の連続スペクトルを有するシステムが示すタイプの挙動に関連してる。乱流は、例えば公知のナビエ・ストークス方程式のような偏微分方程式によってモデル化可能である。
【００１８】
多数の従来技術文献が、特に暗号アルゴリズムに使用されるカオス的システムの解法に関連し、またカオス的システムに依存するストリーム暗号アルゴリズムも含んでいる。
以下、背景技術への一般的な導入として、そのうちのいくつかに簡単に言及する。
【００１９】
ローラル・エアロスペース・コーポレーション（Loral Aerospace Corp.）に譲渡された米国特許第５，００７，０８７号の明細書は、カオスを使用して乱数を発生する方法及び装置を開示している。この特許は、乱数シーケンスを発生するためのカオス的システムの解法について記述し、かつ暗号法におけるその使用の可能性について、特に鍵の発生及び管理の分野におけるその使用の可能性について言及している。この明細書では、数値シーケンスの反復可能性が回避される必要があると記載されている。
【００２０】
ヒューズ・エアクラフト・カンパニー（Hughes Aircraft Company）に譲渡された米国特許第５，０４８，０８６号は、カオス理論に基づく暗号化システムに関連している。このシステムは、所定の値のμに対してカオスを呈するマッピングである、ロジスティック方程式ｘｎ＋１＝μｘｎ（１−ｘｎ）を使用する。この計算では、浮動小数点演算が使用される。
【００２１】
川崎市の株式会社東芝に譲渡された米国特許第６，０１４，４４５号の明細書は、ランダム変数及び鍵ストリームの発生を組み込んだ暗号化／復号化の装置及び方法を開示している。この開示内容はカオス的ストリーム暗号に関連し、浮動小数点計算が使用されていると記載している。
【００２２】
アップル・コンピュータ・インコーポレイテッド（Apple Computer, Inc.）に譲渡されたＰＣＴ出願公開ＷＯ９８／３６５２３号の明細書は、カオス的システムを使用して秘密鍵から公開鍵及び調整可能な裏口（バックドア）を発生する方法を開示している。カオス的システム上で計算する間での精度の規則を確立する必要性が記載されている。この明細書は、一例として、丸めのための特定の標準とともに、特定された浮動小数点又は固定小数点の精度が識別可能であると記載している。
【００２３】
ディー．カハナー（D. Kahaner），シー．モラー（C. Moler）及びエス．ナッシュ（S. Nash）による“数値的方法とソフトウェア（Numerical Methods and Software）”（プレンティスホール・インターナショナル・エディションズ（Prentice-Hall International Editions）、１９８９年）は、（擬似）乱数の発生に関する概論を含んでいる。この文献は、（擬似）乱数発生器の性能を判定するための下記のような基準を記載している。
ａ）高品質：発生器は、すべての統計的テストに合格し、かつ極めて長い寿命を持たねばならない。
ｂ）効率：実行は迅速であり、記憶装置の必要量は最小でなければならない。
ｃ）反復可能性：同じ開始条件を指定すると、同じシーケンスが発生される。ユーザはいつでも発生器を再スタートできる必要があるが、明示的な初期化は不要である。開始手順におけるわずかの変化は、結果的に、異なるランダムシーケンスをもたらす。
ｄ）マシンの独立性と移植性：アルゴリズムは、異なる種類のコンピュータ上で動作しなければならない。特に、如何なる演算もプログラムを停止させる原因となってはならない。発生器をまったく同様に初期化することにより、異なるコンピュータ上で同じ乱数のシーケンスが発生されなければならない。
ｅ）簡単さ：アルゴリズムは、実装及び使用が容易でなければならない。
この文献はさらに、どんな発生器もこれらすべての基準を首尾良く満足させることはできないと述べている。
【００２４】
エイチ．カマタ（H. Kamata），イー．テツロ（E. Tetsuro）及びワイ．イシダ（Y. Ishida）による“ＤＳＰの実装によるカオスを用いた安全な通信システム（Secure Communication System Using Chaos via DSP Implementation）”（ＩＥＥＥ、１９９６年）は、システムの実装にディジタル信号プロセッサ（ＤＳＰ）が使用された、カオス回路に基づく通信システムについて記述している。固定小数点ＤＳＰを使用することにより、このシステムはアナログ回路よりも頑健にされている。送信されたメッセージの復元は、カオス受信システムを送信システムに同期化することに基づいている。
【００２５】
数値計算において、例えばインテル（Intel）のマンデルブロ計算において、固定小数点の変数を使用することが知られている。インテル（２００１年１２月７日に、http://developer.intel.com/software/idap/resources/technical_collateral/mmx/MANDEL.HTMで公にアクセス可能な、ＭＭＸ（商標）テクノロジー・アプリケーション・ノーツ（MMXTMTechnology Application Notes）“ＭＭＸ（商標）テクノロジーを用いたフラクタルの実装（Implementing Fractals with MMXTMTechnology）”を参照。）は、ＭＭＸ技術（特定の計算を高速化する、インテルのプロセッサへのアドオン）を使用してマンデルブロ集合（非線形なシステムから導出可能な集合）を高速に計算しうる方法について説明している。これは、固定小数点計算を用いて実行される。
【００２６】
マンデルブロ集合は、次式のマッピングによって計算される。
【００２７】
【数７】
2004530919.tif 000009
【００２８】
インテルは、それらの計算において一定の小数点分離記号の位置を使用する。いわゆる５．１１が利用される。すなわち、１６ビットの数が利用され、小数点分離記号は５番目のビットの後に置かれ、“５”は小数点分離記号より後の５つのビットを示し、“１１”は小数点分離記号より後の１１のビットを示す。
【発明の開示】
【発明が解決しようとする課題】
【００２９】
一般にコンピュータでは、実数は浮動小数点型の数によって表される。浮動小数点の数は、例えば３１４１５・１０−４のように、仮数と指数よりなる数として定義され、ここで“３１４１５”が仮数であり、“−４”が指数である。コンピュータが浮動小数点の変数で計算を実行する場合、コンピュータは毎回結果が一致するように指数を再計算する。“浮動小数点”という名称は、複数の計算において、指数の変化に起因して小数点分離記号が移動するという事実を示している。しかしながら、浮動小数点の算術は様々なプロセッサアーキテクチャで異なって定義されるので、精度及び丸めの処理に違いが生じる。浮動小数点の数の代わりに、固定小数点の数が使用可能である。固定小数点の数はコンピュータ上で整数型の数として表され、ここでは、実数の整数部と小数部とを分離するために、仮想小数点又は分離記号（想像上の小数点分離記号とも呼ばれる）が“手動で”、すなわちプログラマによって導入される。ゆえに固定小数点の数での計算は簡単な整数演算によって実行され、この演算は、異なる２つのプロセッサ上で実行される同じ計算が、負の数の表現が異なる可能性のあることを除いてこれらの２つのプロセッサで同一の結果を生じるという意味で、すべてのプロセッサ上で同一である。こうした異なる表現の可能性は、いくつかのプロセッサが１の補数を利用し、他のプロセッサが２の補数を利用することの結果として生じることがある。さらにまた、これらの演算は、通常は、対応する浮動小数点演算よりも高速である。
【００３０】
一般に、固定小数点の数のタイプはΦ（α．β）で表され、αは整数部を保持するために使用されるビット数であり、βは小数部を保持するためのビット数である。α及びβの値と、従って小数点の位置とは、通常は予め決定されていて定常的である。固定小数点の数は符号なしの場合と符号ありの場合のいずれかが可能であるが、その場合はΦが各々Ｕ又はＳで表される。後者の場合、符号を保持するために１ビットが必要とされるので、Ｓ（α．β）を保持するためにα＋β＋１ビットが必要とされる。Ｕ（α．β）の範囲は［０；２α−２−β］であり、Ｓ（α．β）の範囲は［−２α；２α−２−β］である。これにより、固定小数点の数の分解能は２−βである。
【００３１】
固定小数点の数における小数点分離記号の位置は、数の整数部のディジットと小数部のディジットとの間の重み付けになる。最良の計算結果を達成するために、通常は、小数点分離記号の後に可能な限り多くのディジットを含んで最高の分解能を得ることが望ましい。しかしながら、整数部にも、オーバーフローが発生しないことを保証するのに十分なビットを割り当てることが重要であるかもしれない。オーバーフローとは、ロード又は計算される値と同程度の大きさの数値を保持できないレジスタへ値をロードする、又は当該レジスタにおいて値を計算することである。オーバーフローは、結果的に、最上位のビット（ディジット）と起こりうる符号の変化とを削除する。
【００３２】
本発明の様々な態様においては、小数点分離記号の位置は設計の時点で割り当てられてもよい。適正な位置を選択するため、好適には、位置が選択されるべき可能な数の範囲が解析される。可能な最大の正の値と可能な最小の負の値とが決定され、これら２つのうちの絶対値の最大値が次式に挿入されてαの値が決定される。
【００３３】
【数８】
2004530919.tif 000010
【００３４】
小数点の位置は、異なる複数の固定小数点の変数の間で変化する可能性がある。しかしながら、加算及び減算演算は、同様の位置を有する数の入力を必要とする。ゆえに、時として小数点の位置をシフトさせる必要がある。ｎビットの右シフトは、Φ（α．β）からΦ（α＋ｎ．β−ｎ）への変換に対応する。ｎビットの左シフトは、Φ（α．β）をΦ（α−ｎ．β＋ｎ）へ変換する。符号なしの数の変換は論理シフト演算によって行われるのに対して、符号付きの数には算術シフトが使用される。
【００３５】
固定小数点の数での数学的演算である加算、減算、乗算及び除算は、簡単な整数演算として実行される。加算及び減算演算は、桁上げに起因して結果的にサイズΦ（α＋１．β）の数になる可能性がある。しかしながら、通常、この結果は、入力と同じフォーマットの数にするために切り捨てられる。
【００３６】
乗算及び除算は、引数の小数点分離記号が同様の位置にあることを必要としない。しかしながら、除算の場合、分子は分母及び結果の２倍の長さを有する必要があるので、分子は除算の前に予め展開される。結果は次のようなフォーマット：Ｓ（α．β）・Ｓ（ｃ．ｄ）＝Ｓ（α＋ｃ＋１．β＋ｄ）及びＳ（α＋ｃ＋１．β＋ｄ）／Ｓ（α．β）＝Ｓ（ｃ．ｄ）を有することになる。符号なしの乗算及び除算の場合は、Ｓ（α＋ｃ＋１．β＋ｄ）がＵ（α＋ｃ．β＋ｄ）で置換される。乗算において、予め決められた結果のフォーマットよりも超過したディジットは、目標のレジスタサイズに合わせて切り捨てられる。
【００３７】
固定小数点での計算に関する別の情報は、アール．イェーツ（R. Yates）による“固定小数点算術：概論（Fixed-Point Arithmetic: An Introduction）”（この文献は、２００１年１２月７日において、http://personal.mia.bellsouth.net/lig/y/a/yatesc/fp/pdfで取得可能である。）で見つけることができる。
【００３８】
数学的システムの数値解法における浮動小数点の変数の利用は、予測不可能な切り捨て及び／又は丸めの誤差を生じさせる可能性がある。解を求める数学的システムが非線形である場合、かつ特に当該システムがカオス的である場合は、１つのステップにおける小さなずれが後続のステップでは大きなずれとなる可能性があるので、すべての積分ステップでの解の精度が最重要となる。切り捨て及び／又は丸めの誤差があらゆる計算で同じように一貫して発生されれば、同一の初期条件に基づく２つの解は同一であり、よってその計算は再現可能である。しかしながら、ほとんどの場合において、浮動小数点の数の切り捨て及び／又は丸めの誤差はソフトウェアによって完全に制御されるのではなく、当該ソフトウェアを実行しているハードウェアによっても制御される。従って切り捨て及び／又は丸めの誤差はハードウェアに依存し、その結果として、異なる２つのハードウェアプロセッサでは切り捨て及び／又は丸めが異なって実行される可能性がある。大部分の計算では、切り捨て及び丸めが、計算に必要な精度よりずっと小さな程度のオーダーの不正確さを発生しているために、この点は重要でない。しかしながら、例えばカオス的システムの解では、切り捨てが実行される方法における小さなずれが、後の計算ステップでは解に大きなずれをもたらす可能性がある。
【００３９】
従って、本発明の目的は、切り捨て及び／又は丸めの誤差が予測可能であるか、又はこのような誤差がソフトウェアによって完全に制御されうる、すなわち計算の精度がハードウェアとは独立である、数学的システムにおいて数値計算を実行する方法と、擬似乱数を発生する方法とを提供することにある。本発明の別の目的は、こうした数値計算を実行する方法と、擬似乱数を再現可能な方法で発生する方法とであって、コンピュータ上で実行されるときに高速である、すなわち利用可能なハードウェアプロセッサ能力を最適に使用する方法を提供することにある。本発明のさらに別の目的は、コンピュータで実行されるときに高速な、データを暗号化しかつ復号化する方法及びシステムを提供することにある。
【課題を解決するための手段】
【００４０】
ここのコンテキストにおいて“擬似乱数”という用語が使用される場合、これは、再現可能な方法及び／又は決定論的方法で発生されることが可能な、すなわち、ある１つの擬似乱数発生アルゴリズムの異なる２回の実行において、その２回の実行での擬似乱数発生アルゴリズムへの入力として同一の鍵又はシード（種）値が使用されれば同一の擬似乱数が結果的にもたらされるような方法で発生されることが可能な乱数として理解される必要がある。
【００４１】
ここのコンテキストにおいて、固定小数点の変数は、仮想小数点分離記号を有する整数型の数として定義され、整数は小数点分離記号より後にディジットを持たない数として定義される。従って、実数は、仮想小数点分離記号（又は小数点）を整数におけるどこか予め決められた固定位置に、例えば左から４番目のディジットに挿入して表現される。この位置は、数に対する数学的演算の結果として変更される可能性もある。このｋ位置はまた、論理演算の使用によって変更を余儀なくされる場合もある。
【００４２】
上述の議論から想起される通り、固定小数点の数は整数であり、これに仮想小数点分離記号が付加される。数は、小数点分離記号より前のビットを示すいわゆる“整数部”と、小数点分離記号から後のビットを示す“分数部”とで構成される。ここのコンテキストではビットはディジットとも呼ばれ、かつこの逆も行われる。
【００４３】
固定小数点の数の計算を含むコンピュータプログラムにおいて、又は固定小数点の計算を実行するための電子回路又は装置においては、小数点分離記号の適正な位置を決定するための手段が提供されていることがある。従って、当該プログラム、回路又は装置は、計算中に、発生しうるオーバーフローを検出することができ、発生しうるオーバーフローが検出された場合は、小数点分離記号のいずれかの側のビット数を変更する、すなわち問題となっている１つ又は複数の変数を記憶するレジスタにおける小数点分離記号の位置を変更することができる。この変更は、小数点分離記号を１桁又はそれ以上だけ右又は左へ移動させることによって実行可能である。好適には、レジスタ内で使用されない可能性のあるビット数を最小化するために、できるだけ多くのビットを小数点分離記号より右側で使用し、これにより最適な計算の精度を達成する。小数点分離記号の位置を変更することにより、発生しうるオーバーフローを検出するための付加的演算に係る必要条件に起因して計算速度はある程度損なわれるものの、コンピュータプログラム、回路又は装置を組み込むアプリケーションの設計者又はプログラマが設計又はプログラミングの段階で精度及びオーバーフローに関して考慮することを必要とせずに、計算の精度は最適化され、それと同時にオーバーフローの危険性は除去されるか低下される。それに代わって、あるいはそれに加えて、計算中のどの時点又はどの場所でオーバーフローが発生するのか又は発生しそうであるのかを決定するテストプログラムを提供することも可能であり、従って、当該プログラムのプログラマ又は設計者は、オーバーフローが発生しないように、１つ又は複数の変数における小数点分離記号の位置を固定でき、それによって、最終的な実装において、発生しうるオーバーフローに関する決定が一切不要となる。しかしながら、発生しうるオーバーフローの決定は、付加的な保護手段的機能として最終的実装に組み込まれてもよい。さらに、プログラマ又は設計者は、計算中の、予め決められ、固定された段階において、小数点分離記号の変更を実装することを選択してもよい。
【００４４】
先に議論したように、実数は、１つ又は複数の固定小数点の数によって表現されることが可能である。同様に、ｉ２＝−１とするとき、複素数ｃ＝ａ＋ｉｂは、１つ又は複数の固定小数点の数によって、例えば実数部ａ及び／又は虚数部ｂを固定小数点の数として表すことによって、表現されることが可能である。実数部及び虚数部の一方だけが固定小数点の数として表現される場合に、他方は、浮動小数点の数又は整数のような他の任意のタイプの数によって表現されてもよい。
【００４５】
ここのコンテキストにおいて、“データキャリア”又は“コンピュータが読み取り可能なデータキャリア”という用語は、コンピュータ又はコンピュータシステムによってアクセス可能な、データを記憶する能力のある任意の装置又は媒体として理解される必要がある。従って、コンピュータが読み取り可能なデータキャリアは、例えば、ＲＡＭ、ＲＯＭ、ＥＰＲＯＭ又はＥＥＰＲＯＭ等のメモリ、コンパクトフラッシュカード、メモリースティックカード、フロッピー又はハードディスクドライブ、コンパクトディスク（ＣＤ）、ＤＶＤ、データテープ又はＤＡＴテープを含むことが可能である。
【００４６】
本発明に係る方法によって導出されるデータ及びこのような方法において使用されるデータを含む信号は、例えば電気的な回線又は光回線等の通信回線か、あるいは無線又は光送信を使用する無線通信手段を介して伝送されることが可能である。例としては、インターネット、ＬＡＮ（ローカルエリアネットワーク）、ＭＡＮ（メトロポリタンエリアネットワーク）、ＷＡＮ（広域ネットワーク）、電話回線、賃借された専用回線、私設の専用回線、及びケーブル又は衛星テレビネットワークがある。
【００４７】
ここのコンテキストにおいては、“電子装置”という用語は、電子的なインパルス又は光インパルスによってデータを処理する任意の装置として理解される必要がある。本発明に係る方法に適用可能な電子装置の例としては、ＣＰＵ、マイクロコントローラ又はＤＳＰ（ディジタル信号プロセッサ）等のプロセッサがあり、また、パーソナルコンピュータ、メインフレームコンピュータ、携帯用装置、スマートカード、例えば暗号化のような所定の目的に合わせて特別に設計されたチップを含む、コンピュータ、あるいはプロセッサ又は数学的演算を実行するための他の電子回路を組み込んだ他の任意の装置がある。電子装置の例にはさらに、計算及び／又は演算を実行するように適応化又は設計されたマイクロチップがある。
【００４８】
プロセッサは、通常は、（ａ）演算されるデータのサイズ、（ｂ）命令サイズ、及び（ｃ）メモリモデルによって分類される。これらの特性は、標準的には、４ビットと１２８ビットの間（例えば１５、１６、３２、６４ビット）の異なるサイズを有することが可能であり、２の累乗に限定されない。
【００４９】
ここのコンテキストにおいては、“プロセッサ”という用語は、下記のものを含む任意のタイプのプロセッサを包含するが、これらに限定されるものではない。
−  “組み込みプロセッサ”とも呼ばれる“マイクロコントローラ”。“マイクロコントローラ”及び“組み込みプロセッサ”は通常、小型プロセッサを示す（通常は大型プロセッサより少ないトランジスタで構成され、制限された電力消費量を有する。）。マイクロコントローラアーキテクチャの例として次のものがある。
−  Ｚ８０
−  ８０５１（例えば、インテル製）
−  ＣＰＵ８／６８００（例えばモトローラ（Motorola）製の、例えば６８ＨＣ０５、６８ＨＣ０８及び６８ＨＣ１１）
−  ＣＰＵ３２／６８ｋ（モトローラ製の６８０００ドラゴンボール（68000 Dragonball）等）
−  典型的には異なる複数の種類のコンピュータ及び制御システムで使用される他のプロセッサ。アーキテクチャの例として次のものがある。
−  アルファ２１ｘｘｘ（２１１６４、２１２６４、２１３６４等）
−  ＡＭＤ  ｘ８６−６４（スレッジハマー（Sledgehammer）等）
−  ＡＲＭ（ＡＲＭ１０、ストロングＡＲＭ（StrongARM）等）
−  ＣＰＵ３２／６８ｋ（例えばモトローラ製の例えば６８０００、６８０３０、６８０４０）
−  ＩＡ３２（例えばインテル製（ｉ４８６、ペンティアム（Pentium）等）、ＡＭＤ製（Ｋ６、Ｋ７等）及びサイリクス（Cyrix）製のｘ８６ファミリ）
−  ＩＡ６４（ＨＰ／インテル（HP/Intel）製のアイテニアム（Itanium）等）
−  ＭＩＰＳ（ＳＧＩ製のＲ４０００、Ｒ１００００等）
−  ＰＡ−ＲＩＳＣ（ＨＰ製の８０００等）
−  パワーＰＣ（PowerPC）（ＩＢＭ／モトローラ（IBM/Motorola）製のＧ３、Ｇ４等）
−ＳＰＡＲＣ（サン（SUN）製のウルトラＳＰＡＲＣ  ＩＩ（UltraSPARC II）、ウルトラＳＰＡＲＣ  ＩＩＩ（UltraSPARC III）等）
−  ＤＳＰ。例として次のものがある。
−  ＤＳＰ５６３００（モトローラ製）
−  ＭＳＣ８１００（モトローラ製）
−  ＴＩ  ＴＭＳ３２０Ｃ６７１１（テキサス・インスツルメンツ（Texas Instruments）製）
【００５０】
ここのコンテキストにおいては、“レジスタ”という用語は、数値のようなデータを含む任意のメモリ空間として理解されるべきものであり、メモリ空間は、例えば、ＣＰＵレジスタ、ＲＡＭ、電子回路内のメモリ、又はハードディスク、フロッピーディスク、コンパクトディスク（ＣＤ）、ＤＶＤ、データテープ又はＤＡＴテープ等の任意のデータキャリアである。
【００５１】
本発明はまた、独立した態様において、本発明の方法によって導出されるデータにも関するということは理解される必要がある。また、本発明が諸方法に関連する場合、これはまた、独立した態様において、このような諸方法を実行するように適応化されているコンピュータプログラム、このようなコンピュータプログラムがロードされたデータキャリア又はメモリ手段、及び／又は当該諸方法を実行するためのコンピュータシステムに関するということも理解される必要がある。
【００５２】
本発明の方法に含まれるあらゆる計算演算は、電子装置上で、又は電子装置によって実行されることが可能である。
【００５３】
第１の態様において、本発明は、少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法を提供する。当該方法は、
−  上記数学的システムを離散的な的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記複数の計算から、結果として得られる数を取得するステップとを含み、上記結果として得られる数は、
−ａ．上記数学的システムに対する解の少なくとも一部と、
−ｂ．上記数学的システムの数値解に関連する別の計算において使用可能な数との少なくとも一方を表現し、
当該方法はさらに、
−ｉ．上記結果として得られる数のディジットのサブセットと、
−ｉｉ．上記結果として得られる数から導出される数のディジットのサブセットと
の少なくとも一方を表現するデータのセットを抽出することを含む。
【００５４】
数のサブセットは、その数のディジット又はビットのすべてである必要はないがそのいくつかであるような、当該数の一部と見なすことが可能である。例えば、１６ビットの数の最下位の８ビットは、当該１６ビット数のサブセットと見なすことができる。
【００５５】
“抽出する”という用語は、問題となる数又はサブセットを、例えばキーストリームとしてか又はキーストリームの一部として、もしくは計算処理の他の任意の最終結果又は中間結果として出力することと、問題となる数又はサブセットを、例えば当該サブセットに対するその後の計算等のその別の使用を見込んで、レジスタに記憶することとを含むが、これらに限定されない。
【００５６】
数全体を抽出する代わりに数の複数のディジットのうちのサブセットを抽出することにより、当該方法が、擬似乱数発生器において、例えば暗号化及び／又は復号化目的で使用される場合のランダム特性が改善される。さらに、ただ１つのサブセットのみが抽出されるので、抽出されたデータのセットに含まれる、数学的システムの内部状態に関する情報量は少なくなり、このことは、本発明に係る方法を組み込んだ暗号化／復号化システムのセキュリティを強化する。
【００５７】
数学的システムは、例えば複数の微分方程式にてなるシステムのような連続的なシステムを含んでいてもよいが、これはまた、もしくは代替として、例えばマップの場合におけるように元は離散的な項で定義されたシステムを含んでいてもよい。数学的システムの少なくとも１つの関数は、後に詳述するように非線形であってもよい。
【００５８】
通常は、複数のディジットのうちのサブセットは、ｋ≦ｍとして、ｍビットの数のうちのｋビットを含み、例えば３２ビットの数のうちの８ビットが抽出される。サブセットが抽出される数と、及び／又は抽出されたデータのセットとは、１つ又は複数の２進数、８進数、１０進数、１６進数などで表現されることが可能である。ｋビットは当該数の最下位のビットであってもよく、又は、当該ビットが抽出される数の中の、予め決められた位置又はランダムな位置から選択されたｋビットであってもよい。例えば、６４ビットの数からは、４２、４７、５３、５５、５６、５７、６１及び６３番目のビットを抽出すること、又は４７乃至５４番目のビットを抽出することができる。
【００５９】
本発明の第１の態様による方法は、制御システムにおける、暗号化及び復号化、電波の変調、雑音を低下させるような画像及び音声信号におけるカオスの同期化、データ圧縮に適用可能であり、また、例えば文書を音声ファイルの最下位ビットで記憶してディジタル送信において文書を隠すための、電子透かしの埋め込み（ウォーターマーキング）、画像深層暗号（ステガノグラフィ）に適用可能である。
【００６０】
固定小数点の数の使用には、固定小数点の数の計算において発生する丸め及び／又は切り捨て誤差がすべてのプロセッサで同一に定義されるという、浮動小数点の数に対する優位点がある。固定小数点の変数の使用により、小数（decimal number）は、数の中に仮想小数点分離記号が置かれる整数型の数として表現されることが可能である。浮動小数点の変数が使用される場合には、切り捨て／丸めの誤差が異なるタイプのプロセッサ上で同一に生じることはない。
【００６１】
切り捨て／丸めの誤差が制御可能であるか又は予測可能であることの結果として、切り捨て／丸めの誤差に敏感な数学的システムにおける数値計算が、再現可能な方法で実行可能になる。従って、例えば非線形システム、特にカオス的システムが、再現可能な方法で数値的に解かれうる。これにより、不正確さを防止するためのフィードバック又は訂正のアルゴリズム又はレジスタを必要とすることなく、もしくは、暗号化におけるシステムの解が復号化におけるときと同一になることを保証する同期化技術を必要とすることなく、暗号化／復号化アルゴリズムなどでの擬似乱数発生器においてカオス的システムを利用できるようになる。このことは次いで計算に寄与し、擬似乱数発生器及び／又は暗号化／復号化アルゴリズムは、こうしたフィードバック又は訂正アルゴリズムもしくは同期化技術を含んだアルゴリズムに比べて高速である。さらに、暗号化されたデータとともに同期化データを送信する必要がない。こうした同期化データはしばしば、暗号化されたデータのサイズに匹敵するサイズにまで達し、例えば、インターネットを介してデータを送信する場合に帯域幅が不十分であることに起因して、この点が大きな問題になる可能性がある。さらに、こうしたデータの送信は、システムのセキュリティを危うくする。またこの計算は、問題となる変数に関する浮動小数点の変数を含む方法における計算よりも高速に実行されるが、これは、固定小数点の数を含む計算ではハードウェアのプロセッサが計算を整数の計算として実行するからであり、整数での計算は一般に浮動小数点の数での計算よりも高速だからである。
【００６２】
ここのコンテキストにおいては、“結果として得られる数”という用語は、計算において発生する任意の数として理解される必要がある。１つよりも多くの結果として得られる数が取得される場合もある。結果として得られる数は、上述の通り、数学的システムに対する解の一部及び／又は中間結果、すなわち数学的システムの任意の変数又はパラメータもしくは計算に使用される他の任意の変数又はパラメータに割り当てられた数であることが可能である。本方法の実装においては、結果として得られる数又はその一部は、例えば暗号化／復号化システムで使用するための擬似乱数として抽出されることが可能である。代替として、結果として得られる数又は複数の結果として得られる数に対して１つ又は複数の数学的演算及び／又は論理演算を実行し、抽出される別の数を求めることも可能である。２進数で表示された、結果として得られる数の、すべてのビット又は選択されたビットのみを抽出することができる。計算中に発生する数の選択されたビットから発生された数は、結果として得られる数と呼ばれうるということは理解される必要がある。従って、“結果として得られる数”という用語はまた、計算中に発生する数の任意の部分をも含んでいる。
【００６３】
本発明の第１の態様による方法は、先に議論した通り、暗号法において、例えば、対称暗号アルゴリズム、公開鍵（又は非対称鍵）アルゴリズム、セキュアハッシュ関数又は暗号ハッシュ関数、もしくはメッセージ認証コード（ＭＡＣ）の実装において有用である。これらのアルゴリズムは、例えば下記のタスクのうちの１つ以上を達成するときに使用可能である。
−  ディジタルデータの機密性を保証して、無許可アクセスからデータを保護する。
−  ディジタルデータの完全性を保証して、情報が正確である、もしくは改ざんされていないことを保証する。
−  例えば所定のタスク又は演算を実行する許可を与えるための認証。
−  他の関係者の身元を照合するためのユーザ認証、又はデータの発信元を照合するためのデータ発信元認証のような認証。
−  電子商取引に関与した証拠を提供して、例えば第１の人物Ａが第２の人物Ｂにメッセージを送り、その後で、このメッセージを送信したことを否定することを防止するための否認防止。この目的のために、ディジタル署名が使用される。ディジタル署名の発生には、公開鍵アルゴリズムとハッシュ関数との使用を組み込むことが可能である。
【００６４】
本発明の第１の態様による方法はまた、いわゆるハッシュ関数にも適用可能である。ハッシュ関数は、少量のデータが、通常は上述の少量のデータより遙かに大きいデータのセットである他のデータを識別する働きをする、ある種のディジタル指紋を提供する。ハッシュ関数は通常、秘密鍵を含まない公開された関数である。ハッシュ関数はまた、認証及び完全性の尺度を提供することもできる。ハッシュ関数は、ディジタル署名アルゴリズムにとって、及びパスワードの保護にとって不可欠である場合が多いが、これは、パスワードの制御のためにパスワード自体に代わってパスワードのハッシュ値が使用されてもよく、それによって通信ネットワーク等を介して送信される必要があるのはパスワード自体ではなくハッシュ値のみになるからである。
【００６５】
秘密鍵を入力として使用するハッシュ関数は、しばしばＭＡＣアルゴリズム又は“鍵付きハッシュ関数”と呼ばれる。ＭＡＣアルゴリズムは、認証及びデータの完全性を保証するために使用される。これは、特定のメッセージが、当該メッセージに発信元であったと表示されている人物又はエンティティから着信したこと（認証）と、当該メッセージが伝送（中継）中に変更されなかったこと（完全性）とを保証する。これは、ＩＰｓｅｃプロトコル（２００１年１２月７日において、http://www.rfc-editor.org で利用可能な、ＲＦＣ  ２４０１を参照。）において、例えば、複数のＩＰパケットが、それらが送信されるときと、それらがその最終的な宛先へ到達するときとの間に変更されていないことを保証するために使用される。これはまた、あらゆる種類の銀行間の送金プロトコルにも使用される。
【００６６】
先に議論した通り、本発明の第１の態様による方法は、ハッシュ又はＭＡＣアルゴリズムに実装可能である。ハッシュ又はＭＡＣアルゴリズムは、所定量の任意長さのデータのチェックサムを計算し、そのチェックサムを結果として与える。この処理は不可逆（一方向）でなければならず、入力値の小さな変化が結果的に大幅に異なる出力を生じさせる必要がある。従って、データ入力への感度は高くなければならない。ハッシュ関数は鍵をシード値として使用しないのに対して、ＭＡＣアルゴリズムは、アルゴリズムのためのシード値を表すか又は決定するこうした鍵を使用し、それにより結果が鍵に依存する。ハッシュ関数は、鍵の代わりに、例えば数πからの所定のビットであるような定数に依存する。代替として、ハッシュ関数が適用されるデータの一部がシード値として使用されてもよい。
【００６７】
ハッシュ／ＭＡＣアルゴリズムは、下記のように実装可能である。
−  当該アルゴリズムでは、ロジスティックマップの形式の数学的システムが使用される。ロジスティックマップは、λをパラメータとして、ｘｎ＋１＝λｘｎ（１−ｘｎ）の形式を有する。後に詳細に議論されるローレンツ（Lorenz）システムのような他のカオス的システムが使用されてもよい。
−  そのチェックサムが計算されるべきメッセージｍに対して当該アルゴリズムが依存する結果として、メッセージは当該システムにその１つの構成要素として組み込まれている。例えば、メッセージと動的変数ｘとのある種の結合が、式ｘｎ＋１＝λｘｎ（１−ｘｎ）＋ε（ｘｎ−ｍｎ）を用いて行われてもよい。
−  パラメータλ及びεと初期値ｘ０とは、メッセージから予め決定され、及び／又はメッセージから導出されてもよい。ＭＡＣアルゴリズムの場合、パラメータλ及びεと初期値ｘ０とは、秘密鍵から完全に又は部分的に決定されることが可能である。
−  当該システムは、メッセージの終わりに到達するまで反復される。ｘ又は最下位ディジットのようなその一部の最終的な計算値は、例えばハッシュ値、ＭＡＣ又はチェックサムとして表される。代替として、結果として得られる数の抽出に先行して、多くの追加の反復を実行することもできる。ｘの最終的な計算値を抽出する代わりに、もしくはこれを抽出することに加えて、計算で無視されていた所定のビットをハッシュ値として抽出することもできる。
−  メッセージｍを力学システム（系）へ導入する方法は変更されうる。例えば、メッセージの一部を使用して、各反復においてｘ変数に影響を与えることができる。このような影響は、例えばメッセージの複数の所定のビットに対してＸＯＲ（排他的論理和）演算を実行してｘの最下位ディジットを得ることにより達成可能である。
【００６８】
ハッシュ／ＭＡＣ関数に関する別の詳細は、ブルース・シュナイアー（Bruce Schneier）による“応用暗号学（Applied Cryptography）”第２版，ジョン・ワイリー・アンド・サンズ（John Wiley & Sons），１９９６年で参照される。
【００６９】
本発明の第１の態様による方法の利用分野としての１つの可能性は、非対称アルゴリズムとも呼ばれる公開鍵暗号化である。復号化に使用される鍵は、暗号化に使用される鍵とは異なる。例えば、鍵発生関数は、１つは暗号化のための鍵であり、もう１つは復号化のための鍵である１対の鍵を発生する。一方は秘密鍵であり、他方は公開鍵である。後者は、暗号化されていないバージョンでインターネットを介して送信されてもよい。暗号化鍵は、カオス的システムのための複数のパラメータ及び／又は初期条件を構成するか、もしくは含むことが可能である。平文は、秘密鍵によって開始されない限り非可逆であるカオス的システムを変調するために用いられる。復号化のためには、暗号化に使用されるシステムのダイナミクス（力学）とは逆のダイナミクスを有する数学的システムが使用される。
【００７０】
本発明の第１の態様による方法においては、固定小数点の数として表現された変数を含む計算が、浮動小数点の数及び整数のような他の種類の数として表現された１つ又は複数の変数を含む、他のタイプの変数での計算を含む可能性がある。
【００７１】
数学的システムは、離散的なシステムであっても、連続的なシステムであってもよい。以下、様々なタイプの数学的システムについて検討する。
【００７２】
計算は、各固定小数点の数が小数点分離記号を有する少なくとも第１及び第２の固定小数点の数を含むことが可能であり、第１の固定小数点の数の小数点分離記号は第２の固定小数点の数の小数点分離記号の位置とは異なる位置に位置決めされている。第１及び第２の固定小数点の数の小数点分離記号は、選択された位置に位置決めされてもよい。
【００７３】
結果として得られる数は、
整数と、
浮動小数点の数と、
固定小数点の数と
で構成されるグループから選択された変数として表現されることが可能である。
【００７４】
一般に、数学的システムは、１つ又は複数の微分方程式か、もしくは１つ又は複数の離散的マップ又はマッピングを含むことが可能である。微分方程式の場合、数学的システムは、１つ又は複数の常微分方程式及び／又は１つ又は複数の偏微分方程式を含むことが可能である。離散的マッピングの場合、数学的システムは、１つ又は複数の領域を保存するマップ、及び／又は１つ又は複数の領域を保存しないマップを含むことが可能である。数学的システムの少なくとも１つの関数は、非線形であることが可能である。
【００７５】
本発明の方法はまた、積分方程式を含む他のタイプの関数又は方程式に適用可能である。少なくとも１つの非線形微分方程式又はマッピングはカオス的挙動を呈する可能性がある。すなわち、これは、少なくとも１つの正のリヤプノフ指数を有することがあり、この場合、本方法は、数学的計算の間に少なくとも１回はリヤプノフ指数を計算することを含むことが可能である。数学的システムがカオス的挙動を呈する場合には、本発明の方法は、擬似乱数発生方法において、例えば暗号化／復号化方法において効果的に適用されることが可能である。当該数学的システムがカオス的挙動を呈するか否かを決定するために、数学的計算の間に少なくとも１回だけ少なくとも１つのリヤプノフ指数が計算されてもよい。当該数学的システムがカオス的挙動を呈していないとき、例えば計算されたリヤプノフ指数が正でないときには、計算は中断され、他の初期値及び／又は他のパラメータから再開されることが可能である。
【００７６】
少なくとも非線形な微分方程式又はマッピングは、好適には、少なくとも１つの独立変数ｔの関数でありうる少なくとも１つの状態変数Ｘを決定する。
【００７７】
特に、数学的システムは以下のシステムのうちの１つ又は複数のものを含むことが可能である。
−  以下のものを含む連続な微分方程式、
−  ナビエ・ストークス方程式等の偏微分方程式、
−  以下のものを含む常微分方程式、
−  ローレンツシステム、結合されたローレンツシステム、レスラー（Roessler）システム、結合されたレスラーシステム、ハイパーカオス的レスラーシステム、ウエダ（Ueda）システム、最も単純な２次の散逸的なカオス的フロー、最も単純な区分的な線形の散逸的なカオス的フローを含む散逸フローのような自律システム、
−  Ｎ≧３とするとき、天体力学からのＮ体問題を含むハミルトニアンシステム、
−  強制ダフィング方程式、強制負性抵抗発振子、強制ブリュセレータ（forced brusselator）、強制減衰振り子方程式、結合された振子、強制二重井戸発振子、強制ファン・デル・ポール発振子のような強制システムを含む非自律システム、
−遅延ロジスティック方程式、母集団モデル（population model）を含む遅延微分方程式。
【００７８】
−  以下のものを含む離散的マッピング、
−  以下のものを含む、領域を保存する及び領域を保存しないマップ、
−  テントマップ、非対称テントマップ、２ｘモジュロ１マップ及びアノーソフ（Anosov）マップと、一般化されたベーカー（Baker's）マップ、ロジ（Lozi）マップとのような、任意次元の区分的に線形のマップとともに、区分的に線形なマップの、より高次への一般化及び／又は結合、
−  ロジスティックマップ、エノン（Henon）マップ及びＮ連結ロジスティックマップを含む（２次又はより高次の）多項式マップと、Ｎ連結エノンマップ等の多項マップの、より高次への一般化及び／又は結合、
−  サインサークル（Sine circle）マップ、サイン（正弦）マップ、チリコフ（Chirikov）標準マップ、シナイ（Sinai）マップ、標準マップを含む三角関数マップと、三角関数マップの、より高次への一般化及び／又は結合、
−  ベルヌーイシフト、１０進シフト、馬蹄形マップ、イケダ（Ikeda）マップ、パイコネ（pastry）マップ、ディジタルフィルタのモデル、１次元の任意マップからの２次元のエノン型マップの構成、デボジェラエーレ（DeVogelaere）マップを含むその他のマップ。
−  セルオートマトン。
−  ニューラルネットワーク。
【００７９】
上述のレスラーシステムは、次式の形式を有する。
【００８０】
【数９】
2004530919.tif 000011
【数１０】
2004530919.tif 000012
【数１１】
2004530919.tif 000013
【００８１】
ここで、典型的なパラメータ値は、ａ＝ｂ＝０．２，ｃ＝５．７である。レスラーシステムについては、オー．イー．レスラー（O. E. Roessler），フィジカル・レターズ（Phys. Lett.），５７Ａ，３９７−３９８，（１９７６年）にさらに詳しく記述されている。
【００８２】
上述のエノンマップは、次式の形式を有する。
【００８３】
【数１２】
2004530919.tif 000014
【００８４】
ここで、典型的なパラメータ値は、ａ＝１．４，ｂ＝０．３である。詳細に関しては、エム．エノン（M. Henon），コミュニケーションズ・イン・マセマティカル・フィジクス（Commun. Math. Phys.），５０，６９−７７，（１９７６年）を参照されたい。
【００８５】
ｘｎ＋１＝μｘｎ（１−ｘｎ）の形式のロジスティックマップが使用されてもよい。次式の形式を有し、しばしば猫写像（cat map）と呼ばれるアノーソフマップが使用されてもよい。
【００８６】
【数１３】
2004530919.tif 000015
【００８７】
マップは、ｉ）線形の行列乗算と、ｉｉ）非線形のモジュロ演算との２つのステップで構成され、後者は、反復を単位正方形内部に保持させる。アノーソフマップは、任意個数の変数に一般化することが可能である。さらに行列は、領域保存性であることとシステムに対して少なくとも１つの正のリヤプノフ指数を有することとの必要条件によってのみ制限される任意の係数を有することが可能である。これらの指数は、このようなシステムに対して解析的に計算可能である。詳細に関しては、エー．ジェイ．リヒテンベルク（A.J. Lichtenberg）及びエム．エー．リーバーマン（M. A. Liebermann），正則及びカオス力学（Regular and Chaotic Dynamics），シュプリンガー（Springer），１９９２年，（ｐ．３０５）を参照されたい。
【００８８】
さらに、結合マップの１つのタイプであるマップ格子が使用されてもよい。下記の例では、ｘｉは（複数の点にてなるＮ次元アレーで表現された）格子上の変数を表し、格子は、Ｍ個の点を有する１次元アレーである。格子上の各点は、矢印の右側の関数によって更新される。ここで、関数ｆは、例えばロジスティックマップであってもよい。例から分かるように、格子上の隣接する点は線形に結合し、ここで、線形の結合はパラメータγ及びεによって調整される。境界条件は、格子要素１及びＭが扱われる方法を示す。
【００８９】
【数１４】
2004530919.tif 000016
【００９０】
最後に、ある簡単な３次元の流動方程式（flow equation）を使用することが可能である。システムは通常、ローレンツシステム及びレスラーシステムより少ない項で構成される。すなわち、５つの項及び２つの非線形項（nonlinearity）、又は６つの項及び１つの非線形項のいずれかである。これに比べてローレンツ及びレスラーシステムは各々、７つの項で構成されている。ジェイ．シー．スプロット（J. C. Sprott），フィジカル・レビュー（Phys. Rev.），Ｅ５０，Ｒ６４７−Ｒ６５０，（１９９４年）を参照されたい。適正なシステムは、下記のリストで与えられる。
【００９１】
【数１５】
2004530919.tif 000017
【数１６】
2004530919.tif 000018
【数１７】
2004530919.tif 000019
【数１８】
2004530919.tif 000020
【数１９】
2004530919.tif 000021
【数２０】
2004530919.tif 000022
【数２１】
2004530919.tif 000023
【数２２】
2004530919.tif 000024
【数２３】
2004530919.tif 000025
【数２４】
2004530919.tif 000026
【数２５】
2004530919.tif 000027
【数２６】
2004530919.tif 000028
【数２７】
2004530919.tif 000029
【数２８】
2004530919.tif 000030
【数２９】
2004530919.tif 000031
【数３０】
2004530919.tif 000032
【数３１】
2004530919.tif 000033
【数３２】
2004530919.tif 000034
【数３３】
2004530919.tif 000035
【００９２】
ローレンツシステムは、次式の微分方程式を含む。
【００９３】
【数３４】
2004530919.tif 000036
【数３５】
2004530919.tif 000037
【数３６】
2004530919.tif 000038
【００９４】
ここで、Ｘ＝（ｘ，ｙ，ｚ）は状態変数であり、ｔは独立変数であり、σ、ｒ及びｂはパラメータである。
【００９５】
次式の条件が満たされる場合には、ローレンツシステムの定常点は安定ではなく、この場合のローレンツシステムは、おそらくカオス的挙動を呈している。
【００９６】
【数３７】
2004530919.tif 000039
【００９７】
複数のパラメータは一定であっても、あるいは可変であってもよく、複数の可変なパラメータであれば、例えば計算結果がより予測不可能となることに寄与し、これは、擬似乱数発生方法又は暗号化／復号化方法においては有益である可能性がある。
【００９８】
非線形マッピングの場合、計算は非線形関数の数値的な反復を含むことができ、反復は、状態変数Ｘの初期条件Ｘ０に基づいている。
【００９９】
計算を実行するステップは、ｍ≦ｎ＋１として１つ又は複数の以前の解Ｘｍと独立変数ｔのステップ長ΔＴｎとに基づいて解Ｘｎ＋１を反復して計算することにより、非線形微分方程式を数値積分することを含んでもよい。好適には、状態変数Ｘの少なくとも１つの初期条件Ｘ０と、ステップ長の初期値ΔＴ０とが提供される。ステップ長は、計算が開始される前に与えられてもよく、又は、計算の進行に伴って計算されてもよい。例えば、ステップ長の初期値ΔＴ０は、初期条件Ｘ０から計算されてもよい。
【０１００】
ローレンツシステムの離散化された定式化では、解Ｘｎ＋１は、ステップ長ΔＴ＝（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）を使用して次式のように計算可能である。
【０１０１】
【数３８】
2004530919.tif 000040
【数３９】
2004530919.tif 000041
【数４０】
2004530919.tif 000042
【０１０２】
ここで、
Δｔｘ，ｎはｘｎ＋１の計算に使用されるステップ長であり、
Δｔｙ，ｎはｙｎ＋１の計算に使用されるステップ長であり、
Δｔｚ，ｎはｚｎ＋１の計算に使用されるステップ長である。
【０１０３】
上述した通り、ステップ長ΔＴは、計算を通して一定であってもよく、又は変化してもよい。例えば、積分ステップの各々又はいくつかにおいて、ステップ長ΔＴの要素（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）のうちの少なくとも１つが、計算に関わる、もしくは計算から導出される１つ又は複数の数の関数であってもよい。また、各積分ステップにおいて、ステップ長ΔＴの要素（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）のうちの少なくとも１つが、当該数学的システムに対する現在の解又は以前の解である、少なくとも１つの解Ｘｍの関数であってもよい。積分ステップの各々又はいくつかにおいては、ステップ長ΔＴの要素（Δｔｘ，ｎ，Δｔｙ，ｎ，Δｔｚ，ｎ）のうちの少なくとも１つが、現在又は以前の積分ステップである、少なくとも１つのステップ長ΔＴｍの関数である。変化するステップ長ΔＴは、本発明による方法だけでなく、微分方程式の任意の数値解にも使用可能であり、従って、本発明はまた、独立した態様として、可変なステップ長を使用して微分方程式を数値的に解く方法にも関連する。暗号化／復号化方法におけるような擬似乱数発生方法では、可変なステップ長は、システムのセキュリティの改善、すなわち結果として得られる鍵ストリームをさらに予測不可能なものにすることに寄与しうる。
【０１０４】
擬似乱数発生方法では、初期条件Ｘ０及び／又はステップ長の初期値ΔＴ０は、シード値から計算されてもよく、もしくはシード値を表現してもよい。暗号化／復号化方法では、初期条件Ｘ０の少なくとも一部及び／又はステップ長の初期値ΔＴ０の少なくとも一部は、暗号化鍵から計算されてもよく、もしくは暗号化鍵を表現してもよい。また、数学的システムの少なくともいくつかのパラメータの少なくとも一部は、シード値又は暗号化鍵から計算されてもよく、もしくはシード値又は暗号化鍵を表現してもよい。鍵は、公開鍵であっても、秘密鍵であってもよい。
【０１０５】
抽出されたデータのセットは、暗号化に使用可能な擬似乱数を含む可能性がある。計算から結果として得られる複数の数が抽出されうる。抽出するステップは、結果となる１つ又は複数の数からのｋ個の最下位ビットのような、結果として得られる数の複数ｋ個のビットから導出される１つ又は複数の数を抽出することを含んでもよく、このことは、導出される数の予測不可能性に寄与する。抽出されるｋビットは、例えば、結果となる１つ又は複数の数にモジュラス又は論理“積”関数を適用することによって導出可能である。抽出するステップは、最下位のｋビットを抽出することの代替として、結果として得られる数の予め決められた位置又は可変な位置におけるｋビットを抽出することを含んでもよい。数ｋは、１６−６４、２４−３２のような、８と１２８との間の範囲から選択された整数値であることが可能である。複数の数が抽出される場合、抽出される数は異なる値のｋによって導出されてもよく、このことがさらに、導出される数の予測不可能性に寄与する。抽出された１つ又は複数の数は、結合されたデータのセットを得るために、算術演算及び／又は論理演算によって操作されることが可能であれる。抽出された１つ又は複数の数及び／又は結合されたデータのセットは、元のデータを暗号化するために、算術演算及び／又は論理演算において元のデータと結合されることが可能である。同様に、抽出された１つ又は複数の数及び／又は結合されたデータのセットは、暗号化されたデータを復号化して元のデータを得るために、算術演算及び／又は論理演算において暗号化されたデータと結合されることが可能である。算術演算及び／又は論理演算は、ＸＯＲ演算、乗算又は加算を含むことが可能である。例えば、算術演算及び／又は論理演算は、暗号化のための、元のデータと結合されたデータのセットとの加算と、復号化のための、暗号化されたデータからの結合されたデータのセットの減算とを含んでもよい。代替として、算術演算及び／又は論理演算は、暗号化のための、元のデータからの結合されたデータのセットの減算と、復号化のための、結合されたデータのセットと暗号化されたデータとの加算とを含む。数の減算又は加算を行うときには、モジュラス関数を適用することが必要な場合がある。抽出されたデータのセットが、複数の数から導出されたデータを含む場合、例えば最下位のｋビットである、複数のビットにてなる１つのセットは、１つの数から抽出されることが可能であり、それに対して、例えば６４ビット数における４７−５４番目のビットである他のビットは、他の数から抽出されることが可能である。
【０１０６】
ブロック暗号の暗号化／復号化システムでは、例えば暗号文を出力として与える暗号化システムに対して平文と鍵とが入力されるように、計算は、平文のブロックを表現するデータに作用することができる。ブロック暗号の暗号化及び復号化システムでは、平文のブロックに対する少なくとも１つの演算を定義するために、抽出されたデータのセットが使用されてもよい。本発明の第１の態様による方法はブロック暗号アルゴリズムに適用可能であり、ここで、平文のブロックは２つのサブブロックに分割され、一方のサブブロックは、他方のサブブロックに影響を与えるために使用される。ここでは、例えば、変更されたバージョンの最初のブロック（又はその一部）が、ＸＯＲ関数等によって他方（又はその一部）に影響を与えるために使用される。このようなアルゴリズムは一般にフェイステル（Feistel）ネットワークと呼ばれる。ブルース・シュナイアーによる応用暗号学，第２版，ジョン・ワイリー・アンド・サンズ，１９９６年が参照される。このような場合、第１のサブブロック又はその変更されたバージョンは、本方法に依存するハッシュ関数によって変換されることが可能である。このハッシュ関数は、入力として暗号鍵を与えられる。反復毎に、ハッシュ関数には新たな暗号鍵を入力として与えてもよい。代替として、ハッシュ関数にはすべてのラウンドで同じ暗号鍵を与えることもできる。別の代替として、例えば、同じ暗号鍵を各ブロックの全ラウンドで入力として与えることにより、もしくは異なる暗号鍵を各ラウンドで各ブロックに対して入力として与えることにより、暗号鍵をブロック毎に変化させることもできる。
【０１０７】
抽出されたデータは、復号化鍵又は暗号化鍵として使用可能である。計算が２つの数学的システムで実行されるシステムでは、一方のシステムから抽出されたデータのセットは、他方のシステムの鍵の発生に使用されるか、もしくは他方のシステムの鍵として使用されることが可能である。抽出されたデータはまた、ディジタル署名を表現するデータの発生に、及び／又はディジタルデータへの電子透かしの埋め込みにも使用可能である。
【０１０８】
本発明の第１の態様による方法において、電子装置は所定のレジスタ幅を有する電子処理装置を備えてもよく、これにより当該方法は、
−  上記レジスタ幅より大きいビット幅の少なくとも１つの整数を、高々上記レジスタ幅に等しいビット幅をそれぞれ有する少なくとも２つのサブナンバーとして表現するステップと、
−  上記計算の少なくとも１つを上記サブナンバーの各々に対するサブ計算として実行し、高々上記処理装置のレジスタ幅に等しい、より小さなビット幅の整数として表された少なくとも２つの部分的結果に到達するステップと、
−  上記部分的結果を連結して、上記少なくとも１つの計算の結果の表現を発生させるステップとを含む。
【０１０９】
同様に、プロセッサのレジスタ幅より小さい幅の数の計算も実行可能であって、それによって、例えば論理積のような演算が実行可能であり、例えば６４ビットレジスタの場合、３２ビットの数に関する計算には６４ビットレジスタの上位半分は使用されない。問題となる数の符号を保持するため、例えば３２ビットの数の最上位ビットは、６４ビットレジスタの上位３２ビットへコピーされてもよい。
【０１１０】
整数は、通常、計算に使用される１つ又は複数の固定小数点の数を含み、もしくは表現している。整数型の数として表現される固定小数点の数は、実数を表すことが可能である。
【０１１１】
本発明の第１の態様による方法は、以下本発明の他の態様に関連して議論される任意のステップと組み合わされうるということは理解される必要がある。
【０１１２】
本発明はまた、少なくとも１つの関数を含む数学的システムにおいて数値計算を実行するコンピュータプログラムに関し、当該コンピュータプログラムは、
−  上記数学的システムを複数の離散的な項で表現することと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現することと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行することと、
−  上記計算から、結果として得られる数を取得することとに適応化され、上記結果として得られる数は、
−  ａ．上記数学的システムに対する解の少なくとも一部と、
−  ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
当該コンピュータプログラムはさらに、
−  ｉ．上記結果として得られる数のディジットのうちのサブセットと、
−  ｉｉ．上記結果として得られる数から導出された数のディジットのうちのサブセットと
の少なくとも一方を表現するデータのセットを抽出するように適応化されている。
【０１１３】
本コンピュータプログラムはさらに、本願明細書で検討されている任意の演算及び方法のステップを実行するように適応化されていてもよい。本発明はまた、このようなコンピュータプログラムがロードされる、コンピュータが読み取り可能なデータキャリアに関し、かつこのようなコンピュータが読み取り可能なデータキャリアを備えたコンピュータ、又はこのようなコンピュータが読み取り可能なデータキャリアに接続されたコンピュータに関し、上記コンピュータは、当該プログラムを実行するプロセッサ手段を備えている。
【０１１４】
本発明はまた、数学的システムにおける計算から導出されている抽出されたデータのセットを含む信号に関し、抽出されたデータのセットに到達することを目的として、
−  上記数学的システムは複数の離散的な項で表現され、
−  上記数学的システムの少なくとも１つの変数は固定小数点の数として表現され、
−  上記計算は、固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように実行され、かつ、
−  結果として得られる数は上記計算から取得され、上記結果として得られる数は、
−  ａ．上記数学的システムに対する解の少なくとも一部と、
−  ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
これにより、抽出されたデータのセットは、
−  ｉ．上記結果として得られる数のディジットのうちのサブセットと、
−  ｉｉ．上記結果として得られる数から導出された数のディジットのうちのサブセットと
の少なくとも一方を表現する。
【０１１５】
本発明はさらに、平文と、数学的システムにおける計算から抽出された少なくとも１つのデータのセットとの組み合わせとして導出されている暗号化されたデータのセットを含む信号に関し、上記抽出されたデータのセットに到達することを目的として、
−  上記数学的システムは複数の離散的な項で表現され、
−  上記数学的システムの少なくとも１つの変数は固定小数点の数として表現され、
−  上記計算は、固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように実行され、かつ、
−  結果として得られる数は上記計算から取得され、上記結果として得られる数は、
−  ａ．上記数学的システムに対する解の少なくとも一部と、
−  ｂ．上記数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
これにより、抽出されたデータのセットは、
−  ｉ．上記結果として得られる数のディジットのうちのサブセットと、
−  ｉｉ．上記結果として得られる数から導出された数のディジットのうちのサブセットと
の少なくとも一方を表現する。
【０１１６】
本発明の任意の方法及び／又はコンピュータプログラムから導出される任意のデータ及びこのようなデータを含む任意の信号もまた、添付された請求の範囲に含まれるということは理解される必要がある。さらに、後述される本発明の別の態様に関して以下に記述される任意の特徴、方法のステップ、又は機能は、本発明の第１の態様による方法と組み合わされうるということは理解される必要がある。
【０１１７】
第２の態様において、本発明は、少なくとも１つの独立変数に関連した少なくとも１つの状態変数を決定する少なくとも１つの非線形関数を含む数学的システムに対する解における周期的な挙動を検出する方法に関し、当該方法は、
−  数学的システムを複数の離散的な項で表現することと、
−  計算を実行して、結果として得られる数を取得することを含み、上記結果として得られる数は上記数学的システムに対する解の少なくとも一部を表現し、
−  選択された解を電子装置のメモリにおけるアレーＡに記憶することを含み、上記アレーは有限個数ｎ＋１個の解を記憶するように適応化され、
当該方法は、
−  現在の解と、
−  上記アレーに記憶された上記解の特定の１つと
の少なくとも一方が、上記アレーに記憶された他の解と実質的に同一であるか否かを決定することを含む。
【０１１８】
計算を実行するステップと、選択された解を記憶するステップと、決定するステップとは、計算の間に連続して、すなわち計算の間に、例えば各反復に関連して、例えば各計算ステップで繰り返し実行されてもよい。
【０１１９】
現在の解又はアレーに記憶された解の特定の１つが、アレーに記憶された１つ又は複数の他の解と実質的に同一であれば、数学的システムの解はおそらく周期的な挙動を示している。本発明の第２の態様による方法が擬似乱数発生方法において使用される場合、特にこれが暗号化／復号化方法に使用されるとすれば、このような周期的な挙動は、発生された擬似乱数又は鍵ストリームの予測不可能性に悪影響を及ぼすことから望ましくない。上述の方法を適用すれば、周期的な挙動を検出することができる。
【０１２０】
現在の解又はアレーに記憶された解の特定の１つが、アレーに記憶された１つ又は複数の他の解と実質的に同一であるか否かを決定するステップは、好適には、解が完全に同一であるか否かを決定することを含む。状態変数Ｘのアレーを表す数学的システムを解く場合、この決定するステップは、Ｘのエントリのうちの一部のみが実質的に同一であるか否かを決定することを含んでもよい。
【０１２１】
計算時間及び／又はメモリを節約するために、選択された解のみがメモリに記憶されてもよい。
【０１２２】
当該方法において、アレーにおける各エントリは、アレーレベルＡｉ，０≦ｉ≦ｎ毎に増大している経過時間を有する解を含んでもよく、当該方法は、
−  選択された解をアレーに記憶するステップにおいて、現在の解をアレーＡにおける０番目のレベルＡ０に記憶し、これにより、アレーＡにおける０番目のレベルで記憶された古い値に上書きすることと、
−  ０番目の予め決められた基準が満たされているとき、０番目のレベルが現在の解によって上書きされる前に古い値をアレーＡにおける１番目のレベルへ移動することとを含み、
アレーにおける第１のレベル及びそれ以上の各レベルｉに対しては、
−  レベルｉに対するｉ番目の予め決められた基準が満たされているとき、ｉ番目のレベルがｉ−１番目のレベルから移動される値によって上書きされる前に、ｉ番目のレベルに記憶された古い値をアレーＡにおけるｉ＋１番目のレベルへ移動することを含み、
ｎ番目のレベルが更新されるとき、ｎ番目のレベルに以前に記憶された古い値を廃棄することを含む。
【０１２３】
アレー内の各レベルｉに対して、ｉ番目のレベルに記憶された古い値がｉ＋１番目のレベルへ移動されることなく新しい値によって上書きされている回数を計数してもよく、予め決められた回数だけ古い値が移動されなかったならときにｉ番目の予め決められた基準は満たされる。この予め決められた回数は、アレーＡのすべてのレベルで同一であってもよく、又は、それは複数のレベルの間で変化してもよい。アレーＡのｉ番目のレベルに対するこの予め決められた回数は、例えば、１つ又は複数の値において符号の変化が発生する時などのように、アレーに記憶された１つ又は複数の値に依存してもよい。
【０１２４】
現在の解又はアレーに記憶された上記解の特定の１つが、アレーに記憶された１つ又は複数の他の解と実質的に同一であるか否かを決定するステップは、所定のテスト基準が満たされている場合にのみ実行されてもよい。例えば、テスト基準は、少なくとも１つの状態変数の符号が＋から−へ変化する場合、又は−から＋へ変化する場合、もしくはこれらの両方の場合に満たされうる。テスト基準はまた、少なくとも１つの独立変数に関する、少なくとも１つの状態変数の少なくとも１つの導関数の符号に変化が生じるときに満たされうるが、この場合は、当該方法はさらに導関数の計算を含む。
【０１２５】
当該方法において、テスト値は少なくとも１つの状態変数から、及び／又は導関数から計算されてもよく、テスト基準はこのテスト値に基づいている。テスト基準は、テスト値の符号又はテスト値の導関数の符号に変化が生じるときに満たされてもよく、もしくは予め決められた値が提供されてもよい。
【０１２６】
計算を実行するステップは、本発明の第１の態様による方法を適用することによって実行されてもよく、本発明の第１の態様に関連して議論される任意のステップとともに、本発明の別の態様による方法に関連して後述される任意のステップとが含まれてもよい。
【０１２７】
第３の態様において、本発明は擬似乱数を発生する方法に関し、当該方法は、
Ｉ）数学的システムを複数の離散的な項で表現することと、
ＩＩ）数学的システムの少なくとも初期条件を表現するシード値を定義することと、
ＩＩＩ）数学的システムの少なくとも１つの変数を固定小数点の数として表現することと、
ＩＶ）固定小数点の数として表現された少なくとも１つの変数を含む計算を実行し、かつ、上記計算から、結果として得られる数を取得することを含み、結果として得られる数は、
ａ．数学的システムに対する解の少なくとも一部と、
ｂ．数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
Ｖ）計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出することを含む。
【０１２８】
当該方法が暗号化／復号化方法に適用される場合、シード値は、暗号化／復号化鍵のようなユーザが定義する値であってもよい。
【０１２９】
擬似乱数は、例えば１つ又は複数の数の最下位のｋビット又は選択されたｋビットであるような、計算の間に発生した１つ又は複数の数のｋ個のディジットから導出された数として抽出されてもよい。
【０１３０】
当該方法は、所定量の擬似乱数が発生されるまでステップＩＶ）及びステップＶ）を反復することを含んでもよい。
【０１３１】
所定量の擬似乱数がスペアのシード値として発生されて、電子装置のメモリに記憶されてもよく、これは、例えば、本発明の第２の態様による方法によって、もしくは他の方法によって周期的な挙動が検出された場合に使用可能である。所定量の擬似乱数は、アルゴリズム内に記憶されてもよい。
【０１３２】
当該方法はさらに、先に議論したように、本発明の第２の態様による周期的な挙動を検出するための方法を含んでもよい。その場合、本発明の第３の態様による擬似乱数を発生するための方法は、
現在の解又はアレーに記憶された上記解の特定の１つが、アレーに記憶された１つ又は複数の他の解と実質的に同一であるか否かを決定するステップが、現在の解又は特定の解が１つ又は複数の他の解と同一であることを示すときに、
擬似乱数の発生を中断する、すなわちステップＩＶ）及びステップＶ）の反復を中断することと、
スペアのシード値をステップＩＩ）においてシード値として使用することと、
擬似乱数の発生を再開する、すなわちステップＩＶ）及びステップＶ）の反復を再開することを含むことができる。
【０１３３】
従って例えば、暗号化／復号化方法においては、周期的な挙動が検出されれば、スペアの暗号化／復号化鍵が使用されうる。
【０１３４】
擬似乱数の発生を再開するステップに先行して、所定量の擬似乱数が新たなスペアのシード値として発生されて、電子装置のメモリに記憶されてもよい。ステップＩＶ）及びステップＶ）がステップＩＩ）における新たなシード値を用いて開始されるときには、アレーＡの各レベルは、好ましくはステップＩＶ）に先行してリセットされる。
【０１３５】
本発明の第３の態様による方法は、本発明の第１の態様に関連して上述されたステップ、及び／又は本発明の別の態様に関連して後述されるステップを含んでもよい。
【０１３６】
第４の態様において、本発明は、元のデータのセットを、暗号化されたデータのセットに暗号化する方法に関し、当該方法は、
Ａ）擬似乱数を、
Ｉ）数学的システムを複数の離散的な項で表現するステップと、
ＩＩ）数学的システムの少なくとも初期条件を表現する暗号化鍵を定義するステップと、
ＩＩＩ）数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
ＩＶ）固定小数点の数として表現された少なくとも１つの変数を含む計算を実行し、かつ上記計算から、結果として得られる数を取得するステップであって、結果として得られる数は、
ａ．数学的システムに対する解の少なくとも一部と、
ｂ．数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現するステップと、
Ｖ）計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出するステップとを実行することによって発生するステップと、
Ｂ）元のデータ及び擬似乱数を、
ｉ．算術演算と、
ｉｉ．論理演算と
の少なくとも一方によって操作し、結合されたデータのセットを取得するステップとを含み、上記結合されたデータのセットは暗号化されたデータである。
【０１３７】
ステップＡ）に先行して、元のデータのサブセットがデータのセットから分離されてもよく、ステップＢ）はこのデータのサブセットに対して実行されてもよい。このステップは、元のデータのセット全体を共同で構成する複数のサブセットが暗号化されるまで反復されることが可能である。
【０１３８】
擬似乱数は、例えば最下位のｋビット又は選択されたｋビットであるような、計算の間に発生した１つ又は複数の数のｋ個のディジットから導出された数として抽出されてもよい。
【０１３９】
ステップＩＶ）及びステップＶ）は、所定量の擬似乱数が発生されるまで反復されてもよい。
【０１４０】
所定量の擬似乱数がスペアの暗号化鍵として発生されて、電子装置のメモリに記憶されてもよい。例えば、計算の少なくとも１つの積分又は反復ステップから結果として得られる、もしくは生じる数は、スペアの暗号化鍵として記憶されることが可能である。スペアの暗号化鍵は、例えば、数学的システムに対する解における周期的な挙動の発生に起因して暗号化が中断されるときに使用されうる。スペアの暗号化鍵を出力することが不要である場合には、これは暗号化アルゴリズム内に記憶されてもよい。当該方法が復号化に使用される場合、スペアの鍵は復号化鍵である。
【０１４１】
上記記述から明らかであるように、当該方法は、本発明の第２の態様による周期的な挙動を検出するための方法を含んでもよく、その場合、本発明の第４の態様による暗号化するための方法は、
現在の解又はアレーに記憶された上記解の特定の１つが、アレーに記憶された１つ又は複数の他の解と実質的に同一であるか否かを決定するステップが、現在の解又は特定の解が１つ又は複数の他の解と同一であることを示すとき、
擬似乱数の発生を中断する、すなわちステップＩＶ）及びステップＶ）の反復を中断することと、
スペアの暗号化鍵をステップＩＩ）において暗号化鍵として使用することと、
擬似乱数の発生を再開する、すなわちステップＩＶ）及びステップＶ）の反復を再開することを含むことができる。
【０１４２】
擬似乱数の発生を再開するステップに先行して、所定量の擬似乱数が新たなスペアの暗号化鍵として発生されて、電子装置のメモリに記憶されてもよい。
【０１４３】
好適には、ステップＩＶ）及びステップＶ）がステップＩＩ）における新たなシード値を用いて開始されるときには、アレーＡの各レベルは、ステップＩＶ）に先行してリセットされる。
【０１４４】
本発明の第４の態様による暗号化のための方法はさらに、本発明の第１、第２及び第３の態様による方法に関連して上述された任意のステップ、及び／又は本発明の別の態様に関連して後述される任意のステップを含んでもよい。
【０１４５】
第５の態様において、本発明は、本発明の第４の態様による方法によって暗号化されている暗号化されたデータのセットを復号化する方法に関し、この第５の態様による復号化するための方法は、
ａ）暗号化方法に関連して先に定義されたステップＡ）を実行することで、暗号化方法のステップＶ）において抽出されたものと同じ擬似乱数を抽出するステップと、
ｂ）暗号化されたデータ及び擬似乱数を算術演算及び／又は論理演算によって操作し、元のバージョンのデータ、すなわち復号化されたバージョンのデータを取得するステップとを含む。
【０１４６】
ステップａ）に先行して、暗号化されたデータのサブセットは暗号化されたデータのセットから分離されてもよく、かつデータのサブセットが上述の暗号化方法によって暗号化されている場合、復号化する方法は、このデータのサブセットに対してステップａ）及びステップｂ）を実行することを含みうる。このステップは、暗号化されたデータのセット全体を共同で構成する複数のサブセットが復号化されるまで反復されてもよい。
【０１４７】
暗号化されたデータを復号化するときに、暗号化方法のいずれのステップも、元のデータを暗号化する以前のシーケンスの間と同じ方法で適用されることが可能である。
【０１４８】
本発明の第１、第２、第３及び第４の態様に関連して上述されたいずれのステップも、本発明の第４の態様による復号化する方法にさらに適用されてもよい。さらに、本発明の第５の態様によるステップは、後述される本発明の別の態様に含まれてもよい。
【０１４９】
第６の態様において、本発明は、データのセットを暗号化しかつ復号化するコンピュータプログラムに関し、上記コンピュータプログラムは暗号化モード及び復号化モードで実行するように適応化され、上記コンピュータプログラムはさらに、
ｉ）下記のステップ、すなわち、
−  数学的システムを複数の離散的な項で表現するステップと、
−  数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された少なくとも１つの変数を含む計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップであって、結果として得られる数は、
ａ．数学的システムに対する解の一部と、
ｂ．数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現するステップと、
−  計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出するステップと
を実行することにより、擬似乱数を再現可能な方法で発生し、
ｉｉ）データ及び擬似乱数を、
−  算術演算と、
−  論理演算と
の少なくとも一方によって操作し、結合されたデータのセットを取得するように適応化され、
−  上記コンピュータプログラムが暗号化モードで実行されている場合、上記結合されたデータのセットは上記データの暗号化されたバージョンを表現し、
上記コンピュータプログラムが復号化モードで実行されている場合、上記結合されたデータのセットは上記データの復号化されたバージョンを表現している。
【０１５０】
操作するステップは、上述の任意の論理関数及び／又は算術関数を含んでもよい。データを操作するためにＸＯＲ演算子が使用される場合、暗号化モードと復号化モードとは同一のステップを含むことが可能である。
【０１５１】
擬似乱数を発生するステップは、本発明の第３の態様による方法に関連して上述された任意のステップをさらに含んでもよい。
【０１５２】
本発明の第６の態様によるコンピュータプログラムは、本発明の第１、第２、第３、第４及び第５の態様に関連して上述された任意のステップとともに、本発明の別の態様に関連して後述される任意のステップを実行するように適応化されてもよい。
【０１５３】
本発明はさらに、本発明の第６の態様によるコンピュータプログラムがロードされる、コンピュータが読み取り可能なデータキャリアに関し、かつこのようなコンピュータが読み取り可能なデータキャリアを備えたコンピュータ、又はこのようなコンピュータが読み取り可能なデータキャリアに接続されたコンピュータに関し、上記コンピュータは、当該プログラムを実行するプロセッサ手段を備えている。
【０１５４】
第７の態様において、本発明は擬似乱数を発生する方法に関し、当該方法は、１つのインスタンスにおいて、
Ｉ）数学的システムを複数の離散的な項で表現することと、
ＩＩ）数学的システムの少なくとも初期条件を表現するシード値を定義することと、
ＩＩＩ）数学的システムの少なくとも１つの変数を固定小数点の数として表現することと、
ＩＶ）固定小数点の数として表現された少なくとも１つの変数を含む計算を実行して、結果として得られる数を取得することを含み、結果として得られる数は、
ａ．数学的システムに対する解の一部と、
ｂ．数学的システムの数値解に関連した別の計算に使用可能な数と
の少なくとも一方を表現し、
Ｖ）計算の間に発生した少なくとも１つの数から導出された数を擬似乱数として抽出することと、
ステップＩ）乃至Ｖ）を複数のインスタンスで並列に実行することを含む。
【０１５５】
２つ以上のインスタンスにおける計算は、同時に実行されるか、連続して実行されるかのいずれかであることが可能である。従って、２つ以上のインスタンスにおける計算は、複数の計算を同時に処理する命令を実行することにより、もしくは一時に単一の計算のみを処理する命令を実行することにより、行うことができる。
【０１５６】
従って、並列な複数のインスタンスにおける擬似乱数の発生は、いくつかの場合には、特に当該方法が実行されるハードウェアが並列処理をサポートしているときには、ステップが１つのインスタンスのみで実行されるときより高速である。さらに、２つ以上のインスタンスを結合することにより、１つしか使用されなかった場合よりも、暗号化においてはより長い鍵を適用することができる。例えば、暗号化鍵の１つの部分を第１のインスタンスに使用し、暗号化鍵の他の部分を第２のインスタンスに使用することができる。
【０１５７】
任意の高次元の数学的システムは、より低い次元の複数のシステムを結合することによって構成されうる。例えば、Ｎ個のロジスティックマップを結合すれば、Ｎ次元システムを生み出すことができる。結合するメカニズムは、Ｎ個の異なる変数に対応するＮ個の異なるマップにおける線形関数又は非線形関数のいずれかを含むことによって構成されることが可能である。１つの変数を決定するマップ内の結合関数は、他のすべての変数に依存する場合も依存しない場合もある。代替として、結合は、Ｎ個の変数のうちの１つを残りのＮ−１個のマップのうちの１つ又は複数に代入することによって実行されうる。
【０１５８】
２つ以上のロジスティックマップは、線形な結合項を介して結合されてもよい。以下に示された例では、結合項の前のパラメータε１及びε２は、結合の強度、すなわち２つのロジスティックマップの各々が他方に対して有する影響の程度を制御する。
【０１５９】
【数４１】
2004530919.tif 000043
【０１６０】
数又はデータは、少なくともインスタンスの各々についてステップＩＶ）を実行する間は、複数のインスタンスの間で送信されてもよい。ステップＶ）についても、同じことが当てはまる。
【０１６１】
当該方法は、インスタンスの各々におけるステップＶ）で抽出された複数の擬似乱数を、算術演算及び／又は論理演算を使用して共通の擬似乱数に結合することを含んでもよい。
【０１６２】
パラメータ値及び／又は変数値、もしくはこれらの一部は、２つのインスタンスの間で交換されてもよい。従って、例えば一方のインスタンスのｘｎ＋１ともう一方のインスタンスのｘｎ＋１とが各反復ステップの後で交換されてもよく、もしくは一方のインスタンスのｘｎ＋１がもう一方のインスタンスのｙｎ＋１と交換されてもよい。同様に、ステップ長Δｔｎも２つのインスタンス間で交換されうる。変数値又はパラメータ値の交換はまた、第１のインスタンスの値に対して、その値が第２のインスタンスの値の変更に使用される前に、論理演算及び／又は算術演算を実行することにより達成されうる。
【０１６３】
本発明の第７の態様による方法は、本発明の他の態様に関連して上述された、もしくは後述される任意のステップを含んでもよい。
【０１６４】
第８の態様において、本発明は、少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法に関し、当該方法は、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップとを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現し、
上記計算を実行するステップは、
−  少なくとも１つの以前の解Ｘｍ，ｍ≦ｎ＋１に基づいて解Ｘｎ＋１を反復して計算することを含み、これにより上記計算を実行するステップは、状態変数Ｘの少なくとも１つの初期条件Ｘ０に基づいて開始され、
当該方法はさらに、
−  暗号鍵を上記計算への入力として提供することを含み、これにより上記暗号鍵は初期条件Ｘ０の発生に使用される。
【０１６５】
ここのコンテキストにおいて、“以前の解”という用語は現在の解Ｘｎ＋１も含むということは理解される必要がある。
【０１６６】
ここで本発明の他の態様に関連して記述された任意のかつすべてのコメント及び議論は、本発明の第８の態様による方法にも当てはまる。
【０１６７】
第９の態様において、本発明は、データのセットを識別するための識別値を決定する方法に関し、当該方法は少なくとも１つの関数を含む数学的システムにおいて数値計算を実行することを含み、当該方法は、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップとを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現し、
これにより、データのセットの少なくとも一部の表現は上記計算において使用され、
当該方法はさらに、
−  上記結果として得られる数の少なくとも一部を上記識別値として抽出することを含む。
【０１６８】
従って、本発明の第９の態様による方法は、先に詳述されたハッシュ関数又はハッシュアルゴリズムと見なされてもよい。識別値は、数値計算における異なる計算ステージで抽出された多数の被抽出数によって構成されることが可能である。抽出は、各計算ステップにおいて、又は各反復ステップにおいて発生してもよく、あるいは、それは、選択された計算ステージでのみ発生してもよい。
【０１６９】
“識別値”という用語は、データのセットを識別するハッシュ値又は暗号チェックサムであることが可能である。ブルース・シュナイアーによる応用暗号学，第２版，ジョン・ワイリー・アンド・サンズ，１９９６年が参照される。暗号鍵が計算のシード値として使用される場合、ハッシュ関数はＭＡＣ関数（メッセージ認証コード）と呼ばれる。
【０１７０】
数学的システムは、偏微分方程式又は常微分方程式等の微分方程式、もしくは領域を保存するマップ又は領域を保存しないマップ等の離散的マッピングを含んでもよい。数学的システムは、少なくとも１つの状態変数Ｘを決定する少なくとも１つの非線形マッピング関数を含んでもよい。
【０１７１】
非線形マッピング関数は、例えば、ｘｎ＋１＝λｘｎ（１−ｘｎ）の形式を有するロジスティックマップを含んでもよい。ここで、λはパラメータであり、ｘｎ＋１は計算の（ｎ＋１）番目のステージにおける状態変数ｘの値であり、ｘｎは計算のｎ番目のステージにおける状態変数ｘの値である。
【０１７２】
ロジスティックマップは、ｘｎ＋１＝λｘｎ（１−ｘｎ）＋ε（ｘｎ−ｍｎ）の形式に変形されもよい。ここで、λ及びεはパラメータであり、ｘｎ＋１は計算の（ｎ＋１）番目のステージにおける状態変数ｘの値であり、ｘｎは計算のｎ番目のステージにおける状態変数ｘの値であり、ｍｎはデータのセットのｎ番目の部分の表現を含む。
【０１７３】
暗号鍵は、λ、ε及び状態変数ｘの初期値ｘ０のうちの少なくとも１つを少なくとも部分的に決定するために使用されてもよい。
【０１７４】
数学的システムは、
−  次式の形式を有するアノーソフマップ、
【数４２】
2004530919.tif 000044
又は、
−  次式の形式を有するエノンマップ
【数４３】
2004530919.tif 000045
等の、複数の非線形マッピング関数にてなるセットを含んでもよい。
【０１７５】
数学的システムは、少なくとも１つの非線形微分方程式、及び／又は複数の非線形微分方程式にてなるセットを含んでもよい。
【０１７６】
好適には、数学的システムは少なくとも１つの正のリヤプノフ指数を有し、これにより、ある程度の不規則さ、又はカオス的挙動が達成され、これにより、システムのランダムな特性とセキュリティとが強化される。
【０１７７】
数学的システムがカオス的挙動を呈しているか否かを決定するために、数学的計算の間に、少なくとも１つのリヤプノフ指数が少なくとも１回計算されてもよい。これがカオス的挙動を呈していなければ、すなわち計算されたリヤプノフ指数が正でなければ、計算は中断され、他の初期値及び／又は他のパラメータから再開されることが可能である。
【０１７８】
少なくとも１つの非線形微分方程式は、好適には、少なくとも１つの独立変数ｔの関数である少なくとも１つの状態変数Ｘを決定する。複数の非線形微分方程式にてなるセットは、例えばローレンツシステムを含んでもよい。
【０１７９】
ここで本発明の他の態様に関連して記述された任意のかつすべてのコメント及び議論は、本発明の第９の態様による方法にも当てはまる。
【０１８０】
第１０の態様において、本発明は、少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法に関し、当該方法は、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記関数の少なくとも１つの選択された変数の範囲を制限するステップとを含み、上記範囲は、上記範囲によって制限されない場合に上記選択された変数が上記関数によって有したであろう値を除外するように十分に狭く、
−  計算を実行して、結果として得られる数を取得するステップを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現し、
−  計算の結果として得られる選択された変数の値が上記範囲を超えているとき、上記選択された変数に上記範囲内の値を割り当てるステップを含む。
【０１８１】
例えば、上記範囲を超えている値の上位ビットが切り捨てられると、上記範囲内の値を割り当てるステップはモジュラス関数と考えることができる。従って、本発明の第１０の態様による方法のこれらのステップは、暗号化／復号化システムのランダムな特性を強化するため、及び／又は暗号化されたデータから数学的システムの内部状態に関する情報を導出することをより困難にするために、意図的なオーバーフローをもたらすことができる。
【０１８２】
ここで本発明の他の態様に関連して記述された任意のかつすべてのコメント及び議論は、本発明の第９の態様による方法にも当てはまる。特に、暗号化及び復号化に関連して記述された任意のかつすべてのコメントが当てはまり、また、本発明の第１０の態様による方法も同様に、本発明の任意のかつすべての態様に、特に暗号化及び復号化に関する態様に当てはまる。
【０１８３】
従って本発明の第１０の態様による方法は、例えば暗号化及び復号化の少なくとも一方に使用される擬似乱数を発生する、擬似乱数発生方法の一部であってもよい。数学的システムは、好適には、少なくとも１つの正のリヤプノフ指数を有する。
【０１８４】
第１１の態様において、本発明は、少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法を提供し、当該方法は、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を整数として表現するステップと、
−  上記整数内に仮想小数点分離記号を配置するステップとを含み、これにより上記整数は実数を表現し、
−  整数として表現された少なくとも１つの変数を含む計算を実行して、結果として得られる数を取得するステップを含み、上記結果として得られる数は整数として表され、
−  下記ステップ、すなわち、
−  上記整数における上記仮想小数点分離記号の位置を訂正するステップと、
−  上記結果として得られる数に仮想分離記号を配置するステップと
の少なくとも一方を実行することにより、結果として得られる数における上記仮想小数点分離記号を、予め決められた位置に位置決めするステップを含む。
【０１８５】
結果として得られる数は、通常は、固定された位置の小数点分離記号を有する固定小数点の数である。代替として、結果として得られる数における小数点分離記号の位置は、計算が完了した後に訂正されてもよい。第３の可能性は、小数点分離記号の位置を計算を実行する前と後で訂正することである。結果として得られる数における小数点分離記号から左の位置のすべてが使用されていない場合であって、かつ、計算においては、結果として得られる数の分解能より相対的に高い分解能を保持することが望ましい場合には、このことが適切なときがある。例えば、結果として得られる数は、Ｓ（１０．２１）のフォーマットを有することが望ましい。従って、例えば２つのＳ（７．２４）フォーマットの数の加算は、Ｓ（８．２３）のフォーマットで実行されてもよく、次いで、これは、Ｓ（１０．２１）のフォーマットの、結果として得られる数に変換される。これにより、引数における最下位ビットから２番目及び３番目のビットの桁上げが結果を左右する可能性がある。
【０１８６】
最後に、計算によっては、任意の小数点分離記号の位置を訂正することが不要である、又は必要のない場合がある。
【０１８７】
小数点分離記号の位置の訂正は、通常はシフト演算によって実行される。
【０１８８】
ここで本発明の他の態様に関連して記述された任意のかつすべてのコメント及び議論は、本発明の第９の態様による方法にも当てはまる。
【０１８９】
第１２の最も広範な態様において、本発明は、少なくとも１つの関数を含む数学的システムにおいて数値計算を実行する方法を提供し、当該方法は、
−  上記数学的システムを複数の離散的な項で表現するステップと、
−  上記数学的システムの少なくとも１つの変数を固定小数点の数として表現するステップと、
−  固定小数点の数として表現された上記少なくとも１つの変数を当該計算が含むように、上記計算を実行するステップと、
−  上記計算から、結果として得られる数を取得するステップとを含み、上記結果として得られる数は、
ａ．上記数学的システムに対する解の少なくとも一部と、
ｂ．上記数学的システムの数値解に関連した別の計算において使用可能な数と
の少なくとも一方を表現する。
【０１９０】
ここで本発明の他の態様に関連して記述された任意のかつすべてのコメント及び議論は、本発明の第９の態様による方法にも当てはまる。
【０１９１】
第１３の態様において、本発明は、少なくとも１つの関数を含む非線形な数学的システムにおいて数値計算を実行する回路を提供し、
上記回路は、数学的システムが、上記回路又はコンピュータプログラムコードにおいて、上記数値計算のうちの少なくとも選択された１つが整数演算を含むように変形された項で表現されるように設計又はプログラムされ、これにより、数学的システムの変形されていない表現における上記選択された数値計算は、１つ又は複数の浮動小数点演算か、又は１つ又は複数の固定小数点の数における小数点分離記号の位置決めを制御することかを必要とし、
上記回路は、上記選択された計算は１つ又は複数の整数に対する少なくとも１つの置換計算によって置き換えられるように設計又はプログラムされ、これにより数学的システムは、上記回路又はコンピュータプログラムコードにおいて、上記少なくとも１つの置換計算が仮想小数点分離記号の位置決めを必要としないように表される。
【０１９２】
数学的システムは、カオス的挙動を呈することが可能である。
【０１９３】
従って、例えば下記計算、
【数４４】
2004530919.tif 000046
及び、
【数４５】
2004530919.tif 000047
は、まずｘｎ＋１を計算することによって実行可能である。次に、ｙｎ＋１の式は次式によって計算可能である。
【０１９４】
【数４６】
2004530919.tif 000048
【０１９５】
これにより、ｙｎに２を乗算する計算ステップを省略することができる。
【０１９６】
従って、置換計算の実行により、計算時間を節約することができる。
【０１９７】
同様に、本発明はまた、電子回路において、少なくとも１つの関数を含む非線形な数学的システムにおいて数値計算を実行する方法を提供し、当該方法は、上記回路において、又は上記回路の動作のよりどころとなるコンピュータプログラムセグメントにおいて、
−  上記数学的システムを、上記数値計算の少なくとも選択された１つが整数演算を含むように変形された項で表現するステップを含み、これにより、数学的システムの変形されていない表現における上記選択された数値計算は、１つ又は複数の浮動小数点演算か、あるいは１つ又は複数の固定小数点の数における小数点分離記号の位置決めの制御を必要とし、
−  上記選択された計算を、１つ又は複数の整数に対する少なくとも１つの置換計算によって置き換えるステップを含み、これにより数学的システムは、上記回路又はコンピュータプログラムコードにおいて、上記少なくとも１つの置換計算が仮想小数点分離記号の位置決めを必要としないように表され、かつ、
上記置換計算を実行するステップを含む。
【発明を実施するための最良の形態】
【０１９８】
図１は、ディジタルデータを暗号化し、送信し、復号化するシーケンスの概要図である。図２は、ブロック暗号システムにおける暗号化シーケンスを示す図であり、図３は、ストリーム暗号システムにおける暗号化シーケンスを示す図である。ブロック暗号システム及びストリーム暗号システムについては、先の本発明の背景技術についての議論において述べられている。
【０１９９】
次に、本発明の様々な態様による好適な実施形態として、データを暗号化／復号化するための方法とアルゴリズムについて説明する。本アルゴリズムは、データの暗号化／復号化における大部分の目的に適用可能である。しかしながら、本アルゴリズムは、本質的に、大きなファイル、ライブ又は予め記録された音声／ビデオ、著作権で保護された素材（コンピュータゲーム又は他のソフトウェア等）、及び記憶するためのデータ（バックアップ及び／又は移動（transportation）等）といった、データストリーム又は他の連続的なデータの暗号化において有利である。さらに、本アルゴリズムは、その速さにより、これらの目的に特に適合するものとなっている。本アルゴリズムは、その計算方法に起因して、非常に小さなプロセッサ上でも使用可能である。
【０２００】
本アルゴリズムは、擬似ランダムシーケンス・ストリーム暗号システム（ＰＲＳＳＣ）に依存する。ＰＳＳＲＣシステムは擬似乱数発生器（図４の外側のボックスの内容物）によって特徴付けられ、当該発生器は、２進数の鍵に基づいて、擬似ランダムなデータのシーケンスを発生する。図４で参照されるように、いわゆる鍵ストリームであるこのシーケンスは、暗号化及び復号化に使用される。鍵ストリームは、可能な各鍵に固有のものである。
【０２０１】
平文に対して論理ＸＯＲ関数（図面の中では
【数４７】
2004530919.tif 000049
の記号で表されている）を適用すると、同量の鍵ストリームが平文を暗号化する。ＸＯＲ関数の出力が暗号文である。この暗号文にもう一度同じアプローチを適用すると、暗号文が復号化されて平文になる。復号化に使用された鍵が暗号化に使用された鍵と完全に同一であれば、復号化は、暗号化された平文のみを復号化する。
【０２０２】
暗号化されたデータの完全性は、暗号文を復号化する能力のある鍵に存在している。従って、鍵の推測は困難でなければならない。これを保証するため、本アルゴリズムの基本設計は、少なくとも１２８ビットの鍵を使用している。１２８ビットの鍵サイズは、約３．４・１０３８個の異なる鍵を生み出す。
【０２０３】
本アルゴリズムは、次の３つの常微分方程式で構成されるローレンツシステムのような、カオス的挙動を呈するシステムを使用する。
【０２０４】
【数４８】
2004530919.tif 000050
【数４９】
2004530919.tif 000051
【数５０】
2004530919.tif 000052
【０２０５】
ここで、σ，ｒ，ｂはパラメータであり、ｘ，ｙ，ｚは状態変数である。
【０２０６】
図５は、ローレンツシステムの数値解のプロットを示す。
【０２０７】
システムでカオスが発生するためには、次式のパラメータ基準が満たされる必要がある。
【０２０８】
【数５１】
2004530919.tif 000053
【０２０９】
これが満たされたとしても、すべての解がカオス的となるわけではない。パラメータ空間には、いわゆる周期窓が存在することがあり、これは、周期解を発生させる、複数のパラメータの組み合わせを示す。システムを実装する前に、リヤプノフ指数の計算を使用してパラメータ空間の解析が行われる。一般に、正のリヤプノフ指数は、数学的システムに対する解がカオス的であることを示す。エドワード・オット（Edward Ott），力学系におけるカオス（Chaos in Dynamical Systems），ケンブリッジ大学出版局（Cambridge University Press），１９９３年を参照されたい。
【０２１０】
複数のパラメータは、典型的には、暗号化鍵のような又は暗号化鍵の一部のようなシード値から決定される。好適には、本発明による方法を具体化するアルゴリズムは、予め定義された区間内にあるパラメータ値のみが可能にされるように設計され、これにより、システムが正のリヤプノフ指数を有することの確率が高くなることを保証する。従って、数学的システムは、カオス的挙動を呈することについて高い確率を有する。それに加えて、又はそれに代わって、リヤプノフ指数は、数学的システムに対する解のカオス的でない挙動を検出できるように、数学的計算の開始ときに、もしくは数学的計算の間に決定されてもよい。
【０２１１】
数学的システムはまた、他の連続的なシステム（レスラーシステム等）又は離散的マップ（エノンマップ等）である可能性もある。
【０２１２】
積分は、数値積分ルーチンを使用して実行される。初期条件及び積分ステップ長が提供されると、数値積分ルーチンは、例えばオイラー法又はルンゲ・クッタ法を使用して、離散的なメッシュ点における解を計算する。オイラー法を使用してローレンツ方程式を離散的な項で表現すると、次の方程式から解を計算することができる。
【０２１３】
【数５２】
2004530919.tif 000054
【数５３】
2004530919.tif 000055
【数５４】
2004530919.tif 000056
【０２１４】
計算は、後に説明する固定小数点の数を使用して実行可能である。
【０２１５】
複数の微分方程式にてなるシステムの数値積分の間、従属変数ではない連続変数（時間ｔ又は空間ｓ等）は離散化される。この処理は、連続的な区間［ａ；ｂ］を離散的な点のセットで置換することを示す。こうしたシステムでは、ΔＴ＝（Δｔｘ，Δｔｙ，Δｔｚ）は通常、積分のステップ長、又は積分ステップと呼ばれる。
【０２１６】
図７は、複数のカオス的システムのような、同一のシステム又は異なるシステムの２つ以上のインスタンスを同時に計算する可能な方法を示す。本方法は、より高速の計算速度及び改善されたセキュリティをもたらし、より大きな鍵が使用可能である。好適には、２つのシステム間に、例えばΔｔｘ，Δｔｙ及び／又はΔｔｚの交換等のステップ長の交換のような何らかの通信又は結合が存在すべきである。
【０２１７】
内部変数は、基本設計では各々３２ビット幅であるが、任意の可変幅も使用可能である。ローレンツシステムを使用する場合は、６つの内部変数（３つの状態変数及び３つのパラメータ）が存在する。従って、内部変数セットによって与えられた発生器の内部状態を表現するために、（基本設計では）１９２ビットが使用される。１２８ビット鍵を１９２ビットまでパディングすることは、不正な値を回避するように、すなわち、すべての変数が、許容された値を含むように、かつ鍵からのビットが無視されることを防止するように実行される必要がある。パディングは、予め決められた０及び１の値を挿入することか、又は鍵からのビットを反復することを含むことが可能である。図６は、パディングによる鍵の拡張を示す図である。
【０２１８】
積分は、例えば任意の１つの状態変数から計算可能な、可変な時間ステップを使用して実行されることが可能である。基本設計では、ステップ長Δｔは、各積分ステップで変化する。この変動は、状態変数Ｘに結合される。
【０２１９】
鍵ストリームは、複数の状態変数に関連するデータのうちのいくつかのものから抽出される。これは、ｙ変数から最下位の８ビットを抽出することによって、又は、例えば１つのステップの計算において実行された１つ又は複数の乗算から、計算で消去されたデータのうちのいくつかのものを収集することによって実行可能である。
【０２２０】
一般に、カオス的システムの計算は、コンピュータ上で浮動小数点の変数を使用して実行される。しかしながら、この方法は複数の問題を発生させる。１つの問題点は、浮動小数点の変数を使用すると、浮動小数点を異なるコンピュータシステムへ実装するときの僅かな差に起因して、同一の鍵が使用された場合でも異なるコンピュータで異なる鍵ストリームを発生させうることにある。
【０２２１】
従って、固定小数点の変数が使用される。固定小数点の変数は整数のデータ型に基づき、これは様々なコンピュータシステム上で等しく実装される。実数のような数を表すためには、小数点より後のディジットが必要とされ、小数点は、数の終わり以外のどこかに人為的に配置される（例えば１２３４５ではなく１２．３４５）。
【０２２２】
本アルゴリズムの適正な演算を保証するため、好適にはいくつかのテストが実行される必要がある。これらのテストはのうちのあるものは実行ときに行われ、他のものは設計ときに行われる。
【０２２３】
初期化処理の一部として、状態変数の完全なデータコンテンツ（例えば１９２ビット）に等しいか、もしくは所定量の完全な鍵（例えば１２８ビット）に等しい量の鍵ストリームが本アルゴリズムを使用して発生され、周期解又は定常点の検出のために鍵が再ロードされる必要がある場合には、上記鍵ストリームは保存される。この場合、保存されたシーケンスは新しい鍵としてロードされ、余分な鍵（extra key）の抽出を含む初期化が再度実行される。
【０２２４】
コンピュータ上での数の有限な表現に起因して、どの数値解も周期的となる。しかしながら、いくつかの鍵は、やや短い周期を有する鍵ストリームを結果的にもたらすことがある。これは、システムのセキュリティを損なう可能性があるために望ましくない。従って、本発明は、このような周期解を検出するためのアルゴリズムを含んでいる。このアルゴリズムは、変数の符号又は変数の勾配を監視する。ローレンツシステムを使用する場合は、ｘに対してチェックが実行される。符号がマイナスからプラスへ変化する（又はプラスからマイナスへ、もしくは単に変化する）と、位置チェックが実行される（位置チェックは、全反復の後でも実行可能である）。位置チェックは、状態変数の完全なセットを、以前からのバッファリングされたセットと比較する。完全な一致が発見されれば、周期解が検出される。
【０２２５】
力学システムの定常点は、反復の間も変化しないままである、複数の状態変数のセットである。このような定常点は、複数の状態変数の現在のセットを最終のセットと比較することによって、又はすべての変数の勾配がゼロであるか否かをチェックすることによって、もしくは１つの変数の現在の勾配とその以前の勾配とが両方ともゼロであるか否かをチェックすることによって検出可能である。
【０２２６】
カオス的システムは何らかの理由で周期解に入る。システムのセキュリティを損なわないためには、周期解を検出して訂正しなければならない。システムの解が周期的になれば、数学的システムの解から抽出される数もまた周期的になり、よって擬似ランダムではなくなるので、好ましくは、暗号化は停止されるものとする。周期解のテストは、解の座標を以前に計算された座標と比較することを含む。完全な一致が発見されれば、システムは周期解に入っている。
【０２２７】
以前に計算された座標を記憶するのに必要なメモリの量を減らすため、かつ座標のテストに必要な処理時間を短縮するため、座標キャッシュには選択された座標のみが記憶される。周期解をテストするために必要なプロセッサ時間を短縮するため、テストは、座標が所定の基準を満たす場合にのみ実行される。図８は、周期解のチェックを実行する原理を示している。
【０２２８】
図９は周期解を有する数学的システムを示し、特に、周期解を有する２次元非線形システムを示している。本システムは決定論的である。これは、解がその初期条件によって完全に特定されることを意味する。理論上、この解は連続となり、よって無限に多い点で構成される。システムを数値的に解く場合は、時間区間が離散化され、これらの点で解が計算される。数学的システムに対する数値解は、単なる座標セットのシーケンスである。２次元システムについて考察すると、解は、図９の曲線上の点で示された、多数の点（ｘ，ｙ）において特定される。システムの決定論的性質は、解が前にも来たことのある１つの点をヒットすることがあれば、その解は周期的であり、今後も周期的であり続けることを含意している。本テストでは、この性質が使用されている。
【０２２９】
数値積分の間に周期解をテストするためには、計算された現在の座標セットを以前の値と比較する必要がある。これを実行するため、座標セットは、それらが計算されたときに記憶される。この記憶は待ち行列（キュー）のように機能し、座標キャッシュと呼ばれる。計算された座標セットは、座標キャッシュ内のすべての座標セットと比較される。完全な一致（２つの座標セット中のすべての値が等しい）が発見されると、システムは周期的状態にある。完全な一致が存在せず、テストに合格すれば、周期的挙動は検出されず、計算を続けることができる。テストされた座標は、計算の継続の前に、後の計算用にキャッシュに追加される。
【０２３０】
計算されたシステムの座標セットのすべてをキャッシュに保存するためには、あまりに多くのメモリ及びプロセッサ時間が必要になる。従って、図１０に示されたように、選択された座標のみが記憶される。
【０２３１】
キャッシュは多くのレベルよりなり、その各々がレベル毎に増大する経過時間の座標を含んでいる。各テストの後、又は多くのテストの後、テストされた座標はレベル０に書き込まれる。座標がレベル０に２度目（又は他の任意のとき）に書き込まれる毎に、古い値は、それが上書きされる前にレベル１へ書き込まれる。他のレベルにおいて座標を書き込む方法も同様であり、値が任意のレベルに２度目に書き込まれる毎に、古い値は、それが現在のレベルで上書きされる前に次のレベルへ移動される。
【０２３２】
本方法により、座標キャッシュは指数関数的に増える経過時間を有する座標を含むことになる。レベル０は、１又は２の経過時間（以前にチェックされた座標か、又は以前にチェックされた座標より１つ前の座標）を有する座標を記憶し、レベル１は３−６の経過時間（座標が書き込まれた後のテストにおいて３であり、次いで次の座標が書き込まれるまで順次６まで増加する）を有する座標を記憶し、レベル２は７−１４の経過時間を有する座標を記憶する、等々となる。
【０２３３】
実施例Ｉにおける擬似プログラムコードは、キャッシュが実装されうる方法を示す。
【０２３４】
レベルの経過時間は変化しているので、周期解を即座に発見することはできない。１１回のテストの周期長さを有する周期解は、レベル２におけるデータの経過時間が７と１４との間にあることから、キャッシュのレベル２において検出されることになる。しかしながら、テストは、座標が正確に１１回のテストの分だけ経過するまでは、周期解を発見しないであろう。従って、周期的な挙動が検出される前にテストが１２回まで実行される可能性がある。この場合、このことは、それが検出されるまでにシステムは１２／１１周期まで経過していく可能性があるということを意味する。
【０２３５】
上述のアルゴリズムへの拡張として可能性のあるものが、変化するＴｒａｎｓｐｏｒｔＡｇｅである。例Ｉの擬似コードのプログラムを参照されたい。いくつかの座標が、他の座標よりも周期解の一部をなす可能性が高いと識別されうるならば、例Ｉの擬似コードのプログラムで参照されるＩｎｅｓｒｔＣｏｏｒｄｉｎａｔｅ手順がこれらを認識し、それらに対する低減されたＴｒａｎｓｐｏｒｔＡｇｅの値を使用することが可能である。これは、キャッシュ中の臨界座標（critical coordinate）にとって有利に働き、多くの臨界座標が記憶されている場合はキャッシュ内のデータをより新しいものにする。キャッシュ内の、経過時間がより短いデータは、周期解の検出を、当該周期解に含まれるより少ない反復の後に可能にする。
【０２３６】
テストは、各反復の後に実行可能である。これは、解の新しい座標セットを計算した毎であることを意味する。しかしながら、プロセッサ資源を節約するためには、それに代わって、テストは周期的間隔で実行される必要がある。テストを有効なものにするためには、テストは、解が認識可能な位置にある時点で実行される必要がある。テストが毎回その同じ位置で実行されることを確実にするための１つの方法は、解のグラフィックなプロットにおける認識可能な点を発見することにある。これを行うためには、システムは、その特徴的な挙動について解析される必要があり、かつ基準が選択される必要がある。先に示した非線形システムの場合、図１１乃至図１３に示された基準の例が使用可能である。
【０２３７】
第１の可能な基準は、図１１に示されたように、ｘの符号がマイナスからプラスへ変化することにある。すなわち、ｘの符号がマイナスからプラスへ変化するとき、テストが実行される。第２の基準は、図１２に示されたように、ｄｘの符号がプラスからマイナスへ変化することにある。第３の基準は、図１３に示されたように、ｄｙがプラスからマイナスへ変化することにある。
【０２３８】
基準を選択するときには、２つのことが考慮される必要がある。まず第１に、周期解として可能性のあるすべてのものが基準を満たしうることを必要とする。第２は、プロセッサの負荷を減らすために、テスト回数が最も少ない基準を選択する必要がある。
【０２３９】
設計の時点では、システム及び選択されたパラメータ空間に関するいくつか特別なテストを行って、システムの効率、安定性及び正確さを確認することができる。これらのテストには、グラム・シュミットの直交化法を使用するリヤプノフ指数の計算を含むとともに、鍵ストリームの統計的解析を含むことができる。
【０２４０】
実施例Ｉ．
以下の擬似コードのプログラムは、１度に１バイトを暗号化する、本発明によるデータの暗号化及び復号化のためのプログラムの一例を示している。本プログラムは、図１５乃至図２２のフローチャートに従って動作する。本プログラムは、３２ビットのレジスタを用いて動作する。図１５は、データを含むファイルを暗号化する方法を示す。図１６乃至図２２は、周期解のチェックとローレンツシステムを使用するストリーム暗号とに関連する、下記の擬似コードで示された関数に対応する。
【０２４１】
固定小数点ライブラリの擬似コード．
ＦｌｏａｔＴｏＦｉｘｅｄＰｏｉｎｔ：浮動小数点の数Ｘを固定小数点の数に変換する。この関数の結果は、Ｓ（ａ．ｂ）又はＵ（ａ．ｂ）のフォーマットを有する。
【０２４２】
［擬似コード１］
2004530919.tif 000057
【０２４３】
ＦｉｘｅｄＰｏｉｎｔＴｏＦｌｏａｔ：フォーマットＳ（ａ．ｂ）又はＵ（ａ．ｂ）を有する固定小数点の数Ｘを浮動小数点の数に変換する。
【０２４４】
［擬似コード２］
2004530919.tif 000058
【０２４５】
ＣｏｎｖｅｒｔＦｉｘｅｄＰｏｉｎｔ：入力されたフォーマットＳ（ａ．ｂ）又はＵ（ａ．ｂ）を有する固定小数点の数Ｘを、要求されたフォーマットＳ（ｃ．ｄ）又はＵ（ｃ．ｄ）に変換する。引数Ｘが符号付きであれば結果は符号付きであり、かつその反対も成り立つ。
【０２４６】
［擬似コード３］
2004530919.tif 000059
【０２４７】
同じフォーマットの複数の固定小数点の数に関する加算及び減算は、通常の整数の加算及び減算関数を使用して実行される。
【０２４８】
ＭｕｌＦｉｘｅｄＰｏｉｎｔ：２つの固定小数点の数Ｘ及びＹを乗算する。ＸはフォーマットＳ（ａ．ｂ）又はＵ（ａ．ｂ）を有し、ＹはフォーマットＳ（ｃ．ｄ）又はＵ（ｃ．ｄ）を有する。結果として得られる固定小数点の数は、フォーマットＳ（ｅ．ｆ）又はＵ（ｅ．ｆ）を有する。結果は、Ｘ及びＹと同様に、必ず符号付きの値又は符号なしの値のいずれかであり、３２ビットレジスタに記憶される。“＞＞”は、符号付き乗算の場合は右への算術シフトであり、符号なし乗算の場合は右への論理シフトである。
【０２４９】
［擬似コード４］
2004530919.tif 000060
【０２５０】
周期解のチェックのための擬似コード．
周期解をチェックするためのサブシステムにおけるグローバルな定数。変曲点の個数がＴｒａｎｓｐｏｒｔＡｇｅＣａｃｈｅＤｅｐｔｈ−１より少ないとき、当該コードは周期を検出することができる（変曲点は反復回数の高々２分の１の個数だけ存在しうるということに注意する）。
【０２５１】
［擬似コード５］
2004530919.tif 000061
【０２５２】
周期解をチェックするためのサブシステムは、例えば古い座標のキャッシュと、周期解が発見されたときにロードされるスペア鍵とを記憶するための、多くのグローバルな変数を有する。
【０２５３】
［擬似コード６］
2004530919.tif 000062
【０２５４】
ＳｅｔｕｐＣｏｏｒｄｉｎｔｅＣｈｅｃｋ：周期解をチェックするためのサブシステムをセットアップする。（０，０，０）はローレンツシステムの定常点であり、よって、これは鍵の再ロードが必要であることを指示する座標値であることから、座標キャッシュのすべての位置は（ｘ，ｙ，ｚ）＝（０，０，０）にリセットされる。
【０２５５】
［擬似コード７］
2004530919.tif 000063
【０２５６】
ＩｎｓｅｒｔＣｏｏｒｄｉｎａｔｅ：所定のレベルに記憶された以前の値の経過時間が所定のしきい値を超えると、座標を座標キャッシュの所定のレベルに書き込む。当該レベルにおける古い値は、上書きされる前に次のレベルに書き込まれる。
【０２５７】
［擬似コード８］
2004530919.tif 000064
【０２５８】
ＣｈｅｃｋＣｏｏｒｄｉｎａｔｅ：変数ｘの解曲線が、当該曲線の勾配の符号が正から負に変化する変曲点を有するか否かをチェックする。変化がなければ、関数は終了する。そうでなければ関数は、座標キャッシュに等しい座標が記憶されているか否かをチェックする。一致が発見されれば、関数はスペア鍵をアルゴリズムにロードする。最後に、座標が座標キャッシュに書き込まれる。
【０２５９】
［擬似コード９］
2004530919.tif 000065
【０２６０】
ローレンツシステムを使用するストリーム暗号用の擬似コード．
ここのコンテキストにおいては、引数ｑをとるモジュラス関数ＭＯＤは、範囲［０；ｑ［の正の値を返す。
【０２６１】
ローレンツ方程式のσ変数は、“ｓ”と名称変更されている。
【０２６２】
固定小数点の変数のフォーマットは、表１に従って定義される。
【０２６３】
【表１】
2004530919.tif 000066
【０２６４】
Ｃｒｙｐｔ関数に使用される一時的な固定小数点の変数のフォーマットは、表２に従って定義される。
【０２６５】
【表２】
2004530919.tif 000067
【０２６６】
パラメータｒ，ｂ及びｓの許容された値、及び座標ｘ，ｙ及びｚの許容された開始条件は、表３に示されている。
【０２６７】
【表３】
2004530919.tif 000068
【０２６８】
Ｃｒｙｐｔ：暗号化、復号化及びＰＲＮＧ関数。引数は、ＰＤａｔａ（暗号化／復号化する第１のバイトへのポインタ）及びＰＥｎｄ（暗号化／復号化する最後のバイトへのポインタ）である。関数が、擬似乱数を発生させることを目的としていれば、関数には、要求された擬似ランダムデータと同じサイズの、所定量にてなる暗号化すべきデータ（複数のゼロ等）が与えられる必要がある。
【０２６９】
［擬似コード１０］
2004530919.tif 000069
【０２７０】
ＭａｓｋＰａｒａｍｅｔｅｒｓ：拡張鍵又は擬似ランダムシーケンスをロードした後に初期条件及びパラメータが有効であることを保証するために、この関数を使用して条件及びパラメータを変更する必要がある。訂正は、表３で定義された拘束条件に従って実行される。
【０２７１】
［擬似コード１１］
2004530919.tif 000070
【０２７２】
Ｉｎｉｔ１９２：（ＰＳｅｅｄポインタで指定された）１９２ビットのシードをシステムのステートにロードする。
【０２７３】
［擬似コード１２］
2004530919.tif 000071
【０２７４】
Ｉｎｉｔ１２８：（ＰＳｅｅｄポインタで指定された）１２８ビットのシード（又は鍵）を、鍵セットアップ手順を実行するシステムのステートにロードする。
【０２７５】
［擬似コード１３］
2004530919.tif 000072
【０２７６】
システムの出力、すなわち鍵ストリームの統計的特性は、ＮＩＳＴ（米国国立標準技術局）のテストスイートに従ってテストされることが可能である。‘暗号アプリケーション用の乱数及び擬似乱数発生器のための統計的テストスイート（A statistical test suite for random and pseudo-random number generators for cryptographic applications）’，ＮＩＳＴスペシャル・パブリケーション（NIST Special Publication），８００−２２が参照される。また、http://csrc.nist.gov/rng/rng2.html も参照されたい。ＮＩＳＴのテストスイートは、以下で簡単に要約された１６個の異なるテストを含んでいる。これらのテストは、例えば、ローレンツシステムを使用するストリーム暗号用の上述の擬似コードに類似するプログラムに対して実行されることが可能である。
【０２７７】
これらのテストは、ランダム性に関してほとんど重複のない多数の定義を与えている。以下ではより簡単な定義が記述されているが、それに対して、確率論からのより複雑な概念を必要とする定義は、“真のランダムシーケンスに対して、計算されうる／期待されるもの”という言い回しによって示される。上述のＮＩＳＴの出版物は、適正な定義と、確率論における研究への参考文献とを含んでいる。
【０２７８】
頻度モノビット（monobit）テスト：このテストは、鍵ストリームシーケンスの全体に対する０及び１の比率を決定する。真にランダムな鍵ストリームシーケンスである場合、１の個数は０の個数とほぼ同じであることが期待される。テスト中は、問題となる鍵ストリームシーケンスに対してこの特性が成り立っているか否かが調査される。
【０２７９】
頻度ブロックテスト：このテストでは、鍵ストリームシーケンスがＭビットのブロックに分割される。真にランダムな鍵ストリームシーケンスでは、各ブロック内の１の個数は約Ｍ／２個である。このことがまた、テストされた鍵ストリームシーケンスを特徴付けていれば、このテストは成功とされる。
【０２８０】
ラン（Runs）テスト：鍵ストリームシーケンス内のラン（run）は、同一の複数のビットにてなるサブシーケンスとして定義される。このテストは、異なる長さのランをチェックする。このとき、長さｋのランは、そのランにおけるビットとは逆の値のビットを境界とする同一のｋビットによって構成される。異なる長さのランの発生は、真のランダムシーケンスの場合に期待されるものと比較される。
【０２８１】
０の最長ラン：このテストでは、シーケンスは、各々Ｍビットであるブロックに分割され、各ブロック内で最長の１のランが発見される。ブロックに対するランの長さの分布は、ランダムシーケンスでのブロックに対する分布と比較される。期待される１の最長ランの長さの不規則さは、期待される０の最長ランの長さにも不規則さが存在することを示す。
【０２８２】
２値行列の階数テスト：このテストでは、鍵ストリームシーケンスのうちの固定された長さのサブシーケンスが使用され、Ｍ・Ｑビットのセグメントを集めてＭ×Ｑ行列にすることにより多数の行列が形成される。これらの行列の階数を計算することにより、当該テストはサブシーケンス間の線形従属をチェックする。
【０２８３】
離散フーリエ変換テスト：離散フーリエ変換を適用することにより、このテストは鍵ストリームシーケンスの周期特性をチェックする。結果として得られる周波数成分の高さが、真のランダムシーケンスから定義されるしきい値と比較される。
【０２８４】
重なりのないテンプレートの一致テスト：このテストの実行に当たっては、非周期的なｍビットパターンが定義され、特定パターンの出現がカウントされる。
【０２８５】
重なりのあるテンプレートの一致テスト：このテストは重なりのないテンプレートの一致テストによく似たものであり、ｍビットのパターンの構造と、パターンの探索が実行される方法とだけが異なる。この場合、ｍビットのパターンは、ｍ個の１よりなるシーケンスである。
【０２８６】
モーラー（Maurer）のユニバーサル統計テスト：このテストは、鍵ストリームシーケンスにおける、一致する複数のパターンの間の距離を計算する。これを行うことにより、鍵ストリームシーケンスの圧縮性の尺度が得られる。圧縮性が極めて高い鍵ストリームシーケンスは、非ランダムであるとされる。
【０２８７】
レンペル・ジブ圧縮テスト：このテストでは、累積的かつ明確に区別されるパターンの個数が計算され、こうして鍵ストリームシーケンスの圧縮性の尺度がもたらされる。結果は、多数の明確に区別される特徴的なパターンを有するランダムシーケンスと比較される。
【０２８８】
線形複雑度テスト：このテストは、線形フィードバックシフトレジスタの長さを計算し、シーケンスが、ランダムであると見なされるほど十分に複雑であるか否かを決定する。
【０２８９】
系列（serial）テスト：このテストは、シーケンス全体にわたる、重なりのある、すべての可能なｍビットパターンの頻度を計算する。真にランダムな鍵ストリームシーケンスの場合は、２ｍ個の可能なｍビットパターンのすべてが同じ確率で発生する。問題となる鍵ストリームシーケンスに対して、この確率からの偏差が計算される。
【０２９０】
近似エントロピーテスト：このテストの焦点は系列テストと同じであるが、ｍビット及び（ｍ＋１）ビットパターンの頻度を計算するという特徴が追加されている。異なる長さのパターンについて得られた結果が比較され、シーケンスをランダム又は非ランダムのいずれかとして特徴付けるために使用される。
【０２９１】
累積和テスト：このテストでは、＋１及び−１にそれぞれ対応する１及び０を用いたランダムウォークを定義するために、シーケンスが使用される。部分的な鍵ストリームシーケンスの累積和の振幅が、真にランダムな鍵ストリームシーケンスに期待されるものとしては大きすぎるか否か、又は小さすぎるか否かが決定される。
【０２９２】
ランダム偏差（Random excursion）テスト：このテストでは、シーケンスは、累積和テストの場合と同様にランダムウォークに変換される。ランダムウォークが潜在的に通過しうる所定のステート（累積和が保持しうる値）を訪れる回数は、シーケンスをランダム又は非ランダムのいずれかとして特徴付けるために使用される。検討されるステートは、−４，−３，−２，−１，１，２，３，４である。
【０２９３】
変形ランダム偏差テスト：ランダム偏差テストとほぼ同じ。このテストでは、１８個のステートが使用される。
【０２９４】
各テストについて、実際のシーケンスと仮定された真にランダムなシーケンスとの定量的な比較を提供するＰ値、すなわちＰｖａｌが計算される。Ｐ値の定義は、実際のテストに依存する（ＮＩＳＴの文書を参照）。Ｐｖａｌ＞αである値はランダム性を示す。ここで、αは区間０．００１≦α≦０．０１における値であり、αの正確な値は各テスト毎に定義されている。これ以外の値のときは、非ランダム性が宣言される。
【０２９５】
ＮＩＳＴのテストスイートは、各テストに対して、そのＰ値が基準Ｐｖａｌ＞αに合格しなければならないサンプルの比率を定義している。ランダム偏差テストを除く上述のすべてのテストでは、そのそれぞれのＰ値であるＰｖａｌが適正な基準に合格するサンプルの比率は少なくとも０．９７２７６６でなければならない。ランダム偏差テストに関して、ＮＩＳＴによって与えられた比率は、少なくとも０．９６７８１３である。
【０２９６】
本発明の好適な実施形態では、無作為に選択された鍵を使用して取得された少なくとも１０４個のサンプルの平均として、好適には次のような比率、すなわち、少なくとも０．９７５、例えば少なくとも０．９８、例えば少なくとも０．９８５以上、例えば少なくとも０．９９、例えば少なくとも０．９９５、例えば少なくとも０．９９８、が達成される。
【０２９７】
下記の表４では、ＮＩＳＴのテストスイートに対する可能な入力パラメータが、ＮＩＳＴのテストスイートに添付された文書で使用されている表記法で示されている。
【０２９８】
【表４】
2004530919.tif 000073
【０２９９】
実施例ＩＩ．
表５は、本発明の方法による暗号化の速さを示すとともに、様々な既知の暗号化方法による暗号化の速さを示している。本発明による暗号化方法の速さは、本発明による暗号化／復号化プログラムの特徴を組み込んだ試作品において達成された。鍵サイズは２５６ビットキーであり、暗号化／復号化速度は、４００ＭＨｚのペンティアムＩＩプロセッサ上で、暗号化／復号化アルゴリズムの実行に費やされたクロックサイクル数をカウントすることによって測定された。当該アルゴリズムの試作品は、図７に例示されているように、２つのインスタンスを含むシステム上に、ＭＭＸ（商標）命令を用いたアッセンブリ言語で実装された。この試作品は、カオス的挙動を呈する２つのローレンツシステムを解き、各積分ステップにおいて、すなわち２つのインスタンスにてなる組み合わされた積分ステップの各々において、合計６４ビットを抽出した。この試作品が、図１５乃至図２２を参照して例Ｉで説明した擬似コードプログラムのアルゴリズムと異なる点は、主に次の通りであった。
−  この試作品は、２つのシステムを並列に解くことによりＭＭＸ（商標）技術を利用した。
−  この試作品は、各積分ステップにおいて合計６４ビットを抽出した。
−  この試作品は周期解のテストを行わなかった。
【０３００】
測定値から速度が計算され、
４５０ＭＨｚのペンティアムＩＩプロセッサ上での１０１０メガビット／秒の暗号化／復号化速度に等しいと計算された。
【０３０１】
【表５】
2004530919.tif 000074
【０３０２】
速度は、異なる出典に基づいて評価される。表５の“速度［クロック／バイト］”欄における上付き文字は、出典となる以下の参考文献を示す。
１．Ｃｒｙｐｔｏ＋＋  ４．０  ベンチマークス，www.eskimo.com/~weidai/benchmarks.html，ＭＳ  Ｃ＋＋（インテル、セルロン（Celeron）８５０ＭＨｚ），２００１年１２月７日に利用可能。
２．ブルース・シュナイアーほか，高速なソフトウェア暗号化：インテルのペンティアムプロセッサ上での最適ソフトウェア速度のための暗号化アルゴリズムの設計（Fast Software Encryption: Designing Encryption Algorithms for Optimal Software Speed on the Intel Pentium Processor）。
３．アオキ・カズマロ（Kazumaro Aoki）ほか，ＡＥＳ候補の高速な実装（１２８ビット鍵、１２８ビットブロック、ペンティアムＩＩ）（Fast Implementation of AES Candidates （128 bit keys, 128 bit blocks, Pentium II））。
４．ＮＥＳＳＩＥ第１フェーズの性能評価（ドラフト３．０版）（Performance Evaluation of NESSIE First Phase (draft version 3.0)）。２００１年１２月７日に利用可能なhttp://www.cosic.esat.kuleuven.ac.be/nessie/。
【０３０３】
一般に、多くの実装において、例えばより多くのメモリを必要とするが処理時間を節約することができるルックアップテーブルを用いることによって、速度とメモリの条件が互いに取捨されうる。
実施例ＩＩの終わり．
【０３０４】
例えば２つの数を加算又は乗算する場合のように、２進数で表現された数に対する計算を実行する場合、その加算又は乗算の結果として得られる数のビットが省略されうるか又は無視されうるものであれば、加算又は乗算に含まれる計算の一部を省略することができる。従って、結果として得られる数の最下位ビットが不要であれば、もしくは結果として得られる数の最上位ビットが無視されうるものであれば（擬似乱数発生器の場合、必要なものは計算の真の結果ではなく単に擬似乱数であることから、このことが成り立つ）、結果として得られる数の最下位ビット及び／又は最上位ビットは計算される必要がない。
【０３０５】
従って、別の態様において、本発明は、計算が実行される処理装置のレジスタ幅より大きい所定のビット幅の整数に対して数学的演算を実行するための方法に関する。固定小数点の数での数学的演算又は計算は整数の演算として実行され、これにより、整数は２進数として表現される。整数の２進表現は、所定のレジスタ幅を、例えば３２ビットを必要とする。当該２進数の表現に要する幅より小さいレジスタ幅、例えば８ビットを有する処理装置によって加算又は乗算等の数学的演算を実行する場合には、当該２進数は、処理装置のレジスタ幅に等しいかもしくはこれより小さい幅によってそれぞれ表される複数の２進サブナンバーに分割されることが可能である。従って、２つの３２ビット数は、４個の８ビットサブナンバーにてなる２組に分割されることが可能であり、乗算又は加算は、８ビット処理装置によって８ビットのサブナンバーに対して実行可能である。例えば、
数Ａ＝１１０１１００１１０１１０１０１０１１０１０１０１０１１０１１１と、
数Ｂ＝１００００１１１０１１１１０１１１１１１０１０１０１００１００１と
の加算によって結果Ｒ＝Ａ＋Ｂに到達することは、以下のステップを行うことによって実行可能である。
【０３０６】
１．数Ａ及びＢを各々、４つのサブナンバーＡ１，Ａ２，Ａ３及びＡ４と、Ｂ１，Ｂ２，Ｂ３及びＢ４とに分割する。Ａ１は数Ａの最上位の８ビットを表し、Ａ４は数Ａの最下位の８ビットを表す、等である。従って、上述の例では、サブナンバーは下記の通りとなる。
Ａ１＝１１０１１００１，
Ａ２＝１０１１０１０１，
Ａ３＝０１１０１０１０，
Ａ４＝１０１１０１１１，
Ｂ１＝１００００１１１，
Ｂ２＝０１１１１０１１，
Ｂ３＝１１１１０１０１，
Ｂ４＝０１００１００１。
【０３０７】
２．次に、最下位のサブナンバーＡ４及びＢ４を加算する：Ｒ４＝Ａ４＋Ｂ４。Ａ４及びＢ４の加算から結果的に生じる任意の桁上げＣ４を記憶する。
【０３０８】
３．次に、第２の最下位サブナンバーＡ３及びＢ３、及び上記ステップ２からの桁上げＣ４を加算する：Ｒ３＝Ａ３＋Ｂ３＋Ｃ４。この加算から結果的に生じる任意の桁上げＣ３を記憶する。
【０３０９】
４．ステップ３と同様にＡ２とＢ２を加算してＲ２及びＣ２を得る。
【０３１０】
５．ステップ３及び４と同様にＡ１とＢ１を加算してＲ１を得る。この加算から結果的に生じる任意の桁上げＣ１は、オーバーフローと見なし、考慮しない。
【０３１１】
６．ＡとＢの加算によって得られる数を４つのサブナンバーＲ１，Ｒ２，Ｒ３及びＲ４として記憶し、及び／又はサブナンバーＲ１，Ｒ２，Ｒ３及びＲ４から構成された３２ビット幅の列で表現する。
【０３１２】
乗算演算の結果として得られる数におけるすべてのビットが別の計算に使用されるわけではない場合、及び／又はすべてのビットが別の計算にとって重要なわけではなく無視されうる場合、乗算される数のビット幅より小さいレジスタ幅を有する処理装置上での乗算演算に関わる処理時間は、以下で説明するように部分的乗算のみを実行することによって短縮可能である。例えば、８ビット処理装置上での２つの１６ビット数Ｄ及びＥ、すなわち、
Ｄ＝１１０１１００１１０１１０１０１と、
Ｅ＝０１１０１０１０１０１１０１１１と
の乗算によって３２ビット数Ｆに到達することは、以下のステップによって実行可能である。
【０３１３】
１．数Ｄ及びＥを各々、２つのサブナンバーＤ１，Ｄ２及びＥ１，Ｅ２に分割する。Ｄ１はＤの最上位の８ビットを表し、Ｄ２はＤの最下位の８ビットを表す、等である。従って、上述の例では、サブナンバーは下記の通りとなる。
Ｄ１＝１１０１１００１，
Ｄ２＝１０１１０１０１，
Ｅ１＝０１１０１０１０，
Ｅ２＝１０１１０１１１。
【０３１４】
２．Ｄ１にＥ１を乗算し、２つの８ビット数Ｇ１及びＧ２で表される１６ビット数を得る。
【０３１５】
３．Ｄ１にＥ２を乗算し、２つの８ビット数Ｈ１及びＨ２で表される１６ビット数を得る。
【０３１６】
４．Ｄ２にＥ１を乗算し、２つの８ビット数Ｉ１及びＩ２で表される１６ビット数を得る。
【０３１７】
５．Ｄ２にＥ２を乗算し、２つの８ビット数Ｊ１及びＪ２で表される１６ビット数を得る。
【０３１８】
６．結果として得られる３２ビット数Ｆを４つの８ビット数Ｆ１，Ｆ２，Ｆ３及びＦ４で表す。ここで、図１４に示されたように、
Ｆ４＝Ｊ２，
Ｆ３＝Ｈ２＋Ｉ２＋Ｊ１，
Ｆ２＝Ｇ２＋Ｈ１＋Ｉ１＋［Ｆ３の計算から結果的に生じる任意の桁上げ］，
Ｆ１＝Ｇ１＋［Ｆ２の計算から結果的に生じる任意の桁上げ］
である。ここで、ＭＳは“最上位の８ビット”を示し、ＬＳは“最下位の８ビット”を示す。
【０３１９】
処理時間は、Ｆ４、すなわち乗算の結果として得られる数の最下位ビットを無視することにより、かつＦ３をもたらす加算においてＪ１を無視することによって節約可能である。従って、ステップ５のＤ２とＥ２の乗算は省略されることが可能であり、よって実行される数学的演算はより少なくなり、処理時間の節約に繋がる。この省略は計算結果に影響するが、省略が例えば擬似乱数発生器における、例えば暗号化／復号化アルゴリズムでの計算を通じて一貫して実行されるならば、かつこれが暗号化と復号化の両方で実行されるならば、この省略は許容されうる。一般に、暗号化／復号化等の問題となるコンテキストにおいて重要な、カオス的挙動等の数学的システムの特性は、１つ又は複数の計算ステップの省略が計算に与える影響に関わらず保持されることは保証されなければならない。
【０３２０】
別の態様では、本発明は、第１の２進数及び第２の２進数に対して乗算演算を実行する方法に関する。本方法は、多くの中間結果を総和することを含み、これにより、中間結果の総和は２つの数の積に等しくなる。各中間結果は、第１の数のうちの単一のビット（１又は０）と、第２の数αの全体との積として得られ、これにより、この積と、従って中間結果とは、簡単な“ｉｆ．．．ｔｈｅｎ”アルゴリズム及び／又は論理積演算によって、積１・α＝αとして、かつ積０・α＝０として決定されることが可能である。
【０３２１】
中間の数の計算に引き続き、中間の数は、所定数の位置だけ左へ移動される。上記移動される位置の数は、その特定の中間の数を計算する基礎となる第１の数のビットの位置に対応する。代替として、第２の数、又は第１の数の特定ビットのいずれかが左にスイッチングして移動される。従って、２つの数のうちの第１のものの１ビットを乗算するステップが、第１の数の各ビットに対して反復される。例えば、第１の数０１１０と第２の数１０１０の積は、次のように計算される。すなわち、第１の数の最下位ビット０は第２の数１０１０と乗算され、第１の中間の数００００が取得される。次に、第１の数の最下位ビットから２番目のビット１が第２の数と乗算され、かつ１つの位置だけ左にシフトされて第２の中間の数１０１００が取得される。次に、第１の数の最下位ビットから３番目のビット１が第２の数と乗算され、かつ２つの位置だけ左にシフトされて第３の中間の数１０１０００が取得される。最後に、第１の数の最上位ビット０が第２の数と乗算され、かつ３つの位置だけ左にシフトされて第４の中間の数０００００００が取得される。結果として得られる数は、下に示した通り、４つの中間の数の総和として取得される。下線は、個々のステップでどのビットが乗算されているかを示す。
【０３２２】
［式１］
2004530919.tif 000075
【図面の簡単な説明】
【０３２３】
【図１】電子データを暗号化し、伝送し、復号化するシーケンスを示す図である。
【図２】ブロック暗号システムにおける暗号化シーケンスを示す図である。
【図３】ストリーム暗号システムにおける暗号化シーケンスを示す図である。
【図４】本発明の様々な態様による暗号化／復号化アルゴリズムにおける鍵要素を示す図である。
【図５】ローレンツシステムの数値解のプロットである。
【図６】パディングによる鍵の拡張を示す図である。
【図７】２つ以上の同一又は異なるカオス的システムのインスタンスを同時に計算する可能な方法を示す図である。
【図８】周期解のチェックを実行する原理を示す図である。
【図９】周期解を有する数学的システムを示す図である。
【図１０】以前に計算された座標を記憶する座標キャッシュにおける複数のレベル間の移動を示している。
【図１１】周期解を検出するための様々な基準を示す図である。
【図１２】周期解を検出するための様々な基準を示す図である。
【図１３】周期解を検出するための様々な基準を示す図である。
【図１４】８ビットプロセッサ上での１６ビット数の乗算方法を示す図である。
【図１５】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【図１６】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【図１７】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【図１８】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【図１９】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【図２０】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【図２１】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【図２２】本発明による暗号化方法の一実施形態の動作を示すフローチャートである。
【符号の説明】
【０３２４】
Ｄ１，Ｄ２，Ｅ１，Ｅ２…サブナンバー、
Ｆ…３２ビット数、
Ｆ１乃至Ｆ４，Ｇ１，Ｇ２，Ｈ１，Ｈ２，Ｉ１，Ｉ２，Ｊ１，Ｊ２…８ビット数。
【図１】
2004530919.tif 000087
【図２】
2004530919.tif 000088
【図３】
2004530919.tif 000089
【図４】
2004530919.tif 000090
【図７】
2004530919.tif 000091
【図８】
2004530919.tif 000092
【図１０】
2004530919.tif 000093
【図１４】
2004530919.tif 000094
【図１５】
2004530919.tif 000095
【図１６】
2004530919.tif 000096
【図１７】
2004530919.tif 000097
【図１８】
2004530919.tif 000098
【図１９】
2004530919.tif 000099
【図２０】
2004530919.tif 000100
【図２１】
2004530919.tif 000101
【図２２】
2004530919.tif 000102
【国際公開パンフレット】
2004530919.tif 000103
2004530919.tif 000104
2004530919.tif 000105
2004530919.tif 000106
2004530919.tif 000107
2004530919.tif 000108
2004530919.tif 000109
2004530919.tif 000110
2004530919.tif 000111
2004530919.tif 000112
2004530919.tif 000113
2004530919.tif 000114
2004530919.tif 000115
2004530919.tif 000116
2004530919.tif 000117
2004530919.tif 000118
2004530919.tif 000119
2004530919.tif 000120
2004530919.tif 000121
2004530919.tif 000122
2004530919.tif 000123
2004530919.tif 000124
2004530919.tif 000125
2004530919.tif 000126
2004530919.tif 000127
2004530919.tif 000128
2004530919.tif 000129
2004530919.tif 000130
2004530919.tif 000131
2004530919.tif 000132
2004530919.tif 000133
2004530919.tif 000134
2004530919.tif 000135
2004530919.tif 000136
2004530919.tif 000137
2004530919.tif 000138
2004530919.tif 000139
2004530919.tif 000140
2004530919.tif 000141
2004530919.tif 000142
2004530919.tif 000143
2004530919.tif 000144
2004530919.tif 000145
2004530919.tif 000146
2004530919.tif 000147
2004530919.tif 000148
2004530919.tif 000149
2004530919.tif 000150
2004530919.tif 000151
2004530919.tif 000152
2004530919.tif 000153
2004530919.tif 000154
2004530919.tif 000155
2004530919.tif 000156
2004530919.tif 000157
2004530919.tif 000158
2004530919.tif 000159
2004530919.tif 000160
2004530919.tif 000161
2004530919.tif 000162
2004530919.tif 000163
2004530919.tif 000164
2004530919.tif 000165
2004530919.tif 000166
2004530919.tif 000167
2004530919.tif 000168
2004530919.tif 000169
2004530919.tif 000170
2004530919.tif 000171
2004530919.tif 000172
2004530919.tif 000173
2004530919.tif 000174
2004530919.tif 000175
2004530919.tif 000176
2004530919.tif 000177
2004530919.tif 000178
2004530919.tif 000179
2004530919.tif 000180
2004530919.tif 000181
2004530919.tif 000182
2004530919.tif 000183
2004530919.tif 000184
2004530919.tif 000185
2004530919.tif 000186
2004530919.tif 000187
2004530919.tif 000188
2004530919.tif 000189
2004530919.tif 000190
【国際公開パンフレット（コレクトバージョン）】
2004530919.tif 000191
2004530919.tif 000192
【国際調査報告】
2004530919.tif 000193
2004530919.tif 000194
2004530919.tif 000195
2004530919.tif 000196
2004530919.tif 000197