기사공부(알기사, 비 대칭키 암호)

비대칭키

 

키 배송문제

- 대칭키를 사용하게 되면 키 배송문제가 발생한다.

키 배송문제 : 통신을 위해서는 키가 필요하지만 키를 보내게 되면 도청자가 도청 할 수도 있기 때문에 키를 안 보낼수도 보낼수도 없게 되는 문제

- 키 배송문제 해결 방법

1. 키의 사전에 공유

2. 키 배포센터 운영

3. Diffie-Hellman 키 교환

4. 공개키 암호

 

1. 키의 사전에 공유

- 키 사전 공유는 키 관리기관(TA)에서 사전에 두 사용자에게 비밀 경로를 통해 키를 전송

- 키 사전 공유는 TA도 필요하고 비밀통로가 필요하며 TA는 많은 사용자의 키를 관리 해야한다.

TA가 관리해야되는 키의 수 : n(n-1)/2 → 비용이 많이 든다.

 

2. 키 배포센터 운영

- 암호통신이 필요할 때 마다 키 배포센터(KDC)에게 의뢰해 개인과 키 배포 센터 사이에 키를 사전에 공유하는 방식

- n명의 인원이 있다면 n개의 키가 있으면 된다.

 

3. Diffie-Hellman의 키 교환

- 1976년 디피와 마틴 헬먼이 최초로 제안한 알고리즘

- 키를 교환하는 것이 아닌 공유키를 계산하여 만들어냄

- 통신을 위해 양쪽은 300자리 이상의 수 p,q를 선택한다.

- 키 교환의 안정성은 이산대수의 어려움을 기반으로 둔다.

- 절차

1. Alice는 임의의 큰 수 0<= x<=p-1 선택, R1 = gx mod p 인 R1을 선택

2. Bob은 임의의 큰 수 0<= y<=p-1 선택 R2 = gy mod p 인 R2를 선택

3. Alice는 Bob에게 R1을 Bob은 Alice에게 R2를 전송

4. Alice는 K = (R2)x mod p를 계산, Bob은 K = (R1)y mod p를 계산

5. 이렇게 구한 K를 통신에 사용할 대칭키로 사용한다.

K =(gx mod p)y mod p = (gy mod p)x mod p = gxy mod p

- Diffie-Hellman 공격

1. 서비스 공격

- Diffie-Hellman은 계산의 복잡성 때문에 비밀키 생성에서 큰 지연시간을 가진다.

이를 이용해 공격자가 키 생성요청을 동시에 다수요청하면 키 생성 부담으로 서버 마비를 일으키는 서비스 거부공격(DOS)를 일으킬 수 있다.

→ 쿠키 사용으로 방지 가능

2. 중간자 공격

- 키 교환 공격은 인증단계가 없어 중간자 공격에 취약

→전자서명, 공개키 인증서 등 인증을 통해 해결 가능

 

4. 공개키 암호로 해결

- 대칭키 암호는 암호화키 와 복호화키가 동일하였으나 공개키는 암호화키와 복호화키가 다르다.

- 암호화키를 공개키(공격자가 알아도 상관없음, 수신자가 생성), 복호화키를 비밀키(수신자가 생성)라 한다.

- 공개키는 대칭키에 비행 속도가 매우 느리다.

- 공개키 사용원칙

1. 암호화키와 복호화키는 같은 사람의 키 쌍이어야 한다.

2. 키는 암ㆍ복호화 중 한 번만 사용이 가능하다.

3. 타인의 개인키는 사용할 수 없다.

- 비대칭 알고리즘에 따른 종류

1. 소인수분해의 어려움 : Rabin, RSA

2. 이산대수의 어려움 : Elgama, ECC, DSA

RSA

- 공개키 알고리즘 중 하나이며 세계적인 표준

- 키의 안정성을 인수분해의 어려움으로 함

- SSL 프로토콜을 가진 웹 브라우저, PGP 등에서 많이 사용

- RSA 절차

1. 서로 다른 소수 p,q를고른다.

2. N = p*q인 N을 구한다.

3. π(N) = (p-1)*(q-1)인 π(N)을 구한다.

4. π(N)보다 작지만 π(N)과 소인수인 e를 구한다(e = 공개키)

5. e*d mod π(N) = 1인 d를 구한다.

6. 공개키 = {e,N}, 비밀키 = {d,N}

