Chap 4. 공개키 암호.

Slides:



Advertisements
Similar presentations
Chapter | 4 암호화 기술 Ⅱ암호화. ❖ 암호  통신문의 내용을 제 3자가 판 독할 수 없는 글자 · 숫 자 · 부호 등으로 변경 시킨 것 2/16 암호? 철수 영희 Plaintext attack attack ? ? Cryptography 개방통신로 모레 3.
Advertisements

최성락 최인석 나주한. 특징 : 공개키 n, g 를 사용하여 키 분배가 가능. (g 는 Zn 의 primitive element) Discrete logarithm 에 기반. 두 명 이상의 경우에도 적용가능. 키 교환 없이도.
HTTPS Packet Capture Tutorial
Format String Attack! 포맷 스트링 공격 경일대학교 사이버보안학과 학년 남주호.
Chapter 8 네트워크 보안 Computer Networking: A Top Down Approach , 5th edition. Jim Kurose, Keith Ross Addison-Wesley, April 2009.
(c) Byoungcheon Lee, Joongbu Univ.
암호-4장. 공개키 암호 ㅎㅎ 정보보호 기능의 가장 핵심적 기술인 암호를 다룬다. 흥미로운 암호의 역사를 소개하고, 고전적인 암호체계로부터 현대적인 디지털 암호체계에 이르는 기술의 발전을 살펴보고 현대의 고급 암호분석 기법을 소개한다. 한빛미디어(주)
전자계산학과 대학원 그룹웨어 연구실 진 훈 Code and RSA 전자계산학과 대학원 그룹웨어 연구실 진 훈
제 9 장 구조체와 공용체.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
컴퓨터 프로그래밍 기초 [Final] 기말고사
자바 암호 프로그래밍 Java Cryptography Programming
제13장 전자서명과 인증 프로토콜 Digital Signatures and Authentication Protocols
Chap 8. 인증과 키교환.
교과목 소개 정보보호.
암호학 응용 Applied cryptography
I부 암호.
Ch14 – 2. 인증프로토콜(2) - 공개키 인증서 -.
30장 메시지 보안, 사용자 인증과 키 관리 30.1 메시지 보안 30.2 전자서명 30.3 사용자 인증 30.4 키 관리
File Depender 중간 발표.
공개키 암호화 프로그래밍 전자상거래보안.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
23 장 OSI 상위계층 23.1 세션(session)층 23.2 표현(presentation)층
제10장 메시지 인증과 해쉬 함수 Message Authentication and Hash Functions
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
Error Detection and Correction
정보화 사회와 컴퓨터 보안.
멀티미디어 시스템 (아날로그 이미지,신호를 디지털로 변환 방법) 이름 : 김대진 학번 :
Modulo 연산.
Tail-recursive Function, High-order Function
제9장 공개키 암호 (I) Public-key Cryptography
암호화 및 인증.
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
전자상거래 보안 (암호학과 네트워크보안) ) Chul Ho Rhee
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
문제 2명의 사형수가 있다. 둘에게는 검정색 모자와 흰색 모자를 임의로 씌우는데, 자기가 쓴 모자의 색은 절대로 알 수가 없다. 서로 상대의 모자색만을 볼 수 있고, 이들이 살기 위해선 자신의 쓴 색의 모자를 맞춰야 한다. 단, 둘 중 한명만이라도 자신이 쓴 모자의 색을.
자바스크립트 암호 프로그래밍 Javascript Cryptography Programming
전자서명의 형태 수기서명 디지털서명. 전자서명의 형태 수기서명 디지털서명 전자서명의 필요성.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
8장 쿠키와 세션 한빛미디어(주).
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
16 장 네트워크 보안 : 방화벽과 VPN 16.1 개요 16.2 기밀성 16.3 전자 서명 16.4 인터넷 보안
KERBEROS.
1. 2진 시스템.
제 13장 PGP 암호 기술을 조합하는 기술.
컴퓨터 개론 √ 원리를 알면 IT가 맛있다 쉽게 배우는 컴퓨터 기본 원리 한빛미디어 교재출판부.
비대칭 암호화 알고리즘 공개키 암호화 알고리즘 소속 : 한세사이버보안고등학교 조장 : 안도현
VHDL를 이용한 DES 설계 정보통신컴퓨터공학부 5조 김인옥, 백미숙
SSL, Secure Socket Layer
제 Ⅲ부 키, 난수, 응용 기술.
통신망 정보보호 이재광, 이임영, 소우영, 최용락.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
Modulo 연산.
2장 PHP 기초 PHP의 시작과 끝을 이해한다. 주석문에 대하여 이해한다. echo 문을 이용하여 화면에 출력하
5장. 선택 알고리즘.
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
한국의 인터넷 뱅킹 보안에 대하여 Oxford University Computing Laboratory
(c) Byoungcheon Lee, Joongbu Univ.
수치해석 ch3 환경공학과 김지숙.
제7장 관용암호 이용한 기밀성 Confidentiality Using Symmetric Encryption
암호 시스템 (Crypto system) 신효철
어서와 C언어는 처음이지 제21장.
제 1장 서론 1.#.
아날로그 신호를 디지털 신호로 변환하는 A/D 변환기 A/D 변환 시 고려하여 할 샘플링 주파수 D/A 변환기
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
II-1 단항식의 계산 01 소인수분해 지수법칙 지수법칙 지수법칙⑴ 3개 2개 5개 3+2 m개 n개 (m+n)개 합.
진리표를 이용한 타당성 증명 진리표(truth table) : 단순 문장들이 진리값을 상이하게 가질 수 있는 가능한 모든 경우를 남김없이 열거한 표 (ex) 오늘은 날씨가 맑거나 비가 올 것이다. 오늘은 날씨가 맑다 비가 온다 오늘은 날씨가 맑거나 비가 올 것이다. T.
6 객체.
Presentation transcript:

