Նայենք այն սցենարը, երբ անհրաժեշտ է ապահովել բանկային պահոցների անվտանգությունը: Այն համարվում է ամբողջովին անբարձրաստիճան առանց բանալիի, որը ձեզ տալիս են աշխատանքի առաջին օրը: Ձեր նպատակը եզակի և վստահելի պահպանել բանալին:

Վերլուծենք, դուք որոշել եք ամբողջ ժամանակ պահել բանալին ձեր մոտ, տրամադրելով մուտք պահոցին անհրաժեշտության դեպքում: Բայց շատ շուտ դուք կբռնեք, որ նման որոշումը իրականում չես կարող масштабировать, քանի որ ամեն անգամ պահոցն բացելու համար անհրաժեշտ է ձեր ֆիզիկական ներկայությունը: Իսկ կթողնե՞ք ամբաստարկը, որը ձեզ խոստացվում էր: Բացի այդ, ավելի հուզող հարց է՝ իսկ ի՞նչ կլինի, եթե դուք կորցնեք միակ բանալին:

ՉՔՄԱՆԻՃԱՄ դուք որոշել եք ստեղծել բանալիի պատճեն և վստահել այն մեկ այլ աշխատակցի: Բայց դուք հասկանում եք, որ սա նույնպես կատարյալ չէ: Բանալիների քանակը կրկնապատկելով, դուք նաև կրկնապատկեցիք բանալիի գողության հնարավորությունները:

Հուսահատվելով, դուք ոչնչացնում եք պատճենը և որոշում եք բաժանել սկզբնական բանալին երկու մասի: Այսպիսով, դուք կարծում եք, որ երկու վստահելի անձինք, որոնք ունեն բանալիի հատվածները, պետք է ֆիզիկական առկայություն ունենան, որպեսզի հավաքի բանալին և բացի պահոցը: Սա նշանակում է, որ գողին անհրաժեշտ է գողանալ երկու հատված, ինչը երկակի դժվարություն է մեկ բանալիի գողանալու համար: Բայց շուտով դուք հասկանում եք, որ այս սխեման չնչին է լավ, քան միայն մեկ բանալին, քանի որ եթե որևէ մեկը կորցնի բանալիի կեսը, ամբողջ բանալին վերականգնել չի լինի:

Հարցը կարող է լուծվել մի շարք լրացուցիչ բանալիներով և կողպեքներով, բայց նման մոտեցմամբ շուտով անհրաժեշտ կլինի բազմաթիվ բանալիներ և կողպեկներ: Դուք որոշում եք, որ համարժեք սխեմայում պետք է բաժանել բանալին, որպեսզի անվտանգությունն ամբողջությամբ մեկ մարդու վրա չհենվի: Դուք նաև եզրակացնում եք, որ պետք է գոյություն ունենա որոշակի քանակի հատվածներ, որպեսզի մեկ հատվածի կորուստը (կամ եթե մեկը գնաց արձակուրդ) ամբողջ բանալին մնա գործնական:

Ինչպե՞ս բաժանել գաղտնիքը

Այս բանալու կառավարման սխեմայի մասին մտածել է Ադի Շամիրը 1979 թվականին, երբ հրապարակեց իր աշխատանքը «Ինչպես բաժանել գաղտնիքը». Արսում կարճ նկարագրվում է նշված պահոյի սխեմա՝ արդյունավետ գաղտնի արժեքի (օրինակ՝kriptografic key) բաժանելու համար հանդիպանակների: Այնուհանդերձ, երբ և միայն երբ առնվազն Այս հոդվածից հանդիպանակներ հավաքվում են, կարելի է հեշտությամբ վերականգնել գաղտնիքը .

Ապահովության տեսանկյունից, այս սխեմայի կարևոր հատկությունն այն է, որ հանցագործը ոչինչ չպետք է իմանա, եթե չունի առնվազն հանդիպանակներ: Ն навіть կին այս հանդիպանակների լինելը պետք է մեզ տեղեկատվություն չտա: Մենք այս հատկությունը կոչում ենք սեմանտիկ անվտանգություն Քաղաքական ինտերպոլացիա.

Շամիրի պահոյի սխեման կառուցված է

քաղաքական ինտերպոլացիայի գաղափարի շուրջ անցկացված է կոնցեպտի շուրջ պոլինոմային ինտերպոլյացիայիԵթե դուք ծանոթ չեք այս գաղափարին, այն իսկապես բավականին պարզ է: Իրականում, եթե երբևէ գծել եք կետեր գծանկարում և ապա կապել եք դրանք գծերով կամ կորերով, ապա դուք արդեն օգտագործել եք այն:

