[未完成]ECC椭圆曲线加密算法(二)


上一篇文章中，[ECC 椭圆曲线加密 (一)](https://qiita.com/shooter/items/888d764e6db2e320d4ea) 介绍了椭圆曲线的加法，乘法。

## 同余运算

同余就是有相同的余数，两个整数 a、b，若它们除以正整数 m 所得的余数相等，则称 a，b 对于模 m 同余，用$a ≡ b \ (mod \ m)$表示。

在数论中叫“时钟运算”。这个“时钟运算”跟 CPU 时钟周期没有关系。

$$
12÷5=2...2 \\
17÷5=3...2 \\
27÷5=5...2 \\
\\
17 \ mod \ 5 = 2 \\
12 ≡ 17  (mod \ 5) \\
17 ≡ 27  (mod \ 5)
$$

python 中用`%` 计算同余，如何计算 $2^{137} mod \ 71$呢？

```python
2**137%71
#或者
pow(2,137,71)
12%5
27%5
```

## 有限域

上一篇中的椭圆曲线，对坐标（x，y）没有任何限制，只要符合曲线方程就可以，坐标可以是整数、负数、有理数，即在实数范围内，实数用$\mathbb{R}$ 表示。

椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点，我们要把椭圆曲线定义在有限域上。
而椭圆曲线密码所使用的椭圆曲线是定义在有限域内，有限域用 $\mathbb{F}$ 表示。
有限域最常见的例子是，当元素为质数时的有限域（用$\mathbb{F}_p$表示）所组成的整数集合。

假设在 $\mathbb{F}_{223}$中的椭圆曲线 $y^2=x^3+7$ 是什么计算规则呢？
$y^2 ≡ (x^3+7) \ (mod \ 223)$，用到同余的概念。
我们找到 3 个坐标 (192, 105) (17, 56), (1, 193) 都在有限域中。

```python
#计算他们的余数是否相同
(192**3+7)%223 == 105**2%223
(17**3+7)%223 == 56**2%223
(1**3+7)%223 == 193**2%223
```

## 椭圆曲线上的离散对数
在椭圆曲线密码中，我们首先定义一条椭圆曲线，然后对椭圆曲线上的某一点之间的运算进行定义，并用这些运算来进行密码技术的相关计算，这就是椭圆曲线加密算法的数学依据。

如果椭圆曲线上一点 P，我们计算 nP，显然点的分布与顺序都是杂乱无章的。

>![](https://upload-images.jianshu.io/upload_images/47789-a5a951216db7c715.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

## 乘法逆元

在模 7 乘法中：

*   1 的逆元为 1 (1*1)%7=1
*   2 的逆元为 4 (2*4)%7=1
*   3 的逆元为 5 (3*5)%7=1
*   4 的逆元为 2 (4*2)%7=1
*   5 的逆元为 3 (5*3)%7=1
*   6 的逆元为 6 (6*6)%7=1

扩展欧几里得算法用来求乘法逆元

在 mod p 的意义下我们把 x 的乘法逆元写作 $x^{-1} $，乘法逆元有如下的性质：
 $x \times x^{-1} ≡ 1 (mod \ p)$

乘法逆元的一大应用是**模意义下的除法**，除法在模意义下并不是封闭的，但我们可以根据上述公式，将其转化为乘法。
假设需要`1/4 mod 23`，可以转化为$1*4^{-1} mod \ 23$，又可以转化为 1*(4 和 23 的乘法逆元) mod 23。

```python
def ext_euclid(a, b):
     if b == 0:
         return 1, 0, a
     else:
         x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
         x, y = y, (x - (a // b) * y)
         return x, y, q
```

## 标量乘法

除了加法，我们定义另外一种运算：标量乘法，也即数乘

$nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}$

写成如上形式的话，nP 的计算看上去需要 n 次加法。如果 n 有 k 位二进制位的话，即$2^k$位，那我们的算法复杂度就是$O(2^k)$, 计算量有点大，但是其实存在更快速的方案。

其中一个就是先做**倍数再做加法**。假设 n=151，其对应的二进制是 10010111。而二进制数字可以转化为：

$$
\begin{array}{rcl}
    151 & = & 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 \\
    & = & 2^7 + 2^4 + 2^2 + 2^1 + 2^0
\end{array}
$$

我们可以这么写：

$151P = 2^7 P + 2^4 P + 2^2 P + 2^1 P + 2^0 P$

 所以，该运算过程是这样的：

- 获取 P
- 取 P 的 2 倍，得到 2P
- 2P 加上 P
- 把 2P 再取 2 倍，得到 4P
- 4P 加上 2P 加上 P
- 4P 再取 2 倍，得到 8P
- 不取 8P 做运算
- 8P 取 2 倍，得到 16P
- 16P 加上 4P 加上 2P 加上 P
- ……

最终，要得到 151P 我们只是做了一些简单的倍数以及加法。

如果我们计算 6P，只需要
- P
- 通过 P 得到 2P
- 通过 2P 得到 4P
- 2P+4P 得到 6P

可以看看下面的 Python 代码实现

```python
def bits(n):
    '''
    bits(151) => 1, 1, 1, 0, 1, 0, 0, 1
    '''
    while n:
        yield n & 1
        n >>= 1

def double_and_add(n, x):
    result = 0
    addend = x

    for bit in bits(n):
        if bit == 1:
            result += addend
        addend *= 2

    return result
```

---

参考：
https://www.cnblogs.com/Kalafinaian/p/7392505.html
https://oi.men.ci/mul-inverse/
https://eng.paxos.com/blockchain-101-foundational-math
https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography
https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/