DES从入门到放弃

• 基本操作

  

• IP置换表

  

• 扩展运算

  

  方框内为32bit原始数据，扩展后为48bit

• S盒置换

  

  

  

  输入6bit，第一位和第六位组成一个二进制数对应S盒中的行号，二到五位组成一个二进制数对应S盒中的列号，交叉点的数据是是该盒的输出

  S盒行列从0开始记数，对于上图S1盒，输入0b101011，输出0b1001

  • S盒设计准则

    1. 每个S盒均为6位输入，4位输出。
    2. 没有一个S盒的输出位是接近输入位的线性函数。
    3. 如果将输入位的最左、最右端的位固定，变化中间的4位，每个可能的4位输出只得到一次.4）如果S盒的两个输入仅有1位的差异，则其输出必须至少有2位不同.5）如果S盒的两个输入仅有中间2位不同，则其输出必须至少有2位不同。
    4. 如果S盒的两个输入前2位不同，后两位已知，则其输出必不同。
    5. 对于输入之间的任何非零的6位差分，32对中至多有8对显示出的差分导致了相同的输出差分。

• P盒置换

  

  把输入的每位映射到输出位

  输入0001 0000 1010 0001 0000 0000 0000 0001

  输出1000 0000 0000 0000 0000 1000 1000 0110

  • P盒设计准则

    1. 在第i轮S盒的4位输出中，2位将影响S盒第i+1轮的中间位，其余2位将影响最后位。
    2. 每个S盒的4位输出影响6个不同的S盒，但没有一个影响同一个S盒。
    3. 如果一个S盒的4位输出影响另一个S盒的中间1位，那么后一个的输出位不会影响前一个S盒的中间1位。

• 子密钥生成

  

  

• DES的python实现

  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_re = ( 
  	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 )
    
  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 )
  		)
  	)
    
  expand = ( 
  	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 )
    
  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 )
    
  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, 33, 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 )
    
  shift = (1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1)
    
  def str2bin(str):
  	res = ''
  	for i in str:
  		t = bin(ord(i))[2:].zfill(8)
  		res += t
  	return res
    
  def bin2str(bstr):
  	res = ''
  	for i in range(0, len(bstr), 8):
  		t = chr(int(bstr[i:i+8], 2))
  		res += t
  	return res
    
  def change(bstr, array):
  	res = ''
  	for i in array:
  		res += bstr[i-1]
  	return res
    
  def ip_change(bstr):
  	return change(bstr, ip)
    
  def ipre_change(bstr):
  	return change(bstr, ip_re)
    
  def p_change(bstr):
  	return change(bstr, p)
    
  def expand_change(bstr):
  	return change(bstr, expand)
    
  def pc1_change(bstr):
  	return change(bstr, pc1)
    
  def pc2_change(bstr):
  	return change(bstr, pc2)
    
  def xor(bstr1, bstr2):
  	res = bin(int(bstr1,2) ^ int(bstr2,2))[2:].zfill(len(bstr1))
  	return res
    
  def left_shift(bstr, round):
  	t = bstr[shift[round]:len(bstr)]
  	res = t + bstr[:shift[round]]
  	return res
    
  def s_change(bstr):
  	res = ''
  	index = 0
  	for i in range(0, len(bstr), 6):
  		t = bstr[i:i+6]
  		row = t[0] + t[-1]
  		row = int(row, 2)
  		col = t[1:5]
  		col = int(col, 2)
  		num = s[index][row][col]
  		num = bin(num)[2:].zfill(4)
  		res += num
  		index += 1
  	return res
    
  def f_func(bstr, bkey):
  	e_res = expand_change(bstr)
  	xor_res = xor(e_res, bkey)
  	s_res = s_change(xor_res)
  	res = p_change(s_res)
  	return res
    
  def gen_key(bkey):
  	res = []
  	changed_key = pc1_change(bkey)
  	key_c = changed_key[:28]
  	key_d = changed_key[28:]
  	for i in range(len(shift)):
  		key_c = left_shift(key_c, shift[i])
  		key_d = left_shift(key_d, shift[i])
  		key_res = pc2_change(key_c+key_d)
  		res.append(key_res)
  	return res
    
  def des_enc(bplain, bkey):
  	ip_res = ip_change(bplain)
  	ldata = ip_res[:32]
  	rdata = ip_res[32:]
  	key_list = gen_key(bkey)
  	for i in range(16):
  		t = rdata
  		f_res = f_func(t, key_list[i])
  		rdata = xor(f_res, ldata)
  		ldata = t
  	bcipher = ipre_change(rdata+ldata)
  	return bcipher
    
  def des_dec(bcipher, bkey):
  	ip_res = ip_change(bcipher)
  	ldata = ip_res[:32]
  	rdata = ip_res[32:]
  	key_list = gen_key(bkey)
  	for i in range(16):
  		t = rdata
  		f_res = f_func(t, key_list[15-i])
  		rdata = xor(f_res, ldata)
  		ldata = t
  	bplain = ipre_change(rdata+ldata)
  	return bplain
    
    
  def divide_enc(plaintext, key):
  	bplain = str2bin(plaintext)
  	bkey = str2bin(key)
  	bcipher = ''
  	for i in range(0, len(bplain), 64):
  		bcipher += des_enc(bplain[i:i+64], bkey)
  	return bcipher
    
  def divide_dec(ciphertext, key):
  	bcipher = str2bin(ciphertext)
  	bkey = str2bin(key)
  	bplain = ''
  	for i in range(0, len(bcipher), 64):
  		bplain += des_dec(bcipher[i:i+64], bkey)
  	return bplain
    
  def encrypt(plaintext, key):
  	ciphertext = bin2str(divide_enc(plaintext, key)).encode('hex')
  	return ciphertext
    
  def decrypt(ciphertext, key):
  	plaintext = divide_dec(ciphertext.decode('hex'), key)
  	return bin2str(plaintext)
    
  if __name__ == '__main__':
  	a = encrypt('aaaaaaaa', '00000000')
  	print(a)
  	b = decrypt(a,'00000000')
  	print(b)
    
  

