النظر في السيناريو عندما يكون ذلك ضروريا لضمان سلامة قبو البنك. يعتبر منيعًا تمامًا بدون مفتاح ، والذي يُعطى لك في اليوم الأول من العمل. هدفك هو حفظ المفتاح بأمان.

لنفترض أنك قررت الاحتفاظ بالمفتاح معك طوال الوقت ، مما يتيح الوصول إلى المتجر حسب الحاجة. لكنك ستدرك بسرعة أن هذا الحل في الممارسة العملية لا يتدرج بشكل طبيعي ، لأنه في كل مرة تحتاج فيها إلى وجودك المادي لفتح المستودع. ماذا عن الإجازات التي وعدت بها؟ بالإضافة إلى ذلك ، فإن السؤال مخيف أكثر: ماذا لو فقدت مفتاحًا واحدًا؟

مع فكرة الإجازة ، قررت إنشاء نسخة من المفتاح وتكليفه بموظف آخر. ومع ذلك ، أنت تفهم أن هذا ليس مثاليًا أيضًا. بمضاعفة عدد المفاتيح ، تضاعفت أيضًا إمكانيات سرقة المفاتيح.

يائسة ، يمكنك تدمير مكررة وتقرر تقسيم المفتاح الأصلي إلى النصف. الآن ، حسب اعتقادك ، يجب أن يكون شخصان موثوقان بهما شظايا أساسية حاضرين فعليًا لجمع المفتاح وفتح المتجر. هذا يعني أن اللص يحتاج إلى سرقة شريحتين ، وهو ضعف صعوبة سرقة مفتاح واحد. ومع ذلك ، ستدرك قريبًا أن هذا المخطط ليس أفضل بكثير من مفتاح واحد فقط ، لأنه إذا فقد شخص ما نصف المفتاح ، فلن يمكن استعادة المفتاح بالكامل.

يمكن حل المشكلة من خلال سلسلة من المفاتيح والأقفال الإضافية ، ولكن مع هذا النهج ، ستحتاج بسرعة إلى الكثير من المفاتيح والأقفال. أنت تقرر أنه في مخطط مثالي ، تحتاج إلى تقسيم المفتاح حتى لا يعتمد الأمان بالكامل على شخص واحد. أنت أيضًا تستنتج أنه يجب أن يكون هناك حد معين لعدد الأجزاء ، بحيث إذا فقدت جزء واحد (أو إذا ذهب شخص ما في إجازة) ، فسيظل المفتاح بأكمله وظيفيًا.

كيفية مشاركة السر

تم التفكير في هذا النوع من مخطط الإدارة الرئيسية من قبل عدي شامير في عام 1979 عندما نشر عمله كيف تشارك سرًا . يشرح المقال بإيجاز ما يسمى $$$(ك ، ن) دولا$ مخطط الحد الفاصل لتقسيم القيمة السرية بشكل فعال (على سبيل المثال ، مفتاح التشفير) إلى $$$ن$ أجزاء. ثم ، ومتى وفقط على الأقل $$$ك$ من $$$ن$ أجزاء تجميعها ، يمكنك بسهولة استعادة السرية $$$S$ .

من الناحية الأمنية ، من الخصائص المهمة لهذا المخطط أن المهاجم يجب ألا يعرف أي شيء على الإطلاق إذا لم يكن لديه على الأقل $$$ك$ أجزاء. حتى توافر $$$ك - 1 دولا$ أجزاء لا ينبغي أن تعطي أي معلومات. نحن نسمي هذا العقار الدلالي الأمن .

متعدد الحدود الاستيفاء

مخطط عتبة شامير $$$(ك ، ن) دولا$ مبنية حول مفهوم الاستيفاء متعدد الحدود . إذا لم تكن على دراية بهذا المفهوم ، فهو في الواقع بسيط للغاية. بشكل عام ، إذا قمت برسم نقاط على مخطط ما ، ثم قمت بتوصيلها بخطوط أو منحنيات ، فإنك تستخدمها بالفعل!


يمكن رسم عدد غير محدود من كثيرات الحدود من الدرجة الثانية من خلال نقطتين: لاختيار النقطة الوحيدة ، تحتاج إلى نقطة ثالثة. التوضيح: ويكيبيديا

