(十一)椭圆曲线密码(ECC)

news/2024/4/19 19:51:57/

椭圆曲线密码(ECC)

ECC比RSA和经典的Diffie-Hellman等更强大、更高效——含256比特密钥的ECC比含4096比特密钥的RSA提供的安全性更强,但同时ECC也更复杂。
ECC会对大数进行乘法运算,ECC做大数乘法是为了将所有元素看作点,并将它们组合在一起,构成一条数学曲线,这条曲线被称为椭圆曲线(其实与椭圆无关)。椭圆曲线有许多不同的类型——简单的和复杂的、高效的和低效的、安全的和不安全的。
椭圆曲线可以实现经典公钥密码系统的所有功能,包括加密、签名和密钥协商等,并且它的执行速度比经典公钥密码系统更快。

椭圆曲线

椭圆曲线是平面上的曲线,曲线方程定义了所有属于曲线的点。无论曲线是什么,曲线上的点都满足曲线方程的(x,y)对。
椭圆曲线定义了这样一条曲线,这条曲线对应的方程为(Weierstrass型),其中常数a和b决定了曲线的形状。

在密码学中使用椭圆曲线时,需要使用曲线上的点来完成加密等功能,若误用了不在曲线上的点通常会带来安全风险。

整数的椭圆曲线

在密码学中使用的曲线上的点都是整数。现在假设有一条曲线,方程为 。方程的解是模某个数n之后的计算结果(即y∈[0,n))。
现在假设n=191,当x=3时,得,此时相当于,得到y=46或145,这些解得到的集合称为
下图为在实数域内(上)的图形和整数域内(下)的图形。
当x=3时,解得点(3,46),(3,145)在曲线上。

域和有限域

对于某个数n,按照模n定义加法和乘法的数的集合,每个元素x分别有一个关于加法的逆元(记作-x)和一个关于乘法的逆元(记作1/x),并且包含包含恒等元素0,这样的集合称为域。
例如在中,有x+0=x,x+(-x)=0,则(100+91) mod 191=0,所以100的加法逆元是91。
有x*1=x,,则,所以48的乘法逆元是4。

有限域也叫伽罗瓦域(GF),当域含有有限数量的元素时,就称该域为有限域。

加法定律

现在再来考虑,现在选取椭圆曲线上的两点P和Q,对两个点做加法,得到一个新的点R。
方法:作连接点P和点Q的直线,该直线与曲线相交于第三点,这一点关于x轴的反射点R即为P+Q。
下面计算R的坐标。
设P点坐标,Q点坐标 。R点坐标,则



有两种特殊情况:
1.当Q=-P时,如下图所示,两个点与曲线不会交于第三点。此时两点互为逆元。
P+(-P)=O,其中,O被称为无穷远点,意思为连接P和–P之间的直线一直延伸到无穷远,不会与曲线相交。
2.当Q=P时,P、Q重合,P+Q=P+P=2P,此时不能用上面的公式算出R的坐标,需要在点P处画一条曲线的切线,其中P是切点,这条切线会与曲线相交于另一点,这一交点记为R,如下图
计算公式为:
,其中a是曲线方程的参数a,对于来说a=-4

乘法定律

乘法是将曲线上的点P乘以某个数k,相当于k个P相加,即

所以乘法就是按照上面的加法定律操作k-1遍。但是如果k过大,这种方法会非常慢,所以还有一种简便的方法:



......

这里即为n*P。

椭圆曲线群

椭圆曲线上的点的集合构成了群。根据群的定义,如果点P和点Q都在一个给定的曲线上,那么P+Q也在该曲线上。对于曲线上的任何三个点P、Q和R,都有(P+Q)+R=P+(Q+R)。在椭圆曲线的所有点组成的群中,无穷远点就是单位元,并被表示为O,也即对曲线上任意的点P,P+O=P始终成立。此外,点P=还有唯一的逆元–P=,这时就有P+(–P)=O。

曲线上的点的数量,这也被称为椭圆曲线的基数、群的阶,简称为阶。

