對(duì)稱加密如何實(shí)現(xiàn)？
1.對(duì)稱密碼基礎(chǔ)
加密是為了防止要傳達(dá)的內(nèi)容被別人知道。例如，你如果想在課堂上傳小紙條給后位小紅說：i love coding，但又怕在遞紙條的過程中被老師看到，知道了你的心思，于是將每個(gè)字母變字母表中的后一個(gè)字母（如a變成b，i變成j，z變成a），得到密文：j mpwf dpejoh，這樣即老師人拿到這紙條，也不知道你說的是什么。
這就是一個(gè)加密的過程，把原本的內(nèi)容稱為明文，一般用p表示；加密后得到的內(nèi)容稱為密文，一般用c表示；而加密的這個(gè)過程可以看做是一個(gè)加密函數(shù)E，即
c=E(p)
E是指Encrypt，函數(shù)輸入是明文，輸出是加密之后的密文。上面的例子中i love coding便是明文，j mpwf dpejoh便是密文，而把字母在字母表中向后移動(dòng)一位的操作就是加密函數(shù)。
在小紅得到小紙條后，可以根據(jù)你加密的方法，將每個(gè)字母變成字母表中的前一個(gè)字母，就可以從你的密文小紙條得到你要說的內(nèi)容i love coding，心領(lǐng)神會(huì)，順便還會(huì)懷疑一下你的腦袋……無論怎樣，這個(gè)解密的過程就也可以看做是一個(gè)解密函數(shù)D，即
p=D(c)
D是指Decrypt，函數(shù)輸入是密文，輸出是解密之后的明文。
在這個(gè)過程這種，小紅能夠成功解密小紙條的前提是，你得和她在課前約定好你加密的時(shí)候移動(dòng)的是1位，2位還是幾位，不然他就會(huì)和老師一樣一臉懵逼，不知道你在說啥。你們提前約定好的這個(gè)“幾位”，就是加密和解密的密鑰k，你會(huì)根據(jù)這個(gè)秘鑰來進(jìn)行加密，小紅會(huì)根據(jù)這個(gè)秘鑰來進(jìn)行解密。
所以你的傳紙條的動(dòng)作抽象成這個(gè)過程：
明文p---->加密函數(shù)E---->密文c---->傳輸---->密文c----->解密函數(shù)D---->明文p
或者用公式來表達(dá)是：
c=Dk(Ek(c))
用大白話說就是：明文用同一個(gè)密鑰先加密再解密得到的還是同一個(gè)明文（等于沒說…）
從這里我們可以總結(jié)出加密體質(zhì)的五個(gè)要素：{明文p，密文c，密鑰k，加密函數(shù)E，解密函數(shù)D}，對(duì)稱解密的的意思就是說，加密和解密的密鑰是一樣的，上面的過程是不是正好很對(duì)稱呢?
為了方便使用，不用每次自己手動(dòng)掰手指數(shù)字符，你還寫了Python程序：
# 移位密碼
def _move_leter(letter, n):
"""
把字母變?yōu)樽帜副砗髇位的字母,z后面接a
:param letter: 小寫字母
:param n: 要移動(dòng)的字母
:return: 移動(dòng)的結(jié)果
"""
return chr((ord(letter) - ord('a') + n) % 26 + ord('a'))
def Encrypt(k, p):
"""
移位密碼加密函數(shù)E
:param k: 秘鑰k,每個(gè)字母在字母表中移動(dòng)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):
"""
移位密碼解密函數(shù)D
:param k: 秘鑰k,每個(gè)字母在字母表中移動(dòng)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
運(yùn)行這段代碼，就可以看到輸出了：
明文：ilovecoding
密文：jmpwfdpejoh
解密：ilovecoding
終于，現(xiàn)在你能和你的小紅秘密地傳達(dá)紙條內(nèi)容了，迎來全班人羨慕的目光，從此走上人生巔峰，本文到此結(jié)束。
…Hey，醒醒…
2.密碼分析
面對(duì)你倆日益頻繁的紙條往來，老師終于坐不住了，他想知道你倆寫的到底是啥，于是在某次逮到你遞紙條之后，決定下功夫破解你所使用的密碼，也就是密碼分析。
根據(jù)他的了解，以你的水平，最可能用的就是移位密碼，但具體每次移動(dòng)了幾位，無法直接觀察得出。不過他又一想，你移動(dòng)的位數(shù)頂多是25位，因?yàn)椋苿?dòng)26位的效果等于沒移動(dòng)，移27位的效果不就跟移動(dòng)1位的效果是一樣的嘛！這就是說，你的密碼只能是0-25中的某一個(gè)數(shù)字，而不可能是其他的，就這么二十幾個(gè)秘鑰，一個(gè)一個(gè)試就能知道你寫的是啥！
老師果然聰明絕頂，關(guān)鍵是也還會(huì)Python，就索性寫了一個(gè)程序，每次嘗試用不同的秘鑰來進(jìn)行解密，并觀察解密出來的內(nèi)容是否有意義：
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)
運(yùn)行程序輸出結(jié)果為：
秘鑰0：jmpwfdpejoh
秘鑰1：ilovecoding
秘鑰2：hknudbnchmf
秘鑰3：gjmtcambgle
...........
逐行觀察輸出結(jié)果，到第二行的時(shí)候就能看到原來的明文，也就知道了你要對(duì)小紅說的內(nèi)容以及你們所約定的秘鑰。面對(duì)你冒著巨大風(fēng)險(xiǎn)在課堂上所傳遞的紙條內(nèi)容，老師心里可能也是復(fù)雜的…
Anyway，你的小秘密已經(jīng)被老師知道了，此時(shí)比較灰心，一直在想，究竟是什么原因致使紙條計(jì)劃失敗？其實(shí)原因很明顯，各位也看出來了，小明所使用的加密體制中，可用的秘鑰太少，或者說秘鑰空間太小，別人直接一一列舉進(jìn)行窮搜就能破解，這就提示我們：一個(gè)好的加密體制，它的秘鑰空間應(yīng)該是足夠大的。
其實(shí)，你此次所用的移位密碼是古典的加密體制之一，據(jù)說凱撒打仗時(shí)就用這種方法與將軍們聯(lián)系，所以位移密碼也叫凱撒密碼（Caesar cipher）。類似的還有代換密碼，仿設(shè)射密碼等等，都是將單個(gè)字母替換成別的字母，來達(dá)到加密的目的。報(bào)紙上的猜謎游戲就經(jīng)常用這些方法，一般根據(jù)字母頻率進(jìn)行破解，有興趣可以進(jìn)行進(jìn)一步的了解。
所以到底要用什么樣的加密方法，才能保證我和小紅的秘密不被人偷窺呢？
2.1 密碼分析情形
俗話說，知己知彼，百戰(zhàn)不殆，了解破解者的密碼分析方法，或許能夠幫助我們想出更安全的密碼體制。可以在不同的情形下考察密碼體制的安全性，一般我們都假設(shè)破解者知道我們所使用的密碼體制，也就是說，不把密碼體制的安全性寄托在加密和解密方法的保密性上，而是放在秘鑰上。
破解者的目的就是找出所使用的秘鑰，常見的有以下幾種攻擊情形：
唯密文攻擊： 破解者擁有密文c。這就是老師破解紙條的情形。
已知明文攻擊： 破解者擁有一些明文p及其對(duì)應(yīng)的密文c。考慮到實(shí)際情形，這個(gè)假設(shè)是比較合理的，例如破解者獲得一封郵件加密后的密文，可以猜測一個(gè)詞很可能是'hi'或者'dear'，這樣就可能找到一個(gè)明文–密文對(duì)。
選擇明文攻擊： 破解者能夠指定一個(gè)明文p，獲得其對(duì)應(yīng)的密文c，較強(qiáng)的假設(shè)。
選擇密文攻擊： 破解者指定一個(gè)密文c，獲得其對(duì)應(yīng)的明文，較強(qiáng)的假設(shè)。
天啊，你不禁驚呼，在這么強(qiáng)的假設(shè)下，真的會(huì)有密碼體制能夠存活嗎？
答案是有，而且這種密碼體制已經(jīng)被廣泛應(yīng)用，甚至可以說無處不在，它就是AES（Advanced Encryption Standard）。
3.SPN網(wǎng)絡(luò)
難道不是要介紹AES嗎，怎么會(huì)變成SPN網(wǎng)絡(luò)，這是啥？可以吃嗎？
AES、DES等很多現(xiàn)代對(duì)稱加密方法的核心就是SPN網(wǎng)絡(luò)，它是代換-置換網(wǎng)絡(luò)（Substitution-Permutation Network）的縮寫，是現(xiàn)代對(duì)稱加密方法設(shè)計(jì)的藍(lán)本。可以說，了解SPN網(wǎng)絡(luò)，就基本了解了AES。
很巧的是，這個(gè)網(wǎng)絡(luò)正好是容易理解的。SPN網(wǎng)絡(luò)的思想很簡單：既然加密一次不夠安全，那我就加密多次，把第一次加密產(chǎn)生的密文再進(jìn)行加密，解密的時(shí)候我連續(xù)進(jìn)行兩次解密就可以了，這樣是不是就安全了一些呢？
對(duì)于密碼體制 S1 ，其加密與解密函數(shù)為 E1 與 D1，對(duì)于密碼體制 S2，其加密與解密函數(shù)為 E2 與 D2 ，我構(gòu)造出一個(gè)新的密碼體制 S3，其加密函數(shù)為：
c=E2（E1(p)）
解密函數(shù)為：
p=D1(D2(c))
記為 S3=S1*S2
這樣破解 S3 就可能會(huì)困難些。這個(gè)想法是不是很直接呢？這個(gè)思想在1949年才被提出，而提出者，可能理科生都多少聽過他的名字——香農(nóng)（Shannon）。
注意，不是任何的加密體制都可以這樣“乘”起來變得更強(qiáng)，例如對(duì)于你的移位密碼，嵌套起來還是移位密碼（為什么？），沒有任何改善，即 S1*S1=S1，這樣的密碼體制被稱為冪等的。
如果密碼體制不是冪等的，那么多次迭代就可能能夠提高安全性，SPN就是使用這種思想，包含多輪的迭代，每輪的操作都是相同的。下面，介紹SPN單輪的操作：
3.1 SPN單輪操作
SPN網(wǎng)絡(luò)是對(duì)一定長度的比特進(jìn)行操作的，在本文中的SPN網(wǎng)絡(luò)中，一次加密的長度為16個(gè)比特，即2字節(jié)，也就是說每次加密16比特的明文，輸出16比特的密文。
一個(gè)SPN網(wǎng)絡(luò)包含多輪迭代，每輪迭代的操作內(nèi)容都一樣是：異或運(yùn)算–>分組代換–>單比特置換
3.1.1 第一步——異或運(yùn)算
異或運(yùn)算是比較常見的二元比特運(yùn)算，用⊕表示，其規(guī)則就是“相同得0，不同得1”：
0 ⊕ 0 = 0
1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
對(duì)于比特串，直接按每一位對(duì)應(yīng)進(jìn)行計(jì)算即可以了：
0011 ⊕ 1010 = 1001
異或的有比較有意思的性質(zhì)：一個(gè)比特串亦或另一個(gè)比特串兩遍，還是等于他自己，即a ⊕ b ⊕ b = a，這是因?yàn)閍 ⊕ b ⊕ b = a ⊕ ( b ⊕ b ) =a ⊕ 0 = a，可以帶入一些例子試試看。
SPN網(wǎng)絡(luò)中，每一輪的第一步就是把輸入的比特串w和秘鑰k進(jìn)行亦或：u = w ⊕ k，如：
0001110000100011 = 0010011010110111 ⊕ 0011101010010100
這一步的目的是根據(jù)秘鑰對(duì)明文進(jìn)行混淆。如果你只知道輸出u而不知道秘鑰k，那么你就猜不出實(shí)際輸入的w是什么，它是什么都可能，而且是等概率的。例如對(duì)于1 = a ⊕ b，不告訴你b是0還是1，你就不知道a是什么。而對(duì)于和操作，如果知道1 = a and b，那么就能確定a與b都是1。
這就是第一步，是不是很簡單呢？
3.1.2 第二步——分組代換
這一步也很簡單，將第一步輸出的16比特的串分為4組，每組4比特，即0001110000100011寫成0001 1100 0010 0011。然后對(duì)于每組再根據(jù)事先所定的表進(jìn)行代換，代換表長這樣：
圖1
就拿第一列來說，表的意思是：如果你是0（0000），那么我要把你換成成E（1110），就是一個(gè)簡單的映射操作。
原比特串長這樣：0001 1100 0010 0011 <==> 1 C 2 3，再對(duì)每個(gè)字母查表得到：4 5 D 1 <==> 0100 0101 1101 0001，這樣就得到代換后的比特串0100 0101 1101 0001，完成了第二步。
這個(gè)表一般稱為S盒（Substitution），這個(gè)過程可以用v = S(u)表示，u是第一步異或的結(jié)果，也是第二步分組代換的輸入，v是第二步的輸出。需要注意，S盒的輸入和輸出一般是非線性的關(guān)系。
3.1.3 第三步——單比特置換
單比特置換是將16比特中的每一比特，根據(jù)P盒（Permutation）移動(dòng)挪位，這樣說很不直觀，直接上例子，P盒長這樣：
圖2
拿第二列來說，表的意思是：第2個(gè)比特要挪到第5個(gè)比特的位置，舉個(gè)好看的例子：
0100 0000 0000 0000 置換后為==> 0000 1000 0000 0000
這個(gè)例子里面第二個(gè)比特的1挪到了第五的位置，而其他位置的比特都是0，挪位置之后還是0。
對(duì)于第二部輸出的結(jié)果1100 1101 1100 0100，置換后的比特串為0010 1110 0000 0111，這樣就完成了第三步。
這一步可以用W = S(v)表示，v是第二部的輸出，也是第三步的輸入，W是第三步的輸出，P盒置換是一種線性的變換。
這三步放在一起結(jié)果如下，建議讀者自己計(jì)算一遍：
w = 0010 0110 1011 0111
k = 0011 1010 1001 0100
第一步，異或運(yùn)算：
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) )，這樣就完成了一輪迭代，里面用到的參數(shù)有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比特密文結(jié)果，是不是很簡單？需要注意的是，每一輪迭代的秘鑰k是不一樣的，一般是由一個(gè)基礎(chǔ)秘鑰經(jīng)特定秘鑰編排算法生成的，而使用的S盒P盒都是相同的，會(huì)提前確定好，并且是公開的。
下圖是一個(gè)三輪SPN網(wǎng)絡(luò)的示意圖（圖片來自維基百科）：圖4
注意在最后一輪去掉了代換操作，這樣做可以使加密算法稍微做一些調(diào)整就可以用來進(jìn)行解密。
OK! SPN網(wǎng)絡(luò)就是這些內(nèi)容，你已經(jīng)掌握了它，如果你還想和小紅傳紙條的話，可以試試用它加密，會(huì)比移位密碼更安全一些。
什么？自己手動(dòng)代換置換太麻煩？不用怕，貼心的我已經(jīng)為你準(zhǔn)備好了Python代碼。
3.3 用Python實(shí)現(xiàn)SPN網(wǎng)絡(luò)
我實(shí)現(xiàn)的是4輪迭代的SPN網(wǎng)絡(luò)，以及加密和解密算法，其結(jié)構(gòu)圖如下（圖片來自 Cryptography Theory and Practice ）：圖5
每次加密輸入16比特的明文，輸出16比特的密文，代碼如下：
# S盒參數(shù)
S_Box = [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7]
# P盒參數(shù)
P_Box = [1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
def gen_K_list(K):
"""
秘鑰編排算法，由一個(gè)32比特秘鑰生成5個(gè)16比特子秘鑰
:param K: 32比特秘鑰
:return: [k1,k2,k3,k4,k5]，五個(gè)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盒參數(shù)
: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盒參數(shù)
: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盒參數(shù)
: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盒參數(shù)
: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網(wǎng)絡(luò)，可以用來進(jìn)行加密或解密
:param x: 16比特輸入
:param s_box: S盒參數(shù)
:param p_box: P盒參數(shù)
:param Ks: [k1,k2,k3,k4,k5]，五個(gè)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):
"""
根據(jù)秘鑰K對(duì)16比特明文x進(jìn)行加密
: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):
"""
根據(jù)秘鑰K對(duì)16比特密文y進(jìn)行解密。
: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('解密結(jié)果：', format(decrypt(K, encrypt(K, x)), '016b'))
assert decrypt(K, encrypt(K, x)) == x
可以直接看do_SPN函數(shù)，函數(shù)里面循環(huán)3次，對(duì)應(yīng)3輪迭代，第4輪迭代沒有置換操作。encrypt與decrypt函數(shù)調(diào)用do_SPN函數(shù)即可進(jìn)行加密和解密操作（為什么可以調(diào)用SPN進(jìn)行解密？可以對(duì)照代碼觀察SPN的結(jié)構(gòu)想一想），運(yùn)行程序輸出為：
初始明文： 0010011010110111
加密密文： 1011110011010110
解密結(jié)果： 0010011010110111
至此，SPN網(wǎng)絡(luò)已經(jīng)完全實(shí)現(xiàn)！那么它的安全性如何呢？
首先，我們知道，這個(gè)SPN網(wǎng)絡(luò)的秘鑰是32位的，大約是有4百萬的候選秘鑰，這個(gè)數(shù)量的秘鑰，手動(dòng)窮搜是很難的，用計(jì)算機(jī)來窮搜就會(huì)比較容易了，不過我們隨時(shí)對(duì)它進(jìn)行改造，增加秘鑰長度，如256位，這時(shí)候機(jī)器窮搜也不行了。
