암호학의 기초 2001. 4. 23. 2001.4.23,(월)

목 차 1. 암호의 목적 2. 기본 용어 7. 인증 3. 암호문의 형태 8. 디지털 서명 4. 블록 암호 9. 해쉬 함수 목 차 1. 암호의 목적 2. 기본 용어 3. 암호문의 형태 4. 블록 암호 5. 스트림 암호 6. 공개키 암호 7. 인증 8. 디지털 서명 9. 해쉬 함수 10. 질문과 토론 2001.4.23,(월)

암호의 목적 2001.4.23,(월)

우편 수단의 예 B A 과거 B A 현재 2001.4.23,(월)

예제 A가 보낸 편지를 받고 B가 생각할 수 있는 문제점 전자 우편의 득과 실 해결 방안 : 암호 사용 다른 사람이 내용을 보지 않았는가? (기밀) A가 보낸 것은 확실한가? (변조) 편지의 내용이 변조되지 않았는가? (위장) A가 보낸 사실을 부인하지 않을까? (송(수)신 부인) 전자 우편의 득과 실 해결 방안 : 암호 사용 2001.4.23,(월)

기본 용어 2001.4.23,(월)

암호 알고리즘 평문을 암호문으로(암호화) 또는 암호문을 평문으로(복호화) 변환하는 방법(암호 시스템을 사용하려는 사람은 누구나 가지고 있음) 변환 시 사용되는 변수(정보)를 "키"라 함 키의 공유 방법에 따라 비밀키 암호와 공개키 암호로 구분 비밀키 암호: 송수신자가 별도의 안전한 방법으로 (비밀)키를 공유 공개키 암호: 암호화시는 상대방의 공개키를 사용하고 복호화시에는 자신의 비밀키를 사용 2001.4.23,(월)

비밀키 암호와 공개키 암호 (비밀키 암호) (공개키 암호) 2001.4.23,(월)

비밀키 .vs. 공개키 알고리즘 암호시스템 비밀키 알고리즘 공개키 알고리즘 항목 암호키의 관계 암호키=복호키 암호키복호키 O:장점 X:단점 암호시스템 비밀키 알고리즘 공개키 알고리즘 항목 암호키의 관계 암호화 키 복호화 키 암호알고리즘 대표 예 비밀키의 분배 비밀키의 보유수 안전한 인증 암/복호화 속도 암호키=복호키 비밀 비밀 공개 Skipjack* DES 필요(X) 많음(X), 상대방별 키 필요 곤란(X) 빠름(O) 암호키복호키 공개 {비밀} 비밀 {공개} 공개 RSA 불 필요(O) 적음(O), 자신의 키만 비밀 용이(O) 느림(X) 2001.4.23,(월)

암호문의 형태 2001.4.23,(월)

예제 문장(text) 음성(voice) 화상(image) 평문 : 안녕하십니까? 암호문 : !&ef6*)+|^zd 아날로그 방식 디지털 방식 화상(image) 2001.4.23,(월)

비밀키 암호 2001.4.23,(월)

비밀키 암호 기술 구현 평가/분석 설계 2001.4.23,(월)

암호 공격방식 Ciphertext only attack Known plaintext attack Chosen plaintext attack Adaptively chosen plaintext attack Adaptively chosen ciphertext attack 2001.4.23,(월)

비밀키 암호의 장점 구현이 용이(적은 비용) 빠른 속도(실시간 서비스) 키 크기가 상대적으로 작음 각종 암호시스템의 primitive로 작용 약한 암호에서 강한 암호로의 전환 용이 오랜 역사 2001.4.23,(월)

비밀키 암호의 단점 안전하게 키를 공유하는 방법에 제한 관리할 키의 가지수가 많음 자주 키를 교환해야 하는 경우에 불편 디지털 서명 등의 기법에 적용하기가 곤란 안전성을 분석하기가 어려움(수학적 난제에 어려움을 두지 않음) 2001.4.23,(월)

비밀키 크기 .vs. 공개키 크기 비밀키 공개키(RSA 기준) 56 비트 64 비트 80 비트 112 비트 128 비트 384 비트 512 비트 768 비트 1792 비트 2304 비트 2001.4.23,(월)

