【密码学】分组密码之DES

Author Avatar
source. 12月 29, 2018
  • 在其它设备中阅读本文章

DES, Data Encryption Standard, 数据加密标准开创了公开密码算法的先例,极大地促进了密码学的发展。

分组密码

分组密码,Block Cipher ,是将明文消息编码表示后的二进制序列,划分为固定大小的块,每块分别在密钥的控制下变换成等长的二进制序列。

分别代表明文空间、密文空间、密钥空间、加密算法、解密算法,有:

要求

  1. 分组足够长,防止明文穷举攻击。
  2. 密钥足够长,防止密钥穷举攻击。
  3. 由密钥确定的置换算法要足够复杂,足以抗击各种已知的攻击。
  4. 加密、解密算法要足够简单,易于软件和硬件的快速实现。

设计原则

混淆

英文 Confusion ,在加密算法中,明文、密文、密钥之间的关系要足够复杂,防止统计分析攻击。

扩散

英文 Diffusion ,每一比特的变化尽可能多地影响到输出密文序列的变化,以便隐蔽明文的统计特征。

迭代结构

常用 Feistel 网络,优点如下:

  1. 加解密的相似性
  2. 物理上的重复性易于在软硬件上实现

加密算法 Encryption

解密算法 Decryption

加解密过程唯一的不同:子密钥的顺序。>

特点:雪崩效应(输入明文或密钥即使只有很小的变化,也会导致输出密文产生巨大的变化)。

DES

分组长度 64 比特,密钥长度 64 比特(其中有效长度为 56 比特),8 的倍数位为奇校验位(保证每 8 位有奇数个 1)。

基本结构

如图,64 比特的密钥经过置换选择和循环移位操作可生成 16 个 48 比特的子密钥。明文 m 经过初始置换 IP 后划分为左右两部分(各32 比特),经过 16 轮 Feistel 结果(其中最后一轮不做左右交换)再做一次逆置换 IP-1得到密文 c 。

img

密钥编排算法

用于生成迭代的子密钥。具体过程为:

64位初始密钥经过置换选择1 ( PC-1 ) 后变成 56 位,经过循环左移和置换选择2 ( PC-2 ) 后分别得到 16 个 48 位子密钥 Ki 用做每一轮的迭代运算。

PC-1 去掉了校验位, PC-2 去掉了9, 18, 22, 25, 35, 38, 43, 54 位。(详见课本P80 4.2.5)

置换选择

置换选择1(PC-1)和置换选择2(PC-2):

pc1 = (57, 49, 41, 33, 25, 17,  9,
        1, 58, 50, 42, 34, 26, 18,
       10,  2, 59, 51, 43, 35, 27,
       19, 11,  3, 60, 52, 44, 36,
       63, 55, 47, 39, 31, 23, 15,
        7, 62, 54, 46, 38, 30, 22,
       14,  6, 61, 53, 45, 37, 29,
       21, 13,  5, 28, 20, 12,  4)

pc2 = (14, 17, 11, 24,  1,  5,  3, 28,
       15,  6, 21, 10, 23, 19, 12,  4, 
       26,  8, 16,  7, 27, 20, 13,  2, 
       41, 52, 31, 37, 47, 55, 30, 40, 
       51, 45, 33, 48, 44, 49, 39, 56, 
       34, 53, 46, 42, 50, 36, 29, 32)

# Permuted Choice 1 (PC-1) or Permuted Choice 2 (PC-2)
def PermutedChoice(k,num):
    if num == 1:
        t = pc1
    else:
        t = pc2
    ans = "".join(k[x-1] for x in t)
    return ans

循环左移

每次循环左移次数和循环左移函数(可以使用切片法):

d = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]
d_1 = [0,-1,-2,-2,-2,-2,-2,-2,-1,-2,-2,-2,-2,-2,-2,-1,-1]

# Loop Left Shift
def LoopLeftShift(s,num):
    l = len(s)
    num %= l
    ans = s[num:]+s[:num]
    return ans

加入取模操作的好处:若 num 为负数,则相当于可以处理循环右移,方便解密时使用。

初始置换 IP 和它的逆置换 IP-1

IP 在第一轮迭代之前进行,目的是将原明文块的位进行换位操作(查表),实际并没有密码意义,因此在软件中时常直接被去掉。

IP-1 在最后一轮迭代之后进行,在加密算法中输出为密文,在解密算法中输出明文,若 IP 被去掉,IP-1 也相应的被去掉。

img

IP 最后一列为 2, 4, 6, 8, 1, 3, 5, 7,左一列比右一列+8 。

