ECC(持续更新🥱)

ECC

椭圆曲线密码学(Elliptic Curve Cryptography)，是一种基于椭圆曲线数学的公钥密码。

基于 ECC 的三大问题：密钥交换、数字签名、离散对数

椭圆曲线

椭圆曲线定义式：\(y^2\;=x^3+ax+b\)，（维尔斯特拉斯标准形式）

曲线的一般形式：\(y^2+a_1xy+a_3y\;=x^3+a_2x^2+a_4x+a_6\)

判别式\(\Delta=-16(4a^3+27b^2)\;mod\;p=0\)

曲线性质

椭圆曲线上的困难问题:\(Q=nP\)，给定椭圆曲线上\(P、Q\)两点，求\(n\)十分困难

point addition 点加法

沿曲线的 P + Q 两点画一条通过两点的直线。现在继续这条线，直到它第三次与你的曲线相交。最后在该点沿 y 轴的方向取反射。 \(P+Q+R'=0,R=P+Q,R'(x,-y)=R(x,y)\)

有限域

定义在有限域\(F_p\)上，零元是\(O\)

点的阶:对于椭圆曲线上一点\(P\)，若存在一个最小的正整数\(n\)，使得\(nP=O\)，则称\(n\)是点\(P\)的阶。

椭圆曲线的阶:每个在有限域上的椭圆曲线都由有限个点组成，有多少个点椭圆曲线的阶就是多少。

Sage 环境

在线环境https://sagecell.sagemath.org/

本地环境https://doc.sagemath.org/html/en/installation/index.html (推荐在 Linux 环境搭建)

基本语法https://www.osgeo.cn/sagemath/tutorial/index.html

简单运算

1
2
3
4
5
6
7
8
9
a = 497
b = 1768
p = 9739
E = EllipticCurve(GF(p), [a, b])
Q = E(1539, 4742)
R = E(4403,5202)
P = E(2339, 2213)
print(P+Q)
print(4*R)

ECDH（密钥交换）

ECDH 是椭圆曲线迪菲-赫尔曼秘钥交换（Elliptic Curve Diffie–Hellman key Exchange），主要是用来在一个不安全的通道中建立起安全的共有加密资料，一般来说交换的都是私钥。

算法交换过程

公有参数：\(p,g\)

Alice 私钥：大整数\(a\)

生成 Alice 公钥：\(A=g^a\;\mod\;p\)

Alice 将\(A,p,g\)传递给 Bob

Bob 私钥：大整数\(b\)

生成 Bob 公钥：\(B=g^b\;\mod\;p\)

Bob 计算公共密钥：\(K=A^b\;\mod\;p\)

Bob 将\(B,p,g\)传递给 Alice Alice 计算公共密钥：\(K=B^a\;\mod\;p\)

交换完成，二者协商出K公共密钥，并且未在传输过程中暴露 K。

An_der_schonen_Elliptische_Kurve

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
from secret import FLAG, ECDH_KEY_EXCHANGE
from Crypto.Cipher import AES
from hashlib import md5

import binascii

iv = urandom(16)


a = 14489
b = 10289
p = 7486573182795736771889604737751889118967735916352298289975055815020934891723453392369540853603360270847848895677903334441530052977221688450741083448029661

F = GF(p)
E = EllipticCurve(F, [a, b])

G = E.random_point()

my_private_key = random_prime(2^256)

shared, sender_public_key = ECDH_KEY_EXCHANGE(G, my_private_key)

key = md5(str(int(shared.xy()[0])).encode()).digest()

cipher = AES.new(key, AES.MODE_CBC, iv)
ciphretext = cipher.encrypt(FLAG)

