封面

0.前言

最开始只是想整理一下密码学课程的作业,后面越写越多,就索性写成一篇入门的介绍。在这篇文章中,我会把自己对对称加密的理解和一些作业的代码串起来,力图清晰明白地展示出来,文中所有代码都放在我的Github上,如果有错误之处还请轻拍。

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 = D_k( E_k( 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网络的思想很简单:既然加密一次不够安全,那我就加密多次,把第一次加密产生的密文再进行加密,解密的时候我连续进行两次解密就可以了,这样是不是就安全了一些呢?

对于密码体制\(S_1\),其加密与解密函数为\(E_1\)与\(D_1\),对于密码体制\(S_2\),其加密与解密函数为\(E_2\)与\(D_2\),我构造出一个新的密码体制\(S_3\),其加密函数为:$$c = E_2( E_1( p ) )$$

解密函数为$$p=D_1( D_2( c ) )$$

记为$$S_3 = S_1 * S_2$$这样破解\(S_3\)就可能会困难些。这个想法是不是很直接呢?这个思想在1949年才被提出,而提出者,可能理科生都多少听过他的名字——香农(Shannon)。

注意,不是任何的加密体制都可以这样“乘”起来变得更强,例如对于你的移位密码,嵌套起来还是移位密码(为什么?),没有任何改善,即\(S_1*S_1=S_1\),这样的密码体制被称为幂等的

如果密码体制不是幂等的,那么多次迭代就可能能够提高安全性,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。然后对于每组再根据事先所定的表进行代换,代换表长这样:

代换前 0 1 2 3 4 5 6 7 8 9 A B C D E F
代换后 E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7

就拿第一列来说,表的意思是:如果你是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盒长这样:

置换前的位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
置换后的位置 1 5 6 13 2 6 10 14 3 7 11 15 4 8 12 16

拿第二列来说,表的意思是:第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.2 SPN的多轮迭代

弄清楚一轮的流程,SPN整体就很容易明白了,就是一轮一轮的乘起来,上一轮的输出作为这一轮的输入,这是一个4轮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网络的示意图(图片来自维基百科):

SPN网络(图片来自维基百科)

注意在最后一轮去掉了代换操作,这样做可以使SPN网络稍微做一些调整就可以用来进行解密。

OK! SPN网络就是这些内容,你已经掌握了它,如果你还想和小红传纸条的话,可以试试用它加密,会比移位密码更安全一些。

什么?自己手动代换置换太麻烦?不用怕,贴心的我已经为你准备好了Python代码。

3.3 用Python实现SPN网络

我实现的是4轮迭代的SPN网络,以及加密和解密算法,其结构图如下(图片来自 Cryptography Theory and Practice ):

4层SPN网络(图片来自 *Cryptography Theory and Practice* )

每次加密输入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轮迭代没有置换操作,放在循环后面执行。encryptdecrypt函数调用do_SPN函数即可进行加密和解密操作(为什么可以调用SPN进行解密?可以对照代码观察SPN的结构想一想),运行程序输出为:

初始明文: 0010011010110111
加密密文: 1011110011010110
解密结果: 0010011010110111

至此,SPN网络已经完全实现!那么它的安全性如何呢?

首先,我们知道,这个SPN网络的秘钥是32位的,大约是有4百万的候选秘钥,这个数量的秘钥,手动穷搜是很难的,用计算机来穷搜就会比较容易了,不过我们随时对它进行改造,增加秘钥长度,如256位,这时候机器穷搜也不行了。

其次,如果SPN层数较少,对其进行线性分析或者差分分析通常会比较容易成功,这些分析方法的代码我也已经写好了,不过今天的内容已经够多了,我们下次再介绍它:)