對稱加密如何實現？

1.對稱密碼基礎

加密是為了防止要傳達的內容被別人知道。例如，你如果想在課堂上傳小紙條給后位小紅說：i love coding，但又怕在遞紙條的過程中被老師看到，知道了你的心思，于是將每個字母變字母表中的后一個字母（如a變成b，i變成j，z變成a），得到密文：j mpwf dpejoh，這樣即老師人拿到這紙條，也不知道你說的是什么。

這就是一個加密的過程，把原本的內容稱為明文，一般用p表示；加密后得到的內容稱為密文，一般用c表示；而加密的這個過程可以看做是一個加密函數E，即

c=E(p)

E是指Encrypt，函數輸入是明文，輸出是加密之后的密文。上面的例子中i love coding便是明文，j mpwf dpejoh便是密文，而把字母在字母表中向后移動一位的操作就是加密函數。

在小紅得到小紙條后，可以根據你加密的方法，將每個字母變成字母表中的前一個字母，就可以從你的密文小紙條得到你要說的內容i love coding，心領神會，順便還會懷疑一下你的腦袋……無論怎樣，這個解密的過程就也可以看做是一個解密函數D，即

p=D(c)

D是指Decrypt，函數輸入是密文，輸出是解密之后的明文。

在這個過程這種，小紅能夠成功解密小紙條的前提是，你得和她在課前約定好你加密的時候移動的是1位，2位還是幾位，不然他就會和老師一樣一臉懵逼，不知道你在說啥。你們提前約定好的這個“幾位”，就是加密和解密的密鑰k，你會根據這個秘鑰來進行加密，小紅會根據這個秘鑰來進行解密。

所以你的傳紙條的動作抽象成這個過程：

明文p---->加密函數E---->密文c---->傳輸---->密文c----->解密函數D---->明文p

或者用公式來表達是：

c=Dk(Ek(c))

用大白話說就是：明文用同一個密鑰先加密再解密得到的還是同一個明文（等于沒說…）

從這里我們可以總結出加密體質的五個要素：{明文p，密文c，密鑰k，加密函數E，解密函數D}，對稱解密的的意思就是說，加密和解密的密鑰是一樣的，上面的過程是不是正好很對稱呢?

為了方便使用，不用每次自己手動掰手指數字符，你還寫了Python程序：

# 移位密碼

def _move_leter(letter, n):

"""

把字母變為字母表后n位的字母,z后面接a

:param letter: 小寫字母

:param n: 要移動的字母

:return: 移動的結果

"""

return chr((ord(letter) - ord('a') + n) % 26 + ord('a'))

def Encrypt(k, p):

"""

移位密碼加密函數E

:param k: 秘鑰k,每個字母在字母表中移動k位

:param p: 明文p

:return: 密文c

"""

letter_list = list(p.lower())

c = ''.join([_move_leter(x, k) for x in letter_list])

return c

def Decrypt(k, c):

"""

移位密碼解密函數D

:param k: 秘鑰k,每個字母在字母表中移動k位

:param c: 密文c

:return: 明文p

"""

letter_list = list(c.lower())

p = ''.join([_move_leter(x, -k) for x in letter_list])

return p

if __name__ == '__main__':

p = 'ilovecoding'

print('明文：' + p)

print('密文：' + Encrypt(1, p))

print('解密：' + Decrypt(1, Encrypt(1, p)))

assert Decrypt(1, Encrypt(1, p)) == p

運行這段代碼，就可以看到輸出了：

明文：ilovecoding

密文：jmpwfdpejoh

解密：ilovecoding

終于，現在你能和你的小紅秘密地傳達紙條內容了，迎來全班人羨慕的目光，從此走上人生巔峰，本文到此結束。

…Hey，醒醒…

2.密碼分析

面對你倆日益頻繁的紙條往來，老師終于坐不住了，他想知道你倆寫的到底是啥，于是在某次逮到你遞紙條之后，決定下功夫破解你所使用的密碼，也就是密碼分析。

根據他的了解，以你的水平，最可能用的就是移位密碼，但具體每次移動了幾位，無法直接觀察得出。不過他又一想，你移動的位數頂多是25位，因為，移動26位的效果等于沒移動，移27位的效果不就跟移動1位的效果是一樣的嘛！這就是說，你的密碼只能是0-25中的某一個數字，而不可能是其他的，就這么二十幾個秘鑰，一個一個試就能知道你寫的是啥！

老師果然聰明絕頂，關鍵是也還會Python，就索性寫了一個程序，每次嘗試用不同的秘鑰來進行解密，并觀察解密出來的內容是否有意義：

def analyze(c):

"""

移位密碼分析

:param c: 密文c

:return:

"""

for k in range(26):

# 用不同的秘鑰k嘗試解密

