განიხილეთ სცენარი, სადაც გჭირდებათ ბანკის სარდაფის უზრუნველყოფა. იგი ითვლება აბსოლუტურად აუღებლად გასაღების გარეშე, რომელიც გეძლევათ მუშაობის პირველივე დღეს. თქვენი მიზანია გასაღების უსაფრთხოდ შენახვა.

ვთქვათ, თქვენ გადაწყვიტეთ გასაღები ყოველთვის თან გქონდეთ და საჭიროების შემთხვევაში უზრუნველყოთ საცავზე წვდომა. მაგრამ თქვენ სწრაფად მიხვდებით, რომ ასეთი გამოსავალი პრაქტიკაში კარგად არ არის მასშტაბური, რადგან თქვენი ფიზიკური ყოფნა საჭიროა ყოველ ჯერზე, როდესაც გახსნით საცავებს. რაც შეეხება შვებულებას, რომელსაც დაპირდნენ? გარდა ამისა, კითხვა კიდევ უფრო საშინელია: რა მოხდება, თუ დაკარგავ ერთადერთი გასაღები?

თქვენი შვებულების გათვალისწინებით, გადაწყვეტთ გასაღების ასლის გაკეთებას და სხვა თანამშრომელს მიანდოთ. თუმცა, გესმით, რომ არც ეს არის იდეალური. გასაღებების რაოდენობის გაორმაგებით, თქვენ ასევე გააორმაგებთ გასაღების მოპარვის შანსებს.

სასოწარკვეთილებაში ანადგურებთ დუბლიკატს და გადაწყვეტთ ორიგინალური გასაღების შუაზე გაყოფას. ახლა თქვენ იფიქრებთ, რომ გასაღების ფრაგმენტებით ორი სანდო ადამიანი ფიზიკურად უნდა დაესწროს გასაღების შესაგროვებლად და სარდაფის გასახსნელად. ეს ნიშნავს, რომ ქურდს უნდა მოიპაროს ორი ცალი, რაც ორჯერ უფრო რთულია, ვიდრე ერთი გასაღების მოპარვა. თუმცა, მალე ხვდები, რომ ეს სქემა არ არის ბევრად უკეთესი, ვიდრე მხოლოდ ერთი გასაღები, რადგან თუ ვინმემ დაკარგა ნახევარი გასაღები, სრული გასაღები ვერ აღდგება.

პრობლემის მოგვარება შესაძლებელია დამატებითი გასაღებებისა და საკეტების სერიით, მაგრამ ეს მიდგომა სწრაფად მოითხოვს много გასაღებები და საკეტები. თქვენ გადაწყვიტეთ, რომ იდეალური დიზაინი იქნება გასაღების გაზიარება ისე, რომ უსაფრთხოება მთლიანად არ იყოს დამოკიდებული ერთ ადამიანზე. თქვენ ასევე ასკვნით, რომ ფრაგმენტების რაოდენობის გარკვეული ზღვარი უნდა იყოს, რომ თუ ერთი ფრაგმენტი დაიკარგება (ან თუ ადამიანი შვებულებაში წავა), მთელი გასაღები ფუნქციონირებს.

როგორ გავაზიარო საიდუმლო

საკვანძო მენეჯმენტის ამ ტიპის სქემაზე ფიქრობდა ადი შამირი 1979 წელს, როდესაც მან გამოაქვეყნა თავისი ნამუშევარი "როგორ გავაზიარო საიდუმლო". სტატიაში მოკლედ არის განმარტებული ე.წ ზღვრული სქემა საიდუმლო მნიშვნელობის (როგორიცაა კრიპტოგრაფიული გასაღები) ეფექტურად დაყოფისთვის ნაწილები. მაშინ, როდის და მხოლოდ მაშინ, როცა მაინც საქართველოს ნაწილები აწყობილია, თქვენ შეგიძლიათ მარტივად აღადგინოთ საიდუმლო .

უსაფრთხოების თვალსაზრისით, ამ სქემის მნიშვნელოვანი თვისებაა ის, რომ თავდამსხმელმა არ უნდა იცოდეს აბსოლუტურად არაფერი, თუ არ აქვს ნაწილები. ყოფნაც კი ნაწილები არ უნდა მოგაწოდოთ რაიმე ინფორმაცია. ჩვენ ვუწოდებთ ამ ქონებას სემანტიკური უსაფრთხოება.

პოლინომიური ინტერპოლაცია

შამირის ზღურბლის სქემა კონცეფციის ირგვლივ აგებული მრავალწევრი ინტერპოლაცია. თუ თქვენ არ იცნობთ ამ კონცეფციას, ეს სინამდვილეში საკმაოდ მარტივია. სინამდვილეში, თუ თქვენ ოდესმე დახატეთ წერტილები გრაფიკზე და შემდეგ დააკავშირეთ ისინი ხაზებით ან მრუდებით, თქვენ უკვე გამოიყენეთ იგი!

