銀行の金庫室のセキュリティを確保する必要のあるシナリオを考えてみましょう。勤務初日に渡される鍵がなければ絶対に侵入できないと考えられています。あなたの目標は鍵を安全に保つことです。

常に鍵を携帯し、必要に応じて金庫へのアクセスを許可することにしたとします。しかし、ストレージを開くたびにユーザーが物理的に存在する必要があるため、このソリューションは実際には拡張性に欠けることがすぐにわかります。約束されていた休暇はどうなったのですか?さらにもっと恐ろしい疑問は、もし唯一の鍵を紛失したらどうなるかということです。

休暇を考えて、鍵のコピーを作成し、別の従業員に預けることにしました。しかし、これも理想的ではないことはご理解いただけると思います。鍵の数を倍にすると、鍵が盗まれる可能性も倍になります。

困り果てて、複製したキーを破棄し、元のキーを半分に分割することにしました。さて、鍵を組み立てて金庫を開けるには、鍵の断片を持った信頼できる 2 人が物理的に存在する必要があると考えます。つまり、泥棒は 2 つの破片を盗まなければならないことになり、これは 1 つの鍵を盗むよりも 2 倍困難です。しかし、すぐにこの方式は 1 つのキーだけを使用する場合と大差ないことに気付きます。なぜなら、誰かがキーの半分を紛失した場合、キー全体を回復することはできないからです。

この問題は追加の鍵と錠前で解決できるが、このアプローチではすぐに много 鍵と錠前。セキュリティが 1 人の人物に完全に依存しないように、キーを分割するのが理想的な方式であると判断しました。また、1 つのフラグメントが失われた場合 (またはユーザーが休暇に出かけた場合) でもキー全体が機能し続けるように、フラグメントの数に何らかのしきい値が必要であると結論付けます。

秘密を共有する方法

このタイプの鍵管理方式は、1979年にアディ・シャミールが論文を発表したときに考案されました。 「秘密を共有する方法」。この記事では、いわゆる 秘密値（例えば暗号鍵）を効率的に分割するための閾値方式 部品。そして、少なくとも の 部品が集められれば、秘密を復元するのは簡単だ .

セキュリティの観点から、この方式の重要な特性は、攻撃者が少なくとも 部品。存在さえも 部品はいかなる情報も提供しない必要があります。このプロパティを セマンティックセキュリティ.

多項式補間

シャミールの閾値スキーム コンセプトに基づいて構築 多項式補間。この概念に馴染みがない方のために言っておきますが、実は非常に簡単です。実際、グラフ上に点を描いて、それを直線や曲線で結んだことがあるなら、すでにそれを使用していることになります。

2 点を通る XNUMX 次多項式は無制限に描くことができます。唯一のものを選択するには、XNUMX 番目のポイントが必要です。図： ウィキペディア

1次の多項式を考えてみましょう。 。この関数をグラフにプロットする場合、いくつの点が必要ですか?そうですね、これは直線を形成する線形関数なので、少なくとも 2 つの点が必要であることはわかっています。次に、2次の多項式関数を考えます。 。これは二次関数なので、グラフをプロットするには少なくとも 3 つの点が必要です。 3次の多項式はどうでしょうか?少なくとも4点。などなど。

この性質の本当に素晴らしいところは、多項式関数の次数と少なくとも ポイントを使用すると、この多項式関数の追加ポイントを導出できます。これらの追加点の外挿を 多項式補間.

秘密をでっち上げる

シャミールの巧妙な計画がここで機能していることに、すでにお気づきかもしれません。私たちの秘密は - です 。私たちは変革できる グラフ上の点に そして次数を持つ多項式関数を考え出す 、これはこの点を満たしています。思い出してみましょう は必要なフラグメントのしきい値となるため、しきい値を 3 つのフラグメントに設定する場合は、次数 2 の多項式関数を選択する必要があります。

多項式は次のようになります どこ и — ランダムに選択された正の整数。私たちは次数を持つ多項式を構築しているだけです 、自由係数は  - これは私たちの秘密です 、そしてそれに続く各 メンバーはランダムに選択された正の係数を持ちます。元の例に戻って、 すると、関数 .

この段階では、接続することでフラグメントを生成できます 一意の整数 どこ （それは私たちの秘密だから）。この例では、閾値3で4つのフラグメントを配布したいので、ランダムにポイントを生成します。 そして、鍵の保管者である信頼できる 4 人の人々にそれぞれ 1 ポイントを送ります。また、私たちは人々に次のことを伝えています これは公開情報とみなされ、回復に必要であるため .

秘密の復元

多項式補間の概念とそれがシャミアの閾値方式の基礎となる方法については既に説明しました。 。 4人の受託者のうち3人が復元を希望する場合 補間するだけでいい 独自のユニークなポイントを備えています。これを行うには、ポイントを定義することができます 次の式を使用してラグランジュ補間多項式を計算します。数学よりもプログラミングを理解しているなら、πは本質的に演算子である。 for全ての結果を掛け合わせたもので、シグマは for、これらすべてをまとめたものです。

