(57)【要約】Ｎがｐおよびｑへ因数分解されるか、またはＮが素数であるときに、組ＺＮに対してキーによる整数置換を構成する方法。Ｎビットは、代表的な指数のキーによる置換を求めることによって置換される。Ｎがｐおよびｑへ因数分解できるときは、指数の組は２つの部分へ分割される。この部分は“ラウンド”と呼ばれる反復的な処理を行なわれ、各ラウンドでは、第１の２分の１ラウンドの関数は第１の部分について演算して、第１の２分の１ラウンドの値を形成し、第１の２分の１ラウンドの値と第２の部分とはモジューロｐの加算器によって一緒に加算され、第１の出力値を形成し、第２の２分の１ラウンドの関数は第２の部分について演算して、第２の２分の１ラウンドの値を形成し、第２の２分の１ラウンドの値と第１の部分とが、モジューロｑの加算器によって一緒に加算され、第２の出力値を形成する。このやり方では、ラウンドの出力は再び順序付けられる。Ｎが１３以上の素数であるときは、Ｎは合成数の値ｓとｔとに分割され、２つの組はｓおよびｔの要素でそれぞれ形成される。次に各組は、Ｎが素数でないときの方法を使用して置換される。各ラウンドの最後に、２つのブロックは混合演算を使用してを合成される。
2004511812.tif 000002
【特許請求の範囲】
【請求項１】
ｐ＞１およびｑ＞１として、Ｎ＝ｐｑである場合に、ＺＮの入力値からＺＮの出力値を求めるための、複数のラウンドから成る方法であって、各ラウンドが、
第１のキーおよび第２のキーを生成するステップと、
ラウンドの入力を、Ｚｐの要素である第１の部分と、Ｚｑの要素である第２の部分とに分割するステップと、
第１のキーを第２の部分に適用し、Ｚｐの要素である第３の部分を生成するステップと、
モジューロｐの加算器を使用して第１の部分および第２の部分を加算して、第４の部分を生成するステップと、
第２のキーを第４の部分へ適用し、Ｚｑの要素である第５の部分を生成するステップと、
モジューロｑの加算器を使用して第５の部分を第２の部分へ加算して、第６の部分を生成するステップと、
第４の部分と第６の部分を合成して、ラウンドの出力を形成するステップとを含み、
ラウンドが最終のラウンドであるとき、ラウンドの出力が本方法の出力値であるか、さもなければラウンドの出力が次のラウンドへの入力になる方法。
【請求項２】
Ｎビットのデータブロックを置換するための方法であって、Ｎビットのデータブロックの各ビットを複数のＮの指数の中からの指数と関係付け、Ｎを２以上の整数値ｐおよび２以上の整数値ｑへ因数分解し、
複数のＮの指数を、グループＺｐについて構成されている第１の部分とグループＺｑについて構成されている第２の部分とへ分割して、複数のＮの指数を第２の部分と、整数値ｑによって定義される多価の第１の部分との合成として表わすステップと、
第１の２分の１ラウンドのキーと第２の２分の１ラウンドのキーとを構成するステップと、
第２の部分と第１の２分の１ラウンドのキーとから、第２の部分と第１の２分の１ラウンドのキーとについて演算する第１の非線形関数の出力である第１の２分の１ラウンドの値を求めるステップと、
モジューロｐの加算器を使用して、第１の２分の１ラウンドの値を第１の部分と合成して、第３の部分を生成するステップと、
第３の部分と第２の２分の１ラウンドのキーとから、第３の部分と第２の２分の１ラウンドのキーとについて演算する第２の非線形関数の出力である第２の２分の１ラウンドの値を求めるステップと、
モジューロｑの加算器を使用して、第２の２分の１ラウンドの値と第２の部分とを合成して、第４の部分を生成するステップとを含む方法。
【請求項３】
複数のラウンドの各ラウンドごとにステップが反復し、各ラウンドにおいて生成される第３の部分および第４の部分を、次のラウンドへの入力として使用する請求項２記載の方法。
【請求項４】
次のラウンドが最終のラウンドであり、
最終のラウンドにおいて生成される第３の部分を整数値ｑと乗算するステップと、
乗算された第３の部分と、最終ラウンドにおいて生成された第４の部分とを合成して、最終結果を生成するステップと、
最終結果にしたがってＮビットのデータブロックを置換するステップとを含む請求項３記載の方法。
【請求項５】
第１の２分の１ラウンドのキーおよび第２の２分の１ラウンドのキーをストリーム暗号によって生成する請求項２記載の方法。
【請求項６】
第１の２分の１ラウンドのキーおよび第２の２分の１ラウンドのキーをキー生成方法によって生成する方法であって、
複数の均等に分配されたバイトを生成するステップと、
先ず複数の均等に分配されているバイトの連続している要素の第１の対の一方を乗数によって乗算し、連続している要素の第１の対を一緒に加算して、中間値を生成するステップと、
第１の中間値を検査して、第１の中間値が第１の所定量よりも小さいかどうかを判断するステップと、
第１の中間値が第１の所定量よりも大きいときは、複数の均等に分配されているバイトの連続している要素の第１の対を一緒に加算するステップへ戻るステップと、
第１の中間値を第１の整数値だけモジュールによって低減して、第１の２分の１ラウンドのキーを生成するステップと、
先ず複数の均等に分配されているバイトの連続している要素の第２の対の一方を乗数によって乗算し、連続している要素の第２の対を一緒に加算して、中間値を生成するステップと、
第２の中間値を検査して、第２の中間値が第２の所定量よりも小さいかどうかを判断するステップと、
第２の中間値が第１の所定量よりも大きいときは、複数の均等に分配されているバイトの連続している要素の第２の対を一緒に加算するステップへ戻るステップと、
第２の中間値を第２の整数値だけモジュールによって低減して、第２の２分の１ラウンドのキーを生成するステップと、
第１の２分の１ラウンドのキーと第２の２分の１ラウンドのキーとの複数の対の各々が複数のラウンドの各々と関係しているように、第１の２分の１ラウンドのキーと第２の２分の１ラウンドのキーとの複数の対を生成するために、キー生成方法のステップを繰返すステップとを含む請求項２記載の方法。
【請求項７】
第１の所定量が第２の所定量に等しい請求項６記載のキー生成方法。
【請求項８】
ｎ≧２であり、ｘが第１の所定量の因数であり、かつｉが反復ラウンドを識別するときに、キー生成方法が複数のサブキー｛ａ１，ｉ，ａ２，ｉ．．，ａｎ，ｉ｝について値を判断し、第１の２分の１ラウンドのキーはＫ１ｉ＝ｘｎ−１ａ１，ｉ＋ｘｎ−２ａ２，ｉ＋．．．＋ａｎ，ｉであるステップをさらに含む請求項６記載のキー生成方法。
【請求項９】
第１の非線形関数が、
第２の部分を第１の定数値によって乗算して、第１の乗算結果を生成するステップと、
第１の乗算結果を第１の２分の１ラウンドのキーと合成して、第１の合成結果を生成するステップと、
第１の合成結果を代入して、第１の合成結果を置換して、第１の２分の１ラウンドの値を生成するステップを含む方法である請求項２記載の方法。
【請求項１０】
第１の合成結果を代入するステップであって、
第１の合成値を代入表示値および代入入力値へ分解するステップと、
代入表示値を使用して、第１の複数の置換ボックスの１つを選択するステップと、
第１の複数の代入ボックスからの選択された代入ボックスへ代入入力値を入力して、第１の２分の１ラウンドの値を生成するステップを含む請求項９記載の方法。
【請求項１１】
第２の非線形関数が、
第２の定数値によって第３の部分を乗算して、第２の乗算結果を生成するステップと、
第２の乗算結果を第２の２分の１ラウンドのキーと合成して、第２の合成結果を生成するステップと、
第２の合成結果を代入して、第２の合成結果を置換して、第２の２分の１ラウンドの値を生成するステップとを含む方法である請求項２記載の方法。
【請求項１２】
第１の合成結果を代入するステップが、
第１の合成結果を代入表示値および代入入力値へ分解するステップと、
代入表示値を使用して、第２の複数の代入ボックスの１つを選択するステップと、
第２の複数の代入ボックスからの選択された代入ボックスへ代入入力値を入力し、第２の２分の１ラウンドの値を生成するステップとを含む請求項１１記載の方法。
【請求項１３】
第１の非線形関数が、
第１の定数値によって第２の部分を乗算して、第１の乗算結果を生成するステップと、
第１の乗算結果がｘｎ−１ｕ１＋ｘｎ−２ｕ２＋．．．＋ｕｎに等しくなるように、第１の乗算結果をｕｎで表わした複数の項へ分解するステップと、
複数の項の各々を複数のサブキーａ１，ｉ，ａ２，ｉ．．，ａｎ，ｉの関係するものとモジュールによって加算して、複数の代入入力値を生成するステップと、
複数の代入入力値の各々を複数の代入ボックスの関係するものへ入力して、複数の代入値を生成するステップと、
複数の代入された値の中の少なくとも２つをモジュールによって加算して、第１の２分の１ラウンドの値を生成するステップとを含む方法である請求項８記載の方法。
【請求項１４】
Ｎが１３以上の素数であり、ＳおよびＴが、Ｎ＝Ｓ＋Ｔとなるような合成数の値であるときに、ＺＮの入力値からＺＮの出力値を求めるための、複数のラウンドから成る方法であって、この方法の各ラウンドが、
第１のキーおよび第２のキーを生成するステップと、
第１の組のＳの入力値内の各要素を組｛０，．．．，Ｓ−１｝内のユニークな指数へ割り当てるステップと、
Ｔの入力値の第２の組内の各要素を組｛０，．．．，Ｔ−１｝内のユニークな指数へ割り当てるステップと、
複数の入力指数が組｛０，．．．，Ｓ−１｝の要素であるときに、第１のキーを使用する第１のキーによる整数置換を複数の入力指数に行って、第１の複数の出力指数を生成するステップと、
複数の入力指数が組｛０，．．．，Ｔ−１｝の要素であるときに、第２のキーを使用する第２のキーによる整数置換を複数の入力指数に行って、第２の複数の出力指数を生成するステップと、
第１の複数の出力指数を第２の複数の出力指数と混合するステップとを含む方法。
【請求項１５】
第１の複数の出力指数を第２の複数の出力指数と混合するステップからの出力が、次のラウンドのための入力として使用される請求項１４記載の方法。
【請求項１６】
次のラウンドが最終ラウンドである方法であって、第１の複数の出力指数を第２の複数の出力指数と混合するステップからの出力にしたがって、入力ビット配置を出力ビット配置へ再配置するステップをさらに含む請求項１５記載の方法。
【請求項１７】
プロセッサと、
記憶媒体とを含む無線通信デバイスであって、
記憶媒体がプロセッサによって実行可能な命令を記憶し、プロセッサがＮビットのデータブロックを置換し、各ビットが複数のＮの指数の中からの指数と関係付けられ、複数のＮの指数が、
複数のＮの指数の各々を、グループＺｐについて構成されている第１の部分と、グループＺｑについて構成されている第２の部分とに分割し、複数のＮの指数の各々が、第２の部分と、整数値ｑによって定義される多価の第１の部分との合成として表わすことができるステップと、
第１の２分の１ラウンドのキーと第２の２分の１ラウンドのキーとを構成するステップと、
第２の部分と第１の２分の１ラウンドのキーとから、第２の部分と第１の２分の１ラウンドのキーとについて演算する第１の非線形関数の出力である第１の２分の１ラウンドの値を求めるステップと、
モジューロｐの加算器を使用して、第１の２分の１ラウンドの値を第１の部分と合成して、第３の部分を生成するステップと、
第３の部分と第２の２分の１ラウンドのキーとから、第３の部分と第２の２分の１ラウンドのキーとに対して演算する第２の非線形関数の出力である第２の２分の１ラウンドの値を求めるステップと、
モジューロｑの加算器を使用して、第２の２分の１ラウンドの値を第２の部分と合成して、第４の部分を生成するステップとを含む方法によって置換される無線通信デバイス。
【請求項１８】
プロセッサと、
記憶媒体とを含む無線通信デバイスであって、
記憶媒体がプロセッサによって実行可能な１組の命令を記憶し、プロセッサがＮビットのデータブロックを置換し、Ｎが合成数または素数であり、Ｎが合成数であるときは、プロセッサはＮビットのデータブロックに対してキーによる整数置換を行なうための１組の命令を実行するが、Ｎが素数であるときは、プロセッサはＮビットのデータブロックを第１の組と第２の組とに分割して、第１の組に対して第１のキーによる整数置換を、第２の組に対して第２のキーによる整数置換を行なう１組の命令を実行する無線通信デバイス。
【請求項１９】
ｐ＞１およびｑ＞１として、Ｎ＝ｐｑであるときに、ＺＮの入力値からＺＮの出力値を求めるための装置であって、
第１のキーおよび第２のキーを生成するための手段と、
１ラウンドの入力を、Ｚｐの要素である第１の部分と、Ｚｑの要素である第２の部分とに分割するための手段と、
第１のキーを第２の部分に適用し、Ｚｐの要素である第３の部分を生成するための手段と、
モジューロｐの加算器を使用して第１の部分と第３の部分とを加算して、第４の部分を生成するための手段と、
第２のキーを第４の部分へ適用し、Ｚｑの要素である第５の部分を生成するための手段と、
モジューロｑの加算器を使用して第５の部分を第２の部分へ加算して、第６の部分を生成する手段と、
第４の部分と第６の部分とを合成して、ラウンドの出力を形成する手段とを含む装置。
【請求項２０】
Ｎが１３以上の素数であり、ＳおよびＴが、Ｎ＝Ｓ＋Ｔとなるような合成数の値であるときに、ＺＮの入力値からＺＮの出力値を求める装置であって、複数のラウンドを含み、各ラウンドが、
第１のキーおよび第２のキーを生成するための手段と、
第１の組のＳの入力値を組｛０，．．．，Ｓ−１｝内のユニークな指数へ割り当てるための手段と、
Ｔの入力値の第２の組内の各要素を組｛０，．．．，Ｔ−１｝内のユニークな指数へ割り当てるための手段と、
複数の入力指数が組｛０，．．．，Ｓ−１｝の要素であるとき、第１のキーを使用する第１のキーによる整数置換を複数の入力指数に対して行って、第１の複数の出力指数を生成するための手段と、
複数の入力指数が組｛０，．．．，Ｔ−１｝の要素であるとき、第２のキーを使用する第２のキーによる整数置換を複数の入力指数に対して行って、第２の複数の出力指数を生成するための手段と、
第１の複数の出力指数を第２の複数の出力指数と混合する手段とを含む装置。
【請求項２１】
第１のステーションと第２のステーションとの間で送られるＮビットのデータメッセージを認証するための方法であって、
第１のステーションにおいてグループＺＮの複数の要素に対してキーによる整数置換を使用して、置換順序を生成するステップと、
置換順序にしたがってＮビットのデータメッセージ内の複数のビットを再び順序付けて、置換されたＮビットのメッセージを形成するステップと、
置換されたＮビットのメッセージに基づいて第１の巡回冗長検査（ｃｙｃｌｉｃ ｒｅｄｕｎｄａｎｃｙ ｃｈｅｃｋ， ＣＲＣ）メッセージを生成するステップと、
Ｎビットのデータメッセージおよび第１の巡回冗長検査メッセージを第１のステーションから第２のステーションへ送るステップと、
第２のステーションにおいて受信したＮビットのデータメッセージおよび受信した巡回冗長検査メッセージを検出するステップと、
受信したＮビットのデータメッセージに対してキーによる整数の置換を使用して、第２のステーションにおける第２の置換順序を求めるステップと、
第２の置換順序に基づいて第２の巡回冗長検査メッセージを生成するステップと、
受信した巡回冗長検査メッセージと第２の巡回冗長検査メッセージとを比較して、受信した巡回冗長検査メッセージおよび第２の巡回冗長検査メッセージが整合するとき、受信したＮビットのデータメッセージが認証されるステップとを含む方法。
【請求項２２】
エラーを訂正するのに使用できる方法であって、
受信した巡回冗長検査メッセージおよび第２の巡回冗長検査メッセージとを比較するステップの結果が、所定の閾値以下のエラー量になるかどうかを判断するステップと、
比較するステップの結果が所定の閾値以下のエラー量になるときは、受信した巡回冗長検査メッセージを使用して、受信したＮビットのデータメッセージを訂正するステップと、
比較するステップの結果が所定の閾値よりも多いエラー量になるときは、Ｎビットのデータメッセージの再伝送を要求するステップをさらに含む請求項２１記載の方法。
【発明の詳細な説明】
【０００１】
発明の背景
Ｉ．発明の分野
本発明は、概ね通信の分野、とくにメッセージ認証コードにおいて使用するためのＮを法とする整数の組に対してキーによる置換を構成することに関する。
【０００２】
ＩＩ．背景
メッセージ認証コード（ｍｅｓｓａｇｅ ａｕｔｈｅｎｔｉｃａｔｉｏｎ ｃｏｄｅ， ＭＡＣ）は、暗号によって求められる項目（ｉｔｅｍ）であり、これは、特定の当事者から発信され、かつ他の当事者によって変更されていないメッセージを確認（ｖｅｒｉｆｙ）するために、特定のメッセージに添付される。このために、ＭＡＣは遠隔通信の多数の分野で使用することができる。ＭＡＣは、例えば、無線通信の分野で使用されている。
【０００３】
無線通信の分野には、多くの応用があり、例えば、コードレス電話、ページング、無線ローカルループ、パーソナルディジタルアシスタント（ｐｅｒｓｏｎａｌ ｄｉｇｉｔａｌ ａｓｓｉｓｔａｎｔ， ＰＤＡ）のような無線データアプリケーション、セルラおよびＰＣＳ電話システムのような無線電話、移動インターネットプロトコル（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ， ＩＰ）電話、並びに衛星通信システムが含まれる。特定の重要なアプリケーションは、移動加入者のための無線電話である。
【０００４】
種々の空中インターフェイスは、無線通信システム、例えば周波数分割多重アクセス（ｆｒｅｑｕｅｎｃｙ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ， ＦＤＭＡ）、時分割多重アクセス（ｔｉｍｅ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ， ＴＤＭＡ）、および符号分割多重アクセス（ｃｏｄｅ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ， ＣＤＭＡ）のために開発された。これと関連して、種々の国内および国際的な標準規格、例えばＡｄｖａｎｃｅｄ Ｍｏｂｉｌｅ Ｐｈｏｎｅ Ｓｅｒｖｉｃｅ （ＡＭＰＳ）、Ｇｌｏｂａｌ Ｓｙｓｔｅｍ ｆｏｒ Ｍｏｂｉｌｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ （ＧＳＭ）、Ｉｎｔｅｒｉｍ Ｓｔａｎｄａｒｄ ９５ （ＩＳ−９５）が設定された。
【０００５】
無線電話通信システムの例には、符号分割多重アクセス（ｃｏｄｅ ｄｉｖｉｓｉｏｎ ｍｕｌｔｉｐｌｅ ａｃｃｅｓｓ， ＣＤＭＡ）システムがある。ＩＳ−９５の標準規格、および派生の標準規格、すなわちＩＳ−９５Ａ、ＡＮＳＩ Ｊ−ＳＴＤ−００８、ＩＳ−９５Ｂ、提案された第三世代の標準規格であるＩＳ−９５ＣおよびＩＳ−２０００、データに限定して提案された高データレートのＣＤＭＡの標準規格、など（ここでは、まとめてＩＳ−９５と呼ぶ）は、米国電気通信工業会（Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｉｎｄｕｓｔｒｙ Ａｓｓｏｃｉａｔｉｏｎ， ＴＩＡ）および他の周知の標準規格制定機関によって公布され、セルラまたはＰＣＳの電話通信システムのためのＣＤＭＡの空中インターフェイスの使用を指定している。ＩＳ−９５の標準規格の使用に実質的にしたがって構成された無線通信システムの例は、米国特許第５，１０３，４５９号および第４，９０１，３０７号に記載されており、これらは本発明の譲受人に譲渡され、ここでは参考文献として十分に取り上げている。
【０００６】
無線通信システム上で送られたデータを暗号化するための１つの方法には、国立標準技術研究所（Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ）によってＦＩＰＳ ＰＵＢ ４６−２において（１９９３年１２月３０日に）公布されたデータ暗号化規格（Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ， ＤＥＳ）があり、これはフェイステルネットワーク（Ｆｅｉｓｔｅｌ Ｎｅｔｗｏｒｋ）を使用して、二値コード情報を暗号へ変換する。フェイステルネットワークは、ＤＥＳにおいて６４ビット長のデータブロックを変換するのに使用される。最初に、６４ビットのデータブロックに対して最初の置換（ｐｅｒｍｕｔａｔｉｏｎ）ステップを行なう。置換されたデータブロックは、３２ビットの長さをもつ両半分のブロックに分割され、一方のブロックはＬに分類され、他方のブロックはＲに分類される。これらのブロックは、次に示す関係式を使用して反復的な手順で処理される。
【０００７】
【数１】
2004511812.tif 000003
【０００８】
各反復ステップをラウンド（ｒｏｕｎｄ）と呼ぶので、関数ｆを“ラウンド”関数とも呼ぶ。ＤＳＮのアルゴリズムでは、ラウンド関数ｆは４つの演算から成る。最初に、５６ビットのキーから４８ビットのサブキーを選択する。次にラウンド関数ｆは、拡張置換（ｅｘｐａｎｓｉｏｎ ｐｅｒｍｕｔａｔｉｏｎ）を介して右半分のデータブロックを３２ビットから４８ビットへ拡張するステップと、ＸＯＲ演算を介してこの拡張の結果を４８ビットのサブキーと合成するステップと、この合成の結果を８つの代入ボックス（ｓｕｂｓｔｉｔｕｔｉｏｎ ｂｏｘ）へ送って、追加の３２ビットを生成するステップと、この生成の結果を置換するステップとを含む。関数ｆの出力は別のＸＯＲ演算によって左半分のブロックと合成され、この合成の結果は新しい右半分のブロックとして使用され、一方で古い右半分のブロックは、次のラウンドの新しい左半分のブロックとして使用される。各ラウンドごとにｆを再構成して、次の関係式を満足させることができるので、ＤＥＳのラウンドは可逆性（ｒｅｖｅｒｓｉｂｌｅ）である。
【０００９】
【数２】
2004511812.tif 000004
【００１０】
データブロックは二値形式であるので、ＤＥＳのような従来技術の方法では、プレーンテキストメッセージ（その要素はｎの項のカルテシアン積Ｚ２×Ｚ２×．．．×Ｚ２の組のメンバーである）を暗号文メッセージ（同様にその要素はｎの項のカルテシアン積Ｚ２×Ｚ２×．．．×Ｚ２の組のメンバーである）へ暗号化する。ここで使用されているように、Ｚｍは、加法のモジューロｍにしたがう巡回群｛０，１，．．．，ｍ−１｝である。したがって、ＤＥＳの目的は、プレーンテキスト（例えば、元のデータ）のメッセージ内のビットの順序を変更することではない。むしろ、ＤＥＳの目的は、暗号文の各ビットがプレーンテキストの全ビットに依存するような暗号文を生成することである。
【００１１】
ＤＥＳは可逆性であり、キーの制御のもとで２６４の入力を２６４の出力へ変換するので、ＤＥＳは、キーが整数の組｛０，１，．．．，２６４−１｝の置換を選択する方法であると考えることもでき、したがってキーによって選択される置換は、許可されていない当事者から隠され続けなければならない。
【００１２】
通常の通信では、ＭＡＣは、メッセージと、メッセージの発信者および受信者のみが知っている共有の秘密キーＫとが入力された関数の出力である。選択された特定の関数が保護されているときは、送られたメッセージを傍受し、かつそれを変更する可能性のあるアクティブなアタッカー（ａｃｔｉｖｅ ａｔｔａｃｋｅｒ）は、キーＫを発見することも、受信者が合理的な確率で妥当（ｖａｌｉｄ）として受信することになるメッセージを生成することもできない。
【００１３】
新しいタイプのＭＡＣは、１９９９年８月９日に出願された米国特許出願第０９／３７１，１４７号（“ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＦＯＲ ＧＥＮＥＲＡＴＩＮＧ Ａ ＭＥＳＳＡＧＥ ＡＵＴＨＥＮＴＩＣＡＴＩＯＮ ＣＯＤＥ”）において提案され、本発明の譲受人によって譲渡され、ここでは参考文献として十分に取り入れており、このＭＡＣは、幾つかのキーの影響のもとでｍビットのデータブロックのビットを再び順序付け、再び順序付けられたｍビットブロックの線形関数であるｘビットの巡回冗長検査（ｃｙｃｌｉｃ ｒｅｄｕｎｄａｎｃｙ ｃｈｅｃｋ， ＣＲＣ）を構成することに依存している。このＭＡＣは、ＣＲＣ−ＭＡＣと呼ぶ。送信者は元のｍ−ビットのデータブロックをＣＲＣ−ＭＡＣと一緒に受信者へ送る。受信者は共有のキーを使用して、受信したデータメッセージのビットを再び順序付ける。次に受信者は生成されたブロックからＣＲＣを計算する。この方法を使用すると、受信者は、データが転送中に変更されたかどうかを検出することと、伝送中に発生した少数のエラーを訂正することができ、一方でアクティブなアタッカーには、メッセージを偽造または変更するのがさらに困難になる。
【００１４】
ｍ＋ｘ＝２ｘ−１−１であるとき、ｍおよびｘが最適であることは、よく知られている。ｘビットのＣＲＣ−ＭＡＣの構成は、米国特許出願第０９／３７１，１４７号により詳しく記載されている。この技術において普通の技能をもつ者には、１６ビットのＣＲＣは無線通信の分野において特定用途をもつことが知られている。上述の関係式において数ｘ＝１６を使用すると、ＣＲＣ−ＭＡＣの構成のためのデータブロックの最適な大きさは、ｍ＝（２１５−１）−１６＝３２，７５１ビットである。
【００１５】
ｍおよびｘの最適値について既に記載したように、ＣＲＣ−ＭＡＣには、元のｍビットのデータブロックのビットを再び順序付けることによって、キーを使用してｍビットの中間ブロック、ここではｍ＝（２ｘ−１−１）を構成する方法が必要である。米国特許出願第０９／３７１，１４７号に記載されているように、ｍビットの中間ブロックの構成は２つのアルゴリズムを使用して実行することができる。第１のアルゴリズムで、各指数（ｉｎｄｉｃｅｓ）をｍビットのデータブロック内のビットへ処理する。第１のアルゴリズムは、ｍビットのデータブロックの各ビット位置と関係する各指数ｘについて、ｘと同じ範囲内のユニークな指数ｙを判断する（なお、ｙはｘおよび共有の秘密キーから判断される）ため第２のアルゴリズムに要求する。次に第１のアルゴリズムで、中間のブロックのビット位置ｙの値を、データブロックの位置ｘにおけるビットの値に設定する。
【００１６】
第１のアルゴリズムが範囲｛０，１，．．．，ｍ−１｝内の指数ｘの各々についてこれらのステップを実行すると、中間のブロックはｍビットのブロックになり、ここにはデータブロックのビットが異なる順序で含まれている。ＣＲＣ−ＭＡＣを保護するために、所与のキーについて、第１のアルゴリズムが中間のブロックの同じ位置に同じブロックからの２ビットを置かないことが必要である。第２のアルゴリズムが、各キーごとに組｛０，１，．．．，ｍ−１｝から各キー自体への１対１のマッピングを定義するときのみ、この条件は満たされる。１対１のマッピングは、この技術では一般的に置換（ｐｅｒｍｕｔａｔｉｏｎ）と呼ばれている。したがって、ＣＲＣ−ＭＡＣには、キーを使用して、組｛０，１，．．．，ｍ−１｝における置換を定義する方法が必要である。さらに、キーによって選択される置換は、許可されていない当事者からは隠され続けなければならない。
【００１７】
ＤＥＳは、キーを使用して整数の組｛０，１，．．．，２６４−１｝における置換を判断する方法であるとすると、キーによって選択される置換は許可されていない当事者から隠され続けなければならない。ｍの値が２６４であるときは、ＤＥＳは第２のアルゴリズムに対する条件を満たしていることになる。しかしながら、ＤＥＳおよび他のブロックの暗号は順序（ｏｒｄｅｒ）２Ｍの組間の１対１の関係を生成するためにのみ構成されていて、他の順序の組間の１対１の関係を定義していないので、このような暗号を第２のアルゴリズムとして使用することはできない。さもなければ、ブロックの暗号の特性は、第２のアルゴリズムに必要な条件を満たし、第２のアルゴリズムは同じ保護の概念で構成されていたであろう。
【００１８】
ＲＳＡアルゴリズムおよびＥｌ−Ｇａｍａｌアルゴリズムのようないくつかの公開鍵暗号化アルゴリズムは、キーがＺＮ（Ｎは２の累乗以外の一定の値）における置換を定義するための方法を開示している。しかしながら、これらの公開鍵アルゴリズムは３２，７５１のような小さい値のＮに対しては保護されていないので、これらの方法はＣＲＣ−ＭＡＣで使用されるべきではない。キーによって選択される置換は、ＣＲＣ−ＭＡＣに必要なＮの値について、許可されていない当事者から隠されなければならない。
【００１９】
したがって、現在はＣＲＣ−ＭＡＣにおいて大きい数（ｌａｒｇｅ ｎｕｍｂｅｒ）のＮのデータビットを置換することが求められている。上述の最適の場合は、データブロックには３２，７５１ビットが含まれているべきである。既に記載したように、Ｎビットを置換するには、キーによって選択される置換が許可されていない当事者から隠され続けるように、キーが組｛０，１，．．．，Ｎ−１｝＝ＺＮに対する置換を定義する方法が必要である。このような方法に求められることは、Ｎが合成数（ｃｏｍｐｏｓｉｔｅ）であっても、素数（ｐｒｉｍｅ）であっても、いかなるＮの値にも適用できることである。素数は１よりも大きい整数であって、１と自分自身のみを因数とする整数である。合成数は１よりも大きく、素数でない整数である。このような方法は、遠隔通信システムにおけるメッセージの認証およびエラー訂正の他に、種々の幅広い応用に適用できる。
【００２０】
要約
本発明では、Ｎの値が２の累乗でないとき、キーによって選択される置換が許可されていない当事者から隠され続けるように、キーが組ＺＮに対する置換を定義する方法が求められていることに対処した。本発明は、１３以上のすべての整数に応用可能である。Ｎが素数であるか、合成数であるかにしたがって、異なる方法を使用する。
【００２１】
本発明は、Ｎビットのデータブロックを置換するための方法に関し、Ｎビットのデータブロックの各ビットは、複数のＮの指数の中の指数と関係している。Ｎが合成数であり、かつＮが１よりも大きい整数値ｐと１よりも大きい整数値ｑとへ因数分解されるときは、本発明は、幾つかのラウンドを行なうことによって入力値から出力値を求める方法であって、各ラウンドは、第２の部分と整数値ｑによって乗算された第１の部分との合成として表わすことができる入力値を、グループＺｐについて構成されている第１の部分と、グループＺｑについて構成されている第２の部分とへ分割するステップと、第１の２分の１ラウンドのキーと第２の２分の１ラウンドのキーとを構成するステップと、第２の部分および第１の２分の１ラウンドのキーとから、第２の部分と第１の２分の１ラウンドのキーとについて演算する第１の非線形関数の出力である第１の２分の１ラウンドの値を求めるステップと、モジューロｐの加算器を使用して、第１の２分の１ラウンドの値を第１の部分と合成して、第３の部分を生成するステップと、第３の部分と第２の２分の１のラウンドのキーとから、第３の部分と第２の２分の１ラウンドのキーとについて演算する第２の非線形関数の出力である第２の２分の１のラウンドの値を求めるステップと、モジューロｑの加算器を使用して、第２の２分の１ラウンドの値と第２の部分とを合成するステップと、第３の部分を整数値ｑによって乗算して、第２の２分の１ラウンドの値を加算することによって、第２の２分の１ラウンドからの出力値を構成するステップとが含まれている方法に関する。
【００２２】
Ｎが１３よりも大きい素数であるときは、Ｎは２つの合成数ＳとＴとの和として書き表わすことができ、組ＺＮを、Ｓに等しい要素数をもつ組Ａと、Ｔに等しい要素数をもつ組Ｂとの２つの組へ分割することができる。合成数Ｎについての上述の方法は、組Ａにおける置換と、組Ｂにおける置換とを定義するのに適用でき、幾つかのラウンドを実行することによって入力値から出力値を求めることができ、各ラウンドは素数のラウンドと混合のラウンドとから構成されていて、かつ最終のラウンドは素数のラウンドのみである。素数のラウンドでは、ラウンドの入力値が組Ａに含まれているか、または組Ｂに含まれているかを判断し、値が組Ａに含まれているときは、既に記載したようにラウンドのキーによって定義されている組Ａにおける置換を使用して入力値から第１の値を判断し、値が組Ｂに含まれているときは、既に記載したようにラウンドのキーによって定義される組Ｂにおける置換を使用して入力値から第１の値を判断するステップを含み、混合のラウンドでは、全組ＺＮについて、Ａ内の値の約Ｓ／ＮをＡ内の値にマップする特性をもつ簡単な置換へ、第１の値を入力して、ラウンドの出力を生成するステップを含む。
【００２３】
好ましい実施形態の詳細な説明
図１は、ＦＩＰＳ ＰＵＢ４６−２において（１９９３年１２月３０日に）発行されたデータ暗号化標準規格（Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ， ＤＥＳ）によって指定されている従来技術の暗号化計算のブロック図である。６４ビットブロックの入力１００は、最初の置換ステップ１０１にしたがって置換される。最初の置換ステップ１０１の結果は、ブロックＬ０１０２およびＲ０１０３である。
【００２４】
第１のラウンドでは、ブロックＲ０１０３およびブロックのキービットＫ１１０４は、関数ｆ１０５によって演算される。ブロックｆ１０５およびブロックＬ０１０２の出力は、モジューロ２の加算器１０６を使用して合成され、ブロックＲ１１１３を形成する。ブロックＬ１１１２は、ブロックＲ０１０３に等しく設定される。
【００２５】
第２のラウンドでは、ブロックＲ１１１３およびブロックのキービットＫ２１１４は、関数ｆ１１５によって演算される。関数ｆ１１５およびブロックＬ１１１２の出力は、モジューロ２の加算器１１６を使用して合成され、ブロックＲ２１２３を形成する。ブロックＬ２１２２は、ブロックＲ１１１３に等しく設定される。
【００２６】
第１のラウンドおよび第２のラウンドについて記載されている手続きは、１６ラウンドが完了するまで繰返される。ｎ番目のラウンド中に、ブロックのキービットＫｎ１２４およびブロックＲｎは、関数ｆ１２５によって演算され、この演算の出力は、モジューロ２の加算器１２６を使用してブロックＬｎと合成される。最終のラウンドでは、ブロックＲ１６１４２およびブロックＬ１６１４３が逆の最初の置換ステップ１４４へ入力され、出力１４５を形成する。
【００２７】
ＤＥＳ方法では、ブロックのビットを演算し、他のブロックの暗号もブロックのビットについて演算する。したがって、現在の最新技術では、大きさ２ｎ（ｎは全体的にブロック内のビット数）のブロックの暗号化に焦点を当てている。本発明は、任意の大きさの組からの値の暗号化を向上した改良である。
【００２８】
図２は、本発明の１つのラウンドの例示的な実施形態のブロック図であり、キーによる整数置換（ｋｅｙｅｄ ｉｎｔｅｇｅｒ ｐｅｒｍｕｔａｔｉｏｎ， ＫＩＰ）はＺＮ（Ｎは素数ではない）について構成されている。Ｎ＝ｐｑ（整数ｐ＞１およびｑ＞１）とする。入力Ｃｉ２００は２つの部分、すなわち部分Ｌｉ２１０およびＲｉ２１１へ分割され、Ｃｉ＝Ｌｉ−ｑ＋Ｒｉ，Ｌｉ∈ＺｐおよびＲｉ∈Ｚｑとなる。部分Ｒｉ２１１および２分の１のラウンド値Ｋ１ｉ２１２は非線形関数ｆ１２１３によって演算され、２分の１のラウンドの値ｖｉを形成する。２分の１のラウンドの値ｖｉは、モジューロｐの加算器２１５を使用して部分Ｌｉへ加算され、部分Ｌ’ｉ２２０を形成する。部分Ｌ’ｉ２２０および２分の１のラウンドキーＫ２ｉ２２２は、非線形関数ｆ２２２３によって演算され、２分の１のラウンド値ｖ’ｉを形成する。２分の１のラウンド値ｖ’ｉおよび部分Ｒｉ２１１をモジューロｑの加算器２２５を使用して一緒に加算して、部分Ｒ’ｉ２２１を求める。出力部分Ｃｉ＋１２３０は、式Ｃｉ＋１＝Ｌ’ｉ−ｑ＋Ｒ’ｉによって形成される。その代わりに、Ｌ’ｉ２２０およびＲ’ｉ２２１を次の反復ラウンドで使用してもよい。
【００２９】
図２に記載した方法は可逆であり、したがってＣｉはＣｉ＋１から判断することができる。最初に、Ｃｉ＋１は部分Ｌ’ｉおよびＲ’ｉへ分割され、関係式Ｃｉ＋１＝Ｌ’ｉ−ｑ＋Ｒ’ｉを満足させる。Ｒｉを導き出すには、ｖ’ｉ＝ｆ２（Ｌ’ｉ，Ｋ２ｉ）を求めて、Ｒ’ｉ（モジューロｑ）から２分の１のラウンドの値ｖ’ｉを減算する。結果の値はＲｉである。Ｒｉが分かると、ｖｉ＝ｆ１（Ｒｉ，Ｋ１ｉ）を評価し、Ｌ’ｉ（モジューロｐ）から２分の１ラウンドの値ｖｉを減算することによって、Ｌｉを求める。結果の値はＬｉである。Ｃｉの値はＣｉ＝Ｌ’ｉ−ｑ＋Ｒｉとして判断される。
【００３０】
図３は、プロセッサを使用した整数置換デバイスのブロック図である。制御装置３２０はプロセッサ３２２に接続されていて、プロセッサ３２２の動作を指示する命令の組を含んでいる。制御装置３２０はソフトウエアプログラムまたは１組のマイクロコードを含むことができる。プロセッサ３２２は、置換デバイスによって要求される操作を実行するハードウエアである。プロセッサ３２２はマイクロ制御装置、マイクロプロセッサ、または本明細書に記載した機能を実行するように設計されたディジタル信号プロセッサとして構成することができる。プロセッサ３２２にはメモリ素子３２４が接続されていて、メモリ素子３２４は値および命令を記憶するのに使用される。メモリ素子３２４はランダムアクセスメモリか、または本明細書に記載した機能を実行するように設計されている他のメモリデバイスと共に構成されていてもよい。命令および値は、読み出し専用メモリ、ランダムアクセスメモリ、または他のメモリデバイス内に記憶することができる。
【００３１】
図２に概ね示されているように、ＺＮに対するキーによる整数置換を生成する方法は、ｐおよびｑに対する種々の選択に適応するように変更することができる。図４は、キーによる整数置換方法の１ラウンドの実施形態のブロック図であり、なおｐ＝１７８、ｑ＝１８４であり、したがってＮ＝３２７５２である。さらに加えて、数値３２７５２は８９×２３×２４へ因数分解でき、なお８９×２＝１７８、２３×２３＝１８４である。入力Ｃｉ４００は２つの部分、すなわち部分Ｌｉ４１０および部分Ｒｉ４１１へ分割され、したがってＣｉ＝１８４　Ｌｉ＋Ｒｉである。部分Ｌｉ４００はＬｉ＝Ｃｉ ｄｉｖ １８４から求めることができる（なお、Ａ ｄｉｖ Ｂは（Ａ÷Ｂ）の整数部分である）。部分Ｒｉ４１１は、Ｒｉ＝Ｃｉ ｍｏｄ １８４から求めることができる。
【００３２】
部分Ｒｉ４１１および定数α４１３は、モジューロ３５６の乗算器４１４によって一緒に乗算され、乗算結果ｕを生成する。乗算結果ｕおよび２分の１のラウンドキー値Ｋ１ｉ４１２はモジューロ３５６の加算器４１６によって一緒に加算され、合成結果ｗを生成する。整数値３５６＝２＊１７８であることに注意すべきである。ステップ４１９では、合成結果ｗは、関係式ｗ＝ｘ＊ｍ＋ｙによって代入表示値（ｓｕｂｓｔｉｔｕｔｉｏｎ ｉｎｄｉｃａｔｏｒ ｖａｌｕｅ）ｘおよび代入入力値（ｓｕｂｓｔｉｔｕｔｉｏｎ ｉｎｐｕｔ ｖａｌｕｅ）ｙへ分解され、なお代入表示値ｘは組Ｚ２の要素であり、代入入力値ｙは組Ｚｍの要素であり、ｍはｐに等しく設定され、この特定の実施形態ではｐ＝１７８である。代入表示値ｘを使用して、各々がＺ１７８における置換である２つの代入ボックスＳ０４２０およびＳ１４２１の一方を選択する。代入表示値ｘを使用して、代入ボックスＳｘを選択した後で、代入ボックスＳｘによって代入入力値ｙを演算して、２分の１ラウンドの値ｖｉを求める。モジューロ１７８の加算器４２３によって２分の１ラウンドの値ｖｉおよび部分Ｌｉ４１０を演算して、部分Ｌ’ｉ４２４を求める。
【００３３】
モジューロ３６８の加算器４２６によって部分Ｌ’ｉ４２４および定数β４２５を一緒に乗算して、乗算結果ｕ’を生成する。整数値３６８＝２＊１８４であることに注意すべきである。モジューロ３６８の加算器４２９によって乗算値ｕ’および２分の１ラウンドのキーの値Ｋ２ｉ４２８を一緒に加算して、合成結果ｗ’を生成する。ステップ４３０では、関係式ｗ’＝ｘ’＊ｎ＋ｙ’によって合成結果ｗ’を代入表示値ｘ’および代入入力値ｙ’へ分解する（なお、代入表示値ｘ’は組Ｚ２の要素であり、代入入力値ｙ’は組Ｚｎの要素であり、ｎはｑに等しく設定され、この特定の実施形態ではｑ＝１８４である）。代入表示値ｘ’を使用して、各々がＺ１８６に対する置換である２つの代入ボックスＴ０４３３およびＴ１４３４の一方を選択する。代入表示値ｘ’を使用して、代入ボックスＴｘ’を選択した後で、代入ボックスＴｘ’によって代入入力値ｙ’を演算して、２分の１ラウンドの値ｖ’ｉを求める。モジューロ１７８の加算器４３６によって２分の１ラウンドの値ｖ’ｉおよび部分Ｒｉ４１１を演算して、部分Ｒ’ｉ４３７を求める。
【００３４】
キーによる整数置換のために選択された２つの関数ｆ１４８０およびｆ２４９０は、構造において互いに類似している。関数ｆ１４８０は定数によって入力を乗算し、結果のモジューロ２ｐを低減し、値ｕを求める。本発明の上述の実施形態では、２ｐ＝３５６である。関数ｆ２４９０では、定数β＝３６８によって入力を乗算して、結果のモジューロ２ｑ（２ｑ＝３６８）を低減して、値ｕ’を求める。定数αおよびβは、αと３５６とが互いに素であり、βと３６８とが互いに素であるように選択される。例えば、３３と３５６とは互いに素であるので、定数αは整数値３３に等しく設定できる。乗算の後で、２分の１ラウンドのキーをモジューロ３５６に加算して、ｗ＝ｘ＊ｍ＋ｙ（ｘ∈Ｚ２、ｙ∈Ｚｊ、ｊはそれぞれ値ｐまたはｑをもつ）として表わすことができる出力値ｗを求める。ｘの値を使用して、２つの代入ボックスの一方を選択する。関数ｆ１４８０では、これらの２つの代入ボックスはＳ０、Ｓ１で示され、各代入ボックスＺ１７８における置換である。関数ｆ２４９０では、これらの２つの代入ボックスはＴ０、Ｔ１で示され、各代入ボックスはＺ１８４における置換である。ｆ１の出力はｖｉ＝Ｓｘ（ｙ）であり、ｆ２の出力はｖ’ｉ＝Ｔｘ（ｙ）の出力である。
【００３５】
２分の１ラウンドのキー値Ｋ１ｉおよびＫ２ｉの判断
本発明の実施形態における２分の１ラウンドのキー値はＳＯＢＥＲＩＩのストリーム暗号によって生成でき、なおＳＯＢＥＲＩＩのストリーム暗号は、１９９７年９月２２日に出願された米国特許出願第０８／９３４，５８２号（“ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＦＯＲ ＧＥＮＥＲＡＴＩＮＧ ＥＮＣＲＹＰＴＩＯＮ ＳＴＲＥＡＭ ＣＩＰＥＲＳ”）、１９９７年１０月２４日に出願された米国特許出願第０８／９５７，５７１号（“ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＦＯＲ ＧＥＮＥＲＡＴＩＮＧ ＥＮＣＲＹＰＴＩＯＮ ＳＴＲＥＡＭ ＣＩＰＥＲＳ”）、１９９８年８月２８日に出願された米国特許出願第０９／１４３／４４１号（“ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＦＯＲ ＧＥＮＥＲＡＴＩＮＧ ＥＮＣＲＹＰＴＩＯＮ ＳＴＲＥＡＭ ＣＩＰＥＲＳ”）、および１９９９年９月８日に出願された米国特許出願第０９／２４６，３６６号（“ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＦＯＲ ＧＥＮＥＲＡＴＩＮＧ ＥＮＣＲＹＰＴＩＯＮ ＳＴＲＥＡＭ ＣＩＰＥＲＳ”）に記載されている。上述の特許出願は本発明の譲受人に譲渡されており、本明細書では別途記載しない。しかしながら、ストリーム暗号が、均等に分配されているバイトを生成するときは、このようなストリーム暗号を使用して、２分の１ラウンドのキーの値を生成できることに注意すべきである。このようなストリーム暗号がｓ０，ｓ１，．．．，ｓｔ，．．．で表わされる出力バイトを生成するとき、２つの連続しているバイトの整数値ｚｔ＝２５６ｓ２ｔ＋ｓ２ｔ＋１はＺ６５５３６において均等に分配されることに注意すべきである。本発明の例示的な実施形態では、ＳＯＢＥＲＩＩは、セッションキーおよび恐らくは若干の追加のデータを使用して初期設定され、ｓ０，ｓ１，．．．，ｓｔ，．．．で表わされる十分なバイトの出力を生成する。２分の１のラウンドのキーは、均等に分配されるように設計されている。均等に分配された２分の１のラウンドのキーを生成する１つの方法では、ｚｔが６５５０４未満であるときのみ、２つの連続している整数値バイトｚｔ＝２５６ｓ２ｔ＋ｓ２ｔ＋１を使用する。６５５０４は整数値３５６（２ｐ＝３５６）および３６８（２ｑ＝３６８）によって因数分解できるので、低減されたモジューロ３５６またはモジューロ３６８で
ある０ないし６５５０３の均等に分配された数ｚｔも、それぞれＺ３５６およびＺ３６８において均等に分配されることになる。
【００３６】
ｚｔの値を、ｔ＝０から計算する。ｚｔが６５５０４以上であるときは、ｔはインクリメントされ、ｚｔの値はｔの新しい値において計算される。このプロセスは、ｚｔの値が６５５０４未満であることが分かるまで繰返される。次に６５５０４未満のｚｔの値は、Ｋ１１を求めるための低減されたモジューロ３５６である。Ｋ１ｉを判断した後で、ｔの値はインクリメントされ、ｔの新しい値においてｚｔの値を計算する。ｚｔが６５５０４以上であるときは、ｔはインクリメントされ、ｔの新しい値においてｚｔの値を計算する。このプロセスは、ｚｔの新しい値が６５５０４未満であることが分かるまで繰返される。６５５０４未満のこのｚｔの値は、Ｋ２１を求めるための低減されたモジューロ３６８である。Ｋ１１をおよびＫ２１を判断すると、ｔはインクリメントされ、ｔから０へ設定しなくても、プロセスはこの方法の始めに戻る。全ての２分の１のラウンドキーが求められるまで、この方法を繰返して、Ｋ１２、Ｋ２２、Ｋ１３、Ｋ２３などを判断する。図５は、この反復プロセスを詳しく示したフローチャートである。
【００３７】
ステップ５００では、指数（ｉｎｄｅｘ）ｔは０に等しく設定され、ラウンド数ｉは１に設定される。ステップ５１０では、中間値ｚｔは関係式ｚｔ＝２５６ｓ２ｔ＋ｓ２ｔ＋１によって判断される。ｚｔが６５５０４未満であるときは、ステップ５２０へ進む。ｚｔが６５５０４以上であるときは、ステップ５３０へ進む。ステップ５２０では、Ｋ１ｉはｚｔ ｍｏｄ ３５６に等しく設定され、指数ｔはインクリメントされ、プロセスのフローチャートはステップ５４０へ進む。ステップ５３０では、指数ｔはインクリメントされ、プロセスのフローチャートはステッ５１０へ進む。ステップ５４０では、値ｚｔを関係式ｚｔ＝２５６ｓ２ｔ＋ｓ２ｔ＋１（指数ｔはステップ５２０においてインクリメントされている）によって判断する。ｚｔが６５５０４未満であるときは、ステップ５５０へ進み、ｚｔが６５５０４以上であるときは、ステップ５６０へ進む。ステップ５５０では、、Ｋ２ｉはｚｔ ｍｏｄ ３６８に等しく設定され、指数ｔおよびｉはインクリメントされる。ｉ＜ｒであるときは、ステップ５１０へ戻る。ステップ５６０では、指数ｔはインクリメントされ、プログラムのフローチャートはステップ５４０へ進む。
【００３８】
本発明の別の実施形態では、図２に概ね示したキーによる整数置換はＺ３２７５１についてｐ＝３３およびｑ＝１２１３として実行される。（３２７５１＝３３×１２１３であることに注意すべきである。）図６は、ｐ＝３３およびｑ＝１２１３を使用して、この方法の１ラウンドを示すブロック図である。入力Ｃｉ６００はＣｉ＝Ｌｉ＊１２１３＋Ｒｉとなるように、２つの部分、部分Ｌｉ６０１および部分Ｒｉ６０２へ分割される。部分Ｌｉ６０１は関係式Ｌｉ＝Ｃｉ ｄｉｖ （１２１３）によって判断でき、部分Ｒｉは関係式Ｒｉ＝Ｃｉ ｍｏｄ （１２１３）によって判断できる。部分Ｒｉ６０２および定数α６０３をモジューロ２７３の乗算器６０４によって一緒に乗算され、乗算結果ｕが求められる。定数α６０３および数２７３（２７３＝１９６８３）が互いに素であるように組Ｚ１９６８３から選択する。ステップ６０９では、ｕを関係式ｕ＝２７２ｕ１＋２７ｕ２＋ｕ３によって因数分解して、項ｕ１、ｕ２、ｕ３を求める。
【００３９】
モジューロ２７の加算器６１３を使用して、項ｕ１およびサブキーの値Ｋ１Ａｉ６１０を一緒に加算し、代入入力値ｇ１を求める。モジューロ２７の加算器６１４を使用して、項ｕ２およびサブキーの値Ｋ１Ｂｉ６１１を一緒に加算し、代入入力値ｇ２を求める。モジューロ２７の加算器６１５を使用して、項ｕ３およびサブキーの値Ｋ１Ｃｉ６１２を一緒に加算し、代入入力値ｇ３を求める。本明細書に記載した方法には、ｐおよびｑ、またはｕの適切な選択値に依存して、多数の可能な実行形態があることに注意すべきである。例えば、ｕが、ステップ６０９において使用されている３つの項ではなく、４以上の項（例えば、ｕ＝２７３ｕ１＋２７２ｕ２＋２７ｕ３＋ｕ４）へ因数分解されるときは、加算器の数は増加することになる。加算器の数が増加すると、適切な数のサブキーの値も必要となる。サブキーの値Ｋ１Ａｉ６１０、Ｋ１Ｂｉ６１１、およびＫ１Ｃｉ６１２は、組Ｚ２７の要素から選択され、別途記載する方法で判断される。例えば、ｕが４以上の項に因数分解される場合は、過多に実験をしなくても、より多くのサブキー値を生成し、本発明の他の実施形態を満足させるような方法にすることができる。
【００４０】
代入入力値ｇ１を代入ボックスＳ１６１９によって演算して、代入された値ｈ１を求める。代入入力値ｇ２を代入ボックスＳ２６２０によって演算して、代入された値ｈ２を求める。代入入力値ｇ３を代入ボックスＳ３６２０によって演算して、代入された値ｈ３を求める。代入された値ｈ１、代入された値ｈ２、および代入された値ｈ３をモジューロ２７の加算器６２５によって一緒に加算して、２分の１のラウンド値ｖｉを判断する。２分の１のラウンド値ｖｉおよび部分Ｌｉ６０１をモジューロ２７の加算器６２７を使用して一緒に加算して、部分Ｌ’ｉ６２８を求める。
【００４１】
部分Ｌ’ｉ６２８および定数β６５０をモジューロ１２１３の乗算器６５５によって乗算して、乗算結果をｕ’ｉを求める。定数β６５０は、組Ｚ１２１３のゼロ以外の要素から選択される。乗算結果ｕ’ｉおよび２分の１ラウンドのキー値Ｋ２ｉ６５３をモジューロ１２１３の加算器６５６を使用して一緒に加算して、代入入力値ｇ’を求める。代入入力値ｇ’を代入ボックスＴ６５７へ送って、２分の１ラウンドの値ｖ’ｉを求める。２分の１ラウンドの値ｖ’ｉおよび部分Ｒｉ６０２をモジューロ１２１３加算器６５８を使用して一緒に加算し、部分Ｒ’ｉ６５９を求める。部分Ｌ’ｉ６２８および部分Ｒ’ｉ６５９は、次の反復ラウンドにおいて使用される。代わりのやり方では、部分Ｌ’ｉ６２８を数値＝１２１３によって乗算し、部分Ｒ’ｉ６５９へ加算し、部分Ｃｉ＋１６６０を形成する。
【００４２】
２分の１ラウンドのキー値Ｋ１ｉ＝｛Ｋ１Ａｉ，Ｋ１Ｂｉ，Ｋ１Ｃｉ｝およびＫ２ｉの判断
本発明のこの実施形態において２分の１ラウンドのキーの値はＳＯＢＥＲＩＩのストリーム暗号によって生成される。しかしながら、ストリーム暗号が均等に分配されたバイトを生成するときは、ストリーム暗号を使用して、２分の１ラウンドのキーの値を生成することができる。このようなストリーム暗号がｓ０，ｓ１，．．．，ｓｔ，．．．で表わされる出力バイトを生成するときは、２つの連続しているバイトの整数値、ｚｔ＝２５６ｓ２ｔ＋ｓ２ｔ＋１はＺ６５５３６について均等に分配されることになることに注意すべきである。
【００４３】
サブキーの値の組Ｋ１ｉ＝｛Ｋ１Ａｉ，Ｋ１Ｂｉ，Ｋ１Ｃｉ｝は、数が０ないし５９０４８（５９０４９＝３×２７３）の間で均等に分配され、かつ低減されたモジューロ２７３であるときは、数はＺ２７×Ｚ２７×Ｚ２７について均等に分配されているという解析（ｏｂｓｅｒｖａｔｉｏｎ）によって判断される。２分の１ラウンドのキー値Ｋ２ｉは、数が０ないし６５５０１（６５５０２＝５４×１２１３）の間で均等に分配され、かつ低減されたモジューロ１２１３であるときは、数はＺ１２１３についても均等に分配されているという解析によって判断される。これらの解析を使用すると、Ｋ１ｉ＝｛Ｋ１Ａｉ，Ｋ１Ｂｉ，Ｋ１Ｃｉ｝およびＫ２ｉの値（１≦ｉ≦ｒ）を判断するための例示的な方法には、図７に詳しく示したステップが含まれる。
【００４４】
ステップ７００では、指数ｔは０に等しく設定され、ラウンド数ｉは１に等しく設定される。ステップ７１０では、中間値ｚｔは、関係式ｚｔ＝２５６ｓ２ｔ＋ｓ２ｔ＋１によって判断される。ｚｔが５９０４９であるときは、ステップ７２０へ進む。ｚｔが５９０４９以上であるときは、ステップ７３０へ進む。ステップ７３０では、指数ｔはインクリメントされ、プロセスのフローチャートはステップ７１０へ進む。ステップ７２０では、Ｋ１ｉがｚｔ ｍｏｄ １９６８３に等しく設定され、指数ｔはインクリメントされる。ステップ７２５では、Ｋ１ｉ＝２７２Ｋ１Ａｉ＋２７Ｋ１Ｂｉ＋Ｋ１Ｃｉとなるように、Ｋ１Ａｉ，Ｋ１Ｂｉ，Ｋ１Ｃｉの値を判断する。ステップ７２５の次は、プログラムのフローチャートはステップ７４０へ進む。ステップ７４０では、値ｚｔは関係式ｚｔ＝２５６ｓ２ｔ＋ｓ２ｔ＋１（指数ｔはステップ７２０においてインクリメントされている）によって判断される。ｚｔが６５５０２未満であるときは、ステップ７５０へ進み、ｚｔが６５５０２以上であるときは、ステップ７６０へ進む。ステップ７５０では、Ｋ２ｉがｚｔ ｍｏｄ １２１３に等しく設定され、指数ｔおよびｉはインクリメントされる。ｉ＜ｒであるときは、ステップ７１０へ戻る。ステップ７６０では、指数ｔはインクリメントされ、プログラムのフローチャートはステップ７４０へ進む。
【００４５】
上述の方法を使用するとき、サブキーＫ１Ａｉ，Ｋ１Ｂｉ，Ｋ１Ｃｉ（１≦ｉ≦ｒ）の各々は、Ｚ２７について均等に分配され、第２の２分の１のラウンドのキーＫ２ｉは（１≦ｉ≦ｒ）、Ｚ１２１３について均等に分配される。代入ボックスは、非線形性およびランダム性のような、十分な暗号特性をもつように選択される。２分の１のラウンドキーが均等に分配されていないときは、代入ボックスへの入力は均等に分配されず、独立する。
【００４６】
本明細書に記載したキーによる整数置換方法は、メッセージ認証コードで使用することを意図されているが、１組の整数のキーによる置換が要求される場合に使用してもよい。例えば、本明細書に記載した本発明の実施形態を使用して、ＤＥＳが組｛０，１，．．．，２６４−１｝内の整数を組｛０，１，．．．，２６４−１｝内の他の整数へ暗号化するやり方と類似したやり方で、組｛０，１，．．．，Ｎ−１｝内の整数を組｛０，１，．．．，Ｎ−１｝内の他の整数へ暗号化することができる。
【００４７】
本明細書に記載したキーによる整数置換の暗号化プロセスと暗号化プロセスとは、各ラウンド内の２つの２分の１ラウンドの関数の順序が逆にされていること、出力ｖｉがＬｉから減算されたモジューロｐであること、および出力ｖ’ｉがＲｉからの減算されたモジューロｑであることを除いて暗号プロセスと同じである。
【００４８】
図８は、本発明の別の例示的な実施形態のブロック図であり、キーによる整数の置換はＺＮ（Ｎは素数）について構成されている。Ｎ＝Ｓ＋Ｔとする。Ｎ≧１３の各値には、Ｎ＝Ｓ＋Ｔとなるような２つの構成要素ＳおよびＴが存在することに注意すべきである。したがって、ステップ８００では、Ｎの指数のグループは、Ｓの指数から構成されているセクションＡ８０１と、Ｔの指数から構成されているセクションＢ８０２とへ分割される。セクションＡ８０１の指数は｛ａ０，ａ１，．．．，ａＳ−１｝へ再び分類され、セクションＢ８０２の指数は｛ｂ０，ｂ１，．．．，ｂＴ−１｝へ再び分類される。セクションＡ８０１の指数は、キーによる整数置換ＫＩＰＳ８１０にしたがって置換される。キーによる整数置換ＫＩＰＳ８１０は、既に記載した本発明の実施形態にしたがって実行することができる。セクションＢ８０２の指数は、キーによる整数置換ＫＩＰＴ８１１にしたがって置換される。キーによる整数置換ＫＩＰＴ８１１は、既に記載した本発明の実施形態にしたがって実行することができる。
【００４９】
したがって、ＫＩＰＮの素数のラウンドは次のように定義することができる：
ｘ∈｛ａ０，ａ１，．．．，ａＳ−１｝であるときは、
ＫＩＰＡ，Ｂ（ｘ）＝ＫＩＰＳ（ｘ）、または、
ｘ∈｛ｂ０，ｂ１，．．．，ｂＴ−１｝であるときは、
ＫＩＰＴ（ｘ）。
【００５０】
ステップ８２０では、ＫＩＰＡ，Ｂ（ｘ）の出力に“混合（ｍｉｘｉｎｇ）”演算、例えばアフィン演算ＡｆｆＳ（ｘ）＝Ｕ＊ｘ＋Ｖ（ｍｏｄ Ｎ）（１≦Ｕ≦Ｎ−１、ＵおよびＶの値は保護キー（ｓｅｃｕｒｅ ｋｅｙ）に依存する）を行なう。数学的に、演算子Ｂ：Ｃ　ＤはＢｒ＝Ａｒ＋ｂ（Ｃ，Ｄ⊆Ｒ、ｂはＤの固定要素、ｒはＣの要素、ＡはＣをＤへマップする線形演算子）によって定義されるとき、Ｂはアフィン演算子である。
【００５１】
図８の一般的な方法では、素数の要素をもつ組を、各組が素数の要素以外から構成されている２以上の組へ分割し、次に図２および本発明の他の種々の実施形態に記載したキーによる整数置換を合成数の組について行なう。１つの組の要素の置換は、この１つの組によって定義される出力になるので、各ラウンドの後で１つの組の要素を別の組に挿入する混合演算を行なう。
【００５２】
図８に概ね記載されているように、本発明の１つの実施形態では、Ｎ＝Ｓ＋Ｔとする（Ｎは素数であり、ＳおよびＴは合成数である）。Ａ＝｛０，１，Ｓ−１｝およびＢ＝｛Ｓ，．．．，Ｎ−１｝と定義すると、組Ａ内の要素数は｜Ａ｜＝Ｓであり、組Ｂ内の要素数は｜Ｂ｜＝Ｔである。素数のラウンドは、０≦ｘ≦Ｓ−１であるときは、ＫＩＰＡ，Ｂ（ｘ）＝ＫＩＰＳ（ｘ）であり、Ｓ≦ｘ≦Ｎ−１であるときは、ＫＩＰＡ，Ｂ（ｘ）＝Ｓ＋ＫＩＰＴ（ｘ―Ｓ）であると定めることができる。
【００５３】
図８に概ね記載されているように、本発明の別の実施形態では、Ｎは素数であり、Ｎ＝２Ｔ＋１とする（ＴおよびＴ＋１は合成数である）。Ａ＝｛０，２，４，．．．，２Ｔ｝＝｛２ｙ：ｙ∈ＺＴ＋１｝およびＢ＝｛１，３，５，．．．，２Ｔ−１｝＝｛２ｙ＋１：ｙ∈ＺＴ｝と定義する。したがって、組Ａは偶数の値を含み、組Ｂは奇数の値を含んでいる。したがって素数のラウンドはｘ＝２ｙであるときは、ＫＩＰＡ，Ｂ（ｘ）＝２ＫＩＰＴ＋１（ｙ）であり、ｘ＝２ｙ＋１であるときは、ＫＩＰＡ，Ｂ（ｘ）＝１＋ＫＩＰＴ（ｙ））であると定義することができる。
【００５４】
図８に記載されているように、本発明のさらに別の実施形態では、ステップ８２０のアフィンマッピング演算において使用されているように、固定定数を使用することができる。Ｐｒｏｂ（ＡｆｆＵ，Ｖ（ｘ） ｉｎ Ａ：× ｉｎ Ａ）がほぼ｜Ａ｜／Ｎとなるように、ＵおよびＶの値を選択する。ＵおよびＶの値は、組ＡおよびＢ内の要素の区分に依存する。組ＡおよびＢは、｜Ａ｜〜｜Ｂ｜〜（Ｎ／２）になるように選択される。置換Ｙ３＝ＫＩＰＮ（Ｘ０）は、４つの素数のラウンドおよび３つのアフィンラウンドをもち、置換は次に示すものによって定義される：
Ｙ０＝ＫＩＰＡ，Ｂ（Ｘ０），
Ｘ１＝ＡｆｆＵ，Ｖ（Ｙ０），
Ｙ１＝ＫＩＰＡ，Ｂ（Ｘ１），
Ｘ２＝ＡｆｆＵ，Ｖ（Ｙ１），
Ｙ２＝ＫＩＰＡ，Ｂ（Ｘ２），
Ｘ３＝ＡｆｆＵ，Ｖ（Ｙ２），
Ｙ３＝ＫＩＰＡ，Ｂ（Ｘ３）。
【００５５】
ＫＩＰＡおよびＫＩＰＢは、ＫＩＰＮのキーの長さに等しいキーの長さで保護されると仮定する。４つの素数のラウンド内のＫＩＰＡおよびＫＩＰＢに必要な８つの２分の１ラウンドのキーを求めるのに、ＫＩＰＮはＳＯＢＥＲＩＩのようなキースケジュールをもたなければならない。この構成は、保護されている置換になると考えられている。
【００５６】
大きい数の素数のラウンドまたはキーに依存するアフィンラウンド、あるいはこの両者を使用するために、他の実施形態を構成してもよい。使用される素数のラウンドの数が増加すると、素数のラウンドの関数を、より弱いキーによる整数置換から構成して、速度を増すことができる。
【００５７】
ＺＮになるキーによる整数置換を構成する方法を記載してきた。発明の詳細な記述（ｄｅｓｃｒｉｐｔｉｏｎ）は、当業者が本発明を実行または使用できるようにするために与えられている。これらの実施形態に対する種々の変形は、当業者には容易に明らかであり、本明細書において定義されている一般的な原理は、発明的な能力（ｉｎｖｅｎｔｉｖｅ ｆａｃｕｌｔｙ）を使用せずに他の実施形態に応用することができる。したがって、本発明は、本明細書に開示した実施形態に制限されることを意図されるのではなく、本明細書に記載した原理および新規な特徴と一致する最も幅広い技術的範囲にしたがうことを意図されている。
【図面の簡単な説明】
【図１】
ＤＥＳという名前の従来技術の暗号化計算のフローチャート。
【図２】
モジューロｐの加算器とモジューロｑの加算器とを使用する暗号化計算の本発明の実施形態のブロック図。
【図３】
プロセッサを使用する整数置換デバイスのブロック図。
【図４】
Ｚ３２７５２における暗号化計算のブロック図。
【図５】
図４の暗号化計算において実行されているように、２分の１ラウンドのキーＫ１ｉおよびＫ２ｉの偏差を示すフローチャート。
【図６】
Ｚ３２７５１に対する別の暗号化計算のブロック図。
【図７】
図６の暗号化計算において実行されている２分の１ラウンドのキーＫ１ｉおよびＫ２ｉの偏差を示すフローチャート。
【図８】
ＺＮ（Ｎは素数）に対して実行される本発明の実施形態の暗号化計算のブロック図。
【図１】
2004511812.tif 000005
【図２】
2004511812.tif 000006
【図３】
2004511812.tif 000007
【図４】
2004511812.tif 000008
【図５】
2004511812.tif 000009
【図６】
2004511812.tif 000010
【図７】
2004511812.tif 000011
【図８】
2004511812.tif 000012
【国際公開パンフレット】
2004511812.tif 000013
2004511812.tif 000014
2004511812.tif 000015
2004511812.tif 000016
2004511812.tif 000017
2004511812.tif 000018
2004511812.tif 000019
2004511812.tif 000020
2004511812.tif 000021
2004511812.tif 000022
2004511812.tif 000023
2004511812.tif 000024
2004511812.tif 000025
2004511812.tif 000026
2004511812.tif 000027
2004511812.tif 000028
2004511812.tif 000029
2004511812.tif 000030
2004511812.tif 000031
2004511812.tif 000032
2004511812.tif 000033
2004511812.tif 000034
2004511812.tif 000035
2004511812.tif 000036
2004511812.tif 000037
2004511812.tif 000038
2004511812.tif 000039
2004511812.tif 000040
2004511812.tif 000041
2004511812.tif 000042
2004511812.tif 000043
2004511812.tif 000044
2004511812.tif 000045
2004511812.tif 000046
2004511812.tif 000047
【国際公開パンフレット（コレクトバージョン）】
2004511812.tif 000048
【国際調査報告】
2004511812.tif 000049
2004511812.tif 000050