椭圆曲线密码芯片及接口的设计与实现.pdf

《椭圆曲线密码芯片及接口的设计与实现.pdf》由会员分享，可在线阅读，更多相关《椭圆曲线密码芯片及接口的设计与实现.pdf（109页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、华南理工大学硕士学位论文椭圆曲线密码芯片及接口的设计与实现姓名：邹候文申请学位级别：硕士专业：计算机技术指导教师：唐韶华;唐屹20041101摘要摘要 椭圆曲线密码的安全性得到普遍的公认，在比特安全性上和 目前广泛使用的R S A相 比有很大的差距，在一些资源受限如智能卡、P D A、移动设备等环境 下和R S A 相比也有较为明显的优势。本文主要从以下几个方面对特征 P 上椭圆曲线密码(E C C)的实现进行了讨论:首选是介绍基本的数学基础以及如何建立椭圆曲线密码系统，并给出了我们在项目中使用的带认证的加密方案。第二是探讨了椭圆曲 线密码系统的程序编制问 题，在此我们讨论并测试了大整数运算和

2、有效实现椭圆曲线密码运算的算法，并粗略地比较了美国国立标准与技术研究院(K I S T)推荐的曲线和我们选择的曲线的实现效率，对实现椭圆曲线密码所需要的 H a s h算法、伪随机数的产生以及对称加密算法进行了简单讨论并给出了相应的实验数据。第三是关于椭圆曲线密码在单片机中的实现，并和文献上的实现结果进行了比较，简单地讨论 了卡上私钥的安全保护技术问题，同时在该芯片的接 口上作 了较为详细的讨论，其中包括 串行、U S B和 P C I 接 口的软硬件实现方案和科研样品的制作过程。我们设计的U S B 接口的椭圆曲线密码卡具有保护私钥的功能，与文献上的实现速度相比有较大的优势，能够满足实际应用

3、的需求，该卡可应用于电子政务和电子商务中。设计的 P C I 卡为我们今后设计高速的密码芯片打下良好的基础。关键词:椭圆曲线，密码芯片，串行接口，U S B 接口，P C I 接口华南理工大学硕士学位论文Ab s t r a c tT h e s e c u r i t y o f t h e e l l i p t i c c u r v e c r y p t o g r a p h y i s a c k n o w l e d g e d.I t s s e c u r i t yi n t e n s i t y p r o v i d e d b y a b i t i s s t

4、 r o n g e r t h a n t h a t o f R S A.C o m p a r i n g w i t h R S A,i t h a sp r e d o m i n a n c e u n d e r s o me r e s t r i c t e d r e s o u r c e,s u c h a s s ma r t c a r d,P D A,mo b i l ed e v i c e.T h i s p a p e r m a i n l y d i s c u s s e s c e r t a i n a s p e c t s o f t h e

5、i m p l e m e n t a t i o n o f E l l i p t i cC u r v e C r y p t o g r a p h y o v e r c h a r a c t e r i s t i c p a s f o l l o w:F i r s t o f a l l i n t r o d u c e b a s i cm a t h e m a t i c k n o w l e d g e a n d h o w t o s e t u p a c r y p t o g r a p h i c s y s t e m o f e l l i p

6、t i c c u r v e s a sw e l l a s p r o v i d e a v e r i f i a b l e e n c r y p t i o n s c h e m e u s e d i n o u r p r o j e c t.S e c o n d l y w es t u d y h o w t o s p e e d u p t h e p e r f o r ma n c e o f t h e s y s t e m.We u s e d i f f e r e n t m o d u l e s,s o m e o f w h i c h i

7、s r e c o mme n d e d b y N I S T a n d t h e o t h e r i s c h o s e n b y u s,t o i m p l e me n tm o d u l a r m u l t i p l i c a t i o n a n d c o m p a r i n g t h e i r e f f i c i e n c y,a n d t e s t s o m e a l g o r i t h m sw h i c h c a n e f f i c i e n t l y p e r f o r m t h e o p e

8、 r a t i o n s o f E l l i p t i c C u r v e C r y p t o g r a p h yMo r e o v e r,i m p l e m e n t a n d d i s c u s s t h e h a s h f u n c t i o n a n d t h e p s e u d o r a n d o m n u m b e rg e n e r a t i o n a l g o r i t h m a s w e l l a s A d v a n c e d E n c r y p t i o n S c h e m e

