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 を省略する場合もある。

暗号化

暗号化は以下のように行われる。平文を x とする。

$e(x)=x(x+B)\ {\bmod {\ }}n$

復号

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

$x^{2}+Bx-y=0{\pmod {p}}$

$x^{2}+Bx-y=0{\pmod {q}}$

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

$x_{p}={\left(y+{\frac {B^{2}}{4}}\right)}^{(p+1)/4}-{\frac {B}{2}}\ {\bmod {\ }}p$

$x_{q}={\left(y+{\frac {B^{2}}{4}}\right)}^{(q+1)/4}-{\frac {B}{2}}\ {\bmod {\ }}q$

とすると、求める解 x は、(a,b) in { $(x_{p},x_{q})$, $(p-B-x_{p},x_{q})$, $(x_{p},q-B-x_{q})$, $(p-B-x_{p},q-B-x_{q})$ }の4組を中国の剰余定理により、x=a mod p, x=b mod qとして求める。

安全性

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

$x^{2}+Bx-y1=0{\pmod {n}}$

を満たす 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. (in PDF).

関連項目

• 公開鍵暗号
• 暗号