CRYPTOHACK-ELLIPTIC CURVES

椭圆曲线在公钥密码学中的应用最早是在1985年提出的。在抵御了数十年的攻击之后，从2005年左右开始，它们被广泛使用，与之前的公钥密码系统（如RSA）相比，它们提供了诸多优势。
较小的椭圆曲线（EC）密钥提供了更大的强度，256位EC密钥具有与3072位RSA密钥相同的安全级别。此外，使用这些密钥机型的某些操作（包括签名）在时间和内存方面可能更为有效。最后，由于ECC比RSA更复杂，它具有鼓励开发人员使用可信库而不是自行开发的较好效果。
下面这些挑战旨在让你对椭圆曲线密码学（ECC）背后的陷门函数有直观的理解；让你初步接触其背后的数学结构；并让你尝试破解像椭圆曲线数字签名算法（ECDSA）这样的流行方案。

BACKGROUND

Background Reading

椭圆曲线密码学（ECC）是一种非对称密码协议，与RSA和Diffie-Hellman（DH）一样，依赖于陷门函数。总结一下：陷门函数允许客户端通过执行数学运算来保护数据机密，这在计算上很容易做到，但目前被认为解密起来很难。
对于RSA来说，陷门函数依赖于分解大数的难度。对于Diffie-Hellman来说，陷门函数依赖于有限域中离散对数问题的难度。对于RSA和DH来说，贯穿协议脉络的操作对我们来说都很熟悉，乘法和取数字的幂是我们在学校中会学到的。这方面ECC脱颖而出，因为除非你正在寻找相关的信息，否则ECC中的组操作不会出现在你的生活中。

这里的讨论并不全面，对于真正想了解ECC的人，我推荐Ben Lynn的椭圆曲线笔记，以及Jeffrey Hoffstein、Jill Pipher、Joseph H.Silverman的教科书《数学密码学导论》。

让我们看看所说的椭圆曲线到底是什么来开始思考。我们将会学习魏尔施特拉斯(Weierstrass)方程，其形式如下
$$
E:Y^2=X^3+aX+b
$$
椭圆曲线有一个惊人的特性：我们可以定义一个算子，我们称之为“点加法”。此运算符在某条曲线上取两个点，并在曲线上产生第三个点。取椭圆曲线上的点集，点加法定义了一个阿贝尔(Abelian)群运算。

这里有很多可说的。让我们激励这一点！我们可以将点的标量乘法理解为同一点的重复点加法。$Q=[2]P=P+P$.原来标量乘法是一个陷门函数！ECC依赖于在已给出$Q$和$P$的$Q=[n]P$中找到$n$的难度。

那么，我们如何理解点加法呢？

从几何上讲，我们可以这样理解点加法$P+Q$。取一个椭圆曲线并沿曲线标记两点$P,Q$及其$x,y$坐标。画一条穿过两个点的直线。现在继续这条线，直到它第三次与你的曲线相交。标记这个新的交点$R$。最后，取$R$并沿$y$方向反射，生成$R^{\prime}=R(x,-y)$。这个点加的结果就是$P+Q=R^{\prime}$

如果我们想把两个相同的点像$P+P$这样加在一起呢？我们不能通过一个点绘制一条唯一的线，但我们可以通过计算该点处曲线的切线来选择一条唯一线。计算点$P$处的切线。继续这条线，直到它与点$R$处的曲线相交。像以前一样表示这一点：$P+P=R^{\prime}=R(x,-y)$

如果没有第三个交点怎么办？有时你会选择两个点$P,Q$，这条线就不会再与曲线相交了。在这种情况下，我们说这条线与点（$O$）相交，点是位于无穷远处每条垂直线末端的一个点。因此，椭圆曲线的点加法是在2D空间中定义的，其中一个附加点位于无穷远处。

下面是一个图表，作为理解这些不同情况的视觉辅助

image-20241118164305997

点$O$充当组中的恒等算子：$P+O=P$和$P+(-P)=O$