블록 암호 .vs. 스트림 암호 결정요소 블록 암호 적용환경 구현방법(H/W, S/W:속도,메모리(code size, data size, cache memory)) 블록 암호 다양한 응용(예: 인증, 해쉬 함수) 많이 연구된 이유: 표준화, DES ‘90년대 들어 강력한 분석방법으로 인하여 많은 연구 2001.4.23,(월)

블록 암호 .vs. 스트림 암호 스트림 암호 일반적으로 H/W 설계 시 블록 암호에 비해 빠르며 적은 구현 복잡도를 지님 Buffering에 한계가 있거나 받은 문자를 개별적으로 처리해야 하는 경우 풍부한 이론을 가지고 있음에도 많이 공개되지 않는 이유: “proprietary and confidential” 2001.4.23,(월)

블록 암호 운용방법 2001.4.23,(월)

블록 암호 모드(ECB) 2001.4.23,(월)

블록 암호 모드(OFB) 2001.4.23,(월)

블록 암호 모드(CFB) 2001.4.23,(월)

블록 암호 모드(CBC) 2001.4.23,(월)

블록 암호 예제 2001.4.23,(월)

블록 암호 예제(1) 평문 시저암호 2001.4.23,(월)

블록 암호 예제(2) 평문 DES(ECB 모드) 2001.4.23,(월)

블록 암호 예제(3) 평문 DES(CBC 모드) 2001.4.23,(월)

블록 암호 알고리즘 소개 2001.4.23,(월)

DES 1972년 공모(미국 상무성) IBM이 개발(개발자 비공개) NSA에서 수정(키 크기 등) NIST에서 표준으로 공표(1977년) 5년마다 안전성 재평가 기본사양 입출력 크기: 64비트 키 크기: 56비트 라운드 수: 16 안전성: DC, LC, DES Key Challenge 2001.4.23,(월)

DES 알고리즘 구조 2001.4.23,(월)

DES 알고리즘 구조 2001.4.23,(월)

FEAL 1987년 일본 NTT 개발 기본사양 S/W 구현에 적합 안전성: DC, LC에 취약 입출력 크기: 64비트 키 크기: 64비트 라운드 수: 4,8,12,16,32 S/W 구현에 적합 안전성: DC, LC에 취약 2001.4.23,(월)

IDEA(1) 1990년 유럽의 Lai와 Massey가 개발 기본사양 S/W 구현에 적합 안전성: 8라운드 IDEA 안전 입출력 크기 : 64 비트 키 크기 : 128 비트 라운드 수: 8 S/W 구현에 적합 안전성: 8라운드 IDEA 안전 PGP에 채책 2001.4.23,(월)

IDEA(2) 2001.4.23,(월)

RC5 1994년 미국의 Rivest가 개발 입출력, 키 크기 및 라운드 수 : 가변 S/W, H/W 구현에 모두 적합 입출력, 키 크기 및 라운드 수 : 가변 S/W, H/W 구현에 모두 적합 알고리즘이 매우 간단하며 속도가 빠름 AES의 후보 알고리즘인 RC6의 모태 2001.4.23,(월)

MISTY 1996년 일본 미츠비시에서 개발 DC/LC에 안전성 증명되는 구조 기본사양 입출력 크기 : 64 비트 키 크기 : 128 비트 라운드 수 : 8 라운드 이상 2001.4.23,(월)

SKIPJACK 1990년 미국 NSA에서 개발 1998년 까지 비밀로 분류 Fortezza 카드에 사용 기본사양 입출력 크기 : 64 비트 키 크기 : 80 비트 라운드 수 : 32 2001.4.23,(월)

DES를 좀더... 2001.4.23,(월)

DES 의 일생 탄생기 ‘70년대 성장기 ‘80~’90년대 중반 쇠퇴기(?) ‘90년대 말 1977년 이후 매 5년마다 표준(안전성) 알고리즘 검토 1987년까지 안전성만 보장하고 있음 현재 DES를 대치 할 새로운 알고리즘을 선정중에 있음(AES) 현재 전 세계적으로 가장 널리 보급되어 있으며 지금도많이 사용됨 2001.4.23,(월)

DES의 H/W 구현 기술 년도 회사 Chip Clock 속도(Byte/s) 1991 1993 1994 1995 Newbridge VLSI Tech. CE-Infosys CA20C03A CA95C68 VM007 SuperCrypt 6868* 25 MHz 33 MHz 32 MHz 30 MHz 3.85 M 14.67 M 200 M 20 M 64 M * DES 1회 동작 : 8 clock cycle 2001.4.23,(월)

