橢圓曲線加密演算法

NO IMAGE

橢圓曲線加密演算法,即:Elliptic Curve Cryptography,簡稱ECC,是基於橢圓曲線數學理論實現的一種非對稱加密演算法。相比RSA,ECC優勢是可以使用更短的金鑰,來實現與RSA相當或更高的安全。據研究,160位ECC加密安全性相當於1024位RSA加密,210位ECC加密安全性相當於2048位RSA加密。

  橢圓曲線在密碼學中的使用,是1985年由Neal Koblitz和Victor Miller分別獨立提出的。
  

橢圓曲線

一般情況下,橢圓曲線可用下列方程式來表示,其中a,b,c,d為係數。

E:y2=ax3 bx2 cx d

例如,當a=1,b=0,c=-2,d=4時,所得到的橢圓曲線為:

E:y2=x3-2x 4

該橢圓曲線E的影象如圖X-1所示,可以看出根本就不是橢圓形。  

image

定義橢圓曲線的運算規則

加法

過曲線上的兩點A、B畫一條直線,找到直線與橢圓曲線的交點,交點關於x軸對稱位置的點,定義為A B,即為加法。如下圖所示:A B = C

image

二倍運算

上述方法無法解釋A A,即兩點重合的情況。因此在這種情況下,將橢圓曲線在A點的切線,與橢圓曲線的交點,交點關於x軸對稱位置的點,定義為A A,即2A,即為二倍運算。

image

正負取反

將A關於x軸對稱位置的點定義為-A,即橢圓曲線的正負取反運算。如下圖所示:

image

無窮遠點

如果將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)也為橢圓曲線上的點。

image

計算xG

  相關公式如下:
  有限域GF(p)上的橢圓曲線y² = x³ ax b,若P(Xp, Yp), Q(Xq, Yq),且P≠-Q,則R(Xr,Yr) = P Q 由如下規則確定:

  Xr = (λ² – Xp – Xq) mod p
  Yr = (λ(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:
  λ = (3×0² 1)/2×1 mod 23 = (1/2) mod 23 = 12
  Xr = (12² – 0 – 0) mod 23 = 6
  Yr = (12(0 – 6) – 1) mod 23 = 19
  即2G為點(6,19)

  計算3G:
  3G = G 2G,即(0,1) (6,19)
  λ = (19 – 1)/(6 – 0) mod 23 = 3
  Xr = (3² – 0 – 6) mod 23 = 3
  Yr = (3(0 – 3) – 1) mod 23 = 13
  即3G為點(3, 13)

  同理計算4G、5G…xG,分佈如下圖:
  
  [圖片上傳失敗…(image-2d5c43-1526642990683)]
  

橢圓曲線加解密演算法原理

  建立基於橢圓曲線的加密機制,需要找到類似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

程式碼實現:

package main
import (
"crypto/ecdsa"
"crypto/elliptic"
"crypto/rand"
"crypto/sha256"
"math/big"
"fmt"
)
//通過橢圓曲線完成簽名和驗證
func main() {
//宣告明文
message := []byte("hello world")
//生成私鑰
privateKey, _ := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
//生成公鑰
pub := privateKey.PublicKey
//將明文雜湊
digest := sha256.Sum256(message)
//簽名
r, s, _ := ecdsa.Sign(rand.Reader, privateKey, digest[:])
//設定私鑰的引數型別為曲線型別
param := privateKey.Curve.Params()
//獲得私鑰byte長度
curveOrderByteSize := param.P.BitLen() / 8
//獲得簽名返回值的位元組
rByte, sByte := r.Bytes(), s.Bytes()
//建立陣列
signature := make([]byte, curveOrderByteSize*2)
//通過陣列儲存了簽名結果的返回值
copy(signature[curveOrderByteSize-len(rByte):], rByte)
copy(signature[curveOrderByteSize*2-len(sByte):], sByte)
//認證
//將明文做hash雜湊,為了驗證的內容對比
digest = sha256.Sum256(message)
curveOrderByteSize = pub.Curve.Params().P.BitLen() / 8
//建立兩個整形物件
r, s = new(big.Int), new(big.Int)
//設定證書值
r.SetBytes(signature[:curveOrderByteSize])
s.SetBytes(signature[curveOrderByteSize:])
​```
//認證
e := ecdsa.Verify(&pub, digest[:], r, s)
if e == true {
fmt.Println("OK")
} else {
fmt.Println("failed")
}
​```
}