ორი წერტილის მეშვეობით შეგიძლიათ დახაზოთ 2 ხარისხის პოლინომები შეუზღუდავი რაოდენობით. მათგან ერთადერთის ასარჩევად საჭიროა მესამე წერტილი. ილუსტრაცია: ვიკიპედია

განვიხილოთ მრავალწევრი პირველი ხარისხით, . თუ გსურთ ამ ფუნქციის დახატვა გრაფიკზე, რამდენი ქულა გჭირდებათ? კარგად, ჩვენ ვიცით, რომ ეს არის წრფივი ფუნქცია, რომელიც ქმნის წრფეს და ამიტომ მას მინიმუმ ორი წერტილი სჭირდება. შემდეგი, განიხილეთ მრავალწევრი ფუნქცია მეორე ხარისხით, . ეს არის კვადრატული ფუნქცია, ასე რომ, მინიმუმ სამი ქულაა საჭირო გრაფიკის გამოსაყენებლად. რას იტყვით პოლინომზე სამი ხარისხის მქონე? მინიმუმ ოთხი ქულა. Და ასე შემდეგ.

ამ თვისებაში ყველაზე მაგარი ის არის, რომ მრავალწევრი ფუნქციის ხარისხის გათვალისწინებით და მაინც წერტილები, ჩვენ შეგვიძლია გამოვიტანოთ დამატებითი ქულები ამ პოლინომიური ფუნქციისთვის. ჩვენ ვუწოდებთ ამ დამატებითი პუნქტების ექსტრაპოლაციას მრავალწევრი ინტერპოლაცია.

საიდუმლოს შედგენა

შეიძლება უკვე მიხვდით, რომ სწორედ აქ მოქმედებს შამირის ჭკვიანური სქემა. მოდით ვთქვათ ჩვენი საიდუმლო - რამდენად . შეგვიძლია შემობრუნება გრაფიკის წერტილამდე და გამოვიდეს მრავალწევრი ფუნქცია ხარისხით , რომელიც აკმაყოფილებს ამ პუნქტს. შეგახსენებთ რომ იქნება ჩვენი საჭირო ფრაგმენტების ბარიერი, ასე რომ, თუ ზღურბლს დავაყენებთ სამ ფრაგმენტზე, უნდა ავირჩიოთ პოლინომიური ფუნქცია მეორე ხარისხით.

ჩვენს მრავალწევრს ექნება ფორმა სად и - შემთხვევით შერჩეული დადებითი მთელი რიცხვები. ჩვენ უბრალოდ ვაშენებთ მრავალწევრს ხარისხით , სადაც თავისუფალი კოეფიციენტი  - ეს არის ჩვენი საიდუმლო და ყოველი მომდევნოსთვის თვალსაზრისით არის შემთხვევით შერჩეული დადებითი კოეფიციენტი. თუ დავუბრუნდებით თავდაპირველ მაგალითს და ვივარაუდებთ, რომ , შემდეგ ვიღებთ ფუნქციას .

ამ ეტაპზე შეგვიძლია ფრაგმენტების გენერირება შეერთებით უნიკალური მთელი რიცხვები სად (რადგან ეს ჩვენი საიდუმლოა). ამ მაგალითში ჩვენ გვინდა გავანაწილოთ ოთხი ფრაგმენტი სამი ზღურბლით, ასე რომ ჩვენ შემთხვევით ვაგენერირებთ ქულებს და გაუგზავნეთ თითო ქულა ოთხივე სანდო პირს, გასაღების მცველებს. ჩვენ ასევე ვაცნობებთ ხალხს ამის შესახებ , ვინაიდან ეს საჯარო ინფორმაციად ითვლება და აუცილებელია აღდგენისთვის .

საიდუმლოს აღდგენა

ჩვენ უკვე განვიხილეთ პოლინომიური ინტერპოლაციის კონცეფცია და ის, თუ როგორ უდევს იგი შამირის ზღურბლის სქემას. . როცა ოთხი რწმუნებულიდან ნებისმიერ სამს სურს აღდგენა მათ მხოლოდ ინტერპოლაცია სჭირდებათ თავისი უნიკალური წერტილებით. ამისათვის მათ შეუძლიათ განსაზღვრონ თავიანთი ქულები და გამოთვალეთ ლაგრანგის ინტერპოლაციის პოლინომი შემდეგი ფორმულის გამოყენებით. თუ პროგრამირება თქვენთვის უფრო ნათელია, ვიდრე მათემატიკა, მაშინ pi არსებითად ოპერატორია for, რომელიც ამრავლებს ყველა შედეგს და სიგმა არის for, რომელიც ამატებს ყველაფერს.

