銀行の金庫を保護する必要があるシナリオを考えてみましょう。 鍵がなければ絶対に難攻不落だと考えられており、仕事の初日に鍵が渡されます。 目標は、キーを安全に保管することです。

必要に応じてストレージにアクセスできるように、キーを常に持ち歩くことにしたとします。 ただし、ストレージを開くたびに物理的な存在が必要になるため、このようなソリューションは実際にはうまく拡張できないことがすぐにわかります。 約束された休暇はどうなりますか？ さらに、質問はさらに恐ろしいものです。唯一の鍵を紛失した場合はどうなりますか?

あなたは休暇を念頭に置いて、キーのコピーを作成し、それを別の従業員に託すことにしました。 ただし、これも理想的ではないことは理解されています。 鍵の数が XNUMX 倍になれば、鍵の盗難の可能性も XNUMX 倍になります。

必死になって、あなたは複製を破棄し、元のキーを半分に分割することにしました。 ここで、鍵を集めて金庫を開けるには、鍵の破片を持っている XNUMX 人の信頼できる人が物理的にその場に立ち会わなければならないと考えるかもしれません。 これは、泥棒は XNUMX つの鍵を盗む必要があることを意味し、これは XNUMX つの鍵を盗むよりも XNUMX 倍困難です。 ただし、誰かが半分のキーを紛失した場合、完全なキーを回復することはできないため、このスキームは XNUMX つのキーよりも優れているわけではないことがすぐにわかります。

この問題は一連の追加のキーとロックで解決できますが、このアプローチではすぐに次のことが必要になります。 много 鍵と錠前。 あなたは、セキュリティが XNUMX 人の担当者に完全に依存しないようにキーを共有するのが理想的な設計であると判断します。 また、XNUMX つのフラグメントが失われた場合 (または人が休暇に入った場合) に、キー全体が機能し続けるように、フラグメントの数に何らかのしきい値が必要であると結論付けています。

秘密を共有する方法

このタイプの鍵管理スキームは、1979 年にアディ・シャミールが著書を出版したときに考えられました。 「秘密を共有する方法」。 この記事では、いわゆる 秘密の値 (暗号キーなど) を効率的に分割するためのしきい値スキーム。 部品。 そして、少なくともそのときだけ、 の パーツが組み立てられているので、簡単にシークレットを復元できます .

セキュリティの観点から見ると、このスキームの重要な特性は、少なくとも次の知識がない限り、攻撃者は絶対に何も知らないはずであるということです。 部品。 存在感さえも 部分には情報を提供しないでください。 このプロパティを セマンティックセキュリティ.

多項式補間

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

2 つの点を介して、XNUMX 次の多項式を無限に描くことができます。その中から XNUMX つだけを選択するには、XNUMX 番目の点が必要です。 図： ウィキペディア

次数 XNUMX の多項式を考えてみましょう。 。 この関数をグラフにプロットしたい場合、ポイントは何個必要ですか? これは直線を形成する一次関数であるため、少なくとも XNUMX つの点が必要であることがわかっています。 次に、次数 XNUMX の多項式関数を考えます。 。 これは二次関数であるため、グラフをプロットするには少なくとも XNUMX つの点が必要です。 XNUMX 次の多項式はどうでしょうか? 少なくともXNUMX点。 などなど。

このプロパティの本当に素晴らしい点は、多項式関数の次数を考慮すると、少なくとも 点があれば、この多項式関数の追加の点を導出できます。 これらの追加点の外挿を「外挿」と呼びます。 多項式補間.

秘密をでっち上げる

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

多項式は次の形式になります。 どこ и — ランダムに選択された正の整数。 次数を使用して多項式を構築しているだけです , ここで、自由係数  - これは私たちの秘密です 、および後続のそれぞれについて ランダムに選択された正の係数が存在します。 元の例に戻って次のように仮定すると、 、関数を取得します .

この時点で、接続することでフラグメントを生成できます。 一意の整数 どこ （それは私たちの秘密だからです）。 この例では、しきい値 XNUMX で XNUMX つのフラグメントを分散したいため、ポイントをランダムに生成します。 そして、鍵の管理者である XNUMX 人の信頼できる人物にそれぞれ XNUMX ポイントを送ります。 私たちは人々にもそれを知らせます 、これは公開情報とみなされ、回復に必要であるため .

秘密を取り戻す

多項式補間の概念と、それがシャミールのしきい値スキームの基礎となる方法についてはすでに説明しました。 。 XNUMX人の管財人のうちXNUMX人が復元を希望する場合 、補間するだけで済みます 独自のポイントを備えています。 これを行うために、彼らは自分のポイントを決定できます 次の式を使用してラグランジュ補間多項式を計算します。 数学よりもプログラミングの方がわかりやすい場合、pi は本質的に演算子です。 for、すべての結果を乗算します。シグマは次のようになります。 for、すべてを合計します。

に 次のように解決して、元の多項式関数を返すことができます。

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

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

シャミールの基本的なアイデアをうまく​​適用しましたが、 、これまで無視してきた問題が残されています。 多項式関数は安全でない整数演算を使用しています。 攻撃者が関数のグラフ上で追加のポイントを取得するたびに、他のポイントの可能性が少なくなることに注意してください。 整数演算を使用して多項式関数の点の数を増やしてプロットすると、これを自分の目で確認できます。 これは、私たちが定めたセキュリティ目標に対して逆効果です。なぜなら、攻撃者は少なくとも情報を得るまではまったく何も知らないはずだからです。 断片。

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

攻撃者はその後、 、数えます :

定義したので、 ランダムに選択された正の整数として、可能な数は限られています 。 攻撃者はこの情報を使用して推測することができます 、5 より大きい値であれば何でもよいので、 ネガティブ。 私たちが決定したので、これは真実であることがわかります

その後、攻撃者は考えられる値を計算できます。 交換 в :

オプションが限られているため、 値の選択と確認がいかに簡単であるかがわかります。 。 ここでの選択肢は XNUMX つだけです。

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

この脆弱性を解消するために、Shamir 氏はモジュラー演算を使用することを提案しています。 на どこ и — すべての素数のセット。

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

このスキームを前の例に適用し、次を使用することで、これによってスキームのセキュリティがどのように向上するかを実証できます。 。 新しい多項式関数 、そして新たなポイント 。 これで、キーキーパーは再び多項式補間を使用して関数を再構築できるようになりました。今回のみ、加算と乗算の演算にはモジュロ リダクションを伴う必要があります。 （例えば ).

この新しい例を使用して、攻撃者がこれらの新しいポイントのうち XNUMX つを学習したと仮定します。 、および公開情報 。 今回、攻撃者は、持っているすべての情報に基づいて、次の関数を出力します。  すべての正の整数の集合であり、 は弾性係数を表します .

今、攻撃者は再び発見しました 、計算します :

それから彼はもう一度試みます 交換 в :

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

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

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

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

もう XNUMX つの問題は、フラグメントの長さが対応するシークレットの長さに等しいため、シークレットの長さを簡単に判断できることです。 この問題は簡単な方法で解決できます パディング 固定長までの任意の数値を含むシークレット。

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

Демо

На このページ Shamir の秘密共有スキームのインタラクティブなデモンストレーションがあります。 ライブラリを基にしたデモンストレーション ssss-js、それ自体は人気のあるプログラムの JavaScript ポートです。 SSSS。 大きな値を計算することに注意してください , и しばらく時間がかかる場合があります。

出所： habr.com