9、a n d s t i l l g i v e t h e i re x p e r i m e n t a l d a t a r e s p e c t i v e l y.T h i r d l y,w e i m p l e m e n t E C C i n t h e S C M a n d c o m p a r eo u r r e s u l t w i t h t h e r e f e r e n c e s,a t t h e s a me t i m e d i s c u s s i n d e t a i l h o w t o u s e s o f t a n

10、 dh a r d w a r e t o i m p l e m e n t t h e c h i p i n t e r f a c e s u c h a s t h e C O M，U S B a n d P C I.O u rc i p h e r c a r d o f t h e e l l i p t i c c u r v e w i t h U S B i n t e r f a c e,c a n p r o t e c t p r i v a t e k e y,a n d i t ss p e e d i s h i g h e r t h a n t h a t

11、o f t h e i m p l e me n t o n t h e r e f e r e n c e s.I t c a n s a t i s f y p r a c t i c a la p p l i c a t i o n s u c h a s E l e c t r i c G o v e r n me n t a n d E l e c t r i c B u s i n e s s.K e y Wo r d s:i n t e r f a c ee l l i p t i c c u r v e,c i p h e r c a r d,s e r i a l i n t

12、 e r f a c e d,U S B i n t e r f a c e,P C Iit 华南理工大学学位论文原创性声明 本人郑重声明:所呈交的论文是 本人在导师的指导下独立进行研究所取得的研究成果。除了 文中特别加以 标注引用的内 容外，本论文不 包含任何其他个人或集休已经发表或撰写的 成果作品。对本文的研究做出重要贡献的个人和集体，均已 在文中以明 确方式标明。本人完全意识到本声明的法律后果 由本人承担。作 者 签 名:铆 文日 期:z o a 今 年 /月 1 5 日学位论文版权使用授权书 本学位论文作者完全了 解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门 或机构

13、送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华南理上大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口，在_年解密后适用本授权书。本学位论文属于 不保密口。(请在以 上相应方框内打“J )作 者 签 名:3 M久日 期-诚日 期:m年I 月/5日年1!月 I S 日第一章绪论第一章绪论椭圆曲线密码学研 究现状 椭圆曲线公钥密码(E C C)最早在 1 9 8 5 年由N e a l K o b l i t z 和 V.M i I I e r 分别独立地提出，是继 R S A,D S A之后安全性得到普遍公认

14、的又一个 公钥密码。公钥密码都基于某个数学难题，椭圆 曲线密码最吸引人的地方在于它基于椭圆曲线离散对数(E C D L P)问题，到目前为止，求解椭圆曲线离散对数问题最好的方法还是指数级时间复杂度的，而 R S A 的大数分解和 D S A 的离散对数目 前已经找到亚指数时间复杂度的求解方法。这意味着在相同安全级别的情况下，E C C 的系统参数要比R S A 和 D S A 要小，目前普遍认为 1 6 0 位的 E C C 和 1 0 2 4 位的 R S A,D S A 的安全性相当，并且随着安全级别的不断提 高，这种差别将会越来越大。近年来，许多国际标准化组织己将椭圆曲线公钥密码体制作为

15、其标准向全球颁布，其中包括I E E E(I n s t i t u t e o f E l e c t r i c a l a n d E l e c t r o n i c s E n g i n e e r s)、A N S I(A m e r i c a nN a t i o n a l S t a n d a r d s I n s t i t u t e)、I S O(I n t e r n a t i o n a l S t a n d a r d sO r g a n i z a t i o n)、N I S T(N a t i o n a l I n s t i t u t

16、e o f S t a n d a r d s a n d T e c h n o l o g y)等。2 本文的理论与实际意义 随着计算机网络的日益普及，公钥密码的作用也显得越来越重要。椭圆曲线密码体制是目前己知的公钥体制中比特安全性最强的一种体制，它不但可以实现高 度安全性，而且在同等安全强度下，能够以 较小的开销和时延实现较高的安全性。因此E C C 特别适用于带宽、存储空间、能耗等资源条件受限的情况，这主要包括智能卡、移动设备、P D A(P e r s o n a l D i g i t a l A s s i s t a n t)等。目前椭圆曲线的理论研究已经较为成熟，国外己有用椭

