Smart Attack

适用于 $p = \text{E.order()}$

脚本

def SmartAttack(P,Q,p):#Q==k*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)

Pohlig_Hellman Attack

适用于已知目标比特位，且阶数分解后有不必要的素因子

脚本

def Pohlig_Hellman(E,P,G):
    """
    :param E: 有限域Fp上的椭圆曲线 E
    :param P: 公钥 P=k*G
    :param G: 基点 G
    :return: 私钥 k
    """
    # 曲线基点的阶
    n = E.order()
    # 将椭圆曲线的阶分解为若干小素数
    factors, exponents = zip(*factor(n))
    print(factors)
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))]  # 这一步对于小素数，如果大于我们求解的明文的话，可以省略较大的素数值，加速计算结果。

    dlogs = []
    for fac in primes:
        t = int(int(n) // int(fac))
        # dlog为离散对数分解后对应的私钥值
        dlog = discrete_log(t * P, t * G, operation="+")
        dlogs += [dlog]
        print("factor: " + str(fac) + ", Discrete Log: " + str(dlog))  # calculates discrete logarithm for each prime order
    k = crt(dlogs, primes)  # 中国剩余定理
    return k

例题

Micro Transmissions

题目

from Crypto.Util.number import getPrime
from Crypto.Random import random
from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
import hashlib
FLAG = b"crypto{???????????????????}"
def gen_key_pair(G, nbits):
    n = random.getrandbits(nbits)
    P = n*G
    return P.xy()[0], n
def gen_shared_secret(P, n):
	S = n*P
	return S.xy()[0]
def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data
# Efficient key exchange
nbits = 64
pbits = 256
# Curve parameters
p = getPrime(pbits)
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
print(f"Sending curve parameters:")
print(f"{E}")
print(f"Generator point: {G}\n")
# Generate key pairs
ax, n_a = gen_key_pair(G, nbits)
bx, n_b = gen_key_pair(G, nbits)
print(f"Alice sends public key: {ax}")
print(f"Bob sends public key: {bx}\n")
# Calculate point from Bob
B = E.lift_x(bx)
# Encrypted flag with shared secret
shared_secret = gen_shared_secret(B,n_a)
encrypted_flag = encrypt_flag(shared_secret)
print(f"Alice sends encrypted_flag: {encrypted_flag}")
'''
Sending curve parameters:
Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 99061670249353652702595159229088680425828208953931838069069584252923270946291
Generator point: (43190960452218023575787899214023014938926631792651638044680168600989609069200 : 20971936269255296908588589778128791635639992476076894152303569022736123671173 : 1)
Alice sends public key: 87360200456784002948566700858113190957688355783112995047798140117594305287669
Bob sends public key: 6082896373499126624029343293750138460137531774473450341235217699497602895121
Alice sends encrypted_flag: {'iv': 'ceb34a8c174d77136455971f08641cc5', 'encrypted_flag': 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453'}
'''

分析

这里我们已知 $nbits=64$ ，而阶数分解之后得到7 · 11 · 17 · 191 · 317 · 331 · 5221385621<10> · 5397618469<10> · 210071842937040101<18> · 637807437018177170959577732683<30>，简要计算一下得到后三位可以不要。

from Crypto.Util.number import *
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
data = {'iv': 'ceb34a8c174d77136455971f08641cc5',
        'encrypted_flag': 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453'}
p=99061670249353652702595159229088680425828208953931838069069584252923270946291
a=1
b=4
E=EllipticCurve(GF(p),[a,b])
G=E(43190960452218023575787899214023014938926631792651638044680168600989609069200,20971936269255296908588589778128791635639992476076894152303569022736123671173)
A=E.lift_x(87360200456784002948566700858113190957688355783112995047798140117594305287669,all=true)[1]
B=E.lift_x(6082896373499126624029343293750138460137531774473450341235217699497602895121,all=true)[1]
#print(G.order())7 · 11 · 17 · 191 · 317 · 331 · 5221385621<10> · 5397618469<10> · 210071842937040101<18> · 637807437018177170959577732683<30>
#这里发现G的阶后两位素数特别大，但是我们求的n只有64位，所以用P-H优化。
def Pohlig_Hellman(E,P,G):
    """
    :param E: 有限域Fp上的椭圆曲线 E
    :param P: 公钥 P=k*G
    :param G: 基点 G
    :return: 私钥 k
    """
    # 曲线基点的阶
    n = E.order()
    # 将椭圆曲线的阶分解为若干小素数
    factors, exponents = zip(*factor(n))
    print(factors)
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-3]  # 这一步对于小素数，如果大于我们求解的明文的话，可以省略较大的素数值，加速计算结果。

    dlogs = []
    for fac in primes:
        t = int(int(n) // int(fac))
        # dlog为离散对数分解后对应的私钥值
        dlog = discrete_log(t * P, t * G, operation="+")
        dlogs += [dlog]
        print("factor: " + str(fac) + ", Discrete Log: " + str(dlog))  # calculates discrete logarithm for each prime order
    k = crt(dlogs, primes)  # 中国剩余定理
    return k
k=Pohlig_Hellman(E,A,G)
print(k)
x=(k*B).xy()[0]
print(x)

然后计算 $flag$ 即可。
注意这里的E.lift_x()函数，这个函数默认取负点。

1	A=E.lift_x(A_x,all=True)

这会得到一个点集，前一个是负点后一个是正点。(不过这里不知道为什么不能取负点)

奇异椭圆

适用于 $4a^3+27b^2\equiv0\pmod{p}$

计算log

脚本

def attack_sigular_ECC(p, a, b, Q, G):
    """
    用于解决奇异椭圆曲线上的离散对数问题 Q = k*G , 魏尔斯特拉斯曲线方程的一般形式为：y^2 = x^3+ax+b
    :param p: 有限域模 p
    :param a: 曲线参数 a
    :param b: 曲线参数 b
    :param Q: 公钥
    :param G: 基点
    :return: 返回私钥 k 值
    """
    print("[*] 尝试攻击奇异椭圆曲线!!!")
    # 判断曲线是否为奇异曲线
    if (4 * a ^ 3 + 27 * b ^ 2) % p == 0:
        print("[*] 为奇异椭圆曲线!!!")
        # 定义有限域 Fp 上的关于 x 的多项式
        PR.<x> = GF(p)[]
        f = x ^ 3 + a * x + b
        root = f.roots()  # x^3+ax+b = 0，求解x
        print("该曲线的根为：", root)
        for r in root:
            # 选择其中一个奇点
            x0 = r[0]
            # 将奇点平移到(0,0)
            f_ = f.subs(x=x + x0)
            equation = str(f_.factor())
            print("\n平移后的曲线方程为：y^2 =", equation)
            if "x^2" in equation:  # f_ = (x + C) * x^2
                # 其余所有在曲线上的点也需要平移
                Q_ = (Q[0] - x0, Q[1])
                G_ = (G[0] - x0, G[1])
                # 取曲线方程化简后的常数 C 值
                start_index = equation.find('+') + 1
                end_index = equation.find(')')
                C = int(equation[start_index:end_index])
                print("曲线方程化简后其中的常数 C =", C)
                # 将椭圆曲线上的点映射为有限域上的点，降低求解离散对数问题的复杂度
                alpha = GF(p)(C).square_root()
                Q_ = (Q_[1] + alpha * Q_[0]) * (Q_[1] - alpha * Q_[0]) ^ (-1) % p
                G_ = (G_[1] + alpha * G_[0]) * (G_[1] - alpha * G_[0]) ^ (-1) % p
                k = discrete_log(Q_, G_)
                print("[*] 攻击成功！！！")
                print("\n离散对数问题 Q = k*G 中私钥 k 值为：", k)
                return k
    else:
        return "[*] 为非奇异椭圆曲线!!!"

例题

Elliptic Nodes

题目

from secrets import a, b
from collections import namedtuple
from Crypto.Util.number import inverse, bytes_to_long
FLAG = b"crypto{???????????????????????}"
# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")
# The point at infinity (origin for the group law).
O = 'Origin'
def check_point(P):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p
def point_inverse(P):
    if P == O:
        return P
    return Point(P.x, -P.y % p)
def point_addition(P, Q):
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R
def double_and_add(P, n):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R
def public_key():
    d = bytes_to_long(FLAG)
    return double_and_add(G, d)
# Define the curve
p = 4368590184733545720227961182704359358435747188309319510520316493183539079703
gx = 8742397231329873984594235438374590234800923467289367269837473862487362482
gy = 225987949353410341392975247044711665782695329311463646299187580326445253608
G = Point(gx, gy)
Q = public_key()
print(Q)

分析

from collections import namedtuple
from Crypto.Util.number import *
from gmpy2 import *
Q_x=2582928974243465355371953056699793745022552378548418288211138499777818633265
Q_y=2421683573446497972507172385881793260176370025964652384676141384239699096612
G_x=8742397231329873984594235438374590234800923467289367269837473862487362482
G_y=225987949353410341392975247044711665782695329311463646299187580326445253608
p=4368590184733545720227961182704359358435747188309319510520316493183539079703
a=(G_y**2-Q_y**2+Q_x**3-G_x**3)*inverse_mod(G_x-Q_x,p)
b=(G_y**2-G_x**3-a*G_x)
assert (4*a**3+27*b**2)%p==0
Point = namedtuple("Point", "x y")
G=Point(G_x,G_y)
Q=Point(Q_x,Q_y)
k=attack_sigular_ECC(p,a,b,Q,G)
print(long_to_bytes(k))

Mov Attack

适用于嵌入度 $k \le 20$ 的情况

脚本

def MOV_attack(P, G, n, p):
    """
    求解(非)/超奇异椭圆曲线上的离散对数问题，P = k*G ,返回私钥 k 值
    :param P: 公钥
    :param G: 基点
    :param n: 基点G的阶,n = G.order
    :param p: 有限域 F_p
    :return: P = k*G 中的私钥 k
    """
    # 计算嵌入度
    k = 1
    while pow(p, k, n) != 1:
        k += 1
    if k <= 20:
        print(f'[*] 嵌入度 k 值为: {k} ,这个 DLP 问题能够转移到有限域 GF(p^{k}) 上')

        # 将椭圆曲线上的点映射到更大的有限域 F_p^k 上
        Ee = EllipticCurve(GF(p ^ k), [a, b])
        # 扩展有限域上的同一点
        Pe = Ee(P)
        Ge = Ee(G)

        # 取新曲线上的随机一点
        R = Ee.random_point()
        m = R.order()  # 阶
        d = gcd(m, G.order())
        # 计算Q点，其中Q的阶是M除以d的结果，确保Q的阶与G的阶相兼容。
        Q = (m // d) * R
        # 检查G的阶是否是Q的阶的整数倍，这是为了确保Weil对运算的正确性。
        assert G.order() / Q.order() in ZZ

        # 计算Weil配对
        # P_Q = Pe.weil_pairing(Q, G.order())
        # G_Q = Ge.weil_pairing(Q, G.order())

        # 计算Tate配对 (速度更快)
        P_Q = Pe.tate_pairing(Q, G.order(), k)
        G_Q = Ge.tate_pairing(Q, G.order(), k)
        print("[*] 启动 DLP 求解程序.......")

        na = P_Q.log(G_Q)
        return na
    else:
        return f'嵌入度 k 值为: {k} ,这个 k值太大了！'

杂题

Ellipse Curve Cryptography

题目

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import *
from hashlib import sha1
import random
import os
from collections import namedtuple
# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")
FLAG = b"crypto{????????????????????????????????}"  # REMOVE ME
def point_addition(P, Q):
    Rx = (P.x*Q.x + D*P.y*Q.y) % p
    Ry = (P.x*Q.y + P.y*Q.x) % p
    return Point(Rx, Ry)
def scalar_multiplication(P, n):
    Q = Point(1, 0)
    while n > 0:
        if n % 2 == 1:
            Q = point_addition(Q, P)
        P = point_addition(P, P)
        n = n//2
    return Q
def gen_keypair():
    private = random.randint(1, p-1)
    public = scalar_multiplication(G, private)
    return (public, private)
def gen_shared_secret(P, d):
    return scalar_multiplication(P, d).x
def encrypt_flag(shared_secret: int, flag: bytes):
    # Derive AES key from shared secret
    key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(flag, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data
# ================ #
# Curve parameters #
# ================ #
p = 173754216895752892448109692432341061254596347285717132408796456167143559
D = 529
G = Point(29394812077144852405795385333766317269085018265469771684226884125940148,94108086667844986046802106544375316173742538919949485639896613738390948)
A, n_a = gen_keypair()
B, n_b = gen_keypair()
assert (A.x**2 - D*A.y**2) % p == 1
assert (B.x**2 - D*B.y**2) % p == 1
print(f"Alice's public key: {A}")
print(f"Bob's public key: {B}")
shared_secret = gen_shared_secret(B, n_a)
flag_enc = encrypt_flag(shared_secret, FLAG)
print(f'Encrypted flag: {flag_enc}')
'''
Alice's public key: Point(x=155781055760279718382374741001148850818103179141959728567110540865590463, y=73794785561346677848810778233901832813072697504335306937799336126503714)
Bob's public key: Point(x=171226959585314864221294077932510094779925634276949970785138593200069419, y=54353971839516652938533335476115503436865545966356461292708042305317630)
Encrypted flag: {'iv': '64bc75c8b38017e1397c46f85d4e332b', 'encrypted_flag': '13e4d200708b786d8f7c3bd2dc5de0201f0d7879192e6603d7c5d6b963e1df2943e3ff75f7fda9c30a92171bbbc5acbf'}
'''

分析

从题目知道 $A,B$ 在 $x^2-Dy^2 = 1$ 这个双曲线上，然后定义了一个陌生的点加法。
可以先尝试多进行几次点加法感受一下。

p = 173754216895752892448109692432341061254596347285717132408796456167143559
D, Px, Py = GF(p)['D,x,y'].gens()
for j in range(1, 11):
    Qx, Qy = Px, Py   # 每次从 (x,y) 开始
    for i in range(1, j):  
        Rx = (Px * Qx + D * Py * Qy)
        Ry = (Px * Qy + Py * Qx)
        Qx, Qy = Rx, Ry
    print("x^", j, ":", Qx)
    print("y^", j, ":", Qy)
    print("*" * 100)

分析一下输出

\begin{aligned} x & \quad y \\ x^2 + Dy^2 & \quad 2xy \\ x^3 + 3Dxy^2 & \quad 3x^2y + Dy^3 \\ x^4 + 6Dx^2y^2 + D^2y^4 & \quad 4x^3y + 4Dy^3 \end{aligned}

如果对二项式展开熟悉的话会发现这里的系数就是二项式展开的系数，但是现在还拼不成一个二项式，需要我们对右边乘上一个 $\sqrt{D}$ 。

\begin{aligned} x & \quad \sqrt{D}y \\ x^2 + (\sqrt{D}y)^2 & \quad 2x\cdot \sqrt{D}y \\ x^3 + 3x(\sqrt{D}y)^2 & \quad 3x^2\cdot \sqrt{D}y + (\sqrt{D}y)^3 \\ x^4 + 6x^2(\sqrt{D}y)^2 + (\sqrt{D}y)^4 & \quad 4x^3\cdot \sqrt{D}y + 4(\sqrt{D}y)^3 \end{aligned}

于是就得到了 $(x+\sqrt{D}y)^i$ 的展开。

A=(155781055760279718382374741001148850818103179141959728567110540865590463, 73794785561346677848810778233901832813072697504335306937799336126503714)
B=(171226959585314864221294077932510094779925634276949970785138593200069419, 54353971839516652938533335476115503436865545966356461292708042305317630)
p=173754216895752892448109692432341061254596347285717132408796456167143559
D=529
G=(29394812077144852405795385333766317269085018265469771684226884125940148,
94108086667844986046802106544375316173742538919949485639896613738390948)
g=G[0]+23*G[1]
a=A[0]+23*A[1]
F=GF(p)
n_a=discrete_log(F(a),F(g))
print(n_a)

于是就能得到 $n_a$

from Crypto.Cipher import AES
from Crypto.Util.number import *
import hashlib
from collections import namedtuple
Point = namedtuple("Point", "x y")
def point_addition(P, Q):
    Rx = (P.x*Q.x + D*P.y*Q.y) % p
    Ry = (P.x*Q.y + P.y*Q.x) % p
    return Point(Rx, Ry)
def scalar_multiplication(P, n):
    Q = Point(1, 0)
    while n > 0:
        if n % 2 == 1:
            Q = point_addition(Q, P)
        P = point_addition(P, P)
        n = n//2
    return Q
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)
    print(plaintext)
p = 173754216895752892448109692432341061254596347285717132408796456167143559
D = 529
B=Point(171226959585314864221294077932510094779925634276949970785138593200069419,54353971839516652938533335476115503436865545966356461292708042305317630)
n_a=85659350935432836744105386596354218808820976897571304400328185351959247
K=scalar_multiplication(B,n_a)
shared_secret = K.x
iv = '64bc75c8b38017e1397c46f85d4e332b'
ciphertext = '13e4d200708b786d8f7c3bd2dc5de0201f0d7879192e6603d7c5d6b963e1df2943e3ff75f7fda9c30a92171bbbc5acbf'
decrypt_flag(shared_secret, iv, ciphertext)
#b'crypto{c0n1c_s3ct10n5_4r3_f1n1t3_gr0up5}\x08\x08\x08\x08\x08\x08\x08\x08'