(57)【要約】【課題】ペアリング暗号の高速化を実現する多倍長整数演算装置を提供する。【解決手段】q0-q3レジスタにa7-a0,b7-b0を格納する格納部と、q4-q5レジスタにb6,b7,b4,b5,b2,b3,b0,b1を格納する置換部と、q6,q7←mul_mul(dj,dj+4,dj+8)を実行する乗算部と、i=0,またはj=N/2-1の場合にq8,q9,q10←shift_blk(q6,q7,q9)を実行し、それ以外の場合にq8,q9,q10←add_long(q6,q7,q8,q9,q10)を実行する途中加算部と、q8,q9←marge(q8,q9,q10)を実行し、c2n,c2n+1,carry,r4←add_str(q8,r4,carry)を実行するマージ加算部と、c2N−2,c2N−1,carry,r4←add_str(q9,r4,carry)を実行する加算部とを含む。【選択図】図４
2014137415.tif 000002
【特許請求の範囲】
【請求項１】
x,yをx≧5,y≧11を充たす整数とし、
128bitの記憶領域であるy個のq-レジスタq0,...,qy−1と、
q-レジスタを二つに分割した64bitの記憶領域である2y個のd-レジスタd0,...,d2y−1と、
32bitの記憶領域であるx個のr-レジスタr0,...,rx−1を備える多倍長整数演算装置であって、
pを256bit以下の素数とし、
Fpを素体とし、
a,bを素体Fp上の要素とし、
通常環境のワード長W、サイズN=┌(└log2p┘+1)=W┐により、
【数２３】
2014137415.tif 000025
と表現されるものとし、
carryをキャリービットとし、32bit加算で発生するオーバーフロー{0,1}が格納されるものとし、
ビット列に対するq-レジスタの表現を[ビット列]qとし、
ビット列に対するd-レジスタの表現を[ビット列]dとし、
ビット列に対するr-レジスタの表現を[ビット列]rとし、
矢印記号は代入を意味するものとし、[ ]内に示すカンマ記号は、カンマ記号の両側に位置する各ビット列のビット長が互いに等しくなるように分割する記号とし、任意のビット列である第1から第4ビット列に対して、
演算記号addsを([第1ビット列+第2ビット列]r,carry)←[第1ビット列]r+[第2ビット列]rとし、
演算記号adcsを([第1ビット列+第2ビット列+carry]r,carry)←[第1ビット列]r+[第2ビット列]r+carryとし、
演算記号ldrを[ビット列]r=r*←ビット列とし、
演算記号strをビット列←r*=[ビット列]rとし、
演算記号vmovを[第1ビット列]r,[第2ビット列]r←[第1ビット列,第2ビット列]dとし、
演算記号vaddlを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[第1ビット列,第3ビット列]d+[第2ビット列,第4ビット列]dとし、
演算記号vaddwを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[[第1ビット列]d,[第3ビット列]d]q+[第2ビット列,第4ビット列]dとし、
演算記号vmullを[[第1ビット列×第2ビット列]d,[第3ビット列×第4ビット列]d]q←[第1ビット列,第3ビット列]d×[第2ビット列,第4ビット列]dとし、
演算記号vaddを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[[第1ビット列]d,[第3ビット列]d]q+[[第2ビット列]d,[第4ビット列]d]qとし、
演算記号vmovlを[[第1ビット列]d,[第2ビット列]d]q←[第1ビット列,第2ビット列]dとし、
演算記号vldを[ビット列]q=q*←ビット列とし、
演算記号vstをビット列←q*=[ビット列]qとし、
記号s*,t*,s~*,t~*,s'*,t'*,s~'*,t~'*を、各32bitの一時変数とし、
mul_mul(di,dj+4,dj+8)は、
di=[a2i+1,a2i]d,dj+4=[b2j+1,b2j]d,dj+8=[b2j,b2j+1]dを入力とし、
q6←vmull di,dj+4
q7←vmull di,dj+8
を計算して、
q6=[a2i+1b2j+1,a2ib2j]q,q7=[a2i+1b2j,a2ib2j+1]qを出力する計算式を表すものとし、
shift_blk(q6,q7,q9)は、
q6=[a2i+1b2j+1,a2ib2j]q
q7=[a2i+1b2j,a2ib2j+1]q
q9=[[s2n+1,t2n+1]d[s2n,t2n]d]q
を入力とし、
q8←vaddw q9,d12
q9←vmovl d13
q10←vaddl d14,d15
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
q10=[[s~'2n+2,t~'2n+2]d,[s~'2n+1,t~'2n+1]d]q
を出力する計算式を表すものとし、
add_long(q6,q7,q8,q9,q10)は、
q6=[a2i+1b2j+1,a2ib2j]q
q7=[a2i+1b2j,a2ib2j+1]q
q8=[[s2n+1,t2n+1]d,[s2n,t2n]d]q
q9=[[s2n+3,t2n+3]d,[s2n+2,t2n+2]d]q
q10=[[s~2n+2,t~2n+2]d,[s~2n+1,t~2n+1]d]q
を入力とし、
q8←vaddw q8,d12
q9←vaddw q9,d13
q10←vaddw q10,d14
q10←vaddw q10,d15
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
q10=[[s~'2n+2,t~'2n+2]d,[s~'2n+1,t~'2n+1]d]q
を出力する計算式を表すものとし、
marge(q8,q9,q10)は、
q8=[[s2n+1,t2n+1]d,[s2n,t2n]d]q
q9=[[s2n+3,t2n+3]d,[s2n+2,t2n+2]d]q
q10=[[s~2n+2,t~2n+2]d,[s~2n+1,t~2n+1]d]q
を入力とし、
d17←vadd d17,d20
d18←vadd d18,d21
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
を出力する計算式を表すものとし、
add_str(q*,r4,carry)は、
q*=[[s2n+1,t2n+1]d,[s2n,t2n]d]q,r4,carry
を入力とし、
r1,r2←vmov d2*
c2n,carry←adcs r1,r4,carry
r3,r4←vmov d2*+1
c2n+1,carry←adcs r3,r2,carry
を計算して、
c2n,c2n+1,r4,carryを出力する計算式を表すものとし、
q0-レジスタのd0-レジスタにa1,a0を、d1-レジスタにa3,a2を格納し、q1-レジスタのd2-レジスタにa5,a4を、d3-レジスタにa7,a6を格納し、q2-レジスタのd4-レジスタにb1,b0を、d5-レジスタにb3,b2を格納し、q3-レジスタのd6-レジスタにb5,b4を、d7-レジスタにb7,b6を格納する格納部と、
q4-レジスタのd8-レジスタに置換後のb0,b1を、d9-レジスタに置換後のb2,b3を、q5-レジスタのd10-レジスタに置換後のb4,b5を、d11-レジスタに置換後のb6,b7を格納する置換部と、
n=0,1,2,3,…,N-2の範囲でnを設定し、n<N/2の条件下でi=0、j=nと設定し、n≧N/2の条件下で、i=n-N/2+1、j=N/2-1と設定し、乗算部および途中加算部の動作が1度実行されるたびに、iのインクリメント、jのデクリメントを実行し、i<N/2、j≧0のいずれかにおいて範囲外となった場合には、nをインクリメントする繰り返し処理制御部と、
q6,q7←mul_mul(dj,dj+4,dj+8)を実行する乗算部と、
i=0,またはj=N/2-1の場合に、q8,q9,q10←shift_blk(q6,q7,q9)を実行し、
それ以外の場合に、q8,q9,q10←add_long(q6,q7,q8,q9,q10)を実行する途中加算部と、
q8,q9←marge(q8,q9,q10)を実行し、
c2n,c2n+1,carry,r4←add_str(q8,r4,carry)を実行し、c*,c*+1の出力を行うマージ加算部と、
c2N−2,c2N−1,carry,r4←add_str(q9,r4,carry)を実行し、c*,c*+1の出力を行う加算部と、
を含む多倍長整数演算装置。
【請求項２】
x,yをx≧5,y≧11を充たす整数とし、
128bitの記憶領域であるy個のq-レジスタq0,...,qy−1と、
q-レジスタを二つに分割した64bitの記憶領域である2y個のd-レジスタd0,...,d2y−1と、
32bitの記憶領域であるx個のr-レジスタr0,...,rx−1を備える多倍長整数演算装置が実行する多倍長整数演算方法であって、
pを256bit以下の素数とし、
Fpを素体とし、
a,bを素体Fp上の要素とし、
通常環境のワード長W、サイズN=┌(└log2p┘+1)=W┐により、
【数２４】
2014137415.tif 000026
と表現されるものとし、
carryをキャリービットとし、32bit加算で発生するオーバーフロー{0,1}が格納されるものとし、
ビット列に対するq-レジスタの表現を[ビット列]qとし、
ビット列に対するd-レジスタの表現を[ビット列]dとし、
ビット列に対するr-レジスタの表現を[ビット列]rとし、
矢印記号は代入を意味するものとし、[ ]内に示すカンマ記号は、カンマ記号の両側に位置する各ビット列のビット長が互いに等しくなるように分割する記号とし、任意のビット列である第1から第4ビット列に対して、
演算記号addsを([第1ビット列+第2ビット列]r,carry)←[第1ビット列]r+[第2ビット列]rとし、
演算記号adcsを([第1ビット列+第2ビット列+carry]r,carry)←[第1ビット列]r+[第2ビット列]r+carryとし、
演算記号ldrを[ビット列]r=r*←ビット列とし、
演算記号strをビット列←r*=[ビット列]rとし、
演算記号vmovを[第1ビット列]r,[第2ビット列]r←[第1ビット列,第2ビット列]dとし、
演算記号vaddlを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[第1ビット列,第3ビット列]d+[第2ビット列,第4ビット列]dとし、
演算記号vaddwを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[[第1ビット列]d,[第3ビット列]d]q+[第2ビット列,第4ビット列]dとし、
演算記号vmullを[[第1ビット列×第2ビット列]d,[第3ビット列×第4ビット列]d]q←[第1ビット列,第3ビット列]d×[第2ビット列,第4ビット列]dとし、
演算記号vaddを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[[第1ビット列]d,[第3ビット列]d]q+[[第2ビット列]d,[第4ビット列]d]qとし、
演算記号vmovlを[[第1ビット列]d,[第2ビット列]d]q←[第1ビット列,第2ビット列]dとし、
演算記号vldを[ビット列]q=q*←ビット列とし、
演算記号vstをビット列←q*=[ビット列]qとし、
記号s*,t*,s~*,t~*,s'*,t'*,s~'*,t~'*を、各32bitの一時変数とし、
mul_mul(di,dj+4,dj+8)は、
di=[a2i+1,a2i]d,dj+4=[b2j+1,b2j]d,dj+8=[b2j,b2j+1]dを入力とし、
q6←vmull di,dj+4
q7←vmull di,dj+8
を計算して、
q6=[a2i+1b2j+1,a2ib2j]q,q7=[a2i+1b2j,a2ib2j+1]qを出力する計算式を表すものとし、
shift_blk(q6,q7,q9)は、
q6=[a2i+1b2j+1,a2ib2j]q
q7=[a2i+1b2j,a2ib2j+1]q
q9=[[s2n+1,t2n+1]d[s2n,t2n]d]q
を入力とし、
q8←vaddw q9,d12
q9←vmovl d13
q10←vaddl d14,d15
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
q10=[[s~'2n+2,t~'2n+2]d,[s~'2n+1,t~'2n+1]d]q
を出力する計算式を表すものとし、
add_long(q6,q7,q8,q9,q10)は、
q6=[a2i+1b2j+1,a2ib2j]q
q7=[a2i+1b2j,a2ib2j+1]q
q8=[[s2n+1,t2n+1]d,[s2n,t2n]d]q
q9=[[s2n+3,t2n+3]d,[s2n+2,t2n+2]d]q
q10=[[s~2n+2,t~2n+2]d,[s~2n+1,t~2n+1]d]q
を入力とし、
q8←vaddw q8,d12
q9←vaddw q9,d13
q10←vaddw q10,d14
q10←vaddw q10,d15
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
q10=[[s~'2n+2,t~'2n+2]d,[s~'2n+1,t~'2n+1]d]q
を出力する計算式を表すものとし、
marge(q8,q9,q10)は、
q8=[[s2n+1,t2n+1]d,[s2n,t2n]d]q
q9=[[s2n+3,t2n+3]d,[s2n+2,t2n+2]d]q
q10=[[s~2n+2,t~2n+2]d,[s~2n+1,t~2n+1]d]q
を入力とし、
d17←vadd d17,d20
d18←vadd d18,d21
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
を出力する計算式を表すものとし、
add_str(q*,r4,carry)は、
q*=[[s2n+1,t2n+1]d,[s2n,t2n]d]q,r4,carry
を入力とし、
r1,r2←vmov d2*
c2n,carry←adcs r1,r4,carry
r3,r4←vmov d2*+1
c2n+1,carry←adcs r3,r2,carry
を計算して、
c2n,c2n+1,r4,carryを出力する計算式を表すものとし、
q0-レジスタのd0-レジスタにa1,a0を、d1-レジスタにa3,a2を格納し、q1-レジスタのd2-レジスタにa5,a4を、d3-レジスタにa7,a6を格納し、q2-レジスタのd4-レジスタにb1,b0を、d5-レジスタにb3,b2を格納し、q3-レジスタのd6-レジスタにb5,b4を、d7-レジスタにb7,b6を格納する格納ステップと、
q4-レジスタのd8-レジスタに置換後のb0,b1を、d9-レジスタに置換後のb2,b3を、q5-レジスタのd10-レジスタに置換後のb4,b5を、d11-レジスタに置換後のb6,b7を格納する置換ステップと、
n=0,1,2,3,…,N-2の範囲でnを設定し、n<N/2の条件下でi=0、j=nと設定し、n≧N/2の条件下で、i=n-N/2+1、j=N/2-1と設定し、乗算ステップおよび途中加算ステップが1度実行されるたびに、iのインクリメント、jのデクリメントを実行し、i<N/2、j≧0のいずれかにおいて範囲外となった場合には、nをインクリメントする繰り返し処理制御ステップと、
q6,q7←mul_mul(dj,dj+4,dj+8)を実行する乗算ステップと、
i=0,またはj=N/2-1の場合に、q8,q9,q10←shift_blk(q6,q7,q9)を実行し、
それ以外の場合に、q8,q9,q10←add_long(q6,q7,q8,q9,q10)を実行する途中加算ステップと、
q8,q9←marge(q8,q9,q10)を実行し、
c2n,c2n+1,carry,r4←add_str(q8,r4,carry)を実行し、c*,c*+1の出力を行うマージステップと、
c2N−2,c2N−1,carry,r4←add_str(q9,r4,carry)を実行し、c*,c*+1の出力を行うキャリー有加算ステップと、
を含む多倍長整数演算方法。
【請求項３】
請求項２に記載された多倍長整数演算方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化、復号技術に用いられる多倍長整数演算装置、多倍長整数演算方法、プログラムに関する。
【背景技術】
【０００２】
非特許文献1において、Intel(登録商標)アーキテクチャで利用可能なSIMD環境SSE2を用いて多倍長整数乗算を効率的に実行している。計算アルゴリズムは、初めに乗算をいくつかの適当な大きさの部分乗算に分割を行う。次に、各々の部分乗算をSIMD命令を用いて計算し、メモリ上に結果をストアする。最終的に、全ての部分乗算の結果を順次加算していくことで乗算全体の計算を行っている。また通常環境上での多倍長整数乗算の実装方法としてComba法がある。Comba法では、下位の結果を計算する乗算から順番に計算することにより、出力結果のロード、ストアを削減している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】IntelCorporation、“ストリーミングＳＩＭＤ拡張命令２（ＳＳＥ２）を使用した大数の乗算の実行”、[online]、平成13年12月6日、[平成24年12月20日検索]、インターネット<URL:http://www.intel.co.jp/content/dam/www/public/ijkk/jp/ja/documents/developer/w_big_mul_j.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ペアリング暗号はIDベース暗号など利便性の高い暗号システムを構築可能な公開鍵暗号方式である。暗号システムを用いて情報を安全に取り扱うためには、我々が利用している様々なデバイス上で動作する必要がある。一方、ペアリング暗号の計算時間は従来の公開鍵暗号と比較して低速であり、PC上では十分実用的な計算速度ではあるが、携帯電話などの計算リソースの小さなデバイス上では低速であり実際に利用することは未だ困難である。素数pとして、素体Fp上のペアリングの構成においては、素体Fp演算やその拡大体Fpm演算などが必要である。それらの様々な演算において、ペアリングの計算で最も支配的な計算量を持つのが素体Fp上の要素a,bの乗算c=a×bである。そこで本発明では、SIMD命令を有するシステム上での高速な多倍長整数乗算の構成を示すことにより、ペアリング暗号の高速化を実現する多倍長整数演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の多倍長整数演算装置は、x,yをx≧5,y≧11を充たす整数とし、128bitの記憶領域であるy個のq-レジスタq0,...,qy−1と、q-レジスタを二つに分割した64bitの記憶領域である2y個のd-レジスタd0,...,d2y−1と、32bitの記憶領域であるx個のr-レジスタr0,...,rx−1と、格納部と、置換部と、乗算部と、途中加算部と、繰り返し処理制御部と、マージ加算部と、加算部を含む。
【０００６】
pを256bit以下の素数とし、Fpを素体とし、a,bを素体Fp上の要素とし、通常環境のワード長W、サイズN=┌(└log2p┘+1)/W┐により、
【０００７】
【数１】
2014137415.tif 000003
【０００８】
と表現されるものとし、carryをキャリービットとし、32bit加算で発生するオーバーフロー{0,1}が格納されるものとし、ビット列に対するq-レジスタの表現を[ビット列]qとし、ビット列に対するd-レジスタの表現を[ビット列]dとし、ビット列に対するr-レジスタの表現を[ビット列]rとし、矢印記号は代入を意味するものとし、[ ]内に示すカンマ記号は、カンマ記号の両側に位置する各ビット列のビット長が互いに等しくなるように分割する記号とし、
任意のビット列である第1から第4ビット列に対して、
演算記号addsを([第1ビット列+第2ビット列]r,carry)←[第1ビット列]r+[第2ビット列]rとし、
演算記号adcsを([第1ビット列+第2ビット列+carry]r,carry)←[第1ビット列]r+[第2ビット列]r+carryとし、
演算記号ldrを[ビット列]r=r*←ビット列とし、
演算記号strをビット列←r*=[ビット列]rとし、
演算記号vmovを[第1ビット列]r,[第2ビット列]r←[第1ビット列,第2ビット列]dとし、
演算記号vaddlを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[第1ビット列,第3ビット列]d+[第2ビット列,第4ビット列]dとし、
演算記号vaddwを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[[第1ビット列]d,[第3ビット列]d]q+[第2ビット列,第4ビット列]dとし、
演算記号vmullを[[第1ビット列×第2ビット列]d,[第3ビット列×第4ビット列]d]q←[第1ビット列,第3ビット列]d×[第2ビット列,第4ビット列]dとし、
演算記号vaddを[[第1ビット列+第2ビット列]d,[第3ビット列+第4ビット列]d]q←[[第1ビット列]d,[第3ビット列]d]q+[[第2ビット列]d,[第4ビット列]d]qとし、
演算記号vmovlを[[第1ビット列]d,[第2ビット列]d]q←[第1ビット列,第2ビット列]dとし、
演算記号vldを[ビット列]q=q*←ビット列とし、演算記号vstをビット列←q*=[ビット列]qとし、
記号s*,t*,s~*,t~*,s'*,t'*,s~'*,t~'*を、各32bitの一時変数とし、
mul_mul(di,dj+4,dj+8)は、
di=[a2i+1,a2i]d,dj+4=[b2j+1,b2j]d,dj+8=[b2j,b2j+1]dを入力とし、
q6←vmull di,dj+4
q7←vmull di,dj+8
を計算して、
q6=[a2i+1b2j+1,a2ib2j]q,q7=[a2i+1b2j,a2ib2j+1]qを出力する計算式を表すものとし、
shift_blk(q6,q7,q9)は、
q6=[a2i+1b2j+1,a2ib2j]q
q7=[a2i+1b2j,a2ib2j+1]q
q9=[[s2n+1,t2n+1]d[s2n,t2n]d]q
を入力とし、
q8←vaddw q9,d12
q9←vmovl d13
q10←vaddl d14,d15
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
q10=[[s~'2n+2,t~'2n+2]d,[s~'2n+1,t~'2n+1]d]q
を出力する計算式を表すものとし、
add_long(q6,q7,q8,q9,q10)は、
q6=[a2i+1b2j+1,a2ib2j]q
q7=[a2i+1b2j,a2ib2j+1]q
q8=[[s2n+1,t2n+1]d,[s2n,t2n]d]q
q9=[[s2n+3,t2n+3]d,[s2n+2,t2n+2]d]q
q10=[[s~2n+2,t~2n+2]d,[s~2n+1,t~2n+1]d]q
を入力とし、
q8←vaddw q8,d12
q9←vaddw q9,d13
q10←vaddw q10,d14
q10←vaddw q10,d15
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
q10=[[s~'2n+2,t~'2n+2]d,[s~'2n+1,t~'2n+1]d]q
を出力する計算式を表すものとし、
marge(q8,q9,q10)は、
q8=[[s2n+1,t2n+1]d,[s2n,t2n]d]q
q9=[[s2n+3,t2n+3]d,[s2n+2,t2n+2]d]q
q10=[[s~2n+2,t~2n+2]d,[s~2n+1,t~2n+1]d]q
を入力とし、
d17←vadd d17,d20
d18←vadd d18,d21
を計算して、
q8=[[s'2n+1,t'2n+1]d,[s'2n,t'2n]d]q
q9=[[s'2n+3,t'2n+3]d,[s'2n+2,t'2n+2]d]q
を出力する計算式を表すものとし、
add_str(q*,r4,carry)は、
q*=[[s2n+1,t2n+1]d,[s2n,t2n]d]q,r4,carry
を入力とし、
r1,r2←vmov d2*
c2n,carry←adcs r1,r4,carry
r3,r4←vmov d2*+1
c2n+1,carry←adcs r3,r2,carry
を計算して、
c2n,c2n+1,r4,carryを出力する計算式を表すものとし、
格納部は、q0-レジスタのd0-レジスタにa1,a0を、d1-レジスタにa3,a2を格納し、q1-レジスタのd2-レジスタにa5,a4を、d3-レジスタにa7,a6を格納し、q2-レジスタのd4-レジスタにb1,b0を、d5-レジスタにb3,b2を格納し、q3-レジスタのd6-レジスタにb5,b4を、d7-レジスタにb7,b6を格納する。置換部は、q4-レジスタのd8-レジスタに置換後のb0,b1を、d9-レジスタに置換後のb2,b3を、q5-レジスタのd10-レジスタに置換後のb4,b5を、d11-レジスタに置換後のb6,b7を格納する。繰り返し処理制御部は、n=0,1,2,3,…,N-2の範囲でnを設定し、n<N/2の条件下でi=0、j=nと設定し、n≧N/2の条件下で、i=n-N/2+1、j=N/2-1と設定し、乗算部および途中加算部の動作が1度実行されるたびに、iのインクリメント、jのデクリメントを実行し、i<N/2、j≧0のいずれかにおいて範囲外となった場合には、nをインクリメントする。乗算部は、q6,q7←mul_mul(dj,dj+4,dj+8)を実行する。途中加算部は、i=0,またはj=N/2-1の場合に、q8,q9,q10←shift_blk(q6,q7,q9)を実行し、それ以外の場合に、q8,q9,q10←add_long(q6,q7,q8,q9,q10)を実行する。マージ加算部は、q8,q9←marge(q8,q9,q10)を実行し、c2n,c2n+1,carry,r4←add_str(q8,r4,carry)を実行し、c*,c*+1の出力を行う。加算部は、c2N−2,c2N−1,carry,r4←add_str(q9,r4,carry)を実行し、c*,c*+1の出力を行う。
【発明の効果】
【０００９】
本発明の多倍長整数演算装置によれば、ペアリング暗号の高速化を実現することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明で用いられるq-レジスタとd-レジスタの対応を示す図。
【図２】実施例1の多倍長整数演算装置の動作であるS11,S12,S13について説明する図。
【図３】実施例1の多倍長整数演算装置の動作であるS16,S17について説明する図。
【図４】実施例1の多倍長整数演算装置の構成を示すブロック図。
【図５】実施例1の多倍長整数演算装置の動作を示すフローチャート。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１２】
＜記号、関数の定義＞
以下、実施例に用いられる記号、関数等の定義を行う。
【００１３】
pを256bit以下の素数、Fpを素体とする。素体Fp上の要素a,bは、通常環境のワード長W、サイズN=┌(└log2p┘+1)/W┐により、
【００１４】
【数２】
2014137415.tif 000004
【００１５】
と表現される。なお、記号┌・┐は、・以上の最小の整数を計算、記号└・┘は、・以下の最大の整数を計算する関数である。このとき素体Fp上の乗算c=a×bは、要素a,b∈Fpを入力とし、
【００１６】
【数３】
2014137415.tif 000005
【００１７】
で計算される。この計算は、ワード長W毎の乗算と加算により構成する。素体Fp上の多倍長整数乗算の計算環境として、W=32bitのレジスタと命令を持つ通常環境とV=128bitのレジスタと命令を持つSIMD環境を有するシステムとする。今回構成する乗算装置のため、通常環境およびSIMD環境はそれぞれ下記の命令とレジスタを備える。
【００１８】
＜通常環境＞
通常環境では、x個の32bitレジスタ(r-レジスタ)が備え付けられており、各々のレジスタをr0,...,rx−1と表現する。ビット列a={0,1}32に対して、r-レジスタの表現を[a]rとする。a,bをメモリ上に保存された32bitの値とした場合、通常環境では下記の命令を持つ。
キャリー無加算adds:([a+b]r,carry)←[a]r+[b]r
キャリー有加算adcs:([a+b+carry]r,carry)←[a]r+[b]r+carry
ロードldr:[a]r=r*←a
ストアstr:a←r*=[a]r
ここでcarryはキャリービットであり、32bit加算で発生するオーバーフロー{0,1}が格納される。
【００１９】
＜SIMD環境＞
SIMD環境では、y個の128bitレジスタ(q-レジスタ)が備え付けられており、各々のレジスタをq0,...,qy−1と表現する。q-レジスタは2y個の64bitレジスタ(d-レジスタ)としても利用可能であり、q-レジスタとd-レジスタの対応は図1の通りとなる。
【００２０】
aij={0,1}64、ai={0,1}32とし、ビット列a=a32||a10=a3||a2||a1||a0={0,1}128としたとき（記号||はビット列の連結を意味する）、q-レジスタ、d-レジスタの表現を
[a]q=[[a32]d,[a10]d]q=[[a3,a2]d,[a1,a0]d]q
とする。a,bをメモリ上に保存された128bitの値とした場合、SIMD環境では下記の命令を持つ。なお、[ ]内に示すカンマ記号は、カンマ記号の両側に位置する各ビット列のビット長が互いに等しくなるように分割する記号とする。
SIMD環境から通常環境への値移動vmov:[a0]r,[a1]r←[a1,a0]d
Long加算vaddl:[[a1+b1]d,[a0+b0]d]q←[a1,a0]d+[b1,b0]d
Word加算vaddw:[[a32+b1]d,[a10+b0]d]q←[[a32]d,[a10]d]q+[b1,b0]d
乗算vmull:[[a1×b1]d,[a0×b0]d]q←[a1,a0]d×[b1,b0]d
加算vadd:[[a32+b32]d,[a10+b10]d]q←[[a32]d,[a10]d]q+[[b32]d,[b10]d]q
Long移動vmovl:[[a1]d,[a0]d]q←[a1,a0]d
ロードvld:[a]q=q*←a
ストアvst:a←q*=[a]q
【００２１】
加算命令vaddwやvaddでは、計算結果のd-レジスタで64bitを超えた場合、キャリーが無視されて計算される。
上記の2種類の環境において、素体Fp上の多倍長整数a,bを入力とする乗算c=a×bを計算する。
【実施例１】
【００２２】
上記のような環境や命令を持つ典型的な例として、モバイルデバイス等で用いられるARMv7アーキテクチャがある。ARMv7アーキテクチャでは、通常環境でW=32、SIMD環境でV=128であり、各環境におけるq-レジスタは16個、r-レジスタは15個装備されている。この環境下において多倍長整数乗算を以下に示すAlgorithm1,...,6により実現することができる。
【００２３】
【数４】
2014137415.tif 000006
【００２４】
【数５】
2014137415.tif 000007
【００２５】
【数６】
2014137415.tif 000008
【００２６】
【数７】
2014137415.tif 000009
【００２７】
【数８】
2014137415.tif 000010
【００２８】
【数９】
2014137415.tif 000011
【００２９】
なお、Algorithm3,4,5,6におけるs*,t*,s~*,t~*,s'*,t'*,s~'*,t~'*は、各Algorithmで利用される各32bitの一時変数であり、一時的な値が代入される。s2n,t2nは、(s2n2W+t2n)22nWへ対応が可能である。チルダは[s~2n+1,t~2n+1]dと[s2n+1,t2n+1]dに異なる値が格納されることを示すために付与されている。また、プライムは値が更新されたことを示すために付与されている。
【００３０】
上述した条件により実現した実施例1の多倍長整数演算装置について、図4、図5を参照して説明する。図4は本実施例の多倍長整数演算装置1の構成を示すブロック図である。図5は本実施例の多倍長整数演算装置1の動作を示すフローチャートである。
【００３１】
図4に示すように、本実施例の多倍長整数演算装置1は、格納部11と、置換部12と、乗算部13と、途中加算部14と、繰り返し処理制御部15と、マージ加算部16と、加算部17と、y個のq-レジスタ(q0-レジスタ100-0,q1-レジスタ100-1,q2-レジスタ100-2,…,qy−1-レジスタ100-y-1)と、x個のr-レジスタ(r0-レジスタ200-0,r1-レジスタ200-1,r2-レジスタ200-2,…,rx−1-レジスタ200-x-1)とを備える。ただし、前述したようにq-レジスタ、r-レジスタはそれぞれ11個、5個必要であるため、x≧5,y≧11とする。格納部11は、a,bを入力とし、当該a,bを4個のq-レジスタに格納する(S11)。詳細には、ステップS11では、格納部11は、Algorithm1における1-2行目である
【００３２】
【数１０】
2014137415.tif 000012
【００３３】
を実行する。具体的には図2に示すように格納部11は、q0-レジスタ100-0のd0-レジスタにa1,a0を格納し、d1-レジスタにa3,a2を格納する。格納部11は、q1-レジスタ100-1のd2-レジスタにa5,a4を格納し、d3-レジスタにa7,a6を格納する。格納部11は、q2-レジスタ100-2のd4-レジスタにb1,b0を格納し、d5-レジスタにb3,b2を格納する。格納部11は、q3-レジスタ100-3のd6-レジスタにb5,b4を格納し、d7-レジスタにb7,b6を格納する。次に置換部12は、bに対して、[b*+1,b*]dを[b*,b*+1]dに置換し、2個のq-レジスタに保存する(S12)。詳細には、ステップS12において、置換部12は上述のAlgorithm1における3行目である
【００３４】
【数１１】
2014137415.tif 000013
【００３５】
を実行する。具体的には図2に示すように、置換部12はq4-レジスタ100-4のd8-レジスタに置換後のb0,b1を格納し、d9-レジスタに置換後のb2,b3を格納する。同様に、q5-レジスタ100-5のd10-レジスタに置換後のb4,b5を格納し、d11-レジスタに置換後のb6,b7を格納する。
【００３６】
次に、繰り返し処理制御部15が実行する繰り返し制御について説明する。繰り返し処理制御部15は、Algorithm1における4,5,6,12,13,14,17行目に従って繰り返し処理を実行する。詳細には、Algorithm1における4行目
【００３７】
【数１２】
2014137415.tif 000014
【００３８】
において、記号n=0,1,2,3,…,N-2の範囲で値が代入されることを示している。さらに、Algorithm1における5行目
【００３９】
【数１３】
2014137415.tif 000015
【００４０】
において、n<N/2の条件下で、i=0とし、j=n(n=0,1,2,3,…,N/2-1)とすること、また、n≧N/2の条件下で、i=n-N/2+1(つまりi=1,2,3,…,N/2-1)とし、j=N/2-1とすることを示している。さらに、Algorithm1における6行目
【００４１】
【数１４】
2014137415.tif 000016
【００４２】
において、i<N/2であって、j≧0である場合に、7行目から13行目が実行されることを示している。さらに、Algorithm1における13行目
【００４３】
【数１５】
2014137415.tif 000017
【００４４】
において、iがインクリメントされ、jがデクリメントされることを示している。従って、Algorithm1では、まずn=0の条件下で、i=0,j=0の条件の下、Algorithm1における6行目から12行目が実行されて、13行目においてiがインクリメントされ、jがデクリメントされることにより、Algorithm1の6行目の条件外となってループの一回目を終了する。次に、n=1の条件下で、i=0,j=1の条件の下、Algorithm1における6行目から12行目が実行されて、13行目においてiがインクリメントされ、jがデクリメントされ、i=1,j=0の条件の下、Algorithm1における6行目から12行目が再び実行されてループの２回目を終了する。次に、n=2の条件下で、i=0,j=2の条件の下、Algorithm1における6行目から12行目が実行されて、13行目においてiがインクリメントされ、jがデクリメントされ、i=1,j=1の条件の下、Algorithm1における6行目から12行目が再び実行され、13行目においてiがインクリメントされ、jがデクリメントされ、i=0,j=2の条件の下、Algorithm1における6行目から12行目が再び実行されてループの３回目を終了する。ループの４回目は、i=0,j=3の条件、i=1,j=2の条件、i=2,j=1の条件、i=3,j=0の条件で実行される。
【００４５】
従って、繰り返し処理制御部15は、n=0,1,2,3,…,N-2の範囲でnを設定し、n<N/2の条件下でi=0、j=n(n=0,1,2,3,…,N/2-1)とi,jを設定し、n≧N/2の条件下で、i=n-N/2+1(つまりi=1,2,3,…,N/2-1)、j=N/2-1とi,jを設定する。繰り返し処理制御部15は、後述するS13,S14が1度実行されるたびに、iのインクリメント、jのデクリメントを実行する。繰り返し処理制御部15は、i<N/2、j≧0のいずれかにおいて範囲外となった場合には、nをインクリメントし、後述するS13,S14が1度実行されるたびに、iのインクリメント、jのデクリメントを実行する。
【００４６】
乗算部13は繰り返し処理制御部15から制御信号を取得して、乗算2回を1単位として所定の順序で乗算を実行し、乗算結果を2つのq-レジスタに格納する(S13)。詳細には、ステップS13において乗算部13は、上述のAlgorithm1における7行目である
【００４７】
【数１６】
2014137415.tif 000018
【００４８】
を実行する。mul_mul(dj,dj+4,dj+8)の処理内容はAlgorithm2に記載されている。例えば、i=0,j=0の条件では、乗算部13は、d0=(a1,a0),d4=(b1,b0),d8=(b0,b1)を入力とし、Algorithm2の乗算を実行して、図2(A)に示すようにq6-レジスタ100-6のd13-レジスタにa1b1をd12-レジスタにa0b0を格納し、q7-レジスタ100-7のd15-レジスタにa1b0をd14-レジスタにa0b1を格納する。i=0,j=1の条件では、乗算部13は、d0=(a1,a0),d5=(b3,b2),d9=(b2,b3)を入力とし、Algorithm2の乗算を実行して、図2(B)の上段に示すようにq6-レジスタ100-6のd13-レジスタにa1b3をd12-レジスタにa0b2を格納し、q7-レジスタ100-7のd15-レジスタにa1b2をd14-レジスタにa0b3を格納する。i=1,j=0の条件では、乗算部13は、d1=(a3,a2),d4=(b1,b0),d8=(b0,b1)を入力とし、Algorithm2の乗算を実行して、図2(B)の下段に示すようにq6-レジスタ100-6のd13-レジスタにa3b1をd12-レジスタにa2b0を格納し、q7-レジスタ100-7のd15-レジスタにa3b0をd14-レジスタにa2b1を格納する。
【００４９】
次に途中加算部14は、乗算結果を途中加算し、加算結果を3個のq-レジスタに格納する(S14)。詳細には、ステップS14において途中加算部14は、Algorithm1の8行目
【００５０】
【数１７】
2014137415.tif 000019
【００５１】
の条件を充たす場合に、q6-レジスタ100-6、q7-レジスタ100-7、q9-レジスタ100-9を参照して、Algorithm1の9行目に示された途中加算
【００５２】
【数１８】
2014137415.tif 000020
【００５３】
を実行して、加算結果をq8-レジスタ100-8、q9-レジスタ100-9、q10-レジスタ100-10に格納する。途中加算部14は、それ以外の場合(else)に、q6-レジスタ100-6からq10-レジスタ100-10を参照して、Algorithm1の11行目に示された途中加算
【００５４】
【数１９】
2014137415.tif 000021
【００５５】
を実行して、加算結果をq8-レジスタ100-8、q9-レジスタ100-9、q10-レジスタ100-10に格納する。なお、shift_blk(q6,q7,q9)の処理内容はAlgorithm3に、add_long(q6,q7,q8,q9,q10)の処理内容はAlgorithm4に記載されている。次に繰り返し処理制御部15は、S13-S14が所定回数繰り返されているかを判断し、S13-S14が所定回数繰り返されている場合には、マージ加算部16に制御信号を送信する(S15AY)。一方、S13-S14が所定回数繰り返されていない場合には、乗算部13に制御信号を送信する(S15AN)。具体的には繰り返し処理制御部15は前述したインクリメント、デクリメントの結果、i<N/2、j≧0のいずれかが範囲外となる場合にはS13-S14が所定回数繰り返されていると判断してマージ加算部16に制御信号を送信する(S15AY)。一方、繰り返し処理制御部15は、前述したインクリメント、デクリメントの結果、i<N/2、j≧0のいずれも充たされる場合にはS13-S14が所定回数繰り返されていないと判断して乗算部13に制御信号を送信する(S15AN)。次に、マージ加算部16は、加算結果を格納した3個のレジスタをマージし、下位の値を保持しているq-レジスタにキャリー有加算とストアを実行する(S16)。詳細には、ステップS16においてマージ加算部16は、加算結果を格納したq8-レジスタ100-8、q9-レジスタ100-9、q10-レジスタ100-10に対してAlgorithm1の15行目に示されたマージ
【００５６】
【数２０】
2014137415.tif 000022
【００５７】
を実行してマージ結果をq8-レジスタ100-8、q9-レジスタ100-9に格納する。marge(q8,q9,q10)の処理内容はAlgorithm5に記載されている。さらに、ステップS16においてマージ加算部16は、マージ結果を格納したq8-レジスタ100-8に対してAlgorithm1の16行目に示されたキャリー有加算
【００５８】
【数２１】
2014137415.tif 000023
【００５９】
を実行し、c*,c*+1のストア（出力）を行う（図３参照）。なお、add_str(q8,r4,carry)の処理内容はAlgorithm6に記載されている。次に繰り返し処理制御部15は、S13-S16が所定回数繰り返されているかを判断し、S13-S16が所定回数繰り返されている場合には、加算部17に制御信号を送信する(S15BY)。一方、S13-S16が所定回数繰り返されていない場合には、乗算部13に制御信号を送信する(S15BN)。具体的には繰り返し処理制御部15は前述したnのインクリメントの結果、n>N-2となる場合にはS13-S16が所定回数繰り返されていると判断して加算部17に制御信号を送信する(S15BY)。一方、繰り返し処理制御部15は、前述したnのインクリメントの結果、n=1,2,3,…,N-2の何れかである場合にはS13-S16が所定回数繰り返されていないと判断して乗算部13に制御信号を送信する(S15BN)。最後に加算部17は、繰り返し処理制御部15から制御信号を取得して、上位の値を保持しているq-レジスタを通常環境へ移動しキャリー有加算とストアを実行する(S17)。詳細には、ステップS17において加算部17は、マージ結果を格納したq9-レジスタ100-9に対してAlgorithm1の18行目に示されたキャリー有加算
【００６０】
【数２２】
2014137415.tif 000024
【００６１】
を実行し、c*,c*+1のストア（出力）を行う（図３参照）。
【００６２】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００６７】
なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００６８】
＜発明の効果＞
1)乗算の計算回数の削減
通常環境での乗算mullは、入力レジスタ2個と出力レジスタ2個により32bit×32bit→64bitの計算を行う。一方、SIMD環境でのSIMD命令vmullは、32bit×32bit→64bitを2並列で計算可能となり、乗算命令の計算回数が1/2となる。またARMアーキテクチャにおいて、mullは3クロック、vmullは2クロックであり、実行サイクル自体も削減できる。
【００６９】
2)入力a,bのロード回数の削減
最大256bitの入力a,bをメモリからレジスタに格納する際、SIMD環境では、q-レジスタ4個で入力a,bを保持することが可能である。計算中は，これらのレジスタの内容変更を禁止することで、入力a,bのロード回数を削減できる。
【００７０】
3)出力cのロード、ストアの削減
乗算a×b=cの計算結果を下位のワードから順次計算することにより、中間結果のメモリとレジスタ間でのストア、ロードを除去できる。結果として、乗算結果のメモリへのストアを最小である2N回に削減できる。
【００７１】
4)SIMD環境の2並列64bit加算および通常環境のキャリー有32bit加算の併用による加算処理の効率化
通常命令では、2個の32bit入力の加算結果のオーバーフローはcarryとして制御レジスタに格納される。一方、SIMD命令では、64bit入力の加算を2並列で計算可能だが、計算結果のd-レジスタで64bitを超えた場合のオーバーフローは保存されない。提案アルゴリズムでは、計算途中では、32bit毎のキャリー部とボディ部に分割することで、途中加算部でのオーバーフローを防ぎ、最終的なキャリー部とボディ部の加算を通常環境のキャリー有加算を用いることで、SIMD環境のみでキャリー有加算を実現するよりも効率的な加算処理を実現した。
【図１】
2014137415.tif 000027
【図２】
2014137415.tif 000028
【図３】
2014137415.tif 000029
【図４】
2014137415.tif 000030
【図５】
2014137415.tif 000031