DES의 S/W 구현 기술 Processor Clock 속도(Byte/s) 8088 68040 80486 Sparc 10/52 HP9000/887 4.7 MHz 40 MHz 66 MHz 125 MHz 2.96 K 128 K 344 K 672 K 1.57 M 2001.4.23,(월)

DES의 S/W 구현 신기술 E. Biham에 의하여 제안(‘97.1) Bit-slice 기법 사용 최근 DES 및 RC5 해독에 사용 속도: 300 MHz Alpha processor를 사용시 17 MB/s 의 속도를 보임(동일 processor 를 사용한 기존 최고 속도: 3.5 MB) MISTY 알고리즘에도 적용되어 상당한 속도 개선을 이룸 (‘97.10) 2001.4.23,(월)

블록 암호의 안전성 2001.4.23,(월)

블록 암호의 안전성 키 크기 구조적 안전성 취약 구조 분석 키 전수 조사 2001.4.23,(월)

블록 알고리즘 분석/해독 기법(I) DC: Differential Cryptanalysis(‘90) ‘90년 이전: DES 구조 및 S-Box의 특성 분석 DES: 247 의 복잡도로 해독 가능 LC: Linear Cryptanalysis(‘93) DES: 243 의 복잡도로 해독 가능 ‘94년 1월 12대의 workstation을 이용하여 50일 만에 DES를 해독한 결과 발표 Exhaustive key search(키전수조사) H/W(‘93): DES key search machine(100만불) S/W(‘97,’98,’99): Internet computer 및 전용칩을 이용 키 조사 2001.4.23,(월)

블록 알고리즘 분석/해독 기법(II) 기타 Higher order Differential attack Truncated Differential attack Interpolation attack Impossible attack Related-Key attack Differential fault attack Slide attack 등 2001.4.23,(월)

DES Challenge 2001.4.23,(월)

DES Challenge DES Challenge I ‘97.2.18 : 해독 시작 ‘97.6.17 : 해독 성공 분산환경(병렬처리) DES Challenge II ‘98.7.1 : 해독 시작 ‘98.7.3 : 해독 성공(56시간) 전용 칩 DES Challenge III ‘99.1.18 : 해독 시작 ‘99.1.19 : 해독 성공(22시간) 전용 칩 + 10만대 PC 2001.4.23,(월)

DES Challenge 2001.4.23,(월)

DES 생존 방안 나 DES 2001.4.23,(월)

이중 암호 2001.4.23,(월)

삼중 암호(triple-DES) 2001.4.23,(월)

새로운 미국 표준 알고리즘: AES 2001.4.23,(월)

AES 배경(NIST) Need for DES replacement Need for E-Commerce Privacy DES Cracks Let’s do it the right way public input and analysis International Process (요구조건) 128비트 입출력크기, 128,192,256 비트 키 크기 (Criteria) 안전성, 효율성, 유연성 2001.4.23,(월)

AES 후보 5개 알고리즘 12개 국에서 15개의 알고리즘이 제안 2라운드 후보 알고리즘: 5개(‘99.8.9) 미국 3(MARS, RC6, Twofish) 유럽 2(RIJNDAEL, Serpent) 최종 알고리즘: 2000년 9월말 2001.4.23,(월)

한국 표준 블록 알고리즘 SEED 2001.4.23,(월)

스트림 암호 2001.4.23,(월)

스트림 암호-개요 모태: one-time pad 이진수열 발생기 요구조건 장점: perfect cipher, unconditionally secure 단점: vast amount of secret key needed 이진수열 발생기 요구조건 주기가 길어야 한다. 통계적 난수 특성이 우수해야 한다. 선형복잡도가 커야 한다. 상관공격에 안전해야 한다. 2001.4.23,(월)

암호화 방법 2001.4.23,(월)

Additive 스트림 암호 2001.4.23,(월)

자동 동기 스트림 암호 2001.4.23,(월)

이진수열 발생법 2001.4.23,(월)

LFSR 2001.4.23,(월)

NFSR 2001.4.23,(월)

비선형 여과함수 2001.4.23,(월)

비선형 결합함수 2001.4.23,(월)

비선형 결합함수:예제 2001.4.23,(월)

시각제어논리(예제) 2001.4.23,(월)

기타 2001.4.23,(월)

