上一篇文章中，ECC椭圆曲线加密(一) 介绍了椭圆曲线的加法，乘法。
同余运算
同余就是有相同的余数，两个整数 a、 b，若它们除以正整数 m所得的余数相等，则称 a， b对于模m同余，用表示。
在数论中叫 “时钟运算”。 这个 “时钟运算” 跟CPU时钟周期没有关系。
python中用% 计算同余，如何计算 呢?
2**137%71
#或者
pow(2,137,71)
12%5
27%5
有限域
上一篇中的椭圆曲线，对坐标（x，y）没有任何限制，只要符合曲线方程就可以，坐标可以是整数、负数、有理数，即在实数范围内，实数用 表示。
椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点，我们要把椭圆曲线定义在有限域上。
而椭圆曲线密码所使用的椭圆曲线是定义在有限域内，有限域用 表示。
有限域最常见的例子是，当元素为质数时的有限域（用表示）所组成的整数集合。
假设在 中的椭圆曲线
是什么计算规则呢？
，用到同余的概念。
我们找到3个坐标 (192, 105) (17, 56), (1, 193)都在有限域中。
#计算他们的余数是否相同
(192**3+7)%223 == 105**2%223
(17**3+7)%223 == 56**2%223
(1**3+7)%223 == 193**2%223
椭圆曲线上的离散对数
在椭圆曲线密码中，我们首先定义一条椭圆曲线，然后对椭圆曲线上的某一点之间的运算进行定义，并用这些运算来进行密码技术的相关计算，这就是椭圆曲线加密算法的数学依据。
如果椭圆曲线上一点P，我们计算nP，显然点的分布与顺序都是杂乱无章的。
乘法逆元
在模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的乘法逆元写作 ，乘法逆元有如下的性质：
乘法逆元的一大应用是模意义下的除法，除法在模意义下并不是封闭的，但我们可以根据上述公式，将其转化为乘法。
假设需要1/4 mod 23，可以转化为，又可以转化为1*(4和23的乘法逆元) mod 23。
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 的计算看上去需要 n 次加法。如果 n 有 k 位二进制位的话，即位，那我们的算法复杂度就是
, 计算量有点大，但是其实存在更快速的方案。
其中一个就是先做倍数再做加法。假设n=151，其对应的二进制是10010111。而二进制数字可以转化为：
我们可以这么写：
所以，该运算过程是这样的：
- 获取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代码实现
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://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/
网友评论