(57)【要約】【課題】拡大体乗算を高速に計算する。【解決手段】第一シャフル部２は、i={0,1}について、値Aからシャフルにより値A’[i]を生成し、値Bからシャフルにより値B’[i]を生成する。キャリー無し乗算部３は、i={0,1}について、値A’[i]及び値B’[i]を入力としてキャリー無し乗算により値C’[i]を計算する。第二シャフル部４は、値C’[0],C’[1]からシャフルにより値Cを生成する。第三シャフル部５は、値C’[0],C’[1]からシャフルにより値Dを生成する。剰余計算部６は、値Dに対して既約多項式f[X]による剰余を計算し、値D’を生成する。排他的論理和部７は、値Cと値D’との排他的論理和を計算する。【選択図】図１
2015135587.tif 000002
【特許請求の範囲】
【請求項１】
A,Bを2のm次拡大体のL個の要素からなる値とし、
i={0,1}について、値Aから次式に示す値A’[i]を生成し、値Bから次式に示す値B’[i]を生成する第一シャフル部と、
【数１３】
2015135587.tif 000015
i={0,1}について、値A’[i]及び値B’[i]を入力としてキャリー無し乗算により値C’[i]を計算するキャリー無し乗算部と、
値C’[0],C’[1]から次式に示す値Cを生成する第二シャフル部と、
【数１４】
2015135587.tif 000016
値C’[0],C’[1]から次式に示す値Dを生成する第三シャフル部と、
【数１５】
2015135587.tif 000017
値Dに対してm次の既約多項式f[X]による剰余を計算し、値D’を生成する剰余計算部と、
値Cと値D’との排他的論理和を計算する排他的論理和部と、
を含む拡大体乗算装置。
【請求項２】
請求項１に記載の拡大体乗算装置であって、
上記第一シャフル部及び上記キャリー無し乗算部は、i={0,1}について、並列かつ同時に処理を行うものである
拡大体乗算装置。
【請求項３】
A,Bを2のm次拡大体のL個の要素からなる値とし、
第一シャフル部が、i={0,1}について、値Aから次式に示す値A’[i]を生成し、値Bから次式に示す値B’[i]を生成する第一シャフルステップと、
【数１６】
2015135587.tif 000018
キャリー無し乗算部が、i={0,1}について、値A’[i]及び値B’[i]を入力としてキャリー無し乗算により値C’[i]を計算するキャリー無し乗算ステップと、
第二シャフル部が、値C’[0],C’[1]から次式に示す値Cを生成する第二シャフルステップと、
【数１７】
2015135587.tif 000019
第三シャフル部が、値C’[0],C’[1]から次式に示す値Dを生成する第三シャフルステップと、
【数１８】
2015135587.tif 000020
剰余計算部が、値Dに対してm次の既約多項式f[X]による剰余を計算し、値D’を生成する剰余計算ステップと、
排他的論理和部が、値Cと値D’との排他的論理和を計算する排他的論理和ステップと、
を含む拡大体乗算方法。
【請求項４】
請求項３に記載の拡大体乗算方法であって、
上記第一シャフルステップ及び上記キャリー無し乗算ステップは、i={0,1}について、並列に同時に処理を行う
拡大体乗算方法。
【請求項５】
請求項１又は２に記載の拡大体乗算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関し、特に、暗号や符号で用いられる、2の拡大体と呼ばれる代数構造上の乗算を計算する技術に関する。
【背景技術】
【０００２】
2のm次拡大体要素は、mビットのビット列で表現される。以降、2のm次拡大体をGF(2m)と書く。GF(2m)上の加算はビットごとの排他的論理和（XOR）で表現され、計算は容易である。一方、乗算は以下のような意味をもち、加算と比べて複雑である。
【０００３】
まず、m次拡大体要素a∈GF(2m)の各ビットは以下のようにm-1次多項式a[X]の係数a0,…,am-1として解釈される。
【０００４】
【数１】
2015135587.tif 000003
【０００５】
このとき、m次拡大体要素a,bの積ab∈GF(2m)は、以下のように表される。
【０００６】
【数２】
2015135587.tif 000004
【０００７】
ただし、f[X]は既約多項式と呼ばれる特定のm次多項式である。例えば、1+X+X2は2次の既約多項式である。
【０００８】
非特許文献１には、2の拡大体乗算を計算する従来技術として、多項式法、巡回群法、正規規定法、乗算表を利用した手法などが記載されている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】田中哲士、安田貴徳、櫻井幸一、“Graphics processing unitを用いたgf(232)上の高速演算の実装”、コンピュータセキュリティシンポジウム2013、2013年
【発明の概要】
【発明が解決しようとする課題】
【００１０】
非特許文献１記載の従来技術は、計算速度が遅いという課題がある。
【００１１】
この発明は、2の拡大体乗算を高速に計算することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、この発明の拡大体乗算装置は、A,Bを2のm次拡大体のL個の要素からなる値とし、i={0,1}について、値Aから次式に示す値A’[i]を生成し、値Bから次式に示す値B’[i]を生成する第一シャフル部と、
【００１３】
【数３】
2015135587.tif 000005
【００１４】
i={0,1}について、値A’[i]及び値B’[i]を入力としてキャリー無し乗算により値C’[i]を計算するキャリー無し乗算部と、値C’[0],C’[1]から次式に示す値Cを生成する第二シャフル部と、
【００１５】
【数４】
2015135587.tif 000006
【００１６】
値C’[0],C’[1]から次式に示す値Dを生成する第三シャフル部と、
【００１７】
【数５】
2015135587.tif 000007
【００１８】
値Dに対してm次の既約多項式f[X]による剰余を計算し、値D’を生成する剰余計算部と、値Cと値D’との排他的論理和を計算する排他的論理和部と、を含む。
【発明の効果】
【００１９】
この発明によれば、2の拡大体乗算を高速に計算することができる。
【図面の簡単な説明】
【００２０】
【図１】図１は、拡大体乗算装置の機能構成を例示する図である。
【図２】図２は、拡大体乗算方法の処理フローを例示する図である。
【発明を実施するための形態】
【００２１】
この発明は、Lmビットのキャリー無し乗算と呼ばれる処理とシャッフルと呼ばれる処理が利用できるときに、L回分の2のm次拡大体乗算を高速に並列処理する方法である。
【００２２】
キャリーとは繰り上がりを意味し、キャリー無し乗算とは、例えば、筆算で乗算を行った際の桁ごとの繰り上がりが無いような乗算である。特に、この発明では二進数の場合を言う。シャッフルとは、ベクトルがあるときに並び順を指定して各要素を並び替える操作である。
【００２３】
近年のＣＰＵ（Central Processing Unit、中央演算処理装置）には、64ビットキャリー無し乗算や128ビットもしくは256ビットシャッフルを搭載しているものが存在する。
【００２４】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２５】
［実施形態］
図１を参照して、拡大体乗算装置１の構成例を説明する。拡大体乗算装置１０は、入力部１、第一シャフル部２、キャリー無し乗算部３、第二シャフル部４、第三シャフル部５、剰余計算部６、排他的論理和部７及び出力部８を含む。拡大体乗算装置１０は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。拡大体乗算装置１０は、例えば、中央演算処理装置の制御のもとで各処理を実行する。拡大体乗算装置１０に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２６】
図２を参照しながら、実施形態に係る拡大体乗算装置１０が実行する拡大体乗算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００２７】
ステップＳ１において、入力部１へLmビットの2個の値A,B∈GF(2m)Lが入力される。
【００２８】
ステップＳ２において、第一シャフル部２は、i={0,1}について、値Aからシャフルにより次式に示すLmビットの値A’[i]を生成する。
【００２９】
【数６】
2015135587.tif 000008
【００３０】
また、第一シャフル部２は、i={0,1}について、値Bからシャフルにより次式に示すLmビットの値B’[i]を生成する。
【００３１】
【数７】
2015135587.tif 000009
【００３２】
値A’[0],A’[1],B’[0],B’[1]はキャリー無し乗算部３へ出力される。
【００３３】
ステップＳ３において、キャリー無し乗算部３は、i={0,1}について、値A’[i]及び値B’[i]を入力としてキャリー無し乗算を次式により計算し、値C’[i]を生成する。値C’[0],C’[1]は第二シャフル部及び第三シャフル部へ出力される。
【００３４】
【数８】
2015135587.tif 000010
【００３５】
ただし、CLMは2Lmビット入力Lmビット出力のキャリーなし演算を計算する関数である。
【００３６】
ステップＳ４において、第二シャフル部４は、値C’[0],C’[1]からシャフルにより次式に示す値Cを生成する。値Cは排他的論理和部７へ出力される。
【００３７】
【数９】
2015135587.tif 000011
【００３８】
ステップＳ５において、第三シャフル部５は、値C’[0],C’[1]からシャフルにより次式に示す値Dを生成する。値Dは剰余計算部６へ出力される。
【００３９】
【数１０】
2015135587.tif 000012
【００４０】
ステップＳ６において、剰余計算部６は、並列ビット演算により、値Dに対して既約多項式f[X]による剰余を次式により計算し、値D’を生成する。値D’は排他的論理和部７へ出力される。
【００４１】
【数１１】
2015135587.tif 000013
【００４２】
ステップＳ７において、排他的論理和部７は、値Cと値D’との排他的論理和を計算し、値Eを生成する。値Eは出力部８へ出力される。
【００４３】
【数１２】
2015135587.tif 000014
【００４４】
ステップＳ８において、出力部８は値Eを出力する。
【００４５】
このように、この発明の拡大体乗算技術は、多ビット長のキャリー無し乗算が利用できるとき、L回の乗算を2回のキャリー無し乗算により並列に同時に計算することができる。したがって、2の拡大体乗算を高速に計算することができる。
【００４６】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４７】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５２】
１０  拡大体乗算装置
１  入力部
２  第一シャフル部
３  キャリー無し乗算部
４  第二シャフル部
５  第三シャフル部
６  剰余計算部
７  排他的論理和部
８  出力部
【図１】
2015135587.tif 000021
【図２】
2015135587.tif 000022