ラビン暗号とは

/情報・暗号

ラビン暗号とは

ラビン暗号とは、公開鍵暗号(非対象鍵暗号)の一種で、桁数が大きい合成数の素因数分解が困難であることを安全性の根拠とした暗号化方式です。ラビン暗号は、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$ の組合せより、4つの平文候補($M_1,M_2,M_3,M_4$)を得ることができます。

$M_p^+=\sqrt{C}\pmod{p}$
$M_q^+=\sqrt{C}\pmod{q}$
$M_1=\sqrt{C}\pmod{n}$
$M_p^+=\sqrt{C}\pmod{p}$
$M_q^-=-\sqrt{C}\pmod{q}$
$M_2=\sqrt{C}\pmod{n}$
$M_p^-=-\sqrt{C}\pmod{p}$
$M_q^+=\sqrt{C}\pmod{q}$
$M_3=\sqrt{C}\pmod{n}$
$M_p^-=-\sqrt{C}\pmod{p}$
$M_q^-=-\sqrt{C}\pmod{q}$
$M_4=\sqrt{C}\pmod{n}$

ラビン暗号の安全性

ラビン暗号は受動的攻撃に対する安全性は、素因数分解と等価であることが証明されています。尚、受動的攻撃とは、公開されている情報(公開鍵)から暗号文から平文を解読する攻撃です。

 

応用数学
物理数学、計算数学、情報・暗号、機械学習、金融工学、ゲーム理論
散策路TOP
古典物理、量子力学、物性論、数学、応用数学、力学、電磁気学、相対論、熱・統計力学、解析学、代数学、幾何学、統計分析、情報

 

タイトルとURLをコピーしました