17、圆曲线进行加解密和数字签名的产品出现在市场上，这些产品可被广泛应用于保密通信、网络安全、电 子商务等方面。国内也有很多椭圆曲线密码体制的软件和硬件的实现，但从实用角度出发，还存在着很多不尽如人意的地方。目前智能卡己经广泛应用于金融、电信等领域，由于用传统的手法很难窃取其上的数据，因此特别适用于存放公钥密码系统中的私钥，所有涉及到私钥的运算都可以在卡上完成，私钥自始至终都不离开智能卡，目 前这是一种被认为最好的管理私钥的方法。智能卡上有一片单片机，并有其标准的接口，由于处理私钥的密码卡的应用环境和目 前广泛使用的智能卡的使用场合和环境有所不同。日 5 日第一章绪论第一章绪论椭圆曲线密码学研 究现

18、状 椭圆曲线公钥密码(E C C)最早在 1 9 8 5 年由N e a l K o b l i t z 和 V.M i I I e r 分别独立地提出，是继 R S A,D S A之后安全性得到普遍公认的又一个 公钥密码。公钥密码都基于某个数学难题，椭圆 曲线密码最吸引人的地方在于它基于椭圆曲线离散对数(E C D L P)问题，到目前为止，求解椭圆曲线离散对数问题最好的方法还是指数级时间复杂度的，而 R S A 的大数分解和 D S A 的离散对数目 前已经找到亚指数时间复杂度的求解方法。这意味着在相同安全级别的情况下，E C C 的系统参数要比R S A 和 D S A 要小，目前普遍认

19、为 1 6 0 位的 E C C 和 1 0 2 4 位的 R S A,D S A 的安全性相当，并且随着安全级别的不断提 高，这种差别将会越来越大。近年来，许多国际标准化组织己将椭圆曲线公钥密码体制作为其标准向全球颁布，其中包括I E E E(I n s t i t u t e o f E l e c t r i c a l a n d E l e c t r o n i c s E n g i n e e r s)、A N S I(A m e r i c a nN a t i o n a l S t a n d a r d s I n s t i t u t e)、I S O(I n t

20、e r n a t i o n a l S t a n d a r d sO r g a n i z a t i o n)、N I S T(N a t i o n a l I n s t i t u t e o f S t a n d a r d s a n d T e c h n o l o g y)等。2 本文的理论与实际意义 随着计算机网络的日益普及，公钥密码的作用也显得越来越重要。椭圆曲线密码体制是目前己知的公钥体制中比特安全性最强的一种体制，它不但可以实现高 度安全性，而且在同等安全强度下，能够以 较小的开销和时延实现较高的安全性。因此E C C 特别适用于带宽、存储空间、能耗等资源

21、条件受限的情况，这主要包括智能卡、移动设备、P D A(P e r s o n a l D i g i t a l A s s i s t a n t)等。目前椭圆曲线的理论研究已经较为成熟，国外己有用椭圆曲线进行加解密和数字签名的产品出现在市场上，这些产品可被广泛应用于保密通信、网络安全、电 子商务等方面。国内也有很多椭圆曲线密码体制的软件和硬件的实现，但从实用角度出发，还存在着很多不尽如人意的地方。目前智能卡己经广泛应用于金融、电信等领域，由于用传统的手法很难窃取其上的数据，因此特别适用于存放公钥密码系统中的私钥，所有涉及到私钥的运算都可以在卡上完成，私钥自始至终都不离开智能卡，目 前这是

22、一种被认为最好的管理私钥的方法。智能卡上有一片单片机，并有其标准的接口，由于处理私钥的密码卡的应用环境和目 前广泛使用的智能卡的使用场合和环境有所不同。日 5 日华南理工大学硕士学位论文接 口作为 目前个人计算机最通用、最方便的接 口之一，我们为椭 圆曲线密码卡设计了U S B 接口。同时为便于需要时开发智能卡，我们在设计时选择某智能卡芯片对应型号的单片机作为主处理器，如此一来，我们在设计智能卡时对单片机 上的代码更改是非常少的。串行口作为计算机上一个通用的接口，虽然目前正逐步被U S B 所取代，但 由于其设 计相对于 U S B设计来说较 为容易，对 U S B接 口有参考意义，因此我们实