Chap 4. 공개키 암호

목 차 1. 공개키 암호 시스템의 원리 2. RSA 알고리즘 3. 키 관리

1. 공개키 암호 시스템의 원리 관용 암호 방식의 문제점 키 분배의 문제 디지털 서명이 불가능  공개키 암호로 해결 (1976년 Diffe와 Hellman에 의해 제기)

1.1 공개키 암호 시스템 공개키 알고리즘 공개키 알고리즘의 특징 : 두 개의 다른 키 사용 공개키 : 모든 사람이 접근 가능한 키 (공개) 개인키 : 각 사용자 자신만이 소유 (비밀) (관용 암호에 사용되는 키는 비밀키라고 함) 공개키 알고리즘의 특징 암호 알고리즘과 암호키를 알아도 복호키 계산 불가능 두 개의 키 중 하나는 암호에 다른 하나는 복호에 사용

관용 암호와 공개키 암호 비교 관용 암호 공개키 암호 암호/복호에 동일한 키와 암호/복호에 각각 서로 다른 키 와 관용 암호 공개키 암호 암호/복호에 동일한 키와 암호/복호에 각각 서로 다른 키 와 동일한 알고리즘 사용 동일한 알고리즘 사용 수신자와 송신자는 키를 수신자와 송신자는 연관된 키쌍 중 교환해야 함 하나를 알아야 함 공유한 키(비밀키)는 비밀로 유지 키 쌍중 하나(개인키)를 비밀로 유지 키 분배의 어려움 공개키를 공개 디지털 서명 불가능 디지털 서명 가능 속도가 빠름 속도가 느림

공개키 암호의 단순 모델 : A가 B에게 암호화 메시지를 보내는 경우 1. 공개키와 개인키 생성 평문 암호문 평문 암호 알고리즘 복호 알고리즘 사용자 A 사용자 B 1. 공개키와 개인키 생성 2. 공개키는 공개하고 개인키는 개인이 소유 3. A는 B의 공개키로 메시지를 암호화 4. B는 자신의 개인키로 메시지 복호화 (B의 개인키를 모르는 제 3자는 메시지 복호 불가능)

공개키 암호 시스템 : 기밀성 : 공개키로 암호화함으로써 메시지 기밀성 제공 평문 암호문 평문 암호문과 공개키로부터 평문 획득 불가능 암호 해독자 평문 암호문 평문 암호화 복호화 사용자 A 사용자 B B의 개인키 B의 공개키 키 쌍 출처

공개키 암호 시스템 : 인증 : 개인키로 서명함으로써 송신자 인증 제공 평문 서명문 평문 개인키를 알 수 없음으로 위조된 서명문 작성 불가능 (평문은 알 수 있음) 암호 해독자 평문 서명문 평문 암호화 복호화 사용자 A 사용자 B A의 개인키 A의 공개키 키 쌍 출처

공개키 암호 시스템 : 기밀성과 인증 : 개인키로 서명하고 공개키로 암호화하여 기밀성과 인증 제공 평문 서명문 암호문 서명문 복호화 복호화 사용자 A 사용자 B B의 개인키 B의 공개키 키 쌍 출처 A의 개인키 A의 공개키 키 쌍 출처