这就引出了定义椭圆曲线的问题。

定义：椭圆曲线E是Weierstrass方程的解集
$$
E:Y^2=X^3+aX+b
$$
与无穷远处的一个点$O$。参数$a,b$必须满足下述关系
$$
4a^3+27b^2\neq{O}
$$
以确保曲线上没有奇点。

形式上，设$E$为椭圆曲线，点加法具有以下性质

(a) P+O=O+P=P

(b) P+(-P)=O

(c) (P+Q)+R=P+(Q+R)

(d) P+Q=Q+P

在ECC中，我们研究有限域$\mathbb{F}_p$上的椭圆曲线。这意味着我们观察曲线对特征$p$的模，椭圆曲线将不再是曲线，而是一组$x,y$坐标为$\mathbb{F}_p$中整数的点。

以下入门挑战将带您完成ECC的计算，并让您习惯ECC构建的基本操作，玩得开心！

性质(d)表明点加法是可交换的。flag是我们给具有交换运算的群起的名字。

flag: crypto{Abelian}

STARTER

Point Negation

在背景部分，我们介绍了如何将椭圆曲线上的点加法视为阿贝尔群运算的基础知识。在这幅几何图中，我们允许曲线上的坐标是任何实数。

为了在密码环境中应用椭圆曲线，我们研究了在有限域$\mathbb{F}_p$中具有坐标的椭圆曲线。

我们仍然认为椭圆曲线的形式为$E:Y^{2}=X^3+aX+b$，并满足以下条件：$a,b\in{\mathbb{F}_p},4a^3+27b^2\neq{O}$

然而我们不再将椭圆曲线看作一个几何对象，而是一组被如下定义的点
$$
E(\mathbb{F}_p)={(x,y):x,y\in{\mathbb{F}}_p~satisfying~~y^2=x^3+ax+b}\cup{O}
$$

注意：我们在背景中介绍的所有内容仍然有效。群的恒等算子是无穷远处的点：$O$，加法定律不变。给定$E(\mathbb{F}_p)$中的两个点，加法将在$E(\mathbb{F}_p)$中生成另一个点。

对于Starter组中的所有挑战，我们将使用椭圆曲线
$$
E:Y^2=X^3+497X+1768\ mod\ 9739
$$
使用该曲线和点$P(8045,6936)$，找到点$Q(x,y)$使得$P+Q=O$

记住，我们现在在有限域中工作，所以你需要正确处理负数。

资料：

- The Animated Elliptic Curve: Visualizing Elliptic Curve Cryptography

WriteUp

$P+Q=O$，可知Q的x为8045，y为-6939，对9739取模得到2803。

flag: crypto{8045,2803}

Point Addition

在使用椭圆曲线密码学时，我们需要将点加在一起。在背景挑战中，我们通过几何方法找到了一条穿过两个点的线，找到了第三个交点，然后沿着y轴反射。

结果表明，存在一种计算椭圆曲线点加法的有效算法。

摘自Jeffrey Hoffstein、Jill Pipher、Joseph H.Silverman的《数学密码学导论》，以下算法将计算椭圆曲线上两点的加法

两点的点加法算法：$P+Q$

(a) 如果$P=O$，那么$P+Q=Q$

(b) 否则，如果$Q=O$，那么$P+Q=P$

(c) 否则，记$P=(x_1,y_1),\ Q=(x_2,y_2)$

(d) 如果$x_1=x_2,\ y_1=-y_2$，那么$P+Q=O$

(e) 否则：

​ (e1) 如果$P\neq{Q}:\lambda=(y_2-y_1)/(x_2-x_1)$

​ (e2) 如果$P=Q:\lambda=(3x^2_1+a)/2y_1$

(f) $x_3=\lambda^2-x_1-x_2$

(g) $y_3=\lambda(x_1-x_3)-y_1$

(h) $P+Q=(x_3,y_3)$

