Պատկերացրեք մի իրավիճակ, երբ դուք պետք է ապահովեք բանկի պահոցը։ Այն համարվում է լիովին անթափանցելի առանց այն բանալու, որը ձեզ տրվում է աշխատանքի առաջին օրը։ Ձեր նպատակն է բանալին անվտանգ պահել։

Ենթադրենք, որ դուք որոշում եք բանալին միշտ ձեզ մոտ պահել՝ անհրաժեշտության դեպքում թույլ տալով մուտք գործել պահոց։ Սակայն դուք շուտով կհասկանաք, որ նման լուծումը գործնականում լավ չի գործում, քանի որ ամեն անգամ պահոցը բացելու համար անհրաժեշտ է ձեր ֆիզիկական ներկայությունը։ Իսկ ի՞նչ կասեք ձեզ խոստացված արձակուրդի մասին։ Եվ ավելի սարսափելի է հարցը. ի՞նչ կլինի, եթե կորցնեք ձեր միակ բանալին։

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

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

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

Ինչպես կիսվել գաղտնիքով

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

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

Բազմանդամային ինտերպոլյացիա

Շամիրի շեմային սխեման կառուցված հայեցակարգի շուրջ բազմանդամային ինտերպոլյացիաԵթե ​​դուք ծանոթ չեք այս հասկացությանը, ապա այն իրականում բավականին պարզ է։ Իրականում, եթե երբևէ գրաֆիկի վրա կետեր եք նկարել, ապա դրանք գծերով կամ կորերով միացրել, ապա արդեն օգտագործել եք այն։

Երկու կետերով կարելի է անցկացնել անսահմանափակ թվով 2-րդ աստիճանի բազմանդամներ։ Դրանցից միայն մեկը ընտրելու համար անհրաժեշտ է երրորդ կետը։ Նկարազարդում՝ Wikipedia

Եկեք դիտարկենք մեկ աստիճանի բազմանդամ՝ Եթե ​​ուզում եք այս ֆունկցիան պատկերել գրաֆիկի վրա, քանի՞ կետ է ձեզ անհրաժեշտ։ Մենք գիտենք, որ դա գծային ֆունկցիա է, որը կազմում է գիծ, ​​ուստի անհրաժեշտ է առնվազն երկու կետ։ Հաջորդը, դիտարկենք երկրորդ աստիճանի բազմանդամային ֆունկցիա։ Սա քառակուսային ֆունկցիա է, ուստի այն գծագրելու համար անհրաժեշտ է առնվազն երեք կետ։ Իսկ ինչպե՞ս կլինի երրորդ աստիճանի բազմանդամի դեպքում։ Առնվազն չորս կետ։ Եվ այսպես շարունակ։

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

Գաղտնիք հորինելը

Դուք գուցե արդեն հասկացել եք, որ այստեղ է, որ Շամիրի խորամանկ ծրագիրը գործի է դրվում։ Ենթադրենք, որ մեր գաղտնիքը - Ից Մենք կարող ենք վերափոխել գրաֆիկի վրա գտնվող կետին և ստեղծեք աստիճան ունեցող բազմանդամային ֆունկցիա , որը բավարարում է այս կետը։ Հիշե՛ք, որ կլինի մեր պահանջվող բեկորների շեմը, ուստի եթե մենք սահմանենք շեմը երեք բեկորի, մենք պետք է ընտրենք երկրորդ աստիճանի բազմանդամային ֆունկցիա։

Մեր բազմանդամը կունենա տեսքը Որտեղ и — պատահականորեն ընտրված դրական ամբողջ թվեր։ Մենք պարզապես կառուցում ենք աստիճան ունեցող բազմանդամ , որտեղ ազատ գործակիցն է  - սա մեր գաղտնիքն է , և հաջորդողներից յուրաքանչյուրը անդամների թիվը պատահականորեն ընտրված դրական գործակից է։ Եթե վերադառնանք սկզբնական օրինակին և ենթադրենք, որ , ապա մենք ստանում ենք ֆունկցիան .

