공개키 암호 방식

공개키암호방식 Korea College of Information & Technology

수업내용 공개키암호방식의개요 RSA 암호방식 RSA 암호방식의안전성 RSA 암호방식의해독 RSA 암호방식의반복법에의한공격 ElGamal 암호방식 이산대수문제 ElGamal 암호방식 Merkle-Hellman 의 Knapsack 암호방식 Merkle-Hellman I 형 Knapsack 암호방식 Merkle-Hellman II 형 Knapsack 암호방식 Questions & Answers Korea College of Information & Technology 2

공개키암호방식의개요 Korea College of Information & Technology

공개키암호방식의등장배경 기존의관용암호방식에서발생하는문제점 키관리, 키분배 관용암호방식키개수 Xab A Xae B Xbc Xac Xbe Xad E n(n-1) / 2 Xbd Xce Xde Xcd 사용자수 (n) C D Korea College of Information & Technology 4

공개키암호방식의개요 "New directions in cryptography 1976 년 Diffie,Hellman, 공개키암호방식이론발표 기존의관용암호방식에서발생하는키관리문제점을해결한암호방식을제안 공개키암호방식 키를두개로나누어하나는암호화키로또다른하나는복호화키로사용한다. 암호화키는공개목록에등록공개하고복호화키는개인이비밀리에보관한다. 그러므로암호화키는공개키 (public key), 복호화키는개인키 (private key) 라부른다. 키의사전분배가필요없는획기적인방식 Korea College of Information & Technology 5

공개키암호방식의개요 대칭키암호알고리즘 공개키암호방식 사용된키가동일하다. 사용된키가동일하지않다. 암호화 복호화 사용된키가동일한가? 암호화키 복호화키 평문 암호알고리즘 암호문 암호문 복호알고리즘 평문 Korea College of Information & Technology 6

공개키암호방식의개요 키구조 Korea College of Information & Technology 7

사용자수와키의개수 대칭키암호방식 비대칭키암호방식 Xa Xab A Xae A Ya B Xbc Xac Xbd Xbe Xad Xce Xde E Xb B Yb Yc 개키 Repository Yd Ye E Xe Xcd Xc Xd C D C D Korea College of Information & Technology 8

사용자수와키의개수 키개수 관용암호방식 개키암호방식 2n 사용자수가 10,000 명이면 관용암호방식 : 49,995,500 개의키필요 공개키암호방식 : 20,000 개의키필요 n(n-1) / 2 사용자수 (n) Korea College of Information & Technology 9

공개키암호방식의개요 공개키암호방식구조 Korea College of Information & Technology 10

알고리즘성능차이 대칭키알고리즘 vs 공개키알고리즘성능차이 동일강도를갖는대칭키암호알고리즘과공개키암호알고리즘에사용되는키길이비교 대칭키암호알고리즘용키길이 공개키암호알고리즘용키길이 56 bits 384 bits 64 bits 512 bits 80 bits 768 bits 112 bits 1,792 bits 128 bits 2,304 bits Korea College of Information & Technology 11

관용암호방식과공개키암호방식비교 구분 관용암호방식 공개키암호방식 History BC 500년경 1976년 키 대칭키 ( 비밀키 ) 비대칭키 ( 공개키, 사설키 ) 암호키관계 암호화키 = 복호화키 암호화키 복호화키 암호화키 비밀 공개 복호화키 비밀 비밀 암호알고리즘 비밀 / 공개 공개 키의개수 N * (N-1) / 2 2 * N 장점 계산속도빠름 알고리즘이다양 암호키사전공유불필요 통신대상의추가가용이 단점키분배및관리의어려움계산속도느림 대표적인예 DES RSA Korea College of Information & Technology 12