• 3DES

  使用三个密钥，执行三次DES算法

  加密过程：加密-解密-加密

  $C=Ek_3(Dk_2(Ek_1(P))) $

  解密过程：解密-加密-解密

  $P=Dk_1(EK_2(Dk_3(C))) $

• DES弱密钥

  • 产生原因

    DES加密与解密在算法上对称，区别只是密钥的使用顺序。将密文c输入，逆序使用子密钥就可以恢复明文

    若密钥生成的子密钥$k_1=k_{16},k_{15}=k_2,…k_9=k_8$，对一个明文加密两次，得到的还是明文，这样的密钥称为弱密钥

    64位的密钥K经PC-1之后，变为56位，分为高28位和低28位，分别进行移位。

    若高28位和低28位为全0或全1，则经过移位后不变，16个子密钥都相同。

    移位是独立进行的，组合可以得到

    K1＝…＝K16＝0x000000000000
    K1＝…＝K16＝0xFFFFFFFFFFFF
    K1＝…＝K16＝0x000000FFFFFF
    K1＝…＝K16＝0xFFFFFF000000
    

    所以至少有四个弱密钥

    若两个密钥生成的子密钥恰好对称，由一个密钥加密的信息可以通过用另一个密钥再次加密来解密，这两个密钥称为一组半弱密钥

  • 弱密钥

    $E_k(E_{k}(x))=x$

    0x0101010101010101
    0xFEFEFEFEFEFEFEFE
    0xE0E0E0E0F1F1F1F1
    0x1F1F1F1F0E0E0E0E
    若不考虑校验位以下四组也为弱密钥
    0x0000000000000000
    0xFFFFFFFFFFFFFFFF
    0xE1E1E1E1F0F0F0F0
    0x1E1E1E1E0F0F0F0F
    

  • 半弱密钥

    $E_{k_1}(E_{k_2}(x))=x$

    0x011F011F010E010E 和 0x1F011F010E010E01
    0x01E001E001F101F1 和 0xE001E001F101F101
    0x01FE01FE01FE01FE 和 0xFE01FE01FE01FE01
    0x1FE01FE00EF10EF1 和 0xE01FE01FF10EF10E
    0x1FFE1FFE0EFE0EFE 和 0xFE1FFE1FFE0EFE0E
    0xE0FEE0FEF1FEF1FE 和 0xFEE0FEE0FEF1FEF1