我们正在处理一个有限域，因此上述计算应该以$p$为模进行，我们不“除”整数，而是乘以一个数字的模逆。例如$5^{-1}\equiv{9}\ mod\ 11$

我们将使用以下椭圆曲线和素数：
$$
E:Y^2=X^3+497X+1768\ mod\ 9739
$$

你可以通过以下等式来测试你的算法：$X+Y=(1024,4440),X+X=(7284,2107)\ for\quad X=(5274,2841),Y=(8669,740)$

使用该曲线和点$P=(493,5564),Q=(1539,4742),R=(4403,5202)$，通过实现上述算法找到点$S(x,y)=P+P+Q+R$

在计算完$S$后，将坐标代入曲线以确保点$S$在$E(\mathbb{F}_p)$上

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
from sage.all import GF

class Point:
    def __init__(self, x, y, p):
        F = GF(p) # 定义有限域
        # 让x,y在有限域内运算
        self.x = F(x)
        self.y = F(y)
        self.modulus = p # 模数
        
def addition(p1: Point, p2: Point, a, b):
    x1 = p1.x
    y1 = p1.y
    x2 = p2.x
    y2 = p2.y
    if x1 == x2 and y1 == y2: # 如果P,Q重合
        d = (3*x1**2 + a) / (2*y1)
    else: # P,Q为不同两点
        d = (y2 - y1) / (x2 - x1)
    x = d**2 - x1 - x2
    y = d*(x1 - x) - y1
    return Point(x, y, p1.modulus)

X = Point(5274, 2841, 9739)
Y = Point(8669, 740, 9739)
XY = Point(1024, 4440, 9739)
XX = Point(7284, 2107, 9739)
assert addition(X, Y, 497, 1768).x == XY.x and addition(X, Y, 497, 1768).y == XY.y
assert addition(X, X, 497, 1768).x == XX.x and addition(X, X, 497, 1768).y == XX.y
P = Point(493, 5564, 9739)
Q = Point(1539, 4742, 9739)
R = Point(4403, 5202, 9739)
x1 = addition(P, P, 497, 1768)
x2 = addition(x1, Q, 497, 1768)
x3 = addition(x2, R, 497, 1768)
assert x3.y**2 == x3.x**3 + 497*x3.x + 1768
print('crypto{'+str(x3.x)+','+str(x3.y)+'}')
# crypto{4215,2162}

Scalar Multiplication

两点的标量乘法由重复加法定义：$[3]P=P+P+P$

在接下来的几个挑战中，我们将使用标量乘法在不安全的信道上创建共享密钥，类似于Diffie-Hellman挑战。

摘自Jeffrey Hoffstein、Jill Pipher、Joseph H.Silverman的《数学密码学导论》，以下算法将有效地计算椭圆曲线上一点的标量乘法

标量乘法的二重加法算法

输入：$P\in{E(\mathbb{F}_p)}$和一个整数$n>0$

输出：$Q=[n]P\in{E(\mathbb{F}_p)}$

  1. 设$Q=P\quad and\quad R=O$
  2. while循环 n > 0
  3. 如果$n\equiv{1}\ mod\ 2$，设$R=R+Q$
  4. 设$Q=[2]Q\quad and\quad n=\lfloor n/2 \rfloor$
  5. 如果$n>0$，继续第二步循环
  6. 返回点$R=[n]P$

这不是最有效的算法，有许多有趣的方法可以改进这种计算，但这对我们的工作来说已经足够了。

我们将使用以下椭圆曲线和素数：
$$
E:Y^2=X^3+497X+1768\ mod\ 9739
$$

你可以通过以下等式来测试你的算法：

$[1337]X=(1089,6931)\quad for\quad X=(5323,5438)$

使用该曲线和点$P=(2339,2213)$，通过实现上述算法找到点$Q(x,y)=[7863]P$

在计算完$Q$后，将坐标代入曲线以确保点$Q$在$E(\mathbb{F}_p)$上

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
from sage.all import GF

