박 종 혁 (jhpark1@snut.ackr) 3장. 블록 암호 및 DES 박 종 혁 (jhpark1@snut.ackr) http://www.parkjonghyuk.net
목 차 단순 DES 블록 암호 기법의 원리 DES DES의 강점 차분 및 선형 암호 해독 블록 암호의 설계 원리 블록 암호의 운용 모드 (보너스)
단순 DES 단순 DES 교육용 알고리즘으로 손으로 예제를 풀 수 있음 단순 DES는 S-DES라고 표현 8비트 평문 블록 ( 1 0 1 1 1 1 0 1 ) 10비트 키를 입력
단순 DES 키의 생성 P10 P8을 적용하는 단계 LS는 비트를 좌로 순환 이동 LS-1은 한 비트 좌로 이동 3 5 2 7 4 10 1 9 8 6 P8 6 3 7 4 8 5 10 9
단순 DES IP 초기 IP IP-1 마지막 IP-1 IP-1 ( IP ( X ) ) = X 2 6 3 1 4 8 5 7 4
단순 DES 함수 F E/P(확장/수열) S-box의 S0, S1 P4 E/P 4 1 2 3 P4 2 4 3 1
블록 암호 기법의 원리 스트림 암호 블록 암호 기법 한 번에 1비트 혹은 1바이트의 디지털 데이터 스트림을 암호화 하는 방식 평문 블록 전체를 가지고 같은 크기의 암호문 블록을 생성 모드를 이용하여 스트림 암호 기법과 동일한 효과 Feistel 암호 방식 혼돈과 확산(Confusion & Diffusion) 혼돈 : 키를 발견하기 어렵게 하기 위해 암호문에 대한 통계 값과 암호 키 값 사이에 관계를 가능한 복잡하게 하는 것 확산 : 평문의 통계적 구조가 암호문의 광범위한 통계값에 분산 키를 추론하기 어렵게 하기 위해 평문과 암호문 사이에 통계적인 관계를 가능한 한 복잡하게 만드는 것
블록 암호 기법의 원리 Feistel 암호 구조의 유도 n비트 블록처리: n비트 평문을 입력으로 n비트 암호문 출력 역으로 n 비트 암호문 입력에 대해 n비트 평문 출력(역의 성립: reversible, 비단수형: nonsingular) 2n 가지의 서로 다른 블록 존재 가능 그림 3.4 n 비트-n 비트 블록치환( n=4 인 경우) 4비트입력으로 16개 값 중 하나 선택하고 , 내부 치환에 의하여 16개 출력 값 중 하나 대응하여 4비트 출력
Feistel 암호 방식 두 개 이상의 기본 암호 연속적 수행(치환, 순열 번갈아 수행) 확산과 혼돈 Shannon Claude Shannon 소개(SHAN49) 통계적 분석에 기초한 암호 해독 방지 Shannon “매우 이상적인 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적이어야 한다.” 확산(diffusion) 평문의 통계적 구조가 암호문에 광범위하게 분산(평문과 암호문 관계 복잡) 각 평문 숫자가 다수의 암호문 숫자 값에 영향 yn = mn+i (mod 26) ; M = m1, m2, m3, … :문자 메시지 혼돈(confusion) 암호문의 통계적 구조와 암호 키 값 사이의 관계 복잡 키를 이용한 암호문 생성 방법 복잡( 키 추론 어려움)
Feistel 암호 구조 처리구조 그림 3.5 고전 Feistel 구조 하나의 반복 구조 길이 2w 비트인 평문 블록(L0, R0) 분할 처리 K로부터 유도된 n개의 키(Ki) 사용 n회의 동일한 반복 구조 실행 그림 3.5 고전 Feistel 구조 하나의 반복 구조 오른 쪽 반 R0에 반복 함수 F 적용 반복 서브키 K1 적용(K Ki) 왼쪽 반 L0와 XOR(치환 작용) 좌우 양쪽 결과를 교환(순열 작용)
Feistel 네트워크의 매개 변수와 설계 특성 블록 크기 64비트가 일반적이나 현재는 가변적 블록 크기로 128비트로 이용함 키 크기 64비트 또는 128비트의 크기를 이용함 반복 수 Feistel 암호 방식은 다중 반복 과정은 보안성을 증가, 일반화는 16회 서브키 생성 알고리즘 알고리즘이 복잡할수록 암호해독이 더욱 더 어려움 반복 함수 함수가 복잡할 수록 일반적으로 암호해독이 더욱 더 어려움 빠른 소프트웨어 암/복호화 프로그램의 실행 속도가 관심사 분석의 용이성
DES(Data Encryption Standard) 암호화키 56비트를 이용하여 64비트 출력으로 변환
DES(Data Encryption Standard) 초기순열(IP) 역 초기 순열(IP-1) 확장 순열(E) 순열함수(P) 58 50 42 34 26 18 10 3 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 61 43 35 27 19 11 63 45 37 29 21 13 5 55 47 39 31 23 15 7 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 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 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 32 27 3 9 19 13 30 6 22 11 4 25
DES(Data Encryption Standard)
DES(Data Encryption Standard) 함수 F(R,K)의 계산
DES(Data Encryption Standard) 14 4 13 1 2 15 11 8 3 10 6 12 5 9 7 S2 S3 S4 S5 S6 S7 S8 DES의 S-박스 정의
DES(Data Encryption Standard) 키 생성 DES 키 의 단계별 계산표 순열선택1(PC-1) 좌측 이동 스케줄 쇄도우효과 (Avalanche Effect) 순열선택2(PC-2) 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 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 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 반복 번호 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 회전된 비트 수 평문이나 키의 작은 변화가 암호문에 대하여 대하여 중요한 변화를 일으키는 암호알고리즘의 중요한 성질
블록 암호의 운용 모드 블록 암호의 운용 모드 전자 코드북 (ECB: Electronic Code Book)) 평문 64비트 각각의 블록은 동일키를 사용하여 개별적으로 암호 암호 블록 연결 (CBC: Cipher Block Chaining) 암호 알고리즘의 입력은 선행 암호문 64비트와 다음 평문 64비트를 연결하여 XOR하는 방식 암호 피드백 (CFB: Cipher Feedback) 입력은 한번에 J비트씩 처리, 선행 암호문은 평문과 XOR연산된 의사 난수 출력을 만드는 암호 알고리즘의 입력으로 이용 출력 피드백 (OFB: Output Feedback) 암호 알고리즘의 입력이 선행한 DES 출력이라는 것을 제외하면 CFB와 유사함 계수기 (CTR: Counter) 평문의 각 블록이 암호화된 카운터와 XOR됨
블록 암호의 운용 모드
블록 암호의 운용 모드 전자코드북: ECB
블록 암호의 운용 모드 암호 블록 연결 모드: CBC
블록 암호의 운용 모드 암호 피드백 모드: CFB
블록 암호의 운용 모드 출력 피드백 모드: OFB
블록 암호의 운용 모드 계수기 모드: Counter - 평문 블록과 같은 크기의 카운터 값을 입력으로 하여 암호화 - 암호화 결과를 평문과 XOR 실행하여 암호문 생성 - CTR모드의 장점[LIPM00] 카운터 하드웨어 효율성 암호화(또는 암호문)를 다수의 평문(또는 암호문)과 병렬로 처리 가능 소프트웨어 효율성 병렬처리 파이프라이닝, 다수의 레지스터 및 SIMD 명령처리 전처리 암호 알고리즘의 실행은 평문(또는 암호문)과 별개로 작동 임의 접근 임의의 I번쨰 블록으로 임의적 접근 처리 가능 검증 보안 다른 운영 모드들 만큼 안전하다는 검증 가능 단순성 암호화 알고리즘만 구현 필요, 복호화 키 생성 스케줄 불필요
블록 암호의 운용 모드 P1 C1 K P2 C2 PN CN (a) Encryption (b) Decryption Counter P2 C2 Counter + 1 PN CN Counter + N-1 (a) Encryption (b) Decryption
Thanks Q & A