암호이론과 보안 고전적 암호시스템

Size: px

Start display at page:

Download "암호이론과 보안 고전적 암호시스템"

경석 야
7 years ago
Views:

1 6장 : 공개키 암호시스템 정보보호이론 Fall 2014

2 Mid-Term 10월 21일 :00 pm ~ 21:00 pm 10월 14일 수업내용까지 Need to fully understand various concepts on cryptographic primitives. Write down all your works to obtain full score

3 6.1 공개키 암호 개요 대칭키 암호 1. 안전한 채널을 통해서 사용자가 서로 동일한 키를 사전 공유 2. n명이 서로 비밀통신을 하기 위해서는 n(n 1) 2 개의 키가 필요 3. 송신자나 수신자의 부인방지를 제공하지 못함.

4 6.1 공개키 암호 개요 공개키 (or 비대칭키(Asymmetric) 암호시스템) Diffie와 Hellman은 1976년 발표된 논문 New Directions in Cryptography 에서 공개키 암호시스템 소개 각 사람마다 한 쌍의 키(공개키 pk, 개인키 sk) 공개키는 모두에게 공개되고, 개인키는 비밀로 보관 공개키 pk로부터 개인키 sk를 도출하는 것은 계산적으로 불가 능 (Computationally Infeasible)

5 6.1 공개키 암호 개요 공개키 암호시스템과 대칭키 암호시스템의 차이점 대칭키 암호시스템 공개키 암호시스템 비밀키 분배 필요 불필요 보유 비밀키 개수 (n명이 비밀통신 하는 경 우) (n 1)개 (상대방별로 키가 필요) 1개 (자신의 비밀키만 보유) 암호화 & 복호화 속도 빠름 느림 대표 예 DES, AES, SEED, ARI A RSA, ElGamal

6 6.1 공개키 암호 개요 하이브리드 암호시 스템 대용량의 데이터 를 암호화하기 위 해서 대칭키 암호 시스템에서 사용 되는 비밀키 k를 공개키 암호시스 템으로 암호화 (E pk (비밀키 k) ) 하여 분배하고, 수신자는 분배된 비밀키를 이용하 여 대용량의 데이 터를 대칭키 암호 시스템으로 암호 화

7 6.1 공개키 암호 개요-기본개념 일방향 함수 (One-Way Function) f 1. f is easy to compute. 2. f 1 is difficult to compute. 소인수분해 문제 When n is large, n = p q is a one-way function. Given p and q, it is always easy to calculate n ; given n, it is very difficult to compute p and q. 최근까지 알려진 결과로는 2009년에 232자리의 십진수를 수 백대의 컴퓨터를 사용하여 2년만에 인수분해에 성공 232자리 십진수는 이진수로 나타내면 768 비트가 필요하며 위 의 결과는 768비트 RSA의 경우 동일한 계산능력으로 2년만에 평문이 복호화 될 수 있음을 의미

8 6.1 공개키 암호 개요-기본개념 Trapdoor One-Way Function(TOWF) 1. f is easy to compute. 2. f 1 is difficult to compute. 3. Given y and a trapdoor, x can be computed easily. 공개키 설계의 기본 개념

9 P-NP 문제 Undecidable No algorithm that solves it Decidable If a problem can be solved in poly-time, it is tractable. Otherwise, it is intractable. P : there exists a poly-time algorithm NP : We don t know if there exists a poly-time algorithm and nobody insists that it cannot be solvable in poly-time.

10 NP 문제 1. 비결정적 단계(Nondeterministic Phase) Guess 2. 결정적 단계(Deterministic Phase) 다항식 시간 검증 예) 소인수 분해 문제 입력 : 합성수 n 비결정적 단계 : p와 q를 Guess 결정적 단계 : p x q =? N 을 다항식시간 안에 검증

11 NP 예) 소인수분해 문제(Integer Factorization Problem, IFP) n = p 1 r 1 p 2 r 2 p n r n 인수분해 방법 1. Trivial Division 2. Fermat Method 3. Pollard p 1 Method 4. Pollard rho Method : particularly effective at splitting composite numbers with small factors. 5. More Efficient Methods : Quadratic Sieve, Number Field Sieve NOTE : On a quantum computer, factorization is a tractable problem using Shor's algorithm.

12 NP 예) 소인수분해 문제(Integer Factorization Problem, IFP) n = p 1 r 1 p 2 r 2 p n r n Trivial Division 입력 n (= p q)을 n 1/2 까지 나눈다. n = n 1/2 n 1/2. 따라서 min(p, q) n 1/2 시간복잡도 입력의 크기 x = log 2 n (즉 n의 이진수 비트 수) n = 2 x, 따라서 n 1/2 = 2 x/2 다항식시간이 아님! NOTE : 시간 복잡도는 입력의 크기의 함수로 표현됨 입력의 크기 : 입력에 사용된 비트수

13 이산 대수 문제 (Discrete Logarithm Problem, DLP) 유한 순환 군 Z p 에 생성자 g와 어떤 원소 y G가 있을 때, x = log g y mod p 를 계산하는 문제 실수 R상에서 log g y 에 대한 계산은 효율적으로 계산. 하지만, Z p 상에서는 로그 연산이 정의되어 있지 않기 때문에, x를 구하 는 효율적인 계산이 존재하지 않음

14 중국인의 나머지 정리(CRT) 쌍마다 서로 소인 자연수 n 1, n 2,, n k 와 정수 a 1, a 2,, a k 에 대하여 x a i (mod n i ), 1 i k, 를 만족하는 x는 법 (n 1 n 2 n k ) 안에서 유일하게 존재 Example : solve x 2 (mod 3), x 3 (mod 5), and x 2 (mod 7). x = 23. 즉 23 2 (mod 3), 23 3 (mod 5), and 23 2 (mod 7).

