等候大修。

射影平面

定义:平面上全体无穷远点与全体平常点构成射影平面。

定义平行线相交于无穷远点 $O_{\infin}$,使平面上任意两直线都有且仅有唯一的交点。

射影平面点:对普通平面上点 (x, y),令 x=X/Z, y=Y/Z, Z≠0, 则可投影为射影平面上的点 (X:Y:Z)。如 (1, 2) -> 形如 (Z:2Z:Z), Z≠0

无穷远点:Z=0

椭圆曲线

由韦尔斯特拉斯 (Weierstrass) 方程所确定的曲线。

描述方程类似于计算椭圆周长的方程,故得名。

\[Y^2Z+aXYZ+bYZ^2=X^3+cX^2Z+dXZ+eZ^3\\ y^2+axy+by=x^3+cx^2+dx+e\]
  1. 椭圆曲线方程是一个齐次方程
  2. 曲线上每个点都必须是非奇异的(光滑的), 即偏导数不同时为 0

定义椭圆曲线上的阿贝尔群

对于集合 G,有加法(乘法)运算,且具有以下性质:

任意取椭圆曲线上两点 P、Q(若 P、Q 两点重合,则作 P 点的切线),作直线交于椭圆曲线的另一点 R’,过 R’ 作 y 轴的平行线交于 R,定义 P + Q = R 。这样,加法的和也在椭圆曲线上,并同样具备加法的交换律、结合律。(P + Q + R’ = 0)

有限域椭圆曲线

椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,把椭圆曲线定义在有限域上。

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

常用方程(short Weierstrass 形式):$y^2=x^3+ax+b\ (a,b\in GF(p), \Delta = 4a^3+27b^2\ne 0)$

​ 附加条件确保 $x^3+ax+b=0$ 无重根,用来避免某些退化。

设 $P(x_1,y_1)$, $Q(x_2,y_2)$, $P\ne -Q$, 则对于 $P+Q=(x_3,y_3)$, 有: \(x_3\equiv \lambda ^2 - x_1-x_2\ (mod\ p)\\ y_3\equiv \lambda (x_1-x_3)-y_1\ (mod\ p)\\ \lambda = \begin{cases} { {y_2-y_1}\over{x_2-x_1} }, P \ne Q\\ { {3x_1 ^ 2 + a}\over {2y_1} }, P = Q \end{cases}\)

如果椭圆曲线上一点 P,存在最小的正整数 n 使得数乘 $nP=O_∞$ ,则将 n 称为 P 的阶;若 n 不存在,则 P 是无限阶的。

Hasse 的结果表明,$\mid E(F_{p^e})\mid = p^e + 1 - t,\mid t\mid \le 2\sqrt{p^e}$,即该曲线上的点数量接近 $p^e+1$。

Schoof 发现的算法可在 $log(p^e)$ 的多项式时间复杂度内计算 $\mid E(F_{p^e})\mid$,待补充

爱德华兹曲线

方程: $x^2+y^2=1+dx^2y^2,d \ne 0,1$,该曲线也可通过变量代换为 Weierstrass 形式。其上的加法定义为:$P+Q=({x_1y_2+x_2y_1\over 1+dx_1x_2y_1y_2},{y_1y_2-x_1x_2\over 1-dx_1x_2y_1y_2})$。无穷远点为 $\mathcal{O}=(0,1)$,某个点的逆为 $(-x_1,y_1)$。

Pairing

令 $G_0,G_1,G_T$ 为 三个素数阶为 $q$ 的循环群,其中生成元 $g_0\in G_0, g_1\in G_1$。一个配对就是说,有高效可计算的函数 $e: G_0 \times G_1 \rightarrow G_T$,且其满足如下属性:

  1. 双线性:对于所有 $u,u’ \in G_0, v,v’ \in G_1$,我们有:

    ​ $e(u+u’,v)=e(u,v)·e(u’,v)$ and the same for the right one.

  2. 非退化性:$\exists P\in G_0,Q\in G_1$ s.t. $e(P,Q)\ne 1$。

  3. 可计算性:存在一个快速算法,以计算 $\forall P\in G_1,Q\in G_2:e(P,Q)$。

其中 $G_0,G_1$ 被称为 pairing groups 而 $G_T$ 被称为 target group;当 $G_0=G_1$ 时,我们称之为对称配对。

由双线性,我们显然有 $e(g_0^\alpha, g_1^\beta)=e(g_0, g_1)^{\alpha·\beta}=e(g_0^\beta, g_1^\alpha)$

ECC Attack

Pohlig-Hellman

适用于 $ord(G) = \Pi p_i^ {e_i}$ 的情况

