這邊會展示的程式碼，是不能拿來做正式加解密的。
我先註明一下，因為時間不是很夠了，無法研究一些特殊的曲線跟算法。
所以這邊只能拿出最基本的，實驗且娛樂性質的程式。
當取模的數有點大時，整個加密系統幾乎跑不太動。
當然，這並沒有做類似於X25519那樣的曲線特化。
因此如果未來有時間有機會，會再寫幾篇真正能像RSA那樣隨意調整長度的程式。
這邊就是講解除和去編寫一些程式碼，讓上一章講的東西實現而已。
再一次聲明，這個不是安全曲線、不是有效的程式、比起我寫完的RSA還要慢上超級無敵多。
無法體現出ECC的優秀，但能展示ECC的一些方法。
首先我們的第一步就是讓大家輸入a、b、mod，並確認是否符合橢圓曲線的規則。
判斷是否符合單一解的橢圓曲線公式：(4 * (a^3) + 27 * (b^2)) (mod n) == 0
def get_arg(lens:int) -> Tuple[int, int, int]:
while True:
a = int(input('a：'))
b = int(input('b：'))
mod = get_prime(lens)
if (4 * (a ** 3) + 27 * (b ** 2)) % mod == 0:
print('Is not correct number.')
else:
break
return a, b, mod
get_prime請看RSA那邊的程式。
生成大質數的一個Function。
接著我們必須先把R＝Q+P的公式寫成function。
還記得公式嗎：
要是 xp==xq 而且 yp == yq則：S為(3*Xp^2 - a)/(2*Yp) (mod K)
要是 xp!=xq 則：S為(Yp-Yq)/(Xp-Xq) (mod K)
但為了方便，我們把分子跟分母先分開。
要是xp!=xq 則確認是否有負號，要是有將負號紀錄起來，將分子跟分母都先取絕對值。
接著做gcd取得最大公因數，然後分子分母同除以最大公因數。
最後將分母變成倒數形式，並先做模處理防止有小數。
分子跟倒數後的分母兩者相乘並乘以負號後紀錄，取得兩點的斜率並取模，最後回傳R點或稱為G點（代號的不同）。
def get_q(p: Tuple[int, int], q: Tuple[int, int], a: int, mod: int) -> Tuple[int, int]:
def get_s(p: Tuple[int, int], q: Tuple[int, int], a: int, mod: int) -> int:
negative = 1
if p == q:
numerator = 3 * (p[0] ** 2) + a
denominator = 2 * p[1]
else:
numerator = q[1] - p[1]
denominator = q[0] - p[0]
if numerator < 0 or denominator < 0:
negative = -1
numerator = abs(numerator)
denominator = abs(denominator)
gcd = get_gcd(numerator, denominator)
numerator = numerator // gcd
denominator = denominator // gcd
# Get reciprocal
reciprocal = get_reciprocal(denominator, mod)
return (negative*numerator * reciprocal) % mod
s = get_s(p, q, a, mod)
xr = (s**2-p[0]-q[0]) % mod
yr = (s*(p[0]-xr) - p[1]) % mod
return xr, yr
完成了計算兩點之後，我們就必須先選一個點來當作基點。
因此隨機選擇一個數值來當G點。
而G點也必須符合橢圓曲線上的點。
判斷是否在曲線上：y^2 (mod n) == x^3+x*a+b (mod n)
def get_point(a: int, b: int, mod: int, lens: int) -> Tuple[int, int]:
while True:
x = random.randint(10**(lens-1), 10**lens-1)
for _ in range(100):
y = random.randint(10**(lens-1), 10**lens-1)
if (y ** 2 % mod) == ((x**3+x*a+b) % mod):
print(9)
return x, y
並且要知道這個G點跟取餘數之後最大的n點。
利用不斷的做兩點堆疊從G、2G、3G...nG。
def get_g_n(g: Tuple[int, int], a: int, mod: int) -> int:
symmetry_y = (-1*g[1]) % mod
temp = g
n = 0
while True:
n += 1
temp = get_q(temp, g, a, mod)
if g[0] == temp[0] and symmetry_y == temp[1]:
return n
這下我們檢視一下現有的參數：
接下來就簡單了。
還記得我說的吧？
我們很難從AG或BG跟G得知A或B。
那我們先選一個A然後算出它的AG。
再用同樣方法隨機選一個B，然後算出它的BG。
程式很簡單地在0到n（此基點的最大階）中挑一個來當作私鑰。
然後算出公鑰。
def get_xg(g: Tuple[int, int], xg: Tuple[int, int], x: int, a: int, mod: int) -> Tuple[int, int]:
temp = xg
while x != 1:
temp = get_q(temp, g, a, mod)
x -= 1
return temp
def gen_key(g: Tuple[int, int], n: int, a: int, mod: int) -> Tuple[int, Tuple[int, int]]:
private_key = random.randint(0, n)
public_key = get_xg(g,g, private_key, a, mod)
return private_key, public_key
這樣就可以得到(A,AG,G)跟(B,BG,G)，然後兩者交換後驗證是否能得到共同的ABG。
然後其他的流程如下：
def eccdh():
lens = int(input('金鑰長度：'))
a, b, mod = get_arg(lens+1)
g, n = gen_g(a, b, mod, lens)
a_private, a_public = gen_key(g, n, a, mod)
b_private, b_public = gen_key(g, n, a, mod)
# check ABG
apbp = get_xg(g,a_public, b_private, a, mod)
bpap = get_xg(g,b_public, a_private, a, mod)
if apbp != bpap:
print("APBP Is Not Equal：", apbp, bpap)
return False
def get_gcd(a: int, b: int) -> int:
return a if b == 0 else get_gcd(b, a % b)
def get_reciprocal(value: int, mod: int) -> int:
for i in range(1, mod):
if (i * value) % mod == 1:
return i
return -1
這邊我很慚愧的跟大家說，這個程式不像之前的RSA之類的，能真的寫出來並使用。
這邊其實是用便利的方式來算出xG的……其實不能這樣（這樣會簡單的被反推或驗證，而且速度太慢）。
而且想講的X25519曲線特性也沒機會講，我會先提供我所有的資料在補充資料裡面。
裡面其實很詳細地介紹了X25519的優勢，但沒能完全理解並實現其算法還是有點難過的。
但不用擔心，我會找時間寫幾篇文章來處理這部份，唯一的缺點就是不連貫而已。
本來想說花時間將X25519的演算法處理完，但後來一看裡面太多新的數學知識了。
例如Edwards曲線、蒙哥馬利曲線、蒙哥馬利階梯等等的。
無法完整地討論整個ECC我自己也很慚愧，要是能完整地討論這一部份，這系列的文章將會是很先進的密碼學類文章了。
還有很多關於ECC的算法都沒有介紹……有機會一定跟大家來說說。
如果到時候有做新的文章更新，或是大神有寫文章，我會放在留言或編輯後，放在最下面。
接下來就是Hash的部分了。
Ed25519: high-speed high-security signatures
Elliptic Curve Cryptography (ECC) - Concepts
iThome鐵人賽
看影片追技術