Bank kassasını təmin etməyiniz lazım olan bir ssenarini nəzərdən keçirin. İşin ilk günündə sizə verilən açar olmadan tamamilə keçilməz hesab olunur. Məqsədiniz açarı təhlükəsiz saxlamaqdır.
Tutaq ki, açarı hər zaman yanınızda saxlamağa qərar verdiniz və lazım olduqda kassaya giriş təmin etdiniz. Ancaq tez bir zamanda başa düşəcəksiniz ki, belə bir həll praktikada yaxşı miqyasda deyil, çünki hər dəfə anbarı açmaq üçün fiziki olaraq iştirak etməlisiniz. Bəs sizə vəd edilən tətil haqqında? Bundan əlavə, sual daha qorxuludur: yeganə açarı itirsəniz nə olacaq?
Tətil ideyası ilə açarın surətini çıxarmaq və başqa bir işçiyə həvalə etmək qərarına gəlirsiniz. Ancaq bunun da ideal olmadığını başa düşürsən. Açarların sayını iki dəfə artırmaqla siz açarların oğurlanması şansını da iki dəfə artırdınız.
Çarəsiz, dublikatı məhv edirsiniz və orijinal açarı yarıya bölməyə qərar verirsiniz. İndi siz düşünürsünüz ki, açarı toplamaq və anbarı açmaq üçün açar fraqmentləri olan iki etibarlı şəxs fiziki olaraq orada olmalıdır. Bu o deməkdir ki, oğrunun iki fraqmenti oğurlaması lazımdır ki, bu da bir açarı oğurlamaqdan iki dəfə çətindir. Ancaq tezliklə başa düşürsünüz ki, bu sxem yalnız bir açardan çox da yaxşı deyil, çünki kimsə açarın yarısını itirirsə, tam açarı bərpa etmək mümkün deyil.
Problem bir sıra əlavə açarlar və kilidlər ilə həll edilə bilər, lakin bu yanaşma tez bir zamanda tələb olunacaq много açarlar və qıfıllar. Siz ideal sxemin açarı paylaşmaq olduğuna qərar verdiniz ki, təhlükəsizlik tamamilə bir nəfərə etibar etməsin. Siz həmçinin belə nəticəyə gəlirsiniz ki, fraqmentlərin sayı üçün müəyyən hədd olmalıdır ki, bir fraqment itirilərsə (və ya şəxs tətilə gedirsə) bütün açar işlək qalsın.
Bir sirri necə bölüşmək olar
Bu tip əsas idarəetmə sxemi Adi Şamir tərəfindən 1979-cu ildə işini dərc edərkən düşünülmüşdür . Məqalə qısaca sözdə izah edir 
məxfi dəyərin (məsələn, kriptoqrafik açarın) effektiv şəkildə bölünməsi üçün hədd sxemi hissələri. Sonra, ən azı nə vaxt və yalnız nə vaxt haqqında hissələri yığılır, sirri asanlıqla bərpa edə bilərsiniz .
Təhlükəsizlik nöqteyi-nəzərindən bu sxemin mühüm xüsusiyyəti ondan ibarətdir ki, təcavüzkar heç olmasa heç olmasa heç nə öyrənməməlidir. hissələri. Hətta varlığı hissələri heç bir məlumat verməməlidir. Biz buna mülk deyirik semantik təhlükəsizlik.
Polinom interpolyasiyası
Eşik Şamir sxemi konsepsiyası ətrafında qurulmuşdur polinom interpolyasiyası. Əgər bu konsepsiya ilə tanış deyilsinizsə, əslində çox sadədir. Ümumiyyətlə, əgər siz nə vaxtsa qrafikdə nöqtələr çəkmisinizsə və sonra onları xətlər və ya əyrilərlə birləşdirmisinizsə, siz artıq ondan istifadə etmisiniz!
İki nöqtə vasitəsilə siz 2-ci dərəcəli çoxhədsiz sayda polinom çəkə bilərsiniz. Onlardan yalnız birini seçmək üçün üçüncü nöqtə lazımdır. İllüstrasiya:
Birinci dərəcəli çoxhədli hesab edin, . Bu funksiyanı qrafikdə çəkmək istəyirsinizsə, sizə neçə nöqtə lazımdır? Biz bilirik ki, bu, xətti təşkil edən xətti funksiyadır və buna görə də bizə ən azı iki nöqtə lazımdır. Sonra, iki dərəcəli çoxhədli funksiyanı nəzərdən keçirin, . Bu kvadrat funksiyadır, ona görə də qrafiki çəkmək üçün ən azı üç nöqtə tələb olunur. Üçüncü dərəcəli çoxhədli haqqında necə? Ən azı dörd nöqtə. Və sair və s.
Bu xassə haqqında həqiqətən gözəl şey, polinom funksiyasının dərəcəsini nəzərə alaraq və ən azı xallar, bu çoxhədli funksiya üçün əlavə xallar əldə edə bilərik. Bu əlavə nöqtələrin ekstrapolyasiyası deyirik polinom interpolyasiyası.
Sirr etmək
Yəqin ki, siz artıq başa düşmüsünüz ki, burada Şamirin ağıllı sxemi işə düşür. Tutaq ki, bizim sirrimiz - Mi . dönə bilərik qrafikdəki nöqtəyə qədər və dərəcə ilə çoxhədli funksiya ilə çıxış edin , bu məqamı qane edir. Bunu xatırlayın tələb olunan fraqmentlərin həddi olacaq, ona görə də biz həddi üç fraqmentə təyin etsək, iki dərəcəyə malik çoxhədli funksiyanı seçməliyik.
Polinomumuz formaya sahib olacaq Hara и təsadüfi seçilmiş müsbət tam ədədlərdir. Biz sadəcə dərəcə ilə çoxhədli qururuq , burada sərbəst əmsal - Bu bizim sirrimizdir , və sonrakıların hər biri şərtlər təsadüfi seçilmiş müsbət əmsaldır. İlkin nümunəyə qayıdıb bunu fərz etsək , onda biz funksiyanı alırıq .
Bu nöqtədə biz birləşdirərək fraqmentlər yarada bilərik unikal tam ədədlər Hara (çünki bu bizim sirrimizdir). Bu misalda, üç həddi olan dörd fraqmenti paylamaq istəyirik, buna görə də təsadüfi olaraq xallar yaradırıq. və açarın sahibi olan dörd etibarlı adamın hər birinə bir xal göndərin. Bunu insanlara da deyirik , çünki o, ictimai məlumat sayılır və bərpa üçün zəruridir .
Gizli Bərpa
Biz artıq çoxhədli interpolyasiya anlayışını və onun Şamirin eşikləmə sxeminin əsasını necə təşkil etdiyini müzakirə etdik. . Dörd qəyyumdan üçü bərpa etmək istədikdə , onlar yalnız interpolyasiya etməlidirlər unikal məqamları ilə. Bunun üçün onlar öz məqamlarını müəyyən edə bilərlər və aşağıdakı düsturdan istifadə edərək Laqranc interpolyasiya polinomunu hesablayın. Əgər proqramlaşdırma sizə riyaziyyatdan daha aydındırsa, o zaman pi əslində operatordur for, bütün nəticələri çoxaldır və siqma forbu hər şeyi əlavə edir.
Hazırda biz bunu belə həll edə və orijinal polinom funksiyamızı qaytara bilərik:
Madam ki, biz bunu bilirik , bərpa sadə şəkildə edilir:
Təhlükəsiz tam arifmetikadan istifadə
Baxmayaraq ki, biz Şamirin əsas ideyasını uğurla tətbiq etmişik , indiyə qədər görməzlikdən gəldiyimiz bir problemlə qaldıq. Çoxhədli funksiyamız təhlükəli tam arifmetikadan istifadə edir. Qeyd edək ki, təcavüzkarın funksiya qrafikimizdə əldə etdiyi hər əlavə nöqtə üçün digər nöqtələr üçün daha az imkan var. Tam ədəd arifmetikasından istifadə edərək çoxhədli funksiya üçün artan sayda nöqtələr qurarkən bunu öz gözlərinizlə görə bilərsiniz. Bu, bizim bəyan etdiyimiz təhlükəsizlik məqsədinə əks təsir göstərir, çünki təcavüzkar heç olmasa, heç olmasa heç nə bilməməlidir fraqmentlər.
Tam arifmetik sxemin nə qədər zəif olduğunu nümayiş etdirmək üçün təcavüzkarın iki xal aldığı ssenarini nəzərdən keçirin. və ictimai məlumatı bilir . Bu məlumatdan o, nəticə çıxara bilər , ikiyə bərabərdir və məlum dəyərləri düstura birləşdirin и .
Təcavüzkar daha sonra tapa bilər , saymaq :
Biz müəyyən etdiyimizdən təsadüfi seçilmiş müsbət tam ədədlər kimi, mümkün məhdud sayda var . Bu məlumatla təcavüzkar nəticə çıxara bilər , çünki 5-dən çox olan hər şey edəcək mənfi. Biz müəyyən etdiyimiz üçün bu doğru çıxır
Bundan sonra təcavüzkar mümkün dəyərləri hesablaya bilər əvəz edir в :
Məhdud seçimlərlə dəyərləri götürüb yoxlamağın nə qədər asan olduğu aydın olur . Burada yalnız beş seçim var.
Təhlükəsiz tam arifmetika ilə məsələnin həlli
Bu zəifliyi düzəltmək üçün Şamir modul arifmetikadan istifadə etməyi təklif edir haqqında Hara и bütün sadə ədədlərin çoxluğudur.
Modul arifmetikanın necə işlədiyini tez xatırlayaq. Əl saatları tanış bir anlayışdır. O, saatdan istifadə edir . Saatın əqrəbi on ikini keçən kimi birə qayıdır. Bu sistemin maraqlı xüsusiyyəti ondan ibarətdir ki, sadəcə saata baxaraq, saat əqrəbinin neçə dövrə vurduğunu çıxara bilmərik. Ancaq saat əqrəbinin 12 dəfə dörd dəfə keçdiyini bilsək, sadə bir düsturla keçən saatların sayını tam olaraq təyin edə bilərik. Hara bölənimizdir (burada ), - bu əmsaldır (qalıqsız bölən neçə dəfə orijinal ədədə keçir, burada ), və adətən modul operatoruna zəngi qaytaran qalıqdır (burada ). Bütün bu dəyərləri bilmək bizə tənliyi həll etməyə imkan verir , lakin əmsalı atlasaq, heç vaxt orijinal dəyəri bərpa edə bilməyəcəyik.
Dövrəni əvvəlki nümunəmizə tətbiq etməklə və istifadə etməklə bunun dövrəmizin təhlükəsizliyini necə yaxşılaşdırdığını nümayiş etdirə bilərik. . Yeni çoxhədli funksiyamız , və yeni nöqtələr . İndi əsas gözətçilər funksiyamızı yenidən qurmaq üçün bir daha çoxhədli interpolyasiyadan istifadə edə bilərlər, yalnız bu dəfə toplama və vurma əməliyyatlarından sonra modulun azaldılması aparılmalıdır. (məs ).
Bu yeni nümunədən istifadə edərək, düşünək ki, təcavüzkar bu yeni məqamlardan ikisini öyrənib, , və ictimai məlumat . Bu dəfə təcavüzkar, malik olduğu bütün məlumatlara əsaslanaraq, aşağıdakı funksiyaları göstərir, harada bütün müsbət tam ədədlərin çoxluğudur və modul əmsalını təmsil edir .
İndi təcavüzkarımız yenidən tapır , hesablama :
Sonra yenidən geri çəkilməyə çalışır əvəz edir в :
Bu dəfə onun ciddi problemi var. Formula çatışmayan dəyərlər , и . Bu dəyişənlərin sonsuz sayda kombinasiyası olduğundan o, heç bir əlavə məlumat əldə edə bilmir.
Təhlükəsizlik Mülahizələri
Şamirin gizli paylaşma sxemi təklif edir informasiya təhlükəsizliyi. Bu o deməkdir ki, riyaziyyat hətta qeyri-məhdud hesablama gücünə malik hücumçuya qarşı da güclüdür. Bununla belə, sxem hələ də bir neçə məlum problemi ehtiva edir.
Məsələn, Şamir sxemi yaratmır yoxlanılacaq fraqmentlər, yəni insanlar saxta fraqmentlər təqdim etməkdə və düzgün sirrin bərpasına mane olmaqda sərbəstdirlər. Kifayət qədər məlumatı olan düşmən fraqment qoruyucu hətta dəyişdirərək başqa bir fraqment yarada bilər öz mülahizənizlə. Bu problem ilə həll olunur yoxlanıla bilən gizli paylaşma sxemləriFeldman sxemi kimi.
Başqa bir problem ondan ibarətdir ki, hər hansı fraqmentin uzunluğu müvafiq sirrin uzunluğuna bərabərdir, ona görə də sirrin uzunluğunu asanlıqla müəyyən etmək olar. Bu problem sadəlövhlüklə həll olunur dolgu sabit uzunluğa qədər ixtiyari nömrələrlə gizli.
Nəhayət, qeyd etmək vacibdir ki, təhlükəsizliklə bağlı narahatlıqlarımız sxemin özündən kənara çıxa bilər. Həqiqi kriptoqrafik tətbiqlər üçün, təcavüzkar tətbiqin icra müddətindən, keşləmədən, qəzalardan və s.-dən faydalı məlumatları çıxarmağa çalışdıqda tez-tez yan kanal hücumları təhlükəsi var. Əgər bu narahatlıq doğurursa, siz inkişaf zamanı funksiyalar və daimi axtarışlar kimi qoruyucu vasitələrin istifadəsini diqqətlə nəzərdən keçirməli, yaddaşın diskdə saxlanmasının qarşısını almalı və bu məqalənin əhatə dairəsindən kənarda qalan bir sıra başqa şeyləri nəzərdən keçirməlisiniz.
Demo
Haqqında Şamirin gizli paylaşma sxeminin interaktiv nümayişi var. Nümayiş kitabxananın bazasında aparılıb , özü də məşhur proqramın JavaScript portudur . Qeyd edək ki, böyük dəyərlərin hesablanması , и bir müddət çəkə bilər.
Mənbə: www.habr.com