CryptoHack学习记录（三）

椭圆曲线密码

1985年首次提出将椭圆曲线用于公钥密码。在抵御了数十年的攻击之后，它们从2005年左右开始被广泛使用，与以前的公钥密码系统（如RSA）相比，它提供了一些好处。
较小的EC密钥具有更大的强度，256位EC密钥具有与3072位RSA密钥相同的安全级别。此外，使用这些密钥的几个操作（包括签名）在时间和内存方面都会更有效。
本课程旨在直观了解ECC背后的trapdoor功能；浸入其背后的数学结构中；打破像ECDSA这样的流行计划。

Background Reading

椭圆曲线密码（ECC）是一种非对称密码协议，与RSA和Diffie-Hellman（DH）一样，它依赖于trapdoor函数。
对于RSA，trapdoor函数依赖于分解大数的难度。对于Diffie-Hellman来说，陷门依赖于离散对数问题的硬度。对于RSA和DH来说，贯穿协议脉络的操作对我们来说都很熟悉。所以ECC脱颖而出，因为ECC中的组操作不会在生活中出现。

让我们从椭圆曲线的含义开始思考ECC，我们将研究魏尔斯特拉斯方程：

$$y^2=x^3+ax+b$$

椭圆曲线有一个惊人的特点：我们可以定义一个算子，我们称之为“点加法”。该运算符在某条曲线上取两个点，并在曲线上生成第三个点。取椭圆曲线上的一组点，点加法定义了阿贝尔群运算。

我们可以将点的标量乘法理解为同一点的重复点加法。$Q=2P=P+P$。原来标量乘法是一个trapdoor函数，ECC依赖于求$n$的硬度，使得给定$Q$和$P$时$Q＝nP$

那么如何理解点加法？

几何上，我们可以这样理解点加法$P+Q$。取一条椭圆曲线，用它们的$x,y$坐标标记曲线上的两个点$P,Q$。画一条穿过两个点的直线。现在继续直线，直到它第三次与曲线相交。标记这个新的交点$R$。最后，取R并沿y方向反射它，得到$R’=R(x,-y)$。点相加的结果是$P+Q=R’$
如果我们想把两个相同的点加在一起：$P+P$呢？我们无法通过一个点绘制唯一的直线，但我们可以通过计算该点处曲线的切线来选择唯一的直线。计算点$P$处的切线。继续延长，直到它与点R处的曲线相交。如前所述反射此点：$P+P=R’=R(x,-y)$
如果没有第三个交点会发生什么？有时你会选择两个点$P,Q$，这条线不会再碰到曲线。在这种情况下，我们说这条线与点$O$相交（点是位于无限远处每条垂直线末端的一个点）。因此，椭圆曲线的点添加是在2D空间中定义的，附加点位于无穷远处。

点$O$充当群的单位元：$P+O=P$和$P+(-P)=O$。
这就引出了定义椭圆曲线：椭圆曲线$E$是Weierstrass方程的解集。

$$E:y^2=x^3+ax+b$$

常数$a,b$必须满足以下关系以确保曲线上没有奇点（带有尖点或者交点）：

$$4a^3 + 27 b^2 ≠ 0$$

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

$P + O = O + P = P$
$P + (−P) = O$
$(P + Q) + R = P + (Q + R)$
$P + Q = Q + P$

在ECC中，我们研究有限域$F_p$上的椭圆曲线。这意味着我们以特征$p$为模来观察曲线，椭圆曲线将不再是曲线，而是$x,y$坐标在$F_p$中为整数的点的集合。
上面第四条性质表明点加法是可交换的，flag是我们给具有交换运算的群的名称。

群满足交换律，为阿贝尔群（Abelian）。

Point Negation

上文了解了如何将椭圆曲线上的点加法视为阿贝尔群运算的基础知识。在几何图中，我们允许曲线上的坐标为任何实数。
为了在密码设置中应用椭圆曲线，我们研究了在有限域Fp中具有坐标的椭圆曲线。
我们仍将考虑E形式的椭圆曲线：$y^2=x^3+ax+b$，其满足以下条件：$a,b∈F_p,4a^3+27b^2≠0$。然而，我们不再将椭圆曲线视为几何对象，而是由定义的一组点：

$$E(F_p) = \{(x,y) : x,y ∈ F_p, y^2 = x^3 + a x + b\} ∪ O$$

我们在背景中介绍的所有内容仍然有效。群的恒等式是无穷远处的点：O，加法定律不变。给定E（Fp）中的两点，加法定律将在E（Fp）中生成另一点。

