有限体とは

コンピュータで利用されている暗号方式としてRSA暗号や楕円曲線暗号が挙げられますが，これらの演算には有限体という数論的な計算が必要不可欠となっています．

有限体の計算とは、とある素数$p$を法とし，$\lbrace 0, …, p-1 \rbrace$で計算することができます．

突然，「法」とかよくわからない言葉が出てきますが，例えば，法が$p = 7$のとき，有限体は集合として$ \lbrace 0,1,2,3,4,5,6 \rbrace $と表すことができます．

これは割り算の余りと同じで， $$ 14 \div 7 = 2 … 0 $$ となり，あまりは0です．14 → 15にしてみるとどうでしょう．あまりは１になります． 15→…→20とすると，あまりは2,3,…,6となり，有限体の集合を表すことができます．

コンピュータで利用される暗号は有限体が重要と最初に述べました．このことから，余りの計算は現代のインターネットの安全性を保つために必要不可欠となっているのです．(詳しくは別の記事に書きます)

今回は，有限体の計算手法についてメモとして残して置きます．

剰余加算

有限体の足し算は単純に考えると

z = (x + y) % p
return z

のようにプログラムを書けば計算が可能となります．

しかし，暗号で利用される位数$p$は256bit等と非常に大きいので，単純に考えて余りを求めるだけにビット数分程度のクロックサイクルを要します．ちなみに，足し算や引き算は一桁クロックサイクルで実行できることがほとんどです．

そのため，高速化を図るには次のようにします．

z = x + y
If z > p then z -=  p
return z

とすることで，高速な足し算と引き算で有限体の足し算を実装することが可能となります．

もちろん、入力$x, y$は$p$未満であることが条件です。

同じように引き算も，%を使ってプログラムを書くのではなく，$x-y$を実行したときに負の値になった場合に法を足せば同じ値になります．

z = x - y
If 0 > z then z = z + p
return z

多倍長演算ライブラリを用いると

int sub128(bn& z, const bn& x, const bn& y);

上記のような関数になっていることがあり、xとyに入力、zが計算結果、returnで返されるint型の数値はキャリーの発生を得ることができます。

分岐処理でキャリーを判別するようにするとかんたんなプログラムになります。

暗号処理で最も利用される処理は剰余乗算です。これを高速化すると暗号処理全体が高速化するという重要な処理です。

これも直感的に実装すると

z=x*y
z%=p

になりますが、%は非常に遅いので避けたいところです。

モンゴメリ・リダクションという技を用いることで、ビットシフトや加減算などの軽量な処理で剰余を取ることができます。

これで計算するには、法$p$の値からパラメータを事前計算し、入力値をMontgomeryの世界で計算できるようにMR表現にする必要があります。

事前計算で$R, R^{-1}, nr$を求めます。

MR表現にした数値を$[x], [y]$と表現します。

$[x] [y]=[xy]$

という計算ができ、

$$ ((xR \bmod{p})(yR \bmod{p})R^{-1} \bmod{p})=(xyR) \bmod{p} $$

はじめにxとyに事前計算で求めた$R$を剰余乗算することでMR表現にすることができます。

MR表現は法$p$の有限体ですので、そのまま計算することができます。