at ჩვენ შეგვიძლია გადავჭრათ ეს ასე და დავაბრუნოთ ჩვენი თავდაპირველი მრავალწევრი ფუნქცია:

ვინაიდან ჩვენ ვიცით ეს , აღდგენა შესრულებულია უბრალოდ:

არაუსაფრთხო მთელი რიცხვის არითმეტიკის გამოყენება

მიუხედავად იმისა, რომ ჩვენ წარმატებით გამოვიყენეთ შამირის ძირითადი იდეა , დაგვრჩენია პრობლემა, რომელიც აქამდე იგნორირებულია. ჩვენი პოლინომიური ფუნქცია იყენებს არაუსაფრთხო მთელი რიცხვების არითმეტიკას. გაითვალისწინეთ, რომ ყოველი დამატებითი წერტილისთვის, რომელსაც თავდამსხმელი იღებს ჩვენი ფუნქციის გრაფიკზე, ნაკლებია სხვა ქულების შესაძლებლობა. ამის დანახვა შეგიძლიათ საკუთარი თვალით, როდესაც ასახავთ მზარდი რაოდენობა პოლინომიური ფუნქციისთვის მთელი არითმეტიკის გამოყენებით. ეს კონტრპროდუქტიულია ჩვენი უსაფრთხოების მიზნისთვის, რადგან თავდამსხმელმა აბსოლუტურად არაფერი უნდა იცოდეს მანამ, სანამ არ ექნება ფრაგმენტები.

იმის საჩვენებლად, თუ რამდენად სუსტია მთელი არითმეტიკული წრე, განიხილეთ სცენარი, რომელშიც თავდამსხმელმა მიიღო ორი ქულა. და იცის საჯარო ინფორმაცია, რომ . ამ ინფორმაციით მას შეუძლია დაასკვნოს უდრის ორს და შეაერთეთ ცნობილი მნიშვნელობები ფორმულაში и .

შემდეგ თავდამსხმელს შეუძლია იპოვოს , ითვლიან :

ვინაიდან ჩვენ განვსაზღვრეთ როგორც შემთხვევით შერჩეული დადებითი მთელი რიცხვები, შესაძლებელია შეზღუდული რაოდენობა . ამ ინფორმაციის გამოყენებით თავდამსხმელს შეუძლია დაასკვნა , ვინაიდან 5-ზე მეტი არაფერი გამოდგება უარყოფითი. ეს სიმართლეა, რადგან ჩვენ დავადგინეთ

შემდეგ თავდამსხმელს შეუძლია გამოთვალოს შესაძლო მნიშვნელობები ჩანაცვლება в :

შეზღუდული ვარიანტებით ცხადი ხდება, რამდენად მარტივია მნიშვნელობების შერჩევა და შემოწმება . აქ მხოლოდ ხუთი ვარიანტია.

ამოცანის ამოხსნა არაუსაფრთხო მთელი რიცხვის არითმეტიკით

ამ დაუცველობის აღმოსაფხვრელად შამირი გვთავაზობს მოდულარული არითმეტიკის გამოყენებას, ჩანაცვლებას on სად и - ყველა მარტივი რიცხვის სიმრავლე.

მოდით სწრაფად გავიხსენოთ როგორ მუშაობს მოდულური არითმეტიკა. საათი ხელით ნაცნობი კონცეფციაა. ის იყენებს საათს, რომელიც არის . როგორც კი საათის ისარი თორმეტს გადის, ის უბრუნდება ერთს. ამ სისტემის საინტერესო თვისება ის არის, რომ უბრალოდ საათის დათვალიერებით, ჩვენ არ შეგვიძლია დავასკვნათ, რამდენი ბრუნი მოახდინა საათის ისრმა. თუმცა, თუ ვიცით, რომ საათის ისრმა 12-ს ოთხჯერ გასცდა, შეგვიძლია სრულად განვსაზღვროთ გასული საათების რაოდენობა მარტივი ფორმულის გამოყენებით. სად  არის ჩვენი გამყოფი (აქ ),  არის კოეფიციენტი (რამდენჯერ შედის გამყოფი თავდაპირველ რიცხვში ნაშთის გარეშე, აქ ), და  არის ნაშთი, რომელიც ჩვეულებრივ აბრუნებს მოდულო ოპერატორის ზარს (აქ ). ყველა ამ მნიშვნელობის ცოდნა საშუალებას გვაძლევს ამოხსნათ განტოლება , მაგრამ თუ გამოვტოვებთ კოეფიციენტს, ვერასდროს შევძლებთ თავდაპირველი მნიშვნელობის აღდგენას.