23、现并讨论了单片机的串行接口。对于一些需要大量密码运算的应用场合，设计高速的密码处理芯片是解决问题的一个可取的方法，这就存在芯片与计算机实现 高速接 口的问题,P C I 接口作为 目前高速通用 的微机接口，是高速的密码处理芯片接 口的理想选择之一，因此本文也讨论并实现了 P C I 接口。3 国内外相关文献综述 在公钥密码中使用椭圆曲线的思想来自 于 K o b l i t z 和M i l l e r 。到目前为止己经有多家标准组织或机构公布了相关的椭圆曲线标准或草案，主要包括工 3-9 等。文献 1 0 是一篇由K o b l i t z,M e n e z e s 和 V a n s t

24、 o n 撰写关于这个主题的综述性文章，在综述文章方面我们还参考 了 1 1 和【1 2 。在【1 3 中可 以看到很好的快速实现椭圆曲线运算方面的讨论。在椭圆曲线域的选择上，除了P 1 3 6 3 中讨论的特征 P、特征2 外，目前还有优化扩域 1 4,2 0、小特征 1 5 等。文献 1 6)讨论椭圆曲线在单片机中的实现，文献 1 7,1 8,2 7 讨论了椭圆曲线密码在 MC S 5 1 微处理器的实现，文献 2 6)讨论了在 MS P 4 3 0 x 3 3 x 微处理器中的实现，在这些讨论中都可以找到他们的的实验数据。4 本研究课题的来源 本研究课题来源于由广州大学信息安全研究所裴定

25、一教授主持的项目:“椭圆曲线密码的实现及其应用”，该项目主要包括以下几方面内容:1)G T I S 1.0信息安全软件:2)生成安全椭圆曲线算法的快速软件实现(S E A 和 S a t h o);3)G T E C密码卡:4)著作(研究生教材)一本，论文 8 篇(S C I 收录2 篇)。该项目己于 0 4 年7月9日 通过了广州市科技局组织的专家鉴定，本人在项目中负责 G T E C密码卡的硬件和主机接口程序的设计，并且参与了卡上应用逻辑的设计。5 本文主要 内容和章节安排 本文第二章介绍椭圆曲线密码体制中涉及到的一些基本概念包括有限域、椭圆曲线、椭圆曲线点的表示、椭圆曲线密码体制的建立等

26、内容。第三章主要讨论华南理工大学硕士学位论文接 口作为 目前个人计算机最通用、最方便的接 口之一，我们为椭 圆曲线密码卡设计了U S B 接口。同时为便于需要时开发智能卡，我们在设计时选择某智能卡芯片对应型号的单片机作为主处理器，如此一来，我们在设计智能卡时对单片机 上的代码更改是非常少的。串行口作为计算机上一个通用的接口，虽然目前正逐步被U S B 所取代，但 由于其设 计相对于 U S B设计来说较 为容易，对 U S B接 口有参考意义，因此我们实现并讨论了单片机的串行接口。对于一些需要大量密码运算的应用场合，设计高速的密码处理芯片是解决问题的一个可取的方法，这就存在芯片与计算机实现 高

27、速接 口的问题,P C I 接口作为 目前高速通用 的微机接口，是高速的密码处理芯片接 口的理想选择之一，因此本文也讨论并实现了 P C I 接口。3 国内外相关文献综述 在公钥密码中使用椭圆曲线的思想来自 于 K o b l i t z 和M i l l e r 。到目前为止己经有多家标准组织或机构公布了相关的椭圆曲线标准或草案，主要包括工 3-9 等。文献 1 0 是一篇由K o b l i t z,M e n e z e s 和 V a n s t o n 撰写关于这个主题的综述性文章，在综述文章方面我们还参考 了 1 1 和【1 2 。在【1 3 中可 以看到很好的快速实现椭圆曲线运算

