SystemVerilogでMontgomery curvesの加算公式の実装

[mathjax]今回はSystemVerilogでMontgomery curvesの射影座標での加算公式の実装をした．
注：これと前の記事をゼミ資料としてスライドにまとめた．また，ゼミでの指摘を最後に追記した．

1.前回の結果から
加減算器を2つ，乗算器を1つでは8ステップで処理を完了できることが分かった．しかし，今回は簡単のため加減算器2つではなく加算器1つと減算器1つで実装を行う．
 
 
2.構成
今回のシステムはcontrol unit,memory,adder,subtractor,multiplierの5つで構成する．以下にシステムのブロック図と信号の流れを図1として示す．なお，control unitに対する入力X1,Z1,Xm,Zm,Xn,Znと出力Xmn,Zmnは簡単のため省略している．
動作としてはcontrol unitがmemoryの入力/出力を制御し，演算とmemoryへの結果の保存を繰り返しながら，XmnとZmnを計算する．

図1 加算についてのブロック図

 
2.1.control unitの内部状態
control unitの内部状態としてはinfとcountが存在する．infは加算の対象となる片方の点が無限遠点(Z座標が0)なら1とし，無限遠点ではない方の点をXmn,Zmnとして出力とする．countは処理のステップを0から8として保持し，control unitはcountの値に合わせてin_selやout_selを変化させてmemoryを制御する．
 
2.2.in_sel,out_selの構造
in_sel,out_selは以下のような構造となっている．
logic [1:0] in_sel[2:0];
logic [3:0] out_sel[5:0];
in_selは2ビットが3つの配列となっている．in_selは演算器の演算結果をmemoryのどこに格納するかを指定する．なお，値の指定には6がオフセットされる．例えばin_sel[1]の値が1であるとき，減算の結果はmemory[7]に保存される．
 

表1 in_selの説明

 
out_selは4ビットが6つの配列となっている．out_selは各演算器の入力にmemoryのどこの番地を出力するかと決める．
 

表2 out_selの説明

 
2.3.メモリの配置
メモリ配置の意味を以下の表3として示す．
 

表3 メモリ配置の説明

 
2.4.各信号について
ブロック図中の信号の意味について，以下に表4として示す．
 

表4 ブロック図中の信号の説明

 
 
3.制御信号の設計
control unitはin_sel,out_selを用いてmemoryを制御し，XmnとZmnを計算する．計算のため，前回示した加算のアルゴリズムから制御信号としてin_sel,out_selに何を出力するべきかを考える．最初に8ステップのなかで，memoryと演算器がどのように動作すればよいのか考えてみる．
ここでMはmemoryの中のデータを表し，M[0]からM[5]にはX1,Z1,Xm,Zm,Xn,Znがロードされていることとする．なお，左辺の添字を6+?としているのはmemoryに入力するのはmemory[6]からmemory[9]であり，in_selは2ビットで表すためである．また，水色で示した部分は本来必要ない計算であり，結果はmemoryの使わない部分に格納している．
step1

M[6+0]=M[4]+M[5]

M[6+1]=M[2]-M[3]

M[6+2]=M[0]*M[0]

step2

M[6+0]=M[2]+M[3]

M[6+1]=M[4]-M[5]

M[6+2]=M[6]*M[7]

step3

M[6+0]=M[0]+M[0]

M[6+1]=M[0]-M[0]

M[6+3]=M[6]*M[7]

step4

M[6+0]=M[8]+M[9]

M[6+1]=M[8]-M[9]

M[6+2]=M[0]*M[0]

step5

M[6+0]=M[0]+M[0]

M[6+3]=M[0]-M[0]

M[6+2]=M[6]*M[6]

step6

M[6+0]=M[0]+M[0]

M[6+1]=M[0]-M[0]

M[6+3]=M[7]*M[7]

step7

M[6+0]=M[0]+M[0]

M[6+1]=M[0]-M[0]

M[6+2]=M[1]*M[8]

