ラビン署名アルゴリズム

暗号学において、ラビン署名アルゴリズムは、 1978年にマイケル・O・ラビンによって最初に提案されたデジタル署名の方法である。 ^{[1] [2] [3]}

ラビン署名アルゴリズムは、最初に提案されたデジタル署名方式の 1 つです。署名の必須ステップとしてハッシュの使用を導入することで、適切にスケーリングされたパラメータを前提として、選択メッセージ攻撃下での存在的偽造不可能性という、現在の偽造に対するセキュリティの最新基準を満たす最初の設計となりました。

ラビン署名は指数を持つRSA署名に似ていますが、これにより質的な違いが生じ、より効率的な実装^[4]と、 RSAでは証明されていない整数因数分解の難しさ^{[2] [3] [5]}に対するセキュリティ保証が可能になります。しかし、ラビン署名は、RSASSA-PKCS1-v1_5やRSASSA-PSSなどのRSA署名方式と比較して、IEEE P1363 ^[6]以外ではあまり使用されず、標準化もされていません。 ${\displaystyle e=2}$

Rabin 署名方式は、メッセージのランダム化ハッシュ関数 とビットのランダム化文字列によってパラメータ化されます。 ${\displaystyle H(m,u)}$${\displaystyle m}$${\displaystyle k}$${\displaystyle u}$

公開鍵

公開鍵は、と が奇数である整数のペアです。は任意に選択され、固定定数になることもあります。${\displaystyle (n,b)}$${\displaystyle 0\leq b<n}$${\displaystyle n}$${\displaystyle b}$

サイン

メッセージの署名は、ビット文字列と整数のペアであり、${\displaystyle m}$${\displaystyle (u,x)}$${\displaystyle k}$${\displaystyle u}$${\displaystyle x}$$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}.}$$

秘密鍵

公開鍵の秘密鍵は、素数の大きな空間から一様にランダムに選択された、の秘密の奇数素因数分解です。${\displaystyle (n,b)}$${\displaystyle p\cdot q}$${\displaystyle n}$

メッセージに署名する

秘密鍵を使用してメッセージに署名するには、署名者はまずビットの文字列を一様にランダムに選択し、 を計算します。 とします。が を法とする二次非剰余である場合、署名者は独立したランダム からやり直します。^{[2] : p. 10} それ以外の場合、署名者は素数を法とする平方根を計算するための標準アルゴリズムを使用してを計算します。選択すると最も簡単になります。平方根は一意ではなく、署名方式のさまざまなバリエーションで平方根の選択が異なります。^[4]いずれにしても、署名者は同じハッシュ に対して 2 つの異なる根を明らかにしないようにする必要があります。および は方程式 を満たします。 次に署名者は中国剰余定理を使用してについてシステムを解き、が必要に応じて を満たすようにします。署名者は上の署名として を明らかにします。${\displaystyle m}$${\displaystyle k}$${\displaystyle u}$${\displaystyle c:=H(m,u)}$${\displaystyle d=(b/2){\bmod {n}}}$${\displaystyle c+d^{2}}$${\displaystyle n}$${\displaystyle u}$$${\displaystyle {\begin{aligned}x_{p}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {p}},\\x_{q}&:={\Bigl (}-d\pm {\sqrt {c+d^{2}}}{\Bigr )}{\bmod {q}},\end{aligned}}}$$${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$${\displaystyle c}$${\displaystyle x_{p}}$${\displaystyle x_{q}}$$${\displaystyle {\begin{aligned}x_{p}(x_{p}+b)&\equiv H(m,u){\pmod {p}},\\x_{q}(x_{q}+b)&\equiv H(m,u){\pmod {q}}.\end{aligned}}}$$$${\displaystyle {\begin{aligned}x&\equiv x_{p}{\pmod {p}},\\x&\equiv x_{q}{\pmod {q}},\end{aligned}}}$$${\displaystyle x}$${\displaystyle x}$$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}$$${\displaystyle (u,x)}$${\displaystyle m}$

を解く前の試行回数は、全整数の約 1/4 が を法とする平方剰余であるため、平均約 4 回の試行で幾何分布します。${\displaystyle u}$${\displaystyle x(x+b)\equiv H(m,u){\pmod {n}}}$${\displaystyle x}$${\displaystyle n}$