النظر في كثير الحدود مع درجة واحدة ، $$$f (x) = x + 2$ . إذا كنت ترغب في رسم هذه الوظيفة على الرسم البياني ، فكم عدد النقاط التي تحتاجها؟ حسنًا ، نحن نعلم أن هذه وظيفة خطية تشكل خطًا وبالتالي هناك حاجة إلى نقطتين على الأقل. بعد ذلك ، فكر في وظيفة متعددة الحدود من الدرجة الثانية ، $$$f (x) = x ^ 2 + 2x + 1$ . هذه هي وظيفة من الدرجة الثانية ، لذلك لا بد من ثلاث نقاط على الأقل لبناء الرسم البياني. ماذا عن كثير الحدود مع الدرجة الثالثة؟ على الأقل أربع نقاط. وهلم جرا وهكذا دواليك.

الشيء الرائع حقًا في هذه الخاصية هو ، بالنظر إلى درجة وظيفة كثير الحدود ، وعلى الأقل $$ نقاط ، يمكننا استخلاص نقاط إضافية لهذه الوظيفة كثير الحدود. يسمى استقراء هذه النقاط الإضافية الاستيفاء متعدد الحدود .

صنع سر

ربما تكون قد أدركت بالفعل أن مخطط شامير الذكي يلعب دوره هنا. لنفترض سرنا $$$S$ هل هذا $$ . يمكننا الدوران $$$S$ إلى حد ما على الرسم البياني $$$(0.42) دولا$ ويأتي مع وظيفة متعدد الحدود مع درجة $$$k-1$ الذي يرضي هذه النقطة. أذكر ذلك $$$ك$ ستكون عتبة الشظايا المطلوبة ، لذلك إذا وضعنا العتبة على ثلاث شظايا ، فيجب علينا اختيار دالة متعددة الحدود مع الدرجة الثانية.

سيكون لدينا كثير الحدود تأخذ الشكل $$$f (x) = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$ اين $$$a_0 = S$ و $$$a_1 ، ... ، a_ {k-1}$ - أعداد صحيحة موجبة تم اختيارها عشوائيا. نحن مجرد بناء متعدد الحدود مع درجة $$$k-1$ أين هو معامل الحرة $$$a_0 دولا$ هو سرنا $$$S$ ، وكل من التالي $$$k-1$ لدى الأعضاء معامل إيجابي تم اختياره عشوائيًا. إذا عدت إلى المثال الأصلي وافترضت ذلك $$$S = 42 ، k = 3 ، a_1 ، ... ، a_ {k-1} = [3،5]$ ثم نحصل على الوظيفة $$$f (x) = 42 + 3x + 5x ^ 2$ .

في هذه المرحلة ، يمكننا توليد شظايا عن طريق الاتصال $$$ن$ أعداد صحيحة فريدة في $$$f (x) = 42 + 3x + 5x ^ 2$ اين $$$x \ neq 0$ (لأن هذا هو سرنا). في هذا المثال ، نريد توزيع أربعة أجزاء بحدود ثلاثة ، لذلك نقوم بإنشاء نقاط بشكل عشوائي $$ وإرسال نقطة واحدة إلى كل من الأشخاص الموثوق بهم الأربعة ، وحفظة المفاتيح. نحن أيضا نقول للناس ذلك $$$ك = 3 دولا$ ، لأنها تعتبر معلومات عامة وضرورية للتعافي $$$S$ .

سر الانتعاش

لقد ناقشنا بالفعل مفهوم الاستيفاء متعدد الحدود وحقيقة أنه يكمن وراء مخطط عتبة شامير $$$(ك ، ن) دولا$ . عندما أي ثلاثة من الوكلاء الأربعة يريدون استرداد $$$S$ انهم بحاجة فقط إلى أقحم $$$f (0)$ مع نقاط فريدة من نوعها. للقيام بذلك ، يمكنهم تحديد نقاطهم $$$(x_1 ، y_1) ، ... ، (x_k ، y_k) = (18 ، 1716) ، (27 ، 3768) ، (31 ، 4940)$ وحساب متعدد الحدود لاجرانج باستخدام الصيغة التالية. إذا كنت البرمجة أكثر وضوحا من الرياضيات، وبي - هو في الواقع مشغل for ، التي تتكاثر كل النتائج، وسيجما - هو for ، أن تضيف كل ما يصل.

