(57)【要約】【課題】  少ない余剰レジスタで処理可能な非線形関数S-boxの計算方法は、アルゴリズム毎に個別に検討する必要がある。本発明は暗号アルゴリズムによらず、少ない余剰レジスタで処理可能な非線形関数S-boxの計算技術を実現することを目的とする。【解決手段】  S-boxを計算するための多項式写像におけるレジスタ操作の際に、元のデータを使った演算の後で、他のデータとの演算によって元のデータが変更される演算を行い、後の演算で使用するデータである元のデータ又は演算結果を格納すべきレジスタがない場合は、余剰レジスタに退避する。【選択図】  図３
2013205437.tif 000002
【特許請求の範囲】
【請求項１】
CPUと記憶部を備えた処理装置が平文データの暗号化又は暗号文データを復号するための非線形関数S-boxの計算方法であって、
予め定められた順序に従って合成すると入出力がn-bitの置換であるS-boxを表現する、予め定められた個数の多項式写像を前記記憶部に格納し、
前記CPUが備えるn本の入出力用レジスタの各々に格納されているn-bitデータ、及び前記記憶部に格納された多項式写像に基づいて前記S-boxを計算する際に、
前記n-bitデータから有限体GF(2)上のn次元線形空間GF(2)nの元である第一の数値列に変換する第一のステップと、
前記入出力用レジスタに格納されている前記第一の数値列を、前記入出力用レジスタとは異なるレジスタ、及び前記予め定められた多項式写像を用いて、第二の数値列に変換する第二のステップと、
前記第二のステップを、前記多項式写像の個数回だけ繰り返す第三のステップと、を実行することを特徴とする非線形関数S-box計算方法。
【請求項２】
前記第一のステップは、n-bitデータa1,...,anからn次元線形空間GF(2)nの元(a1,...,an)に変換し、
前記第二のステップは、n次元線形空間GF(2)nの元(a1, ..., an)と予め定められた個数の多項式写像F1, ..., FLに対してFi(a1, ..., an)を計算し、(a1, ..., an)にFi(a1, ..., an)を代入する変換を行い、
前記第三のステップは、iが1からnまでの間、Fi(a1, ..., an)を計算し、(a1,...,an)にFi(a1, ..., an)を代入する変換を行った後、iを1増加させて前記処理を繰り返す、
ことを特徴とする請求項１記載の非線形関数S-box計算方法。
【請求項３】
前記記憶部に格納されている各多項式写像の種類は、基本多項式写像、triangular 多項式写像、及び可逆なアフィン多項式写像のうち、少なくとも１種類を含むことを特徴とする請求項２記載の非線形関数S-box計算方法。
【請求項４】
前記多項式写像におけるレジスタ操作の際に、元のデータを使った演算の後で、他のデータとの演算によって元のデータが変更される演算を行い、後の演算で使用するデータである元のデータ又は演算結果を格納すべきレジスタがない場合は、余剰レジスタに退避する、ことを特徴とする請求項１記載の非線形関数S-box計算方法。
【請求項５】
前記多項式写像における前記レジスタ操作は、
（１）写像後も元のデータをそのまま使うデータは、当該レジスタに残しておき、
（２）他のデータとの演算によって変更されるが、元のデータをそのまま使わない場合は、演算結果を元のデータが格納されていたレジスタに格納し、
（３）他のデータとの演算によって変更されるが、元のデータを他の演算でも使う場合は、他のデータとの演算の前に元のデータを余剰レジスタに一時的に退避し、
（４）元のデータが格納されていたレジスタに演算結果または中間データを格納又は加算できない場合は、演算結果を余剰レジスタに一時的に格納し、
（５）他のデータとの演算によって変更される前に、元のデータを他の演算で使用する、ことを特徴とする請求項４記載の非線形関数S-box計算方法。
【請求項６】
CPUを備え、平文データの暗号化又は暗号文データを復号するためのS-box計算装置であって、
予め定められた順序に従って合成すると入出力がn-bitの置換であるS-boxを表現する、予め定められた個数の多項式写像を格納する記憶部、
前記CPUが備えるn本の入出力用レジスタの各々に格納されているn-bitデータ、及び前記記憶部に格納された多項式写像に基づいて前記S-boxを計算する際に、前記n-bitデータから有限体GF(2)上のn次元線形空間GF(2)nの元である第一の数値列に変換する第一の変換手段と、
前記入出力用レジスタに格納されている前記第一の数値列を、前記入出力用レジスタとは異なるレジスタ、及び前記予め定められた多項式写像に基づいて、第二の数値列に変換する第二の変換手段と、
前記第二の変換手段を、前記多項式写像の個数回だけ繰り返す第三の手段と、を備えることを特徴とするS-box計算装置。
【請求項７】
前記第一の変換手段は、n-bitデータa1, ..., anからn次元線形空間GF(2)nの元(a1, ..., an)に変換し、
前記第二の変換手段は、n次元線形空間GF(2)nの元(a1, ..., an)と予め定められた個数の多項式写像F1, ..., FLに対してFi(a1, ..., an)を計算し、(a1, ..., an)にFi(a1, ..., an)を代入する変換を行い、
前記第三の手段は、iが1からnまでの間、Fi(a1, ..., an)を計算し、(a1, ..., an)にFi(a1, ..., an)を代入する変換を行った後iを1増加させる処理を繰り返す、
ことを特徴とする請求項６記載のS-box計算装置。
【請求項８】
前記記憶部に格納されている各多項式写像は、基本多項式写像、triangular 多項式写像、及び可逆なアフィン多項式写像の何れか一つであることを特徴とする請求項７記載のS-box計算装置。
【請求項９】
前記多項式写像におけるレジスタ操作の際に、元のデータを使った演算の後で、他のデータとの演算によって元のデータが変更される演算を行い、後の演算で使用するデータである元のデータ又は演算結果を格納すべきレジスタがない場合は、余剰レジスタに退避する、ことを特徴とする請求項６記載のS-box計算装置。
【請求項１０】
前記多項式写像における前記レジスタ操作は、
（１）写像後も元のデータをそのまま使うデータは、当該レジスタに残しておき、
（２）他のデータとの演算によって変更されるが、元のデータをそのまま使わない場合は、演算結果を元のデータが格納されていたレジスタに格納し、
（３）他のデータとの演算によって変更されるが、元のデータを他の演算でも使う場合は、他のデータとの演算の前に元のデータを余剰レジスタに一時的に退避し、
（４）元のデータが格納されていたレジスタに演算結果または中間データを格納又は加算できない場合は、演算結果を余剰レジスタに一時的に格納し、
（５）他のデータとの演算によって変更される前に、元のデータを他の演算で使用する、ことを特徴とする請求項９記載のS-box計算装置。
【請求項１１】
計算機で読み取り可能な記憶媒体であって、請求項１に記載の非線形関数S-boxの計算方法を実行するためのプログラムを格納した、ことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロック暗号、ストリーム暗号、暗号学的ハッシュ関数の計算におけるS−box計算方法、及びプログラムの技術に関する。
【背景技術】
【０００２】
ブロック暗号、ストリーム暗号、暗号学的ハッシュ関数などの共通鍵暗号のソフトウェア実装の一手法として、ビットスライス実装が知られている。ビットスライス実装とは、小さなビット幅（例えば４ビット）の入出力をもつ構成要素（ブロック暗号AESであればS−box、MixColumns、AddRoundKey、ShiftRows）を組み合わせて共通鍵暗号アルゴリズムを構成する技術であり、暗号処理の並列化を図り、プロセッサの演算回路の効率を高め、暗号化処理速度、復号処理速度を高めるソフトウェア実装方法である。
【０００３】
ビットスライス実装の効果は、暗号アルゴリズムの構造や（ブロック暗号の場合は）使用する暗号利用モードに依存しており、ビットスライス実装することを想定して暗号設計されることも多い。効率的なビットスライス実装が可能な暗号アルゴリズムの例としてブロック暗号DES、Serpentなどが知られている。
【０００４】
ブロック暗号、ストリーム暗号、暗号学的ハッシュ関数などの共通鍵暗号において、効率的なビットスライス実装が可能か否かは暗号アルゴリズムの構成要素として含まれる非線形関数の構造に依存する。非線形関数はブロック暗号、ストリーム暗号、暗号学的ハッシュ関数などの共通鍵暗号において安全性を強化するための構成要素として用いられる。
【０００５】
この非線形関数を実現する一手法としてS−boxが知られている。ここで、S−boxとは比較的小さな整数m, n （例えば4≦m,n≦8）に対し, mビット入力、nビット出力をもつ非線形な関数（本実施例の場合は、入力ビット長、出力ビット長を表す整数m、nはm＝nとする。）
S−box:{0,1}ｍ→{0,1}ｎ                                       （数１）
である。
【０００６】
以後、nビットのビット列全体の集合{0,1}nと有限体GF(2)上のn次元線形空間GF(2)n を写像φ
φ: {0,1}n→GF(2)n,  ａ1ａ2…ａn−1ａn→(ａ1,ａ2,…,ａn−1,ａn)    （数２）
によって同一視することにする。
【０００７】
S−boxの計算方法の一つとしてテーブル参照が知られている（非特許文献１参照）。テーブル参照は、集合{S−box(0), S−box(1), …, S−box(2m−1)}を表として保持しておく。そして関数S−boxへの入力xに対し、上記集合の元であるS−box(x)を取り出し、出力する。例えば、米国標準のブロック暗号AESにおけるS−boxの表参照用のテーブルについては非特許文献４のp.16 (暗号化処理で使用するS−box), p.22（復号処理で使用する逆S−box）に記載がある。
【０００８】
（数１）で表される非線形関数S−boxは、有限体GF(2)上の多項式写像の形で表されることが知られている。ここで、非線形関数S−boxを表現する有限体GF(2)上の多項式写像とは、GF(2)上のn変数多項式F1,…,Fn が存在して、すべてのａ1ａ2…ａｍ−1ａｍ∈{0,1}ｍに対して
S−box(a1,…,am )＝(F1 (a1,…,am ), …, Fn(a1,…,am ))             （数３）
が成り立つことである。（数３）は、関数S−boxが、関数としてS−box＝(F1,…Fn)と表わされることを示している。
【０００９】
ここで、F1, …FnはGF(2)上のn変数多項式である。（数３）は、集合{0, 1}m の元a1...am を関数S−boxに代入した値S−box(a1,…am )が、(F1 (a1,…am ), …Fn (a1,…am))と等しいことを述べている。多項式写像については、例えば非特許文献２、３に記載がある。ビットスライス実装では、S−boxの入出力となるmビットデータa1,…amは、それぞれ異なるレジスタに格納されている。そのため、S−boxの計算では、入出力データを保持するレジスタの他に、S−boxの計算における中間値の計算、及び保持を行うためのレジスタ（余剰レジスタ）が必要になる。
【００１０】
以後、入力ビット長、出力ビット長を表す整数m、nはm＝nとする。また、非線形関数S−boxは全単射（つまり、nビット列の集合{0, 1}n 上の置換）であるとする。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】D.A.Osvik, Speeding up serpent, AES Candidate Conference, April 2000.
【非特許文献２】A. van der Essen, Polynomial Automorphisms and the Jacobian Conjecture, Progress in Mathematics, Vol.190, Birkhauser Verlag, Basel−Boston−Berlin, 2000.
【非特許文献３】S.Maubach, Polynomial automorphisms over finite fields, Serdica Math. J. 27 (2001), No.4, 343−350.
【非特許文献４】National Institute of Standards and Technology, Announcing the ADVANCED ENCRYPTION STANDARD (AES), Federal Information Processing Standards Publication 197, November 2001. Available at http://csrc.nist.gov/publications/fips/fips197/fips−197.pdf
【非特許文献５】E.Biham, A Fast New DES Implementation in Software, FSE’97, LNCS 1267, pp.260−272, 1997.
【非特許文献６】株式会社 日立製作所, ストリーム暗号 Enocoro 仕様書 Ver. 2.0. (http://www.hitachi.co.jp/rd/yrl/crypto/enocoro/index.html)
【発明の概要】
【発明が解決しようとする課題】
【００１２】
情報通信ネットワークの進展とともに電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度やメモリ使用量、更にレジスタ使用本数などがある。
【００１３】
しかし、一般に、安全性、処理速度、メモリ使用量、レジスタ使用本数の間にはトレードオフの関係があり、全ての要件を満たすことは難しい。
【００１４】
レジスタの本数（個数）が少ないCPU上（例えばIA32 (x86系)のCPUは汎用レジスタが８本）でビットスライス実装したプログラムを実行する場合、暗復号で使用する鍵データ、及び平文データ（復号する場合は暗号文）がレジスタに格納されている。上記プログラムを用いて暗号化（または復号）処理を実施すると、上記プログラムに従って暗号化（または復号）が開始される。このとき、上記鍵データ、平文データの他に、暗号化（または復号）の中間値データを保持しておく必要がある。
【００１５】
汎用PCにおいて、値を保持するためにレジスタやメモリが利用される。ある計算をCPU上で実行する場合、その計算の入力値をレジスタに格納し、その後、実際の計算を行う。そのため、上記入力値がメモリに格納されている場合、上記入力値をメモリからレジスタに転送することが必要になり、転送の処理時間を要する。このように、メモリ上の値を計算で使用するためには上述の転送が必要となるため、計算に必要な値は可能な限りレジスタに格納しておくことが望ましい。
【００１６】
ところが、レジスタの本数が少ないCPUでは、上記鍵データ、平文データ、及び上記中間値データの全てをレジスタに格納できないことがある。このように、格納すべき全てのデータのデータサイズがレジスタに格納できるデータサイズより大きい場合、格納できないデータは、レジスタではなく、メモリに格納しなければならない。したがって、上記プログラムをアセンブリ言語で実装している場合、必然的に多くのスタック操作（アセンブリ言語のpush命令、pop命令）が必要となる。以後、中間値データを格納するためのレジスタを余剰レジスタと呼ぶ。
【００１７】
一般に、少ない余剰レジスタを用いたビットスライス実装において、最も重要となるのは非線形関数S−boxの実装方法である。
【００１８】
多くのスタック操作が必要であれば、スタック操作によってメモリアクセス頻度が高くなり、速度低下を引き起こす。一方、実システムで様々なアプリケーションが実行されているような環境（例えばサーバなど）において、S−boxの計算で多くの余剰レジスタを必要とする暗号のソフトウェアプログラムが組込まれている場合、上記アプリケーションが使用可能なレジスタが少なくなるため、処理時間に大きな影響を及ぼす。また、S−boxは暗号アルゴリズム毎に異なるため、少ない余剰レジスタを用いたビットスライス実装が可能か否かは、暗号アルゴリズム毎に個別に検討する必要がある。
【００１９】
例えば、非特許文献１では、ブロック暗号Serpentに対し、少ない余剰レジスタを用いたビットスライス実装方法を提供している。ところが、非特許文献１に記載の方法はブロック暗号Serpentに対してのみ適用可能であり、他のブロック暗号への直接適用は困難である。
【００２０】
また、非特許文献１以外にも、少ない余剰レジスタを用いたビットスライス実装方法が提供されているブロック暗号があり、ブロック暗号DESについては非特許文献５に記載されているものの、非特許文献１と同様、他のブロック暗号への直接適用は困難である。
【００２１】
したがって、非線形関数S−boxの構造に依存せず、少ない余剰レジスタによるS−boxの汎用的なソフトウェア実装方法が提供されていない。
【００２２】
本発明は、上記課題に鑑みてなされたもので、非線形関数S−boxの置換に依存せず、少ない余剰レジスタで処理可能な非線形関数S−boxの計算技術を実現することを目的とする。
【課題を解決するための手段】
【００２３】
上述したように、少ない余剰レジスタでS−boxを計算する従来技術は、暗号アルゴリズム毎 (S−boxの置換毎)に計算方法を個別に検討する必要がある。
【００２４】
本発明は、限定された種類の置換を、予め定められた順番に従って施すことによりS−boxを計算する。ここで、置換を多項式写像で表現した場合の、限定された種類の置換とは、後述する基本多項式写像、triangular 多項式写像、及び可逆なアフィン多項式写像をさす。基本多項式写像、triangular 多項式写像、及び可逆なアフィン多項式写像は少ない余剰レジスタで処理可能であるという特徴を用いて、少ない余剰レジスタで処理可能な非線形関数S−boxの計算を行う。
【発明の効果】
【００２５】
本発明により、少ない余剰レジスタで非線形関数S−boxの計算が可能となる。上記の限定された置換を変えるだけで、種々の暗号アルゴリズムに対応したS−boxの計算が可能になる。そして、少ない余剰レジスタで計算が可能であることにより、実システムに適用した場合であっても、他のアプリケーションの処理時間に大きな影響を及ぼすことなく各種共通鍵暗号の処理が可能である。
【図面の簡単な説明】
【００２６】
【図１】第一の実施形態の暗号通信システムのシステム構成図である。
【図２】第一の実施形態のS−box計算部の機能ブロックである。
【図３】第一の実施形態のS−box計算部の処理を説明するためのフローチャートである。
【図４】第二の実施形態のS−box計算部の処理に係る多項式写像の構成例を示す図である。
【図５】第一の実施形態の数４の計算処理を説明するための計算例である。
【図６】第一の実施形態の数６の計算処理を説明するための計算例である。
【図７】第一の実施形態の数８の計算処理を説明するための計算例である。
【発明を実施するための形態】
【００２７】
以下、本発明を適用した第一の実施形態を図面により説明する。
【００２８】
（システム構成）
図１は第一の実施例における暗号通信システムのシステム構成図であり、本発明の暗号通信システムの機能ブロック構成も示している。
【００２９】
ネットワーク126を介して、ディスプレイ124及びキーボード125を有するコンピュータＡ(114)から、ディスプレイ152及びキーボード153を有するコンピュータＢ(145)にデータが転送される。コンピュータＡ(114)は、ＲＡＭ115、入出力インタフェース130、及び、ＣＰＵ144を有し、ＲＡＭ115には、S−box処理プログラムPROG2(120)を含む暗号化処理プログラムPROG1(116)、秘密鍵Key(117)、補助情報IV(118)、及び平文M(119)が格納されている。コンピュータＢ(145)は、ＲＡＭ146、入出力インタフェース156、及び、ＣＰＵ157を有し、ＲＡＭ146には、S−box処理プログラムPROG4(151)を含む復号処理プログラムPROG3(147)、秘密鍵Key(148)、補助情報IV(149)、及び平文M(150)が格納されている。
【００３０】
（S−box計算部構成）
図２は、本実施形態に係るS−box処理プログラム120の構成例を示す図である。なお、図２に示す構成は、図１におけるコンピュータA 114およびコンピュータB 145において、共通の構成である。
【００３１】
S−box処理プログラム120は、CPU144内にある入出力レジスタ208に格納されているnビットデータを入力とし、nビットデータを出力するものであり、アフィン多項式写像計算部201、基本多項式計算部202、triangular多項式写像計算部203、プログラム読み込み部204、繰り返し判定部205、及び多項式写像所属判定部206を備える。
【００３２】
CPU144は、余剰レジスタ207と、入出力レジスタ208とを備える。各部201〜208の機能については、処理の説明において後記する。
【００３３】
（情報の送受信）
次に、図１に沿ってメッセージの暗号化処理および復号処理の概要を説明する。
【００３４】
まず、コンピュータA 114が、入力されたメッセージを暗号化する場合の動作について図１を参照して説明する。メッセージはデジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
【００３５】
まず、CPU144は、入出力インタフェース130を介して、平文メッセージ（入力メッセージ）M 119を取得する。
【００３６】
次に、CPU144は、RAM115に格納されている秘密鍵Key117、補助情報IV(118)を取得する。補助情報IV(118)は、暗号化処理プログラムPROG1(116)としてブロック暗号を利用している場合は、カウンターモードのような暗号利用モードの初期値であり、暗号化処理プログラムPROG1(116)としてストリーム暗号を利用している場合は、ストリーム暗号の初期値である。
【００３７】
CPU144は、受け取った秘密鍵Key117、補助情報IV(118)を用いて、平文メッセージMの暗号化処理を行う。
【００３８】
以後、暗号化処理プログラムPROG1(116)として利用する暗号方式は非線形関数S−boxを構成要素にもつとする。また、非線形関数S−boxはS−box処理プログラムPROG2(120)として実現されているとする。暗号化処理は図3で後記するS−box計算処理を含む。
【００３９】
そして、CPU144は、平文メッセージ119の出力メッセージ（暗号文）をデータ127として入出力インタフェース130から出力する。データ127は、ネットワーク126を介してコンピュータB 145へ転送される。
【００４０】
次に、コンピュータB 145が、暗号化されたメッセージであるデータ127を復号する場合の動作について図１を用いて説明する。
【００４１】
コンピュータB 145のCPU157は、入出力インタフェース156を介して、コンピュータA 114によって暗号化されたメッセージをデータ101として入力を受け付ける。
【００４２】
次に、CPU157は、RAM146に格納されている秘密鍵Key148、補助情報IV(149)を取得する。補助情報IV(149)は、復号処理プログラムPROG3(147)としてブロック暗号を利用している場合は、カウンターモードのような暗号利用モードの初期値であり、復号処理プログラムPROG3 (147)としてストリーム暗号を利用している場合は、ストリーム暗号の初期値である。
【００４３】
CPU157は、受け取った秘密鍵Key148、補助情報IV(149)を用いて、暗号化されたメッセージの復号処理を行う。
【００４４】
以後、復号処理プログラムPROG3(147)として利用する暗号方式は非線形関数S−boxを構成要素にもつとする。また、非線形関数S−boxはS−box処理プログラムPROG2(120)として実現されているとする。復号処理も図3で後記するS−box計算処理を含む。
【００４５】
コンピュータB 145は、CPU157で復号されたデータを、入出力インタフェース156を介して、ディスプレイ152などから出力メッセージとしての復号メッセージを出力する。
【００４６】
（S−box計算処理）
次に、図２を参照しつつ、S−box計算処理について詳細に説明する。
【００４７】
まず、上述した限定された種類の置換である基本多項式写像、triangular 多項式写像、及び可逆なアフィン多項式写像について説明する。基本多項式写像、triangular 多項式写像、及び可逆なアフィン多項式写像は、逆関数が効率的に求められるような多項式写像として知られている。以下、ｋを体とする。
【００４８】
これらの多項式写像は、変換の対象を、処理前、又は最中に限定した変換処理が行える特徴を有するので、少ないレジスタでS−boxの計算処理を行うことができる。
【００４９】
Ｆ＝(F1, …  Fn)がｋ上の基本多項式写像であるとは、多項式写像Ｆが
Ｆ(ｘ1,…,ｘｎ)＝(ｘ1,…,ｘi−1,ｘi＋ｆ(ｘ1,…,ｘi−1,ｘi＋1,…,ｘn),ｘi＋1,…,ｘn)                                                                 （数４）
ｆ∈ｋ[ｘ1,…,ｘi−1,ｘi＋1,…,ｘn]                                  （数５）
なる形となる多項式写像である。
【００５０】
G＝(G1,…Gn)がk上のtriangular 多項式であるとは、多項式写像Gが
Ｇ(ｘ1,…,ｘｎ)＝(ａ１ｘ1＋ｆ1(ｘ2,…,ｘn), ａ2ｘ2＋ｆ2(ｘ3,…,ｘn),…,ａnｘn＋ｆn)                                                                 （数６）
ｆi∈ｋ[ｘi＋1,…,ｘn](i＝1,…,n−1), ｆn∈ｋ, ａi∈ｋ(i＝1,…,n)    （数７）
なる形となる多項式写像である。
【００５１】
Ｈ＝ (H1,…Hn )がｋ上の可逆なアフィン多項式写像であるとは、多項式写像Ｈが
Ｈ(ｘ1,…,ｘｎ)＝(Σj＝1nａ１,jｘj＋ｂ1, Σj＝1nａ2,jｘj＋ｂ2 ,…, Σj＝1nａn,jｘj＋ｂn)                                                           （数８）
なる形となる多項式写像である。但し、行列Ａ＝{ａi,j}1≦i,j≦nは可逆な行列である。本実施例では、体k ＝ GF(2) ＝ {0, 1}のとき、GF(2)の元aを自然にビットとみなす。例えば、a ＝ 0であれば、aを自然に１ビット0とみなし、a＝1であれば、aを自然に１ビット1とみなす。
【００５２】
次に、ｋ ＝ ＧＦ(2)として、基本多項式写像、triangular 多項式写像、及び可逆なアフィン多項式写像が余剰レジスタ１本で計算できることを図５、図６、及び図７を用いて説明する。
【００５３】
ここで、以下の各多項式写像におけるレジスタ操作の原則を説明する。（  ）は図中の具体例を示す。
（１）写像後も元のデータをそのまま使うデータは、当該レジスタに残しておく。（図５のｘ１、ｘ３、ｘ４）
（２）他のデータとの演算によって変更されるが、元のデータをそのまま使わない場合は、演算結果を元のデータが格納されていたレジスタに格納する。（図５のｘ２、図６のｘ１、図７のｘ２）
（３）他のデータとの演算によって変更されるが、元のデータを他の演算でも使う場合は、他のデータとの演算の前に元のデータを余剰レジスタに一時的に退避する。（図７のｘ１）
（４）元のデータが格納されていたレジスタに演算結果（または中間データ）を格納（加算等も含む）できない場合は、演算結果を余剰レジスタに一時的に格納する。（図５のｘ３ｘ４、図６のｘ２ｘ４、図７のｘ１＋ｘ４）
（５）（ア）他のデータとの演算によって変更されるが、（イ）元のデータを他の演算でも使う場合は、（イ）を行ってから（ア）を行う。（図６のｘ３）
以上の原則をまとめると、元のデータを使った演算の後で、他のデータとの演算によって元のデータが変更される演算を行い、後の演算で使用するデータ（元のデータ又は演算結果）を格納すべきレジスタがない場合は、余剰レジスタに退避する。
【００５４】
（基本多項式写像）
図５は基本多項式写像の計算処理を説明するための図である。ここでは、CPU144は、５本以上のレジスタを具備しているものとし、そのうちの４本のレジスタをreg.1、…、reg.4、残りの１本のレジスタをreg.tmpとする。そして、レジスタreg.1、…、reg.4を入出力レジスタ208とし、レジスタreg.tmpを余剰レジスタ207とする。上記４本のレジスタreg.1、…、reg.4にはそれぞれ、値としてx1、x2、x3、x4が格納されているとする。そして、余剰レジスタreg.tmpには適当な値tが格納されているとする。
【００５５】
まずCPU144はＲＡＭ115に格納されているS−box処理プログラムPROG2(120)を読み込む。ここでは、S−box処理プログラムPROG2(120)の中に基本多項式写像FとしてＦ(ｘ1,…,ｘ4)＝(ｘ1,ｘ2＋ｘ3＋ｘ3ｘ4,ｘ3,ｘ4)が格納されているものとする。
【００５６】
このとき、図５の(1)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1、x2、x3、x4、tが格納されている。CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.2とreg.3の値の排他的論理和を計算し、その結果をreg.2に格納する。このとき、図５の(2)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1、x2＋x3、x3、x4、tが格納されている。次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、レジスタ3とレジスタ4の値の論理積を計算し、その結果をreg.tmpに格納する。このとき、図５の(3)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1、x2＋x3、x3、x4、x3x4が格納されている。
【００５７】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、レジスタreg.2とreg.tmpの値の排他的論理和を計算し、その結果をreg.2に格納する。このとき、図５の(4)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1、x2＋ x3＋x3x4、x3、x4、x3x4が格納されており、上記の基本多項式写像Fが計算できたことになる。
【００５８】
一般に、基本多項式写像は数４の形をしており、数４よりn本の入出力レジスタのうち、i番目のレジスタreg.i以外のn−1本のレジスタreg.1、…、reg.i−1、reg.i＋1、…、reg.nの値は変更しない。そして、i番目のレジスタreg.iの値のみを変更する。このとき、数４の右辺にあるｆ(ｘ1,…,ｘi−1,ｘi＋1,…,ｘｎ)を単項式の和の形に変形すると、上記各単項式は、レジスタi以外のn−1本のレジスタreg.1、…、reg.i−1、reg.i＋1、…、reg.nに格納されている値を用い、逐次的に計算可能である。このとき、上記逐次的な計算における中間値を余剰レジスタreg.tmpに格納することによって、ｆ(ｘ1,…,ｘi−1,ｘi＋1,…,ｘｎ)の値を余剰レジスタreg.tmpに格納するように計算することができる。その後、余剰レジスタreg.tmpの値とi番目のレジスタreg.iの値の排他的論理和を計算し、その結果をi番目のレジスタreg.iに格納することによって、GF(2)上の基本多項式写像は、n本の入出力レジスタと１本の余剰レジスタのみを用いて計算できる。
【００５９】
（triangular 多項式写像）
図６はtriangular 多項式写像の計算処理を説明するための図である。図５の説明と同様、CPU144は、５本以上のレジスタを具備しているものとし、そのうちの４本のレジスタをreg.1、…、reg.4、残りの１本のレジスタをreg.tmpとする。そして、レジスタreg.1、…、reg.4を入出力レジスタ208とし、レジスタreg.tmpを余剰レジスタ207とする。上記４本のレジスタreg.1、…、reg.4にはそれぞれ、値としてx1、x2、x3、x4が格納されているとする。そして、余剰レジスタreg.tmpには適当な値tが格納されているとする。
【００６０】
まずCPU144はＲＡＭ115に格納されているS−box処理プログラムPROG2(120)を読み込む。ここでは、S−box処理プログラムPROG2(120)の中にtriangular 多項式写像GとしてＧ(ｘ1,…,ｘ4)＝(ｘ1＋ｘ2＋ｘ2ｘ4,ｘ2＋ｘ3＋ｘ3ｘ4,ｘ3＋ｘ4,ｘ4＋１)が格納されているものとする。このとき、図６の(1)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1、x2、x3、x4、tが格納されている。CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.1とreg.2の値の排他的論理和を計算し、その結果をreg.1に格納する。このとき、図６の(2)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x2、x2、x3、x4、tが格納されている。
【００６１】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、レジスタ2とレジスタ4の値の論理積を計算し、その結果をreg.tmpに格納する。このとき、図６の(3)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x2、x2、x3、x4、x2x4が格納されている。次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、レジスタreg.1とreg.tmpの値の排他的論理和を計算し、その結果をreg.1に格納する。このとき、図６の(4)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x2＋x2x4、x2、x3、x4、x2x4が格納されている。
【００６２】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.2とreg.3の値の排他的論理和を計算し、その結果をreg.2に格納する。このとき、図６の(5)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋ x2＋x2x4、x2＋x3、x3、x4、x2x4が格納されている。次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.3とreg.4の値の論理積を計算し、その結果をreg.tmpに格納する。このとき、図６の(6)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x2＋x2x4、x2＋x3、x3、x4、x3x4が格納されている。
【００６３】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.2とreg.tmpの値の排他的論理和を計算し、その結果をreg.2に格納する。このとき、図６の(7)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x2＋x2x4、x2＋x3＋x3x4、x3、x4、x3x4が格納されている。次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.3とreg.4の値の排他的論理和を計算し、その結果をreg.3に格納する。このとき、図６の(8)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x2＋x2x4、x2＋x3＋x3x4、x3＋x4、x4、x3x4が格納されている。
【００６４】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.4と定数1の値の排他的論理和を計算し、その結果をreg.4に格納する。この演算は、レジスタに格納されている値の否定演算子を用いることで実現できるため、上述したレジスタreg.1、…、reg.4、reg.tmp以外のレジスタは使用しない。このとき、図６の(9)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x2＋x2x4、x2＋x3＋x3x4、x3＋x4、x4＋1、x3x4が格納されており、上記のtriangular 多項式写像Gが計算できたことになる。
【００６５】
一般に、triangular 多項式写像は数６の形をしており、数６よりi番目のレジスタreg.iの値は、i＋1番目以降のレジスタreg.i＋1、…、reg.nの値を用いて変更する。このとき、上述した図５の説明と同様の理由により、i番目のレジスタreg.iの値は、n−i本のレジスタreg.i＋1、…、reg.nの値と１本の余剰レジスタのみを用いて計算することができる。この操作をiが1からnまで逐次的に処理することによって、GF(2)上のtriangular 多項式写像はn本の入出力レジスタと１本の余剰レジスタのみを用いて計算できる。
【００６６】
（可逆なアフィン多項式写像）
図７は可逆なアフィン多項式写像の計算処理を説明するための図である。図５、及び図６の説明と同様、CPU144は、５本以上のレジスタを具備しているものとし、そのうちの４本のレジスタをreg.1、…、reg.4、残りの１本のレジスタをreg.tmpとする。そして、レジスタreg.1、…、reg.4を入出レジスタ208、レジスタreg.tmpを余剰レジスタ207とする。上記４本のレジスタreg.1、…、reg.4にはそれぞれ、値としてx1、x2、x3、x4が格納されているとする。そして、余剰レジスタreg.tmpには適当な値tが格納されているとする。
【００６７】
まずCPU144はＲＡＭ115に格納されているS−box処理プログラムPROG2(120)を読み込む。ここでは、S−box処理プログラムPROG2(120)の中に可逆なアフィン多項式写像HとしてＨ(ｘ1,…,ｘ４)＝(ｘ１＋ｘ３,ｘ２＋ｘ４,ｘ１＋ｘ４,ｘ３)が格納されているものとする。
【００６８】
このとき、図７の(1)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1、x2、x3、x4、tが格納されている。CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.1の値をreg.tmpに格納する。このとき、図７の(2)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1、x2、x3、x4、x1が格納されている。
【００６９】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、レジスタ1とレジスタ3の値の排他的論理和を計算し、その結果をreg.1に格納する。このとき、図７の8(3)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x3、x2、x3、x4、x1が格納されている。
【００７０】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、レジスタreg.2とreg.4の値の排他的論理和を計算し、その結果をreg.2に格納する。このとき、図７の(4)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x3、x2＋x4、x3、x4、x1が格納されている。
【００７１】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.4とreg.tmpの値の排他的論理和を計算し、その結果をreg.tmpに格納する。このとき、図７の(5)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1＋x3、x2＋x4、x3、x4、x1＋x4が格納されている。
【００７２】
次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.3の値をreg.4に格納する。このとき、図７の(6)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1 ＋ x3、x2 ＋ x4、x3、x3、x1 ＋ x4が格納されている。次に、CPU144は、S−box処理プログラムPROG2(120)を読み込み、reg.tmpの値をreg.3に格納する。このとき、図７の(7)のタイミングでレジスタreg.1、…、reg.4、reg.tmpにはそれぞれx1 ＋ x3、x2 ＋ x4、x1 ＋ x4、x3、x1 ＋ x4が格納されており、上記の可逆なアフィン多項式写像Hが計算できたことになる。
【００７３】
一般に、可逆なアフィン多項式写像は数8の形をしており、入力x1、…、xn の縦ベクトルt(x1, …, xn)（左肩のtはベクトルの転置を表す）に対するアフィン変換（線型変換＋定数の加算）とみなすことができる。線型変換は、ある行列を施したものとみなすことができ、特に正則行列（可逆な行列）は６つの基本変形の積で表される。ここで、６つの基本変形とは、以下の操作である。
１．行列の第i行と第j行を入れ替える。
２．行列の第i行に非零定数cをかける。
３．行列の第i行に第j行の非零定数倍を加える。
４．行列の第i列と第j列を入れ替える。
５．行列の第i列に非零定数cをかける。
６．行列の第i列に第j列の非零定数倍を加える。
【００７４】
上述した図５、図６の説明と同様の理由により、上記６つの各基本変形は、n本の入出力レジスタと１本の余剰レジスタのみを用いて計算することができる。したがって、正則行列による線型変換もn本の入出力レジスタと１本の余剰レジスタのみを用いて計算することができるから、GF(2)上の可逆なアフィン多項式写像はn本の入出力レジスタと１本の余剰レジスタのみを用いて計算することができる。
【００７５】
アフィン多項式写像全体の集合、triangular 多項式写像全体の集合、及び基本多項式写像全体の集合はそれぞれ可逆な多項式写像の部分群となることが知られており、それらの集合をそれぞれAff(k, n)、J(k, n)、及びE(k, n)と表すことにする。
【００７６】
上記Aff(k, n)、及びE(k, n)の全ての元で生成される可逆な多項式写像の部分群はtame 多項式写像の部分群と呼ばれている（非特許文献２参照）。tame 多項式写像の部分群の元はtame 多項式写像と呼ばれている。
【００７７】
また、上記Aff(k, n)、及びJ(k, n)の全ての元で生成される可逆な多項式写像の部分群と上記Aff(k, n)、及びE(k, n)の全ての元で生成される可逆な多項式写像の部分群が一致すること、およびJ(k, n)の元がE(k, n)のn個の元とAff(k, n)の1個の元の合成の形で表すことができること、も知られている（非特許文献２参照）。
【００７８】
一般に、多項式写像が上記の合成の形に表すことができるか否かを判定することは困難であるが、多項式写像を置換とみなしたとき、体kが有限体GF(2)であれば上記の合成の形に分解できることは知られている（非特許文献３参照）。
【００７９】
図３は、第一の実施形態に係るS−box計算の流れを示すフローチャートである。
【００８０】
まず、CPU144がnビットデータa1, …anの入力を、プログラム読み込み部204が多項式写像F1, …  FLの入力を、それぞれ受け付ける（ステップ301）。
【００８１】
ここで、多項式写像F1, …FLは有限体GF(2)上のn変数多項式写像であり、Lは多項式写像F1, …FLの個数であり、nビット列{0, 1}n上で全単射であるとする。また、多項式写像F1, …FLは、暗号化処理プログラムPROG1(116)で利用している暗号アルゴリズムに依存しており、F1, …FLを写像として合成した多項式写像は、S−boxを表現する有限体GF(2)上のn変数多項式写像と一致するものとし、多項式写像F1, …FLはプログラムとして実現する前に、予め計算されているものとする。
【００８２】
ここで、多項式写像の各多項式は多項式環GF(2)[x1,…xn]ではなく、GF(2)[x1,…xn]/(x12 −x1,…xn2 − xn)の元とみなす。ここで、GF(2)[ x1,…xn]の元ではなくGF(2)[ x1,…xn]の剰余環の元とみなす、とは、環GF(2)[ x1,…xn]のイデアル(x12 − x1,…xn2 − xn)の要素を含むGF(2)[ x1,…xn]の多項式は同値とみなすことであり、この剰余環を考えることにより、各多項式写像F1,…FLの各単項式は、xim (mは2以上の整数)を含まないため、「S−box処理プログラム120のプログラムサイズが小さくなる」、「xim (mは2以上の整数)の計算を行わないため、もともとの多項式環で考えるより、多項式写像への代入計算が高速になる」という効果がある。
【００８３】
次に、繰り返し判定部205は、iに1を代入する（ステップ302）。
【００８４】
繰り返し判定部205は、iが多項式写像の個数L以下であるか否かを判定する（ステップ303）。
【００８５】
ステップ303の結果、i≦Lが成立する場合（ステップ303→Yes）、ステップ304へ行く。i≦Lが成立しない場合（ステップ303→No）、ステップ310へ行く。
【００８６】
多項式写像所属判定部206は、多項式写像Fiが可逆なアフィン多項式写像である（Ｆi∈Ａff(ｋ,ｎ)）か否かを判定する（ステップ304）。ステップ304の結果、Ｆi∈Ａff(ｋ,ｎ)が成立する場合（ステップ304→Yes）、ステップ305へ行く。Ｆi∈Ａff(ｋ,ｎ)が成立しない場合（ステップ304→No）、ステップ306へ行く。
【００８７】
アフィン多項式写像計算部201は、図７に示した方法によって、各j（j ＝1,…n）に対して、余剰レジスタ207と入出力レジスタ208を用いてFj (a1,…an)を計算し、aj に代入する（ステップ305）。
【００８８】
多項式写像所属判定部206は、多項式写像Fiが基本多項式写像である（Ｆi∈Ｅ(ｋ,ｎ)）か否かを判定する（ステップ306）。ステップ306の結果、Ｆi∈Ｅ(ｋ,ｎ)が成立する場合（ステップ306→Yes）、ステップ307へ行く。Ｆi∈Ｅ(ｋ,ｎ)が成立しない場合（ステップ306→No）、ステップ308へ行く。
【００８９】
基本多項式写像計算部202は、図５に示した方法によって、各j（j ＝1,…n）に対して、余剰レジスタ207と入出力レジスタ208を用いてFj (a1,…an)を計算し、aj に代入する（ステップ307）。
【００９０】
triangular多項式写像計算部203は、図６に示した方法によって、各j（j ＝1,…n）に対して、余剰レジスタ207と入出力レジスタ208を用いてFj (a1,…an)を計算し、aj に代入する（ステップ308）。各aj に対する代入操作は並列的に行われる。
【００９１】
繰り返し判定部205は、iにi＋1を代入する（ステップ309）。
【００９２】
CPU144はnビットデータa1, anを出力する（ステップ310）。
【００９３】
以上説明したように、CPU144から出力されるnビットデータa1,…anは、余剰レジスタ207の1本のレジスタと入出力レジスタ208を用いて計算できる。この理由は図５〜図７の説明で述べた通りである。
【００９４】
なお、本実施形態では、可逆なアフィン多項式写像、基本多項式写像、及びtriangular多項式写像を、1本の余剰レジスタと入出力レジスタで計算可能なことを示したが、上記多項式写像を、2本以上の余剰レジスタと入出力レジスタで計算してもよい。
【００９５】
一般に、多項式写像を、アフィン多項式写像、基本多項式写像、及びtriangular多項式写像の合成の形で表現する方法は一意的ではないが、どのような合成の形であってもよい。
【００９６】
（第一実施形態の効果）
以上のように、第一実施形態のS−box計算方法によれば、1本の余剰レジスタと入出力レジスタを用いてS−boxを計算することが可能となる。すなわち、本実施形態によれば、どのような暗号アルゴリズムであっても、少ない本数の余剰レジスタを用いた共通鍵暗号のソフトウェア実装が可能になる。
（第二実施形態）
次に、図１から図４を参照して、本発明に係る第二の実施形態について説明する。第一の実施形態では、ブロック暗号、ストリーム暗号、暗号学的ハッシュ関数などの一般的な共通鍵暗号のソフトウェア実装において、少ない余剰レジスタと入出力レジスタを用いたS−boxの計算方法を説明したが、第二の実施形態では、具体的な共通鍵暗号アルゴリズムに対して、少ない余剰レジスタと入出力レジスタを用いてS−boxを計算する方法を説明する。
【００９７】
本実施形態では、具体的な共通鍵暗号アルゴリズムとして、ストリーム暗号向けの疑似乱数生成器Enocoro−128v2を用いて説明する。なお、疑似乱数生成器Enocoro−128v2については、例えば、非特許文献６に記載されている。
【００９８】
第二の実施形態において、第一の実施形態と異なるのは、図１の暗号化処理プログラムPROG1 116、図１のS−box処理プログラムPROG2 (120)に格納されている多項式写像F1, …FL、図１の復号処理プログラムPROG3 (147)、図１のS−box処理プログラムPROG4 (151)に格納されている多項式写像G1, …GLであるため、ここではこれらの説明を記載し、それ以外の構成および処理は図示および説明を省略することとする。つまり、第一の実施形態では、具体的な暗号アルゴリズムは明記せず、どのような暗号アルゴリズムのS−box (ただし、全単射)であっても、入出力レジスタと１本の余剰レジスタで計算可能であることを述べたが、第二の実施形態では、例として、具体的な暗号アルゴリズムについて、第一の実施形態で記述した内容を、どのように実現するか、について述べている。
【００９９】
第二の実施形態では、図１の暗号化処理プログラムPROG1 (116)および図１の復号処理プログラムPROG3 (147)にはストリーム暗号Enocoro−128v2のプログラムが格納されている。
【０１００】
さらに、図１のS−box処理プログラムPROG2 (120)に格納されている多項式写像F1, …FLについては、L ＝ 27であり、各i（1≦i≦L）に対し、図１のS−box処理プログラムPROG2 120に格納されている多項式写像F1,…F27は、図４に示すとおりとする。また、図１のS−box処理プログラムPROG4 151に格納されている多項式写像G1,…G27については、Fi＝Giである。
【０１０１】
なお、図４に示す多項式写像F1,…F27に対し、多項式写像F2i−1（1≦i≦14)は可逆なアフィン多項式写像であり、多項式写像F2i（1≦i≦13)はtriangular多項式写像または基本多項式写像である。
【０１０２】
CPU144が、S−box処理プログラム120から図４に記載の多項式写像F1,…F27を読み込み、入出力レジスタ207に格納されているnビットデータa1,…an、及び上記の読み込んだ多項式写像F1,…F27によってS−boxの変換を行う処理を説明する。
【０１０３】
この計算は、図３に示すフローチャートを用いて計算を行う。
【０１０４】
図４に示した各多項式写像は、基本多項式写像、triangular 多項式写像、又は可逆なアフィン多項式写像の何れかであり、第一の実施形態で説明したように、図５〜図７に示した方法で計算を行うことにより、入出力レジスタ207に格納されているnビットデータa1, … anから基本多項式写像、triangular 多項式写像、可逆なアフィン多項式写像の値を計算できる。
【０１０５】
CPU144から出力されるnビットデータa1,…anは、余剰レジスタ207の1本のレジスタと入出力レジスタ208を用いて計算できる。この理由は第一の実施形態と同様である。
【０１０６】
なお、本実施形態では、第一の実施形態と同様、可逆なアフィン多項式写像、基本多項式写像、及びtriangular多項式写像を、1本の余剰レジスタと入出力レジスタで計算可能であるが、上記多項式写像を、2本以上の余剰レジスタと入出力レジスタで計算してもよいことは第一の実施形態と同様である。
【０１０７】
一般に、多項式写像を、アフィン多項式写像、基本多項式写像、及びtriangular多項式写像の合成の形で表現する方法は一意的ではないが、どのような合成の形であってもよいことは第一の実施形態と同様である。
【０１０８】
（第二実施形態の効果）
第一の実施形態と同様に、第二実施形態のS−box計算方法によれば、1本の余剰レジスタと入出力レジスタを用いてS−boxを計算することが可能となる。すなわち、本実施形態によれば、少ない本数の余剰レジスタを用いたストリーム暗号Enocoro−128v2のソフトウェア実装が可能になる。
【０１０９】
なお、上記の各実施形態では、暗号通信システムとして説明し、暗号化プログラムはブロック暗号、ストリーム暗号として説明したが、認証システムとし、
暗号化プログラムをハッシュ関数プログラムとしてもよい。
【符号の説明】
【０１１０】
101：データ、114：コンピュータＡ、115：RAM、116：暗号化処理プログラムPROG1、117：秘密鍵Key、118：補助情報IV、119：平文M、120：S−box処理プログラムPROG2、124：ディスプレイ、125：キーボード、126：ネットワーク、127：データ、130：入出力インタフェース、144：CPU、145：コンピュータＢ、146：RAM、147：復号処理プログラムPROG3、148：秘密鍵Key、149：補助情報IV、150：平文M、151：S−box処理プログラムPROG4、152：ディスプレイ、153：キーボード、156：入出力インタフェース、157：CPU
【図１】
2013205437.tif 000003
【図２】
2013205437.tif 000004
【図３】
2013205437.tif 000005
【図４】
2013205437.tif 000006
【図５】
2013205437.tif 000007
【図６】
2013205437.tif 000008
【図７】
2013205437.tif 000009