28、方面的讨论。在椭圆曲线域的选择上，除了P 1 3 6 3 中讨论的特征 P、特征2 外，目前还有优化扩域 1 4,2 0、小特征 1 5 等。文献 1 6)讨论椭圆曲线在单片机中的实现，文献 1 7,1 8,2 7 讨论了椭圆曲线密码在 MC S 5 1 微处理器的实现，文献 2 6)讨论了在 MS P 4 3 0 x 3 3 x 微处理器中的实现，在这些讨论中都可以找到他们的的实验数据。4 本研究课题的来源 本研究课题来源于由广州大学信息安全研究所裴定一教授主持的项目:“椭圆曲线密码的实现及其应用”，该项目主要包括以下几方面内容:1)G T I S 1.0信息安全软件:2)生成安全椭圆曲线算

29、法的快速软件实现(S E A 和 S a t h o);3)G T E C密码卡:4)著作(研究生教材)一本，论文 8 篇(S C I 收录2 篇)。该项目己于 0 4 年7月9日 通过了广州市科技局组织的专家鉴定，本人在项目中负责 G T E C密码卡的硬件和主机接口程序的设计，并且参与了卡上应用逻辑的设计。5 本文主要 内容和章节安排 本文第二章介绍椭圆曲线密码体制中涉及到的一些基本概念包括有限域、椭圆曲线、椭圆曲线点的表示、椭圆曲线密码体制的建立等内容。第三章主要讨论华南理工大学硕士学位论文接 口作为 目前个人计算机最通用、最方便的接 口之一，我们为椭 圆曲线密码卡设计了U S B 接口

30、。同时为便于需要时开发智能卡，我们在设计时选择某智能卡芯片对应型号的单片机作为主处理器，如此一来，我们在设计智能卡时对单片机 上的代码更改是非常少的。串行口作为计算机上一个通用的接口，虽然目前正逐步被U S B 所取代，但 由于其设 计相对于 U S B设计来说较 为容易，对 U S B接 口有参考意义，因此我们实现并讨论了单片机的串行接口。对于一些需要大量密码运算的应用场合，设计高速的密码处理芯片是解决问题的一个可取的方法，这就存在芯片与计算机实现 高速接 口的问题,P C I 接口作为 目前高速通用 的微机接口，是高速的密码处理芯片接 口的理想选择之一，因此本文也讨论并实现了 P C I

31、接口。3 国内外相关文献综述 在公钥密码中使用椭圆曲线的思想来自 于 K o b l i t z 和M i l l e r 。到目前为止己经有多家标准组织或机构公布了相关的椭圆曲线标准或草案，主要包括工 3-9 等。文献 1 0 是一篇由K o b l i t z,M e n e z e s 和 V a n s t o n 撰写关于这个主题的综述性文章，在综述文章方面我们还参考 了 1 1 和【1 2 。在【1 3 中可 以看到很好的快速实现椭圆曲线运算方面的讨论。在椭圆曲线域的选择上，除了P 1 3 6 3 中讨论的特征 P、特征2 外，目前还有优化扩域 1 4,2 0、小特征 1 5 等。

32、文献 1 6)讨论椭圆曲线在单片机中的实现，文献 1 7,1 8,2 7 讨论了椭圆曲线密码在 MC S 5 1 微处理器的实现，文献 2 6)讨论了在 MS P 4 3 0 x 3 3 x 微处理器中的实现，在这些讨论中都可以找到他们的的实验数据。4 本研究课题的来源 本研究课题来源于由广州大学信息安全研究所裴定一教授主持的项目:“椭圆曲线密码的实现及其应用”，该项目主要包括以下几方面内容:1)G T I S 1.0信息安全软件:2)生成安全椭圆曲线算法的快速软件实现(S E A 和 S a t h o);3)G T E C密码卡:4)著作(研究生教材)一本，论文 8 篇(S C I 收录2

33、 篇)。该项目己于 0 4 年7月9日 通过了广州市科技局组织的专家鉴定，本人在项目中负责 G T E C密码卡的硬件和主机接口程序的设计，并且参与了卡上应用逻辑的设计。5 本文主要 内容和章节安排 本文第二章介绍椭圆曲线密码体制中涉及到的一些基本概念包括有限域、椭圆曲线、椭圆曲线点的表示、椭圆曲线密码体制的建立等内容。第三章主要讨论第一章绪论椭圆曲线密码的编程实现，这其中包括大整数运算和有限域上的椭圆曲线运算，在大整运算上简单讨论了我们使用的模和 N 工 S T 推荐的模.在有限域上的椭圆曲线运算中我们采用了一些优化算法，在这一章中我们还简单介绍了 编程中需要使用到的几个附加算法。第四章我们

