(57)【要約】【課題】ガロア拡大体ＧＦ（２m）の乗法逆元演算処理において、高速化を実現する。【解決手段】ガロア拡大体ＧＦ（２m ）上の既約多項式に関する乗法逆元演算において、正規基底に基づいて２k乗演算（ｋは０以上の整数）がｋ回のＧＦ（２）上の右巡回シフトによって実行できることを用い、２k回の右巡回シフトを実行する２2^k乗演算と２元の乗算とを行って乗法逆元を算出する。【選択図】      図２
2007187725.tif 000002
【特許請求の範囲】
【請求項１】
標数をＰ（Ｐは素数）、拡大次数をｍ（ｍは２以上の整数）とするガロア拡大体ＧＦ（Ｐm ）上の既約多項式に関する乗法逆元を算出するガロア逆元演算高速化処理装置において、
前記標数Ｐが２、拡大次数ｍが２s＋１（ｓは０以上の整数）であるガロア拡大体ＧＦ（２m ）における乗法逆元を算出する逆元演算手段を備え、該逆元演算手段は、正規基底に基づいて２k回（ｋは０以上ｓ−１以下の整数）のＧＦ（２）上の右巡回シフトを実行する２2^k乗演算手段と、２元の乗算を行う乗算手段とを有し、前記２2^k乗演算手段によるｍ−１回のＧＦ（２）上の右巡回シフトと、前記乗算手段によるｌｏｇ2（ｍ−１）回の乗算とによってガロア拡大体ＧＦ（２m ）における乗法逆元を算出することを特徴とするガロア逆元演算高速化処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガロア拡大体ＧＦ（２m）の乗法逆元演算を高速で実現することを可能とするガロア逆元演算高速化処理装置に関する。
【背景技術】
【０００２】
従来のガロア逆元演算高速化処理装置としては、フェルマーの小定理を用いて乗法逆元を計算するというものが知られている（例えば、非特許文献１、非特許文献２参照）。
フェルマーの小定理とは、Ｐを素数、ΧをＰで割り切れない整数としたとき、ΧP-1−１はＰで割り切れる、即ち、ΧP-1≡１（ｍｏｄ  Ｐ）が成立するというものである。これは、Ｐを法とするΧの逆元はΧP-2であることを示しており、このフェルマーの小定理を用いると、ガロア拡大体ＧＦ（２m）の乗法逆元は次式をもとに算出することができる。
【０００３】
Χ-1＝Χ2^m-2＝（Χ2）（Χ2）2（Χ2）4…（Χ2）m-1  ………（１）
この式のとおりに計算を進めると、乗法逆元を求めるには（ｍ−２）回の乗算が必要になる。
ところで、ソフト／ハードウェア向けの逆数演算アルゴリズムの評価ポイントは、乗算処理の回数、シフトローテイト処理の回数及びレイテンシ（順序回路の場合はクロック数×クロック周波数）である。
【０００４】
上記（１）式に示す公式の計算を、例えばガロア拡大体ＧＦ（２9）ハードウェア順序回路として作る場合には、図３に示すように７個の乗算回路と８個の２乗回路を持つことになる。このように、（Χ2）のｉ乗を求めながら（ｍ−２）回のループで計算するアルゴリズムがよく用いられる。このとき、レイテンシ（サイクル数）は（ｍ−２）となる。
また、高速化を実現するため、組み合わせ回路で実現する場合には、木構造を作れば、Ｍを乗算回路のレイテンシとして次式で表される。
Ｍ＝ｌｏｇ2（ｍ−１）＋１  ………（２）
ここで、一般に、べき乗演算のレイテンシはごく小さいので無視する。
【０００５】
また、他の逆元演算処理方法として、乗算と部分体上での乗法逆元演算の組み合わせによる方法も知られている。
これは、ガロア拡大体ＧＦ（２m）においてｍ＝ｋｑ（ｍが合成数）であるとき、ＧＦ（２m）の乗法逆元演算をＧＦ（２m）の乗算とＧＦ（２k）（ないしＧＦ（２q））の乗法逆元演算に帰着する方法である。これにより、うまく原始多項式や表現基底を選定すれば、かなり回路規模が縮小され、回路速度も速くなる場合がある。
【０００６】
さらに、他の方法として、多項式上でユークリッド互除法を用いて乗法逆元を計算する方法も知られている。
これは、入力多項式（乗法逆元を求めたい多項式）をＡ、原始多項式をＦとしたとき、ユークリッド互除法でＢＡ＋ＦＭ＝１を満たすＢ，Ｍを求めると、ガロア体上ではＢがＡの乗法逆元になるという性質を利用したものである。この方法は、一般にレイテンシが０（ｍ）となるという問題がある。
【０００７】
【非特許文献１】S.B.Wicker and V.K.Bhargava(eds.), Reed-Solom on Codes   and their Applications, IEEE Press, 1994.
【非特許文献２】J.Guajardo and C.Paar, "Efficient Algorithms for Ellip  tic Curve Cryptosystems," proc. of 17th Annual Intl. Cryptology Conf.(CRYPTO'  97), LNCS1294, pp.342-356, 1997.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記従来のガロア逆元演算方法にあっては、ガロア拡大体ＧＦ（２m）の乗法逆元演算を行う場合には、（ｍ−２）回の乗算が必要であるので、例えば、ガロア拡大体ＧＦ（２9）上の既約多項式に関する乗法逆元演算を行う場合には、７回の乗算が必要となる。この乗算回数は拡大次数ｍに比例して増加することになり、拡大次数ｍが大きくなるほど逆元演算処理時間が長くなり、ＣＰＵの負荷が増大するという未解決の課題がある。
【０００９】
また、上記従来の乗算と部分体上での乗法逆元演算の組み合わせによる方法にあっては、限られた特定の場合にしか使用できず、例えば、ｍが素数である場合には全く使用できなかったり、ターゲットの体ＧＦ（２m）の原始多項式によっては回路規模や速度の向上が得られなかったりするという未解決の課題がある。
そこで、本発明は、上記従来例の未解決の課題に着目してなされたものであり、ガロア拡大体ＧＦ（２m）の逆元演算の高速化を実現することにより、処理時間を短縮してＣＰＵの負荷を低減することができるガロア逆元演算高速化処理装置を提供することを目的としている。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、請求項１に係るガロア逆元演算高速化処理装置は、前記標数Ｐが２、拡大次数ｍが２s＋１（ｓは０以上の整数）であるガロア拡大体ＧＦ（２m ）における乗法逆元を算出する逆元演算手段を備え、該逆元演算手段は、正規基底に基づいて２k回（ｋは０以上ｓ−１以下の整数）のＧＦ（２）上の右巡回シフトを実行する２2^k乗演算手段と、２元の乗算を行う乗算手段とを有し、前記２2^k乗演算手段によるｍ−１回のＧＦ（２）上の右巡回シフトと、前記乗算手段によるｌｏｇ2（ｍ−１）回の乗算とによってガロア拡大体ＧＦ（２m ）における乗法逆元を算出することを特徴としている。
【００１１】
この請求項１に係る発明では、拡大次数ｍが２s＋１（ｓは０以上の整数）であるガロア拡大体ＧＦ（２m ）における乗法逆元を算出する際に、正規基底に基づいて２k乗演算（ｋは０以上の整数）がｋ回のＧＦ（２）上の右巡回シフトによって実行できることを用い、２k回のＧＦ（２）上の右巡回シフトを実行する２2^k乗演算と２元の乗算とによって逆元演算を行う。そのため、従来のアルゴリズムのように（Χ2）のｉ乗を求めながら（ｍ−２）回のループで計算する必要がなくなり、２元の乗算回数を従来の（ｍ−２）回からｌｏｇ2（ｍ−１）回に大幅に減少させることができ、逆元演算処理時間を大幅に短縮することができる。
【発明の効果】
【００１２】
本発明の請求項１に係る発明によれば、拡大次数ｍが２s＋１（ｓは０以上の整数）であるガロア拡大体ＧＦ（２m ）における乗法逆元を算出する際に、正規基底に基づいて２k乗演算がｋ回のＧＦ（２）上の右巡回シフトによって実行できることを用いて、２k回のＧＦ（２）上の右巡回シフトを実行する２2^k乗演算を行うことにより、２元の乗算回数を大幅に減少して処理時間を短縮することができると共に、逆元演算を行うＣＰＵの負荷を低減することができるという効果が得られる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態を図面に基づいて説明する。
ガロア体の乗法逆元演算は、様々なアプリケーションに利用されている。本発明では、正規基底を用いてガロア拡大体ＧＦ（２m）（ここで、ｍ＝２s＋１）の逆元演算の高速化を実現することにより、逆元演算処理時間を短縮してＣＰＵの負荷を低減する。
先ず、ガロア体について説明する。
【００１４】
ガロア体は、加減乗除が自由にできる有限個の元からなる集合であり、元の個数は体の位数と呼ばれる。素数Ｐを位数とするガロア体は素体と呼ばれ、ＧＦ（Ｐ）のように表記される。ガロア体は素体ＧＦ（Ｐ）或いは素数のべき乗数位数の体ＧＦ（Ｐm）としてしか存在しないことが示されており、ＧＦ（Ｐm）はＧＦ（Ｐ）上のｍ次拡大体と呼ばれる。
【００１５】
例えば、標数が２の拡大体ＧＦ（２m）とは、ＧＦ（２）のｍ次元ベクトル空間をいい、各元は（０，１，０，０，…）のようにｍ個の０と１で表される。
ＧＦ（Ｐm）は、ＧＦ（Ｐ）上のｍ次既約多項式を用いることで構成できる。ここで、ＧＦ（Ｐ）上のｍ次既約多項式とは、ＧＦ（Ｐ）の元を係数としてもつ多項式であり、且つ１次以上ｍ次未満の多項式により割り切れない多項式のことである。
【００１６】
次に、正規基底について説明する。
任意の要素ａ∈ＧＦ（ｑm）（ここで、ｑ＝ｐn  ｐ：素数）に対し、［ａ，ａq，…，ａq^(m-1)］がＧＦ（ｑ）上の１次独立のとき、［ａ，ａq，…，ａq^(m-1)］をＧＦ（ｑm）のＧＦ（ｑ）上の正規基底という。
また、この定理には、以下の補題が証明されている。
（補題１）  任意のＧＦ（ｑm）（ここで、ｑ＝ｐn  ｐ：素数）において、少なくとも１組の正規基底が存在する。
（補題２）  ∀χ∈ＧＦ（ｑm）、正規基底［ａ，ａq，…，ａq^(m-1)］により、
χ＝χ0ａ＋χ1ａq＋…＋χm-1ａq^(m-1)
＝［χ0，χ1，…，χm-1］  ………（５）
とベクトル表示されているものとする。このとき、χqは、
χq＝χm-1ａ＋χ0ａq＋χ1ａq^2＋…＋χm-2ａq^(m-2)
＝［χm-1，χ0，χ1，…，χm-2］  ………（６）
のように、１回の右巡回シフトで実行できる。
【００１７】
本発明では、この正規基底を用いてＧＦ（２m）における逆元の高速化を提案する。
上記（補題２）より、ｑ＝２であるときには、χ2＝［χm-1，χ0，χ1，…，χm-2］となり、２乗算は１回のＧＦ（２）上の右巡回シフトにより実行できる。また、４乗算（２2乗算）は２回のＧＦ（２）上の右巡回シフトにより実行することができる。
これにより、２k乗演算はｋ回のＧＦ（２）上の右巡回シフトにより実行できることがわかる。
【００１８】
したがって、今、ＧＦ（２m）（ここで、ｍ＝２s＋１）において、∀χ∈ＧＦ（２m）（ここで、χ≠０）の逆元χ-1を求めるのに要するＧＦ（２m）における乗算回数をＭ（ｍ）、ＧＦ（２）上の巡回シフト回数をＳ（ｍ）とする。
このとき、
Ｍ（ｍ）＝ｓ＝ｌｏｇ2（ｍ−１）  ………（７）
Ｓ（ｍ）＝２s＝ｍ−１  ………（８）
で逆元χ-1を求めるアルゴリズムが存在する。
【００１９】
これを証明するために、先ず、ｍ＝２s＋１であるとき、（２m−２）を２進数表示する。すると、次式のように、１が２s個連続して並ぶことになる。
（２m−２）＝［１１…１１０］  ………（９）
また、χ-1＝χ2^m-2であるので、∀χ∈ＧＦ（２m）（ここで、χ≠０）に対して逆元χ-1を求めるには、先ず、次式で表されるｙを算出する。
ｙ＝χ[11…11]  ………（１０）
【００２０】
ここで、χの指数は１が２s個連続して並ぶものとする。１が２s個連続して並ぶ［１１…１１］を２倍すると、１が２s個連続して並ぶ［１１…１１０］となる。そこで、上記（１０）式からｙ2を算出すれば、逆元χ-1を求めることができる。
ｙ2＝χ[11…110]＝χ2^m-2＝χ-1  ………（１１）
【００２１】
そこで、１≦ｔ≦ｓに対して、χ[11…11]を求めることを考える。このχの指数は、１が２t個連続して並ぶものとする。
今、χ[11…11]（χの指数は１が２t個連続）を求めるのに要するＧＦ（２m）における乗算回数をｍt、ＧＦ（２）上の右巡回シフト回数をｃtとする。
ここで、χ[11…11] （χの指数は１が２t個連続）は下記（１２）式で表すことができる。
【００２２】
【数１】
2007187725.tif 000003
【００２３】
したがって、上記（１２）式より、ｍt及びｃtは下記（１３）及び（１４）式のようになる。
ｍt＝ｍt-1＋１  ………（１３）
ｃt＝ｃt-1＋２t-1  ………（１４）
ここで、明らかにｍ0＝０、ｃ0＝０であるので、前記（１３）及び（１４）式より下記（１５）及び（１６）式を得る。
ｍs＝ｓ  ………（１５）
ｃs＝Σ２i＝２s−１  ………（１６）
上記（１６）式において、Σはｉ＝０から（ｓ−１）までの２iの和を求める関数とする。
【００２４】
ところで、χ-1を求めるには、前記（１０）式のｙに対してｙ2を計算する。つまり、１回のＧＦ（２）上の右巡回シフトを施す必要があるので、結局、Ｍ（ｍ）及びＳ（ｍ）は下記（１７）及び（１８）式のようになる。
Ｍ（ｍ）＝ｍt＝ｓ＝ｌｏｇ2（ｍ−１）  ………（１７）
Ｓ（ｍ）＝ｃs＋１＝２s＝ｍ−１  ………（１８）
このように、前記（７）及び（８）式を証明することができる。
【００２５】
次に、この定理のアルゴリズムの具体例について説明する。
今、∀χ∈［χ0，χ1，…，χ8］＝ＧＦ（２9）に対し、その逆元χ-1を求めるものとする。このとき、逆元χ-1を求めるには、
χ-1＝χ2^m-2＝χ2^9-2＝χ510＝χ[111111110]  ………（１９）
を計算すればよい。
【００２６】
ガロア拡大体ＧＦ（２m）（ｍ＝ｓ＋１）の逆元演算手順を示すフローチャートは、図１に示すようになり、先ずステップＳ１で変数ｙをχとする。次いでステップＳ２に移行して、ループ変数ｋを初期値０に設定し、ステップＳ３に移行する。
ステップＳ３では、次式によって変数ｚを算出する。
ｚ＝ｙ2^2^k  ………（２０）
次にステップＳ４で、変数ｙと前記ステップＳ３で算出したｚとを乗算し、新たな変数ｙとして算出する。
ｙ＝ｙｚ  ………（２１）
【００２７】
次にステップＳ５で、ループ変数ｋをインクリメントしてステップＳ６に移行し、ループ変数ｋが（ｓ−１）より大きいか否かを判定する。ステップＳ６の判定結果がｋ≦ｓ−１であるときには前記ステップＳ３に移行し、ｋ＞ｓ−１であるときには、ステップＳ７に移行して次式をもとに変数ｙを算出する。
ｙ＝ｙ2  ………（２２）
【００２８】
上記（２２）式によって算出されたｙがガロア拡大体ＧＦ（２m）の逆元χ-1となる。
したがって、ガロア拡大体ＧＦ（２9）に対し、その逆元χ-1を求める場合には、先ず、図１のステップＳ３でｙ2^2^0＝ｙ2^1、即ちＧＦ（２）上の右巡回シフトを１回行ってχ[10]を算出する。
（χ[1]）2＝χ[10]  ………（２３）
【００２９】
次にステップＳ４に移行して、上記（２３）式により算出したχ[10]とχ[1]との乗算、即ちＧＦ（２9）上の乗算を１回行ってχ[11]を算出し、ステップＳ５に移行する。
χ[10]χ[1]＝χ[11]   ………（２４）
ステップＳ５ではループ変数ｋをインクリメントしてｋ＝１とし、拡大次数ｍ＝９であるのでｓ＝３であり、ｋ≦ｓ−１であるのでステップＳ３に移行して、ｙ2^2^1＝ｙ2^2、即ちＧＦ（２）上の右巡回シフトを２回行ってχ[1100]を算出する。
（χ[11]）2^2＝χ[1100]  ………（２５）
【００３０】
次にステップ４では、ＧＦ（２9）上の乗算を１回行ってχ[1111]を算出し、ステップＳ５に移行する。
χ[1100]χ[11]＝χ[1111]   ………（２６）
ステップＳ５ではループ変数ｋをインクリメントしてｋ＝２とし、ｋ≦ｓ−１であるのでステップＳ３に移行して、ｙ2^2^2＝ｙ2^4、即ちＧＦ（２）上の右巡回シフトを４回行ってχ[11110000]を算出する。
（χ[1111]）2^4＝χ[11110000]  ………（２７）
【００３１】
次にステップ４では、ＧＦ（２9）上の乗算を１回行ってχ[11111111]を算出し、ステップＳ５に移行する。
χ[11110000]χ[1111]＝χ[11111111]   ………（２８）
そして、ステップＳ５でループ変数ｋをインクリメントしてｋ＝３とし、ｋ＞ｓ−１となるのでステップＳ７に移行してｙ2、即ちＧＦ（２）上の右巡回シフトを１回行ってχ[111111110]を算出する。
（χ[11111111]）2＝χ[111111110]  ………（２９）
上記（２９）式をもとに算出されたχ[111111110]が、ＧＦ（２9）における逆元χ-1となる。
【００３２】
図２は、ガロア拡大体ＧＦ（２9）における逆元演算処理を示す回路図である。このように、逆元演算回路は、２2^k演算手段としての２2^k演算回路と乗算手段としての２元の乗算回路とによって構成されている。
また、このときの乗算回数Ｍ（ｍ）と巡回シフト回数Ｓ（ｍ）は、前記（７）及び（８）式よりＭ（ｍ）＝３、Ｓ（ｍ）＝８となる。これは、上記逆元演算処理手順からも明らかである。
【００３３】
一方、従来の逆元演算処理においては、前述したように（ｍ−２）回の乗算が必要である。そのため、ＧＦ（２9）における逆元χ-1を求める際には、図３に示すように７回の乗算と８回の右巡回シフトとが必要となる。
したがって、本発明のアルゴリズムを用いることにより、従来のアルゴリズムと比較して、ＧＦ（２9）における乗算回数を７回から３回へと著しく減少させることができることがわかる。
【００３４】
このように、上記実施形態においては、ガロア拡大体ＧＦ（２m ）における乗法逆元を算出する際に、正規基底に基づいて、２k乗演算がｋ回のＧＦ（２）上の右巡回シフトによって実行できることを用いるので、逆元演算の高速化を実現して処理時間を短縮することができると共に、逆元演算を行うＣＰＵの負荷を低減することができる。
また、ガロア拡大体ＧＦ（２m ）における乗法逆元を算出する際に、２k回のＧＦ（２）上の右巡回シフトを実行する２2^k乗演算を行うことにより、２元の乗算回数を従来の（ｍ−２）回からｌｏｇ2（ｍ−１）回に大幅に減少して処理時間を短縮することができる。
【図面の簡単な説明】
【００３５】
【図１】本発明におけるガロア拡大体ＧＦ（２9）の逆元演算処理手順を示すフローチャートである。
【図２】本発明におけるガロア拡大体ＧＦ（２9）の逆元演算処理を示す回路図である。
【図３】従来のガロア拡大体ＧＦ（２9）の逆元演算処理を示す回路図である。
【図１】
2007187725.tif 000004
【図２】
2007187725.tif 000005
【図３】
2007187725.tif 000006