シャミールの秘密共有

シャミアの秘密分散法(SSS) は、グループ内で秘密情報(「秘密」) を配布するための効率的な秘密分散 アルゴリズムです。グループの定足数が協力して知識を共有しない限り、秘密は公開されません。これを実現するために、秘密は数学的に部分 (「シェア」) に分割され、十分な数のシェアが結合された場合にのみ秘密を再構成できます。SSS には情報理論的セキュリティの特性があり、攻撃者が一部のシェアを盗んだとしても、定足数のシェアを盗まない限り、攻撃者が秘密を再構築することは不可能です。

シャミアの秘密共有は、マスターシークレットへのアクセスキーを共有するために一部のアプリケーションで使用されます。

SSS は、分散形式で秘密を保護するために使用され、最もよく使用されるのは暗号化キーを保護することです。秘密は複数の共有に分割されますが、各共有からは秘密に関する情報は提供されません。

SSS によって保護された秘密を再構築するには、しきい値と呼ばれる一定数のシェアが必要です。しきい値以下のシェア数では、秘密に関する情報は得られません (完全な秘密性と呼ばれる特性)。この意味で、SSS はワンタイム パッドの一般化です(ワンタイム パッドは、2 つのシェアしきい値と合計 2 つのシェアを持つ SSS と見なすことができます)。^[1]

企業は金庫を安全に保護する必要があります。金庫のコードを知っている人が1 人だけだと、金庫を開ける必要があるときにコードが紛失したり、利用できなくなったりする可能性があります。コードを知っている人が複数いると、お互いを信頼できず、常に正直に行動できない可能性があります。

このような状況では、SSS を使用して、会社の許可された個人に配布される金庫のコードのシェアを生成することができます。各個人に与えられるシェアの最小しきい値と数は、許可された個人 (のグループ) のみが金庫にアクセスできるように選択できます。しきい値よりも少ないシェアが提示された場合、金庫を開くことはできません。

事故、強制、または反対行為により、一部の個人が自分の株式について誤った情報を提示する場合があります。正しい株式の合計が最小しきい値を満たさない場合、金庫はロックされたままになります。

シャミアの秘密分散法は、

• パスワードマネージャーのルートキーを復号するためのキーを共有する、^[2]
• 暗号化された電子メールにアクセスするためのユーザーキーを回復する^[3 ]
• マスターシークレットを再作成するために使用されるパスフレーズを共有し、それが暗号通貨ウォレットへのアクセスに使用されます。^[4]

SSSは有用な特性を持っていますが、弱点^[5]もあり、一部の用途には適していません。

便利なプロパティは次のとおりです。

1. 安全: この方式は情報理論的に安全です。
2. 最小: 各ピースのサイズは元のデータのサイズを超えません。
3. 拡張可能: 任意のしきい値に対して、既存の共有に影響を与えることなく、共有を動的に追加または削除できます。
4. 動的: 秘密を変更せずに、多項式を時々変更し (同じ自由項を維持)、参加者ごとに新しいシェアを構築することで、セキュリティを強化できます。
5. 柔軟性: 階層が重要な組織では、組織内での重要性に応じて、各参加者に異なる数の株式を発行できます。たとえば、しきい値が3の場合、社長は 3 つの株式を与えられれば単独で金庫を開けることができますが、それぞれ 1 つの株式を持つ 3 人の秘書は、金庫を開けるために株式を組み合わせる必要があります。

弱点は次のとおりです。

1. 検証可能な秘密共有なし: シェアの再構成プロセス中、SSS は使用されている各シェアの正確性を検証する方法を提供しません。検証可能な秘密共有は、株主が誠実であり、偽のシェアを提出していないことを確認することを目的としています。
2. 単一障害点: 秘密は、共有に分割されるときに 1 か所に存在し、再構成されるときにも 1 か所に存在する必要があります。これらは攻撃ポイントであり、マルチ署名などの他のスキームでは、これらの単一障害点の少なくとも 1 つが排除されます。

