Costas陣列的存在性、計數(shù)問題及其在密碼學中的應用.pdf

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

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

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

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

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