(57)【要約】      （修正有）【課題】最適な機密性を提供し、大規模でない計算ソースのみを必要とする比較的単純な関数を用いて実施できるデータ暗号法を提供する。【解決手段】計算機は、入力情報ｘを関数Ｆでコード化した情報Ｆ（ｘ）を出力するキーを用いて処理する。関数Ｆは非相関モジュールＭKを使用し、Ｆ（ｘ）=［Ｆ'(ＭK)］（ｘ）である（ここで、Ｋはランダムキーであり、Ｆ'は暗号関数である）。一般に、非相関モジュールは、キーを含む関数ＭKでメッセージｘを変換する役目を行い、ランダムな変数のキーを有する任意のｔ個の異なるメッセージから得た分散ＭK（ｘ1），...，ＭK（ｘt）が均一またはほぼ均一な分散を有するようにする。【選択図】図１
2009116348.tif 000002
【特許請求の範囲】
【請求項１】
計算機によって使用可能な記録媒体に格納されたデータの暗号方法であって、計算機が入力情報ｘを関数Ｆでコード化した情報Ｆ（ｘ）を出力するキーを用いて処理する方法において、関数Ｆは少なくとも２に等しいランクの非相関モジュールＭKを使用し、Ｆ（ｘ）=［Ｆ'（ＭK）］（ｘ）である（ここで、Ｋはランダムキーであり、Ｆ'はコード化関数である）ことを特徴とするデータの暗号方法。
【請求項２】
前記入力情報ｘを所定の長さの要素ｘ0に分割することを特徴とする請求項１に記載の暗号方法。
【請求項３】
前記関数Ｆが、Ｆ（ｘ）=Ｆ'（ＭK（ｘ））の形式であることを特徴とする請求項１および２のいづれか１項に記載の暗号方法。
【請求項４】
前記コード化関数Ｆ'が、以下に示すよう２つの関数Ｆ''およびＧ''に分割されることを特徴とする請求項１および２のいづれか１項に記載の暗号方法：
Ｆ（ｘ）=Ｆ''（ＭK（Ｇ''（ｘ）））
【請求項５】
前記非相関モジュールＭKが、逆変換可能であることを特徴とする請求項１から４のいづれか１項に記載の暗号方法。
【請求項６】
前記非相関モジュールが、ＭK（ｘ）=ａｘ＋ｂ（ここで、Ｋ=（ａ，ｂ）、ａ≠０）であることを特徴とする請求項５に記載の暗号方法。
【請求項７】
前記非相関モジュールが、ＭK（ｘ）=ａ/（ｘ＋ｂ）＋ｃ（ここで、Ｋ=（ａ，ｂ，ｃ）、ａ≠０）であることを特徴とする請求項５に記載の暗号方法。
【請求項８】
前記非相関モジュールＭKが、逆変換不能であることを特徴とする請求項１から４のいづれか１項に記載の暗号方法。
【請求項９】
前記関数Ｆが、関数Ｆiをｎ回の反復処理するファイステル関数であることを特徴とする請求項５に記載の暗号方法。
【請求項１０】
前記各反復において、Ｆi（ｘ）=Ｆ'i（ＭK（ｘ））であることを特徴とする請求項９に記載の暗号方法。
【請求項１１】
前記各反復において、Ｆi（ｘ）=Ｆ''i（ＭK（Ｇ''i（ｘ）））であることを特徴とする請求項９に記載の暗号方法。
【請求項１２】
ＭK（ｘ）=ｋ1＋ｋ2ｘ＋ｋ3ｘ2＋...＋ｋtｘt-1（ここで、Ｋ=（ｋ1，ｋ2，ｋ3，...，ｋt））であることを特徴とする請求項１１に記載の暗号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は処理装置で利用可能な媒体に記録したデータを非相関化する方法に関する。
【背景技術】
【０００２】
知られているデータの暗号化方法または暗号方法は多くある。これらはデータをコード化する役目をし、キーを所有する認定された受信者のみデータを読むことができる。暗号化の重要性は情報通信網と同時に高まっており、法律制定に伴いその利用が普及することは予想できる。
【０００３】
いくつかの暗号化方法により、無条件機密保護を提供することができるが、処理に手間がかかる技術手段を必要とするため、通信が遅くなったり、キーの交換管理の費用が高くなったりし、実際に使用できないものさえある。
【０００４】
例えば、暗号化されていないメッセージのフローを暗号化するために、バーナム暗号化方法（Vernam encryption method）では同じ長さのキーのフローを必要とし、送信者と受信者間の同期を達成するのが難しくなる。
【０００５】
無条件機密保護の条件は、1949年、シャノン（Shannon）によって形式化された。彼は情報理論を基に、無条件機密保護には、キーが、劣化することなく暗号化できるメッセージ全体の大きさと少なくとも同等でなくてはならないことを示した。
【０００６】
暗号化操作は、処理装置で利用可能な媒体に記録され、よく送信されるデータの保護を確実にするため実施する。一連の機密にすべきメッセージの暗号化には、少数のメッセージに対して独立にこれらの操作を実施しなければならない。
【０００７】
現在用いられる主な暗号化操作は米国政府が採用するデータ暗号化規格（DES: digital data encryption standard）である。この操作はいわゆるファイステル（Feistel）スキームに続く単純な関数の（16段の）反復に基づく。反復数が多いのは、暗号化されたメッセージ間の相関を弱めるためである。
【０００８】
DESについては多くの文献、特にダグラス  スティンソン（Douglas STINSON）による「暗号化、理論と実践」（"Encryption, Theory and Practice"（International Thompson Publishing））という題名の出版物で説明されている。
【非特許文献１】Douglas STINSON  "Encryption, Theory and Practice"（International Thompson Publishing）
【０００９】
暗号化の信頼性を改善し、徹底的な調査から保護するため、キーの長さを長くし、オーダー１の非相関の導入が提案されている。これは下記２つの文献の著者達が提案してきたことである。
【非特許文献２】Advances in Cryptology-CRYPTO 96, 16th Annual International Cryptology Conference, Santa Barbara, August 18-22 1996, Proceedings no. Conf. 16, August 18th 1996, Koblitz N (ED), pages 252-267 by KILIAN J. et al.
【非特許文献３】Advances in Cryptology-ASIACRYPT, Fujiyoshida, November 11-14 1991, no. Conf. 1, November 11th 1991, Hideki Imai; Rivest R L; Tsutomu Matsumoto, pages 210-224 by EVEM S. et al.
【００１０】
しかし、この方法では近年開発された線形および微分暗号解読技術で可能になった攻撃から保護するのに十分ではない。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、最適な機密性を提供し、大規模でない計算ソースのみを必要とする比較的単純な関数を用いて実施できるデータ暗号法を提供することにある。
【課題を解決するための手段】
【００１２】
この目的のため、本発明は計算機によって使用可能な媒体に格納されたデータの暗号方法に関し、この方法では、計算機が入力情報ｘを関数Ｆでコード化した情報Ｆ（ｘ）を出力するキーを用いて処理する。
【００１３】
本発明において、関数Ｆは少なくとも２に等しいランクの非相関モジュールＭKを使用し、Ｆ（ｘ）=［Ｆ'（ＭK）］（ｘ）である（ここで、Ｋはランダムキーであり、Ｆ'は暗号関数である）。
一般に、非相関モジュールは、キーを含む関数ＭKでメッセージｘを変換する役目を行い、ランダムな変数のキーを有する任意のｔ個の異なるメッセージから得た分散ＭK（ｘ1），...，ＭK（ｘt）が均一またはほぼ均一な分散を有するようにする。
【００１４】
こうした非相関モジュールは、入力情報ｘに対して所定の長さのデータｘ0を出力する情報分割装置（information dividing device）の後、データ暗号化装置内で使用できる。
本発明は、関数Ｆでコード化したメッセージｃ1，...，ｃtのｔ個のブロックがその関数についてのいかなる統計的情報も与えないように実施できる。
【００１５】
それぞれが個々の利点を有する種々の実施例において、本発明は任意の技術的に実行可能な組み合わせによる下記特性を有する:
-入力情報ｘは所定の長さの要素ｘ0に分割され、
-関数Ｆは、Ｆ（ｘ）=Ｆ'（ＭK（ｘ））の形式であり、
-コード化関数Ｆ'は２つの関数Ｆ''およびＧ''に分割され、
Ｆ（ｘ）=Ｆ''（ＭK（Ｇ''（ｘ）））、
-非相関モジュールＭKは逆変換可能であり、
-非相関モジュールは、ＭK（ｘ）=ａｘ＋ｂであり（ここで、Ｋ=（ａ，ｂ）、ａ≠０）、
-非相関モジュールは、ＭK（ｘ）=ａ/（ｘ＋ｂ）＋ｃであり（ここで、Ｋ=（ａ，ｂ，ｃ）、ａ≠０）、
-関数Ｆは、関数Ｆiをｎ回の反復それぞれに適用するファイステル関数であり、
-非相関モジュールＭKは逆変換可能であり、
-各反復で、Ｆi（ｘ）=Ｆ'i（ＭK（ｘ））であり、
-各反復で、Ｆi（ｘ）=Ｆ''i（ＭK（Ｇ''i（ｘ）））であり、
-ＭK（ｘ）=ｋ1＋ｋ2ｘ＋ｋ3ｘ2＋...＋ｋtｘt-1
（ここで、Ｋ=ｋ1，ｋ2，ｋ3，...，ｋt）である。
【発明を実施するための最良の形態】
【００１６】
以下、本発明を図および実施例を用いてより詳細に説明する。
図１は、８段の反復のファイステルスキームに適用した本発明を示す。
【００１７】
記録データを暗号化する本発明の方法は、Ｆ（ｘ）=［Ｆ'（ＭK）］（ｘ）（ここで、Ｋはランダムなキー、Ｆ'はコード化関数である）である非相関モジュールＭKを用いた秘密キーを実施するのが有利である。
【００１８】
コード化関数Ｆ'は２つの関数Ｆ''およびＧ''に分割され、Ｆ（ｘ）=Ｆ''（ＭK（Ｇ''（ｘ）））であるのが有利である。
【００１９】
このような非相関モジュールは、逆変換可能な関数Ｆおよび任意の関数Ｆに使用できる。
【００２０】
関数Ｆが逆変換可能である時、暗号方法は暗号化方法である。つまり、キーの保有者が入力情報を再生できる。関数Ｆが逆変換できない場合、暗号方法でデータを認証できる。
【００２１】
パラメータ値ｔ=２で、関数ＭKは:
ＭK（ｘ）=ａｘ＋ｂ
であるのが有利である（ここで、Ｋ=（ａ，ｂ）、ａ≠０、記号＋はメッセージスペースの翻訳を表す）。
【００２２】
非相関はオーダー２で完全になる。逆変換操作は:
（ＭK）-1（ｙ）=ａ-1ｙ-ａ-1ｂ
【００２３】
パラメータ値ｔ=３の場合の他の実施例で、関数ＭKは:
ＭK（ｘ）=ａ/（ｘ＋ｂ）＋ｃ
であるのが有利である。（ここで、Ｋ=（ａ，ｂ，ｃ）、ａ≠０。この演算では、１/０=０とする。）逆変換操作は下記のとおり:
（ＭK）-1（ｙ）=ａ/（ｙ-ｃ）-ｂ
【００２４】
非相関モジュールＭKの使用は逆変換不可能な関数の場合でも同様に有利である。
【００２５】
加算および乗算を定義するメッセージのような代数構造を用いる。例えば、有限な集合における演算または素数の切り捨てモジュロ演算を用いる。
【００２６】
全てのパラメータ値ｔに、ＭK（ｘ）=ｋ1＋ｋ2ｘ＋ｋ3ｘ2＋...＋ｋtｘt-1ここで、Ｋ=（ｋ1，ｋ2，ｋ3，...，ｋt）の形式の非相関関数を提案できる。
【００２７】
ファイステルl暗号化のスキームを図１に示す。
64ビットの平文ｘのブロックに対して、ｘ=Ｌ0Ｒ0を設定する（ここで、Ｌ0は数列ｘの初めの32ビットを、Ｒ0は残りの32ビットを有する）。
【００２８】
等しい関数ｆの４段の反復をｘに適用する。１≦ｉ≦４で、ＬiＲiを下記の法則に従って計算する:
Ｌi=Ｒi-1
Ｒi=Ｌi-1＋ｆ（Ｒi-1＋Ｋi）
ここで、＋記号は２本の数列のビットごとのＥＯＲ（排他的ＯＲ）を表す。Ｋ1，Ｋ2，Ｋ3，Ｋ4はＫから計算された32ビットの数列である。
【００２９】
この結果は（Ｌ4，Ｒ4）となる。これは、例えば下記のように、非相関モジュールを適用する式Ｌ4Ｒ4に組み込まれる:
Ｋ5Ｋ6×Ｌ4Ｒ4＋Ｋ7Ｋ8
（Ｋ5，Ｋ6，Ｋ7，Ｋ8は各々32ビットの数列である）。
【００３０】
この結果は、ファイステルスキームによる２番目の関数に対する入力Ｌ'0Ｒ'0の役目をし、Ｌ'4Ｒ'4=Ｆ（ｘ）という結果を導く前記のものに類似する。
Ｋ'1，Ｋ'2，Ｋ'3，Ｋ'4もまた32ビットの数列である。
ここでキーはＫ1，Ｋ2，Ｋ3，Ｋ4，Ｋ'1，Ｋ'2，Ｋ'3，Ｋ'4，Ｋ5，Ｋ6，Ｋ7，Ｋ8である。
一般に、関数Ｆ''およびＧ''は任意の暗号化関数でよい。
【００３１】
ここで、２つの実施例を詳細に説明する:
これらの好ましい実施例の１番目では、８段の反復のファイステルスキームを用いる。Ｇ''は４つの関数ｆ1，ｆ2，ｆ3，ｆ4の連続処理、Ｆ''は４つの関数ｆ5，ｆ6，ｆ7，ｆ8の連続処理である（関数ｆiは関数ｆおよびランダムキーＫから定義する）。
【００３２】
関数ｆは下記の方法で定義する:
もしｘが32ビットワードであれば、まず下記φ（ｘ）を定義する:
φ（ｘ）=ｘ＋256.Ｓ（ｘｍｏｄ256）ｍｏｄ２32
ここで、Ｓは例えば付録１の表に表した関数で、ｕは横軸に、ｖは縦軸に表し、各々が１６進数である。（ｕ，ｖ）=ｘを座標（ｕ，ｖ）に示す値を有する値Ｓ（ｘ）に対応させる。
【００３３】
ｆ（ｘ）を下記式で定義する:
ｆ（ｘ）=φ（Ｒ11L（φ（ｘ））＋ｒｍｏｄ２32）
（ここで、Ｒ11Lは、11ビットの左への巡回置換であり、ｒは定数で、例えば下記のようにｓで定義される:
【００３４】
ｒ=ｂ７ｓ１５１６２および
【数１】
2009116348.tif 000003
キーＫは、各々64ビットの数列Ｋiを８個連結してできた256ビットの数列である:Ｋ=（Ｋ1Ｋ2Ｋ3...Ｋ8）。
【００３５】
ファイステルスキームは、関数ｆiを用いて実施する:
【数２】
2009116348.tif 000004
ここで、ｋiを下記のように定義し:
【００３６】
【表１】
2009116348.tif 000005
【００３７】
非相関モジュールは下記式となる:
【数３】
2009116348.tif 000006
【００３８】
２番目の好ましい実施例では、32段の反復のファイステルスキームを使用する:
最初の実施例に比べて、キーＫは2048ビットの数列、ｒはその値を保持し、関数ｆはｆ'に置換される:
ｆ'（ｘ）=Ｒ11L（ｘ）＋ｒｍｏｄ２32
関数ｆiは関数ｆ'iに置換される:
ｆ'i（ｘ）=ｆ'（ｘ.Ｋ2i-1＋Ｋ2iｍｏｄ２32-５）。
【００３９】
【表２】
2009116348.tif 000007
【図面の簡単な説明】
【００４０】
【図１】８段の反復のファイステルスキームに適用した本発明を示す。
【図１】
2009116348.tif 000008
【手続補正書】
【提出日】平成21年1月26日(2009.1.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
計算機によって使用可能な記録媒体に格納されたデータの暗号方法であって、計算機が入力情報ｘを関数Ｆでコード化した情報Ｆ（ｘ）を出力するキーを用いて処理する方法において、関数Ｆは少なくとも２に等しいランクの非相関モジュールＭKを使用し、Ｆ（ｘ）=Ｆ'（ＭK（ｘ））である（ここで、Ｋはランダムキーであり、Ｆ'はコード化関数である）ことを特徴とするデータの暗号方法。