$$

$$P (x) = \ sum_ {j = 1} ^ {k} p_j (x)$$

$$

$$P_j (x) = y_j \ prod _ {\ scriptstyle m = 1 \ atop \ scriptstyle m \ neq j} ^ {k} \ frac {x-x_m} {x_j-x_m}$$

في $$$ك = 3 دولا$ يمكننا حل هذا على النحو التالي وإرجاع وظيفة متعدد الحدود الأصلي:

$$

$$\ تبدأ {محاذاة} P (x) & = {y_1} \ left ({x-x_2 \ over x_1-x_2} \ cdot {x-x_3 \ over x_1-x_3} \ left) + {y_2} \ left ( {x-x_1 \ over x_2-x_1} \ cdot {x - \ _ 3 \ over x_2-x_3} \ right) + {y_3} \ left ({x-x_1 \ over x_3-x_1} \ cdot {x-x_2 \ أكثر من x_3-x_2} \ right) \\ P (x) & = {1716} \ left ({x-27 \ over 18-27} \ cdot {x-31 \ over 18-31} \ right) + {3768 } \ left ({x-18 \ over 27-18} \ cdot {x-31 \ over 27-31} \ right) + {4940} \ left ({x-18 \ over 31-18} \ cdot {x -27 \ أكثر من 31-27} \ right) \\ P (x) & = 42 + 3x + 5x ^ 2 \ end {align}$$

لأننا نعرف ذلك $$$S = P (0)$ الانتعاش $$$S$ نفذت ببساطة:

$$

$$\ تبدأ {align} P (0) & = 42 + 3 (0) + 5 (0) ^ 2 \\ P (0) & = 42 \ end {align}$$

باستخدام حساب عدد صحيح غير آمن

على الرغم من أننا طبقنا الفكرة الأساسية لشامير بنجاح $$$(ك ، ن) دولا$ ، لا تزال لدينا مشكلة تجاهلناها حتى الآن. تستخدم الدالة متعدد الحدود الخاصة بنا حساب عدد صحيح غير آمن. لاحظ أنه لكل نقطة إضافية يتلقاها المهاجم على الرسم البياني لوظيفة لدينا ، هناك خيارات أقل لنقاط أخرى. يمكنك أن ترى ذلك بعينيك عند بناء رسم بياني مع زيادة في عدد النقاط لوظيفة متعددة الحدود باستخدام حساب عدد صحيح. هذا يأتي بنتائج عكسية بالنسبة لهدفنا الأمني ​​المعلن ، لأن المهاجم لا يتوجب عليه تعلم أي شيء على الإطلاق حتى يكون لديهم على الأقل $$$ك$ شظايا.

لتوضيح مدى ضعف المخطط مع الحساب الصحيح ، ضع في اعتبارك سيناريو حصل فيه المهاجم على نقطتين $$$(18 ، 1716) ، (273768)$ ويعرف المعلومات العامة ذلك $$$ك = 3 دولا$ . من هذه المعلومات يمكن أن نستنتج $$$f (x)$ يساوي اثنين وربط القيم المعروفة في الصيغة $$$x$ و $$$f (x)$ .

$$

$$\ تبدأ {محاذاة} f (x) & = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f (x) & = S + a_1x + a_2x ^ 2 \\ f (18) \ equiv 1716 & = S + a_118 + a_218 ^ 2 \\ f (27) \ equiv 3768 & = S + a_127 + a_227 ^ 2 \ end {align}$$

ثم يمكن للمهاجم العثور عليها $$$a_1$ العد $$$f (27) - f (18)$ :

$$

منذ أن حددنا $$$a_1، ...، a_ {k-1}$ كما أعداد صحيحة موجبة تم اختيارها عشوائيا ، هناك عدد محدود من ممكن $$$a_2 دولا$ . باستخدام هذه المعلومات ، يمكن للمهاجم أن يستنتج $$$a_2 \ in [1،2،3،4،5]$ ، لأن كل ما هو أكثر من 5 سيفعل $$$a_1$ سلبي. اتضح أن هذا صحيح ، كما قررنا $$$a_2 = 5$