스트림 암호 발전 방향 2001.4.23,(월)

발전방향(1) 80년대 이전: Geffe, Threshold, Stop-and-go, MUX 등: 대부분 취약함(Alternating step generator 제외) Summation generator(‘84): 해독 Gollmann cascade(‘87): 해독 Shrinking Generator(‘93): 구현상 문제 A5(‘94, GSM의 CDMA에 사용): 해독 2001.4.23,(월)

발전방향(2) Word 단위의 스트림 암호(S/W) FCSR을 이용한 스트림 암호: 문헌상에 공개된 것은 없음 Fish(‘94): 취약® Pike(‘95) SEAL(‘94): 취약점 없을 것으로 간주되었으나 ‘97년에 축소모델에 대하여 약점이 발견 WAKE(‘94): 취약점이 있으나 빠른 속도로 인하여 Anti-virus program에 사용 FCSR을 이용한 스트림 암호: 문헌상에 공개된 것은 없음 2001.4.23,(월)

발전방향(3) 수열의 주기성 및 선형복잡도에 대한 많은 이론이 제시됨: ‘60년대부터 연구되기 시작하여 암호 뿐만 디지털 통신분야에도 많이 응용되며, 많은 스트림 알고리즘 분석에 사용 대부분의 공격방식은 Correlation attack과 Divide-and-conquer attack Resynchronization weakness 2001.4.23,(월)

비밀키 암호 etc 2001.4.23,(월)

비밀키 국제 표준화 동향(1) ISO/IEC JTC1/SC27/WG2 Entity authentication: Mechanisms using symmetric encipherment algorithms(IS 9798-2) Hash-functions using an n-bit block cipher algorithm(IS 10118-2) Key management: Mechanisms using techniques(IS 11770-2) 2001.4.23,(월)

비밀키 국제 표준화 동향(2) Modes of operation for a 64-bit block cipher algorithm(IS 8372) Mode of operation for an n-bit block cipher algorithm(IS 10116) Data integrity mechanism using a cryptographic check function employing a block cipher algorithm(IS 9797) 2001.4.23,(월)

비밀키 알고리즘 등록 현황(1) 2001.4.23,(월)

비밀키 알고리즘 등록 현황(2) 2001.4.23,(월)

비밀키 암호 사용 주요 S/W PGP: IDEA PEM: DES(CBC) SSL: DES, IDEA, RC-2, RC-4 RSA-Euro: DES 기타: MITRENET, ISDN, KryptoKnight 등 2001.4.23,(월)

휴식 2001.4.23,(월)

공개키 암호 2001.4.23,(월)

공개키 암호-개념(1) 한번 잠기면 영원히 열지 못하는 자물쇠 Keyed 일방향 함수 Trapdoor 일방향 함수 키 없는 자물쇠 한번 잠기면 영원히 열지 못하는 자물쇠 Keyed 일방향 함수 Trapdoor 일방향 함수 잠김 열림 잠김 열림 공개키 비밀키 (예:비밀키 암호) 공개키 암호 일방향 함수 (one-way function) 주어진 평문x에 대해, 암호문 f(x)를 계산하는 것은 용이하나 f(x)로 부터 x를 계산하는 것은 계산상 불가능한 함수 f 2001.4.23,(월)

공개키 암호-개념(2) A B B A 기밀성 (A가 B에게 평문 M을 암호화하여 보내는 경우) 잠김 열림 A B (어느 누구도 암호문을 생성할 수 있지만 오직 B만이 복호 가능) 인증성(디지털 서명)(A가 B에게 평문을 서명하여 보내는 경우) A의 비밀키 A의 공개키 잠김 열림 B A (A만이 서명을 할 수 있지만 어느 누구도 확인 가능) 2001.4.23,(월)

비밀키 암호의 키분배 U1 : 안전한통신로 K10 K1 K2 U5 U2 총 키의 개수 : 5C2 = 10개 K3 K9 K8 2001.4.23,(월)

공개키 암호의 키분배 U1 (pk1, sk1) : 일반통신로 pk1 U5 U2 pk2 공개 영역 (pk5, sk5) 총 키의 개수 : 5개 U3 (pk4, sk4) (pk3, sk3) 2001.4.23,(월)

공개키 분배와 전화번호(1) 전화번호 안내 서비스 갑순이 전화번호는 ? 860-4957입니다 너의 전화번호? 860-4957 2001.4.23,(월)

