（系统分析与集成专业论文）基于椭圆曲线的数字签名及其应用研究.pdf

硕士学位论文基于椭圆曲线的数字签名及其应用研究 摘要 本课题的 任务是完成对椭圆曲 线数字签名改进算法的实现，以 及设计出 基于该 算法的门限群签名和有向门限群签名方案。 椭圆曲线密码体制有安全性能高、计算量小、速度快、占 用空间小、带宽要求 低等一系列优点，已 逐渐被各大国际标准组织采纳为公钥密码和数字签名标准。在 我国，电 子签名法律还刚刚颁布， 对椭圆曲 线数字签名的研究和应用还不成熟， 还 没有一个统一的标准， 对椭圆曲 线运用于特殊签名更是刚刚起步。因此， 深入研究 椭圆曲 线数字签名及其在特殊签名中的应用， 具有深远的意义。 本论文首先对密码体制特别是公钥密码体制进行了介绍，然后介绍了各类数字 签名，并 特别介绍了 椭圆曲 线数字签名算法及其改进算法;详细给出了用j a v a 2 实 现整个改进的 椭圆曲 线数字签名算法的 签名和验证过程;接着利用改进的 算法便于 进行密钥分割的 特性，给出了结合该椭圆曲 线数字签名算法、门限群签名思想和可 验证秘密分享思想设计的门限 群签名方案， 并对其正确性、稳定性和安全性进行了 论证;进一步设计了具有指定接收者的有向门限 群签名方案，并对其正确性、 稳定 性和安全性进行了论证。 本论文从实现角度证明了改进的椭圆曲线数字签名算法的正确性，并利用该算 法避免有限域内求逆运算的特性， 将其进行了可验证的密钥分割，设计出了一种新 的基于椭圆曲线的门限群签名方案和有向门限群签名方案。 关键词: 椭圆曲线，数字签名， j a v a 2 ，门限群签名，有向门限群签名 硕士学位论文 基于椭圆曲 线的数字签名及其应用研究 ab s t r a c t t h i s t as k i s t o c o m p l e t e t h e p e r f o r m a n c e o f t h e i m p r o v e d e c d s a a n d d e s i g n o f t h e t h r e s h o l d g r o u p s i g n a t u r e a n d t h e d i r e c t e d t h r e s h o l d g r o u p s i g n a t u re b a s e d o n t h e i m p r o v e d e c d s a . e l l i p t i c c u r v e c r y p t o s y s t e m h as t h e a d v a n t a g e s o f h e ig h t s e c u r i t y , s m a l l c o m p u t a t i o n a l c o m p l e x i t y , h i g h s p e e d , s m a l l s p a c e a n d l i m i t e d b a n d w i d t h , a n d h as b e e n a d o p t e d as p u b l i c k e y c r y p t o g r a p h y a n d d i g it a l s i g n a t u r e s t a n d a r d b y s e v e r a l i n t e r n a t i o n a l s t a n d a r d o r g a n i z a t i o n . i n o u r c o u n t r y , t h e e l e c t r o n i c s i g n a t u r e l a w h as j u s t p u b l i s h e d . t h e r e s e a r c h a n d a p p l ic a t i o n o f e c d s a a r e n o t m a t u r e d e n o u g h a n d t h e u n i t e d s t a n d a r d h as n o t f o r m e d . t h e r e s e a r c h o f t h e e l l i p t i c c u r v e a p p l i e d t o s p e c i a l s i g n a t u r e s i s o n l y a t s t a r t . t h e r e f o r e , it h as i m p o r t a n t s ig n i f i c a n t i n t h e r e s e a r c h i n e c d s a a n d i t s a p p l i c a t i o n t o s p e c i a l s i g n a t u r e s . t h i s p a p e r f i r s t l y a n a l y s i s e d t h e c ry p t o s y s t e m s , e s p e c i a l l y t h e p u b l i c k e y c r y p t o s y s te m . t h e n s o m e s o rt s o f d ig i ta l s i g n a t u r e s w e re in t r o d u c e d , e s p e c ia l ly t h e e c d s a a n d t h e i m p r o v e d a l g o r i t h m . t h e w h o le p r o c e s s o f e l l i p t i c c u r v e d i g i t a l s i g n a t u r e a n d a u t h e n t i c a t e u s e d j a v a 2 w as d e s c r i b e d i n d e t a i l . u s i n g t h e c h a r a c t e r i s t i c t h a t t h e i m p r o v e d s i g n a t u r e a l g o r i t h m i s c o n v e n i e n t t o s h a r e s e c r e t , a t h r e s h o l d g r o u p s i g n a t u r e s c h e m e w as p r o p o s e d , w h ic h in t e g r a t e d t h e im p r o v e d e c d s a , t h r e s h o l d s ig n a t u r e a n d a v e r i f i a b l e t h r e s h o l d s i g n a t u re s c h e m e . t h e t r u t h , s ta b i l 沁 a n d s e c u r i ty o f t h e s c h e m e w e r e p r o v e d . f u rt h e r m o r e , a d i r e c t e d t h r e s h o l d gr o u p s i g n a t u r e s c h e m e w i t h s p e c i fi c r e c e i v e r w as p r o p o s e d a n d t h e t r u t h , s t a b i l ity a n d s e c u r i t y w e r e p r o v e d . t h i s p a p e r v a l i d a t e d t h e t ru t h o f t h e im p r o v e d e c d s a b y i m p l e m e n t i n g t h e a l g o r i t h m . u s i n g t h e c h a r a c t e r i s t i c t h a t t h e a l g o r i t h m c a n a v o i d i n v e r s i o n in p ri m e fi e l d s s e c r e t w as s h a r e d a n d a n e w t h r e s h o l d g r o u p s i g n a t u r e s c h e m e a n d a d i r e c t e d t h r e s h o l d g r o u p s i g n a t u r e s c h e m e b as e d o n e l l i p t ic c u r v e w as p r o p o s e d . k e y w o r d s : e l l i p t i c c u r v e , d i g i t a l s i g n a t u r e , j a v a 2 , t h r e s h o l d g rou p s i g n a t u r e , d i r e c t e d t h r e s h o l d g r o u p s i g n a t u r 学位论文独创性声明 本人郑重声 明 i 、坚持 以 “ 求实、创新”的科学精神从事研究工作。 本论文是我个人在导师指导下进行的研究工作和取得的研 3. 的 。 4. 本论文中除引文外，所有实验、数据和有关材料均是真实 本论文中除引文和致谢的内容外，不包含其他人或其它机 构 己经发表或撰 写过 的研究成果 。 5 、其他同志对本研究所做的贡献均己在论文中作了声明并表 示 了谢 意 。 作者签名: k 5,11- 获 日期: 辱州f 8 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、 使用学位论文的规定， 学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版;有权将学位论文用于非赢利 目的的少量复制并允许论 文进入学校图书馆被查阅;有权将学位论文的内容编入有关数据库进 行检索;有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解 密 后适用 本规 定 。 作者签名: 日期: 殷 l j v o 茸,v r 2 ， 8 4 硕士学位论文基于椭圆曲 线的数字签名及其应用研究 第一章 课题的研究背景及意义 1 . 1数字签名的研究意义 目 前， 我国 信息与网络防 御能力极为 脆弱，形势严峻。 很多重要的 信息系统基 本上处于不设防状态。阻碍我国电 子政务、电 子商务广泛应用的 最大障碍就是安全 问题，不安全的协议会给电 子政务、电子商务带来致命的损失，研究适用于电子商 务运行机制的数字签名算法、身份识别系统是一项重要内容。 数字签名是当前网 络安全领域的 研究热点。 特别地， 在电子商务、电 子银行、 电 子政务等应用领域，数字签名是关键技术之一， 在社会生活的各个领域也有极其 广阔的应用前景。数字签名在实现身份认证、数据完整性、不可抵赖性等功能方面 都有重要应用。 数字签名的实现基础是加密技术， 其使用公钥加密算法和散列函 数。常用的 数 字签名算法有: r s a , d s s , e c d s a , e l g a m a 1 , s c h n o r r 等;还有一些用于特殊用 途的数字签名，如盲签名、群签名、失败一 终止 签名等。 在平常生活中， 使用手写签字和印章随处可见， 如签署合同、 办理证明等。 如 果在网络上实现签字和印章的电子化，其好处和优点是无疑的。 数字签名的目的 之 一， 就是在网络环境中 代替传统的 手工签字和印 章， 其可以 抵御的网 络攻击有:防 冒 充 ( 伪造) 、防篡改 ( 防止破坏信息的完整性) 、防重放、防抵赖和机密性 ( 保密 性) 。 现在， 数字签名技术的常见技术方式是使用一个智能卡， 甚至还附加采用指纹、 视网 膜扫描以 及语音识别测试等其他技术， 或者所有这些东西的合成技术以 提高 签 名和认证的准确性。 1 . 2信息安全的关键技术 密码学是网络信息安全的基础，公钥密码体制是密码学的重要组成部分，数字 签名的基础就是公钥密码体制。密码学是网络信息安全研究的重要领域。 在计算机网络深入普及的 信息时代，信息本身就是时间，就是财富。信息的传 硕士学位论文基于椭圆曲 线的数字签名及其应用研究 第一章 课题的研究背景及意义 1 . 1数字签名的研究意义 目 前， 我国 信息与网络防 御能力极为 脆弱，形势严峻。 很多重要的 信息系统基 本上处于不设防状态。阻碍我国电 子政务、电 子商务广泛应用的 最大障碍就是安全 问题，不安全的协议会给电 子政务、电子商务带来致命的损失，研究适用于电子商 务运行机制的数字签名算法、身份识别系统是一项重要内容。 数字签名是当前网 络安全领域的 研究热点。 特别地， 在电子商务、电 子银行、 电 子政务等应用领域，数字签名是关键技术之一， 在社会生活的各个领域也有极其 广阔的应用前景。数字签名在实现身份认证、数据完整性、不可抵赖性等功能方面 都有重要应用。 数字签名的实现基础是加密技术， 其使用公钥加密算法和散列函 数。常用的 数 字签名算法有: r s a , d s s , e c d s a , e l g a m a 1 , s c h n o r r 等;还有一些用于特殊用 途的数字签名，如盲签名、群签名、失败一 终止 签名等。 在平常生活中， 使用手写签字和印章随处可见， 如签署合同、 办理证明等。 如 果在网络上实现签字和印章的电子化，其好处和优点是无疑的。 数字签名的目的 之 一， 就是在网络环境中 代替传统的 手工签字和印 章， 其可以 抵御的网 络攻击有:防 冒 充 ( 伪造) 、防篡改 ( 防止破坏信息的完整性) 、防重放、防抵赖和机密性 ( 保密 性) 。 现在， 数字签名技术的常见技术方式是使用一个智能卡， 甚至还附加采用指纹、 视网 膜扫描以 及语音识别测试等其他技术， 或者所有这些东西的合成技术以 提高 签 名和认证的准确性。 1 . 2信息安全的关键技术 密码学是网络信息安全的基础，公钥密码体制是密码学的重要组成部分，数字 签名的基础就是公钥密码体制。密码学是网络信息安全研究的重要领域。 在计算机网络深入普及的 信息时代，信息本身就是时间，就是财富。信息的传 硕士学位论文基于椭圆曲线的数字签名及其应用研究 输通道是脆弱的公共信道.信息存储于 “ 不设防”的计算机系统中， 如何保护信息 的安全使之不被窃取及不至于被篡改或破坏，已 成为当 今普遍关注的重大问 题。密 码是有效而且可行的 办法。在计算机网 络的刺激下，近代密码学便在算法复杂性理 论的基础上建立起来了。 信 息 安 全 的 概 念 包 括 11 , 信息的保密性:保证信息不泄露给未经授权的人。 信息的 完整性:防止信息被未经授权的 篡改。 信息的可用性:保证信息和信息系统确实为授权者 所用，防止由 于计 算机病毒 或其它人为因素造成系统的拒绝服务，或者为非法者所用。 信息的可控性:对信息和信息系统实施安全监控管理，防止非法信息。 信息的不可否认性:保证信息行为人不能过后否认自己的行动。 利用密码变换保护信息安全是密码最原始、 最基本的功能; 然而，随着信息和 信息技术发展起来的现代密码学， 不仅用于解决信息的 保密性，也用于解决信息的 完整性， 可用性， 可控性和不可抵赖性。 因此， 密码是保护信息安全的最有效手段， 也是保护信息安全的关键技术。 1 . 3国内外相关技术的研究进展 1 9 7 6 年发表的“ n e w d ir e c t io n s in c ry p t o g r a p h y ”这篇划时 代的文章奠 定了公 钥 密码系 统的 基础3 2 3 。自 从公 钥密 码的 概念被提出以 来， 相继提出了 许多 公 钥密 码方 案， 如r s 人 、 背包体制、 m c e l i e c e . e tg a m a t 体 制等。 在 不断的 研究和实践中， 有 些方案被攻破了， 有些方案不太实用。 最初 1 0 年的公钥密码技术的研究和发展表明， 最安全实用两种类型的公钥密 码体制是 基于大整数分解困难问题的密码体制与基于 离散对数困难问 题的密码体制。 在2 0 0 4 年的信息安全国际 会议上。 曹珍富教授做的“ 密码理论中的若干问题” 的报告8 中， 介绍了能够代表当 前密码学发展的新方向。 其中 提到公钥密码在信息 安 全中担负 起密钥协商、数字签名、消息认证等重要角色，已 成为最核心的密码。 公钥密码主要用于数字签名和密钥分配。目 前数字签名的 研究内 容非常丰富， 包括普通签名和特殊签名.总结现今普 遍使用的 数字签名算法，都是基于以 下三个 数学难题的基础之上: ( 1 )整数的因子分解 ( i n t e r g e r f a c t o r i z t i o n )问 题， 如r s a算法; 硕士学位论文基于椭圆曲线的数字签名及其应用研究 输通道是脆弱的公共信道.信息存储于 “ 不设防”的计算机系统中， 如何保护信息 的安全使之不被窃取及不至于被篡改或破坏，已 成为当 今普遍关注的重大问 题。密 码是有效而且可行的 办法。在计算机网 络的刺激下，近代密码学便在算法复杂性理 论的基础上建立起来了。 信 息 安 全 的 概 念 包 括 11 , 信息的保密性:保证信息不泄露给未经授权的人。 信息的 完整性:防止信息被未经授权的 篡改。 信息的可用性:保证信息和信息系统确实为授权者 所用，防止由 于计 算机病毒 或其它人为因素造成系统的拒绝服务，或者为非法者所用。 信息的可控性:对信息和信息系统实施安全监控管理，防止非法信息。 信息的不可否认性:保证信息行为人不能过后否认自己的行动。 利用密码变换保护信息安全是密码最原始、 最基本的功能; 然而，随着信息和 信息技术发展起来的现代密码学， 不仅用于解决信息的 保密性，也用于解决信息的 完整性， 可用性， 可控性和不可抵赖性。 因此， 密码是保护信息安全的最有效手段， 也是保护信息安全的关键技术。 1 . 3国内外相关技术的研究进展 1 9 7 6 年发表的“ n e w d ir e c t io n s in c ry p t o g r a p h y ”这篇划时 代的文章奠 定了公 钥 密码系 统的 基础3 2 3 。自 从公 钥密 码的 概念被提出以 来， 相继提出了 许多 公 钥密 码方 案， 如r s 人 、 背包体制、 m c e l i e c e . e tg a m a t 体 制等。 在 不断的 研究和实践中， 有 些方案被攻破了， 有些方案不太实用。 最初 1 0 年的公钥密码技术的研究和发展表明， 最安全实用两种类型的公钥密 码体制是 基于大整数分解困难问题的密码体制与基于 离散对数困难问 题的密码体制。 在2 0 0 4 年的信息安全国际 会议上。 曹珍富教授做的“ 密码理论中的若干问题” 的报告8 中， 介绍了能够代表当 前密码学发展的新方向。 其中 提到公钥密码在信息 安 全中担负 起密钥协商、数字签名、消息认证等重要角色，已 成为最核心的密码。 公钥密码主要用于数字签名和密钥分配。目 前数字签名的 研究内 容非常丰富， 包括普通签名和特殊签名.总结现今普 遍使用的 数字签名算法，都是基于以 下三个 数学难题的基础之上: ( 1 )整数的因子分解 ( i n t e r g e r f a c t o r i z t i o n )问 题， 如r s a算法; 硕士学位论文基于椭圆曲线的数字签名及其应用研究 ( 2 ) 离 散 对 数( d is c r e t e l o g a r it h i m ) 问 题， 如e lg a m a 1 . d s a . s c h n o r r 等 算 法: ( 3 ) 椭圆曲 线 ( e ll ip t i c c u r v e ) 离散 对数问 题， 如e c d s a算法。 在 公 钥 密 码体 制中， 影响比 较大的 之 一 是 椭圆曲 线 密 码体 制e c c ( e ll ip t ic c u r v e c ry p t o s y s t e m s ) 。由 于分解大整数的能 力日 益增强， 给r s a的 安全带 来了 威胁，目 前的 研究表明，想要保证2 0 年的安全就要选择1 2 8 0 b i t 的 模长， 这给实现带来了 难 度。 而基于离散对数问题的公钥密码在目 前技术下只需要5 1 2 b i t 的 模长就可以 保证 安全， 特别是椭圆曲 线上的离散对数计算更困难，目 前技术下只需要1 6 0 b i t 模长就 可以， 适用于智能卡实现，因而受到国内 外学者的 广泛关注。国际权威密码机构己 经确认， 椭圆曲 线密码体制将逐步取代r s a密码体制成为公钥密码体制的 主体， 它 的 发 展 前 景 十 分 广阔 1叱 椭圆曲线密码体制的一个迷人之处在于， 基于它的离散对数问题还没有亚指数 时间的攻击， 并且由 于椭圆曲 线具有更小的密钥长度、更小的带宽、 而且它的实现 速 度更快， 使得它更适合于 功率和 集成电 路空间 受限的 应用场合19 ) 。 在过去的 十多 年 里， 椭圆曲 线离 散 对 数问 题e c d l p ( e l li p t ic c u r v e d i s c r e t e l o g a r it h m p r o b le m ) 受到全世界前沿科学家的极大关注。目前的 研究热点在于如何加快椭圆曲 线上点的 运算， 特别是标量乘运算的 速度， 椭圆曲 线签名算法运用于特殊签名的方案等。 2 0 0 2 年， 科技部高技术研究发展项目中， 由 清华大学微电子研究所开展了 关于 椭圆曲 线告诉密码芯片的实现技术和 e c c - i p核关键技术的 研究和实现. 完成了 基 于 特征2 的椭圆曲 线密码芯片的全部设计，以 及对给予素数域曲 线椭圆曲 线密码的 芯片集成技术的深入研究， 2 0 0 4年底，北京天一集成研制的“ wl a n专用高速椭圆曲 线密码算法芯片及 1 p核 ( e c c ) 项目 获得信息产业部和财政部的立项。该项目 针对椭圆曲 线进行研 究，开发支持 1 9 2 - 2 5 6 6 i t 模p域上，任意可变曲 线的e c c公钥密码算法芯片系列 产品。 这些都表明， 我国 在椭圆曲 线密码体制上的 研究和实现已 经轰轰烈烈的开展 起来。 目 前国外对椭圆曲线密码研究最成功的是c e rt i c o m公司。 1 9 9 5 年开始， 以s c o t i v a n s t o n 。 为首的加拿大 w a t e r l o o大学的几位密码学家成立了c e rt i c o m研究小组， c e rt i c o m以 推动椭圆曲线密码在商业领域内的 广泛应用为主要目 标，经过十多年的 研究， c e rt i c o m开发出了 在商业领域内高效、 安全、 低成本的实现e c c技术的方法。 毫无疑问，数字签名是保证数据完整性，实现网络认证以及开展现代电 子商务 硕士学位论文 基于椭圆曲 线的数字签名及其应用研究 的重要工具，随着网 络应用的蓬勃发展，普通的数字签名技术已 经不能满足许多应 用的 要求。 近十多年以 来。 众多研究者提出了 许多特殊的 数字签名，如群签名、门 限 群签名、 不 可否认群签名 等等。 群签名方 案首次由c h a u m和h e y s t 提出， 在 群签 名方案中引入秘密分享， 就形成门 限群签名方案。 但由 于本身采用的密 码体制及抗 攻击性、强壮性、稳定性等方面的原因，目 前还没有完善的门限签名方案。这也使 得对于该特殊签名的研究成为热点。 数字签名必然要涉及到法律问题。1 9 9 1 年，美国n i s t公布了其数字签名标准 d s s ( d ig i t a l s ig n a t u r e s t a n d a r d ) ， 并于1 9 9 4 年正式 采用为美国 联邦信息处理标准。 随后其他一些国家也颁布了自己的 数字签名标准，如俄罗 斯 1 9 9 4年颁布的g o s t 8 3 4 . 1 0 一 9 4 标准等。我国于2 0 0 4 年8 月， 通过了 中 华人民共和国电 子签名法 ， 并于2 0 0 5 年4 月i 日 起执行i a 1 1 . 4本课题主要研究内容 目 前，r s a数字签名体制仍是国际上一些标准化组织如i s o , i t u , s wi f t等 的 标准， 然而 近年来的 研究 表明， 5 1 2 b it 模长的r s a已 经被攻破19 1 ， 而椭圆曲 线上 的离散对数的计算要比有限域上的离散对数计算更困难。对于同样规模参数，椭圆 曲 线密码每一比 特密钥的强度要大的多: 要得到同 样强度的密码，椭圆曲 线系统的 参数规模要小的多。小的参数无论在实现上还是在应用上都具有较大的优越性。 由 于目 前的 椭圆曲 线签名算法， 都不可避免的需要进行有限域上的求逆运算， 这种运算的速度比 较慢， 一次求逆运算大约相当于8 0 次乘法运算， 很大程度上影响 了整个签名的速度。另一方面，求逆运算的 存在，使得秘密分享很难得到实现。因 此， 文献0 1提出了 一种椭圆曲 线签名 算法， 避免了 有限 域中的 求逆运算，比 文献(3 3 1 中 建议的椭圆曲 线签名算法简单。在本文中，详细介绍了该算法的实现过程。 本文首先探讨了 对这种椭圆曲 线数字签名算法的实现，介绍了用 a v a 2 具体实 现该算法的流程，从而证明了 算法的可行性和安全性。 在此基础上， 本文提出了基 于这种椭圆曲 线数字签名算法的 群签名方案和有向 群签名方案，并证实了 这些方法 的正确性、稳定性和安全性。 硕士学位论文 基于椭圆曲 线的数字签名及其应用研究 的重要工具，随着网 络应用的蓬勃发展，普通的数字签名技术已 经不能满足许多应 用的 要求。 近十多年以 来。 众多研究者提出了 许多特殊的 数字签名，如群签名、门 限 群签名、 不 可否认群签名 等等。 群签名方 案首次由c h a u m和h e y s t 提出， 在 群签 名方案中引入秘密分享， 就形成门 限群签名方案。 但由 于本身采用的密 码体制及抗 攻击性、强壮性、稳定性等方面的原因，目 前还没有完善的门限签名方案。这也使 得对于该特殊签名的研究成为热点。 数字签名必然要涉及到法律问题。1 9 9 1 年，美国n i s t公布了其数字签名标准 d s s ( d ig i t a l s ig n a t u r e s t a n d a r d ) ， 并于1 9 9 4 年正式 采用为美国 联邦信息处理标准。 随后其他一些国家也颁布了自己的 数字签名标准，如俄罗 斯 1 9 9 4年颁布的g o s t 8 3 4 . 1 0 一 9 4 标准等。我国于2 0 0 4 年8 月， 通过了 中 华人民共和国电 子签名法 ， 并于2 0 0 5 年4 月i 日 起执行i a 1 1 . 4本课题主要研究内容 目 前，r s a数字签名体制仍是国际上一些标准化组织如i s o , i t u , s wi f t等 的 标准， 然而 近年来的 研究 表明， 5 1 2 b it 模长的r s a已 经被攻破19 1 ， 而椭圆曲 线上 的离散对数的计算要比有限域上的离散对数计算更困难。对于同样规模参数，椭圆 曲 线密码每一比 特密钥的强度要大的多: 要得到同 样强度的密码，椭圆曲 线系统的 参数规模要小的多。小的参数无论在实现上还是在应用上都具有较大的优越性。 由 于目 前的 椭圆曲 线签名算法， 都不可避免的需要进行有限域上的求逆运算， 这种运算的速度比 较慢， 一次求逆运算大约相当于8 0 次乘法运算， 很大程度上影响 了整个签名的速度。另一方面，求逆运算的 存在，使得秘密分享很难得到实现。因 此， 文献0 1提出了 一种椭圆曲 线签名 算法， 避免了 有限 域中的 求逆运算，比 文献(3 3 1 中 建议的椭圆曲 线签名算法简单。在本文中，详细介绍了该算法的实现过程。 本文首先探讨了 对这种椭圆曲 线数字签名算法的实现，介绍了用 a v a 2 具体实 现该算法的流程，从而证明了 算法的可行性和安全性。 在此基础上， 本文提出了基 于这种椭圆曲 线数字签名算法的 群签名方案和有向 群签名方案，并证实了 这些方法 的正确性、稳定性和安全性。 硕士学位论文 基于椭圆曲线的数字签名及其应用研究 第二章密码体制 2 . 1 2 . 1 . 1 密码学基础 基本概念 密码学包括两个方面:密码编码学和密码分析学。密码编码学就是研究对数据 进行变换的原理、手段和方法的技术和科学， 其目 的是隐藏数据的真实内 容，以 防 止数据被无察觉的篡改和非法使用。密码分析学是为了 取得秘密的消息，而对密码 系统及其流动的数据进行分析，是对密 码原理、手段和方法进行分析、 攻击的技术 和科学。密码编码学和密码分析学相互矛盾， 又相互促进。 密码学的理论基础是数学， 例如代数、概率论、 信息论、 数论、组合论等，随 着密码学的 发展， 还涉及到电子学、 计算机科学、 语言学等， 当前量子密码的研究， 又涉及量子力学理论。 密码学的基本思想就是隐藏、伪装信息，使未经授权者不能得到消息的真正含 义， 伪装信息的方法就是进行一组可逆的数字变换。 伪装 ( 变换)之前的信息是原 始信息， 称为明文， 伪装之后的 信息， 看起来是一串 无意义的乱码， 称为密文。 把 明 文伪装成密文的过程称为加密，该过程使用的数学变换就是加密算法。 把密文还 原成明文的过程称为解密，该过程使用的数学变换，通常是加密时数学变换的逆变 换。 就是解密算法。加密与 解密通常需要参数控制， 我们把该参数称为密钥， 有时 也称为密码。 加密时使用的叫加密密码 ( 加密密钥) ， 解密时使用的叫解密密码 ( 解 密密钥) 。 2 . 1 . 2密码系统原理 一个密 码系统是由明 文空间、密文空间、密钥空间、 加密算法与 解密算法五个 部分组成。 明文、 密文、 密钥空间分别表示全体明 文、 全体密文、 全体密钥的集合， 加密算法和解密算法是一些公式、 法则 或程序， 规定了明 文与密文之间的 数学变换 规 则 12 ) 下 面用字母分别表示， 密钥k = ( k , k d ) ， k表示加 密密钥， k , -4t . 0 v密 9 硕士学位论文 基于椭圆曲线的数字签名及其应用研究 第二章密码体制 2 . 1 2 . 1 . 1 密码学基础 基本概念 密码学包括两个方面:密码编码学和密码分析学。密码编码学就是研究对数据 进行变换的原理、手段和方法的技术和科学， 其目 的是隐藏数据的真实内 容，以 防 止数据被无察觉的篡改和非法使用。密码分析学是为了 取得秘密的消息，而对密码 系统及其流动的数据进行分析，是对密 码原理、手段和方法进行分析、 攻击的技术 和科学。密码编码学和密码分析学相互矛盾， 又相互促进。 密码学的理论基础是数学， 例如代数、概率论、 信息论、 数论、组合论等，随 着密码学的 发展， 还涉及到电子学、 计算机科学、 语言学等， 当前量子密码的研究， 又涉及量子力学理论。 密码学的基本思想就是隐藏、伪装信息，使未经授权者不能得到消息的真正含 义， 伪装信息的方法就是进行一组可逆的数字变换。 伪装 ( 变换)之前的信息是原 始信息， 称为明文， 伪装之后的 信息， 看起来是一串 无意义的乱码， 称为密文。 把 明 文伪装成密文的过程称为加密，该过程使用的数学变换就是加密算法。 把密文还 原成明文的过程称为解密，该过程使用的数学变换，通常是加密时数学变换的逆变 换。 就是解密算法。加密与 解密通常需要参数控制， 我们把该参数称为密钥， 有时 也称为密码。 加密时使用的叫加密密码 ( 加密密钥) ， 解密时使用的叫解密密码 ( 解 密密钥) 。 2 . 1 . 2密码系统原理 一个密 码系统是由明 文空间、密文空间、密钥空间、 加密算法与 解密算法五个 部分组成。 明文、 密文、 密钥空间分别表示全体明 文、 全体密文、 全体密钥的集合， 加密算法和解密算法是一些公式、 法则 或程序， 规定了明 文与密文之间的 数学变换 规 则 12 ) 下 面用字母分别表示， 密钥k = ( k , k d ) ， k表示加 密密钥， k , -4t . 0 v密 9 硕士学位论文基于椭圆曲线的数字签名及其应用研究 设明文m,密文c ，加密算法e ,解密算法及 把明文加密为密文: c= e( m , k ) . 把密文解密为明文: m= d( c , k d ) = d( e ( m, k) , k d ) . 这个过程可以由图2 . 1 来表示: 图2 . 1 密码系统加密解密示意图 2 . 2密码体制分类 密码学随着历史的发展， 也由原来的初级阶段发展成今天较高级的 形式。 最初 的 可以 称为手工阶段，以 第二次世界大战期间涌现的一批密码机为代表的时期，可 以称为机械式阶段.随着电 子技术与计算机技术的发展，密码学进入了今天较高级 的阶段。用不同的分类标准， 有不同的密码体制分类。根据密钥的特点， 密码体制 分为对称密码体制和非对称密码体制。为了 便于讲述。我们把密码不严格的划分为 古典密码、分组密码、公钥密码和其他密码。 还有一些新的 密码体制正在被研究， 如基于辫群的密码体制、n t r u 、量子密码体制等。 2 . 2 . 1古典密码 古典密码是相对于现代密码技术而言的， 它没有一个严格的定义。一般采用换 位， 代替等方式和机械式轮转密码机技术。 从现代密码学观点来看，古典密码很不 安全，极易被破解， 但是它在过去是发挥了巨 大作用的。典型的古典密码有恺撒密 码、 v i g e n e r e 密码、 p l a y f a i r 密 码等等。 硕士学位论文基于椭圆曲线的数字签名及其应用研究 设明文m,密文c ，加密算法e ,解密算法及 把明文加密为密文: c= e( m , k ) . 把密文解密为明文: m= d( c , k d ) = d( e ( m, k) , k d ) . 这个过程可以由图2 . 1 来表示: 图2 . 1 密码系统加密解密示意图 2 . 2密码体制分类 密码学随着历史的发展， 也由原来的初级阶段发展成今天较高级的 形式。 最初 的 可以 称为手工阶段，以 第二次世界大战期间涌现的一批密码机为代表的时期，可 以称为机械式阶段.随着电 子技术与计算机技术的发展，密码学进入了今天较高级 的阶段。用不同的分类标准， 有不同的密码体制分类。根据密钥的特点， 密码体制 分为对称密码体制和非对称密码体制。为了 便于讲述。我们把密码不严格的划分为 古典密码、分组密码、公钥密码和其他密码。 还有一些新的 密码体制正在被研究， 如基于辫群的密码体制、n t r u 、量子密码体制等。 2 . 2 . 1古典密码 古典密码是相对于现代密码技术而言的， 它没有一个严格的定义。一般采用换 位， 代替等方式和机械式轮转密码机技术。 从现代密码学观点来看，古典密码很不 安全，极易被破解， 但是它在过去是发挥了巨 大作用的。典型的古典密码有恺撒密 码、 v i g e n e r e 密码、 p l a y f a i r 密 码等等。 硕士学位论文基子椭圆曲线的数字签名及其应用研究 2 . 2 . 2分组密码 一次对若干位为一组的明文进行操作与 运算的 密码算法， 就是分组密码， 一般 提及的分组密码都使用相同的加密与解密密钥。古典密码和分组密码都属于单密钥 体制， 单密钥体制也称为对称密码体制，或传统密码体制， 其加密密钥和解密密钥 是相同的。 d e s ( d a t a e n c ry p t i o n s t a n d a r d ) 即数据加密标准， 是分组密码的 代表， 它由i b m 公司 提供，于 1 9 7 7年被美国国家标准局 ( n i s t ) 颁布，作为商业与非国防性 政府 部门 使用的 数据加密标准。 它是密码学发展史上的重大事件。 d e s 综合运用了 置换、 代替、 代数等多种密码技巧， 适于软硬件实现。自 从公布以来，它 成为国际上商用 保密通信和计算机通信的最常用的加密算法，并超期服役到2 0 0 0 年。 进入2 0 世纪9 0 年代以 后， 相继有了攻击d e s 的差 分分析法和线性逼迫法以及 一些专门的电子设备。 对d e s 构成了 实际的威胁。 d e s 确实辉煌过， 它的弱点在于 专家们一开始就指出，即密钥太短，号称6 4 位，实际上只有5 6 位。新的加密标准 取代 d e s的时代己 经到来。2 0 0 1 年 1 0月， n i s t公布了a e s的最筛选结果 r ij n d a e l 算法。 分组密码算法非常丰富， 如c a s t , r c 5 , 3 d e s , s a f e r , i d e a等。 n i s t 征 集的 先 进加 密 标 准a e s ( a d v a n c e d e n c ry p ti o n s t a n d a r d ) 活 动， 也 大 大推 动了 分组 密码算法的研究。 2 . 2 . 3公钥密码 公钥密码概念是由w h i t f i e l d d i ff i 。 和m a r t i n h e l im a n 于1 9 7 6 年提出的 3 2 1 ， 它是 密码学历史上的一个重大成就。有关公钥密码体制的具体内 容将在下一节中介绍。 2 . 3公钥密码体制 2 . 3 . 1公钥密码体制简介 公钥密码与以 前所有的密码方法都大相径庭: 一是以前的密码算法都基于代换 与置换操作， 而公钥密码体制使用数学函 数进行 变换:二是公钥密码体制使用非对 硕士学位论文基子椭圆曲线的数字签名及其应用研究 2 . 2 . 2分组密码 一次对若干位为一组的明文进行操作与 运算的 密码算法， 就是分组密码， 一般 提及的分组密码都使用相同的加密与解密密钥。古典密码和分组密码都属于单密钥 体制， 单密钥体制也称为对称密码体制，或传统密码体制， 其加密密钥和解密密钥 是相同的。 d e s ( d a t a e n c ry p t i o n s t a n d a r d ) 即数据加密标准， 是分组密码的 代表， 它由i b m 公司 提供，于 1 9 7 7年被美国国家标准局 ( n i s t ) 颁布，作为商业与非国防性 政府 部门 使用的 数据加密标准。 它是密码学发展史上的重大事件。 d e s 综合运用了 置换、 代替、 代数等多种密码技巧， 适于软硬件实现。自 从公布以来，它 成为国际上商用 保密通信和计算机通信的最常用的加密算法，并超期服役到2 0 0 0 年。 进入2 0 世纪9 0 年代以 后， 相继有了攻击d e s 的差 分分析法和线性逼迫法以及 一些专门的电子设备。 对d e s 构成了 实际的威胁。 d e s 确实辉煌过， 它的弱点在于 专家们一开始就指出，即密钥太短，号称6 4 位，实际上只有5 6 位。新的加密标准 取代 d e s的时代己 经到来。2 0 0 1 年 1 0月， n i s t公布了a e s的最筛选结果 r ij n d a e l 算法。 分组密码算法非常丰富， 如c a s t , r c 5 , 3 d e s , s a f e r , i d e a等。 n i s t 征 集的 先 进加 密 标 准a e s ( a d v a n c e d e n c ry p ti o n s t a n d a r d ) 活 动， 也 大 大推 动了 分组 密码算法的研究。 2 . 2 . 3公钥密码 公钥密码概念是由w h i t f i e l d d i ff i 。 和m a r t i n h e l im a n 于1 9 7 6 年提出的 3 2 1 ， 它是 密码学历史上的一个重大成就。有关公钥密码体制的具体内 容将在下一节中介绍。 2 . 3公钥密码体制 2 . 3 . 1公钥密码体制简介 公钥密码与以 前所有的密码方法都大相径庭: 一是以前的密码算法都基于代换 与置换操作， 而公钥密码体制使用数学函 数进行 变换:二是公钥密码体制使用非对 硕士学位论文基于椭圆曲线的数字签名及其应用研究 称的 方法， 使用两个密钥 加密密钥与解密密钥) ， 而传统密码算法仅仅使用一个密 钥。故也 称双密钥体制， 或非 对称密码体制。因此公钥密码体制被认为是 密码学上 的一块里程碑。 自 从公钥密码体制的概念被提出来以后，相继提出了许多公钥密码方案，如 r s a , 背 包 体 制、 m c e l i e c e , e ig a m a l 体 制 等 15 1 。 关 于 最 初1 0 年 的 公 钥 密 码 技 术的 研究和发展，目 前只有两种类型的公钥系统是安全实用的，即基于大整数分解困难 问 题的密码体制与基于离散对数困 难问 题的密码体制。 基于大整数分解问 题的密码体制主要有r s a , r a b i n - w i l l i a m s 体制、 l u c体制 及其推广， 二次剩余体制等。 在2 .3 . 2 节中 我们将介绍r s a体制。 基于离散对数困难问 题的密码体制主要包括基于有限 域的乘法群上的离散对数 问 题的 d s a或 e i g a m a l 密码体制， 基于 椭圆曲 线离散 对数的 椭圆曲 线密码体制 ( e c c) a 公钥密码体制的思想为:每个用户使用一对密钥， 加密密钥k