Contents

Notes: Public Key Cryptosystems Using Elliptic Curves

Notes for $Public\ Key\ Cryptosystems\ Using\ Elliptic\ Curves$

Public Key Cryptosystems Using Elliptic Curves J. Borst

$\text { Chapter 1 }$ Introduction

公钥加密系统的安全性主要是基于一些困难的数学问题(对于当前情况而言),已经有许多数学困难问题被应用到公钥密码中。目前主要适用的是大整数的分解问题和离散对数问题。

$\text { Chapter 2 }$ Elliptic Curves

$2.1 \quad$Introduction

Weierstrass 等式是一个同质的深度为3的方程,格式为: $$ \tag{2.1} Y^{2} Z+a_{1} X Y Z+a_{3} Y Z^{2}=X^{3}+a_{2} X^{2} Z+a_{4} X Z^{2}+a_{6} Z^{3}, $$ 满足上述方程的点也就是多项式 $F$ 的根: $$ \tag{2.2}F(X, Y, Z)=Y^{2} Z+a_{1} X Y Z+a_{3} Y Z^{2}-X^{3}-a_{2} X^{2} Z-a_{4} X Z^{2}-a_{6} Z^{3}, $$ 如果对于所有的点$P=(X, Y, Z)$满足方程$(2.1)$,并且在$P$点的偏导数$\frac{\partial F}{\partial X}, \frac{\partial F}{\partial Y}$ 或 $\frac{\partial F}{\partial Z}$中至少有一个是非零的,则称该 Weierstrass 方程为非奇异的 (non-singular) 或光滑的 (smooth)。如果对于一些点$P$,三个偏导数都是0,那么称该 Weierstrass 方程为奇异的(singular),并且称点$P$为一个奇异点 (singular point)。

一个椭圆曲线(或者说一个非奇异的三次曲线)是对于一个光滑 Weierstrass 方程的所有解的集合。一个解被称为椭圆曲线上的一个点或者称 $EC-point$。一个奇异Weierstrass 方程的全部解的集合,被称为一个奇异三次曲线 (singular cubic curive),我们用 $E$ 来表示一个曲线。在三次曲线上总是有一个点的 $Z$ 坐标为 0,名为 $(0:1:0)$。它被称为无穷远点并用 $O$ 来表示。

当我们将$x=\frac{X}{Z},y=\frac{Y}{Z}$代入方程$(2.1)$中时,Weierstrass 方程可以表示为: $$ \tag{2.3}y^{2}+a_{1} x y+a_{3} y=x^{3}+a_{2} x^{2}+a_{4} x+a_{6} $$ 对于群 $K$,两条曲线 $E_1/K$ 和 $E_2/K$: $$ \begin{array}{l} E_{1}: y^{2}+a_{1} x y+a_{3} y=x^{3}+a_{2} x^{2}+a_{4} x+a_{6} \\ E_{2}: y^{2}+a_{1}^{\prime} x y+a_{3}^{\prime} y=x^{3}+a_{2}^{\prime} x^{2}+a_{4}^{\prime} x+a_{6}^{\prime} \end{array} $$ 在 $K$ 上是同构的,表示为 $E_{1} / K \cong E_{2} / K$,如果存在 $r, s, t, u \in K$ ,并且$u \neq 0$,这样变量的变化 $(x, y) \longrightarrow\left(u^{2} x+r, u^{3} y+u^{2} s x+t\right)$ 将等式 $E_1$ 转化为 $E_2$,这样变量的变化称为 admissible change of variables

$2.2 \quad$The Discriminant and $j$ -Invariant

