라빈 암호 (Rabin cryptosystem)는 미하엘 라빈 이 1979년1월에 발표한, 소인수분해 기반 공개키 암호(비대칭 암호)이다.
공개키로 암호화하고, 개인키로 복호화한다.
중국인의 나머지정리(Chinese Remainder Theorem, CRT)를 활용한다.
밥이 앨리스에게 암호문을 보내고, 앨리스는 이를 해독한다.
앨리스는 매우 크며 서로 다른 두 소수 p, q을 고른다. 계산 편의를 위해
p
≡
q
≡
3
(
mod
4
)
{\displaystyle p\equiv q\equiv 3{\pmod {4}}}
n = pq을 구한 뒤 밥에게 보낸다.
n은 공개키, p와q는 앨리스의 개인키이다. 밥은 앨리스에게 보낼 평문 m을 고른다.
m
∈
P
=
{
1
,
2
,
⋯
,
n
−
1
}
{\displaystyle m\in P=\{1,2,\cdots ,n-1\}}
밥은 암호문
c
=
m
2
(
mod
n
)
{\displaystyle c=m^{2}{\pmod {n}}}
앨리스는 암호문 c를 받고, n을 아는 상황이다.
m
p
=
c
(
mod
p
)
,
m
q
=
c
(
mod
q
)
{\displaystyle m_{p}={\sqrt {c}}{\pmod {p}},m_{q}={\sqrt {c}}{\pmod {q}}}
p
∗
y
p
+
q
∗
y
q
=
1
{\displaystyle p*y_{p}+q*y_{q}=1}
y
p
,
y
q
{\displaystyle y_{p},y_{q}}
m이 합성수이면, 효율적으로 찾는 방법이 발견되지 않았다.
m이 소수이거나, 두 소수의 곱이면 중국인의 나머지정리로 푼다. 중국인의 나머지정리를 이용하면, 근 네 개가 나타나며 이 가운데 하나가 mod n에 대해 m과 같다. 근은 아래와 같다.
r
1
=
p
∗
y
p
∗
m
p
+
q
∗
y
q
∗
m
q
(
mod
n
)
{\displaystyle r_{1}=p*y_{p}*m_{p}+q*y_{q}*m_{q}{\pmod {n}}}
−
r
1
=
n
−
r
1
{\displaystyle -r_{1}=n-r_{1}}
r
2
=
p
∗
y
p
∗
m
p
−
q
∗
y
q
∗
m
q
(
mod
n
)
{\displaystyle r_{2}=p*y_{p}*m_{p}-q*y_{q}*m_{q}{\pmod {n}}}
−
r
2
=
n
−
r
2
{\displaystyle -r_{2}=n-r_{2}}
r
1
,
r
2
{\displaystyle r_{1},r_{2}}
gcd
(
|
r
1
−
r
2
|
,
n
)
=
p
o
r
q
{\displaystyle \gcd(|r_{1}-r_{2}|,n)=p\ or\ q}
p
≡
q
≡
3
(
mod
n
)
{\displaystyle p\equiv q\equiv 3{\pmod {n}}}
m
p
=
c
1
4
(
p
+
1
)
(
mod
p
)
,
m
q
=
c
1
4
(
q
+
1
)
(
mod
q
)
{\displaystyle m_{p}=c^{{1 \over {4}}(p+1)}{\pmod {p}},\ m_{q}=c^{{1 \over {4}}(q+1)}{\pmod {q}}}
(
m
p
)
2
≡
c
1
2
(
p
+
1
)
≡
c
∗
c
1
2
(
p
−
1
)
≡
c
∗
(
c
p
)
(
mod
p
)
,
c
p
{\displaystyle (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}}}
c
≡
m
2
(
mod
p
q
)
⇒
c
≡
m
2
(
mod
p
)
{\displaystyle c\equiv m^{2}{\pmod {pq}}\Rightarrow c\equiv m^{2}{\pmod {p}}}
∴
(
c
p
)
=
1
⇒
(
m
p
)
2
≡
c
(
mod
p
)
{\displaystyle \therefore ({c \over p})=1\Rightarrow (m_{p})^{2}\equiv c{\pmod {p}}}
암호화에서 Square modulo를 계산하기 때문에, 3차 이상을 계산해야 하는 RSA에 비해 효율적이다.
복호화에서 two modular exponentiations와 중국인의 나머지정리를 적용하므로 효율성은 RSA와 비슷하다.
암호화 함수가 4 to 1 함수이므로, 복호화 과정에서 4가지 서로 다른 결과가 나오고 이중 3가지는 가짜 결과이기 때문에, 푸는 과정에서 진짜 결과를 잘 추론해야 한다. 특히 숫자 값을 암호화한 경우 모호성 제거 스킴(disambiguation scheme)를 사용해야 한다. 이 단점을 개량해서 [암호문1 : 평문1]을 유지하는 알고리즘이 쓰인다.
Rabin 알고리즘은 소인수 분해 문제와 동치이다. (RSA에서는 동치성이 증명되지 않았다.) 따라서 동치성이 증명되거나, 소인수분해 일반공식이 등장할 때까지 상당히 안전하다.
선택 암호문 공격(chosen ciphertext attack)에 취약할 수 있다.
제작 시 quadratic residue modulo n을 사용하므로, 이와 관련된 공격이 가능하다.
