（模式识别与智能系统专业论文）基于“背包问题”的公钥加密算法的研究.pdf

硕士论文 幕于“背包问题”的公钢加密算法的研究 摘要 公钥加密体制是密码编码学的一个重要研究方向。本文讨论基于“背包问题” 的公钥加密体制。首先介绍了已有的背包加密体制，对已有的两种加密算法进行了 改进。然后介绍了有关复合加密的理论，将复合加密理论、递归加密体制和概率加 密体制进行融合，设计一个具有递归加密结构的概率背包加密算法。该算法具有背 包加密体制加、解密速度快的优点，同时具有m c 背包加密体制和基于离散对数问 题的加密体制的安全性。攻击者要想破译该算法，不仅要能够解出二元一次不定方 程爿x + 砂= c 的确定解，而且要同时具有破译m c 背包加密算法和基于离散对数 问题的加密算法的能力。 关键词：公钥加密体制，背包问题，矩阵覆盖，复合加密，递归加密，概率加密 硕士论文基于“背包问题”的公钥加密算法的研究 a b s t r a c t t h ep u b l i c - k e yc r y p t o s y s t e mi sa ni m p o r t a n tb r a n c h o f c r y p t o s y s t e m i nt h i sp a p e r w e f i r s t l yi n t r o d u c e da l lk i n d so fp u b l i c k e yc r y p t o s y s t e m sb a s e do nk n a p s a c kp r o b l e m a n dm a t r i xc o v e r ，a n di m p r o v e dt w oo f t h e m s e c o n d l yw ei n t r o d u c e dt h ec o m p o s i t e c r y p t o s y s t e m ，t h er e c u r s i o n c r y p t o s y s t e m a n dt h e p r o b a b i t i s t i cc r y p t o s y s t e m w e d e s i g n e dan e we n c r y p t i o na l g o r i t h mb a s e do nt h et h r e et h e o r i e sw ed i s c u e s s e d t h i s a l g o r i t h mh a st h e 卿e so ft h e a l g o r i t h m s b a s e do nm a t r i xc o v e ra n d d i s p e r s e l o g a r i t h m t ob a l ( i n t ot l i s a l g o r i t h r n ，t h ea t t a c k e rm u s tb ea b l et og e tt 1 1 ea n s w e r so f t h e e q u a t i o n 撤+ b y = c j a n db r e a ki n t ot h e s y s t e m sb a s e do nm a t r i xc o v e ra n d d i s p e r s el o g a r i t h 蔷、 k e yw o r d s ：p u b l i c k e yc r y p t o s y s t e m ，k n a p s a c kp r o b l e m ，m a t r i x c o 、，e r l c o m p o s i t e e n c r y p t i o n ，r e c u r s i o ne n c r y p t i o n ，p r o b a b i l i s t i c e n c r y p t i o n i i 警6 2 4 3 1 4 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 己在论文中作了明确的说明。 研究生签名：隆垫! 堑矽，手年；月6 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 肄 ”，( 年占月l ，日 堡主堡苎； 型蔓! 墅型旦望二堕丝造垫堕翌堕塑塑! | 堕一 1 1 密码学的发展 第一章绪论 自古以来，信息保密就被广泛地关注。历史上的战争，对密码学理论和技术的 发展起了巨大的推动作用。1 9 4 9 年，c e s h m m o a 发表了“保密系统的通信理论” 一文；1 9 7 6 年w d i f e 和n l e h e l l m a n 发表了“密码学的新方向”，这两篇重要的 论文标志着密码学的理论和技术的新变革。 随着计算机网络的发展，计算机之间以惊人的速度互相交换着信息。而很多的 时候，发送信息的用户都希望只有合法的用户( 接受者) i 爿能读懂信息的内容，例如 银行的用户信息，或国家安全、军事与外交等部门的秘密指令等，均属于这类信息。 这类信息的保护的需要，使得数据加密算法和技术迅速发展。 作为研究加密技术的密码学，这一历史悠久的学科，发展历史大致可分为三个 阶段【1 1 ： 第一个阶段为从古代到1 9 4 9 年。这一时期可看作是科学密码学的前夜时期， 这段时期的密码技术可以说是一种艺术，而不是一种科学，密码学家常常是凭直觉 和信念来进行密码设计和分析，而不是推理证明。 第二个阶段为从1 9 4 9 年到1 9 7 5 年。1 9 4 9 年s h a n n o n 发表的“保密系统的信 息理论”一文为私钥密码系统建立了理论基础，从此密码学成为门科学，但密码 学直到今天仍具有艺术性，是具有艺术性的一门科学。这段时期密码学理论的研究 工作进展不大，公开的密码学文献很少。 第三个阶段为1 9 7 6 年至今。1 9 7 6 年d i f f i e 和h e l l m a n 的“密码学的新方向” 一文导致了密码学上的一场革命。他们首次证明了在发送端和接收端无密钥传输的 保密通讯是可能的，从而开创了公钥密码学的新纪元。 1 2 密码学的基本概念 密码学是研究系统安全和保密通信的一门科学。它随着信息技术的发展而发 展。在信息量日益庞大、信息的价值显得越来越重要的时候，人们对信息的安全性 要求就越来越高，这也就促进了密码学的发展。密码学主要分为两个学科，密码编 码学和密码分析学。密码编码学主要从事信息的安全保密或者认证的工作，防止信 息被别人窃取或者伪造：而密码分析学主要从事破译加密信息或者伪造信息的工 作，当然它的发展也促进了密码编码学的不断地发展。 堡主兰兰 茎王：堕皇塑望：堕坌塑垫童兰堡堕型望! 一 我们知道加密、解密过程都是在一组密钥的控制下进行的。根据密钥的特点， 可以将密码体制分成对称密码体制和非对称密码体制。对称密码体制使用的加密密 钥和解密密钥是一样，所以也被称为单密钥体制或者常规体制。非对称密码体制， 通常采用两个或两个以上的密钥，且加密密钥和解密密钥是分开的、不一样的，所 以又称为公钥加密体制。 一个密码通信系统【1 1 通常可以用图1 2 1 来表示。它由以下几个部分组成：明 文消息空间p ；密文消息空f h j c ；密钥空间k 和k ，。在常规体制下k ，= k ，= k ， 通信双方共同使用的会话密码k 。必须在安全的信道下由发送方传送给接受方；在 公钥加密体制下，k 。k ，发送方用接受方的公开密钥加密信息，接受方用自己 的私钥解密信息，加密过程e ：p c ，k 。k i ，加密过程d c 一p ，k 2 k ：。 在常规体制下，= k ，由密钥信道来传送；在公钥加密体卷4 下，每一个公丌密钥 k ，k 。都有一个私钥密钥k ，k ，与之对应，且它们之叫有一个公开密钥和私钥密 钥的生成器。对一切脚p ，都有d 。( e 。沏) ) = m 。 幽12 1 罾码通信系统模型 从上图可以看出，对于给定的明文m ，和密钥k k ，通过加密器就可以将 明文变换为密文c = e ，( m ) ；接受者利用密钥信道传送来的密钥k 。( 常规体制下) 或者 用本地的与k ，匹配的密钥k ：，对收到的密文进行解密恢复明文m ：d 。( c ) 。 同样在这个模型中，有密码分析者的被动攻击和非法入侵者的主动攻击。主动 攻击是指非法入侵者采用删除、更改、伪造等手段向系统注入假信息，以达到损人 利己的目的的行为。被动攻击是指密码分析者对截获的密文进行分析，以求得到明 文的攻击行为。 密码分析者的工作就是要破译得到的密文c 得到明文m 。他们所用的破译方法 有穷举法和分析法两种。穷举法是对截获的密文依次使用各种可能的密钥解密，直 堡主堡奎 墨王：堕皇塑壁：塑竺塑塑堕苎鲨塑堕! i 一 到得到有意义的明文；或者在密钥不变的情况下，对所有可能的明文进行加密直到 得到与截获的密文一致的结果为止。理论上说，只要有足够的时间和空间，穷举法 可以破译所有的算法，但是由于实际的时间和空间的限制使得这种方法变得不可行 了。例如，用穷举法花三年的时间可以破译一个机密文件，但是如果该机密文件的 保密期只有两年的话，那么这样穷举就没有意义了。分析法又分为确定性分析法和 统计分析法。确定性分析法是利用一个或几个已知量用数学关系式表示出所求未知 量( 如密钥等) 。统计分析法是利用明文的己知统计规律进行破译的方法，密码分析 者对截获的密文进行统计分析，得出其问的统计规律，并与明文的统计规律进行对 比，从中提取明文和密文之间的对应或变换信息。可以看出要对付密码分析，从确 定性分析的角度看必须使得系统达到实际上的不可破性，即从要截获的密文，在公 钥体制中己知公钥，要确定私钥或任意明文在计算上是不可行的；从统计分析的角 度看必须减少明文的多余度，使得找到明文密文对的概率大大减少。同样系统 保密性要不依赖于对加密体制或算法的保密，而依赖于密钥。 要对付非法入侵者的主动攻击，防止消息的窜改、删除和伪造的一种有效的方 法就是使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的 真伪，实现这种功能的密码系统称为认证系统。加密和认证是密码编码学的两大应 用。 1 3 公钥密码学的理论和发展 密码学本与计算机科学无关，由于计算机和网络的飞速发展，它与密码学的结 合使得近代密码学理论得到革命性的变革和迅速发展。传统的密码体制是建立在通 过通信双方共同约定的密钥来加、解密的基础之上的，这显然不适合计算机网络上 的秘密通信的需要。1 9 7 6 年d i f f i e 和h e l l m a n 在“密码学的新方向”一文中提出了 公钥密码体制的新概念。在公钥密码体制中，有公开密钥和秘密密钥之分，发送方 可以用接受方的公开密钥对要传输的信息进行加密，接受方用自己的秘密密钥解密 接受到的加密信息就可以得到发送方所要传送的信息。在这一过程中通信的双方并 不需要共同约定密钥。这一概念明确的提出了用来解决计算机网络上秘密通信的问 题的方法，从而开创了现代密码学的新领域【2 】a 公钥加密算法用一个密钥对信息进行加密，而用另一个不同但是相关的密钥对 加密后的信息进行解密。这些算法有以下的特性： ( 1 ) 仅仅知道加密算法和加密密钥而要确定解密密钥，在计算上是不可行的。 ( 2 ) 两个相关密钥中任何一个都可以用作加密而让另一个用作解密，比如r s a 。 图1 3 1 给出了公钥加密的过程的模型。 塑主望兰 苎至：堂璺塑望：竺坌塑塑窒兰鲨丝竺茎 图1 3 1 公钥加密过程模型 图1 3 1 中墨。表示用户b 的公开密钥，k 。表示用户6 的秘密密钥，e 表示加 密算法，d 表示解密算法。 在这个过程中有以下的几个步骤： ( 1 ) 网络中每个用户端都有自己的对加密、解密密钥，并且将加密密钥公开。 加密密钥通过解密密钥变换得到，但是反过来知道加密密钥想得到解密密钥在计算 上是不可行的。 ( 2 ) 用户a 想把自己的信息发送给b ，他就用b 的公开密钥进行加密。然后将加 密得到的密文传送给用户6 。 ( 3 ) 用户b 接受到a 发送的密文后，用自己的秘密密钥进行解密就可以得到a 要 发送给他的信息了。 如果一个函数f ，对它的定义域上的任意x 都易于计算，( x ) ，而对于，的值域 中几乎所有的y ，当f 已知时在“多项式时间”内计算，。1 ( _ y ) 是不可行的，这样的 厂就是单向函数。如果当给定某些辅助信息时则易于计算单向函数厂的逆一，则 称j r 是一个陷门单向函数。 公钥加密体制都是建立在数学中己知的n p 问题之上的，利用n p 问题来构造 一个陷门单向函数，用陷门单向函数和密钥来实现加、解密。加密过程是一个单向 的过程，只知道明文和公钥是无法计算密文的；同样解密过程也是很简单的，只有 当给定某些辅助信息即私钥时，计算密文才会变得很容易。 已知的n p 问题有很多，能够用来构造公钥加密体制的并不多。现有的公钥加 密算法都是基于以下n p 困难问题的： ( 1 ) 背包问题：”个整数的集合a = d 。，日：，吒 和整数s ，找出a 的一个子集 其中元素之和等于s 。 ( 2 ) 整数分解问题：正整数，是否存在整数_ 、n 2 ，1 啊，”2 芝a j ( 2 瞧”) 则称爿是超递 i = 1 增向量。 有一个未知向量= x ，x ：，x 。) e o ，1 “，已知口。x 。+ 口：x ：+ + q x 。：j 如果 a 是超递增向量，则称为简单背包问题，求解算法如下： x 。= 1 ，当s 。 【x 。= 0 ，当s 一 口，1 w m 且( w ，川) = 1 。 j = 1 计算幺垒( ”q ) 。( f _ i ， ) ，w 一7 ( o w 一 0 ，则存在唯一的整数对9 ，使得 a = q b + r , o r b 显然有g c d ( d ，6 ) = g c d ( b ，) 。作阻下计算 口2 q l b + ， b2 9 2 ，i + 吒， ，i = 9 3 r 2 + 吩 0 b ， 0 ，2 ， 0 r 3 ，2 ， 堡圭堡兰墨三_ 二堂皇生堕墅旦竺望塑童兰堡堕! ! ! i 一 0 2 = 日_ 一l + 0 ，0 _ k l ， 0 一l = g 。“厶+ “，_ + l = o ， 这里因为最，6 为有限的正整数，每除一步余数都是严格地减小的，所以经过有 限步除法，必能做到余数0 。= 0 。上述计算过程即为e u c l i d 除法。 2 3 。2 格的规约基和l 3 一算法 任给n 令线性无关的向量执，6 。r ”，使用g r a m s c h m i d t 正交化可以产生 一组两n i e 交的向量6 7 ，b ：，有 6 7 = b l 轷卜瓢哪 渤) ，其【班幌娥驴”j ) ，2 i 若的一组基抚，6 。，满足 h 专( 1 蔓， f ”) 与阿删22 挑，1 2 ( 1 去，那么 f ，：= l d k l 的最近整数；b t ：= b t r b 7 “目：= ”目一r “口，= 1 ，一，l 一1 i“h ：。b k 一， 该算法首先用g r a m s c h m i d t 正交化计算6 j 与“。，然后开始个迭代过程。每 次迭代总使下面两式成立： 吲 ，1 s ， i k 1 6 j + 。6 圳三盼2 1 f 。( 江】，m ) 。对给定f ，当x ：w 时， 9 一 i i 、l 如l r ， t ；卜r 以 州蛳 硕士论文基于“背包问题”的公钥加密算法的研究 _ k l m w 半。由于q = 。2 幽，所以w 离点1 k , 一m 的距离吐满足关系 d d ，0 一竿 2 - + # - i ( 假定包2 如果觏同时放在一个坐标系中，在w 左边很 近的地方就会有一个点集k i n , 浮，n ，其中每个点均称为极小点。对每个给定 的f ，_ k , m 与冬竺( f ) 构成的区间称为一个聚集点。 0 d 现在将；啦线在横坐标方向上缩小搬倍，则曲线应为：。：v 哼v b ( m o d m ) ， v = 二是新的横坐标。于是，相应的距离一变为d ；三z 2 一“。假设的第m r1 一， + f i 。 埘 。川。 p 个极小点、厶的第g 个极小点、厶的第j 个极小点形成聚集点，则有 - - e 2 p 一旦 s ：，l p 6 。bb i2 2 1 。i 一毛 毒i b ： 1 鲁一毒b z 这里j j ，窜，_ 。，j 均为正整数，占：= 毛一一屯= 石，s j ：孑，虿：2 一“。 则这个不等式组可以转化为 l p - q a ，i s 占，1 i 五 其中g ，( f - l ，五) 是己知的有理数。下面用2 3 1 中介绍的3 一算法求解 n ( f - l ，丑) 和q 。选取一个0 + 1 ) 0 + 1 ) 矩阵 1o 01 0 一盘l 0 一a 2 0 0 一1 一a 。 00 02 ”( 。+ 占4 + 使得矩阵中的各列为格上的一组基6 i , - - - , b 。，“用三3 一算法，可以求出三的 硕士论文基于“背包问题”的公钥加密算法的研究 n 一组规约基c 1 ，t 一，q ，c ，其中q = p b 。+ q b 。+ i = i p l q a p 。一q a 。 q 2 - n ( n + 1 ) 4 占”“ 。由上l 一算法 求出了p ( f _ 1 ， ) 和g 使得慨一g d j 占( f = l ，”) 。若求出的g 是负数，则用一c 代替c 。求出p ，( i = 1 ，”) 和q ，这样就求出了聚集点。 第二步：设聚集点在i 曲线的第p 个极小点的右边，则v ：兰必定在区间 陪，等卜设其它曲线落在这个区间内的极小点依次她，则必有某 区间卜，v 。】( 1 fss 一1 ) 使得v v ，v 。o 令芝竺一，其中w。，朋，w“，埘。均为正整数，然后对w，坍。和w，朋“同时做mw mm 。一 e u c l i d 除法，直到不完全商不等为止。设所有相等的不完全商依次为口2 一，吼 则有 跏= 擘1 w + ， w 2 q 2 r l + r 2 ，l = 9 3 乇+ ，3 ： 一2 2 q h 矗i + h 从上式可以看出，m ，w 可用矗一表示。再根据所给区间可以确定具体的， + 的值，这样就可以求出陷门变换对( w 肼) 了。变换对如果有很多对，只要任取其中 一对就行了。 2 3 4 低密度背包体制的破译方法 设一个背包向量口= 。，口z ，) 定义d ( 口) = i 云蒜为向量口的密 度。背包体制中公开密钥向量的密度称为该体制的密度。 t 9 8 3 年t l a g a r i a s 和o d l y z k o 提出了一个破解低密度背包的算法一s v 算法f 1 ( s h o r t v c 。o r 算法) 。此算法对d ( 口) o 6 4 5 的背包体制几乎可以全部破译。下面介绍 塑圭丝壅兰三! ! 翌皇塑里羔墅塑塑堕兰垄型塑坠 该算法的具体内容： 设给定背包向量口：( 口，口一，) 及j ，求解口i _ + n ：x ：+ + _ = s 的解向量 ( 一，x 2 ，h ) o ，1 “。 f 1 ) 取盯+ l 维向量 b l = ( 1 ，0 ，0 ，一a 1 ) ， b 2 = ( o ，l ，0 , - a 2 ) ， b 。= ( 0 ，0 ，1 , - a 。) ， 以+ = ( o ，0 ，o ，s ) ， 这是n + 1 维格三的一组基。 ( 2 ) 用l3 一算法求l 的规约基c ，c 2 ，c 。，c h 。 ( 3 ) 若n + 1 个向量c ，“= 1 , - - - , ”+ 1 ) 中有一个，设为c ，= ( c m ，c m ，c 。+ 1 ) ，满足： 当l 歹s 珂时若c 。= 0 或为常数口，则x ，= c “a ( 1 sjs ) 就是解：否则转 ( 4 ) 。 ( 4 ) 用一= e a 。一s 替换s ，重复( 1 ) 一( 3 ) 步，得到解( ，f ：，x 。) 。由此可得 原背包问题的解为( 1 一x l ，1 一x 。2 ，l x 。) 。 这两个破译方法是用来破译背包加密算法的主要方法，很多的一次背包体制都 是用其中一个方法破译的。这也说明一次背包体制虽然有其加密、解密速度快的优 点，但是它的安全性却让人担忧。鉴于背包体制的优点，人们一直在寻求新的背包 体制以对抗上述的两种破译方法。 2 4 一次背包加密体制的改进 为了对抗各种破译一次背包的方法，对一些现有的一次背包体制做了相应的改 进。主要有多次迭代的m h 背包体制、基于孙子定理的背包体制、拆分型背包体制。 多次迭代背包体制的思想是将原先m h 背包体制中的一次变换变为多次变换。 大致算法思想o t t 3 ： 选取超递增向量口= 0 ，口：，口。) ，h 一1 个变换对( w 。，m 。) ( f - 1 ，向) ，变换过程 a 忙= 。( k = 2 ，h ) 。 公开密钥口“，秘密密钥是口和 ( 嵋，强) ( f - 1 ，彬。解密时c “1 = 。( t = h ，2 ) ，c ( 。) = 盯m t 。解之可 得明文。这个体制同样被破解了。 1 9 8 8 年，何敬民与卢开澄c l 。1 提出了基于孙子定理的背包体制。该体制不再是利 2 硕士论文基于“背包问题”的公钥加密算法的研究 用超递增背包向量来构作简单背包问题然后进行求解，而是求解丢番图方程来得到 明文。 该体制的设计如下： 随机选取n 个正整数m 1 ，m 2 ，m 。满足( m ，m ，) = 1 ( 1 i i h ) ，计算 m = m 、聊。一m 。= m m 。( 1 i h ) 并且m 满足l m m a x ( a l x i + + 口：x 。) ，这里瞒，x 。) 是明 文， 满足0 兰x ，1 0 。1 。任选w 满足1 w 1 1 6 ，i ，1 1 6 ；8 = b 。i ，岛= ( 6 。，6 ，。) i = 1 再作向量c = b 。+ p b 2 。对c 进一步隐藏，c = g ，d l + q ：d 2 ，q 1 ，9 2 z ，要求吐，d ： 不具有超递增性。 该体制的构成如下： 公钥：d l ，d 2 ； 私钥：qj ，q 2 , p ，s i ，s 2 ，口； 硕士论文 基于“背包问题”的公钥加密算法的研究 明文：x = ( x 。，- ，。) 0 ，l “； 加密：( c l ，c 2 ) ，c l = d l 工1 ，c 2 = d 2 石。： 解密： ( 1 ) q l c l + q 2 c 2 = c ， ，= c 3 ，由于ib l x 7 峰f i b , | | 口，分别将b l , b ：扩展为b ：= ( 6 ，q c ) = ( 6 ，b 。，q c ，q c 。) f _ 】 2 “ b z2 ( c ，以) = ( c 1 - 一，巳，b 2 1 ，6 ：。) ，选择一个正整数p 却 瓦，作线性组合 f = l d = b ：+ p b ：，再将d 拆分成d = q j d ，+ 吼d ：，其中d id ：是正整数向量且不具有超递 增性。 该体制的构成如下： 公钥：d id 2 ； 私钥：q ，p ，g l ，q 2 , b 1 ，b 2 ，d ，c ； 硕士论文基于“背包问题”的公钥加密算法的研究 b 耳文： x = ( x l ，x 2 ) = ( x l l ，x h ，x 2 l ，一，z 2 。) o ，1 ) 2 ”； 加密：( 8 i ，e 2 ) ，其中e i = 吐z 7 ，e 2 = d 2 x 7 ： 解密： ( 1 ) 计算= 吼p 。+ q z e ：，6 i x 7 = ，玩x i = 。 因为= q t p l + 口2 9 2 = q l d i 工7 + q 2 d 2 工7 = d x7 = 6 ：x 7 + p 6 i 工7 因为p ，巩，所以 反x 7 = ，又因为6 ：x r = 6 1 x ? + g 甜；，g 窆q0 1 q b 。，6 i 。j ，所以可得 6 ，x j = c 反x7 1 。按照上面所说的解此背包的算法即可求得五。 ( 2 ) 计算如工7 = ( 厂一b ；x 7 ) p ，6 ：x ；= 玩善7 一“i 。 因为f = g i p l + 9 2 9 z = q l d l x 7 + 9 2 d 2 x 7 = d x 7 = b l x 7 + p b ；x 7 ，由上一步已知6 ：x r ，代 入可解得坟x 72 ( 厂一b l x ”) p ，又因为玩工7 = c x r + b 2 x ：t ，己知c 和石。，所以可得 b 2 x r 2 = b ；x 7 一“j ，按照上面所说的解此背包的算法即可求得x ：。 ( 3 ) 将而，x ：合并得明文x 。 阵b 例：设超递增向量为口= ( 1 ，2 ，7 ) 选择口= 11 及正整数向量c ：( 5 ，2 ，1 2 ) ，置换矩 01 0 f o 1 0 j 。0 ；j 8 22 l ；。0j j 贝。6 i 2 口8 ，2 ( 2 ，i 7 ) t b 2 = a b 2 = ( 7 , 1 , 2 ) , 分另u 扩展6 ，b 2 得q = ( 6 l ，q c ) = ( 2 ，1 ，7 ，5 5 ，2 2 ，1 3 2 ) ，如= ( c ，b 2 ) = ( 5 ，2 ，1 2 ，7 ，1 ，2 ) ，选择p ：2 2 0 ， d = 6 l + p b ；2 ( 1 1 0 2 ，4 4 1 ，2 6 4 7 ，1 5 9 5 ，2 4 2 ，5 7 2 ) ，取q i = 1 ，9 2 ：1 ，则可取 d l = ( 5 0 0 ，2 1 3 ，1 2 3 4 ，1 2 3 ，3 2 ，4 1 2 ) ，d 2 = ( 6 0 2 ，2 2 8 ，1 4 1 3 ，1 4 7 2 ，2 1 0 ，1 6 0 ) 。 设明文序列为x = ( 工，z 2 ) = ( 1 10 0 ，i ，o ) ，q = d i x t = 7 4 5 ，p 2 ：d 2 z r ：1 0 4 0 ，密 文为( 7 4 5 ，1 0 4 0 ) 。 解密：厂2 q l q + 9 2 p 221 7 8 5 ，b l x 7 = ，= 2 5 ，b l x i = 。：3 ，可解碍 一2 ( 1 ，1 ，o ) ：6 ：x 7 = ( 一b l x 7 ) p = 8 ，6 ：x ；= 6 ：x 7 一“i = 1 ，解得z ：( o ，l ，o ) ，合 1 5 硕士论文基于。背包问题”的公钥加密算法的研究 并得明文x = ( z l ，x ：) = ( 1 100 ，l ，o ) 。 注意在选取d ，和d ，时，不能使其中的任何一个具有超递增性。从体制的安全性 考虑，建议选取的f 应该大一些，这样即使体制的部分被破译，明文也是”! 种可能。 要从本体制中的公钥d ，d ，寻找密钥是不可能的，因为从密钥生成过程来看，用 s h a m i r 方法是找不到一个变换对。首先，公钥d ，d ，是从d 分拆得到的，在不知道 系数q 。，q ：的情况下是无法确定d 的：再则d = b i + p b ：，这是一个二元一次不定方 程，由二元一次不定方程解的讨论【9 i 可以看出，不知道确定的方程的系数，方程的 解是无法确定的，所以即使确定d ，但是不知道密钥p 的情况下，也是无法确定b i ，b ： 的。选取大密度的背包向量就可以对抗低密度背包体制的破译方法。 同样可以在生成公钥和私钥的过程中加入模余变换。例如：可以选取正整数 肌，w ，w ，满足m z ，0 w m 1 3g c d ( m ，w ) = 1 ，0 w 一1 m 且w 一1 是w 模m 的 i = 1 逆即w - l w = l ( m o d m ) 。作变换d 。= 。，w 4 , 等d 。分拆成d = q l d + g ：d ：。体制变 为： 公钥：d i ，d 2 ： 私钥：q ，p ，q l ，q 2 ，m ，w 一，b i ，b 2 ，口，c ： 明文：x = ( x l ，x 2 ) = ( x ，x x 2 l ，z 2 。) 0 ，i “； 加密：( p l ，p 2 ) ，其中巳= d i x 7 ，e 2 = d 2 x 7 ； 解密： ( 1 ) 计算。2q i p ，+ g ：p z ，厂= w - t f 。，啦7 = ，b t x r ，= 蕃6 f 一，所以6 f x 7 = ，又因为6 i x 7 = b i x i + q c x r ，g 宝q 即 g 善玩r 岛z i ，所以可得6 t x i = 。，按照上面所说的解此背包的算法即可 求得五。 ( 2 ) 计算6 i x 7 = ( 一6 ：x 7 ) 7 j 口，6 ：z ；= 吐x 7 一“j 。 因为厂2 q l p l + 9 2 e 22 q l d l z 7 十9 2 d 2 x7 = d x 7 = 6 i x 7 + p 呒x 7 ，由上一步已知6 i x r ，代 1 6 硕士论文 基于“背包问题”的公钥加密算法的研究 入可解得跌，= ( 厂一b l x 7 ) p ，又因为如x 7 = “? + 6 2 x 2 t ，已知拜。而，所以可得 6 ：x ：t = 如x 7 一“i ，按照上面所说的解此背包的算法即可求得x 2 。 ( 3 ) 将x ，x 2 合并得明文z 。 硕士论文 基于“背包问题”的公钥加密算法的研究 第三章二次背包公钥密码体制 3 1 二次背包体制的提出 二次背包问题也叫矩阵覆盖问题( 即m c 问题) ，它是一个已知的n p c 问题， 可以用来构造陷门单向函数，所以可以用来构造二次背包体制。实际上一次背包也 是二次背包的特例。 虽然大部分的一次背包体制均被破译了，但背包体制以其加密、解密速度快， 易于软件实现的特点，仍然吸引人们极大的兴趣。利用二次背包问题构造的二次背 包体制具有很强的安全性，可以有力地对抗了已有的破译一次背包体制的方法。用 矩阵代替维向量而做成的矩阵覆盖方案，因破译的计算量比背包向量大得多，且 密文中不仅含有单个单元的信息，还含有两两之间的关系信息，所以破译的复杂性 加强。 m c 背包体制首先是来学嘉旺 设计出来的，他的设计大致如下： 任取正整数超递增向量( 二 ，二。) ，正整数p 窆二。任取两个。打的正整 i = 1 数矩阵( 口j ) 与( ) ，令( ) = q 0 o 口删 + p ( 口；) 。在选取正整数m ，w ( n 一b 2 , 1 ) ： i = 1 作矩阵c = a + p b 。m c 二次型代数体制如下： 公钥：c ： 私钥：p ，口； 明文：x = ( 一，靠) o ，1 n 1 9 硕士论文 f x i 加密：y = ( 工l ，一，k ) c i ； l “ 解密：因为c = a + p b ，所以y = h 由于f x 以计算y t = ，北= 上p ，代入最初的计算式lj ，爿e a i x ，= 办可万 忙l + 4 ( x 基于“背包问题”的公钥加密算法的研究 p ( x b ：，辟( lb 。，一b ：，睁所 这是一个简单背包问题，很容易就可以解得明文( _ ，x 。) 。 例：设正整数超递增向量为( 3 ，6 ，1 1 ，2 1 ) ，分成两个整数向量b ：( 1 ，5 ，4 ，1 8 ) 和 b 2 = ( 2 ，1 ，7 ，3 ) 。选取正整数p = 2 5 3 ，a = 731 ：3 。5 。1 ：5i ，所以c ：彳+ 加 1 2 6 5 4 j 设明文为( 1 ，0 ，0 ，1 ) ，加密得密文y = 2 4 2 3 1 。 l一4 3 41 61 2 3一1 29 1 56 0 4 5 l 5 0 72 4 9 i 2 5 2 6 1 2 8 1 l 2 0 2 71 0 0 0 i9 0 9 34 6 1 4 解密：先计算y - 2 ，2 ，。a ，y ：= 砉 = 。s 解此简单背包问题得明文( 1 ，0 ，0 ，1 ) 。 1 7 7 4 8 8 4 3 7 0 9 3 3 1 8 3 3 7 4 4i 3 8 5 5j i 2 9 9 9 f 1 3 8 8 7 l = 佤t + 4 y 2 = 2 4 1lllj h ，l1 ) “ + 0llllj 一k l 4 )h x 6 。h ( m 时，就可以利用上述代数式来建立个m c 分段加密体制，先解出 ( x 1 i t 一，x 。) ，然后再解出( x ，x 。) 。 该体制的设计如下： 设a = ( q ，口，) 和6 = ( k 。，屯) 是正整数的超递增向量，将向量6 随机扩展 为行维正整数向量6 = ( 6 l i 一，6 。，b 。，b 。) ，作代数式 f ( x ) = ( q _ ) 2 + p t ( 6 ，) ( c j ) + 尸慨( 窆6 ： ) ( 芝曩) 其中b 】= ( 6 ，一b ，) 和b ：= ( 6 2 ，b ：。) 是正整数向量，且满足b = b 1 + 6 2 c 1 2 ( c ，c 。) 和c ：2 ( c ：i ，一，c “) 都是正整数向量，并且p 。和p ：满足 p 。 ( q ) 2 ，p ： ( 6 ，。) ( c 、，) 。 由f ( x ) 可以整理成个二次型 这里a 是n m 阶整数矩阵 ，( z ) = ( x ， 2 l 、，j 一 ，=iijjiiiiiiijr ； 如 咖 1，j 置； ，l 彳 )h x 硕士论文基于“背包问题”的公钥加寮算法的研究 a = 口? 十p 1 6 i l c l l + p l p 2 b 2 1 c 2 l f 1 2 a 1 + p l b l 2 。1 14 - p lp 2 b 2 2 。2 i 口2 + p l b l l c i2 + p i p 2 b 2 1 c 2 2 口；+ p 1 6 1 2 c 1 2 + p l p 2 b 2 2 c z 2 p l b l l q + p l p 2 b 2 1 c 2 。 p l b 】2c l 。+ p i p 2 b 2 2 0 2 。 p l b l 。c 1 1 + p 1 p 2 b 2 ”c 2 lp 1 b l 。c 】2 + p l p 2 b 2 。c 2 2一p l b l 。c l + p 1 p 2 6 2 。c 2 可以