伪素数编码序列在背包向量公钥密码体制中应用

《伪素数编码序列在背包向量公钥密码体制中应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、维普资讯http://www.cqvip.com第5卷第2期电路与系统学报、ml5No．22000年6月JOURNALOFCIRCUITSANDSYSTEMSJune2呻。文章编号1007—0249(2000)02001904伪素数编码序列在背包向量公钥密码体制中的应用t罗一福州丈学计算机系，福州350002)【擅要】本文研究了一组伪素数编码序列，给出求解该序列的通项公式并利用它们的超递增序列特性，将其应用在常规的陷门背包公钥密码体制中为防止破译，本文采取变形的非超递增序列作为陷门背包向量，来提高背包公钥密码体制的安全性【关■词】伪素数编码，非超递增序列，背包公钥密码体制，安全性【中圈

2、分类号lTNgl8【文献标识码lA1引言自Diffie和Hellman在1976年提出公开密钥的概念”以来，各种公开密钥方案不断出现。特别是1978年Merkle和Hellman提出以背包向量为背景的超递增序列的公开密钥体制】，也奠定了一个很好的基础。对于这种超递增体制的破译方法，Shamir于1984年用等价密钥产生超递增序列的方法】，成功地破译了这种背包体制。之后，又出现许许多多有效的破译方法口】。为了增强这类超递增序列的攻击能力，基于文[4]中的方案，本文给出一组伪素数编码序列，作为陷门背包向量应用于公钥密码体制中，以进一步加强抗击破译的能力。2一组新型伪素数编码序列由于素数的特

3、殊性质和不规则分布等特点，在现代密码研究与各种各样编码系统中得到了广泛应用为了本文编码的需要，我们根据文【7】叙述的一类s序列，对其进行必要的分析。考虑到它在Q逻辑拓扑空间是一类由二进制最小项顶点组成的布尔序集编码序列，为便于理解，现简述如下：假定Q为一非空集合的逻辑拓扑空间，即：=(cu，E)f：t=0,1⋯，2一1；=1,2．，：mH}(其中U为布尔顶点子集合，E为相邻链路子集合)，若顶点v．_÷v(f，，∈f)按某种给定相邻顺序依次排列，使得对于每一个链路Es(=1,2．．．．，2；∈)顺序不变，则称U排列为ago逻辑拓扑空间序列，简记序列。因为该序列构造的布尔序集编号与自然数序

4、列编号相类似，所，可从中寻找一种与素数有关的新型编码序列的分布规律。因此，不妨先讨论下列几个有关概念定义1若序列：b0，b】j1．．．b．．．bi+n,b⋯分布在sgo_÷。。)序列域中，其中每个元素重量逼近或等于素数重量，且i一一，则称该序列为伪素数编码序列。(这里的“重量”概念均指每个元素及素数对应的数值大小，或理解为对应二进制数中“1”的个数数值大小。)定义2若序列：b0'，自，．．．．．6⋯．．分布在s_÷。。)序列域中，其中每个元素重量逼近或等于素数重量的程度弱于伪素数编码序列，则称该序列为伴随伪素数编码序列。定义3形如：0，1，2，4，11，17，53，67，233，263

5、，977，1039，4001，4127，16193，16447，65153，65663，261377，262399，1047041，1049087，4191233，4195327，16771073，16779263，⋯序列，称为伪素数编码第一类序列，记作(P)。定义4形如：0，1．1，5，10，18，52，68，232，264，976，1040，4000，4128，16192，16448，65152，65664，261376，262400⋯．序列，称为伴随伪素数编码第一类序列，记作S2o',(p‘)。对于一般情形的这类伪素数编码序列和变形的伴随伪素数编码序列，可用1代表阶数，表示不同收

6、稿日期：1999．10．28，惨定日期：2000—04—24维普资讯http://www.cqvip.com电路与系统学报第5卷类型。随着阶数的变化，1阶Sb⋯o,(p)或(p’)序列同样可存在无穷多。分析这类超递增序列可以发现，其变化速度比熟知的Fibonacci序列还要快。该序列的特点是可用通项公式描述，并有各种不同特性，既可以重新构造，也可以递推实现。这里不再详细赘述。本文证明了求解(p)和(p)两个序列的通项公式，得到了如下结果：定理1．当”≥3时，对于：(P)编码序列，则有-(p)：2(=)+(二：)2；一2(=】一2(!!=!：：)一(一1)(1)另设初始边界条件：aI=o

7、’口2=l，则当H≥3时，(1)式即为(p)编码序列的通项公式。定理2当n≥3时，对于(p‘)编码序列，则有”(p)=(p)+(一1)(2)另设初始边界条件：a】=o，a2=1，则当／,／≥3时，(2)式即为(p)编码序列的通项公式。为说明问题起见，只证定理1。证啊：首先对s(p)伪素数编码序列作一定的分解排列，从其分布规律中可以发现，对应，I为偶数时的分解表达式，恒为五个2的不同幂次方的加或减项；而对应n为奇数时的分解表达式，恒为四个2的不同