没有合适的资源?快使用搜索试试~ 我知道了~
首页椭圆曲线数字签名算法(ECDSA)中文版
椭圆曲线数字签名算法(ECDSA)中文版
5星 · 超过95%的资源 需积分: 28 100 下载量 108 浏览量
更新于2023-03-03
评论 5
收藏 199KB DOC 举报
椭圆曲线数字签名算法(ECDSA)是使用椭圆曲线对数字签名算法(DSA)的模拟,与普通的离散对数问题(discrete logarithm problem DLP)和大数分解问题(integer factorization problem IFP)不同,椭圆曲线离散对数问题(elliptic curve discrete logarithm problem ECDLP)没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。本文将详细论述ANSI X9.62标准及其协议和实现方面的问题。
资源详情
资源评论
资源推荐
椭圆曲线数字签名算法(ECDSA)
原文 The Elliptic Curve Digital Signature
Algorithm (ECDSA)
公司
(翻译部分内容有删节)
摘要
椭圆曲线数字签名算法( )是使用椭圆曲线对数字签名算法( )的模拟。
于 年成为 标准,并于 年成为 和 标准。它在 年
既已为 所接受,并且包含它的其他一些标准亦在 的考虑之中。与普通的离散对数
问题( !"#)和大数分解问题($%&$
!'#)不同, 椭圆 曲线离 散对数 问题 ( ()
!"#)没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高
于其他公钥体制。本文将详细论述 *+, 标准及其协议和实现方面的问题。
1、介绍
数字签名算法()在联邦信息处理标准 '# 中有详细论述。它的安全性基于素域上
的离散对数问题。
椭圆曲线密码()由 -!& 和 . 于 / 年发明。它可以看作是
椭圆曲线对先前基于离散对数问题("#)的密码系统的模拟,只是群元素由素域中的数
换为有限域上的椭圆曲线上的点。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题
("#)的难解性。
椭圆曲线离散对数问题远难于离散对数问题,椭圆曲线密码系统的单位比特强度要远高于
传统的离散对数系统。因此在使用较短的密钥的情况下, 可以达到于 " 系统相同的
安全性。这带来的好处就是计算参数更小,密钥更短,运算速度更快,签名也更加短小。
因此椭圆曲线密码尤其适用于处理器速度、带宽及功耗受限的场合。
是椭圆曲线对 的模拟。 首先由 .$$ 在 年为了响
应 对数字签名标准()的要求而提出。 于 年作为 标准被采纳,
在 年作为 标准被采纳,并于 年成为 和 '# 标准。包含它的其他
一些标准亦在 的考虑之中。本文中我们将介绍 *+, 标准。也将介绍一些签名
的基础知识以及协议及实现方面的问题。
本文其他部分的安排如下:第二节中我们将回顾数字签名方案和 。第三节和第四节将
分别介绍有限域和椭圆曲线。第五节将讲述域参数的产生,第六节将讲述密钥对的产生。
第七节的内容是 的签名和验证过程。第八章论证 的安全性。第九节和第
十节讲述的是 协议和实现方面的问题。
2、数字签名方案
2.1 背景知识
数字签名的目的是提供一个手写签名的数字化副本。签名是一个依赖于签名者私钥和一段
消息的比特串。签名必须是可验证的,即如果对签名的真实性存在疑问,必须由一个中立
的第三方作出公正的裁决,并且无需知道签名者的私钥。对签名的抵赖以及伪造签名应该
能被发现。
本文论述的是非对称摘要数字签名。“非对称”即用户的密钥对各不相同。用户的私钥用于
签名,其他用户用他的公钥来检验签名的真实性。摘要是指对一段消息先用哈希函数进行
摘要计算,尔后再对消息摘要进行签名。
安全性。从理论上讲,在选择消息攻击下,数字签名应该是不可伪造的。这一概念由
01 和 ) 提出。更一般的讲就是攻击者获得用户 的摘要和签名,
但他无法用其他的摘要来伪造这样一个签名。
应用。数字签名方案用于以下一些用途:数据完整性(确保数据没有被未知或未授权的中
间人改变),数据源认证(确保数据的来源是可信的),不可否认性(确保用户不能对自
己的行为进行抵赖)。数字签名是密码学协议的基本组成部分,并且可以提供其他一些服
务 如 : 身 份 认 证 ( '#, , 2345 ) , 密 钥 传 递 前 的 认 证 (
*+,5,23345),经验证的密钥协商(23345)。
分类。数字签名方案可以根据所基于的数学难题进行分类:
1、基于大整数分解(')的方案,安全性基于大整数分解的难度。实例有 方案和
!$ 方案。
2、基于离散对数(")的方案,安全性基于有限域上普通的离散对数问题。实例包括
0,$, 和 6!4( 方案。
3、基于椭圆曲线()的方案,安全性基于椭圆曲线离散对数问题。
2.2 数字签名算法
于 年由 提出,并在 '#, 中得到确认。 可以看作是 0
签名方案的一个变形。其安全性建立在素域上的离散对数问题的困难性之上。
参数的产生。每个用户的安全参数产生如下:
1、选择 , 比特的素数 7 和 8 比特的素数 ,满足 79 4。
2、在有限域 : ;中寻找 7 阶循环子群的生成元 ,具体方法是在 : ;选取元素 计算
<= 4>27 ,当 ? 时即找到满足要求的 。
3、域参数就是 ,7 和 。
密钥对的产生。每个拥有域参数 ,7 和 进行如下操作:
1、选择伪随机数 @ 满足 A@A 4。
2、计算 6<@ 。
3、用户的私钥是 @,公钥是 6。
签名过程:
1、选择伪随机数 B 满足 ABA 4。
2、计算 *<B ,<*7,若 < 则返回第一步。
3、计算 B47。
4、计算 <C4=>。
5、计算 <B4=D@>7,若 < 则返回第一步。
6、对消息 的签名就是=E>。
签名的验证。为了验证=E>是对 的签名,需要使用签名者的域参数= E7E>和公钥
6 进行如下运算:
1、验证 , 在区间FE74G中。
2、计算 <C4=>。
3、计算 H<47。
4、计算 (<H7 和 (<H7
5、计算 *<(6( 及 )<*7。
6、如果 )< 则认可此签名。
安全性分析。由于 和 均小于 7,故 签名长度小于 5 比特。 的安全性依赖
于两个方面,它们都基于离散对数问题的难解性,一个是 : ;上的离散对数问题,目前已
有数域筛算法去加以解决,这是一种亚指数级的算法。其平均运算时间为:
=@ ==D=>>=$ >25=$$ >25>>
其中 约为 +5,若 是 8 比特的素数,则上式的计算量是无法接受的。因此目前
8 比特的 可以应付现有攻击。另一个是 7 阶子群上的离散对数问题,给定
,7, 和 6,6<@ ,要寻找 @,目前最好的算法是 #I 算法,大约要
做
7=J72>
步。若 7 是 , 比特的,则该算法在计算上不可行,因此 是很安全的。 的安全
性主要取决于 和 7 的尺寸。增加其中一个的尺寸而不增加另一个的尺寸对安全性的提高
并无益处。此外,对两种离散对数问题解决算法的提高都会削弱 。
安全参数的产生。 的早期版本受到了一些批评,因此 '#, 推出了一种新模式以
产生素数以及“可证明的随机性”。它可以防止用户故意构造一个利于破译的素数(例如可
以由 来产生域参数并发送给用户)。 '# 指定了两个模式,分别使用 C4 和
,产生伪随机私钥 @。'#, 指定使用这两种模式以及其他经过 '# 认可的安全
模式。
3、有限域
我们将简要介绍有限域的知识。更多详细内容请参看其他书籍。有限域由一个有限集合 '
和 ' 上的两个二元运算组成,这两个运算满足某种运算规则,分别称为加法和乘法。有限
域的阶即域中元素的个数。当仅当 7 是素数时存在一个 7 阶有限域,这个有限域是唯一的,
记作 '7。有很多方法可以描述 '7 的元素,有些描述方式可以使域上的软件及硬件运算更
加高效。若 7< ,其中 为素数, 为正整数,则 称为 '7 的特征, 称为 '7 的度。
至于椭圆曲线密码,一般基于素域或是多项式域。在 5+ 和 5+ 中我们将分别介绍这两种
有限域上的元素和运算以及多项式域的两种表示方法:多项式表示方法和正规基表示方法。
3.1 有限域 Fp
# 为素数,有限域 ' 称为素域,由整数集KEELLE 4M和其上的符合下列规则的运算组
成:
4加法:E!N ,D!<, 为 与 ! 的和模 所得的值。
4乘法:E!N ,;!<, 为 与 ! 的积模 所得的值。
4求逆运算: 是 ' 中的非零元素, 的逆是唯一的,记作 4,有 ;4<
例 1 .'5, 全部元 素 为 KEELLEM , 其 上三种 运 算: D<, ;<5,4
<5。
3.2 有限域 F2m
' 称之为特征为 的有限域,可以看做是 ' 上的 维向量空间。' 中存在 个不
同的元素 OEOLLEO4,任一个 ON' 均可写为以下形式:
O<PPDPODLLDP4O4PNKEM
集合KOEOLLEO4M称为 ' 在 ' 上的基。有这样一个基,域中所有元素就可以
用一个比特串=PEPELLP4>来表示。这样,加法就可以用向量的逐比特异或运算来
表示,乘法运算则依赖于基的选择。
基的选择方式是多种多样的。一些基可以使运算变得高效。*+, 给出了两种基,
分别是多项式基和正规基。
多项式基
%=@><@D%4@4DLL%@D%@D%(QNKEM)是 ' 上的 次本原多项式。
域元素。有限域 ' 由 ' 上的所有不多于 次的多项式组成。
'<K4@4DLLD@D9NKEMM
域元素 4@4DLLD@D 可以写为比特串
=4ELLE>
形式。
因此 ' 的元素可以写为长度为 的比特串。乘法单位元是=EELEE>,加法零元是
全零串=EELLE>。
域运算。
4 加 法 : <= 4ELLE> , !<=!4ELLE!E!> , D!<<=4E
LLEE>,<*!。
4 乘 法 : <= 4ELLE> , !<= !4ELLE!E!> , ;!<<=4E
LLEE>,多项式 4@4DLLD@D 由=4@4DLLD@D>;=!4
@4DLLD!@D!>模 %=@>而来。
4求逆运算: 是 ' 中的非零元素,4 满足 4;<
例 2.有限域 '8E模多项式为 %=@><@8D@D,有限域中 , 个元素分别为:
=>=>@=>
@D=>@=>@D=>
@D@=>@D@D=>@5=>
@5D=>@5D@=>@5D@D=>
@5D@=>@5D@D=>@5D@D@=>
@5D@D@D=>
'R8 上的运算举例:
4=>D=><=>
4=>;=><=> =@5D@D>;= @5D><@,D@/D@D
=@,D@/D@D>=@8D@D><@5D@D@D
4=>4<=>
@<=>是 '8 的生成元
@<=>@<=>@5<=>@8<=>
@/<=>@,<=>@3<=>@<=>
@<=>@<=>@<=>@<=>
@5<=>@8<=>@/<=>
模多项式的确定。*+, 的两条标准如下:
1.如果在 ' 上有 次三项本原多项式 @D@BD,则模多项式应在这些多项式中选取 B
最小的那个。
2.若不存在那样的多项式,则 %=@>应为 次 / 项本原多项式 @D@B5D@BD@BD。
这时有三条原则:=>B5 应尽量小。=>B5 确定时 B 应尽量小。=5>B5EB 确定时,B 应
尽量小。
正规基(略)
4、有限域上的椭圆曲线
本节我们将给出椭圆曲线的简要介绍,更详细的内容请参见其他书目。
4.1Fp 上的椭圆曲线
剩余26页未读,继续阅读
孤单旅行
- 粉丝: 20
- 资源: 7
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 2023年中国辣条食品行业创新及消费需求洞察报告.pptx
- 2023年半导体行业20强品牌.pptx
- 2023年全球电力行业评论.pptx
- 2023年全球网络安全现状-劳动力资源和网络运营的全球发展新态势.pptx
- 毕业设计-基于单片机的液体密度检测系统设计.doc
- 家用清扫机器人设计.doc
- 基于VB+数据库SQL的教师信息管理系统设计与实现 计算机专业设计范文模板参考资料.pdf
- 官塘驿林场林防火(资源监管)“空天地人”四位一体监测系统方案.doc
- 基于专利语义表征的技术预见方法及其应用.docx
- 浅谈电子商务的现状及发展趋势学习总结.doc
- 基于单片机的智能仓库温湿度控制系统 (2).pdf
- 基于SSM框架知识产权管理系统 (2).pdf
- 9年终工作总结新年计划PPT模板.pptx
- Hytera海能达CH04L01 说明书.pdf
- 数据中心运维操作标准及流程.pdf
- 报告模板 -成本分析与报告培训之三.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论5