Երկու կետերի միջոցով կարող է անցնել անսահման թվով 2-րդ աստիճանի բազմագիծ: Դրանցից մեկը ընտրելու համար անհրաժեշտ է երրորդ կետ: Ilustracia: Վիքիպեդիա

Նայենք 1-րդ աստիճանով բազմագծին, . Եթե ցանկանում եք կառուցել այս ֆունկցիան գծանկարում, քանի կետ է ձեզ անհրաժեշտ: Մենք գիտենք, որ դա գծային ֆունկցիա է, որը ձևավորում է գիծ, ուստի անհրաժեշտ է առնվազն երկու կետ: Հետո դիտարկենք 2-րդ աստիճանի բազմագիծ, . Սա քառակուսային ֆունկցիա է, ուստի գծանկարը կառուցելու համար անհրաժեշտ է առնվազն երեք կետ: Ինչպես է արտադրանքը 3-րդ աստիճանի բազմագծի դեպքում? Առնվազն չորս կետ: Եվ այլն:

Իրապես այս հատկության օգտակար կողմերից մեկն այն է, որ ունենալով բազմագծի ֆունկցիայի աստիճանը և առնվազն կետեր, մենք կարող ենք ծագեցնել ավելցուկային կետեր այս բազմագծային ֆունկցիայի համար: Այդ ավելցուկային կետերի միջակայքը մենք կոչում ենք բազմագծային միջակայք.

Գաղտնիքի ստեղծում

Հնարավոր է, դուք արդեն հասկացել եք, որ այստեղ մտնում է Շամիրի խելացի սխեման: Նևենք մեր գաղտնիքը — սա . Մենք կարող ենք փոխել գծանկարի կետում և մտածել բազմագծային ֆունկցիայի մասին, որի աստիճանը , որը բավարարում է այս կետը: Հիշեցնենք, որ մեր պահանջվող կտորների շեմը կլինի, ուստի եթե մենք սահմանենք շեմը երեք կտոր, ապա պետք է ընտրենք 2-րդ աստիճանի բազմագիծ:

Մեր բազմագիծը կլինի տեսքով , где և — պատահականորեն ընտրված դրական ամբողջ թվեր: Մենք պարզապես կառուցում ենք 2-րդ աստիճանի բազմագիծ, որտեղ ազատ գործակցիչը է մեր գաղտնիքը,  , իսկ մնացած յուրաքանչյուր տարր ունի պատահականորեն ընտրված դրական գործակից: Եթե վերադառնանք սկզբնական օրինակին և ենթադրենք, որ , ապա մենք կունենանք ֆունկցիա Այս փուլում մենք կարող ենք արտադրել ֆрагменты, միացնելով .

հատուկ ամբողջ թվեր (որովհետև սա մեր գաղտնիքն է): Այս օրինակով մենք ցանկանում ենք բաժանել չորս ֆрагմենտ՝ երեք շեմով, ուստի պատահականորեն արտադրում ենք կետեր , где և ուղարկում մեկ կետ յուրաքանչյուրին չորս վստահելի մարդկանց, որոնք մուտքի բանալիներ են: Մենք նաև հայտնում ենք մարդկանց, որ , քանի որ սա համարվում է հասարակ տեղեկություն և անհրաժեշտ է վերականգնման համար: Գաղտնիքի վերականգնում .

Մենք արդեն քննարկել ենք բազմագծային միջակայքի գաղափարը և այն, ինչը հիմք է հանդիսանում Շամիրի շեմային սխեմայի համար

. Երբ ցանկացած երեքի չորս վստահելի մարդիկ ցանկանում են վերականգնել , նրանց պարզապես անհրաժեշտ է միջավայրել նրանց յուրահատուկ կետերով: Այս նպատակով նրանք կարող են որոշել իրենց կետերը: առանձնահատկություններով։ Այս նպատակով նրանք կարող են սահմանել իրենց կետերը և հաշվել Լագրանժի միջանկյալ բազմաձևը հետևյալ բանաձևով։ Եթե ծրագրավորումը ձեզ ավելի հայտնի է, քան մաթեմատիկան, ապա π—ը հիմնականում օպերատոր է մանավանդ, որն բազմապատկում է բոլոր արդյունքները, mientras σ—ը մանավանդ, որը գումարում է բոլորը։

