2015-05-16

近代加密快速冪次計算

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

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

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

做法就是最普遍見到的。

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
}

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

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;
}

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)

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
}

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)

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
}

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: $x^{2^i}$	$n$	$n/2$
Left-To-Right	1: $x$	$n$	$n/2$
Left-To-Right(2-bits)	3: $x$, $x^2$, $x^3$	$n$	$3n/8$
Left-To-Right(sliding)	2: $x$, $x^3$	$n$	$n/3$

Attack

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

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

error example

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

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 \left [ 0 \right ] = R \left [ 1 \right ] \times g$，同時 $R \left [ 0 \right ]$ 會是最後的答案。

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 \left [ 1 \right ]$ 的計算是為了下一次為 $a \left [ i+1 \right ] = 1$ 而存在的！

Morris' Blog