Rabin暗号

ラビン暗号とは

ラビン暗号は、1979年にマイケル・ラビンによって発表された公開鍵[[暗号]]方式です。この暗号方式は、大きな合成数の素因数分解の困難さを安全性の根拠としており、RSA[[暗号]]と同様の原理に基づいています。

特徴

ラビン暗号の最大の特徴は、選択平文攻撃に対する安全性と、素因数分解問題を解くことの難しさが等価であることが数学的に証明されている点です。これは、暗号理論において非常に重要な成果とされています。

しかしながら、選択暗号文攻撃に対しては、全く安全ではないことが証明されています。そのため、理論的な意義は大きいものの、実際の暗号システムにそのまま利用することは推奨されていません。

暗号方式

ラビン暗号は、以下の3つのアルゴリズムから構成されます。

鍵生成

1. 素数pとqの選択: まず、二つの異なる素数 p と q を選びます。これらの素数は、p ≡ q ≡ 3 (mod 4) を満たすように選択します。これは、後の復号処理を簡略化するための条件です。この条件を満たす素数を用いた合成数 n = p × q は、ブラム数と呼ばれます。
2. 合成数nの算出: 選んだ素数 p と q の積を n とします。この n が公開鍵の一部となります。
3. 定数Bの選択: 0 ≤ B ≤ n-1 の範囲で定数 B を選択します。この B は、通常は0とすることが多いため、省略されることもあります。最終的に、(n, B) が公開鍵となり、(p, q) が秘密鍵となります。

暗号化

平文を x とすると、暗号化は以下の式で行われます。

math
e(x) = x(x + B) \mod n

復号

暗号文を y とすると、復号は以下の2つの連立方程式の解 x を求めることで行われます。

math
x^2 + Bx - y ≡ 0 \mod p


math
x^2 + Bx - y ≡ 0 \mod q


これらの式は、それぞれ p と q を法とする二次方程式です。この二次方程式は、一般的に二つの解を持つため、結果として4つの候補が算出されます。復号時に正しい平文を一意に特定するためには、平文に十分な冗長性を持たせる必要があります。具体的な解の算出方法は以下のようになります。

math
x_p = \left(y + \frac{B^2}{4}\right)^{(p+1)/4} - \frac{B}{2} \mod p


math
x_q = \left(y + \frac{B^2}{4}\right)^{(q+1)/4} - \frac{B}{2} \mod q


これらの結果を用いて、以下の4組の候補を計算します。

math
(x_p, x_q)

math
(p - B - x_p, x_q)

math
(x_p, q - B - x_q)

math
(p - B - x_p, q - B - x_q)


これらの候補に対して、中国の剰余定理を適用し、最終的な平文 x を算出します。得られた4つの解の中から正しい平文を選ぶためには、平文に何らかの冗長性を付与するなどの工夫が必要です。

安全性

ラビン暗号の安全性の根拠は、合成数 n の素因数分解問題の困難さにあります。もし攻撃者が n の素因数 p と q を特定できれば、復号鍵を入手したことになり、暗号を解読できます。

ラビン暗号の解読問題は、以下のように素因数分解問題に帰着させることができます。ある平文 x1 に対応する暗号文 y1 が与えられたとき、

math
x^2 + Bx - y_1 ≡ 0 \mod 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.

関連項目

公開鍵[[暗号]]
* 暗号

もう一度検索