SeoulTech UCS Lab 2014-1 st 현대암호학 제 4 장대칭암호 박종혁교수 Tel: 970-6702 Email: jhpark1@seoultech.ac.kr
1절문자암호에서비트열암호로 2절일회용패드-절대해독불가능한암호 3절 DES란? 4절트리플 DES 5절 AES 선정과정 6절 Rijndael 2
제 1 절문자암호에서비트열암호로 1.1 부호화 1.2 XOR 3
1.1 부호화 암호화에컴퓨터사용이필수 암호화프로그램도평문을비트열로변경하고비트열로된암호문을출력 부호화 (encoding) 문자열을비트열로바꾸는것 4
ASCII 문자열 midnight 을다음과같은비트열로부호화 m 01101101 i 01101001 d 01100100 n 01101110 i 01101001 g 01100111 h 01101000 t 01110100 5
1.2 XOR XOR 은 익스클루시브오아 (exclusive or), 또는짧게 엑스오아 라고읽는다. 우리말로는배타적논리합 0 XOR 0 = 0 (0 과 0 의 XOR 은 0 이된다 ) 0 XOR 1 = 1 (0 과 1 의 XOR 은 1 이된다 ) 1 XOR 0 = 1 (1 과 0 의 XOR 은 1 이된다 ) 1 XOR 1 = 0 (1 과 1 의 XOR 은 0 이된다 ) 6
한비트의 XOR XOR 은 이라는기호를써서표현 a b 설명 0 0 = 0 0과 0의 XOR은 0이된다 0 1 = 1 0과 1의 XOR은 1이된다 1 0 = 1 1과 0의 XOR은 1이된다 1 1 = 0 1과 1의 XOR은 0이된다 같은숫자끼리의 XOR 은반드시 0 이된다 0 0 = 0 1 1 = 0 7
비트열 XOR 0 1 0 0 1 1 0 0 A 1 0 1 0 1 0 1 0 B ------------------------------- 1 1 1 0 0 1 1 0 A B 8
비트열 XOR 1 1 1 0 0 1 1 0 A B 1 0 1 0 1 0 1 0 B ------------------------------------------- 0 1 0 0 1 1 0 0 A B B = A (A 로돌아간다 ) 9
암호화 / 복호화의순서와매우비슷 평문 A 를키 B 로암호화하고, 암호문 A B 를얻는다. 암호문 A B 를, 키 B 로복호화해서평문 A 를얻는다. 10
XOR 은그림을마스크한다 11
제 2 절일회용패드 - 절대해독불가능한암호 2.1 일회용패드란? 2.2 일회용패드의암호화 2.3 일회용패드의복호화 2.4 일회용패드는해독할수없다 12
2.1 일회용패드란? 1 회용패드 (one-time pad) 전사공격에서키공간을모두탐색하더라도해독할수없는암호 13
2.2 일회용패드의암호화 평문과랜덤한비트열과의 XOR 만을취하는단순한암호 14
일회용패드암호화예 평문 : midnight ASCII 로부호화 문자 m i d n i g h t ASCII 코드 단어 01101101 01101001 01100100 01101110 01101001 01100111 01101000 01110100 m i d n i g h t 키 : 랜덤비트열 키 01101011 11111010 01001000 11011000 01100101 11010101 10101111 00011100 15
일회용패드암호화예 01101101 01101001 01100100 01101110 01101001 01100111 01101000 01110100 midnight 01101011 11111010 01001000 11011000 01100101 11010101 10101111 00011100 키 00000110 10010011 00101100 10110110 00001100 10110010 11000111 01101000 암호문 16
2.3 일회용패드의복호화 암호문과키의 XOR 을계산하면평문 00000110 10010011 00101100 10110110 00001100 10110010 11000111 01101000 암호문 01101011 11111010 01001000 11011000 01100101 11010101 10101111 00011100 키 01101101 01101001 01100100 01101110 01101001 01100111 01101000 01110100 midnight 17
2.4 일회용패드는해독할수없다 현실적인시간내에해독이곤란하다는의미는아니다. 키공간전체를순식간에계산할수있는무한대의계산력을갖는컴퓨터로도일회용패드는해독할수없다. 문자열이복호화되었다하더라도, 그것이바른평문인지아닌지판정할수없다. 18
전사공격 암호문을복호화해보면도중에모든 64 비트패턴이등장한다 그중에나타날수있는문자열 규칙적인문자열 aaaaaaaa, abcdefgh, zzzzzzzz 등 의미있는영어단어 midnight, onenight, mistress 등 무의미한문자열 %Ta_AjvX, HY(&JY!z, $@~*\^^), Er#f6)(% 따라서어느것이바른평문인지알수없다 즉어떤키를사용하면바르게복호화할수있는지알수없다 19
전사공격 일회용패드에서는키들을적용하여얻어진것이바른평문인지아닌지를판정하는것이불가능하다. 그러므로일회용패드를해독할수없다. 20
Question (1# Home Work) 다음경우각각에대하여 one-time pad 암호의암호문의패턴은무엇인가? a. 평문이 n 개의 0 으로구성되는경우 b. 평문이 n 개의 1 으로구성되는경우 c. 평문이 0 과 1 로교차되어구성되는경우 d. 평문이랜덤스트림비트인경우 21
제 3 절 DES 란? 3.1 DES 란? 3.2 DES 암호화 / 복호화 3.3 DES 의구조 3.4 Feistal 구조 22
3.1 DES 란? DES 는 64 비트의키를적용하여 64 비트의평문을 64 비트의암호문으로암호화시키는대칭형블록암호이다. DES 알고리즘에서는사용하는함수 대체 (substitution) 치환 (permutation) 대체와치환은 1949 년도에 Claude Shanon 이제시한혼돈 (confusion) 과확산 (diffusion) 이라는두가지개념에기반을두고있다. 23
블록암호기법의원리 스트림암호 한번에 1 비트혹은 1 바이트의디지털데이터스트림을암호화하는방식 블록암호기법 평문블록전체를가지고같은크기의암호문블록을생성 모드를이용하여스트림암호기법과동일한효과 Feistel 암호방식 ( 혼돈과확산 : Confusion & Diffusion) - Claude Shannon 소개 (SHAN49): 매우이상적인암호는암호문에대한모든통계적정보가사용된키와독립적이어야한다. - 통계적분석에기초한암호해독방지 혼돈 : 키를발견하기어렵게하기위해암호문에대한통계값과암호키값사이에관계를가능한복잡하게하는것 확산 : 평문의통계적구조가암호문의광범위한통계값에분산 키를추론하기어렵게하기위해평문과암호문사이에통계적인관계를가능한복잡하게만드는것 24
Feistel 암호구조의유도 n 비트블록처리 : n 비트평문을입력으로 n 비트암호문출력 역으로 n 비트암호문입력에대해 n 비트평문출력 ( 역의성립 : reversible, 비단수형 : nonsingular) 2n 가지의서로다른블록존재가능 n 비트 -n 비트블록치환 ( n=4 인경우 ) 4 비트입력으로 16 개값중하나선택하고, 내부치환에의하여 16 개출력값중하나대응하여 4 비트출력 25
Feistel 암호구조 처리구조 길이 2w 비트인평문블록 (L0,R0) 분할처리 K 로부터유도된 n 개의키 (Ki) 상용 n 회의동일한반복구조실행 그림 : 고전 Feistel 구조 하나의반복구조 오른쪽반 R0 에반복함수 F 적용 반복서브키 K1 적용 (K Ki) 왼쪽반 L0 와 XOR( 치환작용 ) 좌우양쪽결과를교환 ( 순열작용 ) 26
페이스텔네트워크의성질 원하는만큼라운드수를늘릴수있다 라운드함수 F 에어떤함수를사용해도복호화가가능하다 암호화와복호화를완전히동일한구조로실현할수있다. 27
DES 콘테스트 (DES Challenge) 1997 년의 DES Challenge Ⅰ 96 일 1998 년의 DES Challenge Ⅱ-1 41 일 1998 년의 DES Challenge Ⅱ-2 56 시간 1999 년의 DES Challenge Ⅲ 22 시간 15 분 28
3.1 DES 란? DES(Data Encryption Standard) 는 1977 년에미국의연방정보처리표준규격 (FIPS) 으로채택된대칭암호 전사공격으로해독할수있는수준 29
3.1 DES 란? 암호화키 56 비트를이용하여 64 비트출력으로변환 30
3.1 DES 란? 초기순열 (IP) 확장순열 (E) 역초기순열 (IP ¹) 순열함수 (P) 31
3.1 DES 란? DES 알고리즘의단일반복과정 32
3.1 DES 란? 함수 F(R, K) 의계산 33
3.1 DES 란? DES 의 S- 박스정의 34
3.1 DES 란? 키생성 DES 키의단계별계산표 순열선택 1(PC-1) 순열선택 2(PC-2) 35
블록암호 블록암호 (block cipher) 블록단위로처리를하는암호알고리즘 긴비트길이의평문을암호화하기위해서는평문을 64비트블록으로나누고각각을 DES로암호화한다 36
3.2 DES 의암호화 복호화 64 비트평문을 64 비트암호문으로암호화하는대칭암호알고리즘 키의비트길이는 56 비트 64 비트평문 ( 비트열 ) 을하나의단위로모아서암호화 37
제 4 절트리플 DES 4.1 트리플 DES 란? 4.2 트리플 DES 암호화 4.3 트리플 DES 복호화 4.4 트리플 DES 의현황 38
4.1 트리플 DES 란? 트리플 DES(triple-DES) DES는전사공격으로현실적인시간내에해독 DES를대신할블록암호가필요 이를위해개발된것이트리플 DES DES보다강력하도록 DES를 3단겹치게한암호알고리즘 39
4.2 트리플 DES 암호화 40
트리플 DES 는 DES 로도사용 41
트리플 DES 종류 DES 모든키에같은비트열을사용 DES-EDE2 키 1 과키 3 에같은키를사용하고키 2 에다른키를사용 EDE 는암호화 (Encryption) 복호화 (Decryption) 암호화 (Encryption) 순서 DES-EDE3 키 1, 키 2, 키 3 을모두다른비트열을사용 42
DES-EDE2 43
4.3 트리플 DES 복호화 암호화의역순 키 3, 키 2, 키 1 의순으로복호화 암호화 복호화를행한다 44
트리플 DES(DES-EDE3) 의복호화 45
4.4 트리플 DES 의현황 처리속도는빠르지않고 안전성면에서도풀려버린사례가있음 46
제 5 절 AES 선정과정 5.1 AES 란? 5.2 AES 선정과정 5.3 AES 최종후보및선정 47
5.1 AES 란? AES (Advanced Encryption Standard) DES 를대신한새로운표준대칭암호알고리즘 AES 의후보로서다수의대칭암호알고리즘을제안했지만, 그중에서 Rijndael 이라는대칭암호알고리즘이 2000 년에 AES 로서선정 48
5.2 AES 선정과정 NIST(National Institute of Standard and Technology) 에서공모 경쟁방식에의한표준화 (standardization by competition) 조건 제한없이무료로이용 ANSI C와 Java에의한구현 암호해독에대한강도의평가 암호알고리즘설계규격과프로그램공개 49
5.3 AES 최종후보및선정 1 차심사통과 : 15 개 CAST256, Crypton, DEAL, DFC, E2, Frog, HPC, LOKI97, Magenta, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish 2 차심사통과 : 5 개 명칭 MARS RC6 Rijndael Serpent Twofish 응모자 IBM RSA Daemen, Rijmen Anderson, Biham, Knudsen Counterpane 50
제 6 절 Rijndael 6.1 Rijndael 이란? 6.2 Rijndael 의암호화와복호화 6.3 Rijndael 의해독 6.4 어떤암호를사용하면좋은가? 51
6.1 Rijndael 이란? 벨기에연구자 Joan Daemen 과 Vincent Rijmen 이설계한블록암호알고리즘 블록길이 128 비트 키의비트길이 128 비트 192 비트 256 비트 52
6.2 Rijndael 의암호화와복호화 복수의라운드 (round) 로구성 (10~14) SPN(Substitution-Permutation Network) 구조 SubBytes ShiftRows MixColumns AddRoundKey 53
Rijndael 암호화 1 라운드 54
Rijndael 복호화 1 라운드 55
6.3 Rijndael 의해독 Rijndael 알고리즘의수학적구조 Rijndael 의수식을수학적인조작에의해풀수있다면, Rijndael 을수학적으로해독할수있을것이다 Rijndael 에대한유효한공격은현재로서는발견되지않았다. 56
6.4 어떤암호를사용하면좋은가? DES 사용하지말것 과거소프트웨어와의호환성유지를위해필요 트리플 DES 호환성때문에앞으로도당분간사용 점차 AES 로대체 AES(Rijndael) 고속 다양한플랫폼 현재까지안전 사용권장 AES 최종후보 5 개도사용가능 57
Q & A 58
Thank You! 59