DES

DES(Data Encryption Standard)

DES는 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 알고리즘이다.

DES는 8byte가 한 블록으로 하는 블록 암호이며, 전체 구조는 초기 순열(Initial Permutation, IP), 최종 순열(Final Permutation, FP), 페이스텔(Feistel) 구조의 16라운드, 그리고 각 라운드에 사용되는 48bit의 키를 생성하는 키 생성 구조로 구성되어 있다.

---

DES 원리

DES는 치환(Substitutation)과 순열(Permutation)을 사용하여 혼돈 성질과 확산 성질을 만족시킨다.

치환과 순열은 매우 단순한 연산이므로 한 번 적용한다고 해서 암호학적 효과를 기대할 수 없지만, 여러 번 교차해서 사용하면 혼돈과 확산 두 성질을 모두 만족시킬 수 있다. 이러한 특성을 이용하여 치환이나 순열 같은 단순한 연산들로 한 라운드를 구성하고, 각 라운드를 여러 번 반복하여 만드는 암호를 곱 암호(product cipher)라고 한다.

Feistel 구조

DES는 다음과 같은 페이스텔 구조를 따른다.

 

 

① 입력으로 들어온 블록을 동일한 길이의 왼쪽 블록 L과 오른쪽 블록 R로 나눈다.

② 각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록이 된다.

③ 왼쪽 블록은 오른쪽 블록에 라운드 함수 F를 적용한 결과와 xor되어 다음 라운드의 오른쪽 블록으로 입력된다.

 

여기서 key는 각 라운드에서 생성된 키다.

복호화하는 방법은 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 이루어진다.

 

 

 

 

---

DES과정

Step 1. 초기 순열(Initial Permutation)

DES는 시작할 때 초기 순열을 수행한다.

초기 순열은 정해진 테이블을 이용하여 64bit입력을 비트 단위로 전치한다. 테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트가 된다.

이렇게 행렬이 되어 있으면, 테이블의 2번째 값이 4일 때 출력의 2번째 비트는 입력의 4번째 비트가 된다. 즉 전치 행렬로 생각하면 된다.

# Initial Permutation Table
IPT = [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]

def plain2bitstring(plain: str):
    return "".join(format(ord(c), "0>8b") for c in plain)

def plain2bitarray(plain: str):
    bitstring = plain2bitstring(plain)
    encoded = bytearray([int(b) for b in bitstring])
    return encoded