对于初学者集合中的所有挑战，我们将使用椭圆曲线：
$E： y^2=x^3+497x+1768,p:9739$
使用上述曲线和点$P(8045,6936)$，找到点$Q(x,y)$，使$P+Q=O$。

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

$P+Q=O$，$Q=(-P)=(x,-y)=(8045,-6936)$

有限域为9739，对坐标进行取模：

得到$Q(8045,2803)$

Point Addition

在使用椭圆曲线密码时，我们需要一起添加点。在背景介绍中，我们通过找到一条穿过两个点的线，找到第三个交点，然后沿着y轴进行反射，以几何方式实现这一点。
结果表明，存在一种计算椭圆曲线的点加法律的有效算法。
以下算法将计算椭圆曲线上两点的相加：
两点相加算法：$P+Q$

如果$P=O$，则$P+Q=Q$
如果$Q=O$，则$P+Q=P$
否则，写入$P=(x_1,y_1$和Q=$(x_2,y_2)$
如果$x_1=x_2,y_1=−y_2$，则$P+Q=O$
否则：
如果$P≠Q:\ \ λ=\frac{y_2-y_1}{x_2-x_1}$
如果$P=Q:\ \ λ=\frac{3x_1^2+a}{2y_1}$
$x_3=λ^2−x_1−x_2,y_3=λ(x_1−x_3)−y_1$
$P+Q=(x_3,y_3)$

我们正在处理一个有限域，因此上述计算应在模p下进行，我们不“除以”整数，而是乘以数字的模逆。

我们将使用以下椭圆曲线和素数：$E: y^2=x^3+497x+1768,p: 9739$

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

计算$S$后，将坐标代入曲线。确保点$S$位于$E(F_p)$

可以通过确保$x+y=(1024,4440)$和$x+x=(7284,2107)$（对于$x=(5274,2841)$和$y=(8669,740)$）来测试算法。

根据上面的两点相加算法写程序：

import gmpy2

a=497
p=9739

def point_add(x1,y1,x2,y2):
    if x1==0 and y1==0:
        return x2%p,y2%p
    elif x2==0 and y2==0:
        return x1%p,y1%p
    else:
        if x1==x2 and y1==-y2:
            return 0,0
        elif x1==x2 and y1==y2:
            r=(3*pow(x1,2,p)+a)*gmpy2.invert((2*y1)%p,p)
        else:
            r=(y2-y1)%p*gmpy2.invert((x2-x1)%p,p)
        x3=r**2-x1-x2
        y3=r*(x1-x3)-y1
        return x3%p,y3%p
    
assert point_add(5274,2841,8669,740)==(1024,4440)
assert point_add(5274,2841,5274,2841)==(7284,2107)
a1,b1=point_add(493,5564,493,5564)
a2,b2=point_add(a1,b1,1539,4742)
a3,b3=point_add(a2,b2,4403,5202)
print(a3,b3)

Scalar Multiplication

两个点的标量乘法由重复加法定义：$3P=P+P+P$
在接下来的几个挑战中，我们将使用标量乘法在不安全的信道上创建共享秘密，类似于Diffie-Hellman。
以下算法将有效地计算椭圆曲线上一点的标量乘法：

倍加算法：

输入：$E$中的$P(F_p)$和$n>0$的整数：
1.设置$Q=P,R=O$。
2.当$n>0$时循环：
3.如果$n≡1 \bmod 2$，则设置$R=R+Q$
4.设置$Q=2Q,n=[\frac n 2]$
5.如果$n>0$，则在步骤2继续循环。
6.返回等于$nP$的点$R$。

这不是最有效的算法，有很多有趣的方法可以提高计算效率，但这对我们的工作来说已经足够了。

我们将使用以下椭圆曲线和素数：$E: y^2=x^3+497x+1768,p: 9739$

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

计算$Q$后，将坐标代入曲线，确保点$Q$在$E(F_p)$中。可以通过测试：$1337x=(1089,6931)$表示$x=(5323,5438)$来测试算法。

根据上面的算法写程序：

import gmpy2

a=497
p=9739

def point_add(x1,y1,x2,y2):
    if x1==0 and y1==0:
        return x2%p,y2%p
    elif x2==0 and y2==0:
        return x1%p,y1%p
    else:
        if x1==x2 and y1==-y2:
            return 0,0
        elif x1==x2 and y1==y2:
            r=(3*pow(x1,2,p)+a)*gmpy2.invert((2*y1)%p,p)
        else:
            r=(y2-y1)%p*gmpy2.invert((x2-x1)%p,p)
        x3=r**2-x1-x2
        y3=r*(x1-x3)-y1
        return x3%p,y3%p
    
def scalar_mul(x1,y1,n):
    x2,y2=0,0
    while n:
        if n%2==1:
            x2,y2=point_add(x2,y2,x1,y1)
        x1,y1=point_add(x1,y1,x1,y1)
        n=n//2
    return (x2,y2)

assert scalar_mul(5323,5438,1337)==(1089,6931)
print(scalar_mul(2339,2213,7863))

注意这里的加法也不是简单的坐标加减，也要使用两点相加算法。

Curves and Logs

椭圆曲线离散对数问题（ECDLP）是寻找整数$n$使得$Q=nP$的问题。
像我们遇到的离散对数问题一样，$E(F_p)$中一个点的标量乘法似乎是一个难以解决的问题。
这使得它成为trapdoor函数的绝佳候选。
Alice和Bob正在交谈，他们想创建一个共享的秘密，这样他们就可以开始使用某种对称加密协议对消息进行加密。
Alice和Bob不信任他们的联系，因此他们需要一种方法来创建别人无法复制的秘密。
Alice和Bob在曲线$E$、素数$p$和生成点$G$上达成一致。

在椭圆曲线密码学中，G的阶是素数是很重要的。构造安全曲线很复杂，建议使用预先构造的曲线，其中提供了要使用的曲线、素数和生成器。

Alice生成一个秘密随机整数$n_A$并计算$Q_A=n_AG$
Bob生成一个秘密随机整数$n_B$并计算$Q_B=n_BG$
Alice向Bob发送$Q_A$，Bob向Alice发送$Q_B$。由于ECDLP的硬度，旁观者Eve无法在合理的时间内计算$n_{A/B}$。
然后Alice计算$n_AQ_B$，Bob计算$n_BQ_A$
由于标量乘法的关联性，$S=n_AQ_B=n_BQ_A$
爱丽丝和鲍勃可以使用$S$作为他们的共同秘密。
使用曲线、素数和生成器：

$$E: y^2 = x^3 + 497 x + 1768, p: 9739, G: (1804,5368)$$

在Alice向你发送$Q_A=(815,3190)$后，用你的秘密整数$n_B=1829$计算共享秘密。
通过计算$x$坐标的SHA1哈希值生成密钥（取坐标的十进制表示形式并将其转换为字符串），flag是hexdigest：

import gmpy2
from Crypto.Hash import SHA1

a=497
p=9739

def point_add(x1,y1,x2,y2):
    if x1==0 and y1==0:
        return x2%p,y2%p
    elif x2==0 and y2==0:
        return x1%p,y1%p
    else:
        if x1==x2 and y1==-y2:
            return 0,0
        elif x1==x2 and y1==y2:
            r=(3*pow(x1,2,p)+a)*gmpy2.invert((2*y1)%p,p)
        else:
            r=(y2-y1)%p*gmpy2.invert((x2-x1)%p,p)
        x3=r**2-x1-x2
        y3=r*(x1-x3)-y1
        return x3%p,y3%p
    
def scalar_mul(x1,y1,n):
    x2,y2=0,0
    while n:
        if n%2==1:
            x2,y2=point_add(x2,y2,x1,y1)
        x1,y1=point_add(x1,y1,x1,y1)
        n=n//2
    return (x2,y2)

s=scalar_mul(815,3190,1829)
ss=SHA1.new()
ss.update(str(s[0]).encode())
print(ss.hexdigest())

Efficient Exchange

Alice和Bob正在研究椭圆曲线离散对数问题，并思考他们发送的数据。
他们希望尽可能保持数据传输的效率，并意识到不需要同时发送公钥的$x$和$y$坐标。
只要Alice和Bob在曲线参数上达成一致，给定的$x$只有两个可能的$y$值。
事实上，给定从他们接收的值$x$中允许的$y$值，他们共享秘密的$x$坐标将是相同的。

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

使用曲线、素数和生成器：

$$E: y^2 = x^3 + 497 x + 1768, p: 9739, G: (1804,5368)$$

在Alice发送给你$q_x=4726$后，用你的秘密整数$n_B=6534$计算共享秘密。
使用decrypt.py文件对flag进行解码：

可以通过只发送一位来指定公共$y$坐标的两个可能值中的哪一个，试着想想你该怎么做。这两个$y$值是如何相互关联的？

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 = ?
iv = 'cd9da9f1c60925922377ea952afc212c'
ciphertext = 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'

print(decrypt_flag(shared_secret, iv, ciphertext))

我们需要计算一下公共秘密，这里根据上面$p$的定义可以使用勒让德符号的相关知识求解二次剩余平方根：

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import gmpy2

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')

def point_add(x1,y1,x2,y2):
    if x1==0 and y1==0:
        return x2%p,y2%p
    elif x2==0 and y2==0:
        return x1%p,y1%p
    else:
        if x1==x2 and y1==-y2:
            return 0,0
        elif x1==x2 and y1==y2:
            r=(3*pow(x1,2,p)+a)*gmpy2.invert((2*y1)%p,p)
        else:
            r=(y2-y1)%p*gmpy2.invert((x2-x1)%p,p)
        x3=r**2-x1-x2
        y3=r*(x1-x3)-y1
        return x3%p,y3%p
    
def scalar_mul(x1,y1,n):
    x2,y2=0,0
    while n:
        if n%2==1:
            x2,y2=point_add(x2,y2,x1,y1)
        x1,y1=point_add(x1,y1,x1,y1)
        n=n//2
    return (x2,y2)

a=497
p=9739
x=4726
n=6534
iv='cd9da9f1c60925922377ea952afc212c'
ciphertext='febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'

y=pow(x**3+497*x+1768,(p+1)//4,p)
s1=scalar_mul(x,y,n)[0]
print(decrypt_flag(s1,iv,ciphertext))

Montgomery’s Ladder

这一类充满了椭圆曲线密码的不安全实现。选择不好的曲线会导致被攻击，但即使选择的曲线是安全的，也可以从设备中提取私钥！
学习私人信息的一种方法是通过旁道分析。在高级别上，使用秘密执行操作的系统可以通过诸如所花费的时间或电路所做的工作之类的数据泄露有关秘密的信息。
针对ECDSA签名的定时攻击可能会泄露有关随机数的信息，这与LadderLeak等复杂攻击一起可能会对协议造成致命影响。为了防止这种情况，已经做了很多工作，使椭圆曲线上的点的标量乘法在恒定时间内运行。
椭圆曲线上的点的标量乘法的恒定时间算法的一个关键组件基于蒙哥马利阶梯。在这个挑战中，目标是实现最基本的版本：群$E(F_p)$中的蒙哥马利二进制算法：

输入：$E$中的$P$和$L$位的整数$k=\sum 2^ik_i$，其中$k_{L-1}=1$
输出：$E$中的$[k]P$

将$(R_0,R_1)$设置为$(P,[2]P)$
对于$i=L-2$向下至$0$：
如果$k_i=0$，则将$(R_0,R_1)$设置为$([2]R_0,R_0+R_1)$
否则将$(R_0,R_1)$设置为$(R_0+R_1,[2]R_1)$
返回值$R_0$

我们将使用以下椭圆曲线和素数：

$$E: Y^2 = X^3 + 486662X^2 + X\ \ p: 2^{255} - 19$$

使用上述曲线和$G.x=9$的生成点，通过执行上述算法，找到点$Q=[0x1337c0decafe]G$的x坐标（十进制表示）。
这条曲线是蒙哥马利形式的，而不是像这些挑战中的许多曲线那样的魏尔斯特拉斯。尽管这条曲线可以映射到Weierstrass形式，并且可以重复使用旧的加倍和加法公式，但我们建议直接使用蒙哥马利曲线的公式：$By^2=x^3+Ax^2+x$。为了鼓励这一点，我们在仿射坐标中给出了曲线的加法和乘法公式。请参见蒙哥马利曲线和蒙哥马利阶梯，以获得一组在投影坐标系中美丽而快速的公式。

蒙哥马利曲线的加法公式（仿射）
输入：群$E(F_p)$中的$P,Q(P≠Q)$
输出：群$E(F_p)$中的$R=(P+Q)$
$α=\frac{y_2-y_1}{x_2-x_1}$
$x_3=Bα^2-A-x_1-x_2$
$y_3=α(x_1-x_3)-y_1$

蒙哥马利曲线的加倍公式（仿射）
输入：群$E(F_p)$中的$P$
输出：群$E(F_p)$中的$R=[2]P$
$α=\frac{3x^2_1+2Ax_1+1}{2By_1}$
$x_3=Bα^2-A-2x_1$
$y_3=α(x_1-x_3)-y_1$

注意，所有操作都是在$\bmod p$下执行的。

算法还没理解，暂时还没做出来。