라빈 암호체계

1. 개요

라빈 암호체계는 1978년 마이클 O. 라빈에 의해 처음 발표된 트랩도어 함수를 기반으로 하는 공개 키 암호 시스템이다. 이 시스템은 소인수 분해 문제의 어려움에 기반하여 암호화와 디지털 서명에 사용되며, 키 생성, 암호화, 복호화의 세 가지 알고리즘으로 구성된다. 라빈 암호는 효율적인 암호화 속도를 가지지만, 복호화 과정에서 여러 개의 가능한 평문이 생성될 수 있으며, 선택 평문 공격 및 선택 암호문 공격에 취약하다는 특징이 있다. 또한, 전자 서명 알고리즘으로도 활용될 수 있으며, 서명 생성 및 검증 과정을 통해 메시지의 무결성을 보장한다.

2. 역사

마이클 O. 라빈은 1978년에 라빈 서명 방식의 일부로 라빈 트랩도어 함수를 처음 발표하였다. 라빈 서명 방식은 서명을 위조하는 것이 소인수 분해만큼 어렵다는 것을 증명할 수 있는 최초의 디지털 서명 방식이었다.

이 트랩도어 함수는 이후 교과서에서 공개 키 암호화 방식의 예로 재사용되었으며, 라빈이 암호화 방식으로 발표한 적은 없지만, 라빈 암호 시스템으로 알려지게 되었다.

3. 절차

라빈 암호체계는 키 생성, 암호화, 복호화의 세 단계로 이루어진다.

* 키 생성: 공개 키와 개인 키를 생성한다. 공개 키는 모두에게 공개되고, 개인 키는 메시지 수신자만 알고 있다.
* 암호화: 평문을 공개 키를 사용하여 암호문으로 변환한다.
* 복호화: 암호문을 개인 키를 사용하여 원래의 평문으로 복원한다.

3.1. 키 생성(Key generation)

앨리스는 매우 크며 서로 다른 두 소수 p와 q를 선택한다. 계산 편의를 위해 p ≡ q ≡ 3 (mod 4)를 만족하는 소수를 사용해도 좋다. (이러한 수를 블럼 수라고 한다.) n = pq를 계산하여 밥에게 공개한다. n은 공개 키, p와 q는 앨리스의 개인 키이다.

라빈 암호체계의 키 생성 과정은 다음과 같다.

3.2. 암호화(Encryption)

밥은 앨리스에게 보낼 평문 m을 선택한다. 이때 m은 1부터 n-1 사이의 값이다. 밥은 암호문 $c\; =\; m^2\; \backslash pmod\{n\}$을 계산하여 앨리스에게 전송한다.

예시로, $p\; =\; 7$ 및 $q\; =\; 11$을 사용하면 $n=77$이 된다. 평문으로 $m\; =\; 20$을 선택하면, 암호문은 다음과 같이 계산된다.

:$c\; =\; m^2\; \backslash bmod\{n\}\; =\; 400\; \backslash bmod\{77\}\; =\; 15$.

메시지 M은 가역적인 매핑을 사용하여 숫자 m ()으로 변환된 후, $c\; =\; m^2\; \backslash bmod\{n\}$을 계산하여 암호화할 수 있다. 이렇게 계산된 c가 암호문이 된다.

평문을 x라고 할 때, 암호화는 다음과 같이 수행될 수도 있다.

:$e(x)\; =\; x(x\; +\; B)\backslash \; \backslash bmod\; \backslash \; n$

3.3. 복호화(Decryption)

앨리스는 암호문 c와 개인 키 (p, q)를 이용하여 평문 m을 복원한다.

먼저, m_p = √c (mod p), m_q = √c (mod q)를 계산한다. 그리고 p * y_p + q * y_q = 1을 만족하는 y_p, y_q를 확장 유클리드 알고리즘을 이용해 찾는다.

