橢圓曲線加密c
非對稱加密需要兩個密鑰：公鑰(publickey) 和私鑰 (privatekey)。公鑰和私鑰是一對，如果用公鑰對數據加密，那麼只能用對應的私鑰解密。如果用私鑰對數據加密，只能用對應的公鑰進行解密。因為加密和解密用的是不同的密鑰，所以稱為非對稱加密。
非對稱加密演算法的保密性好，它消除了最終用戶交換密鑰的需要。但是加解密速度要遠遠慢於對稱加密，在某些極端情況下，甚至能比對稱加密慢上1000倍。
演算法強度復雜、安全性依賴於演算法與密鑰但是由於其演算法復雜，而使得加密解密速度沒有對稱加密解密的速度快。對稱密碼體制中只有一種密鑰，並且是非公開的，如果要解密就得讓對方知道密鑰。所以保證其安全性就是保證密鑰的安全，而非對稱密鑰體制有兩種密鑰，其中一個是公開的，這樣就可以不需要像對稱密碼那樣傳輸對方的密鑰了。這樣安全性就大了很多。
RSA、Elgamal、背包演算法、Rabin、D-H、ECC (橢圓曲線加密演算法)。使用最廣泛的是 RSA 演算法，Elgamal 是另一種常用的非對稱加密演算法。
收信者是唯一能夠解開加密信息的人，因此收信者手裡的必須是私鑰。發信者手裡的是公鑰，其它人知道公鑰沒有關系，因為其它人發來的信息對收信者沒有意義。
客戶端需要將認證標識傳送給伺服器，此認證標識 (可能是一個隨機數) 其它客戶端可以知道，因此需要用私鑰加密，客戶端保存的是私鑰。伺服器端保存的是公鑰，其它伺服器知道公鑰沒有關系，因為客戶端不需要登錄其它伺服器。
數字簽名是為了表明信息沒有受到偽造，確實是信息擁有者發出來的，附在信息原文的後面。就像手寫的簽名一樣，具有不可抵賴性和簡潔性。
簡潔性：對信息原文做哈希運算，得到消息摘要，信息越短加密的耗時越少。
不可抵賴性：信息擁有者要保證簽名的唯一性，必須是唯一能夠加密消息摘要的人，因此必須用私鑰加密 (就像字跡他人無法學會一樣)，得到簽名。如果用公鑰，那每個人都可以偽造簽名了。
問題起源：對1和3，發信者怎麼知道從網上獲取的公鑰就是真的？沒有遭受中間人攻擊？
這樣就需要第三方機構來保證公鑰的合法性，這個第三方機構就是 CA (Certificate Authority)，證書中心。
CA 用自己的私鑰對信息原文所有者發布的公鑰和相關信息進行加密，得出的內容就是數字證書。
信息原文的所有者以後發布信息時，除了帶上自己的簽名，還帶上數字證書，就可以保證信息不被篡改了。信息的接收者先用 CA給的公鑰解出信息所有者的公鑰，這樣可以保證信息所有者的公鑰是真正的公鑰，然後就能通過該公鑰證明數字簽名是否真實了。
RSA 是目前最有影響力的公鑰加密演算法，該演算法基於一個十分簡單的數論事實：將兩個大素數相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，即公鑰，而兩個大素數組合成私鑰。公鑰是可發布的供任何人使用，私鑰則為自己所有，供解密之用。
A 要把信息發給 B 為例，確定角色：A 為加密者，B 為解密者。首先由 B 隨機確定一個 KEY，稱之為私鑰，將這個 KEY 始終保存在機器 B 中而不發出來；然後，由這個 KEY 計算出另一個 KEY，稱之為公鑰。這個公鑰的特性是幾乎不可能通過它自身計算出生成它的私鑰。接下來通過網路把這個公鑰傳給 A，A 收到公鑰後，利用公鑰對信息加密，並把密文通過網路發送到 B，最後 B 利用已知的私鑰，就能對密文進行解碼了。以上就是 RSA 演算法的工作流程。
由於進行的都是大數計算，使得 RSA 最快的情況也比 DES 慢上好幾倍，無論是軟體還是硬體實現。速度一直是 RSA 的缺陷。一般來說只用於少量數據加密。RSA 的速度是對應同樣安全級別的對稱密碼演算法的1/1000左右。
比起 DES 和其它對稱演算法來說，RSA 要慢得多。實際上一般使用一種對稱演算法來加密信息，然後用 RSA 來加密比較短的公鑰，然後將用 RSA 加密的公鑰和用對稱演算法加密的消息發送給接收方。
這樣一來對隨機數的要求就更高了，尤其對產生對稱密碼的要求非常高，否則的話可以越過 RSA 來直接攻擊對稱密碼。
和其它加密過程一樣，對 RSA 來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設 A 交給 B 一個公鑰，並使 B 相信這是A 的公鑰，並且 C 可以截下 A 和 B 之間的信息傳遞，那麼 C 可以將自己的公鑰傳給 B，B 以為這是 A 的公鑰。C 可以將所有 B 傳遞給 A 的消息截下來，將這個消息用自己的密鑰解密，讀這個消息，然後將這個消息再用 A 的公鑰加密後傳給 A。理論上 A 和 B 都不會發現 C 在偷聽它們的消息，今天人們一般用數字認證來防止這樣的攻擊。
(1) 針對 RSA 最流行的攻擊一般是基於大數因數分解。1999年，RSA-155 (512 bits) 被成功分解，花了五個月時間（約8000 MIPS 年）和224 CPU hours 在一台有3.2G 中央內存的 Cray C916計算機上完成。
RSA-158 表示如下：
2009年12月12日，編號為 RSA-768 (768 bits, 232 digits) 數也被成功分解。這一事件威脅了現通行的1024-bit 密鑰的安全性，普遍認為用戶應盡快升級到2048-bit 或以上。
RSA-768表示如下：
(2) 秀爾演算法
量子計算里的秀爾演算法能使窮舉的效率大大的提高。由於 RSA 演算法是基於大數分解 (無法抵抗窮舉攻擊)，因此在未來量子計算能對 RSA 演算法構成較大的威脅。一個擁有 N 量子位的量子計算機，每次可進行2^N 次運算，理論上講，密鑰為1024位長的 RSA 演算法，用一台512量子比特位的量子計算機在1秒內即可破解。
DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 簽名演算法的變種，被美國 NIST 作為 DSS (DigitalSignature Standard)。 DSA 是基於整數有限域離散對數難題的。
簡單的說，這是一種更高級的驗證方式，用作數字簽名。不單單只有公鑰、私鑰，還有數字簽名。私鑰加密生成數字簽名，公鑰驗證數據及簽名，如果數據和簽名不匹配則認為驗證失敗。數字簽名的作用就是校驗數據在傳輸過程中不被修改，數字簽名，是單向加密的升級。
橢圓加密演算法（ECC）是一種公鑰加密演算法，最初由 Koblitz 和 Miller 兩人於1985年提出，其數學基礎是利用橢圓曲線上的有理點構成 Abel 加法群上橢圓離散對數的計算困難性。公鑰密碼體制根據其所依據的難題一般分為三類：大整數分解問題類、離散對數問題類、橢圓曲線類。有時也把橢圓曲線類歸為離散對數類。
ECC 的主要優勢是在某些情況下它比其他的方法使用更小的密鑰 (比如 RSA)，提供相當的或更高等級的安全。ECC 的另一個優勢是可以定義群之間的雙線性映射，基於 Weil 對或是 Tate 對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。不過一個缺點是加密和解密操作的實現比其他機制花費的時間長。
ECC 被廣泛認為是在給定密鑰長度的情況下，最強大的非對稱演算法，因此在對帶寬要求十分緊的連接中會十分有用。
比特幣錢包公鑰的生成使用了橢圓曲線演算法，通過橢圓曲線乘法可以從私鑰計算得到公鑰， 這是不可逆轉的過程。
https://github.com/esxgx/easy-ecc
Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 演算法。
https://www.jianshu.com/p/58c1750c6f22
DH，全稱為"Diffie-Hellman"，它是一種確保共享 KEY 安全穿越不安全網路的方法，也就是常說的密鑰一致協議。由公開密鑰密碼體制的奠基人 Diffie 和 Hellman 所提出的一種思想。簡單的說就是允許兩名用戶在公開媒體上交換信息以生成"一致"的、可以共享的密鑰。也就是由甲方產出一對密鑰 (公鑰、私鑰)，乙方依照甲方公鑰產生乙方密鑰對 (公鑰、私鑰)。
以此為基線，作為數據傳輸保密基礎，同時雙方使用同一種對稱加密演算法構建本地密鑰 (SecretKey) 對數據加密。這樣，在互通了本地密鑰 (SecretKey) 演算法後，甲乙雙方公開自己的公鑰，使用對方的公鑰和剛才產生的私鑰加密數據，同時可以使用對方的公鑰和自己的私鑰對數據解密。不單單是甲乙雙方兩方，可以擴展為多方共享數據通訊，這樣就完成了網路交互數據的安全通訊。
具體例子可以移步到這篇文章： 非對稱密碼之DH密鑰交換演算法
參考：
https://blog.csdn.net/u014294681/article/details/86705999
https://www.cnblogs.com/wangzxblog/p/13667634.html
https://www.cnblogs.com/taoxw/p/15837729.html
https://www.cnblogs.com/fangfan/p/4086662.html
https://www.cnblogs.com/utank/p/7877761.html
https://blog.csdn.net/m0_59133441/article/details/122686815
https://www.cnblogs.com/muliu/p/10875633.html
https://www.cnblogs.com/wf-zhang/p/14923279.html
https://www.jianshu.com/p/7a927db713e4
https://blog.csdn.net/ljx1400052550/article/details/79587133
https://blog.csdn.net/yuanjian0814/article/details/109815473
❷ ECC 演算法簡介
與 RSA（Ron Rivest，Adi Shamir，Len Adleman 三位天才的名字）一樣，ECC（Elliptic Curves Cryptography，橢圓曲線加密）也屬於公開密鑰演算法。
一、從平行線談起
平行線，永不相交。沒有人懷疑把：）不過到了近代這個結論遭到了質疑。平行線會不會在很遠很遠的地方相交了？事實上沒有人見到過。所以「平行線，永不相交」只是假設（大家想想初中學習的平行公理，是沒有證明的）。
既然可以假設平行線永不相交，也可以假設平行線在很遠很遠的地方相交了。即平行線相交於無窮遠點P∞（請大家閉上眼睛，想像一下那個無窮遠點P∞，P∞是不是很虛幻，其實與其說數學鍛煉人的抽象能力，還不如說是鍛煉人的想像力）。
給個圖幫助理解一下：
直線上出現P∞點，所帶來的好處是所有的直線都相交了，且只有一個交點。這就把直線的平行與相交統一了。為與無窮遠點相區別把原來平面上的點叫做平常點。
以下是無窮遠點的幾個性質。
直線 L 上的無窮遠點只能有一個。（從定義可直接得出）
平面上一組相互平行的直線有公共的無窮遠點。（從定義可直接得出）
平面上任何相交的兩直線 L1、L2 有不同的無窮遠點。（否則 L1 和 L2 有公共的無窮遠點 P ，則 L1 和 L2 有兩個交點 A、P，故假設錯誤。）
平面上全體無窮遠點構成一條無窮遠直線。（自己想像一下這條直線吧）
平面上全體無窮遠點與全體平常點構成射影平面。
二、射影平面坐標系
射影平面坐標系是對普通平面直角坐標系（就是我們初中學到的那個笛卡兒平面直角坐標系）的擴展。我們知道普通平面直角坐標系沒有為無窮遠點設計坐標，不能表示無窮遠點。為了表示無窮遠點，產生了射影平面坐標系，當然射影平面坐標系同樣能很好的表示舊有的平常點（數學也是「向下兼容」的）。
我們對普通平面直角坐標繫上的點A的坐標（x, y）做如下改造：
令 x=X/Z ，y=Y/Z（Z≠0）；則 A 點可以表示為（X:Y:Z）。
變成了有三個參量的坐標點，這就對平面上的點建立了一個新的坐標體系。
例 2.1：求點（1,2）在新的坐標體系下的坐標。
解：
∵X/Z=1 ，Y/Z=2（Z≠0）
∴X=Z，Y=2Z
∴坐標為（Z:2Z:Z），Z≠0。
即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0 的坐標，都是（1,2）在新的坐標體系下的坐標。
我們也可以得到直線的方程 aX+bY+cZ=0（想想為什麼？提示：普通平面直角坐標系下直線一般方程是 ax+by+c=0）。
新的坐標體系能夠表示無窮遠點么？那要讓我們先想想無窮遠點在哪裡。根據上一節的知識，我們知道無窮遠點是兩條平行直線的交點。那麼，如何求兩條直線的交點坐標？這是初中的知識，就是將兩條直線對應的方程聯立求解。
平行直線的方程是：
aX+bY+c1Z =0；
aX+bY+c2Z =0 (c1≠c2)； （為什麼？提示：可以從斜率考慮，因為平行線斜率相同）；
將二方程聯立，求解。有
c2Z= c1Z= -（aX+bY）
∵c1≠c2
∴Z=0
∴aX+bY=0
所以無窮遠點就是這種形式（X：Y：0）表示。注意，平常點 Z≠0，無窮遠點 Z=0，因此無窮遠直線對應的方程是 Z=0。
例 2.2：求平行線 L1：X+2Y+3Z=0 與 L2：X+2Y+Z=0 相交的無窮遠點。
解：
因為 L1∥L2
所以有 Z=0， X+2Y=0
所以坐標為（-2Y:Y:0），Y≠0。
即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0 的坐標，都表示這個無窮遠點。
看來這個新的坐標體系能夠表示射影平面上所有的點，我們就把這個能夠表示射影平面上所有點的坐標體系叫做射影平面坐標系。
練習：
1、求點A(2,4) 在射影平面坐標系下的坐標。
2、求射影平面坐標系下點(4.5:3:0.5)，在普通平面直角坐標系下的坐標。
3、求直線X+Y+Z=0上無窮遠點的坐標。
4、判斷：直線aX+bY+cZ=0上的無窮遠點 和 無窮遠直線與直線aX+bY=0的交點，是否是同一個點？
三、橢圓曲線
上一節，我們建立了射影平面坐標系，這一節我們將在這個坐標系下建立橢圓曲線方程。因為我們知道，坐標中的曲線是可以用方程來表示的（比如：單位圓方程是 x2+y2=1）。橢圓曲線是曲線，自然橢圓曲線也有方程。
橢圓曲線的定義：
一條橢圓曲線是在射影平面上滿足如下方程的所有點的集合，且曲線上的每個點都是非奇異（或光滑）的。
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3 [3-1]
定義詳解：
Y2Z+a1XYZ+a3YZ2 = X3+a2X2Z+a4XZ2+a6Z3 是 Weierstrass 方程（維爾斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是一個齊次方程。
橢圓曲線的形狀，並不是橢圓的。只是因為橢圓曲線的描述方程，類似於計算一個橢圓周長的方程（計算橢圓周長的方程，我沒有見過，而對橢圓線 積分 （設密度為1）是求不出來的），故得名。
我們來看看橢圓曲線是什麼樣的。
所謂「非奇異」或「光滑」的，在數學中是指曲線上任意一點的偏導數 Fx(x,y,z)，Fy(x,y,z)，Fz(x,y,z) 不能同時為0。如果你沒有學過高等數學，可以這樣理解這個詞，即滿足方程的任意一點都存在切線。下面兩個方程都不是橢圓曲線，盡管他們是方程 [3-1] 的形式，因為他們在（0:0:1）點處（即原點）沒有切線。
橢圓曲線上有一個無窮遠點O∞（0:1:0），因為這個點滿足方程[3-1]。
知道了橢圓曲線上的無窮遠點。我們就可以把橢圓曲線放到普通平面直角坐標繫上了。因為普通平面直角坐標系只比射影平面坐標系少無窮遠點。我們在普通平面直角坐標繫上，求出橢圓曲線上所有平常點組成的曲線方程，再加上無窮遠點O∞（0:1:0），不就構成橢圓曲線了么？
我們設 x=X/Z，y=Y/Z 代入方程 [3-1] 得到：
y2+a1xy+a3y = x3+a2x2+a4x+a6 [3-2]
也就是說滿足方程 [3-2] 的光滑曲線加上一個無窮遠點O∞，組成了橢圓曲線。為了方便運算，表述，以及理解，今後論述橢圓曲線將主要使用 [3-2] 的形式。
本節的最後，我們談一下求橢圓曲線一點的切線斜率問題。由橢圓曲線的定義可以知道，橢圓曲線是光滑的，所以橢圓曲線上的平常點都有切線。而切線最重要的一個參數就是斜率 k 。
例 3.1：求橢圓曲線方程 y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常點 A(x,y) 的切線的斜率 k 。
解：
令
F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6
求偏導數
Fx(x,y)= a1y-3x2-2a2x-a4
Fy(x,y)= 2y+a1x+a3
則導數為：
f'(x)=- Fx(x,y)/ Fy(x,y)=-( a1y-3x2-2a2x-a4)/(2y+a1x +a3) = (3x2+2a2x+a4-a1y) /(2y+a1x +a3)
所以
k=(3x2+2a2x+a4-a1y) /(2y+a1x +a3) [3-3]
看不懂解題過程沒有關系，記住結論[3-3]就可以了。
練習：
1、將給出圖例的橢圓曲線方程Y2Z=X3-XZ2 和Y2Z=X3+XZ2+Z3轉換成普通平面直角坐標繫上的方程。
四、橢圓曲線上的加法
上一節，我們已經看到了橢圓曲線的圖象，但點與點之間好象沒有什麼聯系。我們能不能建立一個類似於在實數軸上加法的運演算法則呢？天才的數學家找到了這一運演算法則
自從近世紀代數學引入了群、環、域的概念，使得代數運算達到了高度的統一。比如數學家總結了普通加法的主要特徵，提出了加群（也叫交換群，或 Abel（阿貝爾）群），在加群的眼中。實數的加法和橢圓曲線的上的加法沒有什麼區別。這也許就是數學抽象把。關於群以及加群的具體概念請參考近世代數方面的數學書。
運演算法則：任意取橢圓曲線上兩點 P、Q （若 P、Q兩點重合，則做 P 點的切線）做直線交於橢圓曲線的另一點 R』，過 R』 做 y 軸的平行線交於 R。我們規定 P+Q=R。（如圖）
法則詳解：
這里的 + 不是實數中普通的加法，而是從普通加法中抽象出來的加法，他具備普通加法的一些性質，但具體的運演算法則顯然與普通加法不同。
根據這個法則，可以知道橢圓曲線無窮遠點 O∞ 與橢圓曲線上一點 P 的連線交於 P』，過 P』 作 y 軸的平行線交於 P，所以有 無窮遠點 O∞ + P = P 。這樣，無窮遠點 O∞ 的作用與普通加法中零的作用相當（0+2=2），我們把無窮遠點 O∞ 稱為零元。同時我們把 P』 稱為 P 的負元（簡稱，負P；記作，-P）。（參見下圖）
根據這個法則，可以得到如下結論 ：如果橢圓曲線上的三個點 A、B、C，處於同一條直線上，那麼他們的和等於零元，即 A+B+C= O∞
k 個相同的點 P 相加，我們記作 kP。如下圖：P+P+P = 2P+P = 3P。
下面，我們利用 P、Q點的坐標 (x1,y1)，(x2,y2)，求出 R=P+Q 的坐標 (x4,y4)。
例 4.1：求橢圓曲線方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 上，平常點 P(x1,y1)，Q(x2,y2) 的和 R(x4,y4) 的坐標。
解：
（1）先求點 -R(x3,y3)
因為 P, Q, -R 三點共線，故設共線方程為
y=kx+b
其中，若 P≠Q (P,Q兩點不重合)，則直線斜率
k=(y1-y2)/(x1-x2)
若 P=Q (P,Q兩點重合)，則直線為橢圓曲線的切線，
故由例 3.1 可知：
k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3)
因此 P, Q, -R 三點的坐標值就是以下方程組的解：
y2+a1xy+a3y=x3+a2x2+a4x+a6 [1]
y=(kx+b) [2]
將 [2] 代入[1] 有
(kx+b)2+a1x(kx+b)+a3(kx+b) =x3+a2x2+a4x+a6 [3]
對 [3] 化為一般方程，根據三次方程根與系數關系（若方程x³＋ax²＋bx＋c=0 的三個根是 x1、x2、x3，則： x1＋x2＋x3=－a，x1x2＋x2x3＋x3x1=b，x1x2x2=－c）
所以
-(x1+x2+x3)=a2-ka1-k2
x3=k2+ka1+a2+x1+x2 --------------------- 求出點 -R 的橫坐標
因為
k=(y1-y3)/(x1-x3)
故
y3=y1-k(x1-x3) ------------------------------ 求出點 -R 的縱坐標
（2）利用 -R 求 R
顯然有
x4=x3=k2+ka1+a2+x1+x2 -------------- 求出點 R 的橫坐標
而 y3 y4 為 x=x4 時 方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 的解化為一般方程 y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根據二次方程根與系數關系（如果方程 ax²＋bx＋c=0 的兩根為 x1、x2，那麼 x1+x2=-b/a，x1x2=c/a）
得：
-(a1x+a3)=y3+y4
故
y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3) ----- 求出點 R 的縱坐標
即：
x4=k2+ka1+a2+x1+x2
y4=k(x1-x4)-y1-a1x4-a3
本節的最後，提醒大家注意一點，以前提供的圖像可能會給大家產生一種錯覺，即橢圓曲線是關於 x 軸對稱的。事實上，橢圓曲線並不一定關於 x 軸對稱。如下圖的 y2-xy=x3+1
五、密碼學中的橢圓曲線
我們現在基本上對橢圓曲線有了初步的認識，這是值得高興的。但請大家注意，前面學到的橢圓曲線是連續的，並不適合用於加密。所以，我們必須把橢圓曲線變成離散的點。
讓我們想一想，為什麼橢圓曲線為什麼連續？是因為橢圓曲線上點的坐標，是實數的（也就是說前面講到的橢圓曲線是定義在實數域上的），實數是連續的，導致了曲線的連續。因此，我們要把橢圓曲線定義在有限域上（顧名思義，有限域是一種只有由有限個元素組成的域）。
域的概念是從我們的有理數，實數的運算中抽象出來的，嚴格的定義請參考近世代數方面的數。簡單的說，域中的元素同有理數一樣，有自己得加法、乘法、除法、單位元(1)，零元(0),並滿足交換率、分配率。
下面，我們給出一個有限域 Fp，這個域只有有限個元素。
Fp 中只有 p（p為素數）個元素 0, 1, 2 …… p-2, p-1
Fp 的加法（a+b）法則是 a+b≡c (mod p) ，即 (a+c)÷p 的余數和 c÷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 也是一個 0 到 p-1 之間的整數，但滿足 b×b-1≡1 (mod p)；具體求法可以參考初等數論。
Fp 的單位元是 1，零元是 0。
同時，並不是所有的橢圓曲線都適合加密。y2=x3+ax+b是一類可以用來加密的橢圓曲線，也是最為簡單的一類。下面我們就把 y2=x3+ax+b 這條曲線定義在 Fp 上：
選擇兩個滿足下列條件的小於 p ( p 為素數) 的非負整數 a、b
4a3+27b2≠0 (mod p)
則滿足下列方程的所有點 (x,y)，再加上 無窮遠點 O∞ ，構成一條橢圓曲線。
y2=x3+ax+b (mod p)
其中 x,y 屬於 0 到 p-1 間的整數，並將這條橢圓曲線記為 Ep(a,b)。
我們看一下 y2=x3+x+1 (mod 23) 的圖像
是不是覺得不可思議？橢圓曲線，怎麼變成了這般模樣，成了一個一個離散的點？橢圓曲線在不同的數域中會呈現出不同的樣子，但其本質仍是一條橢圓曲線。舉一個不太恰當的例子，好比是水，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一網路，水又變成了水蒸氣。但其本質仍是 H2O。
Fp上的橢圓曲線同樣有加法，但已經不能給以幾何意義的解釋。不過，加法法則和實數域上的差不多，請讀者自行對比。
1. 無窮遠點 O∞ 是零元，有 O∞ + O∞ = O∞，O∞ + P = P
2. P(x,y) 的負元是 (x,-y)，有 P + (-P) = O∞
3. P(x1,y1), Q(x2,y2) 的和 R(x3,y3) 有如下關系：
x3≡k2-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)
其中
若 P=Q 則 k=(3x2+a)/2y1
若 P≠Q 則 k=(y2-y1)/(x2-x1)
例 5.1：已知 E23(1,1) 上兩點 P(3,10)，Q(9,7)，求 (1)-P，(2)P+Q，(3) 2P。
解：
(1) –P的值為(3,-10)
(2) k=(7-10)/(9-3)=-1/2
2 的乘法逆元為 12， 因為 2*12≡1 (mod 23)
k≡-1*12 (mod 23)
故 k=11
x=112-3-9=109≡17 (mod 23)
y=11[3-(-6)]-10=89≡20 (mod 23)
故 P+Q 的坐標為 (17,20)
3) k=[3(32)+1]/(2*10)=1/4≡6 (mod 23)
x=62-3-3=30≡20 (mod 23)
y=6(3-7)-10=-34≡12 (mod 23)
故 2P 的坐標為 (7,12)
最後，我們講一下橢圓曲線上的點的階。如果橢圓曲線上一點 P，存在最小的正整數 n，使得數乘 nP=O∞，則將 n 稱為 P 的階，若 n 不存在，我們說 P 是無限階的。 事實上，在有限域上定義的橢圓曲線上所有的點的階 n 都是存在的（證明，請參考近世代數方面的書）
練習：
1． 求出 E11(1,6) 上所有的點。
2．已知 E11(1,6) 上一點 G(2,7)，求 2G 到 13G 所有的值。
六、橢圓曲線上簡單的加密/解密
公開密鑰演算法總是要基於一個數學上的難題。比如 RSA 依據的是：給定兩個素數 p、q 很容易相乘得到 n，而對 n 進行因式分解卻相對困難。那橢圓曲線上有什麼難題呢？
考慮如下等式：
K=kG [其中 K, G為 Ep(a,b) 上的點，k 為小於 n（n 是點 G 的階）的整數]
不難發現，給定 k 和 G，根據加法法則，計算 K 很容易；但給定 K 和 G，求 k 就相對困難了。這就是橢圓曲線加密演算法採用的難題。我們把點 G 稱為基點（base point），k（key point）就是私有密鑰。
現在我們描述一個利用橢圓曲線進行加密通信的過程：
1、用戶 A 選定一條橢圓曲線 Ep(a,b)，並取橢圓曲線上一點，作為基點 G。
2、用戶 A 選擇一個私有密鑰 k，並生成公開密鑰 K=kG。
3、用戶 A 將 Ep(a,b) 和點 K，G 傳給用戶 B。
4、用戶 B 接到信息後，將待傳輸的明文編碼到 Ep(a,b) 上一點 M（編碼方法很多，這里不作討論），並產生一個隨機整數 r（random）。
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 進行解碼就可以得到明文。
在這個加密通信中，如果有一個偷窺者 H ，他只能看到 Ep(a,b)、K、G、C1、C2 而通過 K、G 求 k 或通過 C2、G 求 r 都是相對困難的。因此，H 無法得到 A、B 間傳送的明文信息。
密碼學中，描述一條 Fp 上的橢圓曲線，常用到六個參量：
T=(p,a,b,G,n,h)
p 、a 、b 用來確定一條橢圓曲線，G 為基點，n 為點 G 的階，h 是橢圓曲線上所有點的個數 m 與 n 相除的整數部分。這幾個參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：
1、p 當然越大越安全，但越大，計算速度會變慢，200 位左右可以滿足一般安全要求；
2、p≠n×h；
3、pt≠1 (mod n)，1≤t<20；
4、4a3+27b2≠0 (mod p)；
5、n 為素數；
6、h≤4。
七、橢圓曲線簽名在軟體保護的應用
我們知道將公開密鑰演算法作為軟體注冊演算法的好處是：黑客很難通過跟蹤驗證演算法得到注冊機。下面，將簡介一種利用 Fp(a,b) 橢圓曲線進行軟體注冊的方法。
軟體作者按如下方法製作注冊機（也可稱為簽名過程）
1、選擇一條橢圓曲線 Ep(a,b) 和基點 G；
2、選擇私有密鑰 k；
3、產生一個隨機整數 r ；
4、將用戶名和點 R 的坐標值 x,y 作為參數，計算 SHA（Secure Hash Algorithm 安全散列演算法，類似於 MD5）值，即 Hash=SHA(username,x,y)；
5、計算 sn≡r - Hash * k (mod n)
6、將 sn 和 Hash 作為用戶名 username 的序列號
軟體驗證過程如下：（軟體中存有橢圓曲線 Ep(a,b) 和基點 G 以及公開密鑰 K）
1、從用戶輸入的序列號中，提取 sn 以及 Hash；
2、計算點 R≡sn*G+Hash*K ( mod p )，如果 sn、Hash 正確，其值等於軟體作者簽名過程中點 R(x,y) 的坐標，
因為 sn≡r-Hash*k （mod n）
所以 sn*G+Hash*K=(r-Hash*k)*G+Hash*K=rG-Hash*kG+Hash*K=rG-Hash*K+Hash*K=rG=R；
3、將用戶名和點 R 的坐標值 x,y 作為參數，計算 H=SHA(username,x,y)；
4、如果 H=Hash 則注冊成功，如果 H≠Hash ，則注冊失敗（為什麼？提示注意點 R 與 Hash 的關聯性）。
簡單對比一下兩個過程：
作者簽名用到了：橢圓曲線 Ep(a,b)，基點 G，私有密鑰 k，及隨機數 r。
軟體驗證用到了：橢圓曲線 Ep(a,b)，基點 G，公開密鑰 K。
黑客要想製作注冊機，只能通過軟體中的 Ep(a,b)，點 G，公開密鑰 K ，並利用 K=kG 這個關系獲得 k 才可以，而求 k 是很困難的。
練習：
下面也是一種常於軟體保護的注冊演算法，請認真閱讀，並試回答簽名過程與驗證過程都用到了那些參數，黑客想製作注冊機，應該如何做。
軟體作者按如下方法製作注冊機（也可稱為簽名過程）
1、選擇一條橢圓曲線 Ep(a,b)，和基點 G；
2、選擇私有密鑰 k；
3、產生一個隨機整數 r；
4、將用戶名作為參數，計算 Hash=SHA(username)；
5、計算 x』=x (mod n)
6、計算 sn≡(Hash+x』*k)/r (mod n)
7、將 sn 和 x』 作為用戶名 username 的序列號
軟體驗證過程如下：(軟體中存有橢圓曲線 Ep(a,b) 和基點 G 以及公開密鑰 K)
1、從用戶輸入的序列號中，提取 sn 以及 x』；
2、將用戶名作為參數，計算 Hash=SHA(username)；
3、計算 R=(Hash*G+x』*K)/sn，如果 sn、Hash 正確，其值等於軟體作者簽名過程中點 R(x,y)
因為 sn≡(Hash+x』*k)/r (mod n)
所以 (Hash*G+x』*K)/sn=(Hash*G+x』*K)/[(Hash+x』*k)/r]=(Hash*G+x』*K)/[(Hash*G+x』*k*G)/(rG)]=rG*[(Hash*G+x』*K)/(Hash*G+x』*K)]=rG=R (mod p)
4、v≡x (mod n)
5、如果 v=x』 則注冊成功。如果 v≠x』 ，則注冊失敗。
主要參考文獻
張禾瑞，《近世代數基礎》，高等 教育 出版社，1978
閔嗣鶴 嚴士健，《初等數論》，高等教育出版社，1982
段雲所，《網路信息安全》第三講，北大計算機系
Michael Rosing ，chapter5《Implementing Elliptic Curve Cryptography》，Softbound，1998
《SEC 1: Elliptic Curve Cryptography》，Certicom Corp.，2000
《IEEE P1363a / D9》，2001
❸ ECC橢圓曲線加密演算法(一)
btc address:
eth address:
隨著區塊鏈的大熱，橢圓曲線演算法也成了密碼學的熱門話題。在Bitcoin 生成地址 中使用到了橢圓曲線加密演算法。
橢圓曲線的一般表現形式：
橢圓曲線其實不是橢圓形的，而是下面的圖形：
Bitcoin使用了 secp256k1 這條特殊的橢圓曲線，公式是：
這個東西怎麼加密的呢？
19世紀挪威青年 尼爾斯·阿貝爾 從普通的代數運算中，抽象出了加群（也叫阿貝爾群或交換群），使得在加群中，實數的演算法和橢圓曲線的演算法得到了統一。是什麼意思呢？
我們在實數中，使用的加減乘除，同樣可以用在橢圓曲線中！
對的，橢圓曲線也可以有加法、乘法運算。
數學中的群是一個集合，我們為它定義了一個二元運算，我們稱之為「加法」，並用符號 + 表示。假定我們要操作的群用𝔾表示，要定義的 加法 必須遵循以下四個特性：
如果在增加第5個條件：
交換律：a + b = b + a
那麼，稱這個群為阿貝爾群。根據這個定義整數集是個阿貝爾群。
岔開一下話題， 伽羅瓦 與 阿貝爾 分別獨立的提出了群論，他們並稱為現代群論的創始人，可惜兩位天才都是英年早逝。
如上文所說，我們可以基於橢圓曲線定義一個群。具體地說：
在橢圓曲線上有 不重合且不對稱的 A 、B兩點，兩點與曲線相交於X點, X與 x軸 的對稱點為R，R即為 A+B 的結果。這就是橢圓曲線的加法定義。
因為橢圓曲線方程存在 項，因此橢圓曲線必然關於x軸對稱
曲線： ，
坐標：A=(2,5)，B=(3,7)
A、B正好在曲線上，因為坐標滿足曲線公式
那如何找到相交的第三個點呢？
通過 A、B兩點確定直線方程，
設直線方程： ，m為直線的斜率
進一步得到c=1。
聯立方程：
X(-1,-1)的x坐標-1代入方式正好滿足方程，所以A、B兩點所在直線與曲線相交於 X(-1,-1)，則點X的關於x軸的對稱點為R(-1,1)，即A(2,5)+B(3,5)=R(-1,1)。
根據橢圓曲線的 群律(GROUP LAW) 公式，我們可以方便的計算R點。
曲線方程：
當A=(x1,y1)，B=(x2,y2) ，R=A+B=(x3,y3)，x1≠x2時,
， m是斜率
x3=
y3=m(x1-x3)-y1
A=(2,5), B=(3,7) , R=(-1,1) 符合上面的公式。
橢圓曲線加法符合交換律么？
先計算(A+B)，在計算 A+B+C
先計算B+C， 在計算 B+C+A
看圖像，計算結果相同，大家手動算下吧。
那 A + A 呢， 怎麼計算呢？
當兩點重合時候，無法畫出 「過兩點的直線」，在這種情況下，
過A點做橢圓曲線的切線，交於X點，X點關於 x軸 的對稱點即為 2A ，這樣的計算稱為 「橢圓曲線上的二倍運算」。
下圖即為橢圓曲線乘法運算：
我們將在 ECC橢圓曲線加密演算法(二) 介紹有限域，橢圓曲線的離散對數問題，橢圓曲線加密就是應用了離散對數問題。
參考：
https://eng.paxos.com/blockchain-101-foundational-math
https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introction/
❹ 橢圓曲線密碼學的一些具體的內容
⑴ 無窮遠元素（無窮遠點，無窮遠直線）
平面上任意兩相異直線的位置關系有相交和平行兩種。引入無窮遠點，是兩種不同關系統一。
AB⊥L1， L2∥L1，直線AP由AB起繞A點依逆時針方向轉動，P為AP與L1的交點。
Q=∠BAP→p /2 AP → L2
可設想L1上有一點P∞，它為L2和L1的交點，稱之為無窮遠點。
直線L1上的無窮遠點只能有一個。
（因為過A點只能有一條平行於L1的直線L2，而兩直線的交點只能有一個。）
結論：
1*. 平面上一組相互平行的直線，有公共的無窮遠點。
（為與無窮遠點相區別，把原來平面上的點叫做平常點）
2*.平面上任何相交的兩直線L1,L2有不同的無窮遠點。
原因：若否，則L1和L2有公共的無窮遠點P∞，則過兩相異點A和P ∞有相異兩直線，與公理相矛盾。
3*. 全體無窮遠點構成一條無窮遠直線。
註：歐式平面添加上無窮遠點和無窮遠直線，自然構成射影平面。
⑵ 齊次坐標
解析幾何中引入坐標系，用代數的方法研究歐氏空
間。這樣的坐標法也可推廣至攝影平面上，建立平面攝影
坐標系。
牋 L1,L2
L1: a1x+b1y+c1=0
L2: a2x+b2y+c2=0
其中a1,b1不同時為0；a2,b2也不同時為0。
設
D= a1 b1 Dx= b1 c1 Dy= c1 a1
a2 b2 b2 c2 c2 a2
若D≠0，則兩直線L1,L2相交於一平常點P(x,y），其坐標為x=Dx/D，y=Dy/D.
這組解可表為：x/Dx=y/Dy=1/D
（約定：分母Dx，Dy有為0時，對應的分子也要為0）
上述表示可抽象為（Dx，Dy，D).
若 D=0，則L1∥L2，此時L1和L2交於一個無窮遠點P∞。
這個點P∞可用過原點O且平行於L2的一條直線L來指出他
的方向，而這條直線L的方程就是：a2x+b2y=0.
為把平常點和無窮遠點的坐標統一起來，把點的坐標用
（X，Y，Z）表示，X，Y，Z不能同時為0，且對平常點
（x，y）來說，有Z≠0，x=X/Z，y=Y/Z，於是有：
i.e.
X / Dx = Y / Dy = Z / D，
有更好的坐標抽象，X,Y,Z），這樣對於無窮遠點則有Z=0，
也成立。
註：
a).若實數p≠0，則（pX,pY,pZ）與（X,Y,Z）表示同一個點。實質上用（X:Y:Z）表示。3個分量中，只有兩個是獨立的，</pre>
<pre>；具有這種特徵的坐標就叫齊次坐標。
b).設有歐氏直線L，它在平面直角坐標系Oxy上的方程為：
ax+by+c=0
則L上任一平常點（x,y）的齊次坐標為（X,Y,Z），Z≠0，代入得：
aX+bY+cZ=0
給L添加的無窮遠點的坐標（X,Y,Z）應滿足aX+bY=0，Z=0；平面上無窮遠直線方程自然為：Z=0 !!
⑶任意域上的橢圓曲線
K為域，K上的攝影平面P2(K）是一些等價類的集合{(X:Y:Z)}。考慮下面的Weierstrass方程（次數為3的齊次方程）：
Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3
（其中系數ai∈K，或ai∈K為K的代數閉域）
Weierstrass方程被稱為光滑的或非奇異的是指對所有適合
以下方程的射影點P=(X:Y:Z) ∈ P2(K）來說，
F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0
在P點的三個偏導數 之中至少有一個不為
0若否稱這個方程為奇異的。
橢圓曲線E的定義：
橢圓曲線E是一個光滑的Weierstrass方程在P2(K）中的
全部解集合。
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
註：
a) 在橢圓曲線E上恰有一個點，稱之為無窮遠點。即（0:1:0）用θ表示。
b) 可用非齊次坐標的形式來表示橢圓曲線的Weierstrass方程：
設 x=X/Z，y=Y/Z，於是原方程轉化為：
y2+a1xy+a3y=x3+a2x2+a4x+a6 ⑴
此時，橢圓曲線E就是方程⑴在射影平面P2(K）上的全部平常點解，外加一個無窮遠點θ組成的集合。
c) 若a1,a2,a2,a4,a6∈K，此時橢圓曲線E被稱為定義在K上，用E/K表示。如果E能被限定在K上，那麼E的K--</pre>
<pre>；有理點集合表示為E(K），它為E中的全體有理坐標點的集合外加無窮遠點θ.
⑷實域R上的橢圓曲線
設K=R，此時的橢圓曲線可表為平面上的通常曲線上
的點，外加無窮遠點θ。
實域R上橢圓曲線的點的加法運演算法則：
設L ∈ P2(R）為一條直線。因為E的方程是三次的，所以L可與E在P2(R）恰有三個交點，記為P,Q,R
（注意：如果L與E相切，那麼P,Q,R可以不是相異的）。按下述方式定義E上運算⊙：
設P,Q ∈ E，L為聯接P,Q的直線（若P=Q，則L取過P點的切線）；設R為L與E的另一個交點；
再取連接R與無窮遠點的直線L′。則L′與E的另一個交點定義為P ⊙Q。
上頁的實際圖像為橢圓曲線y2=x3 - x的一般化。來自對具體曲線的抽象。對運算更具體一些：
設 P=(x1,y1），Q=(x2,y2），P⊙Q=(x3,y3），
由P Q的定義，設y=αx+β為通過P,Q兩點直線L的方程，可算出：
α=(y2-y1）/(x2-x1），β=y1-αx1
易見，直線L上的一個點（x，αx+β）是在橢圓曲線E上，
當且僅當（αx+β）2= x3 - x。
P⊙Q=(x1,y1） (x2,y2）=(x3,y3） =(x3,-（αx3+β））
其中，x3= α2-x1-x2=((y2-y1） / (x2-x1））2-x1-x2；
y3=-y1+((y2-y1）/(x2-x1））（x1-x3）
當P=Q時：P⊙Q=（x3，y3）算得：
x3=（（3x12-1）/2y1）2-2x1; y3= -y1+（（3x12-1）/2y1）（x1-x3）
註：
a) 如果直線L與E相交與三點P,Q,R（不一定相異），那麼 (P⊙Q)R=θ（從圖中可見）。
b) 任給P∈E,P⊙θ =P （此時設Q= θ ，易見L=L′）
c) 任給P,Q∈E有：P⊙Q =Q⊙P
d) 設P∈E，那麼可以找到 - P∈E使P -P= θ
e) 任給P,Q,R∈E，有（P⊙Q）⊙R= P⊙（Q⊙R)
綜上所述，知E對 運算形成一個Abel群。
f) 上述規則可開拓到任意域上，特別是有限域上。假定
橢圓曲線是定義在有限域Fq上（q=pm），那麼
E(Fq)={(x,y）∈Fq×Fq | y2+a1xy+a3y=x3+a2x2+a4x+a6} ∪{θ}
它對? 斝緯梢桓鋈海?獮bel群。 令Fq表示q個元素的有限域，用E(Fq）表示定義在Fq上
的一個橢圓曲線E。
定理1.(Hass定理） E(Fq）的點數用#E(Fq）表示，則
| #E(Fq)-q-1|≤2q1/2
⑴ Fp（素域，p為素數）上橢圓曲線
牋 p>3 a,b Fp 4a3+27b2 0 a b
義的Fp上的一個橢圓曲線方程為：
y2=x3+ax+b ⑵
它的所有解（x,y），（x Fp，y Fp），連同一個稱為撐耷鈐?
點敚?俏?齲┑腦?刈槌傻募?霞俏狤（Fp），由Hass定理
知：p+1-2p1/2≤#E(Fp) ≤ p+1+2p1/2
集合E(Fp）對應下面的加法規則，且對加法 形成
一個Abel群：
（i) θ⊙ θ=θ （單位元素）
（ii) (x,y）⊙ θ=(x,y），任給（x,y) ∈E(Fp)
（iii) (x,y）⊙ (x,-y)=θ，任給（x,y) ∈E(Fp），即點（x,y）的逆元
為（x,-y).
（iv) 令（x1,y1），（x2,y2）為E(Fp）中非互逆元，則
（x1,y1）⊙ (x2,y2）=(x3,y3），其中
x3=α2-2x1，y3= α（x1-x3）-y1
且α=(y2-y1）/(x2-x1） ⑶
（v）（倍點運算規則）
設（x1,y1） ∈E(Fp),y1≠0，則2(x1,y1）=(x3,y3），其中
x3= α2-2x1,y3=α（x1-x3）-y1
這里α=（3x12+a)/（2y1） ⑷
註：若#E(Fp)=p+1，曲線E(Fp）稱為超奇異的，否則稱為
非超奇異的。
例子：F23上的一個橢圓曲線
令y2=x3+x+1是F23上的一個方程（a=b=1），則該橢圓曲
線方程在F23上的解為（y2=x3+x+1的點）：
（0,1），（0,22），（1,7），（1,16），（3,10），（3,13），（4,0），（5,4），（5,19），（6,4），</pre>
<pre>；（6,19），（7,11），（7,12），（9,7），（9,16），（11,3），（11,20），（12,4），（12,19），（13,7），</pre>
<pre>；（13,16），（17,3），（17,20），（18,3），（18,20），（19,5），（19,18）；θ。
群E(F23）有28個點（包括無窮遠點θ）。
2） F2m上的橢圓曲線
F2m上由參數a,b∈F2m，b≠0定義的一個非超奇異橢
圓曲線E(F2m）是方程
y2+xy=x3+ax2+b ⑸
的解集合（x,y），其中x,y∈F2m，連同θ。
E(F2m）的加法規則如下：
（i) θ +θ= θ
（ii) 任給（x,y) ∈E(F2m），則（x,y）⊙ θ=(x,y)
（iii) 任給（x,y) ∈E(F2m），則（x,y)+(x,x+y)= θ，
即點（x,y）的逆為（x,x+y).
（iv) 兩個相異且不互逆的點的加法規則：
令（x1,y1），（x2,y2） ∈E(F2m）且有x1≠x2則
（x1,y1） (x2,y2）=(x3,y3），其中
x3=α2+α+x1+x2+a；
y3=α（x1+x3）+x3+y1.
其中 α= (y2+y1）/(x2+x1）
（v) 倍點規則
令（x1,y1） ∈E(F2m），其中x1≠0。則
2(x1,y1）=(x3,y3），其中
x3= α 2+ α +a,y3=x12+（α +1）x3，這里α =(x1+y1/x1）
易見，群E(F2m）為Abel群。
例：F24上的一個橢圓曲線
f(x)=x4+x+1為F2上的一個不可約多項式，易見
F24=F2[x] / (f(x)) = {(k0,k1,k2,k3） | (k0,k1,k2,k3）=k0+k1α+k2α2+k3α3， </pre>
<pre>；α為f(x)的零點，ki∈F2}
假定F24上的非超奇異橢圓曲線有下述方程定義：
y2+xy=x3+α4x2+1，注意f（α）=0。
方程應表為：
（1000)y2 + （1000)xy = （1000)x3 + （1100）x2 +（1000) 1985年，N. Koblitz和V. Miller分別獨立提出了橢圓曲線密碼體制（ECC），</pre>
<pre>；其依據就是定義在橢圓曲線點群上的離散對數問題的難解性。
⑴知E(Fq）對點的?斣慫閾緯梢桓鯝bel群
設p∈E(Fq），若p的周期很大，即使
p⊙p⊙ …… ⊙p= θ （共有 t個p相加）
成立的最小正整數 t，希望 t 很大。
（t = p的周期，表示為∏（p)=t）。
並且對Q∈E(Fq），定有某個正整數m使
Q=m·p=p⊙ …… ⊙p （共有t個p相加）
定義
m=㏒pQ (m為以p為底Q的對數）。
橢圓曲線上的點形成的群E(Fq），相關它的離散對數
問題是難處理的。 選取基域Fq，Fq的橢圓曲線具體給定為確定的形式。
在E(Fq）中選一個周期很大的點，如選了一個點P=(xp,yp），
它的周期為一個大的素數n，記∏ (P)=n（素數）。
注意：在這個密碼體制中，具體的曲線及點P和它的n都
是公開信息。密碼體制的形式採用EIGamal體制，是完全
類比過來。
a）密鑰的生成
Bob（使用者）執行了下列計算：
i) 在區間[1,n-1]中隨機選取一個整數d。
ii) 計算點Q:=dP (d個P相）
iii) Bob公開自己的公開密鑰-- (E(Fq),p,n,Q)
iv) Bob的私鑰為整數d！
Alice要發送消息m給Bob，Alice執行：
i) 查找Bob的公鑰（E(Fq),p,n,Q),
ii) 將m表示成一個域元素m∈Fq,
iii) 在區間[1，n-1]內選取一個隨機數k,
iv) 依據Bob的公鑰計算點 (x1,y1）：=kP(k個P相）
v) 計算點（x2,y2）：=kQ，如果x2=0，則回到第iii）步
Ⅵ） 計算C:=m·x2
Ⅶ） 傳送加密數據（x1,y1,C）給Bob
b) Bob的解密過程
Bob收到Alice的密文（x1,y1,C）後，執行
i) 使用私鑰d，計算點（x2，y2）：=d(x1,y1），再計算Fq中x2-1=
通過計算m:=C·x2-1，恢復出明文數據
❺ 橢圓曲線加密演算法
橢圓曲線加密演算法，即：Elliptic Curve Cryptography，簡稱ECC，是基於橢圓曲線數學理論實現的一種非對稱加密演算法。相比RSA，ECC優勢是可以使用更短的密鑰，來實現與RSA相當或更高的安全。據研究，160位ECC加密安全性相當於1024位RSA加密，210位ECC加密安全性相當於2048位RSA加密。
橢圓曲線在密碼學中的使用，是1985年由Neal Koblitz和Victor Miller分別獨立提出的。
一般情況下，橢圓曲線可用下列方程式來表示，其中a,b,c,d為系數。
例如，當a=1,b=0,c=-2,d=4時，所得到的橢圓曲線為:
該橢圓曲線E的圖像如圖X-1所示，可以看出根本就不是橢圓形。
過曲線上的兩點A、B畫一條直線，找到直線與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為A+B，即為加法。如下圖所示：A + B = C
上述方法無法解釋A + A，即兩點重合的情況。因此在這種情況下，將橢圓曲線在A點的切線，與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為A + A，即2A，即為二倍運算。
將A關於x軸對稱位置的點定義為-A，即橢圓曲線的正負取反運算。如下圖所示：
如果將A與-A相加，過A與-A的直線平行於y軸，可以認為直線與橢圓曲線相交於無窮遠點。
綜上，定義了A+B、2A運算，因此給定橢圓曲線的某一點G，可以求出2G、3G（即G + 2G）、4G......。即：當給定G點時，已知x，求xG點並不困難。反之，已知xG點，求x則非常困難。此即為橢圓曲線加密演算法背後的數學原理。
橢圓曲線要形成一條光滑的曲線，要求x,y取值均為實數，即實數域上的橢圓曲線。但橢圓曲線加密演算法，並非使用實數域，而是使用有限域。按數論定義，有限域GF(p)指給定某個質數p，由0、1、2......p-1共p個元素組成的整數集合中定義的加減乘除運算。
假設橢圓曲線為y² = x³ + x + 1，其在有限域GF(23)上時，寫作：y² ≡ x³ + x + 1 (mod 23)
此時，橢圓曲線不再是一條光滑曲線，而是一些不連續的點，如下圖所示。以點(1,7)為例，7² ≡ 1³ + 1 + 1 ≡ 3 (mod 23)。如此還有如下點：
(0,1) (0,22)(1,7) (1,16)(3,10) (3,13)(4,0)(5,4) (5,19)(6,4) (6,19)(7,11) (7,12)(9,7) (9,16)(11,3) (11,20)等等。
另外，如果P(x,y)為橢圓曲線上的點，則-P即(x,-y)也為橢圓曲線上的點。如點P(0,1)，-P=(0,-1)=(0,22)也為橢圓曲線上的點。
相關公式如下：有限域GF(p)上的橢圓曲線y² = x³ + ax + b，若P(Xp, Yp), Q(Xq, Yq)，且P≠-Q，則R(Xr,Yr) = P+Q 由如下規則確定：
Xr = (λ² - Xp - Xq) mod pYr = (λ(Xp - Xr) - Yp) mod p其中λ = (Yq - Yp)/(Xq - Xp) mod p（若P≠Q）, λ = (3Xp² + a)/2Yp mod p（若P=Q）
因此，有限域GF(23)上的橢圓曲線y² ≡ x³ + x + 1 (mod 23)，假設以(0,1)為G點，計算2G、3G、4G...xG等等，方法如下：
計算2G：λ = (3x0² + 1)/2x1 mod 23 = (1/2) mod 23 = 12Xr = (12² - 0 - 0) mod 23 = 6Yr = (12(0 - 6) - 1) mod 23 = 19即2G為點(6,19)
計算3G：3G = G + 2G，即(0,1) + (6,19)λ = (19 - 1)/(6 - 0) mod 23 = 3Xr = (3² - 0 - 6) mod 23 = 3Yr = (3(0 - 3) - 1) mod 23 = 13即3G為點(3, 13)
建立基於橢圓曲線的加密機制，需要找到類似RSA質因子分解或其他求離散對數這樣的難題。而橢圓曲線上的已知G和xG求x，是非常困難的，此即為橢圓曲線上的的離散對數問題。此處x即為私鑰，xG即為公鑰。
橢圓曲線加密演算法原理如下：
設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。
公鑰加密：選擇隨機數r，將消息M生成密文C，該密文是一個點對，即：C = {rG, M+rK}，其中K為公鑰
私鑰解密：M + rK - k(rG) = M + r(kG) - k(rG) = M其中k、K分別為私鑰、公鑰。
橢圓曲線簽名演算法，即ECDSA。設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。
私鑰簽名：1、選擇隨機數r，計算點rG(x, y)。2、根據隨機數r、消息M的哈希h、私鑰k，計算s = (h + kx)/r。3、將消息M、和簽名{rG, s}發給接收方。
公鑰驗證簽名：1、接收方收到消息M、以及簽名{rG=(x,y), s}。2、根據消息求哈希h。3、使用發送方公鑰K計算：hG/s + xK/s，並與rG比較，如相等即驗簽成功。
原理如下：hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s= r(h+xk)G / (h+kx) = rG
假設要簽名的消息是一個字元串：「Hello World!」。DSA簽名的第一個步驟是對待簽名的消息生成一個消息摘要。不同的簽名演算法使用不同的消息摘要演算法。而ECDSA256使用SHA256生成256比特的摘要。
摘要生成結束後，應用簽名演算法對摘要進行簽名：
產生一個隨機數k
利用隨機數k，計算出兩個大數r和s。將r和s拼在一起就構成了對消息摘要的簽名。
這里需要注意的是，因為隨機數k的存在，對於同一條消息，使用同一個演算法，產生的簽名是不一樣的。從函數的角度來理解，簽名函數對同樣的輸入會產生不同的輸出。因為函數內部會將隨機值混入簽名的過程。
關於驗證過程，這里不討論它的演算法細節。從宏觀上看，消息的接收方從簽名中分離出r和s，然後利用公開的密鑰信息和s計算出r。如果計算出的r和接收到的r值相同，則表示驗證成功。否則，表示驗證失敗。
❻ ECDSA（橢圓曲線數字簽名演算法）
ECDSA（Elliptic Curve Digital Signature Algorithm）
在現實工作和生活中，我們使用簽名的方式表達對一份文件的認可，其他人可以識別出你的簽名並且無法偽造你的簽名。數字簽名就是對顯示簽名的一種電子實現，它不僅可以完全達到現實簽名的特點，甚至能夠做的更好。
常用的數字簽名演算法有RSA（Rivest-Shamir-Adleman Scheme）、DSS（Digital Signature Standard）等。 比特幣使用ECDSA來生成賬戶的公私鑰以及對交易和區塊進行驗證。
1.Alice（密碼學中常用A到Z開頭的人名代替甲乙丙丁等，字母越靠後出現頻率越低）生成一對密鑰，一個是sk（signing key），是非公開的；另一個是vk（verification key），是公開的。
這一對密鑰同時生成，並且在數學上是相互關聯的，同時，根據vk無法推測出關於sk的任何信息。
2.數字簽名演算法接收兩個輸出：信息M和sk，生成一個數字簽名Sm
3.驗證函數接收信息M、Sm以及vk作為輸入，，返回結果是yes或者no。這一步的目的是為了驗證你看到的針對信息M的數字簽名確實是由Alice的sk來簽發的，用於確認信息與簽名是否相符。
與手寫簽名不同，手寫簽名基本都是相似的，但是數字簽名卻受輸入影響很大。對輸入輕微的改變都會產生一個完全不同的數字簽名。一般不會對信息直接進行數字簽名，而是對信息的哈希值進行簽名。由加密哈希函數的無碰撞性可知，這樣和對原信息進行簽名一樣安全。
在數學上，任何滿足以下方程的點所形成的曲線稱為隨機橢圓曲線： 並且 ，a和b可以為任意值。下面展示幾個隨機橢圓函數的示例：
在了解如何通過基於secp256k1橢圓曲線的ECDSA演算法生成公私鑰之前，我們需要了解在隨機橢圓曲線里，點的加法是如何實現的。
首先定義橢圓曲線上點的加法。設橢圓曲線上有兩點，A和B點，那麼作過這兩點的直線與該曲線相交於第三點（C點），然後關於X軸對稱得到D點，則D為這兩個點的和，記作D=A+BD=A+BD=A+B。很明顯，D點也在該曲線上。所以橢圓曲線上兩點之和也是曲線上的點。
特例：
1.如果兩點重合，則做該點的切線，與曲線相交點的對稱點為和，即A+A=C
如圖：
有了加法以後，乘法實現是不過是進行多次加法運算。有了一個基準點P以後，我們可以對其進行乘法運算，最後可以得到曲線上的另外一個點。
設PPP是橢圓曲線上的一個點，那麼正整數kkk乘以點PPP的結果由下面的式子定義，注意式子中的加法是上面提到的橢圓曲線上點的加法：
點的運算滿足結合律：
很顯然，通過累加 的方式計算 是一種很笨的辦法，其時間復雜度是線性的。上面我們提到過，橢圓曲線上點的加法是滿足結合律的，即 ，擴展一下，就有
於是就有這么一種騷操作，比如計算 ，我們可以先計算 ；然後計算 ；再計算 ；最後計算 。這里我們把15次加法減少到了4次。
當然，k的值不可能總是2的冪。實際上上面的操作可以推廣到k為任意正整數的情況。比如計算23P，首先計算 ，然後
因為 ，所以 。總共只需要7次加法。
分析一下，對於任意正整數k，我們都可以利用這個方法將計算k∗P所需的加法計算次數降低到
也就是說，從時間復雜度的角度來看，這個演算法是一個 的演算法。
這個方法被稱為快速冪演算法，原本常用於快速計算某個數的k次冪，這里將其推廣到橢圓曲線點乘的快速計算中。
為什麼要在介紹了橢圓曲線上點的乘法後突然冒出一個快速冪演算法？快速冪演算法對於橢圓曲線加密有什麼意義？因為數學家/密碼學家發現，利用快速冪演算法計算 的時間復雜度是對數級的，但是要在知道 和 的前提下，倒推出 的值，沒有比挨個嘗試 的值快太多的演算法。於是橢圓曲線加密依賴的數學難題就這么誕生了。
如果我們改一種記法，把橢圓曲線上點的加法記作乘法，原來的乘法就變成了冪運算，那麼上述難題的形式跟離散對數問題應該是一致的。即：
所以這個難題叫橢圓曲線上的離散對數問題。
盡管兩者形式一致，但是他們並不等價。實際上這個問題比大整數質因子分解（RSA）和離散對數（DH）難題都要難得多，目前還沒有出現亞指數級時間復雜度的演算法（大整數質因子分解和離散對數問題都有），以致於同樣的安全強度下，橢圓曲線加密的密鑰比RSA和DH的短不少，這是橢圓曲線加密的一大優勢。
假設隨機取一個 ~ 位之間的值x，計算 ，最後的結果一定會落在曲線上的一點。假設該點為 ，在公開 以及具體曲線的方程的情況下，能否反推出最初的隨機值 ？
證：尋找 的過程只能通過暴力計算， 的可能值為 ~ 中的一個，平均來說需要計算 次能夠找到一次 值。那麼問題來了，運行一次 的計算需要多長的時間呢？
假設我們使用的是超級計算機，主頻為 （一秒鍾可以進行一萬億次運算），從宇宙誕生的那一刻開始計算，到現在也就進行了 次。找到 值的概率為 。這個概率和下一秒地球被巨型隕石撞擊而毀滅的概率接近，既然我們讀到了這里，那麼說明這件事沒有發生。
在上面的案例中， 是 ~ 位的一個隨機數，可以作為私鑰。 是隨機橢圓曲線上的一個點，也就是由私鑰生成的公鑰，因此優點可以1得證。
但是密碼學中，並不能使用上面介紹的實數域上的橢圓曲線。因為
所以我們需要引入有限域上的橢圓曲線。
要證明優點2，還需要將隨機橢圓曲線做一些改動：為了保證最後計算出來的點的坐標值相加是512位，secp256k1引入了一個對質數取模的機制。具體來說，隨機橢圓曲線從
變為了 其中 ，是小於 的最大質數。
此時的隨機橢圓曲線函數圖如下：
具體來說，就是向別人證明我知道 ，但不暴露 的任何信息。（有些類似於零知識證明）
證：前面介紹過結合律： 添加一個hash函數，簡單修改可以得出： 使 ，那麼可知 為 。此時方程為： 為了簡單起見，我們記 和 。此時方程化簡為： 上面這個方程是什麼意思呢？
可以這樣假設：在已知 的情況下，如果能夠提供一個 和 滿足上面的方程，就可以證明一個人擁有 。這個假設有一個前提，如果一個人不知道x，那麼他就無法提供 和 滿足上面的等式。
詳細探討這個前提：如果一個人不知道x，又想計算出 和 ，能夠辦到嗎？結論是不能，首先我們無法從 計算出 （在有限時間內）。
還有一個問題：在已知 和 的情況下，能否計算出關於 的任何信息？
根據公式： 只要解出 就可以了。
要想計算出x，就需要知道r，但是在r沒有公開的情況下，有什麼辦法可以計算r嗎？我們知道R=r*P；但是根據這個公式無法倒推出r（剛才介紹的那個數學難題），所以x也是安全的。
至此，可以證明演算法的第二個優點。