ECCNotes3

huangx607087学习ECC的笔记3

0.About

一个密码学fw的学习笔记，很菜（

这一系列主要介绍几种ECC的加密方法，以及通过对RSA的类比，将RSA中常见的几种攻击方法应用于ECC上。

3月23日，自己进了X1c，感谢Am4师傅一路带我，自己后面要更加努力。然而自己还有6月的六级和期末考试，（我这个fw一定要过六级，期末考试一定要全过。。不过可以确定的是，自己会在暑假寻求一个突破。在9月能够成为Am4师傅那样（x

1.椭圆曲线上的除式

在椭圆曲线$y^2=x^3+ax+b$上，我们可以定义这样的除式：
$$
F_{-1},F_0,F_1,F_2,F_3=-1,0,1,2y,3x^4+6ax^2+12bx-a^2
$$

$$
F_4=4y(x^6+5ax^4+20bx^3-5a^2x^2-4abx-8b^2-a^3)
$$

$$
F_{2i}=F_{i+2}F_{i}^3-F_{i+1}^3F_{i-1}
$$

$$
F_{2i+1}=\dfrac{F_i(F_{i+2}F_{i-1}^2-F_{i-2}F^2_{i+1})}{2y}
$$

顺便我们在定义一下多项式$G,H$
$$
G_{i}=xF_i^2-F_{i+1}F_{i-1}
$$

$$
H_i=(F_{i+2}F_{i-1}^2-F_{i-2}F^2_{i+1}) /4y
$$

所以，我们可以得到以下的式子：
$$
mP=(\dfrac{G_m(P)}{F_m^2(P)},\dfrac{H_m(P)}{F_m^3(P)})
$$
而这个式子如果想实现的话，可以调用sagemath中的_multiple_x_numerator,_multiple_x_denominator两个函数来实现对$x$坐标的数乘的多项式（最终用$x$表示）

1
2
3
4
5
6
E=EllipticCurve(GF(10007),[5362,7045])
Fz=E._multiple_x_numerator(7)
Fz
'''
x^49 + 9573*x^47 + 1673*x^46 + 9230*x^45 + 7088*x^44 + 2559*x^43 + 1491*x^42 + 1730*x^41 + 1886*x^40 + 8655*x^39 + 9529*x^38 + 2785*x^37 + 3587*x^36 + 3847*x^35 + 3439*x^34 + 1171*x^33 + 7340*x^32 + 2033*x^31 + 5346*x^30 + 3021*x^29 + 6843*x^28 + 1123*x^27 + 6261*x^26 + 4150*x^25 + 5110*x^24 + 9659*x^23 + 8409*x^22 + 6218*x^21 + 1501*x^20 + 4233*x^19 + 4240*x^18 + 5172*x^17 + 2625*x^16 + 1767*x^15 + 5499*x^14 + 7768*x^13 + 308*x^12 + 1527*x^11 + 2631*x^10 + 6193*x^9 + 6584*x^8 + 9405*x^7 + 1509*x^6 + 7683*x^5 + 3994*x^4 + 8777*x^3 + 2600*x^2 + 3465*x + 993
'''

经过数据的观察可以看出，$mP$中$x$坐标的分子表达式次数总是$m^2$，分母次数总是$m^2-1$，这也印证了之前笔记1中提到的$\ln u$正比于$m^2$的结论。

一般情况下，对椭圆曲线上的点加密的时候，我们可以选择横坐标$x$，然后在椭圆曲线上找点。

我们可以选取一个整数$k$，明文$m$，我们可以计算$m^3+am+b$是否是模$q$的二次剩余。如果是的话，直接对结果开平方即可（见我之前数论笔记）。如果不是的话，我们计算$m+1$，直到找到符合的$m$值。根据二次剩余的分布可知，我们找不到的期望值为$\dfrac 1 {2^k}$。

2.几种ECC加密算法

