ブルーム・ゴールドワッサー暗号

ブルーム・ゴールドワッサー（BG）暗号システムは、 1984年にマヌエル・ブルムとシャフィ・ゴールドワッサーによって提案された非対称鍵暗号化アルゴリズムです。ブルーム・ゴールドワッサーは、定数サイズの暗号文拡張を備えた確率的かつ意味的に安全な暗号システムです。この暗号化アルゴリズムは、ブルーム・ブルム・シューブ（BBS）疑似乱数生成器を用いてキーストリームを生成するXORベースのストリーム暗号を実装しています。復号化は、秘密鍵を用いてBBS生成器の最終状態を操作し、初期シードを見つけてキーストリームを再構築することで行われます。

BG 暗号システムは、整数因数分解、具体的には、が大きな素数である合成値の因数分解 が困難であるという仮定に基づいて、意味的に安全です。BG には、ゴールドワッサー–ミカリ暗号システムなどの以前の確率的暗号化方式に比べて多くの利点があります。第 1 に、その意味的セキュリティは整数因数分解のみに帰着し、追加の仮定 (たとえば、二次残余問題やRSA 問題の困難性 ) を必要としません。第 2 に、BG はストレージの点で効率的であり、メッセージの長さに関係なく、暗号文の拡張サイズが一定になります。BG は計算の点でも比較的効率的で、RSA などの暗号システムと比較しても優れています (メッセージの長さと指数の選択によって異なります)。ただし、BG は適応型選択暗号文攻撃 (以下を参照) に対して非常に脆弱です。 北＝pq{\displaystyle N=pq}p、q{\displaystyle p,q}

暗号化は確率的アルゴリズムを用いて行われるため、ある平文は暗号化されるたびに大きく異なる暗号文を生成する可能性があります。これは、傍受されたメッセージを既知の暗号文の辞書と比較することで、攻撃者がそのメッセージを認識できないようにする点で大きな利点となります。

手術

Blum-Goldwasser 暗号システムは、公開鍵と秘密鍵を生成する確率的鍵生成アルゴリズム、確率的暗号化アルゴリズム、および決定論的復号化アルゴリズムの 3 つのアルゴリズムで構成されています。

鍵生成

公開鍵と秘密鍵は次のように生成されます。

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

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

暗号化

メッセージは次のように公開鍵で暗号化されます。 M{\displaystyle M}n{\displaystyle n}

  1. ブロック サイズをビット単位で計算します。h＝⌊loグラム2（loグラム2（n））⌋{\displaystyle h=\lfloor log_{2}(log_{2}(n))\rfloor }
  2. 各ブロックの長さが ビットであるブロックのシーケンスに変換します。M{\displaystyle M}t{\displaystyle t}メートル1、メートル2、…、メートルt{\displaystyle m_{1},m_{2},\dots ,m_{t}}h{\displaystyle h}
  3. ランダムな整数を選択します。r<n{\displaystyle r<n}
  4. 計算します。×0＝r2モッドn{\displaystyle x_{0}=r^{2}{\bmod {n}}}
  5. 1から私{\displaystyle i}t{\displaystyle t}
    1. 計算します。×私＝×私−12モッドn{\displaystyle x_{i}=x_{i-1}^{2}{\bmod {n}}}
    2. の最下位ビットを計算します。p私＝{\displaystyle p_{i}=}h{\displaystyle h}×私{\displaystyle x_{i}}
    3. 計算します。c私＝メートル私⊕p私{\displaystyle c_{i}=m_{i}\oplus p_{i}}
  6. 最後に、 を計算します。×t+1＝×t2モッドn{\displaystyle x_{t+1}=x_{t}^{2}{\bmod {n}}}

メッセージの暗号化は、すべての値と最終値を加えたものになります。 M{\displaystyle M}c私{\displaystyle c_{i}}×t+1{\displaystyle x_{t+1}}（c1、c2、…、ct、×t+1）{\displaystyle (c_{1},c_{2},\dots ,c_{t},x_{t+1})}

復号化