공개키쌍사용원칙 원칙 1 암호화와복호화에사용되는키는동일인의키여야한다. 원칙 2 사용되는키쌍의각키는암호화 / 복호화과정중한번씩만사용해야한다. 원칙 3 상대방의사설키는사용할수없다. 암호화키 복호화키 위반규칙 송신자사설키 송신자사설키 (2) 송신자사설키 송신자공개키 인증모드 송신자사설키 수신자사설키 (1) 송신자사설키 수신자공개키 (1) 송신자공개키 송신자사설키 (3) 송신자공개키 송신자공개키 (2) 송신자공개키 수신자사설키 (1) 송신자공개키 수신자공개키 (1) 수신자사설키 송신자사설키 (1) 수신자사설키 송신자공개키 (1) 수신자사설키 수신자사설키 (2) 수신자사설키 수신자공개키 (3) 수신자공개키 송신자사설키 (1) 수신자공개키송신자공개키 (1) 수신자공개키수신자사설키암호모드 수신자공개키수신자공개키 (2) Korea College of Information & Technology 13

암호모드 평문을상대방의공개키 (public key) 로암호화하여암호문생성 암호화에사용된공개키와쌍을이루는사설키소유자가복호화가능 송신자 수신자의공개키로암호화 수신자 수신자의사설키로복호화 수신자의공개키 송신자는공개키 Repository( 리파지토리, 저장소 ) 에서가져옴 Korea College of Information & Technology 14

암호모드 < 송신자 > < 수신자 > Plaintext 평문 Plaintext 평문 < 수신자공개키 > < 수신자사설키 > Algorithm (Encryption) 암호알고리즘 Insecure Channel 공중매체 (ex. 인터넷 ) Algorithm (Decryption) 복호알고리즘 Ciphertext 암호문 Ciphertext 암호문 Korea College of Information & Technology 15

인증모드 평문을본인의사설키 (private key) 로암호화하여암호문생성 암호문은누구라도해독할수있음. 그에따라기밀성이유지될수는없지만, 어떠한수취인도그메시지가 A 에의해서생성되었음을확신가능 송신자 송신자의사설키로암호화 = 독점적암호화 수신자 송신자의공개키로복호화함 송신자의공개키 수신자는공개키저장소에서가져옴 Korea College of Information & Technology 16

인증모드 < 송신자 > < 수신자 > Plaintext 평문 Plaintext 평문 < 송신자사설키 > < 송신자공개키 > Algorithm (Encryption) 암호알고리즘 Insecure Channel 공중매체 (ex. 인터넷 ) Algorithm (Decryption) 복호알고리즘 Ciphertext 암호문 Ciphertext 암호문 Korea College of Information & Technology 17

암호모드 + 인증모드 인증먼저, 암호그이후 디지털서명 Korea College of Information & Technology 18

암호모드 + 인증모드 < 송신자 > < 수신자 > Plaintext 평문 < 송신자사설키 > 공개키 Repository ( 리파지토리, 저장소 ) < 송신자공개키 > Plaintext 평문 Algorithm (Encryption) 암호알고리즘 Algorithm (Decryption) 복호알고리즘 Ciphertext 암호문 Ciphertext 암호문 < 수신자공개키 > < 수신자사설키 > Algorithm (Encryption) 암호알고리즘 Insecure Channel 공중매체 (ex. 인터넷 ) Algorithm (Encryption) 암호알고리즘 Ciphertext2 암호문 2 Ciphertext2 암호문 2 Korea College of Information & Technology 19

공개키암호방식의수학적분류 소인수분해에기초한공개키암호방식 RSA( Rivest, A.Shamir, L.Adleman ) Rabin 이산대수문제에기초한공개키암호방식 ECC(Elliptic Curve Cryptosystem) ElGamal Knapsack 문제에기초한공개키암호방식 MH 공개키암호방식 Korea College of Information & Technology 20

RSA 암호방식 RSA 암호방식의안전성 RSA 암호방식의해독 RSA 암호방식의반복법에의한공격 Korea College of Information & Technology

