[보안] 공개키(비대칭) 암호: Rabin, ElGamal, ECC

 공개키(비대칭) 암호 알고리즘에는 대표적으로 RSA가 있습니다. 하지만 이외에도 소인수 분해를 이용한 Rabin과 이산대수를 이용한 ElGamal 알고리즘, 타원곡선을 이용한 ECC 알고리즘이 있습니다. 이에 대해서 알아보겠습니다.

 

[ Contents ]

 

 

1. 소인수 분해를 이용한 비대칭(공개키) 암호 알고리즘

1) RSA

2023.05.16 - [CS] - [보안] RSA의 개념과 특징, 예제: 소수를 이용한 비대칭키(공개키) 암호화 기법

[보안] RSA의 개념과 특징, 예제: 소수를 이용한 비대칭키(공개키) 암호화 기법

 

 RSA는 공개키 암호 방식의 대표 알고리즘입니다. 소인수 분해의 높은 계산복잡도를 이용한 암호 알고리즘으로, 위 링크에서 자세하게 설명했습니다.

 

 

2) Rabin

n = p*q (단, p와 q는 소수)

 

 RSA보다 다소 단순합니다. 소인수 분해가 어려운 점을 착안해서, 단 1번의 곱셈 연산으로 암호화가 가능합니다.

 n은 공개키이고, p와 q는 각 통신자의 개인키입니다. RSA에서의 e와 d 지수가 2로 고정이며, 중국인의 나머지 정리를 이용해서 복호화합니다. 이때 복호화한 결과는 4가지로 나오지만, 1개로 추론하여 결정지을 수 있습니다.

 

 

 

2. 이산대수를 이용한 비대칭(공개키) 알고리즘

1) Diffie-Hellman(디피-헬만 알고리즘)

2023.05.12 - [CS] - [보안] 키 배송 문제와 해결방안: 사전 공유, 키 배포센터, Diffie-ellman 알고리즘, 공개키 암호

[보안] 키 배송 문제와 해결방안: 사전 공유, 키 배포센터, Diffie-ellman 알고리즘, 공개키 암호

 

 RSA만큼 Diffie-Hellman 알고리즘도 유명합니다. 대칭키 알고리즘의 경우, 암호화 키와 복호화 키가 동일하기 때문에 키 배송 문제가 있습니다. 이를 해결하기 위한 방법에는 여러가지가 있으며, 그중 하나가 공개키 방식인 'Diffie-Hellman' 알고리즘입니다.

 해당 알고리즘은 위 글에서 자세히 설명해두었으니, 참고하시기 바랍니다.

 

 

2) ElGamal 방식

 Diffie-Hellman 방식의 확장 버전으로, 이산대수에 근거해서 만든 암호 알고리즘입니다.

 복호화를 위해서는 이산 로그 방정식을 구해야하며, 상당한 계산량과 메모리가 필요해서 성능이 좋지 않습니다. 

 

 

 

3. 타원 곡선을 이용한 비대칭(공개키) 알고리즘

1) 타원 곡선 암호(ECC, Elliptic Curve Cryptosystem)

타원 곡선 그래프 (desmos.com 이용)

 위 타원곡선상의 점들 간 덧셈 연산을 통해 키를 산출합니다. RSA와 같이 소수를 이용한 비대칭 암호기법은 키의 길이가 너무 긴 단점이 있었고, ECC는 키의 길이가 짧아도 동일한 보안성을 제공합니다.

 고전적인 RSA, 디피 헬만 알고리즘보다 훨씬 강력하고 효율적인 보안 알고리즘으로 추대받고 있습니다.