ECDLP问题

称为椭圆曲线离散对数问题:给定一个基本点P和它的某个倍数Q=kP,求解k。
所有的椭圆曲线密码系统都建立在ECDLP问题之上。

求解k的一种方法是寻找两个输出之间的碰撞。这些方程中的点P和
点Q满足Q=kP,其中数k未知,c1、d1、c2和d2是为了寻找k所需的数。
当两个不同的输入产生相同的输出时,就会发生碰撞。需要先找到满足下列方程的两个点:

将Q=kP代入,得
,合并系数得
,这说明 = ,则
=>,得

椭圆曲线的Diffie–Hellman密钥协商(ECDH)

DH:
给定一个固定的数字g,小明选择一个秘密的随机数a,并计算,将A发送给小王;小王选择一个秘密的随机数b并将发送给小明。然后小明和小王将自己的私钥与对方的公钥结合起来,就可以生成相同的
ECDH:
在ECC中,对于某个不动点G,小明取一个秘密的随机数,计算,并将发送给小王。小王选择一个秘密的随机数,计算出点,并将其发送给小明。然后双方据此计算相同的共享密钥

椭圆曲线的签名(ECDSA)

使用ECC进行签名的标准算法是ECDSA,由签名生成算法验证算法组成,签名生成算法使用签名者的私钥创建签名,验证算法可以根据签名者的公钥来检查签名的正确性。签名者持有数字d作为私钥,验证者持有公钥P=dG。双方事先都知道的内容有:使用的椭圆曲线方程,椭圆曲线的阶(曲线中的点数n),以及一个基点的坐标G。

对消息M签名的步骤:
1.先使用hash函数(如SHA-256)对消息M生成一个hash值h(h∈[0,n)),在[0,n)之间选一个随机数k并计算kG的坐标(x,y)。
2.令r=x mod n,计算s=(h+rd)/k mod n生成签名(r,s)。签名的长度取决于椭圆曲线中使用的坐标的长度。

已知签名(r,s)和hash值h,对消息M验签的步骤:
1.计算w=1/s(s的乘法逆元),由s=(h+rd)/k 得 w=k/(h+rd) mod n。
2.计算u=wh=hk/(h+rd),v=wr=rk/(h+rd)
3.计算点Q=uG+vP,P是签名者的公钥,P=dG,只有在Q的x坐标等于签名中的r值时才接受签名。
4.Q=uG+vdG=(u+vd)G,而u+vd=hk/(h+rd)+drk/(h+rd)=(hk+drk)/(h+rd)=k,则Q=kG,说明计算出的点与生成签名时计算的点相同。
一旦验证者确认点kG的x坐标等于接收到的r,验证就完成了;否则,签名将被视为无效而被拒绝。

椭圆曲线的加密(ECIES)

一种简单方法是使用集成加密方案(Integrated Encryption Scheme,IES)。这是一种基于Diffie-Hellman密钥交换的混合非对称-对称密钥的加密算法。本质上,IES通过生成一个Diffie-Hellman密钥对来加密消息,将私钥与接收方自己的公钥组合在一起,从获得的共享密码中派生出对称密钥,然后使用经过身份验证的密码来加密消息。这种加密称为ECIES。

给定接收方的公钥P,ECIES对消息M进行加密的步骤如下:
1.选择一个随机数d,计算点Q=dG,其中基点G是一个固定参数。这里,(d,Q)充当会话密钥对,仅用于加密M。
2.通过计算S=dP得到一个ECDH共享密钥。
3.使用密钥派生方案(KDF)从S中派生出对称密钥K。
4.使用对称密钥K和对称身份验证密码加密消息M,获得密文C和身份验证标签T。
这样,ECIES的密文由会话公钥Q加上C和T组成。解密很简单:接收方通过将R与其私有指数相乘来计算S,然后生成密钥K,利用K解密C并验证T。

曲线的选择

