淺析橢圓曲線加密演算法（ECC）-有解無憂

本文首發于先知社區，原文鏈接：https://xz.aliyun.com/t/6295

數學基礎

黎曼幾何中的“平行線”

歐幾里得《幾何原本》中提出五條公設：

過相異兩點，能作且只能作一直線，
有限直線可以任意地延長，
以任一點為圓心、任意長為半徑，可作一圓，
凡直角都相等，
兩直線被第三條直線所截，如果同側兩內角和小于兩個直角，則兩直線作會在該側相交（平行公設），

《幾何原本》中只有第29條命題，

一條直線與兩條平行直線相交,則所成的內錯角相等,同位角相等,且同旁內角之和等于兩直角

才用到了第五公設，其他命題并沒有使用到，因此一些數學家提出疑問：第五公設能否不作為公設，而作為一條定理？能否靠前四條公設證明之？因此出現了長期的關于“平行線理論”的討論，歐氏幾何講“過直線外一點有且只有一條直線與已知直線平行”，后面就有個羅氏幾何（羅巴切夫斯基）講“過直線外一點至少存在兩條直線和已知直線平行”，那么是否有“過直線外一點，不能做直線和已知直線平行？”，黎曼幾何就回答了這個問題，

黎曼幾何中不承認平行線的存在，即在同一平面內任何兩條直線都有公共點（交點），另一條公設講：直線可以無限延長，但總的長度是有限的，

黎曼幾何也被稱為橢圓幾何，橢圓曲線就是基于黎曼幾何的“平行線理論”，

定義平行線相較于無窮遠點P∞，使平面上所有直線都有唯一的交點，

無窮遠點的性質：

一條直線只有一個無窮遠點，
平面上一組相互平行的兩條直線有公共的無窮遠點，
平面上任何相交的直線有不同的無窮遠點（否則就會存在兩個交點），
平面上全體無窮遠點構成一條無窮遠直線，
平面上全體無窮遠點與全體平常點構成射影平面，

射影平面坐標系

射影平面坐標系是對笛卡爾平面直角坐標系的擴展，普通平面直角坐標系無法表示無窮遠點，因此為了表示無窮遠點的坐標，產生了射影平面坐標系，

射影平面點的表示：

對普通平面直角坐標系上的點A(x,y)，令x=X/Z，y=Y/Z(Z≠0)，則點A在射影平面上表示為(X:Y:Z)，

那么對于平面直角做標記上的點(1,2)，在射影平面上坐標為(Z:2Z:Z)Z≠0，

直線方程表示為aX+bY+cZ=0，

兩條平行線L1: X+2Y+3Z=0與L2: X+2Y+Z=0，因為L1||L2，所以Z=0，X+2Y=0，所以無窮遠點坐標為(-2Y:Y:0)，

橢圓曲線方程

一條橢圓曲線在射影平面滿足一齊次方程——威爾斯特拉斯方程：

的所有點的集合，且曲線上的每個點都是非奇異（光滑）的，

橢圓曲線并不是橢圓，是由橢圓曲線的描述方程類似于計算橢圓周長的方程而得名，

“非奇異”或“光滑”，可以理解為，滿足方程的任意一點都存在切線，雖然有的方程滿足上面的形式，但是并不是橢圓曲線，

橢圓曲線上有一個無窮遠點(0:1:0)且滿足方程，

如何把橢圓曲線放到平面直角坐標系呢？射影平面坐標系只多了個無窮遠點，因此求出平面直角坐標系上橢圓曲線所有平常點組成的曲線方程，再加上無窮遠點，就構成了橢圓曲線，

把x=X/Z,y=Y/Z代入威爾斯特拉斯方程，得到普通方程：

橢圓曲線上的群操作

假設用加法符號“+”表示群操作，給定兩個點及其坐標，P(x1,y1)，Q(x2,y2)，計算第三個點R坐標：

P+Q=R (x1,y1)+(x2,y2)=(x3,y3)

在橢圓曲線上定義阿貝爾群，其運演算法則：

任意選取橢圓曲線上兩點P、Q（若P、Q兩點重合，則作P點的切線）作直線交于橢圓曲線的另一點R'，過R'作y軸平行線交于R，規定P+Q=R，

相異點相加P+Q：

相同點相加P+P：

若有k個相同的P點相加，記作kP，

有限域上的橢圓曲線

實數域上的橢圓曲線是連續的，并不適用于加密，考慮到加密演算法的可實作性，要把橢圓曲線定義在有限域上，使之變成離散的點，

給定一個有限域Fp：

Fp只有p（p為素數）個元素0,1,2...p-2,p-1；
Fp的加法（a+b）法則是a+b≡c(mod p)；
Fp的乘法（a×b）法則是a×b≡c(mod p)；
Fp的除法（a÷b）法則是a÷b≡c(mod p)，即a×b^-1≡c(mod p)，b^-1為b的逆元；
Fp的單位元是1，零元是0；
Fp域內運算滿足交換律、結合律、分配律，

并非所有的橢圓曲線都適合加密，下面定義一類適合加密的橢圓曲線：

