ラビン暗号システム

ラビン暗号システムは、 RSAと同様に、整数因数分解の難しさと関連した安全性を持つトラップドア関数に基づく公開鍵暗号化方式の一種である。^{[1] [2]}

ラビンのトラップドア関数の利点は、逆関数の逆関数が整数の因数分解と同じくらい難しいことが数学的に証明されていることです。一方、RSA トラップドア関数にはそのような証明は知られていません。ラビン関数の各出力は、4 つの入力のいずれによっても生成される可能性があるという欠点があります。各出力が暗号文である場合、復号化時に 4 つの入力のどれが真の平文であるかを識別するために、余分な複雑さが必要になります。これを回避するための単純な試みは、多くの場合、選択暗号文攻撃によって秘密鍵を復元するか、平文空間に冗長性をエンコードすることで、因数分解に対するセキュリティの証明を無効にします。^[1]

ラビントラップドア関数に基づく公開鍵暗号化方式は、主に教科書の例として使用されています。対照的に、RSA は、実際に広く使用されているRSAES-PKCS1-v1_5やRSAES-OAEPなどの標準的な公開鍵暗号化方式の基礎となっています。

ラビントラップドア関数は、1978年にマイケル・O・ラビンによってラビン署名方式の一部として初めて公開されました。^{[3] [4] [5]}ラビン署名方式は、署名の偽造が因数分解と同じくらい困難であることが証明された 最初のデジタル署名方式でした。

トラップドア関数は後に教科書で公開鍵暗号化方式の例として再利用され、^{[6] [7] [1]} ラビンが暗号化方式として公開しなかったにもかかわらず、ラビン暗号システムとして知られるようになりました。

すべての非対称暗号システムと同様に、Rabin システムでは、暗号化用の公開鍵と復号化用の秘密鍵の鍵ペアを使用します。公開鍵は誰でも使用できるように公開されますが、秘密鍵はメッセージの受信者のみが知っています。

Rabin 暗号システムのキーは次のように生成されます。

1. およびとなる2 つの大きく異なる素数 とを選択します。${\displaystyle p}$${\displaystyle q}$${\displaystyle p\equiv 3{\bmod {4}}}$${\displaystyle q\equiv 3{\bmod {4}}}$
2. 計算します。${\displaystyle n=pq}$

次に公開鍵と、そのペアが秘密鍵です。 ${\displaystyle n}$${\displaystyle (p,q)}$

メッセージは、まず可逆マッピングを使用して数値に変換し、次に を計算することで暗号化できます。暗号文は です。 ${\displaystyle M}$${\displaystyle m<n}$${\displaystyle c=m^{2}{\bmod {n}}}$${\displaystyle c}$

メッセージは、次のように平方根を法として暗号文から復元できます。 ${\displaystyle m}$${\displaystyle c}$${\displaystyle n}$

1. 次の式を使用して、を法とする平方根を計算します。 ${\displaystyle c}$${\displaystyle p}$${\displaystyle q}$

   ${\displaystyle {\begin{aligned}m_{p}&=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}\\m_{q}&=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}\end{aligned}}}$

