Download presentation
Presentation is loading. Please wait.
1
1 Chap 3. 관용 암호 방식 현대적 기법
2
2 http://math88.com.ne.kr/crypto/DES/2des.html
3
3 목차 3.1 단순 DES 3.2 블록 암호 기법의 원리 3.3 DES DES DES 의 공격 방법 DES 작동 모드
4
4 과제물 단순 DES 의 암호화 / 복호화 입력 평문 : 본인의 영문 이름 키 : 본인의 학번 끝에서 3 자리 사용 ( 예 : 10 0110 0001) 제출방법 : A4 에 손으로 암호화 과정 및 복호화 과정
5
5 3.1 단순 DES DES (Data Encryption Standard) IBM 에서 Lucifer System 을 개선하여 만듬 1977 년 미 상무성의 국립 표준국 (NBS) 에서 표준 암호 알고리즘으로 채택 64 비트 블럭 암호 알고리즘 56 비트 키를 사용 –64 비트 중 8 비트는 parity check 로 사용 기본 구조 round 수 : 16 round 복호화는 암호화의 역순 단순 DES 교육용 알고리즘 Santa Clara 대학의 Edward Schaefer 개발 8 비트 평문 블럭 과 10 비트 키를 사용
6
6
7
7 기본 함수 IP (Initial Permutation) : 초기순열 함수 f K 전치 (transposition) 치환 (substitution) SW : 데이터의 두 절반을 상호 교환하는 함수 함수 f K IP -1 (Inverse Initial Permutation) : 초기 순열의 역인 순열 함수 암호화 / 복호화 Ciphertext = IP -1 (f K2 (SW(f K1 (IP(Plaintext))))) Plaintext = IP -1 (f K1 (SW(f K2 (IP(Ciphertext)))))
8
8
9
9 키생성 S-DES 는 10-bit Key 를 사용 두개의 8-bit sub key 생성 P10( k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) =( k3, k5, k2, k7, k4, k10, k1, k9, k8, k6) P10 입력 : 1 2 3 4 5 6 7 8 9 10 출력 : 3 5 2 7 4 10 1 9 8 6 ex : Key(1010000010) --> (1000001100)
10
10 LS-1 : 1 비트 Circular Left Shift 연산 ex : (10001) --> (00011) ex : (10001) --> (00011) P8 입력 : 10 비트 출력 : 8 비트 P8( k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) =( k6, k3, k7, k4, k8, k5, k10, k9) P8 6 3 7 4 8 5 10 9 6 3 7 4 8 5 10 9
11
11 1 0 0 1 0 0 1 1 1 0 3 5 2 7 4 10 1 9 8 6 0 0 0 1 1 0 1 1 1 0 1 2 3 4 5 6 7 8 9 10 0 0 1 1 0 1 1 1 0 0 6 3 7 4 8 5 10 9 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 2 3 4 5 6 7 8 9 10 6 3 7 4 8 5 10 9 1 0 0 0 0 0 1 1
12
12
13
13
14
14 암호화 과정 입력 : 8 비트 출력 : 8 비트 IP( 초기 순열 ) 과 IP -1 ( 역 초기 순열 ) M = (IP -1 (IP(M)) IP 입력 : 1 2 3 4 5 6 7 8 출력 : 2 6 3 1 4 8 5 7 IP -1 출력 : 4 1 3 5 7 2 8 6
15
15 함수 f K 전치 (transposition) 치환 (substitution) 입력 8 비트 L (Left most 4 bits) R (Right most 4 bits) 처리 f K = ( L XOR F( R, SK ), R ) SK (Sub Key = K1 or K2) 함수 F() 사용
16
16
17
17 E/P (Expansion/Permutation) 입력 : 4 비트 출력 : 8 비트 P4 E/P 4 1 2 3 2 3 4 1 4 1 2 3 2 3 4 1 P4 2 4 3 1 2 4 3 1
18
18 S-Box 입력 : 4 비트 ( 1 0 1 0 ) 처리 행 : 1 번째와 4 번째 비트 ( 1 0 ) 열 : 2 번째와 3 번째 비트 ( 0 1 ) 0123 01032 13210 20213 33132 S0S1012300123 12013 23010 32103
19
19
20
20 S-DES 분석 Brute force 공격 가능 10 비트 키로 단지 2^10 = 1024 가지의 가능성 암호해독 가능 기지 평문 공격 : 단일평문과 그 출력 암호문이 알려져 있 을때 10 개의 미지수 ( 키 ) 를 갖는 8 개의 비 선형 방정식 (p, c) 으로 나타낼 수 있음 => 공격 가능
21
21 10 개의 미지수 ( 키 ) 를 갖는 8 개의 비 선형 방정식 (p, c) 으로 나타낼 수 있음 (p 0,0, p 0,1, p 0,2, p 0,3 )=(a,b,c,d) (p 1,0, p 1,1, p 1,2, p 1,3 )=(w,x,y,z) 4 비트 출력 = (q,r,s,t) q=abcd+ab+ac+b+d r=abcd+abd+ab+ac+ad+c+1 0123 01032 13210 20213 33132 S0
22
22 2 6 3 1 4 8 5 7 4 1 3 5 7 2 8 6 3 5 2 7 4 10 1 9 8 6 6 3 7 4 8 5 10 9 4 1 2 3 2 3 4 1 2 4 3 1012301032 13210 20213 33132 S0 S1012300123 12013 23010 32103
23
23 3.2 블록암호 기법의 원리 스트림 암호와 블록 암호 기법 스트림 암호 기법 한번에 1 비트 혹은 1 바이트의 디지털 데이터 스트림을 암 호화 Vigenere 암호, Vernam 암호 블록 암호 기법 평문 블록 전체를 가지고 같은 크기의 암호문 블록을 생성 전형적으로 64 비트를 사용 스트림 암호보다 더 넓은 범위에 응용 가능 대부분의 네트워크 암호는 블록 암호 방식을 따름 Feistel 블록 암호 기법의 구조에 따름
24
24 Feistel 암호 구조의 유도 입력 : n 비트 출력 : n 비트 암호화가 역이 성립하기 위한 조건 Reversible Mapping PC 0011 0110 1000 1101 Irreversible Mapping PC 0011 0110 1001 1101
25
25 N=4 일때 블록 치환 작은 블록으로 인해 취약 점 존재 적당한 크기의 n 설정 방법 크면 클수록 암호화 강도 는 높아짐 작으면 작을수록 구현과 성능 면에서는 좋음 => 적당한 암호학적 강도를 갖 고 구현이 용이할 정도의 크 기선택
26
26 Feistel 암호방식 적 (product) 암호의 개념을 이용하여 단순한 치환 암호를 개략 적으로 설계할 수 있음을 제안 적암호 : 두 개 이상의 기본 암호가 연속적으로 수행되도록 하여 어떤 요소의 암호방식보다 암호해독적으로 강하도록 하는 암호 개념 치환과 순열을 번갈아 수행하는 암호 방식의 사용을 제안 혼돈 (confusion) 함수와 확산 (diffusion) 함수를 번갈아 수행 현재 사용하고 있는 모든 중요한 대칭 블록 암호의 기본구조
27
27 확산과 혼돈 통계적 분석에 기초한 암호 해독 방지법 => Claude Shannon 에 의해 소 개된 방법 매우 이상적인 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적이어야 한다. 확산 (diffusion) 평문의 통계적 구조가 암호문의 광범위한 통계 값에 분산되어 버 리는 방식 각 평문 숫자 (digit) 가 다수의 암호문 숫자 값에 영향을 주게 함으 로서 가능 예 > 문자 메시지 M = m 1 m 2 m 3 … 를 통하여 하나의 암호 문자 y n 을 생성하는 방식 y n = sum( 1 <= i <= k ) m n+i mod 26
28
28 혼돈 (confusion) 키를 발견하기 어렵게 하기 위한 방법 암호문에 대한 통계 값과 암호 키 값 사이의 관계를 가능한 복잡하게 만드는 것 복잡한 치환 알고리즘을 사용함으로 가능
29
29 Plaintext(2w bits) w bits XORF F F Ciphertext(2w bits) Round1 L0R0 L1R1 K1 Roundi LiLiRiRi KiKi Roundn LnLnRnRn KnKn Ln+1Rn+1 Feistel 암호구조
30
30 Feistel 암호 구조 왼쪽 반의 데이터에 치환 (substitution) 이 수행됨 치환 다음에는 데이터의 두 개의 반을 교환하는 순열 (permutation) 이 수행됨 S-DES 와 Feistel 의 차이점 알고리즘이 순열 함수로 시작되고 종료됨 IP IP -1
31
31 Feistel 네트워크의 매개변수 블록크기 : 64 비트의 블록 크기면 적당 키 크기 : 64 비트 또는 그 이하의 키 크기는 부적절하며 128 비 트가 일반적 반복 수 : 단일 과정은 보안에 부적절하지만 다중 반복 과정은 보안성을 증가시킴, 전형적인 반복 횟수는 16 회 서브키 생성 알고리즘 : 알고리즘이 복잡할수록 암호해독이 어려워짐 반복 함수 : 역시 함수가 복잡할수록 일반적으로 암호 해독에 더 강해짐
32
32 Plaintext(2w bits) w bits XORF LE0RE0 K1 XORF K2 RE1LE1 XORF LE14RE14 K15 XORF K16 RE15LE15 LE16RE16 LE16 Ciphertext(2w bits) Plaintext(2w bits) w bits K1 K2 K15 K16 XORF F F F LD0=RE16RD0=LE16 Ciphertext(2w bits) RD1=LE15LD1=RE15 LD2=RE14RD2=LE14 LD14=RE2RD14=LE2 RD15=LE1LD15=RE1 LD16=RE0RD16=LE0 LD16=RE0RD16=LE0
33
33 암호화 과정 LE16 = RE15 RE16 = LE15 XOR F(RE15,K16) 복호화 과정 LD1 = RD0 = LE16 = RE15 RD1 = LD0 XOR F(RD0,K16) = RE16 XOR F(RE15,K16) = LE15 XOR F(RE15,K16) XOR F(RE15,K16) XORF LE14RE14 K15 XORF K16 RE15LE15 LE16RE16 LE16 Ciphertext(2w bits) K15 K16 XORF F LD0=RE16RD0=LE16 Ciphertext(2w bits) RD1=LE15LD1=RE15 LD2=RE14RD2=LE14
34
34 암호화 i 번째 반복과정 LEi = REi-1 REi = LEi-1 XOR F(REi-1,Ki) 이에 대한 복호화 과정 REi-1 = LEi LEi-1 = REi XOR F(REi-1,Ki) = REi XOR F(LEi,Ki) -> 복호화 그림에서 (i-1) 번째 복호결과를 만들기 위한 (i) 번째 입 력 형식 증명 XORF LE14RE14 K15 XORF K16 RE15LE15 LE16RE16 LE16 Ciphertext(2w bits) K15 K16 XORF F LD0=RE16RD0=LE16 Ciphertext(2w bits) RD1=LE15LD1=RE15 LD2=RE14RD2=LE14
35
35 특징 IBM 에서 Lucifer System 을 개선하여 만듬 1977 년 미 상무성의 국립 표준국 (NBS) 에서 표준 암호 알고리 즘으로 채택 FIBS PUB46 64 비트 블럭 암호 알고리즘 56 비트 키를 사용 64 비트 중 8 비트는 parity check 로 사용 기본 구조 round 수 : 16 round 복호화는 암호화의 역순 최근에는 DES 암호화를 세 개의 키로 세 번 반복함으로써 암 호의 강도를 높인 Triple-DES 를 사용 3.3 DES (Data Encryption Standard)
36
36 DES 의 역사 전용 암호시스템 : 타 그룹간의 통신에 불리 ==> 데이터 암호 화 표준이 필요 공개암호 표준 : 미국 연방 정부가 움직임 표준화 검토 (1972), 적합한 암호 알고리즘 조사 1973 년 5 월 : 암호방식 공모 (1 차 ) 1974 년 8 월 : 2 차 공모 ==>IBM 이 요건을 갖춤 ==>NBS 가 요건을 NSP 에 의뢰
37
37 조사에 대한 요구 1. It must provide a high level of security. 2. It must be completely specified and easy to understand. 3. The security provided by the algorithm must not be based on the secrecy of the algorithm. 4. It must be all users and suppliers.
38
38 조사에 대한 요구 ( 계속 ) 5. It must be adaptable for use in diverse applications. 6. It must be economical to implement in electronic devices and be efficient to use. 7. It must be amenable to validation. 8. It must be exportable.
39
39 DES 의 역사 ( 계속 ) 1975 년 ~1977: 일반 comment, 계약 체결 1977:NBS(NIST) 가 DES 를 표준 암호 알고리즘으로 채택 U.S.banks have been adopted DES NBS postponed guarantee term of DES from till 1988 to till 1993 NSA proposed CCEP(Commercial COMSEC Endorsement Program; 상용 통신 안전 보증 계획 )instead of DES U.S. bank expect to continue the use of DES
40
40 3.3.1 DES 암호화 DES 의 알고리즘의 일반적 모형 일반적 모형 평문 : 64bit 키 : 56bit + 8bit( 패리티 ) 처리 단계 초기순열 단계 (IP) 16 라운드 반복 좌우 교환단계 역초기순열 단계 (IP -1 )
41
41 3.3.1 DES DES 의 기본 구조 ( 데이타 암호화부 ) 입 력입 력입 력입 력 K1 K2 :::: 초기 치환 L0L0L0L0 L1L1L1L1 L2L2L2L2 R0R0R0R0 R1R1R1R1 R2R2R2R2 :::: f f R 16 L 16 f 역초기 치환 출 력출 력출 력출 력 K16 L i = R i-1 R i = L i-1 XOR f (R i-1, K i )
42
42 초기 치환 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
43
43 DES 의 기본 구조 ( 단일 반복 과정 )
44
44 f 함수의 구성도 8 개의 S-box 로 구성 각 S-box 는 6 비트 입력, 4 비트 출력 생성 R(32bit) 확장순열 E 48bit K (48bit) S1S2S8S7.. 치환 P 32 bit S-box table
45
45 확장순열 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
46
46 S-box Table 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 예 ) 1 0 1 1 0 1 ------ 6 비트 입력 행 (3 행 ) 열 (6 열 ) 0 0 0 1 10 진수 ‘1’ 를 4 비트로 출력 : 0 0 0 1
47
47 DES 의 기본 구조 ( 키 생성부 ) 키 순열선택 1 c0c0c0c0 좌측 시프트 c1c1c1c1 c2c2c2c2 c 15 좌측 시프트 d0d0d0d0 d1d1d1d1 d2d2d2d2 d 15 좌측 시프트 순열선택 2 K1 K2 K16 :::: :::: ::::
48
48 순열선택 1(PC1) 64 비트 -> 56 비트 C0, D0 : 각 28 비트 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 순열선택 2(PC2) 56 비트 ->48 비트 48 비트 키 출력 생성 14 17 11 24 1 5 3 28 15 6 21 10 23 19 2 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 38 44 49 39 56 34 53 46 42 50 36 29 32
49
49 쉬프트 스케줄 라운드 수 좌측 쉬프트 수 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1
50
50 3.3.2 DES 복호화 서브키를 역순으 로 사용 암호화와 같은 알 고리즘 사용 Feistel 구조
51
51 3.3.3 쇄도효과 (Avalanche Effect) 평문이나 키의 작은 변화가 암호문에 대하여 중요한 변 화 발생 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010 011010000 10000101 00101111 01111010 00010011 01110110 11101011 10100100 1110010 1111011 1101111 0011000 0011101 0000100 0110001 1101110 0110010 1111011 1101111 0011000 0011101 0000100 0110001 1101110 (a) (b) 1
52
52 DES 는 강한 쇄도 효과 (Avalanche Effet) 를 갖는다. DES 에 관한 우려사항 미 정부의 채택이후 DES 의 보안 수준에 대한 우려가 지속. 알고리즘의 성질을 이용한 암호 해독의 가능성 – 예 ) s - box 의 약점에 대한 공격 가능성 주장 제기됨 그러나, 약점을 발견한 사람은 현재 존재 하지 않음 키 길이에 관한 우려 –Key Serarch Machine ( 기지 평문 공격 ) Cost Expected search Time $ 100,000 35hours $1,000,000 3.5hours $10,000,000 21minutes
53
53 –Brute force Attack ; 1970 년대 /80 년대 --- low computing power 90 년대 --- high computing power – 미국 수출 허용 기준인 40 비트의 키 : Michael Wienerd 의 key search machine 으로 0.2 초만에 해독 가 능 Key size Number of One Encryption 10 6 Encryption Key size Number of One Encryption 10 6 Encryption Alternative Keys per micro sec per micro sec 32bits 2 23 = 4.3 * 10 9 35.8 minutes 2.15ms 32bits 2 23 = 4.3 * 10 9 35.8 minutes 2.15ms 56bits 2 56 = 7.2 * 10 16 1142years 10.01h 56bits 2 56 = 7.2 * 10 16 1142years 10.01h 128bits 2 128 = 3.4 * 10 38 10 24 years 5.4 * 10 18 years 128bits 2 128 = 3.4 * 10 38 10 24 years 5.4 * 10 18 years
54
54 3.3.4 DES 의 공격 방법 공격 방법 차분 암호 해독 (Differential Cryptanalysis) DES 에 적용해서 널리 알려짐 2 55 미만의 복잡도로 DES 를 해독 2 47 의 선택평문을 가지고 2 47 차수로 DES 를 해독 선형 암호 해독 (Linear Cryptanalysis) 2 47 기지 평문으로 해독가능 기지 평문이 선택 평문보다 구하기 쉽지만 DES 공격으로 서의 선형 암호 해독은 가능성이 없다. 선형 암호 해독의 타당성의 주장이 약하다.
55
55 3.3.5 DES 작동 모드 3.3.5 DES 작동 모드
56
56 ECB (Electronic Codebook) 모드의 특징 평문은 64 비트씩 처리 마지막 비트가 64 비트 미만이면 나머지 비트를 채운 후 진행 동일한 블록이 입력되면 암호문도 같다. --> 해독될 위험성이 있다. 중요 데이타가 같은 위치에 있을 때 취약블럭이 상호 결합하 지 않음 => 연속적인 블럭 암호화법 ; Chaining 기법
57
57 ECB (Electronic Codebook) 모드 암호화 DES 암호화 P1P1 C1C1 K DES 암호화 P2P2 C2C2 K DES 암호화 PNPN CNCN K... DES 복호화 C1C1 P1P1 K 4 복호화 DES 복호화 CNCN PNPN K DES 복호화 C2C2 P2P2 K...
58
58 CBC (Cipher Block Chaining) 모드의 특징 하나의 암호화 스텝의 출력을 사용하여 다음 입력으로 수정 각각의 암호 블럭은 서로 영향을 받음 선행하는 평문 블럭 전체에 좌우됨 C n : 모든 평문 블럭 P 1, P 2,..., P n 의 함수 암호화 : C n =E k (P n +C n-1 ) 복호화 : Q n =D k (C n ) + C n-1 =P n Padding Self-Recovering 기능 첫번째 암호화에 적용할 IV 값은 송수신자가 미리 알아야 함 전송상의 암호문의 결함은 복호화 과정에서 오류 발생
59
59 CBC (Cipher Block Chaining) 모드 암호화 4 복호화 DES 복호화 C1C1 P1P1 K DES 암호화 P2P2 C2C2 K DES 암호화 PNPN CNCN K ... C N-1 DES 암호화 P1P1 C1C1 K DES 복호화 C2C2 P2P2 K DES 복호화 CNCN PNPN K C N-1...
60
60 CFB (Cipher Feedback) 모드의 특징 문자의 길이 : m(1<m<64) 암호화 하기 위한 m 비트 : DES 출력의 m 비트 DES 알고리즘이 회선 양단에서 암호화로서 사용 Shift Register : 매번 새로운 비트로 교체 암호문은 선행하는 평문 모두의 함수 DES 를 스트림 암호 방식으로 사용
61
61 CFB (Cipher Feedback) 모드 암호화 64 비트 레지스터 DES 암호화 선택 j 비트 K P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K PNPNPNPN CNCNCNCN... C N-1 4 복호화 64 비트 레지스터 DES 암호화 선택 j 비트 K P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K PNPNPNPN CNCNCNCN... C N-1
62
62 OFB (Output Feedback) 모드의 특징 CBC, CFB 의 Error Extention 에 대한 응용 Vernam type 키 스트림 : 주기성이 있음 Feedback 의 출발 위치를 제외하고는 CFB 와 유사
63
63 OFB (Output Feedback) 모드 64 비트 레지스터 DES 암호화 선택 j 비트 K P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K PNPNPNPN CNCNCNCN... O N-1 64 비트 레지스터 DES 암호화 선택 j 비트 K P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K PNPNPNPN CNCNCNCN... O N-1 4 복호화 4 암호화
64
64 http://math88.com.ne.kr/crypto/DES/2des.html
Similar presentations
