ECC算法学习(一)算法公式

这篇具有很好参考价值的文章主要介绍了ECC算法学习(一)算法公式。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、ECC简介

ECC全称为“Ellipse Curve Ctyptography”,是一种基于椭圆曲线数学的公开密钥加密算法。与传统的基于大质数分解难题的加密算法不同,该加密方式基于 “离散对数” 这种数学难题。
椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。

优缺点

优点:
性能提升,同样的密钥长度,基于ECC加密要比基于RSA安全很多。而且计算量较小,处理速度更快,存储空间和传输带宽占用较少。

缺点:

  1. 曲线的选择很复杂。
    ECC是基于椭圆曲线的离散对数问题,这并不是一个很好理解的问题,这里的椭圆曲线实际上并不是一个真正意义的椭圆,它的运算和椭圆类似,实际上是一个随着参数变化而不断变化的曲线,不同参数的选取会出现不同的曲线,不同的曲线就会形成不用的ECC标准,不同标准的ECC产生的加解密效果也是千差万别的。

  2. 有可能这条复杂的曲线被人植入了后门,别人就可以通过这个后门轻松的破解。
    现行的一套很流行的ECC标准是由美国郭建安全局NAS发布的,这个标准就被很多人质疑是有被植入了后门的。

  3. 专利问题。
    关于ECC的使用,很多人申请了很多的专利,现在关于ECC使用的专利大多数都掌握在一家公司的手中,这家公司就是黑莓。所以,当你想要构建自己的一套ECC标准的时候,可能不知道哪里就触及了它们的专利,卷入专利之争。

运用

目前我国居民二代身份证正在使用 256 位的椭圆曲线密码,虚拟货币比特币也选择ECC作为加密算法。

二、算法理论基础

椭圆曲线算法可以看作是定义在特殊集合下数的运算,满足一定的规则。椭圆曲线因为用二元三次方程y^2= x^3+ ax + b来表示,类似椭圆周长计算方程而得名。

1. 椭圆曲线的加法

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

ecc,算法知识整理,算法,学习

2. 椭圆曲线的二倍运算

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

ecc,算法知识整理,算法,学习

3. 同余运算

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

a ≡ b ( m o d m ) a \equiv b(mod \quad m) ab(modm)

4. 有限域

椭圆曲线是连续的,并不适合用于加密;所以必须把椭圆曲线变成离散的点,要把椭圆曲线定义在有限域上。而椭圆曲线密码所使用的椭圆曲线是定义在有限域内,有限域最常见的例子是有限域GF§,指给定某质数p,由0,1,2…p-1共p个元素组成的整数集合中加法、二倍运算。例如GF(233)就是
y 2 = ( x 3 + 7 ) ( m o d 223 ) y^2 = (x^3 + 7)(mod \quad 223) y2=(x3+7)(mod223)

5. 乘法逆元

在模7乘法中:

  • 1的逆元为 1 ( 1 ∗ 1 ) 1(1*1)%7 = 1 1(11)
  • 2的逆元为 4 ( 2 ∗ 4 ) 4(2*4)%7 = 1 4(24)
  • 3的逆元为 5 ( 3 ∗ 5 ) 5(3*5)%7 = 1 5(35)
  • 4的逆元为 2 ( 4 ∗ 2 ) 2(4*2)%7 = 1 2(42)
  • 5的逆元为 3 ( 5 ∗ 3 ) 3(5*3)%7 = 1 3(53)
  • 6的逆元为 6 ( 6 ∗ 6 ) 6(6*6)%7 = 1 6(66)

三、算法公式

并不是所有的椭圆曲线都适合加密, y 2 = x 3 + a x + b y^2 = x^3 + ax + b y2=x3+ax+b 类可以用来加密的椭圆曲线,也是最为简单的一类。

