《ECC算法和加密应用大全》由会员分享，可在线阅读，更多相关《ECC算法和加密应用大全（24页珍藏版）》请在金锄头文库上搜索。
1、ECCECC 算法和加密应用大全算法和加密应用大全（一）（一）基本原理基本原理ECC（Elliptic Curves Cryptography）加密算法是一种公钥加密算法，与主流的 RSA 算法相比，ECC 算法可以使用较短的密钥达到相同的安全程度。近年来，人们对 ECC 的认识已经不再处于研究阶段，开始逐步进入实际应用，如国家密码管理局颁布的 SM2 算法就是基于 ECC 算法的。下面我们来认识一下 ECC 的工作原理。椭圆曲线椭圆曲线定义定义在引入椭圆曲线之前，不得不提到一种新的坐标系-射影平面坐标系，它是对笛卡尔直角坐标系的扩展，增加了无穷远点的概念。在此坐标系下，两条平行的直线是有交点
2、的，而交点就是无穷远点。两者的变换关系为：笛卡尔坐标系中的点 a（x,y），令 x=X/Z，y=Y/Z，则射影平面坐标系下的点 a的坐标为（X,Y,Z)，如点（2,3）就转换为（2Z,3Z,Z）。椭圆曲线定义：一条椭圆曲线在射影平面上满足方程：Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3的所有点的集合，且曲线上每个点都是非奇异的。该方程有名维尔维斯特拉斯方程，椭圆曲线的形状不是椭圆，只是因为其描述的方程类似于计算一个椭圆周长的方程。转换到笛卡尔坐标系下的方程为：y y2 2+a+a1 1xy+axy+a3 3y y = = x x3 3+a+a2 2x x2 2+a+
3、a4 4x+ax+a6 6加法法则加法法则运算法则：任意取椭圆曲线上两点 P、Q （若 P、Q 两点重合，则做 P 点的切线）做直线交于椭圆曲线的另一点 R，过 R做 y 轴的平行线交于 R。我们规定 P+Q=R。（如图）此处+不是简单的实数相加，是抽象出来的O+P=P，O为零元曲线上三个点 A,B,C 处于一条直线上，则 A+B+C=O下面，我们利用 P、Q 点的坐标(x1,y1)，(x2,y2)，求出 R=P+Q 的坐标(x4,y4)。P,Q,R共线，设为 y=kx+b，若 PQ，k=(y1-y2)/(x1-x2)若 P=Q，k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3
4、)解方程组得到：x4=k2+ka1-a2-x1-x2; y4=k(x1-x4)-y1-a1x4-a3;密码学中的椭圆曲线密码学中的椭圆曲线定义定义在有限域 Fp 中定义一个椭圆曲线，常用 y2=x3+ax+bFp 中只有 p 个元素，p 为素数Fp 中，a+bc (mod p)，abc (mod p)，a/bc (mod p)4a3+27b20 (mod p) a，b 是小于 p 的非负整数x，y 属于 0 到 p-1 间的证书，曲线标记为 Ep（a，b）阶：椭圆曲线上一点 P，存在正整数 n，使得 nP=O，则 n 为 P 的阶，若 n 不存在，则 P 是无限阶的，有限域上定义的椭圆曲线上所
5、有点的阶都存在。椭圆曲线难题椭圆曲线难题K=kG，其中 K,G 为 Ep（a,b）上的点，k 为小于 n 的整数，n 是点 G 的阶，给定k 和 G，计算 K 容易，但是给定 K 和 G，求 k 就很难了！因此，设 K 为公钥，k 为私钥，G 为基点。加密过程加密过程A 选定一条椭圆曲线 Ep（a,b），并取曲线上一点作为基点 GA 选择一个私钥 k，并生成公钥 K=kGA 将 Ep（a,b）和 k，G 发送给 BB 收到后将明文编码到 Ep（a,b）上一点 M，并产生一个随机数 rB 计算点 C1=M+rK，C2=rGB 将 C1，C2 传给 AA 计算 C1-kC2=M+rkG-krG=M
6、A 对 M 解码得到明文攻击者只能得到 Ep（a,b），G，K，C1，C2，没有 k 就无法得到 M。签名验签流程签名验签流程A 选定一条椭圆曲线 Ep（a，b），并取曲线上一点作为基点 GA 选择一个私钥 k，并生成公钥 K=kGA 产生一个随机数 r，计算 R(x,y)=rGA 计算 Hash=SHA(M)，M=M(modp)A 计算 S=（Hash+Mk）/r(modp)B 获得 S 和 M，Ep(a,b)，K，R(x,y)B 计算 Hash=SHA(M)，M=M(modp)B 计算 R=（Hash*G+M*K）/S=(Hash*G+M*kG)*r/(Hash+Mk)=rG=R（x,y）
7、，若 R=R，则验签成功。以上加解密和签名验签流程只是一个例子，具体应用时可以利用 K=kG 这一特性变幻出多种加解密方式。好了 ECC 加密算法的介绍就到这里了。（二）羽毛币（二）羽毛币应用应用ECC 算法是基于有限域的椭圆曲线上的数学算法。关于 ECC 算法基本原理的介绍，请参考ECC 加密算法入门介绍（http:/ Bitcoin 系统中采用的公钥密码学方案和签名算法的实现细节。一、一、 公钥公钥(pubkey)(pubkey)、私钥、私钥(privkey)(privkey)是什么是什么公开密钥加密（public-key cryptography，也称为非对称(密钥)加密），是指存在一对
8、数学算法相关的密钥，使用其中一个密钥加密后所得的信息，只能用另一个密钥才能解密。如果其中一个公开后并不会危害到另外一个的秘密性质，则称公开的密钥为公钥，不公开的密钥为私钥。公钥的主要作用：加密；验证签名。私钥的主要作用：签名；解密。特性：通过私钥可以计算出公钥，反之则不行。公钥加密：公钥加密的内容可以用私钥来解密只有私钥持有者才能解密。私钥签名：私钥签名的内容可以用公钥验证。公钥能验证的签名均可视为私钥持有人所签署。以上特性通过数学算法来保证。公钥密码学的实现方案有很多种， 常见的有RSA、ElGamal、迪菲赫尔曼密钥交换协议中的公钥加密算法、椭圆曲线加密算法（ECC）。网银系统中主要使用的
9、是 RSA 方案。比特币系统则使用的是 ECC 方案，在核心实现中并不使用加密，只使用了签名算法来确保交易的真实性和所有权的认证。二、椭圆曲线加密算法二、椭圆曲线加密算法(ECC)(ECC)简介简介ECC 方案通常包含有三方面内容，数字签名方案、加密和密钥传输方案、以及密钥协商方案。本文只涉及到比特币系统所使用的数字签名方案。（一）有限域(Finite Field)：(最近有一些关于量子攻击的讨论中涉及到这一概念，有一定数学基础的和毫无数学基础的可以跳过这一小节）域(Field)的特性是集合 F 中的所有元素经过定义后的加法和乘法运算，所得结果仍包含于 F（在加法和乘法上封闭）。无限域的元素个
10、数无限，比如有理数域、实数域。有限域的元素个数有限，这就出现一个问题，假设 F 为从 0 至 9 的整数集合，那么 5，6 都属于 F，但常规的加法定义 5+6=11，11 不属于 F。因而，有限域需要定义加法和乘法，使其满足对加法和乘法的封闭。目前已发现，当且仅当元素个数 q 为质数或某个质素的 n 次幂时，必有一个元素个数为 q 的有限域存在。另外，对于每一个符合这一条件的 q 值，都恰有一个有限域。含有 q 个元素的有限域记作：Fq。ECC 方案中只使用了两类有限域：一种称为质数有限域 Fp，其中 q = p, p 为一个质数；另一种称为基于特征值 2 的有限域 F2m，其中 q = 2
11、m , m 1。比特币系统使用的是第一种。Fp 是一个0,1,p-1的整数集合，有限域 Fp 中定义了加法：a + b r (mod p)乘法：ab s(mod p).（二）基于有限域 Fp 的椭圆曲线域 E(Fp)：椭圆曲线：y2 x3 + ax + b (mod p)当：a, b Fp 且满足 4a3+27b2 0 (mod p). ， x, y Fp 时，这条曲线上的点的集合 P=(x,y)就构成了一个基于有限域 Fp 的椭圆曲线域 E(Fp)，元素个数记作#E(Fp)。问：这和比特币系统有什么关系吗？答：公钥即为该曲线上的某个点 Q=(x,y)的二进制输出格式。公钥可以压缩，是因为 y
12、 可以根据 x 通过曲线函数计算出来。（三）椭圆曲线域 E（Fp)的描述参数：E : y2 x3 + ax + b (mod p)为描述特定的椭圆曲线域，需明确六个参数：T = (p, a, b, G, n, h)p: 代表有限域 Fp 的那个质数a,b：椭圆方程的参数G: 椭圆曲线上的一个基点 G = (xG, yG)n：G 在 Fp 中规定的序号，一个质数。h：余因数（cofactor），控制选取点的密度。h = #E(Fp) / n。比特币系统选用的 secp256k1 中，参数为p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFF
13、FFF FFFFFFFE FFFFFC2F= 2256 232 29 28 27 26 24 1a = 0， b = 7G =04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D959F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448A6855419 9C47D08F FB10D4B8n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141h = 01问：n 和比特币系统有什
14、么关系？答：比特币系统规定私钥的取值范围最大不能超过 n。（四）公钥和私钥：随机从1,n-1中选取一个数 d, 计算 Q = dG。其中，d 就是私钥，而 Q 即为公钥。这一算式看起来很简单，但这怎样保证由 Q 不能算出 d 呢？有限域中的加法和乘法是有特殊规定的。基于 Fp 的椭圆曲线点的集合域中，加法运算是：不同的点相加： (x1, y1) E(Fp) ， (x2, y2) E(Fp)， x1 x2(x1, y1) + (x2, y2) = (x3, y3)，其中，x3 2 x1 x2 (mod p), y3 (x1 x3) y1 (mod p), 而 （y2 y1）/（x2 x1）(mo
15、d p).相同点叠加： (x1, y1) E(Fp) , y1 0.(x1, y1) + (x1, y1) = (x3, y3), 其中，x3 2 21 (mod p), y3 (x1 x3) y1 (mod p), and(312+ a)/2y1(mod p).dG 是一个标量乘法，可以转化为加法运算，如果有爱好者想由公钥逆推出私钥，可以根据这些公式来尝试一下（笔者本人已经放弃了这种努力）。三、 椭圆曲线数字签名算法(ECDSA)：用户的密钥对:（d, Q）；(d 为私钥，Q 为公钥)待签名的信息：M；签名：Signature(M) = ( r, s)签名过程：1、根据 ECC 算法随机生成
16、一个密钥对(k, R), R=(xR, yR)2、令 r = xR mod n，如果 r = 0，则返回步骤 13、计算 H = Hash(M)4、按照数据类型转换规则，将 H 转化为一个 big endian 的整数 e5、s = k-1 (e + rd) mod n，若 s = 0, 则返回步骤 16、输出的 S =(r,s)即为签名。验证过程：1、 计算 H = Hash(M)2、按照数据类型转换规则，将 H 转化为一个 big endian 的整数 e3、计算 u1 = es-1 mod n, u2 = rs-1 mod n4、计算 R = (xR, yR) = u1G + u2Q, 如果 R = 零点，则验证该签名无效5、令 v = xR mo
