ECC(椭圆曲线)

PARAMETER CHOICE（参数选择）

Exceptional Curves(非凡曲线)

求解题目的关键是解决 $public=k\ast G$ 的离散对数问题，已知量为 $public$ 和 $G$ 。

检测曲线可知： $E.order()=p$ 且 $E.order()$ 是素数，这样我们就无法使用 Pohlig-Hellman Algorithm 进行有效攻击，但是可以使用 Smart’s Attack 算法：

相关论文：https://wstein.org/edu/2010/414/projects/novotney.pdf

例题：

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

FLAG = b'crypto{??????????????????????}'

def gen_public_key():
    private = randint(1, E.order() - 1)
    public = G * private
    return(public, private)


def shared_secret(public_key, private_key):
    S = public_key * private_key
    return S.xy()[0]


def encrypt_flag(flag):
    # Bob's public key
    b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
    b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf
    B = E(b_x, b_y)
    # Calculate shared secret
    A, nA = gen_public_key()
    print(f'Public Key: {A}')
    secret = shared_secret(B, nA)
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(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 encryption to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


# Curve params
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece

# Define curve
E = EllipticCurve(GF(p), [a, b])

# Protect against Pohlig-Hellman Algorithm
assert is_prime(E.order())

# Create generator
G = E.gens()[0]
print(f'Generator: {G}')

encrypted_flag = encrypt_flag(FLAG)
print(encrypted_flag)

# Generator: (3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005 : 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850 : 1)
# Public Key: (4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865 : 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757 : 1)
# {'iv': '719700b2470525781cc844db1febd994', 'encrypted_flag': '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0'}

实现 EXP:

import hashlib

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import *
import gmpy2
from sage.all import EllipticCurve


def SmartAttack(G, P, p):
    """
    用于求解当 E(Fp) = p 时,P=kG ,私钥 k 的值
    :param G: 基点 
    :param P: 公钥
    :param p: 模数
    :return: 私钥 k
    """
    E = G.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(G.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == G.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == P.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)

def shared_secret(public_key, private_key):
    S = public_key * private_key
    return S.xy()[0]

# Bob's public key
b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf
# Curve params
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece


public = (
    4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865,
    2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)
# public = kG
E = EllipticCurve(GF(p), [a, b])
assert E.order() == p
G = E.gens()[0]
print(G)
public = E(public)
B = E(b_x, b_y)

k = SmartAttack(G, public, p)
print("k =",k)

secret = shared_secret(B, k)
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(secret).encode('ascii'))
key = sha1.digest()[:16]
data = {'iv': '719700b2470525781cc844db1febd994', 'encrypted_flag': '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0'}

iv = bytes.fromhex(data['iv'])
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(bytes.fromhex(data['encrypted_flag'])),16)
print(flag)

Micro Transmissions(微型传动装置)

$E.order()$ 可以被分解为多个小素数，所以可以用 Pohlig-Hellman Algorithm 进行有效攻击。

实现 EXP:

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

# Sending curve parameters:
a = 1
b = 4
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
G = (43190960452218023575787899214023014938926631792651638044680168600989609069200,
     20971936269255296908588589778128791635639992476076894152303569022736123671173)

a_x = 87360200456784002948566700858113190957688355783112995047798140117594305287669
b_x = 6082896373499126624029343293750138460137531774473450341235217699497602895121

# A_P = n_a*G
data = {'iv': 'ceb34a8c174d77136455971f08641cc5',
        'encrypted_flag': 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453'}
E = EllipticCurve(GF(p), [a, b])
G = E(G)
B = E.lift_x(b_x)
A = E.lift_x(a_x)
# shared_secret = gen_shared_secret(B, n_a)
print(A)

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))][:-2]  # 这一步对于小素数，如果大于我们求解的明文的话，可以省略较大的素数值，加速计算结果。

    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)
assert A == k * G
n_a = k
assert n_a.nbits() == 64
print(k)

shared_secret = (B * n_a).xy()[0]
print("shared_secret =",shared_secret)
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]

cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(data["iv"]))
flag = unpad(cipher.decrypt(bytes.fromhex(data["encrypted_flag"])),16)
print(flag)

Elliptic Nodes(曲线节点)

