一種非線性流式加密算法

1、一種非線性流式加密算法by袁園為了更好的說明算法，我們先對(duì)一些必要的概念做簡(jiǎn)單介紹。1 流式算法1.1 對(duì)稱加密對(duì)稱加密，它的加密和解密都是用同一把密鑰完成。對(duì)稱加密比不對(duì)稱加密快得多，但缺點(diǎn)在于，它的安全性完全依賴于保持密碼的機(jī)密性。不對(duì)稱加密，它要求使用兩個(gè)密鑰，一個(gè)是公共的（公鑰），另一個(gè)是私有的（私鑰）。每個(gè)密鑰都要求使用另一個(gè)密鑰來解密一條消息。它的復(fù)雜性提高，因此沒有普及。1.2 加密算法通常有兩種方法可以對(duì)一批數(shù)據(jù)進(jìn)行加密，一種是區(qū)塊加密系統(tǒng)，另一種是流式加密系統(tǒng)。1.2.1 Block Cipher（區(qū)塊加密系統(tǒng)）區(qū)塊加密獲取一大批數(shù)據(jù)，并用密鑰對(duì)其加密。這個(gè)過程不斷重復(fù)，直至

2、徹底加密整條消息。通常，會(huì)有一個(gè)長(zhǎng)度變量來控制數(shù)據(jù)塊的大小。但無論長(zhǎng)度大小，都會(huì)用整個(gè)密鑰來加密數(shù)據(jù)區(qū)塊。Cipher Function（data , password）=Output整個(gè)密鑰（password）每次都原封不動(dòng)的用于數(shù)據(jù)加密，在連續(xù)使用的過程中，區(qū)塊加密系統(tǒng)在功能上會(huì)越來越弱。密鑰很容易從密文中提取出來。1.2.2 Stream Cipher（流式加密系統(tǒng)）流式加密也使用一個(gè)密鑰，但它的加密單位小的多。區(qū)塊加密可一次加密整頁(yè)文本，但流式加密只能對(duì)構(gòu)成一頁(yè)文本的每個(gè)字母的每個(gè)比特進(jìn)行加密。流式加密使用了除密鑰和數(shù)據(jù)外的一個(gè)狀態(tài)條件，即對(duì)流經(jīng)加密程序的每個(gè)數(shù)據(jù)區(qū)塊，數(shù)據(jù)都會(huì)進(jìn)行不同

3、的加密。為了實(shí)現(xiàn)此算法，需要合并狀態(tài)值和密鑰生成一個(gè)隨機(jī)改變的數(shù)據(jù)流Key Stream。它的加密函數(shù)有兩部構(gòu)成：Key Stream = State Function（State ，Password）；Output = XOR（data , key stream）.2 加密算法2.1 概述該算法本質(zhì)為流式加密算法的一種，即對(duì)明文數(shù)據(jù)的每個(gè)bit位都進(jìn)行加密。而且生成上述Key Stream 的State Function 是非線性函數(shù)，因此是一種非線性流式加密算法，還因?yàn)樗咏饷芏际褂猛幻荑€，所以稱它是對(duì)稱的。2.2 名詞介紹該算法涉及到一些專業(yè)術(shù)語，我們有必要首先作聲明。移位寄存器序列是

4、指由移位寄存器輸出的由“1”和“0”構(gòu)成的序列。相應(yīng)的時(shí)間波形是指由“1”和“-1”構(gòu)成的時(shí)間函數(shù)，如圖2-1所示。(a)1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0(b)圖2-1（a）移位寄存器序列（b）移位寄存器波形移位寄存器序列的產(chǎn)生如圖2-2 。主要由移位寄存器和反饋函數(shù)構(gòu)成。移位寄存器內(nèi)容為或1，反饋函數(shù)的輸入端通過系數(shù)與移位寄存器的各級(jí)狀態(tài)相聯(lián)（）輸出通過反饋線作為的輸入。移位寄存器在時(shí)鐘的作用下把反饋函數(shù)的輸出存入，在下一個(gè)時(shí)鐘周期又把新的反饋函數(shù)的輸出存入而把原的內(nèi)容移入，依次循環(huán)下去，不斷輸出。如果反饋函數(shù)為的模2加（即異或），就稱寄存器為線