$E/K$ 是由仿射Weierstrass方程给出的曲线: $$ E / K: y^{2}+a_{1} x y+a_{3} y=x^{3}+a_{2} x^{2}+a_{4} x+a_{6} $$ 我们定义以下等式: $$ \begin{aligned} b_{2} &=a_{1}^{2}+4 a_{2} \\ b_{4} &=2 a_{4}+a_{1} a_{3} \\ b_{6} &=a_{3}^{2}+4 a_{6} \\ b_{8} &=a_{1}^{2} a_{6}+4 a_{2} a_{6}-a_{1} a_{3} a_{4}+a_{2} a_{3}^{2}-a_{4}^{2} \\ c_{4} &=b_{2}^{2}-24 b_{4} \\ c_{6} &=b_{2}^{3}+36 b_{2} b_{4}-216 b_{6} \end{aligned} $$ 进一步,我们如下定义 Weierstrass 方程 $E$ 的判别式 $\Delta$ : $$ \Delta(E)=-b_{2}^{2} b_{8}-8 b_{4}^{3}-27 b_{6}^{2}+9 b_{2} b_{4} b_{6} $$ 当 $\Delta \neq 0$ 时,我们定义曲线 $E$ 的 $j$-不变式 ($j$-invariant) 为$j(E)=\frac{c_{4}^{3}}{\Delta(E)}$

定理 2.1: 当且仅当$\Delta(E) \neq 0$时,$E$ 是非奇异的。

定理 2.2: 如果两条椭圆曲线$E_{1} / K$ 和 $E_{2} / K$ 在 $K$ 上是同构的,那么 $j\left(E_{1}\right)=j\left(E_{2}\right)$ 。

$2.3 \quad$Curves over Fields with different Characteristics

定义在特征为2或3的域上的椭圆曲线与定义在特征值大于3的域上的曲线不同。

