実装に必要となる演算器の数

[mathjax]ECDSAをFPGA上で実装するにあたり，射影座標での加算と2倍算に必要となる演算器の数の検証．
Montgomery ladderでは加算と2倍算を同時に独立して実行するため，加算と2倍算については別々のモジュールと考える．
注：これと次の記事をゼミ資料としてスライドにまとめた．

 
1.加算
以下に加算について，\((X_{m+n},Z_{m+n})=(X_m,Z_m)+(X_n,Z_n)\)の式を示す．
 
$$ X_{m+n}=Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2 $$
$$ Z_{m+n}=X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2 $$
 
上記の式を元にアルゴリズムを考えると以下のようになる．なお，ここではMontgomery ladderで使用することを想定しているため\(m-n=1\)となり，\(X_{m-n},Z_{m-n}\)は\(X_1,Z_1\)と仮定する．
また，ここではまだレジスタに関しては考えないため，便宜的に\(a_1\)から\(d_2\)を使用している．
 
step1

1.1.  \(a_1=X_m+Z_m\)

1.2.  \(a_2=X_m-Z_m\)

1.3.  \(a_3=X_n+Z_n\)

1.4.  \(a_4=X_n-Z_n\)

step2

2.1.  \(b_1=a_2*a_3\)

2.2.  \(b_2=a_1*a_4\)

step3

3.1.  \(c_1=b_1+b_2\)

3.2.  \(c_2=b_1-b_2\)

step4

4.1.  \(d_1=c_1*c_1\)

4.2.  \(d_2=c_2*c_2\)

step5

5.1.  \(e_1=Z_1*d_1\)

5.2.  \(e_2=X_1*d_2\)

各ステップ内は独立して実行できる．そのため，各ステップ内を並列に動作させることで処理の高速化を図ることができる．
しかし，LE数(回路面積)には制限があるため，より少ない演算器の個数でより高速に処理を完了できるようにしたい．
以下に各ステップごとに必要となる演算器の数を示す．

ここで，加減算器を2つ，乗算器を1つとしてスケジュールを考えてみる．すると，以下のようになる．

よって，加減算器を2つ，乗算器を1つでは8ステップで処理を完了できることが分かる．なお，加減算器を2つと乗算器を2つでは5ステップ，加減算器を4つと乗算器を2つでも5ステップとなる．
乗算器については必要となるLE数が多く，加減算器だけを4つにした場合も8ステップで変わらないため，加減算器を2つと乗算器を1つを使い8ステップで実行することが適していると考える．
 
 
2.2倍算
以下に2倍算について，\((X_{2n},Z_{2n})=2(X_n,Z_n)\)の式を示す．
 
$$4X_nZ_n=(X_n+Z_n)^2-(X_n-Z_n)^2$$
$$X_{2n}=(X_n+Z_n)^2(X_n-Z_n)^2$$
$$Z_{2n}=4X_nZ_n((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n))$$
 
上記の式を元にアルゴリズムを考えると以下のようになる．
 
step1

1.1.  \(a_1=X_n+Z_n\)

1.2.  \(a_2=X_n-Z_n\)

1.1.  \(a_3=A+2\)

step2

2.1.  \(b_1=a_1*a_1\)

2.2.  \(b_2=a_2*a_2\)

2.3.  \(b_3=a_3/4\)

step3

3.1.  \(c_1=b_1-b_2\)

3.2.  \(c_2=b_1*b_2\)

step4

4.1.  \(d_1=b_1-b_2\)

step5

5.1.  \(e_1=b_2+d_1\)

step6

6.1.  \(f_1=c_1*e_1\)

各ステップで必要となる演算器を以下に示す．

上記の図を元にスケジュールを考えると以下のようになる．

よって，加減算器2つ，乗算器1つ，除算器1つの場合7ステップで完了できる．
 
 
3.今後の話
今後はこれをもとに設計を考えてみる．設計後，HDLで記述を行い加算と2倍算についてモジュール化を行い，テストを行う．
なお，mod pやmod lについては別途考える．modについては演算器の後ろにつくことになるかもしれない．