椭圆曲线加密算法

密码学学习笔记

 Liu Ke     2018-06-06   2900 words    & views

Contents

  1. 简介
  2. 椭圆曲线运算
  3. 有限域上的椭圆曲线运算
  4. 椭圆曲线Diffie-Hellman密钥交换
  5. 椭圆曲线ElGamal密码
  6. 椭圆曲线DSA(ECDSA)

有些部分配图要更容易理解一点,之后再补吧。

简介

椭圆曲线密码(Elliptic Curve Cryptography,ECC)是利用椭圆曲线来实现密码技术的统称,包括以下内容:

  • 基于椭圆曲线的公钥密码
  • 基于椭圆曲线的数字签名
  • 基于椭圆曲线的密钥交换

椭圆曲线密码可以用比RSA更短的密钥来实现同等的强度,即椭圆曲线密码密钥短但强度高

椭圆曲线一般方程如下,a,b,c,d为系数:

比特币中使用的数字签名算法为椭圆曲线DSA,它使用到的椭圆曲线方程为:

椭圆曲线运算

椭圆曲线上的加法运算

假设椭圆曲线上有两个点A和B,这样定义椭圆曲线上的A+B:

过点A和B作一条直线,找到这条直线与椭圆曲线的交点,这个交点关于x轴对称的那个点,即为点A+B。

因为椭圆曲线方程中存在\(y^{2}\)项,所以椭圆曲线必定关于x轴对称。

椭圆曲线上的二倍运算

当上文的加法运算中的两个点重合时,即A+A时,过两个点的直线有无数条。在这种情况下:

过点A作关于椭圆曲线的切线,找到这个切线与椭圆曲线的交点,这个交点关于x轴对称的点,即为点A+A,也就是2A。

椭圆曲线上的正负取反运算

将点A关于x轴对称位置的点定义为-A。

椭圆曲线上的无限远点

在椭圆曲线密码中,O用于表示无限远点。

对于A和-A的相加,根据定义的加法运算,找过A与-A的直线与椭圆曲线的交点,但是这条直线与椭圆曲线的交点只有A和-A这两个点。在这种情况下,我们可以认为这条直线与椭圆曲线的交点在无限远点O出。则下面的式子就可以成立:

可以发现,O与0的作用是差不多的。这样,我们就把椭圆曲线上简单的运算都定义出来了。

椭圆曲线上的离散对数问题

设椭圆曲线上的一个点G,可以根据这些运算求出2G,3G,4G…等点的坐标。但是反过来,“已知点xG求数x”这个问题是非常困难的。

密码学的一些技术,都是利用一些数学难题求解的复杂度:

  • RSA利用“质因数分解”的复杂度
  • ElGamal密码和Diffie-Hellman密钥交换利用“有限域上的离散对数问题”
  • 椭圆曲线密码利用“椭圆曲线上的离散对数问题”

椭圆曲线上的离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)的定义为:

已知椭圆曲线E、E上的一点G,以及G的x倍点xG,求x

有限域上的椭圆曲线运算

当x,y都是实数时,椭圆曲线的图形是一条光滑的曲线,称为“实数域R上的椭圆曲线”。

椭圆曲线密码使用到的椭圆曲线是在有限域\(F_p\)上。有限域\(F_p\)是指对于某个给定的质数p,由0,1,2,…,p-1共p个元素所组成的整数集合中定义的加减乘除运算。

直观一点说,实际上就是用整数来计算坐标,把计算的结果除以p求余数。

这里指的是特征数为质数p的素数域GF(p)。在密码学中,最常用的域是阶为p的素数域GF(p)或阶为\(2^m\)的GF(\(2^m\))域。

在这种情况下,有限域\(F_p\)上的椭圆曲线的图形就是一个个离散的点。

对于\(y^{2}=ax^{3}+bx^{2}+cx+d\)在有限域\(F_p\)上,每一个离散的点的坐标(x,y)都满足式子左边“\(y^2\)除以p的余数”等于式子右边“x的表达式的结果除以p的余数”。

