ECC算法原理的认识

公开密钥算法总是要基于一个数学上的难题。比如RSA 依据的是：给定两个素数p、q 很容易相乘得到n，而对n进行因式分解却相对困难。RSA 算法原理具体如下：

1. 找出两个“很大”的质数：P & Q 
   N = P * Q 
   M = (P – 1) * (Q – 1)

2. 找出整数E，E与M互质，即除了1之外，没有其他公约数

3. 找出整数D，使得 ED 除以 M 余 1，即 (E D) % M = 1

4. 经过上述准备工作之后，可以得到：

   • E是公钥，负责加密
   • D是私钥，负责解密
   • N负责公钥和私钥之间的联系

5. 加密算法，假定对X进行加密

   • (X ^ E) % N = Y

6. 解密算法，根据费尔马小定义，可以使用以下公式完成解密

   • (Y ^ D) % N = X

接下来我们看下椭圆曲线上是基于什么难题的？

考虑如下等式：
K=kG [其中 K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数]，不难发现，给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。这就是椭圆曲线加密算法采用的难题，我们把点G称为基点（base point）。现在我们描述一个利用椭圆曲线进行加密通信的过程：

1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。
2、用户A选择一个私有密钥k，并生成公开密钥K=kG。
3、用户A将Ep(a,b)和点K，G传给用户B。
4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r。
5、用户B计算点C1=M+rK；C2=rG。
6、用户B将C1、C2传给用户A。
7、用户A接到信息后，计算C1-kC2，结果就是点M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M
      再对点M进行解码就可以得到明文。

在这个加密通信中，如果有一个偷窥者H ，他只能看到Ep(a,b)、K、G、C1、C2，而通过K、G 求k 或通过C2、G求r 都是相对困难的，因此，H无法得到A、B间传送的明文信息。

 

密码学中，描述一条Fp上的椭圆曲线，常用到六个参量：T=(p,a,b,n,x,y)。
（p 、a 、b） 用来确定一条椭圆曲线，p为素数域内点的个数，a和b是其内的两个大数；
x,y为G基点的坐标，也是两个大数；
n为点G基点的阶；
以上六个量就可以描述一条椭圆曲线，有时候我们还会用到h(椭圆曲线上所有点的个数p与n相除的整数部分)。

利用这六个量T=(p,a,b,n,x,y)来定义一条椭圆曲线的方法如下：

[cpp] view plain copy

print?

1. EC_GROUP *create_curve(void)  
2. {  
3.     BN_CTX *ctx;  
4.     EC_GROUP *curve;  
5.     BIGNUM *a, *b, *p, *order, *x, *y;  
6.     EC_POINT *generator;  
7.   
8.     /* Binary data for the curve parameters */  
9.     unsigned char a_bin[28] =  
10.         {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,  
11.         0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,  
12.         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE};  
13.     unsigned char b_bin[28] =  
14.         {0xB4,0x05,0x0A,0x85,0x0C,0x04,0xB3,0xAB,0xF5,0x41,  
15.         0x32,0x56,0x50,0x44,0xB0,0xB7,0xD7,0xBF,0xD8,0xBA,  
16.         0x27,0x0B,0x39,0x43,0x23,0x55,0xFF,0xB4};  
17.     unsigned char p_bin[28] =  
18.         {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,  
19.         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,  
20.         0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01};  
21.     unsigned char order_bin[28] =  
22.         {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,  
23.         0xFF,0xFF,0xFF,0xFF,0x16,0xA2,0xE0,0xB8,0xF0,0x3E,  
24.         0x13,0xDD,0x29,0x45,0x5C,0x5C,0x2A,0x3D };  
25.     unsigned char x_bin[28] =  
26.         {0xB7,0x0E,0x0C,0xBD,0x6B,0xB4,0xBF,0x7F,0x32,0x13,  
27.         0x90,0xB9,0x4A,0x03,0xC1,0xD3,0x56,0xC2,0x11,0x22,  
28.         0x34,0x32,0x80,0xD6,0x11,0x5C,0x1D,0x21};  
29.     unsigned char y_bin[28] =  
30.         {0xbd,0x37,0x63,0x88,0xb5,0xf7,0x23,0xfb,0x4c,0x22,  
31.         0xdf,0xe6,0xcd,0x43,0x75,0xa0,0x5a,0x07,0x47,0x64,  
32.         0x44,0xd5,0x81,0x99,0x85,0x00,0x7e,0x34};  
33.   
34.     /* Set up the BN_CTX */  
35.     if(NULL == (ctx = BN_CTX_new())) handleErrors();  
36.   
37.     /* Set the values for the various parameters */  
38.     if(NULL == (a = BN_bin2bn(a_bin, 28, NULL))) handleErrors();  
39.     if(NULL == (b = BN_bin2bn(b_bin, 28, NULL))) handleErrors();  
40.     if(NULL == (p = BN_bin2bn(p_bin, 28, NULL))) handleErrors();  
41.     if(NULL == (order = BN_bin2bn(order_bin, 28, NULL))) handleErrors();  
42.     if(NULL == (x = BN_bin2bn(x_bin, 28, NULL))) handleErrors();  
43.     if(NULL == (y = BN_bin2bn(y_bin, 28, NULL))) handleErrors();  
44.   
45.     /* Create the curve */  
46.     if(NULL == (curve = EC_GROUP_new_curve_GFp(p, a, b, ctx))) handleErrors();  
47.   
48.     /* Create the generator */  
49.     if(NULL == (generator = EC_POINT_new(curve))) handleErrors();  
50.     if(1 != EC_POINT_set_affine_coordinates_GFp(curve, generator, x, y, ctx))  
51.         handleErrors();  
52.   
53.     /* Set the generator and the order */  
54.     if(1 != EC_GROUP_set_generator(curve, generator, order, NULL))  
55.         handleErrors();  
56.   
57.     EC_POINT_free(generator);  
58.     BN_free(y);  
59.     BN_free(x);  
60.     BN_free(order);  
61.     BN_free(p);  
62.     BN_free(b);  
63.     BN_free(a);  
64.     BN_CTX_free(ctx);  
65.   
66.     return curve;  
67. }  