print('秘鑰%d：' % k + Decrypt(k, c))

if __name__ == '__main__':

c = 'jmpwfdpejoh'

analyze(c)

運行程序輸出結果為：

秘鑰0：jmpwfdpejoh

秘鑰1：ilovecoding

秘鑰2：hknudbnchmf

秘鑰3：gjmtcambgle

...........

逐行觀察輸出結果，到第二行的時候就能看到原來的明文，也就知道了你要對小紅說的內容以及你們所約定的秘鑰。面對你冒著巨大風險在課堂上所傳遞的紙條內容，老師心里可能也是復雜的…

Anyway，你的小秘密已經被老師知道了，此時比較灰心，一直在想，究竟是什么原因致使紙條計劃失敗？其實原因很明顯，各位也看出來了，小明所使用的加密體制中，可用的秘鑰太少，或者說秘鑰空間太小，別人直接一一列舉進行窮搜就能破解，這就提示我們：一個好的加密體制，它的秘鑰空間應該是足夠大的。

其實，你此次所用的移位密碼是古典的加密體制之一，據說凱撒打仗時就用這種方法與將軍們聯系，所以位移密碼也叫凱撒密碼（Caesar cipher）。類似的還有代換密碼，仿設射密碼等等，都是將單個字母替換成別的字母，來達到加密的目的。報紙上的猜謎游戲就經常用這些方法，一般根據字母頻率進行破解，有興趣可以進行進一步的了解。

所以到底要用什么樣的加密方法，才能保證我和小紅的秘密不被人偷窺呢？

2.1 密碼分析情形

俗話說，知己知彼，百戰不殆，了解破解者的密碼分析方法，或許能夠幫助我們想出更安全的密碼體制。可以在不同的情形下考察密碼體制的安全性，一般我們都假設破解者知道我們所使用的密碼體制，也就是說，不把密碼體制的安全性寄托在加密和解密方法的保密性上，而是放在秘鑰上。

破解者的目的就是找出所使用的秘鑰，常見的有以下幾種攻擊情形：

唯密文攻擊： 破解者擁有密文c。這就是老師破解紙條的情形。

已知明文攻擊： 破解者擁有一些明文p及其對應的密文c。考慮到實際情形，這個假設是比較合理的，例如破解者獲得一封郵件加密后的密文，可以猜測一個詞很可能是'hi'或者'dear'，這樣就可能找到一個明文–密文對。

選擇明文攻擊： 破解者能夠指定一個明文p，獲得其對應的密文c，較強的假設。

選擇密文攻擊： 破解者指定一個密文c，獲得其對應的明文，較強的假設。

天啊，你不禁驚呼，在這么強的假設下，真的會有密碼體制能夠存活嗎？

答案是有，而且這種密碼體制已經被廣泛應用，甚至可以說無處不在，它就是AES（Advanced Encryption Standard）。

3.SPN網絡

難道不是要介紹AES嗎，怎么會變成SPN網絡，這是啥？可以吃嗎？

AES、DES等很多現代對稱加密方法的核心就是SPN網絡，它是代換-置換網絡（Substitution-Permutation Network）的縮寫，是現代對稱加密方法設計的藍本。可以說，了解SPN網絡，就基本了解了AES。

很巧的是，這個網絡正好是容易理解的。SPN網絡的思想很簡單：既然加密一次不夠安全，那我就加密多次，把第一次加密產生的密文再進行加密，解密的時候我連續進行兩次解密就可以了，這樣是不是就安全了一些呢？

對于密碼體制 S1 ，其加密與解密函數為 E1 與 D1，對于密碼體制 S2，其加密與解密函數為 E2 與 D2 ，我構造出一個新的密碼體制 S3，其加密函數為：

c=E2（E1(p)）

解密函數為：

p=D1(D2(c))

記為 S3=S1*S2

這樣破解 S3 就可能會困難些。這個想法是不是很直接呢？這個思想在1949年才被提出，而提出者，可能理科生都多少聽過他的名字——香農（Shannon）。

注意，不是任何的加密體制都可以這樣“乘”起來變得更強，例如對于你的移位密碼，嵌套起來還是移位密碼（為什么？），沒有任何改善，即 S1*S1=S1，這樣的密碼體制被稱為冪等的。

如果密碼體制不是冪等的，那么多次迭代就可能能夠提高安全性，SPN就是使用這種思想，包含多輪的迭代，每輪的操作都是相同的。下面，介紹SPN單輪的操作：

3.1 SPN單輪操作

SPN網絡是對一定長度的比特進行操作的，在本文中的SPN網絡中，一次加密的長度為16個比特，即2字節，也就是說每次加密16比特的明文，輸出16比特的密文。