34、讨论了椭圆曲线在单片机中的实现。根据串行接口、U S B 接口和P C I 接口的不同特点，我们对它们的软硬件开发都作了较为详细的讨论。第五章是一个简单的应用实例。华南理一 大学硕士学位论文第二章椭圆曲线密码体制2.1 有限域 F P 设 p是一个素数，则有限域 F。称为素数域，它由元素 0,1，2,，p-1 和下面的操作组成:加法:令a,b E F,.，则 a+b=r，其中0-r-p-l,r 是 a+b 对p 求模的结果，这个运算我们也称之为模加运算。乘法:令a,b E F P，则a*b=s，其中0-s-p-l,s 是a*b 对 p 求模的结果，这个运算我们也称之为模乘运算。求逆:a 是 F

35、。上的不为零的元素，则 a 模 p 的逆(a-)是 F。上的唯一的一个数，这个数使得a*a 一 (m o d p)=1.例子:对于有限域F,1 0+9=6(1 9 m o d 1 3=6);1 0*9=1 2(9 0 m o d 1 3=1 2);9-=3(9*3 m o d 1 3=1)。2.2 有限域 F p 上的椭 圆曲线 设 p 是大于 3 的素数，F p 上的椭圆曲线 E 由以下方程定义 y =x +a x+b (1)其中a,b E F,4 a +2 7 6 2#0,椭圆曲 线 E(F p)由 满足方 程 1 的 所有解(P.,P,)和一个称作无穷远点 0 组成，椭圆曲线上的加法规则

