【密码学】椭圆曲线密码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高,而且可能涉及专利。

椭圆曲线

椭圆曲线 $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() 可用类似快速幂的形式优化,但本人懒,就酱。

参看

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

椭圆曲线密码学 - 维基百科

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

总结

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

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

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

本科的时候竟然没发现DH这么有用?

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

禁止商业用途,非商业分享转载请注明来源。
本文链接:http://comydream.github.io/2020/12/20/cryptography-ecc/