暗号の数学

計算法 (演算の高速化)

Karatsuba乗算

2n 桁の数 u，vの乗算を行うことを考える．u，v を基数 b の冪 x = bⁿ を用いて

u = u₁x + u₀，　v = v₁x + v₀

のように上半分と下半分に分ければ，x を基数とした乗算と考えることができる．

このとき単純に w = u v を求めると，

w = u₁v₁x² + (u₀v₁ + u₁v₀)x + u₀v₀

のように n 桁 × n 桁の乗算が 4回必要である．しかし

u₀v₁ + u₁v₀ = (u₁ + u₀)(v₁ + v₀) - (u₁v₁ + u₀v₀)

または

u₀v₁ + u₁v₀ = u₁v₁ + u₀v₀ - (u₁ - u₀)(v₁ - v₀)

という関係を使えば n 桁×n 桁の乗算は 3回で済むことが分かる．ここで，さらに u₁,u₀,v₁,v₀ の上位の桁を 0 で埋めて桁数を偶数にするか，あるいは始めから u，v の桁数を 2の冪にしておけば，3回の乗算に同じアルゴリズムを再帰的に適用することができる．この乗算アルゴリズムを Karatsuba乗算(Karatsuba Multiplication)という．すなわち， b 進法で表現したとき 2桁になる整数同士の乗算は，b 進法で 1桁の整数同士の乗算を 3回と，それよりもコストの十分に小さい加減算を用いて行うことができる．

n = 2^kと仮定したとき，b 進法で n 桁の整数同士の乗算をKaratsuba乗算で行うと，b 進法で1桁の整数同士の乗算が 3^k 回必要となる．k = log₂ n より，この方法での b 進法で n 桁の整数同士の乗算のコストは，3^k = 3^{log₂ n} = n^{log₂ 3} ≒ n^1.585 程度で済むことになる．実際には n が 2^k で表現できるとは限らないので， 2^k で表現できないときは n^1.585 よりも少し余計にかかる．

多項式の積 (Karatsuba - Offman乗算)

多項式の変数 x の係数を計算するときに，x⁰ や x² の係数を再利用することにより，加減算より遅い乗算の回数を削減でき高速化が図れる（a_i や b_i が多項式である場合には効果がある）．

(a₀ + a₁ x)(b₀ + b₁ x) = a₀b₀ + (a₀b₁ + a₁b₀) x + a₁b₁ x²
　= a₀b₀ + {(a₀ + a₁)(b₀ + b₁) - a₀b₀ - a₁b₁} x + a₁b₁ x²

(a₀ + a₁ x + a₂ x²)(b₀ + b₁ x + b₂ x²)
　= a₀b₀ + [{(a₀ + a₁)(b₀ + b₁) - a₁b₁} - a₀b₀] x + [(a₀ + a₁ + a₂)(b₀ + b₁ + b₂)
　 - {(a₀ + a₁)(b₀ + b₁) - a₁b₁} - {(a₁ + a₂)(b₁ + b₂) - a₁b₁}] x²
　 + [{(a₁ + a₂)(b₁ + b₂) - a₁b₁} - a₂b₂] x³ + a₂b₂ x⁴

中国人の剰余定理

定理
p₁, p₂, ・・・, p_m を互いに素な整数とするとき，
x ≡ a₁ (mod p₁)

x ≡ a₂ (mod p₂)

・・・

x ≡ a_m (mod p_m)
からなる連立一次合同式は，法 n = p₁p₂・・・p_m のもとで次の一意な解をもつ．
x = a₁n₁x₁ + a₂n₂x₂ + ・・・ + a_mn_mx_m (mod n)

n_ix_i ≡ 1 (mod p_i), 　n_i = n/p_i
例
連立一次合同式

　x ≡ 1 (mod 4)

　x ≡ 3 (mod 5)

　x ≡ 2 (mod 7)
は，次のように解ける．

　4・5・7 = 35・4 = 28・5 = 20・7 = 140

　35・3 ≡ 1 (mod 4)

　28・2 ≡ 1 (mod 5)

　20・6 ≡ 1 (mod 7)

　x = 35・3・1 + 28・2・3 + 20・6・2 = 93 (mod 140)
アルゴリズム
入力：整数 a₁, a₂,・・・, a_k，p₁, p₂.・・・, p_k.
出力：解 x.
1. M := p₁, b := a₁
2. For i = 2 to k
3. 　b := mod (b + M modinv(M, p_i) (a_i - b), M p_i)
4. 　M := M p_i
5. Return b

剰余演算

べき乗剰余演算
整数 M の法 N におけるべき乗剰余 R = M^e mod N を求める．指数 e を 2進表現したときのビット数を n とする．

(1) Binary法(右向き法)
1. R ← M
2. For i = n - 2 down to 0 do
3. 　R ← R² mod N
4. 　If i-th bit of e is 1 then
5. 　　R ← R・M mod N
6. Return R
(2) Binary法(左向き法)
1. R ← 1
2. S ← M
3. For i = 0 to n - 1 do
4. 　 If i-th bit of e is 1 then
5. 　　 R ← R・S mod N
6. 　 S ← S² mod N
7. Return R
(3) 中国人の剰余定理の利用

N が合成数の場合，N の因数分解と中国人剰余定理を用いてべき乗剰余演算を高速化できる．

N = Π p_i, GCD(p_i, p_j) = 1 (i ≠ j) と因数分解できた場合，
Y = X^e mod N はすべての i に対して Y = X^e mod p_i を満たす数である．
Y は，Y_i = X^e mod p_i を計算すれば中国人剰余定理を用いて，

