ECC算法原理的认识

灰太狼 2021-09-10 10:50 396阅读 0赞

公开密钥算法总是要基于一个数学上的难题。比如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，等价于E\*D-1=K\*M
4.  经过上述准备工作之后，可以得到：
    
     *  E是公钥，负责加密
     *  D是私钥，负责解密
     *  N负责公钥和私钥之间的联系
5.  加密算法，假定对X进行加密
    
     *  (X ^ E) % N = Y
6.  解密算法，根据费尔马小定义，可以使用以下公式完成解密
    
     *  (Y ^ D) % N = X

备注：RSA算法原理可以参考阮一峰的一篇博文[<RSA算法原理][RSA][>][RSA]  也可参考[维基百科][Link 1]

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

ECC是建立在基于**椭圆曲线的离散对数问题**上的密码体制，给定椭圆曲线上的一个点G，并选取一个整数k，求解K=kG很容易(注意根据kG求解出来的K也是椭圆曲线上的一个点)；反过来，在椭圆曲线上给定两个点K和G，若使K=kG，求整数k是一个难题。ECC就是建立在此数学难题之上,这一数学难题称为椭圆曲线离散对数问题。其中椭圆曲线上的点K则为公钥(注意公钥K不是一个整数而是一个椭圆曲线点，这个点在OpenSSL里面是用结构体EC\_Point来表示的，为了加深理解，建议自行下载OpenSSL进行查看学习)，整数k则为私钥(实际上是一个大整数)。

不知我说明白了没有，这是网上的一位网友总结的，供参考：  
考虑如下等式：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)来定义一条椭圆曲线的方法如下：

EC_GROUP *create_curve(void)
    {
    	BN_CTX *ctx;
    	EC_GROUP *curve;
    	BIGNUM *a, *b, *p, *order, *x, *y;
    	EC_POINT *generator;
    
    	/* Binary data for the curve parameters */
    	unsigned char a_bin[28] =
    		{0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
    		0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,
    		0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE};
    	unsigned char b_bin[28] =
    		{0xB4,0x05,0x0A,0x85,0x0C,0x04,0xB3,0xAB,0xF5,0x41,
    		0x32,0x56,0x50,0x44,0xB0,0xB7,0xD7,0xBF,0xD8,0xBA,
    		0x27,0x0B,0x39,0x43,0x23,0x55,0xFF,0xB4};
    	unsigned char p_bin[28] =
    		{0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
    		0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,
    		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01};
    	unsigned char order_bin[28] =
    		{0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
    		0xFF,0xFF,0xFF,0xFF,0x16,0xA2,0xE0,0xB8,0xF0,0x3E,
    		0x13,0xDD,0x29,0x45,0x5C,0x5C,0x2A,0x3D };
    	unsigned char x_bin[28] =
    		{0xB7,0x0E,0x0C,0xBD,0x6B,0xB4,0xBF,0x7F,0x32,0x13,
    		0x90,0xB9,0x4A,0x03,0xC1,0xD3,0x56,0xC2,0x11,0x22,
    		0x34,0x32,0x80,0xD6,0x11,0x5C,0x1D,0x21};
    	unsigned char y_bin[28] =
    		{0xbd,0x37,0x63,0x88,0xb5,0xf7,0x23,0xfb,0x4c,0x22,
    		0xdf,0xe6,0xcd,0x43,0x75,0xa0,0x5a,0x07,0x47,0x64,
    		0x44,0xd5,0x81,0x99,0x85,0x00,0x7e,0x34};
    
    	/* Set up the BN_CTX */
    	if(NULL == (ctx = BN_CTX_new())) handleErrors();
    
    	/* Set the values for the various parameters */
    	if(NULL == (a = BN_bin2bn(a_bin, 28, NULL))) handleErrors();
    	if(NULL == (b = BN_bin2bn(b_bin, 28, NULL))) handleErrors();
    	if(NULL == (p = BN_bin2bn(p_bin, 28, NULL))) handleErrors();
    	if(NULL == (order = BN_bin2bn(order_bin, 28, NULL))) handleErrors();
    	if(NULL == (x = BN_bin2bn(x_bin, 28, NULL))) handleErrors();
    	if(NULL == (y = BN_bin2bn(y_bin, 28, NULL))) handleErrors();
    
    	/* Create the curve */
    	if(NULL == (curve = EC_GROUP_new_curve_GFp(p, a, b, ctx))) handleErrors();
    
    	/* Create the generator */
    	if(NULL == (generator = EC_POINT_new(curve))) handleErrors();
    	if(1 != EC_POINT_set_affine_coordinates_GFp(curve, generator, x, y, ctx))
    		handleErrors();
    
    	/* Set the generator and the order */
    	if(1 != EC_GROUP_set_generator(curve, generator, order, NULL))
    		handleErrors();
    
    	EC_POINT_free(generator);
    	BN_free(y);
    	BN_free(x);
    	BN_free(order);
    	BN_free(p);
    	BN_free(b);
    	BN_free(a);
    	BN_CTX_free(ctx);
    
    	return curve;
    }

关于ECC的网站：[https://wiki.openssl.org/index.php/Elliptic\_Curve\_Cryptography][https_wiki.openssl.org_index.php_Elliptic_Curve_Cryptography]

[ http://blog.csdn.net/dog250/article/details/5540500][http_blog.csdn.net_dog250_article_details_5540500]

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

struct ec_key_st {
    	int version;
    
    	EC_GROUP *group;
    
    	EC_POINT *pub_key;
    	BIGNUM	 *priv_key;
    
    	unsigned int enc_flag;
    	point_conversion_form_t conv_form;
    
    	int 	references;
    	int	flags;
    
    	EC_EXTRA_DATA *method_data;
    } /* EC_KEY */;

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

/* create new ecdsa key (== EC_KEY) */
    		if ((eckey = EC_KEY_new()) == NULL)
    			goto builtin_err;
    		group = EC_GROUP_new_by_curve_name(nid);
    		if (group == NULL)
    			goto builtin_err;
    		if (EC_KEY_set_group(eckey, group) == 0)
    			goto builtin_err;
    		EC_GROUP_free(group);

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

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

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

更多ECC的资料

1. [ 维基百科搜索椭圆曲线密码学][Link 2]  维基百科中文网站https://wc.yooooo.us/wiki

[RSA]: http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
[Link 1]: https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
[https_wiki.openssl.org_index.php_Elliptic_Curve_Cryptography]: https://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography
[http_blog.csdn.net_dog250_article_details_5540500]: http://blog.csdn.net/dog250/article/details/5540500
[Link 2]: https://wc.yooooo.us/wiki/%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF%E5%AF%86%E7%A0%81%E5%AD%A6