（计算机软件与理论专业论文）ntru的应用研究.pdf

西华大学硕士学位论文 y9 0 6 8 9 7 n t r u 的应用研究 计算机软件与理论专业 研究生周剑蓉指导教师蔺大正 摘要 随着“密码学的新方向”一文的提出，公钥密码的研究揭开了序 幕。在网络化的今天，公钥密码显得尤为重要。n t r u 是一种新型的公 钥密码。本文主要研究基于n t r u 的应用。第一章简单介绍密码学的历 史、分类、公钥密码以及数字签名。由于n t r u 是基于格上困难问题的 公钥密码，所以在第二章中首先详细介绍格的基本概念、基本性质以及 格上的几个困难问题一一s v p ( 最小向量问题) 、c v p ( 最近向量问题) 、 s b p ( 最小基问题) ，并且系统分析了格上的两个格基归约算法一一高斯 算法、l l l 算法，在这章的末尾详细介绍n t r u 公钥算法，并且对它进行 安全分析，尤其介绍了格攻击方法。第三章首先详细介绍几原有的基于 n t r u 的签名算法一一n s s 、r n s s 、n t r u s i g n 。由于n s s 、r n s s 是 已经被攻破的签名算法，所以我们还介绍了成功攻击n s s 以及r n s s 的方法。在这章的最后介绍了利用c v p 问题构造了两个新的基于n t r u 的签名算法，及其它们的优势。第四章介绍了n t r u 在p k i 中的应用。 在第一节首先介绍p k i 的一些基本概念，在第二节给出了一个n t r u 应 用于p k i 的模型并分析其安全性。 关键词：格：公钥密码：n t r u ：签名：p k i 西华大学硕士学位论文 r e s e a r c ho na p p l i c a t i o nb a s e do nn t r u c o m p u t e rs o f t w a r e t h e o r y m d c a n d i d a t ez h o uj i a n r o n gs u p e r v i s o rl i nd a - z h e n g a b s t r a c t a 1 0 n gw i t h t h ea p p e a r a n c eo ft h ep a p e r ，”n e wd i r e c t i o n si n c r y p t o g r a p h y ”，t h ec u r t a i no ft h ep u b l i ck e yc r y p t o s y s t e m ( p k c ) w a su n c l o s e d i nt h en e t w o r k ，t h ep k cise s p e c i a l l yi m p o r t a n t n t r u isan e w p k c ， a n dt h is p a p e ri l i a i n l y d i s c u s s e dt h e a p p l ic a t i o nb a s e do nn t r u i nc h a p t e fo n e ，t h eh is t o r y ， c l a s s i f i e so f c r y p t o s y s t e m ，p k ca n dd i g i t a ls i g n a t u r e a r e i n t r o d u c e d n t r uisap k cb a s e do nt h ep r o b l e mo fl a t t i c e ，s o i nc h a p t e rt w o ，t h ec o e c e p ta n dp r o p e r t yo f1 a t t ic ea n dsomeh a r d p r o b l e m so f1 a t t i c e ( s v p ( t h es h o r t e s tv e c t o rp r o b l e m ) ，c v p ( t h e c 1 0 s e s tv e c t o rp r o b l e m ) a n ds b p ( t h es m a l l e s tb a s i - sp r o b l e m ) ) a r e r 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 e1 a t t i c eb a s e c 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 is c h a p t e r ，w ep r e s e n t st h e n t r ua r i t b m e t i c i nd e t a i l ，a n dt h e m e t h o d so fa t t a c kn t r u a n dw ee 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 e b a s e da t t a c k si nt h isc h a r p t e r a tt h eb e g i n n i n g0 ft h ec h a p t e r t h r e e ，t h e0 1 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 ，r - n s sa n d n t r u s i g na r ed is c u s s e d g e c a u s et h en s s a n dr - n s sh a v e b e e n b r o k e n ，w ea ls op r e s e n tt h em e t h o d st ob r e a kn s sa n dr n s s a tt h e l a s t o f t h ec h a r p t e r w ei n t r o d u c e dt h eu s i n gt h ec v pp r o b l o mt o c o n s t r u c tt w on e ws i n g n a t u r es c h e m e sb a s e dn t r ua n dt h e i r l i 堕兰奎堂堡主堂堡堡壅 a d v a n t a g e s c h a r p e rf o u rs h o w sak e ye x c h a n g ep r o t o c o lb a s e do i l t h en t r u p u b li c k e yc r y p t o s y s t e m i n c h a p t e r f o u rt h e a p l i ( ：a t i o no fp k ib yn t r ua n dt h em o d e la n dt h es t r u c t u r e is j 【l t r o d u e e d k e y w o r d s ：l a t t i c e ，p k c ，n t r u ，s i g n a t u r e ，p k i i l l 西华大学硕士学位论文 1 绪论 1 1 引言 自从人类有了战争，就有了密码，所以密码作为一种技术源远流 长，可以追溯到远古时代，而且还有过自己的辉煌经历。但成为一门 学科则是近2 0 多年的事，这是受计算机科学蓬勃发展的刺激结果。今 天在计算机被广泛应用的信息时代，信息本身就是时间，就是财富。 大量信息用数据形式存放在计算机系统里。信息的传输则通过公共通 道。这些计算机系统和公共通道是不设防的，是很脆弱的，容易受到 攻击和破坏，信息的丢失不容易被发现，而后果是极其严重的。如何 保护信息的安全不仅仅是军事和政府部门感兴趣的问题，各企业事业 单位也愈感迫切。因为在科技高速发展的信息时代，计算机犯罪每年 使他们遭受的损失极其巨大，而且还在发展中。密码是有效而且可行 的保护信息安全的办法。 。 今天的密码学的应用已经渗透到了社会的各个领域，如对计算机 用户的认证、数据加密、网络安全、安全电子投票、安全电子商务和 电子政务、电子支付等。 密码学的起源可以追溯到古罗马帝国，但直到1 9 4 9 年s h a n n o n 的 一篇文章“保密通信的信息理论”开辟了密码学形成和向前发展的 道路。s h a n n o n 首次用概率论的观点对信息源、密码源，接收和截获 的密文进行定量分析和数学描述，提出了通用的通信系统模型。 西华大学硕士学位论文 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 1 i c e 和b o b 共享一个密钥。若发送方a 1 i c e 想给接收 方b o b 发送一个信息，他利用密钥通过一定的加密规则将信息加密成 密文传给b o b ，b o b 利用所掌握的密钥信息恢复明文。自然，e v e 也可 能会获得该密文信息，但由于他不知道a 1 i c e 和b o b 之间的共享密钥， 因而难以知道信道上所传送的明文信息。 在近代密码学上值得一提的大事有两件：一是1 9 7 7 年美国国家标准 局正式公布实施了美国的数据加密标准( d e s ) ，并批准用于非机密单 位及商业上的保密通信。密码学的神秘面纱从此被揭开。二是d i f f i e 和 l e l l m a n 联合写的一篇文章“密码学的新方向”1 ，提出了适应网 路上的保密通信的公钥密码思想，掀起了公钥密码研究的序幕。受他 们思想的启迪，各种公钥密码体制被提出，特别是r s a 口公钥密码的提 出在密码学史上是个里程碑。可以说“没有公钥密码的研究就没有 近代密码学。” 公钥密码的最初思想来于d i f f i e 和h e l l m a n 两人合写的一篇文章 “密码学的新方向”，旨在解决对称密码体制中最难解决的两个问题： 密钥分配和数字签名，以适应网络通信的发展他们并没有构造出一个 具体的公钥体制，但是他们使用有限域上的离散对数困难问题构造了 一个非对称的密钥交换协议。在他们思想的启下，各种公钥密码体制 被提出，有基于大整数分解问题的r s a 1 公钥体制和基于子集和问题的 m e r k l e h e l l m a n ”1 背包公钥体制。公钥密码体制在现在已经有很大发 展，其安全性有了多种定义，而且公钥密码体制的种类也有所增加。 2 西华大学硕士学位论文 比如基于有限域上离散对数困难问题的e l g a m a l 公钥密码体制”1 ，基 于椭圆曲线上的离散对数困难问题的椭圆曲线密码体制”1 ，基于有限 域的乘法群子群的迹表示的x t r 密码体制口1 ( 其安全性也是基于有限域 上离散对数困难问题) ，基于格( ( 1 a t t i c e ) 中困难问题的密码体制 a j t a 卜d w o rk 8 1 。g g h 0 1 和n t r u ”，以及基于辫群( b r a i dg r o u p ) 的公 钥体制1 等。d i f f i e 和h e l l m a r 联合写的一篇文章“密码学的新方向” ”1 ，提出了适应网路上的保密通信的公钥密码思想，掀起了公钥密码 研究的序幕。受他们思想的启迪，各种公钥密码体制被提出，特别是 r s a ”1 公钥密码的提出在密码学史上是一个里程碑。可以说“没有公钥 密码的研究就没有近代密码学。” 1 2 公钥密码体制思想 在d i f f i e 和h e l l m a n 之前，公钥密码学的思想已经由j a m e se l l is 在1 9 7 0 年1 月的一篇题为“非秘密加密的可能性”的文章中提出。j a m e s e l l i s 是电子通讯安全小组( c e s g ) 的成员，这个小组是英国政府通 信总部( g c h q ) 的一个特别部门。这篇文章没有在公共文献中发表， 而是在1 9 9 7 年1 2 月由g c h q 正式解密的五篇文章中的一篇。在这五篇 文章中，还有一篇是c 1 i f f o r dc o c k s 在1 9 7 3 年发表的题为“关于非 秘密加密的注记“的文章，其中描述的公钥密码体制跟r s a 密码体制 基本一致。 1 9 7 6 年，d i f f i e 和h e l i m a n 在美国国家计算机大会提出了他们革 命性的思想一公开密钥思想，1 9 7 8 年发表了“n e wd i r e c t i o f i si n c r y p t o g r a p h y ”的著名论文，奠定了公钥密码的里程碑。1 9 7 8 年 r m e r k l e 也独立地提出了公钥理论。公钥理论最大特点是采用两个密 钥，把加密密钥和解密密钥分开。自公钥密码体制的思想问世以来， 人们提出了大量公钥密码体制的实现方案。所有这些方案的安全性都 是基于求解某个数学难题( 或叫单向陷门函数) 。在这些方案中，绝大 多数要么被攻破，要么太复杂而难以实现，截止目前，具有一定安全 西华大学硕士学位论文 性又能比较容易实现的体制按照所基于的数学难题，有如下三类： ( 1 ) 、基于大整数素分解难题的公钥密码体制，典型的代表有r s a 体 制和r a b i n 体制。 ( 2 ) 、基于有限域上离散对数难题的公钥密码体制，其中主要包括 e l g a m a l 类加密体制和签名方案，d i f f i e h e l l m a n 密钥交换方案， s c h n o r r 签名方案和n y b e r g r u p p e l 签名方案等。 ( 3 ) 、基于椭圆曲线离散对数难题的公钥密码体制。1 9 8 5 年，k o b l i t z 和m i l l e r 最早分别独立地提出了椭圆曲线密码体制。其中包括椭圆曲 线型的d i f f i e - h e l i m a n 密钥交换方案，椭圆曲线型的s c h n o r r 签名方 案和n y b e r g r u p p e l 签名方案等。 它是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制 中的有限循环群所得到的一类密码体制。因此，严格地说它不是一种 新的密码体制，它只是已有密码体制的椭圆曲线型的翻版( 有限域上 的离散对数) 。如果按照构造体制的方式分类，前面的三类可归纳为两 类，椭圆曲线密码应归于基于离散对数问题的密码体制中。但是后面 我们将看到，由于它具有许多独特的性质，使得人们一开始就对它进 行了单独考虑。 1 3 公钥密码体制的基本理论 对称密码体制是用于两个通信者之间，为在公开信道上传输秘密 消息的密码体制。这种密码体制的使用使其他第三方无法读取截获的 加密消息，对称密码体制描述如下： 记m 是所有可能的明文消息的集合，c 为所有可能密文消息的集合 ( 加密的消息) ，k 为所有可能密钥的集合。 一个对称密码系统包括以下元素： 加解密函数对： a g ，f e z 满足下列条件： d 。( e 。( m ) ) = m ，m m k k ， 4 西华大学硕士学位论文 两个通信实体a 和b 要进行加密通信，首先需要秘密协商私密钥 k k ( 可以通过物理的方法或第三可信中心) 。当a 要向b 发送消息 坍e m 时，a 向b 发送密文c = e k 伽) ，8 收到密文后，利用解密函数d 。 及协商的私密钥进行解密：研= d k ( c ) ，得到明文消息。此密码体制要 求加解密函数计算容易实现，且在没有密钥的情况下，又密文无法确 定明文和密钥。 对称密码体制的缺陷： ( 1 ) 、密钥分配问题：通信双方要进行加密通信，需要通过秘密的 安全信道协商加密密钥，而这种安全信道可能很难实现或代价过高。 ( 2 ) 、密钥管理问题：在有多个用户的网络中，任何两个用户之间 需要有共享的私密钥，当网络中的用户n 很大时，需要管理的密钥数 目是非常大兰竺二望。 ( 3 ) 、没有签名功能：当主体a 收到主体b 的电子文档( 电子数据) 时，无法向第三方证明此电子文档确实来源于b 。 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 t i s in c r y p t o g r a p h y ，论文描述了两个通信主体可以在公开信道上( 不 安全信道) 通信并导出共享的秘密信息，可以利用此秘密信息作为对 称加密密钥。交换协议描述如下： ( 1 ) 、a 和b 公开选择一个有限群g 及一个群元素a g 。 ( 2 ) 、a 生成一个随机整数a ，在群g 中计算a8 ，并把计算结果在 公开信道上传给b 。 ( 3 ) 、b 生成一个随机整数b ，在群g 中计算ab ，并把计算结果在 公开信道上传给a 。 ( 4 ) 、a 接收ab ，并计算( a 。) 4 ( 5 ) 、b 接收a4 ，并计算( 口8 ) 6 此时，a 和b 已有了共享的群元素a “( 可作为共享密钥) 。( 此协议 是没有认证的交换协议，但可以通过第三方对交换的消息认证、签名) 。 5 西华大学硕士学位论文 1 4 公钥密码体制介绍 定义1 单向函数( o n e w a yf u n c t i o n ) ：一函数f 若满足下列一个 条件，则f 称为单向函数。 ( 1 ) 、对于所有f 定义域的任一x ，可以很容易算出 f ( x ) = y 。 ( 2 ) 、对于几乎所有属于f 值域的任一y ，则在计算上不可能求出x ， 使得y = f ( x ) 。 定义2 单向陷门函数( o n e w a yt r a p d o o rf u n c t i o r l ) ：一“可逆” 函数f 若满足下列两个条件，则f 称为单向陷门函数。 ( 1 ) 、对于所有属于f 定义域的任一x ，可以很容易算出 f ( x ) = y 。 ( 2 ) 、对于所有属于f 值域的任一y ，则在计算上除非获得陷门， 否则不可能求出x ，使得x = f 1 ( y ) ，f 。为f 的反函数。但若有一额外 数据z ( 称为陷门) ，则可以容易求出x = f 1 ( y ) 。 构造公钥密码体制，需要单向陷门函数( t o f ) 族。此函数族应满足 对每个k e k ，陷门z 容易得到，即能够得到f 。逆运算的有效算法，但 有效算法不能恢复k 。 给定一陷门单向函数族，每个用户a 随机选取a k ，并公布计算 f 。的算法e 。e 。称为用户a 的公钥，陷门z ( a ) 称为a 的私钥。 公钥加密方法：当用户b 要向用户a 发送消息m 的密文时，利用 a 的公钥e 。，计算f 。( m ) ，a 可以用自己的私钥恢复消息m 。 公钥签名方法：当a 需要向b 发送一个经过签名的消息m 时，a 向b 发送消息m 及s = f 。“( m ) ，此时，任何人可以利用a 的公钥e 。验 证m = f 。( s ) 。 群上的陷门单向函数： 设g 是n 阶乘法群，且群上的乘法运算是容易的，即群上任意两 个元素的乘法运算是多项式可计算的，则群的指数运算是容易计算的， 计算方法如下： 6 函华大学硕士学位论文 输入：口g ，f 三 输出：口1 ( 1 ) 设l 2 b t 2 ，b i o ，1 1 ，缸；1 ，是z 的二进制表示 ( 2 ) 令口o a ( 3 ) f o rif r o mt 一1d o w nt ood o 9 一p 0 i f b i t h e n 0 一$ 联 ( 4 ) o u t p u t 口 计算a 。的最多群运算量是2 1 , 0 9 2 。 。 1 4 1r s a 密码体制 r s a 是由r i v e s t 、s h a m i ra n da d l e m a n 在1 9 7 7 年提出，是 d i f f i e - h e l l m a n 抽象模型的初次实现。实现方法如下： 每个用户a 选取两个大素数p ，q ，并计算n = p q ，妒( ) = ( p - 1 ) ( q 一1 ) ， 任意选取e ：1 ses 驴0 ) ，且g o d ( e ，n ) = l ，利用扩展的e u c l i d e a n 算 法，计算d ，1 s dc 妒0 ) ，a 的公钥为( 1 2 ，e ) ，私钥为d ( p ，q 保密) 。 注：在不知p 、q 的情况下，由e 计算d 是比较困难的。人们相信 攻击r s a 等价于分解大整数n 。因此，我们说r s a 的安全性是基于大 数分解问题。到目前为止，我们认为，若p ，q 分别超过1 0 0 位十进制 数，对n 的分解问题仍是困难的。 r s a 加密运算： 明文x ，密文y = x 。m o d n 解密：明文z = y 4 1 4 2b 1 c a m a l 密码体制 ( 1 ) 初始阶段：选择有限群g 及群中的元素n g ，每个用户可以 7 西华大学硕士学位论文 选择一个随机数z ( 用户的私钥) ，计算a7 ( 公开密钥) 我们假 设消息是g 中的元素，且用户a 要向用户b 发送消息m 。 ( 2 ) a 随机生成整数k ，并计算a 。 ( 3 ) a 查找b 的公钥a6 ，并计算f a 6 1 ，m a “。 ( 4 ) a 向b 发送群元素对( a ，m a ”) 。 ( 5 ) b 计算0 ) 6 ，并由此可以恢复消息m 。 e 1 g a m a l 密码体制与d h 体制是等价的，基于离散对数的困难问题。 为实施的安全性及有效性，群g 及元素a e g 的选取应满足下列条件： ( 1 ) 群g 中的运算应“容易”， ( 2 ) 为安全起见，群( a 中的离散对数应是“困难”的。 1 4 3 椭圆曲线密码体制( b e e ) 有限域k 上的椭圆曲线上的点形成一个a b e l i a l l 群。该群上的加 法运算包括有限域上的算术运算。椭圆曲线上的算法在软件和硬件实 现方面都比较容易。1 9 8 5 年，n k o b l i t z 和v m i l le r 首先提出了椭圆 曲线密码体制。有限域上的椭圆的椭圆曲线可以用于实现 d i f f i e h e l l m a n 密钥交换，e 1 g a m a l 、s c h n o r r 、n i s t 签名方案。椭 圆曲线密码体制的数学基础是利用椭圆曲线上的点构成的a b e l i a n 加 法群构造的离散对数的计算困难性。由于椭圆曲线体制比原有的密码 体制( 如r s a 、e 1 g a m a l 、d s a 等) 更具优越性，所以对这一密码体制 的研究和实现迅速普及。 随着计算机技术、通信技术、网络技术和集成电路技术的发展， 保密安全设备的实现技术发生了巨大的变化，其特点是功能化、模块 化、小型化。而安全保密的核心一密钥的存储和算法的实现采用了个人 安全模块技术，从而大大提高了保密安全设备和系统的安全性和可靠 性。在各种安全保密应用中，如身份认证和支付凭证，i c 卡( p c 卡等) 作为个人安全模块技术可提供用户鉴别、访问控制、密钥存储和安全 处理等安全功能。 8 西华大学硕士学位论文 1 9 9 9 年8 月2 2 日，来自六个不同国家的科学家们在c w i ( c w i 是 在荷兰的一个数学和计算机科学的国家研究学会) 的h e r m a nt er i e l e 的带领下，在对r s a 一1 5 5 的攻击中，利用数域筛法( n f s ) 成功的分解 了5 1 2 - b i tr s a 模的素因子。这宣布5 1 2 - b i tr s a 已不再安全。密码 学家们建议使用1 0 2 4 一b i t 模长，预计要保证2 0 年的安全就要选择 12 8 0 一b i t 的模长，增大r s a 的模长带来了实现上的难度。随着大整数 分解和并行处理技术的发展，当前采用的公钥体制必须进一步增长密 钥才能实现相对的安全性。而这样将使其更加复杂、速度更慢。 出于椭圆曲线密码具有的优点，利用椭圆曲线密码体制不但可以 实现高度安全性，在同等的安全强度下，e c c 则可以较小的开销( 包 括所需的计算量、存储量、带宽、软件和硬件实现的规模等) 和时延 ( 加密和签名速度高) 实现较高的安全性，c e r t i c o m 公司对e c c 和r s a 进行了对比。在实现相同的安全性下，e c c 所需要的密钥量比r s a 少 得多。我国在椭圆曲线方面的研究才刚刚起步，十五计划已经把信息 和网络安全作为今后国家发展的重点任务之一，所以在这个时候深入 研究基于椭圆曲线离散对数的公钥密码具有很大的现实意义。 1 4 4n t r 公钥密码体制 1 9 9 6 年三位美国数学家j e f f r e yh 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 ( n u m b e rt h e o r yr e s e a r c hu n i t ) 公开密钥体 制，经过几年的迅速发展与完善，该算法在密码学领域中受到了高度 的重视并在实际应用中取得了很好的效果。n t r u 算法的安全性是基于 数论中在一个非常大的维数格中寻找一个很短向量的数学难题。就目 前来说，n t r u 的安全性和目前有影响的r s a 算法、椭圆曲线加密体制e c c 等算法是一样安全的。在相同安全级的前提下，n t r u 算法的速度要比 其它公开密钥体制的算法快的多，因为n t r u 算法设计非常巧妙，整个 算法过程只包括小整数的加、乘、模运算，从而提高算法的执行速度。 用t u m b e r 软件工具包执行n t r u 的速度比r s a 快1 0 0 多倍。用n t r u 算法产 9 西华人学硕士学位论文 生密钥的速度也很快，n t r u 密钥的b i t 数也较小。n t r u 算法的优点意味 着可以降低对带宽、处理器、存储器的性能要求，这也扩大了n t r u 公 开密钥体制的应用范围。所以对n t r u 的研究特别是它的应用的研究应 该是很有意义的。 n t r u 密码是一个在数学上比r s a 或e 1 g a m a l 密码还要复杂的密码，而 且因为其复杂性和出现的时间相对较短，所以还不能说对其进行了完 全彻底的研究。( 目前据所知) 只有当量子计算机得到应用时n t r u 密 码算法才有可能被破解“，而r s a 和普通的e 1 g a m a l 一定已经被破解了。 自从1 9 9 3 年p e t e r s h o r l 9 9 6 a 发明针对大整数的快速因数分解量子 算法以来，对于r s a 或普通的离散对数密码算法来说，这种可能性对将 来构成威胁。当然，针对其他公钥密码算法的“困难问题”可能也将 发明快速量子算法，但是到那时r s a 和e 1 g a m a l 和密码算法已经被称为 最容易破解的算法了。 在国外对n t r u 算法的研究、开发和应用进展异常迅速，n t r u 算法被 认为是公开密钥体制中最快的算法，也是比较容易实现的算法。同时 国外有很多研究机构正在对n t r u 算法安全性进行研究，但到目前为止 还没有任何理由说明n t r u 算法是不安全的，我们有理由相信n t r u 算法 完全有可能在公开密钥体制中占有主导地位。 1 5 本文的章节安排 本文在第二章首先介绍了n t r u 公钥算法中使用到的基础知识一 一格以及格基规约，接着介绍n t r u 公钥算法，简单分析它的安全性由 于签名是公钥密码的一大应用，所以我们将在第三章中详细介绍基于 n t r u 之上的几个签名算法：n s s 、r - n s s 、n t r u s i g n ，以及几个成功攻击 n s s 、r - n s s 的方案。在最后介绍两个新的签名算法。第四章介绍n t r u 在p k 中的应用。 1 0 西华大学硕士学位论文 2 基础知识及其n t r u 公钥算法 n t r u 是基于格中困难问题的一种公钥算法，所以有必要介绍一 下格的基本概念。在这一章中首先介绍什么是格、格上的基本概念、 格上的困难问题，格基归约以及著名的l l l 算法，最后介绍n t r u 公钥 算法，并对它进行分析。 2 1 格 在介绍格的性质时我们要经常使用到内积和范数的概念，所以我 们先介绍这两个概念。 2 1 1 内积和向量范数 定义2 1 1 ：数量积 是从r ”r ”到r 上的一个映射( r 表示实数 集) ，并且满足以下性质： 对任给u ，v ，w e r “， 九r 有 1 线旋性： ( “+ v 屿v ) = ( “，v ) + ( w ，v ) ( 地，v ) = 九( h ，v ) ( u , v + w ) = ( “，v ) + ( “，w ) ( “，) w ) ；k ( “，v ) 2 对称性： ( h ，v ) = ( v ，“) 3 恒正性： ( h ，) o 对任意的“一0 标准的内积定义为： ( ( 。，“，- ，“。一。) ， - - - 一。) ) = m 荟- i “，v 1 1 西华大学硕士学位论文 遍常情况f 的内积q 以写为：扛，v ) = h 1 s v ， s 是一个h i x m 的正 定矩阵。 定义2 1 2 ：向量范数 如果从向量空间v 到实数r 上的一个映射| | f | | ， 满足以下条件 1 z o 且= o x 一= 6 2 1 t o - ；l l = 川剐 3 班h 垌l 则称为向量空间v 上的范数 哺只俘孬 薯： ，= 阱ir 我们以后还要使用到的无穷范数： 。= 一t i x o t ，i x , i ，h i ) 以及中心范数： ( 2 1 3 ) ( 2 1 4 ) i i a x ) l l ：为多项式n o ) 的中心范数 吁( h ) 2 2 荟a i 2 - 去( 荟q ) 2 ，, h - - ， 一 l u。u 虬= 三f 口j ( 2 1 5 ) ，”儡 定理2 1 1 “：设y 与均是向量空间c ”上的范数，则存在只与 y ，斗有关的正数，r 2 ，使得 y 0 ) s ( x ) sr 2 y o ) ，v x e c ” 1 2 ( 2 1 6 ) 西华大学硕士学位论文 2 1 2 格的定义和性质 定义2 1 3 ：设b l ，b 2 ，b 为r ”上的n 个线性无关的向量，则称集 合： l = b l x 1 + b 2 z 2 + t + 包x n ) ( 2 1 7 ) 为格。其中r 为实数集合，x ：( u ，从l 到n ) 为任意整数。 这时我们称b l ，b z ，以为格l 的一组基，n 称为格l 的维数或者秩。 为了简单起见我们记矩阵b = 岛，b 2 ，“) ，它是以向量为行向量组成 的矩阵。矩阵口称为格l 的生成矩阵( 或基矩阵) 。可记格l 为( 口) 。 一般有nc m 。如果n = m 则称格为满维的 我们把格中元素称为向量或者点。格中任何一个向量都可以用格 的基来表示。 即对格中一点a ，可以写成： a = 口1 红+ 口2 也+ + 口。b ( 2 1 8 ) 其中a ，( i 从1 到n ) 为整数。 对格的生成矩阵( 基) 作以下变换，所得到的矩阵仍为原来格的生 成矩阵 1 交换两行的顺序 2 其中某一行乘以一1 3 某一行的整数倍加到另一行 显然以上三种矩阵变换等价于对原矩阵右乘上相应的一个模数为 绝对值1 的珊卅整数矩阵。 以上内容可简述为：矩阵a ，b 为格l 的两个不同的基，即 l ) = l ( b ) ，当且仅当存在一个模数为绝对值1 的整数矩阵c ，使得 a = b c 成立。 西华大学硕士学位论文 定义2 1 4 ：格l = l ( b 1 ，6 ：，b n ) 的t ? y i j 式定义为 a e t 工= ( 包，o ) k 脚) - 对于内积( “，v ) = “7 s v ，我们有： d e t l = d e t ( b 7 - s 口1 - 定理2 1 2 ：格的仃歹u 式与基的选择尢夭。 证明：设b ，百为格的两个不同的基矩阵由基矩阵的性质我们可以 知道存在一个行列式为绝对值1 的整数矩阵t 使得百；b t 成立。设 ( ) = 7 s v ， 我们有：d e t 工= ( d e l 睁，西) k 脚) 2 = d e t ( b 7 s - b 1 - = d e t ( t 7 b 7 s b 丁) - = d e t ( ( n z ) 7 - s 丁) 1 1 因为有百：b t ，所以有： 一 ! d e t ( l ) = d e t ( b s 。b ) 2 = ( d c t ( i 巩，。) _ = d e t l。 任给n 个线形无关的向量6 l ，b z ，吃属于r 1 ，我们可以使用格朗姆 一斯密特( g r a m s c h m i d t ) 正交化过程获得一组两两正交的向量 b ：，b ： b ，：，b ： b l = 岛 趣。包一斗口6 ，对于b 1 ( 2 l 1 1 ) 其中l x , i ；( b 州b ) ，( b ，) ，i ，j 。 1 4 西华大学硕士学位论文 2 2 格中困难问题及格基归约 2 2 1 格中的困难问题 在格中主要有以下三个困难问题s v p ，c v p 及s b p 。以下将逐一介绍。 设| | 是一范数，给定一个格，找这个格上关于范数| h | 的最短向量， 即范数值最小。用数学语言表示为： r 、 l 一5 阳 ( 卅，n ，6 1 ，b2 ，“) i 抛( 也， n 耐 h 十1 | 岘( 钟小，n e n ，乜，be z l 很多人为了证明它是一个困难问题作出了很多的工作，但是直到 1 9 9 8 才完全被a j t a i “m ic c i a n e i o d4 等人证明。我们在这里不详细 叙述。 定义2 2 2 ：c v p ( t h ec l o s e s tv e c t o rp r o b l e m ) 问题，即最近向 量问题： 设是一范数，给定一个格l ( 口) 以及目标t 属于r “，寻找格中向 量x ，使得l i x f 最小。用数学语言表示为： -1 l c v p i ( m ， ，6 l ，扫2 ，一，屯，f ) | ) 、p 和。l d ，“v 皑 肿，m ，n e n ，h ，b 2 ，屯z “，t e r lj 这同样也是一个困难问题，文献”讣“”1 中有相应的证明。 定义2 2 3 ：s b p ( t h es m a l l e s tb a s isp r o b l e m ) ，最小基问题：给 定格基口，找到格l ( 口) 的范数最小的一组基。 对于以上三个问题大都使用格基归约的方法进行求解，其中最著 名的就是高斯算法“”和l l l 算法“”1 。高斯算法是由高斯提出，它适 用于二维格。l l l 算法是在1 9 8 2 年由a k l e n s t r o n ，h w l e n s t r a 和 l l o r a s z 三人合作完成，它是一个在任意维格上寻找最短向量的算法。 邑里向短最 中格即町 e曲矿rc帕csec叶曲 “ p叫l22 义 定瓢问 西华大学硕士学位论文 此外还有片断一l l l 算法“c p s c h n o r r 2 1 1 的方法，最近还出现 了一种量子方法妇2 1 等等。十几年来，相继一些密码协议被格基归约算 法攻破，格基归约己是密码分析领域的一个强大工具。 2 2 2 高斯算法和l l l 算法 一组格基a , b 是关于范数| | 的高斯归约基，当且仅当它们满足： l k i ls i 旧i i s0 n 一6 | | s i p + b l l ( 2 2 1 ) m m 栅- s c h 烈鬈攀，赫烈：2 厕2 融以及 m 蒯t _ 静删i 一怕。 斗：，。s 去一s 忙- h i i ( 2 2 2 ) ：，。z o l i o - h i l s 忙+ h i l ( 2 2 3 ) ：戡翟寒o l 南唯旷刮圳： 股亦w 6 1 1 2 _ h i 毒蕈蒜嚣圳圳酬。 ( 1 ) i l a l 6 0 ( 2 2 驯 ( 2 ) 0 5 5 去 ( 2 2 5 ) 定理2 2 2 如果格基a , b 是高斯归约的，则n 是关于范数的格l 的 证明：不失一般性我们设l l a l i s 1 6 西华大学硕士学位论文 要想证明口，b 是格l 的最短向量，只需证明i i 。1 1 5 | 1 6 i | s l h a + 弘1 1 ，l 为任意整数。 由于n ，b 是一组高斯归约基，有 | | n0 s0 6 | 1 s | 1 。- h i i s l l n + 6 j 1 成立，所以我们有 l i t n0g0 t 。一60 ， 1 _ + a l l - ：i i n + 6 0 ，l i n | | s t a 6 4 同理也有怿b 峥忙a 曲l l 成立。 另外对v g e z 0 1 有 肛+ 钏2 一忙+ 6j j 2 = 2 帅一m + 2 l ( n ，b ) - 2 ( n ，b ) = ( ；2 1 ) l l b l l 2 + 2 ( 毫一1 ) ( a ，b ) 注意( a , b ) ：0 ，所以当z 1 时上式显然大于等于0 当芎c o 时，由于有( 。，b ) s 却。j 1 2s 劲b n 我们有 2 1 ) l l b l l 2 + 2 ( 芎一1 ) ( n ，6 ) = ( e 2 1 ) l a 1 2 2 ( 1 一1 ) ( n ，6 ) = ( 芎2 一a ) i b l l 2 一o 鼍) l l b 1 2 = ( 1 2 1 + ；一1 ) i b 1 2z 0 可见对v 毫z o 我们有j l a + h i i s 忙+ 弘j | 成立，同理我们可以证明 对v 仆号z ， 0 ) ，忙+ h i l s 忻口+ b l i ，以及忙+ h i l s 忻n + 弘i 成立，我们有 s s m n + 弘0 成立，可见口是格l 的最短向量。 由以上证明可知，只要将格基转变成高斯归约基就可以得到格的 最小向量。 由图2 2 1 表示为： 1 7 西华大学硕士学位论文 高斯算法2 2 1 g r a p h 2 2 1r u d u c i n gb a s ea ，b 图2 2 1 归约基口b 1 当k | ，去时 1 1 ：2 1 纛 l a l 譬i ： 一：型换习和b如果il z ：则交换i 和 其中符号卜j 表示最靠近实数x 的整数，s 劬0 ) 表示符号函数，当x 是负数时函数值为一1 ，正数时为l 。 定理2 2 3 算法将在至多k 轮迭代后结束，输出格的最小向量 t2f 。e 。+ j ( 掣) 1 + s 证明：见参考文献“3 1 高斯算法只是适用于二维格，对于维数大于二的格还是要使用其 它算法。l l l 是一种在任意维数下求最小基的归约算法。它是 西华大学硕士学位论文 a k l e n s t r o n ，h w l e n s t r a 和l l o r a s z 三人在1 9 8 2 合作完成。这 一算法能成功的在多项式时间内找到不超过最短向量2 ( - 1 ) 7 2 倍的短向 量，而且在实际应用中效果会更好。在1 9 8 2 年著名的密码学家s h a m i r 就用它成功攻破了m e r k e h e l i m a n “”背包公钥体制，可见其重要性。 以下我们将介绍它。 定义2 2 5 一组格基岛，b 2 ，饥e r “是系数6 下的三l 归约基，当 且仅当它们满足： ( 1 ) i ls - ， 1 s ，s i s ，l( 2 2 7 ) ( 2 ) 6 嗍h 晰+ 屹- 1 峪f j 2 f = 2 ，3 ，刀 ( 2 2 8 ) 为了简单起见我们可以取6 ；三。 4 定理2 2 4 比l 归约基满足： ( 1 ) i b i 2 s2 “2 ，1 sjs is ，l ( 2 2 9 ) ( 2 ) d e t ( l ) s r i l p , l l s2 n t n - 1 ) 14 d e t ( l ) ( 2 ，2 1 0 ) ( 3 ) s2 州”h d e t ( l ) “ ( 2 2 1 1 ) 其中耳o = 1 ，2 ，n ) 是由b l ，b ：，“经过格朗姆斯密特 ( c r a m s c h m i d t ) 正交化过程后得到两两正交向量：是任意范数。 证明：( 1 ) 由( 2 2 8 ) 式可知 三刚2s 蚶+ 酬2 h 一，j s 2 = f 一) 1 盼峥 刚1 2 对上式进行递归可得： 2z 啦。胆寺刚1 2 一- z 冲耶 令i l = i ，l = i j 2 鲋叫酬1 2 ，1 sjs i s n 再由格朗姆一施密特( c r a m - s c h m i d