Processing math: 100%

近代加密 快速冪次計算

contents

  1. 1. Right-To-Left
  2. 2. Left-To-Right
  3. 3. Left-To-Right(2-bits)
  4. 4. Left-To-Right(sliding)
  5. 5. Summary
  6. 6. Attack
    1. 6.1. error example
    2. 6.2. Montgomery Ladder

先來上競賽中最常見到的快速冪次寫法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long mul(long long a, long long b, long long mod) {
long long ret = 0;
for( ; b != 0; b>>=1, (a<<=1)%=mod)
if(b&1) (ret += a) %= mod;
return ret;
}
long long mpow(long long x, long long y, long long mod) {
long long ret = 1;
while (y) {
if (y&1)
ret = mul(ret, x, mod);
y >>= 1, x = mul(x, x, mod);
}
return ret;
}

這樣的寫法,只運算 64-bits 內的結果相當不錯,與接下來講的算法速度差異並不大。但對於近代加密所需要的離散對數過程,則會有放大速度差異,因為 x, y, mod 三個參數的 bit-length 都相當長。

Right-To-Left

做法就是最普遍見到的。

1
2
3
4
5
6
7
8
9
void pow(x, a) {
R = 1, g = x
for i = 0 to n, step 1
if (a[i] == 1) // a[i] mean i-bit in a
R = R * g
g = g * g
return R
}
1
2
3
4
5
6
example: a = 26 = (11010)
---
#iterator 0 1 2 3 4
#g x, x^2, x^4, x^8, x^16, ...
binary 0 1 0 1 1
x^a = x^2 x^8 x^16 = x^26

Left-To-Right

1
2
3
4
5
6
7
8
void pow(x, a) {
R = 1
for i = n-1 to 0, step -1
R = R ^ 2
if (a[i] == 1)
R = R * x
return R;
}
1
2
3
4
5
example: a = 26 = (11010)
---
#iterator 0 1 2 3 4
binary 1 1 0 1 0
R x^1 x^11 x^110 x^1101 x^11010

也就是說,每一次迭代,將會將指數左移 (R = R ^ 2 就是要移動 R^xxxx 變成 R^xxxx0,切著看是否要乘上 x 來變成 R^xxxx1),這方法雖然不錯,但是計算高位元空迴圈可是不能忽略!當然對於設計電路的人,固定變量的迴圈展開後就不存在這問題。

效能上,期望的乘法次數與 Right-To-Left 是差不多的!長度為 n bits 的數字,期望值會有 n/2 個 1,因此大約需要 n/2 次乘法。

Left-To-Right(2-bits)

1
2
3
4
5
6
7
8
9
10
void pow(x, a) {
pre-computation: x^2, x^3
R = 1
for i = n/2 to 0, step -2
R = R ^ 4
if (a[i+1]a[i] != 0)
R = R * x^(a[i+1]a[i])
return R
}
1
2
3
4
5
6
example: a = 1737 = (01 10 11 00 10 01)
---
#iterator 0 1 2 3 4 5
R x^1 x^4 x^24 x^108 x^432 x^1736
x^6 x^27 x^434 x^1737
a[i+1]a[i] 01 10 11 00 10 01

長度為 n bits 的數字,倆倆一起期望值會有 3n/8 個非 0 (00, 01, 10, 11 中 4 個有 3 個 !=0,計算組數只有 n/2),因此大約需要 3n/8 次乘法。比剛剛快上一點呢 ( 3n/8<n/2 )!

Left-To-Right(sliding)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void pow(x, a) {
pre-computation: x^3
R = 1
for i = n-1 to 0
if a[i]a[i-1] = (11)
R = R ^ 4
R = R * x^3
i -= 2
else if a[i]a[i-1] = (00)
R = R ^ 4
i -= 2
else if a[i] = (0)
R = R ^ 2
i -= 1
else if a[i] = (1)
R = R ^ 2
R = R * x
i -= 1
return R
}
1
2
3
4
5
example: a = (1 10 11 00 10 01)
---
#iterator 0 1 2 3 4 5 6
R x^11 x^11011 x^11011001 x^11011001001
x^110 x^1101100 x^1101100100

期望的乘法次數 n/3,這很可怕,別問我!

Summary

Algorithm Name Table Size #squaring Average #Multiplication
Right-To-Left 1: x2i n n/2
Left-To-Right 1: x n n/2
Left-To-Right(2-bits) 3: x, x2, x3 n 3n/8
Left-To-Right(sliding) 2: x, x3 n n/3

Attack

上述四種方法中,不外乎都存在 Conditional Jump 出現,會導致執行速度跟程式計數器 (Program Counter) 移動上會有所差別。可以進行實作攻擊,從分析時間、電源不穩攻擊,來找到 a 究竟是何物 (通常要偷的都是 xa 上面的 a)!電源雜訊干擾於當指令執行到 Conditional Jump 時,干擾 R 的計算發生錯誤,如果沒有發生錯誤,表示 a[i]=0,反之就能知道 a[i]=1

很趣味地是提供一個不需要 Conditional Jump 的寫法 (實作上),一樣會有這種問題!

error example

1
2
3
4
5
R[1] = 1
for i = n-1 to 0, step -1
R[1] = R[1] ^ 2
R[a[i]] = R[1] × g
return R[1]

提供一個不相干的垃圾暫存器 (redundancy register) 來減少 Jump 的問題,很明顯地 電源雜訊干擾 的攻擊仍然存在!這作法很有趣的啊!只是會被攻擊。

Montgomery Ladder

1
2
3
4
5
R[0] = 1, R[1] = g
for i = n-1 to 0, step -1
R[1-a[i]] = R[0] × R[1]
R[a[i] = R[a[i]] × R[a[i]]
return R[0]

這作法避開之前的問題,解決其中一種被攻擊的方案。

過程中都滿足 R[0]=R[1]×g,同時 R[0] 會是最後的答案。

1
2
3
4
5
6
example: a = 26 = (11010)
---
#iterator 0 1 2 3 4 5
binary 0 1 1 0 1 0
R[0] 1 x x^3 x^6 x^13 x^26
R[1] x x^2 x^4 x^7 x^14

明顯地,R[1] 的計算是為了下一次為 a[i+1]=1 而存在的!