RSA 암호방식의개요 1978 년 MIT 의 Rivest, Shamir 와 Adleman 이 RSA 공개키암호방식을제안 Korea College of Information & Technology 22

RSA 암호방식의개요 Operating systems. Sun, Microsoft, Apple, Novell. Hardware. Cell phones, ATM machines, wireless Ethernet cards, Mondex smart cards, Palm Pilots, Palladium. Secure Internet communication. Browsers, S/MIME, SSL, S/WAN, PGP, Microsoft Outlook, etc. Korea College of Information & Technology 23

RSA 암호방식의개요 합성수의소인수분해의어려움을이용하여 RSA 암호방식을실현함 가입자는백자리크기이상의두개의소수 p, q 를선택하여 n = p x q 를계산한다. 이때 p 와 q 를알고있는사람은 n 을계산하기쉽지만 n 만알고있는사람은 n 으로부터 p 와 q 를찾는소인수분해가어렵다 Korea College of Information & Technology 24

RSA Key Generation RSA key generation. Select two large prime numbers p and q at random. Compute n = pq. Euler 함수값 φ(n) = (p 1) (q 1) 계산 φ(n) 과서로소인 Ke 를선택한다. gcd (Ke, φ (n)) = 1 인 Ke 선택 다시유클리드호제법을이용하여 Kd 를계산 Ke Kd 1 mod φ (n) Ke 와 n 은공개목록에등록하여공개 (Ke, n) : 공개키 Kd 는비밀리에보관 (Kd, n) : 개인키 Korea College of Information & Technology 25

RSA 암호방식 암호화및복호화 ( 그림 5.2) Korea College of Information & Technology 26

RSA 암호방식 암호화 C M Ke mod n 복호화 M C Kd mod n Korea College of Information & Technology 27

