라빈 암호

라빈 암호(Rabin cryptosystem)는 마이클 O. 라빈(Michael O. Rabin)이 제안한 공개키 암호 방식으로, 합성수 법에서 제곱근을 구하는 문제가 정수 소인수분해 문제와 동등하게 어렵다는 성질을 이용한다.

개요

라빈 암호는 공개키를 이용해 평문을 제곱한 값을 암호문으로 만들고, 개인키인 두 소인수를 이용해 암호문에서 제곱근을 계산하여 복호화하는 공개키 암호 방식이다. 공개키는 두 큰 소수 p, q의 곱 n = pq이고, 개인키는 p와 q이다.

라빈은 1979년 MIT Laboratory for Computer Science 기술 보고서 〈Digitalized Signatures and Public-Key Functions as Intractable as Factorization〉에서 큰 합성수 n = pq를 사용하는 공개키 함수와 전자서명 방식을 제안했으며, 이 함수의 역산이 소인수분해와 동등하게 어렵다는 점을 보였다.

라빈 암호는 RSA와 마찬가지로 큰 합성수의 소인수분해 어려움에 기반하지만, 기본 라빈 함수는 역산 문제가 소인수분해와 계산적으로 동등함이 증명되어 있다는 점이 특징이다. 다만 복호화 결과가 일반적으로 네 개의 후보로 나오므로, 실제 암호 방식으로 사용하려면 올바른 평문을 식별하기 위한 패딩이나 중복 정보가 필요하다.

배경

공개키 암호는 암호화에 쓰는 키와 복호화에 쓰는 키를 분리하는 방식이다. 라빈 암호에서 누구나 알 수 있는 공개키는 n이고, 복호화에 필요한 개인키는 n의 소인수인 p, q이다.

라빈 암호의 핵심 난제는 다음 두 문제가 사실상 같은 어려움을 가진다는 데 있다.

문제	설명
소인수분해 문제	큰 합성수 n = pq에서 p, q를 찾는 문제
합성수 법의 제곱근 문제	c ≡ m² mod n이 주어졌을 때 m을 찾는 문제

p와 q를 알고 있으면 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)를 이용해 제곱근을 효율적으로 구할 수 있다. 반대로 임의의 제곱잉여에 대해 합성수 법의 제곱근을 효율적으로 구할 수 있다면 n을 소인수분해할 수 있다.

알고리즘

키 생성

라빈 암호의 기본 키 생성 절차는 다음과 같다.

1. 서로 다른 큰 소수 p, q를 선택한다.
2. n = pq를 계산한다.
3. 공개키를 n으로 둔다.
4. 개인키를 (p, q)로 둔다.

복호화를 단순하게 하기 위해 설명용 기본형에서는 보통 p ≡ 3 mod 4, q ≡ 3 mod 4인 소수를 선택한다. 이러한 합성수 n = pq는 블룸 정수(Blum integer)라고 부른다.

암호화

평문을 0 ≤ m < n인 정수로 표현한 뒤 다음과 같이 암호문을 계산한다.

c = m² mod n

여기서 m은 평문 정수, c는 암호문이다. 암호화는 모듈러 제곱 한 번으로 이루어지므로 계산이 단순하다.

복호화

개인키 p, q를 가진 수신자는 암호문 c에 대해 다음 값을 계산한다.

m_p = c^((p+1)/4) mod p
m_q = c^((q+1)/4) mod q

위 식은 p ≡ 3 mod 4, q ≡ 3 mod 4일 때 제곱근을 구하는 간단한 방법이다. 이후 중국인의 나머지 정리를 이용해 다음 조건을 만족하는 네 개의 해를 구한다.

x ≡  ±m_p mod p
x ≡  ±m_q mod q

일반적으로 이 네 후보 중 하나가 원래 평문이다. 따라서 실제 복호화에서는 평문에 미리 넣어 둔 구조, 태그, 패딩, 체크섬 등을 확인하여 올바른 후보를 선택해야 한다.

예시

작은 수를 사용한 교육용 예시는 다음과 같다. 실제 보안 용도에는 이 정도 크기의 수를 절대 사용할 수 없다.

p = 7, q = 11
n = pq = 77
평문 m = 20

암호화:
c = m² mod n
  = 20² mod 77
  = 400 mod 77
  = 15

복호화할 때 수신자는 p, q를 알고 있으므로 15의 제곱근을 77 법에서 구할 수 있다. 이 경우 가능한 평문 후보는 다음 네 개이다.

13, 20, 57, 64

네 값은 모두 제곱하면 15 mod 77이 된다. 즉 라빈 암호의 기본형에서는 하나의 암호문이 여러 평문 후보에 대응할 수 있으며, 이 모호성을 해결하는 장치가 필요하다.

RSA와의 비교

라빈 암호는 구조상 RSA와 비슷하지만 중요한 차이가 있다.

