橢圓曲線

橢圓曲線在代數(shù)上的表示是下面這個方程：
y² = x³ + ax + b
其中，a = 0, b = 7 (比特幣系統(tǒng)所使用的版本)，它的圖形如下：

橢圓曲線有一些很有用的特征

• 一條非垂直的直線與橢圓曲線相交于兩點蚁袭，若這兩點均不是切點，則曲線上必有第三點與那條直線相交
• 過曲線上任意一點的非垂直切線與該曲線必有且僅有另一個交點欲低。

利用這些特征药版，我們可以定義兩種運算：“異點相加”和“同點加倍”。

“異點相加”, P + Q = r, 定義為：r為r’基于x軸的反射點（對稱點）白魂。其中汽纤，R’為包含P和Q的直線與曲線的第三個交點,如圖上所示。

同樣福荸，“同點加倍”蕴坪，P + P = r, 定義為：作一條過P點的切線，先求出該切線與曲線的另一交點R’,再計算r‘基于x軸的反射點r敬锐。

求r 坐標,得到一個非常美的結果

當p!=q

有限域

同時背传，并不是所有的橢圓曲線都適合加密。y²=x³+ax+b是一類可以用來加密的橢圓曲線台夺，也是最為簡單的一類径玖。下面我們就把y²=x³+ax+b 這條曲線定義在Fp（模p剩余類構成的域）上：
選擇兩個滿足下列條件的小于p(p為素數(shù))的非負整數(shù)a、b
4a³+27b²≠0　(mod p)
則滿足下列方程的所有點(x,y)颤介，再加上 無窮遠點O∞ 梳星，構成一條橢圓曲線。
y²=x³+ax+b (mod p)
其中 x,y屬于0到p-1間的整數(shù)滚朵，準確的說是模素數(shù)p剩余類丰泊，并將這條橢圓曲線記為Ep(a,b)。

這里為什么要加上無窮遠點呢始绍，無窮遠點來自于射影平面瞳购，射影平面比歐式平面多了無窮遠點，所有無窮遠點構成無窮遠直線亏推，射影平面有一個重要假設：

平行線在無窮遠處相較于一個點学赛，即無窮遠點O點年堆，并且每條直線只有一個無窮遠點

在橢圓曲線E_p(a,b)中p₁+r₁=O,p₁+O=p₁,p₂+r₂=O,p₂+O=p₂
所有橢圓線點按照P+Q=r算法構成加群
O為單元零元，p₁,r₁互為逆元盏浇，p₂,r₂互為逆元变丧。

舉個例子

算法原理

考慮如下等式：K=kG [其中 K,G為Ep(a,b)上的點，k為小于n（n是點G的階）的整數(shù)]萧芙，不難發(fā)現(xiàn)给梅，給定k和G，根據(jù)加法法則双揪，計算K很容易动羽；但給定K和G，求k就相對困難了渔期。這就是橢圓曲線加密算法采用的難題曹质，我們把點G稱為基點（base point）。

加解密流程：
1擎场、用戶A選定一條橢圓曲線Ep(a,b)羽德，并取橢圓曲線上一點，作為基點G迅办。
2宅静、用戶A選擇一個私有密鑰k，并生成公開密鑰K=kG站欺。
3姨夹、用戶A將Ep(a,b)和點K，G傳給用戶B矾策。
4磷账、用戶B接到信息后 ，將待傳輸?shù)拿魑木幋a到Ep(a,b)上一點M（編碼方法很多贾虽，這里不作討論）逃糟，并產(chǎn)生一個隨機整數(shù)r。
5、用戶B計算點C1=M+rK绰咽；C2=rG菇肃。
6、用戶B將C1取募、C2傳給用戶A琐谤。
7、用戶A接到信息后玩敏，計算C1-kC2斗忌，結果就是點M。因為 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M,
再對點M進行解碼就可以得到明文旺聚。

G = (1,18)
prikey = 40
pubkey = get_add(G, prikey)
r = 16
M = (34,24)
C1 = get_r(M,get_add(pubkey, r))
C2 = get_add(G, r)
temp = get_add(C2,prikey)
get_r(C1,(temp[0], MOD-temp[1]))]))

最后一步解密結果和原文一樣

[34, 24]

簽名過程如下：