공개키 분배와 전화번호(2) 공개키 관리 센터 갑순이 공개키는 ? abqwert입니다 너의 공개키? abqwert 2001.4.23,(월)

공개키 암호와 수학의 난제 인수분해문제 이산대수문제 타원곡선상의 이산대수 Lattice 문제 Knapsack 문제 Error Correcting Code 등 2001.4.23,(월)

RSA 2001.4.23,(월)

RSA(1) 1978년 Rivest-Shamir-Adleman이 제안 키 생성 큰 자리 소수 p, q 생성 n = p x q Euler Totient Function : f(n) = (p-1)(q-1) 공개키 (e, n), 개인키 (d, n) e x d = 1 mod f(n) 공개키 (e, n)으로 부터 개인키 d를 구할 수 있는가 ?  p, q를 알면 계산 가능  n으로부터 p, q를 구하는 인수분해문제 2001.4.23,(월)

RSA(2) 암호화/복호화 디지털 서명 암호화 : C = Me mod n 복호화 : M = Cd mod n 서명 생성 : S = h(M)d mod n 서명 검증 : h(M) = Se mod n 2001.4.23,(월)

RSA와 인수분해 p, q가 주어지면 n의 계산은 쉽다 n으로부터 p,q의 계산은 어렵다 예제 p = 131, q = 173이면 n = p q 값은 ? n = 8,881인 경우 n의 소인수 p, q 값은 ? p, q는 10100이상의 큰 소수인 경우 n 인수분해 어려움 : RSA 안전성 2001.4.23,(월)

RSA -기타사항 소수의 생성 방법 : 강한소수(strong prime) 모듈라 멱승방법(예) : 510 mod 69 계산 ? 10 = 23 + 2 510 = ((52)2 x 5)2 mod 69 = (252 x 5)2 mod 69 = (4 x 5)2 mod 69 = 55  4회 모듈러 곱셈 연산 지수값이 e인 경우 ae mod n계산  평균 모듈러 곱셈 연산 회수 : 1.5 log2 e 2999 < e < 21000이면 1,500회 모듈러 곱셈 연산 2001.4.23,(월)

RSA 암호/서명 예제 p = 41, q = 53, n = p q = 2173 f(n) = (p-1)(q-1) = 40 x 52 = 2080 공개키 e = 17 = 24 + 1 비밀키 d = 1713 (1713 x 17 mod 2080 = 1) 공개키 e에 의한 평문 M=5의 암호화 : 517 mod 2173 = 595 개인키 d에 의한 복호화 : 5951713 mod 2173 = 5 개인키 d에 의한 평문 M=5의 서명 : 51713 mod 2173 = 1392 공개키 e에 의한 검증 : 139217 mod 2173 = 5 2001.4.23,(월)

Diffie와 Hellman 2001.4.23,(월)

Diffie-Hellamn 키분배(1) g, p, ya(또는 yb)로 부터 xa(또는 xb)를 계산할 수 있는가 ? 1976년 Diffie와 Hellman에 의하여 제안 p는 큰 자리(> 10200) 소수 g : GF(p)의 원시원소 사용자 A :개인키 xa, 공개키 ya = gxa mod p 사용자 B :개인키 xb, 공개키 yb = gxb mod p g, p, ya(또는 yb)로 부터 xa(또는 xb)를 계산할 수 있는가 ?  이산대수문제의 어려움 2001.4.23,(월)

Diffie-Hellamn 키분배(2) 공통키 K 분배 (Alice) (Bob) ya yb xa xb Insecure channel (Alice) yb (Bob) xa K = ybxa = gxa xb mod p xb K = yaxb = gxa xb mod p 공통키 K 분배 메시지 암호화 : C = EK(M) C 메시지 복호화 : M = DK(C) 2001.4.23,(월)

Diffie-Hellamn 키분배(예제) p = 283 : 소수 g = 3 : GF(p) = {0, 1, . . ., 282}의 원시원소 ya =190 Insecure channel (Alice) (Bob) yb = 142 개인키 xb = 123 공개키 yb = gxb mod p = 3123 = 142 mod 283 K = yaxb = 190123 = 149 mod 283 개인키 xa = 35 공개키 ya = gxa mod p = 335 = 190 mod 283 K = ybxa = 14235 = 149 mod 283 공통키 K = 149 분배 2001.4.23,(월)