还没仔细看,有空补充(咕咕咕

$2.4 \quad$Addition

对于 $E$ 上的点 $P,Q,R$,可以像这样在一个椭圆曲线 $E$ 上定义一个加法:

  1. $P+\mathcal{O}=P$ 且 $\mathcal{O}+P=P$.

  2. $P+\mathcal{O}=P$.

  3. $P+Q=Q+P$.

  4. $P+(-P)=\mathcal{O}$.

  5. $(P+Q)+R=P+(Q+R)$

在无穷远处的点 $\mathcal{O}$ 位于每条垂线上,在下图中给出了三组椭圆曲线上的加法的例子。

https://qiniu.am473ur.com/img/Addition_on_an_Elliptic_Curve.png

  1. $P+Q .$ 并且 $P \neq Q .$ 连接点 $P$ 和 $Q$ 作直线 $l$,直线 $l$ 与椭圆曲线 $E$ 的第三个交点为 $R$,这里 $R$ 是不等于 $\mathcal{O}$ 的。 连接点 $R$ 和无穷远点 $\mathcal{O}$ 得到直线 $l^{\prime}$,$ P+Q$ 得到的点为 $l^{\prime}$ 与 $E$ 的第三个交点。
  2. $S+S=2 S .$ 令点 $m$ 为椭圆曲线 $E$ 在点 $S$ 处的切线, $T$ 为直线 $m$ 在曲线 $E$ 上的第三个交点,$m^{\prime}$ 为一条连接点 $T$ 和 $\mathcal{O}$ 的直线,$2S$ 为 $m^{\prime}$ 与$E$ 的第三个交点。
  3. $T+S .$ 连接点 $T$ 和点 $S$ 作直线 $m$。 但这刚好是椭圆曲线 $E$ 在 $S$ 处的切线,那么我们要找第三个交点就需要通过 $S$ 处的垂线$n$,$n$ 与曲线的另外一个交点,即为 $T+S$ 。

对于椭圆曲线 $E$ 上的点 $P=\left(x_{1}, y_{1}\right), Q=\left(x_{2}, y_{2}\right)$ 计算椭圆曲线上的点加法 $P+Q=\left(x_{3}, y_{3}\right)$ ,可以通过如下方法来计算:

  1. $-P=\left(x_{1},-y_{1}-a_{1} x_{1}-a_{3}\right)$
  2. $Q \neq-P$ 因此

$$ x_{3}=\lambda^{2}+a_{1} \lambda-a_{2}-x_{1}-x_{2} $$

$$ y_{3}=-\left(\lambda+a_{1}\right) x_{3}-\left(y_{1}-\lambda x_{1}\right)-a_{3} $$

其中 $$ \lambda=\left\{\begin{array}{ll} \frac{y_{2}-y_{1}}{x_{2}-x_{1}} & \text { if } P \neq Q \\ \frac{3 x_{1}^{2}+2 a_{2} x_{1}+a_{4}-a_{1} y_{1}}{2 y_{1}+a_{1} x_{1}+a_{3}} & \text { if } P=Q \end{array}\right. $$ 在 $\lambda$ 中,分母恒不为零。

$2.5 \quad$Scalar Multiplication

对于$P \in E$ 并且 $m \in \mathbb{Z}$ ,那么 $m$ 乘 $P$ 被定义为: $$ m P=\left\{\begin{array}{ll} \underbrace{P+\ldots+P}_{\text {m terms }}, & \text { if } m>0, \\ \mathcal{O}, & \text { if } m=0 \\ (-m)(-P), & \text { if } m<0 \end{array}\right. $$ 一般来说,在一个椭圆曲线上计算一个点的乘法,远比在给出 $mP$ 的情况下计算 $m$ 容易。

计算一个点的乘法,有对数时间复杂度的实现,而在给出 $mP$ 的情况下计算较大的整数 $m$,仍然是一个数学困难问题,即椭圆曲线上的离散对数问题 (ECDLP)。

椭圆曲线上的点的阶 (order):对于椭圆曲线 $E$ 上的一个点 $P$ ,存在最小的 $n \in \mathbb{N}^{+}$ 使 $n P=\mathcal{O}$,那么 $n$ 即为点$P$ 的阶。

$2.6 \quad$ The Elliptic Curve Discrete Logarithm Problem

ECDLP: 令 $E$ 为一个椭圆曲线,$P$ 为$E$ 上的一个阶为$n$ 的点,给出一个$E$ 上的点 $Q$ 满足 $Q=mP$,寻找 $m \in{2, \ldots . n-2}$ 。

当 $E$ 和 $P$ 都严格选取的时候,ECDLP被认为是几乎不可能解决的。如果 $m=0,1, n-1$ ,我们会得到 $Q=\mathcal{O}, P, -P$ ,这样的 $m$ 就很容易被发现。但是如果选取的 $P$ 的阶 $n$ 很大,那么通过枚举的方法来寻找 $m$ 是很难顶的。所以可以将$Q$ 作为公钥,$m$ 作为私钥可以应用到公钥密码系统中。

椭圆曲线离散对数问题 (ECDLP) 是离散对数问题 (DLP) 的一个特殊情况。

$2.7 \quad$ Number of Points on a Curve

对于一个椭圆曲线 $E$ ,我们使用 $\# E$ 来表示 $E$ 上的点的个数。

令 $E$ 为一个定义在 $F_{q}$ 上的椭圆曲线,$q=p^{m}$,其中$p$为素数,所以$p$为 $F_{q}$ 的特征值,假定曲线 $E_{q}(a, b)$ 定义在方程 $y^{2}=x^{3}+a x+b$ 上,那么对于所有的 $x \in F_{q}$ ,这个方程最多有两个解。因为 $F_{q}$ 上的元素的个数为 $q$ 并且 $\mathcal{O} \in E$ ,所以 $\# E\left(F_{q}\right) \leq 2 q+1$。然而实际上一个曲线上的点的数量总是接近上界的一半。

定理 2.10 (Hasse): 令$\# E\left(F_{q}\right)=q+1-t$,那么 $|t| \leq 2 \sqrt{q}$ 。

(注意如果 $t=-2 \sqrt{q}$ ,那么 $q+1-t=(\sqrt{q}+1)^{2}>0$)

接下来我们可以使用勒让德符号 (Lengendre symbol) 来计算一个椭圆曲线上的点的个数。

勒让德符号: 令 $p$ 为一个奇素数,那么对于任意的整数 $a \geq 0$ ,勒让德符号 $\left(\frac{a}{p}\right)$ 被定义为: $$ \left(\frac{a}{p}\right)=\left\{\begin{array}{ll} 0 & \text { if } a=0 \bmod p \\ 1 & \text { if } a \text { is a quadratic residue modulo } p \\ -1 & \text { if } a \text { is a quadratic non-residue modulo } p \end{array}\right. $$ 定理 2.11: $$ \left(\frac{a}{p}\right)=a^{\frac{p-1}{2}} \quad(\bmod p) $$ 该定理可用于给出更通用的勒让德式符号:

定义 2.5: 设 $D$ 为欧几里得域。然后我们定义对于所有的 $a \in D$,素数 $p\in D$ 以及 $b \in \mathbb{N}^{+}$

$$ \left(\frac{a}{p}\right)_{b}=a^{\frac{p-1}{b}} \quad(\bmod p) $$

定理 2.12: 假设 $p$ 为一个大于 3 的素数,并且 $a, b \in F_{p}$ ,那么 $$ \# E_{p}(a, b)=1+\sum_{x=0}^{p-1}\left(\left(\frac{x^{3}+a x+b}{p}\right)+1\right) $$ 在这里 $\left(\frac{\cdot}{\cdot}\right)$ 指的是勒让德符号。

。。。然后是一些特殊情况下的,求 $E$ 上点的个数的方法

定理 2.17: 假设 $p$ 为一个素数,对于整数 $m$ 有 $q=p^{m}$。$E$ 为一个定义在 $F_{q}$ 上的椭圆曲线,那么对于任意的 $P \in E\left(F_{q}\right)$ 和任意的 $k \in \mathbb{Z}$ 满足: $$ \left(k \cdot \# E\left(F_{q}\right)\right) P=\mathcal{O} $$

$2.8 \quad$ The Complementary Group

定义 2.6: 假设 $p$ 为一个大于 3 的素数,$a, b \in F_{p}$,一个固定的模 $p$ 意义下的二次非剩余 $v$。那么 $\overline{E_{p}(a, b)}_{v}$ 是对于 $x \in F_{p}$,$y=u \sqrt{v}\ (\bmod p)$ 的点的集合,其中 $u \in F_{p}$,满足: $$ y^{2}=x^{3}+a x+b \quad(\bmod p) $$ 我们称$\overline{E_{p}(a, b)}_{v}$为 $E_{p}(a, b)$ 相对于 $v$ 的互补曲线。

定理 2.20: 假设 $p$ 为一个大于 3 的素数,$v$ 是一个固定的模 $p$ 意义下的二次非剩余,$a, b \in F_{p}$,那么: $$ \# \overline{E_{p}(a, b)}_{v}=1+\sum_{x=0}^{p-1}\left(1-\left(\frac{x^{3}+a x+b}{p}\right)\right) $$ 在这里 $\left(\frac{\cdot}{\cdot}\right)$ 指的是勒让德符号。 $$ \begin{aligned} \# E_{p}(a, b)_{v}+\# \overline{E_{p}(a, b)}_{v}=& 1+\sum_{x=1}^{p}\left(\left(\frac{x^{3}+a x+b}{p}\right)+1\right)+\\ & 1+\sum_{x=1}^{p}\left(1-\left(\frac{x^{3}+a x+b}{p}\right)\right) \\ =& 2+\sum_{x=1}^{p} 2 \\ =& 2 p+2 \end{aligned} $$ 所以在 Hasse 定理中,如果 $\# E_{p}(a, b)=p+1-t$,那么 $\# \overline{E_{p}(a, b)}_{v}=p+1+t$。

$2.9 \quad$ Elliptic Curves over $\mathbb{Z}_{n}$

当 $n$ 不是一个素数的时候,在整数环 $\mathbb{Z_n}$ 上我们也可以定义椭圆曲线,和在有限域中一样,我们将这样的曲线定义为 $\mathbb{Z_n} \times \mathbb{Z_n}$ 中的点的集合,并且这些点是 $y^{2}=x^{3}+a x+b$ 的解,其中 $a, b \in \mathbb{Z_n}$,并且还要加上一个无穷远点$\mathcal{O}_{n}$。因为我们不想考虑域的特征为2或3的情况,我们直接假设 $\operatorname{gcd}(n, 6)=1$ ,因此n没有等于2或3的因子,此外,有 $\operatorname{gcd}\left(4 a^{3}+27 b^{2}, n\right)=1$ 来保证曲线是非奇异的(这里原文说的是nonsingularity criterium)。

把这条曲线称为$E_{n}(a,b)$,$n=pq$,$p$ 和 $q$ 为素数,那么这条曲线上也可以进行椭圆曲线上的加法,但由于n不是素数,这种加法并不总是存在的,$E_n$ 可以看作两条曲线相乘后的结果: $$ \tilde{E}_{n}(a, b)=E_{p}(a, b) \times E_{q}(a, b) $$ 对于一个在曲线$E_n$ 上的点 $P=(x, y)$ ,可以被表示为一组点 $\left[P_{p}, P_{q}\right]=\left[\left(x_{p}, y_{p}\right),\left(x_{q}, y_{q}\right)\right]$ ,其中 $P_p$ 在曲线 $E_{p}(a, b)$ 上,$P_q$ 在曲线 $E_{q}(a, b)$ 上。由于中国剩余定理这个神奇的存在,就可以在已知这一组点和$p,q$的情况下,计算出原曲线 $E_n$ 上的点 $P$。

如果n的因数都非常大,那么曲线上随机的两个点不能进行相加的概率是很小的:

$$ \begin{aligned} \frac{\# E_{p}-1+\# E_{q}-1}{\# E_{n}} &=\frac{\# E_{p}-1+\# E_{q}-1}{\# E_{p} \cdot \# E_{q}-\# E_{p}-\# E_{q}+2} \\ &=\frac{\# E_{p}-1+\# E_{q}-1}{\left(\# E_{p}-1\right)\left(\# E_{q}-1\right)+1} \\ &=\frac{\# E_{p}-1}{\left(\# E_{p}-1\right)\left(\# E_{q}-1\right)+1}+\frac{\# E_{q}-1}{\left(\# E_{p}-1\right)\left(\# E_{q}-1\right)+1} \\ &<\frac{1}{\# E_{q}-1}+\frac{1}{\# E_{p}-1} \\ & \leq \frac{1}{q-2 \sqrt{q}}+\frac{1}{p-2 \sqrt{p}} \end{aligned} $$

定理 2.20: 令 $p,q$ 为大于3的素数,$n=pq$, $a,b \in \mathbb{Z}$ 并且 $\operatorname{gcd}\left(4 a^{3}+27 b^{2}, n\right)=1$,定义$N_{n}=\operatorname{lcm}\left(\# E_{p}(a, b), \# E_{q}(a, b)\right)$,对于所有的点 $P \in E_{n}(a, b)$ 和 $k \in \mathbb{Z}$,在乘法允许的情况下,有:

$$ \left(k N_{n}+1\right) P=P \text { over } E_{n}(a, b) $$

$2.10 \quad$ Division Polynomials

Division Polynomials $\psi_{m} \in \mathbb{Z}[a, b, x, y]$ 是这样定义的: $$ \begin{aligned} \psi_{-1} &=-1 \\ \psi_{0} &=0 \\ \psi_{1} &=1 \\ \psi_{2} &=2 y \\ \psi_{3} &=3 x^{4}+6 a x^{2}+12 b x-a^{2} \\ \psi_{4} &=4 y\left(x^{6}+5 a x^{4}+20 b x^{3}-5 a^{2} x^{2}-4 a b x-8 b^{2}-a^{3}\right) \\ \psi_{2 i+1} &=\psi_{i}\left(\psi_{i+2} \psi_{i-1}^{2}-\psi_{i-2} \psi_{i+1}^{2}\right) / 2 y, i \geq 2 \\ \psi_{2 i} &=\psi_{i+2} \psi_{i}^{3}-\psi_{i+1}^{3} \psi_{i-1}, i \geq 3 \end{aligned} $$ 此外,还可以定义多项式 $\phi_{m}$ 和 $\omega_{m}$: $$ \begin{aligned} \phi_{m} &=x \psi_{m}^{2}-\psi_{m+1} \psi_{m-1} \\ \omega_{m} &=\left(\psi_{m+2} \psi_{m-1}^{2}-\psi_{m-2} \psi_{m+1}^{2}\right) / 4 y \end{aligned} $$ 那么椭圆曲线上的数乘,就可以用Division Polynomials来表示了: $$ m P=\left(\frac{\phi_{m}(P)}{\psi_{m}(P)^{2}}, \frac{\omega_{m}(P)}{\psi_{m}(P)^{3}}\right) $$ 并且我们可以在只知道一个点的 $x$ 坐标的时候,进行椭圆曲线上的乘法运算,并得到运算后的 $x$ 坐标值。因此可以定义符号 $\otimes x$ 来表示仅在x坐标上进行的运算。

用 SageMath 可以很容易的实现仅在x坐标上进行的数乘,非常方便。

$\text { Chapter 3 }$ Using Elliptic Curve Points as Messages

通常我们会把椭圆曲线上的一个点作为明文并进行加密,但是很多时候尽管明文长度在一个有限的范围内,也仍然可能不在椭圆曲线上,这时候需要对它进行一点操作,来把明文转化为曲线上的点,再进行加密。

$3.1 \quad$ Embedding Plaintexts

选取一个整数 $k$,明文 $m$

  1. $i:=1$

  2. $x(m, i):=f(m k+i)$

  3. 检查 $x(m, i)^{3}+a x(m, i)+b$ 是否为模 $q$ 的二次剩余

    (a) 如果是,那么对应 $y$ 的值就是 $x^{3}+a x+b$ 的平方根,这个点就是$(x,y)$,结束。

    (b) 如果不是,那么如果 $i<k$ ,那么 $i:=i+1$,然后跳转到第2步。

可以发现 $i$ 最多只能累加到 $k$ 的大小,如果到了 $k$ 还没找到曲线上的点,那就要重新选取更大的 $k$ 了,然而我实现了一波,发现一般 $i$ 还在个位数,就可以找到了。

$x^{3}+a x+b$ 不是一个模 $q$ 的二次剩余的概率是 $\frac{\#E_q(a,b)}{2q}$,接近 $\frac{1}{2}$。那么对于一个正整数 $k$,找不到 $i$ 的概率为 $\left(\frac{1}{2}\right)^{k}$ 。

所以这个算法还是很靠谱的,并且效率较高,并不用选取太大的$k$。

$\text { Chapter 4 }$ Some Encryption Systems

这一章介绍了基于ECDLP的ElGamal加密,以及其他一些基于分解两个大整数的乘积的加密算法。

  • P36 - ElGamal Encryption
  • P37 - Elliptic Curve ElGamal Encryption
  • P38 - Menezes-Vanstone Cryptosystem
  • P39 - Elliptic Curve Encryption System
  • P39 - Demytko Cryptosystem
  • P41 - KMOV-Type 0
  • P42 - KMOV Cryptosystem
  • P44 - Kuwakado-Koyama Cryptosystem

好多啊。。。然后论文里给了个对比的表格,在第47页

$\text { Chapter 5 }$ Attacks on the Systems based on Factoring

有很多椭圆曲线加密算法的安全性是基于分解两个大素数的乘积,这一点和著名的RSA类似,所以一些对于RSA加密可以进行的攻击,也可能能够攻击这些椭圆曲线加密算法。

这一章就是介绍一些和RSA的相关攻击类似的对于椭圆曲线加密的攻击。

$5.1 \quad$ The Håstad Attack

更新中……(咕咕咕咕咕咕)