Bank kassasini himoya qilishingiz kerak bo'lgan stsenariyni ko'rib chiqing. Bu sizga ishning birinchi kunida beriladigan kalitsiz mutlaqo o'tkazib bo'lmaydigan hisoblanadi. Sizning maqsadingiz kalitni xavfsiz saqlashdir.
Aytaylik, siz kalitni har doim yoningizda saqlashga qaror qildingiz va kerak bo'lganda xotiraga kirishni ta'minlaysiz. Ammo siz tezda bunday yechim amalda yaxshi miqyosga ega emasligini tushunasiz, chunki har safar saqlashni ochganingizda jismoniy mavjudligingiz talab qilinadi. Sizga va'da qilingan ta'til haqida nima deyish mumkin? Bundan tashqari, savol yanada qo'rqinchli: agar siz yagona kalitingizni yo'qotib qo'ysangiz nima bo'ladi?
Ta'tilingizni hisobga olib, siz kalitning nusxasini yaratishga va uni boshqa xodimga topshirishga qaror qilasiz. Biroq, bu ham ideal emasligini tushunasiz. Kalitlar sonini ikki baravar oshirish orqali siz kalitlarni o'g'irlash ehtimolini ham ikki baravar oshirasiz.
Umidsizlikda siz dublikatni yo'q qilasiz va asl kalitni yarmiga bo'lishga qaror qilasiz. Endi siz kalitni olish va omborni ochish uchun kalit bo'laklari bo'lgan ikkita ishonchli odam jismonan hozir bo'lishi kerak deb o'ylaysiz. Bu shuni anglatadiki, o'g'ri ikkita bo'lakni o'g'irlashi kerak, bu bitta kalitni o'g'irlashdan ikki baravar qiyin. Biroq, tez orada siz ushbu sxema faqat bitta kalitdan ko'ra yaxshiroq emasligini tushunasiz, chunki kimdir kalitning yarmini yo'qotsa, to'liq kalitni tiklab bo'lmaydi.
Muammoni bir qator qo'shimcha kalitlar va qulflar bilan hal qilish mumkin, ammo bu yondashuv tezda talab qilinadi много kalitlar va qulflar. Xavfsizlik butunlay bir kishiga tayanmasligi uchun kalitni bo'lishish ideal dizayn bo'ladi, deb qaror qilasiz. Bundan tashqari, siz fragmentlar soni uchun ma'lum bir chegara bo'lishi kerak degan xulosaga keldingiz, shunda bitta bo'lak yo'qolsa (yoki odam ta'tilga chiqsa), butun kalit ishlamaydi.
Qanday qilib sirni baham ko'rish kerak
Ushbu turdagi kalitlarni boshqarish sxemasi haqida Adi Shamir 1979 yilda o'z ishini nashr etganida o'ylagan . Maqolada qisqacha so'zda tushuntirilgan 
maxfiy qiymatni (masalan, kriptografik kalit) samarali bo'lish uchun chegara sxemasi qismlar. Keyin, qachon va faqat qachon kamida dan qismlar yig'ilgan, siz sirni osongina tiklashingiz mumkin .
Xavfsizlik nuqtai nazaridan, ushbu sxemaning muhim xususiyati shundaki, tajovuzkor hech bo'lmaganda hech narsani bilmasligi kerak. qismlar. Hatto mavjudligi qismlar hech qanday ma'lumot bermasligi kerak. Biz bu xususiyatni chaqiramiz semantik xavfsizlik.
Polinom interpolyatsiyasi
Shamir chegara sxemasi kontseptsiyasi atrofida qurilgan polinom interpolyatsiyasi. Agar siz ushbu tushuncha bilan tanish bo'lmasangiz, bu juda oddiy. Haqiqatan ham, agar siz biror marta grafikda nuqtalarni chizgan bo'lsangiz va ularni chiziqlar yoki egri chiziqlar bilan bog'lagan bo'lsangiz, siz undan allaqachon foydalangansiz!
Ikki nuqta orqali cheksiz miqdordagi 2 darajali ko'phadlarni chizishingiz mumkin. Ulardan bittasini tanlash uchun uchinchi nuqta kerak bo'ladi. Tasvir:
Birinchi darajali polinomni ko'rib chiqing, . Agar siz ushbu funktsiyani grafikda chizmoqchi bo'lsangiz, sizga nechta nuqta kerak? Biz bilamizki, bu chiziq hosil qiluvchi chiziqli funktsiyadir va shuning uchun u kamida ikkita nuqtaga muhtoj. Keyin, ikkinchi darajali polinom funksiyani ko'rib chiqing, . Bu kvadratik funktsiya, shuning uchun grafikni chizish uchun kamida uchta nuqta kerak. Uchinchi darajali polinom haqida nima deyish mumkin? Kamida to'rt ball. Va hokazo va hokazo.
Bu xususiyatning chindan ham ajoyib tomoni shundaki, polinom funktsiyasi darajasi va hech bo'lmaganda nuqtalar, biz bu polinom funksiya uchun qo'shimcha nuqtalarni olishimiz mumkin. Biz bu qo'shimcha nuqtalarni ekstrapolyatsiya deb ataymiz polinom interpolyatsiyasi.
Sir yaratish
Shu o‘rinda Shamirning aqlli sxemasi ishga tushishini allaqachon tushungandirsiz. Keling, sirimizni aytaylik Ismi? . Biz aylana olamiz grafikdagi bir nuqtaga va darajali ko'phadli funktsiyani toping , bu fikrni qondiradi. Keling, buni eslaylik zarur bo'laklar ostonasi bo'ladi, shuning uchun agar biz chegarani uchta bo'lakka qo'ysak, biz ikkinchi darajali polinom funksiyasini tanlashimiz kerak.
Bizning polinomimiz shaklga ega bo'ladi qayerda и — tasodifiy tanlangan musbat sonlar. Biz shunchaki darajali polinom qurmoqdamiz , bu erda erkin koeffitsient - Bu bizning sirimiz , va keyingi har biri uchun shartlar tasodifiy tanlangan ijobiy koeffitsient mavjud. Agar biz asl misolga qaytsak va buni taxmin qilsak , keyin biz funktsiyani olamiz .
Ushbu nuqtada biz ulanish orqali fragmentlarni yaratishimiz mumkin ichida noyob butun sonlar qayerda (chunki bu bizning sirimiz). Ushbu misolda biz to'rtta bo'lakni uchta chegara bilan taqsimlamoqchimiz, shuning uchun biz tasodifiy nuqtalarni yaratamiz. va to'rt ishonchli kishining har biriga bittadan ochko yuboring, kalitning saqlovchisi. Buni odamlarga ham yetkazamiz , chunki bu ommaviy axborot hisoblanadi va tiklanish uchun zarur .
Sirni qayta tiklash
Biz allaqachon polinom interpolyatsiyasi kontseptsiyasini va u Shamirning chegara sxemasiga asoslanishini muhokama qildik. . To'rtta ishonchli shaxsdan uchtasi qayta tiklamoqchi bo'lganda , ular faqat interpolyatsiya qilishlari kerak o'ziga xos nuqtalari bilan. Buning uchun ular o'z nuqtalarini aniqlashlari mumkin va quyidagi formuladan foydalanib Lagranj interpolyatsiya ko‘phadini hisoblang. Agar dasturlash sizga matematikaga qaraganda tushunarli bo'lsa, u holda pi aslida operatordir for, bu barcha natijalarni ko'paytiradi va sigma for, bu hamma narsani qo'shadi.
da biz buni shunday hal qilishimiz va asl polinom funksiyamizni qaytarishimiz mumkin:
Chunki biz buni bilamiz , tiklanish oddiygina bajarildi:
Xavfli tamsayı arifmetikasidan foydalanish
Garchi biz Shomirning asosiy g'oyasini muvaffaqiyatli qo'llagan bo'lsak ham , biz shu paytgacha e'tibordan chetda qoldirgan muammo bilan qoldik. Bizning polinom funksiyamiz xavfli butun son arifmetikasidan foydalanadi. E'tibor bering, tajovuzkor bizning funktsiyamiz grafigida olgan har bir qo'shimcha nuqta uchun boshqa nuqtalar uchun kamroq imkoniyatlar mavjud. Butun son arifmetikasidan foydalangan holda ko‘p nomli funksiya uchun nuqtalar sonini ko‘paytirishda buni o‘z ko‘zingiz bilan ko‘rishingiz mumkin. Bu bizning belgilangan xavfsizlik maqsadimizga ziddir, chunki tajovuzkor hech bo'lmaganda hech narsani bilmaguncha hech narsani bilmasligi kerak parchalar.
Butun sonli arifmetik sxema qanchalik kuchsizligini ko‘rsatish uchun tajovuzkor ikki ball olgan stsenariyni ko‘rib chiqing. va ommaviy axborotni biladi . Bu ma'lumotlardan u xulosa chiqarishi mumkin , ikkitaga teng va ma'lum qiymatlarni formulaga kiriting и .
Keyin tajovuzkor topa oladi , hisoblash :
Biz aniqlaganimizdan beri tasodifiy tanlangan musbat butun sonlar sifatida cheklangan soni mumkin . Ushbu ma'lumotlardan foydalanib, tajovuzkor xulosa chiqarishi mumkin , chunki 5 dan kattaroq narsa bajariladi salbiy. Biz aniqlaganimizdan beri bu haqiqat bo'lib chiqdi
Keyin tajovuzkor mumkin bo'lgan qiymatlarni hisoblashi mumkin almashtirish в :
Cheklangan imkoniyatlar bilan qiymatlarni tanlash va tekshirish qanchalik oson ekanligi ayon bo'ladi . Bu erda faqat beshta variant mavjud.
Xavfli tamsayı arifmetikasi bilan muammoni yechish
Ushbu zaiflikni bartaraf qilish uchun Shamir modulli arifmetikadan foydalanishni taklif qiladi haqida qayerda и — barcha tub sonlar toʻplami.
Keling, modulli arifmetika qanday ishlashini tezda eslaylik. Qo'llar bilan soat - bu tanish tushuncha. U soatdan foydalanadi . Soat yelkasi o'n ikkiga o'tishi bilan yana birga qaytadi. Ushbu tizimning qiziqarli xususiyati shundaki, biz soatga qarab, soat qo'li qancha aylanishni amalga oshirganligini aniqlay olmaymiz. Biroq, agar soat yelkasi 12 to'rt marta o'tganini bilsak, oddiy formuladan foydalanib o'tgan soatlar sonini to'liq aniqlashimiz mumkin. qayerda bizning bo'luvchimiz (bu erda ), koeffitsient (bo'luvchi asl songa qoldiqsiz necha marta kiradi, bu erda ), va qolgan qismi bo'lib, u odatda modul operator chaqiruvini qaytaradi (bu yerda ). Ushbu qiymatlarning barchasini bilish bizga tenglamani echishga imkon beradi , lekin agar biz koeffitsientni o'tkazib yuborsak, biz hech qachon asl qiymatini tiklay olmaymiz.
Bu bizning sxemamiz xavfsizligini qanday yaxshilashini sxemani avvalgi misolimizga qo'llash va foydalanish orqali ko'rsatishimiz mumkin. . Bizning yangi polinom funksiyamiz , va yangi nuqtalar . Endi asosiy saqlovchilar funktsiyamizni qayta qurish uchun yana bir bor polinom interpolyatsiyasidan foydalanishlari mumkin, faqat bu safar qo'shish va ko'paytirish operatsiyalari modullarni qisqartirish bilan birga bo'lishi kerak. (masalan ).
Ushbu yangi misoldan foydalanib, tajovuzkor ushbu yangi nuqtalardan ikkitasini bilib oldi deb faraz qilaylik, , va ommaviy axborot . Bu safar tajovuzkor o'zida mavjud bo'lgan barcha ma'lumotlarga asoslanib, quyidagi funktsiyalarni chiqaradi, bu erda - barcha musbat sonlar to'plami, va modul koeffitsientini ifodalaydi .
Endi bizning hujumchimiz yana topadi , hisoblash :
Keyin yana urinib ko'radi almashtirish в :
Bu safar u jiddiy muammoga duch keldi. Formulada qiymatlar yetishmayapti , и . Ushbu o'zgaruvchilarning cheksiz sonli birikmalari mavjud bo'lgani uchun u qo'shimcha ma'lumot ololmaydi.
Xavfsizlik masalalari
Shamirning maxfiy almashish sxemasi taklif qiladi axborot nazariyasi nuqtai nazaridan xavfsizlik. Bu shuni anglatadiki, matematika hatto cheksiz hisoblash kuchiga ega bo'lgan hujumchiga ham chidamli. Biroq, sxema hali ham bir nechta ma'lum muammolarni o'z ichiga oladi.
Misol uchun, Shamirning sxemasi yaratmaydi tekshirilishi kerak bo'lgan qismlar, ya'ni odamlar soxta bo'laklarni erkin taqdim etishi va to'g'ri sirni tiklashga xalaqit berishi mumkin. Etarli ma'lumotga ega bo'lgan dushman parcha saqlovchisi hatto o'zgartirish orqali boshqa fragmentni ishlab chiqarishi mumkin o'z xohishingizga ko'ra. Ushbu muammo yordamida hal qilinadi tasdiqlanadigan maxfiy almashish sxemalari, masalan, Feldman sxemasi.
Yana bir muammo shundaki, har qanday bo'lakning uzunligi mos keladigan sirning uzunligiga teng, shuning uchun sirning uzunligini aniqlash oson. Bu muammoni arzimas narsa bilan hal qilish mumkin to'ldirish belgilangan uzunlikka qadar o'zboshimchalik raqamlar bilan sir.
Va nihoyat, shuni ta'kidlash kerakki, bizning xavfsizlik muammolarimiz dizaynning o'zidan tashqariga chiqishi mumkin. Haqiqiy kriptografik ilovalar uchun ko'pincha tajovuzkor dasturni bajarish vaqti, keshlash, ishdan chiqish va hokazolardan foydali ma'lumotlarni olishga harakat qiladigan yon kanal hujumlari xavfi mavjud. Agar bu tashvish tug'dirsa, ishlab chiqish jarayonida funktsiyalar va doimiy qidiruvlar, xotiraning diskda saqlanishiga yo'l qo'ymaslik kabi himoya choralarini qo'llash va ushbu maqola doirasidan tashqarida bo'lgan bir qator boshqa fikrlarni diqqat bilan ko'rib chiqish kerak.
Namoyish
ning Shamirning sir almashish sxemasining interaktiv namoyishi mavjud. Kutubxonaga asoslangan ko'rgazma , bu o'zi mashhur dasturning JavaScript portidir . Katta qiymatlarni hisoblashni unutmang , и biroz vaqt talab qilishi mumkin.
Manba: www.habr.com