针对曲线Ep(a,b)表示为 y 2 = x 3 + a x + b ( m o d p ) , x , y ∈ [ 0 , p ] , p 为质数 y^2 = x^3 + ax + b(mod \quad p), x,y \in [0,p], p为质数 y2=x3+ax+b(modp),x,y[0,p],p为质数

该曲线关于x轴对称。选择两个满足下列条件的小于p(p为素数)的非负整数a、b,要求满足以下条件
3 a 3 + 27 b 2 ≠ 0 3a^3 + 27b^2 \neq 0 3a3+27b2=0

1、有限域的负元

P ( x , y ) P(x,y) P(x,y) 的负元是 ( x , − y m o d p ) = ( x , p − y ) (x, -y \quad mod \quad p) = (x, p - y) (x,ymodp)=(x,py)

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

P ( x 1 , y 1 ) P(x_1, y_1) P(x1,y1) Q ( x 2 , y 2 ) Q(x_2, y_2) Q(x2,y2) R ( x 3 , y 3 ) R(x_3, y_3) R(x3,y3)三点(其中R是PQ直线与曲线的交点的关于x轴的对称点,即 R = P + Q R = P + Q R=P+Q)有如下关系:
x 3 ≡ k 2 − x 1 − x 2 ( m o d p ) x_3 \equiv k^2 - x_1 - x_2(mod \quad p) x3k2x1x2(modp)
x 3 ≡ k 2 − x 1 − x 2 ( m o d p ) x_3 \equiv k^2 - x_1 - x_2(mod \quad p) x3k2x1x2(modp)

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

P = Q P = Q P=Q,则 k = ( 2 x 2 + a ) / 2 y 1 k = (2x_2 + a)/2y_1 k=(2x2+a)/2y1
P ≠ Q P \neq Q P=Q,则 k = ( y 2 − y 1 ) / ( x 2 − x 1 ) k = (y_2 - y_1)/(x_2 - x_1) k=(y2y1)/(x2x1)

为了方便理解,可以套用以上公式,解决以下例题。

例:已知 E 23 ( 1 , 1 ) E_{23}(1,1) E23(1,1) 上两点 P ( 2 , 10 ) P(2,10) P(2,10), Q ( 9 , 7 ) Q(9,7) Q(9,7),求1) − P -P P, 2) P + Q P + Q P+Q, 3) 2 P 2P 2P