ハッシュ関数で一般的に定義されるあらゆる敵に対するセキュリティ（つまり、ランダムオラクルモデルにおけるセキュリティ）は、因数分解の難しさから導かれます。偽造に成功する確率が高いこのような敵は、を法とするランダムな整数の2 つの異なる平方根と をほぼ同じくらいの確率で見つけることができます。 の場合、はの非自明な因数です。 なぜならであるためですが、だからです。[ ^3] セキュリティを現代的な用語で形式化するには、 の共域などの追加の詳細を記入する必要があります。素因数 の標準サイズを設定すると、 を指定できる場合があります。^[5]${\displaystyle H}$${\displaystyle n}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle c}$${\displaystyle n}$${\displaystyle x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}}$${\displaystyle \gcd(x_{1}\pm x_{2},n)}$${\displaystyle n}$${\displaystyle {x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}}$${\displaystyle n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2})}$${\displaystyle n\nmid x_{1}\pm x_{2}}$${\displaystyle H}$${\displaystyle K}$${\displaystyle 2^{K-1}<p<q<2^{K}}$${\displaystyle H\colon \{0,1\}^{*}\times \{0,1\}^{k}\to \{0,1\}^{K}}$

ハッシュ関数のランダム化は、署名者が平方剰余を見つけられるようにするために導入されましたが、署名のランダム化ハッシュは、後に、より厳密なセキュリティ定理^[3]と固定ハッシュ関数に対する衝突攻撃に対する耐性のためにそれ自体が関連するようになりました。^{[7] [8] [9]}

公開鍵の量はセキュリティを追加しません。なぜなら、与えられたと の合同性を解くアルゴリズムはどれも、を法とする平方根を計算するアルゴリズムのサブルーチンとして簡単に使用できるためであり、その逆も同様です。したがって、実装では、単純化のために を安全に設定できます。は、最初の提案後の処理で完全に破棄されました。^{[10] [3] [6] [4]}を削除すると、署名アルゴリズムのとの式は次のようになります。${\displaystyle b}$${\displaystyle x(x+b)\equiv c{\pmod {n}}}$${\displaystyle x}$${\displaystyle b}$${\displaystyle c}$${\displaystyle n}$${\displaystyle b=0}$${\displaystyle b}$${\displaystyle b}$${\displaystyle x_{p}}$${\displaystyle x_{q}}$$${\displaystyle {\begin{aligned}x_{p}&:=\pm {\sqrt {c}}{\bmod {p}},\\x_{q}&:=\pm {\sqrt {c}}{\bmod {q}}.\end{aligned}}}$$

ラビン署名方式は、1980年にウィリアムズによって微調整され^[10]、 と を選択し、平方根を と で微調整された平方根 に置き換えたため、代わりに が満たされ、署名者は セキュリティを犠牲にすることなく1回の試行で署名を作成できるようになりました。この変形はラビン–ウィリアムズ として知られています。^{[4] [6]}${\displaystyle p\equiv 3{\pmod {8}}}$${\displaystyle q\equiv 7{\pmod {8}}}$${\displaystyle x}$${\displaystyle (e,f,x)}$${\displaystyle e=\pm 1}$${\displaystyle f\in \{1,2\}}$$${\displaystyle efx^{2}\equiv H(m,u){\pmod {n}},}$$

さらに他のバリエーションでは、署名サイズと検証速度のトレードオフ、部分的なメッセージの復元、署名の圧縮（サイズを半分に縮小）、公開鍵の圧縮（サイズを3分の1に縮小）が可能になり、セキュリティを犠牲にすることなく実現できます。^[4]

ハッシュ関数を使わない変種が教科書に掲載されているが、^{[11] [12]}指数 2 については Rabin の功績が認められているものの、ハッシュ関数の使用については認められていない。これらの変種は簡単に破られてしまう。例えば、署名検証式がの代わりに であれば、署名は誰でもメッセージの有効な署名として偽造できる。 ${\displaystyle x=2}$${\displaystyle m=4}$${\displaystyle x^{2}\equiv m{\pmod {n}}}$${\displaystyle x^{2}\equiv H(m,u){\pmod {n}}}$

元の論文^[2]では、ハッシュ関数はという表記で書かれ、Cは圧縮を表し、との連結をビット文字列として表すために が並置法で使用されていました。 ${\displaystyle H(m,u)}$${\displaystyle C(MU)}$${\displaystyle M}$${\displaystyle U}$

慣例により、特定のメッセージ に署名する場合、[署名者] は、合意された長さ の単語 を接尾辞として追加します。 の選択は、メッセージが署名されるたびにランダムに行われます。署名者はハッシュ関数を使用して を単語 に圧縮し、2 進数として… ${\displaystyle M}$${\displaystyle P}$${\displaystyle U}$${\displaystyle k}$${\displaystyle U}$${\displaystyle M_{1}=MU}$${\displaystyle C(M_{1})=c}$${\displaystyle c\leq n}$

この表記は、後になってその部分を無視して乗算を意味すると誤解した一部の著者の間で混乱を招き、署名方式が自明に破綻していると誤解させた。^[13]${\displaystyle C}$${\displaystyle MU}$

• cr.yp.to のラビン・ウィリアムズ署名