Երբ կարող ենք լուծել այս կերպ և վերադարձնել մեր նախնական պոլինոմային ֆունկցիան։

Երջանիկ ենք, որ , վերականգնումը իրականացվում է պարզապես։

Անվտանգ չհաշվարկվող ամբողջաթիվ առարկաների օգտագործումը

Թեև մենք հաջողությամբ կիրառել ենք Շամիրի հիմնական գաղափարը , դեռ մնում է խնդիր, որը մենք անտեսել ենք առայժմ։ Մեր պոլինոմային ֆունկցիան օգտագործում է անվտանգ չհաշվարկվող ամբողջաթիվ առարկաներ։ Լավ հիշեք, որ յուրաքանչյուր լրացուցիչ կետ, որը հարձակվողը ստանում է մեր ֆունկցիայի գրաֆիկում, թողնում է քիչ հնարավորություններ այլ կետերի համար։ Սա կարող եք տեսնել ձեր աչքերով, երբ կառուցում եք գրաֆիկ՝ ավելացնելով պոլինոմային ֆունկցիայի կետերի թիվը, օգտագործելով ամբողջաթիվ առարկաներ։ Սա հակառակ արդյունք է մեր անվտանգության գծային նպատակին, քանի որ ով որու էլ չպետք է տեղեկություն ունենա, մինչև նրանք ունենան գոնե փողոցներ։

Ցույց տալու համար, թե որքան թուլ է ամբողջաթիվ առարկաների համակարգը, դիտենք սցենար, որտեղ հարձակվողը ստացել է երկու կետներ և գիտի հանրային տեղեկությունները, որ ։ Այս տեղեկատվությունից նա կարող է ստանալ , որը հավասար է երկուսին, և մեղադրել հայտնի արժեքները և .

Այնուհետև հարձակողը կարող է գտնել , հաշվելով :

Երբ մենք սահմանել ենք այս որոշմամբ ընտրված դրական ամբողջական թվեր, կա սահմանափակ թվով հնարավորություններ։ Այս տեղեկատվության մասին հարձակվողը կարող է ստանալ , քանի որ ամեն ինչ, որն ավելի մեծ է քան 5-ը, դարձնում է սա բացասական։ Սա առաքվում է ճշմարիտ, քանի որ մենք սահմանել ենք

Այնուհետև հարձակողը կարող է հաշվել հնարավոր արժեքները , փոխարինելով մեջ :

Սահմանափակ տարբերակներով, համար դարձնում է պարզ, թե որքան հեշտ է ընտրել և ստուգել արժեքները ։ Ահա այստեղ ընդամենը հինգ տարբերակ կա։

Անվտանգ չհաշվարկվող ամբողջաթիվ առարկաների խնդրի լուծումը

Այս խոցելիությունը վերացնելու համար Շամիրը առաջարկում է օգտագործել մոդուլային ариֆմետիկան՝ փոխարինելով ըստ , где և — բոլոր առաջնային թվերի բազմությունը։