假设需要求解 I where Q = IG

  1. 求得 G 的阶 n
  2. 分解 n 得到 $n = \Pi p_i^ {e_i}$, 以上可以用 sage 完成
  3. 计算 $I_i\equiv I\ (mod\ p_i^ {e_i})$
    • 设 $I_i = z_0 +z_1 p_i + z_2 p_i^2 + …+z_{e-1}p_i^{e-1}$ ($z_j\in [0,p_i)$)
    • 设 $G_0 = {n\over p_i}G,Q_0 = {n\over p_i}Q$,则 $G_0$ 的阶为 $p_i$
    • 则 $Q_0 = {n\over p_i}Q={n\over p_i}(IG)=IG_0=z_0G_0$ ($ord(G_0)\ is\ p_i$)
    • $IG=Q\rightarrow I_iG=Q\rightarrow l_iG_0=Q_0\rightarrow (z_0 +z_1 p_i + z_2 p_i^2 + …+z_{e-1}p_i^{e-1})G_0=Q_0\rightarrow z_0G_0=Q_0$,枚举得到 $z_0$
    • 就得到了 $(z_1 p_i + z_2 p_i^2 + …+z_{e-1}p_i^{e-1})G_0=Q_0 - z_0G_0$ + 同理,要求得 $z_j$,只需求出 $ Q_j = {n\over p_I^{j+1} }(Q-z_0G-z_1p_iG-…-z_{j-1}p_i^{j-1} G)$,解 $Q_j=z_jG_0$ 即可。最后即得到 $I_i$
  4. 使用 CRT 得到 I

*实际操作中为了方便也可以直接将 $p_i^{e_i}$ 作为一个整体求 $z_0$

参考链接:

简析ECC攻击方法之Pohlig-Hellman

Weak Curves In Elliptic Curve Cryptography

No Correctness Check for Input Points

选择明文攻击,且不检测输入点的合法性(是否在给定曲线上)。

目标

我们能够输入多个 $P(x, y)$,返回 $Q$,目标是要拿到 $Q=xP$ 中的 $x$。

方案

  1. 随机生成点 $P$,直到 $ord(P)$ 有不同的小素数因子 $factor$。
  2. $P=(ord(P)//factor)*P$,这样一来 $ord’(P)=factor$。
  3. 输入 $P$,得到 $Q$,枚举 $x%factor$。
  4. CRT

Tips:小伙伴说 sage 求 order 时,如果曲线不对会报错;那么附上当时做这题(De1CTF - ECDH)的脚本部分。

x = 
y = 
q = 
a = 
# random P and given q, a
b = (y^2 - x^3 - a*x) % q
# we change it
ecc = EllipticCurve(GF(q), [a,b])
G = ecc(x,y)
ord = G.order()
# then we find small factor
print(G * (G.order() // factor) , factor)
# P' with ord(P')

SMART’S ATTACK

#E(Fp) = p

前置知识

HENSEL’S LEMMA(LIFTING)

若 $f$ 为整系数多项式,$p$ 为素数,若 $x_n\in \Z$ 满足: \(f(x_n)\equiv 0\ (mod\ p^n)\\ f'(x_n)\ne 0\ (mod\ p)\) 则有:$x_{n+1} \equiv x_n - f(x_n)f’(x_1)^{-1}\ (mod\ p^{n+1})$ 满足 $f(x_{n+1})\equiv 0\ (mod\ p^{n+1})$

proof

令 $y=-f(x_n)f’(x_n)^{-1}\ (mod\ p^{n+1})$,将 $f$ 在 $x_n$ 处泰勒展开,得:

$f(x_n+y)=f(x_n)+\sum\limits_{i=1}^{\infty}{f^{(i)}(x_n)\over i!}y^i$(把自变量从函数中分离出来)

显然 $\sum\limits_{i=2}^{\infty}{f^{(i)}(x_n)\over i!}y^i \equiv 0\ (mod\ p^{2n})$,则: \(f(x_n+y)\equiv f(x_n) + f'(x_n)y\equiv 0\ (mod\ p^{n+1})\\\) 又:$x_n\equiv x_1\ (mod\ p)$,故 $f’(x_n)^{-1}\equiv f’(x_1)^{-1}\ (mod\ p)$;因为 $p^n \mid f(x_n)$,故 $f(x_n)f’(x_n)^{-1}\equiv f(x_n)f’(x_1)^{-1}\ (mod\ p^{n+1})$。证毕。

($f’(x_n)^{-1}$ 一律指对于 $p^{n+1}$,而 $f’(x_1)^{-1}$ 一律对于 $p$)

P-ADIC NUMBERS

EC ElGamal

Generate

  1. 选定 $E_p(a,b)$ 及生成元 $G$
  2. 将明文信息 $m$ 通过编码嵌入椭圆曲线上的散点 $P_m$
  3. 私钥 $d$ 由服务端选定,公钥 $E=dG$

Encrypt

客户端随机选定 $k$, 密文对 $C_m = (kG, P_m + kE)$

Decrypt

服务端计算 $(P_m+kE)-d(kG)$

ElGamal

Generate

choose a prime p, and two random numbers g and x, compute $y = g^x\ (mod\ p)$

PubKey: (y,g,p)​ PriKey: x

Encrypt

choose random number k where gcd(k, p - 1) = 1​, compute $C_1=g^k\ (mod\ p), C_2 = y^k M\ (mod\ p)$

Decrypt

$M = {C_2\over {C_1^ x} }\ (mod\ p)$