RSA 알고리즘 원리

"New Directions in Cryptography" 논문과 RSA 알고리즘

 

그 당시 업계를 뒤집어 놓을 정도의 제목부터가 남달랐던 논문,  

 

1976년, 휘트필드 디피(Whitfield Diffie)와 마틴 헬만(Martin Hellman)은 "New Directions in Cryptography" 논문을 발표하며 공개 키 암호(public key cryptography) 개념을 처음 제안했습니다. 이 논문은 기존의 대칭 키 암호 방식(예: DES)과는 달리, 암호화와 복호화에 서로 다른 키를 사용하는 방식을 제안하며 암호학에 혁신적인 변화를 가져왔습니다.

 

이 논문에서 직접적으로 RSA(Rivest-Shamir-Adleman) 알고리즘을 언급하지는 않지만, RSA 알고리즘이 등장할 수 있는 이론적 토대를 제공했습니다. 즉, 공개 키 암호 방식이 필요하다는 아이디어를 제시한 것이고, 이후 1977년 로널드 리베스트(Ronald Rivest), 아디 샤미르(Adi Shamir), 레오나드 애들먼(Leonard Adleman)이 이 개념을 구체적으로 수학적으로 구현하여 RSA 알고리즘을 개발한 것입니다. 이름을 보면 알겠지만 세사람의 이름의 글자를 따서 알고리즘 이름이 생겨난 것으로, 외국에도 이름을 널리 알리는 중요한 일인가 보네요.

---

RSA 알고리즘

1. 공개 키 개념의 도입
   • "New Directions in Cryptography" 논문에서 제안한 가장 중요한 개념은 공개 키 암호 시스템입니다.
   • 이 논문에서는 비밀 키를 공유하지 않고도 안전한 통신이 가능해야 한다는 점을 강조했습니다.
   • RSA는 이러한 개념을 기반으로 두 개의 키(공개 키, 개인 키)를 이용한 암호화/복호화 방식을 개발했습니다.
2. 대칭 키 암호 방식의 한계 극복
   • 기존의 대칭 키 암호 방식(예: AES, DES)은 송신자와 수신자가 동일한 키를 공유해야 하는 문제가 있었습니다.
   • 키를 안전하게 교환하는 것이 어렵기 때문에, 공개 키 기반의 새로운 암호 방식이 필요했습니다.
   • RSA는 공개 키를 이용한 암호화를 통해 이 문제를 해결했습니다.
3. 수학적 난제 활용
   • 디피-헬만 키 교환 방식(논문에서 제안된 개념)은 이산 로그 문제를 기반으로 합니다.
   • 반면, RSA는 큰 소수의 곱셈을 이용한 수학적 난제(정수 분해 문제)를 기반으로 합니다.
   • 즉, 공개 키 암호 개념은 동일하지만, RSA는 다른 수학적 원리를 적용하여 구현되었습니다.
4. 디지털 서명과 인증 기술 발전
   • 공개 키 암호 방식이 등장하면서 디지털 서명(digital signature) 개념이 발전했습니다.
   • RSA는 이를 활용하여 전자 서명 및 인증 시스템을 구현할 수 있는 암호화 기법을 제공합니다.
   • 예를 들어, 사용자가 메시지를 전송할 때 RSA 개인 키로 서명하면, 수신자는 공개 키로 이를 검증할 수 있습니다.

---

예시를 통한 설명

기존 대칭 키 방식의 문제점

A(송신자)와 B(수신자)가 서로 메시지를 주고받고 싶다.

1. A가 B에게 메시지를 보낼 때, 암호화를 하려면 공통된 비밀 키(예: K)를 공유해야 한다.
2. 하지만 이 키를 어떻게 안전하게 공유할 것인가?
3. 만약 제3자(공격자 C)가 키를 가로채면, 암호화가 무의미해진다.
4. 이런 문제를 해결하기 위해 공개 키 암호 방식이 필요했다.

---

공개 키 암호(RSA) 방식 적용

1. B(수신자)는 공개 키(Public Key)와 개인 키(Private Key)를 생성한다.
2. 공개 키를 A(송신자)에게 전달하고, A는 이 키로 메시지를 암호화한다.
3. A가 암호화한 메시지는 B의 개인 키 없이 해독할 수 없다.
4. 따라서 공격자가 중간에서 메시지를 가로채더라도, 개인 키 없이는 내용을 알 수 없다.

이 방식은 "New Directions in Cryptography" 논문에서 제안한 공개 키 개념이 없었다면 등장할 수 없었습니다. 즉, RSA는 이 논문의 아이디어를 기반으로 실제 사용 가능한 암호 시스템으로 발전한 것입니다.

---

결론

"New Directions in Cryptography" 논문은 공개 키 암호 개념을 제안, RSA는 이를 실현한 대표적인 알고리즘입니다.

• 논문은 공개 키 기반 암호 시스템의 필요성과 개념을 설명했고,
• RSA는 이를 수학적으로 구현하여 실제 암호화 시스템으로 발전시켰습니다.

만약 이 논문이 없었다면, RSA 같은 비대칭 암호 알고리즘이 등장하기 어려웠을 것입니다. RSA뿐만 아니라, ECDSA, ElGamal 암호, 디지털 서명 등 현대 암호 기술도 이 논문의 영향을 받았습니다.