关于ECC的网站：https://wiki./index.php/Elliptic_Curve_Cryptography

                            http://blog.csdn.net/dog250/article/details/5540500

2.在非对称密钥体系中，用私钥进行签名公钥进行验签，但是对于ECC而言，在做签名与验签的时候除了私钥与公钥外还需要私钥与公钥对应的椭圆曲线，因为在签名和验签的过程中会涉及到多倍点的乘法，多倍点乘法会涉及到椭圆曲线。下面是OpenSSL中ECC所涉及到的ECC_KEY:

[cpp] view plain copy

print?

1. struct ec_key_st {  
2.     int version;  
3.   
4.     EC_GROUP *group;  
5.   
6.     EC_POINT *pub_key;  
7.     BIGNUM   *priv_key;  
8.   
9.     unsigned int enc_flag;  
10.     point_conversion_form_t conv_form;  
11.   
12.     int     references;  
13.     int flags;  
14.   
15.     EC_EXTRA_DATA *method_data;  
16. } /* EC_KEY */;  

其中，第三个和四个参数分别是公钥和私钥，而第二个参数就是私钥与公钥对应的曲线，在程序中往往通过函数EC_KEY_set_group(eckey, group)对EC_KEY的grope进行赋值(将grope赋值给eckey)：

[cpp] view plain copy

print?

1. /* create new ecdsa key (== EC_KEY) */  
2.     if ((eckey = EC_KEY_new()) == NULL)  
3.         goto builtin_err;  
4.     group = EC_GROUP_new_by_curve_name(nid);  
5.     if (group == NULL)  
6.         goto builtin_err;  
7.     if (EC_KEY_set_group(eckey, group) == 0)  
8.         goto builtin_err;  
9.     EC_GROUP_free(group);  

上面这段代码摘自OpenSSL自带的Demo：crypto\ecdsa\ecdsatest.c。

所以，对于ECC算法来说，仅仅知道公钥和私钥是不能调用OpenSSL自带的签名和验签API，还需要知道对应的椭圆曲线：

[cpp] view plain copy

print?

1. int ECDSA_sign(int type, const unsigned char *dgst, int dlen, unsigned char   
2.         *sig, unsigned int *siglen, EC_KEY *eckey)  
3. int ECDSA_verify(int type, const unsigned char *dgst, int dgst_len,  
4.         const unsigned char *sigbuf, int sig_len, EC_KEY *eckey)