15 CRT 해법(Gaussian Method) 1. Find M = m 1 m 2 m k. This is the common modulus. 2. Find M 1 = M/m 1, M 2 = M/m 2,, M k = M/m k. 3. Find the multiplicative inverse of M 1, M 2,, M k using the corresponding moduli (m 1, m 2,, m k ). Call the inverses M 1 1, M 2 1,, M k The solution to the simultaneous equations is

16 이차합동(Quadratic Congruence) x 2 a (mod n) 해를 갖는다면 a를 이차 잉여 (Quadratic Residue, QR), 해를 갖지 않는다면 이차 비잉여(Quadratic Nonresidue, QNR) 해를 갖는다면 서로 합동이 아닌 두 개의 해 원소의 개수가 p 1개인 Z p 에 대하여 이차 잉여와 이차 비잉 여의 개수는 정확하게 (p 1)/2개로 동일 예) Z 13 에서 x 2 4 (mod 13)과 x 2 7 (mod 13)의 해 a a x 2 4 (mod 13)를 만족하는 해는 2, 11 x 2 7 (mod 13)에 대한 해는 존재하지 않음 QR = {1,3,4,9,10,12}이고 QNR = {2,5,6,7,8,11}

17 오일러 판정법(Euler s Criterion) 소수 p에 대하여 Z p 의 원소가 QR에 속하는지 QNR에 속하는 지에 대한 판정 기준 a p a QR a (p 1)/2 1 a QNR

18 이차 합동 방정식의 해 n = 4k + 3 k Z + 인 경우 x a n+1 4 mod n, x a n+1 4 mod n n이 합성수인 경우

19 예)다음 이차 합동 방정식의 해를 구하시오 x 2 53 (mod 77) 풀이 = 7 11로 소인수분해 되며, 7과 11은 모두 4k + 3의 형태 2. x 2 4 mod 7 x ±2 mod 7 3. x 2 9 mod 11 x ±3 (mod 11) 4. 4가지 경우로 CRT를 적용 1. x 2 mod 7, x 3 mod x 2 mod 7, x 3 mod x 2 mod 7, x 3 mod x 2 mod 7, x 3 mod 11 해: x ± 58 mod 77, x ± 30 mod 77

20 제곱-곱 연산 방법(Square-and-Multiply Method) 공개키 암호시스템에서는 지수승 연산이 수행 효율적 방 법이 요구됨 y = a 13 = a a 10 = (a 1 ) 2, a 11 = (a 1 ) 2 a 2. a 110 = (a 11 ) 2 3. a 1100 = (a 110 ) 2, a 1101 = (a 110 ) 2 a

21 제곱-곱 연산 방법(Square-and-Multiply Method) 1. square_and_multiply a, x, n { 2. r = a; 3. for i = t 1 downto 0, t x의 비트 수 4. { r r 2 (mod n) If b i = 1 r r a mod n ; b i : x의 i번째 비트; 7. } 8. } return (r)

22 페르마 소정리(Fermat s Little Theorem) p: prime, a Z p, a p 1 1 (mod p) p: prime, a Z p, a p a (mod p) 예) mod mod 11, mod = (mod 11)

23 오일러 함수(Euler s Phi Function) 오일러 함수 φ( )는 1부터 n까지 n과 서로소인 정수의 개수 φ n = a N gcd a, n = 1 p가 소수일 때, φ p = p 1 서로소인 정수 m, n에 대하여, φ(m n) = φ(m) φ(n) 예) φ 10 gcd 1,10 = 1, gcd 2,10 = 2, gcd 3,10 = 1 gcd 4,10 = 2, gcd 5,10 = 5, gcd 6,10 = 2 gcd 7,10 = 1, gcd 8,10 = 2, gcd 9,10 = 1 φ 10 = 4

24 오일러 정리 (Euler s Theorem) n Z, a Z n a φ n 1 (mod n) n Z, a Z n, a φ n +1 a (mod n) 예) 3 1 mod 15 φ 15 = (mod 15) (mod 15) : 곱셈상의 역원에 대한 정의와 동일 mod (mod 15)

25 소수의 개수 가장 큰 소수 : 6,320,430자리의 소수 (MSU) 소수의 개수는 무한 n보다 작은 소수의 개수 : f n [ n ln n ] < f n < [ n ln n ] n의 값이 커질수록, 그 수가 소수일 확률도 1 작아짐 1,000,000보다 적은 소수의 개수는? 72,383 < f 1,000,000 <78,543. 실제 78,498개의 소수 선택된 수 k 가 소수일 확률 P k is prime 1 ln( k) ln n 의 분포를 따라서

26 소수 판정(Primality Test) n 이 소수인가? 결정적 방법 에라토스테네스의 체(Sieve of Eratosthenes) n 1/2 보다 작은 모든 소수로 나눈다. 비효율적

27 소수 판정(Primality Test) n 이 소수인가? 비결정적 방법 Fermat 소수 판정, Miller-Rabin 소수 판정 composite 항상 true; prime true일 확률이 높음 n번 알고리즘을 수행하여 모두 소수라고 판정한 경우 1 1 k n 의 확률로 true

public key private key Encryption Algorithm Decryption Algorithm 1

public key private key Encryption Algorithm Decryption Algorithm 1 One-Way Function ( ) A function which is easy to compute in one direction, but difficult to invert - given x, y = f(x) is easy - given