정보보호 05 암호개론 (2)
현대암호 (1) 근대암호 기계식암호 SP(Substitution & Permutation) 현대암호 1950 년대이후컴퓨터를이용한암호방법개발 수학적접근방식에의해보다복잡하고해독하기어렵게만들어짐 구분 대칭키알고리즘 블록 (Block) 암호화 스트림 (Stream) 암호화 비대칭키알고리즘으로구분
현대암호 ( 계속 ) 현대암호 (2) 대부분의데이터암호화에는속도가빠른대칭키알고리즘이용 비대칭키알고리즘의경우사용자인증, 키생성등에이용
대칭키암호 (1) 암호화와복호화에하나의키를이용 공통키또는대칭키암호방식이라고지칭 이때의키를비밀키 (secret key) 라고지칭
대칭키암호 (2) 암호화복호화를수행하는두사용자가동일한키를가지고있어야함 Pre-shared key 온라인상에서구두또는메일, 전화로교환 : 수동키 블록암호와스트림암호로분류 대표적알고리즘 : DES, 3DES, SEED, RC2, RC5, AES(Rijndael)
대칭키암호 (3) 블록암호 특정블록크기로암호화 / 복호화를수행하여스트림암호에비해속도가빠름 블록간의연관성때문에오류발생시전체데이터에영향을미침 스트림암호 1970 년대초유럽에서연구 비밀키를상호공유하고, 사용한비밀키는재사용되지않는특징 비트열에오류가발생해도오류확산이없다는장점 1 비트씩연산을하므로수행속도가느리다는것과비밀키를안전하게전송해야하는단점
Data Encryption Standard IBM 에서기존의 LUCIFER 를변형하여개발 1977 년 NIST 에의해표준 (FIPS PUB-46) 으로채택 최초 128 비트의키로 64 비트블록상에서실현 하나의칩으로구현하기위해 56 비트키로줄임 1994 년 2 차로 5 년간사용연장 DES (1)
Feistel 구조 2t 비트의평문블록을각각 t 비트로나누고, L i-1 과 R i-1 자리를교환하는과정을라운드 (i >= 1) 라고하고, 암호문 (L i, R i ) 으로변환되는반복구조 평문블록이암호화과정중에라운드수만큼반복수행 이구조는비교적암호화복호화속도가빠르고, H/W, S/W 구현이용이하며, 아직까지는구조상의문제를발견하지못함 DES (2)
DES (3) 초기치환과정 64 비트스트링으로된평문 X 가 IP(Initial Permutation) 에의해초기치환과정을거침
DES (4) 역치환과정 16 번의치환과정을거친후 IP -1 을적용하여암호문을얻음
DES (5) 암호화과정 치환과정 F함수과정 S-Box P-Box 키생성과정
DES 의안전성 키가 56 비트이므로 2 56 개키존재 1977 년 Diffe-Hellman 에의해 1,000,000 대의병렬컴퓨터로, 1usec 에 1 번 encryption 이가능하다면 10 시간이내찾을수있다고제안 Wiener 에의해 Known Plain-text Attack 으로정확히분석 1997 년 DES 키를찾는프로젝트에서 96 일만에키를찾아냄 3DES 로키길이와라운드수를 3 배로증가시킴
3DES Triple DES DES 의암호화 / 복호화수행과정을 3 회반복 158 비트의암호화키사용
국내대표적인암호화알고리즘 DES 와같은 Feistel 구조 128 비트키 128 비트고정길이입출력 Known Attack 에강한라운드기능 4 개의 8x8 S-Box XOR 과 Modular 의혼합된연산 16 라운드수행 SEED
AES 1998 년사용기한이만료된 DES 를대체할알고리즘으로공모 벨기에에서개발한 Rijndael 이선정되어 2000 년 10 월표준으로선정 특징 가변블록길이 (128, 192, 256) 지원 키도 128, 192, 256 비트사용 키길이에의해라운드결정 Feistel 구조가아닌레이어 (layer) 로구성 선형혼합 (Linear mixing) : 라운드 비선형 (Non-linear) : S-Box 키추가 (Key addition) : 라운드키의 XOR
대칭키암호알고리즘비교
비대칭키암호 1976 년 Diffie 와 Hellman 에의해키분배방식알고리즘발표이후많은알고리즘이제안됨 두키가서로다르므로 비대칭 이라고부르며, 두키가공개키와비밀키로명명되어 공개키암호 라고부름 비밀키보관에따라안전도가좌우되고, 통신상대의확인에디지털서명사용이가능하고, 키관리에뛰어남 상대적으로암호화속도가느려직접데이터를암호화하는데에는사용되지않음
RSA (1) RSA(Rivest, Shamir, Adelman) 1978 년 MIT 의 Rivest, Shamir, Adelman 에의해제안 인터넷뱅킹과같은인증서를통한인증체제에서주로활용
암호화과정 RSA (2) 소인수분해의복잡성을이용하여구현 가입자는두개의소수 p, q 선택하여 n = p q 계산 p, q 를알고있는사용자는 n 을계산하기쉽지만, n 만가지고는 p, q 를유추하기어려움
RSA (3) 암호화 복호화
RSA (4)
RSA (5)
RSA (6)
RSA (7) RSA 암호의안전성 소수 p 와 n 에달려있음 공개키 e 와 n 으로비밀키 d 를찾을수있으면쉽게해독됨 n 으로부터 p,q 를찾을수있으면 n 의소인수분해가가능하고, 오일러함수를찾게되어 e 로부터 d 를찾아낼수있음 부가조건 p 와 q 는거의같은크기의소수 p - 1 과 q 1 은큰소수를인수로가져야함 p 1 과 q 1 의최대공약수는작아야함 현재까지 p, q 의크기가 100 자리이고, n 이 200 자리인합성수의경우 n 의소인수분해가거의불가능한것으로알려짐 e 와 d 의크기가너무작아도안되지만, 지나치게크면연산양이많아져서속도가저하됨 상용장비의경우 512 비트의 n, 약 155 자리수 연산부하증가로상용화에어려움이있음
ElGamal 그외공개키알고리즘 이산대수문제를근간으로만들어진공개키기반암호알고리즘 ECC ElGamal 의이산대수문제대신타원곡선이산대수문제를응용한것
알고리즘비교 (1) RSA ElGamal ECC 수학적문제 소인수분해 이산대수 타원곡선이산대수 키크기 크다 크다 작다 속도 비교적느리다 비교적느리다 빠르다 암호문크기 - 평문의두배 - 메모리 ElGamal에비해적음 가장많이차지 가장적게차지 비용 많이소요 많이소요 적게소요 통신 유선 유선 무선
알고리즘비교 (2) 대칭키암호화 / 복호화에동일한키사용수신자와송신자의키교환필요공유한키를비밀로유지디지털서명불가능속도가빠름 공개키 암호화 / 복호화에각기다른키사용 수신자와송신자는연관된쌍중하나를알아야함 키쌍중하나 ( 개인키 ) 를비밀로유지 공개키를이용한디지털서명가능 속도가느림