ECC-ElGamal

miro-cnblogs / 2024-10-21 / 原文

EC(Elliptic Curve)椭圆曲线

三种椭圆曲线
一般资料会以维尔斯特拉斯曲线（Weierstrass Curve）为例介绍椭圆曲线的基本概念和运算原理，这是因为任意椭圆曲线都可以写为维尔斯特拉斯曲线形式。实际上，椭圆曲线还包括多种其他的类型，如蒙哥马利曲线（Montgomery Curve）、扭曲爱德华曲线（Twisted Edwards Curve）等。Curve25519就是在蒙哥马利曲线上定义的椭圆曲线，而Ed25519是在扭曲爱德华曲线上定义的椭圆曲线。

1.维尔斯特拉斯曲线
椭圆曲线的一般形式可表示为：

$E:y^2=x^3+Ax+B$

其中$A,B∈\mathbb{F}_p$，$4A^3+27B^2≠0$。一般称上式为维尔斯特拉斯形式的椭圆曲线方程。

2.蒙哥马利曲线
蒙哥马利形式的椭圆曲线方程定义为：

$Kt^2=s^3+Js^2+s$ 其中$K,J∈\mathbb{F}_p$，$K(J^2-4)≠0$。

3.扭曲爱德华曲线
扭曲爱德华形式的椭圆曲线方程定义为：

$av^2+w^3=1+dv^2 w^2$ 其中$a,d≠0$且$a≠d$。

椭圆曲线间的转换
维尔斯特拉斯曲线、蒙哥马利曲线、扭曲爱德华曲线这三类椭圆曲线之间可以相互转换。
蒙哥马利曲线 ⇔ 维尔斯特拉斯曲线
任何椭圆曲线都可以写为维尔斯特拉斯形式。反之，当满足特定条件时，维尔斯特拉斯椭圆曲线可以转换为蒙哥马利椭圆曲线。具体转换条件参见《Montgomery Curve》的Equivalence with Weierstrass curves部分。
蒙哥马利曲线$Kt^2=s^3+Js^2+s$转换为等价维尔斯特拉斯曲线$y^2=x^3+Ax+B$的方法为：

