(57)【要約】  差分／線形解読という解読法に対する耐性と、処理時間の高速化が可能な暗号化方法、暗号装置及び暗号処理プログラムの提供。  入力データを少なくとも４個以上の２ｍ個のデータに分割し、（Ａ）前記２ｍ個のデータのうちｍ個のデータについて３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理と、（Ｂ）前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出処理と、（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理の入力対象となったｍ個のデータと、の２ｍ個のデータを入れ替えて次段に送る入替処理と、を含み、前記（Ａ）〜（Ｃ）の処理をｎ回繰り返し、ｎ回目の入れ替え後に得られた２ｍ個のデータを結合し、出力データを生成する。(図１)
2009034929.tif 000002
【特許請求の範囲】
【請求項１】
入力データを少なくとも４個以上の２ｍ個のデータに分割し、
（Ａ）前記２ｍ個のデータのうちｍ個のデータについて３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理と、（Ｂ）前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出処理と、（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理の入力対象となったｍ個のデータと、の２ｍ個のデータを入れ替えて次段に送る入替処理と、を含み、
前記（Ａ）〜（Ｃ）の処理をｎ回繰り返し、ｎ回目の入れ替え後に得られた２ｍ個のデータを結合し、出力データを生成すること、
を特徴とする暗号化方法。
【請求項２】
前記入替処理として、前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和と、前記非線形変換処理の入力対象となったｍ個のデータと、からなるビット列を左右いずれかにデータ長分ローテイトさせること、
を特徴とする請求項１に記載の暗号化方法。
【請求項３】
前記非線形変換処理は、入力されたデータを２つのデータＸ０、Ｙ０に分割した後、一方のデータＹ０に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと他方のデータＸ０との排他的論理和により第１の中間データＹ１を得る第１のラウンドと、
前記第１の中間データＹ１に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと前記一方のデータＹ０との排他的論理和により第２の中間データＹ２を得る第２のラウンドと、
前記第２の中間データＹ２に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと前記第１の中間データＹ１との排他的論理和により第３の中間データＹ３を得る第３のラウンドと、からなり、
前記第２の中間データＹ２と前記第３の中間データＹ３とを結合して出力する請求項１又は２に記載の暗号化方法。
【請求項４】
前記繰り返し回数ｎは、入力データ長に応じた所定の特性確率を満たすよう決定される請求項１乃至３いずれか一に記載の暗号化方法。
【請求項５】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか、又は、前記各演算の組み合わせによって、暗号化する平文データに、鍵データを作用させてから、前記分割手段に出力する請求項１乃至４いずれか一に記載の暗号化方法。
【請求項６】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか、又は、前記各演算の組み合わせによって、前記結合手段から出力された出力データに鍵データを作用させる請求項１乃至５いずれか一に記載の暗号化方法。
【請求項７】
入力データを少なくとも４個以上の２ｍ個のデータに分割する分割手段と、
（Ａ）前記２ｍ個のデータのうち、ｍ個のデータが入力され、各データについて、３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理手段と、
（Ｂ）前記各非線形変換処理手段の出力と、前記非線形変換処理手段に入力されなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出手段と、
（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理手段への入力対象となったｍ個のデータとの２ｍ個のデータを入れ替える入替手段と、
２ｍ個のデータを結合する結合手段と、を備え、
前記分割手段により分割された入力データについて、前記（Ａ）〜（Ｃ）の各手段をｎ回動作させ、ｎ回目の入れ替え後に得られた２ｍ個のデータを、前記結合手段に入力し、出力データを生成すること、
を特徴とする暗号装置。
【請求項８】
前記入替手段は、前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和と、前記非線形変換処理の入力対象となったｍ個のデータと、からなるビット列を左右いずれかにデータ長分ローテイトする処理を行うこと、
を特徴とする請求項７に記載の暗号装置。
【請求項９】
前記非線形変換処理手段は、入力されたデータを２つのデータＸ０、Ｙ０に分割した後、一方のデータＹ０に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと他方のデータＸ０との排他的論理和により第１の中間データＹ１を得る第１のラウンドと、
前記第１の中間データＹ１に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと前記一方のデータＹ０との排他的論理和により第２の中間データＹ２を得る第２のラウンドと、
前記第２の中間データＹ２に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと前記第１の中間データＹ１との排他的論理和により第３の中間データＹ３を得る第３のラウンドと、からなり、
前記第２の中間データＹ２と前記第３の中間データＹ３とを結合して出力する請求項７又は８に記載の暗号装置。
【請求項１０】
前記非線形変換と排他的論理和の算出と入れ替えの繰り返し回数ｎは、入力データ長に応じた所定の特性確率を満たす値に設定されている請求項７乃至９いずれか一に記載の暗号装置。
【請求項１１】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか、又は、前記各演算の組み合わせによって、暗号化する平文データに、鍵データを作用させてから、前記分割手段に出力する初期処理手段を備える請求項７乃至１０いずれか一に記載の暗号装置。
【請求項１２】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか、又は、前記各演算の組み合わせによって、前記結合手段から出力された出力データに、鍵データを作用させる終期処理手段を備える請求項７乃至１１いずれか一に記載の暗号装置。
【請求項１３】
コンピュータに実行させる暗号処理プログラムであって、
入力データを少なくとも４個以上の２ｍ個のデータに分割する処理と、
（Ａ）前記２ｍ個のデータのうちｍ個のデータについて３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理と、（Ｂ）前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出処理と、（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理の入力対象となったｍ個のデータと、の２ｍ個のデータを入れ替えて次段に送る入替処理との前記（Ａ）〜（Ｃ）の各処理をｎ回繰り返し、
ｎ回目の入れ替え後に得られた２ｍ個のデータを結合し、出力データを生成する処理と、を前記コンピュータに実行させる暗号処理プログラム。
【請求項１４】
前記入替処理として、前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和と、前記非線形変換処理の入力対象となったｍ個のデータと、からなるビット列を左右いずれかにデータ長分ローテイトする処理を行う請求項１３に記載の暗号処理プログラム。
【請求項１５】
前記非線形変換処理は、入力されたデータを２つのデータＸ０、Ｙ０に分割した後、一方のデータＹ０に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと他方のデータＸ０との排他的論理和により第１の中間データＹ１を得る第１のラウンドと、
前記第１の中間データＹ１に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと前記一方のデータＹ０との排他的論理和により第２の中間データＹ２を得る第２のラウンドと、
前記第２の中間データＹ２に鍵データを作用させてから非線形変換を行い、該非線形変換されたデータと前記第１の中間データＹ１との排他的論理和により第３の中間データＹ３を得る第３のラウンドと、からなり、
前記第２の中間データＹ２と前記第３の中間データＹ３とを結合して出力する請求項１３又は１４に記載の暗号処理プログラム。
【請求項１６】
前記繰り返し回数ｎは、入力データ長に応じた所定の特性確率を満たす値に設定される請求項１３乃至１５いずれか一に記載の暗号処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の記載］
本発明は、日本国特許出願：特願２００７−２３６９５３号（２００７年９月１２日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、データの通信や蓄積の際にデータを秘匿するための暗号装置及び暗号処理プログラムに関し、特に、ブロックを単位として暗号化を行うブロック暗号技術に関する。
【背景技術】
【０００２】
共通鍵ブロック暗号の代表としてＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）がある。ＤＥＳは１９７７年にＦＩＰＳに採用されて以来、デファクトスタンダードとして広まっていった。ＤＥＳはＦｅｉｓｔｅｌと呼ばれる構造を採用し、その後多くの共通鍵ブロック暗号がＦｅｉｓｔｅｌ構造を採用した。【０００３】
１９９５年に松井らによって提案された６４ビットブロック暗号ＭＩＳＴＹ（登録商標）もＦｅｉｓｔｅｌ構造を採用している（非特許文献１、特許文献１参照）。なお、ＭＩＳＴＹとしては、ＭＩＳＴＹ１と、ＭＩＳＴＹ２とが知られているが、以下、通常のＦｅｉｓｔｅｌ構造を持つ、ＭＩＳＴＹ１を例に挙げて説明する。【０００４】
図６に、ＭＩＳＴＹ１のラウンド関数（ＦＯ）の内部構成を示す。図６の右側を参照すると、入力６４ビットのうちの３２ビットが入力されるＭＩＳＴＹ１のラウンド関数（ＦＯ）３は、３ラウンドのＦｅｉｓｔｅｌ構造を採用している。入力３２ビットのうちの１６ビットが入力される関数（ＦＩｉ１〜ＦＩｉ３）３１は非線形変換処理であり、その構造もまた３ラウンドＦｅｉｓｔｅｌ構造となっている。【０００５】
図６の左側は、関数（ＦＩｉ１）３１の内部構造を表した図であり、それぞれＳ−ｂｏｘと呼ばれる非線形変換処理（Ｓ９）３１１、非線形変換処理（Ｓ７）３１２が用いられている。このようにＭＩＳＴＹ１は３ラウンドのＦｅｉｓｔｅｌ構造を入れ子にした構造を特徴としている。【０００６】
次に、暗号の解析手法と安全性について述べる。代表的な暗号の解析手法として、差分解析や線形解析が挙げられる。これらの解析手法に対する安全性は差分確率や線形確率で評価される。【０００７】
暗号アルゴリズム全体でのこれら確率を導出することは計算量的に難しいため、一般的に小さな部品について正確な確率を求め、ある種の方法によって確率の積み上げを行うことによって暗号アルゴリズム全体の確率を導出する。このように小さな部品の確率を積み上げることによって導出した確率を特性確率と呼ぶ。【０００８】
図７は、Ｆｅｉｓｔｅｌ構造で用いられるＦ関数が全単射な場合の差分の伝播を説明するための図である。入力データとして、差分（０、ΔＡ）が入力された場合、差分ΔＡは第１ラウンドのＦ関数４１に入力され、非線形変換処理の結果、任意の差分ΔＢが出力される。このように、Ｆ関数が全単射な場合、必ず何がしかの差分値が出力される。【０００９】
差分ΔＢは、第２ラウンドのＦ関数４２に入力され、非線形変換処理の結果、差分ΔＡが出力される。第２ラウンドの排他的論理和４５で差分ΔＡ同士が打ち消されるため、第３ラウンドのＦ関数４３には差分は入力されない。図７の太線で示されたパスが、差分の伝播経路となる。【００１０】
ここで、非線形変換処理（Ｆ関数）に差分が入力されることを”アクティブになる”、差分が入力される非線形変換処理を”アクティブな非線形変換処理”と呼ぶ。特に、非線形変換処理がＳ−ｂｏｘである場合、”アクティブＳ−ｂｏｘ”と呼ぶ。【００１１】
図７で示したように、非線形変換処理（Ｆ関数）が全単射である場合、３ラウンド以上でアクティブな非線形変換処理の数は２以上であることが知られている。全単射なＦ関数を用いたＦｅｉｓｔｅｌ構造の暗号方式において、差分／線形特性確率を計算する場合、アクティブな非線形変換処理の確率の積で計算することができるので、非線形変換処理（Ｆ関数）の最大差分確率がｐのとき、３ラウンドのＦｅｉｓｔｅｌ構造における最大差分確率はｐ＾２（ｐの２乗）以下となる。【００１２】
【特許文献１】特開２００２−１４９０５８号公報  １１頁、図１７〜図１９
【非特許文献１】Ｍ．Ｍａｔｓｕｉ，  “Ｎｅｗ  Ｂｌｏｃｋ  Ｅｎｃｒｙｐｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ＭＩＳＴＹ”，ＦＳＥ’９７，  ｐｐ．５４−６８，  Ｓｐｒｉｎｇｅｒ，  １９９７．
【発明の開示】
【発明が解決しようとする課題】
【００１３】
なお、上記特許文献１及び非特許文献１の全開示内容はその引用をもって本書に繰込み記載する。以下の分析は、本発明によって与えられたものである。
ここで、図６に示すＭＩＳＴＹ１の最大差分確率について考える。図６左側の非線形変換処理（Ｓ９）３１１、非線形変換処理（Ｓ７）３１２の最大差分確率は、それぞれ２＾−８と２＾−６なので、図６右側の関数（ＦＩｉ１）３１の最大差分確率は２＾−１４（＝２＾−６×２＾−８）以下と見積もることができる。そして、ラウンド関数（Ｆ０）３の最大差分確率は２＾−２８（＝（２＾−１４）＾２）以下と見積もることができる。ＭＩＳＴＹ１の暗号化処理全体は、８ラウンドのＦｅｉｓｔｅｌ構造であるが、３ラウンド分の最大差分確率は、２＾−５６（＝（２＾−２８）＾２）以下であると見積もることができる。【００１４】
ＭＩＳＴＹ１はブロック長が６４ビットであるため、差分解析に対して安全であるためには、最大差分確率が２＾−６４を下回らなければならない。次に、図８を参照してＭＩＳＴＹ１の最大差分確率が２＾−６４を下回るために必要なラウンド数を説明する。【００１５】
図８の例では、入力データとして、差分（０、ΔＡ）が入力された場合、Ｆ関数５２、５３、５５に差分が入力された時点で、暗号化処理全体の差分特性確率は（２＾−２８）＾３となり、２＾−６４を下回る。つまり、ＭＩＳＴＹ１が差分解析において耐性を持つためには、最低５ラウンドが必要になることを示している。なお、線形確率についても同様の計算をすることができる。【００１６】
つまり、ＭＩＳＴＹ１は３ラウンドＦｅｉｓｔｅｌ構造を２重の入れ子にした実質８×３×３＝７２段の構成によって、差分確率、線形確率の向上を図っているということができる。【００１７】
このように、３ラウンドＦｅｉｓｔｅｌ構造を２重の入れ子にした構成では、１ラウンド当たり、都合９個の非線形変換処理が動作し、相応の処理時間、計算コストが掛かっているが、アクティブとなる非線形変換処理は、そのうちの４個のみとなり、上記差分特性確率の計算で示したように、特性確率に寄与しない無駄な非線形変換処理が多いという問題点がある。【００１８】
本発明は、上記した事情に鑑みてなされたものであって、その目的とするところは、差分解析や線形解析に対する耐性を確保しながら、処理時間を削減し高速化を図ることのできる暗号化方法、暗号装置及び暗号処理プログラムを提供することにある。
【課題を解決するための手段】
【００１９】
本発明の第１の視点によれば、入力データを少なくとも４個以上の２ｍ個のデータに分割し、下記（Ａ）〜（Ｃ）の処理をｎ回繰り返し、ｎ回目の入れ替え後に得られた２ｍ個のデータを結合し、出力データを生成する暗号化方法が提供される。
（Ａ）前記２ｍ個のデータのうちｍ個のデータについて３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理。
（Ｂ）前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出処理。
（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理の入力対象となったｍ個のデータと、の２ｍ個のデータを入れ替えて次段に送る入替処理。【００２０】
本発明の第２の視点によれば、入力データを少なくとも４個以上の２ｍ個のデータに分割する分割手段と、下記（Ａ）〜（Ｃ）の各手段と、２ｍ個のデータを結合する結合手段と、を備え、この（Ａ）〜（Ｃ）の各手段をｎ回動作させ、ｎ回目の入れ替え後に得られた２ｍ個のデータを、前記結合手段に入力し、出力データを生成する暗号装置が提供される。
非線形変換処理手段（Ａ）は、前記２ｍ個のデータのうち、ｍ個のデータが入力され、各データについて、３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う。
排他的論理和算出手段（Ｂ）は、前記各非線形変換処理手段の出力と、前記非線形変換処理手段に入力されなかったデータとのｍ個の排他的論理和を算出する。
入替手段（Ｃ）は、前記排他的論理和したｍ個のデータと、前記非線形変換処理手段への入力対象となったｍ個のデータとの２ｍ個のデータを入れ替える。【００２１】
本発明の第３の視点によれば、コンピュータに実行させる暗号処理プログラムであって、入力データを少なくとも４個以上の２ｍ個のデータに分割する処理の後に、下記（Ａ）〜（Ｃ）の各処理をｎ回繰り返し、ｎ回目の入れ替え後に得られた２ｍ個のデータを結合し、出力データを生成する処理を前記コンピュータに実行させる暗号処理プログラムが提供される。
非線形変換処理（Ａ）では、前記２ｍ個のデータのうちｍ個のデータについて３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う。
排他的論理和算出処理（Ｂ）では、前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和を算出する。
入替処理（Ｃ）では、前記排他的論理和したｍ個のデータと、前記非線形変換処理の入力対象となったｍ個のデータと、の２ｍ個のデータを入れ替えて次段に送る。
【発明の効果】
【００２２】
本発明によれば、特許文献１、非特許文献１に記載された３ラウンドＦｅｉｓｔｅｌ構造を入れ子にしたブロック暗号方式よりも効率よく差分／線形解析に対する耐性を確保することができる。その理由は、入力データを２ｍ個に分割し、上記少なくとも２つの非線形変換処理をアクティブにすることのできる３ラウンドＦｅｉｓｔｅｌ構造を持つｍ個の非線形変換処理に入力する構造を採用したことにある。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１の実施形態に係る暗号装置の構成を表したブロック図である。
【図２】図１の非線形変換処理部の詳細構成を表したブロック図である。
【図３】本発明の第１の実施形態に係る暗号装置における差分の伝播を説明するための図である。
【図４】本発明の第２の実施形態に係る暗号装置の構成を表したブロック図である。
【図５】図４の初期処理部の詳細構成を表したブロック図である。
【図６】ＭＩＳＴＹ（登録商標）のラウンド関数（ＦＯ）の内部構成を表した図である。
【図７】Ｆｅｉｓｔｅｌ構造における差分の伝播を説明するための図である。
【図８】ＭＩＳＴＹ１における最大差分確率が２＾−６４を下回るために必要なラウンド数を説明するための図である。
【符号の説明】
【００２４】
１  暗号処理部
３  ラウンド関数（ＦＯ）
４  非線形変換処理部
１１  分割処理部
１２  結合処理部
１３  非線形変換処理部
１４〜２５、９１〜９４、１３６〜１４３  データ
３１  関数（ＦＩｉ１〜ＦＩｉ３）
４１〜４３、５１〜５５  Ｆ関数
４５、７３〜８４  排他的論理和
６１〜７２  非線形変換処理部
１００  初期処理部
１０１  終期処理部
１３１  分割処理部
１３２  結合処理部
１３３〜１３５  Ｓ−ｂｏｘ
１４４〜１４６  鍵データ
３１１  非線形変換処理（Ｓ９）
３１２  非線形変換処理（Ｓ７）
【発明を実施するための最良の形態】
【００２５】
［第１の実施形態］
次に、本発明を実施するための最良の形態について図面を参照して詳細に説明する。図１は、本発明の第１の実施形態に係る暗号装置の構成を表したブロック図である。図１を参照すると、本発明の第１の実施形態に係る暗号装置の暗号処理部１は、入力データＰを分割する分割処理部１１と、データを非線形変換する非線形変換処理部１３と、データを結合する結合処理部１２とを有する。【００２６】
本実施形態では、分割処理部１１は、平文（入力データ）Ｐを４つのデータ１４、１５、１６、１７に分割する。なお、本実施形態では、入力データを４分割（２ｍ；ｍ＝２）するものとして説明するが、６以上の偶数個（ｍ＞２）とすることもできる。【００２７】
非線形変換処理部１３は、１ラウンドあたり、上記分割処理部１１によるデータ長とデータ分割数に応じた回数動作することになる。本実施形態では、分割処理部１１が４つのデータに分割するので、１ラウンドあたりの非線形変換処理部１３の動作回数は、分割処理部１１によるデータ分割数４の半数の２回（ｍ＝２）となる。また、ラウンド数（段数）ｎについては後に詳述する。【００２８】
また、図中の交差するパスは、入替手段（置換手段）に相当し、１ラウンドにつき入替処理として、非線形変換処理部１３による処理結果と非線形変換処理の対象としなかったデータ１５、１７との排他的論理和と、非線形変換処理部１３への入力対象となったデータ１４、１６と、からなるビット列を左にデータ長分ローテイトする処理が行われる。具体的には、データ１４を非線形変換処理部１３で変換した結果とデータ１５とを排他的論理和したものを中間データ１８とし、データ１６を非線形変換処理１３で変換した結果とデータ１７とを排他的論理和したものを中間データ２０とし、データ１４を中間データ２１、データ１６を中間データ１９とする入替処理が行われる。なお、図１の例では、データ長単位で、データを左方にずらし、左端のデータを右端に移動する左方向へのローテイト処理を行っているが、右方向のローテイト処理とすることもできる。【００２９】
なお、上記した分割処理部１１、非線形変換処理部１３、結合処理部１２、排他的論理和及び入替処理は、回路による構成はもちろんとして、コンピュータを上記した各処理手段として機能させるプログラムによっても実現することができる。【００３０】
図２は、非線形変換処理部１３の詳細構成を表した図である。図２を参照すると、非線形変換処理部１３は、入力データＸを２分割する分割処理部１３１と、分割されたデータを非線形変換するＳ−ｂｏｘ１３３、１３４、１３５と、データを結合する結合処理部１３２と、を有する３ラウンドのＦｅｉｓｔｅｌ構造となっている。また、図中の符号１４４、１４５、１４６は、中間データと排他的論理和される鍵データを表している。【００３１】
ここで、Ｓ−ｂｏｘ１３３、１３４、１３５は、次式に示すように、例えば、ガロア体などの有限体上のべき乗演算Ｇ（ｘ）と、例えば巡回シフトなどのアフィン変換Ａ（ｘ）との組み合わせである。なお、次式中のａ、ｂは、任意の定数であり、自由に選択できる。【００３２】
【数１】
2009034929.tif 000003
【００３３】
一般的にこのような演算の組み合わせによって、差分／線形確率及び代数的に良い性質を得られることが知られている。但し、べき乗演算Ｇ（ｘ）は、処理負荷が大きいため、一般的に予めすべての入力値について事前に計算を行い、その結果を変換テーブルの形で保持しておき、暗号化を行う際には変換テーブルを参照することによって、演算結果を得るという実装が一般的である。例えば、特許文献１にも、非線形変換を変換テーブルで行う例が記載されている（特許文献１の段落０１２３、図２０、図２１）。
上記引用をもって、上記特許文献１に記載されている変換テーブルを用いた非線形変換処理は、本書に繰込み記載されているものとする。【００３４】
続いて、図１を参照して、本実施形態の全体動作について説明する。まず、暗号処理部１に入力された平文Ｐは、分割処理部１１で４つのデータ１４、１５、１６、１７に分割される。【００３５】
データ１４は非線形変換処理部１３に入力されるとともに、次のラウンドにおいて非線形変換結果と排他的論理和される中間データ２１となる。【００３６】
データ１５は、非線形変換処理部１３によるデータ１４の非線形変換結果と排他的論理和され、次のラウンドにおける非線形変換対象の中間データ１８となる。【００３７】
データ１６は、非線形変換処理部１３に入力されるとともに、次のラウンドにおいて非線形変換結果と排他的論理和される中間データ１９となる。【００３８】
データ１７は、非線形変換処理部１３によるデータ１６の非線形変換結果と排他的論理和され、次のラウンドにおける非線形変換対象の中間データ２０となる。【００３９】
中間データ１８は、非線形変換処理部１３に入力されるとともに、次のラウンドにおいて非線形変換結果と排他的論理和される中間データとなる。【００４０】
中間データ１９は、非線形変換処理部１３によるデータ１８の非線形変換結果と排他的論理和され、次のラウンドにおける非線形変換対象の中間データとなる。【００４１】
中間データ２０は、非線形変換処理部１３に入力されるとともに、次のラウンドにおいて非線形変換結果と排他的論理和される中間データとなる。【００４２】
中間データ２１は、非線形変換処理部１３によるデータ２０の非線形変換結果と排他的論理和され、次のラウンドにおける非線形変換対象の中間データとなる。【００４３】
以上の非線形変換処理及び入替処理が所定のｎラウンド繰り返され、最終ラウンドの中間データ２２、２３、２４、２５が、結合処理部１２に入力される。【００４４】
結合処理部１２は、中間データ２２、２３、２４、２５を結合し、結果を暗号文Ｃとする。【００４５】
続いて、図２を参照して、上記した非線形変換処理部１３における処理について説明する。まず、非線形変換処理部１３に入力されたデータＸは、分割処理部１３１でデータ１３６、１３７に２分割される（Ｘ→Ｘ０、Ｙ０）。【００４６】
２分割された一方のデータ１３７（Ｙ０）は鍵データ１４４と排他的論理和され、Ｓ−ｂｏｘ１３３に入力されるとともに、次のラウンドにおいてＳ−ｂｏｘ１３４の出力結果と排他的論理和される中間データ１３８となる。なお、拡大鍵として使用する鍵データ１４４、１４５、１４６は、秘密鍵そのもの、もしくは秘密鍵に何らかの処理を施して生成される。【００４７】
もう一方のデータ１３６（Ｘ０）は、Ｓ−ｂｏｘ１３３によるデータ１３７の非線形変換結果と排他的論理和され、次のラウンドにおける鍵データ１４５との排他的論理和の後、Ｓ−ｂｏｘ１３４に入力される中間データ１３９（Ｙ１）となる。【００４８】
中間データ１３９（Ｙ１）は鍵データ１４５と排他的論理和され、Ｓ−ｂｏｘ１３４に入力されるとともに、次のラウンドにおいてＳ−ｂｏｘ１３５の出力結果と排他的論理和される中間データ１４０となる。【００４９】
もう一方の中間データ１３８は、Ｓ−ｂｏｘ１３４によるデータ１３９の非線形変換結果と排他的論理和され、次のラウンドにおける鍵データ１４６との排他的論理和の後、Ｓ−ｂｏｘ１３５に入力される中間データ１４１（Ｙ２）となる。【００５０】
中間データ１４１（Ｙ２）は鍵データ１４６と排他的論理和され、Ｓ−ｂｏｘ１３５に入力されるとともに、結合処理部１３２に入力される中間データ１４２となる。【００５１】
もう一方の中間データ１４０は、Ｓ−ｂｏｘ１３５によるデータ１４１の非線形変換結果と排他的論理和され、結合処理部１３２に入力される中間データ１４３（Ｙ３）となる。【００５２】
結合処理部１３２は、中間データ１４２、１４３（Ｙ３）を結合し、結果を出力データＹとする。【００５３】
ここで、本実施形態と、特許文献１及び非特許文献１に記載のＭＩＳＴＹ１との安全性及び効率を比較する。比較のために、本実施形態で取り扱う平文Ｐのブロック長をＭＩＳＴＹ１との同様の６４ビットとし、Ｓ−ｂｏｘが一般的な８ビット入出力であるとすると、２＾−６が最良の差分確率となり、全体で２＾−６４を下回るように、Ｓ−ｂｏｘがアクティブになる必要がある。【００５４】
図３は、本実施形態に係る暗号装置における差分の伝播を説明するための図である。本発明における差分確率が最大となる例を示すため、入力データとして、差分（０，０，０，ΔＡ）を与える。まず、差分ΔＡは非線形変換処理６４に入力され、任意の差分ΔＢが出力される。【００５５】
また、差分ΔＡは非線形変換処理６７にも入力され、任意の差分ΔＢが出力される。このとき非線形変換処理６４と非線形変換処理６７の出力差分が等しい場合、排他的論理和７９で差分はキャンセルされ０となる。【００５６】
このように非線形変換処理６６、６８、７０、７１にも差分が入力され、排他的論理和８２、８３でもキャンセルが発生し、６ラウンドの結果として差分（０，０，０，ΔＡ）が出力される。【００５７】
上記６ラウンドまでの過程で、非線形変換処理が１２回動作し、そのうち６つの非線形変換処理に差分が入力されアクティブになる。この非線形変換処理に、図２の３ラウンドのＦｅｉｓｔｅｌ構造を採用すると、先に図７で説明したように最低でも２つのＳ−ｂｏｘがアクティブになる。【００５８】
よって、本発明における暗号方法では、都合６ラウンドの１２×３＝３６回の非線形変換処理の実施で１２個のＳ−ｂｏｘがアクティブになる。このとき、暗号化処理全体の差分特性確率は（２＾−６）＾１２となり、２＾−６４を大きく下回る。【００５９】
一方、上述したＭＩＳＴＹ１の場合、ラウンド関数１回当たり９回（＝３×３）のＳ−ｂｏｘが実行されるが、差分確率が最大となるケースでは、そのうち４個（＝２×２）のＳ−ｂｏｘがアクティブとなるに止まる。全体では、図８に示すように５ラウンドの実施で３ラウンドがアクティブになるので、暗号化処理全体で１２個（＝３×４）のＳ−ｂｏｘがアクティブになる。このときの暗号化処理全体のＳ−ｂｏｘの動作回数は４５回（＝３×３×５）となり、本発明による暗号方法の３６回よりもはるかに多くなる。【００６０】
なお、線形解析についても同様であり、本発明による暗号方法の方が少ないＳ−ｂｏｘの動作回数で、必要な耐性を確保することが可能である。【００６１】
また、本実施形態とＭＩＳＴＹ１の構造はともに、Ｓ−ｂｏｘ参照、鍵データの排他的論理和、データの排他的論理和で構成されており（厳密には、ＭＩＳＴＹ１は補助関数を使用しているが、アクティブＳ−ｂｏｘの議論には影響しないので無視する。）、Ｓ−ｂｏｘの動作回数が暗号化処理の速度に比例すると考えることができるので、本発明の方が差分／線形解析においてＭＩＳＴＹ１よりも効率よく、耐性においても優れているということができる。【００６２】
［第２の実施形態］
次に、上記第１の実施形態に変更を加えた本発明の第２の実施形態について図面を参照して詳細に説明する。図４は、本発明の第２の実施形態に係る暗号装置の構成を表したブロック図である。図４を参照すると、本発明の第２の実施形態に係る暗号処理部１は、上記した第１の実施形態の暗号処理部１の前後に、初期処理部１００と終期処理部１０１とを付け加えた構成となっている。分割処理部１１と、非線形変換処理部１３と、結合処理部１２との構成及び動作は上記した第１の実施形態と同様である。【００６３】
初期処理部１００と終期処理部１０１は、平文Ｐ又は結合処理部１２の出力データに対して鍵データを作用させることによって、解読時における鍵の仮定量を増加させることによって実質的な耐性を向上させる効果がある。なお、初期処理部１００及び終期処理部１０１も、コンピュータを上記した各処理手段として機能させるプログラムによって実現することができる。【００６４】
図５は、初期処理部１００の詳細構成を表したブロック図である。図５を参照すると、初期処理部１００は、図１に示す暗号処理部１の構成中の非線形変換処理部１３に代えて、鍵データ（Ｋ１〜Ｋ８）との論理積（∩）又は論理和（∪）を配した構造となっている。【００６５】
図５の初期処理部１００によれば、出力されるデータ９１には６つの鍵データ（Ｋ１〜Ｋ４、Ｋ５、Ｋ７）が影響し、データ９２には４つの鍵データ（Ｋ１、Ｋ２、Ｋ４、Ｋ６）が影響する。同様に、データ９３には６つの鍵データ（Ｋ１〜Ｋ４、Ｋ６、Ｋ８）が影響し、データ９４には４つの鍵データ（Ｋ１、Ｋ２、Ｋ３、Ｋ５）が影響する。【００６６】
以上のように構成した本実施形態によれば、上記した第１の実施形態の効果に加えて解読時における鍵データの仮定量を増加させることが可能となる。また、終期処理部１０１も、上記初期処理部１００と同様の構造を採用することにより、解読時における鍵データの仮定量を増加させることができる。【００６７】
以上、本発明の好適な実施形態を説明したが、本発明は、上記した各実施形態に限定されるものではなく、本発明の基本的技術的思想を逸脱しない範囲で、更なる変形・置換・調整を加えることができる。例えば、上記初期／終期処理における鍵データとの作用は、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか、もしくは、前記各演算の組み合わせによって実現することができる。またあるいは、平文Ｐを幾つかに分割してから各々のデータに鍵データを算術加算や算術乗算といった演算で作用させるような初期／終期処理を追加した構成も採用可能である。【００６８】
以上の記載は、実施例に基づいて行ったが、本発明は、上記実施例に限定されるものではない。
本発明の全開示(請求の範囲を含む)の枠内において、更にその基本的技術思想に基づいて、実施態様ないし実施例の変更・調整が可能である。また本発明の請求の範囲(クレーム)の枠内において、種々開示要素の多様な組合せ・置換ないし選択が可能である。
本発明の更なる課題・目的及び展開形態は、クレームを含む本発明の全開示事項からも、明らかにされる。
【図１】
2009034929.tif 000004
【図２】
2009034929.tif 000005
【図３】
2009034929.tif 000006
【図４】
2009034929.tif 000007
【図５】
2009034929.tif 000008
【図６】
2009034929.tif 000009
【図７】
2009034929.tif 000010
【図８】
2009034929.tif 000011
【手続補正書】
【提出日】平成21年3月13日(2009.3.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力データを少なくとも４個以上の２ｍ個のデータに分割し、
（Ａ）前記２ｍ個のデータのうちｍ個のデータについて３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理と、（Ｂ）前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出処理と、（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理の入力対象となったｍ個のデータと、の２ｍ個のデータを入れ替えて次段に送る入替処理と、を含み、
前記（Ａ）〜（Ｃ）の処理をｎ回繰り返し、ｎ回目の入れ替え後に得られた２ｍ個のデータを結合し、出力データを生成すること、
を特徴とする暗号化方法。
【請求項２】
（削除）
【請求項３】
（削除）
【請求項４】
（削除）
【請求項５】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか複数を交換則がなりたたないような組み合わせによって、暗号化する平文データに、平文データサイズ以上の鍵データを作用させてから、前記分割手段に出力する請求項１に記載の暗号化方法。
【請求項６】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか複数を交換則がなりたたないような組み合わせによって、前記結合手段から出力された出力データに平文データサイズ以上の鍵データを作用させる請求項１又は５に記載の暗号化方法。
【請求項７】
入力データを少なくとも４個以上の２ｍ個のデータに分割する分割手段と、
（Ａ）前記２ｍ個のデータのうち、ｍ個のデータが入力され、各データについて、３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理手段と、
（Ｂ）前記各非線形変換処理手段の出力と、前記非線形変換処理手段に入力されなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出手段と、
（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理手段への入力対象となったｍ個のデータとの２ｍ個のデータを入れ替える入替手段と、
２ｍ個のデータを結合する結合手段と、を備え、
前記分割手段により分割された入力データについて、前記（Ａ）〜（Ｃ）の各手段をｎ回動作させ、ｎ回目の入れ替え後に得られた２ｍ個のデータを、前記結合手段に入力し、出力データを生成すること、
を特徴とする暗号装置。
【請求項８】
（削除）
【請求項９】
（削除）
【請求項１０】
（削除）
【請求項１１】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか複数を交換則がなりたたないような組み合わせによって、暗号化する平文データに、平文データサイズ以上の鍵データを作用させてから、前記分割手段に出力する初期処理手段を備える請求項７に記載の暗号装置。
【請求項１２】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか複数を交換則がなりたたないような組み合わせによって、前記結合手段から出力された出力データに、平文データサイズ以上の鍵データを作用させる終期処理手段を備える請求項７又は１１に記載の暗号装置。
【請求項１３】
コンピュータに実行させる暗号処理プログラムであって、
入力データを少なくとも４個以上の２ｍ個のデータに分割する処理と、
（Ａ）前記２ｍ個のデータのうちｍ個のデータについて３ラウンドのＦｅｉｓｔｅｌ構造により鍵データとの攪拌を行う非線形変換処理と、（Ｂ）前記各非線形変換処理結果と前記非線形変換処理の対象としなかったデータとのｍ個の排他的論理和を算出する排他的論理和算出処理と、（Ｃ）前記排他的論理和したｍ個のデータと、前記非線形変換処理の入力対象となったｍ個のデータと、の２ｍ個のデータを入れ替えて次段に送る入替処理との前記（Ａ）〜（Ｃ）の各処理をｎ回繰り返し、
ｎ回目の入れ替え後に得られた２ｍ個のデータを結合し、出力データを生成する処理と、を前記コンピュータに実行させる暗号処理プログラム。
【請求項１４】
（削除）
【請求項１５】
（削除）
【請求項１６】
（削除）
【請求項１７】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか複数を交換則がなりたたないような組み合わせによって、暗号化する平文データに、平文データサイズ以上の鍵データを作用させてから、分割する初期処理を前記コンピュータに実行させる請求項１３に記載の暗号処理プログラム。
【請求項１８】
更に、論理演算（論理和、論理積、排他的論理和）、算術演算（加算、減算、乗算、除算）のいずれか複数を交換則がなりたたないような組み合わせによって、前記結合手段から出力された出力データに、平文データサイズ以上の鍵データを作用させる終期処理を前記コンピュータに実行させる請求項１３又は１７に記載の暗号処理プログラム。
【国際調査報告】
2009034929.tif 000012
2009034929.tif 000013
2009034929.tif 000014
2009034929.tif 000015