信息安全技术论文报告.docx

信息安全技术论文报告.docx

《信息安全技术论文报告.docx》由会员分享，可在线阅读，更多相关《信息安全技术论文报告.docx（11页珍藏版）》请在冰点文库上搜索。

信息安全技术论文报告

《信息安全技术》课程论文

实验名称：

ECDSA算法实现及其安全性分析

专业：

计算机科学与技术

班级：

2012级

（1）班

学号：

1220040622

姓名：

曾宪泽

2015年12月5日

ECDSA算法实现及其安全性分析

【摘要】：

阐述了ANSIX9.62椭圆曲线数字签名算法（ECDSA）基本原理；对其安全性进行了初步探讨；并根据该原理对ECDSA进行了程序实现；通过对该程序的运行分析与测试表明，该程序实现了ECDSA的基本功能，且具有系统参数小、处理速度快、密钥尺寸小等优点。

【关键词】：

椭圆曲线密码学；ECDSA；算法实现；安全性

中图分类号：

TP393.08文献标示码：

A

1、前言

椭圆曲线密码系统（ECC）于1985年由NealKoblitz和VictorMiller发明，可看作是传统离散对数（DL）密码系统的椭圆曲线对等表示。

传统系统中的Z*p子群被有限域上的椭圆曲线点群所代替。

椭圆曲线密码系统安全性的数学基础是椭圆曲线离散对数问题（ECDLP）的计算复杂性。

由于ECDLP比DLP困难得多，椭圆曲线统中每个密钥位的强度在本质上要比传统的离散对数系统大得多。

因而除了具有相同等级的安全性外，ECC系统所用的参数比DL系统所用的参数少。

该系统的优点是参数少、速度快以及密钥和证书都较小。

这些优点在处理能力、存储空间、带宽和能源受限的环境中尤其重要。

本文阐述了ANSIX9.62ECDSA算法及其软件实现，并对其安全性进行了初步探讨。

2、椭圆曲线数字签名算法基本原理简介

2.1、数字签名方案

数字签名方案用于提供手写体签名（或其它签名）的数字副本。

数字签名是只有签名者才知道的一些秘密数字（签名者的私钥，该数字用来对消息内容进行签名）。

签名必须是可以验证的——如果出现诸如某个成员是否签署某个文档的争执，则没有偏见的第三方不需要访问签名者的私钥就能公正地解决该问题。

数字签名方案可用于提供如下基本密码学服务：

消息完整性（确保消息不被以非授权或未知方式改变），消息源可信（确保消息源和声明相同）以及抗抵赖性（确保成员不能否认先前的行为和委托）。

ANSIX9.62（ECDSA）表达为：

当运用适当的控制时，该标准的技术提供消息源、消息内容的完整性，消息初始可信性和抗抵赖性

2.1、有限域

有限域由在F上具有二元操作的F元素的有限集组成，二元操作指满足某一算法特性的加法和乘法。

有限域的阶是域中元素的数量。

当且仅当q为素数次方时存在q阶有限域。

如果q为素数次方，则本质上只有一个q阶有限域；这个域记为Fq。

有很多方法描述Fq

中的元素。

如果（q=pm），这里p为素数，m为正整数，则p称为Fq

的特征值，m称为Fq的扩展阶。

大部分标准指定将椭圆曲线密码学技术限定在奇素数阶（q=p）或2的幂（q=2m）之内。

p为一奇素数时，称为素数域的有限域Fq，由具有相应算法操作特性的整数集{0，1，2，…，p-1}组成。

有限域m2F称为特征双有限域和二元有限域，可以看作是由0和1组成的有限域F2上的m维向量空间。

也就是m2F中存在m个元素12m1,,,−αα⋅⋅⋅α，满足每个α∈m2F能用以下的形式唯一写出：

0011m1m1aaa−−α=α+α+⋅⋅⋅+α,这里ai∈{0,1}。

2.3、有限域上的椭圆曲线

在ECC中，我们关心的是某种特殊形式的椭圆曲线，即定义在有限域上的椭圆曲线。

2.3.1、Fp上的椭圆曲线

令p>3为素数，Fp上的椭圆曲线由形如公式

（1）的等式定义：

y2=x3+ax+b

（1）

这里a，b∈Fp，且4a3+27b20（modp）。

椭圆曲线的点集E（Fp）由所有满足等式

