（计算机应用技术专业论文）多元多项式公钥密码体制的研究与应用.pdf

摘要 摘要 公钥密码技术是网络安全技术中一项非常关键的技术，它在密钥管理、数据 加密以及数字签名与认证中起到不可替代的作用，基于m q 问题的多元多项式公 钥密码体制( m p k c ) 由于其自身安全快速高效的特点，以及其在数字签名和低 成本智能卡中广泛应用的巨大潜在性，近年来得到了迅速发展。 本文详细分析了当今公钥密码学领域的研究现状与发展前景，提出了一种快 速安全的多元多项式公钥密码算法，该算法的加密和解密只使用大数的模乘法运 算，因此具有更快的加解密速度。该公钥密码算法的安全性基于大整数分解的困 难性。论述了多元多项式方程在新型公钥密码学中的应用以及数字签名的研究意 义和研究现状，分析了多元多项式公钥密码体制在数字签名中的应用，综合双极 多元多项式体制和混合多元多项式体制的优点，并在原油醋加密计划的基础上设 计了一种更高安全的数字签名方案，该方案不仅利用了线性化方程攻击的方法， 而且考虑到了对原有平衡油醋签名方案的攻击，因此它不但保持了多元多项式公 钥密码体制的优点，而且具有更高的安全性。 关键词：多元多项式公钥密码数字签名 摘要三 a b s t r a c t t h e p u b l i ck e yc r y p t o s y s t e m sa r ev e r yp i v o t a lt e c h n o l o g yi nn e t w o r ks e c u r i t y f i e l d s ，i th a v ep l a y e d ac r i t i c a lr o l e i nk e ym a n a g e m e n t ，d i g i t a ls i g n a t u r ea n d a u t h e n t i c a t i o n t h em u l t i v a r i a t ep u b l i ck e yc r y p t o s y s t e m s ( m p k c ) b a s e do nm q h a v eb e e nd e v e l o p e dr a p i d l yi nr e c e n ty e a r s ，b e c a u s ei ti t s e l fi sv e r yh i g h l ys a f ea n d e f f i c i e n t ，i th a sv e r yl a r g ep o t e n t i a li na p p l i c a t i o no fl o w c o s ts m a r tc a r d sa n dd i g i t a l s i g n a t u r e i nt h i sp a p e rw ep a r t i c u l a r l ya n a l y z er e s e a r c ha c t u a l i t ya n dd e v e l o p m e n t f o r e g r o u n do fp k cn o w a d a y s ，b r i n g f o r w a r daf a s ta n ds a f ea l g o r i t h m ，t h en e w a l g o r i t h mu s e sc h i n e s er e m a i n d e rt h e o r e mt oh i d et h et r a p d o o ri n f o r m a t i o n t h es p e e d o ft h ec r y p t o g r a p h i cs y s t e mi sh i g hi nt h a to n l ys e v e r a lm o d u l a rm u l t i p l i c a t i o n sa n da m u l t i p l i c a t i o nf o rl o w d i m e n s i o n a lm a t r i xa n dv e c t o ra r eu s e dd u r i n ge n c r y p t i o na n d d e c r y p t i o n t h es e c u r i t yo f t h en e ws y s t e mi sb a s e do nt h ei n t r a c t a b i l i t ya s s u m p t i o no f i n t e g e rf a c t o r i z a t i o n a n a l y z et h ea p p l i c a t i o no f m u l t i v a r i a t ep u b l i ck e yc r y p t o s y s t e m s i nd i g i t a ls i g n a t u r e w ed i s c u s sm u l t i v a r i a t ee q u a t i o n s a p p l i c a t i o n si np k ca n dt h e t h e o r yo fd i g i t a ls i g n a t u r ea n ds i g n c r y p t i o n ，b a s e do nt h et w ok i n d so fm u l t i v a r i a t e p u b l i ck e yc r y p t o s y s t e m s ，w ed e s i g n e do n eam o r es e c u r ed i g i t a ls i g n a t u r es c h e m e b a s e do nt h eo i l v e n e g a rs c h e m eo fm p k c m i ss c h e m eu s e st h et h em e t h o do f l i n e a r i z a t i o ne q u a t i o n sa t t a c k s ，a n dc o n c e mt h ea t t a c k sa g a i n s tt h eb a l a n c e do i l v i n e g a r d i g i t a ls i g n a t u r es c h e m e ，s oi th a sn o to n l yt h ev i r t u eo fm p k c ，b u ta l s om o r es e c u r i t y k e y w o r d s ：m u l t i v a r i a t e p u b l i ck e yc r y p t o s y s t e m s d i g i t a ls i g n a t u r e 西安电子科技大学 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容外，论文中不包 含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其 它教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果署名单位仍然为西安电子科技大学，学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在年解密后使用本授权书。 本人签名：逊垄至 导师签名： 同期：造显：圣：丕 f l e a ：一越昏参， 第一章绪论 第一章绪论弟一早三百下匕 1 1 论文的研究背景 信息科技的迅速发展，i n t e m e t 已成为全球重要的信息传播工具。作为一种战 略资源，信息的应用也从原来的军事、科技、文化和商业渗透到当今社会的各个 领域，在社会生产、生活中的作用日益显著。传播、共享和自增殖是信息的固有 属性，与此同时，又要求信息的传播是可控的，共享是授权的，增殖是确认的。 因此在任何情况下，信息的安全和可靠必须是保证的。i n t e m e t 是一种开放和标准 的面向所有用户的技术，其资源通过网络共享。资源共享和信息安全是一对矛盾。 自i n t e m e t 问世以来，资源共享和信息安全一直作为一对矛盾体而存在着，计算 机网络资源共享的进一步加强随之而来的信息安全问题也日益突出，各种计算机 病毒和网上黑客( h a c k e r s ) 对i n t e m e t 的攻击越来越激烈，许多信息数据遭受破 坏的事例不胜枚举。 加密技术是信息安全的核心技术，已经渗透到大部分安全产品之中，并正向 芯片化方向发展。通过数据加密技术可以在一定程度上提高数据传输的安全性， 保证传输数据的完整性。信息安全技术是- - f - i 综合的学科，它涉及信息论、计算 机科学、密码学等多方面的知识，它的主要任务是研究计算机系统和通信网络内 信息的保护方法以实现系统内信息的安全、保密、真实和完整。数据保密变换或 者密码技术，是对计算机信息进行保护的最实用和最可靠的方法。密码学就是研 究数据保密变换的学科，是一门古老而深奥的学科，它对一般人来说是陌生的， 因为长期以来，它只在很小的范围内使用，如情报部门等。计算机密码学是研究 信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是- - f - 新兴的 学科。随着计算机网络和计算机通信技术的发展，计算机密码学得到前所未有的 重视并普及和发展起来。在国外，它已成为计算机安全的研究方向。密码是实现 秘密通信的主要手段，是隐蔽语言、文字、图像的特种符号。凡是用特种符号按 照通信双方约定的方法把电文的原形隐蔽起来，不为第三者识别的通信方式称为 密码通信。在计算机通信中，采用密码技术将信息隐藏起来，在将隐藏后的信息 传输出去，使信息在传输过程中即使被窃取或截获，窃取者也不能了解信息的内 容，从而保证信息传输的安全。 密码体制从原理上可分为两大类：即单钥体制和公钥体制，或称为对称密码 体制和双钥密码体制。单钥体制的加密密钥和解密密钥相同。采用单钥体制的系 2 一 多元多项式公钥密码体制的研究与应用 统的保密性主要取决于密钥的保密性，与算法的保密性无关，即由密文和加解密 算法不可能得到明文。换句话说，算法无法保密，需保密的仅是密钥。根据单钥 体制的这种特点，单钥加密算法可通过低费用的芯片来实现。密钥可由发送方产 生然后再经一个安全可靠的途径送至接收方，或由第三方产生后安全可靠地分配 给通信双方。如何产生满足保密要求的密钥以及如何将密钥安全可靠地分配给通 信双方是这类体制设计和实现的主要课题。密钥产生、分配、存储、销毁等问题， 统称为密钥管理。这是影响系统安全的关键因素，即使密码算法再好，若密钥管 理问题处理不好，就很难保证信息的安全。单钥体制对明文消息的加密有两种方 式：一是明文消息按字符逐位地加密，称为流密码；另一种将明文消息分组，逐 组地进行加密，称为分组密码。 公钥体制是每个用户都有两个确定的密钥，一个是用来公开的，可以像电话 号码一样进行注册公布；另一个是秘密的，用户个人持有。因此公钥钥体制又称 为双钥体制。这种体制的主要特点是将加密和解密能力分开，因而可以实现多个 用户加密的消息只能由一个用户解读，或一个用户加密的消息多个用户可以解密。 前者实现保密通信，后者用于数字签名。 公钥密码的发展是整个密码学发展史中最伟大的一次革命，也可以说是唯一 的一次革命。在这种体制以前的所有密码体制都是替换和置换这些方法。而公钥 密码不再是基于这些方法，而是基于数学函数，并且算法是以非对称的形式使用 两个密钥，这在消息的保密性、密钥分配和认证领域有着重要而深刻的意义。 传统的密码体制存在两个非常困难的问题，一是在密钥分配时要求通信双方 已经共享一个密钥，而该密钥已经通过某种途经分配给双方，或者利用密钥分配 中心，但是这违背了密码学的精髓，就是在通信过程中完全保持秘密，更有甚者， 这些密钥可能因为盗窃或索取而被泄密；另一个是数字签名问题，就是能否设计 一种方法像手写签名那样，确保信息来源于某特定的人，并且各方对此均无异议。 1 9 7 6 年d i 腩和h e l l m a n 在密码学的新方向1 6 j 一文中针对上述两个问题提出了公钥 密码体制的概念。这种体制有两种加密模型：一种用来传送对称加密的密钥，另 一种用来数字签名。 在过去的三十多年，公钥密码学得到了迅速的发展，出现了许多公钥密码算 法，并且也有很多成熟的产品投入了应用，其中相当一部分算法的陷门函数是基 于大整数分解和循环群上离散对数问题这两大数学难题实现的。目前主要有两大 类型的公钥密码系统是安全实用的：( 1 ) 基于大整数因子分解问题的，其中最典型 的代表是r s a l7 j 体制；( 2 ) 基于离散对数f - j 题的，如e i g a m a l 公钥密码体制和影 响比较大的椭圆曲线公钥密码体制。r s a 算法是第一个能同时用于加密和数字签 名的算法，也易于理解和操作。r s a 是被研究得最广泛的公钥算法，从提出到现在 第一章绪论 三 已经二十多年，经历了各种攻击的考验，逐渐人们接受，普遍认为是目前最优秀的 公钥方案之一。r s a 公钥算法的安全性依靠的是，目前还没有快速的方法把较大 的整数分解为两个素数的乘积，近年来由于在整数分解领域技术的快速发展，比 如数域筛技术和基于椭圆曲线的算法等，r s a 必须使用非常大的参数才能保证必 要的安全水平，现在一个安全的r s a 公钥加密体制至少需要一个拥有1 0 0 0 位二 进制数的n 来表是两个素数的乘积，带着这么巨大的参数进行加密和解密运算时， 运行速度之慢、效率之低是可想而知的。这种现象对于计算能力和存储空间受限 的“小 位计算设备而言更是不可容忍的，比如手机和智能卡，还有无线网络感 应器和r f i d 等i 随着科学的发展和技术的进步，不但r s a ，还有基于有限域上 乘法群的离散对数问题( d l p ) 设计的比如e i g a m a l 加密体制很快地趋于老化， 主要的原因是分解技术和有限域中解决d l p 类似的方法的巨大进步。r s a 的安全 性依赖于大数的因子分解，但并没有从理论上证明破译r s a 的难度与大数分解难 度等价，即r s a 的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学 界多数人士倾向于因子分解不是n p 问题。r s a 的缺点主要有：产生密钥很麻烦， 受到素数产生技术的限制，因而难以做到一次一密；分组长度太大，为保证安全性， 至少也要6 0 0b i t s 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几 个数量级，且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标 准化。 公钥密码体制的迅猛发展，涌现了r s a 等一些基于数论的公钥密码体制。这 些基于数论的公钥密码体制，其安全性都是基于数论中某个困难问题，例如因子 分解问题和离散对数问题。但是，由于s h o r 攻击方法【1 3 】的出现，它能够利用量子 计算机上在多项式时间内解决因子分解问题和离散对数问题。这就提出了一个新 问题，那就是对如何构造能够出新的公钥密码体制，使其能抵御未来基于量子计 算机的攻击方法。目前一个研究思路是利用有限域上的多变量多项式集合。这种 思路基于一个已经被证明的定理，那就是求解一个在有限域上的二次以上的多元 多项式方程组是一个n p c 问题1 4 6 j 。在过去的十年中，许多密码学家在这个领域 做了大量工作。 多元多项式公钥密码体制( m p k c ) 是众多可替代当前主流公钥密码的方向 之一，它的陷门信息是由一组二次多元方程( m q ) 来携带的，而这组多元多项 式方程是建立在一个有限域的基础上的，求解这类方程组已经被证明是个n p 困 难性的问题，当然就这个问题本身并不能保证公钥体制是安全的。量子计算机对 于解决这类问题也没有特别的优势，虽然不希望出现高效求解多元多项式方程算 法。另一方面，谁也没有证明大整数分解是n p 困难性问题，当然也没有证据表 明它到底属于哪一类问题。但是量子计算机是非常适合解决这类问题的。 多元多项式公钥密码体制的研究与应用 因此对于安全性基于数论难题的密码体制，比如r s a 的安全基于整数分解难 题等，m p k c 越来越被一部分人认为是一个非常不错的替代。更重要的是m p k c s 在运算效率上远远优于基于数论的一些公钥体制。到目前已经出现了许多基于 m q 的公钥密码方案，比如m a t s u m o t o i m a i l 4 7 1 ， s f l a s h 4 引，h f e t 4 引， o i l v i n e g a r 5 0 1 ，h f e v l 4 9 】，t t m 【5 l l ，r a i n b o w 5 2 】等，并且一些m p k c s 非常适 合运算能力和存储空间较弱的计算设备，比如智能卡、无线网络传感器和r f i d s 等。事实上，f l a s h ，一个多元多项式签名方案，已经被n e s s i e 确定为安全标 准【4 3 1 。 本文对基于m q 问题的多元多项式公钥加密体制做了一些初步的探索，提出 了一个快速加密算法，设计了一个安全性较高的数字签名方案。 1 2 论文内容安排 本文的研究结果及内容安排如下： 第一章绪论部分描述和分析了论文的研究背景，介绍论文的章节内容安排。 第二章首先详细论述了当前公钥密码学面临的几个很现实的问题与紧迫性， 得出人们必须去开发更多而且更安全的公钥密码算法，然后描述了快速公钥密码 的研究热点与现状，简单介绍了新型公钥密码体制多元多项式公钥密码体制 ( m p k c ) 两类典型的代表双极体制和混合体制，最后阐述了数字签名的意义和研 究现状。 第三章首先介绍和分析了现存著名的多元多项式公钥密码算法，然后给出了 一种快速安全的多元多项式公钥密码算法。该算法只使用大数的模乘法运算，因 此具有更快的加解密速度，该公钥密码算法的安全性基于大整数分解的困难性。 第四章是论文的另一项主要工作，设计了一个具有较高安全性的数字签名方 案，它是在原有油醋加密变换基础上进行改进的，能抵抗目前现有的关于多元多 项式公钥体制的攻击。 第五章结束语部分对论文的主要贡献中存在的问题作了描述，并对研究的前 景作出进一步的展望。 第二二章多元多项式公钥密码与数字签名 第二章多元多项式公钥密码与数字签名 2 1 公钥密码学的现状 自从1 9 7 6 年公钥密码学的概念引入以来，公钥密码学一直是密码学中研究 的热点之一。公钥密码学不仅解决了数字签名和对称密码中需要事先共享加密密 钥的问题，而且也极大地方便了密钥管理。公钥密码算法强大的安全功能本应得 到最广泛的应用，然而，需要注意的是，现在主流的公钥密码算法大都是基于整 数分解或者离散对数问题，其速度难以得到保证。而另一方面，公钥密码在无线 网络如a dh o e 网络以及传感器网络中的应用需要这些算法具有快速加解密的功 能。关于主流的公钥密码，这里指出几个事实。 2 1 1 当前公钥密码面临的问题 第一，公钥密码学经过了3 0 年的发展，虽然密码学界提出了许多公钥密码 算法，然而尚未被攻破的公钥密码算法的种类和数量都屈指可数。目前来看，比 较成熟的、安全性能够得到普遍认可的大概只有基于整数分解的、基于离散对数 问题的和n t r u 公钥密码算法1 8 j 。为了不致使一类或几类公钥密码算法的破解会 导致整个公钥密码学的覆灭，因此，需要更多的可供选择的公钥密码算法。 第二，基于整数分解问题和离散对数问题的公钥密码算法，如r s a 1 7 1 、 d i f f i e h e l l m a l l 【6 1 、e lg a i n a l 【9 】和e c c t l 0 , 1 1 1 等都使用了运算量大的模指数运算，因 此，这些算法的计算复杂度都是三次的( r s a 的加密可以通过使用小指数来降低 复杂度，解密也可以通过中国剩余定理来提高解密速度，然而r s a 无法同时加 快加密和解密速度) 。计算复杂度高一方面意味着效率低，另一方面，当安全参数 长度提高时，算法的计算量并不是线性增加的，比如说，如果安全参数的长度提 高一倍，则这些算法的计算量则要增加七倍。随着现代网络技术的发展，各种无 线网络如a dh o e 网络以及传感器网络越来越得到重视，而这些计算复杂度较高 的密码算法是无法在这些资源受限的环境中得到应用的。 第三，整数分解和离散对数问题是两个已经经过充分讨论的数学困难问题， 虽然它们的困难性已经得到了普遍认可，但是，这些问题存在亚指数求解算法( 有 限域乘法群上的离散对数存在亚指数求解算法，而椭圆曲线上的有理点构成的加 法群上的离散对数问题则还没有发现有亚指数求解算法) 。因此，为达到一定的安 6 一 多元多项式公钥密码体制的研究与应用 全性，这些密码算法的密钥长度就必须足够长，这会降低这些密码算法的实现速 度，同时也制约了这些密码算法的进一步应用。另一方面，随着安全性的强化和 安全级别的提高，这些存在压指数攻击算法的密码体制的密钥参数会增长得更快。 从表2 1 【1 2 1 列出的r s a 和e c c 的密钥长度和安全级别之间的对应关系可以看出， 随着安全级别的提高，r s a 的密钥长度增长的更快。 表2 1r s a 和e c c 的密钥长度和安全级别之间的对应关系 安全级别 4 8 5 6 6 48 01 1 21 2 81 6 01 9 22 5 6 r s a4 8 06 4 08 1 61 2 4 8 2 4 3 23 2 4 85 3 1 27 9 3 61 5 4 2 4 e c c9 61 1 21 2 81 6 02 2 42 5 63 2 03 8 45 1 2 第四，整数分解和离散对数问题是两个非常相似的问题，用于分解整数的算 法可以经过修改用来求解离散对数问题，反之亦然，因此，这两类公钥密码算法 一旦有一类被攻破，则另一类算法的安全性也会遭受灭顶之灾。因此，从这一方 面考虑，也需要更多种类的公钥密码算法。 第五，s h o r 已经证明了，使用量子计算机可以有效地分解整数和求解离散对 数问题【1 3 j 。因此，为了抵抗量子计算机对公钥密码学造成的威胁，也需要设计一 些安全性不基于数论困难问题的能够抵抗量子攻击的公钥密码算法。 第六，多项式时间的确定性素性判定算法【1 4 j 的出现也让密码学家重新审视包 括整数分解在内的数论问题。素性判定问题过去也一直被认为可能是一个困难问 题，不会存在有效的确定性的多项式时间算法。然而事实并非如此，因此有些人 就怀疑整数分解和离散对数问题可能也未必如想象的那么困难。从这一方面考虑， 也需要更多种类的公钥密码算法。 综上所述，无论出于安全性方面的考虑还是出自效率方面的考虑，都需要更 多的公钥密码算法。 2 1 2 公钥密码学的研究热点 目前来看，公钥密码学的研究热点主要集中在以下几个方面。 1 新型快速公钥密码的设计与分析。从密码算法计算复杂度的一般表达式 o ( k “) 来看，应当存在两种设计快速公钥密码算法的指导路线。其一就是所设计 的公钥密码算法的计算复杂度要低，即n 必须要小，比如n t r u ；其二就是所设 计的密码算法应该能够以相对较短的密钥参数( 即k 小) 达到相对较高的安全级 别，如e c c 和x t r1 1 5 1 。可以参阅文献 1 6 ，1 7 ，1 8 】。 2 可证明安全性的研究。主要包括对基于整数分解和离散对数问题的实用的 规约比较紧的公钥密码算法的研究，对具有特殊性质的公钥密码算法( 如门限加 密，混合加密，基于身份的密码，签密算法等) 的可证明安全性定义的研究，对 第二二章多元多项式公钥密码与数字签名 构造可证明安全的公钥密码算法的通用方法的研究，对标准模型下可证明安全的 公钥密码算法的研究等i l 圳。 3 抽象公钥密码学。公钥密码学的研究领域之一就是抛丌具体的公钥密码算 法从抽象层面上对公钥密码进行研究，笔者把这一研究领域成为抽象公钥密码学。 其研究内容包括：对各种数学困难问题之间的联系的研究，比如，r s a 问题是否 等价于整数分解【2 0 1 ，离散对数和计算d i f f i e h e l l m a n 以及判定d i f f i e h e l l m a n 问 题之间的关系；对各种可证明安全性定义之间的关系的研究，比如，i n d c c a 2 等 价于n m c c a 2 等；研究如何从一个满足低级别安全性定义的公钥密码算法构造 满足高级别安全性定义的公钥密码算法，即对构造满足可证明安全性目标的公钥 密码算法的普适方法的研究，比如，研究如何从一个陷门单向置换函数构造 i n d c c a 2 公钥密码，如何从一个语义安全的公钥密码构造一个i n d c c a 2 公钥 密码；对具有特殊功能的密码算法的可证明安全性定义的研究，比如，如何定义 门限加密方案的安全性和混合加密算法的安全性等；对计算杂性和公钥密码学的 关系的研究，比如，b r a r r a s d 证明了攻破一个基于n p c 问题的公钥密码算法的 问题不可能n p 困难的；对各种密码算法即单向函数、杂凑函数、陷门单向函数、 公钥加密算法、密钥交换算法以及数字签名算法之间的关系的研究，比如，证明 了单向函数和陷门单向函数是等价的，他给出了一个从任意的单向函数构造陷门 单向函数的普适方法。 4 基于i d 的公钥密码学。基于i d 的公钥密码学由于公钥能够从用户的身 份( 如e m a i l 和电话号码) 等导出，因此无需公钥证书，这极大地方便了密钥管 理。 5 基于双线性对的公钥密码学【2 1 1 。双线性对在公钥密码编码学上的应用始 于2 0 0 0 年。双线性对具有良好的数学性质，能够设计具有特殊功能的公钥密码 算法，比如，第一个实用的基于身份的公钥加密方案就是使用双线性对来构造的。 6 具有特殊性质的密码算法的设计与分析。如短签名体制，群签名算法， 基于多个数学困难问题的密码算法等。 7 公钥密码算法在无线网络如无线蜂窝网、a dh o c 网络和传感器网络中的 应用等。可以在文献 2 2 ，2 3 】中找到对当代密码学研究的热点问题的综述。 2 1 3 影响公钥密码算法效率的几个因素 对一个公钥密码算法效率的评估应该从以下几个方面考虑： 1 密文扩展：密文扩展不能太大，太大则意味着传输效率低，比如g m 密 码体制【2 4 j 。如果密文扩展l 的话，该密码算法就是一个陷门单向置换，容易改造 成为一个数字签名体制如r s a 。但是，现代公钥加密体制都要求满足可证明安全 7 一 多元多项式公钥密码体制的研究与虑j j 目标，因此都是概率加密，因此密文扩展都小于1 2 明文块长度：明文块长度既不能太大也不能太小，太小则意味着密文扩展 会很大，因而效率会降低，比如g m 体制。如果明文块长度太大，则用该公钥体 制进行传递密钥时就会显得得不偿失，比如r s a 。 3 密钥生成速度：快速的密钥生成允许频繁地更换密钥，因此可以抵抗多重 传输攻击，比如n t r u 。 4 加解密速度：快速加解密是一个公钥密码能够成为快速公钥的基本要求。 从a n ( 解) 密算法的计算复杂度o ( k n ) 来看，一个密码算法要实现快速的加( 解) 密，它必须复杂度低，即n 小，比如n t r u ，或者安全参数即k 小，如x t r 。 5 密钥长度：密钥长度在确保安全性的前提下要尽量小。如基于隐含域方 ( h f e ) 的公钥密码【2 5 2 6 1 。 一个具体的公钥密码很难在满足安全性要求的情况下还同时满足这些效率方 面的要求，但是针对不同的应用环境，可以选择与之相适应的密码体制。比如， 如果移动终端主要进行解密操作，那么就可以在此系统中使用解密速度较快的公 钥密码。 2 1 4 快速公钥密码的发展现状 如前所述，设计快速公钥密码可以采取两条技术路线。第一，设计计算复杂 度为线性的或二次的公钥密码算法。这些密码算法包括：陷门背包i z7 。，基于矩阵 覆盖的密码算法【2 8 1 ，基于多元多项式的公钥密码体制【2 引，基于格中的数学困难问 题的公钥密码算法，包括m j t a i d w o r k 2 9 1 、g g h 3 0 1 、n t r u 和c a i c u s i c k 3 l 】等算 法，基于辫群的公钥密码算法，基于广义逆矩阵的公钥算法，使用有限非交换群 构造的公钥密码算法，基于群分解的公钥密码算法，基于代数编码理论的公钥密 码算法，如m c e l i e c e 3 2 】，基于多项式重构的密码算法，基于g r o b n e r 基的公钥密 码算法，以及基于d r i n f e l d 模的公钥密码算法等。第二，设计安全参数小的公钥 密码算法。在这方面所取得的研究成果主要集中在对基于离散对数问题的公钥密 码算法的改进和推广上。其中比较重要的公钥密码算法有，e c c ，l u c 3 3 j ，o h p 引， x t r ，和以c e i l i d h 为代表的基于t o r u s 的公钥密码算法【j 引。 陷门背包陷门背包由于其快速加解密的优势和背包问题的n p 完全性在提 出之初就备受关注，甚至被认为是最有发展前途的公钥密码，然而格规约算法的 出现证明了几乎所有的加性陷门背包都是不安全的。陷门背包所面临的境地是： 背包密度如果小于0 9 4 0 8 ，则该陷门背包容易遭受低密度子集和攻击；如果背包 密度大于l ，则会出现解密不唯一的问题，因此一般认为密度大于1 的背包无法 在公钥密码上得到应用。这也正是密码学界普遍认为背包已经死亡了的原因所在。 第一二章多元多项式公钥密码与数字签名 多元多项式公钥密码体制这一类公钥密码体制的安全性同样基于一个n p 完全问题，即，求解有限域上的多元二次多项式组是一个困难问题。这一类公钥 密码体制的出现可追溯到1 9 8 5 年1 3 州，这一算法和1 9 8 8 年提出的另一算、法【4 。7 】都 被证明是不安全的p7 。，直到1 9 9 6 年p a t a r i n 提出了基于隐含域方程和多项式同构 的公钥密码算法，这一类公钥密码才又重新成为公钥密码学上研究的热点之一。 这一类公钥密码算法的种类很多，用以构造陷门的技巧也千差万别，其中大部分 也已经被破解，剩余的一部分尚需密码学家对其进行严格的安全性讨论。此外， 多元二次多项式组问题也是设计一些特殊的密码算法如短公钥加密算法和短签名 算法的重要的数学问题之一。 格公钥密码格公钥密码于1 9 9 6 年提出，代表算法有a i t a i d w o r k 、g g h 、 c a i c u s i c k 以及n t r u 等。这些算法的安全性基于格上的困难问题：最短向量问 题或最近向量问题。a j t a i d w o r k 和g g h 在低维格的情形下都被n g u y e n 破解了 ( 强3 9 1 ，因此要保证密码体制的安全性，必须增加格的维数，由于这两个体制都使 用了矩阵运算，因此矩阵维数的增加必然导致运算量的增加，这就使得a d 公钥 密码体制和g g h 公钥密码体制不实用；a d 体制还会出现解密错误。由于基于 格的公钥体制只进行简单的线性运算，人们希望这样的公钥体制的速度会很快， 因此从9 6 年之后格公钥体制的研究也是密码学的一个热点问题，2 0 0 1 年 s p r i n g e r 专门组织一次格与密码学的专题讨论【4 0 】。n t r u 由于只使用了简单的模 乘法和模求逆运算，因此它的加解密速度快，密钥生成速度也快，而且n t r u 是 迄今为止唯一的增加格的维数而不损害其实用性的格密码体制。目前对格公钥密 码的研究主要集中在对n t r u 算法的安全性分析、基于n t r u 数字签名算法的 设计与分析上。 基于辫群的公钥密码学1 9 9 9 年a n s h e l 等提出了第一个基于辫群上的共 轭问题的密钥交换算法【4 1 1 ，2 0 0 0 年等人提出了基于辫群的公钥加密算法1 4 2 1 。然 而，这两个算法后来都证明是不安全的。因此也有密码学家声称使用辫群是很难 设计出安全的密码算法来的，其理由便是，辫群上的元素只是符号表示而不是数 字系统表示，群运算也只是简单的符号级联不具有数字系统中乘法运算那样良好 的混淆作用。事实上，辫群上还有一些别的数学困难问题，比如求根问题。 基于g r o b n e r 基的公钥密码严格来讲这一类公钥密码算法的安全性是基于 代数上的一个困难问题：理想中元素的判定问题，即，给定一个理想和一个元素， 判定该元素是否属于该理想。这一类算法最早由k o b l i t z 提出，称为p o l l yc r a c k e r 算法【4 3 州，后来等人又提出了e n r o o t 加密算法【4 5 】，然而这些算法都是不安全的。 2 0 0 6 年a a e c c 杂志特设专刊讨论g r o b n e r 基在公钥密码密码学中的应用，其 中l y 提出了p o l l yc r a c k e r 的改进算法p o u y t w 0 1 4 6 1 。g r o b n e r 基理论在公钥密码 密码学以及在对分组密码的分析上必将得到越来越多的重视和研究。 9 一 1 0 多元多项式公钥密码体制的研究与戍用 x t r 型公钥密码x t r 是2 0 0 0 年提出的。简单来讲，x t r 的一个创新之 处在于使用迹来表示有限域乘法群的子群中的元素和元素的幂，合法的用户其加 解密运算只涉及到乘法群的子群这一“小群”，而其安全性却是基于有限域乘法群 上的离散对数问题，因此x t r 能够用较少的比特达到较高的安全性。这一类密 码算法的计算复杂度仍然是三次的，但是这些算法的安全参数比较小，因此效率 相对较高。然而，应当指出，x t r 型密码算法的设计不属于快速公钥密码算法设 计的主流。其原因就在于这些算法构造的难度大技巧性强，以及这些算法的安全 性仍然是基于离散对数问题。 基于代数编码理论的公钥密码算法和基于多项式重构的密码算法需要较多的 代数编码知识，这里不作介绍。基于矩阵覆盖的密码算法，基于广义逆矩阵的公 钥算法，使用有限非交换群构造的公钥密码算法，基于群分解的公钥密码算法以 及基于d r i n f e l d 模的公钥密码算法等都是密码学上昙花一现的成果，这些算法或 者后来被证明是不安全的，或者是在应用上很难实现。 2 1 5 关于可证明安全性的几点注解 公钥密码学上对安全性的讨论有两种方法，其一就是把密码算法公布，如果 很长一段时间都没有有效的攻击方法，就可以认为该密码算法是( 暂时) 安全的， 这种方法笔者称之为枚举安全性；第二种方法就是把密码算法的安全性规约到一 个公认的数学困难问题，即可证明安全性理论。可证明安全性理论出现之前，对 密码算法安全性的讨论都是集中在枚举安全性上。可证明安全性大有标准化的趋 势，可证明安全性理论是现代公钥密码学的研究中不可回避的一个课题。需要指 出这一理论仍然有争议。争议的两个极端情形是，可证明安全理论的支持者往往 都是言必谈可证明安全性；而极端的反对者则认为，公钥密码学上的可证明是不 可能获得的。比如，m e s s a y 教授在i s p e c 2 0 0 6 大会报告上认为，可证明安全性 通过信息理论安全是可以得到的，但是如果使用计算复杂性的理论结果，则不可 能完成可证明安全性。这里想要说的是，可证明安全性理论框架并不是适用于所 有的公钥密码算法。 第一，从计算复杂性和公钥密码学的关系上看。计算复杂性理论上的困难问 题指的是最坏情况下的计算复杂度，它针对的是一个问题而不是一个问题的特例， 而可证明安全性把安全性总是规约到某个问题的某个具体的特例，因此如果不能 保证密码算法所选取的数学困难问题特例的困难性，则可证明安全性就是无本之 木无源之水，换言之，如果一个数学困难问题最困难的特例无法在密码上应用， 则可证明安全性就不适于基于此问题的密码算法。当然，虽然某个数学困难问题 的最坏情况下的特例不能用于密码学，如果能够保证密码算法上所使用的问题的 第二章多元多项式公钥密码j j 数字签名 特例足够困难，此时，可证明安全性是可以应用的。比如，一般来讲，由于解密 唯一性的要求，密码学上所使用的背包问题的背包密度都是小于1 的，而密度为 l + 1 l 0 9 2 n 的背包问题才是最困难的，因此，一般来讲，背包型密码体制选取的 都不是最坏情况下的背包问题。密度 k ”和l 2 ：k ”1 - - - - k ”就像双极体制中定义的那样，而厶：k 7hk 7 是一个 可逆的线性变换。 混合体制得加密和解密过程是：如果要加密明文消息x = ( ，一) ，首先要 把它代入方程霄( 而，矗，舅，虼) = ( 石，历) ， 并且求解方程组 ( 爿，m ，虼) = ( o ，0 ) 可以得到解y = ( 一，吒) 就是对应的密文。要想 解密密文y = ( 爿，丸) ，应该首先计算歹= 厶_ ( y ) ，然后令歹= ( 兄，死) ，再 把y = ( 两，死) 代入方程( _ ，毛，爿，吒) = ( o ，0 ) ，并求解方程 ( 五，兄，瓦) = ( o ，0 ) 。如果用牙表示此方程的解，那么明文就由式子： z = 厶- l ( j ) 产生。 该体制的签名产生和验证过程是：如果要对消息y 7 = ( o o 吒) 进行签名，必 需执行上述的解密过程找到x 7 = ( i ，石：| ) 。任何人可以通过签名是否满足方程组 日( ，一，以) = ( o ，0 ) 来验证签名的合法性。 该体制的公开钥由厅的，个多项式和有限域k 构成；秘密钥主要包括厶，厶和 厶。方程h ( x ，y ) = ( 0 ，0 ) 根据具体情况可以是秘密的也可以是公开的。 该体制的主要思想是用三个变换厶，厶和厶来隐藏方程h ( x ，y ) = ( 0 ，0 ) ， 因为此方程在给定】，的时候很容易求解。和双极体制一样隐藏日的形式通常不必 要的。混合体制想对较少，其中比较有名的就是p a t a r i n 的d r a g o n 体制【5 3 】。 2 2 3 多项式同构方案 多项式同构( i p ) 问题来源于对m p k c s 的寻找秘密钥的攻击，令鼻，t 是两 1 4 _ 一 多元多项式公钥密码体制的研究与戍用 个k ”hk ”多项式变换：f ( x i ，) = ( 兀，厶) 。 i p 问题就是寻找两个尼”，k ”上的可逆线性变换e ，最，并且满足 互( 五，) = 厶。最。厶( 五，) 这个问题和对寻找一个m p k c 的秘密钥的攻击密切相关，例如m i 加密体制， i p 体制首先由p a t a r i n 提出【4 纠，验证的过程就是寻找两个不同变换的同构来进行的。 一个简单的i p 方案就是单密钥i p ( i p l s ) ，它只需要找到变换厶，因为变换厶和 它一样。 2 2 4 多元多项式体制的安全性和效率分析 和其它的公钥密码体制一样，多元多项式体制( m p k c ) 算法也只有是安全 高效的才具有使用价值。现在来讨论一下双极m p k c s 的加密和签名的安全性和 效率。 实际上，任何m p k c 的加密过程都使用了通常是二次的一个多项式变换，使 得一个k ”上的向量变换为一个k ”上的向量。解密的过程就是求逆的过程，即是解 方程f ( 爿，) = y 。这就意味着方程f ( 爿，) = y 对于任何没有附加信息的 人来说必需是非常难解的。因为这是一个被公认的难题，目前解多元多项式方程 唯一的方法就是利用g r o b n e r 基的方法，而且此法具有指数级的复杂度。从严格 的数学定义上来讲，如果加密变换的逆存在的话，它也能被表示为多项式的形式， 因此必需确保逆变换具有非常高的阶。否则可以使用公钥产生足够多的明文一密 文对，很容易地找到加密的逆，从而攻破该体制。 另外也必须保证分解加密变换的组合f = 厶o f o 厶是非常困难的。否则的话， 很容易从公开钥中推断出私密钥。一般情况下这是非常困难的，更精确地讲对于 分解此变换知道的信息接近与零，尤其是分解多变量变换更是被认为非常难的数 学问题。 当然任何公钥体制都是为应用而研究的，这就要求加密和解密必需能快速的 进行。m p k c 的公开钥是一组多元多项式，它必须被存储起来，必须是公开的而 且能很容易的调用，最重要的是这些多项式的值必需能迅速地计算出来。因此， 这些公开多元多项式的度必需相对较小，当然不能是线性的，因为这样的话该体 制的安全将没有保障。一般情况下，公开多项式的度为二。 。 第二章多元多项式公钥密码与数字签名 2 3 1 数字签名的重要意义 2 3 数字签名 数字签名是社会信息化的必然产物和需要。在人们的日常生活及工作中，许 多事务需要经过当事者签名来加以认可。在传统的以书面文件为载体的事务处理 当中，通常采用印章、手写签字、指纹等方式作为书面签名。书面签名得到司法 部门认可，具有法律意义。在数字化的信息社会里，传统的手写签名和印章等书 面签字方式已经难以发挥作用，因此，人们迫切的需要一种类似于书面签名功能 的数字化的签名方法。数字签名技术应运而生。数字签名是给电子文档进行签名 的一种电子方法，可靠、方便又安全。数字签名是指附加在数据单元上的一些数 据，或是对数据单元所做的密码变换，这种数据或变换能使数据单元的接收者确 认数据单元的来源和数据的完整性，并保护数据，防止被人( 如接收者) 进行伪造。 数字签名建立在公开密钥加密和单向散列函数算法组合的基础之上。 签名机制的本质特征是该签名只有通过签名者的私有信息才能产生，也就是 说，一个签名者的签名只能唯一的由他自己产生。当收发双方发生争议时候，第 三方( 仲裁机构) 就能够根据消息上的数