1.2 공개키 암호 시스템의 응용 공개키 암호 시스템의 사용 공개키 암호 시스템의 응용 암호/복호 (수신자의 공개키로 메시지 암호) 디지털 서명 (송신자의 개인키로 메시지 서명) 키 교환 (세션키를 교환하기 위해 사용) 공개키 암호 시스템의 응용 알고리즘 암호/복호화 디지털 서명 키 교환 RSA 가능 가능 가능 LUC 가능 가능 가능 DSS 불가능 가능 불가능 Diffie-Hellman 불가능 불가능 가능

1.3 공개키 암호를 위한 요구 사항 공개키 알고리즘의 조건 (Diffie와 Hellman) 키 쌍(공개키 KU, 개인키 KR)의 생성이 쉽다. 다음 식과 같은 암호문의 생성이 쉽다. C = EKUb(M) 다음식과 같은 암호문의 복구화가 쉽다. M = DKRb(C) = DKRb[EKUb(M)] 공개키 KUb로부터 개인키 KRb를 결정하는 것은 어렵다. 공개키 KUb와 암호문 C로부터 메시지 M의 복구가 어렵다. 암호와 복호 기능이 다음과 같이 적용 가능하다. (추가 사항) M = EKUb[DKRb(M)]

1.4 공개키 암호 분석 공격 유형 전사적 공격에 취약  키의 크기를 크게 함으로써 방지 (상대적으로 속도가 느려짐) 공개키로부터 개인키를 계산하는 방법  수학적으로 계산이 불가능함을 증명하지 못함 가능한 메시지 공격 : 모든 가능한 메시지를 공개키로 암호화하여 암호문과 비교  메시지에 임의의 비트를 추가함으로써 방지

1.5 Knapsack 알고리즘 일반적인 개념 : 일정한 크기의 배낭에 어떤 물건을 넣어야 하는지에 관한 문제 정의 cargo 벡터 a = (a1, a2, … , an) ai :정수 평문 메시지 블록 x = (x1, x2, … , xn) xi :이진수 대응하는 암호문 S = a · x =  (ai  xi) 개념 공개키 : a xi = 1은 ai가 Knapsack에 포함된다는 의미 S와 a에 의해 x를 복구 n I=1

Knapsack의 조건 S의 값에 유일한 역이 존재 ex) 두 가지 역이 존재하는 예 a = (1, 3, 2, 5), S = 3 일 경우 x = 1010, x = 0100의 두가지 경우가 존재 일반적인 복호는 어려우나, 특별한 지식이 있을 경우 쉬움 초증가 벡터(superincreasing vector) 이용 초증가 벡터 : a의 각 원소가 선행하는 원소들의 합보다 큰 경우 ex) a’ = (171, 197, 459,1191, 2410) 일 경우 x5 = 1, x4 = 1, x3 = 0, x2 = 1, x1 = 0 임을 쉽게 알 수 있음

Knapsack 문제에 초증가 Knapsack 문제를 묶는 방법 a’을 임의로 선택 (a’ : 쉬운 초증가 Knapsack 벡터) m과 w를 선택 m : a’원소들의 합보다 큰 정수 w : m과 서로 소인 정수 a 생성 (a : 어려운 Knapsack 벡터) a = wa’ mod m 쉬운 Knapsack 벡터로의 변환 가능 w-1a = a’ mod m

Knapsack 알고리즘 사용 예 키 생성 a’ (쉬운 Knapsack) w = 467, m = 523, w-1 = 28 (mod 523) a (어려운 Knapsack) 공개키 : KU = a, 개인키 : KR = {w-1, m, a’) 암호화 평문 = 01001011 암호문 = 818 ( 0 467 + 1 355 + 0 131 + 0 318 + 1 113 + 0 21 + 1 135 + 1 215 = 818 ) 1 3 7 13 26 65 119 267 467 375 131 318 113 21 135 215

Knapsack 알고리즘 사용 예 (계속) 복호화 818 w-1 = 818 28 = 415 (mod 523) 415  267  x8 = 1 415 - 267 = 148  119  x7 = 1 148 - 119 = 29  65  x6 = 0 29  26  x5 = 0 29 - 26 = 3  13  x4 = 0 3  7  x3 = 0 3  3  x2 = 1 3 - 3 = 0  1  x1 = 0  평문 : x1x2x3x4x5x6x7x8 = 01001011