IP-1 第二列为 8, 7, 6, 5, 4, 3, 2, 1,右边第二列比当前列+8 。

ip =  (58, 50, 42, 34, 26, 18, 10, 2,
       60, 52, 44, 36, 28, 20, 12, 4,
       62, 54, 46, 38, 30, 22, 14, 6,
       64, 56, 48, 40, 32, 24, 16, 8,
       57, 49, 41, 33, 25, 17, 9 , 1,
       59, 51, 43, 35, 27, 19, 11, 3,
       61, 53, 45, 37, 29, 21, 13, 5,
       63, 55, 47, 39, 31, 23, 15, 7)

ip_1 = (40, 8, 48, 16, 56, 24, 64, 32,
        39, 7, 47, 15, 55, 23, 63, 31,
        38, 6, 46, 14, 54, 22, 62, 30,
        37, 5, 45, 13, 53, 21, 61, 29,
        36, 4, 44, 12, 52, 20, 60, 28,
        35, 3, 43, 11, 51, 19, 59, 27,
        34, 2, 42, 10, 50, 18, 58, 26,
        33, 1, 41,  9, 49, 17, 57, 25)

# Initial Permutation, IP
# It has no cryptographic significance
def InitialPermutation(m,inv=False):
    if inv == False:
        t = ip
    else:
        t = ip_1
    ans = "".join(m[x-1] for x in t)
    return ans

F 函数

小小的 F 函数竟然如此复杂。

也称轮函数,包括四个过程:

  1. 扩展置换 ( E 盒 )
  2. 密钥加
  3. S 盒
  4. P 盒

下面,我们分别解释这几个过程。

1. 扩展置换

32 bit → 48 bit

通过扩展置换,数据的右半部分 Ri 从 32 位扩展到 48 位。扩展置换改变了位的次序,重复了某些位。

img

目的:让 1 位可能影响 2 位,从而快速实现了雪崩效应。(结合 S 盒)

e  = (32, 1,  2,  3,  4,  5,  4,  5, 
       6, 7,  8,  9,  8,  9, 10, 11, 
      12,13, 12, 13, 14, 15, 16, 17,
      16,17, 18, 19, 20, 21, 20, 21,
      22, 23, 24, 25,24, 25, 26, 27,
      28, 29,28, 29, 30, 31, 32,  1)

# Expansion
# the 32-bit half-block is expanded to 48 bits
def Expansion(m):
    ans = "".join(m[x-1] for x in e)
    return ans

2. 密钥加

48 bit ⊕ 48 bit → 48 bit

E 盒输出与子密钥 Xor (逐位异或)。

因为我的处理方法是把字符转成对应的二进制(简单粗暴),所以我写了个封装 Xor 的函数:

# Xor for two str
def Xor(a,b):
    num = len(a)
    ans = "".join(str(int(a[i])^int(b[i])) for i in range(num))
    return ans

3. 代换盒(S 盒)

48 bit → 32 bit***

功能是实现非线性代换。DES 中的唯一的非线性部分。

实际上是查表运算,8 个 S 盒对应把 48 位分成 8 个组(6 位一组)。

每个 S 盒输入 6 位,输出 4 位。

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

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

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

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


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

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

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

   [[13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7],     
     [1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2],     
     [7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8],     
     [2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11]]]
注意:输出也要写成二进制。b>

4. 置换盒(P 盒)

32 bit → 32 bit

简单置换。

p = (16,  7, 20, 21, 29, 12, 28, 17,
      1, 15, 23, 26,  5, 18, 31, 10, 
      2,  8, 24, 14, 32, 27,  3,  9,
     19, 13, 30,  6, 22, 11,  4, 25)

运行结果

加密(输出十六进制)

img

加密(输出 base64 编码)

img

解密(输入十六进制)

img

解密(输入 base64 编码)

img

安全性

img

多重 DES

img

编程中遇到的问题

若明文长度不是 64 的倍数

加密时经常遇到这种情况,最后一个分组不一定能刚好是 64 比特。

通过搜索引擎查了下,发现有好多种 Padding ,在这里,为了简化,我们统一按字符数若不是 8 的倍数则填充 0x00 补到 8 的倍数。

关键代码:

lm = len(m)
# 若不是8的倍数,则用0x00填充
lm_mod = lm%8
if lm_mod != 0:
    FillLength = 8-lm_mod
    m += FillLength*"\x00"
    lm += FillLength

没有什么不朽的,包括艺术本身。

唯一不朽的,是艺术所传递出来的对人和世界的理解。

禁止商业用途,非商业分享转载请注明来源。
本文链接:http://comydream.github.io/2018/12/29/cryptography-des/