跟RSA一樣同樣用 elliptic curves, 通常我們可以做以下兩件事:
除了certicom外,IEEE1363和NIST方面有定義出一些建議使用的curve,其中NIST三條標準的 elliptic curve 為:
另外還有其他著名的curve像是 Curve25519 curve (key exchange使用), Ed25519 curve (數位簽章使用),更多curve 選擇可參考
最近也有一個有趣的專案Million Dollar Curve,想要用樂透等公開random source來建立第三方可驗證的curve
ECC的 Key Exchange (ECDH) 紀錄在 in NIST publication 800-56Ar2中
Elliptic curve是什麼呢? 事實上著名的Fermat's Last Theorem便是由elliptic curve解開的(不過是定義於實數域的elliptic curve),可參考數學女孩
Wolfram MathWorld有完整數學上的定義
我們可以把他想成由以下方程式組成的點:
$y^2=x^3+ax+b$
其中 $4a^3+27b^2 \neq 0$ (用來排除 singular curves). 這種形式稱為 Weierstrass normal form for elliptic curves
根據不同的a, b值, elliptic curves 會呈現不同的形狀, 我們在實數上畫出來 elliptic curves 是對稱x軸的!
通常我們會把無窮遠點也加入 curve中,我們將它標記為 0
故納入無窮遠點後的橢圓曲線為:
$\{(x,y)∈R^2 | y^2=x^3+ax+b, 4a^3+27b^2 \neq 0\} ∪ \{0\}$, 以下我們簡單的畫出elliptic curve和上面的點加法(後面會進一步介紹)給讀者參考:
import numpy as np
import matplotlib.pyplot as plt
from elliptic import *
from fractions import Fraction as frac
import numpy.polynomial.polynomial as poly
def drawLine2P(x,y,xlims):
xrange = np.arange(xlims[0],xlims[1],0.1)
A = np.vstack([x, np.ones(len(x))]).T
k, b = np.linalg.lstsq(A, y)[0]
plt.plot(xrange, k*xrange + b, 'k')
def interactive_curve(a=-4, b=4, Px=3, Qx=-2):
if 4*a^3 + 27*b^2 == 0:
print 'The choice of a = %s and b = %s does not define an elliptic curve because this makes 27a^3 + 4b^2 = 0.'%(a,b)
else:
y, x = np.ogrid[-5:5:100j, -5:5:100j]
plt.contour(x.ravel(), y.ravel(), pow(y, 2) - pow(x, 3) - x * a - b, [0])
C = EllipticCurve(a=frac(a), b=frac(b))
ro = poly.polyroots((b,a,0,1))
ro = ro[np.isreal(ro)]
if(len(ro) == 1):
if Px < ro[0].real:
Px = ro[0].real
if Qx < ro[0].real:
Qx = ro[0].real
else:
if ro[1].real < Px < ro[2].real:
Px = ro[1].real
P = C.from_x(frac(Px))
Q = C.from_x(frac(Qx))
R = P + Q
zero = Ideal(C)
drawLine2P([float(P[0]),float(Q[0])],[float(P[1]),float(Q[1])],[-5,5])
plt.plot(float(P[0]),float(P[1]), 'o')
plt.plot(float(Q[0]),float(Q[1]), 'o')
plt.plot(float(R[0]),float(R[1]), 'o')
plt.xlim([-5,5])
plt.ylim([-5,5])
plt.annotate(r'$P$',
xy=(float(P[0]), float(P[1])), xycoords='data',
xytext=(+10, +30), textcoords='offset points', fontsize=16,
arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=.2"))
plt.annotate(r'$Q$',
xy=(float(Q[0]), float(Q[1])), xycoords='data',
xytext=(+10, +30), textcoords='offset points', fontsize=16,
arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=.2"))
plt.annotate(r'$R$',
xy=(float(R[0]), float(R[1])), xycoords='data',
xytext=(+10, +30), textcoords='offset points', fontsize=16,
arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=.2"))
plt.grid()
plt.show()
from IPython.html.widgets import interact
interact(interactive_curve, a=[-10, 3], b=[-10,10], Px=[-20,20], Qx=[-20, 20])
我們這邊簡單介紹一些abstract algebra中的群論:一個set我們定義 "addition" 並標示為 +, 此 set G 稱之為 group, addition 必續根據下列四個性質來定義!
若再加上 commutativity: $a+b=b+a$ 則此 group 稱為 abelian group.
我們常見的加法配上 integer numbers 組成的set $Z$ 便是 group (事實上他是 abelian group).然而自然數$N$就不是了,因為不符合第四個條件。
若我們能證明某一set滿足以上性質,我們就可以借用抽象代數中的群的相關特性!! 例如: identity element是唯一的,inverse也是唯一的
我們可以定義橢圓曲線群如下:
Addition定義為: 給定三個 aligned 且 non-zero 的點 P, Q, R, P+Q+R=0
經由這樣的定義我們可以得知這個點是無順序性不相關的,也就是說假設 P, Q, R 是 aligned, 則 P+(Q+R)=Q+(P+R)=R+(P+Q)=⋯=0. 因此我們的 +
operator 是 associative 且 commutative 故為一個 abelian group! 既然在abelian group我們就可以把 P+Q+R=0 寫成 P+Q=-R 因此得到圖像加法如下:
可以由此來感受加法!!
接下來我們把上述加法寫成數學式,考慮兩個點$P=(x_P,y_P), Q=(x_Q,y_Q)$,假設兩者不同,通過兩點的線斜率為
$m = \frac{y_P - y_Q}{x_P - x_Q}$
而他與橢圓曲線的交點為$R = (x_R, y_R)$
$\begin{array}{rcl} x_R & = & m^2 - x_P - x_Q \\ y_R & = & y_P + m(x_R - x_P) \end{array}$
因此$(x_P, y_P) + (x_Q, y_Q) = (x_R, -y_R)$
若$P=Q$的話,經由微分$y_P = \pm \sqrt{x_P^3 + ax_P + b}$ 可得 $m = \frac{3 x_P^2 + a}{2 y_P}$
連加$n$次$P$可寫成$nP$此運算稱為scalar multiplication。
這邊可感受乘法
在實際時做上,我們可以藉由double-and-add來加速此運算
def bits(n):
"""
Generates the binary digits of n, starting
from the least significant bit.
bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
"""
while n:
yield n & 1
n >>= 1
def double_and_add(n, x):
"""
Returns the result of n * x, computed using
the double and add algorithm.
"""
result = 0
addend = x
for bit in bits(n):
if bit == 1:
result += addend
addend *= 2
return result
橢圓曲線基於的數學問題是elliptic curve discret logarithm problem(ECDLP): 給定$n, P$我們可以很快利用上述方法算出$Q=nP$,然而給$Q$和$P$要推$n$就不容易了...。
實數域的elliptic curve並不能拿來密碼學使用(前述是在實數中),這邊我們介紹Galois Field (Finite Field)。 Finite field 是一個元素為有限數目的set, 一個簡單的例子是 integers modulo p ($p$為質數)。 我們通常寫成 $Z/p, GF(p), F_p$.
在 field 中我們有兩種 binary operations: addition (+) 和 multiplication (·), 兩者皆為 closed, associative 且 commutative。對此兩種運算, 都存在著唯一的identity element, 且對field內的 element 都有唯一的 inverse element。 最後 multiplicationy在field中是 distributive over addition: $x⋅(y+z)=x⋅y+x⋅z$
$x/y$在field中可寫成$x*y^{-1}$,
接下來我們將elliptic curve限制在 Finit Field中 (注意其仍為abelian group!)
$ \begin{array}{rcl} \left\{(x, y) \in (\mathbb{F}_p)^2 \right. & \left. | \right. & \left. y^2 \equiv x^3 + ax + b \pmod{p}, \right. \\ & & \left. 4a^3 + 27b^2 \not\equiv 0 \pmod{p}\right\}\ \cup\ \left\{0\right\} \end{array} $
0 為無窮遠點, 且 a 和 b 為兩個 $F_p$中的 integer.
來感受一下現在他長怎麼樣吧( $y^2 \equiv x^3 - 7x + 10 \pmod{p}$ 當 $p=19,97,127,487$ 對每一x最多會有兩點y。 另外點是對 $y=p/2$ 對稱的!)
經過此一限制之後,geometric addition會變得不太一樣(可以玩前述tool),不過我們保持定義的話,algebra addition仍然可保持相同公式(多了modulus P)。
接下來我們可以證明出 multiples of P 實際上是一個 cyclic subgroup of the group formed by the elliptic curve
,藉此我們進一步定義出elliptic curve的order(所有點的數目)和點的order(加幾次可以回到自己)。
對密碼學應用來說,我們會去選擇高order的 subgroups。 實務上我們會先選 elliptic curve, 然後計算 order (N), 選擇 high divisor的(n) 來當 subgroup order, 最後找到適合的 base point。
Lagrange's theorem 告訴我們 $h=N/n$ 永遠是整數 (因為 $n$ 為 $N$的 divisor). $h$ 稱作 cofactor of the subgroup.
假設 $E$ 為定義在 field $K$ 上的 elliptic curve,根據 group addition law 我們可以知道每一個$E$上的點都可以產生出一個 cyclic group $G$。若這個 $G$ 的 order 是質數的話就可以用在cryptography上。
這表示group operation, inversion, hasing都可以很快完成,但是DLP很難解
因此跟$F^*$乘法群的對照便是我們可以用$E(K)$上的點配上點加法來類比乘法群元素。在乘法群中,我們會選擇一個$F^*$的subgroup $G$ order為$n$,但任意選通常不會有此order,因此常見的做法是用演算法隨機hash到一個 $x \in F^*$,然後再把他exponential 成 $N/n$,($N$為 $F^*$的元素數量)。
橢圓曲線也是如此,假設$N = \#E(K)$,
若 $G$ 為 $O$, 回到 step 3. 最後我們得到 subgroup with order $n$ 和 cofactor $h$.
Elliptic curve algorithms 是定義於 cyclic subgroup of an elliptic curve over a finite field 因此我們會有下列參數:
也就是 domain parameters包含tuple $(p,a,b,G,n,h)$
事實上有些curve是不安全的,我們如何確保選出的curve是安全的呢,有一種常見作法如下
Curve 用此方法產生稱作 verifiably random. 這個用 hashes 產生 parameters 的方法叫 "nothing up my sleeve", 常常被用於 cryptography中
他給我們一些信心,curve不會是 crafted 而有特定 vulnerabilities 只有設計者知道。 事實上設計者給我們seed和curve, 他沒辦法控制我們選取 parameters $a$ 和 $b$, 因此比較有安全感。
標準產生和驗證 random curves 的方法訂於 ANSI X9.62 並用到 SHA-1. 可以看SECG的相關說明
可以用以下程式來確認:
%%bash
python3 verifyrandom.py
接下來我們將重點放在 ECDH (Elliptic curve Diffie-Hellman)(用於加密), 和 ECDSA (Elliptic Curve Digital Signature Algorithm)(用於簽章)
%%bash
python3 ecdhe.py
%%bash
python3 ecdsa.py
最後,我們上述都是在prime filed, affine coordinate, Weierstrass form curve,更多的其他選擇和加法公式可參考 EFD
import pyelliptic
def generate_key():
return pyelliptic.ECC(curve='secp521r1')
Public 和 private keys 可以從curve exported 出來
curve = generate_key()
priv = curve.get_privkey()
pub = curve.get_pubkey()
print curve.get_curve()
print priv.encode('hex'), len(priv.encode('hex')), len(priv)
print pub.encode('hex'), len(pub.encode('hex')), len(pub)
通常做數位簽章的時候, 我們會先計算 message 的 hash 再做簽章。 PyElliptic 會使用 SHA-512 來做 ECDSA.
def sign(key, msg):
"""Sign a message with the ECDSA key."""
return key.sign(msg)
驗證時候的input是 serialised public key 然後匯入 pyelliptic.ecc.ECC instance 做運算
def verify(pub, msg, sig):
"""Verify the signature on a message."""
return pyelliptic.ECC(curve='secp521r1', pubkey=pub).verify(sig, msg)
現在來說明如何用ECDH來產生shared key
用 pyelliptic時, private key 要是 instance of pyelliptic.ecc.ECC; 而 public key 要是 serialised form.
shared_key = curve.get_ecdh_key(pub)
len(shared_key)
def shared_key(curve, pub):
"""Generate a new shared encryption key from a keypair."""
shared_key = curve.get_ecdh_key(pub)
return shared_key
接下來我們來看看常見的 hybrid encryption的方式,我們會用 ephemeral keys 來做 encryption;也就是我們每次加密會產生 elliptic curve key pair 這種加密方法叫 elliptic curve integrated encryption scheme, ECIES。 (或更準確來說,因為 key exchange 為 on the fly 完成,故稱為 ECDHE)
import struct
import Crypto.Random.OSRNG.posix as RNG
import Crypto.Cipher.AES as AES
__AES_KEYLEN = 32
def generate_nonce():
"""Generate a random number used once."""
return RNG.new().read(AES.block_size)
def pad_data(data):
"""pad_data pads out the data to an AES block length."""
# return data if no padding is required
if len(data) % 16 == 0:
return data
# subtract one byte that should be the 0x80
# if 0 bytes of padding are required, it means only
# a single \x80 is required.
padding_required = 15 - (len(data) % 16)
data = '%s\x80' % data
data = '%s%s' % (data, '\x00' * padding_required)
return data
def unpad_data(data):
"""unpad_data removes padding from the data."""
if not data:
return data
data = data.rstrip('\x00')
if data[-1] == '\x80':
return data[:-1]
else:
return data
def sym_encrypt(data, key):
"""
Encrypt data using AES in CBC mode. The IV is prepended to the
ciphertext.
"""
data = pad_data(data)
ivec = generate_nonce()
aes = AES.new(key, AES.MODE_CBC, ivec)
ctxt = aes.encrypt(data)
return ivec + ctxt
def sym_decrypt(ciphertext, key):
"""
Decrypt a ciphertext encrypted with AES in CBC mode; assumes the IV
has been prepended to the ciphertext.
"""
if len(ciphertext) <= AES.block_size:
raise Exception("Invalid ciphertext.")
ivec = ciphertext[:AES.block_size]
ciphertext = ciphertext[AES.block_size:]
aes = AES.new(key, AES.MODE_CBC, ivec)
data = aes.decrypt(ciphertext)
return unpad_data(data)
def encrypt(pub, msg):
"""
Encrypt the message to the public key using ECIES. The public key
should be a serialised public key.
"""
ephemeral = generate_key() # Alice's private key
key = shared_key(ephemeral, pub) #Symmetric key derives from ECDH (alice_priv + bob_pub)
ephemeral_pub = struct.pack('>H', len(ephemeral.get_pubkey()))
print ephemeral_pub, len(ephemeral.get_pubkey())
ephemeral_pub += ephemeral.get_pubkey() # Alice's public key
print ephemeral_pub
return ephemeral_pub + sym_encrypt(msg, key)
def decrypt(priv, msg):
"""
Decrypt an ECIES-encrypted message with the private key.
"""
ephemeral_len = struct.unpack('>H', msg[:2])[0]
ephemeral_pub = msg[2:2+ephemeral_len] # Alice's public key
key = shared_key(priv, ephemeral_pub) #symmetric key derives from ECDH(bob_priv, alice_pub)
return sym_decrypt(msg[2+ephemeral_len:], key)
上述我們將 public key 加到開頭, 包含 public key 的長度,然後將 ciphertext 接在後面。 解密時需要解回 public key (先讀取 length 然後從 message 中擷取出 public key) 接著用ECDH 找出 shared key後進行訊息加密
curve = generate_key() # Bob generate private key
pub = curve.get_pubkey() # Alice get the pubkey from Bob
plaintext = 'AG is god'
ciphertext = encrypt(pub, plaintext) # Alice encrypt message
print decrypt(curve, ciphertext) #Bob decrypt it