Y = ∑ (N / p_i)d_iY_i mod N

で求められる．ここで， d_i は d_i・N / p_i = 1 mod p_iを満たす数である．

上記の中国人の剰余定理は，RSA暗号の復号に次のように利用される．

M = C^d mod n　(n = pq：p，q は互いに素な整数)を計算する場合，

c₁ = C mod p,　 c₂ = C mod q

d₁ = d mod p - 1,　d₂ = d mod q - 1

m₁ = C^d mod p = c₁^d mod p = c₁^d₁ mod p

m₂ = C^d mod q = c₂^d mod q = c₂^d₂ mod q

より，次の連立方程式を解けばよい．

M ≡ m₁ (mod p)

M ≡ m₂ (mod q)
各種のべき乗演算
(1) Y = X 2^k mod N
　入力： X ∈ Z_N，N (奇数)，k > 0
　出力： X 2^k mod N
1. If k = 0 then return X else k = k -1
2. If X ← 2X
3. If X > N then X ← X - N
4. Goto step 1
(2) Y = X 2^-k mod N
　入力： X ∈ Z_N，N (奇数)，k > 0
　出力： X 2^-k mod N
1. If k = 0 then return X else k ← k -1
2. If X is even then X ← X / 2 else X ← (X + N) / 2
3. Goto step 1
(3) Y = X^-1 (mod 2^k)
　入力：奇整数 X，0 < X < 2^k.
　出力： X^-1 (mod 2^k).
1. Y ← 1
2. For i = 2 to k do
3. 　If XY (mod 2ⁱ) > 2^i-1 then Y ← Y + 2^i-1
4. Return Y
(4) Z = XY mod p²
　入力：整数 X，Y
　出力： XY (mod p²)
1. X = a₁ + b₁p
2. Y = a₂ + b₂p
3. a₁a₂ = a' + b'p
4. a'' = a₁b₂ + a₂b₁ + b' mod p
5. XY mod p² = (a₁ + b₁p)(a₂ + b₂p) mod p²
  
  = a₁a₂ + (a₁b₂ + a₂b₁)p mod p²
  
  = a' + (a₁b₂ + a₂b₁ + b')p mod p²
  
  = a' + a''p　 (< p²)

逆元

並列逆元
2 つの逆元の計算 a^-1 と b^-1 は，
a^-1 = (ab)^-1・b

b^-1 = (ab)^-1・a
により，１回の逆元と 3回の乗算で行うことができる．
再帰的な繰り返しにより， t 個の逆元は 1回の逆元と 3(t-1) 回の乗算で計算できる．例えば，4個の場合次のようになる．
(ab)^-1 = (ab・cd)^-1・cd

(cd)^-1 = (ab・cd)^-1・ab

Montgomery 算法

Montgomery表現
大きな素数 p，2進基数 b に対して，
R =b^t > p
により，R と t を定義する．このとき， GF(p) の元 x に対して
xR (mod p)
を x の Montgomery表現という．この表現と通常の表現とは1対1対応である．
Montgomery表現による加法と減法は通常の方法で行われるが，乗法はより効率的に実行できる．そのため，乗算を行う場合に対象とする数を Montgomery表現に変換し，Montgomery空間上で乗算を行い，結果を通常の表現に戻すことにより効率的に乗算を行うことができる．
Montgomery還元
Montgomery表現から通常の表現に戻す演算を Montgomery還元という．Montgomery表現 y の Montgomery還元 MR(y) は次式で与えられる．
MR(y) = yR^-1 (mod p)
Montgomery還元は，以下のアルゴリズムで与えられる．
　入力：整数 y < pR.
　出力： x = yR^-1 (mod p).
1. u ← -yp^-1 (mod R).
2. x ← (y + up)/R.
3. While x ≧ p do x ← x - p.
4. Return x.
上記において，p^-1 (mod R) を事前に計算し保持しておくことで演算を効率化できる．また，R による除算は，R が2進基数のべきであるためシフト演算で計算できる．
なお， x をモンゴメリ表現 X に変換するためには，R を掛けて p による剰余を求めればよいので，あらかじめ R₂ = R² mod p を用意して MR(xR₂) を求めればよい．
乗算
- 通常表現
  
  x, y ∈ GF(p)
  
  z = xy (mod p)
- Montgomery表現
  
  X = xR (mod p)
  
  Y = yR (mod p)
  
  Z = xyR (mod p)
- Montgomery空間上での乗算
  
  Z = XYR^-1 = (xyR²)R^-1 = xyR (mod p)
- Montgomery還元
  
  MR(Z) = (xyR)R^-1 = xy (mod p)
逆元
- 通常表現
  
  x ∈ GF(p)
  
  z = x^-1 (mod p)
- Montgomery表現
  
  X = xR (mod p)
  
  Z = x^-1R (mod p)
- Montgomery空間上での逆元演算
  
  Z = X^-1R² = (xR)^-1R² = x^-1R (mod p)
- Montgomery還元
  
  MR(Z) = (x^-1R)R^-1 = x^-1 (mod p)
べき乗
- 通常表現
  
  x, e ∈ GF(p)
  
  z = x^e (mod p)
- Montgomery空間上でのべき乗剰余演算 (バイナリ法)
  1. A ← R (mod p), X ← xR (mod p)
  2. i：number of bit in e
  3. A ← MR (A A), i = i - 1.
  4. If e_i = 1, then A = MR (A X).
  5. if i ≠ 0, then go to step 3.
  6. z = MR (A)

Page Top