【密码学】椭圆曲线密码ECC

Author Avatar
source. 12月 20, 2020
  • 在其它设备中阅读本文章

RSA密钥长度太长,计算较慢。亲,来试试ECC吧!

椭圆曲线密码学Elliptic Curve Cryptography,ECC)是一种基于椭圆曲线数学的非对称加密算法,安全性基于椭圆离散对数问题。

优势:ECC 使用较短的密钥就能达到与更长密钥的 RSA 相当等级的安全性。被广泛用于 HTTPS、SSH、PGP 协议以及比特币(BTC)、以太币(ETH)上。

image

ECC 有取代 RSA 的趋势,ECC 是下一代非对称加密算法!

缺陷:可能被 NSA 藏了后门,可信度还没有 RSA 高,而且可能涉及专利。

万恶的 mdgzy!

椭圆曲线

椭圆曲线 $E(a,b)$ 由如下形式的方程定义:

并且要保证曲线不含奇点,即满足:

椭圆曲线始终关于 $x$ 轴对称。

image

图中,红色为 $y^2=x^3-x$,蓝色为 $y^2=x^3+x+1$,作图工具:Desmos。

另外,椭圆曲线还需引入一个无穷处的点作为曲线的一部分,可以使用符号 $O$ 表示。

那么,椭圆曲线的表达式为:

一个群(group)$G$ 由一堆元素和一个运算(加法 $+$)组成,必须满足四个条件:

  • 封闭性:若 $a\in G$ 且 $b\in G$,则 $a+b\in G$
  • 结合律:若 $a,b,c\in G$,则 $(a+b)+c=a+(b+c)$
  • 单位元:对于每个 $a\in G$,$a+O=O+a=a$
  • 逆元:对于每个 $a\in G$,都存在唯一的 $b\in G$,使得 $a+b=O$,称 $b$ 为 $a$ 的逆元

若一个群满足交换律,即 $a+b=b+a$,则称它为交换群或阿贝尔群

若满足群的条件,则可以直接使用群的性质。比如,只有一个单位元,每个元素有且只有一个逆元。

椭圆曲线上的群论

可以在椭圆曲线上定义一个阿贝尔群:

  • 群中的元素是椭圆曲线上的点
  • 单位元是无穷处的点 $O$
  • $(x,y)$ 的逆元是 $(x,-y)$
  • 加法规则:一条直线与 $E$ 交于三个点 $P,Q,R$,它们之和等于 $O$,即 $P+Q+R=O$
  • $+$ 运算满足交换律、结合律

加法的几何描述

由 $P+Q+R=0$ 有:

也就是做穿过 $P$ 和 $Q$ 两点的直线,它穿过的第三个点 $R=(x,y)$ 的关于 $x$ 轴对称的点 $(x,-y)$ 就是 $P+Q$ 的结果。

image

若 $P=Q$,那么这条直线是过点 $P$ 的切线。

实数域上加法的代数描述

一元三次方程的解,直接用公式吧少年。(老师都不想细讲)

椭圆曲线公式:

当$P\ne Q$时:

当$P=Q$时:

$\mathbb{Z}_p$上加法的代数描述

设变元$x,y$和椭圆曲线参数$a,b$都在$\mathbb{Z}_p$上取值,椭圆曲线公式两边取模$p$得到$E_p(a,b)$:

求$P+Q$:

其中,

$\operatorname{GF}(2^m)$上加法的代数描述

设变元$x,y$和椭圆曲线参数$a,b$都在$\operatorname{GF}(2^m)$上取值,得到$E_{2^m}(a,b)$:

大型懵逼现场!反正考试也不太可能会考。

若$P=(x_P,y_P)$,则$-P=(x_P,x_P+y_P)$。

若$P\ne Q,~P\ne-Q,~R=P+Q$,则:

若$R=P+P$,则:

伽罗瓦域可以极大扩展可能取值?

ECC

