好乱..

射影平面

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

定义平行线相交于无穷远点 $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 = { {y_2-y_1}\over{x_2-x_1} }, P \ne Q\\ { {3x_1 ^ 2 + a}\over {2y_1} }, P = Q\)

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

统一地,

对于普遍形式,有: \(\lambda,\upsilon = { {y_2-y_1}\over{x_2-x_1} },{y_1x_2-y_2x_1\over x_2-x_1}, x_1 \ne x_2\\ { 3x_1 ^ 2 + 2a_2x_1+a_4-a_1y_1\over 2y_1+a_1x_1+a_3} , {-x_1^3+a_4x_1+2a_6-a_3y_1\over 2y_1+a_1x_1+a_3}, x_1 = x_2\) $-P=(x,-y-a_1x-a_3)$

当 $P_1\ne P_2$ 时,直线 $M:y=\lambda x + \upsilon$ 经过这两点;相等时 $M$ 即该点处的垂直线。

而 $P_3=P_1+P_2=(\lambda^2+a_1\lambda-a_2-x_1-x_2,-(\lambda+a_1)x_3-\upsilon-a_3)$。

Schoof’s algorithm

$F_q^$ 指有限域 $F_q$ 的单位群,其中 $q = p^r,r\ge 1$。该群中的 DLP 已经很困难了(最快:亚指数级别)。然而 Koblitz 和 Miller 尝试用 $E(F_q,+)$ 来代替 $F_q^$,以期更加困难的 DLP,这就导致了 ECC 的诞生。(Elliptic Curve 密码系统的安全性依赖于 ECDLP 的难度)

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

前置知识

Frobenius map:$\phi_q:\overline{F_q}\rightarrow \overline{F_q},x\rightarrow x^q$。

Frobenius map on an elliptic curve:$\phi_q:E(\overline{F_q})\rightarrow E(\overline{F_q}),(x,y)\rightarrow (x^q,y^q)$。

the trace of Frobenius at $q$:设为 $a:=q+1-#E(F_q)$。

Hasse’s Theorem:$E$ 是 $F_q$ 上的椭圆曲线,则 the trace of Frobenius 满足 $\mid a \mid < 2\sqrt{q}$。

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

Schoof’s algorithm

1985年,Schoof 在他的 paper 中描述了一个计算群阶的算法,时间复杂度为 $O(log^8(q))$。

Schoof’s algorithm:(关键在于中国剩余定理)

输入:椭圆曲线 $E:y^2=x^3+Ax+B$ over $F_q$, $q=p^r$;

输出:$#E(F_q)$.

  1. 选择一系列小素数 $S={2,3,5,…,L}$,$p\notin S,\prod\limits_{l\in S}l>4\sqrt{q}$;
  2. 令 $a=q+1-#E(F_q)\in \Z$。用一 sub-algorithm 计算出所有的 $a\ mod\ l\in S$;
  3. 使用中国剩余定理计算出 $a\ mod\ \prod l$,确定满足该同余式的 $a\in \Z,\mid a\mid \le 2\sqrt{q}$;
  4. 输出 $#E(F_q)=q+1-a$。

输入:椭圆曲线 $E:y^2=x^3+Ax+B$ over $F_q$, $q=p^r$、一素数 $l\ne p$;

输出:$(a\ mod\ l)$.

  1. 若 $gcd(x^3+Ax+B,x^q-x)\ne 1$ 则 $a\equiv 0\ mod\ 2$,否则 $a\equiv 1\ mod\ 2$;
  2. 若 $l$ 为奇素数,则:(设 $q_l\equiv q\ (mod\ l),\mid q_l\mid <{l\over 2}$)
    1. 计算横坐标:$(x’,y’)=(x^{q^2},y^{q^2})+q_l(x,y)\ mod\ \phi_l$;
    2. 对于 $j=1,2,…,(l-1)/2$:
      1. 计算 $(x_j,y_j)=j(x,y)$ 的横坐标 $x_k$;
      2. 若 $x’-x^q-j\equiv 0\ (mod\ \psi_l)$,继续第 3 步;否则尝试下一个 $j$,若均被尝试过,则跳过;
      3. 计算 $y’,y_j$,如果 $(y’-y_j^q)/y\equiv 0\ (mod\ \phi_l)$,则 $a\equiv j\ (mod\ l)$;否则 $a\equiv -j\ (mod\ l)$。
    3. 若所有 $j$ 都尝试失败了,则令 $w^2\equiv q\ (mod\ l)$,若 $w$ 不存在,则 $a\equiv 0\ (mod\ l)$。
    4. 若 $gcd(numerator(x^q-x_w),\phi_l)=1$,则 $a\equiv 0\ (mod\ l)$;否则,计算 $gcd(numerator((y^q-y_w)/y),\phi_l)$,若其为 1,则 $a\equiv -2w\ (mod\ l)$;否则 $a\equiv 2w\ (mod\ l)$。

1990年后,Atikin 和 Elkies 对他的算法进行了改进,然后称之为 SEA算法,复杂度为 $O(log^6(q))$。

爱德华兹曲线

方程: $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)$

双线性映射可以:将曲线上的两个点映射到基域上的一个元素。

通常,取 $G_0=G_1$ 为有限域上的超奇异椭圆曲线,$G_T$ 为 $G_0$ 的基域乘法群。

(这样一来,DDH就不是困难的了:check if $e(T,G)=e(xG,yG)$)

Application

三方 DH 协议:(安全性基于 Bilinear Diffie-Hellman 问题:给定 $G_1,G_2,P,aP,bP,cP$,hard for computing $e(P,P)^{abc}$) 随机选择大素数 $p$,生成 p 阶循环群 $G_1,G_2$,设 $e:G_1×G_1\rightarrow G_2$

交换 $aP,bP,cP$,则共享密钥 $K=e(P,P)^{abc}$。

IBC (Identity-based cryptography)

IBC 产生公钥:反之于传统公钥产生(先选择私钥再计算公钥,故混乱,需要PKI进行管理)

​ 先选择公钥(F(ID),ID:用户身份,每个用户唯一确定),再产生私钥。

​ KGC (Key Generation Center) 以主密钥,由 ID 产生用户私钥。

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)$