（应用数学专业论文）环zn上圆锥曲线数字签名的研究.pdf

摘要 摘要 1 9 9 8 年曹珍富教授提出了圆锥曲线密码体制，与椭圆曲线相比，在圆锥曲线 上的明文的嵌入、逆元的求解、元素的阶和点的运算等都容易实现。通过引进标 准二进制计算群元素的整数倍的算法，圆锥曲线密码体制的计算量节省了1 4 的计 算量。 本文在圆锥曲线密码方面所取得的研究成果如下： 1 对杨等人提出的基于环乙上圆锥曲线的e i g a m a l 数字签名方案的攻击，能 够从公钥和签名中求解出签名私钥，其签名方案被完全攻破。通过对原签名方案 参数的重新选取，提出了一种新的方案。该方案能够抵抗本文的攻击，并且综合 了大数分解和有限群上的计算离散对数问题的困难性，增强了安全性。 2 利用改进的方案构造了广播和有序多重数字签名方案。广播多重数字签名 方案具有无需进行多次交换数据以获得同一个参数的优点；有序多重数字签名方 案具有签名的长度不随签名的人数增加而增加的优点。 关键词：圆锥曲线离散对数公钥密码数字签名 a b s t r a c t u o n l cc u ec r y p t o g r a p h yw a si n t r o d u c e db yp r o f c a oz h e n f ui n l 9 9 8 c o m p a r e d w i t he c c , p l a i n t e x te m b e d d i n g ，i n v e r s eo p e r a t i o n , c o m p u t i n ge l e m e n to r d e r a n dd o i n t 1 nc u n ，e sa r ef a c i l i t y w h e nt h es t a n d a r db i n a r y s y s t y mw a sa d o p t e dt oc o m p u t et h e i n t e 伊a lm u l t i p l eo fa ne l e m e n to fag r o u p ，t h et i m ec a n b es a v e da p p r o x i m a t e l vb vl 4 t h em a i nr e s e a r c hr e s u l t si nt h i sp a p e r i n c l u d e ： l b ya t t a 似t ot h ed i g i t a ls i g n a t u r es c h e m eb a s e do nt h ec o n i cc u r v eo v e r z ，l p r o p o s e d b yy a n ge t c ，s e c r e tk e yc a b eg a i n e db yp u b l i ck e ya n d t h es i g n a t u r e s ot h e s l g n a t 叶es c h e m ei sn o ts e c u r i t y ，an e wd i g i t a l s i g n a t u r es c h e m ei sp r o p o s e d b y c a o o s m gt h ep a r a m e t e ra g a i n i tc a l lr e s i s tt h e a t t a c k 幻t h ep a p e ra n dm a k e c o m p r e h e n s i v e l yu s eo ft h ed i f f i c u l t i e si nt h ef a c t o r i z i n gl a r g ei n t e g e ra n dc o m p u t i n g d i s c f e t el o g a r i t h mo nf i n i t eg r o u p ，i n c r e a s i n gt h e s e c u f i t yo f i t z ，b a s e d0 nt h en e ws c h e m eb r o a d c a s t i n ga n ds e q u e n t i a l m u l t i s i g n a t u r ed i g i t a l s c h e m ea r es t c t u r e d ，t h e f o r m e rh a st h e a d v a n t a g et oo b t a i nt h es a m es i 2 n a t u r e p a r 啪e t 盱w i t h o u te x c h a n g i n gd a t af o rm a n yt i m e sa m o n g s i g n e r s ；t h el a t t e r h a st h e a d v a n t a g eo ft h es i z eo ft h em u l t i ，s i g n a t u r en o tt ob ed e p e n d e n to nt h en u m b e ro f t h e k e y w o r d s ： c o n i cc h iv e d i s c r e t el o g a r i t h m p u b l i c - k e yc r y p t o s y s t c m d i g i t a ls i g n a t u r e 西安电子科技大学 学位论文独创性( _ - - j l ；创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特l l d i l 以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：固煎蕴上 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：翌羞丑压2 矿 导师签名：五毕 同期2 笃孳! 酋纷2 i j f il l 上量胖 第一章绪论 第一章绪论 1 1 研究问题的背景与意义 计算机网络的产生把我们带进一个信息社会，在信息化社会里，计算机网络 己成为现代社会赖以生存的物质基础，大量传输和存储的信息的安全保密和防伪 问题成为人们关注的一个重要课题。在当前，计算机网络的安全问题同益突出， 有关网络安全威胁的事件频频在电视和网络等媒体报道，网络安全的形势不容乐 观，已严重地威胁到人们j 下常的生活，甚至威胁到国家安全。网络安全的实质是 信息安全，信息安全的核心技术之一是密码技术。人们普遍认为现代密码是解决 信息安全的最有效的方法，因此，密码学的研究成为当前一个研究热点。 密码学，这门古老而年轻的科学，是信息安全的核心技术。回顾密码学的发 展，如同翻开一本内容丰富、充满传奇色彩的故事书。人类对密码的研究和应用 已有几千年的历史，从4 0 0 0 年前的古埃及到上个世纪的两次世界大战，密码一直 扮演着极其重要的角色。古罗马的凯撒大帝第一次将密码技术应用到人类实践中。 当时，凯撒大帝利用传信兵与前线的将军们通信，为了防止传信兵中途被抓或者 篡改信件，凯撒采用了一种特殊的写信方式：将字母顺序推后3 位，即a 字母写 为d ，将b 字母写为e ，以此类推。信件写完后，凯撒将信件卷起，在封口滴上 厚厚的蜡，在蜡未干以前，压上自己的私印。将军收到信件之后，首先检查蜡封 是否完整，蜡印是否是凯撒的印章，然后才拆开信件，按照只有他和凯撒才知道 的字母替换规律读信。在现在的密码学教科书上，我们仍能找到这种密码方法， 即c a e s a r 密码。这种密码系统是现代密码系统的雏形，蕴含了信息安全学科所强 调的四种基本服务：机密性、认证行、数据完整性和不可抵赖性。 密码学在二战期间也发挥了重要的作用。1 9 1 8 年，为了保护银行通信的安全， 德国人a r t h u rs c h e r i b i u s 发明了第一台被称为e n i g m a 的非手工编码密码机。二 战期间，这种密码机的加密通信能力被德国人应用于军事，为德军在二战初期的 胜利起到了重要作用，让盟军大伤脑筋。后来，波兰人m a r i a nr e j e w s k i 初步破解 了e n i g m a ，随后，英国人a l a nt u r i n g 更是终结了e n i g m a ，盟军随后开发了称 为c o l o s s u s 的机器，很多学者认为成功破解e n i g m a 使得二战提前一年结束。 然而，密码学作为- i - j 科学则仅仅是近5 0 年的事情。1 9 4 8 年，s h a n n o n 发表 了划时代的“通信的数学理论”，宣告了信息论的诞生。随后，s h a n n o n 发表了著 名的“保密系统的通信理论”一文，用信息论观点对信息保密闯题傲了全面的论 述。该文将密码学的研究纳入科学的轨道，同时，为对称密码学的构建提供了直 环z 。上圆锥曲线数字签名的研究 接的理论基础。 为了解决对称密码系统中密钥分发和管理问题，1 9 7 6 年，d i f f i e 和h e l l m a n 在 他们的经典论文“密码学的新方向”【2 】中提出了一种允许通信双方在不安全信道上 安全地协商密钥协议，即著名的d i m e h e l l m a n 协议。在此基础上，他们提出了公 钥密码学的概念。因此，这篇经典论文成为密码学的研究和应用由传统走向现代 的标志。虽然他们没有构造出个具体的公钥密码系统，而只是猜测其存在，但 是他们的工作引起了密码学界的广泛关注。 1 9 7 8 年，r i v e s t 、s h a m i r 和a d l e m a n 提出了著名的r s a 公钥密码体制1 3 l ，这 是第一个实用的公钥密码体制，由于他们的杰出贡献，他们获得了2 0 0 2 年的图灵 奖。2 0 多年来。虽然r s a 公钥密码体制经历了风风雨雨，但是仍然是目前应用最 为广泛的密码体制之一。随后，其他学者和研究人员基于另外的数学难题提出了 大量的公钥密码算法，其中代表方案有：基于大整数分解问题的改进r s a 算法和 r a b i n 算法，基于有限域上的离散对数问题的e i g a m a l 算法1 4 l 以及近来受到广泛关 注的基于圆锥曲线的密码算法等。 近2 0 多年来。公钥密码的研究如雨后春笋，研究者们相继提出了一系列公钥 密码算法，还提出了很多新的概念和应用，如数字签名、认证协议、基于身份的 密码系统、数字签密等。在公钥密码领域也逐渐出现了很多研究课题，如具有附 加性质的数字签名、门限密码系统、数字签密、基于身份的密码学、密钥管理等。 在经历了几千年后密码这门古老的艺术现在已经成为一门公丌而活跃的学科。 1 2 研究进展 1 数字签名理论基础与应用研究现状 2 0 世纪7 0 年代，公钥密码体制的诞生是现代密码学形成的一个重要标志。不 久，基于公钥密码体制的数字签名技术也随之产生。1 9 9 1 年8 美国国家标准局国 家标准技术学会( n a t i o n a li n s t i t u t eo fs t a n d a r da n dt e c h n o l o g y ，n i s t ) 公布了数字签 名标准f d i g i t a ls i g n a t u r es t a n d a r d ，d s s ) ，此标准采用的算法称为d s a 。自数字签 名概念提出之后，学者们做了大量的研究工作，并取得了丰硕的成果。 数字签名方案主要是基于公钥密码体制，实现公钥密码体制的主要方法是基 于如下几个不同的数学难题： ( 1 ) 大素数因子分解难题：最著名的算法是r s a ，还有r a b i n 签名方案【5 l 和 f i a t s h a m i r 签名方案【6 1 等。 ( 2 ) 离散对数难题：这类应用特别广泛，现在的大部分方案如e i g a m a l 型签名 方案、广义e i g a m a l 型签名方案【7 1 、s c h n o r r 签名方梨钔、d s a 方梨9 1 、n e b e r g r u e p p e l 签名方案i i o 】、o k a m o t o 签名方案i i i 】、h m p 认证加密方案【1 2 】等都是基于这 第一章绪论 个问题进行设计的。 ( 3 ) 离散对数和素因子分解相结合难题：h a m 签名方案【1 3 】、s h a o 签名方案【1 4 】 和“签名方案i l 副等。 ( 4 ) 二次剩余难题：r a b i n 签名方案【1 6 】和h e w 签名方案【1 7 1 。 ( 5 ) 椭圆曲线离散对数伺题：以椭圆曲线上的点构成的a b e l i a n 群为背景结构构 造公钥密码体制。自8 0 年代中期引入这个概念以来，受到了密码学界的广泛关注 和研究，取得了大量的成果，已成为密码学重要的一个分支。 对于普通数字签名而言，解决得最基本问题是通过数字签名方式实现了通信 双方的身份认证、通信的消息源真实性认证和消息的完整性认证等。由于各种不 同的应用背景需要和不同的目的，对特殊的数字签名很难全面进行分类，因此大 致可以分为如下几种特殊的数名签名： ( 1 ) 多重签名方案：实现多个用户对同一个消息进行数字签名称为多重数字签 名( d i g i t a lm u l t i s i g n a t u r e ) 。根据签名过程签名顺序的不同，多重数字签名可分为有 序多重数字签名( s e q u e n t i a lm u l t i l s i g n a t u r e ) 和广播多重数字签名( b r o a d c a s t i n g m u l t i s i g n a t u r e ) 。有序多重数字签名是指所有签名者按照一定的顺序进行签名；广 播多重数字签名是指消息的发送者将消息发送给每一位签名者进行签名，然后签 名者将签名消息发送给签名收集者，由收集者对签名消息进行整理而形成签名。 多重签名方案签名的研究参考文献【1 8 3 l 】。 ( 2 ) 群签名方案：19 9 1 年，c h a u m 和h e y s t 首先提出群签名【3 2 1 ( g r o u ps i g n a t u r e ) 的概念，该方案允许合法用户以用户组的名义签名，即代表群体执行签名，验证 者从签名不能判定签名者的真实身份，但能通过群管理员查出真实签名者。具有 签名者匿名和只有权威才能辨认签名者等多种特点，在实际应用中有广泛应用。 ( 3 ) 盲签名方案：1 9 8 2 年，d 。c h a u m 首次提出了盲签名的概念，盲签名1 3 3 是 一种特殊的数字签名，它与通常的数字签名的不同之处在于：签名者并不知道他 所要签发文件的具体内容。正是这一特点，盲签名可广泛应用于许多领域，如电 子投票系统和电子现金系统等。 ( 4 ) 代理签名：m a m b 0 1 3 4 1 和k i m l 3 5 1 等人介绍了代理签( p r o x ys i g n a t u r e ) 的概 念。代理签名是指在一个签名方案中，原始签名人( o r i g i n a ls i g e r ) 授权他的签名权 给代理签名人( p r o x ys i g e r ) ，然后让代理签名人代表原始人生成有效的签名。 此外，还有自证明认证的签名方案【3 6 1 、具有消息恢复的签名方案f 3 刀、门限共 享签名方案1 3 8 】、不可否认签名方案【3 9 1 、零知识证明方案等其它不同形式的数字 签名，吸引了学者们的广泛关注和研究，取得了大量的研究成果。 在基础理论研究的同时，数字签名的应用研究也引起了学术界尤其是密码学 界和计算机网络中的广泛重视。特别是随着电子通信和计算网络的应用，作为数 据安全技术之一的数字签名的地位和作用，越来越显示出其优越性。 环z j 上圆锥曲线数字签名的研究 目前，数字签名技术己应用于商业、金融、军事等领域，特别是电子邮件( e m a i l ) 、电子资金转账( e f t ) 、电子数据交换( e d i ) 、软件分发数据存储和数据完整性 检验的应用。 2 圆锥曲线密码体制的研究进展 圆锥曲线密码学1 4 l j 是1 9 9 8 年由曹珍富教授首次提出，c s c h n o r r 认为，除椭 圆曲线密码以外这是人们最感兴趣的密码算法。在圆锥曲线群上的各项计算比椭 圆曲线群上的更简单，一个令人激动的特征是在其上的编码和解码都很容易被执 行。同时，还可以建立模刀的圆锥曲线群，构造等价于大整数分解的密码。现在已 经知道，圆锥曲线群上的离散对数问题在圆锥曲线的阶和椭圆曲线的阶相同的情 况下，是一个不比椭圆曲线容易的问题。所以，圆锥曲线密码已成为密码学中的 一个重要的研究内容。 圆锥曲线密码的发展历程如下：2 0 世纪9 0 年代，对基于有限域凡上的圆锥 曲线c 。( 口，6 ) 及其在大整数分解和密码算法中应用的研究，引起人们很大的兴趣。 对于有限域上的圆锥曲线c 。( 口，6 ) ，1 9 9 6 年张明志首先引进了c 。( 口，b ) 上的加法 运算0 ，并证明t ( c 。( 口，b ) ，o ) 是一个有限加群【4 2 1 。1 9 9 8 年曹珍富【4 3 】提出了基于 c 上圆锥曲线的公钥密码系统及r s a 的圆锥曲线模拟。由于c 。( 岛6 ) 中明文嵌入、 阶的计算及点的运算都比较容易，这些对设计密码算法具有很强的吸引力。2 0 0 2 年，孙琦等1 4 4 利用整数的标准二进制表示州a f ) 提出一个快速计算群元的整数倍的 算法，将该算法引入圆锥曲线上点的运算可以节约近1 4 的计算量。在2 0 0 4 年信 息安全国际会议上，曹珍富教授做了“密码理论中的若干问题”的主题报告，其 中也介绍了密码学的最新进展，他指出圆锥曲线密码学是密码学发展的一个新方 向。2 0 0 5 年，孙琦、王标等将有限域c 上的圆锥曲线的研究拓展到了环z 。上，并 深入讨论了圆锥曲线e ( 口，b ) 和曲线上的公钥密码体制【4 5 - 4 6 ，为环z 。上的圆锥曲线 数字签名体制奠定了基础。将圆锥曲线公钥密码体制应用到数字签名领域，加强 了原有数字签名的安全性能，使其具有更广泛的应用。 1 3 本文的主要工作 本文在前人研究的基础上，做了如下工作： 1 对杨等人提出的基于环乙上圆锥曲线的e l g a m a l 数字签名方案进行了密钥 恢复攻击，该方案被完全攻破，提出了一种新的数字签名方案； 2 基于新的签名方案构造了两种多重数字签名方案。 第一章绪论 5 1 4 本文的体系结构 第一章论述了信息安全的背景，明确在这样的背景下研究圆锥曲线密码学和 其上的数字签名算法的意义，指出本文的研究内容。 第二章给出了研究圆锥曲线密码需要用到的基础知识：代数知识、主要的公 钥加密体制和签名的算法和环z n 上圆锥曲线的理论。 第三章给出了环z n 上圆锥曲线的r s a 公钥加密体制和数字签名算法，并对文 献【1 9 】提出的数字签名方案进行了攻击，能够从公钥和签名中求解出签名私钥，其 签名方案被完全攻破，并对原签名方案进行了改进，提出了一种新的数字签名方 案。 第四章根据新的方案构造了两种多重数字签名方案。 最后对前四章的内容进行总结和展望，指出存在的问题和未来研究的方向。 第二章预备知识 第二章预备矢1 1 4 识弗早耿宙大。以 本章先介绍研究圆锥曲线密码需要的基础代数和数论中的基础知识，再介绍 比较成熟的公钥密码体制和相应的数字签名算法，最后介绍乙上的圆锥曲线的相 关知识 2 1 数学基础知识 1 同余 整除设整数口，b z ( z 为正整数集) ，b 0 ，如果存在整数c ，使得订= b c ， 则称b 整除a ( 或称d 能被b 整除) ，记为bl 口。这时称b 是口的一个因子( 或称约数) ， 口为6 的倍数。 带余除法 设整数口，b z ，b 0 ，则存在唯一的一对整数g 和，使得 口= q b + ，0 ， 6 。 最大公因子我们用g c d ( a ，b ) 表示a 和b 最大公因子。正整数e 称为口和b 最 大公因子，如果： ( 1 ) c 是口和b 的因子； ( 2 ) a t 和b 的任何因子都是c 的因子。 因为我们求得最大公因子是正数，所以有下面的式子： g c d ( a ，b ) = g c d ( a ，一6 ) = g c d ( - a ，b ) = g c d ( 一a ，- b ) = g c d ( i 口i , ib1 ) 。同样的，0 被所有的非零正数整除，所以有 g c d ( a ，0 ) = jai ，如果g c d ( a ，b ) = l ，则称a 和b 是互素的。 同余设死整数纷才( 矿为整数集) ，对于整数a l ，a 2 ，靠若行除以整数a l ， t 2 所得余数相同，则称，称a l ，日2 模刀同余，记为q 兰口2m o d n ，否则，称q ，口2 模刀 不同余。 同余的基本性质 ( 1 ) 反身性：a 末a ( m o d n ) ； ( 2 ) 对称性：若a 兰b ( m o d n ) ，b 兰a ( m o d n ) ； ( 3 ) 传递性：若口三b ( m o d n ) ，b 三c ( m o d n ) ，口兰c ( m o d n ) ； ( 4 ) 整数口，6 对模数1 同余的充分必要条件是疗 6 一a 。 2 素数 素数设a 是任一大于l 的整数，如果a 的正因子只有1 和它本身，就叫做素 数，否则叫做合数。素数在数论中起着至关重要的作用。任何大于1 的整数a 都能 被因式分解为惟一形式1 4 7 l ：口= a q p 2 电只珥，其中p lp 2 ，p t 都是素数，奶 p 2 0 。 环乙上圆锥曲线数字签名的研究 欧拉函数( 刀) 表示小于正整数r 的且与门互素的正整数个数。很显然， 缈( 1 ) = l ，缈( 2 ) = 1 ，矿( 3 ) = 2 ，对于任一素数p ，有：矽( 力) = p 一1 。现假定有两个 不同的素数p 和q ，p q ，则对r = p q ，有：痧( ) = 痧( p g ) = 痧( p ) ( g ) = ( p 一1 ) ( g - 1 ) 。 定理m 设正整数刀的标准分解是刀= p l a l p z 4 仇唧，则： 。 缈( ”) ：门( 1 一土) ( 1 一上) 。 p、pk 费马定理| 4 7 l 如果p 是素数，a 是不能被p 整除的j 下整数，则： a 产1 暑lm o d p 。 费马定理的另一种等价形式也很有用：如果p 是素数，口是任意j 下整数，则： a p 三am o d p 。 欧拉定理m 对于任何互素的整数口和疗，有：口一( ”) 兰1m o d n ，欧拉定理的另 一种等价形式也很有用：口，( ”m 暑a m o d n 。 中国剩余定理1 4 7 0数论中最有用的基础之一是中国剩余定理，它是用来求一 次同余式组x 暑岛m o dm l ，x 三b 2m o dm 2 ，x 兰仇m o d m 的解的定理。设 m l ，所2 ，m 是k 个两两互素的j 下整数，m = m l m 2 m i ，m = m ，m ，( f = 1 , 2 ，k ) ， 则同余式组有唯一的解：x 三m i m l + m 2 m 2 + + m k m tm o d m ，其中 m ，m ，三l m o d m ，( f = 1 , 2 ，k ) 。 3 原根 整数的次数 ( 1 ) 整数的次数的定义 设m 的大于0 整数，( m ，口) = 1 ，是使口7 三l ( m o d m ) 成立的最小正整数，则，叫 做a 对模数m 的次数。 ( 2 ) 次数的性质 定理1 1 4 7 i ：设a 对模数m 的次数为，a ”暑l ( m o d m ) ，t 是正整数，则，i 玎； 定理2 1 4 7 l ：设口对模数m 的次数为，则，i 缈( 聊) ； 定理3 1 4 7 i ：设口对模数m 的次数为，则1 ，口，口2 oa7 对模数m 两两不同余的； 定理4 | 4 7 | ：设a 对模数m 的次数为，五为正整数，a 。对模数m 的次数为，则 卜志。 原根 ( 1 ) 原根定义 设正整数所，g 且( g ，1 ) = l ，如果g 对m 的次数为伊( m ) ，ng 叫做m 的一个 原根。 ( 2 ) 原根的性质 第二章预备知识 9 定理1 4 7 l ：设设正整数m ，( g ，历) = 1 ，则整数g 是所一个原根的充分必要条件 是g ，9 2 ，g 彻，组成模数m 的一组缩系1 4 7 l 。 4 群、环、域 群、环和域都是数学理论中的一个分支，是抽象代数或近世代数的基本元素。 在抽象代数中，我们关心的是其元素能进行代数运算的集合，也就是说，我们可 以通过很多方法，使集合上的两个元素组合得到集合中的第三个元素。这些运算 方法都遵循特殊的规则，而这些规则又能确定集合的性质。 群群g 有时记作 g ， ，是定义了一个二元运算的集合，这个二元运算可以 表示为，g 中每一个序偶( a ，b ) 通过运算生成g 中的元素( a 6 ) ，并满足一下公理： ( 1 ) 封闭性：如果a 和b 都属于g ，则口b 也属于g ； ( 2 ) 结合律：对于g 中任意元素a 、b 、c ，( 口b ) c = a o c ) 成立； ( 3 ) 单位元：g 中存在一个元素e ，对于g 中任意元素a ，都有a e = e a = a 成 立，称e 为单位元； ( 4 ) 逆元：对于g 中任意元素a ，g 中都存在一个元素a ，使得a a = 口a = e 成 立，称为a 的逆元。 如果一个群的元素是有限的，则称该群为有限群，否则，称该群为无限群。 群的阶等于群中的元素的个数。 ( 5 ) 交换律：对于g 中任意元素口、b ，都有口b = b a 成立。 例如，在普通的加法运算下整数集合是一个交换群，在普通的乘法运算下非 零整数集合是一个交换群。当群中的运算是加法时，其单位元是0 ，口的逆元是一口， 并且减法用以下的规则定义：a b = 口+ ( 一6 ) 。 我们在群中定义求幂运算为重复运用群中的运算，如a 3 = a 口臼，且定义 a o = e 为单位元。如果群中的每一个元素都是一个固定元素口( a g ) 的幂 a ( 七为整) ，则称群g 是循环群，口是群g 的生成元。循环群总是交换群，它可能 是有限群或是无限群。 环环r 记为 足+ ，) ，是一个有两个二元运算的集合，这两个二元运算分别 称为加法和乘法，且对于r 中的任意元素口、b 、c ，满足以下公理： ( 1 卜( 5 ) 即尺关于加法是一个交换群，也就说，r 满足所有的( 1 ) 到( 5 ) 的原则， 称这个交换群为加法群，用o 表示单位元，一a 表示a 的逆元； ( 6 ) 乘法的封闭性：如果口和b 都属于r ，则口6 也属于r ； ( 7 ) 乘法的结合律：对于r 中的任意a 、b 、c ，有成立( a b ) c = a ( b c ) 成立； ( 8 ) 分配律：对于尺中的任意a 、b 、c ，式a ( 6 + c ) = a b + a c 和式0 + b ) c = a c + b c 总成立。 环尺如果还满足以下条件则称为交换环： ( 9 ) 乘法的交换律：对于r 中任意元素a ，b ，都有a b = b a 成立。 1 0 环z 。上圆锥曲线数字签名的研究 环r 如果满足以下条件则称为整环： ( 1 0 ) 乘法单位元：在尺中存在元素 a1 = 1 口= 口成立，并且尺为交换环。 ( 1 1 ) 无零因子：如果r 中元素a 、b ， l ，使得对于冗中的任意的元素口，有 且a b = 0 ，则必有1 2 = 0 或b = 0 。 域域f 记为 ，+ ， ，是有两个二元运算的集合，对于f 中的的任意a ：b 、 c ，满足( 1 ) - ( 1 0 ，这两个二元运算分别称为加法和乘法。 ( 1 2 ) 乘法逆元：对于f 中的的任意1 2 ( 除0 外) ，域f 中都存在一个元素a 1 使得 式1 2 口= 口- 1 口= l 成立。 从本质上说，域就是就是一个集合，可以进行加法、减法、乘法和除法而不能 脱离该集合。除法按以下规则定义：口b = a x b 。 5 有限域t ；r t p ) 我们知道域是满足公理( 1 卜( 1 2 ) 的集合。根据域中元素的个数是不是有限，可 以把域划分成有限域和无限域。无限域在密码学中没有特别的意义，然而有限域 却在许多密码编码学中扮演着重要的角色。有限域的元素的个数必须是一个素数 p 的幂p “，力为整数，记为g 尺矿) 。这里只讨论当n = l 时的有限域g f ( p ) 。 给点一个素数，元素个数为p 的有限域g f ( p ) 定义为整数 o ，1 ，2 ，p 一1 ) 的集 合z 。，其运算为模p 的代数运算。 整数 0 ，1 ，2 ，门一1 ) 的集合z 。在模门的代数运算下构成一个交换坏。进一步研 究发现：z 。中的任意整数有乘法逆元，当且仅当该整数与孵互素时。若1 为素数p 时，g f ( p ) 中的所有的非零整数都与p 互素，因此咖) 中的所有的非零整数都有 乘法逆元，因此g f ( p ) 构成一有限域。 下面我们讨论在g f ( p ) o p 求乘法逆元，当p 值较小时，求g f ( p ) o p t r 素的乘法 逆元很容易。我们只需要构造一个乘法表，所要的结果就可以直接在表中读出。 但是，当p 的值较大时，这种方法是不切实际的。 如果g c d ( m ，b ) = l ，那么b 有模m 的乘法逆元。即对于正整数b m ，存在 b - 磁，使b b 三l m o d m 。可以用扩展的e u c l i d 算法求出b 的乘法逆元。 扩展的e u c l i d 算法： ( 1 ) ( a i ，a 2 ，a 3 ) 卜( 1 , 0 ，肌) ，( 骂，垦，马) 卜( 1 ，0 ，b ) ； ( 2 ) 若b = 0 ，则返还a 3 = g c d ( m ，b ) ，不可逆： ( 3 ) 若b = l ，则返还色= g c d ( m ，b ) ，最兰b m o dm ； iji ( 4 ) q = l 詈i ： ( 5 ) ( 互，e ，五) = ( 彳。一q 蜀，a ：一q b 2 ，a 3 一q 玛) ： ( 6 ) ( 4 ，a 2 ，a 3 ) = ( 且，岛，b 3 ) ； 第二章预备知识 ( 7 ) ( 蜀，岛，马) = ( 正，互，乃) ； ( 8 ) 转2 。 2 2 公钥密码和数字签名体制 2 2 1 公钥密码学基础 众所周知d i m e 和h e l l m a n 在1 9 7 6 年发表了具有开创性的著名论文( ( n e w d i r e c t i o n si nc r y t o g r a p h y ) ) ，首先提出了公开密钥密码的思想。在此新思想的基础 上，很快出现了“非对称密钥密码体制”，即“公钥密码体制 ，由于公钥密码体 制加密和解码的不同，且能公开加密密钥，仅需保密解密密钥，所以公钥密码体 制中存在的密钥管理问题变得相对简单，它有效地解决了传统的单密钥体制密钥 管理的困难，使得公钥密码体制的研究成为密码学界最热门的课题之一。 1 公钥密码体制的基本原理 公钥密码体制使用不同的密钥进行加密和解密运算，并且解密密钥不能从加 密密钥变换中获得。加密密钥称为“公开密钥”简称“公钥”( p u b l i c k e y ) ，解密 密钥称为“私密密钥”简称“私钥”( p r i v a t e k e y ) 。公钥密码系统由五个基本部分 组成： ( 1 ) 明文m ，作为输入源，是可理解的消息或数据； ( 2 ) 加密算法，对明文进行各种运算和变换； ( 3 ) 密钥，密钥独立于明文，算法将根据所用的特定的密钥而产生不同的输出； ( 4 ) 密文，作为算法的输出，看起来完全随机且杂乱的数据，是随机的数据流， 并且其意义是不可理解的； ( 5 ) 解密算法。是加密算法的逆运算，需要通过密钥才能恢复出明文。 公钥加密算法的安全性与密钥的长度和破译密文所需要的计算量密切相关。 从抵抗密码攻击的角度看，原则上，不能说传统密码优于公钥密码，也不能说公 钥密码优于传统密码。公钥密码是一种新兴的加密方法，但传统的基于替换技术 的密码系统并未过时，现有的公钥密码系统所需的计算量较大，取缔传统密码不 太可能。另外，在传统密码系统中，用户与密钥分配中心的交互是一件异常麻烦 的事情，但用公钥密码实现密钥分配则比较简单。 公钥密码算法的安全使用要满足如下三个要求： ( 1 ) 加密算法必须是足够强的。得到一个或多个密文对时也不能破译密文或计 算私钥。通常用一种更强的形式表述为：即使敌手拥有一定数量的密文和产生这 些密文的明文，也不能破译密文或计算私钥。 ( 2 ) 发送者和接受者必须在某种安全的形式下获得私钥并且保证私钥的安全。 环z 。上圆锥曲线数字签名的研究 如果有人窃取了私钥，就能够算出通信的内容。 ( 3 ) 基于己知密文和算法的知识就能破译消息是不实际的，所以不需要保密算 法，仅需要保密私钥。 公钥算法有两个主要弱点：加密速度较慢，一般比对称算法慢几个数量级； 公钥系统对选择明文攻击是脆弱的。因此，公钥算法一般用来加密密钥，不易加 密消息。 2 r s a 加密算法 r s a 加密算法是r o nr i v e s t 、a d is h a m i r 和l e na d l e m a n 三位科学家于19 7 7 年提出并于1 9 7 8 年首次发表的，以三个科学家的名字首字母命名为r s a ，它是最 早提出的满足要求的公钥算法之一。r s a 算法诞生之后，很快成为通用的公钥加 密方法。r s a 体制是一种分组密码，其明文和密文均是0 至疗之间的整数，通常刀 是大正整数，可达到3 0 0 0 b i t 位以上。 下面是算法的描述。 参数选取 ( 1 ) 选取两个保密的大素数p 和q ： ( 2 ) 计算刀= p q ，伊( 疗) = ( p - 1 ) ( q 一1 ) ，其中p 、q 是大素数，缈( 疗) 是搿的欧拉函 数值： ( 3 ) 随机选取整数e ，满足l e t p ( n ) ，且g c d ( e ，妒( 门) ) = l ； ( 4 ) 计算d ，满足e d 言1m o d t p ( n ) ，即d 是e 在模妒( ”) 下的乘法逆元，因e 与( 9 ( ) 互素，由由扩展欧几里得算法可知，它的乘法逆元一定存在； ( 5 ) 以 p ，玎) 为公丌钥， d ) 为秘密钥。 加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于力， 即分组长度小于l o g ，门。然后对每个明文分组m ，作加密运算： c = e ( 聊) 三m 。m o d 解密对密文分组的解密运算为： 搬= d ( c ) 兰c d m o d n r s a 算法的解密过程的j 下确性证明参考文献【4 9 】。 r s a 的缺点 ( 1 ) 产生密钥很麻烦，受到大素数产生技术的限制，因而难以做到一次一密。 ( 2 ) 分组长度太大，为保证安全性，刀应该在1 0 2 4 比特以上，使得运算代价很 高，尤其是速度较慢，较对称密码算法慢几个数量级。随着大数分解技术的发展， 这个长度还在增加，不利于数据格式的标准化。 3 e i g a m a l 加密算法 这一体制由e i g a m a l 在1 9 8 5 年提出，是一种基于离散对数问题的双钥密码体 制，既可用于加密，又可用于签名。 第二章预备知识 f 面是算法的描述。 参数选取 ( 1 ) 令z ，是一个有p 个元素的有限域，p 是一个大素数，令g 是z p 中的一个 本原元【4 7 1 或其生成元。明文集聊为z p ，密文集c 为z p z p ，z p 为有限域的乘 法群，z p z p 表示两个群的笛卡尔乘积。 ( 2 ) 选定私钥口，口 p ； ( 3 ) 选定g ( g 兰g 肿卅) 一”) g 胃( 拱) m o dp ， 在此方案中，对同一消息m ，由于随机数k 不同而有不同的签名值 m ，( ri i5 ) ) 。 攻击的主要形式及其分类 1 根据攻击的作用形式，可以将安全性攻击分为两类。 ( 1 ) 被动攻击 5 0 l 在被动攻击中，只是观察通过一个连接的协议数据单元，以便了解所交换的 数据，并不干扰信息流。如搭线窃听、对文件或程序的非法复制等，以获取他人 的信息。被动攻击本质上是在传输中的偷听或监视，其目的是从传输中获得信息。 典型的被动攻击就是截获，包括析出消息内容和通信量分析。 对于被动攻击，通常难以检测的，因为它们并不会导致数据有任何变化，对 付被动攻击的重点是防止而不是检测，可以采用各种数据加密技术进行数据保护。 ( 2 ) 主动攻击1 5 0 主动攻击是指攻击者对连接中的协议数据单元进行各种处理，这些攻击涉及 某些数据流的篡改或一个虚假流的产生，还可以更改、删除、延迟和重放数据， 甚至将合成的或伪造的协议数据单元送入一个连接中。主动攻击的目的就是试图 改变系统资源或影响系统的j 下常工作。 完全防止主动攻击是相当困难的，对于主动攻击，可采取适当的措施( 如加密 技术和鉴别技术相结合) 加以检测，并从主动攻击引起的任何破坏或时延中予以恢 复。同时，这种检测也具有一定的威慑作用。 2 根据密码攻击者可以利用的数据资源来分类，可分为四类。 ( 1 ) 已知密文攻击 所谓已知密文攻击是指密码攻击者获的密文来破译密码。因为攻击者所能利 用的数据资源仅为密文，因此这是对攻击者最不利的情况； ( 2 ) 已知明文攻击 所谓已知明文攻击是指攻击者根据已经知道的某些明文密文对来破译密码。 近代密码学认为，一个密码算法仅当它能经得起已知明文攻击时才是可取的； ( 3 ) 选择明文攻击 所谓选择明文攻击是指攻击者能够选择明文并获得相应的密文； 1 6 环z n 上圆锥曲线数字签名的研究 ( 4 ) 选择密文攻击 所谓选择密文攻击是指攻击者能够选择密文并获得相应的明文。这种攻击主 要攻击公开密钥密码体制，特别是攻击其构造的数字签名。 2 3 圆锥曲线密码学基础 2 3 1 环磊上的圆锥曲线g ( 口，6 ) 的定义 设z n 是一个模，2 的剩余类环，环乙上圆锥曲线g ( 口，6 ) 是i 司余方程 y 2 暑a x 2b x ( m o d n ) 在乙上的解g ，y ) 的集，这里刀= p q ，p ，q 为两个不同的奇素数，( 口，盯) = p ，甩) = l 。 显然0 = ( o ，o ) g ( 口，6 ) ，且有 g ( a ，6 ) = ( x ，y ) 乙乙ly 2 兰饿2 - b x ( m o d 刀) ) 首先以坐标方式给出g ( a ，6 ) 中的全部有理点：g ( 口，6 ) = c u c 2uc 3u o 其中： c i = 把( ，) = ( 6 ( 口一，2 ) 一，t b ( a 一，2 ) 。1 ) ，( 口一1 2 , 力) = 1 , v t z 。 c ：j 只( ，) 2p p 。1 6 ( 口一，2 ) ，刀叫6 ，( 口一，2 ) 一) ，- t ：, q ) = ，l 【v ，乙，即一兰1 ( m 。dq ) ，( 口_ ，2 ) ( 口- ，2 ) 三l ( m 。d q ) j c 3 ：只( ，) = ( g g 1 6 ( 口一，2 ) ，9 9 叫6 ，( 口一，2 ) 一) ，( 口一，2 ，p ) = ，l 【v tz p g g 。兰l ( m o d p ) ，( 口一，2 ) ( 口一，2 ) 兰l ( m o d p ) j 2 3 2 环磊上圆锥曲线g ( a ，6 ) 中加法0 的定义 下面以坐标方式定义坏z 。上的圆锥曲线g ( a ，6 ) 中的加法运算o ，即对任意 尸= ( _ ，m ) e ( 日，b ) ，q = x ：，y ：) c 。g ，6 ) p 0 9 ，定义如下： 1 当p q 时，尸oq 定义【4 5 i ( 1 ) 若g ：一工。，甩) = l ，则p oq = 鼻( ，) c l ，其中，兰丝二旦( m o d 玎) ： x 2 一x m ( 2 ) 若g ：一而，聆) = p ，贝j j p q = 足( r ) g ，其中，毫丝二丛( m o d g ) ； x 2 一而 ( 3 ) 若g ：一x i 刀) = g ，贝u p oq = b ( ，) c 3 其中，_ 丝二盟t o o d p ) ； 工，一x 1 第二章预备知识1 7 ( 4 ) 若( 屯一五，玎) = r l ，则尸o q = 0 。 2 当尸= 甜，p e 9 = 2 p = 2 ( 而，乃) 的定义4 5 1 ( 5 ) 若，门) ：1 ，贝j 2 p ：鼻( f ) c 。，其中f 暑垒挚兰( m 。d 门) ； z 乃 ( 6 ) 若抚，刀) ：仍贝j j 2 p ：最o ) c 2 ，其中f 兰垄孕兰( m o d g ) ； z l ，。 ( 7 )