暗号化されたメッセージは、次のように秘密鍵を使用して復号化できます。 （c1、c2、…、ct、×）{\displaystyle (c_{1},c_{2},\dots ,c_{t},x)}（p、q）{\displaystyle (p,q)}

  1. 計算します。dp＝（（p+1）/4）t+1モッド（p−1）{\displaystyle d_{p}=((p+1)/4)^{t+1}{\bmod {(p-1)}}}
  2. 計算します。dq＝（（q+1）/4）t+1モッド（q−1）{\displaystyle d_{q}=((q+1)/4)^{t+1}{\bmod {(q-1)}}}
  3. 計算します。あなたp＝×dpモッドp{\displaystyle u_{p}=x^{d_{p}}{\bmod {p}}}
  4. 計算します。あなたq＝×dqモッドq{\displaystyle u_{q}=x^{d_{q}}{\bmod {q}}}
  5. 拡張ユークリッドの互除法を使用して、となるようなおよびを計算します。rp{\displaystyle r_{p}}rq{\displaystyle r_{q}}rpp+rqq=1{\displaystyle r_{p}p+r_{q}q=1}
  6. を計算します。これは暗号化で使用された値と同じになります（下の証明を参照）。次に、暗号化で使用されたのと同じ値のシーケンスを計算して、メッセージを復号化します。x0=uqrpp+uprqqmodn{\displaystyle x_{0}=u_{q}r_{p}p+u_{p}r_{q}q{\bmod {n}}}x0{\displaystyle x_{0}}xi{\displaystyle x_{i}}
  7. 1からi{\displaystyle i}t{\displaystyle t}
    1. 計算します。xi=xi−12modn{\displaystyle x_{i}=x_{i-1}^{2}{\bmod {n}}}
    2. の最下位ビットを計算します。pi={\displaystyle p_{i}=}h{\displaystyle h}xi{\displaystyle x_{i}}
    3. 計算します。mi=ci⊕pi{\displaystyle m_{i}=c_{i}\oplus p_{i}}
  8. 最後に、値をメッセージに再構成します。(m1,m2,…,mt){\displaystyle (m_{1},m_{2},\dots ,m_{t})}M{\displaystyle M}

例

と とします。そしてと です。6ビットのメッセージを暗号化するには、それを2つの3ビットブロック に分割します。つまり です。ランダムに を選択し、 を計算します。ここで、値を次のように計算します。 p=19{\displaystyle p=19}q=7{\displaystyle q=7}n=133{\displaystyle n=133}h=⌊log2(log2(133))⌋=3{\displaystyle h=\lfloor log_{2}(log_{2}(133))\rfloor =3}1010012{\displaystyle 101001_{2}}m1=1012,m2=0012{\displaystyle m_{1}=101_{2},m_{2}=001_{2}}t=2{\displaystyle t=2}r=36{\displaystyle r=36}x0=362mod133=99{\displaystyle x_{0}=36^{2}{\bmod {1}}33=99}ci{\displaystyle c_{i}}

x1=992mod133=92=10111002;p1=1002;c1=1012⊕1002=0012x2=922mod133=85=10101012;p2=1012;c2=0012⊕1012=1002x3=852mod133=43{\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad c_{1}=101_{2}\oplus 100_{2}=001_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad c_{2}=001_{2}\oplus 101_{2}=100_{2}\\x_{3}&=85^{2}{\bmod {1}}33=43\end{aligned}}}

つまり暗号化は です。 (c1=0012,c2=1002,x3=43){\displaystyle (c_{1}=001_{2},c_{2}=100_{2},x_{3}=43)}

復号するには、計算する

dp=53mod18=17dq=23mod6=2up=4317mod19=4uq=432mod7=1(rp,rq)=(3,−8) since 3⋅19+(−8)⋅7=1x0=1⋅3⋅19+4⋅(−8)⋅7mod133=99{\displaystyle {\begin{aligned}d_{p}&=5^{3}{\bmod {1}}8=17\\d_{q}&=2^{3}{\bmod {6}}=2\\u_{p}&=43^{17}{\bmod {1}}9=4\\u_{q}&=43^{2}{\bmod {7}}=1\\(r_{p},r_{q})&=(3,-8){\text{ since }}3\cdot 19+(-8)\cdot 7=1\\x_{0}&=1\cdot 3\cdot 19+4\cdot (-8)\cdot 7{\bmod {1}}33=99\\\end{aligned}}}

は暗号化アルゴリズムと同じ値を持つこと がわかります。したがって、復号は暗号化と同じように進行します。x0{\displaystyle x_{0}}

x1=992mod133=92=10111002;p1=1002;m1=0012⊕1002=1012x2=922mod133=85=10101012;p2=1012;m2=1002⊕1012=0012{\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad m_{1}=001_{2}\oplus 100_{2}=101_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad m_{2}=100_{2}\oplus 101_{2}=001_{2}\end{aligned}}}

正しさの証明

復号化アルゴリズムのステップ 6 で計算された値が、暗号化アルゴリズムのステップ 4 で計算された値と等しいことを示す必要があります。 x0{\displaystyle x_{0}}