print(a)
print(b)
print(p)
print(sender_public_key)
print(my_private_key)
print(ciphretext.hex())
print(iv.hex())

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# sage
a=14489
b=10289
p=7486573182795736771889604737751889118967735916352298289975055815020934891723453392369540853603360270847848895677903334441530052977221688450741083448029661
F=GF(p)
E=EllipticCurve(F,[a,b])
sender_public_key=E([1285788649714386836892440333012889444698233333809489364474616947934542770724999997145538088456652601147045234490019282952264340541239682982255115303711207,1081635450946385063319483423983665253792071829707039194609541132041775615770167048603029155228167113450196436786905820356216200242445665942628721193713459])
my_private_key=2549545681219766023689977461986014915946503806253877534915175093306317852773
cipher="2f65ff4a97e0e05c06eab06b58ea38a3d5b6d2a65ea4907bc46493b30081a211d7cffc872a23dbd565ef307f9492bb23"
iv="d151c04c645c3e2a8d3f1ae44589ef20"
iv=bytes.fromhex(iv)
c=bytes.fromhex(cipher)

F = GF(p)
E = EllipticCurve(F, [a, b])

shared=sender_public_key*my_private_key

key = md5(str(int(shared.xy()[0])).encode()).digest()

cipher = AES.new(key, AES.MODE_CBC, iv)
m=cipher.decrypt(c)
print(m)

ECDSA（数字签名）

基于椭圆曲线的 DSA

场景

Alice 想要使用她的私钥\(d_A\)来签名，Bob 想用 Alice 的公钥 \(H_A\)要验证签名\(H_A=d_AG\)。 只有 Alice 才能提供正确的签名，而每个人都可以验证签名。

签名

1.选定一条椭圆曲线\(E_p(a,b)\)。

2.选取一个随机数\(k,1<k<n-1\)，\(n\)为椭圆曲线的阶。

3.选取椭圆曲线的基点\(G(a,b)\),计算 \(K=k * G(a,b)\)，令\(r=K[0]\mod n\)，即 r 是 K 点的横坐标（若 r 为 0，重新选 k 进行计算）。

4.计算明文 M 的哈希，令\(e=hash(M)\)，计算\(s=k^{-1}(z+rd_A)\mod n\)。

5.给出签名\((r,s)\)

验证

1.计算 \(u_1=s^{-1}z\mod n\)

2.计算 \(u_2=s^{-1}r\mod n\)

3.计算点\(P=u_1G+u_2H_A\)

当\(r=x_P\mod n\)时，签名验证成功。

DSA-LCG

试试这个

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
from hashlib import sha384, sha256
from Crypto.Util.number import inverse
from secret import k,privkey,flag
def sign(msg, privkey,k,order):
    e = int(sha384(msg).hexdigest(), 16)
    K = k*G
    r = int(K[0])
    k_ = inverse(k, order)
    s = k_ * (e + privkey * r) % order
    return r, s

q = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff
a = -3
b = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef
M = 8368031831458217786350512159882992957012870179737136526893923006288695827959478962195704930743648877201823593529339381563729143350454126812624495126388843
x = 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7
y = 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f
E = EllipticCurve(GF(q), [0,0,0,a, b])
G = E([x,y])
msg1=b'hello'
r1,s1=sign(msg1,privkey,k,q)
print("r1 =",r1)
print("s1 =",s1)
k2=(a*k+b) % M
msg2=b'world'
r2,s2=sign(msg2,privkey,k2,q)
print("r2 =",r2)
print("s2 =",s2)
key = sha256(str(privkey).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
ct = base64.b64encode(aes.encrypt(pad(flag, 16))).decode()

# r1 = 34007466611771601516061414360911609922088882193344157567527189819210008217689485940426747623610209785764754548617752
# s1 = 371900949338744788274672150932790711380367554085093925552194085487875492160150324907657343202698707270323127656622
# r2 = 38135753943982836042572890793143465851493833988864701898930580343563479696256688655279135669457443358334628248476702
# s2 = 31206970698882787218208833552853920421221998187963884172949797755468379329952479963343252649210115334349094354726288
# ct = "1Emwfale6VRBTlkcNZA3wiiNXrOqeifOC53/jXc+gT9Dv9r5I/q0EJKAgkt/sArW"

ECDLP（离散对数）

给定椭圆曲线 E，已知 P、Q 以及\(Q=kP\)，求 k。

1
2
3
4
E = EllipticCurve(GF(p), [a, b])
Q = E(x1,y1)
P = E(x2,y2)
k=P.discrete_log(Q)

PH 光滑阶分解

crypto-sign-in-1(VNCTF2023)

一道 ECDLP 题目，当时想到使用Pohlig-Hellman算法，但是一直没能找到合适的 A、B 来确定 G 的阶 n，赛后看大佬 wp，果然是用 pwntools 远程多试几组 y1、y2，找到光滑的阶，从而解密成功。

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

from sympy.ntheory.residue_ntheory import nthroot_mod
from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randrange,choice
from hashlib import *
from secret import flag

import socketserver
import os
import signal
import string

table = string.ascii_letters+string.digits

nbit = 128

def pad(m,lenth):
    return m + bytes([i for i in range(lenth-int(len(m)%lenth))])

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b''):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        proof = (''.join([choice(table)for _ in range(20)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
        XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True

    def handle(self):
        proof = self.proof_of_work()
        if not proof:
            self.request.close()
        while 1:
            qa = randrange(0,2**31) * 2
            qb = getPrime(nbit - 32)
            if isPrime(qa * qb + 1):
                q = qa * qb + 1
                break

        for _ in range(len(b'vnctf2023') - 8):
            self.send(b"Send 2 `y' elements to me:  ")
            ans = self.recv()
            try:
                y1, y2 = [int(_) % q for _ in ans.split(b',')]
            except:
                self.send(b"Your parameters are not valid! Bye!!")
                break

            AA = (y1**2 - y2**2 - 2022**3 + 2023**3) * inverse(-1, q) % q
            BB = (y1**2 - 2022**3 - AA * 2022) % q

            def add(P,Q):
                if P[0] != Q[0] and P[1] != Q[1]:
                    t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
                else:
                    t = ((3*P[0]*P[0]+AA)*inverse(2*P[1],q))%q
                x3 = t*t - P[0] - Q[0]
                y3 = t*(P[0] - x3) - P[1]
                return (x3%q, y3%q)

            def mul(t, A, B=0):
                if not t: return B
                return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

            while 1:
                Gx = randrange(0,q - 1)
                try:
                    Gy = int(nthroot_mod((Gx**3 + AA * Gx + BB) % q,2,q))
                    assert (pow(Gy,2,q) == (Gx**3 + AA * Gx + BB) % q)
                    break
                except:
                    continue

            G = (Gx,Gy)
            m = randrange(0,q-1)
            C = mul(m,G)
            aes = AES.new(m.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16))
            enc_flag = aes.encrypt(pad(flag,16))

            self.send(b'The parameters and encrypted flag are:')
            self.send(b'q = ' + str(q).encode())
            self.send(b'G = ('+ str(Gx).encode() + b',' + str(Gy).encode() + b')')
            self.send(b'm * G = ('+ str(C[0]).encode() + b',' + str(C[1]).encode() + b')')
            self.send(b'encrypt flag = ' + enc_flag.hex().encode())
        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

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
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
#sage
from pwn import *
from itertools import product
import string
from hashlib import sha256
from random import getrandbits
from ast import literal_eval
from Crypto.Util.number import *
from Crypto.Cipher import AES

table = string.ascii_letters+string.digits

def set_connect_proof():
    io=remote('node4.buuoj.cn','25385')
    io.recvuntil(b"sha256(XXXX+")
    alphabet = string.ascii_letters + string.digits
    lattar_part=io.recv(16).decode('utf8')
    io.recvuntil(b'== ')
    h=io.recvline().strip().decode('utf8')
    # print(h)
    io.recvuntil(b'[+] Plz Tell Me XXXX :')
    bruteforce=[ ''.join(prefix)+lattar_part  for prefix in product(alphabet,repeat=4)]
    for proof in bruteforce:
        if sha256(proof.encode()).hexdigest()==h:
            io.sendline(proof.encode()[:4])
            print("proof done")
            return io

while True:
    io = set_connect_proof()
    io.recvuntil(b"Send 2 `y' elements to me:  ")
    y1,y2 = getrandbits(128),getrandbits(128)
    io.sendline(f'{str(y1)},{str(y2)}'.encode())
    q = int(io.recvline_contains(b'q = ').decode().strip()[4:])
    G = literal_eval(io.recvline_contains(b"G = ").decode().strip()[4:])
    mG = literal_eval(io.recvline_contains(b"m * G = ").decode().strip()[8:])
    encflag = io.recvline_contains(b'encrypt flag = ').decode().strip()[len(b'encrypt flag = '):]
    AA = (y1**2 - y2**2 - 2022**3 + 2023**3) * inverse(-1, q) % q
    BB = (y1**2 - 2022**3 - AA * 2022) % q
    E = EllipticCurve(GF(q), [AA, BB])
    g_order = E(G).order()
    order_ls = factor(g_order)
    print(f"[+] G order {order_ls}")
    sub_group_order = 1
    for p,e in order_ls:
        if p.nbits() <= 42:
            sub_group_order*= (p^e)
    expon = g_order//sub_group_order
    print(f"[+] {sub_group_order.nbits() = }")
    if sub_group_order.nbits() < 120:
        io.close()
        continue
    mm = discrete_log(expon*E(mG),expon*E(G),ord = sub_group_order,operation = "+")
    print(f"[+] subgroup dlp (m mod {sub_group_order}) = ", mm)
    io.close()
    break

aes = AES.new(int(mm).to_bytes(16, 'big'), AES.MODE_CBC, bytes(16))
flag = aes.decrypt(bytes.fromhex(encflag))
print(flag)

Singular Attack

利用曲线上的奇异点进行攻击，奇点就是该点导数不存在，或者导数为 0 但不是极值点。 若椭圆曲线的判别式\(\Delta=-16(4a^3+27b^2)\;mod\;p=0\)，说明该曲线有奇点。

RWCTF2023 体验赛

1
2
if u == w:
    m = (3*u*w + 4*u + 1) * i(v+x)

根据题目，可得到曲线关于 x 的导数，\(3x^2+4x+1\)，所以可得到方程为\(y^2=x^3+2x^2+x+C\)

题目已知点(4,10)在曲线上，代入得到 100 = 64 + 32 + 4 + C，即 C = 0，所以方程确定\(y^2=x^3+2x^2+x\)

方程左右求导得到\(2y \frac{dy}{dx}=3x^2+4x+1\)，所以当 y=0 时导数不存在，再把 y=0 代入方程，求得 x=-1，所以找到该曲线的奇点为(-1,0)。

下一步我们把曲线平移，使得曲线以(0,0)为奇点，得到y^2 = x^3 + 193387944202565886198256260591909756040*x^2，改写为y^2 = (x + 193387944202565886198256260591909756040) * x^2

因为193387944202565886198256260591909756040 = pow(89654903351345918131227153390056628523,2,p) 我们就可把 P、Q 点映射到乘法群上，从而进行简单的对数计算。

映射法则如下: \[(x,y)\rightarrow\frac{y+tx}{y-tx}\]

EXP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p=193387944202565886198256260591909756041
P.<x> = GF(p)[]
f = x^3 + 2*x^2 + x
P = (4, 10)
Q = (65639504587209705872811542111125696405, 125330437930804525313353306745824609665)
print(f)
f_ = f.subs(x=x-1)
print(f_)
print (f_.factor())
P_ = (P[0] +1, P[1])
Q_ = (Q[0] +1, Q[1])

t = GF(p)(193387944202565886198256260591909756040).square_root()
u = (P_[1] + t*P_[0])/(P_[1] - t*P_[0]) % p
v = (Q_[1] + t*Q_[0])/(Q_[1] - t*Q_[0]) % p
print (v.log(u))

CTF
ECC(持续更新🥱)
https://sch01ar.github.io/2023/04/19/ECC/
作者
Roo1e
发布于
2023年4月19日
许可协议