라빈 암호체계 문서 원본 보기

{{위키데이터 속성 추적}}
'''라빈 암호'''(Rabin cryptosystem)는 [[미하엘 라빈]]이 1979년1월에 발표한, 소인수분해 기반 공개키 암호(비대칭 암호)이다.

공개키로 암호화하고, 개인키로 복호화한다.

중국인의 나머지정리(Chinese Remainder Theorem, CRT)를 활용한다.

== 절차 ==
밥이 앨리스에게 암호문을 보내고, 앨리스는 이를 해독한다.

=== 키 생성(key generation) ===

* 앨리스는 매우 크며 서로 다른 두 소수 p, q을 고른다. 계산 편의를 위해 <math>p \equiv q \equiv 3 \pmod{4}</math>를 사용해도 좋다.
* n = pq을 구한 뒤 밥에게 보낸다.
* n은 공개키, p와q는 앨리스의 개인키이다.

=== 암호화(encryption) ===

* 밥은 앨리스에게 보낼 [[평문]] m을 고른다.  <math>m \in P =\{ 1,2,\cdots,n-1 \}</math>
* 밥은 암호문 <math>c = m^2 \pmod{n}</math>을 보낸다.

=== 복호화(decryption) ===

* 앨리스는 [[암호문]] c를 받고, n을 아는 상황이다.
* <math>m_p = \sqrt c \pmod{p}, m_q = \sqrt c \pmod{q}</math>이고, <math>p*y_p + q*y_q =1 </math>를 만족하는 <math>y_p,y_q </math>를 찾는다.
** m이 합성수이면, 효율적으로 찾는 방법이 발견되지 않았다.
** m이 소수이거나, 두 소수의 곱이면 중국인의 나머지정리로 푼다.
* 중국인의 나머지정리를 이용하면, 근 네 개가 나타나며 이 가운데 하나가 mod n에 대해 m과 같다. 근은 아래와 같다.
** <math>r_1 = p*y_p*m_p+q*y_q*m_q \pmod{n}</math>
** <math>-r_1 = n-r_1</math>
** <math>r_2 = p*y_p*m_p-q*y_q*m_q \pmod{n}</math>
** <math>-r_2 = n-r_2</math>
* <math>r_1, r_2</math>를 계산했다면, <math>\gcd (|r_1- r_2|, n)=p \ or \ q </math>이므로 p,q를 알 수 있다. 따라서 n을 쉽게 소인수분해 할 수 있다.
** <math>p \equiv q \equiv 3 \pmod{n}</math>이면, 아래 성질을 이용해 더 쉽게 풀 수 있다.
*** <math>m_p =  c^{{1\over{4}}(p+1)} \pmod{p},\  m_q =  c^{{1\over{4}}(q+1)} \pmod{q}</math>에서 c의 지수가 정수로 나온다.
*** <math>(m_p)^2 \equiv  c^{{1\over{2}}(p+1)} \equiv c*c^{{1\over{2}}(p-1)}\equiv c*({c \over{p}}) \pmod{p}, {c \over{p}}  </math>is Legendre symbol
*** <math>c \equiv m^2 \pmod{pq} \Rightarrow 
c \equiv m^2 \pmod{p}
</math>
*** <math>\therefore ({c \over p} )=1 \Rightarrow (m_p)^2 \equiv c \pmod{p}
</math>

== 특징 ==

=== 효율성(efficiency) ===
암호화에서 Square modulo를 계산하기 때문에, 3차 이상을 계산해야 하는 RSA에 비해 효율적이다.

복호화에서 two modular exponentiations와 중국인의 나머지정리를 적용하므로 효율성은 RSA와 비슷하다.

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

=== 보안성(security) ===
Rabin 알고리즘은 소인수 분해 문제와 동치이다. (RSA에서는 동치성이 증명되지 않았다.) 따라서 동치성이 증명되거나, 소인수분해 일반공식이 등장할 때까지 상당히 안전하다.

선택 암호문 공격(chosen ciphertext attack)에 취약할 수 있다.

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

{{공개 키 암호 방식}}

[[분류:암호학]]