解:1) P ( 3 , 10 ) P(3,10) P(3,10)的负元是 ( 3 , − 10 m o d 23 ) = ( 3 , 23 − 10 ) = ( 3 , 13 ) (3, -10 \quad mod \quad 23) = (3, 23 - 10) = (3, 13) (3,10mod23)=(3,2310)=(3,13)
2) P ≠ Q , k = ( 7 − 10 ) / ( 9 − 3 ) = − 1 / 2 P \neq Q, k = (7 - 10)/(9 - 3) = -1/2 P=Q,k=(710)/(93)=1/2,因为 2 ∗ 12 ≡ 1 ( m o d 23 ) 2 ∗ 12 ≡ 1 (mod \quad 23) 2121(mod23)
所以2的乘法逆元为12,
k ≡ − 1 ∗ 2 − 1 ( m o d 23 ) ≡ − 1 ∗ 12 ( m o d 23 ) k \equiv -1 * 2^{-1}(mod \quad 23) \equiv -1 * 12(mod \quad 23) k121(mod23)112(mod23),故k=11.
x 3 ≡ k 2 − x 1 − x 2 ( m o d p ) ≡ 1 1 2 − 3 − 9 ( m o d 23 ) = 109 ( m o d 23 ) ≡ 17 x_3 \equiv k^2 - x_1 - x_2(mod \quad p) \equiv 11^2 -3 - 9(mod \quad 23) = 109(mod \quad 23) \equiv 17 x3k2x1x2(modp)11239(mod23)=109(mod23)17
y 3 ≡ k ( x 1. − x 3 ) − y 1 ( m o d p ) ≡ 11 [ 3 − ( − 6 ) ] − 10 ( m o d 23 ) = 89 ( m o d 23 ) ≡ 20 y_3 \equiv k(x1. - x3) - y_1(mod \quad p) \equiv 11[3-(-6)] - 10(mod \quad 23) = 89(mod \quad 23) \equiv 20 y3k(x1.x3)y1(modp)11[3(6)]10(mod23)=89(mod23)20,故 P + Q P + Q P+Q 的坐标为 ( 17 , 20 ) (17,20) (17,20)
3) P = Q P = Q P=Q
k ≡ [ 3 ∗ ( 3 2 ) + 1 ) ] / ( 2 + 10 ) ( m o d 23 ) = 7 + 5 − 1 ( m o d 23 ) k \equiv [3 * (3^2) + 1)] / (2 + 10)(mod \quad 23) = 7 + 5^{-1}(mod \quad 23) k[3(32)+1)]/(2+10)(mod23)=7+51(mod23)
因为 5 ∗ 14 ≡ 1 ( m o d 23 ) 5 * 14 \equiv 1(mod \quad 23) 5141(mod23),5的乘法逆元为14,
故k=6。
x 3 ≡ k 2 − x 1 − x 2 ( m o d p ) = 6 2 − 3 − 3 ( m o d 23 ) = 30 ( m o d 23 ) ≡ 7 x_3 \equiv k^2 - x_1 - x_2(mod \quad p) = 6^2 - 3 - 3(mod \quad 23) = 30(mod \quad 23) \equiv 7 x3k2x1x2(modp)=6233(mod23)=30(mod23)7
y 3 ≡ k ( x 1 − x 3 ) − y 1 ( m o d p ) = 6 ∗ ( 3 − 7 ) − 10 ( m o d 23 ) = − 34 ( m o d 23 ) ≡ 12 y^3 \equiv k(x_1 - x_3) - y_1(mod \quad p) = 6 * (3 - 7) - 10(mod \quad 23) = -34(mod \quad 23) \equiv 12 y3k(x1x3)y1(modp)=6(37)10(mod23)=34(mod23)12,故 x P xP xP 的坐标为 ( 7 , 12 ) (7,12) (7,12)

4. 椭圆曲线加解密算法原理

设私钥、公钥分别为d、Q,即 Q = d G Q = dG Q=dG,其中G为基点,椭圆曲线上的已知G和dG,求d是非常困难的,也就是说已知公钥和基点,想要算出私钥是非常困难的。
公钥加密:选择随机数r,将消息M生成密文C,该密文是一个点对, C = r G , M + r Q C = {rG, M+rQ} C=rG,M+rQ,其中Q为公钥。
私钥解密 M + r Q − d ( r G ) = M + r ( d G ) − d ( r G ) = M M + rQ - d(rG) = M + r(dG) - d(rG) = M M+rQd(rG)=M+r(dG)d(rG)=M,其中d、Q分别为私钥、公钥。

5. 椭圆曲线签名算法原理

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

私钥签名:

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

公钥验证签名:

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

6. 签名过程

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

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

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

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

7. 验证过程

关于验证过程,这里不讨论它的算法细节。从宏观上看,消息的接收方从签名中分离出r和s,然后利用公开的密钥信息和s计算出r。如果计算出的r和接收到的r值相同,则表示验证成功,否则,表示验证失败。文章来源地址https://www.toymoban.com/news/detail-855470.html

