Rabin暗号 Rabin暗号の概要

概要

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として求める。