2. RSA 알고리즘 2.1 알고리즘 설명 RSA의 개발 알고리즘 : 1977년에 개발되어 1978년에 공포 (Rivest, Shamir, Adleman) 알고리즘 평문은 블록으로 암호화 암호화 C = Me mod n 복호화 M = Cd mod n = (Me)d mod n = Med mod n 공개키 : KU = {e, n}, 개인키 : KR = { d, n }

Med = M mod n의 증명 오일러 정리 p,q (솟수), n = qp, 정수 n, m (0mn), k (임의의 정수) 일 때 mk(n)+1 = mk(p-1)(q-1)+1 = m mod n (n) : n보다 적고 n과 서로소인 양의 정수가 되는 함수 ( p,q가 솟수일 경우, (pq) = (p-1)(q-1) ) ed = k(n) + 1 ed = 1 mod (n) e = d-1 mod (n)  e와 d는 mod (n)에 곱셈 역원 (e와 d가 (n)에 서로소인 경우에만 참)

RSA 알고리즘 정리 키 생성 p, q 선택 ( p, q는 솟수 ) n = p  q 계산 정수 d 선택 ( gcd((n),d) =1, 1<d< (n) ) e 계산 ( e = d-1 mod (n) ) 공개키 ( KU = {e, n} ) 개인키 ( KR = {d, n} ) 암호화 C = Me ( mod n ) 복호화 M = Cd ( mod n )

RSA 알고리즘 사용 예 공개키와 개인키 생성 1. 두 솟수 p = 7, q = 17 을 선택 2. n = pq = 7  17 = 119 계산 3. (n) = (p-1)(q-1) = 96 계산 4. (n) = 96과 서로소이고 (n)보다 작은 e 선택 ( e = 5 ) 5. de = 1 mod 96이고 d < 96 인 d를 결정 (d = 77)  공개키 KU = {5, 119}, 개인키 KR = {77, 119}

RSA 알고리즘 사용 예 (계속) 암호화와 복호화 : 평문 메시지 M = 19 일 경우 암호문 : 195 = 66 mod 119  66 복호문 : 6677 = 19 mod 119  19 암호화 복호화 암호문 66 2476099 20807 195 = = 119 나머지 : 66 1.27…10140 1.06 …10138 6677 = = 119 나머지 : 19 평문 19 평문 19 KU = 5, 119 KR = 77, 119

2.2 계산적인 측면 암호화와 복호화 계산량을 줄이는 방법 모듈러 연산의 특징 이용 효율적인 지수 승 [(a mod n)  (b mod n)] mod n = (a  b) mod n  중간 결과를 축소 효율적인 지수 승 직접적인 방법 (x16 일 경우) : x16 = xxxxxxxxxxxxxxxx  15번의 곱셈 효율적인 방법 : x2, x4, x8, x16  4번의 곱셈

키 생성 랜덤한 큰 솟수를 찾는 방법 (확률적 검사법) 1. 랜덤하게 홀수 n을 선택 2. 랜덤하게 a<n인 정수 a를 선택 3. 확률적 솟수 판정법 수행 (만약 n이 검사에서 실패하면 1단계로) 4. n이 충분한 횟수로 통과하면 n을 수용, 그렇지 않으면 2단계로 솟수 생성을 위한 검사 횟수 N에 가까운 솟수는 (ln N)에 대하여 평균 1회 생성 ex) 2200 범위의 솟수  ln(2200)/2 = 70 회 정도 시행

암호 해독의 고찰 암호 해독의 접근 방법 전사적 공격  큰 키를 사용하여 방지 인수 n를 두 소인수로 인수 분해  큰 값에 대한 두 솟수의 곱을 인수 분해하는 적당한 알고리즘이 없음 p와 q을 결정하지 않고 직접 (n)을 결정  인수 분해만큼 어려움 (n)을 결정하지 않고 직접 d를 결정

3. 키 관리 3.1 공개키의 분배 공개키의 공개 발표 자신의 공개키를 다른 사용자에게 전송 등의 방법으로 공개 문제점 어떤 사용자가 다른 사용자 A로 위장하여 공개키 공개 (A에 전송되는 암호화 메시지를 읽을 수 있게 됨) KUa KUb KUa KUb . . KUa KUb 사용자 A 사용자 B KUb KUa

공개적으로 사용 가능한 디렉토리 필요한 사항 기관은 각 가입자에 대한 {이름, 공개키}의 디렉토리 유지 각 가입자는 디렉토리 기관에 공개키 등록 가입자는 필요시 새로운 것으로 교체 가능 기관은 디렉토리를 공포 가입자는 전자적으로 디렉토리 접근 가능 문제점 디렉토리 정보를 수정 위조의 공개키로 임의의 가입자로 위장하여 도청