暗号化アルゴリズムでは、 は を法とする平方剰余として構築されます。したがって、 も を法とする平方剰余であり、これを二乗して得られる他のすべての値も同様です。したがって、オイラーの基準より、となります。そして x0{\displaystyle x_{0}}n{\displaystyle n}p{\displaystyle p}xi{\displaystyle x_{i}}xi(p−1)/2≡1modp{\displaystyle x_{i}^{(p-1)/2}\equiv 1\mod {p}}

xt+1(p+1)/4≡(xt2)(p+1)/4)≡xt(p+1)/2≡xt(xt(p−1)/2)≡xtmodp{\displaystyle x_{t+1}^{(p+1)/4}\equiv (x_{t}^{2})^{(p+1)/4)}\equiv x_{t}^{(p+1)/2}\equiv x_{t}(x_{t}^{(p-1)/2})\equiv x_{t}\mod {p}}

同様に、

xt(p+1)/4≡xt−1modp{\displaystyle x_{t}^{(p+1)/4}\equiv x_{t-1}\mod {p}}

最初の式を累乗すると (p+1)/4{\displaystyle (p+1)/4}

xt+1((p+1)/4)2≡xt(p+1)/4≡xt−1modp{\displaystyle x_{t+1}^{((p+1)/4)^{2}}\equiv x_{t}^{(p+1)/4}\equiv x_{t-1}\mod {p}}

これを何度も 繰り返すと、t{\displaystyle t}

xt+1(p+1)/4)t+1≡x0modp{\displaystyle x_{t+1}^{(p+1)/4)^{t+1}}\equiv x_{0}\mod {p}}
xt+1dp≡up≡x0modp{\displaystyle x_{t+1}^{d_{p}}\equiv u_{p}\equiv x_{0}\mod {p}}

そして同様の議論により、次のことが証明できます。 xt+1dq≡uq≡x0modq{\displaystyle x_{t+1}^{d_{q}}\equiv u_{q}\equiv x_{0}\mod {q}}

最後に、 なので、を掛けて、 rpp+rqq=1{\displaystyle r_{p}p+r_{q}q=1}x0{\displaystyle x_{0}}

x0rpp+x0rqq=x0{\displaystyle x_{0}r_{p}p+x_{0}r_{q}q=x_{0}}

ここから、 と を法として となり、したがって となります。 uqrpp+uprqq≡x0{\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}}p{\displaystyle p}q{\displaystyle q}uqrpp+uprqq≡x0modn{\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}\mod {n}}

セキュリティと効率

ブルーム・ゴールドワッサー方式は、最終的なBBS状態と公開鍵 のみを与えられた場合、鍵ストリームビットを予測することが困難であることに基づき、意味的に安全です。しかし、 形式の暗号文は、攻撃者が選択された暗号文 の復号を要求する適応型選択暗号文攻撃に対して脆弱です。元の暗号文の復号はとして計算できます。 y{\displaystyle y}N{\displaystyle N}c→,y{\displaystyle {\vec {c}},y}m′{\displaystyle m^{\prime }}a→,y{\displaystyle {\vec {a}},y}m{\displaystyle m}a→⊕m′⊕c→{\displaystyle {\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}}

平文のサイズによっては、BGの計算コストは​​RSAよりも高くなる場合も低くなる場合もあります。ほとんどのRSAでは、暗号化時間を最小限に抑えるよう最適化された固定の暗号化指数が使用されるため、RSA暗号化は、ごく短いメッセージを除き、通常BGよりも高いパフォーマンスを発揮します。しかし、RSAの復号指数はランダムに分布するため、同じ長さの暗号文の場合、モジュラー指数演算ではBG復号と同程度の二乗/乗算が必要になることがあります。BGには、RSAでは複数の個別の暗号化が必要となる長い暗号文に対して、より効率的に拡張できるという利点があります。このような場合、BGの方がはるかに効率的になる可能性があります。

参考文献

  1. ^ RFC  4086セクション「6.2.2. Blum Blum Shubシーケンスジェネレータ」
  1. M. Blum、S. Goldwasser、「すべての部分情報を隠す効率的な確率的公開鍵暗号化方式」、Proceedings of Advances in Cryptology – CRYPTO '84、pp. 289–299、Springer Verlag、1985 年。
  2. メネゼス、アルフレッド、ヴァン・オーショット、ポール・C、ヴァンストーン、スコット・A. 『応用暗号ハンドブック』CRC Press、1996年10月。ISBN 0-8493-8523-7
「 https://en.wikipedia.org/w/index.php?title=Blum–Goldwasser_cryptosystem&oldid=1163480618」より取得