之前我们讲过DH密钥交换和Elgamal加密系统，这里我们多介绍几个基于ECC的加密系统。

0x01 Demytko加密

1.加密

寻找两个大素数$p,q$，然后计算$n=pq$。然后确定椭圆曲线的系数$a,b$，并保证$\gcd(4a^3+27b^2,n)=1$。

然后我们计算$N_1,N_2,N_3,N_4=|E_p|,2p+2-N_1,|E_q|,2q+2-N_3$。 由于自己博客中某些符号无法打出来，因此我们借用符号$|D|$表示集合$D$中的元素个数而不是我打不出来的那个符号（因为打那个符号博客处理时会出严重问题导致markdown混乱

接着选取$e$保证$\gcd(e,N_i)=1$即可。其中$i$为$1$到$4$。同时计算$d_1,d_2,d_3,d_4$分别为$e$在模$\dfrac{N_1N_3}{\gcd(N_1N_3)},\dfrac{N_1N_4}{\gcd(N_1N_4)},\dfrac{N_2N_3}{\gcd(N_2N_3)},\dfrac{N_2N_4}{\gcd(N_2N_4)}$下的逆元。

计算出这些数值之后，我们把$n,e,u$作为公钥，$p,q,d_1,d_2,d_3,d_4$作为私钥。

加密时，选取点$P$满足其横坐标为$m$，然后计算$c=(eP)_x$。

2.解密

解密方计算$w=c^3+ac+b$，然后在$d_1$到$d_4$中选择一个这样的私钥用于解密，方法如下。为与分数的出发区分开，以下用$\mathrm{lgd}(\dfrac{a}{b})$来表示$a$是否是$b$的二次剩余，若是值为$1$，不是的话值为$-1$。相关内容可见0xGame Div 4。

$\mathrm{lgd}(\dfrac{w}{p})$ $\mathrm{lgd}(\dfrac{w}{q})$ 选取私钥$d$
$1$ $1$ $d_1$
$1$ $-1$ $d_2$
$-1$ $1$ $d_3$
$-1$ $-1$ $d_4$

然后选取点$Q$使得其横坐标为$c^3+ac+b$，然后计算$dQ$即可，其横坐标就是$m$。

为了快速地算出$|E_p|,|E_q|$，我们可以选取$p\equiv q\equiv 2 \pmod 3$且$a=0$或者$p\equiv q\equiv 3 \pmod 4$且$a=0$，那么$|E_p|=p+1,|E_q|=q+1$。

0x02 KMOV算法

1.加密

寻找两个大素数$p,q$，然后计算$n=pq$。然后确定椭圆曲线的系数$a,b$，并保证$\gcd(4a^3+27b^2,n)=1$。

然后计算$N_1,N_2=|E_p|,|E_q|$。并选择$e$使得$\gcd(e,N_1)=\gcd(e,N_2)=1$。同时计算$d$是$e$模$\dfrac{N_1N_2}{\gcd{N_1N_2}}$的逆元。

其中公钥为$n,e,a,b$，私钥为$p,q,d$。

加密时，直接计算$C=eP$的值即可。

2.解密

直接计算$dC=P$。

然而，这个加密算法有一个比较大的缺点，就是除非使用了特殊的曲线和特殊的素数，不然计算$|E_p|,|E_q|$式一件非常难的事情。因此，1991年有人对这个系统进行了改进，给出了KMOV91。

3.KMOV91

在KMOV91中，直接选取$p\equiv q\equiv 2 \pmod 3$，使得$N_1,N_2=p+1,q+1$。其中$n,e$为公钥，$p,q,d$为私钥。而使用椭圆曲线$y^2=x^3+b,b=P_y^2-P_x^3$。最后保证$P_x^3 \not \equiv P_y^2 \pmod n$即可进行加密。其他过程与原来一样。

3.近期CTF中基于椭圆曲线的攻击方法

