Costas陣列的存在性、計(jì)數(shù)問題及其在密碼學(xué)中的應(yīng)用.pdf

1、任何沒有信息擴(kuò)張的密碼體制都可以看作是置換的結(jié)果。而起源于雷達(dá)信號(hào)設(shè)計(jì)的Costas陣列，作為一種特殊的置換矩陣，與置換一一對(duì)應(yīng)，經(jīng)降維所得Costas序列是一種特殊的置換?，F(xiàn)代密碼學(xué)中的公鑰體制基于特定的數(shù)學(xué)難題。而Costas陣列的存在性、計(jì)數(shù)等問題懸疑至今，成為困難的數(shù)學(xué)問題。圍繞著Costas陣列的存在性、計(jì)數(shù)問題及其在密碼學(xué)上的應(yīng)用，本論文取得了以下三方面的研究成果。 1．給出了廣義Golomb構(gòu)造法所缺少的一個(gè)必要條

2、件；將隨機(jī)優(yōu)化算法應(yīng)用于Costas陣列的存在性探測。本文首先對(duì)廣義Golomb構(gòu)造法進(jìn)行了研究，發(fā)現(xiàn)該推廣法缺少一個(gè)必要條件，并給出了該條件。代數(shù)構(gòu)造法能構(gòu)造無窮多階的Costas陣列，但部分階數(shù)的陣列不能由其構(gòu)造，這些陣列的存在性尚不確定。計(jì)算機(jī)枚舉法可以探測Costas陣列的存在性，但計(jì)算復(fù)雜度呈指數(shù)階。針對(duì)高復(fù)雜度的弊端，本文將Costas陣列的存在性探索視為優(yōu)化問題，建立了優(yōu)化模型。在模型的求解上，文中基于模擬退火算法、遺傳算

3、法和廣義粒子群算法等三大隨機(jī)優(yōu)化算法，分別提出了SAACAS、GACAS、GPSOCAS三種算法，實(shí)驗(yàn)結(jié)果初步表明：三種算法對(duì)于18階以下Costas陣列的探測有效。 2．給出了對(duì)稱Costas陣列個(gè)數(shù)與一般Costas陣列個(gè)數(shù)的關(guān)系式；改進(jìn)了現(xiàn)有的Costas陣列串行搜索算法并將其并行化。本文研究了對(duì)稱Costas陣列的計(jì)數(shù)問題，得到了對(duì)稱Costas陣列個(gè)數(shù)和該階Costas陣列總個(gè)數(shù)的關(guān)系式。現(xiàn)有的Costas陣列枚舉算法

4、基于回溯法，通過置換的差分計(jì)算決定算法繼續(xù)搜索或回溯。從計(jì)算、存儲(chǔ)必要的差分及檢查重復(fù)差分的角度，本文改進(jìn)了現(xiàn)有算法，并以定理的形式給出了證明。最后將改進(jìn)后的枚舉算法并行化，該算法具有線性加速比和可擴(kuò)放性。 3．構(gòu)造了一種基于Costas陣列的數(shù)字簽名方案；將Costas陣列分別應(yīng)用于Shamir背包數(shù)字簽名、Niederreiter公鑰體制和S盒。構(gòu)造Costas陣列的復(fù)雜度屬指數(shù)階，而判定一個(gè)置換矩陣是否為Costas陣列可

5、在多項(xiàng)式時(shí)間內(nèi)完成，因而Costas陣列具有構(gòu)造困難而判定容易的性質(zhì)。由此，本文基于Costas陣列構(gòu)造了一種數(shù)字簽名方案。利用Costas陣列分布的稀疏性，將Costas陣列用于Shamir背包數(shù)字簽名和Niederreiter公鑰體制，提高其安全性。S盒是許多分組密碼算法中的唯一非線性部件，因此，它的密碼強(qiáng)度決定了整個(gè)分組密碼算法的安全強(qiáng)度。任意n階的雙射S盒都可以看作是0到2<'n>-1的所有整數(shù)的一個(gè)置換。本文提出將Costas