1织阳、選擇一條橢圓曲線Ep(a,b)，和基點G翻屈；
2、選擇私有密鑰k（k<n妻坝，n為G的階）伸眶，利用基點G計算公開密鑰K=kG；
3刽宪、產(chǎn)生一個隨機整數(shù)r（r<n）厘贼，計算點R=rG；
4圣拄、將原數(shù)據(jù)和點R的坐標值x,y作為參數(shù)嘴秸，計算SHA1做為hash，即Hash=SHA1(原數(shù)據(jù),x,y)庇谆；
5岳掐、計算s≡r - Hash * k (mod n)
6、r和s做為簽名值饭耳，如果r和s其中一個為0串述，重新從第3步開始執(zhí)行

驗證過程如下：
1、接受方在收到消息(m)和簽名值(r,s)后寞肖，進行以下運算
2纲酗、計算：sG+H(m)K=(x1,y1), r1≡ x1 mod p。
3新蟆、驗證等式：r1 ≡ r mod p觅赊。
4、如果等式成立琼稻，接受簽名吮螺，否則簽名無效。

import numpy as np
import  sys  
import matplotlib.pyplot as plt
def ecc_equation(a, b):
    def ecc(x):
        return x**3+a*x+7
    return ecc

# 求平方根
def get_square_root_mod(mod):
    def get_square_root(n):
        lr = []
        if n >= mod:
            n = n%mod
        for el in xrange(0, mod):
            if el**2%mod == n:
                return el
    return get_square_root
# y
def get_y(x):
    return [x,get_square_root(ecc(x))]

# 檢查點是否在曲線上
def check_point(p, mod=MOD):
    if p[1]**2%mod == (ecc(p[0]))%mod:
        return True
    else:
        return False
# 求element在模mod剩余類群逆元
def invert(element, mod):
    if element >= mod:
        element = element%mod
    if element == 0:
        return None
    for index in xrange(1, mod):
        if element*index%mod == 1:
            return index
# 給出p,q求r=p+q
# if p != q
# c = (py-qy)/(px-qx)
# rx = c^2 - px-qx
# ry = c(px-rx)-py
# if p ==q
# c = (3px^2+a)/2py,rx = c^2-2px,ry=c(px-rx)-py
def get_r(p, q,mod=MOD, a=A):
    p = map(lambda x: x % mod, p)
    q = map(lambda x: x % mod, q)
    if p[0] == q[0] and (p[1]+q[1])%mod==0:
        #互為逆元點和為無窮遠點，方便處理 記為[np.infty,np.infty]
        return [np.infty,np.infty]
    if p != q:
        c = (p[1]-q[1])*invert(p[0]-q[0], mod)%mod
    else:
        c = (3*p[0]**2+a)*invert(2*p[1],mod)%mod
    rx = (c**2-p[0]-q[0])%mod
    ry = (c*(p[0]-rx)-p[1])%mod
    return [rx,ry]

# 構建循環(huán)群
def cycle_group(generate_el):
    power = [generate_el]
    lr = generate_el
    while True:
        lr = get_r(generate_el, lr)
        power.append(lr)
        if lr == [np.infty, np.infty]:
            return power
# 求倍點
def get_add(G, multiple):
    lr = G
    for index in xrange(1, multiple):
        lr = get_r(lr, G)
    return lr
# 功能同上规脸，利用同點加倍坯约，性能更高
def get_multiple(G, multiple):
    if multiple%2 == 0:
        temp = get_multiple(G, multiple/2)
        return get_r(temp,temp)
    else:
        if multiple > 1:
            temp = get_multiple(G, multiple-1)
            return get_r(G, temp)
        else:
            return G
import numpy as np
import  sys  
import matplotlib.pyplot as plt

A = 0
B = 7
MOD = 79
#79
ecc = ecc_equation(A,B)
get_square_root = get_square_root_mod(MOD)
x = xrange(0,MOD)
y = map(get_y, x)
y = np.array(y)
total = y[np.where(y[:,1]>-1)]
total_inverse =map(lambda x:[x[0], MOD-x[1]],filter(filtery , total))
total = np.concatenate((total, total_inverse),axis=0)
#print total

plt.scatter(total[:,0], total[:,1])
plt.show()
print len(total)
print total[np.where(total[:,1]==0)]
print map(lambda x:len(x), map(cycle_group, total))