密碼學(xué)之代換-置換網(wǎng)絡(luò)（SPN）

2021-05-11 21:34 作者:剎那-Ksana- 0人讀過(guò) | 我要投稿

前言

今天繼續(xù)寫(xiě)一些有關(guān)密碼學(xué)的東西。

一、術(shù)語(yǔ)及基礎(chǔ)知識(shí)

和前文一樣，括號(hào)內(nèi)的中文都是用google translate翻譯過(guò)來(lái)的，未必準(zhǔn)確。

Symmetric key algorithms（對(duì)稱(chēng)密鑰算法）: 加密和解密都是用的同一個(gè)key的算法

Bijective（雙射）：同時(shí)滿(mǎn)足injective（內(nèi)射）和surjective（外射）。X中的每一個(gè)元素都與Y中的某個(gè)元素對(duì)應(yīng)，Y中的每一個(gè)元素都與X中的某個(gè)元素對(duì)應(yīng)。

二、Block Cipher（分組密碼）

Block cipher 是通過(guò)一個(gè)長(zhǎng)度為 $n$ 的key $k%5Cin%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%5En%20$ ，進(jìn)行一個(gè)bijective mapping? $E_k%3A%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5El%5Crightarrow%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5El$ , $D_k%3A%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5El%5Crightarrow%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5El$ .?

這里 $l$ 叫做block length，一般 $l$ 都有一個(gè)固定的值（我們可以看成是“預(yù)設(shè)值”），比如說(shuō) $l%3D128$ .?

在這里，我們假設(shè)我們的 $l%3D2$ ，那么我們就有4種不同的值：00,01,10,11，然后這四種不同的值有 $2%5E2!$ 種不同的permutation（排列組合）。比方說(shuō)，00,01,11,10，是key=1時(shí)的排列組合，key=2時(shí)我們又有一種其他的排列組合。這時(shí)候我們就可以通過(guò)一個(gè)表格，將所有不同key情況下的排列組合記錄下來(lái)。

我們有了這個(gè)表格以后，當(dāng)我們指定某個(gè)key，比方說(shuō) $k%3D2$ 的時(shí)候，我們就可以有如下從plaintext到ciphertext的映射： $E_%7Bk%3D2%7D%3D%5Cleft%5C%7B%2000%3A00%2C01%3A11%2C10%3A01%2C11%3A10%20%5Cright%5C%7D%20$

但是，可以想象，如果當(dāng) $l%3D128$ 時(shí)，我們需要一張巨大到不存在的表格來(lái)存儲(chǔ)這些信息。這個(gè)時(shí)候，我們需要用其他辦法來(lái)生成我們的permutation.

三、核心思想

我們現(xiàn)在希望用另一種算法來(lái)替代我們的表格，我們雖然還不知道我們的算法是什么，但是我們希望我們的算法具有一定的隨機(jī)性，就算輸入的兩個(gè)值差異很小，對(duì)應(yīng)輸出的ciphertext也要有很大的差異性。

一個(gè)很經(jīng)典的方法就是將我們的block拆分成長(zhǎng)度相等的小型block，比方說(shuō)，當(dāng)我們block長(zhǎng)度為128時(shí)候，我們就可以拆分為16個(gè)8 bits的更小的block $x_1%2C%20x_2%2C%20...%2C%20x_%7B16%7D$ ， $x_i%5Cin%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5E8$ 。我們對(duì)每一個(gè) $x_i$ 進(jìn)行加密，最后將這些block用一種特定的方法組裝起來(lái)。

*注意，最后的組裝并不是直接將所有 $x_i$ 按照順序拼裝起來(lái)（不然，這樣就等價(jià)于block長(zhǎng)度為8了）。拼裝方法不唯一，但要保證輸入值中的每一個(gè)bit都能對(duì)輸出值的所有bit產(chǎn)生影響。

最后，我們重復(fù)剛才拆分拼裝的步驟多次。

四、Substitution-permutation networks（代換-置換網(wǎng)絡(luò)）

SPN的核心思想就是上述的思想。在SPN里面，我們有一個(gè)Substitution box（簡(jiǎn)稱(chēng)S-Box），S-box是一個(gè)對(duì)小型block加密的算法——最簡(jiǎn)單的，我們可以設(shè)計(jì)一個(gè)的表格，然后對(duì)于一個(gè)輸入值x，我們查詢(xún)表格輸出一個(gè)y。

對(duì)于輸入值 $x%5Cin%20%5Cleft%5C%7B%200%2C1%20%5Cright%5C%7D%20%5El$ ，做如下的事情：

從key里面抽取一個(gè)round key? $k%E2%80%99%3DF(k)$ ，F(xiàn)在這里只是一個(gè)形式，并不代表一定要用某個(gè)函數(shù)來(lái)獲取round key
計(jì)算 $x'%3Dx%5Coplus%20k'$
將 $x'$ 拆分為多個(gè)小型的block? $x_1%2Cx_2%2C...%2Cx_t$
計(jì)算 $x'_i%3DS(x_i)%2Ci%3D1...t$
將每一個(gè)小型的block? $x_i'$ 按照一定的方式重組
重復(fù)以上步驟多次。