구분	라빈 암호	RSA
기본 연산	c = m² mod n	c = m^e mod n
공개 지수	사실상 e = 2에 해당	보통 65537 등 홀수 공개 지수 사용
보안 근거	기본 역산 문제가 소인수분해와 동등함이 증명됨	RSA 문제와 소인수분해의 동등성은 일반적으로 증명되어 있지 않음
복호화 결과	일반적으로 네 개 후보 발생	적절한 조건에서는 하나의 평문으로 복원
실용성	후보 선택과 패딩 설계가 까다로움	표준화된 패딩과 프로토콜이 널리 사용됨

라빈 암호의 이론적 장점은 수동 공격자가 암호문에서 평문을 복원하는 문제가 소인수분해와 동등하다는 점이다. 반면 기본형은 복호화 모호성과 선택 암호문 공격(chosen-ciphertext attack)에 취약하다는 문제가 있어, RSA처럼 널리 표준 암호 방식으로 사용되지는 않는다.

보안 특성

라빈 암호의 주요 보안 특성은 다음과 같다.

• 소인수분해와의 동등성: 기본 라빈 함수의 역산은 n의 소인수분해와 계산적으로 동등하다.
• 결정적 암호화: 같은 평문과 같은 공개키를 사용하면 항상 같은 암호문이 나온다. 따라서 원형 그대로는 현대적 의미의 의미론적 안전성(semantic security)을 제공하지 않는다.
• 복호화 모호성: 일반적으로 네 개의 제곱근 후보가 나오므로 올바른 평문 식별 절차가 필요하다.
• 선택 암호문 공격 취약성: 기본 라빈 암호에서 공격자가 복호화 장치에 조작한 암호문을 질의할 수 있으면 소인수분해 정보를 얻을 수 있다.

특히 선택 암호문 공격에서는 공격자가 임의의 m을 골라 c = m² mod n을 만들고 복호화 결과 중 ±m과 다른 제곱근을 얻으면, 두 제곱근의 차이와 n의 최대공약수를 계산하여 p 또는 q를 구할 수 있다. 이 때문에 기본 라빈 암호는 실제 프로토콜에 그대로 사용해서는 안 된다.

패딩과 변형

라빈 암호를 실제 암호화 방식으로 만들기 위해서는 평문 후보를 구별하고 공격을 막기 위한 인코딩 또는 패딩이 필요하다. 단순히 평문 뒤에 고정된 중복 비트를 붙이는 방식은 후보 식별에는 도움이 될 수 있지만, 보안 증명을 훼손하거나 새로운 공격면을 만들 수 있다. 따라서 라빈 암호의 안전한 사용에는 엄밀하게 설계된 패딩 방식이 필요하다.

대표적인 관련 변형과 응용은 다음과 같다.

항목	설명
라빈 서명	라빈이 원래 제안한 공개키 함수의 주요 응용 중 하나로, 제곱근 계산을 이용한 전자서명 방식이다.
라빈-윌리엄스 서명	라빈 서명의 모호성을 줄이고 구현 조건을 정리한 변형 서명 방식이다.
블룸-골드바서 암호	블룸 블룸 슈브(Blum Blum Shub) 생성기와 라빈 계열 아이디어를 사용하는 확률적 공개키 암호 방식이다.
라빈 기반 연구 변형	복호화 후보 식별, 효율성 개선, 특정 대수적 구조 확장 등을 목표로 여러 변형이 연구되었다.

2025년에는 고전적인 라빈 방식을 일반 수체(number field) 위로 확장하는 연구도 발표되었다. 이 연구는 적절히 선택된 모듈러스에서 무작위 평문의 복호화 문제가 정수 소인수분해 문제와 동등하게 어렵다는 성질을 보이는 등, 라빈 계열 암호가 주로 이론적·연구적 맥락에서 계속 다루어지고 있음을 보여준다.

활용과 한계

라빈 암호는 공개키 암호학에서 중요한 이론적 예제로 자주 다루어진다. 특히 소인수분해와 암호 해독의 동등성, 합성수 법의 제곱근 문제, 중국인의 나머지 정리의 응용을 설명하는 데 유용하다.

다만 실무에서는 다음과 같은 이유로 RSA, 타원 곡선 암호, 현대적인 하이브리드 암호 방식보다 덜 사용된다.

• 복호화 결과가 여러 개라서 메시지 인코딩이 필요하다.
• 기본형은 선택 암호문 공격에 취약하다.
• 안전한 패딩 설계가 단순하지 않다.
• 널리 채택된 상호운용 표준과 구현 생태계가 RSA나 ECC보다 제한적이다.

따라서 라빈 암호는 실무 배포용 알고리즘이라기보다 공개키 암호의 수학적 구조와 보안 증명을 설명하는 대표적 알고리즘으로 이해하는 것이 적절하다.

같이 보기

• 암호
• 암호화 알고리즘
• 암호 알고리즘 보안강도
• RSA 암호화
• 타원 곡선 암호