橢圓曲線Ep(a,b)，p為質數，x,y∈[0,p-1]:

選擇兩個滿足下列約束條件的小于p的非負整數a、b：

無窮遠點O∞是零元，有O∞+O∞=O∞，O∞+P=P；
P(x,y)的負元是(x,-y)，有P+(-P)=O∞；
P(x1,y1)，Q(x2,y2)和R(x3,y3)有如下關系：

其中若P=Q則

，若P≠Q則

k為直線斜率，

橢圓曲線上點的階

如果橢圓曲線上一點P，存在最小的正整數n使得數乘nP=O∞，則稱n為P的階，若n不存在，則P為無限階，

在有限域上定義的橢圓曲線，所有點的階n都是存在的，

加密與解密

等式Q=dG（Q，G為Ep(a,b)上的點，d為小于n（n是點G的階）的整數），在有限域上的橢圓曲線，給定d和G，根據有限域上的加法法則，很容易計算出Q；但給定Q和G，很難計算出d，這就是橢圓曲線的離散對數難題，

點G稱為基點，d為私鑰，Q為公鑰，

加解密步驟

Alice選定一條橢圓曲線Ep(a,b)，并取曲線上一點作為基點G，
Alice選擇一個d作為私鑰，并生成公鑰Q=dG，
Alice將曲線Ep(a,b)和點Q、G發給Bob，
Bob收到資訊后，將待傳輸的明文編碼到曲線Ep(a,b)上的一點M，并選擇一個隨機整數k（k<n），
Bob計算點C1=M+kQ；C2=kG，
Bob將C1 C2發給Alice，
Alice收到資訊后，計算C1-dC2=M+kQ-d(kG)=M+k(dG)-d(kG)=M，得到點M，再對點M進行解碼就得到明文，

攻擊者從信道中截取資訊，只能得到Ep(a,b),Q,G,C1,C2，而通過Q、G求d或通過C1、C2求k都是困難的，因此攻擊者無法獲取到明文，

密碼學中描述一條有限域上的橢圓曲線常用到六個參量：
T=(p,a,b,G,n,h)

p、a、b用來確定一條橢圓曲線，G為基點，n為點G的階，h是有限域橢圓曲線上所有點的個數m與n相除得到的整數部分，

這幾個參量取值的選擇，直接影響了加密的安全性，一般滿足如下條件：

p越大越好，但越大，計算速度會變慢，200位左右可滿足一般安全需求；
p≠n×h；
1≤t＜20；
n為素數；
h≤4，

Demo

這是參考網上的資料實作的簡易ECC加解密Demo：


# -*- coding:utf-8 -*-

def get_inverse(value, p):
    """
    求逆元
    :param value: 待求逆元的值
    :param p: 模數
    """
    for i in range(1, p):
        if (i * value) % p == 1:
            return i
    return -1

def get_gcd(value1, value2):
    """
    輾轉相除法求最大公約數
    :param value1:
    :param value2:
    """
    if value2 == 0:
        return value1
    else:
        return get_gcd(value2, value1 % value2)

def get_PaddQ(x1, y1, x2, y2, a, p):
    """
    計算P+Q
    :param x1: P點橫坐標
    :param y1: P點縱坐標
    :param x2: Q點橫坐標
    :param y2: Q點縱坐標
    :param a: 曲線引數
    :param p: 曲線模數
    """
    flag = 1 # 定義符號位(+/-)

    # 如果P=Q，斜率k=(3x^2+a)/2y mod p
    if x1 == x2 and y1 == y2:
        member = 3 * (x1 ** 2) + a # 分子
        denominator = 2 * y1 # 分母

    # 如果P≠Q， 斜率k=(y2-y1)/(x2-x1) mod p
    else:
        member = y2 - y1
        denominator = x2 - x1

        if member * denominator < 0:
            flag = 0 # 表示負數
            member = abs(member)
            denominator = abs(denominator)

    # 化簡分子分母
    gcd = get_gcd(member, denominator) # 最大公約數
    member = member // gcd
    denominator = denominator // gcd
    # 求分母的逆元
    inverse_deno = get_inverse(denominator, p)
    # 求斜率
    k = (member * inverse_deno)
    if flag == 0:
        k = -k
    k = k % p

    # 計算P+Q=(x3,y3)
    x3 = (k ** 2 - x1 - x2) % p
    y3 = (k * (x1-x3) -y1) % p

    return x3, y3

def get_order(x0, y0, a, b, p):
    """
    計算橢圓曲線的階
    """
    x1 = x0 # -P的橫坐標
    y1 = (-1 * y0) % p # -P的縱坐標
    temp_x = x0
    temp_y = y0
    n = 1
    while True:
        n += 1
        # 累加P,得到n*P=0∞
        xp, yp = get_PaddQ(temp_x, temp_y, x0, y0, a, p)
        # 如果(xp,yp)==-P，即(xp,yp)+P=0∞，此時n+1為階數
        if xp == x1 and yp == y1:
            return n+1
        temp_x = xp
        temp_y = yp

