ECC浅析和在ctf中的应用
字数 991 2025-08-06 23:10:27

ECC浅析及其在CTF中的应用

1. 椭圆曲线密码学(ECC)概述

英文全称: Elliptic Curve Cryptography

主要优势:

  • 较短的密钥长度可提供与RSA相当的安全性
  • 一般认为160位ECC密钥强度相当于1024位RSA密钥
  • 优势：加解密速度快、节省能源、带宽和存储空间
  • 应用实例：比特币(256位ECC)、中国二代身份证(256位ECC)

2. ECC数学基础

2.1 椭圆曲线定义

标准椭圆曲线方程：

y² = x³ + ax + b

其中a、b满足：

4a³ + 27b² ≠ 0

(避免奇点/不可导点)

2.2 椭圆曲线离散对数问题(ECDLP)

核心安全基础：

Q = kP
  • Q和P是椭圆曲线上的点
  • k是一个大整数(私钥)
  • 已知k和P求Q容易
  • 已知Q和P求k困难(ECDLP)

3. ECC加解密流程

3.1 密钥生成

  1. 选择椭圆曲线Ep(a,b)和基点P
  2. 选择大数k作为私钥
  3. 计算公钥Q = kP

3.2 加密过程

  1. 选择随机数r
  2. 生成密文C = (rP, M + rQ)

3.3 解密过程

M + rQ - k(rP) = M + rkP - krP = M

4. 有限域上的椭圆曲线

4.1 有限域概念

  • 域：支持加减乘除运算的集合
  • 有限域：元素个数有限的域
  • 阶：有限域中元素的个数，必须是质数的幂(pⁿ)

4.2 椭圆曲线在有限域上的表示

  • 对计算结果模p(p为素数)
  • 满足交换律、结合律、分配律
  • 记作GF(pⁿ)

5. 椭圆曲线点运算

5.1 点加法(A+B)

给定A(x₁,y₁)和B(x₂,y₂)，计算C(x₃,y₃) = A + B：

λ = (y₂ - y₁)/(x₂ - x₁) mod p
x₃ = λ² - x₁ - x₂ mod p
y₃ = λ(x₁ - x₃) - y₁ mod p

5.2 点倍乘(2A)

给定A(x₁,y₁)，计算2A：

λ = (3x₁² + a)/(2y₁) mod p
x₃ = λ² - 2x₁ mod p
y₃ = λ(x₁ - x₃) - y₁ mod p

6. CTF中的ECC-RSA混合题目分析

6.1 题目背景

  • 使用P521曲线生成RSA的素数p和q
  • p和q是椭圆曲线上的点Q的x和y坐标
  • Q = sG，其中s是私钥

6.2 解题思路

  1. 建立方程：

    • 已知Q在椭圆曲线上：y² ≡ x³ + ax + b mod p
    • 题目中p和q是Q的x和y坐标
    • 因此有：q² ≡ p³ + ap + b mod P

  2. 结合RSA的n=pq：

    q = √(p³ + ap + b)
n = p√(p³ + ap + b)
n² = p²(p³ + ap + b)
p⁵ + ap³ + bp² - n² ≡ 0 mod P

  3. 使用Sage求解：

a = -0x3
b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
P = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PR.<x> = PolynomialRing(Zmod(P))
f = x^5 + a*x^3 + b*x^2 - n^2
roots = f.roots()
print(roots)
  1. RSA解密：
import gmpy2
from Crypto.Util.number import *

n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
p = 4573744216059593260686660411936793507327994800883645562370166075007970317346237399760397301505506131100113886281839847419425482918932436139080837246914736557
q = n//p
e = 65537
c = 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e

d = gmpy2.invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

7. 关键点总结

  1. ECC安全性基于椭圆曲线离散对数问题(ECDLP)
  2. 有限域上的椭圆曲线运算是ECC的基础
  3. 点加法和点倍乘是ECC的核心运算
  4. CTF中常结合ECC和RSA，需灵活运用代数关系
  5. Sage是解决ECC问题的强大工具
  6. 理解曲线参数(a,b,P,G)之间的关系至关重要
ECC浅析及其在CTF中的应用 1. 椭圆曲线密码学(ECC)概述 英文全称 : Elliptic Curve Cryptography 主要优势 : 较短的密钥长度可提供与RSA相当的安全性 一般认为160位ECC密钥强度相当于1024位RSA密钥 优势：加解密速度快、节省能源、带宽和存储空间 应用实例：比特币(256位ECC)、中国二代身份证(256位ECC) 2. ECC数学基础 2.1 椭圆曲线定义 标准椭圆曲线方程： 其中a、b满足： (避免奇点/不可导点) 2.2 椭圆曲线离散对数问题(ECDLP) 核心安全基础： Q和P是椭圆曲线上的点 k是一个大整数(私钥) 已知k和P求Q容易 已知Q和P求k困难(ECDLP) 3. ECC加解密流程 3.1 密钥生成 选择椭圆曲线Ep(a,b)和基点P 选择大数k作为私钥 计算公钥Q = kP 3.2 加密过程 选择随机数r 生成密文C = (rP, M + rQ) 3.3 解密过程 4. 有限域上的椭圆曲线 4.1 有限域概念 域：支持加减乘除运算的集合 有限域：元素个数有限的域 阶：有限域中元素的个数，必须是质数的幂(pⁿ) 4.2 椭圆曲线在有限域上的表示 对计算结果模p(p为素数) 满足交换律、结合律、分配律 记作GF(pⁿ) 5. 椭圆曲线点运算 5.1 点加法(A+B) 给定A(x₁,y₁)和B(x₂,y₂)，计算C(x₃,y₃) = A + B： 5.2 点倍乘(2A) 给定A(x₁,y₁)，计算2A： 6. CTF中的ECC-RSA混合题目分析 6.1 题目背景 使用P521曲线生成RSA的素数p和q p和q是椭圆曲线上的点Q的x和y坐标 Q = sG，其中s是私钥 6.2 解题思路 建立方程 ： 已知Q在椭圆曲线上：y² ≡ x³ + ax + b mod p 题目中p和q是Q的x和y坐标 因此有：q² ≡ p³ + ap + b mod P 结合RSA的n=pq ： 使用Sage求解 ： RSA解密 ： 7. 关键点总结 ECC安全性基于椭圆曲线离散对数问题(ECDLP) 有限域上的椭圆曲线运算是ECC的基础 点加法和点倍乘是ECC的核心运算 CTF中常结合ECC和RSA，需灵活运用代数关系 Sage是解决ECC问题的强大工具 理解曲线参数(a,b,P,G)之间的关系至关重要