根据题目代码分析可知： $Q=flag\ast G$ ，$Q,G,p$ 为已知量，曲线参数 $a,b$ 为未知量。

曲线公式为：$y^2\equiv x^3+ax+b(modp)$

$Q,G$ 为曲线上的两点，所以利用曲线公式联立方程组可以求解 $a,b$ 的值

求解 $a,b$ 后根据椭圆曲线的判别式 $4a^3+27b^2=0$ 可知该曲线为奇异椭圆曲线。

相关知识点参考例题：5. 奇异椭圆曲线 DLP 和 奇异椭圆曲线

EXP:

from collections import namedtuple
from Crypto.Util.number import *
from gmpy2 import *

p = 4368590184733545720227961182704359358435747188309319510520316493183539079703
gx = 8742397231329873984594235438374590234800923467289367269837473862487362482
gy = 225987949353410341392975247044711665782695329311463646299187580326445253608
Q = (2582928974243465355371953056699793745022552378548418288211138499777818633265,
     2421683573446497972507172385881793260176370025964652384676141384239699096612)

Point = namedtuple("Point", "x y")
G = Point(gx, gy)
Q = Point(Q[0], Q[1])

# y^2 = x^3+ax+b
a = (G.y ^ 2 - Q.y ^ 2 - G.x ^ 3 + Q.x ^ 3) * pow(G.x - Q.x, -1, p)
b = G.y ^ 2 - G.x ^ 3 - a * G.x
assert pow(G.y, 2, p) == (G.x ^ 3 + a * G.x + b) % p
assert pow(Q.y, 2, p) == (Q.x ^ 3 + a * Q.x + b) % p
print("a =", a)
print("b =", b)


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 "[*] 为非奇异椭圆曲线!!!"


if __name__ == '__main__':
    a = 64186688762130075872648727143532923412208390610536286437268423112
    b = 32579945572763798990069104934898692239152360555014084068553395172709029894
    p = 4368590184733545720227961182704359358435747188309319510520316493183539079703
    Q = (2582928974243465355371953056699793745022552378548418288211138499777818633265,
         2421683573446497972507172385881793260176370025964652384676141384239699096612)

    k = attack_sigular_ECC(p, a, b, Q, G)
    print(long_to_bytes(k))

Moving Problems(移动问题)

考点：非超奇异椭圆曲线上的MOV攻击

知识点：

(非)超奇异椭圆曲线上的 MOV 攻击

超奇异椭圆曲线

EXP:

from sage.all import *
from Crypto.Cipher import AES
import hashlib
import time
from Crypto.Util.Padding import pad, unpad

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

    return flag

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值太大了！'

p = 1331169830894825846283645180581
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])

# 获取 Frobenius 映射的特征多项式
frobenius_poly = E.frobenius_polynomial()
print("曲线的 Frobenius 映射特征多项式为：", frobenius_poly)

# 计算 Frobenius trace t
t = E.trace_of_frobenius()
if t == 0:
    print("[*] 曲线为超奇异椭圆曲线！")
else:
    print("[*] 曲线为非超奇异椭圆曲线！")

# 基点
G = E.gens()[0]
n = G.order()
print("基点的阶 n =", n)
P1 = E(1110072782478160369250829345256, 800079550745409318906383650948)
P2 = E(1290982289093010194550717223760, 762857612860564354370535420319)

P = P1

start_time = time.time()
k = MOV_attack(P,G,n,p)
print("私钥 k =",k)

# 结束计时
end_time = time.time()
# 计算总运行时间
total_time = end_time - start_time
print(f"代码执行总耗时：{total_time:.2f} 秒")

data = {'iv': 'eac58c26203c04f68d63dc2c58d79aca', 'encrypted_flag': 'bb9ecbd3662d0671fd222ccb07e27b5500f304e3621a6f8e9c815bc8e4e6ee6ebc718ce9ca115cb4e41acb90dbcabb0d'}
flag = decrypt_flag((k*P2).xy()[0])
print(flag)

Real Curve Crypto(真实曲线加密)

SIGNATURES（签名）

Digestive

Curveball

ProSign 3

No Random, No Bias

EDWARDS CURVES（爱德华兹曲线）

Edwards Goes Degenerate

SIDE CHANNELS（旁道攻击）

Double and Broken