暗号装置及び方法
【課題】第１の非線形変換処理Ｓ９と第２の非線形変換処理Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置で、ＲＡＭを用いずＲＯＭ容量を削減する。
【解決手段】第１の非線形変換処理Ｓ９に関連する演算結果を予め格納している第１の変換テーブルと、第２の非線形変換処理Ｓ７に関連する演算結果を予め格納している第２の変換テーブルとをＲＯＭに格納しておき、第１の変換テーブルを２度参照して、第２のテーブルを１度参照する処理にＦＩ関数を等価変換する。第１の変換テーブルを２度参照するような処理にＦＩ関数を等価変換しているので、ＲＯＭ容量を少なくすることができる。
【解決手段】第１の非線形変換処理Ｓ９に関連する演算結果を予め格納している第１の変換テーブルと、第２の非線形変換処理Ｓ７に関連する演算結果を予め格納している第２の変換テーブルとをＲＯＭに格納しておき、第１の変換テーブルを２度参照して、第２のテーブルを１度参照する処理にＦＩ関数を等価変換する。第１の変換テーブルを２度参照するような処理にＦＩ関数を等価変換しているので、ＲＯＭ容量を少なくすることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、ＦＩ関数を利用する暗号技術に関する。
【背景技術】
【０００２】
共通鍵暗号方式の１つであるＭＩＳＴＹ１（詳細は、松井充:ブロック暗号アルゴリズムMISTY, 信学技報, ISEC96-11(1996-07)等を参照のこと）については、様々な実装方式が検討されている。
【０００３】
図１にＭＩＳＴＹ１を含む共通鍵暗号方式の構成の一例を示す。ＭＩＳＴＹ１に係る共通鍵暗号処理はラウンド処理と拡大鍵生成処理の２つの処理を含む。図１に示すように、拡大鍵生成処理は、入力された秘密鍵から複数の拡大鍵（図１では、拡大鍵０、拡大鍵１、．．．、拡大鍵Ｎ）を生成する。生成された拡大鍵は、暗号化処理（ラウンド処理とも呼ぶ）で使用される。暗号化処理は、平文（すなわち暗号化対象データ）を一定のビット長（すなわちブロック長）ごとに区切り、区切った各ブロックに対してラウンド処理を実施し、暗号文を生成する。復号の際には、暗号化処理と逆の演算を行う。
【０００４】
共通鍵暗号方式ＭＩＳＴＹ１は、秘密鍵長が１２８ビット、ブロック長６４ビットを暗号化単位とするアルゴリズムである。
【０００５】
図２に、ＭＩＳＴＹ１のラウンド処理部の構成を示す。図２に示すように、平文Ｐ（６４ビット）を暗号文Ｃ（６４ビット）に変換するラウンド処理部では、ＦＬ関数が１０回実行され、ＦＯ関数が８回実行される。
【０００６】
ｉ番目のＦＯ関数は、図３に示すような構成を有する。ＦＯ関数には、ＫＯi1、ＫＯi2、ＫＯi3及びＫＯi4（各１６ビット）が入力されるようになっている。これらは、秘密鍵１２８ビットを１６ビット毎に分割することによって得られるＫ１乃至Ｋ８のうち４つである。Ｋ１乃至Ｋ８のいずれが用いられるかは、ラウンド値ｉ（ＦＯiのｉの値）に基づきアルゴリズム仕様書に従って決定される。
【０００７】
また、ｉ番目のＦＯ関数では、ＦＩ関数が３回実行される。そして、ＦＩi1関数には、ＫＩi1が入力され、ＦＩi2関数には、ＫＩi2が入力され、ＦＩi3関数には、ＫＩi3が入力される。ＫＩi1乃至ＫＩi3は、１６ビットの値であり、拡大鍵生成アルゴリズムにて生成したＫ'1乃至Ｋ'8のうち３つである。Ｋ'1乃至Ｋ'8のいずれを用いるかは、ラウンド値ｉ（ＦＯiのｉの値）に基づきアルゴリズム仕様書に従って決定される。
【０００８】
ｉ番目のＦＯ関数におけるｊ番目のＦＩ関数の構成を図４に示す。ＦＩ関数は、入力１６ビットの上位９ビットを非線形関数Ｓ９（入力データを決められたアルゴリズム（論理演算の繰り返し）に従って攪拌して出力する関数）に入力して、関数Ｓ９の出力と、入力１６ビットの下位７ビットの上位２ビットに０を追加した（0-extensionと記す）値との排他的論理和を算出して、データａを生成する。また、入力１６ビットの下位７ビットを非線形関数Ｓ７（入力データを決められたアルゴリズム（論理演算の繰り返し）に従って攪拌して出力する関数）に入力して、関数Ｓ７の出力と、データａの上位２ビットを除去した（truncateと記す）値との排他的論理和を算出して、データｂを生成する。さらに、データｂとＫＩijL（ＫＩijの上位７ビット）との排他的論理和を算出し、データｃを生成する。また、データａとＫＩijR（ＫＩijの下位９ビット）との排他的論理和を算出し、データｄを生成する。データｄは、再度非線形関数Ｓ９に入力され、さらに関数Ｓ９の出力とデータｄの上位２ビットに０を追加した値との排他的論理和を算出して、データｅを生成する。そして、最終的にデータｃを上位７ビットとし、データｅを下位９ビットとして連結すれば、１６ビットの出力となる。
【０００９】
次に図５に、ＭＩＳＴＹ１の拡大鍵生成部の構成を示す。拡大鍵生成部では、１２８ビットの秘密鍵を１６ビット毎に分割して、先頭からＫ１乃至Ｋ８を生成する。図５で示すように、Ｋ８を入力としてＫ１をＫＩijとしてＦＩ関数で拡大鍵Ｋ'8を生成する。Ｋ７を入力としてＫ８をＫＩijとしてＦＩ関数で拡大鍵Ｋ'7を生成する。Ｋ６を入力としてＫ７をＫＩijとしてＦＩ関数で拡大鍵Ｋ'6を生成する。Ｋ５を入力としてＫ６をＫＩijとしてＦＩ関数で拡大鍵Ｋ'5を生成する。Ｋ４を入力としてＫ５をＫＩijとしてＦＩ関数で拡大鍵Ｋ'4を生成する。Ｋ３を入力としてＫ４をＫＩijとしてＦＩ関数で拡大鍵Ｋ'3を生成する。Ｋ２を入力としてＫ３をＫＩijとしてＦＩ関数で拡大鍵Ｋ'2を生成する。Ｋ１を入力としてＫ２をＫＩijとしてＦＩ関数で拡大鍵Ｋ'1を生成する。
【００１０】
このように、ＭＩＳＴＹ１をソフトウエア又はハードウエアで実装する際には、ＦＩ関数の実装方法が重要となる。なぜなら、ＦＩ関数はラウンド処理部及び拡大鍵生成部の双方で使用される処理であり、ＦＩ関数を効率的に処理することが可能となれば、ＭＩＳＴＹ１の処理性能が大きく向上する。
【００１１】
ＦＩ関数の従来実装法については日本特許第３９１７３５７号公報に幾つか示されている。
【００１２】
図６及び図７に上記特許公報に開示されている第１の実装例を示す。本実装例では、図４のアルゴリズムを図６に示すようなアルゴリズムに等価変換した上で、非線形関数Ｓ９の処理１００１と、非線形関数Ｓ７を含む処理１００３と、非線形関数Ｓ９を含む処理１００５とをテーブル化する。但し、処理１００１と処理１００５とは異なる。その結果として、図７に示すように、処理１００１がテーブルＴ１に置換され、処理１００３がテーブルＴ４に置換され、処理１００５がテーブルＴ５に置換される。これらのテーブルは、ＲＯＭに格納され、必要なときに参照される。
【００１３】
なお、一例として、Ｋ'1を使用するＦＩ関数については、ＫＩijＲとＫＩijＬ'とは以下のように生成される。
ＫＩijＲ＝Ｋ'1 ＆ 0x1FF
tmpk1＝Ｋ'1 ＆ 0xFE00
tmpk2＝ＫＩijＲ ＆ 0x7F
tmpk3＝tmpk2 ＜＜ 9
tmpk4＝tmpk3 ＋ tmpk1
tmpk5＝tmpk4 ＞＞ 9
ＫＩijＬ'＝tmpk5 ＋ tmpk4
【００１４】
テーブルＴ１、テーブルＴ４及びテーブルＴ５は以下のように定義される。なお、Ｘは入力である。また、全ての取り得るＸ値についてテーブルエントリを生成する。
Ｔ１（Ｘ）＝Ｓ９（Ｘ）
Ｔ５（Ｘ）＝（（Ｘ＆0x7F）＜＜９）＋（Ｘ＆0x7F）＋Ｓ９（Ｘ）
Ｔ４（Ｘ）＝（Ｓ７（Ｘ）＜＜９）＋Ｓ７（Ｘ）
「＜＜９」は左シフトで、「＞＞９」は右シフトで、Ｘ＆０ｘ７ＦはＸの下位７ビットを抽出するものである。
【００１５】
このような実装方法では、テーブルＴ１のサイズが１ＫＢで、テーブルＴ４のサイズが１ＫＢで、テーブルＴ５のサイズが２５６Ｂで、合計２３０４ＢのＲＯＭテーブルサイズが必要となる。但し、ＲＡＭは必要ない。
【００１６】
また、本実装例では、ＦＩ関数１つあたり９サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理全体では２１６サイクルかかる。
【００１７】
一方、拡大鍵生成処理では、ＫＩijＲ及びＫＩijＬ'に相当するデータの事前計算のための７サイクルと、ＦＩ関数の９サイクルと、Ｋ'iについてラウンド処理のためのＫＩijＲ及びＫＩijＬ'を生成する処理のための７サイクルとが、８つのＦＩ関数で必要となる。従って、拡大鍵生成処理全体では、（７＋９＋７）＊８＝１８４サイクル必要となる。
【００１８】
なお、ラウンド処理の処理時間を「ＦＩ関数１回に必要なサイクル数×８」として計算する。なお、ラウンド処理には、ＦＩ関数以外にもＦＬ関数や、ＦＯ関数における拡大鍵との排他的論理和（ＸＯＲ）のためのサイクル数が必要となる。しかしながら、これらの処理は負荷が軽く必要サイクル数が少ないため、処理時間見積りの対象には含めないこととする。
【００１９】
さらに、図８及び図９に上記特許公報に開示されている第２の実装例を示す。図８に示すように、図７に示した第１の実装例において、ＫＩijＲとの排他的論理和及びテーブルＴ５の部分１１０１を、テーブル化する。すなわち、図９に示すように、テーブルＴ５ｊを導入する。
【００２０】
但し、ＫＩijＲは拡大鍵Ｋ'iを基に生成されるデータであり、ユーザが秘密鍵を暗号装置に入力して初めて値が特定できるものである。従って、テーブルＴ５ｊを、ユーザによる秘密鍵入力前に計算しておくことはできず、必ず入力後に計算することとなる。すなわち、テーブルＴ５ｊをＲＯＭには保持できず、ＲＡＭに保持する必要がある。
【００２１】
テーブルＴ１及びＴ４は、上で述べたとおりであり、事前にＸの取り得る全ての値について事前に計算して、ＲＯＭに記録しておく。一方、テーブルＴ５ｊについては、以下のような式で算出される。但し、ユーザによる秘密鍵の入力後に、取り得る入力パターンについて全て計算した後に、ＲＡＭに保持しておく。
Ｔ５ｊ（Ｘ）＝（（（Ｘ＋ＫＩijＲ）＆ 0x7F）＜＜９）＋（（Ｘ＋ＫＩjiＲ）＆0x7F）＋Ｓ９（Ｘ）
【００２２】
このような実装方法では、テーブルＴ１のサイズが１ＫＢで、テーブルＴ４のサイズが２５６Ｂで、合計１２８０ＢのＲＯＭテーブルサイズが必要となる。また、テーブルＴ５をＲＡＭに保持するので、そのサイズは１ＫＢとなる。
【００２３】
この実装例では、ＦＩ関数１つあたり８サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理全体では１９２サイクルかかる。
【００２４】
一方、拡大鍵生成処理では、テーブルＴ５ｊの生成も同時に行う必要がある。このテーブルの生成には１５３６サイクル以上必要になり、その他の拡大鍵生成処理を含めると、全体では１６００サイクル以上必要となる。
【００２５】
さらに、図１０及び図１１に上記特許公報に開示されている第３の実装例を示す。図１０に示すように、図９に示した第２の実装例において、ＫＩijＬ'との排他的論理和及びテーブルＴ４の部分１２０１を、テーブル化する。すなわち、図１１に示すように、テーブルＴ４ｊを導入する。
【００２６】
但し、ＫＩijＬ'は拡大鍵Ｋ'iを基に生成されるデータであり、ユーザが秘密鍵を暗号装置に入力して初めて値が特定できるものである。従って、テーブルＴ４ｊを、ユーザによる秘密鍵入力前に計算しておくことはできず、必ず入力後に計算することとなる。すなわち、テーブルＴ４ｊをＲＯＭには保持できず、ＲＡＭに保持する必要がある。
【００２７】
テーブルＴ１は、上で述べたとおりであり、事前にＸの取り得る全ての値について事前に計算して、ＲＯＭに記録しておく。テーブルＴ５ｊについても、上で述べたとおりであり、ＲＡＭに保持しておく。さらに、テーブルＴ４ｊに格納されるデータは、以下のような式で計算される。但し、ユーザによる秘密鍵の入力後に、取り得る入力パターンについて全て計算した後に、ＲＡＭに保持しておく。
Ｔ４ｊ（Ｘ）＝（Ｓ７（Ｘ）＜＜９）＋Ｓ７（Ｘ）＋ＫＩijＬ'
【００２８】
このような実装方法では、テーブルＴ１のサイズが１ＫＢで、テーブルＴ４ｊのサイズは事前計算用に少なくとも１２８Ｂで、合計１１５２Ｂ以上のＲＯＭテーブルサイズが必要となる。一方、テーブルＴ４ｊ及びＴ５ｊについてはＲＡＭに保持することになるが、サイズは１２８０Ｂとなる。
【００２９】
さらに、この実装例では、ＦＩ関数１つあたり７サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理全体では１６８サイクルかかる。
【００３０】
一方、拡大鍵生成処理では、テーブルＴ４ｊ及びＴ５ｊの生成も同時に行う必要がある。このテーブルの生成には１９２０サイクル以上必要になり、その他の拡大鍵生成処理を含めると、全体では２０００サイクル以上必要となる。
【００３１】
さらに、論文（中嶋純子、松井充: ＭＩＳＴＹのソフトウエアによる高速実装法について (II) SCIS98-9.1B）には、他の実装例が示されている。これについて図１２を用いて説明する。この実装例では、図４に示したＦＩ関数を図１２に示すような形に等価変換している。図１２の例では、非線形関数Ｓ９及びＳ７を含む上段部分をテーブルＴ７に変換し、ＫＩijとの排他的論理和以外で非線形関数Ｓ９を含む下段部分をテーブルＴ８に変換している。
【００３２】
このような実装例では、テーブルＴ７のサイズは１３１０７２Ｂであり、テーブルＴ８のサイズは１３１０７２Ｂであり、合計２６２１４４Ｂ必要となる。なお、ＲＡＭは必要ない。
【００３３】
このような実装例では、ＦＩ関数１つあたり３サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理については７２サイクルかかる。ＫＩijについてはそのまま用いるので、ＦＩ関数が８個分で拡大鍵生成処理には２４サイクル必要となる。
【先行技術文献】
【特許文献】
【００３４】
【特許文献１】日本特許第３９１７３５７号公報
【非特許文献】
【００３５】
【非特許文献１】中嶋純子、松井充: ＭＩＳＴＹのソフトウエアによる高速実装法について (II) SCIS98-9.1B
【非特許文献２】松井充:ブロック暗号アルゴリズムMISTY, 信学技報, ISEC96-11(1996-07)
【発明の概要】
【発明が解決しようとする課題】
【００３６】
ＭＩＳＴＹ１などは組み込み機器に実装する場合もあるので、ＲＡＭ使用量が少ないこと、ＲＯＭサイズが小さいこと、処理速度が高速であることが必要となる。特にＲＡＭについては極力使用量が少ないことが求められ、事前計算テーブルをＲＡＭに保持する手法は組み込み機器環境には向いていない。また、ＲＯＭについても極力サイズが小さいことが求められる。しかし、単純にＲＯＭに格納するテーブルを削減してしまうと、処理速度が著しく低下し、処理速度が不十分となる。
【００３７】
従って、本技術の目的は、暗号装置で用いられるＦＩ関数を実装する上で、ＲＯＭに格納するテーブルのサイズを小さくするための技術を提供することである。
【課題を解決するための手段】
【００３８】
本暗号装置は、第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置である。そして、本暗号装置は、（Ａ−１）９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と第１の出力との排他的論理和の値を、全ての第１の入力Ｘについて格納した第１の変換テーブルと、（Ａ−２）７＊ｎビットの第２の入力Ｙに対する第２の非線形関数Ｓ７の第２の出力と第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と第２の入力Ｙとの排他的論理和の値を、全ての第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリと、（Ｂ）読み出し専用メモリに記録されている第１の変換テーブルを２度用い、読み出し専用メモリに記録されている第２の変換テーブルを１度用いて、ＦＩ関数の１回の演算を行うＦＩ関数演算部とを有する。
【発明の効果】
【００３９】
暗号装置で用いられるＦＩ関数を実装する上で、ＲＯＭに格納するテーブルのサイズを小さくすることができる。
【図面の簡単な説明】
【００４０】
【図１】図１は、共通鍵暗号方式ＭＩＳＴＹ１の構成例を示す図である。
【図２】図２は、ラウンド処理のアルゴリズムを示す図である。
【図３】図３は、ＦＯ関数のアルゴリズムを示す図である。
【図４】図４は、ＦＩ関数のアルゴリズムを示す図である。
【図５】図５は、拡大鍵生成処理のアルゴリズムを示す図である。
【図６】図６は、第１の従来実装例で行われる等価変換を示す図である。
【図７】図７は、第１の従来実装例のアルゴリズムを示す図である。
【図８】図８は、第２の従来実装例で行われる等価変換を示す図である。
【図９】図９は、第２の従来実装例のアルゴリズムを示す図である。
【図１０】図１０は、第３の従来実装例で行われる等価変換を示す図である。
【図１１】図１１は、第３の従来実装例のアルゴリズムを示す図である。
【図１２】図１２は、第４の従来実装例で行われる等価変換を示す図である。
【図１３】図１３は、本技術の実施の形態におけるＦＩアルゴリズムの等価変換を説明するための図である。
【図１４】図１４は、等価変換後の処理内容を説明するための図である。
【図１５】図１５は、プロセッサで処理を実施するような場合の構成を示す図である。
【図１６】図１６は、暗号装置の機能ブロック図である。
【図１７】図１７は、効果の比較表を示す図である。
【図１８】図１８は、ＦＩ関数をハードウエアで実施した場合の一例を示す図である。
【図１９】図１９は、ＦＩ３関連処理の他の例を示す図である。
【図２０】図２０は、ＦＩ３関連処理の他の例を示す図である。
【図２１】図２１は、暗号装置の機能ブロック図である。
【図２２】図２２は、暗号装置の処理フローを示す図である。
【発明を実施するための形態】
【００４１】
本技術の実施の形態では、図４に示したＦＩ関数のアルゴリズムを、図１３に示すように等価変換する。なお、以下では１６ビット入力の例を示すが、１６ビットの整数倍したビット長にも容易に変換できる。その際には、９ビット及び７ビットについても整数倍される。
【００４２】
図１３のアルゴリズムでは、１６ビット入力Ｚの上位９ビットを非線形関数Ｓ９に入力して、非線形関数Ｓ９の出力９ビットのうち下位７ビットを上位に非線形関数Ｓ９の出力９ビットをそのまま下位に配置して連結して第１のデータを生成する。ここまでの処理内容を、第１のテーブルＳ９Ｆに変換する。
【００４３】
また、１６ビット入力Ｚの下位７ビットを非線形関数Ｓ７に入力して、非線形関数Ｓ７の出力と入力Ｚの下位７ビットとの排他的論理和を算出して第２のデータを生成する。そして、第２のデータを上位に、入力Ｚの下位７ビットの上位に０を２ビット加えた値を下位に配置して連結して第３のデータを生成する。ここまでの処理内容を第２のテーブルＳ７Ｆに変換する。
【００４４】
さらに、第１のデータと第３のデータとの排他的論理和の結果と、ＫＩijとの排他的論理和を算出して第４のデータを生成する。
【００４５】
この第４のデータの下位９ビットを、非線形関数Ｓ９に入力して、非線形関数Ｓ９の出力９ビットのうち下位７ビットを上位に非線形関数Ｓ９の出力９ビットをそのまま下位に配置して連結して第５のデータを生成する。この部分は、第１のテーブルＳ９Ｆの元の処理と同じであり、第１のテーブルＳ９Ｆへの参照に置換できる。
【００４６】
そして、第４のデータの上位７ビットの上位に０を２ビット加えた値と第５のデータの下位９ビットとの排他的論理和の結果を下位に配置し、第４のデータの上位７ビットを上位に配置して、出力Ｒが生成される。
【００４７】
このような等価変換後のアルゴリズムにおいて、テーブルＳ９Ｆは、取り得る全ての入力Ｘについて、以下のような値Ｓ９Ｆ（Ｘ）が格納されているテーブルである。同様に、テーブルＳ７Ｆは、取り得る全ての入力Ｙについて、以下のような値Ｓ７Ｆ（Ｙ）が格納されているテーブルである。
Ｓ９Ｆ（Ｘ）＝（（Ｓ９（Ｘ）＆0x7F）＜＜９）＋Ｓ９（Ｘ）
Ｓ７Ｆ（Ｙ）＝（Ｓ７（Ｙ）＋Ｙ）＜＜９）＋Ｙ
上で述べたが、「＆0x7F」は、下位７ビットを抽出する処理を表し、「＜＜９」は９ビット左シフトを表す。なお「＋」は排他的論理和を表している。そして、Ａが７ビット、Ｂが９ビットであれば、（Ａ＜＜９）＋Ｂにて、Ａを上位ビット７ビットに配置してＢを下位ビット９ビットに配置するような処理となる。
【００４８】
従って、再度表せば、テーブルＳ９Ｆ（Ｘ）は、９ビットの入力Ｘに対する非線形変換処理Ｓ９の出力の下位７ビットを抽出し、当該出力の下位７ビットを９ビット左シフトした値と非線形関数の出力との排他的論理和の値を、各Ｘに対応付けて登録したテーブルである。
【００４９】
同様に、テーブルＳ７Ｆ（Ｙ）は、７ビットの入力Ｙに対する非線形関数Ｓ７の出力と入力Ｙとの排他的論理和の結果を９ビット左シフトし、当該排他的論理和の結果の９ビット左シフトした値と入力Ｙとの排他的論理和の値を、各Ｙに対応付けて登録したテーブルである。
【００５０】
このようなテーブルを採用すればＲＡＭに格納しなければならないテーブルは存在しない。
【００５１】
次に、このようなテーブルを用いたＦＩ関数の処理について、図１４を用いて説明する。
【００５２】
暗号装置のプロセッサ（すなわちＣＰＵ（Central Processing Unit））は、入力データを格納しているレジスタＲ０から上位９ビットを取り出し、レジスタＲ１に格納する（ステップＳ１）。そして、プロセッサは、テーブルＳ９Ｆから、レジスタＲ１に格納されている値に対応するアドレスのデータ（例えばＲ１値の順番のデータ）を読み出して、レジスタＲ１に格納する（ステップＳ３）。なお、ステップＳ１及びＳ３は、１回目のＳ９Ｆ処理と呼ぶ。
【００５３】
一方、プロセッサは、レジスタＲ０から下位７ビットを取り出し、レジスタＲ２に格納する（ステップＳ５）。さらに、プロセッサは、テーブルＳ７Ｆから、レジスタＲ２に格納されている値に対応するアドレスのデータ（例えばＲ２値の順番のデータ）を読み出して、レジスタＲ２に格納する（ステップＳ７）。なお、ステップＳ５及びＳ７は、Ｓ７Ｆ処理と呼ぶ。
【００５４】
１回目のＳ９Ｆ処理とＳ７Ｆ処理とは順番の入れ替えが可能であり、また複数コアを有するプロセッサであれば並列に実行しても良い。
【００５５】
そして、プロセッサは、レジスタＲ１のデータとレジスタＲ２のデータとの排他的論理和を算出し、結果をレジスタＲ１に格納する（ステップＳ９）。
【００５６】
また、プロセッサは、拡大鍵ＫＩijを読み出してレジスタＲ３に格納する（ステップＳ１１）。そして、プロセッサは、レジスタＲ１のデータとレジスタＲ３のデータとの排他的論理和を算出し、結果をレジスタＲ１に格納する（ステップＳ１３）。ステップＳ１１及びＳ１３は、拡大鍵加算処理である。
【００５７】
排他的論理和については順番は問われないので、ステップＳ９と拡大鍵加算処理については順番を入れ替えることが可能である。
【００５８】
さらに、プロセッサは、レジスタＲ１から下位９ビットを取り出し、レジスタＲ４に格納する（ステップＳ１５）。また、プロセッサは、テーブルＳ９ＦからレジスタＲ４に格納されている値に対応するアドレスのデータ（例えばＲ４値の順番のデータ）を読み出して、レジスタＲ４に格納する（ステップＳ１７）。さらに、プロセッサは、レジスタＲ４から下位９ビットを取り出して、レジスタＲ５に格納する（ステップＳ１９）。ステップＳ１５乃至Ｓ１９は、第２回目のＳ９Ｆ処理と呼ぶ。
【００５９】
また、プロセッサは、レジスタＲ１から上位７ビットを取り出し、レジスタＲ６に格納する（ステップＳ２１）。そして、プロセッサは、レジスタＲ６の値と当該レジスタＲ６を左に９ビットシフトした値との排他的論理和を算出し、結果をレジスタＲ６に格納する（ステップＳ２３）。ステップＳ２１及びＳ２３を、ＦＩ３関連処理と呼ぶ。
【００６０】
第２回目のＳ９Ｆ処理とＦＩ３関連処理とは順番の入れ替えが可能であり、また複数コアを有するプロセッサであれば並列に実行してもよい。
【００６１】
そして、最後にプロセッサは、レジスタＲ６の値とレジスタＲ５の値との排他的論理和を算出し、レジスタＲ６に格納する（ステップＳ２５）。
【００６２】
このようにしてＦＩ関数の出力データがレジスタＲ６に格納される。
【００６３】
実際に、テーブルＳ９Ｆ及びＳ７Ｆと、図１４で示したような処理をプロセッサに実行させるためのプログラムとを用いて実装する際には、例えば図１５に示すような構成となる。
【００６４】
図１５の暗号装置１は、プロセッサ１０と、ＲＡＭ１１と、ＲＯＭ１２とを有する。プロセッサ１０とＲＡＭ１１及びＲＯＭ１２とはバスで接続されている。ＲＡＭ１１には、平文データ、暗号文データ、秘密鍵データ、拡大鍵データなどが格納される。但し、ＦＩ関数のためのテーブルは格納されない。また、ＲＯＭ１２は、図１４で示したような処理を含むＭＩＳＴＹ１等の暗号処理をプロセッサ１０に実行させるための暗号コードが格納される暗号コード領域と、上で述べたテーブルＳ９Ｆ及びＳ７Ｆを含む暗号テーブルを格納する暗号テーブル格納領域を含む。
【００６５】
なお、プロセッサ１０とＲＯＭ１２とが一体の半導体チップの場合もある。同様に、プロセッサ１０とＲＯＭ１２とＲＡＭ１１とが一体の半導体チップの場合もある。
【００６６】
ＭＩＳＴＹ１を図１５のような暗号装置１で実装すると、図１６に示すような機能が実現される。すなわち、秘密鍵から拡大鍵を生成する拡大鍵生成関数１０１と、拡大鍵を用いて平文を暗号文に暗号化するラウンド処理を実施する暗号化関数１０３と、暗号化関数１０３から呼び出されて演算結果を返すＦＯ関数１０５及びＦＬ関数１０７と、拡大鍵生成関数１０１及びＦＯ関数１０５から呼び出されて演算結果を返すＦＩ関数１０９とが実現される。ＦＩ関数１０９は、上で述べたようなテーブルＳ９Ｆ及びＳ７Ｆを用いて演算を実施する。
【００６７】
図１４に示したような処理をプロセッサに実行させるためのプログラムを作成すると、ＦＩ関数１個につき、１２サイクルかかる。ＭＩＳＴＹ１ではＦＩ関数が２４個あるので、ラウンド処理全体では２８８サイクル必要となる。
【００６８】
一方、拡大鍵生成処理でもＦＩ関数が用いられるが、ＫＩijをそのまま用いるので事前処理は不要で、拡大鍵生成処理全体では１２サイクル×８＝９６サイクル必要となる。
【００６９】
また、ＲＯＭサイズについては、テーブルＳ９Ｆとして１ＫＢ必要で、テーブルＳ７Ｆとして２５６Ｂ必要であるから、全体として１２８０Ｂ必要となる。当然、ＦＩ関数のためにＲＡＭに事前計算テーブルを保持する必要はない。
【００７０】
従来技術との効果比較表を図１７に示す。本実施例は、ＲＡＭに格納すべきテーブルのサイズが０という条件であれば、ＲＯＭに格納すべきテーブルのサイズは最小となっている。なお、処理サイクル（暗号化処理（ラウンド処理）＋拡大鍵生成処理）も、従来技術に比して高速処理となっている。
【００７１】
なお、上で述べたようなプログラムで実装するだけではなく、例えばＦＩ関数１０９並びにテーブルＳ９Ｆ及びＳ７Ｆをハードウエアで実装する場合もある。ハードウエアでの実装例を図１８に示す。
【００７２】
ハードウエアによるＦＩ関数演算部は、セレクタ１乃至４と、排他的論理和演算部２０１及び２０３と、レジスタ２０５とを有する。
【００７３】
セレクタ１には、入力Ｚの上位９ビットと、レジスタ２０５に格納されている値の下位９ビットとが入力されており、いずれかが選択されるようになっている。また、セレクタ１の出力でもって、テーブルＳ９Ｆから該当するデータを読み出すようになっており、テーブルＳ９Ｆの出力はセレクタ２に入力されている。
【００７４】
また、入力Ｚの下位７ビットでもって、テーブルＳ７Ｆから該当するデータを読み出すようになっており、テーブルＳ７Ｆの出力は、セレクタ３に入力されている。
【００７５】
さらに、セレクタ２には、テーブルＳ９Ｆの出力と、レジスタ２０５に格納されている値の上位７ビットに対して当該上位７ビットの上位に０を挿入して生成される９ビットのデータを下位に連結したデータとが入力されている。
【００７６】
また、セレクタ３には、テーブルＳ７Ｆの出力と、テーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値とが入力されている。
【００７７】
さらに、セレクタ４には、入力拡大鍵と、１６ビットの０とが入力されている。
【００７８】
排他的論理和演算部２０１には、セレクタ２の出力とセレクタ３の出力とが入力されており、排他的論理和演算部２０１の出力は排他的論理和演算部２０３に入力されている。
【００７９】
また、排他的論理和演算部２０３には、排他的論理和演算部２０１の出力とセレクタ４の出力とが入力されており、排他的論理和演算部２０３の出力はレジスタ２０５に格納される。
【００８０】
そして、第１のサイクルにおいて、セレクタ１では入力Ｚの上位９ビットが選択され、セレクタ２ではテーブルＳ９Ｆの出力が選択され、セレクタ３ではテーブルＳ７Ｆの出力が選択され、セレクタ４では、入力拡大鍵が選択される。
【００８１】
すなわち、入力Ｚの上位９ビットがセレクタ１で選択されて、当該入力Ｚの上位９ビットでもってテーブルＳ９Ｆから該当するデータを読み出す。そして、テーブルＳ９Ｆの出力は、セレクタ２で選択される。また、入力Ｚの下位７ビットでもってテーブルＳ７Ｆから該当するデータを読み出して、当該セレクタ３でテーブルＳ７Ｆの出力が選択される。さらに、セレクタ２とセレクタ３の出力は、排他的論理和演算部２０１でそれらの排他的論理和が算出される。セレクタ４では拡大鍵ＫＩijで選択され、当該拡大鍵ＫＩijと排他的論理和演算部２０１の出力とが、排他的論理和演算部２０３でそれらの排他的論理和が算出され、レジスタ２０５に格納される。
【００８２】
第１のサイクル後の第２のサイクルにおいては、セレクタ１ではレジスタ２０５に格納されている値の下位９ビットが選択され、セレクタ２では、レジスタ２０５に格納されている値の上位７ビットに対して当該上位７ビットの上位に０を挿入して生成される９ビットのデータを下位に連結したデータが選択され、セレクタ３では、テーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値が選択され、セレクタ４では、１６ビットの０が選択される。
【００８３】
そうすると、レジスタ２０５に格納されている値の下位９ビットでもってテーブルＳ９Ｆから該当するデータを読み出す。このテーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値は、セレクタ３で選択される。セレクタ２では、レジスタ２０５に格納されている値の上位７ビットに対して当該上位７ビットの上位に０を挿入して生成される９ビットのデータを下位に連結したデータが選択される。そして、このデータと、テーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値とは、排他的論理和演算部２０１に入力されて、それらの排他的論理和が算出される。さらに、セレクタ４では、１６ビットの０が選択されるので、排他的論理和演算部２０３では排他的論理和演算部２０１の出力がそのままレジスタ２０５に格納され、当該レジスタ２０５に格納されている値が、最終的なＦＩ関数の出力Ｒとなる。
【００８４】
このようなハードウエアで実装する場合にも、テーブルＳ９Ｆ及びＳ７Ｆを有効に活用することができる。
【００８５】
以上本技術の実施の形態について説明したが、本技術はこれに限定されるものではない。
【００８６】
例えば、ＭＩＳＴＹ１を前提に説明してきたが、ＦＩ関数を利用する他の暗号方式、例えばＭＩＳＴＹ２にも適用可能である。さらに、類似のＦＩ関数を利用するＫＡＳＵＭＩ暗号方式にも応用可能である。
【００８７】
また、図１８に示したハードウエア構成は一例であって、テーブルＳ９Ｆ及びＳ７Ｆを用いる他の実装方式でも良い。
【００８８】
さらに、図１４のＦＩ３関連処理については、図１９に示すように変形することができる。すなわち、プロセッサは、レジスタＲ１の上位７ビットをビット位置をシフトさせずに取り出し（Ｒ１＆０ｘＦＥ００と表す）、レジスタＲ６に格納する（ステップＳ３１）。そして、プロセッサは、レジスタＲ６の値と当該レジスタＲ６を右に９ビットシフトした値との排他的論理和を算出し、結果をレジスタＲ６に格納する（ステップＳ３３）。これでも図１４のＦＩ３関連処理と等価な処理である。また、高速処理が可能である。
【００８９】
同様に、図２０に示すような処理に変形することも可能である。すなわち、プロセッサは、レジスタＲ１の上位７ビットをビット位置をシフトさせずに取り出し、レジスタＲ６に格納する（ステップＳ４１）。そして、プロセッサは、レジスタＲ５の値とレジスタＲ６の値との排他的論理和を算出し、結果をレジスタＲ５に格納する（ステップＳ４３）。さらに、プロセッサは、レジスタＲ６の値を右に９ビットシフトした値を、レジスタＲ６に戻す（ステップＳ４５）。これでも図１４のＦＩ３関連処理と等価な処理である。
【００９０】
本実施の形態をまとめると以下のようになる。
【００９１】
本暗号装置は、第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置である。そして、本暗号装置は、（Ａ−１）９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と第１の出力との排他的論理和の値を、全ての第１の入力Ｘについて格納した第１の変換テーブル（図２１：５１１）と、（Ａ−２）７＊ｎビットの第２の入力Ｙに対する第２の非線形関数Ｓ７の第２の出力と第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と第２の入力Ｙとの排他的論理和の値を、全ての第２の入力Ｙについて格納した第２の変換テーブル（図２１：５１２）とを記録している読み出し専用メモリ（図２１：５１０）と、（Ｂ）読み出し専用メモリに記録されている第１の変換テーブルを２度用い、読み出し専用メモリに記録されている第２の変換テーブルを１度用いて、ＦＩ関数の１回の演算を行うＦＩ関数演算部（図２１：５００）とを有する。
【００９２】
ＭＩＳＴＹ１やＭＩＳＴＹ２のようにＦＩ関数に従った演算を行う暗号において、上で述べたような第１の変換テーブル及び第２の変換テーブルを用意することによって、ＲＡＭを用いずにＲＯＭサイズを少なくすることができる。
【００９３】
また、上で述べたＦＩ関数演算部が、（ｂ１）第３の入力の上位９＊ｎビットを第１の入力Ｘとして第１の変換テーブルから該当する第１のデータを読み出し、（ｂ２）第３の入力の下位７＊ｎビットを第２の入力Ｙとして第２の変換テーブルから該当する第２のデータを読み出し、（ｂ３）第１のデータと第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は第１のデータと入力拡大鍵との排他的論理和にさらに第２のデータの排他的論理和を算出して第３データを生成し、（ｂ４）第３データの下位９＊ｎビットを第１の入力Ｘとして第１の変換テーブルから該当する第４のデータを読み出し、第４のデータの下位９＊ｎビットを取り出して第５のデータを生成し、（ｂ５）第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成し、（ｂ６）第５のデータと前記第６のデータとの排他的論理和を算出するようにしてもよい。
【００９４】
このように第１及び第２の変換テーブルを導入しても必要な演算サイクルはあまり増加せずに済む。ステップ（ｂ５）は様々な等価な実現方法が可能である。
【００９５】
さらに、本暗号装置は、拡大鍵生成部と、暗号化処理部とを有するようにしてもよい。そして、拡大鍵生成部及び暗号化処理部とが、ＦＩ関数演算部に対してＦＩ関数の演算を要求し、ＦＩ関数演算部から演算結果を受け取るようにしてもよい。例えばＭＩＳＴＹ１やＭＩＳＴＹ２では、拡大鍵生成処理においてもＦＩ関数が必要となるので、第１及び第２の変換テーブルが有効に利用される。
【００９６】
また、上で述べたＦＩ関数演算部が、第１乃至第４のセレクタと、第１及び第２の排他的論理和演算部と、レジスタとを有するようにしてもよい。このような場合には、（ｄ１）第１のセレクタには、第３の入力の上位９＊ｎビットと、レジスタに格納されている値の下位９＊ｎビットとが入力されており、（ｄ２）第１のセレクタの出力を、第１の入力Ｘとして第１の変換テーブルから該当する第１のデータを読み出すようになっており、（ｄ３）第３の入力の下位７＊ｎビットを、第２の入力Ｙとして第２の変換テーブルから該当する第２のデータを読み出すようになっており、（ｄ４）第２のセレクタには、第１のデータと、レジスタに格納されている値の上位７＊ｎビットに対して当該上位７＊ｎビットの上位に０を挿入して生成される９＊ｎビットのデータを下位に連結した第３データとが入力されており、（ｄ５）第３のセレクタには、第２のデータと、第１のデータの下位９＊ｎビットに対して７＊ｎビットの０を上位に連結した第４のデータとが入力されており、（ｄ６）第４のセレクタには、入力拡大鍵と、１６＊ｎビットの０とが入力されており、（ｄ７）第１の排他的論理和演算部は、第２のセレクタの出力と第３のセレクタの出力とについて排他的論理和を演算して第５のデータを生成し、（ｄ８）第２の排他的論理和演算部は、第５のデータと第４のセレクタの出力とについて排他的論理和を演算して第６のデータを生成し、レジスタに格納するようにしてもよい。そして、第１のサイクルでは、第１のセレクタでは第３の入力の上位９＊ｎビットが選択され、第２のセレクタでは第１のデータが選択され、第３のセレクタでは第２のデータが選択され、第４のセレクタでは、入力拡大鍵が選択されるようにしてもよい。また、第２のサイクルでは、第１のセレクタではレジスタに格納されている値の下位９＊ｎビットが選択され、第２のセレクタでは第３のデータが選択され、第３のセレクタでは第４のデータが選択され、第４のセレクタでは上記１６＊ｎビットの０が選択されるようにしてもよい。
【００９７】
このようにハードウエアで実装する場合においても第１及び第２の変換テーブルを利用するような構成を採用することができる。
【００９８】
なお、第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を実行する暗号方法（図２２）は、（Ａ）入力Ｚを受け取るステップと、（Ｂ）（ｂ１）９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、（ｂ２）７＊ｎビットの第２の入力Ｙに対する第２の非線形関数Ｓ７の第２の出力と第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている第１の変換テーブルにアクセスして、入力Ｚの上位９＊ｎビットである第１の入力Ｘに該当する第１のデータを読み出すステップと、（Ｃ）読み出し専用メモリに記録されている第２の変換テーブルにアクセスして、入力Ｚの下位７＊ｎビットである第２の入力Ｙに該当する第２のデータを読み出すステップと、（Ｄ）第１のデータと第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は第１のデータと入力拡大鍵との排他的論理和にさらに第２のデータの排他的論理和を算出して第３データを生成するステップと、（Ｅ）読み出し専用メモリに記録されている第１の変換テーブルにアクセスして、第３データの下位９＊ｎビットである第１の入力Ｘに該当する第４のデータを読み出し、第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、（Ｆ）第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、（Ｇ）第５のデータと第６のデータとの排他的論理和を算出するステップとを含む。
【００９９】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【０１００】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１０１】
（付記１）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置であって、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を記録している読み出し専用メモリと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルを２度用い、前記読み出し専用メモリに記録されている前記第２の変換テーブルを１度用いて、前記ＦＩ関数の１回の演算を行うＦＩ関数演算部と、
を有する暗号装置。
【０１０２】
（付記２）
前記ＦＩ関数演算部が、
第３の入力の上位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出し、
前記第３の入力の下位７＊ｎビットを前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出し、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成し、
前記第３データの下位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成し、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成し、
前記第５のデータと前記第６のデータとの排他的論理和を算出する
付記１記載の暗号装置。
【０１０３】
（付記３）
拡大鍵生成部と、
暗号化処理部と
を有し、
前記拡大鍵生成部及び前記暗号化処理部とが、前記ＦＩ関数演算部に対して前記ＦＩ関数の演算を要求し、前記ＦＩ関数演算部から演算結果を受け取る
付記１又は２記載の暗号装置。
【０１０４】
（付記４）
前記ＦＩ関数演算部が、
第１乃至第４のセレクタと、
第１及び第２の排他的論理和演算部と、
レジスタと、
を有しており、
前記第１のセレクタには、第３の入力の上位９＊ｎビットと、前記レジスタに格納されている値の下位９＊ｎビットとが入力されており、
前記第１のセレクタの出力を、前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出すようになっており、
前記第３の入力の下位７＊ｎビットを、前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出すようになっており、
前記第２のセレクタには、前記第１のデータと、前記レジスタに格納されている値の上位７＊ｎビットに対して当該上位７＊ｎビットの上位に０を挿入して生成される９＊ｎビットのデータを下位に連結した第３データとが入力されており、
前記第３のセレクタには、前記第２のデータと、前記第１のデータの下位９＊ｎビットに対して７＊ｎビットの０を上位に連結した第４のデータとが入力されており、
前記第４のセレクタには、入力拡大鍵と、１６＊ｎビットの０とが入力されており、
前記第１の排他的論理和演算部は、前記第２のセレクタの出力と前記第３のセレクタの出力とについて排他的論理和を演算して第５のデータを生成し、
前記第２の排他的論理和演算部は、前記第５のデータと前記第４のセレクタの出力とについて排他的論理和を演算して第６のデータを生成し、前記レジスタに格納し、
第１のサイクルでは、前記第１のセレクタでは前記第３の入力の上位９＊ｎビットが選択され、前記第２のセレクタでは前記第１のデータが選択され、前記第３のセレクタでは前記第２のデータが選択され、前記第４のセレクタでは、前記入力拡大鍵が選択され、
第２のサイクルでは、前記第１のセレクタでは前記レジスタに格納されている値の下位９＊ｎビットが選択され、前記第２のセレクタでは前記第３のデータが選択され、前記第３のセレクタでは前記第４のデータが選択され、前記第４のセレクタでは前記１６＊ｎビットの０が選択される
付記１乃至３のいずれか１つ記載の暗号装置。
【０１０５】
（付記５）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムであって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を実行させるための暗号プログラム。
【０１０６】
（付記６）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を実行する暗号方法であって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を含み、プロセッサに実行される暗号方法。
【０１０７】
（付記７）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を格納しており
前記暗号プログラムが、
入力Ｚを受け取るステップと、
前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
をプロセッサに実行させるための暗号プログラム
であるメモリ。
【０１０８】
（付記８）
前記メモリを有する付記７記載のプロセッサ。
【符号の説明】
【０１０９】
１０１ 拡大鍵生成関数 １０３ 暗号化関数
１０５ ＦＯ関数 １０７ ＦＬ関数
１０９ ＦＩ関数
１０ プロセッサ １１ ＲＡＭ
１２ ＲＯＭ
【技術分野】
【０００１】
本技術は、ＦＩ関数を利用する暗号技術に関する。
【背景技術】
【０００２】
共通鍵暗号方式の１つであるＭＩＳＴＹ１（詳細は、松井充:ブロック暗号アルゴリズムMISTY, 信学技報, ISEC96-11(1996-07)等を参照のこと）については、様々な実装方式が検討されている。
【０００３】
図１にＭＩＳＴＹ１を含む共通鍵暗号方式の構成の一例を示す。ＭＩＳＴＹ１に係る共通鍵暗号処理はラウンド処理と拡大鍵生成処理の２つの処理を含む。図１に示すように、拡大鍵生成処理は、入力された秘密鍵から複数の拡大鍵（図１では、拡大鍵０、拡大鍵１、．．．、拡大鍵Ｎ）を生成する。生成された拡大鍵は、暗号化処理（ラウンド処理とも呼ぶ）で使用される。暗号化処理は、平文（すなわち暗号化対象データ）を一定のビット長（すなわちブロック長）ごとに区切り、区切った各ブロックに対してラウンド処理を実施し、暗号文を生成する。復号の際には、暗号化処理と逆の演算を行う。
【０００４】
共通鍵暗号方式ＭＩＳＴＹ１は、秘密鍵長が１２８ビット、ブロック長６４ビットを暗号化単位とするアルゴリズムである。
【０００５】
図２に、ＭＩＳＴＹ１のラウンド処理部の構成を示す。図２に示すように、平文Ｐ（６４ビット）を暗号文Ｃ（６４ビット）に変換するラウンド処理部では、ＦＬ関数が１０回実行され、ＦＯ関数が８回実行される。
【０００６】
ｉ番目のＦＯ関数は、図３に示すような構成を有する。ＦＯ関数には、ＫＯi1、ＫＯi2、ＫＯi3及びＫＯi4（各１６ビット）が入力されるようになっている。これらは、秘密鍵１２８ビットを１６ビット毎に分割することによって得られるＫ１乃至Ｋ８のうち４つである。Ｋ１乃至Ｋ８のいずれが用いられるかは、ラウンド値ｉ（ＦＯiのｉの値）に基づきアルゴリズム仕様書に従って決定される。
【０００７】
また、ｉ番目のＦＯ関数では、ＦＩ関数が３回実行される。そして、ＦＩi1関数には、ＫＩi1が入力され、ＦＩi2関数には、ＫＩi2が入力され、ＦＩi3関数には、ＫＩi3が入力される。ＫＩi1乃至ＫＩi3は、１６ビットの値であり、拡大鍵生成アルゴリズムにて生成したＫ'1乃至Ｋ'8のうち３つである。Ｋ'1乃至Ｋ'8のいずれを用いるかは、ラウンド値ｉ（ＦＯiのｉの値）に基づきアルゴリズム仕様書に従って決定される。
【０００８】
ｉ番目のＦＯ関数におけるｊ番目のＦＩ関数の構成を図４に示す。ＦＩ関数は、入力１６ビットの上位９ビットを非線形関数Ｓ９（入力データを決められたアルゴリズム（論理演算の繰り返し）に従って攪拌して出力する関数）に入力して、関数Ｓ９の出力と、入力１６ビットの下位７ビットの上位２ビットに０を追加した（0-extensionと記す）値との排他的論理和を算出して、データａを生成する。また、入力１６ビットの下位７ビットを非線形関数Ｓ７（入力データを決められたアルゴリズム（論理演算の繰り返し）に従って攪拌して出力する関数）に入力して、関数Ｓ７の出力と、データａの上位２ビットを除去した（truncateと記す）値との排他的論理和を算出して、データｂを生成する。さらに、データｂとＫＩijL（ＫＩijの上位７ビット）との排他的論理和を算出し、データｃを生成する。また、データａとＫＩijR（ＫＩijの下位９ビット）との排他的論理和を算出し、データｄを生成する。データｄは、再度非線形関数Ｓ９に入力され、さらに関数Ｓ９の出力とデータｄの上位２ビットに０を追加した値との排他的論理和を算出して、データｅを生成する。そして、最終的にデータｃを上位７ビットとし、データｅを下位９ビットとして連結すれば、１６ビットの出力となる。
【０００９】
次に図５に、ＭＩＳＴＹ１の拡大鍵生成部の構成を示す。拡大鍵生成部では、１２８ビットの秘密鍵を１６ビット毎に分割して、先頭からＫ１乃至Ｋ８を生成する。図５で示すように、Ｋ８を入力としてＫ１をＫＩijとしてＦＩ関数で拡大鍵Ｋ'8を生成する。Ｋ７を入力としてＫ８をＫＩijとしてＦＩ関数で拡大鍵Ｋ'7を生成する。Ｋ６を入力としてＫ７をＫＩijとしてＦＩ関数で拡大鍵Ｋ'6を生成する。Ｋ５を入力としてＫ６をＫＩijとしてＦＩ関数で拡大鍵Ｋ'5を生成する。Ｋ４を入力としてＫ５をＫＩijとしてＦＩ関数で拡大鍵Ｋ'4を生成する。Ｋ３を入力としてＫ４をＫＩijとしてＦＩ関数で拡大鍵Ｋ'3を生成する。Ｋ２を入力としてＫ３をＫＩijとしてＦＩ関数で拡大鍵Ｋ'2を生成する。Ｋ１を入力としてＫ２をＫＩijとしてＦＩ関数で拡大鍵Ｋ'1を生成する。
【００１０】
このように、ＭＩＳＴＹ１をソフトウエア又はハードウエアで実装する際には、ＦＩ関数の実装方法が重要となる。なぜなら、ＦＩ関数はラウンド処理部及び拡大鍵生成部の双方で使用される処理であり、ＦＩ関数を効率的に処理することが可能となれば、ＭＩＳＴＹ１の処理性能が大きく向上する。
【００１１】
ＦＩ関数の従来実装法については日本特許第３９１７３５７号公報に幾つか示されている。
【００１２】
図６及び図７に上記特許公報に開示されている第１の実装例を示す。本実装例では、図４のアルゴリズムを図６に示すようなアルゴリズムに等価変換した上で、非線形関数Ｓ９の処理１００１と、非線形関数Ｓ７を含む処理１００３と、非線形関数Ｓ９を含む処理１００５とをテーブル化する。但し、処理１００１と処理１００５とは異なる。その結果として、図７に示すように、処理１００１がテーブルＴ１に置換され、処理１００３がテーブルＴ４に置換され、処理１００５がテーブルＴ５に置換される。これらのテーブルは、ＲＯＭに格納され、必要なときに参照される。
【００１３】
なお、一例として、Ｋ'1を使用するＦＩ関数については、ＫＩijＲとＫＩijＬ'とは以下のように生成される。
ＫＩijＲ＝Ｋ'1 ＆ 0x1FF
tmpk1＝Ｋ'1 ＆ 0xFE00
tmpk2＝ＫＩijＲ ＆ 0x7F
tmpk3＝tmpk2 ＜＜ 9
tmpk4＝tmpk3 ＋ tmpk1
tmpk5＝tmpk4 ＞＞ 9
ＫＩijＬ'＝tmpk5 ＋ tmpk4
【００１４】
テーブルＴ１、テーブルＴ４及びテーブルＴ５は以下のように定義される。なお、Ｘは入力である。また、全ての取り得るＸ値についてテーブルエントリを生成する。
Ｔ１（Ｘ）＝Ｓ９（Ｘ）
Ｔ５（Ｘ）＝（（Ｘ＆0x7F）＜＜９）＋（Ｘ＆0x7F）＋Ｓ９（Ｘ）
Ｔ４（Ｘ）＝（Ｓ７（Ｘ）＜＜９）＋Ｓ７（Ｘ）
「＜＜９」は左シフトで、「＞＞９」は右シフトで、Ｘ＆０ｘ７ＦはＸの下位７ビットを抽出するものである。
【００１５】
このような実装方法では、テーブルＴ１のサイズが１ＫＢで、テーブルＴ４のサイズが１ＫＢで、テーブルＴ５のサイズが２５６Ｂで、合計２３０４ＢのＲＯＭテーブルサイズが必要となる。但し、ＲＡＭは必要ない。
【００１６】
また、本実装例では、ＦＩ関数１つあたり９サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理全体では２１６サイクルかかる。
【００１７】
一方、拡大鍵生成処理では、ＫＩijＲ及びＫＩijＬ'に相当するデータの事前計算のための７サイクルと、ＦＩ関数の９サイクルと、Ｋ'iについてラウンド処理のためのＫＩijＲ及びＫＩijＬ'を生成する処理のための７サイクルとが、８つのＦＩ関数で必要となる。従って、拡大鍵生成処理全体では、（７＋９＋７）＊８＝１８４サイクル必要となる。
【００１８】
なお、ラウンド処理の処理時間を「ＦＩ関数１回に必要なサイクル数×８」として計算する。なお、ラウンド処理には、ＦＩ関数以外にもＦＬ関数や、ＦＯ関数における拡大鍵との排他的論理和（ＸＯＲ）のためのサイクル数が必要となる。しかしながら、これらの処理は負荷が軽く必要サイクル数が少ないため、処理時間見積りの対象には含めないこととする。
【００１９】
さらに、図８及び図９に上記特許公報に開示されている第２の実装例を示す。図８に示すように、図７に示した第１の実装例において、ＫＩijＲとの排他的論理和及びテーブルＴ５の部分１１０１を、テーブル化する。すなわち、図９に示すように、テーブルＴ５ｊを導入する。
【００２０】
但し、ＫＩijＲは拡大鍵Ｋ'iを基に生成されるデータであり、ユーザが秘密鍵を暗号装置に入力して初めて値が特定できるものである。従って、テーブルＴ５ｊを、ユーザによる秘密鍵入力前に計算しておくことはできず、必ず入力後に計算することとなる。すなわち、テーブルＴ５ｊをＲＯＭには保持できず、ＲＡＭに保持する必要がある。
【００２１】
テーブルＴ１及びＴ４は、上で述べたとおりであり、事前にＸの取り得る全ての値について事前に計算して、ＲＯＭに記録しておく。一方、テーブルＴ５ｊについては、以下のような式で算出される。但し、ユーザによる秘密鍵の入力後に、取り得る入力パターンについて全て計算した後に、ＲＡＭに保持しておく。
Ｔ５ｊ（Ｘ）＝（（（Ｘ＋ＫＩijＲ）＆ 0x7F）＜＜９）＋（（Ｘ＋ＫＩjiＲ）＆0x7F）＋Ｓ９（Ｘ）
【００２２】
このような実装方法では、テーブルＴ１のサイズが１ＫＢで、テーブルＴ４のサイズが２５６Ｂで、合計１２８０ＢのＲＯＭテーブルサイズが必要となる。また、テーブルＴ５をＲＡＭに保持するので、そのサイズは１ＫＢとなる。
【００２３】
この実装例では、ＦＩ関数１つあたり８サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理全体では１９２サイクルかかる。
【００２４】
一方、拡大鍵生成処理では、テーブルＴ５ｊの生成も同時に行う必要がある。このテーブルの生成には１５３６サイクル以上必要になり、その他の拡大鍵生成処理を含めると、全体では１６００サイクル以上必要となる。
【００２５】
さらに、図１０及び図１１に上記特許公報に開示されている第３の実装例を示す。図１０に示すように、図９に示した第２の実装例において、ＫＩijＬ'との排他的論理和及びテーブルＴ４の部分１２０１を、テーブル化する。すなわち、図１１に示すように、テーブルＴ４ｊを導入する。
【００２６】
但し、ＫＩijＬ'は拡大鍵Ｋ'iを基に生成されるデータであり、ユーザが秘密鍵を暗号装置に入力して初めて値が特定できるものである。従って、テーブルＴ４ｊを、ユーザによる秘密鍵入力前に計算しておくことはできず、必ず入力後に計算することとなる。すなわち、テーブルＴ４ｊをＲＯＭには保持できず、ＲＡＭに保持する必要がある。
【００２７】
テーブルＴ１は、上で述べたとおりであり、事前にＸの取り得る全ての値について事前に計算して、ＲＯＭに記録しておく。テーブルＴ５ｊについても、上で述べたとおりであり、ＲＡＭに保持しておく。さらに、テーブルＴ４ｊに格納されるデータは、以下のような式で計算される。但し、ユーザによる秘密鍵の入力後に、取り得る入力パターンについて全て計算した後に、ＲＡＭに保持しておく。
Ｔ４ｊ（Ｘ）＝（Ｓ７（Ｘ）＜＜９）＋Ｓ７（Ｘ）＋ＫＩijＬ'
【００２８】
このような実装方法では、テーブルＴ１のサイズが１ＫＢで、テーブルＴ４ｊのサイズは事前計算用に少なくとも１２８Ｂで、合計１１５２Ｂ以上のＲＯＭテーブルサイズが必要となる。一方、テーブルＴ４ｊ及びＴ５ｊについてはＲＡＭに保持することになるが、サイズは１２８０Ｂとなる。
【００２９】
さらに、この実装例では、ＦＩ関数１つあたり７サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理全体では１６８サイクルかかる。
【００３０】
一方、拡大鍵生成処理では、テーブルＴ４ｊ及びＴ５ｊの生成も同時に行う必要がある。このテーブルの生成には１９２０サイクル以上必要になり、その他の拡大鍵生成処理を含めると、全体では２０００サイクル以上必要となる。
【００３１】
さらに、論文（中嶋純子、松井充: ＭＩＳＴＹのソフトウエアによる高速実装法について (II) SCIS98-9.1B）には、他の実装例が示されている。これについて図１２を用いて説明する。この実装例では、図４に示したＦＩ関数を図１２に示すような形に等価変換している。図１２の例では、非線形関数Ｓ９及びＳ７を含む上段部分をテーブルＴ７に変換し、ＫＩijとの排他的論理和以外で非線形関数Ｓ９を含む下段部分をテーブルＴ８に変換している。
【００３２】
このような実装例では、テーブルＴ７のサイズは１３１０７２Ｂであり、テーブルＴ８のサイズは１３１０７２Ｂであり、合計２６２１４４Ｂ必要となる。なお、ＲＡＭは必要ない。
【００３３】
このような実装例では、ＦＩ関数１つあたり３サイクルかかり、ＦＩ関数が２４個あるので、ラウンド処理については７２サイクルかかる。ＫＩijについてはそのまま用いるので、ＦＩ関数が８個分で拡大鍵生成処理には２４サイクル必要となる。
【先行技術文献】
【特許文献】
【００３４】
【特許文献１】日本特許第３９１７３５７号公報
【非特許文献】
【００３５】
【非特許文献１】中嶋純子、松井充: ＭＩＳＴＹのソフトウエアによる高速実装法について (II) SCIS98-9.1B
【非特許文献２】松井充:ブロック暗号アルゴリズムMISTY, 信学技報, ISEC96-11(1996-07)
【発明の概要】
【発明が解決しようとする課題】
【００３６】
ＭＩＳＴＹ１などは組み込み機器に実装する場合もあるので、ＲＡＭ使用量が少ないこと、ＲＯＭサイズが小さいこと、処理速度が高速であることが必要となる。特にＲＡＭについては極力使用量が少ないことが求められ、事前計算テーブルをＲＡＭに保持する手法は組み込み機器環境には向いていない。また、ＲＯＭについても極力サイズが小さいことが求められる。しかし、単純にＲＯＭに格納するテーブルを削減してしまうと、処理速度が著しく低下し、処理速度が不十分となる。
【００３７】
従って、本技術の目的は、暗号装置で用いられるＦＩ関数を実装する上で、ＲＯＭに格納するテーブルのサイズを小さくするための技術を提供することである。
【課題を解決するための手段】
【００３８】
本暗号装置は、第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置である。そして、本暗号装置は、（Ａ−１）９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と第１の出力との排他的論理和の値を、全ての第１の入力Ｘについて格納した第１の変換テーブルと、（Ａ−２）７＊ｎビットの第２の入力Ｙに対する第２の非線形関数Ｓ７の第２の出力と第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と第２の入力Ｙとの排他的論理和の値を、全ての第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリと、（Ｂ）読み出し専用メモリに記録されている第１の変換テーブルを２度用い、読み出し専用メモリに記録されている第２の変換テーブルを１度用いて、ＦＩ関数の１回の演算を行うＦＩ関数演算部とを有する。
【発明の効果】
【００３９】
暗号装置で用いられるＦＩ関数を実装する上で、ＲＯＭに格納するテーブルのサイズを小さくすることができる。
【図面の簡単な説明】
【００４０】
【図１】図１は、共通鍵暗号方式ＭＩＳＴＹ１の構成例を示す図である。
【図２】図２は、ラウンド処理のアルゴリズムを示す図である。
【図３】図３は、ＦＯ関数のアルゴリズムを示す図である。
【図４】図４は、ＦＩ関数のアルゴリズムを示す図である。
【図５】図５は、拡大鍵生成処理のアルゴリズムを示す図である。
【図６】図６は、第１の従来実装例で行われる等価変換を示す図である。
【図７】図７は、第１の従来実装例のアルゴリズムを示す図である。
【図８】図８は、第２の従来実装例で行われる等価変換を示す図である。
【図９】図９は、第２の従来実装例のアルゴリズムを示す図である。
【図１０】図１０は、第３の従来実装例で行われる等価変換を示す図である。
【図１１】図１１は、第３の従来実装例のアルゴリズムを示す図である。
【図１２】図１２は、第４の従来実装例で行われる等価変換を示す図である。
【図１３】図１３は、本技術の実施の形態におけるＦＩアルゴリズムの等価変換を説明するための図である。
【図１４】図１４は、等価変換後の処理内容を説明するための図である。
【図１５】図１５は、プロセッサで処理を実施するような場合の構成を示す図である。
【図１６】図１６は、暗号装置の機能ブロック図である。
【図１７】図１７は、効果の比較表を示す図である。
【図１８】図１８は、ＦＩ関数をハードウエアで実施した場合の一例を示す図である。
【図１９】図１９は、ＦＩ３関連処理の他の例を示す図である。
【図２０】図２０は、ＦＩ３関連処理の他の例を示す図である。
【図２１】図２１は、暗号装置の機能ブロック図である。
【図２２】図２２は、暗号装置の処理フローを示す図である。
【発明を実施するための形態】
【００４１】
本技術の実施の形態では、図４に示したＦＩ関数のアルゴリズムを、図１３に示すように等価変換する。なお、以下では１６ビット入力の例を示すが、１６ビットの整数倍したビット長にも容易に変換できる。その際には、９ビット及び７ビットについても整数倍される。
【００４２】
図１３のアルゴリズムでは、１６ビット入力Ｚの上位９ビットを非線形関数Ｓ９に入力して、非線形関数Ｓ９の出力９ビットのうち下位７ビットを上位に非線形関数Ｓ９の出力９ビットをそのまま下位に配置して連結して第１のデータを生成する。ここまでの処理内容を、第１のテーブルＳ９Ｆに変換する。
【００４３】
また、１６ビット入力Ｚの下位７ビットを非線形関数Ｓ７に入力して、非線形関数Ｓ７の出力と入力Ｚの下位７ビットとの排他的論理和を算出して第２のデータを生成する。そして、第２のデータを上位に、入力Ｚの下位７ビットの上位に０を２ビット加えた値を下位に配置して連結して第３のデータを生成する。ここまでの処理内容を第２のテーブルＳ７Ｆに変換する。
【００４４】
さらに、第１のデータと第３のデータとの排他的論理和の結果と、ＫＩijとの排他的論理和を算出して第４のデータを生成する。
【００４５】
この第４のデータの下位９ビットを、非線形関数Ｓ９に入力して、非線形関数Ｓ９の出力９ビットのうち下位７ビットを上位に非線形関数Ｓ９の出力９ビットをそのまま下位に配置して連結して第５のデータを生成する。この部分は、第１のテーブルＳ９Ｆの元の処理と同じであり、第１のテーブルＳ９Ｆへの参照に置換できる。
【００４６】
そして、第４のデータの上位７ビットの上位に０を２ビット加えた値と第５のデータの下位９ビットとの排他的論理和の結果を下位に配置し、第４のデータの上位７ビットを上位に配置して、出力Ｒが生成される。
【００４７】
このような等価変換後のアルゴリズムにおいて、テーブルＳ９Ｆは、取り得る全ての入力Ｘについて、以下のような値Ｓ９Ｆ（Ｘ）が格納されているテーブルである。同様に、テーブルＳ７Ｆは、取り得る全ての入力Ｙについて、以下のような値Ｓ７Ｆ（Ｙ）が格納されているテーブルである。
Ｓ９Ｆ（Ｘ）＝（（Ｓ９（Ｘ）＆0x7F）＜＜９）＋Ｓ９（Ｘ）
Ｓ７Ｆ（Ｙ）＝（Ｓ７（Ｙ）＋Ｙ）＜＜９）＋Ｙ
上で述べたが、「＆0x7F」は、下位７ビットを抽出する処理を表し、「＜＜９」は９ビット左シフトを表す。なお「＋」は排他的論理和を表している。そして、Ａが７ビット、Ｂが９ビットであれば、（Ａ＜＜９）＋Ｂにて、Ａを上位ビット７ビットに配置してＢを下位ビット９ビットに配置するような処理となる。
【００４８】
従って、再度表せば、テーブルＳ９Ｆ（Ｘ）は、９ビットの入力Ｘに対する非線形変換処理Ｓ９の出力の下位７ビットを抽出し、当該出力の下位７ビットを９ビット左シフトした値と非線形関数の出力との排他的論理和の値を、各Ｘに対応付けて登録したテーブルである。
【００４９】
同様に、テーブルＳ７Ｆ（Ｙ）は、７ビットの入力Ｙに対する非線形関数Ｓ７の出力と入力Ｙとの排他的論理和の結果を９ビット左シフトし、当該排他的論理和の結果の９ビット左シフトした値と入力Ｙとの排他的論理和の値を、各Ｙに対応付けて登録したテーブルである。
【００５０】
このようなテーブルを採用すればＲＡＭに格納しなければならないテーブルは存在しない。
【００５１】
次に、このようなテーブルを用いたＦＩ関数の処理について、図１４を用いて説明する。
【００５２】
暗号装置のプロセッサ（すなわちＣＰＵ（Central Processing Unit））は、入力データを格納しているレジスタＲ０から上位９ビットを取り出し、レジスタＲ１に格納する（ステップＳ１）。そして、プロセッサは、テーブルＳ９Ｆから、レジスタＲ１に格納されている値に対応するアドレスのデータ（例えばＲ１値の順番のデータ）を読み出して、レジスタＲ１に格納する（ステップＳ３）。なお、ステップＳ１及びＳ３は、１回目のＳ９Ｆ処理と呼ぶ。
【００５３】
一方、プロセッサは、レジスタＲ０から下位７ビットを取り出し、レジスタＲ２に格納する（ステップＳ５）。さらに、プロセッサは、テーブルＳ７Ｆから、レジスタＲ２に格納されている値に対応するアドレスのデータ（例えばＲ２値の順番のデータ）を読み出して、レジスタＲ２に格納する（ステップＳ７）。なお、ステップＳ５及びＳ７は、Ｓ７Ｆ処理と呼ぶ。
【００５４】
１回目のＳ９Ｆ処理とＳ７Ｆ処理とは順番の入れ替えが可能であり、また複数コアを有するプロセッサであれば並列に実行しても良い。
【００５５】
そして、プロセッサは、レジスタＲ１のデータとレジスタＲ２のデータとの排他的論理和を算出し、結果をレジスタＲ１に格納する（ステップＳ９）。
【００５６】
また、プロセッサは、拡大鍵ＫＩijを読み出してレジスタＲ３に格納する（ステップＳ１１）。そして、プロセッサは、レジスタＲ１のデータとレジスタＲ３のデータとの排他的論理和を算出し、結果をレジスタＲ１に格納する（ステップＳ１３）。ステップＳ１１及びＳ１３は、拡大鍵加算処理である。
【００５７】
排他的論理和については順番は問われないので、ステップＳ９と拡大鍵加算処理については順番を入れ替えることが可能である。
【００５８】
さらに、プロセッサは、レジスタＲ１から下位９ビットを取り出し、レジスタＲ４に格納する（ステップＳ１５）。また、プロセッサは、テーブルＳ９ＦからレジスタＲ４に格納されている値に対応するアドレスのデータ（例えばＲ４値の順番のデータ）を読み出して、レジスタＲ４に格納する（ステップＳ１７）。さらに、プロセッサは、レジスタＲ４から下位９ビットを取り出して、レジスタＲ５に格納する（ステップＳ１９）。ステップＳ１５乃至Ｓ１９は、第２回目のＳ９Ｆ処理と呼ぶ。
【００５９】
また、プロセッサは、レジスタＲ１から上位７ビットを取り出し、レジスタＲ６に格納する（ステップＳ２１）。そして、プロセッサは、レジスタＲ６の値と当該レジスタＲ６を左に９ビットシフトした値との排他的論理和を算出し、結果をレジスタＲ６に格納する（ステップＳ２３）。ステップＳ２１及びＳ２３を、ＦＩ３関連処理と呼ぶ。
【００６０】
第２回目のＳ９Ｆ処理とＦＩ３関連処理とは順番の入れ替えが可能であり、また複数コアを有するプロセッサであれば並列に実行してもよい。
【００６１】
そして、最後にプロセッサは、レジスタＲ６の値とレジスタＲ５の値との排他的論理和を算出し、レジスタＲ６に格納する（ステップＳ２５）。
【００６２】
このようにしてＦＩ関数の出力データがレジスタＲ６に格納される。
【００６３】
実際に、テーブルＳ９Ｆ及びＳ７Ｆと、図１４で示したような処理をプロセッサに実行させるためのプログラムとを用いて実装する際には、例えば図１５に示すような構成となる。
【００６４】
図１５の暗号装置１は、プロセッサ１０と、ＲＡＭ１１と、ＲＯＭ１２とを有する。プロセッサ１０とＲＡＭ１１及びＲＯＭ１２とはバスで接続されている。ＲＡＭ１１には、平文データ、暗号文データ、秘密鍵データ、拡大鍵データなどが格納される。但し、ＦＩ関数のためのテーブルは格納されない。また、ＲＯＭ１２は、図１４で示したような処理を含むＭＩＳＴＹ１等の暗号処理をプロセッサ１０に実行させるための暗号コードが格納される暗号コード領域と、上で述べたテーブルＳ９Ｆ及びＳ７Ｆを含む暗号テーブルを格納する暗号テーブル格納領域を含む。
【００６５】
なお、プロセッサ１０とＲＯＭ１２とが一体の半導体チップの場合もある。同様に、プロセッサ１０とＲＯＭ１２とＲＡＭ１１とが一体の半導体チップの場合もある。
【００６６】
ＭＩＳＴＹ１を図１５のような暗号装置１で実装すると、図１６に示すような機能が実現される。すなわち、秘密鍵から拡大鍵を生成する拡大鍵生成関数１０１と、拡大鍵を用いて平文を暗号文に暗号化するラウンド処理を実施する暗号化関数１０３と、暗号化関数１０３から呼び出されて演算結果を返すＦＯ関数１０５及びＦＬ関数１０７と、拡大鍵生成関数１０１及びＦＯ関数１０５から呼び出されて演算結果を返すＦＩ関数１０９とが実現される。ＦＩ関数１０９は、上で述べたようなテーブルＳ９Ｆ及びＳ７Ｆを用いて演算を実施する。
【００６７】
図１４に示したような処理をプロセッサに実行させるためのプログラムを作成すると、ＦＩ関数１個につき、１２サイクルかかる。ＭＩＳＴＹ１ではＦＩ関数が２４個あるので、ラウンド処理全体では２８８サイクル必要となる。
【００６８】
一方、拡大鍵生成処理でもＦＩ関数が用いられるが、ＫＩijをそのまま用いるので事前処理は不要で、拡大鍵生成処理全体では１２サイクル×８＝９６サイクル必要となる。
【００６９】
また、ＲＯＭサイズについては、テーブルＳ９Ｆとして１ＫＢ必要で、テーブルＳ７Ｆとして２５６Ｂ必要であるから、全体として１２８０Ｂ必要となる。当然、ＦＩ関数のためにＲＡＭに事前計算テーブルを保持する必要はない。
【００７０】
従来技術との効果比較表を図１７に示す。本実施例は、ＲＡＭに格納すべきテーブルのサイズが０という条件であれば、ＲＯＭに格納すべきテーブルのサイズは最小となっている。なお、処理サイクル（暗号化処理（ラウンド処理）＋拡大鍵生成処理）も、従来技術に比して高速処理となっている。
【００７１】
なお、上で述べたようなプログラムで実装するだけではなく、例えばＦＩ関数１０９並びにテーブルＳ９Ｆ及びＳ７Ｆをハードウエアで実装する場合もある。ハードウエアでの実装例を図１８に示す。
【００７２】
ハードウエアによるＦＩ関数演算部は、セレクタ１乃至４と、排他的論理和演算部２０１及び２０３と、レジスタ２０５とを有する。
【００７３】
セレクタ１には、入力Ｚの上位９ビットと、レジスタ２０５に格納されている値の下位９ビットとが入力されており、いずれかが選択されるようになっている。また、セレクタ１の出力でもって、テーブルＳ９Ｆから該当するデータを読み出すようになっており、テーブルＳ９Ｆの出力はセレクタ２に入力されている。
【００７４】
また、入力Ｚの下位７ビットでもって、テーブルＳ７Ｆから該当するデータを読み出すようになっており、テーブルＳ７Ｆの出力は、セレクタ３に入力されている。
【００７５】
さらに、セレクタ２には、テーブルＳ９Ｆの出力と、レジスタ２０５に格納されている値の上位７ビットに対して当該上位７ビットの上位に０を挿入して生成される９ビットのデータを下位に連結したデータとが入力されている。
【００７６】
また、セレクタ３には、テーブルＳ７Ｆの出力と、テーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値とが入力されている。
【００７７】
さらに、セレクタ４には、入力拡大鍵と、１６ビットの０とが入力されている。
【００７８】
排他的論理和演算部２０１には、セレクタ２の出力とセレクタ３の出力とが入力されており、排他的論理和演算部２０１の出力は排他的論理和演算部２０３に入力されている。
【００７９】
また、排他的論理和演算部２０３には、排他的論理和演算部２０１の出力とセレクタ４の出力とが入力されており、排他的論理和演算部２０３の出力はレジスタ２０５に格納される。
【００８０】
そして、第１のサイクルにおいて、セレクタ１では入力Ｚの上位９ビットが選択され、セレクタ２ではテーブルＳ９Ｆの出力が選択され、セレクタ３ではテーブルＳ７Ｆの出力が選択され、セレクタ４では、入力拡大鍵が選択される。
【００８１】
すなわち、入力Ｚの上位９ビットがセレクタ１で選択されて、当該入力Ｚの上位９ビットでもってテーブルＳ９Ｆから該当するデータを読み出す。そして、テーブルＳ９Ｆの出力は、セレクタ２で選択される。また、入力Ｚの下位７ビットでもってテーブルＳ７Ｆから該当するデータを読み出して、当該セレクタ３でテーブルＳ７Ｆの出力が選択される。さらに、セレクタ２とセレクタ３の出力は、排他的論理和演算部２０１でそれらの排他的論理和が算出される。セレクタ４では拡大鍵ＫＩijで選択され、当該拡大鍵ＫＩijと排他的論理和演算部２０１の出力とが、排他的論理和演算部２０３でそれらの排他的論理和が算出され、レジスタ２０５に格納される。
【００８２】
第１のサイクル後の第２のサイクルにおいては、セレクタ１ではレジスタ２０５に格納されている値の下位９ビットが選択され、セレクタ２では、レジスタ２０５に格納されている値の上位７ビットに対して当該上位７ビットの上位に０を挿入して生成される９ビットのデータを下位に連結したデータが選択され、セレクタ３では、テーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値が選択され、セレクタ４では、１６ビットの０が選択される。
【００８３】
そうすると、レジスタ２０５に格納されている値の下位９ビットでもってテーブルＳ９Ｆから該当するデータを読み出す。このテーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値は、セレクタ３で選択される。セレクタ２では、レジスタ２０５に格納されている値の上位７ビットに対して当該上位７ビットの上位に０を挿入して生成される９ビットのデータを下位に連結したデータが選択される。そして、このデータと、テーブルＳ９Ｆの出力の下位９ビットに対して７ビットの０を上位に連結した値とは、排他的論理和演算部２０１に入力されて、それらの排他的論理和が算出される。さらに、セレクタ４では、１６ビットの０が選択されるので、排他的論理和演算部２０３では排他的論理和演算部２０１の出力がそのままレジスタ２０５に格納され、当該レジスタ２０５に格納されている値が、最終的なＦＩ関数の出力Ｒとなる。
【００８４】
このようなハードウエアで実装する場合にも、テーブルＳ９Ｆ及びＳ７Ｆを有効に活用することができる。
【００８５】
以上本技術の実施の形態について説明したが、本技術はこれに限定されるものではない。
【００８６】
例えば、ＭＩＳＴＹ１を前提に説明してきたが、ＦＩ関数を利用する他の暗号方式、例えばＭＩＳＴＹ２にも適用可能である。さらに、類似のＦＩ関数を利用するＫＡＳＵＭＩ暗号方式にも応用可能である。
【００８７】
また、図１８に示したハードウエア構成は一例であって、テーブルＳ９Ｆ及びＳ７Ｆを用いる他の実装方式でも良い。
【００８８】
さらに、図１４のＦＩ３関連処理については、図１９に示すように変形することができる。すなわち、プロセッサは、レジスタＲ１の上位７ビットをビット位置をシフトさせずに取り出し（Ｒ１＆０ｘＦＥ００と表す）、レジスタＲ６に格納する（ステップＳ３１）。そして、プロセッサは、レジスタＲ６の値と当該レジスタＲ６を右に９ビットシフトした値との排他的論理和を算出し、結果をレジスタＲ６に格納する（ステップＳ３３）。これでも図１４のＦＩ３関連処理と等価な処理である。また、高速処理が可能である。
【００８９】
同様に、図２０に示すような処理に変形することも可能である。すなわち、プロセッサは、レジスタＲ１の上位７ビットをビット位置をシフトさせずに取り出し、レジスタＲ６に格納する（ステップＳ４１）。そして、プロセッサは、レジスタＲ５の値とレジスタＲ６の値との排他的論理和を算出し、結果をレジスタＲ５に格納する（ステップＳ４３）。さらに、プロセッサは、レジスタＲ６の値を右に９ビットシフトした値を、レジスタＲ６に戻す（ステップＳ４５）。これでも図１４のＦＩ３関連処理と等価な処理である。
【００９０】
本実施の形態をまとめると以下のようになる。
【００９１】
本暗号装置は、第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置である。そして、本暗号装置は、（Ａ−１）９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と第１の出力との排他的論理和の値を、全ての第１の入力Ｘについて格納した第１の変換テーブル（図２１：５１１）と、（Ａ−２）７＊ｎビットの第２の入力Ｙに対する第２の非線形関数Ｓ７の第２の出力と第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と第２の入力Ｙとの排他的論理和の値を、全ての第２の入力Ｙについて格納した第２の変換テーブル（図２１：５１２）とを記録している読み出し専用メモリ（図２１：５１０）と、（Ｂ）読み出し専用メモリに記録されている第１の変換テーブルを２度用い、読み出し専用メモリに記録されている第２の変換テーブルを１度用いて、ＦＩ関数の１回の演算を行うＦＩ関数演算部（図２１：５００）とを有する。
【００９２】
ＭＩＳＴＹ１やＭＩＳＴＹ２のようにＦＩ関数に従った演算を行う暗号において、上で述べたような第１の変換テーブル及び第２の変換テーブルを用意することによって、ＲＡＭを用いずにＲＯＭサイズを少なくすることができる。
【００９３】
また、上で述べたＦＩ関数演算部が、（ｂ１）第３の入力の上位９＊ｎビットを第１の入力Ｘとして第１の変換テーブルから該当する第１のデータを読み出し、（ｂ２）第３の入力の下位７＊ｎビットを第２の入力Ｙとして第２の変換テーブルから該当する第２のデータを読み出し、（ｂ３）第１のデータと第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は第１のデータと入力拡大鍵との排他的論理和にさらに第２のデータの排他的論理和を算出して第３データを生成し、（ｂ４）第３データの下位９＊ｎビットを第１の入力Ｘとして第１の変換テーブルから該当する第４のデータを読み出し、第４のデータの下位９＊ｎビットを取り出して第５のデータを生成し、（ｂ５）第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成し、（ｂ６）第５のデータと前記第６のデータとの排他的論理和を算出するようにしてもよい。
【００９４】
このように第１及び第２の変換テーブルを導入しても必要な演算サイクルはあまり増加せずに済む。ステップ（ｂ５）は様々な等価な実現方法が可能である。
【００９５】
さらに、本暗号装置は、拡大鍵生成部と、暗号化処理部とを有するようにしてもよい。そして、拡大鍵生成部及び暗号化処理部とが、ＦＩ関数演算部に対してＦＩ関数の演算を要求し、ＦＩ関数演算部から演算結果を受け取るようにしてもよい。例えばＭＩＳＴＹ１やＭＩＳＴＹ２では、拡大鍵生成処理においてもＦＩ関数が必要となるので、第１及び第２の変換テーブルが有効に利用される。
【００９６】
また、上で述べたＦＩ関数演算部が、第１乃至第４のセレクタと、第１及び第２の排他的論理和演算部と、レジスタとを有するようにしてもよい。このような場合には、（ｄ１）第１のセレクタには、第３の入力の上位９＊ｎビットと、レジスタに格納されている値の下位９＊ｎビットとが入力されており、（ｄ２）第１のセレクタの出力を、第１の入力Ｘとして第１の変換テーブルから該当する第１のデータを読み出すようになっており、（ｄ３）第３の入力の下位７＊ｎビットを、第２の入力Ｙとして第２の変換テーブルから該当する第２のデータを読み出すようになっており、（ｄ４）第２のセレクタには、第１のデータと、レジスタに格納されている値の上位７＊ｎビットに対して当該上位７＊ｎビットの上位に０を挿入して生成される９＊ｎビットのデータを下位に連結した第３データとが入力されており、（ｄ５）第３のセレクタには、第２のデータと、第１のデータの下位９＊ｎビットに対して７＊ｎビットの０を上位に連結した第４のデータとが入力されており、（ｄ６）第４のセレクタには、入力拡大鍵と、１６＊ｎビットの０とが入力されており、（ｄ７）第１の排他的論理和演算部は、第２のセレクタの出力と第３のセレクタの出力とについて排他的論理和を演算して第５のデータを生成し、（ｄ８）第２の排他的論理和演算部は、第５のデータと第４のセレクタの出力とについて排他的論理和を演算して第６のデータを生成し、レジスタに格納するようにしてもよい。そして、第１のサイクルでは、第１のセレクタでは第３の入力の上位９＊ｎビットが選択され、第２のセレクタでは第１のデータが選択され、第３のセレクタでは第２のデータが選択され、第４のセレクタでは、入力拡大鍵が選択されるようにしてもよい。また、第２のサイクルでは、第１のセレクタではレジスタに格納されている値の下位９＊ｎビットが選択され、第２のセレクタでは第３のデータが選択され、第３のセレクタでは第４のデータが選択され、第４のセレクタでは上記１６＊ｎビットの０が選択されるようにしてもよい。
【００９７】
このようにハードウエアで実装する場合においても第１及び第２の変換テーブルを利用するような構成を採用することができる。
【００９８】
なお、第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を実行する暗号方法（図２２）は、（Ａ）入力Ｚを受け取るステップと、（Ｂ）（ｂ１）９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、（ｂ２）７＊ｎビットの第２の入力Ｙに対する第２の非線形関数Ｓ７の第２の出力と第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている第１の変換テーブルにアクセスして、入力Ｚの上位９＊ｎビットである第１の入力Ｘに該当する第１のデータを読み出すステップと、（Ｃ）読み出し専用メモリに記録されている第２の変換テーブルにアクセスして、入力Ｚの下位７＊ｎビットである第２の入力Ｙに該当する第２のデータを読み出すステップと、（Ｄ）第１のデータと第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は第１のデータと入力拡大鍵との排他的論理和にさらに第２のデータの排他的論理和を算出して第３データを生成するステップと、（Ｅ）読み出し専用メモリに記録されている第１の変換テーブルにアクセスして、第３データの下位９＊ｎビットである第１の入力Ｘに該当する第４のデータを読み出し、第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、（Ｆ）第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、（Ｇ）第５のデータと第６のデータとの排他的論理和を算出するステップとを含む。
【００９９】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【０１００】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１０１】
（付記１）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置であって、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を記録している読み出し専用メモリと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルを２度用い、前記読み出し専用メモリに記録されている前記第２の変換テーブルを１度用いて、前記ＦＩ関数の１回の演算を行うＦＩ関数演算部と、
を有する暗号装置。
【０１０２】
（付記２）
前記ＦＩ関数演算部が、
第３の入力の上位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出し、
前記第３の入力の下位７＊ｎビットを前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出し、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成し、
前記第３データの下位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成し、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成し、
前記第５のデータと前記第６のデータとの排他的論理和を算出する
付記１記載の暗号装置。
【０１０３】
（付記３）
拡大鍵生成部と、
暗号化処理部と
を有し、
前記拡大鍵生成部及び前記暗号化処理部とが、前記ＦＩ関数演算部に対して前記ＦＩ関数の演算を要求し、前記ＦＩ関数演算部から演算結果を受け取る
付記１又は２記載の暗号装置。
【０１０４】
（付記４）
前記ＦＩ関数演算部が、
第１乃至第４のセレクタと、
第１及び第２の排他的論理和演算部と、
レジスタと、
を有しており、
前記第１のセレクタには、第３の入力の上位９＊ｎビットと、前記レジスタに格納されている値の下位９＊ｎビットとが入力されており、
前記第１のセレクタの出力を、前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出すようになっており、
前記第３の入力の下位７＊ｎビットを、前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出すようになっており、
前記第２のセレクタには、前記第１のデータと、前記レジスタに格納されている値の上位７＊ｎビットに対して当該上位７＊ｎビットの上位に０を挿入して生成される９＊ｎビットのデータを下位に連結した第３データとが入力されており、
前記第３のセレクタには、前記第２のデータと、前記第１のデータの下位９＊ｎビットに対して７＊ｎビットの０を上位に連結した第４のデータとが入力されており、
前記第４のセレクタには、入力拡大鍵と、１６＊ｎビットの０とが入力されており、
前記第１の排他的論理和演算部は、前記第２のセレクタの出力と前記第３のセレクタの出力とについて排他的論理和を演算して第５のデータを生成し、
前記第２の排他的論理和演算部は、前記第５のデータと前記第４のセレクタの出力とについて排他的論理和を演算して第６のデータを生成し、前記レジスタに格納し、
第１のサイクルでは、前記第１のセレクタでは前記第３の入力の上位９＊ｎビットが選択され、前記第２のセレクタでは前記第１のデータが選択され、前記第３のセレクタでは前記第２のデータが選択され、前記第４のセレクタでは、前記入力拡大鍵が選択され、
第２のサイクルでは、前記第１のセレクタでは前記レジスタに格納されている値の下位９＊ｎビットが選択され、前記第２のセレクタでは前記第３のデータが選択され、前記第３のセレクタでは前記第４のデータが選択され、前記第４のセレクタでは前記１６＊ｎビットの０が選択される
付記１乃至３のいずれか１つ記載の暗号装置。
【０１０５】
（付記５）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムであって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を実行させるための暗号プログラム。
【０１０６】
（付記６）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を実行する暗号方法であって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を含み、プロセッサに実行される暗号方法。
【０１０７】
（付記７）
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を格納しており
前記暗号プログラムが、
入力Ｚを受け取るステップと、
前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
をプロセッサに実行させるための暗号プログラム
であるメモリ。
【０１０８】
（付記８）
前記メモリを有する付記７記載のプロセッサ。
【符号の説明】
【０１０９】
１０１ 拡大鍵生成関数 １０３ 暗号化関数
１０５ ＦＯ関数 １０７ ＦＬ関数
１０９ ＦＩ関数
１０ プロセッサ １１ ＲＡＭ
１２ ＲＯＭ
【特許請求の範囲】
【請求項１】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置であって、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を記録している読み出し専用メモリと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルを２度用い、前記読み出し専用メモリに記録されている前記第２の変換テーブルを１度用いて、前記ＦＩ関数の１回の演算を行うＦＩ関数演算部と、
を有する暗号装置。
【請求項２】
前記ＦＩ関数演算部が、
第３の入力の上位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出し、
前記第３の入力の下位７＊ｎビットを前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出し、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成し、
前記第３データの下位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成し、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成し、
前記第５のデータと前記第６のデータとの排他的論理和を算出する
請求項１記載の暗号装置。
【請求項３】
拡大鍵生成部と、
暗号化処理部と
を有し、
前記拡大鍵生成部及び前記暗号化処理部とが、前記ＦＩ関数演算部に対して前記ＦＩ関数の演算を要求し、前記ＦＩ関数演算部から演算結果を受け取る
請求項１又は２記載の暗号装置。
【請求項４】
前記ＦＩ関数演算部が、
第１乃至第４のセレクタと、
第１及び第２の排他的論理和演算部と、
レジスタと、
を有しており、
前記第１のセレクタには、第３の入力の上位９＊ｎビットと、前記レジスタに格納されている値の下位９＊ｎビットとが入力されており、
前記第１のセレクタの出力を、前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出すようになっており、
前記第３の入力の下位７＊ｎビットを、前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出すようになっており、
前記第２のセレクタには、前記第１のデータと、前記レジスタに格納されている値の上位７＊ｎビットに対して当該上位７＊ｎビットの上位に０を挿入して生成される９＊ｎビットのデータを下位に連結した第３データとが入力されており、
前記第３のセレクタには、前記第２のデータと、前記第１のデータの下位９＊ｎビットに対して７＊ｎビットの０を上位に連結した第４のデータとが入力されており、
前記第４のセレクタには、入力拡大鍵と、１６＊ｎビットの０とが入力されており、
前記第１の排他的論理和演算部は、前記第２のセレクタの出力と前記第３のセレクタの出力とについて排他的論理和を演算して第５のデータを生成し、
前記第２の排他的論理和演算部は、前記第５のデータと前記第４のセレクタの出力とについて排他的論理和を演算して第６のデータを生成し、前記レジスタに格納し、
第１のサイクルでは、前記第１のセレクタでは前記第３の入力の上位９＊ｎビットが選択され、前記第２のセレクタでは前記第１のデータが選択され、前記第３のセレクタでは前記第２のデータが選択され、前記第４のセレクタでは、前記入力拡大鍵が選択され、
第２のサイクルでは、前記第１のセレクタでは前記レジスタに格納されている値の下位９＊ｎビットが選択され、前記第２のセレクタでは前記第３のデータが選択され、前記第３のセレクタでは前記第４のデータが選択され、前記第４のセレクタでは前記１６＊ｎビットの０が選択される
請求項１乃至３のいずれか１つ記載の暗号装置。
【請求項５】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムであって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を実行させるための暗号プログラム。
【請求項６】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を実行する暗号方法であって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を含み、プロセッサに実行される暗号方法。
【請求項７】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を格納しており
前記暗号プログラムが、
入力Ｚを受け取るステップと、
前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
をプロセッサに実行させるための暗号プログラム
であるメモリ。
【請求項８】
前記メモリを有する請求項７記載のプロセッサ。
【請求項１】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を行う暗号装置であって、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を記録している読み出し専用メモリと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルを２度用い、前記読み出し専用メモリに記録されている前記第２の変換テーブルを１度用いて、前記ＦＩ関数の１回の演算を行うＦＩ関数演算部と、
を有する暗号装置。
【請求項２】
前記ＦＩ関数演算部が、
第３の入力の上位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出し、
前記第３の入力の下位７＊ｎビットを前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出し、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成し、
前記第３データの下位９＊ｎビットを前記第１の入力Ｘとして前記第１の変換テーブルから該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成し、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成し、
前記第５のデータと前記第６のデータとの排他的論理和を算出する
請求項１記載の暗号装置。
【請求項３】
拡大鍵生成部と、
暗号化処理部と
を有し、
前記拡大鍵生成部及び前記暗号化処理部とが、前記ＦＩ関数演算部に対して前記ＦＩ関数の演算を要求し、前記ＦＩ関数演算部から演算結果を受け取る
請求項１又は２記載の暗号装置。
【請求項４】
前記ＦＩ関数演算部が、
第１乃至第４のセレクタと、
第１及び第２の排他的論理和演算部と、
レジスタと、
を有しており、
前記第１のセレクタには、第３の入力の上位９＊ｎビットと、前記レジスタに格納されている値の下位９＊ｎビットとが入力されており、
前記第１のセレクタの出力を、前記第１の入力Ｘとして前記第１の変換テーブルから該当する第１のデータを読み出すようになっており、
前記第３の入力の下位７＊ｎビットを、前記第２の入力Ｙとして前記第２の変換テーブルから該当する第２のデータを読み出すようになっており、
前記第２のセレクタには、前記第１のデータと、前記レジスタに格納されている値の上位７＊ｎビットに対して当該上位７＊ｎビットの上位に０を挿入して生成される９＊ｎビットのデータを下位に連結した第３データとが入力されており、
前記第３のセレクタには、前記第２のデータと、前記第１のデータの下位９＊ｎビットに対して７＊ｎビットの０を上位に連結した第４のデータとが入力されており、
前記第４のセレクタには、入力拡大鍵と、１６＊ｎビットの０とが入力されており、
前記第１の排他的論理和演算部は、前記第２のセレクタの出力と前記第３のセレクタの出力とについて排他的論理和を演算して第５のデータを生成し、
前記第２の排他的論理和演算部は、前記第５のデータと前記第４のセレクタの出力とについて排他的論理和を演算して第６のデータを生成し、前記レジスタに格納し、
第１のサイクルでは、前記第１のセレクタでは前記第３の入力の上位９＊ｎビットが選択され、前記第２のセレクタでは前記第１のデータが選択され、前記第３のセレクタでは前記第２のデータが選択され、前記第４のセレクタでは、前記入力拡大鍵が選択され、
第２のサイクルでは、前記第１のセレクタでは前記レジスタに格納されている値の下位９＊ｎビットが選択され、前記第２のセレクタでは前記第３のデータが選択され、前記第３のセレクタでは前記第４のデータが選択され、前記第４のセレクタでは前記１６＊ｎビットの０が選択される
請求項１乃至３のいずれか１つ記載の暗号装置。
【請求項５】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムであって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を実行させるための暗号プログラム。
【請求項６】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算を実行する暗号方法であって、
入力Ｚを受け取るステップと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルとを記録している読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記読み出し専用メモリに記録されている前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記読み出し専用メモリに記録されている前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
を含み、プロセッサに実行される暗号方法。
【請求項７】
第１の非線形関数Ｓ９と第２の非線形関数Ｓ７とを含むＦＩ関数に従った演算をプロセッサに実行させる暗号プログラムと、
９＊ｎビット（ｎは１以上の整数）の第１の入力Ｘに対する前記第１の非線形関数Ｓ９の第１の出力の下位７＊ｎビットを抽出し、当該第１の出力の下位７＊ｎビットを９＊ｎビット左シフトした値と前記第１の出力との排他的論理和の値を、全ての前記第１の入力Ｘについて格納した第１の変換テーブルと、
７＊ｎビットの第２の入力Ｙに対する前記第２の非線形関数Ｓ７の第２の出力と前記第２の入力Ｙとの排他的論理和の結果を９＊ｎビット左シフトし、当該排他的論理和の結果の９＊ｎビット左シフトした値と前記第２の入力Ｙとの排他的論理和の値を、全ての前記第２の入力Ｙについて格納した第２の変換テーブルと、
を格納しており
前記暗号プログラムが、
入力Ｚを受け取るステップと、
前記第１の変換テーブルにアクセスして、前記入力Ｚの上位９＊ｎビットである前記第１の入力Ｘに該当する第１のデータを読み出すステップと、
前記第２の変換テーブルにアクセスして、前記入力Ｚの下位７＊ｎビットである前記第２の入力Ｙに該当する第２のデータを読み出すステップと、
前記第１のデータと前記第２のデータの排他的論理和にさらに入力拡大鍵との排他的論理和を算出して第３データを生成又は前記第１のデータと前記入力拡大鍵との排他的論理和にさらに前記第２のデータの排他的論理和を算出して前記第３データを生成するステップと、
前記第１の変換テーブルにアクセスして、前記第３データの下位９＊ｎビットである前記第１の入力Ｘに該当する第４のデータを読み出し、前記第４のデータの下位９＊ｎビットを取り出して第５のデータを生成するステップと、
前記第３のデータの上位７＊ｎビットと、当該第３のデータの上位７＊ｎビットを９＊ｎビット左シフトした値との排他的論理和と等価な第６のデータを生成するステップと、
前記第５のデータと前記第６のデータとの排他的論理和を算出するステップと、
をプロセッサに実行させるための暗号プログラム
であるメモリ。
【請求項８】
前記メモリを有する請求項７記載のプロセッサ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１１−７５７２１（Ｐ２０１１−７５７２１Ａ）
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願番号】特願２００９−２２５５３５（Ｐ２００９−２２５５３５）
【出願日】平成２１年９月２９日（２００９．９．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願日】平成２１年９月２９日（２００９．９．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]