Korea College of Information & Technology 28 RSA 암호방식의복호화과정 공개키 (Ke) 와개인키 (Kd) 는 modφ(n) 상에서서로역수관계이므로 Ke Kd 1 mod φ(n) 임의의 t 에대해서 암호문이므로 1 ) ( t n K K d e n M M n M n M C t n t n K K K d e d mod mod mod ) ( ) ( 1 ) ( n M C e K mod n M n M n M M t t n mod mod 1 mod ) ( ) (

RSA 암호방식의예 예 공개키 ( 3, 33 ) 개인키 ( 7 ) Korea College of Information & Technology 29

예제 소수 p=47, q=59 로 RSA 공개키암호를구성해보자 예제 5.1 Korea College of Information & Technology 30

RSA 암호방식의안전성 RSA 암호방식의안전성은소수 p 와 q 에달려있음 n = p q 계산 p, q : 소수 공개키 Ke 와 n 을가지고간단하게개인키 Kd 를찾을수있다면 RSA 암호방식은쉽게해독된다. φ(n) = (p 1) (q 1) gcd (Ke, φ (n)) = 1 인 Ke 선택 Ke Kd 1 mod φ (n) n 으로부터 p, q 를찾을수있다면, 즉 n 의소인수분해가가능하면 Euler 함수 φ(n) 을찾게되어유클리드호제법으로공개키 Ke 로부터개인키 Kd 를간단하게찾아낼수있다. Korea College of Information & Technology 31

RSA 암호방식의안전성 RSA 암호방식의안전성을보장받기위한소수 p 와 q 의선택조건과공개키 Ke 와개인키 Kd 의조건들이부가적으로필요함 소수 p 와 q 는다음조건을만족해야 RSA 암호방식이안전하다. 조건 1. p 와 q 는거의같은크기의소수이어야한다. 조건 2. p-1 과 q-1 은큰소수를인수로가져야한다. 조건 3. p-1 과 q-1 의최대공약수는작아야한다. 위의조건은 n=pxq 의소인수분해를어렵게함 Korea College of Information & Technology 32

RSA 암호방식의안전성 소수 p 와 q 의크기가 100 자리이고 n 이 200 자리인합성수라면 현재의소인수분해알고리즘과정보공학기술로는이러한 n 을소인수분해하는것은거의불가능한것으로알려져있음 RSA 암호방식을상용화한장비들은 512 비트의 n, 약 155 자리수를사용하거나 664 비트, 1024 비트의 n 을사용한다. Korea College of Information & Technology 33

RSA 암호방식의해독 암호해독자가 RSA 암호방식의 φ(n) 을안다면, n 이 p x q 이므로다음과같이소인수분해가능함 n p q ( n) ( p 1)( q 1) q=n/p 를대입하면다음과같이미지수 p 의 2 차방정식을얻을수있음 p 2 ( n ( n) 1) p n 위방정식의두개의근 p 와 q 를구하면해독됨 0 Korea College of Information & Technology 34

예제 암호해독자가 n=2419 와 φ(n)=2320 을알고있을때, 이정보로부터 n=pxq 의 p,q 구하기 Korea College of Information & Technology 35 http://www.papertablet.com/main/1314

RSA 암호방식의반복법에의한공격 공개키 Ke 와암호문 C 만을갖고평문을찾는방법 암호문 C 와 n, 공개키 Ke 만갖고, 소인수분해를통하여 p, q 를찾는것보다훨씬짧은시간내에평문 M 을구할수있음. 암호문 C 를공개키 Ke 로반복암호화하는방법 암호문 C 를공개키 Ke 로반복암호화하면다시암호문 C 가나타난다. 그러면다시암호문 C 가나타나기전의값이평문 M 이된다. Korea College of Information & Technology 36

예제 p=11, q=3 으로구성되는작은 n 값의 RSA 암호방식에서의반복암호화공격을해보자. 예제 5.3 Korea College of Information & Technology 37

참고사이트 RSA, Wikipedia http://en.wikipedia.org/wiki/rsa RSA 암호, 위키백과 http://ko.wikipedia.org/wiki/rsa_%ec%95%94%ed% 98%B8 Lecture 22: Cryptology http://www.cs.princeton.edu/courses/archive/spr05/co s126/lectures/22.pdf Korea College of Information & Technology 38

ElGamal 암호방식 이산대수문제 ElGamal 암호방식 Korea College of Information & Technology

ElGamal 암호방식의개요 이산대수문제를근간으로만들어진공개키암호방식 Korea College of Information & Technology 40

이산대수문제 큰소수 p로만들어진집합 Zp 위에서의원시원소 를 g라할때 g x y mod p 의 g와 y값을알고있 어도 log y x mod p g 을구하는것이어렵다는문제를이용 물론, g 와 x 를알면 y 를계산하는것은간단하다. Korea College of Information & Technology 41

이산대수문제 이산대수를만드는 Zp 위의원시원소의수는 φ(p-1) 개 원시원소 g 를차례로누승을증가시켜가면 0 을제외한 Zp 의모든원소가나타난다. Korea College of Information & Technology 42

이산대수문제 예 ) Z 23 의원시원소를알아보자 Z 23 위의원시원소의개수는 φ(22) 개이고 φ(22) = φ(2)xφ(11) = 1 x 10 = 10 이므로 Z 23 위의원시원소의개수는 10 개이다. Z 23 의원시원소 ={5,7,10,11,14,15,17,19,20,21} 원시원소하나를선택 (5) 하여 p-1(22) 과서로소인수 i 로누승하면모든원시원소를찾을수있다. 참고 )Fermat 의소정리 a p-1 =1(mod p) a 22 =1(mod p) Korea College of Information & Technology 43

이산대수문제 Zp 위에서의이산대수값을구하는방법은앞에서와같이대수표를만들어구하는것이제일간단하지만 p 값이크면대수표를만드는것이복잡하므로이산대수값을구하는것이어렵다. g x y mod p 의 g와 y값을알고있어도 x를구하는것이어렵다는문제를이용한암호화방법이이산대수문제를이용한암호화방법이다. Korea College of Information & Technology 44

