[현대 암호학] 06-7. 기타 공개키 암호 / 8. 공개 키 암호에 관한 Q&A

7. 기타 공개키 암호

 

ElGamal 방식

• ElGamal 방식은 Taher ElGamal에 의한 공개 키 알고리즘
• RSA는 소인수분해의 어려움을 이용
• ElGamal 방식은 이산대수를 구하는 것이 어렵다는 것을 이용
• ElGamal 방식 암호화에서는 암호문의 길이가 평문의 2배가 되어 버린다는 결점
• GPG(GnuPG)에서 사용

 

Rabin 방식

• Rabin 방식은 M.O. Rabin에 의한 공개 키 알고리즘
• Rabin 방식은 mod N으로 평방근을 구하는 것이 어렵다는 사실을 이용
• Rabin 방식 공개 키 암호의 해독은 소인수분해 정도로 어렵다는 것이 증명

 

 

타원곡선 암호

• 타원 곡선 암호(ECC, Elliptic Curve Cryptosystems)는 최근 주목받고 있는 공개 키 암호
• RSA에 비해 키의 비트 수가 적다.
• 타원 곡선 위에 곱셈을 정의하고, 이 곱셈의 역연산이 어렵다는 것을 이용

 

 

---

8. 공개 키 암호에 관한 Q&A

 

공개 키 암호의 기밀성

(질문) 공개 키 암호는 대칭 암호보다는 기밀성(Confidentiality)이 높은가?

(답) 이것 만으로는 답할 수 없다. 왜냐하면 키의 비트 길이에 따라 기밀성의 정도가 변화하기 때문

 

 

공개 키 암호와 대칭 암호의 키 길이

(질문) 1024비트 길이의 키를 갖는 공개 키 암호와, 128비트 길이의 키를 갖는 대칭 암호에서는 비트 길이가 긴 공개 키 암호쪽이 안전한가?

(답) 아니다. 공개 키 암호의 키 길이와, 대칭 암호의 키 길이는 직접 비교할 수 없다.

 

 

[참고] 전사 공격에 대한 같은 강도를 갖는 키 길이 비교

 

--------------------------------------------------------------

대칭 암호의 키 길이       공개 키 암호의 키 길이

-------------------------------------------------------------

128비트                       2304비트

112비트                       1792비트

80비트                         768비트

64비트                         512비트

56비트                         384비트

---------------------------------------------------------------

 

 

[참고] 암호키 사용 유효기간

 

키 종류		사용 유효기간
		송신자 사용기간	수신자 사용기간
대칭키 암호 알고리즘	비밀키	최대 2년	최대 5년
공개키 암호 알고리즘	암호화 공개키	최대 2년
	복호화 공개키	최대 2년
	검증용 공개키	최대 2년
	서명용 공개키	최대 2년

 

 

[참고] 보안 강도별 암호 알고리즘 비교

 

보안강도	대칭키암호 알고리즘 (보안강도)	해시함수 (보안강도)	공개키 암호 알고리즘
			인수분해 (비트)	이산대수		타원곡선 암호(비트)
				공개키 (비트)	개인키 (비트)
112비트	112	112	2048	2048	224	224
128비트	128	128	3072	3072	256	256
192비트	192	192	7680	7680	384	384
256비트	256	256	15360	15360	512	512

 

 

 

대칭 암호의 미래

(질문) 공개 키 암호가 생겼기 때문에 앞으로 대칭 암호는 사용할 필요가 없는가?

(답) 아니다.

• 일반적으로 같은 정도의 기밀성을 갖는 키 길이의 경우, 공개 키 암호는 대칭 암호보다도 몇 백배나 느리다.
• 공개키 암호는 긴 메시지를 암호화하기에는 적합하지 않다.
• 목적에 따라 대칭 암호와 공개키 암호 두 가지 모두 사용

 

 

RSA와 소수

(질문) RSA의 키 쌍을 모두가 자꾸 만들어 가면 그 사이 소수가 없어져 버리는 것은 아닐까?

(답) 그럴 염려는 없다.

• 512비트로 표현할 수 있는 소수의 수는 대략 10150으로 전 우주에 존재하는 원자의 개수보다도 많은 수이다.

 

 

RSA와 소인수 분해

(질문) RSA로 암호화할 때 큰 수를 소인수분해 할 필요가 있는 것일까?

(답) 아니다.

• RSA의 암호화에서도, 복호화에서도 그리고 키 쌍의 생성에서도 큰 수를 소인수분해를 할 필요는 없다.

 

 

(질문) RSA를 해독하는 것은 큰 수를 소인수분해 하는 것과 같은 것인가?

(답) 같은 것인지 아닌지 아직 모름

• 분명히 소인수분해를 고속으로 할 수 있다면 RSA는 해독된다.
• RSA를 해독하려면 소인수분해를 꼭 해야 한다는 것이 증명된 것은 아님
• 어쩌면 소인수분해를 하지 않아도 해독할 수 있는 방법이 발견될지도 모름

 

RSA의 비트 길이

(질문) 소인수분해 되지 않기 위해서 N은 몇 비트 길이가 필요한가?

(답) 아무리 비트 수가 커도 언젠가는 소인수분해 된다.

 

 

제 06장 요점 정리

비대칭 암호
공개 키 암호: RSA, Rabin, ElGamal, ECC
공개 키 서명: RSA(PKCS#1 v1.5, PKCS#1 PSS), DSA, ECDSA, EdDSA/Ed25519

키 배송 문제 해결
키의 사전 공유에 의한 해결
키 배포 센터에 의한 해결
Diffie-Hellman 키 교환
공개 키 암호에 의한 해결

RSA 암호화, 복호화
C = P^E mod N (E, N) 공개 키
P = C^D mod N (D, N) 개인 키

RSA-OAEP(Optimal Asymmetric Encryption Padding)
ECC(Elliptic Curve Cryptosystems)