資源描述:
《偽素?cái)?shù)編碼序列在背包向量公鑰密碼體制中應(yīng)用》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、維普資訊http://www.cqvip.com第5卷第2期電路與系統(tǒng)學(xué)報(bào)、ml5No.22000年6月JOURNALOFCIRCUITSANDSYSTEMSJune2呻。文章編號(hào)1007—0249(2000)02001904偽素?cái)?shù)編碼序列在背包向量公鑰密碼體制中的應(yīng)用t羅一福州丈學(xué)計(jì)算機(jī)系,福州350002)【擅要】本文研究了一組偽素?cái)?shù)編碼序列,給出求解該序列的通項(xiàng)公式并利用它們的超遞增序列特性,將其應(yīng)用在常規(guī)的陷門背包公鑰密碼體制中為防止破譯,本文采取變形的非超遞增序列作為陷門背包向量,來(lái)提高背包公鑰密碼體制的安全性【關(guān)■詞】偽素?cái)?shù)編碼,非超遞增序列,背包公鑰密碼體制,安全性【中圈
2、分類號(hào)lTNgl8【文獻(xiàn)標(biāo)識(shí)碼lA1引言自Diffie和Hellman在1976年提出公開密鑰的概念”以來(lái),各種公開密鑰方案不斷出現(xiàn)。特別是1978年Merkle和Hellman提出以背包向量為背景的超遞增序列的公開密鑰體制】,也奠定了一個(gè)很好的基礎(chǔ)。對(duì)于這種超遞增體制的破譯方法,Shamir于1984年用等價(jià)密鑰產(chǎn)生超遞增序列的方法】,成功地破譯了這種背包體制。之后,又出現(xiàn)許許多多有效的破譯方法口】。為了增強(qiáng)這類超遞增序列的攻擊能力,基于文[4]中的方案,本文給出一組偽素?cái)?shù)編碼序列,作為陷門背包向量應(yīng)用于公鑰密碼體制中,以進(jìn)一步加強(qiáng)抗擊破譯的能力。2一組新型偽素?cái)?shù)編碼序列由于素?cái)?shù)的特
3、殊性質(zhì)和不規(guī)則分布等特點(diǎn),在現(xiàn)代密碼研究與各種各樣編碼系統(tǒng)中得到了廣泛應(yīng)用為了本文編碼的需要,我們根據(jù)文【7】敘述的一類s序列,對(duì)其進(jìn)行必要的分析??紤]到它在Q邏輯拓?fù)淇臻g是一類由二進(jìn)制最小項(xiàng)頂點(diǎn)組成的布爾序集編碼序列,為便于理解,現(xiàn)簡(jiǎn)述如下:假定Q為一非空集合的邏輯拓?fù)淇臻g,即:=(cu,E)f:t=0,1?,2一1;=1,2.,:mH}(其中U為布爾頂點(diǎn)子集合,E為相鄰鏈路子集合),若頂點(diǎn)v._÷v(f,,∈f)按某種給定相鄰順序依次排列,使得對(duì)于每一個(gè)鏈路Es(=1,2....,2;∈)順序不變,則稱U排列為ago邏輯拓?fù)淇臻g序列,簡(jiǎn)記序列。因?yàn)樵撔蛄袠?gòu)造的布爾序集編號(hào)與自然數(shù)序
4、列編號(hào)相類似,所,可從中尋找一種與素?cái)?shù)有關(guān)的新型編碼序列的分布規(guī)律。因此,不妨先討論下列幾個(gè)有關(guān)概念定義1若序列:b0,b】j1...b...bi+n,b?分布在sgo_÷。。)序列域中,其中每個(gè)元素重量逼近或等于素?cái)?shù)重量,且i一一,則稱該序列為偽素?cái)?shù)編碼序列。(這里的“重量”概念均指每個(gè)元素及素?cái)?shù)對(duì)應(yīng)的數(shù)值大小,或理解為對(duì)應(yīng)二進(jìn)制數(shù)中“1”的個(gè)數(shù)數(shù)值大小。)定義2若序列:b0',自,.....6?..分布在s_÷。。)序列域中,其中每個(gè)元素重量逼近或等于素?cái)?shù)重量的程度弱于偽素?cái)?shù)編碼序列,則稱該序列為伴隨偽素?cái)?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,?序列,稱為偽素?cái)?shù)編碼第一類序列,記作(P)。定義4形如:0,1.1,5,10,18,52,68,232,264,976,1040,4000,4128,16192,16448,65152,65664,261376,262400?.序列,稱為伴隨偽素?cái)?shù)編碼第一類序列,記作S2o',(p‘)。對(duì)于一般情形的這類偽素?cái)?shù)編碼序列和變形的伴隨偽素?cái)?shù)編碼序列,可用1代表階數(shù),表示不同收
6、稿日期:1999.10.28,慘定日期:2000—04—24維普資訊http://www.cqvip.com電路與系統(tǒng)學(xué)報(bào)第5卷類型。隨著階數(shù)的變化,1階Sb?o,(p)或(p’)序列同樣可存在無(wú)窮多。分析這類超遞增序列可以發(fā)現(xiàn),其變化速度比熟知的Fibonacci序列還要快。該序列的特點(diǎn)是可用通項(xiàng)公式描述,并有各種不同特性,既可以重新構(gòu)造,也可以遞推實(shí)現(xiàn)。這里不再詳細(xì)贅述。本文證明了求解(p)和(p)兩個(gè)序列的通項(xiàng)公式,得到了如下結(jié)果:定理1.當(dāng)”≥3時(shí),對(duì)于:(P)編碼序列,則有-(p):2(=)+(二:)2;一2(=】一2(!!=!::)一(一1)(1)另設(shè)初始邊界條件:aI=o
7、’口2=l,則當(dāng)H≥3時(shí),(1)式即為(p)編碼序列的通項(xiàng)公式。定理2當(dāng)n≥3時(shí),對(duì)于(p‘)編碼序列,則有”(p)=(p)+(一1)(2)另設(shè)初始邊界條件:a】=o,a2=1,則當(dāng)/,/≥3時(shí),(2)式即為(p)編碼序列的通項(xiàng)公式。為說(shuō)明問(wèn)題起見(jiàn),只證定理1。證?。菏紫葘?duì)s(p)偽素?cái)?shù)編碼序列作一定的分解排列,從其分布規(guī)律中可以發(fā)現(xiàn),對(duì)應(yīng),I為偶數(shù)時(shí)的分解表達(dá)式,恒為五個(gè)2的不同冪次方的加或減項(xiàng);而對(duì)應(yīng)n為奇數(shù)時(shí)的分解表達(dá)式,恒為四個(gè)2的不同