DES

한라뽕🍊·2024년 3월 24일
DES대칭키암호블록암호암호학
0

crypto

목록 보기
1/1

  • 분류 : 대칭키, 블록, 곱, 페이스텔

  • 입력 : 평문 (Plaintext), 비밀키 : 64bit(52bit + 8bit parity)

  • 출력 : 암호문 (Ciphertext)

  • 구조
    초기 순열 (Initial Permutation, IP)
    페이스텔 구조 (Feistel) * 16라운드 <= 각 라운드에 48bit key <= key 생성 함수 <= 56비트 비밀키
    최종 순열 (Final Permutation, FP)

  • 특징

암호화

1. 구성

IP = [...]                                             # IP : 64index -> 64index, 일대일 전치, 전치할 인덱스 값 저장
FP = [...]                                             # FP(IP[in]) = in, 일대일 전치, 전치할 인덱스 값 저장

#Feistel
#EPT = [...]                                           # Expansion P-Box table
#SBOX = [[],[],[],..]                                  # S-box
#SPT = [...]                                           # Strait P-box table
#def roundf(block : 32bit, key : 48bit) -> 32bit: ...  # 라운드 함수
#def key_scheduler(key:64bit) -> 48bit array: ...      # 라운드별로 사용할 키를 생성!
def Feistel(block : 64bit, key : 64bit) -> 64bit: ...  # Feistel (후술)

plain = ...                                            # 평문 : 64bit로 나눠 떨어지도록 패딩!
key = ...                                              # key : 64bit 중 parity bit 8개 제외 56비트 사용!(후술)


v1 = [IP[c] for c in plain]                            # 초기 순열 적용

v2 = [Feistel(v1[b:b+64]) for b in range(0, size, 64)] # 각 블록별로 Feistel 적용

v3 = [FP[c] for c in v2]                               # 최종 순열 적용

cipher = v3                                            # 암호화 완료!

2. Feistel 구성

Feistel 구성이라 함은, 다음과 같이

L0:=input[:half]R0:=input[half:]Ln+1:=RnRn+1:=Ln⊕roundf(Rn,Kn)L_0 := input[:half]\\ R_0 := input[half:]\\ L_{n+1} := R_n\\ R_{n+1} := L_n \oplus roundf(R_n, K_n)

반 쪼개서 (라운드 함수를 첨가해) 좌우로 섞는 구성이다.

여느 대칭키 암호가 그렇듯, 역연산이 가능하다.

#EPT = [...]                                           # Expansion P-Box table
#SBOX = [[],[],[],..]                                  # S-box
#SPT = [...]                                           # Strait P-box table
def roundf(block : 32bit, key : 48bit) -> 32bit: ...   # 라운드 함수
def key_scheduler(key : 64bit) -> 48bit array: ...     # 라운드별로 사용할 키를 생성!

#자 설명 드갑니다~~
def Feistel(block : 64bit, key : 64bit) -> 64bit:
	
    #1. 블록을 좌측 반쪽과 우측 반쪽으로 나눈다
    left_half = block[:half]
    right_half = block[half:]
    
    #2. 라운드별로 사용할 키를 생성합니다!
    key_schedule = key_scheduler(key)
    
    #3. 16라운드 돌립니다!
    for i in range(16):
    	tmp = left_half
    	left_half = right_half
        right_half = tmp ^ roundf(right_half, key_scheduler[i])
    
    #4. 이후 좌측 반쪽과 우측 반쪽을 연접해 반환합니다
    return lefthalf + righthalf

2-1. 라운드 함수 구성

  • 입력 : 블록의 반절 : 32bit, 라운드 키 : 48bit
  • 출력 : 블록의 반절 : 32bit
  • 구조
    확장 순열 (Expansion P-Box, EPB)
    XOR 라운드 키
    치환 테이블 (S-Box)
    고정 순열 (Straight P-Box, SPB)

라운드 함수

EPB = [...]                                            # EPB : 32bit 입력을 48bit로 확장/전치할 때 사용됨.
SBOX = [[[],[]...],...]                                # S-box : 48bit -> 32bit 치환
SPB = [...]                                            # SPB : 32bit -> 32bit 전치

def roundf(block : 32bit, key : 48bit) -> 32bit:
	
    #1. 입력된 값을 48비트로 확장!
	expansioned = [block[i] for i in EPT]
    
    #2. 확장된 값과 라운드 키값을 xor연산!
   	expansioned = expansioned ^ key
    
    #3. SBOX로 48bit -> 32bit로 치환한다
    extraction = [0 for i in range(32)]                # 32bit
    for i in range(8):
    	extraction[4*i:4*i+4] = SBOX[i][..][..]        # 후술, 
    
    #4. SPB로 전치!
    result = [SPB[i] for i in extraction]
    
    return result

확장 순열 및 고정 순열

EPB = [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]
       
SPB = [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]

확장된 순열의 i번 인덱스엔 입력의 EPB[i]번 인덱스 값이 위치함.
SPB도 같은 원리이며, SPB는 확장 없이 전치만 함.

(챠카챠카 섞음)