class Point:
    def __init__(self, x, y, p):
        F = GF(p) # 定义有限域
        # 让x,y在有限域内运算
        self.x = F(x)
        self.y = F(y)
        self.modulus = p # 模数
        
def addition(p1: Point, p2: Point, a, b):
    x1 = p1.x
    y1 = p1.y
    x2 = p2.x
    y2 = p2.y
    if x1 == x2 and y1 == y2: # 如果P,Q重合
        d = (3*x1**2 + a) / (2*y1)
    else: # P,Q为不同两点
        d = (y2 - y1) / (x2 - x1)
    x = d**2 - x1 - x2
    y = d*(x1 - x) - y1
    return Point(x, y, p1.modulus)

def Scalar_Multiplication(p: Point, n, a, b):
    q = p
    r = 0
    while n > 0:
        if n % 2 == 1:
            try:
                r = addition(r, q, a, b)
            except:
                r = q
        q = addition(q, q, a, b)
        n = n // 2
    return r

p = Point(2339, 2213, 9739)
s = Scalar_Multiplication(p, 7863, 497, 1768)
print('crypto{' + str(s.x) + ',' + str(s.y) + '}')
# crypto{9467,2742}

Curves and Logs

椭圆曲线离散对数问题（ECDLP）是找到一个整数$n$，使得$Q=[n]P$的问题。

就像我们遇到的离散对数问题一样，$E(\mathbb{F}_p)$中点的标量乘法似乎是一个很难解开的问题，当$P$生成一个大小为$q$的子群时，最有效的算法在$q^{1/2}$时间内运行。

这使其成为陷门函数的绝佳候选者。

Alice和Bob正在交谈，他们想创建一个共享密钥，这样他们就可以开始用一些对称的加密协议加密他们的消息。Alice和Bob不信任他们的连接，所以他们需要一种方法来创建其他人无法复制的密钥。

首先，Alice和Bob就曲线$E$、素数$p$和生成点$G$达成一致，生成素数阶$q$的子群$H=⟨G⟩$

在椭圆曲线密码学中，$G$的阶是素数是很重要的。构建安全曲线很复杂，建议使用预先构建的曲线，其中客户端会得到要使用的曲线、素数和生成器。

椭圆曲线Diffie-Hellman密钥交换过程如下：

  • Alice生成一个随机秘密整数$n_A$并计算$Q_A=[n_A]G$
  • Bob生成一个随机秘密整数$n_B$并计算$Q_B=[n_B]G$
  • Alice将$Q_A$发送给Bob，Bob将$Q_B$发送给Alice。由于ECDLP问题的难度，旁观者Eve无法在有效时间内计算$n_{A/B}$
  • Alice计算$[n_A]Q_B$，Bob计算$[n_B]Q_A$
  • 由标量乘法的可结合性，$S=[n_A]Q_B=[n_B]Q_A$
  • Alice和Bob能够使用$S$作为他们的共享秘密

使用曲线、素数和生成器：
$$
E:Y^2=X^3+497X+1768\ mod\ 9739,\quad G:(1804,5368)
$$
当Alice发送给你$Q_A=(815,3190)$后，用你的秘密整数$n_B=1829$计算共享秘密。

通过计算$x$坐标的SHA1哈希生成密钥（取坐标的整数表示并将其转换为字符串）。flag就是你找到的十六进制摘要。

这条曲线不是加密安全的！！我们为这些初学者挑战选择了一个小素数，以便在学习时保持一切快速。加密安全曲线具有比特大小≈256的素数

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
from sage.all import GF
import hashlib

class Point:
    def __init__(self, x, y, p):
        F = GF(p) # 定义有限域
        # 让x,y在有限域内运算
        self.x = F(x)
        self.y = F(y)
        self.modulus = p # 模数
        
