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).