SBOX

이짝이 약간 문제인데, 아무렴 어떤가.

SBOX = [
    # 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]
    ],
     ...
    # 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],
    ]
]

SBOX의 각 원소들은 4비트로 표현될 수 있는 값의 무작위다.

SBOX[i]에 들어있는 2차원 리스트를 보자.
4*16 행렬이다.

어떤 6bit에 대해

MSB와 LSB로 행을 정하고
나머지 네 비트로 열을 정하면

무작위 4비트 값을 뱉어낸다!
이런 방식으로 6bit -> 4bit로 바꾸는 2차원 리스트가 들어있는데,

그런 2차원 리스트가 8개가 있다.
그러니까, SBOX는 6*8bit 를 4*8bit로 변환하는데 사용된다!
SBOX : 48bit -> 32bit

2-2. 키 생성 함수 구성

  • 입력 : raw key : 64bit

  • 출력 : 48bit key가 16개담긴 array

  • 구조
    패리티 비트 제거 (Parity Bit Drop)
    순환쉬프트 (Rotate Left, ROL)
    압축 순열 (Comporession P-Box)

키 생성 함수


def key_scheduler(key : 64bit) -> 48bit array:
	
    result = []
    
    #1.key에서 parity bit를 지워 56bit로 만든다
    del_parity = [delete parity bit from key]
    
    #2.키를 반으로 쪼갠다!
    left_half = del_parity[:half]
    right_half = del_parity[half:]
    
    #3.라운드 횟수만큼 쉬프트
    for i in range(16):
    	if i in [1, 2, 6, 16]:
        	left_half <<< 2
            right_half <<< 2
    	else:
        	left_half <<< 1
            right_half <<< 1
        
        #4. 합치고 압축 순열 적용
        tmp = left_half + right_half
        
        result.append([tmp[CPB[i]] for i in range(48)])
     
    return result

패리티 비트 제거

64bit = 8byte 중 각 바이트의 패리티 비트를 제거해
64 - 8 = 56bit를 반환

쉬프트

56bit를 반으로 나눠
각자 왼쪽으로 1비트씩 순환 쉬프트를 취한다
이 때, 1, 2, 9, 16 라운드에선 2비트씩 순환한다.
L0:=key[:half]R0:=key[:half]Ln:={Ln−1<<<2ifn∈{1,2,9,16}Ln−1<<<1elseRn:={Rn−1<<<2ifn∈{1,2,9,16}Rn−1<<<1elseL_0 := key[:half]\\ R_0 := key[:half]\\ L_{n} := \begin{cases} L_{n-1}<<<2&if&n\in\{1,2,9,16\}\\ L_{n-1}<<<1&else\end{cases}\\ R_{n} := \begin{cases} R_{n-1}<<<2&if&n\in\{1,2,9,16\}\\ R_{n-1}<<<1&else\end{cases}

압축 순열

56bit 입력을 48bit로 압축시키는 과정이다.

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

압축된 순열의 i번 인덱스엔 입력의 CPB[i]번 인덱스 값이 위치하게 한다. (P-Box들은 원리가 다 같다!)

복호화

뭐... 전부 역원이 존재하는 연산이었으므로
복호화는 암호화의 역순입니,,,다,,
(언젠가 시간이 남으면 한 번 해보고 올리겠습니다!)

취약점

브루트 포스!

  • 대상 : DES
  • 목적 : key 획득 및 복호화
  • 요구사항 : 암호문 c, (평문 p)

56bit key는 오늘날에는 너무나도 짧아 브루트 포스로도 충분히 알아낼 수 있다고 합니다...
놀라운걸?

중간 일치 공격

  • 대상 : 2-DES(이중 DES)
  • 목적 : key 획득
  • 요구사항 : 평문 p, 암호문 c, 암호화 E, 복호화 D

2-DES는 DES보다 키의 길이가 배로 길다.(DES를 두 번 하기 때문이지!)
그러나 DES는 중간 일치 공격에 약점이 있다.

Ek2(Ek1(p))=cE_{k_2}(E_{k_1}(p)) = c
위는 우리의 나약한 2-DES다...

Dk2(Ek2(Ek1(p)))=Dk2(c)Ek1(p)=Dk2(c)D_{k_2}(E_{k_2}(E_{k_1}(p))) = D_{k_2}(c)\\ E_{k_1}(p) = D_{k_2}(c)
암호화와 복호화 방식을 알고있고, 평문 p와 암호문 c를 알고 있으므로
위를 성립시키는 k_1과 k_2를 찾는다!

대충 이렇게 표현하는 모양이다
sol:={(k1,k2)∣Ek1(p)=Dk2(c) for k1,k2∈K}sol := \{(k_1, k_2)|E_{k_1}(p) = D_{k_2}(c)\space for\space k_1, k_2 \isin K\}

이 짓 하고도 우연하게 일치하는 (k,k)가 둘 이상 있을 수 있다.
그럴땐 평문 p'와 암호문 c'를 하나 더 갖고와서 찾아내야한다...

profile
한라뽕🍊
낑깡이 될거야

0개의 댓글