（1）的点（x，y），x∈Fp，y∈Fp组成，包括被称之为无穷点的特殊点Ο。

对于椭圆曲线上的两点相加给出椭圆曲线上第三点，有一条规则，称之为弦切律。

伴随这种加法操作，E（Fp）的点集形成了一个用Ο点作为标记的群。

正是这个群被用来构造椭圆曲线密码系统。

加法律最好用几何解释。

令P＝（x1，y1）且Q＝（x2，y2）是椭圆曲线E上两个截然不同的点，则P和Q的和，记为R＝（x3，y3），定义如下：

首先通过点P和Q作一条直线；这条直线与椭圆曲线交于第三点；则点R就是这个点关于x-轴的映像，如图1所示。

图中的椭圆曲线由两部分组成，象椭圆的图形和无穷曲线。

如果P＝（x1，y1），则P的加倍为R＝（x3，y3）定义如下：

首先做一条直线与椭圆曲线相切于点P；这条直线与椭圆曲线交于第二点；则点R就是这个点关于x-轴的映像，如图2所示。

图1两个不同的椭圆曲线点相加的几何描述（P+Q=R）

图2一个椭圆曲线点加倍的几何描述（P+P=R）

2.3.2、Fm2上的椭圆曲线

Fm2上椭圆曲线由形如公式

（2）的等式定义：

y2+xy=x3+ax2+b

（2）

这里a，b∈Fp，且b≠0，椭圆曲线的点集E（Fp）由所有满足等式

（2）的点（x，y），x∈Fp，y∈Fp组成，这些点包括被称之为无穷点的特殊点Ο。

3、椭圆曲线数字签名的生成和验证算法

3.1、输入ECDSA域参数

ECDSA的域参数由一条特征为p的有限域Fq上的椭圆曲线E和基点G∈E（Fq）组成：

a）域的大小q，这里q=p，为奇素数或q=2m；

b）用一个描述指针FR（域描述）描述Fq的元素；

c）位串seedE的长度至少为160位；

d）Fq上椭圆曲线E的等式定义的Fq上的两个元素a和b；

e）定义E（Fq）中素数阶有限点G=（xG，yG）的Fq上两个域元素xG和yG；

f）点G的阶数n，n>2160且n>4q；

g）以及伴随因子h=#E（Fq）/n。

3．2生成ECDSA密钥对

ECDSA密钥对与EC域参数的特定集相关联。

公钥是基点的随机倍数；而私钥则是用来生成这个倍数的整数。

为了生成ECDSA密钥对，每个成员A都要做如下操作（见图3）：

a）在区间【』，，l-』】中选择一个随机或伪随机整数d；

b）计算Q=dG；

c）A的公钥是Q，私钥是d。

3．3生成ECDSA签名

为了签署消息m，具有域参数D=（口，FR，a，b，G，n，h）及其相关密钥对（，Q）成员A作如下操作图4）：

a）选择一个随机或伪随机整数k满足1≤足≤，1．1；

b）计算kG=Y），且将l转换成整数；

c）计算r=Xlmodn，如果r=O则回到第a步；

d）计算k～modn；

e）计算SHA一1（，，1），并将该位串转换成整数；

f）计算S=（外r）modn，如果s=O则回到第a步；

g）A对消息，，l的签名为（r，）。

3．4验证ECDSA签名

要验证A在消息m上的签名为（r，s），取得A域参数D=-（q，FR，a，b，G，n，JI1）的可信副本和相关公钥Q，推荐也验证D和Q的有效性，然后做以下的操作（见图5）：

a）验证，．和s是区间．【f，l／-J】内的整数；

b）计算SHA-1），并将该位串转换成整数P；

c）计算W=S—modn；

d）计算l1‘=modn和L2‘=mod，l；

e）计算X=UlG+l2‘Q；

f）如果X=0则拒绝签名；否则转换x的坐标l为整数，并计算’，=，lnodtl；

g）当且仅当v=r时接受签名。

4椭圆曲线数字签名算法的程序实现

4．1椭圆曲线数字签名算法的程序流程图

根据上述原理，用c语言开发了二元域F2上的应用程序ECDSA．exe。

4．1．1椭圆曲线数字签名算法密钥对生成流程

图3密钥对生成流程

4．1．2椭圆曲线数字签名算法签名流程

图4签名流程

4．1．3椭圆曲线数字签名算法验证签名流程