一個SPN網絡包含多輪迭代，每輪迭代的操作內容都一樣是：異或運算–>分組代換–>單比特置換

3.1.1 第一步——異或運算

異或運算是比較常見的二元比特運算，用⊕表示，其規則就是“相同得0，不同得1”：

0 ⊕ 0 = 0

1 ⊕ 1 = 0

1 ⊕ 0 = 1

0 ⊕ 1 = 1

對于比特串，直接按每一位對應進行計算即可以了：

0011 ⊕ 1010 = 1001

異或的有比較有意思的性質：一個比特串亦或另一個比特串兩遍，還是等于他自己，即a ⊕ b ⊕ b = a，這是因為a ⊕ b ⊕ b = a ⊕ ( b ⊕ b ) =a ⊕ 0 = a，可以帶入一些例子試試看。

SPN網絡中，每一輪的第一步就是把輸入的比特串w和秘鑰k進行亦或：u = w ⊕ k，如：

0001110000100011 = 0010011010110111 ⊕ 0011101010010100

這一步的目的是根據秘鑰對明文進行混淆。如果你只知道輸出u而不知道秘鑰k，那么你就猜不出實際輸入的w是什么，它是什么都可能，而且是等概率的。例如對于1 = a ⊕ b，不告訴你b是0還是1，你就不知道a是什么。而對于和操作，如果知道1 = a and b，那么就能確定a與b都是1。

這就是第一步，是不是很簡單呢？

3.1.2 第二步——分組代換

這一步也很簡單，將第一步輸出的16比特的串分為4組，每組4比特，即0001110000100011寫成0001 1100 0010 0011。然后對于每組再根據事先所定的表進行代換，代換表長這樣：

圖1

就拿第一列來說，表的意思是：如果你是0（0000），那么我要把你換成成E（1110），就是一個簡單的映射操作。

原比特串長這樣：0001 1100 0010 0011 <==> 1 C 2 3，再對每個字母查表得到：4 5 D 1 <==> 0100 0101 1101 0001，這樣就得到代換后的比特串0100 0101 1101 0001，完成了第二步。

這個表一般稱為S盒（Substitution），這個過程可以用v = S(u)表示，u是第一步異或的結果，也是第二步分組代換的輸入，v是第二步的輸出。需要注意，S盒的輸入和輸出一般是非線性的關系。

3.1.3 第三步——單比特置換

單比特置換是將16比特中的每一比特，根據P盒（Permutation）移動挪位，這樣說很不直觀，直接上例子，P盒長這樣：

圖2

拿第二列來說，表的意思是：第2個比特要挪到第5個比特的位置，舉個好看的例子：

0100 0000 0000 0000 置換后為==> 0000 1000 0000 0000

這個例子里面第二個比特的1挪到了第五的位置，而其他位置的比特都是0，挪位置之后還是0。

對于第二部輸出的結果1100 1101 1100 0100，置換后的比特串為0010 1110 0000 0111，這樣就完成了第三步。

這一步可以用W = S(v)表示，v是第二部的輸出，也是第三步的輸入，W是第三步的輸出，P盒置換是一種線性的變換。

這三步放在一起結果如下，建議讀者自己計算一遍：

w = 0010 0110 1011 0111

k = 0011 1010 1001 0100

第一步，異或運算：

u = w ⊕ k = 0001 1100 0010 0011

第二步，分組代換：

v = S(u) = 0100 0101 1101 0001

第三步，單比特置換：

W = P(v) = 0010 1110 0000 0111

可以寫成：W = P( S(w ⊕ k) )，這樣就完成了一輪迭代，里面用到的參數有k，S盒與P盒，如圖（圖片來自維基百科）：圖3

3.2 SPN的多輪迭代

弄清楚一輪的流程，SPN整體就很容易明白了，就是一輪一輪的乘起來，上一輪的輸出作為這一輪的輸入：

w0 = x

w1 = P(S(w0 ⊕ k1))

w2 = P(S(w1 ⊕ k2))

w3 = P(S(w2 ⊕ k3))

w4 = P(S(w3 ⊕ k4))

y = w4

w0就是16比特的明文，w4是4輪操作后的16比特密文結果，是不是很簡單？需要注意的是，每一輪迭代的秘鑰k是不一樣的，一般是由一個基礎秘鑰經特定秘鑰編排算法生成的，而使用的S盒P盒都是相同的，會提前確定好，并且是公開的。

下圖是一個三輪SPN網絡的示意圖（圖片來自維基百科）：圖4

注意在最后一輪去掉了代換操作，這樣做可以使加密算法稍微做一些調整就可以用來進行解密。

OK! SPN網絡就是這些內容，你已經掌握了它，如果你還想和小紅傳紙條的話，可以試試用它加密，會比移位密碼更安全一些。