36、是:1.0 是加法的单位元。0=-0，对于椭圆曲 线上的任一点P 有 P+O=O+P=P o 2.两个 x 坐标相同但 Y 坐标不同的点相加，即P,=(x,y)和 P,=(x，-Y),则其结果是无穷远点。若 P;二 一 P 2，则P,+P Z=O o 3.要对具有不同的 x 坐标的两个点 Q 1(x,Y,)和 Q 2(x 2,Y s)进行相加，其结果为R(x 3,Y 3),x 3,Y 3 可由以下公式求得:X 3=t-X 1-X z,Y a 1(X,-X 3)-Y 1，其 中x=(Y z-Y J/(x,-X 0 0 4.要对一个点Q(X 1,Y 1)加倍，其结果为 R(x 3,Y 3),X 3

37、,Y 3 可由以下公式求得:x 3 A z-2 X 1,Y s X(x 1-x 3)一 Y 1,l=(3 x，3+a)/2 Y 1例子:设E 是在 Z,，上的椭圆曲线 Y z=x 3+x+6 o E 上有 1 3 个点，即。,(2,4),(2,7),(3,5),(3,6)，(5,2)，(5,9)，(7,2),(7,9),(8,3)，(8,8),(1 0,2)，(1 0,9)。因为任何 素数阶群都是循环群，所 以 E同构于 Z 1 3，并且 除了无穷远点 0 外，华南理一 大学硕士学位论文第二章椭圆曲线密码体制2.1 有限域 F P 设 p是一个素数，则有限域 F。称为素数域，它由元素 0,1，

38、2,，p-1 和下面的操作组成:加法:令a,b E F,.，则 a+b=r，其中0-r-p-l,r 是 a+b 对p 求模的结果，这个运算我们也称之为模加运算。乘法:令a,b E F P，则a*b=s，其中0-s-A1 1+2 M+25J 十 A-J8 M+3S2 A-A1 1+2 M+2SP十 P-P1 2M+2 SJ+C-J1 1 M+3 S2 P-P7 M+3SJ+J-J1 2M+4 SC 十 A-C8M+3S2 J-J4 M+4 SC+C-C1 1 M+3 S2C-C5 M+4 S注:A 表示仿射坐标，P表示标准射影坐标，J表示J a c o b i a n 射影坐标，C表示C h u

39、 d n o v s k y J a c o b i a n坐标。工 表示求逆，5表示求平方.M表示求乘法。2.4 椭圆曲线密码系统的建立 考虑方程 Q=k P，其中Q,P 属于E(F,)，且 k A1 1+2 M+25J 十 A-J8 M+3S2 A-A1 1+2 M+2SP十 P-P1 2M+2 SJ+C-J1 1 M+3 S2 P-P7 M+3SJ+J-J1 2M+4 SC 十 A-C8M+3S2 J-J4 M+4 SC+C-C1 1 M+3 S2C-C5 M+4 S注:A 表示仿射坐标，P表示标准射影坐标，J表示J a c o b i a n 射影坐标，C表示C h u d n o v

40、 s k y J a c o b i a n坐标。工 表示求逆，5表示求平方.M表示求乘法。2.4 椭圆曲线密码系统的建立 考虑方程 Q=k P，其中Q,P 属于E(F,)，且 k A1 1+2 M+25J 十 A-J8 M+3S2 A-A1 1+2 M+2SP十 P-P1 2M+2 SJ+C-J1 1 M+3 S2 P-P7 M+3SJ+J-J1 2M+4 SC 十 A-C8M+3S2 J-J4 M+4 SC+C-C1 1 M+3 S2C-C5 M+4 S注:A 表示仿射坐标，P表示标准射影坐标，J表示J a c o b i a n 射影坐标，C表示C h u d n o v s k y J

41、 a c o b i a n坐标。工 表示求逆，5表示求平方.M表示求乘法。2.4 椭圆曲线密码系统的建立 考虑方程 Q=k P，其中Q,P 属于E(F,)，且 k 2-和n 4 q 2 o6 确认 n G=O o7.确认#E(F,)#q.8，确认输入一个数 B:-:,2 0，使得 以下算法输出 1 0 a)t 二 1.b)f o r i f r o m 1 t o B d o t h e f o l l o w i n g;b l)s e t t 二 t q m o d n.b 2)i f t=1 t h e n r e t u r n 0.c)R e t u r n 1.如果通过以上 8

42、步检查，则输出“v a l i d ，否则输出“i n v a l i d .1-6 步的作用是保证所用曲线是一条合法曲线，第 7 步是为了避免 S S A S 攻击，第 8 步是为了避免 M O V攻击。2.4.2 公私钥对的产生 当椭圆曲线的参数确定以后，公私钥对的产生就相当容易，可以用以下方法产生公私钥对:1)产生一个随机数 s k e y,O-s k e y 2-和n 4 q 2 o6 确认 n G=O o7.确认#E(F,)#q.8，确认输入一个数 B:-:,2 0，使得 以下算法输出 1 0 a)t 二 1.b)f o r i f r o m 1 t o B d o t h e f

43、 o l l o w i n g;b l)s e t t 二 t q m o d n.b 2)i f t=1 t h e n r e t u r n 0.c)R e t u r n 1.如果通过以上 8 步检查，则输出“v a l i d ，否则输出“i n v a l i d .1-6 步的作用是保证所用曲线是一条合法曲线，第 7 步是为了避免 S S A S 攻击，第 8 步是为了避免 M O V攻击。2.4.2 公私钥对的产生 当椭圆曲线的参数确定以后，公私钥对的产生就相当容易，可以用以下方法产生公私钥对:1)产生一个随机数 s k e y,O-s k e y,p-l o 2)计算随机数

44、 s k e y 和基点 G 的点乘 p u b k e y=s k e y*G，判断 p u b k e y 是否在曲 线上，若不在曲线上则转到 1),3)秘密保存私钥 s k e y 并公开公钥 p u b k e y,公钥的有效性检查输入:经过检验的椭圆曲线参数和该椭圆曲线上的一个公钥 Q,输出:合法的公钥则输出“v a l i d ,否则输出“i n v a l i d e1.确认 Q-A 0,华南理工大学硕士学位论文2.确认 x,和 y。在 0 和 p-1 之间。3.确认 y。3Y u=X，十 a x,+b o4.确认 n Q=O o 如果通 过以上 4步检查则输出“v a l i