Diffie-Hellman과 이산대수 x가 주어지면 gx mod p의 계산은 쉽다 gx mod p 로 부터 x의 계산은 어렵다 2001.4.23,(월)

ElGamal & 타원곡선 2001.4.23,(월)

ElGamal 공개키 암호(1) Diffie-Hellman 키분배 방식을 변형시켜 공개키 암호 방식 제안 개인키 x, 공개키 y = gx mod p 암호화 r = gk mod p (난수 k) c = m yk mod p 암호문 : (r, c) 복호화 m = c r-x mod p 2001.4.23,(월)

ElGamal 공개키 암호(2) (Alice) (Bob) 공개키 y 공개키 y 암호화 : 개인키 x r = gk mod p Insecure channel 공개키 y (Alice) (Bob) 공개키 y 개인키 x 암호화 : r = gk mod p c = m yk mod p (r, c) 복호화 : m = c r-x mod p 2001.4.23,(월)

타원곡선 암호(개요) 타원곡선 장점 y2=x3+Ax+B 꼴의 대수곡선으로 순수수학, 암호론 모두에서 매우 중요 순수수학에서는 350년 동안 풀리지 않던 수학 최고의 난제인 페르마 정리를 증명하는데 핵심적인 역할 암호론에서는 현재까지 알려진 모든 공개키 암호 중에 가장 안전하고 효율적인 타원곡선암호에 사용 장점 비트 당 안전성이 높음(160 비트의 타원곡선암호는 1,024비트 RSA 암호에 상응) 기존 알고리즘이 다양한 공격에 취약함이 발견된 반면 타원곡선 암호는 현재까지 특별한 취약점이 알려져 있지 않음 암호화 및 서명의 속도가 빠름 키 사이즈가 작고, 계산량과 대역폭이 작아 스마트 카드처럼 메모리와 계산 능력이 제한되는 곳에 유리 2001.4.23,(월)

타원곡선 암호(동향) 세계적인 표준화 그룹인 IEEE P1363, ISO/IEC, ANSI X9 등에서 타원곡선에 관한 표준화 작업이 이루어 지고 있으며, ISO/IEC의 표준화 작업에는 국내의 의견이 반영된 바 있음 Certicom, NTT, Matsushita, Tompson, Siemens, NeXT Computer를 비롯한 많은 회사에서 타원곡선 암호를 구현하였으며 여러가지 타원곡선 암호를 이용한 정보보호서비스가 제공될 예정 최근 전자상거래 SET2.0에 타원곡선암호를 사용하기로 결정하므로써, 타원곡선암호가 전세계적으로 널리 사용될 것으로 보임 결론적으로, 타원곡선암호가 RSA를 대치하는 주도적인 공개키 암호가 될 것으로 예측됨 2001.4.23,(월)

인증 2001.4.23,(월)

인증이란? 사용자 인증 누구인가 ? 메시지 인증 정보가 위조/변조 되었는가 ? 누가 그 정보를 제공하였는가 ? 누가 그 정보를 제공했는지 3자에게 증명 가능  디지털 서명 2001.4.23,(월)

사용자 인증 방법(1) 신체적 특징 이용 지문, 눈동자, 목소리, 생김새, 필체 무엇을 알고 있는가 ? 키, 패스워드, 공통된 과거 기억 무엇을 가지고 있는가 ? 증표, 카드, 토큰  출입통제, 특정 지역 내에서 사용  네트워크를 통한 신분확인 불가능 2001.4.23,(월)

사용자 인증 방법(2) Replay Attack 2001.4.23,(월)

사용자 인증 방법(3) 네트워크을 통한 사용자 인증  암호 기술의 사용 없이 불가 암호 프로토콜의 중요성 인식 필요 사용자 인증과 함께 암호키 분배 안전한 사용자 인증의 실현 신체적 특징 + 패스워드 + 암호 방식 암호를 이용한 인증 방식 일방향 인증 : 패스워드 방식, challenge-response 방식 양방향 인증 2001.4.23,(월)

안전하지 못한 인증 방법 예 (1) (2) 패스워드는 ? 열려라 참깨 패스워드는 ? = EK(열려라 참깨) 열려라 참깨 = DK( ) K : 공유 비밀키 2001.4.23,(월)