중국인의 나머지 정리를 이용하여 다음 네 개의 근을 구한다.
* r₁ = (y_p * p * m_q + y_q * q * m_p) mod n
* r₂ = n - r₁
* r₃ = (y_p * p * m_q - y_q * q * m_p) mod n
* r₄ = n - r₃

이 네 개의 근 중 하나가 원래의 평문 m이다.

만약 $p\; \backslash equiv\; q\; \backslash equiv\; 3\; \backslash pmod\{4\}$이면, 아래 성질을 이용해 더 쉽게 풀 수 있다.
* $m\_p\; =\; c^((p+1))\; \backslash pmod\{p\}$
* $m\_q\; =\; c^((q+1))\; \backslash pmod\{q\}$
* $(m\_p)^2\; \backslash equiv\; c^((p+1))\; \backslash equiv\; c*c^((p-1))\backslash equiv\; c*()\; \backslash pmod\{p\}$ ($$는 르장드르 기호)
* $c\; \backslash equiv\; m^2\; \backslash pmod\{pq\}\; \backslash Rightarrow\; c\; \backslash equiv\; m^2\; \backslash pmod\{p\}$
* $\backslash therefore\; ()=1\; \backslash Rightarrow\; (m\_p)^2\; \backslash equiv\; c\; \backslash pmod\{p\}$

네 개의 값 중 어느 것이 올바른 평문인지 판별하기 위해, 평문에 중복성(redundancy)을 추가하거나 패딩 기법을 사용할 수 있다.

4. 특징

라빈 암호체계는 다음과 같은 특징을 가진다.

* 효율성: RSA에 비해 암호화 과정이 효율적이다. 라빈 암호는 제곱 연산만으로 암호화를 수행하지만, RSA는 세제곱 이상의 연산을 필요로 한다.
* 효과성: 암호화 함수가 4:1 함수이므로 복호화 과정에서 네 가지 서로 다른 결과가 나오며, 이 중 셋은 가짜 결과이다. 따라서 복호화 시 진짜 결과를 잘 추론해야 한다. 평문이 텍스트 메시지인 경우 추론이 어렵지 않지만, 숫자 값인 경우 모호성 제거 방식을 사용해야 한다. 이러한 단점을 보완하기 위해 암호문과 평문이 1:1 대응이 되도록 하는 알고리즘이 사용되기도 한다.
* 보안성: 소인수 분해 문제와 동치이므로, 소인수분해 일반 공식이 나오거나 동치성이 증명되기 전까지는 상당히 안전하다고 볼 수 있다. 그러나 선택 암호문 공격에 취약하며, 선택 평문 공격에 대해 구별 불가능성을 제공하지 않는다.

4.1. 효율성(Efficiency)

암호화 과정은 RSA에 비해 효율적이다. 라빈 암호는 제곱 연산만으로 암호화를 수행하는 반면, RSA는 세제곱 이상의 연산을 필요로 한다. 복호화 과정의 효율성은 RSA와 비슷하다. 두 번의 모듈러 지수 연산과 중국인의 나머지 정리를 사용한다.

4.2. 효과성(Effectiveness)

암호화 함수가 4:1 함수이므로, 복호화 과정에서 네 가지 서로 다른 결과가 나오고 이 중 셋은 가짜 결과이기 때문에, 복호화 과정에서 진짜 결과를 잘 추론해야 한다. 특히 숫자 값을 암호화한 경우 모호성 제거 스킴(disambiguation scheme)을 사용해야 한다. 이 단점을 개량해서 [암호문 1: 평문 1]을 유지하는 알고리즘이 쓰인다.

복호화는 올바른 결과 외에 세 개의 잘못된 결과를 생성하므로 올바른 결과를 추측해야 한다. 이는 라빈 암호체계의 주요 단점이며, 널리 실용화되지 못한 요인 중 하나이다.

