上一篇分享了“模運算”相關的知識，並且計算了一些有限域的例子，這一篇我們討論在通用零知識證明中經常提到的橢圓曲線和雙線性配對。橢圓曲線作為雙線性對的基礎和前置知識，我們首先介紹一下其在實數域上的表現形式。
原文標題：【密碼專欄】動手計算雙線性對（中）
前言
上一篇分享了“模運算”相關的知識，並且計算了一些有限域的例子，這一篇我們討論在通用零知識證明中經常提到的橢圓曲線和雙線性配對。橢圓曲線作為雙線性對的基礎和前置知識，我們首先介紹一下其在實數域上的表現形式，然後通過計算的方法列出” F_101 ” 和其擴域“ F_101^2”上的全部元素的列表。
橢圓曲線相關知識—曲線方程
橢圓曲線的一般形式的方程其實比較複雜，稱為Weierstrass方程，形如下面的形式：
圖片
我們先將a,b,c,d,e 隨意的取值為1,2,3,4,5，並通過畫圖來查看曲線在直角坐標系上的表現形式。根據二次方程求根公式（假設求根公式可用），我們將其變換為x關於y的函數:
圖片
根據方程作圖如下：
圖片
根據上面的方程（1）和作圖過程了解道，曲線由上下兩個半支組成，關於y=0.5對稱。對稱的總是美的，但是這個曲線卻有一點瑕疵，他的對稱軸並不是x 軸而是y=0.5。考慮到Weierstrass太過複雜，人們更經常使用的是在Weierstrass方程的基礎上進行一些坐標變換（平移和縮放）和參數化簡後的形式。新的形式關於x 軸對稱。
圖片
當取a=0，b=3時，畫出曲線如下圖，容易驗證（1，2）是曲線上一點，對稱的（1，-2）也是。
圖片通過方程我們畫出了曲線y^2=x^3+3 的圖像，但是說這就是橢圓曲線的圖像其實並不准確。準確地說，我們畫的是在實數域上這個方程的圖像。在復數域上當然有更多的點也滿足曲線方程但是我們的圖像中並沒有體現，例如（-2，√5i）。如果把曲線看作點的集合，那數域的擴張直接影響到我們要討論的這個集合的大小，這在本文後半部分我們還會看到。另外為了讓其擁有更多的性質，我們認為橢圓曲線其實還包括一個“無窮遠”點。這個點在圖中並不能體現出來，我們也不能以直角坐標的形式寫出這個點的坐標，但是當我們說橢圓曲線時默認其點的集合中包含這個點。 “無窮遠點”一般用” O “表示。
橢圓曲線相關知識—點的運算
就像討論“ F_7 ”時那樣，有了元素的集合還需要有在集合上的運算。這條曲線就是橢圓曲線點的集合，但是為了構建密碼算法還需要定義點的運算。不同於域中需要兩種基本運算，這裡我們只需要定義一種特殊的基本運算就可以，不妨將這種運算稱作加法，用“+” 表示。通過幾何意義可以清楚的理解這種運算的定義，例如我們選取了曲線上的兩個點A和B計算加法，把A+B的結果記為C，過程如下：1）過AB做直線，交曲線於T；2）過T做x軸垂線，交曲線於C點，C即為所求；
圖片
需要說明的是，當兩個“加數”位置的點為同一個點時，步驟一中所做的其實是過該點的切線。另外，當AB的連線本身就垂直於x軸時，我們規定AB和曲線的第三個交點是無窮遠點“O”。在這樣的規則下容易發現，任何點P 都有一個對應的P’ ,使得P+P’=O ；並且任何點A 和O 的運算的結果都是A 本身。而且因為連線AB和連線BA其實是同一條直線，因此我們也能夠得知這裡定義的點的加法是滿足交換率的。根據定義再結合一些解析幾何的知識，就可以求出點加法的坐標計算公式。例如假設A 和B 的坐標分別為(Xa,Yb) 和(Xa,Yb) ,那麼C 點坐標如下：
圖片
其中” λ ” 是直線AB 連線的斜率，或者當A、B 重合時是A 點的切線斜率。現在我們將轉而討論有限域上的橢圓曲線，其上的橢圓曲線表現為一些散佈的點。在有限域上A+B 雖然已經沒有明確的幾何意義，但是有同樣的計算公式。我們已經驗證過（1，2）是橢圓曲線上的點，那麼我們就把該點記為G ，並且從該點開始，計算G, G+G，G+G+G… 看看會有怎樣的規律。以G+G為例，我們進行演算,首先計算λ ，也就是G點的斜率：
圖片
然後計算C點坐標：
圖片
因此G+G 的坐標為（68，74）。而G+2G 稍稍有不同，主要是λ需要從切線斜率修改為過AB 的直線斜率：
圖片
因此我們也計算出G+2G=3G 的坐標（26，45），以此類推進行計算，我們得到下表：
圖片
讀者可以選擇表中的點，例如(32,42) ，來驗證其是否在曲線上，也就是是否滿足曲線方程y^2=x^3+3 mod 101，相關演算我們不在本文贅述。經過計算和驗證可以發現，這一系列點構成了一個週期為17的循環。如果我們將k 個G 相加記為kG，並且將O 看作0G ，那麼有17 G= O。這像極了模17加法的規律，並且在模17加法和為0的兩個數對應的兩個橢圓曲線點的和正好是O ，我們說這樣的17個點和加法一起構成一個有17個元素的循環群。因為這只是一篇科普性質的文章，我們不給出循環群的嚴格定義，但是正如它的名字中強調的“循環”，循環群最突出的性質就是能夠由某個元素不斷運算從而得到全部。
需要強調的是這17個點並不是F_101 上橢圓曲線的全部，但僅利用這17個元素組成的集合我們已經能夠在其中完成點的加法運算，也就是說任意選擇集合中兩個點進行加法，其結果不會跳出到集合之外。在本篇最後，我們展示17個點在直角坐標系中的分佈（無法展現O ），讀者可以體會其中的對稱之美。下一篇我們將找到另一個17個元素的循環群並且在其基礎上計算雙線性映射，敬請期待。
圖片
附錄
圖片
▲表2：模101元素逆元表
作者：喬沛楊趣鏈科技基礎平台區塊鏈底層密碼學小組
展開全文打開碳鏈價值APP 查看更多精彩資訊
