سناریویی را در نظر بگیرید که در آن باید صندوق بانکی را ایمن کنید. بدون کلید کاملاً غیرقابل نفوذ در نظر گرفته می شود که در همان روز اول کار به شما داده می شود. هدف شما ذخیره ایمن کلید است.
فرض کنید تصمیم دارید کلید را همیشه نزد خود نگه دارید و در صورت نیاز به فضای ذخیره سازی دسترسی داشته باشید. اما شما به سرعت متوجه خواهید شد که چنین راه حلی در عمل مقیاس خوبی ندارد، زیرا هر بار که ذخیره سازی را باز می کنید، حضور فیزیکی شما لازم است. در مورد تعطیلاتی که به شما قول داده بودند چطور؟ علاوه بر این، این سوال حتی ترسناک تر است: اگر تنها کلید خود را گم کنید چه؟
با در نظر گرفتن تعطیلات خود، تصمیم می گیرید یک کپی از کلید تهیه کنید و آن را به کارمند دیگری بسپارید. با این حال، می دانید که این نیز ایده آل نیست. با دو برابر کردن تعداد کلیدها، احتمال سرقت کلید را نیز دو برابر می کنید.
در ناامیدی، نسخه تکراری را از بین می‌برید و تصمیم می‌گیرید کلید اصلی را به دو نیم کنید. اکنون، شما فکر می کنید که دو فرد مورد اعتماد با قطعات کلید باید به صورت فیزیکی حضور داشته باشند تا کلید را جمع کنند و طاق را باز کنند. این بدان معنی است که یک دزد باید دو قطعه را بدزدد که دو برابر دزدیدن یک کلید دشوارتر است. با این حال، به زودی متوجه می شوید که این طرح خیلی بهتر از یک کلید نیست، زیرا اگر کسی نیمی از کلید را گم کند، کلید کامل قابل بازیابی نیست.
مشکل را می توان با یک سری کلید و قفل اضافی حل کرد، اما این روش به سرعت نیاز دارد много کلید و قفل شما تصمیم می گیرید که طراحی ایده آل این است که کلید را به اشتراک بگذارید تا امنیت به طور کامل به یک شخص متکی نباشد. همچنین به این نتیجه رسیدید که باید مقداری آستانه برای تعداد قطعات وجود داشته باشد تا اگر یک قطعه گم شود (یا اگر شخصی به تعطیلات برود)، کل کلید فعال بماند.
چگونه یک راز را به اشتراک بگذاریم
این نوع طرح مدیریت کلیدی توسط آدی شامیر در سال 1979 هنگام انتشار آثارش مورد توجه قرار گرفت . مقاله به طور خلاصه توضیح می دهد که به اصطلاح 
طرح آستانه برای تقسیم مؤثر یک مقدار مخفی (مانند یک کلید رمزنگاری) به قطعات. سپس، حداقل زمانی که و تنها زمانی از قطعات مونتاژ شده اند، شما به راحتی می توانید راز را بازیابی کنید .
از نقطه نظر امنیتی، ویژگی مهم این طرح این است که مهاجم نباید مطلقاً چیزی بداند مگر اینکه حداقل چیزی را داشته باشد. قطعات. حتی حضور قطعات نباید هیچ اطلاعاتی ارائه دهند. ما به این ملک می گوییم امنیت معنایی.
درونیابی چند جمله ای
طرح آستانه شمیر بر اساس مفهوم ساخته شده است درونیابی چند جمله ای. اگر با این مفهوم آشنا نیستید، در واقع بسیار ساده است. در واقع، اگر تا به حال نقاطی را روی یک نمودار رسم کرده اید و سپس آنها را با خطوط یا منحنی به هم متصل کرده اید، قبلاً از آن استفاده کرده اید!
از طریق دو نقطه می توانید تعداد نامحدودی چند جمله ای درجه 2 رسم کنید. برای انتخاب تنها یکی از آنها، به یک نقطه سوم نیاز دارید. تصویر:
چند جمله ای را با درجه یک در نظر بگیرید، . اگر بخواهید این تابع را روی یک نمودار رسم کنید، به چند نقطه نیاز دارید؟ خوب، ما می دانیم که این یک تابع خطی است که یک خط را تشکیل می دهد و بنابراین حداقل به دو نقطه نیاز دارد. سپس یک تابع چند جمله ای با درجه دو را در نظر بگیرید، . این یک تابع درجه دوم است، بنابراین حداقل سه نقطه برای رسم نمودار مورد نیاز است. چند جمله ای با درجه سه چطور؟ حداقل چهار امتیاز و به همین ترتیب، و غیره.
نکته جالب در مورد این ویژگی این است که با توجه به درجه تابع چند جمله ای و حداقل نقاط، ما می توانیم نقاط اضافی برای این تابع چند جمله ای استخراج کنیم. ما برون یابی این نکات اضافی را می نامیم درونیابی چند جمله ای.
ساختن یک راز
شاید قبلاً متوجه شده باشید که این همان جایی است که نقشه هوشمندانه شامیر وارد عمل می شود. بیایید راز خود را بگوییم - آیا . می توانیم بچرخیم به نقطه ای از نمودار و یک تابع چند جمله ای با درجه ایجاد کنید ، که این نکته را برآورده می کند. بگذارید آن را به خاطر بیاوریم آستانه قطعات مورد نیاز ما خواهد بود، بنابراین اگر آستانه را روی سه قطعه قرار دهیم، باید یک تابع چند جمله ای با درجه دو انتخاب کنیم.
چند جمله ای ما شکل خواهد داشت جایی که и - اعداد صحیح مثبت به طور تصادفی انتخاب شده اند. ما فقط یک چند جمله ای با درجه می سازیم ، جایی که ضریب آزاد است - این راز ماست و برای هر یک از موارد بعدی در شرایط یک ضریب مثبت تصادفی انتخاب شده وجود دارد. اگر به مثال اصلی برگردیم و فرض کنیم که ، سپس تابع را دریافت می کنیم .
در این مرحله می‌توانیم با اتصال قطعاتی تولید کنیم اعداد صحیح منحصر به فرد در جایی که (چون راز ماست). در این مثال، ما می خواهیم چهار قطعه را با آستانه سه توزیع کنیم، بنابراین به طور تصادفی امتیاز ایجاد می کنیم. و برای هر یک از چهار نفر معتمد، متولیان کلید، یک امتیاز بفرستید. ما نیز این را به مردم اطلاع دادیم ، زیرا این اطلاعات عمومی محسوب می شود و برای بازیابی ضروری است .
بازیابی راز
ما قبلاً در مورد مفهوم درونیابی چند جمله ای و چگونگی زیربنای طرح آستانه شامیر بحث کرده ایم. . وقتی هر سه نفر از چهار متولی بخواهند بازیابی کنند ، آنها فقط نیاز به درون یابی دارند با نکات منحصر به فرد خودش برای این کار می توانند امتیاز خود را مشخص کنند و چند جمله ای درونیابی لاگرانژ را با استفاده از فرمول زیر محاسبه کنید. اگر برنامه نویسی برای شما واضح تر از ریاضیات است، پس اساساً pi یک عملگر است for، که همه نتایج را ضرب می کند و سیگما است for، که همه چیز را جمع می کند.
در ما می توانیم آن را به این صورت حل کنیم و تابع چند جمله ای اصلی خود را برگردانیم:
چون ما این را می دانیم ، بهبود به سادگی انجام می شود:
استفاده از محاسبات اعداد صحیح ناامن
اگرچه ما ایده اصلی شامیر را با موفقیت به کار برده ایم ، ما با مشکلی مانده ایم که تا به حال از آن چشم پوشی کرده ایم. تابع چند جمله ای ما از محاسبات اعداد صحیح ناامن استفاده می کند. توجه داشته باشید که به ازای هر نقطه اضافی که مهاجم در نمودار تابع ما به دست می آورد، امکانات کمتری برای نقاط دیگر وجود دارد. وقتی تعداد نقاط فزاینده ای را برای یک تابع چند جمله ای با استفاده از حساب اعداد صحیح رسم می کنید، می توانید این را با چشمان خود ببینید. این برای هدف امنیتی اعلام شده ما اثر معکوس دارد، زیرا مهاجم باید مطلقاً چیزی بداند تا زمانی که حداقل نداشته باشد قطعات
برای نشان دادن اینکه مدار حسابی اعداد صحیح چقدر ضعیف است، سناریویی را در نظر بگیرید که در آن مهاجم دو امتیاز را به دست آورد. و اطلاعات عمومی را می داند که . از این اطلاعات او می تواند استنباط کند ، برابر با دو، و مقادیر شناخته شده را به فرمول وصل کنید и .
سپس مهاجم می تواند پیدا کند ، با احتساب :
از آنجایی که ما تعریف کردیم به عنوان اعداد صحیح مثبت به طور تصادفی انتخاب شده، تعداد محدودی ممکن است . با استفاده از این اطلاعات، مهاجم می تواند استنباط کند ، زیرا هر چیزی بزرگتر از 5 انجام خواهد داد منفی. از آنجایی که ما مشخص کرده ایم این درست است
سپس مهاجم می تواند مقادیر ممکن را محاسبه کند جایگزین کردن в :
با گزینه های محدود برای مشخص می شود که انتخاب و بررسی مقادیر چقدر آسان است . در اینجا فقط پنج گزینه وجود دارد.
حل مسئله با محاسبات اعداد صحیح ناامن
برای از بین بردن این آسیب پذیری، Shamir استفاده از محاسبات مدولار را پیشنهاد می کند بر جایی که и - مجموعه تمام اعداد اول.
بیایید به سرعت به یاد بیاوریم که محاسبات مدولار چگونه کار می کند. ساعت با عقربه ها مفهومی آشناست. او از یک ساعت استفاده می کند . به محض اینکه عقربه ساعت از دوازده گذشت، به یک برمی گردد. یکی از ویژگی های جالب این سیستم این است که به سادگی با نگاه کردن به ساعت نمی توان نتیجه گرفت که عقربه ساعت چند دور انجام داده است. با این حال، اگر بدانیم که عقربه ساعت 12 و چهار بار گذشته است، می‌توانیم تعداد ساعت‌های گذشته را با استفاده از یک فرمول ساده مشخص کنیم. جایی که مقسوم‌کننده ما است (اینجا ), ضریب (در اینجا چند بار مقسوم علیه بدون باقی مانده به عدد اصلی وارد می شود )، آ باقیمانده است که معمولاً یک تماس اپراتور مدول را برمی‌گرداند (اینجا ). دانستن همه این مقادیر به ما امکان می دهد معادله را حل کنیم ، اما اگر ضریب را از دست بدهیم، هرگز نمی توانیم مقدار اولیه را بازیابی کنیم.
ما می توانیم نشان دهیم که چگونه این امر امنیت طرح ما را با اعمال این طرح در مثال قبلی و استفاده از آن بهبود می بخشد. . تابع چند جمله ای جدید ما و نکات جدید . اکنون نگهدارنده های کلید می توانند بار دیگر از درونیابی چند جمله ای برای بازسازی تابع ما استفاده کنند، فقط این بار عملیات جمع و ضرب باید با کاهش مدول همراه باشد. (به عنوان مثال ).
با استفاده از این مثال جدید، فرض کنیم مهاجم دو مورد از این نکات جدید را یاد گرفته است. و اطلاعات عمومی . این بار مهاجم بر اساس تمام اطلاعاتی که دارد توابع زیر را خروجی می دهد که در آن مجموعه ای از تمام اعداد صحیح مثبت است، و نشان دهنده ضریب مدول است .
حالا مهاجم ما دوباره پیدا می کند ، محاسبه می کند :
سپس دوباره تلاش می کند جایگزین کردن в :
این بار او یک مشکل جدی دارد. مقادیر از دست رفته فرمول , и . از آنجایی که تعداد نامتناهی ترکیب از این متغیرها وجود دارد، او نمی تواند اطلاعات اضافی را به دست آورد.
ملاحظات امنیتی
طرح اشتراک مخفی شامیر پیشنهاد می کند امنیت از دیدگاه تئوری اطلاعات. این بدان معنی است که ریاضیات حتی در برابر مهاجمی با قدرت محاسباتی نامحدود مقاوم است. با این حال، مدار همچنان حاوی چندین مشکل شناخته شده است.
مثلاً طرح شامیر ایجاد نمی کند قطعاتی که باید بررسی شوندیعنی افراد می توانند آزادانه قطعات جعلی ارائه دهند و در بازیابی راز صحیح دخالت کنند. یک نگهدارنده قطعه متخاصم با اطلاعات کافی حتی می تواند با تغییر قطعه دیگری تولید کند به صلاحدید خود این مشکل با استفاده از طرح های به اشتراک گذاری راز قابل تاییدمانند طرح فلدمن.
مشکل دیگر این است که طول هر قطعه با طول راز مربوطه برابر است، بنابراین تعیین طول راز آسان است. این مشکل را می توان با بی اهمیتی حل کرد لایه گذاری مخفی با اعداد دلخواه تا یک طول ثابت.
در نهایت، مهم است که توجه داشته باشیم که نگرانی های امنیتی ما ممکن است فراتر از خود طراحی باشد. برای برنامه های رمزنگاری دنیای واقعی، اغلب تهدید حملات کانال جانبی وجود دارد که در آن مهاجم سعی می کند اطلاعات مفیدی را از زمان اجرای برنامه، حافظه پنهان، خرابی ها و غیره استخراج کند. اگر این یک نگرانی است، در طول توسعه باید به دقت به استفاده از اقدامات حفاظتی مانند توابع و جستجوهای زمان ثابت، جلوگیری از ذخیره حافظه در دیسک و تعدادی از ملاحظات دیگر که خارج از محدوده این مقاله هستند، توجه شود.
نسخه ی نمایشی
بر یک نمایش تعاملی از طرح اشتراک مخفی شامیر وجود دارد. تظاهرات بر اساس کتابخانه ، که خود یک پورت جاوا اسکریپت برنامه محبوب است . توجه داشته باشید که محاسبه مقادیر بزرگ , и ممکن است مدتی طول بکشد.
منبع: www.habr.com