Հիշենք արագ, ինչպես է աշխատում մոդուլային ариֆմետիկան։ Ժամացույցը ծանոթ կոնցեպտ է։ Այն օգտագործում է ժամեր, որոնք են ։ Երբ ժամացույցի սլաքը անցնում է տասներկուսն, այն վերադարձնում է մեկին։ Այս համակարգի հետաքրքիր առանձնահատկությունն այն է, որ պարզապես դիտելով ժամացույցը, մենք չենք կարող հասկանալ, թե որքան անգամ է ժամացույցի սլաքը անցել։ Բայց եթե մենք գիտենք, որ ժամացույցի սլաքը անցել է 12-ը 4 անգամ, կարելի է պարզ բանաձևով ամբողջությամբ որոշել անցած ժամերը։ , где  — սա nuestro բաժանող (որտեղ ),  — սա համամետներ (առավելութի քանակը, որն առանց մնացորդի որպես սկզբնական համարը, այստեղ Կամ  — սա մնացորդն է, որը սովորաբար վերադարձնում է մոդուլի օպերատորը (որտեղ ). Բոլոր այս արժեքների գիտությունը թույլ է տալիս մեզ լուծել հավասարումը , բայց եթե մենք անտեսենք համամետը, ապա երբեք չենք կարող վերականգնել սկզբնական արժեքը։

Կ можем ենք ցուցադրել, թե ինչպես է դա բարելավում մեր սխեմայի անվտանգության մակարդակը, կիրառելով սխեման մեր նախորդ օրինակին և օգտագործելով . Մեր նոր բազմաֆունկցիոնալ ֆունկցիան , իսկ նոր կետերը . Այժմ բանալիների պահապանները կրկին կարող են օգտագործել բազմաֆունկցիոնալ միջօրեական ՝ մեզ համար վերականգնելու մեր ֆունկցիան, բայց այս անգամ գումարման և բազմապատկման գործողությունները պետք է ուղեկցվեն մոդուլի կրճատմամբ (օրինակ՝ ).

Այս նոր օրինակով, կմեռնություն ենթադրում ենք, որ հարձակում կատարողը գիտի այս նոր կետերից երկուսը, , և հանրային տեղեկությունները . Այս անգամ հարձակում կատարողը, հիմնվելով բոլոր ձեռքում եղած տեղեկությունների վրա, դուրս է բերում հետևյալ ֆունկցիաները, որտեղ  — բոլոր դրական ամբողջ թիվերի հավաքածուն, իսկ ներկայացնում է մոդուլի համամետը .

Այժմ մեր հարձակում կատարողը կրկին գտնում է , հաշվելով :

Այժմ նա կրկին փորձում է դուրս բերել , փոխարինելով մեջ :

Այս անգամ նա լրջագույն խնդրի առաջ կանգնած է։ Ֆորմուլայում բացակայում են արժեքները , և . Քանի որ կա անվերջ թվով այդ փոփոխականների կոմբինացիաներ, նա չի կարող ստանալ լրացուցիչ տեղեկություն։

Ապահովության անդիստումներ

Շամիրի գաղտնիքը բաժանելու սխեման առաջարկում է ապահովություն տեղեկատվության տեսության կողմից. Դա նշանակում է, որ մաթեմատիկան դիմադրում է նույնիսկ անսահման կարողությունների հարձակման կատարող։ Այնուամենայնիվ, սխեման դեռ ունի մի շարք հայտնի խնդիրներ։

Օրինակ, Շամիրի սխեման չի ստեղծում չափորոշիչ կիսաձայններ, այսինքն' մարդիկ կարող են ազատորեն ներկայացնել կեղծ կիսաձայններ և խանգարել ճիշտ գաղտնիքի վերականգնմանը։ Այստեղ վնասակար կիսաձայնի պահապանն, բավարար տեղեկատվություն ունենալով, նույնիսկ կարող է արտադրել այլ կիսաձայն՝ փոխելով ի իր ցանկությամբ։ Այս խնդիրը լուծվում է անդրադարձվող գաղտնիքների բաժանման սխեմաների միջոցով, ինչպիսիք են Ֆելդմանի սխեման։

Մյուս խնդիրը այն է, որ որևէ կիսաձայնի երկարությունը հավասար է համապատասխան գաղտնիքի երկարությանը, այնքան հեշտ է պարզել գաղտնիքի երկարությունը։ Այս խնդիրը լուծվում է պարզագույն լինելով գաղտնիքը մահվան թվերով մինչև ամրացված երկարությունը։

Վերջապես, կարևոր է նշել, որ մեր անվտանգության մտահոգությունները կարող են դուրս գալ հենց սխեմայի շրջանակներից։ Իրական գրիպտոգրաֆիական հավելվածներում հաճախ գոյություն ունի երրորդ կողմի ալիքներով հարձակումների վտանգ, երբ ախտանշանակը փորձում է տեղեկատվություն ստանալ հավելվածի գործարկման ժամանակ, կэшավորման, խաթարումների միջոցով և այլն։ Եթե դա մտահոգություն է առաջացնում, ապա մշակման ընթացքում անհրաժեշտ է ուշադիր հաշվի առնել պաշտպանիչ միջոցների օգտագործումը, ինչպիսիք են ֆունկցիաներն ու եռաչափ որոնումը մշտական գործածման ժամանակ, կանխարգելել հիշողության պահպանման նժարային սարքերում և մտածել մի շարք այլ բաներ, որոնք դուրս են այս հոդվածի շրջանակներից։

Դեմո

Նա այս էջում գտնվում է Շամիրի գաղտնիքի բաժանման սխեմայի ինտերակտիվ իրավիճակային ցուցադրություն։ Ցուցադրությունը կատարվել է ssss-js, որը ինքնուրույն является JavaScript-пորտing հայտնի ծրագրից ssss:։ Գիտակցեք, որ մեծ արժեքների հաշվարկը , և կարող է պահանջել որոշ ժամանակ։

Ընտանիք: habr.com