JP2015135587A

JP2015135587A - 拡大体乗算装置、拡大体乗算方法及びプログラム

Info

Publication number: JP2015135587A
Application number: JP2014006335A
Authority: JP
Inventors: 大五十嵐; Masaru Igarashi; 浩気濱田; Hiroki Hamada; 亮菊池; Akira Kikuchi; 千田　浩司; Koji Senda; 浩司千田
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2014-01-17
Filing date: 2014-01-17
Publication date: 2015-07-27
Anticipated expiration: 2034-01-17
Also published as: JP6093718B2

Abstract

【課題】拡大体乗算を高速に計算する。【解決手段】第一シャフル部２は、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’との排他的論理和を計算する。【選択図】図１

Description

この発明は、情報セキュリティ技術に関し、特に、暗号や符号で用いられる、2の拡大体と呼ばれる代数構造上の乗算を計算する技術に関する。

2のm次拡大体要素は、mビットのビット列で表現される。以降、2のm次拡大体をGF(2^m)と書く。GF(2^m)上の加算はビットごとの排他的論理和（XOR）で表現され、計算は容易である。一方、乗算は以下のような意味をもち、加算と比べて複雑である。

まず、m次拡大体要素a∈GF(2^m)の各ビットは以下のようにm-1次多項式a[X]の係数a₀,…,a_m-1として解釈される。

このとき、m次拡大体要素a,bの積ab∈GF(2^m)は、以下のように表される。

ただし、f[X]は既約多項式と呼ばれる特定のm次多項式である。例えば、1+X+X²は2次の既約多項式である。

非特許文献１には、2の拡大体乗算を計算する従来技術として、多項式法、巡回群法、正規規定法、乗算表を利用した手法などが記載されている。

田中哲士、安田貴徳、櫻井幸一、"Graphics processing unitを用いたgf(232)上の高速演算の実装"、コンピュータセキュリティシンポジウム2013、2013年

非特許文献１記載の従来技術は、計算速度が遅いという課題がある。

この発明は、2の拡大体乗算を高速に計算することを目的とする。

上記の課題を解決するために、この発明の拡大体乗算装置は、A,Bを2のm次拡大体のL個の要素からなる値とし、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に対して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(2^m)^Lが入力される。

ステップＳ２において、第一シャフル部２は、i={0,1}について、値Aからシャフルにより次式に示すLmビットの値A’[i]を生成する。

また、第一シャフル部２は、i={0,1}について、値Bからシャフルにより次式に示すLmビットの値B’[i]を生成する。

値A’[0],A’[1],B’[0],B’[1]はキャリー無し乗算部３へ出力される。

ステップＳ３において、キャリー無し乗算部３は、i={0,1}について、値A’[i]及び値B’[i]を入力としてキャリー無し乗算を次式により計算し、値C’[i]を生成する。値C’[0],C’[1]は第二シャフル部及び第三シャフル部へ出力される。

ただし、CLMは2Lmビット入力Lmビット出力のキャリーなし演算を計算する関数である。

ステップＳ４において、第二シャフル部４は、値C’[0],C’[1]からシャフルにより次式に示す値Cを生成する。値Cは排他的論理和部７へ出力される。

ステップＳ５において、第三シャフル部５は、値C’[0],C’[1]からシャフルにより次式に示す値Dを生成する。値Dは剰余計算部６へ出力される。

ステップＳ６において、剰余計算部６は、並列ビット演算により、値Dに対して既約多項式f[X]による剰余を次式により計算し、値D’を生成する。値D’は排他的論理和部７へ出力される。

ステップＳ７において、排他的論理和部７は、値Cと値D’との排他的論理和を計算し、値Eを生成する。値Eは出力部８へ出力される。

ステップＳ８において、出力部８は値Eを出力する。

このように、この発明の拡大体乗算技術は、多ビット長のキャリー無し乗算が利用できるとき、L回の乗算を2回のキャリー無し乗算により並列に同時に計算することができる。したがって、2の拡大体乗算を高速に計算することができる。

この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。

［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

１０拡大体乗算装置
１入力部
２第一シャフル部
３キャリー無し乗算部
４第二シャフル部
５第三シャフル部
６剰余計算部
７排他的論理和部
８出力部

Claims

A,Bを2のm次拡大体のL個の要素からなる値とし、
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に対してm次の既約多項式f[X]による剰余を計算し、値D’を生成する剰余計算部と、
値Cと値D’との排他的論理和を計算する排他的論理和部と、
を含む拡大体乗算装置。
請求項１に記載の拡大体乗算装置であって、
上記第一シャフル部及び上記キャリー無し乗算部は、i={0,1}について、並列かつ同時に処理を行うものである
拡大体乗算装置。
A,Bを2のm次拡大体のL個の要素からなる値とし、
第一シャフル部が、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に対してm次の既約多項式f[X]による剰余を計算し、値D’を生成する剰余計算ステップと、
排他的論理和部が、値Cと値D’との排他的論理和を計算する排他的論理和ステップと、
を含む拡大体乗算方法。
請求項３に記載の拡大体乗算方法であって、
上記第一シャフルステップ及び上記キャリー無し乗算ステップは、i={0,1}について、並列に同時に処理を行う
拡大体乗算方法。
請求項１又は２に記載の拡大体乗算装置としてコンピュータを機能させるためのプログラム。