偽素數(shù)編碼序列在背包向量公鑰密碼體制中應(yīng)用

《偽素數(shù)編碼序列在背包向量公鑰密碼體制中應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、維普資訊http://www.cqvip.com第5卷第2期電路與系統(tǒng)學(xué)報、ml5No．22000年6月JOURNALOFCIRCUITSANDSYSTEMSJune2呻。文章編號1007—0249(2000)02001904偽素數(shù)編碼序列在背包向量公鑰密碼體制中的應(yīng)用t羅一福州丈學(xué)計算機系，福州350002)【擅要】本文研究了一組偽素數(shù)編碼序列，給出求解該序列的通項公式并利用它們的超遞增序列特性，將其應(yīng)用在常規(guī)的陷門背包公鑰密碼體制中為防止破譯，本文采取變形的非超遞增序列作為陷門背包向量，來提高背包公鑰密碼體制的安全性【關(guān)■詞】偽素數(shù)編碼，非超遞增序列，背包公鑰密碼體制，安全性【中圈

2、分類號lTNgl8【文獻標(biāo)識碼lA1引言自Diffie和Hellman在1976年提出公開密鑰的概念”以來，各種公開密鑰方案不斷出現(xiàn)。特別是1978年Merkle和Hellman提出以背包向量為背景的超遞增序列的公開密鑰體制】，也奠定了一個很好的基礎(chǔ)。對于這種超遞增體制的破譯方法，Shamir于1984年用等價密鑰產(chǎn)生超遞增序列的方法】，成功地破譯了這種背包體制。之后，又出現(xiàn)許許多多有效的破譯方法口】。為了增強這類超遞增序列的攻擊能力，基于文[4]中的方案，本文給出一組偽素數(shù)編碼序列，作為陷門背包向量應(yīng)用于公鑰密碼體制中，以進一步加強抗擊破譯的能力。2一組新型偽素數(shù)編碼序列由于素數(shù)的特

3、殊性質(zhì)和不規(guī)則分布等特點，在現(xiàn)代密碼研究與各種各樣編碼系統(tǒng)中得到了廣泛應(yīng)用為了本文編碼的需要，我們根據(jù)文【7】敘述的一類s序列，對其進行必要的分析。考慮到它在Q邏輯拓撲空間是一類由二進制最小項頂點組成的布爾序集編碼序列，為便于理解，現(xiàn)簡述如下：假定Q為一非空集合的邏輯拓撲空間，即：=(cu，E)f：t=0,1?，2一1；=1,2．，：mH}(其中U為布爾頂點子集合，E為相鄰鏈路子集合)，若頂點v．_÷v(f，，∈f)按某種給定相鄰順序依次排列，使得對于每一個鏈路Es(=1,2．．．．，2；∈)順序不變，則稱U排列為ago邏輯拓撲空間序列，簡記序列。因為該序列構(gòu)造的布爾序集編號與自然數(shù)序

4、列編號相類似，所，可從中尋找一種與素數(shù)有關(guān)的新型編碼序列的分布規(guī)律。因此，不妨先討論下列幾個有關(guān)概念定義1若序列：b0，b】j1．．．b．．．bi+n,b?分布在sgo_÷。。)序列域中，其中每個元素重量逼近或等于素數(shù)重量，且i一一，則稱該序列為偽素數(shù)編碼序列。(這里的“重量”概念均指每個元素及素數(shù)對應(yīng)的數(shù)值大小，或理解為對應(yīng)二進制數(shù)中“1”的個數(shù)數(shù)值大小。)定義2若序列：b0'，自，．．．．．6?．．分布在s_÷。。)序列域中，其中每個元素重量逼近或等于素數(shù)重量的程度弱于偽素數(shù)編碼序列，則稱該序列為伴隨偽素數(shù)編碼序列。定義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，?序列，稱為偽素數(shù)編碼第一類序列，記作(P)。定義4形如：0，1．1，5，10，18，52，68，232，264，976，1040，4000，4128，16192，16448，65152，65664，261376，262400?．序列，稱為伴隨偽素數(shù)編碼第一類序列，記作S2o',(p‘)。對于一般情形的這類偽素數(shù)編碼序列和變形的伴隨偽素數(shù)編碼序列，可用1代表階數(shù)，表示不同收

6、稿日期：1999．10．28，慘定日期：2000—04—24維普資訊http://www.cqvip.com電路與系統(tǒng)學(xué)報第5卷類型。隨著階數(shù)的變化，1階Sb?o,(p)或(p’)序列同樣可存在無窮多。分析這類超遞增序列可以發(fā)現(xiàn)，其變化速度比熟知的Fibonacci序列還要快。該序列的特點是可用通項公式描述，并有各種不同特性，既可以重新構(gòu)造，也可以遞推實現(xiàn)。這里不再詳細贅述。本文證明了求解(p)和(p)兩個序列的通項公式，得到了如下結(jié)果：定理1．當(dāng)”≥3時，對于：(P)編碼序列，則有-(p)：2(=)+(二：)2；一2(=】一2(!!=!：：)一(一1)(1)另設(shè)初始邊界條件：aI=o

7、’口2=l，則當(dāng)H≥3時，(1)式即為(p)編碼序列的通項公式。定理2當(dāng)n≥3時，對于(p‘)編碼序列，則有”(p)=(p)+(一1)(2)另設(shè)初始邊界條件：a】=o，a2=1，則當(dāng)／,／≥3時，(2)式即為(p)編碼序列的通項公式。為說明問題起見，只證定理1。證?。菏紫葘(p)偽素數(shù)編碼序列作一定的分解排列，從其分布規(guī)律中可以發(fā)現(xiàn)，對應(yīng)，I為偶數(shù)時的分解表達式，恒為五個2的不同冪次方的加或減項；而對應(yīng)n為奇數(shù)時的分解表達式，恒為四個2的不同