（基础数学专业论文）公钥密码算法的效率研究.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取 得的研究成果据我所知，除文中已经注明引用的内容外，本论文不包 含其他个人已经发表或撰写过的研究成果对本文的研究做出重要贡献 的个入和集体，均已在文中作了明确说明并表示谢意 作者签名： 季i 毒 日期：翌2 ：笸：翌 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子 版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅有权将学位论文的内容编入有关数据库进行检 索有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后 适用本规定 学位论文作者签名： 和圣 日期：邈：墨：2 导师签名：f 弓东互 日期：丝1 2 生z ! 摘要：安全性和运行速度是衡量公钥密码算法效率的重要因素，公钥密码算法的 安全性主要基于一个困难的n p 问题，例如离散对数求解问题。而算法的设计将影响 算法的运行速度。本文分析了背包密码算法的安全性，同时对椭圆曲线数字签名算法 的效率进行了比较分析，并且给出了一个改进的椭圆曲线数字签名算法，改进后的数 字签名算法改进了有效签名，并且提高了运行速度。 a b s t r a c t ：s e c u n t yp r o b l e ma n de f f i c i e n c yp r o b l e ma l ea m o n gt h em o s ti m p o r t a n t f a c t o r so fp u b l i c - k e yc r y p t o s y s t e m t h eg e c u r i t yo fp u b l i ck e yc r y p t o s y s t e mi sb a s e do r a nn p p r o b l e m ，s u c ha st h ed i s c r e t el o g a r i t h mp r o b l e m w h i l et h ew o r k i n gs p e e dd e p e n d s o n t h e d e s i g n o f t h es c h e m e i n t h i s t h e s i s ，w e g i v e a n a n a l y s i s o f a k n a p s a c k c r y p t o s y s t e m w ea l s oa n a l y z et h ee f f i c i e n c yo fa ne l l i p t i cc u r v ed i g i t a 】s i g n a t u r es c h e m e f i n a l l yw e p r o v i d ea ni m p r o v e de l l i p t i cc u r v ed i g i t a ls i g n a t u r es c h e m e ，w h i c ha v o i d st h ep o s s i b i l i t y o fi n v a l i ds i g n a t u r ea n di m p r o v e st h ew o r k i n gs p e e do ft h ee l l i p t i cc u r v ed i s i t a ls i g n a t u r e s c h e m e 2 第一章概述 1 1 引言 公钥密码的诞生对于人类信息安全领域带来了空前的革命，公钥密码算法的安全 性是基于一个公认的数学难题，其安全性较高。例如椭圆曲线密码的安全性基于椭圆 曲线离散对数问题。然而，公钥密码算法的效率特别是运行速度是制约其作用的重要 因素。因此，公钥密码算法的效率研究是一个重要的课题。 由于公钥密码算法在效率上存在运行速度慢和系统性能要求高等特点，目前对数 据进行加密时，主要采用公钥密码和对称密码相结合对数据加密。这样一方面利用了 对称密码对数据加密时运行速度快，同时也利用了公钥密码的安全性高等优点，并且 提高了对称密码密钥管理的安全性。 本文分析了几种公钥密码算法的结构，同时分析了这几种公钥密码算法的效率， 最后对e c d s a 算法进行改进，使得改进后的算法提高了运行效率。同时，在文末的 附录部分列有部分算法的j a v a 程序，这些程序的运行环境要求是j v m i 3 及其以上版本 的j a v a 虚拟机。 1 2 当前公钥密码算法中一些已有的研究成果及其效率分析 本文主要从背包密码算法和椭圆曲线数字签名算法分析和改进公钥密码算法的效 率问题。在分析背包密码算法的效率时，主要分析背包密码算法的安全性。对于椭圆 曲线数字签名算法，将从算法的设计对运行速度的影响方面进行分析。 1 2 1 背包密码方面的研究成果及其效率分析 自从m e r k l e - h e u m a n 1 】提出了第一个背包密码算法以来，对背包密码算法的效率 研究一直受到广泛重视，特别是s h a m i r 破解了m h 背包密码算法把背包密码算法的 3 效率研究推向一个新的台阶。背包密码的研究已从数域r 上的m e r k l e - h e u m a n 背包 密码算法推广到伽罗瓦( g a l o i s ) 域上的背包密码变换【2 】。 基于布斯与b 拉定理设计的c h o r - r i v e s t 背包密码算法【3 】是基于有限域上的离散对数 问题设计的算法。在确定系统参数阶段，可以通过七个步骤生成公钥和私钥。并且 在算法设计时，没有使用模乘变换的形式来伪装一个容易解决的子集合问题。c h o r - r i v e s t 背包密码算法设计时的第一步是挑选p 和行，进而在有限域c f ( p ”) 上选取 夕和幂次为n 的t ，根据布斯j b 拉定理计算有限域c f 0 e ) 中p ( 即：o ，l ，p 一1 ) 个 元素与t 相加，然后计算这p 个相加后的和数以g 为底的对数。由于该算法在设计过 程中用到了离散对数计算，其安全性得到了提高。 国内背包密码研究也有很多新的成果。文献【4 】给出了基于背包和离散对数问题相 结合的数字签名研究成果。由于基于离散对数问题的密码算法是一种安全性很高的公 钥密码算法，通过背包问题和离散对数问题相结合，这种算法设计提高了算法的安全 性。文献【5 】提出了基于多背包的密码算法设计，使得对每组明文加密时采用不同的背 包密码算法，而且多背包密码算法之间并不存在关系。在对明文组加密时，选择哪一 个背包密码算法由一个非线性单向随机函数控制。该算法在运行过程中，首先利用明 文分组，采用对称密码算法的形式对分组后的明文进行打乱，其实已达到对明文加密 的目的。在明文打乱后得到的乱码组中，对每一组乱码采用一种背包密码算法进行加 密，这样使得算法的安全性得到了提高。 在一些文献中我们也会看到在效率方面存在问题的背包密码算法。对于文献【6 】给 出的算法设计，攻击者容易构造超递增序列从而实现对该算法的破解。本文将在第三 章对该算法的安全性及其算法结构进行分析，同时给出一种破解算法。 1 2 2 椭圆曲线密码的研究成果及其效率分析 椭圆曲线密码是利用椭圆曲线上的点运算设计的密码算法。椭圆曲线密码算法具 4 有安全性高和运行速度快等优点，使其成为公钥密码研究中一个活跃的课题。椭圆曲 线数字签名算法( e c d s a ) 【7 】日前已被多个标准组织列为行业标准。然而，e c d s a 数 字签名算法在设计时采用两次求逆运算，这两次求逆运算对e c d s a 的运行速度产生 一些影响，有时甚至会出现签名无效的情况。在一些改进的e c d s a 算法中，仍然存 在求逆运算。文献【8 】给出的算法中，在验证签名时，需要计算消息摘要的逆元，该逆 运算对算法的效率也产生一些影响，本文将在第四章对此加以分析。 在改进e c d s a 效率研究方面，已有很多好的成果。文献【9 】通过分析e c d s a 存 在的效率问题，结合椭圆曲线密码机制，e i g a m a l 机制和e c d s a 机制进行了对比，提 出了一种新的签名算法，其实也是一种改进的e c d s a 数字签名。通过算法的设计，使 得该算法在签名和验证过程中没有使用求逆运算。该算法的运算速度比e c d s a 有了 提高。同时，本文借鉴这个算法设计方面的优点，给出了另一个不需要在签名过程和 验证过程中求逆运算的改进算法，相对于e c d s a 来说，效率上也有了提高，本文将 在第四章讨论这一算法。 目前在椭圆曲线密码算法理论中，基于e c c 的签密方案【1 0 】是一种很好的算法设 计。签密是在合理的步骤和时间内同时完成签名和加密两种功能。相对于独立的先签 名然后加密这种过程来说，签密方案开销的系统资源要小的多。文献【1 0 j 给出的基于椭 圆曲线密码体制的签密方案在运行中分为3 个阶段：系统初始化阶段、签密阶段和签密 消息验证恢复阶段。同时该方案由一个认证中心、签密人和接受人来实施，跟传统的 签名方案相同。 1 3 本文的研究内容及其意义 本文通过对计算机及其通信技术的发展状况，结合当前公钥密码算法在效率研究 方面的现状，特别对背包密码算法和椭圆曲线密码算法的效率研究现状进行了分析。 同时，本文在研究这一课题时，结合具体的算法设计来分析和说明如何提高公钥密码 5 算法的效率。为了分析背包密码算法的效率问题，本文在第三章给出了一个背包密码 算法的破解算法。同时，利用矩阵的一些良好性质，设计了一个基于背包问题的m c 矩 阵覆盖密码算法，并且对该算法的安全性进行了分析。最后本文将第四章对椭圆曲线 数字签名算法e c d s a l 7 l 及其改进算法的效率进行分析，并且给出了一个e c d s a 数字 签名算法的改进算法，改进后的算法在运行效率上有了提高。 6 第二章背景知识 1 背包密码知识 m e r k l e 和h e l l m a n 于1 9 7 8 年提出了用超递增序列设计的公钥密码算法，该算法是第 一个背包密码算法。算法通过公开背包向量用于数据加密，其安全性在于知道公开的 背包向量很难求出超递增序列。 2 1m e r l d e - h e l l m a n 1 背包密码算法 背包密码算法是基于一个子集合问题：有一个能承受已知重量b 的背包，问题 为从重量分别为a ，n 。的物品中选取多少个物品，使其重量恰好等于背包的承 受重量b 。用数学表达式来描述上述问题：如果第i 个物品被选取，则取就= 1 ，否 则戤= o ，从而有a l x l + 十= b 。从计算复杂性的角度来说，子集合问题是一 个n p 完全问题。 m e r k l e 和h e l l m a n 1 使用模乘和置换设计了第一个背包密码算法： 设a l ，a 2 ，是超递增序列，即 j - 1 v j = 2 ，n 吩 啦 i = 1 选取整数p 和u ，并且p 和u 具有下列性质： p 2 ，p ) = l ，玩ia i w ( r o o d p ) ，对v i = l ，n 记向量a = ( a l ，) ，b = ( 6 l ，b z ，k ) ，则背包密码算法的私钥为( a ，p ，u ，u - 1 ) ，其 中u 一1 是u 模p 的逆，公钥为b 。 对每一明文块m = m 1 ，其中m 为0 ，1 。 加密： c = b l m l + b 2 r n 2 + + k m ” 7 解密： 通过如下判断恢复出明文： 记t 三c w 一1 ( r o o dp 1 ( 1 ) 若t ，则= 1 ，否则砜= 0 ； n ( 2 ) 若t 一啦佻，则= 1 ，否则= 0 ，( j = n 一1 ，1 ) 。 = 巧+ 1 2 1 1 有关s h a m i r 的攻击算法【2 】 s h a m i r 的攻击算法是第一个破解背包密码的攻击算法。s h a m i r 攻击算法主要利用 公开的背包向量构造超递增序列，同时使用这一超递增序列对背包密码密文解密，实 现了背包密码算法的破解。 m e r k l e - h e u m a n 背包密码算法的安全性主要是通过模乘变换，使得公开的背包向量 不具有超递增性。然而，也正是背包密码算法中采用超递增序列这一特性，使得背包 密码算法的安全性受到了影响。m h 背包密码算法发表两年后，s h o m i r 通过寻找一个解 密密钥对，使用这个密钥对与背包向量的分量构成的序列作模乘变换，能产生超递增 序列即可实现对m e r k l e - h e l l m a n 背包密码算法的破解。 s h a m i r 在攻击m e r l d e - h e l l m a n 背包密码算法时，主要利用作为公钥的背包向量 b = ( b l , 6 2 ，k ) ，寻找一个解密密钥对p 7 ，) ，使其满足： ( 1 ) ( ，p ，) = 1 且1 u 2 因此，若能通过公钥背包向量6 = ( b - ，b 2 ，k ) ，求出告满足上述条件的取值 范围( 显然这样的取值范围是存在的，因为以譬为中心的充分小的邻域就是其中 之一) 。若超递增序列，口：，以的每一项满足 啦，且设向量b ，使得向量b 的分量为氏= 皿+ p v i l ，n ) ，则 i = l 以b 的分量作成的序列不再是超递增序列。 该密码算法的公钥为b ，私钥为。和p 。 设明文块m = ( m 1 ，) ，其中盹为0 ，l ，l l ，1 ) ， 加密： n c = e 6 帆= ( g 1 9 7 1 1 + + k ) + ( m 1 + + 7 h ) p t = l 解密： n c = e 6 驰= ( 0 1 m l + + ) + ( m 1 + + m n ) p = l 兰g l m l + + 8 ，l ( m o dp ) 然后利用o l ，o 。是一个超递增序列就可以实现解密。 3 1 1 破解算法 1 2 】 根据s h a m i r 攻击，明确破解该密码算法的目标是要构造超递增序列，然后对截 获的密文c 进行解密。对于该密码算法的破解，只要选取整数，【p p + 口1 1 1 ， 用p ，来构造新的超递增序列即可破解上述背包密码算法。由此可能会引出下列两个问 题： ( 1 ) 因为p 8 l 都未知，是否能求出p ， ( 2 ) 假设能求出p ，通过p ，构造出超递增序列，问题为p ，是否大于超递增序列 元素相加的和数。 我们通过取定p ，= p + 口l 一1 来说明上面的问题，位于区间【p p + n 1 1 】上 的其它整数也具有类似性质。因为玩= 啦+ p l 1 ，n ) ，i e ib l 是已知的，所 以，= p + n 1 1 = b 1 1 是能求出的。下面说明所选取的p ，满足破解算法的要 求。 破解算法的合理性分析 通过上面选取的一，则有 ( 6 1 ，b 2 ，k ) = ( 口l + p ，n ，l + p ) = ( 1 + ( p + d l 一1 ) ，( 0 2 一口1 + 1 ) + ( p + n l 1 ) ，( a n 一口1 + 1 ) + ( p + m 1 ) ) = ( 1 + p ，( a 2 一n l + 1 ) + p ，( 一o l + 1 ) + p ，) 以下证明1 ，a 2 一n l + 1 ，一n l + l 是要构造的超递增序列，即证明v 2 ，n 以一n t + 1 ( a k 一? 1 1 ) = 口k o 一1 ) ( a l 1 ) k = lk f f i l i - l 这是显然的，因为( l ，n 。) 的分量作成的序列是超递增序列，所以啦 毗，vi = 知= l 2 ，站，即证上述序列是超递增序列。 则： 对于密文e ， n c = 瓯佻= ( 1 m 1 + + 8 t l ) + ( m l - t - - t - m n ) p i = 1 = m 1 + + ( o 。一n l + 1 ) + ( p + n l 一1 ) ( m l + + m n ) 0 兰m l + ( 眈一l + 1 ) 耽+ + ( 一口1 + 1 ) 盯h ( r o o d p ) 因为o l 1 ，故有啦一口1 + 1 啦， 2 ，3 ，一，n ，及p ，p ，则有 nn p p 啦2 ( 吼一1 1 ) t = 1i = l 1 4 因此，从上面的论证过程可知，在破解算法中所选择的一是合理的。这样就可 用m d p hm e r k l e 和m a r f i nh e l l m a n 背包密码算法的解密算法来进行解密，从而恢复出明 文m 1 ， 3 1 2 算法破解的实例 设向量口= ( 2 2 ，4 3 ，7 0 ，1 5 3 ，4 0 1 ，8 9 9 ) ，选取p = 2 2 0 0 ，则 6 = ( 2 2 2 2 ，2 2 4 3 ，2 2 7 0 ，2 3 5 3 ，2 6 0 1 ，3 0 9 9 ) 设明文块m = ( 1 ，0 ，l ，1 ，o ，1 ) ， 加密：g = 6 1 7 珏l + + 6 6 7 7 善6 = 9 9 4 4 。 破解：选取一；h 一1 = 2 2 2 1 ，从而构造出超递增序列l ，2 2 ，4 9 ，1 3 2 ，3 8 0 ，8 7 8 ， 则c 兰1 0 6 0 ( r o o d2 2 2 1 ) 。因为1 0 6 0 8 9 8 ，所以佻= 1 又因为1 0 6 0 8 7 8 1 8 2 g e t n u m b e r ( e & ) j = i 即诹1 ) s 。 j = l 取整数p ，。，使得p 2 ，( u ，p ) = 1 ，u u _ 1 三l ( m o d p ) 。作变换且设b 三 a w ( r o o dp ) ，基于背包问题的m c 矩阵覆盖密码算法的公钥为b ，私钥为0 ，0 j - - 1p a ) 。 设明文m = ( m l ，r n z ，) ，其中仳为0 ，1 ；i = 1 ，2 ，托。 加密：。 解密 m b m t = ( b k l 慨，k 2 ，) m t k=l七=ik = l 三u ( 1 毗帆，。h m ) m t ( r o o d p ) k = l詹= lk = l 则a k l m t ，a k 2 m k ，n h m t 是一个超递增序列， k = lk - = l 七= l nnn ( b k 6 船，讯) 是一个背包向量。 w - i m b m t 兰0 j - - 1 l d ( 钒- 佻，。k 2 ，吼) 护( r o o d p ) 蠹= lk = - ik = l 三( 地m 一，仉) m t ( m o d p ) k f f i lk = l k = l nn + 叻a k l m k + + d h 吼 k = lk = l 1 7 + 钆 。脚 m l i r 设 通过下列方式解出明文： 若g e t n u m b e r ( t ) m i n g e t n u m b e r ( a h ) l ，2 ，l 有= l ； 否则 m n = 0 ： 因为若g e t n u m b e r ( t ) m i n ( g e t n u m b c r ( a h ) 时有竹k = o ，则： 1 ，2 ，n ) nnn g e t n u m b e r ( t ) = g e t n u m b e r ( m l a k l f f t k + 抛毗帆- i - + 口h m ) k = lk = lk = l g e t n u m b e r ( m 1 a k l m k + 他d k 2 m k + + 一1 口k , n - i m k ) k = l k = lk = l g e t n u m b e r ( 岛+ + & 一1 ) 毋一1 否则 有r n j = 1 ； m = 0 ； 当j = 1 时，设n ? , m = g e t n u m b e r ( & ) ，s = 1 0 ，1 4 ” 1 8 若t ( m o d s ) m i n a k , 有m 1 ：1 ；女 1 2 ，”) 否则 7 7 , 1 = 0 ： 因为1 毋一l 矛盾。 k = lk f f i l 反之，若t ( r o o d s ) 岛一1 时，同样能推出7 ，巧= 0 。 同理可以对j = 1 时的情况进行讨论。 3 2 3 实例演示 例：基于背包问题的m c 矩阵覆盖密码算法中，设属于私钥部分的矩阵： a = 1 05 0 06 0 0 0 2 01 0 01 0 0 0 3 02 0 05 0 0 0 则矩阵a 的各列的列和分别是：岛= 6 0 ，= 8 0 0 ，岛= 1 2 0 0 0 。 取p = 2 4 5 7 9 ，u = 6 4 3 7 ，从而p ，p ) = 1 。由w 一1 兰1 ( r o o dp ) ，求出u 一1 = - 3 2 8 0 。 加密 所以，属于公钥的矩阵： 解密 1 5 2 1 22 3 2 3 08 3 9 1 b 三w a ( r o o d p ) = l5 8 4 54 6 4 62 1 8 8 1 设明文：m = ( 1 ，0 ，1 ) m b m t = ( 1 ，0 ，1 ) 2 1 0 5 79 2 9 21 1 0 8 9 4 6 4 62 1 8 8 1 2 1 0 5 79 2 9 2i i 0 8 9 ( 1 ，0 ，1 ) t ：5 5 7 4 9 0 , 1 - - 1 m b m t = 一3 2 8 0 * 5 5 7 4 9 三1 1 0 4 0 ( m o d2 4 5 7 9 ) ( 1 ) g e t n u m b e r ( 1 1 0 4 0 ) = 5 m i n g e t n u m b e r ( a 船) = 4 ，说明m 3 = 1 。 k l ，2 ，3 ( 2 ) 因为1 1 0 4 0 ( r o o d1 0 0 0 ) = 4 0 1 0 ，从而必有m 1 = l ，k = 1 ，2 ，3 。 故从解密得到明文：m = ( 1 ，0 ，1 ) 。 3 2 4 算法的安全性分析 从2 1 1 节介绍的s h a m i r 攻击方法的分析可知，对m e r k l e 和h e l l m a n 设计的背包密 码算法的攻击中，主要利用属于私钥中的超递增序列这一特性和作为公钥的背包向 量b = ( b l ，b 2 ，k ) 来实现对该密码算法的破解。 基于背包问题的m c 矩阵覆盖密码算法的超递增序列c t k l m k ，a k 2 t n k ， k f f i - - l膏= l ea 。n t n k 随着明文的变化而变化，因而是动态的，从而所得的背包向量也是动态的 f f i - 1 ( 注：为了名词在称谓上一致，以下简称动态的超递增序列和动态的背包向量) 且在 这一密码算法中，动态的超递增序列和动态的背包向量都不属于公开信息。又由于上 述矩阵求解是n p 完全问题，从而增强了该密码算法的安全性。若直接用s h a m i r 进行攻 击，则攻击者会面临如下问题。 1 因为攻击者不知道动态的背包向量b ，从而无法利用动态的背包向量来构造新 的超递增序列。若攻击者直接利用s h a m i r 背包破解方法来破解基于背包问题的m c 矩 阵覆盖密码算法，需要解决怎样构造背包向量这一问题。 2 因为作为私钥部分的非负整数矩阵a 的每一行都是超递增序列，若攻击者 采用s h a m i r 的背包破解方法从作为公钥的矩阵b 的每一行入手构造一个非负整数矩 阵a ，使得a 的每一行都是超递增序列，则攻击者必须设计一个解密密钥对( u ，p ，) ， 使得用解密密钥( u ，p ，) 对矩阵b 的每一行作模乘变换后，都能产生超递增序列。按照 这样的攻击算法，攻击者会面临以下问题： ( 1 ) 在计算比值箩的取值范围时，多的取值范围必须是由矩阵b 的每一行 元素所确定的取值范围的交集。这样攻击者至少得利用矩阵b 的其中一行元素来确 定告的取值范围，从而增加了计算上的时间开销。 ( 2 ) 即使攻击者计算出比值的取值范围，从该取值范围设计出一个 解密密钥对( ，尸，) 。如果由u b 兰( r o o d p ) 得到的非负矩阵的元素不具 有。备件1 ) 茭j 1 0 9 e t n u 扣曲e r ( s ：) 的整数倍这一特性，k = 1 ，竹，i = 1 ，佗一1 。那 么，利用( u ，p ，) 对密文作模乘变换后，攻击者利用基于背包问题的m c 矩阵覆盖密码 算法进行解密时，相当于对2 n 个不同的明文的可能取值进行搜索。因此，恢复明文相 当于解一个困难的背包问题。 2 1 ( 3 ) 如果要通过上述第( 2 ) 步变换所得的非负矩阵的元素具有吐f + 1 1 为 1 0 9 e t n u m b e r ( ) 的整数倍，则由变换叫b 三a ( m o dp ) 知，存在整数z ，使得u 7 b h z o ，i 1 ，n ；k ：1 ，付，且当i 2 时，u k z p ，是1 0 9 e t n u m b e r ( 一1 ) 的 整数倍。若从整数右边的第一位向左开始计算整数位数，则考察上述每个i 和每一 个k 的取值，都有u b k i ( r o o d1 0 9 e t n u m b e r ( f f , 一，) 和l p ( m o d1 0 9 e t n u m b e r ( 一- ) 这两 整数相等，从而要选取到这样的一个解密密钥对7 ，p ，) 也是一件困难的事情 3 攻击者利用s h a m t r 攻击方法从矩阵b 的列和岛1 ，如。来估计解密密 钥p ，和，以及构造相应的超递增序列晶1 ，晶。设g = m l k - m i + + r = l r n b h m 为明文m l ，竹h 通过基于背包问题的m c 矩阵覆盖密码算法加密后得到 k = l 的密文，同样设t 兰( m o dp ，) ，通过如下解密： 若t 晶。，则憾= 1 ，否则碱= 0 ，若t 一瓯锄，则以= 1 ，否 则戚= 0 ，0 = n 一1 ，1 ) 从而得到明文嵋，m ：。 若攻击者利用上述方法进行攻击会面临以下问题，通过这种攻击所得到的 明文m j ，成不一定是正确的明文m ，忱，m 。如在实例演示部分，即 使攻击者通过矩阵b 的列和计算出p = p = 2 4 5 7 9 ，u 剐一1 = 一3 2 8 0 ，从而得 出品1 = 6 0 ，s = 7 0 0 ，s = 1 2 0 0 0 。因为通过相应的模乘变换得到t = 1 1 0 4 0 显 然t ( s 刍。+ s 包) ，即m = 1 但t s = 一9 6 0 0 ，从而无法知道m ：，m ；。 第四章椭圆曲线签名算法的效率分析及其改进算法 4 , 1e c d s a 7 算法有待改进的问题 e c d s a 的算法部分已在第二章2 3 节给出了介绍。在e c d s a 数字签名算法的 签名过程和验证过程中各采用一次求逆运算，使得运行速度受到一些的影响。在签 名过程中，当所选取的随机数k 不与互素时，需要重新选取随机数老；在验证签 名过程中，若通过签名所得的8 与不互素时，则本次签名无效，必须重新进行签 名。这样就出现了签名人在完成签名时，需要对签名信息进行一次验证，从而影响 了e c d s a 的运行速度。因此，在对e c d s a 数字签名算法进行改进的研究中，克服 因求逆运算带来的效率问题是一个研究方向。 4 2 一个仍存在求逆运算的改进算法【8 】 该改进算法即第二章2 4 节列出的椭圆曲线改进算法一。在算法的签名过程中，没 有用到e c d s a 的求逆运算，从而在一定程度上提高了系统的运行速度。在验证过程 中，需要对消息的摘要进行求逆，则存在两个方面的问题： ( 1 ) 当哈希函数返回消息的摘要比较大时，计算e 的逆元需要开销一些系统时 间。 ( 2 ) 如果e 和非互素，那么对消息掰的签名就无效，需要重新签名。 4 3 一个不存在求逆的改进算法【9 】 该改进算法即第二章2 5 列出的椭圆曲线改进算法二。在算法的签名过程和验证过 程中都不需要求逆，从而提高了算法的运行速度。 4 4 一个改进的算法【1 4 】 下面我们提出一个对e c d s a 改进后的算法，该算法虽然在系统参数初始化是用到 了求逆运算，但在签名过程和验证过程不需要进行求逆运算。 改进算法的系统参数初始化 设e 是一条给定的椭圆曲线，m 为待签消息，随机选取d z ；，计算q = d p ，其中点p 的取法和e c d s a 中点p 的取法一致。改进算法的私钥为d ，d - 1 ，公钥 为q 。 签名与验证算法 签名： 选取随机数k 【1 ，n 一1 】，计算r = k p ，计算r = 厶( r ) ，8 三d - 1 ( r h ( m ) + k ) ( m o d ) 。将( r s ) 作为消息m 的签名 验证： 计算并验证等式r = 厶( s q r h ( m ) p ) 是否成立。若成立，则接受签名。 算法的合理性 若( r s 确为m 的数字签名，则 厶( s q r h ( m ) p ) = f ( r h ( m ) p + k p r h ( m ) p ) = x ( k p ) = 厶( r ) = r 安全分析 在上面的改进算法中，与e c d s a 数字签名算法类似，攻击者最多只能截获三个参 数r ，s 和m 。若攻击者要伪造签名，那么攻击者必须要伪造待签消息m ，不妨设为 m + ，从而求出m 的散列值为h ( m + ) 。同时，攻击者必须伪造相应的r ，矿，而伪造这 2 4 两个参数将面对求解离散对数这一难解性问题。 运行速度分析 在设计该改进算法时，虽然也用到了逆元，该求逆运算在初始化阶段蒇已经完 成。在算法的签名和验证过程中，没有使用求逆运算。从而提高了运行效率。 第五章结束语 5 1 研究工作总结 公钥密码算法的效率是评价公钥密码算法的一个重要指标，也是影响公钥密码算 法在实际应用中的重要因素。本文在研究这一课题时，以背包密码和椭圆曲线数字签 名为例分析了公钥密码算法的效率。在研究过程中，本文给出了两个具体的背包密码 算法的安全性分析，同时分析了椭圆曲线数字签名算法存在的效率问题。最后本文给 出了一个e c d s a 数字签名算法的改进算法，使得改进后的算法在运行速度上有了提 高。 5 2 展望 随着通信和计算机技术的发展，公钥密码在实际应用中的重要地位会得到进一步 地提高，对公钥密码的效率研究会更加活跃。由于科学技术的发展，未来的公钥密码 算法的效率研究主要体现在其安全性上，同时算法的运行速度也是重要的研究课题。 由于椭圆曲线密码算法具有运算速度快，安全性高等特点，加上椭圆曲线密码在无线 安全领域的广泛运用，这样使得椭圆曲线算法的效率研究会更加活跃。 参考文献 【1 】r m e r k l ea n dm h e l l m a n h i d i n gi n f o r m a t i o na n ds i g n a t u r e si nt r a p d o o rk n a p s a c k s i e e et r a n s a c t i o n so ni n f o r m a t i o nt h e o r y p 5 2 5 - 5 3 0 ，1 9 7 8 【2 】卢开澄计算机密码学一计算机网络中的数据保密与安全清华大学出版社，2 0 0 3 【3 i s c h o r ，r l r i v e s t ak n a p s a c k - t y p ep u b i ck e yc r y p t o s y s t e mb a s e do na r i t h m e t i c i nf i n i t ef i e l d s ，i e e et t a n s i n f o r m t h e o r y3 4 ( 1 9 s s ) ，9 0 1 9 0 9 1 4 】周春浓基于背包和离散对数问题相结合的数字签名研究信息安全与通信保 密，p 1 3 3 - 1 3 5 ，2 0 0 5 5 】汤朋志一种基于多背包的密码算法，微计算机信息，p 5 2 - 5 4 ，2 0 0 6 。 【6 】谭显伦，阮永良一种新的背包加强算法电脑知识与技术( 学术交流版) ，p 4 9 - 5 2 ，2 0 0 4 【7 】j o h n s o nd ，m e n z e sa t h ee l l i p t i cc u r v ed 啦a ls i g n a t u r ea l g o n t h m t e c h n i c a lr e - p o r t ，c o r r9 9 - 3 1 ，c a n a d a ：d e p a r t m e n to fc o m b i n a t o r i c sa n do p t i m i z a t i o n ，u n i v e r s i t y o fw a t e r l o o ，1 9 9 9 【8 】彭庆军种基于椭圆曲线的数字签名方案湖南理工学院学报( 自然科学版) ，p 6 9 - 7 1 ，2 0 0 6 【9 】刘广一种新的椭圆曲线数字签名方案计算机工程与应用，p 1 4 0 - 1 4 1 ，2 0 0 5 【1 0 】杨义先无线通信安全技术北京邮电大学出版社，2 0 0 5 【i i 】k o b l i t z n e l l i p t i c c u r v e c r y p t o s y t e m s m a t h m a t i c s o f c o m p u t i a t i o n ，1 9 8 7 ，4 8 ( 1 7 7 ) ：2 0 3 2 0 9 【1 2 】徐猛对一种新的背包加强算法的破解电脑知识与技术( 学术交流版) ，p 9 2 - 9 4 ，2 0 0 6 【1 3 】徐猛基于背包问题的m c 矩阵覆盖密码算法信息安全与通信保密，p 1 5 6 - 2 7 1 5 8 ，2 0 0 6 【1 4 】徐猛椭圆曲线签名方案预印本，2 0 0 6 攻读硕士期间发表的论文 对一种新的背包加强算法的破解电脑知识与技术( 学术交流版) p 9 2 - 9 4 2 0 0 6 基于背包问题的m c 矩阵覆盖密码算法信息安全与通信保密p 1 5 6 - 1 5 8 ，2 0 0 6 椭圆曲线签名方案预印本，2 0 0 6 致谢 转眼间，三年的研究生时光就要过去了，回首这三年来的点点滴滴，心中感慨万 千。一方面，这里的学术氛围好，我在其中也受到了熏陶，使自己在专业知识上有了 很大的提高。另一方面，这里的老师不仅学问好，还都很热情，积极关心我们，帮助 我们。借此机会我要感谢关心和帮助过我的人。 首先要感谢我的导师陈志杰教授，陈老师治学严谨，学识渊博，德高望重。陈老 师那优美而深入的课堂教学深深吸引了我；陈老师的热心和平易近人给我留下了深刻 的印象，在我最困难的时候陈老师总是鼓励我，在我发表论文时，陈老师不厌其烦地 为我的论文提出指导性的修改意见，使得我在课题研究方面取得了很大的进步。在 此，向陈老师表示衷心的感谢。 同时我要特别感谢我的导师杨思熳讲师，杨老师为人坦诚，学术严谨，做事精益 求精。在我读硕士期间，杨老师热心关心我的学习和生活，给了我很大的帮助。特别 是在我发表论文时，不厌其烦地对我的论文进行修改，同时在我的毕业论文写作过程 中。一直关心论文的进展并提出指导性的修改意见。正是在他的帮助下，我的论文才 得以顺利地完成。借此我要向杨老师表示由衷的感谢。 其次我要感谢黄英娥老师，毕平老师和杜若霞老师，在这三年中她们一直在关心 着我们的学习和生活。同时要感谢资料室的糜老师，在我每次措书时，他总是热心地 为我提供很多信息 还有我要感谢同门的肖罗保同学，我和他经常在宿舍里讨论专业方面的知识，这 样对我们俩的学习和研究都有很好地促进。 最后，还要感谢我的室友时林林，王卫国，刘永瑞，杨荣，鄢彩光和张一凡，他 们对我在学习和生活上给予了很大的帮助。以及感谢所有关心，帮助和支持过我的的 3 0 人。 三年就要过去了，马上我就要投入到一个新的环境中去生活，但这一段美好的时 光一定会在我的记忆中，伴随我，给我勇气和力量去面对新的困难和挑战。 3 1 徐猛 二零零七年五月十六日 附录 以下程序运行在j 2 s e5 0j v m 上，用到了j a v a m a t h b i g i n t e g e r 包，以便能够处 理1 2 8 位的整数。 一个改进的椭圆曲线数字签名算法 椭圆曲线上的点坐标计算 i n ta ，a ； 椭圆曲线上的点坐标计算函数【该方法即2 2 节椭圆曲线上的点运算】 p u b l i cs t a t i cv o i dc o m p u t e c o o r d ( i n te l ，i n ty l ，i n tx 2 ，i n ty 2 ) i f ( ( x 1 = = x 2 ) & & ( ( y l = ；= o ) ii ( y l y 2 ) ) ) 对o + ( x ，y ) = ( x ，y ) ，( x ，y ) + ( x ，- y ) ；o 的情况 x 2 = o ； y 2 - - y i + y 2 ； ) e l s e 趔( x l = = 嘞) & ( y l = = y 2 ) ) ( x , ，y 1 ) = ( x 2 ，y 2 ) ，2 ( x l ，y 1 ) = ( x s ，y 3 ) 的情形 坫( 3 】( ；+ a ) 匆l ； x 2 = a 2 - 2 x 1 ，y 2 = a ( x l x ) - y 1 ； e l s e x l x 2 ，( x l ，y 1 ) + ( x 2 ，y 2 ) = ( x 3 ，y 3 ) 的情形 a = ( y 2 y 1 ) ( x 2 一x 1 ) ； 3 2 x 2 = 二2 】【1 一x 2 ，y 2 = ax l - x ) - y l ； ) 系统参数 p r i v a t eb i g i n t e g e rd ，ne ；e 和d 模n 同余于b i g i n t e g e r v a l u e o f ( 1 ) 设置基点和公钥坐标 p r i v a t ei n tx p ，y p ，x q ，