ثم يمكن للمهاجم حساب القيم المحتملة $$$S$ استبدال $$$a_1$ في $$ :

$$

$$\ تبدأ {محاذاة} 1716 & = S + a_118 + a_218 ^ 2 \\ 1716 & = S + 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ 1716 - S & = 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ -S & = 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 - 1716 \\ -S & = 4104 - 810a_2 + a_218 ^ 2 - 1716 \\ S & = -4104 + 810a_2 - a_218 ^ 2 + 1716 \\ S & = 810a_2 - 324a_2 -2388 \\ S & = 486a_2 - 2388 \ end {محاذاة}$$

مع مجموعة محدودة من الخيارات ل $$$a_2 دولا$ يصبح من الواضح مدى سهولة اختيار القيم والتحقق منها $$$S$ . لا يوجد سوى خمسة خيارات.

حل المشكلة بحساب عدد صحيح غير آمن

للقضاء على هذه الثغرة الأمنية ، يقترح شامير استخدام حساب معياري ، واستبداله $$$f (x)$ على $$$f (x) \ mod p$ اين $$$p \ in \ mathbb {P}: p> S، p> n$ و $$$\ mathbb {P}$ - مجموعة من جميع الأعداد الأولية.

أذكر بسرعة كيف تعمل وحدات حسابية. الساعة مع الأسهم هي بالفعل مفهوم مألوف. انها تستخدم الساعات التي هي $$$\ mod 12$ . حالما تمر ساعة اليد في الثانية عشرة ، فإنها تعود إلى واحدة. من الخصائص المهمة لهذا النظام أنه بمجرد النظر إلى الساعة ، لا يمكننا استنتاج عدد الثورات التي أحدثتها ساعة اليد. ومع ذلك ، إذا علمنا أن ساعة اليد قد مرت 12 مرة أربع مرات ، يمكننا تحديد عدد الساعات المنقضية بالكامل باستخدام صيغة بسيطة $$$a = mq + r$ اين $$$م دولا$ هو المقسوم لدينا (هنا $$$م = 12 دولا$ ) ، $$$ف دولا$ هو المعامل (كم مرة يذهب المقسوم بدون الباقي إلى الرقم الأصلي ، هنا $$$ف = 4 دولا$ ) ، و $$$ص$ هو الباقي ، والذي عادةً ما يُرجع معامل الاتصال الخاص بالمشغل (هنا $$$r = 1.5 دولا$ ) معرفة كل هذه القيم تسمح لنا بحل المعادلة من أجل $$$a = 49.5 دولا$ ولكن إذا كان لنا أن تفوت معدل، ونحن لن استعادة القيمة الأصلية.

يمكنك إثبات كيف يعمل ذلك على تحسين أمان دائرتنا من خلال تطبيق الدائرة على مثالنا السابق واستخدامها $$$ع = 73 دولا$ . لدينا متعدد الحدود وظيفة جديدة $$$f '(x) = 42 + 3x + 5x ^ 2 \ mod 73$ ونقاط جديدة $$ . الآن ، يمكن لحفظة المفاتيح مرة أخرى استخدام الاستيفاء متعدد الحدود لاستعادة وظيفتنا ، وهذه المرة فقط يجب أن تكون عمليات الجمع والضرب مصحوبة بتخفيض المعامل $$$p$ (على سبيل المثال $$$48 + 93 \ mod 73 = 68$ )