패스워드 인증 방식 기존의 패스워드 방식  One-Time Password 등장 매번 같은 패스워드 사용 Replay Attack에 의하여 깨짐 Dictionary Attack에 취약 암호 알고리즘의 강도와 무관  One-Time Password 등장 2001.4.23,(월)

Challenege-Response 방식 K : 공유 비밀키 비 밀 키 방 식 난수 : r C C =? EK(r, Alice) C = EK(r, Alice) 공 개 키 방 식 pk c = Epk(r, Bob) r 공개키 pk, 개인키 : sk 공개키 pk (r, Bob) = Dsk(c) 2001.4.23,(월)

양방향 인증 : 비밀키 방식 K : 공유 비밀키 Bob, rB 난수 : rB 난수 : rA C1 = EK(rA, rB, Bob) C1 (rA, rB, Bob) = DK(C1) C2 = EK(rA, rB) C2 (rA, rB) = DK(C2) 2001.4.23,(월)

양방향 인증 : 공개키 방식 공개키 : pka, 개인키 : ska 공개키 : pkb 공개키 : pkb, 개인키 : skb pka, pkb 난수 : rB C1 = Epka(rB, Alice) C1 (rB, Alice) = Dska(C1) 난수 : rA C2 = Epkb(rA, rB) C2 (rA, rB) = Dskb(C2) rA 2001.4.23,(월)

비밀키 인증 방식 vs 공개키 인증 방식 비밀키 인증 방식 공개키 인증 방식 소규모 시스템에 적합 키 관리 센터 역할 높다 키 분배 어렵다. 공개키 인증 방식 대규모 시스템에 적합 : 전자상거래 키 분배 용이 공개키 인증 문제 대두  인증 센터, 공개키 기반 구조 2001.4.23,(월)

공개키 인증 문제(1) 공개키는 많은 사람에게 널리 알려야 한다. pka가 A의 공개키인지 확인 필요 공개키 인증(X) 공개키 인증을 위한 인증 센터 필요 공개키 기반 구조 구축의 핵심 사이버 사회의 신분확인을 위한 기반 공개키 인증(X)  건전한 사이버 사회 실현 불가 사이버 사회(사이버 인간)을 위한 주민등록증은 ? ==> 인증 센터에 의한 공개키 인증서 2001.4.23,(월)

공개키 인증 문제(2) Alice Bob Charles Charles의 공개키 = pkb C 공개키 : pka 개인키 : ska 공개키 : pkb 개인키 : skb C = Epkb(M) M = Charles에게. 나의 비밀번호는 7623입니다 M = Dskb(C) M = Charles에게. 나의 비밀번호는 7623입니다 Charles Dskc(C) = ? 공개키 : pkc 개인키 : skc 2001.4.23,(월)

공개키 확인서를 이용한 인증 공개키 pk, 개인키 : sk 공개키 확인서 : Cert(pk) Cert(pk), pk c = Epk(r, Bob) c (r, Bob) = Dsk(c) r 2001.4.23,(월)

디지털 서명 2001.4.23,(월)

디지털 서명 서명이란 ? 디지털 서명 : 공개키 암호의 역 변환 사이버 사회의 인감 도장 나만이 할 수 있는 능력 서명자의 도움 없이 확인 가능 : 증거 능력 디지털 서명 : 공개키 암호의 역 변환 공개키에 의한 암호화 ==> 개인키에 의한 복호화 개인키에 의한 서명 ==> 공개키에 의한 서명 검증 사이버 사회의 인감 도장 ==> 인감증명서 = 공개키 확인서, 인감도장 = 개인키 종류: 부가형 서명, 복원형 서명 2001.4.23,(월)

디지털 서명의 정보보호기능 위조 불가 서명자 인증 변경 불가 재사용 불가 부인 봉쇄 2001.4.23,(월)

위조 불가 서비스 (Alice) (Bob) Bob은 Vpka(m, X) = Yes를 만족하는 X를 계산할 수 없다. (m, Sska(m)) 공개키 : pka 개인키 : ska Sska(m) : m에 대한 서명 공개키 : pka (Bob) (m, Sskb(m)) Vpka(m, Sska(m)) = Yes Vpka(m, Sskb(m)) = No 공개키 : pkb 개인키 : skb Bob은 Vpka(m, X) = Yes를 만족하는 X를 계산할 수 없다. Sskb(m) : m에 대한 서명 2001.4.23,(월)