基于椭圆曲线的密码系统的安全性取决于它所使用的群的阶(即曲线的点数)、它的加法公式和它的参数的选取原因。
必须仔细选择曲线方程中的系数a和b,群的阶不能等于一些小数的乘积。
一般在使用时可以选择已经被大量实例证实为安全的曲线。

目前常用的是NIST曲线中的素数曲线和Curve25519。

NIST曲线

NIST曲线名称

在其他标准中的名字

P-192

ansix9p192r1、prime192v1、secp192r1

P-256

ansix9p256r1、prime256v1、secp256r1

P-384

secp384r1

P-512

secp512r1

Curve25519

Daniel J.Bernstein在2006年将Curve25519(数字分段读为25-5-19)推出。
Curve25519的方程形式为
Curve25519适用于模素数的数,是一个256比特的素数,而且尽可能接近。b的系数486662是满足Bernstein设定的安全准则的最小整数。


http://www.ppmy.cn/news/23264.html

相关文章

java顺序存储二叉树应用实例

八大排序算法中的堆排序,就会使用到顺序存储二叉树。 1.线索化二叉树 1.1先看一个问题 将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n17 问题分析: 当我们对上面的二叉树进行中序遍历时,数列为 {8, 3, 10, 1, 6, 14 } 但是 6, 8, 10, 14 这几个…

基于STM32设计的音乐播放器

一、项目背景与设计思路 1.1 项目背景 时代进步,科学技术的不断创新,促进电子产品的不断更迭换代,各种新功能和新技术的电子产品牵引着消费者的眼球。人们生活水平的逐渐提高,对娱乐消费市场需求日益扩大,而其消费电子产品在市场中的占有份额越来越举足轻重。目前消费电…

C语言-程序环境和预处理(14.1)

目录 1. 程序的翻译环境和执行环境 2. 详解编译链接 2.1 翻译环境 2.2 编译本身也分为几个阶段 2.2.1 预编译(预处理) 2.2.2 编译 2.2.3 汇编 2.2.4 链接 2.3 运行环境 写在最后: 1. 程序的翻译环境和执行环境 翻译环境&#xff1…

程序逻辑控制

