DAY 15- 《公钥密码》-ECC

高中听过有人念ㄙㄨㄟˊ 圆形，我当时真是害怕极了。

---

椭圆曲线 （Elliptic curve）

要提到密码学不可不提的就是椭圆曲线密码学。
这个椭圆不是普通的椭圆，甚至有长得不像椭圆。
先来看这个椭圆曲线。

这个椭圆曲线叫做secp256k1，是用来建构比特币公私钥的椭圆曲线。
椭圆曲线会是一个方程序，形如

像secp256k1的方程序是 。

一个椭圆曲线要怎麽创造公私钥，想出这个的人脑袋真的坏掉。
我看着这个图形只觉得他长得好像钥匙孔。

运算

是这样的，我们先给定图形上的一个点 P，
接着取一个倍数 a。
这时 aP 就会对应到图形上的另外一个点（有够神奇）。
而当 a 到达一定大小时，aP这个点就会消失在这个图形上，
而这个点我们称为无穷远点 point at infinity（），此时的 a 称为 order，写作 「#E」。

上面看到的图形是在实数中定义的椭圆曲线，
而我们要使用的是定义在质数体上的椭圆曲线。
简单来说，就是在 mod p，
其中 p 是大於 3 的质数。

椭圆曲线有一些运算性质

1. 负号

若 P =(x, y)， 则-P=(x, -y)

2 单位元

3 加法

如果P和Q是椭圆曲线上的两个点
那麽P+Q就会是将两个点相连之後对x轴做镜射的那个点

假设，，
首先要先算出 PQ线 的斜率 s 。

4 倍数

在椭圆曲线上做倍数的概念，
是找到P 的切线和曲线相较的点对 x 做镜射。

运用以上所讲的四个运算，就可以在椭圆曲线找出我们所需要的点。
而真正使用的 aP 也可以用加法跟倍数做出来。

举个例子好了，
现在我们有一个曲线 (mod17)，

给定点P ( 8, 10 )。
经由运算你可以算出2P=(0, 22)
还可以一直算下去

3P = (16,2)
4P = (6,17)
5P = (20,3)
6P = (10,25)
7P = (2,6)
8P = (13,6)
...
34P = (16,27)
35P = (0,7)
36P = (8,19)
37P = $\theta$

算到最後一个36P+P的时候
因为斜率不存在，我们就说他的结果是无穷远点。

我当然不是用手算的，下面会附上简单的程序码。
不过因为数字简单，我简陋的程序码也有办法算出来，
如果是数字很大的运算，电脑会直接卡住哦。
如果要加快电脑运算，需要用到其他方法来加速。

Hasse's Theorem

椭圆曲线密码学在公钥密码学上的安全性，
取决於椭圆离散问题（ECDLP）的困难度。
也就是给定两个点 T 和 P，问你「T= aP」 中， a 等於多少。

从上面的例子你可以知道，要想知道 a 是多少，基本上就只能把全部算出来找。
所以可以把 a 作为私钥，T 作为公钥。

已前面的secp256k1的例子来说：
在p = 之下
这个曲线上可以使用的点的数量以十六进位写是
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

根本不可能一个一个算出来。

Hasse's 定理是用来大略计算椭圆曲线的 order 。

内涵如下：

≦ #E ≦
也就是曲线上的点大约会跟质数 p 的位元一样。
Order的大小，也攸关着椭圆曲线密码的安全性。

以下是可以算出 aP 的计算机，不过真的算不了太大的数字，就别指望他了。（mod 15401大概15秒）

print("y^2 = x^3+ax+b")
a = int(input("a:"))
b = int(input("b:"))
x,y = (input("P(x,y):")).split(',')
x = int(x)
y = int(y)
p = int((input("mod?:")))

for i in range(2,p):
    if (2*y*i)%p == 1:
        inverse_2y = i
        break 
    else:
        continue
s1 = ((3*x*x+a)*inverse_2y)%p
x1 = (s1*s1-2*x)%p
y1 = (s1*(x-x1)-y)%p
print("2P = ("+str(x1)+','+str(y1)+')')
x2 = x1
x1 = x
y2 = y1
y1 = y

a = 2
while x2-x1 != 0:
    a += 1
    for j in range(2,p):
        if x2-x1 == 1:
            inverse_x2_x1 = 1
        elif ((x2-x1)*j)%p == 1:
            inverse_x2_x1 = j
            break
        else:
            continue
        
    s = ((y2-y1)*inverse_x2_x1)%p
    x2 = (s*s-x1-x2)%p
    y2 = (s*(x1-x2)-y1)%p
 
    print(str(a)+"P = ("+str(x2)+","+str(y2)+")")

a += 1

print(str(a)+"P = point at infinity")
print("#E = "+str(a))

图片来源：
https://wiki.bitcoinsv.io/index.php/Secp256k1
https://gist.github.com/kanhavishva/6e86e43f107dc657e0dddd7fcddc3420

参考资料：
https://en.bitcoin.it/wiki/Secp256k1