step8

M[6+0]=M[0]+M[0]

M[6+1]=M[0]-M[0]

M[6+3]=M[0]*M[9]

上記の命令から，制御信号を構成する．2.2.in_sel,out_selの構造より制御信号は以下のようになる．なお，配列の添字が小さい方が右側になるように記述している．
 
step1

in_sel   : 10 01 00

out_sel : 0000 0000 0011 0010 0101 0100

step2

in_sel   : 10 01 00

out_sel : 0111 0110 0101 0100 0011 0010

step3

in_sel   : 11 01 00

out_sel : 0111 0110 0000 0000 0000 0000

step4

in_sel   : 10 01 00

out_sel : 0000 0000 1001 1000 1001 1000

step5

in_sel   : 10 11 00

out_sel : 0110 0110 0000 0000 0000 0000

step6

in_sel   : 11 01 00

out_sel : 0111 0111 0000 0000 0000 0000

step7

in_sel   : 10 01 00

out_sel : 1000 0001 0000 0000 0000 0000

step8

in_sel   : 11 01 00

out_sel : 1001 0000 0000 0000 0000 0000

 
上記の制御信号をcontrol unitがcountに合わせて出力することで，意図したとおりに計算を行うことができる．
 
 
4.SystemVerilogによる実装
4.1.adder,subtractor,multiplier
以下に演算器のコードを示す．なお，ここでは演算はSystemVerilogの機能(加算，減算，乗算，剰余)を使用している．これは後からより高速なものへ変更する可能性が高いが，ここでは後回しとしている．



4.2.memory
以下にmemoryのコードを示す．

 
4.3.control unit
control unitのコードを以下に示す

5.動作確認
5.1.使用する曲線と点
使用する曲線は\(y^2=x^3+84x^2+x\)で，\(p=65521\)とする．また，点については\(P_1=(5731,1),P_m=(51081,56042),P_n=(19818,18646)\)     \(P_{m+n}=P_m+P_n=(5951,21120)\)とする．なお，\(mod\ p,mod\ l\)を計算する際に\(p,l\)が擬メルセンヌ素数であると都合が良いので，今後はそれも念頭に置いておく．
 
5.2.シミュレーション
以下にModelSim-Alteraでシミュレーションした結果を以下に示す．なお，画像はクリックして拡大しないと小さくて見えない．
 

図2 シミュレーション結果

上記のシミュレーション結果より，正しく\(P_{m+n}=(5951,21120)\)が計算できていることが分かる．また，加算する点の片方を無限遠点(Z座標が0)としたときの結果を以下に示す．

図3 \(P_m\)が無限遠点の場合のシミュレーション結果

図4 \(P_n\)が無限遠点の場合のシミュレーション結果

点の加算が無限遠点の場合，もう片方の点が出力されていることが確認できる．よって，加算は正しく実行できていることがわかる．
 
6.ゼミ発表での先生の指摘
この状態では演算(+,-,*)と\(mod\ p\)をSystemVerilogの+,-,*,%演算子を用いて実装している．加減算については加減算自体の実装は容易であり，\(mod\ p\)の計算も結果の大小比較を行い\(p\)を加算(減算)することで対応できる．
しかし，乗算についてはそれほど簡単ではなく，擬メルセンヌ素数を用いる場合は「ある意味3回乗算を行うことになる」ため，multiplierの後ろにブロックを付け加えるだけでは不十分であり，ステートマシン自体を改造する必要があるかもしれない．
 
次に行う作業としては2倍算(+Montgomery ladderまで?)を行うか，\(mod\ p\)について調べるか，2つの選択肢があったが先に\(mod\ p\)について調べることとした．これは，アルゴリズム自体に変更が必要な可能性があり２倍算を先に実装しても大幅な修正が必要となる可能性があるためである．
よって，\(p\)が擬メルセンヌ素数における\(mod\ p\)について調べるため，”Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms”を読み解く作業に入る．