Posts 简析ECC攻击方法
Post
Cancel

简析ECC攻击方法

ECC (Elliptic Curve Cryptography)

1985年首次提出将椭圆曲线用于公钥密码学。在抵御数十年的攻击之后,他们从2005年左右开始开始广泛使用,与以前的RSA等公钥密码系统相比,具有许多优势。

较小的ECC密钥可提供更高的强度,而256位ECC密钥具有与3072位RSA密钥相同的安全级别。 此外,使用这些键的几种操作(包括签名)在时间和内存方面都可以更加高效。

关于ECC加密原理这里不再赘述,我们着重记住它的计算方法

计算方法

椭圆曲线Ep(a,b),p为质数,\(x,y \in [0,p-1]\)

\[y^2=x^3+ax+b \pmod{p}\]

其中满足约束条件 \(4a^3+27b^2 \neq 0 \pmod{p}\)

并且\(P(x_1,y_1)\),\(Q(x_2,y_2)\)与 \(R(x_3,y_3)\)有如下关系:

\[\begin{aligned} x_3 \equiv k^2-x_1-x_2 \pmod p\\ y_3 \equiv k(x_1-x_3)-y_1 \pmod p \end{aligned}\] \[\begin{aligned} 若 P = Q,则 k=\frac{3x_1^2+a}{2y_1} \pmod p\\ 若 P \neq Q, 则k=\frac{y_2-y_1}{x_2-x_1} \pmod p \end{aligned}\]

例如椭圆曲线E23(1,1)上两点P(3,10),Q(9,7),求:

  1. -P
  2. P+Q
  3. 2P

根据题目所知:\(E23(1,1) \Rightarrow y^2=x^3+x \pmod {23}\)

  1. \[-P = (3,-10 \pmod{23}) = (3,13)\]
  2. 先计算 k,因为 P和Q两点不一样即满足\(P \neq Q\)条件,那么

    \[\begin{aligned} k &=\frac{y_2-y_1}{x_2-x_1}=\frac{7-10}{9-3}=-2^{-1} \pmod {23}\\ &=-12 \pmod{23}\\ &=11 \end{aligned}\] \[\begin{aligned} \therefore P+Q &= (x_3,y_3)\\ &=(k^2-x_1-x_2 \pmod{p},k(x_1-x_3)-y_1 \pmod{p})\\ &=(11^2-3-9 \pmod{23},11\times(3-x_3)-10 \pmod{23})\\ &=(17,11\times(3-17)-10 \pmod{23})\\ &=(17,20) \end{aligned}\]
  3. 先计算 k,因为 P和Q两点一样即满足\(P = Q\)条件,那么

    \[\begin{aligned} k &=\frac{3x_1^2+a}{2y_1}=\frac{3 \times3^2+1}{2 \times 10}\pmod{23}\\ &=7\times 5^{-1} \pmod {23}\\ &=6 \end{aligned}\] \[\begin{aligned} \therefore 2P &= (x_3,y_3)\\ &=(k^2-x_1-x_2 \pmod{p},k(x_1-x_3)-y_1 \pmod{p})\\ &=(6^2-3-3 \pmod{23},6\times(3-x_3)-10 \pmod{23})\\ &=(7,6\times(3-7)-10 \pmod{23})\\ &=(7,12) \end{aligned}\]

使用ECC加密

在椭圆曲线Ep(a,b)上取两点K,G,其中\(K=kG\),k为小于n的整数,根据加法法则,给出k和G可以很容易计算出K,但给出K,G求k则十分困难,并且实际应用中p,n取值十分大。此外定义G为基点(base point),k为私钥(private key),K为公钥(public key)

通信过程

  1. 用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G

  2. 用户A选择一个私有密钥k,并生成公开密钥 K=kG

  3. 用户A将Ep(a,b)和点K,G传给用户B

  4. 用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M,并产生一个随机整数r(r<n)

  5. 用户B计算点 \(C_1 = M + rK\) 和\(C_2 = rG\)并将 \(C_1\) 、 \(C_2\) 传给用户A

  6. 用户A接到信息后,计算 \(C_1 − kC_2\),结果就是点M,再对点M进行解码即可得到明文

    \[\begin{aligned} C_1-kC_2 &= M+rK-krG\\ &=M+rkG-krG\\ &=M \end{aligned}\]

过程如下

1

Elliptic Curve Discrete Logarithm Problem (ECDLP,椭圆曲线离散对数问题)攻击方法:

  1. MOV attack (involves finding linearly independent points and calculating Weil pairing to reduce ECDLP to over finite field instead of group of points on elliptic curve)
  2. Pohlig-Hellman (reduces discrete logarithm calculations to prime subgroups of the order of P and uses Chinese Remainder Theorem to solve system of congruences for discrete logarithm of the whole order )

CTF 中的ECC题目

picoCTF ECC2

Use the Pohlig-Hellman algorithm to calculate Elliptic Curve Discrete Logarithm and recover scalar n used to arrive at point Q (n*P)

题目
Elliptic Curve: y^2 = x^3 + A*x + B mod M
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = *You can figure this out with the point below :)*

P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
n = *SECRET*
n*P = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)

n < 400000000000000000000000000000

Find n.
分析

已知 A、M、P和nP,想要解出n,前提是解出B,因此

\[\begin{aligned} y^2 = x^3+Ax+B \pmod {M}\\ B = y^2-x^3-Ax \pmod{M} \end{aligned}\]

使用 sage 计算B:

1
2
3
4
5
6
7
8
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785

P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
x,y=P[0],P[1]
B = (y^2-x^3-A*x) % M
print(B)
# 25255205054024371783896605039267101837972419055969636393425590261926131199030

现在知道了B,并且解n的问题实际是解决椭圆曲线离散对数问题(ECDLP)。根据之前的内容,将我们的椭圆曲线E的阶乘分解会发现许多小的素数,这表明Pohlig-Hellman是可行的

Ref.

This post is licensed under CC BY 4.0 by the author.