ElGamal algorithm ElGamal encryption consists of three components the key generator the encryption algorithm the decryption algorithm Korea College of Information & Technology 45

ElGamal Key generation 큰소수 p 를선정하여 Zp 위의원시원소 g 와함께 p 를공개한다. 가입자 A는 Zp위의임의의원소 X A 를비밀정보로선택하여 X A 의공개정보 Y A 를계산 y g p 가입자 B도 Zp위의임의의원소 X B 를비밀정보로선택하 X 여 B 의공개정보 Y B 를계산 y A B g mod mod p 가입자 A 와가입자 B 의 Y A, Y B, p, g 를공개목록에등록 Y A 가입자 A 의공개키, Y B 가입자 B 의공개키 X A 가입자 A 의개인키, X B 가입자 B 의개인키 Korea College of Information & Technology 46

ElGamal encryption algorithm 가입자 A 가평문 M 을암호화하여암호문 C 를가입자 B 에게전송 암호화 Zp 상에서임의의난수 r 을선정 수신자 B 의공개키 YB 로 K 값을계산 C1, C2 계산 암호문 C 는 (C1, C2) r K C C 1 2 R C Z p y g KM mod p( M (C, ( p : 소수) r B r 1 mod p mod p C 2 ) : 평문) Korea College of Information & Technology 47

ElGamal decryption algorithm 가입자 B 가가입자 A 로부터수신받은암호문 C 를평문 M 으로복호화 암호문 C1 에가입자자신의개인키 X B 를누승하여 K 값을계산 평문 M 을계산 K K K K M y C r B ( g ( g C X 1 2 X r mod B ) B / ) X r B mod K p로부터 mod mod p mod p p p [ y [ C 1 [ C B 2 g g r X B KM mod mod p] mod p] p] Korea College of Information & Technology 48

ElGamal 암호방식 ElGamal 암호방식의구성 ( 그림 5.3) Korea College of Information & Technology 49

예제 소수 p=23, 원시원소 g=7 일때 ElGamal 암호방식을구성해보자. Korea College of Information & Technology 50

참고사이트 ElGamal encryption, Wikipedia http://en.wikipedia.org/wiki/elgamal_encryption Korea College of Information & Technology 51

Merkle-Hellman 의 Knapsack 암호방식 Merkle-Hellman I 형 Knapsack 암호방식 Merkle-Hellman II 형 Knapsack 암호방식 Korea College of Information & Technology

Knapsack 암호방식의개요 Merkle-Hellman 의 Knapsack 암호방식은 1978 년처음제안 1980 년대초반변형된모든 Knapsack 암호방식이모두해독됨 현재, Knapsack 암호방식은암호방식개념이해와기초적인암호기술연구에유용하게사용됨 Korea College of Information & Technology 53

Knapsack 문제 어떤집합 I = {s1, s2,, sn} 의부분집합을구하는문제 평문 M = m1, m2,, mn( 단 mi=0 또는 1) 일때 n i 1 m s T T 를구하는문제 i i Korea College of Information & Technology 54

Knapsack 암호방식 Knapsack 문제 Korea College of Information & Technology 55

Knapsack 암호방식 Knapsack 문제 ( 계속 ) Korea College of Information & Technology 56

Knapsack 암호방식 Korea College of Information & Technology 57

Knapsack 암호방식 암호화 Korea College of Information & Technology 58

Knapsack 암호방식 복호화 Korea College of Information & Technology 59

참고사이트 Merkle-Hellman http://en.wikipedia.org/wiki/merkle-hellman Knapsack problem, Wikipedia http://en.wikipedia.org/wiki/knapsack_problem Korea College of Information & Technology 60

Questions & Answers Korea College of Information & Technology 61