分类
未分类

椭圆曲线加密算法(Elliptic curve cryptography)ECC

ECC是什么:

ECC是Elliptic Curve Cryptography(椭圆曲线密码学)的缩写,是一种基于椭圆曲线数学的公开密钥加密算法,其本质是利用离散对数问题实现加密。

ECC的主要优势,是在使用更小的密钥的同时,提供更快的性能和更高等级的安全。

椭圆曲线的普通方程:

适合加密的椭圆曲线方程:

椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]:

y²=x²+ax+b(mod p)

选择两个满足下列约束条件的小于P的非法与整数,是为了保证曲线不包含奇点(在数学中指的是曲线任意一点都存在切线)

4a+27b²≠ 0

椭圆曲线要形成一条光滑的曲线,要求x,y取值均为实数,即实数域上的椭圆曲线。但椭圆曲线加密算法,并非使用实数域,而是使用有限域。按数论定义,有限域GF(p)指给定某个质数p,由0、1、2……p-1共p个元素组成的整数集合中定义的加减乘除运算。

而ECC算法是在有限域Fp定义公式:Q=kP,已知大数k和点P的情况下,很容易求点Q,但是已知的点P、点Q,却很难求得k,这就是经典的离散对数问题,ECC算法正是利用该特点进行加密,点Q为公钥,大数k为私钥,点P为基点,和RSA最大的实际区别,主要是密钥长度。

如何计算kG:

相关公式如下:有限域GF(p)上的椭圆曲线y² = x³ + ax + b,若P(Xp, Yp), Q(Xq, Yq),且P≠-Q,则R(Xr,Yr) = P+Q 由如下规则确定:

Xr = (λ² – Xp – Xq) mod p  Yr = (λ(Xp – Xr) – Yp) mod p  其中λ = (Yq – Yp)/(Xq – Xp) mod p(若P≠Q), λ = (3Xp² + a)/2Yp mod p(若P=Q)

因此,有限域GF(23)上的椭圆曲线y² ≡ x³ + x + 1 (mod 23),假设以(0,1)为G点,计算2G、3G、4G…kG等等

 

椭圆曲线加解密步骤:

设私钥、公钥分别为k、K,即K = kG,其中G为G点。

公钥加密:  选择随机数r,将消息M生成密文C,该密文是一个点对,即:  C = {rG, M+rK},其中K为公钥

私钥解密:  M + rK – k(rG) = M + r(kG) – k(rG) = M  其中k、K分别为私钥、公钥。

椭圆曲线上点的阶:

如果椭圆曲线上一点P,存在最小的正整数n使得数乘nP=O∞,则称n为P的阶,若n不存在,则P为无限阶。

在有限域上定义的椭圆曲线,所有点的阶n都是存在的

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注