图5验证流程

4．2椭圆曲线数字签名算法签名和验证实例

图6ECDS行实例

a）选用的NIST推荐椭圆曲线

m163

FRGaussianNormalBasis．T=4

a0x000000ooo00000oo000oooo00o0o000o000oooo0o1

b0x000000000000000000000Ooo000000000000OOo001

xG0x02FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8vG0x0289070FB05D38F18321F2E800536D538CCDAA3D9

n0x04000000000000000000020108A2EOCC0D99F8A5EF

h2

FR2约筒多项式为，∽=163+7+6+3+1

b）私钥

0x00x5584d4bf0x7562818e0x97eafa7b0x85626bde0x5689e56c

c）公钥

0x30x4c6750fd0xa319d5480x89ae53d20x9ae4a5b10x898c949d

0x70x3c4095300x1d2971320x51a04o800xb6ffe8200x1ca09450

d）签名

437352739857664o063579304354969275615843559206632

3582594310210854879224414194207883244929923159093

e）椭圆曲线数字签名密钥对生成、对消息文件签名以及验证签名的过程（如图6所示）。

f）ECDSA运行结果分析

由程序可知：

签名有效输出为ValidSignature；签名无效输出为InvalidSignature。

根据图6运行结果可以清楚看到该程序成功实现了密钥对生成、签名和验证过程。

所以该程序基本完成了椭圆曲线数字签名算法的程序实现，结果正确。

且由表1可知，该程序采用了163位推荐椭圆曲线，而目前可接受的安全强度为112位，所以该程序在密钥位的安全强度上是足够的。

5椭圆曲线数字签名算法的安全性

ECDSA的安全目标是，在现有软硬件条件下使用选择明文攻击签名不可伪造，对一个合法成员A发动此

类攻击的攻击者的攻击目标是在获取A在攻击者所选择的消息集（不包括，，1）上的签名之后，能获取A在某一单条消息上的有效签名。

当前流行的公钥密码系统的数学基础主要有以下三类:

a）因数分解问题（IFP），如RSA，Rabin—Williams算法等；

b）普通离散对数问题（DLP），如DSA算法；

c）椭圆曲线离散对数问题（ECDLP），如ECDSA算法。

表1为不同密钥系统对密钥尺寸的需求，图7为几种公钥系统抗攻击性比较。

从中可以看到对于相同的密钥位强度，ECC系统要比其它几种公钥系统密钥尺寸小得多。

表1不同密钥系统对密钥尺寸的需求

图7几种公钥系统抗攻击性比较

所以ECC和其它几种公钥系统相比，其抗攻击性具有绝对的优势，具有单位比特最高强度的安全性。

如160bitECC与1024bitRSA、DSA有相同的安全强度，而224bitECC则与2048bitRSA、DSA具有相同的安全强度。

鉴于ECDSA是ECC系统基本原理在数字签名中的应用，故ECC系统的安全性就是ECDSA的安全性。

Pointcheval和Stern已经证明了，基于椭圆曲线离散对数问题且所使用的哈希函数是随机函数的前提下，对于选择明文攻击，ECDSA在现有的情况下是不可伪造的。

Browntr]证明了在基本群为普通群且所使用的散列函数是抗冲突的前提下，ECDSA本身是安全的。

6结论

ECDSA是ANSI、IEEE、FIPS、NIST和ISO标准，且正为其它的标准化组织作为标准。

通过对其软件实现、运行测试及分析表明，它具有抗攻击性强、计算量小、处理速度快、密钥尺寸和系统参数小、带宽要求低等优点。

所以研究开发具有自主知识版权的椭圆曲线数字签名算法对于提高信息安全水平有较大的实用价值和现实意义。

TheAlgorithmImplementationofECDSAandSecurityAnalysis

ZHANGWei

（InstituteofElectronicEngineering，CAEP,Minaynag621900，China）Abstract：

ThearithmeticrationaleofANSIX9．62EllipticCurveDitalSingatureAlgorithm（ECDSA）ispreesntednaditssecurityisdiscussedpreliminary．ThroughitsprogramimplementationnadrelativenaalysisitCnabe

foundthatthisprogramrealizesthebasicfunctionofECDSAnadhasmuchadvnatageslikesmallparameters，fast

computationsnadsmallkeyetc．．Keywords：

ellipticcurvecryptography；ECDSA；algorithmimplementation；security