5、性反饋移位寄存器序列產(chǎn)生器（LFSR）。反饋函數(shù)還決定了寄存器移位的狀態(tài)總數(shù)，若使得寄存器能遍歷除全零外的所有狀態(tài)，則稱寄存器為m序列發(fā)生器，對(duì)應(yīng)此時(shí)的稱為本原多項(xiàng)式。 異或（XOR）XOR是一個(gè)簡(jiǎn)單的邏輯運(yùn)算。它是比特位的不進(jìn)位加法，是一種初級(jí)的加密方案，將一個(gè)數(shù)據(jù)區(qū)段與另一個(gè)數(shù)據(jù)區(qū)段合并到一起，從而生成一個(gè)被打亂的輸出。因?yàn)樗乃俣葮O快，因此成為最流行的加密方法之一。在生成Key Stream 后，加密函數(shù)只需將數(shù)據(jù)與其做異或便得到密文，解密是只需將密文再與其做異或，即可得到數(shù)據(jù)。2.3 算法實(shí)現(xiàn) 獲得加密密鑰算法使用password的為64比特。在該算法中狀態(tài)值也是64 bit。算法初始

6、時(shí)取機(jī)器時(shí)間的低64位與password異或得到加密密鑰。以后取算法運(yùn)行一次生成的84 bit中的64 bit作為狀態(tài)值。初始狀態(tài)值的隨機(jī)性，以及后來狀態(tài)值的迭代性，使得加密算法更安全。 移位寄存器.1 兩個(gè)寄存器運(yùn)算上述加密密鑰送到兩個(gè)64級(jí)，但具有不同的本原多項(xiàng)式的m序列寄存器中，作為寄存器的輸入。其中為寄存器的第i bit 位對(duì)兩個(gè)寄存器作如下操作：首先運(yùn)轉(zhuǎn)128次，得到的序列取其最高7bit構(gòu)成一個(gè)十進(jìn)制數(shù)N，查隨機(jī)數(shù)表，輸出另一個(gè)十進(jìn)數(shù)Ni，寄存器再運(yùn)轉(zhuǎn)Ni次，得到64bit輸出序列。將兩個(gè)寄存器的輸出按如下形式運(yùn)算：LFSR1 = A1 + A2 + A3 + A4 + A5 +

7、A6 + A7 + A8LFSR2 = B1 + B2 + B3 + B4 + B5 + B6 + B7 + B8LFSR = A1 B8 + A2 B7 + A3 B6 + A4 B5 + A5 B4 + A6 B3 + A7 B2 + A8 B1.2 得到非線性函數(shù)的輸入上述得到的LFSR 作為第三個(gè)寄存器的輸入，經(jīng)過與前兩個(gè)寄存器相同的運(yùn)轉(zhuǎn)后，輸出序列即位非線性函數(shù)的64bit輸入。 非線性State Function.1 得到14個(gè)十進(jìn)制數(shù)從64bit的輸入中確定14個(gè)數(shù)，計(jì)算式如下：得到的為一組，為另一組。.2 對(duì)第一組數(shù)的處理 根據(jù)的值計(jì)算一組非線性函數(shù)，輸出為一個(gè)8 bit數(shù)。因

8、為的值為03，所以只可能是下面函數(shù)中其中一個(gè)：式中，是兩個(gè)置換表，輸入為7 bit，輸出也為7 bit。根據(jù)計(jì)算出來的值我們繼續(xù)運(yùn)算：上式中Ni7時(shí)，取Ni=0。最后計(jì)算輸出一個(gè)8 bit字。.3 對(duì)第二組數(shù)的處理對(duì)第二組數(shù)做相同的處理，也得到一個(gè)8 bit字。 Key Stream 的生成對(duì)兩個(gè)8 bit字作如下運(yùn)算，輸出一個(gè)4 bit 字合并寄存器3的64 bit輸出，以及上述4 bit字，生成84 bit Key Stream序列： 加密將生成序列奇偶互換，并接在原始序列之后構(gòu)成一個(gè)長(zhǎng)度為168 bit的序列。設(shè)置一個(gè)值指向序列的某一位，由所指當(dāng)前位相鄰的高8 bit構(gòu)成一個(gè)字節(jié)，這個(gè)值

9、由序列第一位開始依次后移直到序列的最后一位。（其中當(dāng)值指向序列末尾時(shí)，不夠8 bit的向序列起始位循環(huán)）由上生成168個(gè)字節(jié)的加密序列，與所給數(shù)據(jù)相應(yīng)的字節(jié)做異或運(yùn)算，得到密文。3附表 31 隨機(jī)數(shù)表87797111073121611110113155921248970364045675596610978849198105112120011916251154317627290921031141251279730445669749510812211022655158829613318654494283100118826416381101512145285931972827619411611345

10、7801043912648737512320465335124235077294326088117184776106102386899233643732 置換表016324864809611282440567288104120117334965819711392541577389105121218345066829811410264258749010612231935516783991151127435975911071234203652688410011612284460769210812452137536985101117132945617793109125622385470861021181430466278941101267233955718710311915314763799511112733 置換表064165266367468569670771872973107411751276137714781579168017811882198320842185228623872488258926902791289229