一種多維度的加密密文編碼算法

一種多維度的加密密文編碼算法

0數(shù)據(jù)庫加密算法隨著計算機網(wǎng)絡(luò)的快速發(fā)展，許多應(yīng)用程序已經(jīng)包含數(shù)據(jù)庫。數(shù)據(jù)庫加密是防止數(shù)據(jù)庫記錄不被泄露的有效手段。通常使用某種加密算法對數(shù)據(jù)庫中的記錄實施加密運算后,還要對加密后的記錄進行編碼,之所以要進行編碼是因為加密后的數(shù)據(jù)庫記錄中很可能包含不可打印字符甚至字符“/0”。由于數(shù)據(jù)庫系統(tǒng)對字符的讀寫只支持可打印字符,如果記錄中出現(xiàn)不可打印字符,讀寫數(shù)據(jù)庫記錄時就要發(fā)生錯誤,所以加密后的數(shù)據(jù)記錄如果沒有經(jīng)過編碼,在讀寫過程中就很可能產(chǎn)生錯誤,導(dǎo)致數(shù)據(jù)庫操作失敗。目前很多基于數(shù)據(jù)庫的應(yīng)用系統(tǒng)中對數(shù)據(jù)庫記錄進行編碼使用的是標(biāo)準的Base64編碼,實際上這種對數(shù)據(jù)庫記錄的保護方式存在明顯的安全隱患。通常一個數(shù)據(jù)庫文件中包括很多條記錄,所有記錄通常使用同一個對稱密鑰進行加密,一旦加密算法選擇得不好,密鑰很容易被得到,攻擊者可以首先使用標(biāo)準的Base64編碼對數(shù)據(jù)庫記錄進行解碼,然后使用加密密鑰對密文解密從而恢復(fù)出原始的數(shù)據(jù)庫記錄。文獻研究了最新的數(shù)據(jù)庫安全系統(tǒng)及技術(shù),但均未解決數(shù)據(jù)庫記錄密文編碼問題;文獻總結(jié)分析了當(dāng)前的數(shù)據(jù)庫加密算法并提出新的算法,但這些算法都存在自身缺陷不能與編碼運算很好地結(jié)合。針對這個問題,本文利用Hill密碼的思想提出了一種數(shù)據(jù)庫密碼編碼算法。新算法彌補了同類算法存在的安全缺陷,而且算法將加密與編碼融合為一體,加密的過程既是編碼過程,大大加快了處理速度,提高了運行效率,實際上該算法提供給數(shù)據(jù)庫一種雙重安全保護機制。1預(yù)備知識1.1編碼字符表的編碼Base64編碼字符表的編碼對象是二進制消息,表1所示的64個基本字符構(gòu)成它的編碼字符集。在編碼過程中,待編碼的二進制消息被分成一個個6比特的單元,每個單元轉(zhuǎn)換成十進制數(shù)字后對照表1進行編碼。標(biāo)準Base64編碼字符表的字符與數(shù)字對應(yīng)關(guān)系如表1所示。本文提出的算法中,筆者沒有使用標(biāo)準的Base64編碼字符表,而是對標(biāo)準表中的字符進行了隨機排列,形成新的字符與數(shù)字對應(yīng)表,稱之為重排的Base64編碼表,如表2所示,這樣做的目的是為了增加統(tǒng)計分析的難度,最終增加了破譯難度。1.2模p同余同余接下來給出如下定義:定義1設(shè)p(p≥2)是給定的正整數(shù),稱之為模,正整數(shù)r滿足0≤r<m,對任意整數(shù)a,存在唯一的整數(shù)r及唯一的整數(shù)q,使等式a=pq+r成立。其中r稱為a模p的余數(shù)。稱全體整數(shù)關(guān)于模p的全體余數(shù)組成的集合為模p的余數(shù)集,記作Zp。例如Z6={0,1,2,3,4,5}。定義2若整數(shù)矩陣A和B的行、列數(shù)相同,并且同一位置的數(shù)據(jù)關(guān)于模p同余,稱矩陣A與B關(guān)于模p同余,記作:A≡Bmodp例如,=mod6=mod6。推論1給定模p,任意整數(shù)矩陣必與由模p的余數(shù)集Zp中的元素構(gòu)成的某一矩陣同余。定義3設(shè)α是Zp中的元素,若存在β∈Zp使得αβ≡1modp稱β為α關(guān)于模p的逆元,記作β=α-1modp定義4設(shè)A是n階整數(shù)方陣,若n階方陣B滿足:(1)B的全部元素屬于Zp;(2)AB≡BA≡I(modp),I為n階單位方陣。稱B是A模p的逆矩陣,記作B=A-1modp定理1n階整數(shù)方陣A有模p逆矩陣的充分必要條件是行列式|A|關(guān)于模p的余數(shù)r存在Zp上的逆元r-1。如表1,可以將Base64編碼表看作64個字符與余數(shù)集Z64的元素的一一對應(yīng),每個數(shù)字編號可以看作相應(yīng)字符的代碼。一般,如果Zp中的元素a與p是互素的,那么a的逆元a-1存在,反之不存在。根據(jù)這一性質(zhì),可以計算出Z64中32個元素有逆元,其對應(yīng)的逆元表如表3所示。2基于平滑密碼概念的密碼編碼算法2.1編碼編碼和編碼該算法借鑒了Hill密碼的思想,將加密運算和編碼運算有機地融為一體,加密的同時就進行編碼運算,因此加密的結(jié)果就是編碼的結(jié)果。算法過程如下:(1)重排標(biāo)準Base64編碼字符表中的字符順序,得到類似表2的重排后的Base64編碼字符表;(2)隨機或離線生成Z64上n階方陣A,滿足|A|在Z64上存在逆元,并求出A模64的逆矩陣A-1。將A用作加密矩陣,A-1用作解密矩陣;(3)將待編碼的數(shù)據(jù)庫記錄從ASCII字符集映射到新Base64編碼表上,然后分為若干分組,其中分組大小為A的階數(shù)n。分組向量記作α,計算A×αmod64,對照新Base64編碼表查找計算結(jié)果中各分量對應(yīng)的字符,將所有分量對應(yīng)的字符排列起來便得到原始記錄的密文編碼;(4)重復(fù)執(zhí)行第(3)步直到所有的記錄被加密和編碼。下面舉例說明該算法的執(zhí)行過程,為敘述方便不妨假設(shè)該例中使用的是如表2所示的重排的Base64編碼字符表。不妨設(shè)A為Z64上的三階矩陣:A==???201012101???計算|A|,得到|A|=1mod64查表3知1在Z64上的逆元為1,故A為Z64上的可逆矩陣。求得A模64的逆矩陣如下(A*為A的伴隨矩陣):A-1=1×A*=[10-121-4-102]A?1=1×A?=???10?121?4?102???假設(shè)當(dāng)前待編碼的數(shù)據(jù)庫記錄為:RMB680,其對應(yīng)的ASCII字符編號為:82,77,66,36,38,30轉(zhuǎn)化為二進制:1010010,1001101,1000010,0100100,0100110,0011110按6位重新分組得到:101001,010011,011000,010010,010001,001100,011110轉(zhuǎn)化為十進制:41,19,24,18,17,12,30將其分為大小為3的三個分組Pi(i=1,2,3),最后一個分組字符數(shù)量不足3,可以按照事先規(guī)定的規(guī)則添加特定字符,不妨本例中添加字符選定為‘0’,在表2中對應(yīng)的編號為36。如下:(41,19,24),(18,17,12),(30,36,36)利用公式P′i=A×Pi(P′i表示Pi對應(yīng)的密文),對分組分別進行加密計算:Ρ′1=×=mod64P′1=???201012101???×???411924???=???4231???mod64Ρ′2=×=mod64P′2=???201012101???×???181712???=???484130???mod64Ρ′2=×=mod64對照表2得到原數(shù)據(jù)庫記錄“RMB680”經(jīng)加密編碼后對應(yīng)的字符串為“F39cT8QC+”。到此,一條記錄的加密編碼過程完成。解密過程就是加密過程的逆過程,解密公式為:Pi=A-1×P′i,再將解密后的字符串映射到ASCII集中即可恢復(fù)原始記錄。2.2算法分析2.2.1時間復(fù)雜度分析設(shè)待加密的數(shù)據(jù)庫記錄數(shù)為n,每條記錄的長度為m,那么該算法的時間復(fù)雜性是O(mn),在n?m的情況下,時間復(fù)雜度是O(n)。當(dāng)數(shù)據(jù)庫越大、記錄數(shù)越多時該算法的時間效率體現(xiàn)得越高。2.2.2重新排列編碼字符的編碼與映射該算法的安全性基于所使用編碼字符集的大小與加密矩陣的階數(shù),實際上通過雙重保密機制來實現(xiàn)對數(shù)據(jù)庫的安全保護,其一是隨機排列的Base64編碼表,其二是加密矩陣。安全強度分析如下:第一點,編碼字符集越大就越安全。本算法使用的是經(jīng)過重排處理的Base64字符集,共有64個字符,重排的目的是為了增加破譯難度。編碼字符集越大,重新排列可能得到的字符與序號的對應(yīng)關(guān)系越多,Base64編碼字符表經(jīng)重新排列后可能產(chǎn)生的新的字符與序號映射表的數(shù)目為:64!≈1.2687×1089(個)第二點,加密矩陣的階數(shù)越大越安全。為了兼顧運算的時間效率,同時有重新排列的編碼字符表作保證,加密矩陣的階數(shù)不必取得太大,滿足安全性夠用的原則就可以了。做到以上兩點,該算法可以達到計算上的安全性,滿足實際應(yīng)用的要求。不妨假設(shè)采用的加密矩陣是5階上三角矩陣,并且滿足:主對角線上的元素取自Z64中有逆元的元素(保證該矩陣在Z64中必然存在模64逆矩陣),其逆矩陣也是主對角線元素有逆元的矩陣。按照這種加密矩陣構(gòu)造方式,在Z64中可能作為加密矩陣的5階上三角矩陣有325×6410=1024×3215(個)假如某臺超級計算機每秒可以判斷100萬億個加密矩陣,使用窮舉法來搜索需要:1.26887×1089×1024×3215÷(1014×3600×24×365)≈1.55654×1093(年)通常,被保護的數(shù)據(jù)庫都具有時效性,短則數(shù)月長則數(shù)十年后就失效了,因此在使用期內(nèi)這種算法的安全度是足夠高的。3數(shù)據(jù)庫編碼算法數(shù)據(jù)庫的安全問題一直是一個研究的熱點,數(shù)據(jù)庫加密必然涉及到編碼問題。一個好的