ECC-ElGamal

标签：11 right ECC 曲线 椭圆 ElGamal left equiv

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公钥加密算法

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

标签：11,right,ECC,曲线,椭圆,ElGamal,left,equiv
From： https://www.cnblogs.com/miro-cnblogs/p/18470278