到了这里,关于ECC算法学习(一)算法公式的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【opencv】示例-image_alignment.cpp 利用ECC 算法进行图像对齐

    affine homography 这段代码是一个 利用ECC (Enhanced Correlation Coefficient) 算法进行图像对齐的示例 。代码首先包含了OpenCV库的头文件,并且使用了OpenCV和标准库的命名空间。然后定义了几个函数和宏进行图像变换矩阵的操作,定义了一些用于解析命令行参数的。 main 函数中,

    2024年04月13日
    浏览(44)
  • 【密码算法 之十四】非对称算法,ECC椭圆曲线算法 之 ECDSA、ECDH、SM2、SM9等

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

    2024年02月13日
    浏览(35)
  • ECC椭圆曲线入门

    https://web3study.club/ ECC(Ellipse Curve Cryptography)又称椭圆曲线密码体制、椭圆曲线加密算法等。 椭圆曲线加密算法在比特币、区块链上有着广泛的应用。 公式: y^2 = x^3 + ax + b 这里使用简单易懂的方式对大家介绍这部分内容,让大家有个简单的理解 公私钥加密内容​ 公钥未公开部

    2023年04月09日
    浏览(41)
  • ECC功能简述及其原理

    1、NOR的特点是芯片内执行(XIP,eXecute In Place),这样应用程序可以直接在flash闪存内运行,不必再把代码读到系统RAM中。优点是可以直接从FLASH中运行程序,但是工艺复杂,价格比较贵,NOR的传输效率很高,在1~4MB的小容量时具有很高的成本效益,但是很低的写入和擦除速度大大影响了它

    2024年02月05日
    浏览(54)
  • DDR5 内存ECC

    针对DDR5,已经写了很多文章来分析,但最近工作中碰到一个问题, 同一个channel里的CB是不是可以任意互换?  让我对DDR5的ECC功能有一些疑问,查了下资料发现这里面水挺深,ECC居然还有好几种? DDR作为目前主板上带宽最高的设备和协议,误码率当然是其中最重要的参数之一

    2024年02月15日
    浏览(35)
  • ECC加密——C++/OPENssl实现

    一、介绍: 因为最近设计一些密钥交换相关的协议,做了很多调研,和学习。本来想直接使用ECC完成密钥交换协议,但是现存的很多代码都是基于ECDH的,这完全不是基于ECC加密的。尝试了很久之后终于自己手写了一份加密方案出来,为了方便更好的加解密,我封装成数组进

    2024年02月13日
    浏览(38)
  • 服务器之 ECC 内存的工作原理

    大家好,我是飞哥! 在开始今天的分享之前,我先给大家看两个 1R * 8 的内存条。 现在的 CPU 都是 64 位的,每次和内存通信都要传输 64 比特的数据。1R * 8 类型的内存中的 1R 指的是该内存条只有一个 rank,8 指的是在每一次 64 比特的内存 IO 过程中,每个内存颗粒分别提供 8

    2024年03月13日
    浏览(34)
  • [密码学][ecc]secp256k1

    secp256k1 is the elliptic curve used in Bitcoin’s public key cryptography. It is defined by the equation y^2 = x^3 + 7 and is based on the finite field mathematics. The “secp” in secp256k1 stands for “Standards for Efficient Cryptography” and “256” refers to the curve’s bit length. The “k1” indicates that it is the first elliptic curve pr

    2024年02月03日
    浏览(44)
  • ECC校验原理以及在Nand Flash中的应用

    ECC,全称为Error Correcting Code,错误纠正码,这是一种编码方式,用于在于可以在一定程度上自行发现和纠正传输过程中发生的错误。 纠错码能够检错或者纠错,主要靠码字之间的差别。这可以用汉明距离d(x,y)来衡量。一种纠错码的最小距离d定义为该种码中任意两个码字

    2024年02月02日
    浏览(48)
  • openssl SM2(ECC)自签服务端和客户端证书

    参考文章:https://www.golinuxcloud.com/openssl-generate-ecc-certificate/#5_Create_CA_certificate_with_ECC_Key (228条消息) openssl 制作SM2多级证书链_酷ying的博客-CSDN博客_openssl sm2 sm3 csr 1、在当前目录创建存储证书文件夹,配置openssl.cnf所需要的文件,将openssl.cnf文件放到当前目录(编译openssl源码包会

    2024年02月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包