ラビン暗号とは
ラビン暗号とは、公開鍵暗号（非対象鍵暗号）の一種で、桁数が大きい合成数の素因数分解が困難であることを安全性の根拠とした暗号化方式です。ラビン暗号は、1979年にラビンにより発明されました。
送信者は受信者の公開鍵（暗号化鍵）で平文から暗号文を作成し、受信者は自分の秘密鍵（複合化鍵）で暗号文を平文に戻します。平文と暗号文、及び、暗号化鍵と複合化鍵の関係は以下で表されます。
| 送信者（暗号化） | 受信者（複合化） |
| 平文（$M$）→ 暗号文（$C$） | 暗号文（$C$）→ 平文（$M$） |
| 暗号化鍵（$n$） | 複合化鍵（$p,q$） |
| $C=M^2\pmod{n}$ －① | $M_p=C^{(p+1)/4}\pmod{p} -②$ $M_q=C^{(q+1)/4}\pmod{q} -③$ |
ラビン暗号は受動的攻撃に対する安全性は、素因数分解と等価であることが証明されています。尚、受動的攻撃とは、公開されている情報（公開鍵）から暗号文から平文を解読する攻撃です。
鍵生成
$p$ と $q$ は互いに素で、以下の関係が成り立つように生成します。
$p\equiv q\equiv 3\pmod{4} -④$
暗号化鍵と複合化鍵には以下の関係があります。$n$（公開鍵）から $p,q$（秘密鍵）を求める素因数分解の困難さがラビン暗号の安全性の根拠となります。
$$n=pq -⑤$$
複合化
$p$ と $q$ が互いに素であるから、拡張ユークリッド互除法より以下を満足する整数 $x$ 、$y$ を求め、
$$xp+yq=1 -⑥$$
中国の剰余定理を使うと、②と③の $\pm M_p$ と $\pm M_q$ の組合せより、次の４つの平文候補を得ることができます。
$M_1=(M_qxp+M_pyq)\pmod{n} -⑦$
$M_2=(M_qxp-M_pyq)\pmod{n} -⑧$
$M_3=(-M_qxp+M_pyq)\pmod{n} -⑨$
$M_4=(-M_qxp-M_pyq)\pmod{n} -⑩$
４つの平文候補からオリジナルの平文を特定するためには、いくつかの冗長的な情報が必要になります。
ラビン暗号の例
簡単なラビン暗号の例を示します。
鍵生成
④の条件を満たす暗号鍵として、$p=3$ と $q=7$ を選びます。このとき、公開鍵は⑤より $n=21$（$=3\times7$）で求められます。尚、平文は $M\lt n$ を満たす必要があります。ここでは $M=19$ とします。
暗号化
①により暗号文は以下で求めます。
$C=19^2\pmod{21}=4$
複合化
複合化では②と③より、
$$M_p=4^{(3+1)/4}\pmod{3}=1$$$$M_q=4^{(7+1)/4}\pmod{7}=2$$
次に、⑥を満たす組合せとして、$x=5$ と $y=-2$ が得られ、⑦～⑩より平文の候補が以下のように求められます。
$M_1=(2\times5\times3-1\times2\times7)\pmod{21}=16$
$M_2=(2\times5\times3+1\times2\times7)\pmod{21}=2$
$M_3=(-2\times5\times3-1\times2\times7)\pmod{21}=19$
$M_4=(-2\times5\times3+1\times2\times7)\pmod{21}=5$
これら４つのうちの１つ（$M_3=19$）が求める平文になります。