باستخدام هذا المثال الجديد ، افترض أن المهاجم قد تعرف على اثنين من هذه النقاط الجديدة ، $$ ، والمعلومات العامة $$$ك = 3 ، ع = 73 دولا$ . هذه المرة ، يعرض المهاجم ، بناءً على جميع المعلومات التي لديه ، الوظائف التالية وأين $$$\ mathbb {N}$ هي مجموعة من جميع الأعداد الصحيحة الموجبة ، و $$$q_x$ يمثل معامل الوحدة $$$f ((x)$ .

$$

$$\ تبدأ {محاذاة} f '(x) & = S + a_1x + a_2x ^ 2 \ mod 73 \\ f' (x) & = S + a_1x + a_2x ^ 2 - 73q_x: q_x \ in \ mathbb {N} \\ f '(18) \ equiv 37 & = S + a_118 + a_218 ^ 2 - 73q_ {18} \\ f' (27) \ equiv 45 & = S + a_127 + a_227 ^ 2 - 73q_ {27} \ end {محاذاة}$$

الآن يجد المهاجم لدينا مرة أخرى $$$a_1$ عن طريق الحوسبة $$$f ((27) - f '(18)$ :

$$

$$\ تبدأ {محاذاة} 45 - 37 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_ {27} - (-73q_ {18})) \\ 8 & = 9a_1 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ -9a_1 & = -8 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ 9a_1 & = 8 - 405a_2 - 73 (q_ {18} - q_ {27}) \\ a_1 & = \ frac {8 - 405a_2 - 73 (q_ {18} - q_ {27})} {9} \\ a_1 & = \ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ end {align}$$

ثم يحاول مرة أخرى الانسحاب $$$S$ استبدال $$$a_1$ في $$$f ((18)$ :

$$

$$\ تبدأ {محاذاة} 37 & = S + 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} \\ -S & = 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} - 37 \\ S & = -18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27} ) \ right) - 324a_2 + 73q_ {18} + 37 \\ S & = 486a_2 + 21 + 219q_ {18} - 146q_ {27} \ end {محاذاة}$$

هذه المرة لديه مشكلة خطيرة. لا توجد قيم في الصيغة $$$a_2$ ، $$$q_ {18}$ و $$$q_ {27}$ . نظرًا لوجود عدد لا حصر له من مجموعات من هذه المتغيرات ، فإنه لا يمكن تلقي أي معلومات إضافية.

اعتبارات الأمان

تقدم السري مخطط تقاسم شامير الأمن من حيث نظرية المعلومات. هذا يعني أن الرياضيات تقاوم حتى ضد المهاجمين الذين يتمتعون بقوة حوسبية غير محدودة. ومع ذلك ، لا تزال الدائرة تحتوي على العديد من المشكلات المعروفة.

على سبيل المثال، نظام شامير لا يخلق شظايا يمكن التحقق منها، وهذا هو، والناس أحرار في جلب شظايا وهمية ومنع استعادة سر الصحيح. يمكن لحارس الشظايا العدائي مع معلومات كافية أن ينتج شظية أخرى عن طريق التغيير $$$S$ حسب تقديرها. يتم حل هذه المشكلة عن طريق مخططات تقاسم سرية التحقق منها، مثل مخطط فيلدمان.

مشكلة أخرى هي أن طول أي جزء يساوي طول السر المقابل ، بحيث يكون من السهل تحديد طول السر. يتم حل هذه المشكلة الحشو السري تافهة لأرقام عشوائية من طول ثابت.

أخيرًا ، من المهم أن نلاحظ أن مخاوفنا الأمنية قد تتجاوز نطاق المخطط نفسه. بالنسبة لتطبيقات التشفير في العالم الحقيقي ، غالبًا ما يكون هناك تهديد بهجمات على قنوات تابعة لجهات خارجية ، عندما يحاول مهاجم استخراج معلومات مفيدة من وقت تشغيل التطبيق ، أو التخزين المؤقت ، أو الأعطال ، وما إلى ذلك. إذا كان هذا مصدر قلق ، فيجب عليك التفكير بعناية في استخدام الإجراءات الوقائية أثناء التطوير ، مثل الوظائف والبحث مع وقت تشغيل ثابت ، ومنع تخزين الذاكرة على القرص ، والنظر في عدد من الأشياء الأخرى التي تتجاوز نطاق هذه المقالة.

عرض

على هذه الصفحة ليس هناك تقاسم مظاهرة التفاعلية خطة شامير السري. يتم إجراء مظاهرة على أساس المكتبة SSSS-شبيبة ، وهو في حد ذاته هو جافا سكريبت ميناء البرنامج شعبية SSSS . لاحظ أن حساب القيم الكبيرة $$$ك$ ، $$$ن$ و $$$S$ قد يستغرق بعض الوقت.