ラビン暗号とは

ラビン暗号とは、公開鍵暗号（非対象鍵暗号）の一種で、桁数が大きい合成数の素因数分解が困難であることを安全性の根拠とした暗号化方式です。ラビン暗号は、1979年にラビンにより発明されました。

送信者は受信者の公開鍵（暗号化鍵）で平文から暗号文を作成し、受信者は自分の秘密鍵（複合化鍵）で暗号文を平文に戻します。平文と暗号文、及び、暗号化鍵と複合化鍵の関係は以下で表されます。

送信者（暗号化）	受信者（複合化）
平文（$M$）→　暗号文（$C$）	暗号文（$C$）→　平文（$M$）
暗号化鍵（$n$）	複合化鍵（$p,q$）
$C=M^2\pmod{n}$　－①	$M_p^\pm=\pm\sqrt{C}\pmod{p}$ $M_q^\pm=\pm\sqrt{C}\pmod{q}$

尚、暗号化鍵と複合化鍵には以下の関係があります。$n$（公開鍵）から $p,q$（秘密鍵）を求める素因数分解の困難さがラビン暗号の安全性の根拠となります。

$$n=pq$$

ここで、中国の剰余定理を使うと、$M_p^\pm$ と $M_q^\pm$ の組合せより、４つの平文候補（$M_1,M_2,M_3,M_4$）を得ることができます。