最開始只是想整理一下密碼學(xué)課程的作業(yè)，后面越寫越多，就索性寫成一篇入門的介紹。我會(huì)把自己對(duì)對(duì)稱加密的理解和一些作業(yè)的代碼串起來，力圖清晰明白地展示出來，文中所有代碼都放在我的Github上，如果有錯(cuò)誤之處還請(qǐng)輕拍。

文章地址：https://gooong.cn/post/crypto...

代碼地址：https://github.com/Gooong/Cry...

加密是為了防止要傳達(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 = D_k( E_k( 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，醒醒...

面對(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)一步的了解。

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

俗話說，知己知彼，百戰(zhàn)不殆，了解破解者的密碼分析方法，或許能夠幫助我們想出更安全的密碼體制?？梢栽诓煌那樾蜗驴疾烀艽a體制的安全性，一般我們都假設(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）。

難道不是要介紹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)本?？梢哉f，了解SPN網(wǎng)絡(luò)，就基本了解了AES。

很巧的是，這個(gè)網(wǎng)絡(luò)正好是容易理解的。SPN網(wǎng)絡(luò)的思想很簡單：既然加密一次不夠安全，那我就加密多次，把第一次加密產(chǎn)生的密文再進(jìn)行加密，解密的時(shí)候我連續(xù)進(jìn)行兩次解密就可以了，這樣是不是就安全了一些呢？

對(duì)于密碼體制(S_1)，其加密與解密函數(shù)為(E_1)與(D_1)，對(duì)于密碼體制(S_2)，其加密與解密函數(shù)為(E_2)與(D_2)，我構(gòu)造出一個(gè)新的密碼體制(S_3)，其加密函數(shù)為：$$c = E_2( E_1( p ) )$$

解密函數(shù)為$$p=D_1( D_2( c ) )$$

記為$$S_3 = S_1 * S_2$$這樣破解(S_3)就可能會(huì)困難些。這個(gè)想法是不是很直接呢？這個(gè)思想在1949年才被提出，而提出者，可能理科生都多少聽過他的名字——香農(nóng)（Shannon）。

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

如果密碼體制不是冪等的，那么多次迭代就可能能夠提高安全性，SPN就是使用這種思想，包含多輪的迭代，每輪的操作都是相同的。下面，介紹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)算-->分組代換-->單比特置換

異或運(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>a ⊕ 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。

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

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

就拿第一列來說，表的意思是：如果你是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)系。

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

拿第二列來說，表的意思是：第二個(gè)比特要挪到第五個(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盒，如圖（圖片來自維基百科）：

弄清楚一輪的流程，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ò)的示意圖（圖片來自維基百科）：

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

OK! SPN網(wǎng)絡(luò)就是這些內(nèi)容，你已經(jīng)掌握了它，如果你還想和小紅傳紙條的話，可以試試用它加密，會(huì)比移位密碼更安全一些。

什么？自己手動(dòng)代換置換太麻煩？不用怕，貼心的我已經(jīng)為你準(zhǔn)備好了Python代碼。

我實(shí)現(xiàn)的是4輪迭代的SPN網(wǎng)絡(luò)，以及加密和解密算法，其結(jié)構(gòu)圖如下（圖片來自 Cryptography Theory and Practice ）：

每次加密輸入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):
    """
    5輪的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ī)器窮搜也不行了。

其次，如果SPN層數(shù)較少，對(duì)其進(jìn)行線性分析或者差分分析通常會(huì)比較容易成功，這些分析方法的代碼我也已經(jīng)寫好了，不過今天的內(nèi)容已經(jīng)夠多了，我們下次再介紹它:)