イスラエルの科学者アディ・シャミールが1979年に初めてこの計画を考案した。^[6]

この方式はラグランジュの補間定理、具体的には多項式上の点が 次数以下の多項式を一意に決定するという定理を利用します。たとえば、直線を定義するには2点、放物線を定義するには 3 点、3次曲線を定義するには 4 点、といった 具合です。${\displaystyle k}$${\displaystyle k-1}$

シャミアの秘密分散法は、有限体上の多項式補間に基づく理想的かつ完全なしきい値方式です。この方式では、秘密(たとえば、金庫への組み合わせ) を次のようにデータ断片(シェアと呼ばれる) に分割することを目的とします。 ${\displaystyle \left(k,n\right)}$${\displaystyle S}$${\displaystyle n}$${\displaystyle S_{1},\ldots ,S_{n}}$

1. 任意のシェアまたは複数のシェアに関する知識があれば、計算が可能になります。つまり、シェアの任意の組み合わせから秘密全体を再構築できます。${\displaystyle k}$${\displaystyle S_{i}}$${\displaystyle S}$${\displaystyle S}$${\displaystyle k}$
2. 任意のシェア数またはそれより少ないシェア数を知っていると、 の可能な値は、シェア数を知っている場合と同様に、最大 シェア数を知っている場合でも同じであるという意味で、完全に未確定のままになります。 シェア数より少ないシェア数では、秘密を再構築することはできません。${\displaystyle k-1}$${\displaystyle S_{i}}$${\displaystyle S}$${\displaystyle S}$${\displaystyle k-1}$${\displaystyle 0}$${\displaystyle S}$${\displaystyle k}$

の場合、秘密を再構築するにはすべてのシェアが必要になります。${\displaystyle n=k}$${\displaystyle S}$

秘密は有限体の元（ただし は生成されるシェアの数より大きい）として表せると仮定します。から元 をランダムに選択し、多項式 を構築します。曲線上の任意の点（たとえば）を計算して点 を見つけます。各参加者には点（多項式への非ゼロの入力とそれに対応する出力）が与えられます。^[7]これらのペアの任意のサブセットが与えられた場合、補間 を使用して を取得できます。これを行うための 1 つの可能な式は です。ここで、多項式上の点のリストは、形式 のペアとして与えられます。 は多項式 の最初の係数に等しいことに注意してください。 ${\displaystyle S}$${\displaystyle a_{0}}$ ${\displaystyle \mathrm {GF} (q)}$${\displaystyle q}$${\displaystyle n}$${\displaystyle k-1}$${\displaystyle a_{1},\cdots ,a_{k-1}}$${\displaystyle \mathrm {GF} (q)}$${\displaystyle f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}}$${\displaystyle n}$${\displaystyle i=1,\ldots ,n}$${\displaystyle \left(i,f\left(i\right)\right)}$${\displaystyle k}$${\displaystyle a_{0}}$${\displaystyle a_{0}=f(0)=\sum _{j=0}^{k-1}y_{j}\prod _{\begin{smallmatrix}m\,=\,0\\m\,\neq \,j\end{smallmatrix}}^{k-1}{\frac {x_{m}}{x_{m}-x_{j}}}}$${\displaystyle k}$${\displaystyle (x_{i},y_{i})}$${\displaystyle f(0)}$${\displaystyle f(x)}$

次の例は、基本的な考え方を示しています。ただし、この例の計算は、理解しやすくするために有限体演算ではなく整数演算を使用して行われていることに注意してください。したがって、以下の例は完全な秘密性を提供しておらず、シャミアの方式の適切な例ではありません。次の例で問題について説明します。

共有する秘密が 1234 であるとします。 ${\displaystyle (S=1234)}$

この例では、秘密は 6 つのシェアに分割されます。3 つのシェアのサブセットがあれば、秘密を再構築するのに十分です。数字はランダムに選択されます。166 と 94 とします。 ${\displaystyle (n=6)}$${\displaystyle (k=3)}$${\displaystyle k-1=2}$

