[KOR] RSA 키 생성 방법, Rabin, ElGamal, ECC
대칭키 암호의 문제 ==> 키 배송 문제(key distribution problem)
sol) 1. 키의 사전 공유에 의한 해결 (Trusted Authority 이용)
2. KDC - key distribution center에 의한 session key 전달 (대칭키 이용 전달)
3. Diffie - Hellman 키 생성에 의한 해결 (이산대수 문제로 세션키 생성)
3.1 DOS 공격 취약
3.2 man-in-the-middle attack
==> cookie 이용한 dos 사전 확인 차단 // authentication으로 해결
4. 공개키 암호에 의한 해결
💥공개키 암호 알고리즘(Public key encryption algorithm)
1. RSA (integer factorization problem, 소인수분해)
2. Rabin (integer factorization problem, 소인수분해)
3. ELGamal (discrete logarithms problem, 이산대수)
4.DSA (discrete logarithms problem, 이산대수)
5.ECC (discrete logarithms problem, 이산대수)
비대칭키 암호시스템은 암복호화를 수학적 함수를 사용하므로 속도는 대칭키에 비해 무척느리다. 또한 공개키 암호가 대칭키 암호에 비해 암호해독에 있어서 더욱 안전하다고 생각하지만, 그것은 키의 길이와 암호를 깨는데 필요한 계산량에 따라 달리지기 때문에, 단지 비대칭키가 관용암호에 비해 더 강하다고 말할 근거가 전혀 없음.
RSA
인수분해 문제(Prime Factorization)해결의 높은 난이도를 이용한 가장 대표적인 공개키 암호 알고리즘. Rivest-Shamir-Adleman(RSA)
C=P^e mod n
P = C^d mod n
(공개 : n, e)
(비공개 : d, p, q,f)
키생성
1. p,q 선택 (p<>q , p와 q는 소수)
2. N=p*q
3. f = (p-1)(q-1)
4. gcd(f,e) = 1 (여기서 e는 공개될 예정)
5. ed mod n = 1
공개키 = (e,n)
개인키 = (d,n)
키생성 예시를 들어보자
ex) p=5 , q=11
N= 5*11 = 55
f = (5-1)(11-1) = 40
gcd(40,e) = 1
e 후보자 => 1,3,7,,,,
(e=3 가정)
3d mod 40 = 1
3d= 41, 81, 121 ...
(3d=81가정)
d= 27
공개키 = (3,55)
개인키 = (27,55)
p,q = N
N의 크기
1. 1024 bit 사용 권장 x
2. 2048 bit 사용 (2030까지)
3. 4096 bit 사용 (2030이후)
plus
p-1와 q-1 커다란 소인수
p-1와 q-1의 최대공약수는 작은 수
p,q는 거의 같은 크기의 소수
RSA에 대한 공격
1) 소인수분해 공격(수학적 공격)
2) 타이밍 공격(시간 공격)
복호화 알고리즘의 실행 시간에 따라 달라진다.(Chosen ciphertext attack(CCA))
랜덤지체(random delay) 방법으로 막을 수 있다.
3. CCA + RSA OAEP
Chosen ciphertext attack(선택 암호문 공격)으로
공격자가 자신이 만든 위조 암호문을 서버에 여러 차례 보내고, 서버가 회신해 주는 오류 메시지나 타이밍을 해석해서 키나 평문 정보를 얻어가는것.
👏RSA OAEP (Optimal Asymmetric Encryption Padding)
복호화에서는 평문 해시값과 정해진 개수의 0 등으로 만들어진 인증정보를 평문 앞에 추가하고 RSA로 암호화한다. (일종의 패딩)
즉, RSA로 복호화한 후 올바른 인증 정보가 떠지지 않으면 원래 평문을 알던 사람이 아닌것으로 추정하고 Decryption error메시지 전달(오류에 대한 상세 설명 제한)
난수를 이용해서 암호문의 패딩을 다른 패턴이 되도록 하여 안전성을 높힘.
Rabin
소인수분해의 어려움으로 이용 (결정적 알고리즘은 아님)
성능낮은 플랫폼에서 활용
ex) 스마트 카드
p,q가 충분히 크기만 한다면 RSA와 동급으로 안전보장.
ELGamal
이산대수 문제에 근거
(이산대수를 구하는 고속 알고리즘은 아직 발견되지 않았음
이산대수는 키 교환 프로토콜의 하나인 diffie-hellman 키 교환방법을 사용)
디지털 서명(Digital Signature), 암호화, 키 교환에 사용될 수 있는 공개키 알고리즘.
ECC(Elliptic Curve Cryptosystem)
RSA, ELGamal 안전성은 높지만 그만큼 키의 크기와 계산량이 매우 높음.
키의 길이를 대폭 줄인 알고리즘 등장
타원곡선(elliptic curve)이론에 근거
(160bit ECC는 1024bit의 RSA키와 동일한 보안수준)
H/W, S/W 구현 용이
스마트카드, 무선통신 단말기와 같이 하드자원이 적은 응용분야에 특히 효율적.
Comments
Post a Comment