1. ECC低指数广播攻击 NepCTF lowExpoent

0o01.分析题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#Sagemath
from Crypto.Util.number import *
from secret import flag
def Encrypt(e, nbits, msg):
    p, q = [getPrime(int(nbits)) for _ in range(2)]
    N = p*q
    x = int(msg)
    while True:
        a, b = [getRandomRange(1, N) for _ in range(2)]
        P.<Yp> = PolynomialRing(Zmod(p))
        fp = x^3 + a*x + b - Yp^2
        P.<Yq> = PolynomialRing(Zmod(q))
        fq = x^3 + a*x + b - Yq^2
        try:
            yp, yq = int(fp.roots()[0][0]), int(fq.roots()[0][0])
            y = crt([yp, yq], [p, q])
            E = EllipticCurve(IntegerModRing(N), [a, b])
            msg_point = E.point((x, y))
            Ep = EllipticCurve(IntegerModRing(p), [a, b])
            Eq = EllipticCurve(IntegerModRing(q), [a, b])
            N1 = Ep.order()
            N2 = 2*p+2-N1
            N3 = Eq.order()
            N4 = 2*q+2-N3
            d = {
                ( 1, 1): inverse_mod(e, lcm(N1, N3)),
                ( 1,-1): inverse_mod(e, lcm(N1, N4)),
                (-1, 1): inverse_mod(e, lcm(N2, N3)),
                (-1, -1): inverse_mod(e, lcm(N2, N4))
            }
            break
        except:
            pass
    cip_point = e*msg_point
    ciphertext = cip_point.xy()[0]
    privKey = (d, p, q)
    pubKey = (a, b, N)
    return (ciphertext, pubKey, privKey)
def Decrypt(ciphertext, pubKey, privKey):
    d, p, q = privKey
    a, b, N = pubKey
    x = ciphertext
    w = x^3 + a*x + b % N
    P.<Yp> = PolynomialRing(Zmod(p))
    fp = x^3 + a*x + b -Yp^2
    yp = fp.roots()[0][0]
    P.<Yq> = PolynomialRing(Zmod(q))
    fq = x^3 + a*x + b -Yq^2
    yq = fq.roots()[0][0]
    y = crt([int(yp), int(yq)], [p, q])
    E = EllipticCurve(IntegerModRing(N), [a, b])
    cip_point = E.point([x, y])
    legendre_symbol_p = legendre_symbol(w, p)
    legendre_symbol_q = legendre_symbol(w, q)
    msg_point = d[(legendre_symbol_p, legendre_symbol_q)]*cip_point
    return msg_point.xy()[0]
msg = bytes_to_long(flag)
f = open("data", "w")
for i in range(70):
    current_st = time()
    cipher = Encrypt(3, 256, msg)
    f.writelines("{}, {}, {}, {}\n".format(cipher[0],*cipher[1]))
f.close()

然后题目最终给出了$70$组不同的$(c,a,b,n)$的四元组，均为对同一明文$x$的加密。

那么这道题，我们可以首先构造关于$x$的多项式。我们刚才看到了，$F_3(x)=3x^4+6ax^2+12bx-a^2$，那么我们可以得到分子的值和分母的值
$$
G=x(3x^4+6ax^2+12bx-a^2)^2-8(x^3+ax+b)(x^6+5ax^4+20bx^3-5ax^2-4ab-8b^2-a^3)
$$

$$
F^2=(3x^4+6ax^2+12bx-a)^2
$$

然后我们由$c\equiv\dfrac G {F^2} \pmod n$，那么有$G-cF^2\equiv 0 \pmod n$。由于$F^2$是八次式，$G$是九次式，因此我们可以构造出$70$个九次式（不过最好保证构造出来的$G$均为monic，也就是最高次项九次项为$1$。

