当前位置:   article > 正文

椭圆曲线密码体制(ECC)简介

ecc私钥为什么不能取到n-1

一、椭圆曲线的基本概念

简单的说椭圆曲线并不是椭圆,之所以称为椭圆曲线是因为他们是用三次方程来表示,并且该方程与计算椭圆周长的方程相似。

   对密码学比较有意义的是基于素数域GF(p)和基于二进制域(GF(2^m))上的椭圆曲线。

   下面重点介绍基于GF(p)上的椭圆曲线:

                 y^2 º x^3 + a*x + b(modp)

 其中p是素数,a和b满足:4a^3 + 27b^2 (mod p) ¹ 0

 满足上述方程的整数对(x, y), 就叫椭圆曲线上的点。

素数域

其实域就是一个集合,在其上面进行加,减,乘,除运算而封闭。比如有理数集合,实数集合,复数集合,这些都是无限域,在密码学中没有什么实际意义,所以考虑与整数有关的域,对密码学有实际意义。

研究最多的就是素数域GF(p)。我的理解就是一个素数p,在集合[0…p-1]上定义一个模加,一个模乘,就构成了一个有限素数域,比如取p = 5,定义如下模加, 模乘:

模加

+

0

1

2

3

4

0

0

1

2

3

4

1

1

2

3

4

0

2

2

3

4

0

1

3

3

4

0

1

2

4

4

0

1

2

3

模乘

+

0

1

2

3

4

0

0

0

0

0

0

1

0

1

2

3

4

2

0

2

4

1

3

3

0

3

1

4

2

4

0

4

3

2

1

下面以连续的椭圆曲线为例介绍一下椭圆曲线上

 的点的运算规则

  椭圆曲线上点的加法定义

    对于椭圆曲线上的任意两点P(x1, y1),

      Q(x2, y2),R = (x3, y3), 其中R = P+Q

  具体描述如下:

     X3 = K^2 – X1 – X2(modp)

     y3 = k(x1-x3) – y1 (modp)

  其中

  当P不等于Q时

     K = (y2 – y1)/(x2 – x1) (modp)

  当P等于Q时

    k = (3*x1^2 + a)/2*y1 (modp)

  19_2197_7

零元   

       对椭圆曲线上的任意一点P(x1, y1), 有

      P + O = O + P = P

          如右图

负元

     -P = (x1, -y1)

     P – P = O

     O = -O

       其中O为无穷远点,一条与Y轴平行的直线

       只有一个无穷点O

纯量乘法

KP = P+P+P+…+P  K个P相加

19_2197_8

 

基于GF(p)上的椭圆曲线举例

P = 23, a = 1, b = 0

方程:y^2 = x^3 + x(mod23)

椭圆曲线上的点:

(0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5)

(13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10)

(18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17)

和无穷远点O构成椭圆曲线上的加法群

其点运算规则和上面讲到的连续椭圆曲线

上的运算规则是相同的

ec3_1

二、椭圆曲线离散对数在密码中的应用

公钥密码算法总要基于一个数学难题,比如RSA的依据是给定两个数p, q很容易相乘得到N, 而对n进行因式分解则相对困难的多。椭圆曲线密码体制(ECC)采用的数学难题则是求椭圆曲线加法群的离散对数问题,具体描述如下:

Q = kG

其中Q为椭圆曲线上的点, G为椭圆曲线上的基点,k 为小于n的整数,n为G的阶即, nG = O

根据上节提到的纯量乘法知道k, G不难求出Q, 但是给定Q, G求k就相对困难了,这就叫椭圆曲线加法群上的离散对数问题。

   上述整数k,就是ECC私钥, Q为公钥, 可以利用此密钥对进行加密,解密,签名,验证等公私钥运算。

  根据上节提到的纯量乘法知道k, G不难求出Q, 但是给定Q, G求k就相对困难了,这就叫椭圆曲线加法群上的离散对数问题。

   上述整数k,就是ECC私钥, Q为公钥, 可以利用此密钥对进行加密,解密,签名,验证等公私钥运算。

三、ECDSA简单介绍

下面简单介绍一下基于GF(p)的椭圆曲线数字签名算法(ECDSA)

预备数据: h(待签名Hash值),公钥Q,私钥d

签名过程:

1. 选取一个随机数k;

2. 计算k = kmodn, 如果k =0返回第1步重新选取;

3. 计算kG = (x1, y1);

4. 计算r = x1mondn;

5. 如果r = 0返回第2步;

6. 计算s = k^-1*(h+ dr )modn;

7. 如果s = 0, 返回第2步;

其中(r, s)为签名结果。

验证过程:

 1. 验证1=<r<=n-1, 若不成立返回false

 2. 验证1=<s<=n-1, 若不成立返回false

 3. 计算c = s^-1modn

 4. 计算u1 = e’*c modn, u2 = r*c mon n

 5. 计算u1*G+u2*Q = (x1, y1), 如果(x1, y1)为O 返回false

 6. 计算v = x1modn;

 7. 如果r != v 返回false

 8. 返回true

四、 ECC与RSA的比较

椭圆曲线加密技术(ECC)是建立在单向函数(椭圆曲线离散对数)得基础上,由于它比RAS使用得离散对数要复杂得多。而且该单向函数比RSA得要难。

如160位ECC与1024位RSA有相同的安全强度。而210位ECC则与2048bitRSA具有相同的安全强度

计算量小,处理速度快虽然在RSA中可以通过选取较小的公钥(可以小到3)的方法提高公钥处理速度,即提高加密和签名验证的速度,使其在加密和签名验证速度上与ECC有可比性,但在私钥的处理速度上(解密和签名),ECC远比RSA、DSA快得多。因此ECC总的速度比RSA、DSA要快得多。

存储空间占用小ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多,意味着它所占的存贮空间要小

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号