椭圆曲线加密算法ECC

一、介绍

ECC是基于椭圆曲线数学原理的一种非对称加密算法。相比RSA，ECC可以使用更短的秘钥来实现与RSA相当或更高的安全。椭圆曲线在密码学中的使用，是1985年由Neal Koblitz 和Victor Miller分别独立提出的。目前椭圆曲线主要采用的有限域有以素数为模的整数域GF（p）和特征为2的伽罗华域GF（）。

二、数学知识

1.椭圆曲线

1>方程

    定义式:

    最常用方程：,判别式

     注：椭圆曲线的定义要求曲线是非奇异的，即图像里没有尖点、自相交或孤立点。代数上，想要成立当且仅当

2>运算规则

• 加法

过曲线任意两点（A、B）的连线与椭圆曲线的交点关于x轴对称的点，定义为A+B

• 二倍

椭圆曲线在A点的切线与椭圆曲线的交点关于x轴对称的点，定义为2A

• 正负取反

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

• 无穷远点

如果A=（-A），过A和-A点的直线与y轴平行，可以认为直线与y轴相交于无穷远点。

3>点的阶

椭圆曲线上任意一点P，设存在最小正整数n，使得np=〇，n为P的阶；若n不存在，则P是无限阶。

2.有限域

1>GF(p)指给定一个质数p,由0-（p-1）共p个元素组成的整数集合中定义的加减乘除运算。

eg:椭圆曲线：,其在有限域GF(23)上，写作：

此时，椭圆曲线是不连续点

2>性质：

• Fp的加法
• 乘法
• 除法
• Fp的单位元是1，零元是〇
• Fp域内运算满足交换律、结合律、分配律

3.椭圆曲线在有限域上的运算

1>若P（x，y）是椭圆曲线上的点，那么-P(x,-y)也是椭圆曲线上的点

2>计算xG（代数加法）

xG是以加法的形式实现的。设xG的点为R，R=P+Q，即直线P、Q的斜率

GF(p)上：，若,且,则R=P+Q,R的坐标由如下规则确定：

其中 

三、加密

1.椭圆曲线要形成一条光滑曲线，要求x、y均为实数，但椭圆曲线加密算法，使用的是有限域。

2.加密原理：椭圆曲线已知G和xG,求x是非常困难的。k=x为私钥，K=xG为公钥，G为椭圆曲线上的点，称为基点。

公钥加密：选择随机数r,密文是一个点对，C={rG,M+rK}

私钥解密：M+rK-k(rG)=M+r(kG)-k(rG)=M            （M+r*公钥-私钥*rG=M）

四、椭圆曲线签名算法（ECDSA）

1、私钥签名：

• 选择随机数r,计算rG（x,y）
• 根据r,M的哈希h,私钥k,计算s = (h+kx)/r
• 发送M和签名{rG,s}

2、公钥验证

• 接受信息
• 根据M求哈希h
• 使用公钥K，验证（hG/s+xk/s）是否等于rG,如果成立，则验证成功。

3.签名过程

DSA签名的第一个步骤是对待签名的消息生成一个消息摘要，不同的签名算法使用不同的消息摘要算法，而ECDSA256使用SHA256生成256比特的摘要。

摘要生成结束后，应用签名算法对摘要进行签名：

• 产生一个随机数k
• 利用随机数k，计算出两个大数r和s。将r和s拼在一起就构成了对消息摘要的签名。

这里需要注意的是，因为随机数k的存在，对于同一条消息，使用同一个算法，产生的签名是不一样的。从函数的角度来理解，签名函数对同样的输入会产生不同的输出。因为函数内部会将随机值混入签名的过程。