기사공부(알기사, 비 대칭키 암호)
비대칭키
키 배송문제
- 대칭키를 사용하게 되면 키 배송문제가 발생한다.
키 배송문제 : 통신을 위해서는 키가 필요하지만 키를 보내게 되면 도청자가 도청 할 수도 있기 때문에 키를 안 보낼수도 보낼수도 없게 되는 문제
- 키 배송문제 해결 방법
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는 인증도 가능)