서명자 인증 (Alice) 누구나 Sska(m)이 m에 대한 Alice의 서명임을 확인할 수 있다. (m, Sska(m)) 공개키 pka 공개키 : pka 개인키 : ska Vpka(m, Sska(m)) = Yes pk != pka이면 Vpk(m, Sska(m)) = No Sska(m) : m에 대한 서명 누구나 Sska(m)이 m에 대한 Alice의 서명임을 확인할 수 있다. 2001.4.23,(월)

변경 불가 서비스 (판사) (Bob) (Alice) (m’, Ssk(m’)) Vpka(m’, Ssk(m’)) = No Sska(m) : m에 대한 A의 서명 (Bob) (Alice) Sska(m) Ssk(m’) m : A가 B에게 10만원을 빌렸다. m’ : A가 B에게 1000만원을 빌렸다 변조과정 2001.4.23,(월)

재사용 불가 서비스 (판사) (Bob) (Alice) (m’, Sska(m)) Vpka(m’, Sska(m)) = No Sska(m) : m에 대한 A의 서명 (Bob) (Alice) m : A가 B에게 10만원을 빌렸다. m’ : A가 B에게 1000만원을 빌렸다 2001.4.23,(월)

부인 봉쇄 서비스 Bob은 Sska(m)이 m에 대한 Alice의 서명임을 증명할 수 있고 누구나 이를 확인할 수 있다. (판사) Vpka(m, Sska(m)) = Yes (m, Sska(m)) Sska(m) : m에 대한 A의 서명 (Bob) (Alice) 2001.4.23,(월)

서명을 이용한 사용자 인증 공개키 pk, 개인키 : sk 공개키 확인서 : Cert(pk) rB c = Ssk(rA, rB) Cert(pk), rA, c pk, Cert(pk) 확인 Vpk((rA, rB), c)= Yes 2001.4.23,(월)

RSA 서명 RSA 공개키 암호와 함께 서명 제안 RSA 서명 및 검증 암호화/복호화의 역변환 가장 널리 사용되고 있음 서명 생성 : 비밀키로 계산 S = h(M)d mod n 서명 검증 : 공개키로 검증 h(M) = Se mod n 암호화/복호화의 역변환 가장 널리 사용되고 있음 2001.4.23,(월)

DSS(1) DSS = DSA + SHA 미국 국가 표준 서명 알고리즘 안전성 : 이산대수문제의 어려움 q : 160 비트 소수 p : 1024비트 소수 (q | (p-1)) g : 위수 q를 갖는 원소 (gq = 1 mod p) 개인키 : 0 < x < q, 공개키 y = gx mod p DSA: digital Signature Standard SHA : Secure Hash Algorithm 2001.4.23,(월)

DSS(2) 서명 검증 h( ) : SHA 서명 생성 : (m, r, s) r = (gk mod p) mod q (난수 k) s = k-1 (h(m) + xr) mod p 서명 검증 w = s-1 mod q u = h(m) w mod q, v = r w mod q r = (gu yv mod p) mod q임을 확인 2001.4.23,(월)

해쉬함수 2001.4.23,(월)

해쉬 함수 해쉬란 ? 디지털 서명 실현의 필수 요소 서명 효율 증대 서명의 안전성 증대 임의의 메시지 길이를 고정된 메시지 길이로 변환 디지털 서명 실현의 필수 요소 서명 효율 증대 서명의 안전성 증대 대표적인 해쉬 함수 : SHA, MD5, RIPEMD 2001.4.23,(월)

해쉬 함수와 디지털 서명 해쉬값 해쉬 과정 Append WISC 2000 에 참가하신 모든 분들에게 감사드립니다. 오늘은 2000년 9월 5일, 화요일입니다. bd4xjazfa 해쉬 과정 Append Signature Signature 2001.4.23,(월)

해쉬 함수 요구 조건 주어진 y에 대하여, y = h(x) 인 x 계산 불가 h(m)이 주어진 경우, h(m’) = h(m)인 m’ 계산 불가 h(m’) = h(m) 인 (m, m’) 계산 불가 (충돌회피성, Collision-Resistance) 2001.4.23,(월)

이 한권의 책 2001.4.23,(월)

Applied CRYPTOGRAPHY 2001.4.23,(월)

Handbook of Applied CRYPTOGRAPHY 2001.4.23,(월)

2001.4.23,(월)