평문이 텍스트 메시지를 나타내도록 의도된 경우 추측은 어렵지 않다. 그러나 평문이 숫자 값을 나타내도록 의도된 경우 이 문제는 일종의 모호성 제거 방식을 통해 해결해야 할 문제가 된다. 이 문제를 제거하기 위해 특수한 구조의 평문을 선택하거나 패딩을 추가할 수 있다. 역전의 모호성을 제거하는 방법은 Blum과 Williams에 의해 제안되었다. 사용되는 두 소수는 4 모듈로 3과 합동인 소수로 제한되고, 제곱의 영역은 이차 잔여 집합으로 제한된다. 이러한 제한은 제곱 함수를 트랩도어 순열로 만들어 모호성을 제거한다.

4.3. 보안성(Security)

라빈 암호 알고리즘은 소인수 분해 문제와 동치이다. (이는 RSA 암호에서는 증명되지 않았다.) 따라서 소인수분해 일반 공식이 나오거나 동치성이 증명되기 전까지는 상당히 안전하다고 볼 수 있다.

하지만 라빈 암호 시스템은 선택 암호문 공격(chosen ciphertext attack)에 취약하다. 암호화 과정이 결정적이므로, 공격자는 암호문과 후보 메시지가 주어지면 후보 메시지를 암호화하여 주어진 암호문이 생성되는지를 쉽게 확인할 수 있다. 즉, 구별 불가능성을 선택 평문 공격에 대해 제공하지 않는다.

또한, 제작 시 quadratic residue modulo n을 사용하므로, 이와 관련된 공격이 가능하다.

라빈 암호 시스템은 선택 암호문 공격에 취약하며, 예를 들어 중복성을 추가하여 단일 근을 생성하는 방식으로 공격을 방해할 수 있지만, 이 경우 소인수 분해 문제와의 동등성 증명이 실패하여 안전성이 불확실해진다.

라빈 암호의 해독 문제는 소인수 분해 문제로 귀착시킬 수 있다. 어떤 평문 x1에 대응하는 암호문 y1이 주어졌을 때, 특정 방정식을 만족하는 x를 구할 수 있다면, 높은 확률로 x1과는 다른 값 x2를 얻을 수 있고, 이를 통해 높은 확률로 소인수 p 또는 q를 구할 수 있다.

5. 디지털 서명 알고리즘

라빈 암호 체계는 전자 서명을 생성하고 검증하는 데 사용될 수 있다. 서명 생성에는 개인 키 $(p,q)$가, 서명 검증에는 공개 키 $n$이 필요하다.

5.1. 서명(Signing)

메시지 $m$은 개인 키 $(p,q)$를 사용하여 다음과 같이 서명할 수 있다.

1. 임의의 값 $u$를 생성한다.
2. 암호화 해시 함수 $H$를 사용하여 $c\; =\; H(m\backslash mathbin\backslash Vert\; u)$를 계산한다. 여기서 이중 막대 기호는 연결을 나타낸다. $c$는 $n$보다 작은 정수여야 한다.
3. 개인 키 $(p,q)$를 사용하여 $c$의 제곱근을 찾는다. 그러면 일반적인 네 가지 결과 $r\_1,\; r\_2,\; r\_3,\; r\_4$가 생성된다.
4. 각 $r\_i$를 제곱하면 $c$가 생성될 것으로 예상할 수 있다. 그러나 이는 $c$가 $p$와 $q$를 법으로 한 이차 잉여인 경우에만 참이다. 이 경우인지 확인하려면 $r\_1$을 제곱한다. 이렇게 해서 $c$가 생성되지 않으면, 새로운 임의의 $u$로 이 알고리즘을 반복한다. 적절한 $c$를 찾기 전에 이 알고리즘을 반복해야 하는 예상 횟수는 4이다.
5. $c$의 제곱근 $r\_1$을 찾았으면, 서명은 $(r\_1,u)$이다.

5.2. 서명 검증(Verifying a signature)

공개 키 n을 사용하여 메시지 m에 대한 서명 (r, u)를 검증하는 방법은 다음과 같다.

1. c = H(m || u)를 계산한다.
2. r′ = c² mod n을 계산한다.
3. r′ ≡ r 이면 서명이 유효하고, 그렇지 않으면 위조된 것이다.