Այս փուլում մենք կարող ենք բեկորներ ստեղծել՝ միացնելով եզակի ամբողջ թվեր Որտեղ (քանի որ դա մեր գաղտնիքն է): Այս օրինակում մենք ուզում ենք բաշխել չորս բեկորներ երեք շեմով, ուստի պատահականորեն միավորներ ենք ստեղծում և ուղարկեք մեկական կետ բանալու պահապան չորս վստահելի անձանցից յուրաքանչյուրին։ Մենք նաև մարդկանց ասում ենք, որ , քանի որ սա համարվում է հանրային տեղեկատվություն և անհրաժեշտ է վերականգնման համար .

Գաղտնիքի վերականգնում

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

Ի Մենք կարող ենք լուծել սա հետևյալ կերպ և ստանալ մեր սկզբնական բազմանդամային ֆունկցիան՝

Քանի որ մենք դա գիտենք , վերականգնում այն իրականացվում է պարզապես՝

Անապահով ամբողջ թվերի թվաբանության օգտագործում

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

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

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

Քանի որ մենք սահմանել ենք քանի որ պատահականորեն ընտրված դրական ամբողջ թվերի դեպքում հնարավոր է սահմանափակ թվով Այս տեղեկատվությունն օգտագործելով՝ հարձակվողը կարող է եզրակացնել , քանի որ 5-ից մեծ ցանկացած թիվ կբավարարի բացասական։ Սա ճիշտ է, քանի որ մենք որոշել ենք

Հարձակվողը կարող է հաշվարկել հնարավոր արժեքները , փոխարինելով в :

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

Անվտանգ ամբողջ թվերի թվաբանության խնդրի լուծում

Այս խոցելիությունը վերացնելու համար Շամիրը առաջարկում է օգտագործել մոդուլային թվաբանություն՝ փոխարինելով մասին Որտեղ и — բոլոր պարզ թվերի բազմությունը։

Եկեք արագորեն վերանայենք, թե ինչպես է գործում մոդուլային թվաբանությունը։ Սլաքներով ժամացույցը ծանոթ հասկացություն է։ Այն օգտագործում է ժամացույց, որը Հենց որ ժամի սլաքը անցնում է տասներկուսի սահմանը, այն վերադառնում է մեկի։ Այս համակարգի հետաքրքիր առանձնահատկությունն այն է, որ մենք չենք կարող եզրակացնել, թե քանի պտույտ է կատարել ժամի սլաքը՝ պարզապես ժամացույցին նայելով։ Սակայն, եթե գիտենք, որ ժամի սլաքը անցել է 12 անգամ չորս անգամ, կարող ենք լիովին որոշել անցած ժամերի քանակը՝ օգտագործելով պարզ բանաձև։ Որտեղ  - սա մեր բաժանարարն է (այստեղ ),  — սա գործակիցն է (քանի անգամ է բաժանարարը առանց մնացորդի մտնում սկզբնական թվի մեջ, այստեղ) ), և  — սա մնացորդն է, որը սովորաբար վերադարձվում է մոդուլո օպերատորը կանչելով (այստեղ Այս բոլոր արժեքները իմանալը թույլ է տալիս լուծել հավասարումը , բայց եթե մենք բաց թողնենք որևէ գործակից, մենք երբեք չենք կարողանա վերականգնել սկզբնական արժեքը։

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

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

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

Ապա նա կրկին փորձում է հետ քաշվել , փոխարինելով в :

Այս անգամ նա լուրջ խնդիր ունի։ Բանաձևում բացակայում են արժեքներ։ , и Քանի որ այս փոփոխականների համակցությունների անվերջ թիվ կա, նա չի կարող որևէ լրացուցիչ տեղեկատվություն ստանալ։

Անվտանգության նկատառումներ

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

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

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

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

Դեմո

On այս էջը Կա Շամիրի գաղտնի տվյալների փոխանակման սխեմայի ինտերակտիվ ցուցադրություն։ Ցուցադրությունը հիմնված է գրադարանի վրա։ ssss-js, որն ինքնին հայտնի ծրագրի JavaScript պորտ է ՍԱՊԾՆկատի ունեցեք, որ մեծ արժեքների հաշվարկը , и դա կարող է որոշ ժամանակ պահանջել։

Source: www.habr.com