（计算机软件与理论专业论文）基于ecc代理数字签名技术研究与设计.pdf

摘要 代理签名体制在电子商务中的应用很广泛，目前的代理签名体制安全性 主要是基于求解大数因子分解问题的困难性或求解离散对数问题的困难性。 随着大整数分解和并行处理技术的进展，公钥密码体制使用的密钥长度 随着增长，这将使其运算速度变慢，密码系统更加复杂。同时，目前也存在 许多针对大整数分解密码体制和离散对数密码体制的攻击算法。 本文简要介绍了代理签名体制概念与性质，并对其中比较典型的两种代 理签名体制进行分析，指出其在密钥长度，处理速度，安全性能等方面存在 着缺点。 本文还对椭圆曲线密码体制和r s a 、d s a 及基于离散对数问题的密码体 制进行分析比较，明确了椭圆曲线密码体制在安全性能、密钥长度、处理速 度、系统参数、带宽要求等方面具有独特优势。本文正是利用椭圆曲线密码 算法的这些优势，构造出椭圆曲线代理签名体制，并对该体制进行分析论证。 该体制的安全性基于椭圆曲线离散对数问题的难解性，它与前面两种代理签 名体制相比，具有安全性高、密钥长度小、处理速度快、系统参数小、带宽 占用低等优点。 关键词：数字签名；代理签名；e c c ；离散对数问题 a b s t r a c t p r o x ys i g n a t u r es y s t e m sh a v eg r e a ta p p l i c a t i o n si ne b u s i n e s sw h o s es e c u r i t yi s b a s e do nt h ed i f f i c u l t yo fi n t e g e rf a c t o r i n go rt h ed i f f i c u l t yo fs o l v i n gt h ec o m m o n d i s c r e t el o g a r i t h mp r o b l e m a st h ed e v e l o p m e n to fi n t e g e rf a c t o r i n ga n dt h ep a r a l l e l c o m p u t i n gt e c h n o l o g y , t h ep u b l i ck e yc r y p t o g r a p h i e su s e dt o d a yh a v et oe n l a r g e k e y 。s i z ew h i c hs l o w st h e i rs p e e da n di n c r e a s e st h e i rc o m p l e x i t y a l s o ，t h e r ea r em a n y a t t a c k i n gm e t h o d st os o l v et h eg e n eo fab i gi n t e g e ra n dt h ec o n n o i ld i s c r e t e l o g a r i t h mp r o b l e m t h i st h e s i si n t r o d u c e st h ec o n c e p ta n dt h ep r o p e r t yo fa p r o x ys i g n a t u r es y s t e m ， a n dw ea n a l y z et w oc o m p a r a t i v e l yr e p r e s e n t a t i v es y s t e m sa n df i n dt h a tt h e r ee x i s t s o m ed i s a d v a n t a g e si nt h el e n g t ho ft h e i rk e y s ，t h es p e e do ft h e i rd i s p o s a la n dt h e i r s e c u r i t y t h i st h e s i sa l s oc o m p a r e sr s a , d s aa n dt h ec r y p t o s y s t e mb a s e do nd i s c r e t e l o g a r i t h mp r o b l e mw i t he c c ( e l l i p t i cc u r v ec r y p t o s y s t e m ) ，f r o mt h ec o m p a r i s o nw e c a nd r a wac o n c l u s i o nt h a te c ch a sap a r t i c u l a ra d v a n t a g ei nt h e s e c u r i t y ，t h el e n g t h o fk e y , t h es p e e do fd i s p o s a l ，t h es y s t e mp a r a m e t e ra n dt h ed e m a n do fb a n d w i d t h t h e t h e s i sm a k e su s eo ft h o s ea d v a n t a g e sa n dc o n s t r u c t st h ep r o x ys i g n a t u r es y s t e mb a s e d o ne c c w ea l s oa n a l y z ea n dd e m o n s t r a t et h es y s t e mw h o s es e c u r i t yi sb a s e do n e c d l p ( e l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ) c o m p a r i n gw i t ht h et w of o r m e r s y s t e m s ，o u rs y s t e mh a st h em e r i t so fi m p r o v e ds e c u r i t y , m u c hl e s sk e y l e n g t h ，f a s t e r s p e e do fd i s p o s a l ，m u c hl e s ss y s t e mp a r a m e t e ra n dm u c hl e s sd e m a n do fb a n d w i d t h k e y w o r d s ：d i g i t a ls i g n a t u r e ；p r o x ys i g n a t u r e ；e c c ；d i s c r e t el o g a r i t h mp r o b l e m 2 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果 对本文的研究曾做出重要贡献的个人和集体，均已在文中以明确 方式标明本人完全意识到本声明的法律责任由本人承担。 论文作者签名：糟 日 期： 论文作者签名：牵跫啦 日 期： 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权贵州大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：薏蟓导师签名：币睥日期：业到幽 第1 章绪论 1 1 研究问题的背景与意义 计算机网络的产生把我们带进一个信息化社会，给我们的社会生活带来了很 多方便，与此同时，大量传输和存储的信息的安全保密和防伪问题日益突出，已 严重地威胁到人们正常的生活，甚至威胁到国家安全。 1 1 1 信息安全的重要性 网络安全的实质是信息安全，信息安全的核心技术之是密码技术。 由于计算机网络技术的迅速发展，尤其是i n t e r n e t 的发展和广泛普及，如电 子商务、电子政务、网上银行、电子证券和各类订票系统等等，这些应用己完全 渗透到我们的同常生活之中，毫无疑问为生产力的发展起到了极大的推动作用。 在信息技术的应用过程中，信息是最为宝贵的资源，因特网为信息的传播和获取 提供了极大的便利，它可以使我们不受时间和空间的限制，和世界上任何个角 落的个人或组织进行信息交流。 在网络给我们带来巨大的经济利益和便利的同时，遍布全球的黑客，利用网 络和系统漏洞，肆意攻击各种业务应用系统和网站，造成巨大的经济损失，搅得 全球不安。机密信息在网络上被泄露、篡改和假冒，计算机病毒和垃圾邮件肆意 传播，不良信息传播给青少年的成长带柬负面影响，计算机犯罪呈上升趋势。网 络信息安全问题不仅仅是一个技术问题，而且严重威胁到我国政治、军事、经济、 文化等各方面的安全，还将使国家处于信息战和经济会融风险的威胁之中，网络 信息安全已成为亟待解决的影响国家全局和长远利益的关键问题之一。 1 1 2 密码理论在信息安全中的重要作用 信息安全是一门涉及计算机技术、网络技术、信息论、密码学、应用数学、 通信技术、法律和管理技术等众多学科交叉和融合的综合性学科。 密码学( c r y p t o l o g y ) 是信息安全的基础之一。它包括两个分支：密码编码学 ( c r y p t o g r a p h y ) 矛t l 密码分析学( c r y p t a n a l y s i s ) 。密码编码学是对信息进行编码实现 信息隐藏的一门学科，主要研究实现信息保密和认证的方法与技术。密码分析学 是研究如何破译密码的- - f - 学科，主要目的是研究密文的破译和消息的伪造。 在传统密码中，用于加密的密钥和用于解密的密钥是相同的，因此通常使用 的加密算法比较简单、高效，密钥简短，安全性高。但是，传送和保管密钥是一 个严峻的问题。 ， 1 9 7 6 年，d i f f i e 发表了著名的论文密码学的新方向，提出了公钥密码体 制的新思想，证明了在发方和收方之间不需要传递密钥的保密通信是可能的，它 使密码学发生了一场变革，具有与传统密码不可取代的优势。 为了适应计算机通信和电子商务迅速发展的需要，密码学的研究领域逐步从 消息加密扩散到数字签名、消息认证、身份识别、防不可否认协议等新的课题。 同时密码学不在局限于军事、政治和外交，而扩大到商务、金融和社会各个领域， 特别是全球范围内的互联网的出现和发展，为人们提供了快速、高效和廉价的通 信，大量敏感信息常常要通过互联网进行交换。由于互联网的开放性，任何人都 可以接入互联网，使得有些人就有可能采用各种非法手段窃取、假冒、欺骗、篡 改和破坏各种重要信息，甚至进行计算机犯罪。网络信息安全问题成为当前比较 突出又急待解决的问题。 事实上，现在网络上应用的保护信息安全的技术，如数据加密技术、数字签 名技术、消息认证与身份识别技术、防火墙技术以及反病毒技术等都是基于密码 学来设计的，可以说密码学是信息安全技术的基础。由此可见，现代密码学的应 用非常广泛。在任何企业、单位和个人都可以应用密码技术来保护自己的信息。 1 1 3 数字签名技术在网络通信中的重要作用 在网络环境中，需要存储、传输大量信息。信息的接收方可以伪造一份报文， 并声称是由发送方发送过来的，从而获得非法利益。因此，需要新的信息安全技 术来保证传输信息的真实性、解决通信双方的争端，这种技术就是数字签名技术。 当通信双方发生了下列情况时，数字签名技术能够解决引发的争端。 ( 1 ) 否认发送方不承认自己发送过某报文。 ( 2 ) 伪造接收方自己伪造一份报文，并声称它来自发送方。 ( 3 ) 冒充网络上的某个用户冒充另一个用户接收或发送报文。 ( 4 ) 篡改接收方对收到的信息进行篡改。 所谓数字签名就是由信息的发送者通过一个单向函数对要传送的报文进行 处理产生别人无法伪造的一段数字串。这个数字串用以认证报文的来源并核实报 文是否发生了变化。一般情况下，发送者用自己的私有密钥加密数据传给接收者， 接收者用发送者的公钥解开数据后，就可确定消息来源，同时也是对发送者发送 的信息的真实性的一个证明，发送者不能抵赖。 在传统的商业系统中，书面文件的亲笔签名或印章是用来规定契约性的责任 的。签名或印章起到认证、核准、生效的作用。同样地，在电子商务活动中，传 送的文件是通过数字签名来证明当事人身份与数据真实性的。数据加密是保护数 据的最基本方法，但也只能防止第三者获得真实数据，它不能保证通信双方的相 互欺骗。数字签名则可以解决否认、伪造、篡改及冒充等问题。使用数字签名技 术使得：发送者事后不能否认发送的报文签名，接收者能够核实发送者发送的报 文签名，接收者不能伪造发送者的报文签名，接收者不能对发送者的报文进行篡 改，网络中的某一用户不能冒充另一用户。 1 1 4 代理签名技术的发展应用 在现实世界里，人们经常将自己的某些权利委托给可靠的代理人，让代理人 代表本人去行使某些权利，在这些可以委托的权利中包括人们的签名权。委托签 名权的传统方法是使用印章，因为印章可以在人们之间灵活的传递。数字签名是 传统的“手写签名”的电子对应物。现实中，我们经常遇到下列问题，如行政官 员出差而暂时无法对各种文件进行签名；总经理希望部门经理就其部门的问题代 表他进行签名；繁忙的高校校长希望办公室主任为众多的合格毕业生代替他签名 等等。这些情况使用传统的“手写签名”解决只需把印章交给代理人即可，但是 普通的数字签名则很难使用简单的传递密钥来解决上述问题，因为印章可以收回 而签名密钥一旦泄露将不可收回。这就需要设计一种新的数字签名方案，这种新 的数字签名方案就是我们要研究的代理签名技术。 1 2 代理签名技术的研究现状 1 9 9 6 年，m a m b o ，u s u d a 和o k a m o t o 提出了代理签名的概念，给出了解决 这个问题的一种方法。代理签名作为一种特殊的签名机制，由于其在众多的领域 都有重要的应用，因而受到人们的广泛研究。迄今为止，人们已经提出了多种代 理签名方案，这些代理签名方案安全性都是基于大整数因子分解的困难性或基于 离散对数问题的难解性。借助不断提高的计算机技术，人们经过不懈的努力，目 f i i 对这两类数学问题的求解能力较过去有了很大的提高。这迫使r s a 体制中使 用的模数和基于有限域上离散对数问题的公钥密码体制中有限域的大小越来越 大。对这两类密码体制，过去5 1 2 比特大小的密钥已足够安全，但现在就不能保 证它的安全性。为了保证足够的安全性，目前一般不得不使用1 0 2 4 比特或2 0 4 8 比特大小的密钥。如此一来，安全性基于前二者的代理数字签名体制就必须进_ 步增长密钥长度，这将使安全性基于这两种数学问题的代理签名体制的运算速度 。 更慢，系统也更加复杂。 椭圆曲线密码体制，即基于椭圆曲线离散对数问题的各种公钥密码体制，最 早于1 9 8 5 年由k o b l i t z 和m l i i e r 分别独立地提出，它是利用有限域上的椭圆曲线 有限循环群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码 体制。 在椭圆曲线密码体制中，1 6 0 比特长的密钥所具有的安全性和前两类体制中 1 0 2 4 比特长的密钥所具有的安全性相皇2 1 0 比特与2 0 4 8 比特相当等。我们在 后面的章节中，可以看到椭圆曲线密码体制的诸多优点。 基于目前的现状，r s a 的安全性己不能满足人们的需要，相比较而言椭圆 曲线的码体制的安全性会更高一些。而目自矿的代理签名方案大都是基于r s a 体 制的，也有基于d s a 密码体制的，它们的安全性不能满足人们的需要。基于椭 圆曲线的代理签名体制有的含有求逆运算，有的复杂度高。鉴于目前的情况，论 文研究的主要内容是椭圆曲线上的代理签名方案，如何设计高安全性、低复杂度 的代理签名思想就是论文的核心问题。 i j 论文的主要研究内容和组织结构 本论文所研究的主要内容结合椭圆曲线密码算法的特性及代理签名的特点， 设计了一种高安全性、低复杂性的椭圆曲线代理数字签名体制。本文提出的代理 数字签名体制与安全性建立在求解大整数因子分解的困难性或求解离散对数问 题的困难性之上的代理数字签名体制相比，具有安全性能更高，计算量小和处理 速度快，存储空间占用小，带宽要求低等优点。论文的组织结构如下： 第1 章绪论。介绍数字签名研究的背景和意义、数字签名理论和应用现状、 本文的研究内容以及组织结构。 第2 章数字签名基础。介绍数字签名方案、椭圆曲线以及基于椭圆曲线密 码体制的基本内容。 第3 章代理数字签名技术。介绍了代理签名的概念、性质、分类、关键技 术以及基于离散对数问题和因子分解问题的代理签名方案。 第4 章基于椭圆曲线密码体制的代理数字签名方案。主要是结合代理数字 签名和椭圆曲线密码体制二者的特性，设计出了一个基于e c c 安全有效的代理 签名方案。 第5 章结束语。对已做的工作进行总结，并指出下一步工作展望。 第2 章数字签名技术 2 1 数字签名基础 数字签名是实现认证的重要工具，如在网络中的密钥分配、电子安全交易方 面都有重要应用，它提供身份认证、数据完整性、不可抵赖等服务。 2 1 1 基本定义 一般数字签名方案包括三个过程：系统初始化过程、签名的产生过程和签名 的验证过程。下面给出数字签名的形式化定义。 ( 1 ) 系统初始化 在系统初始化过程中产生数字签名方案中的基本参数集合为( m ，s ，k ，s i g ， v e r ) ，其中参数定义如下： m ：消息集合 s ：签名集合 k ：密钥集合，包含私钥和公钥 s i g ：签名算法集合 v e r ：签名验证算法集合 ( 2 ) 签名产生过程 对于密钥kf f k ，相应的签名算法为s i g k ：s i g ，s i g k ：m _ s 。对任意的消息 m m ，有s = s i g k ( m ) ，且s s 为消息的签名，将签名消息组( m ，s ) 发送到签名 验证者。 ( 3 ) 签名验证过程 利用签名者的公钥k6 ：k ，相应的签名验证算法为v e r ke v e r ，v e r k ：m s 一 t r u e ，f a l s e ，且 v e r t c x = ( = ，暑嚣 验证者收到签名消息组( m ，s ) 后，计算v c r k ( x ，y ) ，若v c r k ( x ，y ) = t u r c ，则 签名有效，否则签名无效。 2 1 2 常见的数字签名方案 2 1 2 1r s a 算法 r i v e s t 、s h a m i r 和a d l e m a n 于1 9 7 8 年提出了r s a 数字签名和公钥算法，这 是第一个较完善的公丌密钥算法，它既能用于加密也能用于数字签名，而认证过 程相当于保密过程的逆过程。在已提出的公开密钥算法中，r s a 是最容易理解 和实现的。r s a 算法以它的三个发明者r o nr i v e s t 、a d is h a m i r 和l e o n a r d a d l e m a n 的名字命名。 r s a 的安全性建立在大整数素因子分解困难的基础之上。其公开密钥和私 人密钥是一对大素数的函数。从一个公开密钥和密文中恢复出明文的难度等价于 分解两个大素数之积。 ( 1 ) r s a 算法描述如下： 公开密钥：l i t ，两素数p 和q 的乘积( p 和q 必须保密) ；e ，与( p 1 ) 和( q 1 ) 互素的一个数。 私人密钥：d ，d ：e ( r o o d ( p - - 1 ) ( q - - 1 ) ) 。 用于保密时具体算法思想如下： 加密：用公丌密钥对明文m 求e 次方再模1 1 便得到密文c 。 c 三m 。( m o dn ) 解密：用私人密钥对密文c 求d 次方再模n 便得到明文m 。 m 兰c o ( m o dn ) 用于认证时具体算法思想描述如下： 数字签名：先形成文件的散列值，然后用私人密钥求幂。 验证签名：先形成文件的散列值，然后用公开密钥求幂。 r s a 加密和解密算法是一样的，而认证过程相当于保密过程的逆过程，这 使得r s a 算法非常易于理解和使用软硬件实现。 ( 2 ) r s a 算法的安全性分析 从上述算法可知，若1 1 ，q 被因子分解成功，则私人密钥d 便非常容易被计 算出，r s a 便被攻破。因此，我们必须非常注意p 、q 的选取，例如从安全素数 中选取p 、q ，p 和q 的长度相差不大：q 一1 ) 和( q 一1 ) 有大素数因子：公因子( p l ，q 1 ) 很小。并且要避丌某些特殊的值以提高r s a 算法的安全性。另一种 方法是加大密钥的长度，不过这将导致计算量的剧增。 2 1 2 2 数字签名算法d s a 在1 9 9 1 年8 月的时候，n i s t 首次提出了数字签名算法d s a ，并将其用于 数字签名标准d s s 第一版中。1 9 9 4 年5 月1 9 同，该标准( f i p s l 8 6 1 ) 最终被颁布。 d s a 算法使用一个单向散列函数h ( m ) 。该标准指定使用安全散列算法s h a 。 d s a 的安全性是建立在有限域上的离散对数问题之上的。 d s a 使用公丌密钥，为接收者验证数据的完整性和数据发送者的身份，也 可用于由第三方去验证签名和所签数据的真实性。 ( 1 ) d s a 算法描述如下： 公丌密钥：p ，5 1 2 位到1 0 2 4 位的素数：q ，1 6 0 位长，并与p - - 1 互素的因 子；g = h ( p ) q m o dp ，式中h 小于p 一1 ，并且g 1 ；y = g x r o o dp ( 一个p 位的数) 。 私人密钥：x s = s i g ( s 卜b ， m ) ( 5 ) 任何人在试图求出x a ，x b ，o 和。卜b 时，任何数字签名s i g ( o 小b ， m ) 都不会对它产生帮助。 那么我们就称用户a 将它的( 部分) 数字签名权利委托给了用户b ，并且称a 为b 的原始签名人，称b 为a 的代理签名人，称0 为委托密钥，称0 驴b 为代 理签名密钥，称以。小b 作为签名密钥对消息m e m 生成的数字签名s i g ( 0a b ， m ) 为a 的代理签( p r o x ys i g n a t u r e ) 。 定义3 2能够生成代理签名的数字签名体制被成为代理签名体制。 代理签名体制应满足以下基本性质来确保签名的安全性。 性质l 基本的不可伪造性 除了原始签名人外，任何人( 包括代理签名人) 都不能生成原始签名人的普通 数字签名。这个性质是任何数字签名体制都应该具备的性质，它可以保证原始签 名人的基本安全要求。 性质2 代理签名的不可伪造性 除了代理签名人外，任何人( 包括原始签名人) 都不能生成有效的代理签名。 特别，如果原始签名人委托了多个代理签名人，那么任何代理签名人都不能伪造 其他代理签名人的代理签名。这个性质可以保证代理签名人的基本安全要求。 性质3 代理签名的可区分性 任何一个代理签名都与原始签名人的普通数字签名有明显的区别；不同的代 理签名人生成的代理签名之间也有明显的区别。 性质4 不可抵赖性 任何签名人( 不论是原始签名人还是代理签名人) 在生成一个数字签名后，不 能再对它加以否认。 性质5 身份证实性 原始签名人可以根据一个有效的代理签名确定出相应的代理签名人的身份。 利用这个性质，原始签名人就可以对代理签名人进行监督，使代理签名入不能在 不被发现的情况下滥用它的代理签名权利。 性质6 密钥依赖性 代理签名密钥依赖于原始签名人的秘密密钥。 性质7 可注销性 如果原始签名人希望代理签名入只能在一定时间区间内拥有生成代理签名 的能力，那么必须能够让代理签名人的代理签名密钥在指定的时刻失去作用。 3 2 代理签名的基本类型 根据数字签名权力的委托过程的不同方式，代理签名可以大致分为以下几种 基本类型。 ( 1 ) 完全代理签名( f u l ld e l e g a t i o np r o x ys i g n a t u r e ) 在这种类型的代理签名体制中，原始签名人将他的秘密密钥秘密地交给代理 签名人，使得代理签名人拥有他的全部数字签名权力。 ( 2 ) 部分代理签名( p a r t i a ld e l e g a t i o np r o x ys i g n a t u r e ) 在这种类型的代理签名体制中，原始签名人用他的秘密密钥计算出一个新的 秘密密钥，并把这个新密钥秘密地交给代理签名人。代理签名人不能根据这个新 密钥计算出原始签名人真j 下的秘密密钥；能利用新密钥生成代理签名：验证代理 签名的时候必须用到原始签名人的公丌密钥。使用这两种方法有两种类型的方 案： 代理非保护代理签名( p r o x y - u n p r o t e c t e dp r o x ys i g n a t u r e ) 除了原始签名者，指定的代理签名者能够代替原始签名者产生有效代理签 名。但是，没有被指定为代理签名者的第三方不能产生有效代理签名。 代理保护代理签名( p r o x y - p r o t e c t e dp r o x ys i g n a t u r e ) 只有指定的代理签名者能够代替原始签名者产生有效代理签名。但是，原始 签名者和第三方都不能产生有效代理签名。 在部分代理签名中，代理签名者以s 为签名密钥按普通的签名方案产生代理 签名，可以使用修改的验证方程来验证代理签名的有效性。因为在验证方程中有 原始签名者的公钥，所以验证者能够确信代理签名是经原始签名者授权的。人们 7 根据不同的需要提出了各种各样的部分代理签名。例如，门限代理签名、不可否 认代理签名、多重代理签名、具有接收者的代理签名、具有时间戳的代理签名和 具有证书的部分代理签名，极大地丰富和发展了部分代理签名。 部分代理签名具有可区分性等性质。但在些部分代理签名中，原始签名者 也能产生代理签名，这对代理签名者来说是不公平的。这涉及不可否认问题，不 可否认性是指原始签名者和代理签名者不能欺诈性地否认他的签名。在实践中， 不可否认性是非常重要的，例如，当签名滥用发生争议时，权威机构必须确定谁 是代理签名的真f 签名者。因此，具有不可否认性的部分代理签名是商业的理想 选择。 ( 3 ) 具有证书的代理签名( d e l e g a t i o nw i t hw a r r a n tp r o x ys i g n a t u r e ) 在这种类型的代理签名体制中，使用一个称为证书的文件来实现数字签名权 力的委托。这种类型的代理签名体制又可进一步分为两种子类型。 授权代理签名 在这种类型中，证书由一条声明原始签名人将数字签名权力授权给代理签名 人的消息和原始签名人对代理签名人的公开密钥生成的普通数字签名组成，或者 证书仅仅由一条可以证明原始签名人同意将数字签名权力授权给代理签名人的 消息构成。代理签名人在得到证书后，用他自己的在一个普通数字签名体制中的 秘密密钥对一个文件生成数字签名。一个有效的代理签名由代理签名人生成的这 个数字签名和原始签名人交给他的证书组成。 持票代理签名 在这种类型中，原始签名人首先生成一对新的秘密密钥和公开密钥。证书由 一条声明原始签名人将数字签名权力授权给代理签名人的消息和原始签名人对 新公钥生成的普通数字签名组成。原始签名人将新的秘密密钥秘密地交给代理签 名人，同时将证书交给代理签名人。代理签名人在收到证书和新秘密密钥后，用 新秘密密钥生成普通的数字签名，这个数字签名与证书一起就构成了一个有效的 代理签名。 以上各种类型的代理签名体制，各有其优点和不足。完全代理签名的优点是 简单、方便、容易实现，缺点是原始签名人向代理签名人暴露了他的秘密密钥， 使代理签名人可以在任何文件上代表原始签名人生成数字签名，而且他生成的代 理签名与原始签名人的普通数字签名没有任何区别，因而原始签名人和代理签名 人可以对也门生成的签名互相抵赖。 部分代理签名的优点是代理签名人难以获得原始签名入的“主”秘密密钥， 从而只能获得原始签名人的“部分”数字签名权力，代理签名的长度与普通的数 字签名一样，代理签名的生成和验证过程所需的工作量与普通数字签名的生成和 验证所需的工作量差别不大。这种类型的缺点是需要人们精心地去设计，不能直 接使用普通的数字签名体制来实现。 具有证书的代理签名的优点有以下几点。 代理签名人不能获得原始签名人的秘密密钥； 原始签名人可以利用自己的证书对代理签名人的数字签名权力进行限制，例 如可以明确指出代理签名人可以在什么时间，对什么文件生成代理签名等； 可以直接使用任何普通的数字签名体制来实现。 这种类型的缺点有以下几点。 代理签名的长度比普通数字签名的长度大得多( 一般在两倍以上) ： 代理签名的生成和验证所需的工作量比普通数字签名的生成和验证所需的 工作量大得多( 需要执行两次以上普通的签名生成运算和+ 两次以上的签名验证运 算1 。 3 3 代理签名的关键技术 ( 1 ) 授权方式 授权方式直接影响代理签名的安全性。授权时原始签名者首先要让代理签名 者相信其是合法的授权人，即授权中明确包含原始签名者的身份信息：其次授权 中应明确包含授权信息，即规定代理签名者签名权利的范围，必要时还包含代理 签名者的身份信息，显然可以用证书实现。因此典型的代理签名授权是原始签名 者用自己的私钥对授权信息( 证书) 作签名，然后把证书和签名作为授权发给代 理签名者。 ( 2 ) 产生代理签名密钥对的方式 代理签名的私钥应该含有授权信息、代理签名者的身份信息或者生成代理签 名时用到的代理签名者已注册的签名私钥( 间接表明代理签名者的身份) 。只有 这样，代理签名验证时才可以既验证代理签名本身的合法性，又验证授权。 ( 3 ) 通信中使用安全信道问题 在大多数代理签名方案中，往往需要一个安全通道传输部分变量，也就是说 这些变量是非常重要的，不能被攻击者获取。 3 4 两种典型的代理签名方案 3 4 1 基于因子分解问题的代理签名方案 ( 1 ) 初始过程 n = p q ，p 和q 是两个秘密的大素数； 整数v 满足g c d ( v ，( p - 1 ) ( q - - 1 ) ) ：l ； 用户a 的私钥是x z 。； 用户a 的公钥是y z 。 ( 2 ) 委托过程 a 按照以下步骤进行： 随机选取一个数k z 。，计算出e 刊k vm o dn ) ，其中日是一个哈希函数， 而且它的函数值在0 和v 一1 之间。 计算x i = x 。m o dn ： 将( k ，x i ) 秘密地发送给用户b ； b 按以下步骤进行： 计算e = h ( k ”m o dn ) ； 验证对x 1 7 y c = lm o dn 是否成立。 ( 3 ) 代理签名的生成过程 对于待签名的消息m ，b 进行以下步骤： 随机选择一个数r ez 。，计算e 1 - 讯r 7m o dn ，m ) ； 计算出s = d 【l “m o dn ； 以( k ，c l ，s ) 作为对m 的代理签名。 ( 4 ) 代理签名的验证过程 代理签名的收方在收到消息m 和数字签g ( k ，e l ，s ) 后，用以下步骤来验证： 计算e = 矾k m o dn ) ： 计算c t l = h ( m ，s y p 以) 如果e = e 1 ，那么( k ，e l ，s ) 就是一个有效的代理签名。 这个签名体制的f 确性可由以下算式证明： s v y e e l = ( r ) 【l g - ) v y 掣叫气肌。d n = ( 眦。删”k ) v y 佩删“弦m o dn = r v ( ( x ”y ) 瞰利“p ，砌o dn = r vm o dn 这个体制满足代理签名体制的基本性质。 3 4 2 基于离散对数问题的代理签名方案 假设( m ，s ，k ，s i g ，v e r ) 是- - 个基于离散对数问题数字签名体制，p 是 一个大素数，q 为p - - 1 或p - - 1 的大素数因子；g e z ，且g q = 1 m o dp ：用户a 和b 的私钥和公钥对分别是( x a ，y a ) ，( x b ，y b ) ，其中y a = g x 。m o dp 和y b = g 勋m o d p o ( 1 ) 委托过程 a 随机选取一个数k z ，计算k = g k m o dp ； a 计算s - x a + k km o dq ，并将( s ，k ) 秘密地发送给b ； b 验证等式矿= 对m o dp 。 ( 2 ) 代理签名的生成过程 对某个消息m ，b 生成普通的数字签名s = s i g ( s ，m ) ，然后t ：2 ( s ，k ) 作为他 代表a 对消息m 生成的数字签名，即代理签名。 ( 3 ) 代理签名的验证过程 如果代理签名的收方收到消息m 和代理签g ( s ，k ) ，那么他按照以下步骡束 验证签名的有效性： 计算v = y a k km o dp ； 验证v e r ( y a ，( s ，k ) ，m ) = t r u e * - ，v e r ( v ，s ，m ) = t r u e ： 这个签名方案的正确性可以由以下算式证明： v = y a k k m o dp = g 勋g k k m o dp 5 g 勋+ k k m o d p = g sm o dp 即v 可以看作与s 对应的验证公钥。 这个体制满足代理签名体制的基本性质。 当然还有很多的代理签名体制，不过它们的安全性大都是基于大整数因子分 解问题的难解性或是基于一般离散对数问题的难解性。 体制分析 前种体制安全性基于求解大整数因子分解问题的困难性，但是随着大整数 分解和并行处理技术的进展，为了保证高的安全性，必须进步增长密钥长度， 这将使其速度更慢，更加复杂。 后种体制的安全性是基于求解离散对数问题( d l p ) 的困难性，当群g 的阶 比较小时，存在多种算法来求解g 上的d l p 。其中比较著名的有：b a b y s t e p - g i a n ts t e p ，p o l l a r d pm e t h o d ，p o h l l i nh e l l m a n 以及i n d e x v a l u c l u s 等方法。 因此，要保证其安全性，群的阶必须很大。对于f o 来说，素数p 必须大于2 6 0 0 ， 才不至于遭受已知的求解d l p 的各种方法的攻击。 椭圆曲线密码体制是基于e d l p 难解性的密码体制。它优于基于其它一般群 ( 比如有限域f p 上的乘法群f p ) 上的d l p 的密码体制。椭圆曲线离散对数问题要 比基于有限域上离散对数问题的求解更困难，但运算效率优于后者。 而且前两种体制所基于的两个数学问题还要受到亚指数算法的严重威胁，而 椭圆曲线离散对数问题不存在亚指数攻击，而且椭圆曲线资源丰富，同一个有限 域上存在着大量不同的椭圆曲线，这为安全性增加了额外的保证，也为软、硬件 实现带来了方便。 显然为了保证足够的安全性，这两种体制就必须增长密钥长度，速度，运算 等方面就必然受影响，体制也必将更加复杂性，针对这种情形，本文结合椭圆曲 线密码算法和代理签名方案二者的特性，设计出了一种新的代理签名体制，它的 安全性建立在椭圆曲线离散对数问题的难解性之上，与f i ；f - - 种体制相比，具有安 全性能更高、计算量更小、处理速度更快、密钥尺寸和系统参数更小、带宽要求 更低等优点。 第4 章基于椭圆曲线密码体制的代理数字签名方案 目前存在的代理签名体制，安全性是基于求解大整数因子分解的困难性或求 解离散对数问题的困难性，本文提出的代理签名体制，它的安全性是基于椭圆曲 线离散对数问题的难解性，该体制与- f i i j - 者相比，在安全性，密钥量，处理速度， 带宽占用等方面具有更大的优势，该体制还节省存储空间，节省处理时间，能够 适应未来更高安全的需求，而且它生成私钥公钥对非常方便。另一方面，椭圆曲 线资源丰富，同一个有限域上存在着大量不同的椭圆曲线，这就为本体制安全性 增加了额外的保证，也为软、硬件实现带来了方便。 椭圆曲线具有丰富的群结构和多选择性，并可在保持与r s a & d s a 体制同 样的安全性能的前提下缩短密钥长度，网络传输中占用带宽小，因此本文提出的 代理签名方案在无线网络、集成电路卡、w e b 服务器等方面的应用具有广阔的 前景。 4 1 椭圆曲线方程的生成 4 1 1 随机生成基于f p 的椭圆曲线方程 基于f p 的椭圆曲线e ：y 2 = x 3 + a x + b ；a 、b f p ，a - - 4 a 3 + 2 7 b 2 om o dp 。 其中，a n s i x 9 6 2 推荐p 至少为1 6 0 b i t ；下面的算法使用单向哈希函数 s h a 2 5 6 。为了验证曲线方程是随机产生的，使用了一个随机的比特串( s e e d e ) ， 其也作为随机产生的证据。 下面是产生椭圆曲线方程e 的算法： 输入：( p 是一个大素数) 。 输出：_ 个至少1 6 0 b i t 的比特串s e e d e 、a 、b ，a 、b f p 。 ( 1 ) 随机产生1 个长度为g 的比特串s e e d e ，g 1 6 0 ； ( 2 ) 计算h = s h a - 2 5 6 ( s e e d e ) ，然后把h 的最右边v 比特赋给c o ； ( 3 ) 把c o 的最左边位( 即第v 比特) 设置为o ，把变化后的c o 赋给w o ( 该步 骤确保了r 1 6 0 ： ( 2 ) 计算h = s h a 2 5 6 ( s e e d e ) ，然后把h 的最右边v 特赋给b 0 ； ( 3 ) 把g 比特的s e e d e 转换为整数，记作z ； ( 4 ) 循环处理，i 从1 到s ： s i = ( z + i ) m o d2 8 ； 把s i 作为比特串看待，计算b i = s h a - 2 5 6 ( s i ) 。 ( 5 ) 把b b l 、b 。连接起来得到b ： ，b = b 。i lb 1i i l ib s ( 6 ) 如果b = 0 ，那么回到步骤( 1 ) ； ( 7 ) 任意选择个钆a g f ( 2 m ) ； ( 8 ) 到此，求出基于g f ( 2 m ) 的椭圆曲线方程e ： v 2 + x y = x 3 + a x 2 + b ( 9 ) 输 把( ( s e e d e ，a ，b ) 。 4 1 4 基于g f ( 2 m ) 椭圆曲线方程的随机性检查 下面给出一个算法，以检查基于g f ( 2 m ) 的椭圆曲线方程e ：y 2 + x y = x 3 + a x 2 + b 是否通过上面的算法随机产生的。 算法输入是：p ，p - - 2 m ，长度为g 的比特串s e e d e 、a 、b ，a 、bc g f ( 2 m ) 。 算法输出是：是否。 ( 1 ) 计算h = s h a 2 5 6 ( s e e d e ) ，然后把h 的最右边v 比特赋给b i j ： ( 2 ) 把g 比特的s e e d e 转换为整数，记作z ： ( 3 ) 循环处理，i 从l 到s ： s i = ( z + i ) m o d2 。； 把s 作为比特串看待，计算b i = s h a - 2 5 6 ( s i ) 。 ( 4 ) 把b l 。、b l 、b 。连接起来得到b 。： b = = b 0i lb 10 i | b s ( 5 ) 比较b 和b ，如果相等，返回“是”，表示随机产生的；若不成立，返 回“否”，表示不是随机产生的。 注意：在随机产生f p 上的椭圆曲线算法中使r 满足一定条件，是与群同态 的概念有关；同样，随机产生g f ( 2 m ) 上方程算法中的b 也与群同态的概念有关。 4 2 推荐的椭圆曲线 下面介绍一些被推荐的椭圆曲线。例如n i s t 给美国联邦政府推荐使用的1 5 个椭圆曲线如下所列： ( 1 ) 基于f p 的：p = 2 1 9 2 2 “一1 ，p = 2 2 4 2 9 6 + 1 ，p = 2 5 2 1 一l ，p = 2 2 5 6 2 2 2 4 + 2 1 9 2 + 2 9 6 1 ，p = 2 3 8 4 2 1 2 8 2 9 6 + 2 3 2 1 ，p 都是素数。 ( 2 ) 基于g f ( 2 m ) 的有：f 2 1 6 3 ，f 2 2 3 3 ，f 2 2 8 3 ，f 2 4 0 9 ，f 2 5 7 1 。 被推荐的椭圆曲线可以分为以下三类： ( 1 ) 基于f p 的随机产生的椭圆曲线； ( 2 ) 基于g f ( 2 m ) 的随机产生的椭圆曲线： ( 3 ) 基于g f ( 2 m ) 的k o b l i t z 椭圆曲线。 4 3 生成参数 4 3 1 全局参数的构成 ( 1 ) 有限域的大小q 。如果基于f p ，则q = p ，p 为奇素数；如果基于g f ( 2 m ) ， 则q = 2 m 。 ( 2 ) f q 中的个元素f r 。 ( 3 ) 一个至少长1 6 0 b i t 的比特串s e e d e ，用于检查方程是否随机产生，为 可选项。 ( 4 ) a 、b ，用于定义曲线y 2 = x 3 + a x + b 或y 2 + x y = x 3 + a x 2 + b ，a 、b6 f q 。 ( 5 ) 砥、y i ；，x r , 、y c f q ，g = ( 轧、y 。；) ，g 已e ( f q ) ，且g 的阶为素数。 ( 6 ) g 的阶为n ，n 2 1 6 0 ，1 1 4 怕。 ( 7 ) h = # e ( f q ) n 。 全局参数可以简单地表