然后，我们继续类比RSA中低指数广播攻击的方法，可以分别对常数项到九次项分别进行中国剩余定理，并将所有的模数相乘，得到一个所有的系数都很大的一个多项式。（当然九次项系数还是$1$）。然后我们可以看到，这个$N=\prod_{i=1}^{70} n$，由于$n$的比特数大概是$512$，也就是$\ln n=355$，那么$\ln N=24842$，而我们需要密文的规模不超过$\ln m=355$。次数为$9$次式，因此根据Copeersmith定理：只要$\ln x<2760 $，就可以求出这个式子的一个根。很显然$m$的值是符合条件的。

因此这个过程就转化成了求多项式的小根，直接用small_roots就可以解出来了。不过Sagemath中的这些命令也并不是特别好用的我还是调程序调了半天。因此建议通过LLL算法手写一个求多项式小根的脚本。。。。。。

0o02.自己的exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#Sagemath
c=[]
a=[]
b=[]
n=[]
Fzlist=[]
Fmlist=[]
Dlist=[]
for i in range(70):
    R.<x>=PolynomialRing(Zmod(n[i]))
    Fz=x*(3*x^4+6*a[i]*x^2+12*b[i]*x-a[i]^2)^2-8*(x^3+a[i]*x+b[i])*(x^6+5*a[i]*x^4+20*b[i]*x^3-5*a[i]^2*x^2-4*a[i]*b[i]*x-8*b[i]^2-a[i]^3)
    Fm=(3*x^4+6*a[i]*x^2+12*b[i]*x-a[i]^2)^2
    Fzlist.append(Fz)
    Fmlist.append(Fm*c[i])
    Dlist.append(Fz-c[i]*Fm)
Crtlist=[[0 for _ in range(70)] for __ in range(10)]
for i in range(70):
    for j in range(10):
        Crtlist[j][i]=ZZ(Dlist[i][j])
A=[]
for i in range(10):
    A.append(CRT(Crtlist[i],n))
N=1
for i in n:
    N*=i
O.<y>=PolynomialRing(Zmod(N))
S=0
for i in range(10):
    S+=A[i]*y^i
print('Finding Roots')
oo,oooo,ooooo=1,2,3
S.small_roots(epsilon=1/16)
[3088969433059681806521206959873975785377227976800172674306727155831805513908352148702210247662586117242206183337522557]

