ECC算法学不学?

本文涉及的产品
密钥管理服务KMS,1000个密钥,100个凭据,1个月
简介: ECC算法学不学?

Perface

椭圆曲线加密算法,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全,RSA加密算法也是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用。

据研究,160位ECC加密安全性相当于1024位RSA加密,210位ECC加密安全性相当于2048位RSA加密(有待考证)。

比特币Bitcoin使用了 secp256k1这条特殊的椭圆曲线:


流程

椭圆加密算法(Elliptic curve cryptography,简称Ecc)是一种公钥加密体系,算法的基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。以下是Ecc算法的基本流程:

  • 随机生成一个整数r,该整数在1到n-1之间,n是一个素数。
  • 计算椭圆曲线点C1 = [r]G,其中G是基点,得到(x1,y1)。
  • 计算椭圆曲线点C2 = [r],得到(x2,y2)。
  • 将C1和C2的数据类型转换为比特串。
  • 计算 C3 = M*x2(mod p),其中M是要加密的明文信息。
  • 输出密文C = (x1,y1,C3)。
  • 在解密过程中,从密文C中取出C1(x1,y1),使用私钥k计算点C4(x2,y2)=kC1=k(x1,y1),然后计算明文P = C3,解密完成。

以上是Ecc算法的基本流程,具体实现过程可能会因应用场景的不同而有所差异。

一、阿贝尔群

椭圆曲线也可以有运算,像实数的加减乘除一样,这就需要使用到加群。19世纪挪威的尼尔斯·阿贝尔抽象出了加群(又叫阿贝尔群或交换群)。数学中的群是一个集合,我们为它定义了一个“加法”,并用符号+表示,加法必须遵循以下四个特性:

  • 封闭性:如果a和b都是 的成员,那么a+b也是 的成员;
  • 结合律:(a + b) + c = a + (b + c);
  • 单位元:a+0=0+a=a,0就是单位元;
  • 逆元:对于任意值a必定存在b,使得a+b=0。

如果再增加一个条件,交换律:a + b = b + a,则称这个群为阿贝尔群,根据这个定义整数集是个阿贝尔群。

二、椭圆曲线的加法

过曲线上的两点A、B画一条直线,找到直线与椭圆曲线的交点,交点关于x轴对称位置的点,定义为A+B,即为加法。如下图所示:A + B = C

image.png

三、椭圆曲线的二倍运算

上述方法无法解释A + A,即两点重合的情况,因此在这种情况下,将椭圆曲线在A点的切线,与椭圆曲线的交点,交点关于x轴对称位置的点,定义为A + A,即2A,即为二倍运算。

image.png

四、同余运算

同余就是有相同的余数,两个整数 a、 b,若它们除以正整数 m所得的余数相等,则称 a, b对于模m同余。

五、有限域

椭圆曲线是连续的,并不适合用于加密所以必须把椭圆曲线变成离散的点,要把椭圆曲线定义在有限域上

而椭圆曲线密码所使用的椭圆曲线是定义在有限域内,有限域最常见的例子是有限域GF§,指给定某质数p,由0,1,2…p-1共p个元素组成的整数集合中加法、二倍运算。例如GF(233)就是

六、乘法逆元

在模7乘法中:

  • 1的逆元为1 (1*1)%7=1
  • 2的逆元为4 (2*4)%7=1
  • 3的逆元为5 (3*5)%7=1
  • 4的逆元为2 (4*2)%7=1
  • 5的逆元为3 (5*3)%7=1
  • 6的逆元为6 (6*6)%7=1

七、数学解释

并不是所有的椭圆曲线都适合加密

y^2 = x^3 + ax + b

这个类可以用来加密的椭圆曲线,也是最为简单的一类。

针对曲线Ep(a,b)表示为

P为质数,该曲线关于x轴对称。选择两个满足下列条件的小于p(p为素数)的非负整数a、b,要求满足以下条件

  • 1、有限域的负元

  • 2、有限域的加法P+Q

  • 3、斜率计算(P=Q即要计算P点切线,需要求导)

八、椭圆曲线加解密算法原理

