擴散算法是一種數據處理方法，目的在於通過擴散處理使得元素之間相互影響，從而實現完全的雪崩效應。該算法可用於數據加密/解密，計算訊息摘要（Message Digest），生成訊息認證碼（Message Authentication Code），生成隨機數等。
基本介紹
- 中文名：擴散算法
- 外文名：Diffusion Algorithm
- 本質：數據處理
- 用途：數據加密、生成隨機數等
- 標籤：擴散算法 | 擴散加密
算法簡介,算法原理,算法特性,算法用途,數據加密,計算訊息摘要,生成MAC,生成偽隨機數,邏輯實現,有序網路,無序網路,代碼實現,數據加密,計算訊息摘要,生成隨機數,
算法簡介
擴散算法是一種數據處理方法，目的在於通過擴散處理使得元素之間相互影響，從而實現完全的雪崩效應。雪崩效應是指原始輸入中的微小變化，經過積累發展後而造成輸出的巨大改變。而完全的雪崩效應，對於輸入中任意的微小變化都會造成輸出全部產生改變（100%的擴散率）。
擴散算法通過在元素之間建立擴散路徑，使元素沿著該路徑向其他元素擴散。每一個元素都沿著指定的路徑擴散，從而使元素間相互發生影響。
算法原理
擴散算法的核心在於擴散過程，擴散過程由擴散網路決定。所謂擴散，是指元素傳遞影響的過程，若元素A擴散到元素B，則當A發生改變時，B也發生改變。
若有N（N>=1）個元素組成的集合M。通過一定的規則使M中的元素相對應，如M1（起點）對應M4（終點），M4對應M8，M8對應M2，M2對應M6…，描述為Mi向Mj擴散，記作Mi→Mj；分別取出相對應的元素並組成表達式，通過一定的方法對表達式進行處理，再使用處理的結果更新被對應的元素（終點）。當起點元素髮生改變時，終點元素也發生改變；在處理的過程中這種改變會發生傳遞，進而影響其他元素，最終影響所有元素。
圖1（有序網路）
圖1（有序網路）在上述過程中，元素間的對應關係用擴散路徑（以下簡稱路徑）表示，起點元素（Mi）叫做原體，終點元素（Mj）叫做受體；由元素組成的表達式叫做擴算式；對擴算式的處理叫做擴散運算（為防止受體丟失，擴散運算時需加入受體一同運算）；所有路徑的集合叫做擴散網路（以下簡稱網路）；對整個網路執行一次擴散叫做一個周期。
參照圖1，X、Y為元素數量均為8的分組；方框中的數字為元素索引，連線方框之間的線條為擴散路徑，箭頭指向的元素為受體元素，其中虛線表示元素X[0]完成完全擴散所走的路徑；元素索引上方的“*”號表示被X[0]所影響的元素；整個網路的擴散分為四個階段完成，執行擴散時需從上到下順序執行；
建立網路時，若要達到100%的擴散率，必須要保證所建立的網路對於每一個輸入元素都能影響任何一個輸出元素；每個擴散式的擴散運算都必須滿足原體中任意元素的變化都將引起受體的變化（受體為元素組時，則元素組內的每一個元素都要發生變化）。
算法特性
豐富的網路建立規則
網路可以建立為有序的（圖1），也可以建立為無序的（圖2）。
圖2（無序網路）
圖2（無序網路）對於有序的網路，則不需要手動建立路徑，直接套用公式即可。設N為分組長度，先計算對數
，對G進行向上取整；計算基於N的完美長度
；計算完成完全擴散所需的階段數量round=G+E, E>=0；E的取值範圍跟分組數量有關，E的具體取值可根據分組數量或者需要來設定。
對於無序的網路，則需要手動建立路徑，對於任意N長度的分組均存在最短路徑（即單位元素完成完全擴散所需的路徑長度，每一階為一個長度），或許可以通過算法找出該最短路徑，應該不是什麼難事；或許為了某種目的可以增加一些額外的路徑，讓網路看起來更加複雜。
豐富的擴散式建立方式
擴散式的建立除必須包含原體和受體外，還可以包含其他任意元素（元素組），想怎么建，就怎么建了。
圖3（路徑連線方式之一）
圖3（路徑連線方式之一）豐富的擴散運算方式
世間函式千千萬萬，誰人知道你用了誰。想從數據中分析出使用了什麼樣的函式，這幾乎是天方夜譚。只需稍稍更改一點函式參量，就能使數據變得面目全非，猶如蝴蝶扇翅而颶風忽起。
豐富的元素組織方式
完成完全擴散所需要的擴散階段跟元素數量有關，對於1024位元組長度的分組（元素類型為byte），則需要
個擴散階段。若將4個元素組成int類型，則只需要
個擴散階段。若將8個元素組成long類型，則僅需要
個擴散階段。當然，元素可以任意組合。不過使用組合元素也沒那么容易，這還需要滿足對於元素組內任意一個元素的變化都需要引起其他元素的變化（包括原體和受體）。元素組織方式可參見圖3。
圖4（元素組擴散）
圖4（元素組擴散）天生的並行計算支持
每個擴散階段都需要對當前階段的每一條路徑進行擴散運算，因為目前的計算機以串列的方式執行指令，因此需要對這些路徑逐一執行擴散運算。但顯然這些路徑是可以一併執行的，不同路徑內的元素互不影響。如果每個階段的擴散運算都可以同一時刻並行處理的話，那么對於N個元素的擴散算法，理論上速度將提升N倍。
其他特性
簡潔，擴散算法真的只有那么簡單，區區幾行碼就可以達到那么不可思議的效果；靈活，如可以定製網路、定製擴散式、定製函式等。
算法用途
數據加密
擴散算法有著完美的擴散率，因此能夠很好的進行數據加密。而且加密過程非常簡單，天生的並行計算支持能夠極大提升加密速度。
可以將密匙作為分組一同建立路徑，或者將密匙作為擴散運算的參數一同參與運算。使用定製的函式並保密，可讓攻擊者不知所措。使用定製的網路並保密，將會使攻擊者感到異常頭疼。即便攻擊者知道網路建立規則，擴散式建立方式以及所使用的函式，那么也只能束手無策，唯一的攻擊方法就是窮舉攻擊。然而對於支持任意長度密匙的擴散加密，窮其所有，也只能望洋興嘆。當然密匙也不能太短了!
擴散算法其良好的擴展性，可有如下加密模式：
對稱分組加密：使用擴散算法進行加密，對每一組明文的加密都使用的相同的密匙（可以在每一階都使用不同的密匙）。
對稱流加密：僅使用擴散算法生成子密匙流（參見生成隨機數），再使用所生成的密匙流和明文進行異或運算（xor）即可得到密文。使用可靠的擴散運算（函式）再以消除線性，將使密匙重複變得遙遙無期。
對稱分組流加密：使用擴散算法以密匙為基礎生成子密匙流，再使用擴散算法對明文進行分組加密。此模式可以滿足對每一組明文的加密都使用不同的密匙。
半非對稱加密：套用擴散算法，可提高非對稱的加密效率。用非對稱加密數據時，不需要將整個明文組塊合成一個大整數進行加密，只需對明文中的各個元素（元素組）分別加密即可（密匙不同）。
此模式共分三次加密。設有明文M，長度為n；套用非對稱分別對M中的各個元素（M1,M2,M3…Mn）進行加密後得到T1；套用擴散算法對T1進行加密後得到T2；最後再次套用非對稱分別對T2中的各個元素加密得到密文C（密匙與第一次加密相同）。
全非對稱加密：設函式F與函式Fˊ為非對稱互斥函式，通過F(Fˊ)加密後的數據只能通過F’(F)進行解密。套用擴散算法，在進行擴散運算的過程中使用F(Fˊ)進行加密，用Fˊ(F)進行解密即可。
計算訊息摘要
擴散算法可用於生成任意長度的訊息摘要。其100%的擴散率可計算出可靠的訊息摘要數據。對於其定製的擴散算法而言，在不泄露細節的情況下，碰撞攻擊幾乎變得毫無意義。
不過計算訊息摘要時，擴散運算的運算質量直接影響的到訊息摘要的計算質量，可不能馬虎。
生成MAC
MAC即訊息認證碼（帶密匙的訊息摘要）。這也不用說了，計算訊息摘要時加入密碼就好了。
生成偽隨機數
用擴散運算生成偽隨機數，隨機性好，生成速度快，周期長。使用可靠的函式是生成隨機數質量的前提保障，用多種網路交替使用更使隨機效果如虎添翼。可別忘了消除線性喔！
邏輯實現
有序網路
本示例的網路建立規則參照圖1。處理步驟：
S1. 設N(n)為分組長度。計算對數
，並對G進行向上取整，計算完美長度
，計算處理所需擴散階段的數量round = G + E，E>=1，本例E = 1。
S2. 取2組長度為n的分組X和Y，i、j分別是X、Y的元素索引。
S3. 設整數r是擴散階段索引號。第一階r = 0。由X向Y的擴散命名為EY，記作EY=X[i]+Y[j]→Y[j]；由Y向X的擴散命名為EX，記作EX= Y[j]+X[i]→X[i]。組建擴散式分別為：
X[0]+Y[0]→Y[0], Y[0]+X[0]→X[0];
X[1]+Y[1]→Y[1], Y[1]+X[1]→X[1];
X[2]+Y[2]→Y[2], Y[2]+X[2]→X[2];
…
X[n-1]+Y[n-1]→Y[n-1], Y[n-1]+X[n-1]→X[n-1].
S4. 分別取出EY中的原體，使用函式FY計算結果後，更新EY中的受體，即Y[j] = FY(X[i], Y[j])。
S5. 分別取出EX中的原體，使用函式FX計算結果後，更新EX中的受體，即X[i] = FX(Y[j], X[i])。
S6. 第二階，r = 1。組建擴散式分別為：
X[0]+Y[P/2+0]→Y[P/2+0], Y[P/2+0]+X[0]→X[0];
X[1]+Y[P/2+1]→Y[P/2+1], Y[P/2+1]+X[1]→X[1];
X[2]+Y[P/2+2]→Y[P/2+2], Y[P/2+2]+X[2]→X[2];
…
X[n-1] +Y[P/2+n-1]→Y[P/2+n-1], Y[P/2+n-1] X[n-1]→X[n-1];
然後執行步驟S4、S5。
S7. 第三階，r = 2。組建擴散式分別為：
X[0]+Y[P/4+0]→Y[P/4+0], Y[P/4+0]+X[0]→X[0];
X[1]+Y[P/4+1]→Y[P/4+1], Y[P/4+1]+X[1]→X[1];
X[2]+Y[P/4+2]→Y[P/4+2], Y[P/4+2]+X[2]→X[2];
…
X[n-1] +Y[P/4+n-1]→Y[P/4+n-1], Y[P/4+n-1]+X[n-1]→X[n-1];
然後執行步驟S4、S5。
S8. 第r階（僅當此示例中不是第一階時）。組建擴散式分別為：
X[0]+Y[P/2r+0]→Y[P/2r+0], Y[P/2r+0]+X[0]→X[0];
X[1]+Y[P/2r+1]→Y[P/2r+1], Y[P/2r+1]+X[1]→X[1];
X[2]+Y[P/2r+2]→Y[P/2r+2], Y[P/2r+2]+X[2]→X[2];
…
X[n-1] +Y[P/2r+n-1]→Y[P/2r+n-1], Y[P/2r+n-1]+X[n-1]→X[n-1];
然後執行步驟S4、S5。
無序網路
本示例的網路建立規則參見圖2，處理步驟：
S1. 設有分組X、Y，分組長度為N，本例N=8。
S2. 計算處理所需擴散階段的數量round，round可根據網路建立規則和N進行調整，本例round 可取4。由X向Y的擴散記作EY=X[i] +Y[j]→Y[j]，由Y向X的擴散記作EX=Y[j]+X[i]→X[i]，i、j為元素索引。
S3. 第1階，組建擴散式分別為：
X[0]+Y[3]→Y[3], Y[3]+X[0]→X[0];
X[1]+Y[0]→Y[0], Y[0]+X[1]→X[1];
X[2]+Y[7]→Y[7], Y[7]+X[2]→X[2];
…
X[7]+Y[5]→Y[5], Y[5]+X[7]→X[7].
S4. 分別取出EY中的原體，分別使用函式FY計算結果後，更新EY中受體的各元素，即:Y[j] = FY(X[i], Y[j])。
S5. 分別取出EX中的原體，分別使用函式FX計算結果後，更新EX中受體的各元素，即X[i] = FX(X[i], Y[j]), 。
S6. 第2階，組建擴散式分別為：
X[0]+Y[5]→Y[5], Y[5]+X[0]→X[0];
X[1]+Y[3]→Y[3], Y[3]+X[1]→X[1];
X[2]+Y[4]→Y[4], Y[4]+X[2]→X[2];
…
X[7]+Y[1]→Y[1], Y[1]+X[7]→X[7];
然後執行S4、S5。
S7. 第3階，組建擴散式分別為：
X[0]+Y[2]→Y[2], Y[2]+X[0]→X[0];
X[1]+Y[4]→Y[4], Y[4]+X[1]→X[1];
X[2]+Y[0]→Y[0], Y[0]+X[2]→X[2]
…
X[7]+Y[3]→Y[3], Y[3]+X[7]→X[7];
然後執行S4、S5。
S6. 第4階，組建擴散式分別為：
X[0]+Y[0]→Y[0], Y[0]+X[0]→X[0];
X[1]+Y[1]→Y[1], Y[1]+X[1]→X[1];
X[2]+Y[2]→Y[2], Y[2]+X[2]→X[2];
…
X[7]+Y[7]→Y[7], Y[7]+X[7]→X[7];
然後執行S4、S5。
代碼實現
數據加密
/** * <p> * 套用擴散算法進行數據加密和解密示例（以兩組為例，分別為X和Y）。 * </p> * * * @version 2.0 * @author Angel * */public class CryptoDemo { /* * S盒子， 任意0~255之間的不重複隨機整數。 S盒子是用於數據加密時函式所使用的數據，用以消除線性。 S盒子的隨機性將會影響加密質量。 */ //@formatter:off public static final byte[] S = { (byte)0xd9, (byte)0x25, (byte)0x48, (byte)0x5c, (byte)0x55, (byte)0xa0, (byte)0x3c, (byte)0x94, (byte)0x83, (byte)0x36, (byte)0x11, (byte)0x74, (byte)0x69, (byte)0x2e, (byte)0x59, (byte)0x7b, (byte)0xd1, (byte)0x23, (byte)0x70, (byte)0x75, (byte)0x3a, (byte)0xbf, (byte)0x8c, (byte)0xd8, (byte)0x2f, (byte)0x34, (byte)0xb3, (byte)0x79, (byte)0xa4, (byte)0x27, (byte)0xa9, (byte)0x1d, (byte)0xb0, (byte)0xc8, (byte)0x38, (byte)0x8f, (byte)0x49, (byte)0x8b, (byte)0x89, (byte)0x0f, (byte)0x3b, (byte)0x92, (byte)0x33, (byte)0xcf, (byte)0xcd, (byte)0x1b, (byte)0x06, (byte)0xf0, (byte)0xfb, (byte)0x82, (byte)0xbb, (byte)0xc6, (byte)0xf2, (byte)0x07, (byte)0x4e, (byte)0xe8, (byte)0x77, (byte)0x6c, (byte)0x88, (byte)0x28, (byte)0xba, (byte)0xb9, (byte)0xe1, (byte)0xe9, (byte)0xd7, (byte)0x4b, (byte)0x81, (byte)0xde, (byte)0x08, (byte)0x0d, (byte)0xfc, (byte)0x03, (byte)0x87, (byte)0x56, (byte)0x14, (byte)0x0a, (byte)0x63, (byte)0x98, (byte)0x7a, (byte)0xf9, (byte)0x2c, (byte)0x7e, (byte)0x13, (byte)0x7d, (byte)0x04, (byte)0x01, (byte)0x9e, (byte)0xbc, (byte)0x41, (byte)0xdf, (byte)0x05, (byte)0x4f, (byte)0xfa, (byte)0x47, (byte)0x53, (byte)0xf8, (byte)0x46, (byte)0x52, (byte)0x8e, (byte)0x4a, (byte)0x76, (byte)0x09, (byte)0x1e, (byte)0xd2, (byte)0x2d, (byte)0x3e, (byte)0x61, (byte)0x5a, (byte)0x20, (byte)0x29, (byte)0xd0, (byte)0x16, (byte)0xb4, (byte)0x67, (byte)0xbd, (byte)0x50, (byte)0x60, (byte)0x35, (byte)0x19, (byte)0xd5, (byte)0xdd, (byte)0x8a, (byte)0xea, (byte)0xa5, (byte)0xac, (byte)0x1a, (byte)0x58, (byte)0x1f, (byte)0x5d, (byte)0x40, (byte)0x6d, (byte)0x86, (byte)0xeb, (byte)0x42, (byte)0x02, (byte)0x00, (byte)0xaa, (byte)0x9b, (byte)0xa1, (byte)0x7f, (byte)0xe4, (byte)0xb8, (byte)0xe6, (byte)0x21, (byte)0x68, (byte)0x12, (byte)0xd6, (byte)0x4d, (byte)0x4c, (byte)0x62, (byte)0xc0, (byte)0x66, (byte)0x0e, (byte)0x72, (byte)0x64, (byte)0xf6, (byte)0x80, (byte)0xb5, (byte)0xd4, (byte)0xf4, (byte)0x84, (byte)0x9d, (byte)0x73, (byte)0x51, (byte)0xe3, (byte)0x26, (byte)0xf3, (byte)0x1c, (byte)0x96, (byte)0xe2, (byte)0xcc, (byte)0x90, (byte)0xa3, (byte)0xc5, (byte)0xda, (byte)0xf7, (byte)0xad, (byte)0x6b, (byte)0x44, (byte)0x31, (byte)0xdb, (byte)0xa7, (byte)0xd3, (byte)0xfd, (byte)0xb2, (byte)0xcb, (byte)0xc7, (byte)0xf1, (byte)0x91, (byte)0x97, (byte)0xae, (byte)0xb6, (byte)0x45, (byte)0xc4, (byte)0xec, (byte)0xc2, (byte)0xce, (byte)0x18, (byte)0x3d, (byte)0xbe, (byte)0x7c, (byte)0xe5, (byte)0xb1, (byte)0xc9, (byte)0x0c, (byte)0x54, (byte)0x24, (byte)0x43, (byte)0x30, (byte)0x2a, (byte)0xb7, (byte)0xca, (byte)0x6e, (byte)0xc3, (byte)0x5b, (byte)0x9f, (byte)0x10, (byte)0xee, (byte)0x8d, (byte)0x95, (byte)0x32, (byte)0xc1, (byte)0x57, (byte)0x0b, (byte)0xed, (byte)0x99, (byte)0x5f, (byte)0xdc, (byte)0xaf, (byte)0x17, (byte)0xef, (byte)0xff, (byte)0x9c, (byte)0x9a, (byte)0x85, (byte)0x2b, (byte)0xab, (byte)0x5e, (byte)0xf5, (byte)0x6f, (byte)0xa6, (byte)0x39, (byte)0xa8, (byte)0x6a, (byte)0x3f, (byte)0x93, (byte)0x65, (byte)0xe0, (byte)0xfe, (byte)0x71, (byte)0x15, (byte)0x78, (byte)0x22, (byte)0xa2, (byte)0x37, (byte)0xe7, }; /* * 逆S盒子，設v是一個0~255之間的整數，_S必須滿足_S[S[v]] = v. */ public static final byte[] _S = { (byte)0x1c, (byte)0xc2, (byte)0xb1, (byte)0x88, (byte)0x20, (byte)0x6a, (byte)0x03, (byte)0xc8, (byte)0xba, (byte)0xa6, (byte)0xf9, (byte)0xa5, (byte)0x96, (byte)0x5a, (byte)0xe2, (byte)0xa3, (byte)0x2b, (byte)0x3c, (byte)0xa9, (byte)0x75, (byte)0x87, (byte)0x5b, (byte)0x28, (byte)0x3d, (byte)0xcd, (byte)0x61, (byte)0x69, (byte)0x09, (byte)0x68, (byte)0x21, (byte)0xd6, (byte)0x57, (byte)0x85, (byte)0x0a, (byte)0x7d, (byte)0x2c, (byte)0x9c, (byte)0xfb, (byte)0x70, (byte)0x35, (byte)0x72, (byte)0x9e, (byte)0x08, (byte)0x6c, (byte)0xfc, (byte)0x30, (byte)0x3e, (byte)0x64, (byte)0xa0, (byte)0x4a, (byte)0x38, (byte)0x9a, (byte)0xf0, (byte)0x1d, (byte)0x3f, (byte)0x52, (byte)0x0d, (byte)0xbd, (byte)0xbc, (byte)0xb2, (byte)0xd7, (byte)0xf2, (byte)0x47, (byte)0x95, (byte)0x16, (byte)0x5d, (byte)0x43, (byte)0x55, (byte)0x41, (byte)0x2d, (byte)0xb3, (byte)0x3a, (byte)0xa1, (byte)0x4b, (byte)0x53, (byte)0x39, (byte)0x2a, (byte)0xac, (byte)0x44, (byte)0xab, (byte)0xee, (byte)0x90, (byte)0xe7, (byte)0x36, (byte)0x1e, (byte)0xf7, (byte)0x12, (byte)0xc0, (byte)0x97, (byte)0x80, (byte)0x2e, (byte)0x34, (byte)0x63, (byte)0xf8, (byte)0xc3, (byte)0xd9, (byte)0x77, (byte)0xbe, (byte)0x29, (byte)0x24, (byte)0x0c, (byte)0x49, (byte)0x0e, (byte)0x7f, (byte)0xb7, (byte)0xbf, (byte)0xfa, (byte)0x04, (byte)0x42, (byte)0x60, (byte)0x59, (byte)0x66, (byte)0xaf, (byte)0x3b, (byte)0xb4, (byte)0x26, (byte)0x1f, (byte)0x6e, (byte)0x1b, (byte)0x2f, (byte)0xdf, (byte)0xcf, (byte)0xdc, (byte)0xb0, (byte)0xc6, (byte)0x37, (byte)0x78, (byte)0x67, (byte)0x07, (byte)0xd5, (byte)0x06, (byte)0xc7, (byte)0xd4, (byte)0xda, (byte)0xae, (byte)0xb5, (byte)0xc4, (byte)0xe5, (byte)0xcb, (byte)0x5f, (byte)0x4c, (byte)0xc5, (byte)0x18, (byte)0xa7, (byte)0x58, (byte)0x8a, (byte)0x11, (byte)0xd2, (byte)0xca, (byte)0x7a, (byte)0xef, (byte)0x65, (byte)0x45, (byte)0xf6, (byte)0xfd, (byte)0xad, (byte)0x27, (byte)0x9f, (byte)0xe6, (byte)0xff, (byte)0xec, (byte)0x0f, (byte)0x7c, (byte)0x91, (byte)0x4e, (byte)0x81, (byte)0x25, (byte)0x9d, (byte)0xbb, (byte)0xed, (byte)0x51, (byte)0x6b, (byte)0xd0, (byte)0xe8, (byte)0x8d, (byte)0x98, (byte)0x50, (byte)0x33, (byte)0x5c, (byte)0xaa, (byte)0x99, (byte)0xf5, (byte)0x89, (byte)0x7e, (byte)0xa2, (byte)0x71, (byte)0x94, (byte)0xa8, (byte)0x86, (byte)0x46, (byte)0xe9, (byte)0x74, (byte)0x01, (byte)0xd8, (byte)0x05, (byte)0x4f, (byte)0x32, (byte)0x40, (byte)0xe0, (byte)0xdd, (byte)0x82, (byte)0xa4, (byte)0xe3, (byte)0xc1, (byte)0x14, (byte)0x13, (byte)0xb6, (byte)0xdb, (byte)0xf3, (byte)0x23, (byte)0xe1, (byte)0xde, (byte)0x4d, (byte)0x84, (byte)0xc9, (byte)0x5e, (byte)0xfe, (byte)0x8e, (byte)0xeb, (byte)0x56, (byte)0x83, (byte)0x00, (byte)0x6d, (byte)0x62, (byte)0xf4, (byte)0xea, (byte)0x15, (byte)0xcc, (byte)0x1a, (byte)0x76, (byte)0x17, (byte)0xf1, (byte)0x10, (byte)0x8c, (byte)0x73, (byte)0x31, (byte)0xb9, (byte)0x02, (byte)0x54, (byte)0x6f, (byte)0x92, (byte)0x79, (byte)0x19, (byte)0x22, (byte)0x8b, (byte)0x93, (byte)0xe4, (byte)0xb8, (byte)0x7b, (byte)0x9b, (byte)0xce, (byte)0x8f, (byte)0x48, (byte)0xd3, (byte)0xd1, (byte)0x0b, }; static long LONG_TEN = 100000000000000L; int E = 2; // 額外的循環數量E int N; // 分組長度N int P; // 基於長度N的完美長度。 int round; // 用於加密的輪數（對應擴散階段的數量）。 byte[][] KX; // 用於加密的子密匙（X）， 每一輪的密匙都不相同。 byte[][] KY; // 用於加密的子密匙（Y）， 每一輪的密匙都不相同。 // @formatter:on public CryptoDemo(int keySize) { // keySize:byte N = keySize; int G = (int) Math.ceil(Math.log(N) / Math.log(2)); // 計算以2為底N的對數,並向上取整 P = 1 << G; // P=2的G次方 round = G + E; KX = new byte[round][]; KY = new byte[round][]; } /** * 生成子密匙， 通過擴散算法使得原密匙的每一個密匙都影響其它任何一個密匙。 * <p> * 每個周期完成後，將本周的輸出作為下一個周期的輸入再計運算元密匙。共需round個周期。 * </p> * * @param kx * 原始密匙X * @param ky * 原始密匙Y */ public void init(byte[] kx, byte[] ky) { for (int i = 0; i < round; i++) { init(kx, ky, i); } } Function FKx = new XKey(); // 用於生成子密匙的函式X Function FKy = new YKey(); // 用於生成子密匙的函式Y private void init(byte[] kx, byte[] ky, int index) { int l = 0; for (int i = 1; i <= round; i++) { for (int r = 0; r < N; r++) { ky[r] = (byte) (FKy.call(kx[l], ky[r]) & 255); kx[l] = (byte) (FKx.call(kx[l], ky[r]) & 255); l = (++l) % N; } l = P >> i; } KX[index] = kx.clone(); KY[index] = ky.clone(); } /** * 用於生成子密匙的函式X實現。 * * @author Angel * */ class XKey implements Function { int A = 11; int B = 21; int C = 31; @Override public int call(int x, int y, int... values) { return A * x * x + B * y + C; } } /** * 用於生成子密匙的函式Y實現。 * * @author Angel * */ class YKey implements Function { long C = 0x6180339887L; @Override public int call(int x, int y, int... values) { double a = Math.sin(x); double b = Math.cos(y); long v = (long) ((a + b) * LONG_TEN + C); return (int) (v & 0xffffffff); } } // ---------------------------------------------------------------------------- Function Ex = new XEncrypt(); // 用於加密進行擴散運算的函式X Function Ey = new YEncrypt(); // 用於加密進行擴散運算的函式Y /** * 加密明文。次方法只加密一組數據，X,Y的長度為N。 * * @param X * 明文X * @param Y * 明文Y */ public void encrypt(byte[] X, byte[] Y) { int x = 0; for (int i = 1, k = 0; i <= round; i++, k++) { for (int y = 0; y < N; y++) { Y[y] = (byte) Ey.call(X[x], Y[y], KY[k][y]); X[x] = (byte) Ex.call(X[x], Y[y], KX[k][y]); // KX[k][x] // 不建議使用%運算 // 當N&(N-1)=0時，可使用&運算，即N=2的j次方（j>0,且j為整數） x = (++x) % N; // x = (++x) & (N-1); } x = P >> i; } } /** * 用於加密算法的函式X實現。 * * @author Angel * */ class XEncrypt implements Function { /** * 由於java中byte的值域為[-128,127],因此需要將運算後的值加128以改變值域為[0,255]（余同）。 * * <p> * 此處為行方便，特將key以其他參數的第0位傳入(余同)。 * </p> */ @Override public int call(int left, int right, int... values) { // values[0] is key return S[(left ^ values[0]) + 128] ^ right; } } /** * 用於加密算法的函式Y實現。 * * @author Angel * */ class YEncrypt implements Function { @Override public int call(int left, int right, int... values) { // values[0] is key return S[(right ^ values[0]) + 128] ^ left; } } // ------------------------------------------------------------------------ Function Dx = new XDecrypt(); // 用於解密進行擴散運算的函式X Function Dy = new YDecrypt(); // 用於解密進行擴散運算的函式Y /** * 解密密文，次方法只解密一組數據，X,Y的長度為N。 * * @param X * 密文X，對應加密後所輸出的X * @param Y * 密文Y，對應加密後所輸出的Y */ public void decrypt(byte[] X, byte[] Y) { int x = 0; int k = round - 1; for (int i = 0; i < round; i++, k--) { for (int y = 0; y < N; y++) { X[x] = (byte) Dx.call(X[x], Y[y], KX[k][y]); // KX[k][x] Y[y] = (byte) Dy.call(X[x], Y[y], KY[k][y]); x = (++x) % N; // x=(++x)&(N-1); and N&(N-1)=0 } x = (1 << i) % P; // x=(1<<i)&(P-1); and P&(P-1)=0 } } /** * 用於解密算法的函式X實現。 * * @author Angel * */ class XDecrypt implements Function { @Override public int call(int left, int right, int... values) { // values[0] is key return _S[(left ^ right) + 128] ^ values[0]; } } /** * 用於解密算法的函式Y實現。 * * @author Angel * */ class YDecrypt implements Function { @Override public int call(int left, int right, int... values) { // values[0] is key return _S[(right ^ left) + 128] ^ values[0]; } } // --------------------------------------------------------------------------- static interface Function { int call(int left, int right, int... values); } static void print(byte[] array) { for (byte b : array) { String s = Integer.toHexString(b & 0xff); if (s.length() == 1) { s = '0' + s; } System.out.print(s + ", "); } } // -------------------------------------------------------------------------- /** * 微變加密測試， 每次加密只需改變原輸入的一個元素（可以是密匙或者明文）。 * 不建議使用弱密匙，當所有左密匙的元素相等且所有右密匙的元素都相等時為弱密匙，即： * <p> * LK[0]=LK[1]=LK[2]=...=LK[n]; RK[0]=RK[1]=RK[2]=...=RK[n]; * </P> */ public static void microChangeTest() { String line = "------------------------------------------------------------------------------------------"; int length = 9; byte[] KX = { 1, 1, 1, 1, 1, 1, 1, 1, 2 }; // 密匙X（不能全部相等） byte[] KY = { 1, 1, 1, 1, 1, 1, 1, 1, 2 }; // 密匙Y（不能全部相等） byte[] MX = { 1, 1, 1, 1, 1, 1, 1, 1, 1 }; // 明文X byte[] MY = { 1, 1, 1, 1, 1, 1, 1, 1, 1 }; // 明文Y CryptoDemo demo = new CryptoDemo(length); for (int i = 0; i < 256; i++) { demo.init(KX, KY); // 初始化密匙 byte[] TX = MX.clone(); byte[] TY = MY.clone(); System.out.print("明 文："); print(TX); print(TY); System.out.println(); demo.encrypt(TX, TY); System.out.print("加密後："); print(TX); print(TY); System.out.println(); byte[] CX = TX.clone(); byte[] CY = TY.clone(); demo.decrypt(CX, CY); System.out.print("解密後："); print(CX); print(CY); System.out.println(); MX[0]++; // 更改原數據 System.out.println(line); } } public static void main(String[] args) { microChangeTest(); }}計算訊息摘要
import java.io.IOException;import java.io.InputStream;/** * 套用擴散算法生成訊息摘要的示例。 * <p> * 此示例使用有序的網路規則。訊息摘要長度被定義為16個位元組（即128位，可定義為任意長度，以位元組為單位）。 * </P> * * @version 2.0 * @author Angel */public class MessageDigestDemo { long LONG_TEN = 100000000000000L; /* * 訊息摘要元數據，元數據可以是任意不全相等的數字。 * 訊息摘要元數據是為確保所生成有效數據的保障，否則當輸入數據不滿足某些條件時，會導致生成的訊息摘要無效 */ //@formatter:off static final byte[] METADATA = new byte[] { (byte)0x19, (byte)0xd5, (byte)0xdd, (byte)0x8a, (byte)0xff, (byte)0xa5, (byte)0xac, (byte)0x1a, (byte)0x58, (byte)0x1f, (byte)0x5d, (byte)0x40, (byte)0x6d, (byte)0x86, (byte)0xeb, (byte)0x42, }; int N = 8; // 分組長度 int size = 2 * N; // 訊息摘要長度 int E = 1; // 額外的循環輪數 int P; // 基於長度N的完美長度 int round; // 完成完全擴散所需的階段數量 byte[] buf; // 用於存儲訊息摘要數據的快取區 //@formatter:on public MessageDigestDemo() { int G = (int) Math.ceil(Math.log(N) / Math.log(2)); P = 1 << G; round = G + E; } /** * 對一組訊息生成訊息摘要數據。 */ protected void run(byte[] message) { int x = 0; for (int i = 1; i <= round; i++) { for (int y = N; y < size; y++) { buf[y] = (byte) (Fy(buf[x], buf[y], message[x]) & 255); buf[x] = (byte) (Fx(buf[x], buf[y], message[x]) & 255); x = (++x) % N; // should not use % } x = (P >> i); } } public int Fx(int x, int y, int m) { return 111 * x + 121 * y + 131 * m + 0x5201314; } public int Fy(int x, int y, int m) { double a = Math.sin(x); double b = Math.cos(y); double c = Math.tan(m); long v = (long) ((a + b + c + 3.1415926535897) * LONG_TEN); return (int) (v & 0xffffffff); } /** * 根據傳入的輸入流生成訊息摘要數據，當讀取完輸入流之後，需要對數據進行補齊。 * <p> * 補齊的方式為：如果最後讀取的數據長度不足N（N是分組長度，這裡是8），則從結束位置開始，依次從1~N按順序填充。 如果最後讀取的數據長度恰好是N， * 則仍需要填充一組數據。 * </p> * * @param in * 輸入流 * @return 訊息摘要數據 * @throws IOException */ public byte[] run(InputStream in) throws IOException { buf = METADATA.clone(); byte[] code = new byte[N]; int count = 0; do { count = in.read(code); count = Math.max(0, count); if (count < N) { fill(code, count, (N - count)); } run(code); } while (count >= N); return buf; } /** * 向code裡面填充數據，填充方式為從起始位置開始，順序填入1~length的值。 * * @param code * 要填充的數組 * @param start * 起始位置 * @param length * 填充長度 */ public void fill(byte[] code, int start, int length) { for (int i = 0; i < length; i++) { code[i + start] = (byte) (i + 1); } } // --------------------------------------------------------------------- static class ByteInputStream extends InputStream { static final String DEF_CHARSET = "UTF-8"; byte[] buf; int index = 0; int size; ByteInputStream(byte[] message) { buf = message; size = buf.length; } @Override public int read() throws IOException { if (index >= size) { return -1; } return buf[index++]; } } public static String toHex(byte[] code) { StringBuffer buf = new StringBuffer(); for (int i = 0; i < code.length; i++) { String hex = Integer.toHexString(code[i] & 0xff); if (hex.length() == 1) { hex = '0' + hex; } buf.append(hex); } return buf.toString(); } // ------------------------------------------------------------------------- public static void main(String[] args) throws Exception { MessageDigestDemo demo = new MessageDigestDemo(); String message = "change char to test"; byte[] array = message.getBytes(); // byte[] array = { -128, 127, 125, -109, 13, -99, -101, 99 }; // 指定要生成訊息摘要的檔案 // String src = "message_digest.txt"; // InputStream in = MessageDigestDemo.class.getResourceAsStream(src); for (int i = 0; i < 255; i++) { InputStream in = new ByteInputStream(array); byte[] code = demo.run(in); System.out.println(toHex(code)); array[0]++; } }}生成隨機數
/** * 套用擴散算法生成隨機數的示例，此示例不是執行緒安全的。 * <p> * 此示例使用有序的網路規則，內設一個32位元組的隨機數快取區。每次獲取隨機數時，從緩衝區中讀取一個位元組。 * 當快取區讀取滿後，以快取區的內容作為輸入重新生成隨機數。 * </p> * * <p> * 此隨機數所生成的數字不是真正隨機的，僅當做擴散運算生成隨機數的示範。 * </p> * * @author Angel * */public class RandomDemo { //@formatter:off static final byte[] S = { (byte)0xaf, (byte)0x6c, (byte)0xae, (byte)0xdf, (byte)0x93, (byte)0x18, (byte)0x73, (byte)0x46, (byte)0x8f, (byte)0x5a, (byte)0x58, (byte)0xd4, (byte)0x22, (byte)0xe5, (byte)0x36, (byte)0x91, }; //@formatter:on static int N = 16; // may change to other number int size = 2 * N; byte[] seed; byte[] buf = new byte[size]; int G; int P; int round; int index = 0; public RandomDemo(long seed) { this(convert(seed)); } public RandomDemo(byte[] seed) { setSeed(seed); G = (int) Math.ceil(Math.log(N) / Math.log(2)); P = 1 << G; round = G + 1; produce(); } public byte next() { if (index == N) { produce(); index = 0; } return buf[index++]; } public void nextBytes(byte[] bytes) { int len = bytes.length; for (int i = 0; i < len; i++) { bytes[i] = next(); } } // Should be private // produce random number and put in buffer public void produce() { int x = 0; for (int i = 1; i <= round; i++) { for (int y = N; y < size; y++) { buf[y] = (byte) (Fx(buf[y], buf[x]) & 255); buf[x] = (byte) (Fy(buf[x], buf[y]) & 255); x = (++x) % N; // should not use % } x = (P >> i); } } private int Fy(int x, int y) { return 49 * x + 71 * y + 0x9527; } private int Fx(int x, int y) { int v = x ^ y; int h = v >> 4 & 0xF; int l = v >> 0 & 0xF; return 31 * S[h] + 119 * S[l]; } public void setSeed(long seed) { setSeed(convert(seed)); } public void setSeed(byte[] seed) { this.seed = seed; for (int i = 0; i < N; i++) { if (i < seed.length) { buf[i] = seed[i]; } else { buf[i] = (byte) i; } } } static byte[] convert(long seed) { byte[] b = new byte[8]; b[0] = (byte) (seed >> 0 & 0xFF); b[1] = (byte) (seed >> 8 & 0xFF); b[2] = (byte) (seed >> 16 & 0xFF); b[3] = (byte) (seed >> 24 & 0xFF); b[4] = (byte) (seed >> 32 & 0xFF); b[5] = (byte) (seed >> 40 & 0xFF); b[6] = (byte) (seed >> 48 & 0xFF); b[7] = (byte) (seed >> 56 & 0xFF); return b; } static String toHex(byte value) { String hex = Integer.toHexString(value & 0xFF); if (hex.length() == 1) { return '0' + hex; } return hex; } static String toHex(long value) { String hex = Long.toHexString(value); if (hex.length() == 1) { return '0' + hex; } return hex; } static boolean match(byte[] src, byte[] dest, int N) { for (int i = 0; i < N; i++) { if (src[i] != dest[i]) { return false; } } return true; } public static void main(String[] args) { RandomDemo random = new RandomDemo(System.currentTimeMillis()); byte[] cache = random.buf.clone(); long count = 100000000000L; for (long i = 1; i < count; i++) { // System.out.print(toHex(r.next()) + ", "); // if (i % r.N == 0) { // System.out.println(); // } random.produce(); if (match(cache, random.buf, N)) { System.out.println("Repeat at: 0x" + toHex(i)); break; } if ((i & 0xFFFFFF) == 0) { System.out.println("At: 0x" + toHex(i)); } } System.out.println("Wonderful !"); }}