ECC的安全性基于椭圆曲线上的离散对数问题,考虑方程$Q=kP$:

  • 已知$k,P$,计算$Q$容易
  • 已知$P,Q$,计算$k$困难

ECC Diffie-Hellman

和ElGamal一样,它的安全性也基于离散对数问题,很快想到,可以往DH上套:

  1. 选定一个大的模数$q$(两种形式:素数$p$或$2^m$,分别对应上面两种域)以及系数$a$和$b$,由此定义椭圆曲线$E_q(a,b)$,并在其上挑选一个基点$G=(x_g,y_g)$,它的阶$n$(使得$nG=O$成立的最小正整数)是一个非常大的数。$E_q(a,b)$和$G$均公开。
  2. Alice选择一个小于$n$的整数$n_A$作为私钥,计算公钥$P_A=n_AG$并公开
  3. Bob选择一个小于$n$的整数$n_B$作为私钥,计算公钥$P_B=n_BG$并公开
  4. Alice计算密钥$K=n_AP_B=(n_An_B)G$,Bob计算密钥$K=n_BP_A=(n_An_B)G$。

这样,Alice和Bob就通过不安全信道建立起了密钥$K$。

注意:上述过程中的加法、数乘运算均是椭圆曲线下的运算。

ECC 加解密

和ElGamal一样,本质上就是通过DH协商一个密钥,然后用这个密钥进行加解密。

密钥生成:

  1. 协商椭圆曲线$E_q(a,b)$和基点$G=(x_g,y_g)$
  2. Alice选择一个私钥$n_A$,计算公钥$P_A=n_AG$并公开
  3. Bob选择一个私钥$n_B$,计算公钥$P_B=n_BG$并公开

假设Bob要给Alice发一个消息$M$:

  1. Bob使用自己的私钥$n_B$和Alice的公钥$P_A$计算共同密钥$K=n_BP_A=(n_An_B)G$
  2. Bob发送$c_1=P_B,~c_2=K+M$

Alice收到密文,解密过程:

  1. Alice计算共同密钥$K=n_Ac_1=n_AP_B=(n_An_B)G$
  2. Alice解密消息$M=c_2-K$

若$K=(x_K,y_K)$,则$-K=(x_k,-y_K)$。

再次提醒:上述过程中的加法、数乘运算均是椭圆曲线下的运算。

Online Calculator

ECCalculator - christelbach - $\mathbb{Z}_p$下的加法

Python Code

def ecAdd(P, Q, a, b, p):
    x_P, y_P = P
    x_Q, y_Q = Q
    if P == Q:
        lmd = (3*x_P*x_P+a)*pow(2*y_P,-1,p)%p
    elif x_P == x_Q:
        return (0, 0)
    else:
        lmd = (y_Q-y_P)*pow(x_Q-x_P,-1,p)%p
    x_R = (lmd*lmd-x_P-x_Q)%p
    y_R = (lmd*(x_P-x_R)-y_P)%p
    return (x_R, y_R)


def ecTimes(n, P, a, b, p):
    R = P
    for i in range(2, n+1):
        R = ecAdd(P, R, a, b, p)
        # print('{}P = ({}, {})'.format(i, R[0], R[1]))
    return R

椭圆曲线数乘运算 ecTimes() 可用类似快速幂的形式优化,但本人懒,就酱。

参看

密码编码学与网络安全——原理与实践(第七版)

椭圆曲线密码学 - Wikipedia

ECC椭圆曲线加密算法介绍 - 知乎

总结

终于知道本科的时候为什么不学且不考ECC了:

  • 看着很玄学
  • 推导略复杂
  • 做题套公式,计算复杂且易出错

说实话我觉得把公式贴在这里都是浪费时间。

读书患不多,思义患不明,患足己不学。既学患不行。

本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明来自 ComyDream
本文链接:http://comydream.github.io/2020/12/20/cryptography-ecc/