공개적으로 사용 가능한 디렉토리 (계속) 공개키 디렉토리 KUa KUb 사용자 A 사용자 B

공개키 기관 : 공개키 기관에서 공개키 분배 제어 공개키 기관 시행자 A 대응자 B (1) Request || Time1 (2) EKRau[KUb || Request || Time1] (5) EKRau[KUa || Request || Time2] (3) EKUb[IDA || N1] 시행자 A (6) EKUa[N1 || N2] 대응자 B (7) EKUb[N2]

공개키 기관 (계속) (1) 단계 B의 공개키에 대한 요구를 타임스템프와 함께 전송 (2) 단계 자신의 개인키로 암호화하여 전송 (3) 단계 B의 공개키를 저장하고, A의 식별자(IDA)와 임시비표(N1)을 B의 공개키로 암호화하여 전송

공개키 기관 (계속) (4), (5) 단계 B는 (1), (2) 단계와 같은 방법으로 A의 공개키 획득 (6) 단계 B는 임시비표 N1, N2를 A의 공개키로 암호화하여 전송 (7) 단계 A는 N2를 B의 공개키로 암호화하여 전송 문제점 공개키 디렉토리 수정에 취약

공개키 인증서 공개키 기관의 도움없이 인증서를 이용하여 키 교환 인증서 방식을 위한 요구 사항 임의의 가입자는 인증서의 내용(이름, 공개키) 확인 가능 임의의 가입자는 인증서의 정당성 확인 가능 인증 기관만이 인증서 생성과 갱신 가능 임의의 가입자는 인증서의 현행성 확인 가능

공개키 인증서 (계속) : 사용자는 공개키 인증서를 받은 후 인증서로 공개키 전송 공개키 기관 시행자 A 대응자 B KUa KUb CA = EKRau[ Time1, IDA, Kua ] CA = EKRau[ Time2, IDB, Kub ] (1) CA 시행자 A (2) CB 대응자 B : 사용자는 공개키 인증서를 받은 후 인증서로 공개키 전송

3.2 비밀키의 공개키 분배 공개키의 사용처 단순 비밀키 분배 (1) 단계 : 공개키는 느리기 때문에 관용 암호의 비밀키 분배에 많이 사용 단순 비밀키 분배 (1) Kua || IDA (2) EKUa[Ks] 사용자 A 사용자 B (1) 단계 A는 공개키 쌍 {KUa, KRa}을 생성하고, 식별자 IDA와 함께 공개키 전송 (2) 단계 B는 비밀키 Ks를 생성하고 A의 공개키로 암호화하여 전송

단순 비밀키 분배 (계속) 문제점 : 적극적인 공격에 약함 (1) A는 공개키 쌍 {KUa, KRa}을 생성하고, 공개키 전송 (2) E는 메시지를 가로채고, 자신의 공개키(KUe)를 전송 (3) B는 비밀키 Ks를 생성하고 E의 공개키로 암호화하여 전송 EKUe[Ks] (4) E는 메시지를 가로채어 Ks를 획득 (DKRe[EKUe[Ks]] = Ks (5) E는 A에게 EKUa[Ks] 전송  E는 A와 B가 모르게 비밀값 Ks 획득 (도청 공격)

기밀성과 인증을 가지는 비밀키 분배 : 적극적, 소극적 공격에 대한 해결 (1) EKUb [N1 || IDA] (2) EKUa [N1 || N2] (3) EKUb [ N2] 사용자 A 사용자 B (4) EKUb [EKRa [Ks]]

기밀성과 인증을 가지는 비밀키 분배 (계속) : 공개키를 교환했다고 가정 (1) 단계 (2) 단계 (3) 단계 (4) 단계 A의 식별자와 임시비표(N1)를 B의 공개키로 암호화하여 전송 (2) 단계 B는 새로운 임시비표(N2)와 N1을 A의 공개키로 암호화하여 전송 (3) 단계 A는 보증을 위해 B의 공개키로 암호화한 N2을 반환 (4) 단계 A는 비밀키 Ks를 선택하여 M=EKUb[EKRa[Ks]]를 B에게 전송

혼합 방식 키 분배 센터(KDC)의 사용을 유지 : 각 사용자에게 마스터키를 나누어주고, 마스터키로 암호화 된 비밀 세션키를 분배 공개키 방식은 마스터키를 분배하기 위해 사용