45、d ，否则输 出“i n v a l i d 。注意如果在同一椭圆曲线参数上有多个公钥则还要确认没有任何一个公钥是相同的。2.4.3 签名方案 签名过程 输入:明文M、私钥 s k e y 和椭圆曲线参数。输出:签名信息。1)选择一个随机数 r,1 r p-l o 2)计算随机数和基点的点乘，并取 X 坐标 R=X(r*G),3)计算 M 和 R 的H a s h 值并与私钥相乘 K=H(M I I R)*s k e y,4)计算随机数和 K 的差值S=r-K o 5)返回(R,S)作为签名结果。验证签名过程:输入:明文M、签名结果(R,S)和签名者的公钥 p u b k e y o 输出:0

46、表示验证失败，1 表示验证成功。6)计算 M 和 R 的H a s h 值 V=H(M I I R)。7)计算 V 与签名者的公钥的点乘V 1=V*p u b k e y o 8)计算 S 和基点G 的点乘V 2=S*G o 9)计算 V 1 和 V 2的点加 V 3=V I+V Z o 1 0)用V 3 的X 坐标和 R 比较，相等则返回 1，否则返回0.本签名方案和 E C D S P 的区别是不用求 s-(m o d。)。2.4.4 加密方案加密过程 输入:明文 M，公钥 p u b k e y 和椭圆曲线参数。输 出:密文。1)选择一个随机数 r,l-r-p-l o 2)计算随机数和基

47、点的点乘 R=r*G o 3)计算随机数和公钥的点乘 K=r*p u b k e y=(K _ x,K _ y)e 4)计算 K _ x 的H a s h 值 K l=H(K _ x)，这里的H a s h 函数我们采用 S H A-1 算法。5)计算 K 1 的 H a s h值 K 2=H(K l)。6)用 K 1 作密钥对明文进行加密，这里我们采用模 2 加，C=M.K 1.华南理工大学硕士学位论文2.确认 x,和 y。在 0 和 p-1 之间。3.确认 y。3Y u=X，十 a x,+b o4.确认 n Q=O o 如果通 过以上 4步检查则输出“v a l i d ，否则输 出“i

48、n v a l i d 。注意如果在同一椭圆曲线参数上有多个公钥则还要确认没有任何一个公钥是相同的。2.4.3 签名方案 签名过程 输入:明文M、私钥 s k e y 和椭圆曲线参数。输出:签名信息。1)选择一个随机数 r,1 r p-l o 2)计算随机数和基点的点乘，并取 X 坐标 R=X(r*G),3)计算 M 和 R 的H a s h 值并与私钥相乘 K=H(M I I R)*s k e y,4)计算随机数和 K 的差值S=r-K o 5)返回(R,S)作为签名结果。验证签名过程:输入:明文M、签名结果(R,S)和签名者的公钥 p u b k e y o 输出:0表示验证失败，1 表示

49、验证成功。6)计算 M 和 R 的H a s h 值 V=H(M I I R)。7)计算 V 与签名者的公钥的点乘V 1=V*p u b k e y o 8)计算 S 和基点G 的点乘V 2=S*G o 9)计算 V 1 和 V 2的点加 V 3=V I+V Z o 1 0)用V 3 的X 坐标和 R 比较，相等则返回 1，否则返回0.本签名方案和 E C D S P 的区别是不用求 s-(m o d。)。2.4.4 加密方案加密过程 输入:明文 M，公钥 p u b k e y 和椭圆曲线参数。输 出:密文。1)选择一个随机数 r,l-r-p-l o 2)计算随机数和基点的点乘 R=r*G

50、o 3)计算随机数和公钥的点乘 K=r*p u b k e y=(K _ x,K _ y)e 4)计算 K _ x 的H a s h 值 K l=H(K _ x)，这里的H a s h 函数我们采用 S H A-1 算法。5)计算 K 1 的 H a s h值 K 2=H(K l)。6)用 K 1 作密钥对明文进行加密，这里我们采用模 2 加，C=M.K 1.华南理工大学硕士学位论文2.确认 x,和 y。在 0 和 p-1 之间。3.确认 y。3Y u=X，十 a x,+b o4.确认 n Q=O o 如果通 过以上 4步检查则输出“v a l i d ，否则输 出“i n v a l i d