2. 拡張ユークリッドの互除法を使用して、 となる およびを見つけます。${\displaystyle y_{p}}$${\displaystyle y_{q}}$${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$
3. 中国剰余定理を使用して、を法とする4 つの平方根を求めます。 ${\displaystyle c}$${\displaystyle n}$

   ${\displaystyle {\begin{aligned}r_{1}&=\left(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{2}&=n-r_{1}\\r_{3}&=\left(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{4}&=n-r_{3}\end{aligned}}}$

これら 4 つの値のうちの 1 つが元の平文ですが、追加情報がなければ 4 つのうちどれが正しいのかは判断できません。 ${\displaystyle m}$

上記のステップ 1 の式が実際に の平方根を生成することは、次のように示せます。最初の式では、 であることを証明します。指数は整数です。 であれば証明は簡単なので、 は を割り切れないと仮定できます。はを意味するので、c はを法とする平方剰余であることに注意してください。すると、 ${\displaystyle c}$${\displaystyle m_{p}^{2}\equiv c{\bmod {p}}}$${\displaystyle p\equiv 3{\bmod {4}},}$${\textstyle {\frac {1}{4}}(p+1)}$${\displaystyle c\equiv 0{\bmod {p}}}$${\displaystyle p}$${\displaystyle c}$${\displaystyle c\equiv m^{2}{\bmod {pq}}}$${\displaystyle c\equiv m^{2}{\bmod {p}}}$${\displaystyle p}$

${\displaystyle m_{p}^{2}\equiv c^{{\frac {1}{2}}(p+1)}\equiv c\cdot c^{{\frac {1}{2}}(p-1)}\equiv c\cdot 1\mod p}$

最後のステップはオイラーの基準によって正当化されます。

例えば、 と を取ると、 となります。を平文とします。したがって、暗号文は となります 。 ${\displaystyle p=7}$${\displaystyle q=11}$${\displaystyle n=77}$${\displaystyle m=20}$${\displaystyle c=m^{2}{\bmod {n}}=400{\bmod {77}}=15}$

復号化は次のように進行します。

1. 計算して。${\displaystyle m_{p}=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}=15^{2}{\bmod {7}}=1}$${\displaystyle m_{q}=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}=15^{3}{\bmod {11}}=9}$
2. 拡張ユークリッドの互除法を使用しておよび を計算します。 であることが確認できます。${\displaystyle y_{p}=-3}$${\displaystyle y_{q}=2}$${\displaystyle y_{p}\cdot p+y_{q}\cdot q=(-3\cdot 7)+(2\cdot 11)=1}$
3. 4 つの平文候補を計算します。

   ${\displaystyle {\begin{aligned}r_{1}&=(-3\cdot 7\cdot 9+2\cdot 11\cdot 1){\bmod {77}}=64\\r_{2}&=77-64=13\\r_{3}&=(-3\cdot 7\cdot 9-2\cdot 11\cdot 1){\bmod {77}}=\mathbf {20} \\r_{4}&=77-20=57\end{aligned}}}$

そして、 が目的の平文であることがわかります。4 つの候補はすべて 15 mod 77 の平方根であることに注意してください。つまり、各候補について、となり、それぞれが同じ値 15 に暗号化されます。 ${\displaystyle r_{3}}$${\displaystyle r_{i}^{2}{\bmod {77}}=15}$${\displaystyle r_{i}}$

ラビン暗号システムは、デジタル署名の作成と検証に使用できます。署名を作成するには、秘密鍵が必要です。署名の検証には、公開鍵が必要です。 ${\displaystyle (p,q)}$${\displaystyle n}$

メッセージは次のように秘密鍵で署名できます。 ${\displaystyle m}$${\displaystyle (p,q)}$

1. ランダムな値を生成します。${\displaystyle u}$
2. 暗号ハッシュ関数 を使用してを計算します。ここで、二重バーは連結を表します。は 未満の整数である必要があります。${\displaystyle H}$${\displaystyle c=H(m\mathbin {\Vert } u)}$${\displaystyle c}$${\displaystyle n}$
3. 秘密鍵を使用しての平方根を求めます。これにより、通常の 4 つの結果が生成されます。${\displaystyle c}$${\displaystyle (p,q)}$${\displaystyle r_{1},r_{2},r_{3},r_{4}}$
4. 各 を二乗すると になると思われるかもしれません。しかし、これが成り立つのは、 が および を法とする平方剰余である場合のみです。これが成り立つかどうかを判断するには、 を二乗します。 が得られない場合、新しいランダムでこのアルゴリズムを繰り返します。適切な を見つけるまでにこのアルゴリズムを繰り返す必要があると予想される回数は4 です。${\displaystyle r_{i}}$${\displaystyle c}$${\displaystyle c}$${\displaystyle p}$${\displaystyle q}$${\displaystyle r_{1}}$${\displaystyle c}$${\displaystyle u}$${\displaystyle c}$
5. の平方根を求めると、署名は になります。${\displaystyle r_{1}}$${\displaystyle c}$${\displaystyle (r_{1},u)}$

メッセージの署名は、次のように公開鍵を使用して検証できます。 ${\displaystyle (r,u)}$${\displaystyle m}$${\displaystyle n}$

1. 計算します。${\displaystyle c=H(m\mathbin {\Vert } u)}$
2. 計算${\displaystyle r'=c^{2}{\bmod {n}}}$
3. 署名は、次の場合には有効であり、そうでない場合は偽造となります。${\displaystyle r'\mathrel {\stackrel {?}{=}} r}$

復号すると、正しい結果に加えて 3 つの誤った結果が生成されるため、正しい結果を推測する必要があります。これがラビン暗号システムの主な欠点であり、実用化が広範に行われなかった要因の 1 つです。

平文がテキストメッセージを表すことを意図している場合、推測することは難しくありません。しかし、平文が数値を表すことを意図している場合、この問題は何らかの曖昧性解消スキームによって解決しなければならない問題になります。この問題を排除するために、特別な構造を持つ平文を選択したり、パディングを追加したりすることができます。反転の曖昧さを排除する方法は、BlumとWilliamsによって提案されました。使用される2つの素数は、4を法として3に合同な素数に制限され、平方のドメインは平方剰余の集合に制限されます。これらの制限により、平方関数は落とし戸 順列になり、曖昧さが排除されます。^[8]

暗号化するには、 n を法とする平方を計算する必要があります。これは、少なくとも立方体の計算を必要とする RSAよりも効率的です。

復号化には、中国剰余定理と 2 つのモジュラー指数計算が適用されます。ここでの効率は RSA に匹敵します。

すべての Rabin 暗号化暗号文の可能な平文の 1 つを見つけるアルゴリズムは、法 を因数分解するために使用できることが証明されています。したがって、ランダムな平文の Rabin 復号化は、少なくとも整数因数分解問題と同じくらい困難であり、これは RSA では証明されていません。因数分解には多項式時間アルゴリズムがないと一般に考えられており、これは、秘密鍵 なしでランダムな Rabin 暗号化値を復号化する効率的なアルゴリズムが存在しないことを意味します。 ${\displaystyle n}$${\displaystyle (p,q)}$

ラビン暗号システムは、暗号化のプロセスが決定論的であるため、選択平文攻撃に対する識別不能性を提供しません。暗号文と候補メッセージが与えられた場合、攻撃者は暗号文が候補メッセージをエンコードしているかどうかを簡単に判断できます (候補メッセージを暗号化すると、指定された暗号文が生成されるかどうかを確認するだけです)。

ラビン暗号システムは、選択暗号文攻撃に対して安全ではありません（チャレンジメッセージがメッセージ空間から一様にランダムに選択された場合でも）。^{[6] : 214}最後の 64 ビットの繰り返しなどの冗長性を追加することで、システムは単一のルートを生成するようにすることができます。これにより、この特定の選択暗号文攻撃が阻止されます。なぜなら、復号アルゴリズムは攻撃者がすでに知っているルートのみを生成するからです。この手法を適用すると、因数分解問題との同等性の証明に失敗するため、2004 年時点でこの変形が安全かどうかは不明です。ただし、Menezes、Oorschot、Vanstone による Handbook of Applied Cryptography では、ルートの検出が 2 部構成のプロセス（1. ルートと2. 中国剰余定理の適用）で ある限り、この同等性は可能性が高いと見なしています。${\displaystyle {\bmod {p}}}$${\displaystyle {\bmod {q}}}$

• 暗号に関するトピック
• ブルーム・ブルーム・シュブ
• シャンクス・トネリアルゴリズム
• シュミット・サモア暗号
• ブルーム・ゴールドワッサー暗号
• クネルスのアルゴリズム

• ブッフマン、ヨハネス。暗号の Einführung。第 2 版。ベルリン: Springer、2001 年。ISBN 3-540-41283-2 
• Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. Handbook of Applied Cryptography . CRC Press, 1996 年 10 月。ISBN 0-8493-8523-7 
• ラビン、マイケル。因数分解と同じくらい扱いにくいデジタル署名と公開鍵関数(PDF 形式)。MIT コンピュータサイエンス研究所、1979 年 1 月。
• Scott Lindhurst、「有限体における平方根を計算するための Shank アルゴリズムの分析」、R Gupta および KS Williams、「Proc 5th Conf Can Nr Theo Assoc、1999、vol 19 CRM Proc & Lec Notes、AMS、1999 年 8 月。
• R Kumanduri および C Romero、「Number Theory w/ Computer Applications、Alg 9.2.9」、Prentice Hall、1997 年。素数を法とする二乗剰余の平方根の確率。

• Menezes、Oorschot、Vanstone、Scott: 応用暗号ハンドブック (無料 PDF ダウンロード)、第 8 章を参照