文章目录 顺序结构分支结构循环结构输入输出猜数字一、顺序结构 所谓顺序结构就是程序一步一步的往下执行。 public class 顺序结构 {public static void main(String[] args) {System.out.println("Hello");System.out.println("World");System.out.pri…

【深度学习】Stable Diffusion AI 绘画项目搭建详解,并运行案例

文章目录前言1.安装环境1.1 基础环境1.2 权重文件2.牛刀小试2.1 用法在这里3.封装api总结前言 先把人家的git放过来:https://github.com/CompVis/stable-diffusion 40.7k 的stars, flask 和 django 两个web框架也不过如此数量级吧。 就是给一段文字&…

FMC DA子卡设计方案原理图:FMCJ465-2路 16bit 12.6GSPS FMC DA子卡

FMCJ465-2路 16bit 12.6GSPS FMC DA子卡 一、板卡概述: FMCJ465是一款转换速率最高为12.6GSPS 的 DAC 回放板,DAC位数16bit; 板卡基于ADI的AD9172系列DAC设计;板卡支持2路可配置的触发输出/触发输入;DAC的时钟支持内部参考时钟、外部参考时钟、外部…

(考研湖科大教书匠计算机网络)第三章数据链路层-第九节:以太网交换机自学习和转发帧的流程

获取pdf:密码7281专栏目录首页:【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一:自学习算法流程演示(1)情况1(2)情况2(3)情况3(4)情况…

Vue2学习笔记

Vue2笔记 Vue 在组件实例上暴露的内置 API 使用 $ 作为前缀。它同时也为内部属性保留 _ 前缀。因此,你应该避免在顶层 data 上使用任何以这些字符作前缀的属性。 Vue 自动为 methods 中的方法绑定了永远指向组件实例的 this。这确保了方法在作为事件监听器或回调函…

计算机网络-网络层

文章目录前言概述IP地址划分分类IP地址IP 地址与硬件地址划分子网和构造超网总结前言 本博客仅做学习笔记,如有侵权,联系后即刻更改 科普: 参考网址 概述 因特网设计理念 网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服…

向量的点积与叉积

1. 向量的点积 点积是指两个维度相同的向量相乘,结果是对应坐标配对的乘积之和: eg: [12]∙[12]11237\left[\begin{array}{l} 1 \\ 2 \end{array}\right] \bullet\left[\begin{array}{l} 1 \\ 2 \end{array}\right]1 \times 12 \times 37[12​]∙[12​]11237 留意…

跨域小样本系列1:简介篇

来源:投稿 作者:橡皮 编辑:学姐 跨域小样本系列1:简介√ 跨域小样本系列2:常用数据集与任务设定详解 跨域小样本系列3:元学习方法解决CDFSL以及两篇SOTA论文讲解 跨域小样本系列4:finetune方…

【C++: list的模拟实现】

目录 1 list的简单回顾 2 类中成员变量的声明 3 __list_iterator 中运算符重载 4 list中的迭代器 5 list中增删查改以及clear 6 const迭代器 6.1 __list_iterator的重新实现 6.2 list类的巧妙修改 7 构造函数&&拷贝构造&&赋值运算符重载 8 反向迭代器…

类和对象(中)万字详解

文章目录类的默认成员函数1. 构造函数1. 概念2. 无参时主函数中的写法3. 特性特性1-3特性 4特性 5内置类型(int char double)自定义类型特性 62. 析构函数1. 概念2. 特性3.先构造后析构4. 对于成员变量3. 拷贝构造函数1.值传递2. 引用传递3.内置类型(int char double)4. 浅拷贝…

基础知识:浅谈java多线程

多线程的描述 随着工业的进步,现在的笔记本、台式机乃至商用的应用服务器至少也都是4 核、8 核甚至 16 核的也都不少见。而在实际的系统运行的过程中,如何能够尽可能地利用我们的服务器CPU呢?越来越多的程序在执行任务的时候开始使用多线程&…

MySQL关键字执行顺序

一、 关键字书写顺序 select distinct from join on where group by having union (all) order by limit二、 关键字实际执行顺序 from on join where group by having select distinct union (all) order by limit三、 解读 执…

【Python】自动解析markdown中的图片并保存

python自动化下载/上传md中图片实在是太方便了 1.起因 为什么需要python来下载md里面的图片?原因很简单,那就是需要把图片保存下来,上传到第二个图床(迁移) 对于阿里云OSS来说,有两种迁移办法 使用官方的…

((蓝桥杯 刷题全集)【备战(蓝桥杯)算法竞赛-第4天(搜索与图论-下 专题)】( 从头开始重新做题,记录备战竞赛路上的每一道题 )距离蓝桥杯还有63天

🏆🏆🏆🏆🏆🏆🏆 欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录&a…

【微信小程序】在WXML文件中显示JS文件中全局变量的方法

前言我们知道在wxml中可以通过数据绑定的方法来获取到js文件中data里面的数据,并且显示到wxml界面,那么我们该如何在wxml中显示js文件里面的全局变量呢?显示data里面数据的方法在wxml种我们可以显示js代码中data代码段中的变量。具体的操作是…

Jenkins部署及持续集成——傻瓜式教程

文章目录jenkins安装jenkins启动jenkins登录jenkins插件Jenkin创建一个项目通过Git进行构建构建策略jenkins安装 jenkins官网 https://www.jenkins.io/ 支持Docker pull下载安装 我用的windows,这里下载war包,这个位置下载的是最新的,需要java11或者更…

C++类和对象:面向对象编程的核心。| 面向对象还编什么程啊,活该你是单身狗。

👑专栏内容:C学习笔记⛪个人主页:子夜的星的主页💕座右铭:日拱一卒,功不唐捐 文章目录一、前言二、面向对象编程三、类和对象1、类的引入2、类的定义Ⅰ、声明和定义在一起Ⅱ、声明和定义分开Ⅲ、成员变量命…