ECC 隨筆

, , ,

Before all

橢圓曲線好ㄟ >< b
隨筆記一下，一樣是從CryptoHack學來ㄉ
未完成，會慢慢補齊全。

Note

基本知識：

通常ECC丟出來的曲線都是：

  • E: Y^2 = X^3 + aX + b
  • 4a^3 + 27b^2 ≠ 0

在F_p下曲線點加法定律：
簡單來說就是取兩點連線後交取縣的第三點之對稱點。 

1
2
3
4
(a) P + O = O + P = P
(b) P + (−P) = O
(c) (P + Q) + R = P + (Q + R)
(d) P + Q = Q + P

加法算法owo： 

1
2
3
4
5
6
7
8
9
(a) If P = O, then P + Q = Q.
(b) Otherwise, if Q = O, then P + Q = P.
(c) Otherwise, write P = (x1, y1) and Q = (x2, y2).
(d) If x1 = x2 and y1 = −y2, then P + Q = O.
(e) Otherwise:
  (e1) if P ≠ Q: λ = (y2 - y1) / (x2 - x1)
  (e2) if P = Q: λ = (3x12 + a) / 2y1
(f) x3 = λ2 − x1 − x2,     y3 = λ(x1 −x3) − y1
(g) P + Q = (x3, y3)

image
source code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
def add_point(p1, p2):
    if p1 == (0, 0):
        return p2
    if p2 == (0,0):
        return p1
    x1, y1 = p1
    x2, y2 = p2
    if x1 == x2 and y1 == -y2:
        return (0, 0)
    lamda = 0
    if p1 == p2:
        lamda = int((3*pow(x1,2,p)+a) * inverse(2*y1, p))
    else:
        lamda = int((y2-y1) * inverse(x2-x1, p))
    x3 = int((pow(lamda, 2) - x1 - x2) % p)
    y3 = int((lamda*(x1 - x3) - y1) % p )
    return (x3, y3)

乘法運算owo：
p.s.所有點都要用int()不然sage會抓Zmodp
像這樣：
image 

1
2
3
4
5
6
7
8
9
def mul_point(n, P):
    Q = P
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_point(R, Q)
        Q = add_point(Q, Q)
        n = n//2
    return R

密鑰共享：
image
Efficient Exchange:
就是透過x求y，蠻好懂ㄉ。 

1
2
3
4
5
q_x = 4726
nB = 6534
y_2 = (pow(q_x,3) + 497*q_x + 1768) % p
q_y = pow(y_2, (p+1)//4, p)
Q = (q_x, q_y)

DLP

基於ecc的離散對數問題

MOV Attack

link here
當p是質數的時候標準型可以用以下算法去解，你的order越smooth計算速度會越快。
如果今天公鑰的模不是質數，先分解之後CRT就好。
source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a=-104951229064556148327739944704067225950771091414555823142245215914591450861058912834056552784840698307176425328594627265181382568207073595237991025400591036568504091217142152714020714029902656538299906438142893329711443629030712718260179304547062440636851281426983383018754523639374608995894644699923989
b=330613225413866308562655832653992432640737790102976283577689980446254383044796881349939456563614098677350931763722745890480665024910308168117972351801983224014875943389010425754101569428868865308406299896128864429744942281764740765767448933787468732728303440425139427370295303413074468467311732278185653261247210818747688700223033416748171231713809540831008656574944346358659431821890836056720018803565200414398913172518371053256926775457844063169319469
q=359160846099444348290305694779134753321907709661985769865266028792407078112888527565129439985352509538424954784005539823019894001632619107445650921758147
E = EllipticCurve(GF(q), [a, b])
G=E(28607748532586155305766590971512659203413099194155217832119487667929904063769085772752568246866731921408737399300889149334418551010959577073796486388937480663378183502384364325599822278159619696537650011902619010103876865119734678532259458237178383683768508566703123494722154129671015135020887186845060 , 11556771936710627311327152614495265716197411903352782890022099742435127886458521280682189301147652900443377696183067981621473494668018204621652208514757)
C=E(26711100496576685119729576632487291804536666301038622556968335217486889947153426038920564765985480495027226192426180920889404710714177330897458470987192539137847486749759239413620141196304823376881474287741080498376534259054440609508444858615416246577282166556054773489020913794668822330843444608421730, 12165040241593082803221196359814491555817137316163617470672182014503810780161804477407976153593724606514937006081912866361176466134156934782183659322121025579094922887583052870888825027604616070534178050563950169432924241914421544127099391730894894981983461145749926628000691771375822508363489298910865)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []
for fac in primes:
    t = int(G.order()) // int(fac)
    dlog = discrete_log(t*C,t*G,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order

l = crt(dlogs,primes)
print(l)

Pohlig-Hellman

sage裡面的discrete_log是基於Pohlig-Hellman和BSGS，所以用discrete_log即可實現。

1
discrete_log(A, G, G.order(), operation='+')

Smart’s Attack

當曲線的order=p時，基於 Hensel’s Lemma的攻擊方案
詳細證明可以去看：https://wstein.org/edu/2010/414/projects/novotney.pdf 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break
    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break
    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp
    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()
    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)