设私钥、公钥分别为d、Q,即Q = dG,其中G为基点,椭圆曲线上的已知G和dG,求d是非常困难的,也就是说已知公钥和基点,想要算出私钥是非常困难的。

  • 公钥加密:选择随机数r,将消息M生成密文C,该密文是一个点对,C = {rG, M+rQ},其中Q为公钥。
  • 私钥解密:M + rQ - d(rG) = M + r(dG) - d(rG) = M,其中d、Q分别为私钥、公钥。

九、椭圆曲线签名算法原理

椭圆曲线签名算法(ECDSA)。设私钥、公钥分别为d、Q,即Q = dG,其中G为基点。

私钥签名:

  • 选择随机数r,计算点rG(x, y)。
  • 根据随机数r、消息M的哈希h、私钥d,计算s = (h + dx)/r。
  • 将消息M、和签名{rG, s}发给接收方。

公钥验证签名:

  • 接收方收到消息M、以及签名{rG=(x,y), s}。
  • 根据消息求哈希h。
  • 使用发送方公钥Q计算:hG/s + xQ/s,并与rG比较,如相等即验签成功。

原理:hG/s + xQ/s = hG/s + x(dG)/s = (h+xd)G/s = r(h+xd)G / (h+dx) = rG

10、签名过程

假设要签名的消息是一个字符串:“Hello World!”。DSA签名的第一个步骤是对待签名的消息生成一个消息摘要,不同的签名算法使用不同的消息摘要算法,而ECDSA256使用SHA256生成256比特的摘要。

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

  • 产生一个随机数k
  • 利用随机数k,计算出两个大数r和s。将r和s拼在一起就构成了对消息摘要的签名。
    这里需要注意的是,因为随机数k的存在,对于同一条消息,使用同一个算法,产生的签名是不一样的。从函数的角度来理解,签名函数对同样的输入会产生不同的输出。因为函数内部会将随机值混入签名的过程。

11、验证过程

关于验证过程,这里不讨论它的算法细节。从宏观上看,消息的接收方从签名中分离出r和s,然后利用公开的密钥信息和s计算出r。如果计算出的r和接收到的r值相同,则表示验证成功,否则,表示验证失败。


目录
相关文章
|
6月前
|
算法 安全 数据安全/隐私保护
DSA与RSA的区别、ECC(椭圆曲线数字签名算法(ECDSA))
DSA与RSA的区别、ECC(椭圆曲线数字签名算法(ECDSA))
603 0
|
14天前
|
存储 安全 算法
AES算法
【10月更文挑战第30天】AES算法
32 2
|
6月前
|
算法
初步理解ECC
初步理解ECC
|
3月前
|
算法 安全 JavaScript
安全哈希算法:SHA算法
安全哈希算法:SHA算法
53 1
安全哈希算法:SHA算法
|
5月前
|
算法 安全 Java
深入解析ECC(椭圆曲线密码学)加解密算法
深入解析ECC(椭圆曲线密码学)加解密算法
深入解析ECC(椭圆曲线密码学)加解密算法
|
6月前
|
算法 安全 物联网
非对称加密算法ECC
**ECC**,椭圆曲线密码学,是基于椭圆曲线数学的非对称加密技术,以其短密钥、高效安全著称。适用于移动设备、物联网、签名验证及金融交易,保障数据安全和完整性。其安全性依赖于椭圆曲线上的离散对数难题。ECC是资源受限环境的理想选择,提供强大加密的同时减少计算需求。
214 2
|
6月前
|
算法 安全 物联网
什么是ECC?ECC 和 RSA 之间有何区别?
什么是ECC?ECC 和 RSA 之间有何区别?
1085 1
|
算法 安全 物联网
ECC算法详解+python实现
在了解了RSA算法的基础上,我们再学习ECC算法。
520 1
ECC算法详解+python实现
|
NoSQL 数据安全/隐私保护
AES 加密算法小结
AES 加密算法小结
164 0
|
机器学习/深度学习 算法 Python
RSA 加密算法主要公式
RSA 加密算法主要公式
160 0