ჩვენ შეგვიძლია ვაჩვენოთ, თუ როგორ აუმჯობესებს ეს ჩვენი სქემის უსაფრთხოებას სქემის ჩვენს წინა მაგალითზე და გამოყენებით . ჩვენი ახალი მრავალწევრი ფუნქცია და ახალი პუნქტები . ახლა გასაღების მცველებს შეუძლიათ კიდევ ერთხელ გამოიყენონ პოლინომიური ინტერპოლაცია ჩვენი ფუნქციის აღსადგენად, მხოლოდ ამჯერად შეკრებისა და გამრავლების ოპერაციებს თან უნდა ახლდეს მოდულის შემცირება. (მაგალითად ).

ამ ახალი მაგალითის გამოყენებით, დავუშვათ, რომ თავდამსხმელმა ისწავლა ორი ახალი პუნქტი, და საჯარო ინფორმაცია . ამჯერად თავდამსხმელი, მის ხელთ არსებული ყველა ინფორმაციის საფუძველზე, გამოსცემს შემდეგ ფუნქციებს, სადაც  არის ყველა დადებითი მთელი რიცხვის სიმრავლე და წარმოადგენს მოდულის კოეფიციენტს .

ახლა ჩვენი თავდამსხმელი ისევ პოულობს , გამოთვლა :

შემდეგ ის კვლავ ცდილობს ჩანაცვლება в :

ამჯერად მას სერიოზული პრობლემა აქვს. ფორმულას აკლია მნიშვნელობები , и . ვინაიდან ამ ცვლადების კომბინაციების უსასრულო რაოდენობაა, მას არ შეუძლია რაიმე დამატებითი ინფორმაციის მიღება.

უსაფრთხოების მოსაზრებები

შამირის საიდუმლო გაზიარების სქემა გვთავაზობს უსაფრთხოება ინფორმაციის თეორიის თვალსაზრისით. ეს ნიშნავს, რომ მათემატიკა მდგრადია შეუზღუდავი გამოთვლითი სიმძლავრის მქონე თავდამსხმელის წინააღმდეგაც კი. თუმცა, წრე ჯერ კიდევ შეიცავს რამდენიმე ცნობილ პრობლემას.

მაგალითად, შამირის სქემა არ ქმნის შესამოწმებელი ფრაგმენტები, ანუ ადამიანებს შეუძლიათ თავისუფლად წარმოადგინონ ყალბი ფრაგმენტები და ხელი შეუშალონ სწორი საიდუმლოს აღდგენას. მტრულად განწყობილ ფრაგმენტს, რომელსაც აქვს საკმარისი ინფორმაცია, შეეძლო სხვა ფრაგმენტის შექმნაც კი შეცვლით თქვენი შეხედულებისამებრ. ეს პრობლემა მოგვარებულია გამოყენებით გადამოწმებადი საიდუმლო გაზიარების სქემები, როგორიცაა ფელდმანის სქემა.

კიდევ ერთი პრობლემა ის არის, რომ ნებისმიერი ფრაგმენტის სიგრძე უდრის შესაბამისი საიდუმლოს სიგრძეს, ამიტომ საიდუმლოს სიგრძის დადგენა ადვილია. ამ პრობლემის მოგვარება შესაძლებელია წვრილმანით padding საიდუმლო თვითნებური რიცხვებით ფიქსირებულ სიგრძემდე.

დაბოლოს, მნიშვნელოვანია აღინიშნოს, რომ ჩვენი უსაფრთხოების საზრუნავი შეიძლება გასცდეს თავად დიზაინს. რეალურ სამყაროში კრიპტოგრაფიული აპლიკაციებისთვის, ხშირად არსებობს გვერდითი არხის შეტევების საფრთხე, როდესაც თავდამსხმელი ცდილობს ამოიღოს სასარგებლო ინფორმაცია აპლიკაციის შესრულების დროიდან, ქეშირებიდან, ავარიებიდან და ა.შ. თუ ეს შემაშფოთებელია, განვითარებისას ფრთხილად უნდა იქნას განხილული დამცავი ზომების გამოყენება, როგორიცაა ფუნქციები და მუდმივი დროის ძიება, მეხსიერების დისკზე შენახვის თავიდან აცილება და რიგი სხვა მოსაზრებები, რომლებიც სცილდება ამ სტატიის ფარგლებს.

დემო

წლის ეს გვერდი არსებობს შამირის საიდუმლო გაზიარების სქემის ინტერაქტიული დემონსტრირება. დემონსტრაცია ბიბლიოთეკის საფუძველზე ssss-js, რომელიც თავად არის პოპულარული პროგრამის JavaScript პორტი ssss. გაითვალისწინეთ, რომ დიდი მნიშვნელობების გამოთვლა , и შეიძლება გარკვეული დრო დასჭირდეს.

წყარო: www.habr.com