に これを次のように解くと、元の多項式関数が復元されます。

私たちはそれを知っているので、 、 回復 それは簡単に実行されます:

安全でない整数演算の使用

シャミールの基本的な考え方をうまく応用したが 、私たちは今まで無視してきた問題を抱えたままになっています。多項式関数では安全でない整数演算が使用されています。攻撃者が関数グラフ上で取得する追加ポイントごとに、他のポイントの可能性が少なくなることに注意してください。整数演算を使用して多項式関数の点の数が増加するグラフをプロットすると、これを自分の目で確認できます。これは、私たちが掲げたセキュリティ目標とは逆効果です。なぜなら、攻撃者は少なくとも 断片。

整数演算方式がいかに弱いかを示すために、攻撃者が2つのポイントを持っているシナリオを考えてみましょう。 そして公開情報を知っている 。この情報から彼は推測できる 2に等しいので、既知の値を式に代入します。 и .

攻撃者は、 数えて :

定義したので ランダムに選択された正の整数であるため、可能な数は限られている。 。この情報を使って攻撃者は 5より大きい値であれば問題ありません ネガティブ。これは真実であることが判明しました。

攻撃者は、可能な値を計算できる。 交換 в :

選択肢が限られているため、 値の選択と確認がいかに簡単かが分かります 。ここには選択肢が5つしかありません。

安全でない整数演算の問題を解決する

この脆弱性を排除するために、シャミールはモジュラー演算を使用することを提案している。 на どこ и — すべての素数の集合。

モジュラー演算がどのように機能するかを簡単に思い出してみましょう。針の付いた時計はおなじみの概念です。彼女は時計を使っているが 。時針が12時を過ぎるとすぐにXNUMX時に戻ります。このシステムの興味深い特性は、時計を見るだけでは時針が何回回転したかを推測できないことです。しかし、時針がXNUMXをXNUMX回通過したことが分かれば、簡単な式を使って経過した時間数を完全に決定することができます。 どこ  - これは私たちの除数です（ここでは ),  — これは係数（余りのない除数が元の数に何倍になるか、ここでは ）、および  — これは剰余であり、通常はモジュロ演算子を呼び出すことによって返されます（ここでは ）。これらの値をすべて知ることで、次の方程式を解くことができます。 しかし、係数を忘れると、元の値を復元できなくなります。

この方式がいかにセキュリティを向上させるかは、前の例にこの方式を適用し、 。新しい多項式関数 、そして新しいポイント 。これで、キーキーパーは再び多項式補間を使用して関数を再構築できますが、今回は加算と乗算の演算にモジュロ削減が伴う必要があります。 （例えば ).

この新しい例を使って、攻撃者がこれらの新しいポイントのうちの2つを学んだと仮定します。 、および公開情報 。今回、攻撃者は、自分が持っているすべての情報に基づいて、以下の関数を導き出します。  — すべての正の整数の集合、そして モジュールの係数を表す .

今、攻撃者は再びそれを見つけた 計算して :

そして彼は再び撤退を試みる 交換 в :

今回彼は深刻な問題を抱えている。式に値がありません , и 。これらの変数の組み合わせは無限にあるため、追加情報を得ることはできません。

セキュリティに関する考慮事項

シャミアの秘密分散法は 情報理論の観点から見たセキュリティ。これは、無制限の計算能力を持つ攻撃者に対しても数学が耐性があることを意味します。ただし、このスキームにはまだいくつかの既知の問題が残っています。

例えば、シャミールの計画は チェックされた断片つまり、人々は自由に偽の断片を提示し、正しい秘密の復元を妨害することができます。十分な情報を持つ敵対的なフラグメントキーパーは、変更することで別のフラグメントを生成することさえできる。 あなたの判断で。この問題は、 検証可能な秘密共有方式フェルドマン計画など。

もう 1 つの問題は、どのフラグメントの長さも対応する秘密の長さに等しいため、秘密の長さを簡単に判断できることです。この問題は簡単に解決できる 詰め物 固定長までの任意の数字を持つ秘密。

最後に、セキュリティ上の懸念は、この計画自体の範囲を超えて広がる可能性があることに注意することが重要です。実際の暗号化アプリケーションでは、攻撃者がアプリケーションの実行時間、キャッシュ、クラッシュなどから有用な情報を抽出しようとするサイドチャネル攻撃の脅威がしばしば存在します。これが懸念される場合は、開発中に、定数時間関数やルックアップ、メモリがディスクにフラッシュされるのを防ぐなどの保護手段の使用、およびこの記事の範囲を超えるその他の多くの事項について慎重に検討する必要があります。

Демо

На このページ シャミアの秘密分散方式のインタラクティブなデモンストレーションがあります。このデモンストレーションは図書館に基づいて行われた。 ssss-jsは、それ自体が人気のあるプログラムのJavaScriptポートです SSSS。大きな値を計算する場合は注意してください , и 少し時間がかかるかもしれません。

出所： habr.com