0o03 出题人Am4的官方wp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from functools import reduce
from Crypto.Util.number import *
f = open("data", "r")
ciphertext = []
a, b, n = [], [], []
for i in range(70):
ci, ai, bi, ni = [int(num) for num in f.readline().strip().split(", ")]
ciphertext.append(ci)
a.append(ai)
b.append(bi)
n.append(ni)
e = 3
deg = 9
coeffi = []
for i in range(70):
E = EllipticCurve(IntegerModRing(n[i]), [a[i], b[i]])
P.<m> = PolynomialRing(Zmod(n[i]))
f = ciphertext[i]*E._multiple_x_denominator(e, m) -
E._multiple_x_numerator(e, m)
coeffi.append(f.coefficients(sparse=False))
large_coeffi = [crt([int(coeffi[j][i]) for j in range(70)], [n[j] for j in
range(70)]) for i in range(deg+1)]
N_bitlength = sum([n[i].bit_length() for i in range(70)])
min_n = min(n)
N = reduce(lambda x, y: x*y, n)
Sc = large_coeffivar("x")
assume(x, 'integer')
f =
Sc[9]*x^9+Sc[8]*x^8+Sc[7]*x^7+Sc[6]*x^6+Sc[5]*x^5+Sc[4]*x^4+Sc[3]*x^3+Sc[2]*x^2
+Sc[1]*x+Sc[0]
lat = []
lat.append([large_coeffi[i]*min_n**i for i in range(deg+1)]+[1/(deg+1)])
for i in range(deg+1):
lat.append([((min_n**j)*N if (i==j) else 0) for j in range(deg+1)]+[0])
Mat = matrix(lat)
Mat_LLL = Mat.LLL()
for lin in range(deg):
Sc = [int(i) for i in Mat_LLL[lin]]
Sc = [(Sc[i]//(min_n**i)) for i in range(deg+1)]
var("x")
assume(x, 'integer')
f =
Sc[9]*x^9+Sc[8]*x^8+Sc[7]*x^7+Sc[6]*x^6+Sc[5]*x^5+Sc[4]*x^4+Sc[3]*x^3+Sc[2]*x^2
+Sc[1]*x+Sc[0]
print(factor(f))
break
'''
m =
3088969433059681806521206959873975785377227976800172674306727155831805513908352
148702210247662586117242206183337522557
print(long_to_bytes(m))
'''

2.ECC上的相关明文攻击

0o01 分析题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#Sagemath
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, getRandomRange
from secret import flag
flag = bytes_to_long(flag)
p, q = [getPrime(int(256)) for _ in range(2)]
a, b = [getRandomRange(1, p*q) for _ in range(2)]
class Task():
    def __init__(self, a, b, p, q, e):
        self.p, self.q = p, q
        self.a, self.b = a, b
        self.N = self.p*self.q
        self.e = e
        self.Kbits = 8
        Ep = EllipticCurve(IntegerModRing(self.p), [self.a, self.b])
        Eq = EllipticCurve(IntegerModRing(self.q), [self.a, self.b])
        N1 = Ep.order()
        N2 = 2*self.p+2-N1
        N3 = Eq.order()
        N4 = 2*self.q+2-N3
        self.d = {
            ( 1, 1): inverse_mod(self.e, lcm(N1, N3)),
            ( 1,-1): inverse_mod(self.e, lcm(N1, N4)),
            (-1, 1): inverse_mod(self.e, lcm(N2, N3)),
            (-1, -1): inverse_mod(self.e, lcm(N2, N4))
        }
        self.E = EllipticCurve(IntegerModRing(self.N), [self.a, self.b])
    def Enc(self, plaintext):
        try:
            msg_point = self.msg_to_point(plaintext)
            cip_point = self.e*msg_point
            return cip_point.xy()[0]
        except:
            return None
    def Dec(self, ciphertext):
        x = ciphertext
        w = x^3 + self.a*x + self.b % self.N
        P.<Yp> = PolynomialRing(Zmod(self.p))
        fp = x^3 + self.a*x + self.b -Yp^2
        yp = fp.roots()[0][0]
        P.<Yq> = PolynomialRing(Zmod(self.q))
        fq = x^3 + self.a*x + self.b -Yq^2
        yq = fq.roots()[0][0]
        y = crt([int(yp), int(yq)], [self.p, self.q])
        cip_point = self.E.point([x, y])
        legendre_symbol_p = legendre_symbol(w, self.p)
        legendre_symbol_q = legendre_symbol(w, self.q)
        msg_point = self.d[(legendre_symbol_p, legendre_symbol_q)]*cip_point
        return msg_point.xy()[0] >> self.Kbits
    def msg_to_point(self, x, shift=False):
        if shift:
            x <<= self.Kbits
        checkPoint = None
        for i in range(2<<self.Kbits):
            P.<Yp> = PolynomialRing(Zmod(self.p))
            fp = x^3 + self.a*x + self.b - Yp^2
            P.<Yq> = PolynomialRing(Zmod(self.q))
            fq = x^3 + self.a*x + self.b - Yq^2
            try:
                yp, yq = int(fp.roots()[0][0]), int(fq.roots()[0][0])
                y = crt([yp, yq], [self.p, self.q])
                E = EllipticCurve(IntegerModRing(self.p*self.q), [self.a, self.b])
                checkPoint = E.point((x, y))
                break
            except:
                x += 1
        return checkPoint
delta = 28552609273
e = 137
cip = Task(a, b, p, q, e)
print(f"a = {a}")
print(f"b = {b}")
print(f"n = {p*q}")
plaintext1 = cip.msg_to_point(flag, shift=True).xy()[0]
ciphertext1 = cip.Enc(plaintext1)
print(f"ciphertext1 = {ciphertext1}")
plaintext2 = cip.msg_to_point(flag+delta, shift=True).xy()[0]
ciphertext2 = cip.Enc(plaintext2)
print(f"ciphertext2 = {ciphertext2}")
delta = plaintext2 - plaintext1
print(f"delta = {delta}")
# a = 4281014323581546488462714122303747203636223358897123235803046898862939653328802115362584316327572195541081125920528501180620492421895128401613948866529122
# b = 1504110610934153564757355169781343270879282969971532470271782059859117769089994716068562704547770368420258743734175281689611986131092394954948339191589449
# n = 6638798722521613809421411597209101115203859862340555482590990067056543831415553727351714220257486793657912537305448979625073630917241320204281256125412671
# ciphertext1 = 6327639450575093157999054915625304951894564605402541939450801256931875815282143921161475586010526883609974743159835451980804875847625527741681757415519394
# ciphertext2 = 3275348139763310265438126795688591830796510682708632201044899744259822398076574133105844638686347122066389056025294466297206704146167073441486603569471235
# delta = 7309467973885

很显然，这道题给出了$m$的明文和$m+d$的明文，加密指数为$137$，那么我们就可以用我们刚才提到的函数构造出多项式，然后求多项式的GCD来确定最后的根。

不过整个代码的实现还是挺困难的，因为里面的微操很多，比如要把求出来的多项式先转成list再转回多项式。不然程序运行会出现错误。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#Sagemath
a = 4281014323581546488462714122303747203636223358897123235803046898862939653328802115362584316327572195541081125920528501180620492421895128401613948866529122
b = 1504110610934153564757355169781343270879282969971532470271782059859117769089994716068562704547770368420258743734175281689611986131092394954948339191589449
n = 6638798722521613809421411597209101115203859862340555482590990067056543831415553727351714220257486793657912537305448979625073630917241320204281256125412671
c1= 6327639450575093157999054915625304951894564605402541939450801256931875815282143921161475586010526883609974743159835451980804875847625527741681757415519394
c2= 3275348139763310265438126795688591830796510682708632201044899744259822398076574133105844638686347122066389056025294466297206704146167073441486603569471235
d = 7309467973885
E=EllipticCurve(Zmod(n),[a,b])
Fz=E._multiple_x_numerator(137)
Fm=E._multiple_x_denominator(137)
print('[+] Proof Work Finished')
Fmlist=list(Fm)
Fzlist=list(Fz)
R.<t>=PolynomialRing(Zmod(n))
Fm1,Fm2,Fz1,Fz2=0,0,0,0
for i in range(len(Fmlist)):
    Fm1+=Fmlist[i]*(t^i)
    Fm2+=Fmlist[i]*((t+d)^i)
for i in range(len(Fzlist)):
    Fz1+=Fzlist[i]*(t^i)
    Fz2+=Fzlist[i]*((t+d)^i)
G1,G2=c1*Fm1-Fz1,c2*Fm2-Fz2
def gcdpro(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()
    #return -gcdpro(g1, g2)[0]
H=(gcdpro(G1,G2))
print(H)
from Crypto.Util.number import *
print(long_to_bytes(n-H[0]))
#b'DASCTF{692d49f84fe5497fa05d6e91a1cf4e3e}\x04'

当然，ECC中也可以通过使用共模攻击和RSA中的Coppersmith来出题。可以预测的是，到目前为止，CTF中ECC的题目的数量并不是特别多。这就。】说明了ECC有可能会成为后面CTF的一个出题热门点。

CTFSeason2
#Notes
ECCNotes3
http://example.com/2021/03/25/ECCNotes3/
作者
huangx607087
发布于
2021年3月25日
许可协议