Rabin暗号のソースを表示

'''Rabin暗号'''（[[:en:Rabin cryptosystem]]）とは、1979年に[[マイケル・ラビン]]が発表した[[公開鍵暗号]]である。[[選択平文攻撃]]で解読することと[[素因数分解]]問題を解くことが等価であることが証明された初の暗号である。

== 概要 ==
Rabin暗号は[[1979年]]、[[マイケル・ラビン]]により発明された。この暗号は[[RSA暗号]]と同じく、大きな[[合成数]]の[[素因数分解]]の困難さを安全性の根拠とした暗号方式である。

この暗号は、鍵となる合成数が素因数分解できない限り、少なくとも[[選択平文攻撃]]による[[暗号解読|解読]]に対して理論的に「安全である」と証明されている。しかしながら[[選択暗号文攻撃]]に対しては全く安全でないことも証明できる。そのため、証明可能安全性を有するという意味で[[暗号理論]]的な意義は大きいが、そのまま使用することは推奨されない。

== 暗号方式 ==
Rabin暗号は、以下の3つのアルゴリズム（鍵生成、暗号化、復号）で定義される。

=== 鍵生成 ===
まず 2つの異なる[[素数]] ''p'' と ''q'' を用意しその[[積]]を ''n'' と置く。 そして 0 ≤ B ≤ n-1 の B を選び、これと ''n'' を[[公開鍵]]（暗号化鍵）とし、''p,q'' を[[秘密鍵]]（復号鍵）とする。

このとき ''p'' ≡ ''q'' ≡ 3 (mod 4) となるように ''p,q'' を選ぶ（''n'' を[[ブラム数]]とする）と復号処理が簡易化される。以下、''n'' はブラム数とする。また、B は単純に 0 とすることもできるため、B を省略する場合もある。<!-- 幾つかのテキストや en では省略されている -->

=== 暗号化 ===
暗号化は以下のように行われる。平文を ''x'' とする。
:<math>e(x) = x(x + B)\ \bmod \ n</math>

=== 復号 ===
一方、復号は次のように行われる。暗号文を ''y'' とすると、次の2つの[[連立方程式]]の解 ''x'' が求める平文である。このとき、暗号化は[[単射]]ではなく、そのため復号の際に一意に平文を求めることができないことに注意を要する。

: <math> x^2 + Bx - y = 0  \pmod p</math>
: <math> x^2 + Bx - y = 0  \pmod q</math>

上記の方程式には4つの解が求まるが、4個の解から正しい平文を特定することはできない。正しい平文が求められるには、平文に十分な[[冗長度]]を持たせる等の条件が必要となる。具体的には、

: <math>x_p = {\left(y+\frac{B^2}{4}\right)}^{(p+1)/4} - \frac{B}{2} \ \bmod \ p</math>
: <math>x_q = {\left(y+\frac{B^2}{4}\right)}^{(q+1)/4} - \frac{B}{2} \ \bmod \ q</math>

とすると、求める解 ''x'' は、(a,b) in { <math>(x_p, x_q)</math>, <math>(p-B-x_p, x_q)</math>, <math>(x_p, q-B-x_q)</math>, <math>(p-B-x_p, q-B-x_q)</math> }の4組を[[中国の剰余定理]]により、x=a mod p, x=b mod qとして求める。

== 安全性 ==
Rabin暗号の解読問題は、次のように素因数分解問題へ帰着できることが示せる。
ある平文 ''x1'' に対応する暗号文 ''y1'' を与えられたときに、

: <math> x^2 + Bx - y1 = 0  \pmod n</math>

を満たす ''x'' を求めることができた場合、3/4 の確率で ''x1'' とは異なる値 ''x2'' が得られる。そのとき、無視できない確率で GCD(|x1+x2+B|,n) = p または q となる。<!-- こんな感じだったはず -->

== 参考文献 ==
* Michael Rabin, "Digitalized Signatures and Public-Key Functions as Intractable as Factorization", MIT Laboratory for Computer Science, January 1979. [http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-212.pdf (in PDF)].

== 関連項目 ==
* [[公開鍵暗号]]
* [[暗号]]
{{DEFAULTSORT:らひんあんこう}}

{{cryptography navbox|public-key}}
[[Category:暗号]]
[[Category:エポニム]]