什么？自己手動代換置換太麻煩？不用怕，貼心的我已經為你準備好了Python代碼。

3.3 用Python實現SPN網絡

我實現的是4輪迭代的SPN網絡，以及加密和解密算法，其結構圖如下（圖片來自 Cryptography Theory and Practice ）：圖5

每次加密輸入16比特的明文，輸出16比特的密文，代碼如下：

# S盒參數

S_Box = [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7]

# P盒參數

P_Box = [1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]

def gen_K_list(K):

"""

秘鑰編排算法，由一個32比特秘鑰生成5個16比特子秘鑰

:param K: 32比特秘鑰

:return: [k1,k2,k3,k4,k5]，五個16比特子秘鑰

"""

Ks = []

for i in range(5, 0, -1):

ki = K % (2 ** 16)

Ks.insert(0, ki)

K = K >> 4

return Ks

def pi_s(s_box, ur):

"""

分組代換操作

:param s_box:S盒參數

:param ur:輸入比特串，16比特

:return:輸出比特串，16比特

"""

vr = 0

for i in range(4):

uri = ur % (2 ** 4)

vri = s_box[uri]

vr = vr + (vri << (4 * i))

ur = ur >> 4

return vr

def pi_p(p_box, vr):

"""

單比特置換操作

:param p_box:P盒參數

:param vr:輸入比特串，16比特

:return:輸出比特串，16比特

"""

wr = 0

for i in range(15, -1, -1):

vri = vr % 2

vr = vr >> 1

wr = wr + (vri << (16 - p_box[i]))

return wr

def reverse_Sbox(s_box):

"""

求S盒的逆

:param s_box:S盒參數

:return:S盒的逆

"""

re_box = [-1] * 16

for i in range(16):

re_box[s_box[i]] = i

return re_box

def reverse_Pbox(p_box):

"""

求P盒的逆

:param s_box:P盒參數

:return:P盒的逆

"""

re_box = [-1] * 16

for i in range(16):

re_box[p_box[i] - 1] = i + 1

return re_box

def do_SPN(x, s_box, p_box, Ks):

"""

4輪的SPN網絡，可以用來進行加密或解密

:param x: 16比特輸入

:param s_box: S盒參數

:param p_box: P盒參數

:param Ks: [k1,k2,k3,k4,k5]，五個16比特子秘鑰

:return: 16比特輸出

"""

wr = x

for r in range(3):

ur = wr ^ Ks[r] # 異或操作

vr = pi_s(s_box, ur) # 分組代換

wr = pi_p(p_box, vr) # 單比特置換

ur = wr ^ Ks[3]

vr = pi_s(s_box, ur)

y = vr ^ Ks[4]

return y

def encrypt(K, x):

"""

根據秘鑰K對16比特明文x進行加密

:param K:32比特秘鑰

:param x:16比特明文

:return:16比特密文

"""

Ks = gen_K_list(K)

return do_SPN(x, S_Box, P_Box, Ks)

def decrypt(K, y):

"""

根據秘鑰K對16比特密文y進行解密。

:param K:32比特秘鑰

:param y:16比特密文

:return:16比特明文

"""

Ks = gen_K_list(K)

Ks.reverse() # 秘鑰逆序編排

# 秘鑰置換

Ks[1] = pi_p(P_Box, Ks[1])

Ks[2] = pi_p(P_Box, Ks[2])

Ks[3] = pi_p(P_Box, Ks[3])

s_rbox = reverse_Sbox(S_Box) # S盒求逆

p_rbox = reverse_Pbox(P_Box) # P盒求逆

return do_SPN(y, s_rbox, p_rbox, Ks)

if __name__ == '__main__':

x = 0b0010011010110111

K = 0b00111010100101001101011000111111

print('初始明文：', format(x, '016b'))

print('加密密文：', format(encrypt(K, x), '016b'))

print('解密結果：', format(decrypt(K, encrypt(K, x)), '016b'))

assert decrypt(K, encrypt(K, x)) == x

可以直接看do_SPN函數，函數里面循環3次，對應3輪迭代，第4輪迭代沒有置換操作。encrypt與decrypt函數調用do_SPN函數即可進行加密和解密操作（為什么可以調用SPN進行解密？可以對照代碼觀察SPN的結構想一想），運行程序輸出為：

初始明文： 0010011010110111

加密密文： 1011110011010110

解密結果： 0010011010110111

至此，SPN網絡已經完全實現！那么它的安全性如何呢？

首先，我們知道，這個SPN網絡的秘鑰是32位的，大約是有4百萬的候選秘鑰，這個數量的秘鑰，手動窮搜是很難的，用計算機來窮搜就會比較容易了，不過我們隨時對它進行改造，增加秘鑰長度，如256位，這時候機器窮搜也不行了。