ضع في اعتبارك سيناريو تحتاج فيه إلى تأمين خزنة بنكية. يعتبر منيعًا تمامًا بدون مفتاح ، والذي يتم إعطاؤه لك في اليوم الأول من العمل. هدفك هو تخزين المفتاح بأمان.
لنفترض أنك قررت الاحتفاظ بالمفتاح معك في جميع الأوقات ، مع توفير الوصول إلى الخزنة حسب الحاجة. لكنك ستدرك بسرعة أن مثل هذا الحل لا يتسع نطاقه بشكل جيد في الممارسة ، لأنه في كل مرة تحتاج إلى التواجد فعليًا لفتح الخزنة. ماذا عن الإجازة التي وعدت بها؟ بالإضافة إلى ذلك ، فإن السؤال المخيف أكثر: ماذا لو فقدت المفتاح الوحيد؟
مع فكرة الإجازة ، تقرر عمل نسخة من المفتاح وتوكله إلى موظف آخر. ومع ذلك ، فأنت تدرك أن هذا ليس مثاليًا أيضًا. بمضاعفة عدد المفاتيح ، تكون قد ضاعفت أيضًا فرص سرقة المفاتيح.
يائسًا ، تدمر النسخة المكررة وتقرر تقسيم المفتاح الأصلي إلى نصفين. الآن ، تعتقد أن شخصين موثوقين بهما شظايا رئيسية يجب أن يكونا حاضرين فعليًا لجمع المفتاح وفتح الخزنة. هذا يعني أن اللص يحتاج إلى سرقة جزأين ، وهو ضعف صعوبة سرقة مفتاح واحد. ومع ذلك ، سرعان ما تدرك أن هذا المخطط ليس أفضل بكثير من مجرد مفتاح واحد ، لأنه إذا فقد شخص ما نصف المفتاح ، فلا يمكن استرداد المفتاح الكامل.
يمكن حل المشكلة بسلسلة من المفاتيح والأقفال الإضافية ، لكن هذا النهج سيتطلب بسرعة كثير مفاتيح وأقفال. أنت تقرر أن المخطط المثالي هو مشاركة المفتاح بحيث لا يعتمد الأمان بالكامل على شخص واحد. تستنتج أيضًا أنه يجب أن يكون هناك حد معين لعدد الأجزاء بحيث في حالة فقد جزء واحد (أو إذا ذهب الشخص في إجازة) ، يظل المفتاح بأكمله يعمل.
كيف تشارك سرا
كان هذا النوع من مخطط الإدارة الرئيسية قد فكر فيه عدي شامير في عام 1979 عندما نشر عمله . المقال يشرح بإيجاز ما يسمى ب 
مخطط عتبة لتقسيم قيمة سرية بشكل فعال (على سبيل المثال ، مفتاح تشفير) إلى القطع. ثم متى وفقط عندما على الأقل من يتم تجميع الأجزاء ، يمكنك بسهولة استعادة السر .
من وجهة نظر أمنية ، فإن الخاصية المهمة لهذا المخطط هي أن المهاجم يجب ألا يتعلم أي شيء على الإطلاق إذا لم يكن لديه على الأقل القطع. حتى الوجود يجب ألا تعطي الأجزاء أي معلومات. نسمي هذه الخاصية الأمن الدلالي.
استيفاء متعدد الحدود
مخطط عتبة شامير بنيت حول هذا المفهوم استيفاء كثير الحدود. إذا لم تكن معتادًا على هذا المفهوم ، فهو في الواقع بسيط للغاية. بشكل عام ، إذا كنت قد رسمت نقاطًا على مخطط ما ثم قمت بتوصيلها بخطوط أو منحنيات ، فقد استخدمتها بالفعل!
من خلال نقطتين ، يمكنك رسم عدد غير محدود من كثيرات الحدود من الدرجة الثانية. لاختيار النقطة الوحيدة منها ، تحتاج إلى نقطة ثالثة. توضيح:
النظر في كثير الحدود مع الدرجة الأولى ، . إذا كنت تريد رسم هذه الوظيفة على رسم بياني ، فكم عدد النقاط التي تحتاجها؟ حسنًا ، نعلم أن هذه دالة خطية تشكل خطًا ، وبالتالي نحتاج إلى نقطتين على الأقل. بعد ذلك ، ضع في اعتبارك دالة متعددة الحدود من الدرجة الثانية ، . هذه دالة تربيعية ، لذا يلزم وجود ثلاث نقاط على الأقل لرسم الرسم البياني. ماذا عن كثير الحدود من الدرجة الثالثة؟ أربع نقاط على الأقل. وهلم جرا وهكذا دواليك.
الشيء الرائع حقًا في هذه الخاصية هو أنه ، بالنظر إلى درجة دالة كثيرة الحدود على الأقل من النقاط ، يمكننا اشتقاق نقاط إضافية لهذه الدالة كثيرة الحدود. نحن نسمي استقراء هذه النقاط الإضافية استيفاء كثير الحدود.
سر
ربما تكون قد اكتشفت بالفعل أن هذا هو المكان الذي تدخل فيه خطة شامير الذكية. افترض سرنا - هو . يمكننا أن نستدير إلى النقطة على الرسم البياني وتوصل إلى دالة متعددة الحدود بدرجة الذي يرضي هذه النقطة. أذكر ذلك سيكون عتبة الأجزاء المطلوبة ، لذلك إذا قمنا بتعيين الحد على ثلاثة أجزاء ، يجب أن نختار دالة متعددة الحدود بدرجة اثنين.
سيكون لدينا كثير الحدود الشكل حيث и يتم اختيارهم عشوائيًا أعداد صحيحة موجبة. نحن فقط نبني كثير الحدود بدرجة حيث المعامل الحر - هذا هو سرنا ، وكل من اللاحقة المصطلحات هي معامل موجب تم اختياره عشوائيًا. العودة إلى المثال الأصلي وافتراض ذلك ، ثم نحصل على الوظيفة .
في هذه المرحلة ، يمكننا إنشاء أجزاء من خلال الاتصال فريد من نوعه في حيث (لأنه سرنا). في هذا المثال ، نريد أن نوزع أربعة أجزاء بحد ثلاثة ، لذلك نقوم بتوليد نقاط بشكل عشوائي وأرسل نقطة واحدة إلى كل من الأشخاص الأربعة الموثوق بهم ، حراس المفتاح. كما نقول للناس ذلك ، لأنها تعتبر معلومات عامة وضرورية للتعافي .
التعافي السري
لقد ناقشنا بالفعل مفهوم الاستيفاء متعدد الحدود وكيف يكمن وراء مخطط شامير العتبة. . عندما يريد أي ثلاثة من كل أربعة أمناء استعادة ، لا يحتاجون إلا إلى الاستيفاء بنقاطهم الفريدة. للقيام بذلك ، يمكنهم تحديد نقاطهم وحساب لاغرانج كثير حدود الاستيفاء باستخدام الصيغة التالية. إذا كانت البرمجة أوضح بالنسبة لك من الرياضيات ، فإن pi في الأساس عامل تشغيل forالذي يضاعف كل النتائج ، ويكون سيجما هو forيضيف كل شيء.
في يمكننا حلها على هذا النحو وإرجاع دالة كثيرة الحدود الأصلية:
منذ أن عرفنا ذلك ، التعافي يتم ببساطة:
استخدام حساب عدد صحيح غير آمن
على الرغم من أننا نجحنا في تطبيق فكرة شامير الأساسية ، لقد تركنا مع مشكلة تجاهلناها حتى الآن. تستخدم دالة كثيرة الحدود حسابًا صحيحًا غير آمن. لاحظ أنه مقابل كل نقطة إضافية يحصل عليها المهاجم على الرسم البياني للوظائف لدينا ، هناك احتمالات أقل للنقاط الأخرى. يمكنك أن ترى هذا بأم عينيك عندما ترسم عددًا متزايدًا من النقاط لدالة متعددة الحدود باستخدام حساب عدد صحيح. هذا يأتي بنتائج عكسية لهدفنا الأمني المعلن ، لأن المهاجم يجب ألا يعرف شيئًا على الإطلاق حتى يكون لديه على الأقل فتات.
لتوضيح مدى ضعف المخطط الحسابي الصحيح ، ضع في اعتبارك سيناريو حصل فيه المهاجم على نقطتين ويعرف المعلومات العامة التي . من هذه المعلومات ، يمكنه الاستدلال ، يساوي اثنين ، وقم بتوصيل القيم المعروفة بالصيغة и .
يمكن للمهاجم العثور بعد ذلك العد :
منذ أن حددنا كأعداد صحيحة موجبة بشكل عشوائي ، هناك عدد محدود من الممكن . باستخدام هذه المعلومات ، يمكن للمهاجم أن يستنتج ، لأن أي شيء أكبر من 5 سيصنع سلبي. تبين أن هذا صحيح ، لأننا قررنا
يمكن للمهاجم بعد ذلك حساب القيم الممكنة استبدال в :
مع خيارات محدودة لـ يصبح من الواضح مدى سهولة التقاط القيم والتحقق منها . لا يوجد سوى خمسة خيارات هنا.
حل مشكلة حساب الأعداد الصحيحة غير الآمنة
لإصلاح هذه الثغرة الأمنية ، يقترح شامير استخدام الحساب المعياري عن طريق الاستبدال في حيث и هي مجموعة جميع الأعداد الأولية.
لنتذكر بسرعة كيف يعمل الحساب النمطي. ساعات اليد مفهوم مألوف. إنها تستخدم الساعة التي هي . بمجرد مرور عقرب الساعات على الثانية عشرة ، يعود إلى واحد. من الخصائص المثيرة للاهتمام لهذا النظام أنه بمجرد النظر إلى الساعة ، لا يمكننا استنتاج عدد الدورات التي أحدثها عقرب الساعات. ومع ذلك ، إذا علمنا أن عقرب الساعات قد تجاوز 12 أربع مرات ، فيمكننا تحديد عدد الساعات التي انقضت تمامًا باستخدام صيغة بسيطة حيث هو القاسم (هنا ), - هذا هو المعامل (كم مرة يدخل المقسوم عليه بدون باقي الرقم الأصلي هنا م)، و هو الباقي ، والذي عادةً ما يقوم بإرجاع استدعاء لمشغل modulo (هنا ). تتيح لنا معرفة كل هذه القيم حل المعادلة لـ ، ولكن إذا تخطينا المعامل ، فلن نتمكن أبدًا من استعادة القيمة الأصلية.
يمكننا توضيح كيف يؤدي ذلك إلى تحسين أمان دائرتنا من خلال تطبيق الدائرة على مثالنا السابق واستخدامه . دالة كثيرة الحدود الجديدة لدينا والنقاط الجديدة . الآن يمكن لحراس المفاتيح مرة أخرى استخدام الاستيفاء متعدد الحدود لإعادة بناء وظيفتنا ، هذه المرة فقط يجب أن تتبع عمليات الجمع والضرب بتقليل النمط. (على سبيل المثال ).
باستخدام هذا المثال الجديد ، افترض أن المهاجم قد تعلم نقطتين من هذه النقاط الجديدة ، ، والمعلومات العامة . هذه المرة ، يقوم المهاجم ، بناءً على جميع المعلومات التي لديه ، بعرض الوظائف التالية ، حيث هي مجموعة جميع الأعداد الصحيحة الموجبة ، و يمثل معامل المعامل .
الآن الدخيل لدينا يجد مرة أخرى ، حساب :
ثم حاول الانسحاب مرة أخرى استبدال в :
هذه المرة لديه مشكلة خطيرة. الصيغة تفتقد إلى القيم , и . نظرًا لوجود عدد لا حصر له من مجموعات هذه المتغيرات ، لا يمكنه الحصول على أي معلومات إضافية.
اعتبارات أمنية
يقترح مخطط مشاركة شامير السري أمن المعلومات. هذا يعني أن الرياضيات قوية حتى ضد مهاجم يتمتع بقوة حوسبة غير محدودة. ومع ذلك ، لا يزال المخطط يحتوي على العديد من المشكلات المعروفة.
على سبيل المثال ، مخطط شامير لا يخلق شظايا لفحصهاأي أن الأشخاص أحرار في تقديم شظايا مزيفة والتدخل في استعادة السر الصحيح. يمكن لحافظ الشظايا العدائي الذي لديه معلومات كافية أن ينتج جزءًا آخر عن طريق التغيير حسب تقديرك. تم حل هذه المشكلة مع أنظمة مشاركة سرية يمكن التحقق منها، مثل مخطط فيلدمان.
مشكلة أخرى هي أن طول أي جزء يساوي طول السر المقابل ، لذلك من السهل تحديد طول السر. يتم حل هذه المشكلة عن طريق التافه حشوة سرية بأرقام عشوائية تصل إلى طول ثابت.
أخيرًا ، من المهم ملاحظة أن مخاوفنا الأمنية قد تتجاوز المخطط نفسه. بالنسبة لتطبيقات التشفير الحقيقية ، غالبًا ما يكون هناك تهديد بهجمات القناة الجانبية ، عندما يحاول المهاجم استخراج معلومات مفيدة من وقت تنفيذ التطبيق ، والتخزين المؤقت ، والتعطل ، وما إلى ذلك. إذا كان هذا مصدر قلق ، يجب أن تفكر بعناية في استخدام وسائل الحماية أثناء التطوير ، مثل الوظائف وعمليات البحث في الوقت الثابت ، ومنع حفظ الذاكرة على القرص ، والنظر في عدد من الأشياء الأخرى التي تقع خارج نطاق هذه المقالة.
عرض
في هناك عرض تفاعلي لمخطط شامير للمشاركة السرية. تم إجراء المظاهرة على أساس المكتبة ، وهو في حد ذاته منفذ JavaScript لبرنامج مشهور . لاحظ أن حساب القيم الكبيرة , и قد يستغرق بعض الوقت.
المصدر: www.habr.com