これにより係数が得られる。秘密は${\displaystyle (a_{0}=1234;a_{1}=166;a_{2}=94),}$${\displaystyle a_{0}}$

したがって、秘密シェア（ポイント）を生成する多項式は次のようになります。

${\displaystyle f(x)=1234+166x+94x^{2}}$

多項式の 6 つの点は次のように構築されます。${\displaystyle D_{x-1}=(x,f(x))}$

${\displaystyle D_{0}=(1,1494);D_{1}=(2,1942);D_{2}=(3,2578);D_{3}=(4,3402);D_{4}=(5,4414);D_{5}=(6,5614)}$

スキームの各参加者は、異なるポイント（とのペア）を受け取ります。の代わりに が使用されるため、ポイントは から始まり、 から始まるわけではありません。が秘密である ため、これが必要です。${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle D_{x-1}}$${\displaystyle D_{x}}$${\displaystyle (1,f(1))}$${\displaystyle (0,f(0))}$${\displaystyle f(0)}$

秘密を再現するには、3つのポイントがあれば十分です

3 つのポイントの使用を検討してください。 ${\displaystyle \left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)}$

ラグランジュ基底多項式の計算:

${\displaystyle \ell _{0}(x)={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}\cdot {\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}}$

${\displaystyle \ell _{1}(x)={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot {\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}\cdot {\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5}$

${\displaystyle \ell _{2}(x)={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot {\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}\cdot {\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}}$

多項式補間の式を使用すると、次のようになります。 ${\displaystyle f(x)}$

${\displaystyle {\begin{aligned}f(x)&=\sum _{j=0}^{2}y_{j}\cdot \ell _{j}(x)\\[6pt]&=y_{0}\ell _{0}(x)+y_{1}\ell _{1}(x)+y_{2}\ell _{2}(x)\\[6pt]&=1942\left({\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}\right)+3402\left(-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5\right)+4414\left({\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}\right)\\[6pt]&=1234+166x+94x^{2}\end{aligned}}}$

秘密は自由係数であることを思い出してください。つまり、 となり、秘密が復元されました。 ${\displaystyle S=1234}$

ラグランジュ多項式を使用してソース多項式の係数を見つけるために多項式補間を使用すると、未使用の定数が計算されるため効率的ではありません。 ${\displaystyle S=f(0)}$

これを考慮すると、ラグランジュ多項式を使用して見つけるための最適化された式は次のように定義されます。 ${\displaystyle f(0)}$

${\displaystyle f(0)=\sum _{j=0}^{k-1}y_{j}\prod _{\begin{smallmatrix}m\,=\,0\\m\,\neq \,j\end{smallmatrix}}^{k-1}{\frac {x_{m}}{x_{m}-x_{j}}}}$

上で示した方法の簡略版は有限体演算ではなく整数演算を使用して機能しますが、セキュリティ上の問題があります。イブは見つけたものごと にに関する情報を取得してしまうのです。${\displaystyle S}$${\displaystyle D_{i}}$

彼女が 2 つの点と を見つけたとします。彼女はまだ点を持っていないので、理論的には についてこれ以上の情報を得ることはできないはずです。しかし、彼女は 2 つの点からの情報と公開情報を組み合わせることができます: 。そうすることで、イブは次の代数計算を実行できます。 ${\displaystyle D_{0}=(1,1494)}$${\displaystyle D_{1}=(2,1942)}$${\displaystyle k=3}$${\displaystyle S}$${\displaystyle n=6,k=3,f(x)=a_{0}+a_{1}x+\cdots +a_{k-1}x^{k-1},a_{0}=S,a_{i}\in \mathbb {Z} }$

1. の式に との値を入力します。${\displaystyle f(x)}$${\displaystyle S}$${\displaystyle k:f(x)=S+a_{1}x+\cdots +a_{k-1}x^{k-1}\Rightarrow {}f(x)=S+a_{1}x+a_{2}x^{2}}$
2. （1）にとの値を記入する。${\displaystyle D_{0}}$${\displaystyle x}$${\displaystyle f(x):1494=S+a_{1}1+a_{2}1^{2}\Rightarrow {}1494=S+a_{1}+a_{2}}$
3. （1）にとの値を記入する。${\displaystyle D_{1}}$${\displaystyle x}$${\displaystyle f(x):1942=S+a_{1}2+a_{2}2^{2}\Rightarrow {}1942=S+2a_{1}+4a_{2}}$
4. (3)-(2)を引くと、これを書き直すことができる。${\displaystyle (1942-1494)=(S-S)+(2a_{1}-a_{1})+(4a_{2}-a_{2})\Rightarrow {}448=a_{1}+3a_{2}}$${\displaystyle a_{1}=448-3a_{2}}$
5. ここで、イブは(4)の結果を(2)に置き換えることができます。これにより、Sが偶数であるという情報が得られます。${\displaystyle 1494=S+(448-3a_{2})+a_{2}\Rightarrow {}S=1046+2a_{2}}$

上記の攻撃は、多項式が構築された方法によって多項式が取ることのできる値に対する制約を悪用します。多項式の係数は整数でなければならず、スキームで使用される各座標で評価されるときに多項式は値として整数を取らなければなりません。これにより、シェア数が より少ない場合、結果の秘密を含む未知のポイントでの可能な値が減ります。 ${\displaystyle k}$

この問題は、有限体演算を使用することで解決できます。有限体は常にサイズ で、 は素数、は正の整数です。体のサイズはを満たし、秘密の可能な値の数よりも大きくなければなりませんが、後者の条件は、秘密をより小さな秘密値に分割し、それぞれにスキームを適用することで回避できます。以下の例では、素体 (つまりr = 1) を使用します。図は、有限体上の多項式曲線を示しています。 ${\displaystyle q=p^{r}}$${\displaystyle p}$${\displaystyle r}$${\displaystyle q}$${\displaystyle q>n}$${\displaystyle q}$

実際には、これは小さな変更にすぎません。フィールドの位数q (つまり、フィールドが持つ値の数) は、参加者の数と秘密が取る値の数よりも大きくなるように選択する必要があります。多項式を含むすべての計算は、整数ではなくフィールド (この例ではp を法として計算され、 は素数と見なされます)で計算する必要があります。フィールドの選択と、このフィールドの値への秘密のマッピングは、どちらも公に知られているものと見なされます。 ${\displaystyle a_{0}=S}$${\displaystyle p=q}$

この例では、 を選択すると、多項式は となり、点が与えられます。${\displaystyle p=1613}$${\displaystyle f(x)=1234+166x+94x^{2}{\bmod {1613}}}$${\displaystyle (1,1494);(2,329);(3,965);(4,176);(5,1188);(6,775)}$

今回、イブは（ポイントを獲得するまで）を見つけても何の情報も得られません。 ${\displaystyle D_{x}}$${\displaystyle k}$

再び、イブがと を見つけ、公開情報が であると仮定します。前の攻撃を試みた場合、イブは次のことができます。 ${\displaystyle D_{0}=\left(1,1494\right)}$${\displaystyle D_{1}=\left(2,329\right)}$${\displaystyle n=6,k=3,p=1613,f(x)=a_{0}+a_{1}x+\dots +a_{k-1}x^{k-1}\mod {p},a_{0}=S,a_{i}\in \mathbb {N} }$

1. 式にとおよびの値を入力します。${\displaystyle f(x)}$${\displaystyle S}$${\displaystyle k}$${\displaystyle p}$${\displaystyle f(x)=S+a_{1}x+\dots +a_{3-1}x^{3-1}\mod 1613}$
2. （1）にとの値を記入する。${\displaystyle D_{0}}$${\displaystyle x}$${\displaystyle f(x):1494\equiv S+a_{1}1+a_{2}1^{2}{\pmod {1613}}\Rightarrow {}1494\equiv S+a_{1}+a_{2}{\pmod {1613}}}$
3. （1）にとの値を記入する。${\displaystyle D_{1}}$${\displaystyle x}$${\displaystyle f(x):1942\equiv S+a_{1}2+a_{2}2^{2}{\pmod {1613}}\Rightarrow {}1942\equiv S+2a_{1}+4a_{2}{\pmod {1613}}}$
4. (3)-(2)を引くと、これを次のように書き直す。${\displaystyle (1942-1494)\equiv (S-S)+(2a_{1}-a_{1})+(4a_{2}-a_{2}){\pmod {1613}}\Rightarrow {}448\equiv a_{1}+3a_{2}{\pmod {1613}}}$${\displaystyle a_{1}\equiv 448-3a_{2}{\pmod {1613}}}$

には 個の値が考えられます。 は常に 3 ずつ減少することがわかっているので、が で割り切れる場合は と結論付けることができます。しかし、は素数なので、これを結論付けることはできません。したがって、有限体を使用すると、この攻撃の可能性を回避できます。 ${\displaystyle p}$${\displaystyle a_{1}}$${\displaystyle [448,445,442,\ldots ]}$${\displaystyle p}$${\displaystyle 3}$${\displaystyle a_{1}\in [1,4,7,\ldots ]}$${\displaystyle p}$

また、Eve は と結論付けることができますが、上記の整数演算の例とは異なり、モジュラー演算の「ラップアラウンド」動作により「S は偶数である」という漏洩が防止されるため、追加情報は提供されません。 ${\displaystyle S\equiv 1046+2a_{2}{\pmod {1613}}}$

コードをより明確にするため、ここでは素体を使用します。実際には、便宜上、より小さなバイナリ体を使用して構築されたスキームを、セキュリティを損なうことなく、秘密のビットの小さな部分文字列に個別に適用できます (バイト単位の適用の場合は GF(256) など)。フィールドのサイズはシェアの数よりも大きくなければならないという厳格な条件は、依然として尊重する必要があります (たとえば、シェアの数が 255 を超える可能性がある場合は、フィールド GF(256) を GF(65536) などに置き換えることができます)。

「""
シャミアの秘密分散法の次の Python 実装は、
CC0 および OWFa の条件の下でパブリック ドメインにリリースされています: 
https://creativecommons.org/publicdomain/zero/1.0/ 
http://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0

使用方法については、下の行を参照してください。Python 2 および 3 でテスト済みです。
"""

 __future__ からdivisionをインポートします __future__からprint_functionをインポートします
   

 ランダム
インポート 関数ツールのインポート

#12位 メルセンヌプライム
_PRIME  =  2  **  127  -  1

_RINT  = 関数ツール。部分的(ランダム. SystemRandom () . randint ,  0 )

def  _eval_at ( Poly ,  x ,  prime ): 
""" 以下の make_random_shares でシャミール プールを生成するために使用される、x での多項式 (係数タプル) を評価します    。    """ accum = 0 for coeff in reversed ( poly ): accum *= x accum += coeff accum %=素数return accum    


      
       
          
          
          
     

def  make_random_shares ( secret ,  minimum ,  shares ,  prime = _PRIME ): 
"""    指定された secret のランダム シャミア プールを生成し、share points を返します。    """ if minimum > shares : raise ValueError ( "プール secret は回復不可能です。" ) poly = [ secret ] + [ _RINT ( prime - 1 ) for i in range ( minimum - 1 )] points = [( i , _eval_at ( poly , i , prime )) for i in range ( 1 , shares + 1 )] return points    


       
         
                
         
                    
     

def  _extended_gcd ( a ,  b ): 
"""     p を法とする整数の除算は、    分母を法として逆数を求め、その逆数を分子に掛けることを意味します    (注: A の逆数は A*B % p == 1 となる B です)。これは、    拡張ユークリッド互除法で計算できます    http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation     """ x = 0 last_x = 1 y = 1 last_y = 0 while b != 0 : quot = a // b a , b = b , a % b x , last_x = last_x - quot * x , x y , last_y = last_y - quot * y , y return last_x , last_y    






      
      
      
      
       
            
              
                
                
      

def  _divmod ( num ,  den ,  p ): 
"""素数 p の num / den を計算します。    

    これを説明すると、結果は次のようになります: 
    den * _divmod(num, den, p) % p == num 
    """ 
    inv ,  _  =  _extended_gcd ( den ,  p ) 
    return  num  *  inv

def  _lagrange_interpolate ( x ,  x_s ,  y_s ,  p ): 
"""     n 個の (x, y) ポイントが与えられた場合、指定された x の y 値を求めます。k    ポイントは k 次までの多項式を定義します。    """ k = len ( x_s ) assert k == len ( set ( x_s )), "ポイントは一意である必要があります" def PI ( vals ): # 大文字の PI -- 入力の積accum = 1 for v in vals : accum *= v return accum nums = [] # 不正確な除算を避けるdens = [] for i in range ( k ): others = list ( x_s ) cur = others . pop ( i ) nums . append ( PI ( x - o for o in others )) dens . append ( PI ( cur - o for o in others )) den = PI ( dens ) num = sum ([ _divmod ( nums [ i ] * den * y_s [ i ] % p , dens [ i ], p ) for i in range ( k )]) return ( _divmod ( num , den , p ) + p ) % p    



      
        
       
          
           
              
         
        
      
       
          
          
              
              
      
              
                  
           

def  recover_secret ( shares ,  prime = _PRIME ): 
"""    共有ポイント    (多項式上のポイント (x,y)) から秘密を回復します。    """ if len ( shares ) < 3 : raise ValueError ( "少なくとも 3 つの共有が必要です" ) x_s , y_s = zip ( * shares ) return _lagrange_interpolate ( 0 , x_s , y_s , prime )    



       
         
       
        

def  main (): 
"""メイン関数""" secret = 1234 shares = make_random_shares ( secret 、minimum = 3 、shares = 6 )    
      
        

    print ( 'Secret: ' , 
          secret ) 
    print ( 'Shares:' ) 
    if  shares : 
        for  share  in  shares : 
            print ( ' ' ,  share )

    print ( 'シークレットは最小のシェアのサブセットから回復されました: ' , 
          recover_secret ( shares [ : 3 ])) 
    print ( 'シークレットは別の最小のシェアのサブセットから回復されました: ' , 
          recover_secret ( shares [ - 3 :]))

 __name__  ==  '__main__'の場合: 
    main ()

• 秘密共有
• 安全なマルチパーティ計算
• ラグランジュ多項式
• 準同型秘密分散– シンプルな分散投票プロトコル
• 二人ルール
• 部分的なパスワード

• ドーソン、E.; ドノバン、D. (1994)、「シャミアの秘密共有スキームの広さ」、コンピュータ＆セキュリティ、13：69-78、doi：10.1016/0167-4048（94）90097-3。
• Benzekki, K. (2017)。「安全なマルチクラウド ストレージのための検証可能な秘密共有アプローチ」。ユビキタス ネットワーキング。コンピュータ サイエンスの講義ノート。第 10542 巻。カサブランカ: Springer。pp. 225–234。doi : 10.1007/978-3-319-68179-5_20。ISBN 978-3-319-68178-8。。

• Crypto++ライブラリにおけるシャミアの秘密分散
• シャミアの秘密分散法 (ssss) – GNU GPL実装
• sharedsecret – Goでの実装
• s4 - HashiCorp のシャミア秘密分散アルゴリズムを利用したオンライン シャミア秘密分散ツール
• Shamir39 - iancoleman.io の Web バージョン
• kn Secrets - シャミールの秘密共有を可能な限りアクセスしやすくすることを目的とした専用ウェブサイト上のウェブバージョン