7. C = Pe mod N으로 C를 구할 수 있다.(P는 주어짐)(P = Cd mod N)

 

- RSA의 공격

1. 수학적 공격 - 키의 길이가 긴 걸 사용으로 해결가능

- 키 길이가 길어지면 처리속도 느려짐

2. 타이밍 공격 - 랜덤지체 공격으로 해결 가능

3. 선택암호문 공격 - OAEP로 해결

- OAEP

1. 평문 해시값과 정해진 개수의 ‘0’등으로 만들어진 인증정보를 평문 앞 추가하고 RSA 암호화

2. 인증정보가 올바르지 않으면 decryption error 메시지를 회신(어떤 에러인지는 구체적으로 알리지 않음)

3. RSA-OAEP는 난수를 이용하기 때문에 안정성을 높이고 있다.

- RSA 권장사항

1. N은 1024bit이상(309자리 이상 십진수)

2. 두 소수 p,q는 512bit 이상(154자리 이상 십진수)

3. p,q는 같지는 않지만 거의 같은 크기의 소수

4. (p-1),(q-1)은 커다란 소인수를 가져야 한다.

5. (p-1),(q-1)의 최대공약수는 작은 수여야 한다,

 

Rabin

- 인수분해의 어려움을 근거로 만든 시스템

- RSA의 공개키(N,e)에서 e대신에 b가 들어간 것

- 암호화는 매우 간단

- 성능이 낮은 플랫폼에서 잘 활용 될 수 있다,(ex) 스마트 카드)

- RSA만큼 안전하다고 할 수 있다.

 

ElGamal

- 이산대수의 어려움을 근거로 만든 시스템

- 디지털 서명, 키 교환, 암호화에서 사용될 수 있음.

- DH 알고리즘의 확장판

- 암호문의 길이는 평문의 길이의 약 2배가 된다.

- 암ㆍ복호화 속도가 제일 느리고 많은 메모리 공간이 필요하다.

- 키 교환, 인증, 짧은 메시지 암ㆍ복호화에 사용

 

ECC

- RSA, ElGamal은 안정성에 비해 속도가 매우 느리다는 단점을 가지고 있다.(키의 길이가 길기 때문에)

- ECC는 짧은 키 길이로 RSA, ElGamal과 동일한 수준의 보안성을 제공 할 수 있다.

→ ECC의 키 길이 160bit의 안정성 = RSA의 키 길이 1024bit의 안정성

- 이산대수의 어려움을 근거로 만든 시스템

- 1985년 코블리치와 밀러가 처음 제안

- 하드웨어, 소프트웨어에서 구현하기 용이 → 스마트카드, 무선 통신 단말기같은 메모리, 처리능력이 제한된 응용분야에서 많이 사용

ECC vs RSA

구분	ECC	RSA
기반구조	WPKI(무선)	PKI(유선)
속도	우수	느림
키 크기	적음	많음
사용 분야	소형 모바일 환경	인프라가 다소 구현된 환경

 

대칭키 vs 공개키

구분	대칭키	공개키
키의 상호관계	암호화키 = 복호화키	암호화키 != 복호화 키
안전 키 길이	128비트 이상	2048비트 이상
암호화 키	비밀	공개
복호화 키	비밀	비밀
비밀키 전송	필요	불 필요
키 개수	n(n-1)/2	2n
암호화 속도	빠름	느림
경제성	높다	낮다
제공 서비스	기밀성	기밀성, 인증, 부인방지
목적	데이터 암호화	대칭 키 교환
전자서명	복잡	간단
단점	키 교환 원리 x → 많은 키 필요	중간자 공격에 취약, 속도 느림
해당 알고리즘	DES,3DES,AES	RSA, Rabin, ElGamal,ECC

 

하이브리드 암호

- 공개키 암호의 장점과 대칭키 암호의 장점을 살릴 수 있도록 조합하는 방식

- 대칭키 암호로 파일 암호화(빠른 암호화 가능) + 대칭키 암호의 키 기밀성 지키기 위한 공개키 사용

- 하이브리드 암호에서는 의사난수 생성기, 대칭키 암호, 공개키 암호 기술이 사용

→ 의사난수 생성기 : 세션키 생성

대칭키 암호 : 메시지 암호화

공개키 암호 : 세션키 암호화

- PGP, SSL/TLS에서 많이 사용(PGP는 인증도 가능)