$\left\{ \begin{array}{l} {A = \frac{3 - J^{2}}{3K^{2}}} \\ {B = \frac{2J^{3} - 9J}{27K^{3}}} \end{array} \right.$

蒙哥马利曲线点$(s,t)$转换为等价维尔斯特拉斯曲线点$(x,y)$的方法为：

$\left\{ \begin{array}{l} {x = \frac{3s + J}{3K}} \\ {y = \frac{t}{K}} \end{array} \right.$

反之，维尔斯特拉斯曲线点$(x,y)$转换为等价蒙哥马利曲线点$(s,t)$的方法为：

$\left\{ \begin{array}{l} {s = \frac{3Kx - J}{3}} \\ {t = \frac{y}{K}} \end{array} \right.$

蒙哥马利曲线 ⇔ 维尔斯特拉斯曲线
所有扭曲爱德华曲线都与蒙哥马利曲线双向有理等价（Birationally Equivalent），反之亦然。所谓双向有理等价，可以理解为除了个别点外，扭曲爱德华曲线的点和蒙哥马利曲线的点存在相互映射关系。
扭曲爱德华曲线$av^2+w^3=1+dv^2 w^2$转换为等价蒙哥马利曲线$Kt^2=s^3+Js^2+s$的方法为：

$\left\{ \begin{array}{l} {J = \frac{2\left( {a + d} \right)}{a - d}} \\ {K = \frac{4}{a - d}} \end{array} \right.$

扭曲爱德华曲线点$(v,w)$转换为等价蒙哥马利曲线点$(s,t)$的方法为：

$ \left\{ \begin{array}{l} {s = \frac{1 + w}{1 - w}} \\ {t = \frac{s}{v}} \end{array} \right.$

蒙哥马利曲线点$(s,t)$转换为扭曲爱德华曲线点$(v,w)$的方法为：

$\left\{ \begin{array}{l} {v = \frac{s}{t}} \\ {w = \frac{s - 1}{s + 1}} \end{array} \right.$

当$t=0$或$s=-1$时，映射方法为$(v,w)=(0,-1)$。

椭圆曲线上的运算
1.有限域的负元
$P⁡(x,y)$的负元是$(x,-y\pmod{p})=(x,p-y)$
2.有限域的加法
$P⁡(x_1,y_1 )$，$Q⁡(x_2,y_2 )$和$R⁡(x_3,y_3 )$三点（其中$R$是直线$PQ$与曲线交点关于$x$轴的对称点，即有$R=P+Q$）有如下关系：

$\left\{ \begin{array}{l} {x_{3} \equiv k^{2} - x_{1} - x_{2}~\left( {\text{mod}~p} \right)} \\ {y_{3} \equiv k\left( {x_{1} - x_{3}} \right) - y_{1}~\left( {\text{mod}~p} \right)} \end{array} \right.$

3.斜率计算

$k = \left\{ \begin{matrix} \frac{3x_{1}^{2} + a}{2y_{1}} & {P = Q} \\ \frac{y_{2} - y_{1}}{x_{2} - x_{1}} & {P \neq Q} \end{matrix} \right.$

ECC-ElGamal公钥加密算法

设$p>3$是一个大素数，$E$是有限域$\mathbb{F}_p$上的椭圆曲线，$G∈E$是椭圆曲线上的一个点，并且$G$的阶足够大。$p$和$E$以及$G$都公开。
随机选取整数$x$，$1≤x≤\mbox{ord}⁡(G)-1$，其中$\mbox{ord}⁡(G)$表示以基点$G$在曲线$E$上生成群的阶。计算$Y=xG$。$Y$是公开的加密密钥（公钥），$x$是保密的解密密钥（私钥）。
加密变换：明文消息映射到椭圆曲线上的点$M=(m_1,m_2 )$，随机选取一个整数$k$，满足$1≤k≤\mbox{ord}⁡(G)-1$，密文为$C=(c_1,c_2 )$，其中$c_1=kG$，$c_2=M+kY$。
解密变换：对任意密文$C=(c_1,c_2 )$，明文为$M=c_2-xc_1$。

证明：
根据加密变换有$c_1=kG$，$c_2=M+kY=M+kxG$，故$c_2-xc_1=M+kxG-xkG=M$。
证毕。

例：
设$p=11$，$E$是由$y^2≡x^3+x+6\pmod{11}$所确定的有限域$\mathbb{F}_{11}$上的椭圆曲线，基点$G=(2,7)$。选定的私钥为$x=7$，明文映射到曲线的点$M=(10,9)$。
因选择的私钥为$x=7$，那么对应公钥为

$Y=7G=(7,2)$

计算过程示例：
首先计算$2G$，$2G=G+G$，

$k \equiv \frac{3 \cdot 2^{2} + 1}{2 \cdot 7}~\left( {\text{mod}~11} \right) \equiv 13 \cdot 14^{- 1}~\left( {\text{mod}~11} \right) \equiv 2 \cdot 4~\left( {\text{mod}~11} \right) \equiv 8$ $x \equiv 8^{2} - 2 - 2~\left( {\text{mod}~11} \right) \equiv 60~\left( {\text{mod}~11} \right) \equiv 5$ $y \equiv 8\left( {2 - 5} \right) - 7~\left( {\text{mod}~11} \right) \equiv - 31~\left( {\text{mod}~11} \right) \equiv 2$

所以$2G=(5,2)$。
然后计算$3G$，$3G=2G+G$，

$k \equiv \frac{2 - 7}{5 - 2}~\left( {\text{mod}~11} \right) \equiv - 5 \cdot 3^{- 1}~\left( {\text{mod}~11} \right) \equiv 6 \cdot 4~\left( {\text{mod}~11} \right) \equiv 2$ $ x \equiv 2^{2} - 5 - 2~\left( {\text{mod}~11} \right) \equiv - 3~\left( {\text{mod}~11} \right) \equiv 8$ $y \equiv 2\left( {5 - 8} \right) - 2~\left( {\text{mod}~11} \right) \equiv - 8~\left( {\text{mod}~11} \right) \equiv 3$

所以$3G=(8,3)$。
类似计算可得$4G=(10,2)$，$6G=(7,9)$，$7G=(7,2)$，$8G=(3,5)$，$14G=(2,7)$。可以注意到有$14G=G⇒13G=0$，所以对于基点$G=(2,7)$有$\mbox{ord}⁡(G)=13$。由此计算公钥$Y$为

$Y = 7G = (7,2)$

假设随机选取$k=3$，有

$c_1=kG=3G=(8,3)$ $c_2=M+kY=M+kxG=(10,9)+21(2,7)=(10,2)$

因此，明文$M=(10,9)$对应的密文为$C=(c_1,c_2 )=((8,3),(10,2))$。
对于解密过程而言，已知私钥$x=3$，收到密文$C=(c_1,c_2 )=((8,3),(10,2))$，于是明文恢复过程为

$M = c_{2} - xc_{1} = (10,2) - 3(8,3) = (10,9)$

至此，ECC-ElGamal公钥加密算法加解密过程完毕。

参考
ISO/IEC 18033-2:2006 Information technology – Security techniques – Encryption algorithms – Part 2: Asymmetric ciphers
RFC 7748 Elliptic Curves for Security
曹天杰. 密码学引论[M].
Ed25519与Curve25519：概念与相互转换 - 知乎 (zhihu.com)
椭圆曲线加密算法（ECC） - 知乎 (zhihu.com)
辅因子（cofactor）解释：揭开椭圆曲线不为人知的秘密 - 知乎 (zhihu.com)