其实,重点就是椭圆曲线上的离散对数问题非常难求解

椭圆曲线Diffie-Hellman密钥交换

非椭圆曲线的Diffie-Hellman密钥交换所利用的是:

以p为模,已知G和\(G^xmodp\)求x的复杂度(有限域上的离散对数问题)。

椭圆曲线Diffie-Hellman密钥交换利用的是:

在椭圆曲线上,已知G和xG求x的复杂度(椭圆曲线上的离散对数问题)。

假设通信双方为小王和小刘,他们需要共享一个对称密码的密钥,但是双方的通信线路已经被窃听,就可以通过椭圆曲线Diffile-Hellman密钥交换,具体过程如下:

  1. 小王向小刘发送点G(G不怕被窃听)。
  2. 小王生成随机数a。将a称为小王的私钥(这个a不用告诉小刘,也不能让窃听者获得)。
  3. 小刘生成随机数b。将b称为小刘的私钥(b也不用告诉小王,也不能让窃听者获得)。
  4. 小王向小刘发送点aG,这是小王的公钥(aG不怕被窃听)。
  5. 小刘向小王发送点bG,这是小刘的公钥(bG也不怕被窃听)。
  6. 小王接收到小刘发送的bG,计算abG,也就是点bG在椭圆曲线上的a倍,即a(bG)=abG。abG就是小王和小刘之间的共享密钥。
  7. 小刘接收到小王发送的aG,计算abG,也就是点aG在椭圆曲线上的b倍,即b(aG)=abG。abG就是小王和小刘之间的共享密钥。

这样,就完成了椭圆曲线上的Diffie-Hellman密钥交换。在这个过程中,即使G、aG和bG被窃听了,由椭圆曲线上的离散对数问题,窃听者也无法计算出a和b,也很难得到密钥abG。

如果每次通信都使用不同的随机数a和b,即使本次通信被破解,也能保证之前的通信内容的机密性,这就是前向安全性(Forward Secrecy,FS)。

椭圆曲线ElGamal密码

通过椭圆曲线Diffie-Hellman交换,小王和小刘可以得到共享密钥abG,就可以很容易实现椭圆曲线ElGamal密码。假设小王向小刘发送一条消息,将消息用椭圆曲线上的一个点M表示(实际使用的是这个点的x坐标)。

加密过程如下:

  1. 小王利用自己的私钥a和小刘的公钥bG,对消息M计算出点M+abG。密文为M+abG
  2. 小王向小刘发送密文M+abG。

解密过程如下:

  1. 小刘接收到密文M+abG。
  2. 小刘利用自己的私钥b和小王的公钥aG,计算出共享密钥abG。
  3. 小刘将密文M+abG减去共享密钥abG,即可得到消息M。

窃听者不能计算出abG,所以即使密文被窃取,也无法被破译。

椭圆曲线DSA(ECDSA)

通过椭圆曲线可以实现数字签名。比特币中使用的数字签名算法就是椭圆曲线DSA,具体细节我们之后再探讨。

假设小王对消息m加上数字签名,小刘对这个签名进行验证。

以下提到的“计算”都是以p为模的模运算。

生成数字签名

首先有一个椭圆曲线上的基点G,消息为m,消息的哈希值为h,小王的私钥为a,公钥为aG。具体过程如下:

  1. 小王由随机数r和基点G,求出点\(rG=(x,y)\)
  2. 小王由随机数r、消息m、消息的哈希值h和私钥a,计算\(s=\frac{h+ax}{r}\)
  3. 小王将消息m、点\(rG=(x,y)\)和s发给Bob

这里的点rG和s就是数字签名

验证数字签名

小刘对接收到的信息验证数字签名,具体过程如下:

  1. 小刘接收到消息m、点\(rG=(x,y)\)和s
  2. 小刘由m求出消息的哈希值h
  3. 小刘利用小王的公钥aG计算下面的式子:
  1. 将上一步的计算结果同rG进行比较,如果相等,则证明签名正确:

攻击者没有小王的私钥a,无法计算出s。当随机数r改变时,数字签名也会改变。