def addition(p1: Point, p2: Point, a, b):
    x1 = p1.x
    y1 = p1.y
    x2 = p2.x
    y2 = p2.y
    if x1 == x2 and y1 == y2: # 如果P,Q重合
        d = (3*x1**2 + a) / (2*y1)
    else: # P,Q为不同两点
        d = (y2 - y1) / (x2 - x1)
    x = d**2 - x1 - x2
    y = d*(x1 - x) - y1
    return Point(x, y, p1.modulus)

def Scalar_Multiplication(p: Point, n, a, b):
    q = p
    r = 0
    while n > 0:
        if n % 2 == 1:
            try:
                r = addition(r, q, a, b)
            except:
                r = q
        q = addition(q, q, a, b)
        n = n // 2
    return r

qa = Point(815, 3190, 9739)
s = Scalar_Multiplication(qa, 1829, 497, 1768)
x_str = str(s.x)
hash_object = hashlib.sha1(x_str.encode())
sha1_hash = hash_object.hexdigest()
print('crypto{' + sha1_hash + '}')
# crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}

Efficient Exchange

Alice和Bob正在研究椭圆曲线离散对数问题，并思考他们发送的数据。

他们希望尽可能保持数据传输的效率，并意识到不需要同时发送公钥的$x$和$y$坐标。

只要Alice和Bob在曲线参数上达成一致，对于给定的$x$，$y$只有两个可能的值。

事实上，给定他们接收到的$x$值中允许的$y$值，他们共享秘密的$x$坐标将是相同的。

对于这些挑战，我们使用了素数$p≡3\ mod\ 4$，这将帮助你从$y^2$中找到y

使用曲线、素数和生成器：
$$
E:Y^2=X^3+497X+1768\ mod\ 9739,\quad G:(1804,5368)
$$
在Alice发送给你$x(Q_A)=4726$后用你的秘密整数$n_B=6534$计算出共享秘密值。

使用decrypt.py文件来解码flag

{‘iv’: ‘cd9da9f1c60925922377ea952afc212c’, ‘encrypted_flag’: ‘febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8’}

您可以通过只发送一个位来指定公共$y$坐标取了两个可能值中的哪一个。试着想想如何做到这一点。这两个$y$值是如何相互关联的？

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
from sage.all import GF
from sympy.ntheory import sqrt_mod
import hashlib

class Point:
    def __init__(self, x, y, p):
        F = GF(p) # 定义有限域
        # 让x,y在有限域内运算
        self.x = F(x)
        self.y = F(y)
        self.modulus = p # 模数
        
def addition(p1: Point, p2: Point, a, b):
    x1 = p1.x
    y1 = p1.y
    x2 = p2.x
    y2 = p2.y
    if x1 == x2 and y1 == y2: # 如果P,Q重合
        d = (3*x1**2 + a) / (2*y1)
    else: # P,Q为不同两点
        d = (y2 - y1) / (x2 - x1)
    x = d**2 - x1 - x2
    y = d*(x1 - x) - y1
    return Point(x, y, p1.modulus)

def Scalar_Multiplication(p: Point, n, a, b):
    q = p
    r = 0
    while n > 0:
        if n % 2 == 1:
            try:
                r = addition(r, q, a, b)
            except:
                r = q
        q = addition(q, q, a, b)
        n = n // 2
    return r

x = 4726
n_b = 6534

[y1,y2] = sqrt_mod(x**3 + 497*x + 1768, 9739, True)
p1 = Point(x, y1, 9739)
p2 = Point(x, y2, 9739)
a1 = Scalar_Multiplication(p1, n_b, 497, 1768)
a2 = Scalar_Multiplication(p2, n_b, 497, 1768)
print(a1.x, a1.y, a2.x, a2.y)
# 1791 7558 1791 2181
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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


shared_secret = 1791
iv = 'cd9da9f1c60925922377ea952afc212c'
ciphertext = 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'

print(decrypt_flag(shared_secret, iv, ciphertext))
# crypto{3ff1c1ent_k3y_3xch4ng3}