Crypto In Action (1) - 基础算法

每个椭圆曲线都是一个方程式，比如Bitcoin使用的secp256k1 ^[1] 曲线: $$y^2 = x^3 + 7$$

这些曲线的代数运算(比如$x^3 = x \times x \times x$ ...)是一类特殊的运算，只有加法、乘法，除法是乘逆，减法是加逆。

通过最基本的加法、乘法，构建出除法、幂以及平方根等一系列算术运算，它们是计算椭圆曲线方程的最基础数学操作，也是密码学的基石。

本文介绍两个核心算法，为有限域的算术运算（加、减、乘、除）做准备。

Euclid Algorithm

欧几里得算法，求最大公约数

Example:

求37和14的最大公约数: gcd(37,14)，计算过程：

$$ \begin{aligned} &a_1 =37,\\ &a_2 =14,\\ &a_3 =37 - 2 \times 14 =9,\\ &a_4 =14 - 1 \times 9 =5,\\ &a_5 =9 - 1 \times 5 =4,\\ &a_6 =5 - 1 \times 4 =1\\ \end{aligned} $$

发现什么木有？这个过程归纳出一个规律:

$$a_{j+2} = a_{j} - q_{j}a_{j+1}$$

假设 $j=3$，我们得到$a_{5}$:

$$ \begin{aligned} &a_{5} = a_{3} - q_{3}a_{4} = 9 - 1 \times 5 =4\\ &q_{3} = a_{3}/a_{4}\\ &a_{5} = a_{3} - a_{4} \times (a_{3}/a_{4})\\ &a_{5} = a_{3} \mod a_{4}\\ \end{aligned} $$

其实这个规律就是不停的求模，Rust非递归实现: ^[2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/// The function `gcd` implements Euclidean algorithm with non-recursive
pub fn gcd(mut a: i8, mut b: i8) -> i8 {
    while b != 0 {
        a %= b;
        let tmp = a;
        a = b;
        b = tmp;
    }
    return a;
}

Extened Euclid Algorithm

扩展欧几里得算法, 根据欧几里得算法倒推求满足等式系数的一种算法。
就是求等式中的r和s，使其满足等式: $$ \begin{aligned} &gcd(a,b) = ra + sb\\ \end{aligned} $$

Example: $$ \begin{aligned} &gcd(37,14) = r \times 37 + s \times 14\\ &1= r \times 37 + s \times 14\\ \end{aligned} $$

我们来做一个求解推导: $$ \begin{aligned} &a_1 = 37 = a = 1a+0b,\\ &a_2 = 14 = b = 0a+1b,\\ &a_3 = 9 = a_1-2a_2 = a-2b,\\ &a_4 = 5 = a_2-a_3 = -a+3b,\\ &a_5 = 4 = a_3-a_4 = 2a-5b,\\ &a_6 = 1 = a_4-a_5 = -3a+8b\\ \end{aligned} $$

使用表格表示: $$a_j =r_{j}a + s_{j}b$$ $$ \begin{bmatrix} a_j & r_j & s_j \\ 37 & 1 & 0 \\ 14 & 0 & 1 \\ 9 & 1 & -2 \\ 5 & -1 & 3 \\ 4 & 2 & -5 \\ 1 & -3 & 8 \\ \end{bmatrix} $$

这个算法需要根据推导进行分析，Rust非递归实现: ^[3]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/// The function `xgcd` implements Extended Euclidean algorithm with non-recursive
pub fn xgcd(a: i8, b: i8) -> (i8, i8, i8) {
    let (mut s, mut s_last) = (0, 1);
    let (mut t, mut t_last) = (1, 0);
    let (mut r, mut r_last) = (b, a);
    while r != 0 {
        let quotient = r_last / r;
        r_last -= quotient * r;
        s_last -= quotient * s;
        t_last -= quotient * t;
        mem::swap(&mut r, &mut r_last);
        mem::swap(&mut s, &mut s_last);
        mem::swap(&mut t, &mut t_last);
    }
    (r_last, s_last, t_last) // (gcd, coeff_a, coeff_b)
}

小结

本节讨论了数论中最基础的两个算法，从Euclid Algorithm到Extened Euclid Algorithm。