（计算机软件与理论专业论文）基于ntru签名的理论研究.pdf

西华大学硕士学位论文 基于n t r u 签名的理论研究 计算机软件与理论专业 研究生扬真真指导教师蔺大正 摘要 网络的飞速发展，政务、商务及日常生活的信息化，使得与公钥密码技术 相伴的数字签名技术有了广泛的应用前景。数字签名之予数字文件，正如手写 签名之于纸质文件，在电子商务和政务中有广泛应用。自从w d i f f i e 和 m h e l l m a n 首先提出了“数字签名”的思想后，相继出现了以r s a 、e 1 m a m m 和d s s 为代表的一些数字签名方案。 n t r u 密码体制是现代公钥密码学领域中的一个重要课题，是一种新型简 单的快速公钥密码，算法的安全性是基于数论中在一个非常大的维数格中寻找 个很短向量的数学难题。该算法具有极高的加密速度和安全性，占用系统的 资源少，又由于其密钥生成非常简单，所以可以做一次一密，它的良好性质已 得到普遍公认。因而在信息安全领域中具有广泛的应用前景，基于此密码方案 的签名体制也受到了高度的关注 本文主要围绕以下几个方面针对基于n t r u 的签名算法进行研究： 由于n t r u 是基于格上困难问题的公钥密码，所以在第三章中首先详细介 绍格的基本概念、基本性质以及格上的几个困难问题s v p ( 最小向量问题) 、 c v p ( 最近向量闯题) 、s b p ( 最小基阀题) 并且系统分析了格上的两个格基归约 算法一高斯算法、u 工算法，在这章的末尾详细介绍n t r u 公钥算法。 详细介绍原有的几个基于n t r u 的签名算法n s s 、n t r u s i 萨、 m e l l e a b i l t yo fn t r u s i g i l 。在这章中提出了一种新的基于n t r u 的签名体制， 此体制中的密钥获取作了特别的处理，而在此后的签名过程中安全性也没有降 低，给出了这种签名体制与n t r u s i 目的比较，并姆此体制的主要部分用 西华大学硕士学位论文 m a t h e m a t i c a 实现；最后提出了一种基于n t r u 的门限签名方案，首次将n t r u 密码体制和秘密共享方案进行了结合。 关键词：格；公钥密码体制；n t r u ；签名；门限； 西华大学硕士学位论文 r e s e a r c ho ns i g n a t u r e sb a s e do nn t r u m d c a n d i d a t ey a n gz h e n - z h e ns u p e r v i s o rl i n d a - z h e n g a b s t r a c t w i t ht h ef a s td e v e l o p m e n to ft h en e t w o r k sa sw e l la st h ea p p e a r a n c eo fm o r e a n dm o r ei n f o r m a t i o ns y s t e m sd e a l i n gw i t hg o v e r n m e n t a la f f a i r s ，c o m m e r c i a l a f f a i r s ，a n de v e nd a i l ya f f a i r s ，d i g i t a ls i g n a t u r e as u b s e to fp u b l i c - k e yc r y p t o l o g y i ss u r et ob ea t t r a c t i v ef o rm o t e ：e x t e n s i v ea p p l i c a t i o n si nt h ec o m i n gy e a r s t h e r e l a t i o n sb e t w e e nd i g i t a ls i g n a t u r ea n dd i g i t a ld o c u m e n ta r es i m i l a rt ot h o s e b e t w e e nt y p i c a lw r i t t e ns i g n a t u r ea n dp a p e rd o c u m e n t a sar e s u l t ，d i g i t a ls i g n a t u r e h a sb e e nw i d e l yu s e di ne - g o v e r n m e n ta n de - c o m m e r c e s i n c et h ei d e ao f “d i g i t a l s i g n a t u r e ”w a sf i r s t l yp r o p o s e d b yw d i f f i ea n dm h e l i m a n ，m a n yd i 百“s i g n a t u r e s h a v eb e e np r o p o s e d ，s u c ha st h ef a m o u ss c h e m e so fr s a , e 1 g a m a l ，d s s ，e t c n t r u c r y p t o s y s t e mi sa ni m p o r t a n ts u b j e c ti nt h ef i e l do fm o d e mp u b l i ck e y c r y p t o g r a p h y , a n di t i san e ws i m p l ep u b l i ck e yc r y p t o g r a p h yo fe x p e d i t i o u s n e s s n e s e c u r i t yo ft h en t r up u b l i ck e yc r y p t o s y s t e mi sb a s e d0 nt h eh a r dp r o b l e m o ff i n d i n ga v e r ys h o r tv e c t o ri nal a t t i c eo fv e r yh i g hd i m e n s i o n t h i sa r i t h m e t i c c a nb eo n e t i m ep a db e c a u s eo fi t st e r r i b l e l yh i g hs p e e do fe n c r y p t i o n , h i g h s e c u r i t y , a n de x t r e m e l yc a o fc o m p u t i n gi t ss e c r e tk e y n t r uc r y p t o s y s t e mh a s t h e s eg o o dc h a r a c t e r s ，a n db e e na c k n o w l e d g e dp r e v a l e n t l y s o i th a sw i d e a p p l i c a t i o np r o s p e c ti ni n f o r m a t i o ns e c u r i t yf i e l d w e l lt h e n , t h es c h e m e so f s i g n a t u r eb a s e do n t h i sc r y p t o s y s t e ma l eg a i n e dh i g l la t t e n t i o n s t 1 l i sp a p e rb e l o wm a i l yd i s c u s s e ss e v e r a la s p e c t sa i ma tt h es i g n a t u r es c h e m e s b a s e do nn t r i j ： i l l 西华大学硕士学位论文 n t r ui sap k cb a s e do nt h ep r o b l e mo fl a t t i c e ，s oi nc h a p t e rt h r e e ，t h e c o n c e p ta n dp r o p e r t yo fl a t t i c ea n ds o m eh a r dp r o b l e m so fl a t t i c e ( s v p ( t h es h o r t e s t v e c t o r p r o b l e m ) ，c v p ( t h e c l o s e s tv e c t o r p r o b l e m ) a n ds b p ( t h es m a l l e s t b a s i s p r o b l e m ) ) a r er e s e a r c h e d a n dt w om e t h o d so fr e d u c i n gt h el a t t i c eb a s e - g a u s s a l g o r i t h m a n dl l la l g o r i t h ma r ea l s oi n t r o d u c e d i nt h ee n do ft h i sc h a p t e r , w e p r e s e n t st h en t r ua r i t h m e t i ci nd e t a i l ，a n dt h em e t h o d so fa t t a c kn t r u a n dw c e s p e c i a l l yi n t r o d u c e dt h el a t t i c eb a s e d a t t a c k si nt h i sc h a r p t e r o t h eo l ds i g n a t u r e ss c h e m e sb a s e do nn t r u n s s ，n t r u s i g na n dm e l l e a b i l t y o fn t r u s i g na r ed i s c u s s e d i nt h i sc h a p t e r , w cp r o p o s e dan e ws i g n a t u r eb a s eo n n t r u ，a d a p t i n gs e c r e th a sb e e ns p e c i a l l yd i s p o s e d ，a n ds e c u r i t yi sn o td e s c e n d a t l a s ti tw a sc a r r i e do u ti tw i t ht h em a t h c m a t i c a a tt h el a s t , w ea l s op r o p o s e da t h r e s h o l ds i g n a t u r eb a s e do nn t r u t h i si st h ef i r s tt i m ec o m b i n e db e t w e e nn t r u a n ds e c r e ts h a r i n g k e y w o r d s ：l a t t i c e ；p k c s ；n t r u ；s i g n a t u r e ；t h r e s h o l d ； 西华大学硕士学位论文 申明 本人申明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示谢意。 本学位论文成果是本人在攻读硕士学位期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签字：芥耘鸯真 导师签字： p 7 年月r 日 7 硝僻f f 月1 日 西华大学硕士学位论文 1 绪论 1 1 引言 随着信息社会的到来，人们在享受信息资源所带来的巨大的利益的同时， 也面临着信息安全的严峻考验。信息安全已经成为世界性的现实问题，信息安 全问题已威胁到国家的政治、经济、军事、文化、意识形态等领域，同时，信 息安全问题也是人们能否保护自己个人隐私的关键。信息安全是社会稳定安全 的必要前提条件。 今天的密码学的应用已经渗透到了社会的各个领域，深入到信息安全的各 个环节和对象主要技术有：数据加密，密码分析，数字签名，信息鉴别，零 知识认证，秘密共享等等。密码学的数学工具也更加丰富，概率统计、数论、 组合、代数、混沌、椭圆曲线等，现代数学的许多领域都有密码学的足迹。密 码学的发展为人们提供了保障网络信息安全的核心技术，加密可以实现信息传 递的机密性，而数字签名可以实现信息的认证性和完整性。数字签名作为传统 手写签名或印章的替代物，在网络社会应用非常广泛 密码学的起源可以追溯到古罗马帝国，但直到1 9 4 9 年s h a n n o n 的一篇文 章“保密通信的信息理论”【1 l 开辟了密码学形成和向前发展的道路，并提出了 通用的通信系统模型。 e v e g r a p h1 1s h a n n o n sc o m m u n i c a t i o ns y s t e mm o d e l 图1 1s h a n n o n 的通信系统模型 西华大学硕士学位论文 通信双方a l i c e 和b o b 共享一个密钥。若发送方a l i c e 想给接收方b o b 发 送一个信息，他利用密钥通过一定的加密规则将信息加密成密文传给b o b ，b o b 利用所掌握的密钥信息恢复明文。自然，e v e 也可能会获得该密文信息，但由 于他不知道a l i c e 和b o b 之间的共享密钥，因而难以知道信道上所传送的明文 信息。 公钥密码的最初思想来于d i f f i c 和h c l l m a n 两人合写的一篇文章“密码学 的新方向”【”，旨在解决对称密码体制中最难解决的两个问题：密钥分配和数 字签名。他们并没有构造出一个具体的公钥体制，但是他们使用有限域上的离 散对数困难问题构造了一个非对称的密钥交换协议在他们思想的启下，各种 公钥密码体制被提出。有基于大整数分解问题的r s a l 3 i 公钥体制和基于子集 和问题的m c r l d c - h e l l m a n t i 背包公钥体制。公钥密码体制在现在已经有很大 发展，其安全性有了多种定义，而且公钥密码体制的种类也有所增加。比如基 于有限域上离散对数困难问题的e l g a m a l 公钥密码体制 i ，基于椭圆曲线上 的离散对数困难问题的椭圆曲线密码体制1 6 1 ，基于有限域的乘法群子群的迹表 示的x t r 密码体制( 其安全性也是基于有限域上离散对数困难问题) ，基于 格( l a t t i c e ) q b 困难问题的密码体制a i t a i d w o r k t ”，g g h i 1 和n t r u t l ”，以及 基于辫群( b r a i dg r o u p ) 的公钥体制【“1 等。 n t r u 是近几年来才出现的一种公钥密码，现已成为公钥密码研究的热 点，在信息安全领域中将具有广泛的应用前景。 1 2 本文的工作 本文关注与n t r u 公钥密码体制在签名和门限签名方面的应用。以现有的 基于n t r u 密码体制的签名算法和秘密共享方案为基础，作出了以下的研究工 作： ( 1 ) 、综述了公钥密码体制。对其思想、基本理论以及其典型的公钥密码算 法进行了介绍，并将n t r u 公钥密码体制与其他体制进行了比较，这样更加突 出了n t r u 公钥密码体制的优势，表明了目前n t r u 公钥密码体制在密码研 2 西华大学硕士学位论文 究和实施中的重要性。 ( 2 ) 、详细介绍了n t r u 公钥密码体制的数学基础和n t r u 公钥算法的过 程。 ( 3 ) 、对现有的基于n t r u 的典型的几个签名体制进行了描述，也说明了其 各自的优缺点，为下一步提出新的签名体制作基础。 ( 4 ) 、提出了一种新的基于n t r u 的签名体制，证明了其工作原理是可行的， 并且与n t r u s i g n 进行了对比，同时用m a t h e m a t i c a 实现了签名算法，将各个 主要的算法以函数的形式展现；本文也利用了m e l l e a b i l i t yo fn t r u s i g n ( - - 种 对n t r u s i g n 的补充) 和b r i c k e l l 秘密共享方案提出了一种基于n t r u 的门限 签名算法。 1 3 本文的组织 本文将在第二章介绍公钥密码体制的思想、基本理论以及对典型的公钥密 码体制进行了简单的介绍第三章中介绍n t r u 公钥密码体制的数学基础，以 及n t r u 公钥加密算法。在第四章中首先介绍目前几种典型的基于n t r u 的 签名体制( n s s ，n t r u s i g n 和m e l l e a b i l i t yo fn t r u s i g n ) ，然后提出一种新的签 名体制，并用m a t h e m a t i e a 加以实现。然后提出一种基于n t r u 和秘密共享方 案的门限签名体制。最后第五章是结束语，总结全文 3 西华大学硕士学位论文 2 预备知识 n t r u 是一种公钥密码体制，它的思想和基本理论雷同与其他的公钥密码 体制，下面我们将对公钥密码体制作简单的介绍。 2 1 公钥密码体制的思想 事实上，现实生活中到处都体现出公钥密码体制的思想，可以说，公钥密 码思想是现实生活的提炼和抽象，学习应用密码学知识也需要结合现实生活， 这样才能把握本质，才能创新。这也是一般科学研究的基本方法。 在d i f f i c 和h c l l m a n 之前，公钥密码学的思想已经由j a m e se l l i s 在1 9 7 0 年1 月的一篇题为“非秘密加密的可能性”的文章中提出。j a m e se l l i s 是电 子通讯安全小组( a 三s g ) 的成员，这个小组是英国政府通信总部( g c h q ) 的一个特别部门。这篇文章没有在公共文献中发表，而是在1 9 9 7 年1 2 月由 g c h q 正式解密的五篇文章中的一篇在这五篇文章中，还有一篇是c l i f f o r d c o c k s 在1 9 7 3 年发表的题为“关于非秘密加密的注记。的文章，其中描述的公 钥密码体制跟r s a 密码体制基本一致 1 9 7 6 年，d i f f i c 和h e l l m a n 在荚国国家计算机大会提出了他们革命性的思 想一公开密钥思想，1 9 7 8 年发表了“n e w d i r c c t i o 璐i n c r y p t o g r a p h y ”的著名论 文，奠定了公钥密码的里程碑。1 9 7 8 年r m c r k l c 也独立地提出了公钥理论。 公钥理论的最大特点是采用两个密钥，把加密密钥和解密密钥分开自公钥密 码体制的思想问世以来，人们提出了大量公钥密码体制的实现方案。所有这些 方案的安全性都是基于求解某个数学难题( 或叫单向陷门函数) 。在这些方案中， 绝大多数要么被攻破，要么太复杂而难以实现，截止目前，具有一定安全性又 能比较容易实现的体制按照所基于的数学难题，有如下四类： ( 1 ) 、基于大整数素分解难题的公钥密码体制，典型的代表有r s a 体制和 r a b i n 体制。 4 西华大学硕士学位论文 ( 2 ) 、基于有限域上离散对数难题的公钥密码体制，其中主要包括e 1 g a m a l 类加密体制和签名方案，d i 颤c h e l l 姐密钥交换方案，s c l l n o r r 签名方案等。 ( 3 ) 、基于椭圆曲线离散对数难题的公钥密码体制。 ( 4 ) 、基于多项式环的密码体制。这是一种新兴的密码体制，自从1 9 9 6 年 被提出以来，得到了学术界的高度关注在后面我们将看到，由于这种密码体 制具有许多独特的性质，使得人们一开始就对它进行了单独考虑。 2 2 公钥密码体制的基本理论 公钥密码体制是用于两个通信者之间，为在公开信道上传输秘密消息的密 码体制。这种密码体制的使用使其他第三方无法读取截获的加密消息，公钥密 码体制描述如下： 记m 是所有可能的明文消息的集合，c 为所有可能密文消息的集合( 加 密的消息) ，k 为所有可能密钥的集合。 一个对称密码系统包括以下元素： 加解密函数对： d k ( b 伽) ) 1 删，所e m ，k e k 两个通信实体彳和b 要进行加密通信，首先需要秘密协商私密钥k e k ( 可 以通过物理的方法或第三可信中心) 当a 要向丑发送消息小e m 时，a 向口发 送密文c 1 e 。伽) ，b 收到密文后，利用解密函数d i 及协商的私密钥进行解密： m1 d t ( c ) ，得到明文消息。此密码体制要求加，解密函数计算容易实现，且在 没有密钥的情况下，有密文无法确定明文和密钥 对称密码体制的缺陷： ( 1 ) 、密钥分配问题：通信双方要进行加密通信，需要通过秘密的安全信道 协商加密密钥，而这种安全信道可能很难实现或代价过高 ( 2 ) 、密钥管理问题：在有多个用户的网络中，任何两个用户之间需要有共 享的私密钥，当网络中的用户弗很大时，需要管理的密钥数目非常大，达到 5 西华大学硕士学位论文 h q 1 ) t 。 ( 3 ) 、没有签名功能：当主体a 收到主体口的电子文档( 电子数据) 时，无 法向第三方证明此电子文档确实来源于口 1 9 7 6 年，d i f f i e 和h e l l m a n 公开发表了一篇论文( n e wd i r e c t i o n si n c r y p m g r a p h y ，论文描述了两个通信主体可以在公开信道上( 不安全信道) 通 信并导出共享的秘密信息，可以利用此秘密信息作为对称加密密钥。交换协议 描述如下： ( 1 ) 、a 和暑公开选择一个有限群g 及一个群元素g g ( 2 ) 、a 生成一个随机整数a ，在群g 中计算g ，并把计算结果在公开信 道上传给矗。 ( 3 ) 、口生成一个随机整数b ，在群g 中计算g ，并把计算结果在公开信 道上传给a 。 ( 4 ) 、a 接收9 6 ，并计算( 9 6 ) 。 ( 5 ) 、占接收9 4 ，并计算( g ) 6 。 此时，a 和占已有了共享的群元素g 。( 可作为共享密钥) ( 此协议是没 有认证的交换协议，但可以通过第三方对交换的消息认证、签名) 。 在实际应用中，公钥可以用来加密和验证数字签名，而私钥可以用来解密 和数字签名。每个通信方公开自己的公钥，关键是保护好自己的私钥。 2 3 公钥密码体制的介绍 定义1 单向函数( o n e - w a yf u n c t i o n ) ：一函数，着满足下列一个条件，则 ，称为单向函数。 ( 1 ) 、对于所有厂定义域的任一工，可以很容易算出y f ( x ) 。 ( 2 ) 、对于几乎所有属于，值域的任一y ，则在计算上不可能求出x ，使得 ，o ) - y 。 定义2 单向陷门函数( o n e - w a yt r a p d o o rf u n c t i o n ) ：一。可逆”函数f 若 满足下列两个条件，则f 称为单向陷门函数 6 西华大学硕士学位论文 ( 1 ) 、对于所有属于f 定义域的任一z ，可以很容易算出y f ( d 。 ( 2 ) 、对于所有属于f 值域的任一) ，则在计算上除非获得陷门，否则不可 能求出x ，使得x i f 1 ( y ) ，f 1 为f 的反函数。但若有一额外数据z ( 称为陷 门) ，则可以容易求出了f “( y ) 。 构造公钥密码体制，需要单向陷门函数族。此函数族应满足对每个k k ， 陷门z 容易得到，即能够得到，i 逆运算的有效算法，但有效算法不能恢复k 给定一陷门单向函数族，每个用户a 随机选取a k ，并公布计算的算 法。e 。称为用户a 的公钥，陷门z q ) 称为爿的私钥。 公钥加密方法：当用户口要向用户4 发送消息m 的密文时，利用a 的公钥 e ，计算，d 伽) ，a 可以用自己的私钥恢复消息埘 公钥签名方法：当a 需要向矗发送一个经过签名的消息m 时，4 向露发送 消息m 及j 一无1 ) ，此时。任何人可以利用a 的公钥e 验证m i 正0 ) 。 2 3 1r s a 密码体制 r s a 体制是公钥体制的最具有典型意义的方法大多数使用公钥体制进行 加密和数字签名的产品和标准都是r s a 算法，例如用于保护电子邮件安全的 p r i v a c ye n h a n c e dm a i l ( p e m ) 和p r e t t yg o o dp r i v a c y ( p g p ) 。它的安全性是基于大 整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今 没有有效的方法予以解决，因此可以确保r s a 算法的安全性。 r s a 是由r i v e s t 、s h a m i ra n d a d l c m a n 在1 9 7 8 年提出的，是d i f f i e h c l l m a n 抽象模型的初次实现。实现方法如下： 每个用户a 选取两个大素数p ，口，并计算n i p q ，妒o ) i ( p 一1 x q 1 ) ，妒o ) 是欧拉函数，且伽p 1 ，任意选取一个正数：1 e s 声o ) ，l e tg c d ( e ，妒0 ) ) - i ， 利用扩展的e u c l i d e a n 算法，计算出正数d ( 1 d 妒0 ) ) ，使其满足 e d 一1 ( m o d 妒o ) ) ，a 的公钥为“e ) ，私钥为d ( p ，曰保密) 注：在不知p ，q 的情况下，由e 计算d 是比较困难的。人们相信攻击r s a 等价于分解大整数雄因此，我们说r s a 的安全性是基于大数分解问题到目 前为止，我们认为，若p ，4 分别超过1 0 0 位十进制数，对拜的分解闯题仍是困 7 西华大学硕士学位论文 难的。 r s a 加密算法( 对消息m 进行加密) ： 加密过程：加密者计算e 沏) - - m 。m o d n ，输出e ( 聊) 。 解密过程：解密者计算小- 陋伽矿m o d n ，得到州- m r s a 加密算法是正确的，因为 伽) ) 。- m 。- 珊m o d 一，所以小- 珊成立。 2 3 2e l g m n a l 密码体制 e i g a m a l 公钥密码体制是由t e 1 g a m a l 于1 9 8 5 年提出的，直到现在仍然是 一个安全性能良好的公钥密码体制。该算法既能用于数据加密也能用于数字签 名，其安全性依赖于计算有限域上离散对数这一难题。下面详细介绍该算法： ( 1 ) 、选取大素数p ，a z ：是一个本原元，p 和口公开。 ( 2 ) 、随机选取整数d ，且使1 式d p 一1 ，计算，一a 。m o d p ，其中卢是 公开的加密体制的公钥，d 是保密的解密密钥 ( 3 ) 、明文空间为z ：，密文空问为z ：z ：。 ( 4 ) 、加密变换为：对任意明文m e z ：，秘密随机选取一个整数七，使 1 七s p - 2 ，则密文为c 一( c l ，c 2 ) ，其中c l a m o d p ，c 2 一m 卢m o d p 。 ( 5 ) 、解密变换：对任意密文c - ( c 。，c ：) e z ；x z ；，明文为m - - c ：( c ? ) 。1 m o d p 在e i g a m a l 公钥密码体制中，密文依赖于明文所和秘密选取的随机数k ， 因此明文空问中的一个明文对应密文空间中的许多不同密文。该算法的最大应 用是以它为基础制定的美国数字签名标准d s s 。 2 3 3 密码体椭圆曲线制( e c c ) 椭圆曲线密码体制是一种相对比较新的技术，已逐渐被人们用作基本的数 字签名系统。我国在椭圆曲线方面的研究也才刚刚起步椭圆曲线作为数字签 名的基本原理大致和r s a 与d s a ( 数字签名算法) 的功能相同，但是数字签 名的产生与认证的速度要比r s a 和d s a 快。下面简单介绍这种密码体制： 此算法基于椭圆曲线离散对数难题，1 9 8 5 年n k o b l i t z 和v m i l l e r 提出将 8 西华大学硕士学位论文 椭圆曲线用于密码算法，分别利用有限域上椭圆曲线的点构成的群，实现了离 散对数密码算法。随后，基于椭圆曲线的数字签名算法，即椭圆曲线数字签名 算法e c d s a ，由i e e et 作组和a n s i ( a m e r c i a nn a t i o n a ls t a n d a r d si n s t i t u t e ) x 9 组织开发，随即展开了椭圆曲线密码学研究除椭圆曲线外，还有人提出 在其他类型的曲线( 如超椭圆曲线) 上实现公钥密码算法，其根据是有限域上 的椭圆曲线上的点群中的离散对数问题( e c d l p ) e c d l p 是比因子分解问题 更难解决的问题，许多密码专家认为它是指数级的难度。从目前已知的最好求 解算法来看，1 6 0 b i t 的椭圆曲线密码算法的安全性相当于1 0 2 4 b i t 的r s a 算法。 此后，有人在椭圆曲线上实现了类似e l g a m a l 的加密算法，以及可恢复明 文的数字签名方案。 出于椭圆曲线密码具有的优点，利用椭圆曲线密码体制不但可以实现高度 安全性，在同等的安全强度下，e c c 则可以较小的开销( 包括所需的计算量、 存储量、带宽，软件和硬件实现的规模等) 和时延( 加密和签名速度高) 实现较高 的安全性，c e r t i c o m 公司对e c c 和r s a 进行7 对比在实现相同的安全性下， e c c 所需要的密钥量比r s a 少得多。 2 3 4n t r u 公钥密码体制 j h o f f s t e i n ，】p i p h e r ，和j h s i l v e r m a n 三位美国数学家于1 9 9 6 年提出了 n t r u 公钥加密体制i ”1 ，这是一个基于多项式环z 】“z ”一1 ) 的密码体制， 其中是一个安全参数。它的安全性是基于数论中在一个维数非常大的格中寻 找一个很短向量的数学难题。就目前来说，n t r u 的安全性和目前有影响的r s a 算法、椭圆曲线加密体制e c c 等算法是一样安全的在相同安全级的前提下， n t r u 算法的速度要比其它公开密钥体制的算法快的多，因为n t r u 算法设计 非常巧妙，整个算法过程只包括小整数的加，乘、模运算，从而提高算法的执 行速度。n t g u 算法的优点意味着可以降低对带宽、处理器、存储器的性能要 求，这也扩大y n r r u 公开密钥体制的应用范围。所以对n t r u 的研究特别是 它的应用的研究应该是很有意义的。 2 0 0 1 年研究人员j h o f f s t e i n ，j p i p h e r ，和j h s i l v e r m a n 利用n t r u 格提出了 9 西华大学硕士学位论文 n s s 体制( n t r u s i g n a t u r es c h e m e ，即n t r u 数字签名体制) 这个体制的安 全性与在某个格中寻找短的向量有关，设计者在提出后不久就观察到了这个弱 点，后来被证明是不安全的。几个月后l l y a m i r o n o v 单独做出了统一的报告。 该体制的签名泄露了私钥信息，导致了一类统计攻击( s t a t i s t i c a la t t a c k ) 。 在2 0 0 1 年欧洲密码会上，设计者对n s s 进行了改进，提出了加强的n s s 以 防止这种统计攻击。改进后的签名仍然泄漏了私钥信恩，不需要私钥知识就可 直接伪造签名攻击，g e n t r y ，j o n s s o n 和s t e r n 发现了这种编码方法的弱点妒1 。 同时，s z y d l o 发现使用同余条件可由长的有效签名恢复密钥n 3 i 。这种弱点实际 上是由于n s s 方法与n t r u 格中近似最近向量问题( a p p r - c v p ) 的不完全联系 造成的。作者再次对n s s 进行了改进，设计出r - n s s ( r e v i s e dn s s ) 使签名点和 信息摘要点与c v p 的联系更为紧密，有效地防止了直接伪造攻击【l l 。2 0 0 1 后， g e n t r y 等证明了一个结果：r n s s 产生的有效签名仍然泄漏了足够的信息，给 攻击者创造了机会。为了防止以上这些攻击，h o f s t e i n j ，g r a h a mn 和p i p h e r j 三位数学家于2 0 0 2 年提出t n t r u s i g n 体制i ”l ，并于2 0 0 3 年对n t r u s i g n 进行 了再次修改，就以前的攻击对n t r u s i g n 进行了安全性分析，基本上该算法能 够抵御以前所发现的攻击几种基于n t r u 的典型签名体制将在第四章中作详 细介绍。 在国外对n r r u 算法的研究、开发和应用进展异常迅速，n t r u 算法被认 为是公开密钥体制中最快的算法，也是比较容易实现的算法。同时国外有很多 研究机构正在对n t r u 算法安全性进行研究，但到目前为止还没有任何理由说 明n t r u 算法是不安全的，我们有理由相信n t r u 算法完全有可能在公开密钥 体制中占有主导地位。 1 0 西华大学硕士学位论文 3 基础知识及其n t r u 公钥算法 n t r u 是基于格中困难问题的一种公钥算法，所以有必要介绍一下格的基 本概念。在这一章中首先介绍什么是格、格上的基本概念、格上的困难问题， 格基归约以及著名的高斯算法和u 工算法，最后介绍n t r u 公钥算法。 3 1 格 在介绍格的性质时我们要经常使用到内积和范数的概念，所以我们先介绍 这两个概念。 3 1 1 内积争向量范数 定义3 1 1 ：数量积t ，是从r 。x r l 到r 上的一个映射( r 表示实数集) ，并 且满足以下性质： 对任给“，v ，w e r 。，a e r 有 1 。线性： + n v ( ，y + 屿v a u ，l ，- a ，v “，y + w - ，y ，+ t ，讳 - u “ 3 恒正性： “，n ) o 对任意的h - 0 标准的内积定义为： 一一，) 机，k 。) ) - m 荟- i 蜥 西华大学硕士学位论文 通常情况下的内积可以写为：h ，y “7 s v ，s 是一个研x m 的正定矩阵。 定义3 1 幺向量范数 如果从向量空间y 到实数尺上的一个映射帅，满足以下条件( 工是向量空间 中的任意一个i 甸f o ： 1 、删2 0 且m 一0 z - 0 ； 2 、恤i 删； 3 、i k + _ ) ，8 b g + l l y g 。 则称l h | 为向量空问y 上的范数 最重要的范数是e u c l i d e a n 范数，也称为2 范数，l l p 是我们熟知的： 肛l ：。妊，工) 善t 2 ( 3 1 1 ) 1 范数： 啪。- 薹毛 ( 3 1 2 ) 通常我们所定义的p 范数如下( p 大于等于1 ) ： ( 釉9 形 ( 3 1 3 ) 我们以后还要使用到的无穷范数： 肛j l m a x 舡。i ，k 。i ，k 。，口 ( 3 1 4 ) 以及中心范数： ：为向量口ta 。，口。，4 。) 的中心范数 2 一萋瓴一心) 2 - m 刍- i 吼2 一i 1 【m 刍- i 。) 2 ， ”去荟q ( 3 1 $ 定理3 1 1 n 6 1 ：设r 与u 均是向量空间c 。上的范数，则向量范数y 和是 等价的，当存在正数和r 2 使得对坛c 。，都有： 西华大学硕士学位论文 ，l ，s p 丘y 3 1 2 格的定义和性质 定义3 1 j ：设“，6 2 ，以为r 。上的h 个线性无关的向量， l 一 h 毛+ 6 2 屯+ + ) ( 3 1 6 ) 则称集合： ( 3 1 7 ) 为格。其中尺为实数集合。名，( j 从1 到玎) 为任意整数。 这时我们称岛，b 2 ，为格l 的一组基，n 称为格l 的维数或者秩。为了简 单起见我们记矩阵口- 协，6 2 ，屯) ，它是以向量6 为行向量组成的矩阵。矩阵 口称为格的生成矩阵( 或基矩阵) 可记格l 为l p ) 。 一般有nt m 。如果n - m 则称格为满维的。 我们把格中元素称为向量或者点。格中任何一个向量都可以用格的基来表 不。 即对格中一点a ，可以写成： a 一4 a + 4 2 6 2 + + 吒瓯 ( 3 1 8 ) 其中q ( f 从i 到雄) 为整数。 对格的生成矩阵( 基) 作以下变换，所得到的矩阵仍为原来格的生成矩阵 1 、交换两行的顺序； 2 、其中某一行乘以一1 ； 3 、某一行的整数倍加到另一行。 显然以上三种矩阵交换等价于对原矩阵右乘上相应的一个模数是为绝对 值为1 的掰嬲整数矩阵。 以上内容可简述为：矩阵a ，b 为格的两个不同的基，即l ( a ) - l ) ，则 存在一个模数是绝对值为1 的整数矩阵c ，使得爿一b c 成立 西华大学硕士学位论文 定义3 1 4 - 格l - 工( 6 l ，6 ：，屯) 的行列式定义为： d e t l = ( d e t 【 ，岛) l 。) ； ( 3 工9 ) 对于内积球，y - n 7 s v ，我们有： d e t l - d e t ( b 7 s 曰) - ( 3 1 1 0 ) 定理3 1 2 ：格的行列式与基的选择无关。 证明：设占，丑为格三的两个不同的基矩阵。由基矩阵的性质我们可以知道 存在一个行列式的绝对值为1 的整数矩阵r 使得i 。b t 成立。设 t 1 12 s v 。 我们有：d e t l - ( d e t 随，屯) l 。汹) i 1 r1 一d e t ( b 7 s b ) 2 一d e t ( t 7 b 7 s b r 、- 一d c t ( ( b t ) 7 s p 丁) ) j 因为有i b t ，所以有： d o t ( l ) - d e t ( b 7 s 历j 。( a c t ( i ，说，。严 一d c t z 任给厅个线形无关的向量6 l ，乞，6 ；属于r 。，我们可以使用格朗姆一斯密 特( g r a m - s c h m i d t ) j e 交化过程获得一组两两正交的向量蚓 6 l ，6 ：，6 3 ，吒， 其中魄一6 l ，包- 以一薹6 ，对于1 s f j 玎 ( 3 1 1 1 ) 1 4 西华大学硕士学位论文 且鲍，一峨屯b b 。，( 1 s ，f n ) 贝l jd e t ( l p ) ) d e t ( p ) ) 。 3 2 格中困难问题及基归约 3 2 1 格中困难问题 在格中主要有以下三个困难问题s v p , c v p 及s b p 。以下将逐一介绍。 定义3 2 1 s v p ( t h es h o r t e s tv e c t o rp r o b l e m ) 即格中最短向量问题： 设是一范数，给定一个格，找这个格上关于范数删的最短向量，即哪范 数值最小用数学语言表示为： 、 s 叫，蚓im ；篇岂劣矿丑乱6 2 a ”册 ( 3 2 1 ) 很多人为了证明它是一个困难问题作出了很多的工作，但是直到1 9 9 8 才 完全被a j t a i l ”1 m i c c i a n c i o t ”1 等人证明。我们在这里不详细叙述。 定义3 2 2 ：c v p ( t h e c l o s e s t v e c t o r p r o b l e m ) l 6 j 题，即最近向量问题： 设| l i 是一范数，给定一个格l 佃) 以及目标f 属于，寻找格中向量x ，使 得忙一t h 最j 、用数学语言表示为： c 肌卜h ，t m , n e n 擎意篆警a 这同样也是一个困难问题，文献n 9 i1 2 0 l 中有相应的证明。 定义3 2 3 ：s b p ( t h es m a l l e s tb a s i sp r o b l e m ) ，最小基问题：给定格基b ，找 到格( 口) 最小的一组基。 对于以上三个问题大都使用格基归约的方法进行求解，其中最著名的就是 商斯算法【2 l i 和u 上算法f 2 2 1 。高斯算法是由高斯提出，它适用于二维格。u 工 堕兰奎堂堡主兰垡笙奎 一 _ _ - _ _ _ _