def get_dot(x0, a, b, p):
    """
    計算P和-P
    """
    y0 = -1
    for i in range(p):
        # 滿足適合加密的橢圓曲線條件，Ep(a,b)，p為質數，x,y∈[0,p-1]
        if i**2 % p == (x0**3 + a*x0 + b) % p:
            y0 = i
            break
    # 如果找不到合適的y0回傳False
    if y0 == -1:
        return False
    # 計算-y
    x1 = x0
    y1 = (-1*y0) % p
    return x0, y0, x1, y1

def get_graph(a, b, p):
    """
    畫出橢圓曲線散點圖
    """
    xy = []
    # 初始化二維陣列
    for i in range(p):
        xy.append(['-' for i in range(p)])

    for i in range(p):
        value = https://www.cnblogs.com/KRDecad3/p/get_dot(i, a, b, p)
        if (value != False):
            x0,y0,x1,y1 = value
            xy[x0][y0] = 1
            xy[x1][y1] = 1

    print('橢圓曲線散點圖：')
    for i in range(p):
        temp = p - 1 -i
        if temp >= 10:
            print(temp, end='')
        else:
            print(temp, end='')

        # 輸出具體坐標值
        for j in range(p):
            print(xy[j][temp], end='')
        print()

    print(' ', end='')
    for i in range(p):
        if i >= 10:
            print(i, end='')
        else:
            print(i, end='')

    print()

def get_nG(xG, yG, priv_key, a, p):
    """
    計算nG
    """
    temp_x = xG
    temp_y = yG
    while priv_key != 1:
        temp_x, temp_y = get_PaddQ(temp_x, temp_y, xG, yG, a, p)
        priv_key -= 1
    return temp_x, temp_y

def get_KEY():
    """
    生成公鑰私鑰
    """
    # 選擇曲線方程
    while True:
        a = int(input('輸入橢圓曲線引數a（a>0）的值：'))
        b = int(input('輸入橢圓曲線引數b（b>0）的值：'))
        p = int(input('輸入橢圓曲線引數p（p為素數）的值：'))

        # 滿足曲線判別式
        if (4*(a**3)+27*(b**2))%p == 0:
            print('輸入的引數有誤，請重新輸入！\n')
        else:
            break

    # 輸出曲線散點圖
    get_graph(a, b, p)

    # 選擇基點G
    print('在上圖坐標系中選擇基點G的坐標')
    xG = int(input('橫坐標xG：'))
    yG = int(input('縱坐標yG：'))

    # 獲取曲線的階
    n = get_order(xG, yG, a, b, p)

    # 生成私鑰key，且key<n
    priv_key = int(input('輸入私鑰key(<%d)：'%n))
    #生成公鑰KEY
    xK, yK = get_nG(xG, yG, priv_key, a, p)
    return xK, yK, priv_key, a, b, p, n, xG, yG

def encrypt(xG, yG, xK, yK,priv_key, a, p, n):
    """
    加密
    """
    k = int(input('輸入一個整數k(<%d)用于計算kG和kQ：' % n))
    kGx, kGy = get_nG(xG, yG, priv_key, a, p) # kG
    kQx, kQy = get_nG(xK, yK, priv_key, a, p) # kQ
    plain = input('輸入需要加密的字串：')
    plain = plain.strip()
    c = []
    print('密文為：', end='')
    for char in plain:
        intchar = ord(char)
        cipher = intchar * kQx
        c.append([kGx, kGy, cipher])
        print('(%d,%d),%d' % (kGx, kGy, cipher), end=' ')

    print()
    return c

def decrypt(c, priv_key, a, p):
    """
    解密
    """
    for charArr in c:
        kQx, kQy = get_nG(charArr[0], charArr[1], priv_key, a, p)
        print(chr(charArr[2] // kQx), end='')
    print()


if __name__ == '__main__':
    xK, yK, priv_key, a, b, p, n, xG, yG = get_KEY()
    c = encrypt(xG, yG, xK, yK, priv_key, a, p, n)
    decrypt(c, priv_key, a, p)

注：加密函式中，計算密文是通過明文字符的ASCII碼乘點kQ的x坐標得到，即incharkQx；而一些加密中是將明文轉換為大整數再轉換為曲線上的點M(x,y)，密文為(C1=kG, C2=(M+kQ))，解密M=C1-priv_keyC2=M+kQ-priv_keykG=M+kpriv_keyG-priv_keykG

總結

本文初步介紹了ECC演算法的基本原理和實作步驟，另外，橢圓曲線還應用于密鑰交換ECDH、數字簽名ECDSA等，一些區塊鏈專案中使用的加密演算法也是橢圓曲線，如位元幣中的數字簽名演算法Secp256k1，

由于本人水平有限，文章出現紕漏，還請大佬們斧正，

參考文章

https://www.pediy.com/kssd/pediy06/pediy6014.htm

https://blog.dyboy.cn/websecurity/121.html

https://github.com/amintos/PyECC/tree/master/ecc

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/10880.html

標籤：訊息安全

上一篇：Reproduction CVE_2019_0708

下一篇：Silky-CTF: 0x02 Vulhub Walkthrough