« DES暗号高速化の検討 | トップページ | ファミコン用 音源ドライバー nsd.lib リリース »

2012/02/18

多倍長整数 の処理考察

CPUの演算命令で扱える範囲を超える整数の演算方法。

やはり、機械語レベルのコードを考えると、C言語で記述すると無駄なコードを吐きまくる気がしてならない。
C言語には、『キャリー付きの演算』をする命令が無いから。
加算・減算は確実にアセンブリ言語で書く方が処理速度が速くなりそう。

例えば、足し算はMASM風にかくと、これで行けると思う。

; ecx : 扱う整数のバイト数を入れて。
; edi : 整数のポインタ
; esi : 整数のポインタ
; ebx : 返値

  xor edx, edx
  clc
  .repeat
    mov eax, [edi + edx * 4]
    adc eax, [esi + edx * 4]
    mov [ebx + edx * 4], eax
    inc edx
  .untilcxz


掛け算も、ようは筆算の要領でシフトと加算で表現する。
シフトも、アセンブリ言語でキャリー付きのシフトを使うと速い。

割り算も、掛け算どうよう、筆算の要領で。
割る数をシフトして、割られる数から引き算だから。


さて、RSA暗号処理に必要な演算 を考えてみる。

RSA暗号における暗号化と複合化は以下の計算式を計算する。
もちろん、yやeやnは、10進数にすると600桁とかそういうレベルの整数。

 x = y^e (mod n)

yのe乗というのは、掛け算を相当する数繰り返すことになる。
しかし、べき乗には性質があって、

 x = y^e (mod n)
  = y^(a+b) (mod n)
  = y^a (mod n) * y^b (mod n)

が成り立つ。
つまり、べき乗する数eを、2の倍数どおしの足算に変換すれば、
従来より早いべき乗計算が実現できる。

つまり、
e = 2^s1 + 2^s2 + ... 2^sn
とする。

 x = y^e (mod n)
  = y^(2^s1 + 2^s2 + ... 2^sn) (mod n)
  = y^(2^s1) (mod n) × y^(2^s2) (mod n) × ... y^(2^sn) (mod n)

で、こう仮定する。

 t[0] = y   = y^ 1 = y^(2^0)
 t[1] = t0^2 = y^ 2 = y^(2^1)
 t[2] = t1^2 = y^ 4 = y^(2^2)
 t[3] = t2^2 = y^ 8 = y^(2^3)
 t[4] = t3^2 = y^16 = y^(2^4)
 ・・・

勘のいい人は解ると思うけど、まず、このt[n]を求めればいい。
で、必要なt[n]を掛け算すれば、y^e(mod n)が求まる。

例として、2^100(mod 101)を求めてみる。

t[0] = 2                   … 2^(2^0) mod 101
t[1] = t[0]^2 = 2^2 = 4 ≡ 4 (mod 101) … 2^(2^1) mod 101
t[2] = t[1]^2 = 4^2 = 16 ≡ 16 (mod 101) … 2^(2^2) mod 101
t[3] = t[2]^2 = 16^2 = 256 ≡ 54 (mod 101) … 2^(2^3) mod 101
t[4] = t[3]^2 = 54^2 = 2919 ≡ 88 (mod 101) … 2^(2^4) mod 101
t[5] = t[4]^2 = 88^2 = 7744 ≡ 68 (mod 101) … 2^(2^5) mod 101
t[6] = t[5]^2 = 68^2 = 4624 ≡ 79 (mod 101) … 2^(2^6) mod 101

さて、xを計算してみる。

x = 2^100(mod 101)
 = 2^(64 + 32 + 4)(mod 101)
 = 2^(2^6 + 2^5 + 2^2)(mod 101)
 = 2^(2^6)(mod 101) × 2^(2^5)(mod 101) × 2^(2^2)(mod 101)

であるから、これの式をt[n]に置き換えると

 = t[6] × t[5] × t[2](mod 101)
 = 79 × 68 × 16 (mod 101)
 = 85952 ≡ 1(mod 101)

つまり、

2^100 ≡ 1 (mod 101)

である事が求まる。
(※フェルマーの小定理『 a^(p-1) ≡ 1 (mod p) 』から、計算結果は正しいことがわかる。)


正直にべき乗の為の掛け算を100回する必要はなく、かなり掛け算の回数が減っており、高速化できる。
この辺はC言語で書いて、掛け算や足算は、アセンブリ言語でかいた関数を呼ぶのが良い気がする。

あとは、mod の高速化だな。
これも、割り算で筆算の要領で余りを求めるのが良い気がしていたが、
論文を色々読んでみたが、それよりも早いアルゴリズムがあるらしい。
様は「商」は要らなくて「余」だけが欲しいのだから、法nの世界の性質を利用するらしい。

あとで、勉強予定。

|

« DES暗号高速化の検討 | トップページ | ファミコン用 音源ドライバー nsd.lib リリース »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/36969/54015233

この記事へのトラックバック一覧です: 多倍長整数 の処理考察:

« DES暗号高速化の検討 | トップページ | ファミコン用 音源ドライバー nsd.lib リリース »