The second week of the introductory computer science course at Harvard CS50 involved DES encryption, which was implemented in Python after reading the third chapter of “In-depth Cryptography” published by Tsinghua University. This article is something I wrote before, and I think it is necessary to save it, so I write it here.

The course does not require personal implementation, and C crypt.h already contains DES encryption, only need to guess the key can complete the chapter’s problems. Out of fun I wasted some time to achieve a little personally. Also, the mystery of the S-box setup is very fascinating.

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 = [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 Box
S1 = [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]

S2 = [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]

S3 = [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]

S4 = [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]

S5 = [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]

S6 = [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]

S7 = [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]

S8 = [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]

# S Box Collection
S = [S1, S2, S3, S4, S5, S6, S7, S8]

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,
       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]

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]

plainintext = "password"
key = "password"


def char2bin(intext):
    asciicode = []
    binarycode = []
    for i in range(len(intext)):
        asciicode.append(ord(intext[i]))
        mid = bin(asciicode[i]).replace("0b", "0")
        for i in mid:
            binarycode.append(int(i))
    return binarycode


text_bin = char2bin(plainintext)
key_bin = char2bin(key)


def displace(rule, data, length):
    bridge = [0 for i in range(length)]
    for i in range(length):
        bridge[i] = data[rule[i]-1]
    return bridge


text_bin_IP = displace(IP, text_bin, 64)
key_bin_PC1 = displace(PC1, key_bin, 56)


def divide(data):
    l = int(len(data)/2)
    return data[:l], data[l:]


(key_c, key_d) = divide(key_bin_PC1)
(text_l, text_r) = divide(text_bin_IP)
text_div = [text_l, text_r]


def switch(data, way):
    mid = [0 for i in range(28)]
    for i in range(28-way):
        mid[i+way] = data[i]
    for i in range(way):
        mid[i] = data[-way+i]
    return mid


ki = [0 for i in range(16)]
combine = []
for i in range(16):
    if(i == 0 or i == 1 or i == 8 or i == 15):
        way = 1
    else:
        way = 2
    key_c = switch(key_c, way)
    key_d = switch(key_d, way)
    combine = key_c+key_d
    ki[i] = displace(PC2, combine, 48)


def xor(a, b):
    xor = [0 for i in range(len(a))]
    for i in range(len(a)):
        xor[i] = a[i] ^ b[i]
    return xor


def func_f(key, ext):
    coor = []
    sboxout = []
    kex = xor(key, ext)
    for i in range(8):
        pos = 6*i
        xis = kex[pos]*2+kex[5+pos]
        yis = kex[pos+1]*8+kex[pos+2]*4+kex[pos+3]*2+kex[pos+4]
        coor.append(xis)
        coor.append(yis)
    for i in range(8):
        integer = S[i][coor[2*i]*16+coor[i+1]]
        mid = bin(integer).replace("0b", "")
        if len(mid) < 4:
            mid = "0"*(4-len(mid))+mid
        for i in mid:
            sboxout.append(int(i))
    return displace(P, sboxout, 32)


for i in range(16):
    ext = displace(E, text_div[1], 48)
    mid = text_div[1]
    text_div[1] = xor(text_div[0], func_f(ki[i], ext))
    text_div[0] = mid

decrept = displace(_IP, text_div[0]+text_div[1], 64)
print(decrept)