def bitarray2plain(bitarray: bytearray):
    bitstring = bitarray2bitstring(bitarray)
    encoded = "".join([chr(int(bitstring[i*8:i*8+8], 2)) for i in range(len(bitstring)//8)])
    return encoded

def bitarray2bitstring(bitarray: bytearray):
    return "".join([str(b) for b in bitarray])

def permutation(block: bytearray, table: list[int], outlen: int):
    permutated = bytearray(outlen)
    for n in range(len(table)):
        m = table[n]-1
        permutated[n] = block[m]

    return permutated

plain = "DEScrpyt"
key = ""

bitarray = plain2bitarray(plain)
print(f"bitstring of '{plain}' : {bitarray2bitstring(bitarray)}")

# Initial Permutation
initial_permutated = permutation(IPT, bitarray, 64)
print(f"bitstring of initial_permutated: {bitarray2bitstring(initial_permutated)}")

step1의 소스코드를 보면 plain text가 DEScrpyt일 때 해당 문자열을 8bit 이진수로 나타낸다.

그리고 초기 순열을 적용하여, 비트 단위로 전치한다.

Step 2. 라운드 함수

라운드 함수 F는 오른쪽 블록만 입력되므로 길이는 32bit이다. 라운드 함수는 확장 순열(Expansion P-Box), 라운드 키 결합(XOR), 치환 테이블, 고정 순열로 이루어져 있다.

 

확장 순열(Expansion P-Box)

입력을 비트 단위로 전치하는 동시에 전체 길이를 48bit로 확장한다. 32bit를 4bit씩 8개 부분으로 나누고, 테이블을 참조하여 각각을 6bit로 확장한다.

 

라운드 키 결합(XOR)

확장 순열로 나온 출력을 라운드 키 K와 xor한다.

# Expansion P-Box Table
EPT = [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]

# Feistal
left_half = initial_permutated[:32]
right_half = inital_permutated[32:]

# Iterates 16 rounds
for round in range(16):
    # Expansion
    expansioned = permutation(right_half, EPT, 48)

    # XOR with round key
    for bit_idx in range(48):
        expansioned[bit_dix] ^= round_keys[round][bit_idx]

 

S-Box와 고정 순열

S-Box(Subsitutation-Box)는 라운드 키 결합에서 출력된 48bit 결과 값을 32bit로 축소한다.

먼저, 입력을 6bit씩 8개 부분으로 나눈다. 6bit 중 첫 번째와 마지막은 행을 결정하고, 나머지 4개는 열을 결정한다. 그 뒤, S-Box의 표에서 행과 열을 참조하여 값을 반환한다.

S-Box로 길이를 축소하고 나면, 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이루어진다.

# S-Boxs
S = [
    # 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],
    ]
]

# Straight P-Box Table
SPT = [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]

def substitutaion(block, table):
    row = (block[0] << 1) + block[5]
    column = (block[1] << 3) + (block[2] << 2) + (block[3] << 1) + block[4]

    val = table[row][column]
    binary = bin(val)[2:].zfill(4)
    return bytearray([int(b) for b in binary])

# Substitutaion
substituted = bytearray(32)
for block_idx in range(8):
    substituted[4*block_idx:4*block_idx+4] = substitution(expansioned[6*block_idx:6*block_idx+6], S[block_idx])

# Straight
straighted = permutation(substituted, SPT, 32)

키 생성 함수

키 생성 함수(key scheduling)는 64bit 입력을 받아 각 라운드에 필요한 48bit 라운드 키를 생성하는 함수이다.

이 함수는 패리티 비트 제거, 쉬프트, 압축 순열로 구성되어 있다.

 

패리티 비트 제거(Parity Bit Drop)

64bit 입력에서 패리티 비트를 제거하고, 남은 56bit에 순열을 적용한다. DES의 비밀키에서 각 byte의 가장 오른쪽 bit는 7bit에 대한 홀수 패리티 비트이다.

 

쉬프트(Shift)

56bit에서 왼쪽 26bit와 오른쪽 26bit로 나누어 각각 1bit나 2bit만큼 왼쪽으로 순환 shift 하는 과정이다.

1,2,9,16라운드에서는 1bit만 나머지 라운드에서는 2bit만큼 쉬프트 한다.

 

압축 순열(Compression P-Box)

56bit의 입력을 48bit로 압축하는 과정이다.

# Parity Bit Drop Table
PBDT = [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]
# Compression P-Box Table
CPBT = [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]

def key_scheduling(key: bytearray):
    shift_1 = [0, 1, 8, 15]
    round_keys = []
    # Drop parity bit
    parity_erased = permutation(key, PBDT, 56)
    left = parity_erased[:28]
    right = parity_erased[28:]
    # Shift
    for i in range(16):
        if i in shift_1:
            left = left[1:] + left[0:1]
            right = right[1:] + right[0:1]
        else:
            left = left[2:] + left[:2]
            right = right[2:] + right[:2]
        # Compression
        round_keys.append(permutation(left+right, CPBT, 48))
    return round_keys

Step 3. 최종 순열(Final Permutation)

마지막으로 최종순열을 적용한다. 

FPT = [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]
       
 # Final permutation
final_permutated = permutation(initial_permutated, FPT, 64)
print(f"bitstring of final_permutated: {bitarray2bitstring(final_permutated)}")
# plain == FP(IP(plain)) => FP = IP^{-1}
print(f"plaintext of final_permutated: {bitarray2plain(final_permutated)}")

그래서 최종 DES의 코드는 다음과 같다.

# Initial/Final Permutation Table
IPT = [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]
       
FPT = [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]
       
# Expansion P-Box Table
EPT = [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]
       
# S-Boxs
S = [
    # 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],
    ]
]
# Straight P-Box Table
SPT = [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]
# Parity Bit Drop Table
PBDT = [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]
# Compression P-Box Table
CPBT = [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]
        
def plain2bitstring(plain: str):
    return "".join(format(ord(c), "0>8b") for c in plain)
    
def plain2bitarray(plain: str):
    bitstring = plain2bitstring(plain)
    encoded = bytearray([int(b) for b in bitstring])
    return encoded
    
def bitarray2plain(bitarray: bytearray):
    bitstring = bitarray2bitstring(bitarray)
    encoded = "".join([chr(int(bitstring[i*8:i*8+8], 2)) for i in range(len(bitstring)//8)])
    return encoded
    
def bitarray2bitstring(bitarray: bytearray):
    return "".join([str(b) for b in bitarray])
    
def bitarray2bytes(bitarray: bytearray):
    bitstring = bitarray2bitstring(bitarray)
    
    return bytes([int(bitstring[8*i:8*i+8], 2) for i in range(len(bitstring)//8)])
    
def permutation(block: bytearray, table: list[int], outlen: int):
    permutated = bytearray(outlen)
    for n in range(len(table)):
        m = table[n]-1
        permutated[n] = block[m]
    return permutated
def substitution(block: bytearray, table: list[int]):
    row = (block[0] << 1) + block[5]
    column = (block[1] << 3) + (block[2] << 2) + (block[3] << 1) + block[4]
    val = table[row][column]
    binary = bin(val)[2:].zfill(4)
    return bytearray([int(b) for b in binary])
    
def key_scheduling(key: bytearray):
    shift_1 = [0, 1, 8, 15]
    round_keys = []
    
    # Drop parity bit
    parity_erased = permutation(key, PBDT, 56)
    left = parity_erased[:28]
    right = parity_erased[28:]
    
    # Shift
    for i in range(16):
        if i in shift_1:
            left = left[1:] + left[0:1]
            right = right[1:] + right[0:1]
        else:
            left = left[2:] + left[:2]
            right = right[2:] + right[:2]
            
        # Compression
        round_keys.append(permutation(left+right, CPBT, 48))
    return round_keys
    
plain = "DEScrypt"
key = "DreamCry"

# Key scheduling
round_keys = key_scheduling(plain2bitarray(key))
bitarray = plain2bitarray(plain)

# Initial permutation
initial_permutated = permutation(bitarray, IPT, 64)

# Feistel
left_half = initial_permutated[:32]
right_half = initial_permutated[32:]

# Iterate 16 rounds
for round in range(16):
    # Expansion
    expansioned = permutation(right_half, EPT, 48)
    # XOR with round key
    for bit_idx in range(48):
        expansioned[bit_idx] ^= round_keys[round][bit_idx]
        
    # Substitution
    substituted = bytearray(32)
    for block_idx in range(8):
        substituted[4*block_idx:4*block_idx+4] = substitution(expansioned[6*block_idx:6*block_idx+6], S[block_idx])
   
   	# Straight
    straighted = permutation(substituted, SPT, 32)
    tmp = bytearray(right_half)
    for i in range(32):
        right_half[i] = left_half[i] ^ straighted[i]
    left_half = tmp
    
# Final permutation
encrypted = permutation(right_half+left_half, FPT, 64)
encrypted = bitarray2bytes(encrypted)

그리고 이런 crypto를 사용할 수 있는 module이 pycryptodome라는 module이 있다.

from Crypto.Cipher import DES

encrypted = DES.new(key, DES.MODE_ECB).encrypt(plain)

이렇게 module을 import 해주고 key랑 plain text를 입력하면 위 코드랑 결과가 같게 나온다.