Մտածեք մի սցենար, որտեղ դուք պետք է ապահովեք բանկային պահոց: Այն համարվում է բացարձակ անառիկ առանց բանալի, որը ձեզ տրվում է աշխատանքի հենց առաջին օրը։ Ձեր նպատակն է ապահով պահել բանալին:
Ենթադրենք, դուք որոշել եք բանալին միշտ ձեզ մոտ պահել՝ անհրաժեշտության դեպքում ապահովելով մուտք դեպի պահեստ: Բայց դուք արագ կհասկանաք, որ նման լուծումը գործնականում այնքան էլ մեծ չէ, քանի որ ձեր ֆիզիկական ներկայությունը պահանջվում է ամեն անգամ, երբ բացում եք պահեստը: Ի՞նչ կասեք այն արձակուրդի մասին, որը ձեզ խոստացել էին։ Բացի այդ, հարցն ավելի վախեցնող է. իսկ եթե կորցնեիք ձեր միակ բանալին:
Հաշվի առնելով ձեր արձակուրդը, դուք որոշում եք պատճենել բանալին և այն վստահել մեկ այլ աշխատակցի: Այնուամենայնիվ, հասկանում եք, որ սա նույնպես իդեալական չէ։ Կրկնապատկելով բանալիների քանակը՝ դուք նաև կրկնապատկում եք բանալիների գողության հավանականությունը:
Հուսահատության մեջ դուք ոչնչացնում եք կրկնօրինակը և որոշում եք բուն բանալին կիսով չափ կիսել: Այժմ դուք կարող եք մտածել, որ երկու վստահելի մարդիկ, որոնք ունեն առանցքային բեկորներ, պետք է ֆիզիկապես ներկա գտնվեն բանալին հավաքելու և պահոցը բացելու համար: Սա նշանակում է, որ գողը պետք է գողանա երկու կտոր, ինչը երկու անգամ ավելի դժվար է, քան մեկ բանալի գողանալը: Այնուամենայնիվ, դուք շուտով հասկանում եք, որ այս սխեման շատ ավելի լավ չէ, քան ընդամենը մեկ բանալի, քանի որ եթե ինչ-որ մեկը կորցնում է կես բանալին, ամբողջական բանալին չի կարող վերականգնվել:
Խնդիրը կարող է լուծվել մի շարք լրացուցիչ բանալիների և կողպեքների միջոցով, բայց այս մոտեցումը արագ կպահանջի շատ բանալիներ և կողպեքներ. Դուք որոշում եք, որ իդեալական դիզայնը կլինի բանալին կիսելն այնպես, որ անվտանգությունն ամբողջությամբ չհենվի մեկ անձի վրա: Դուք նաև եզրակացնում եք, որ բեկորների քանակի համար պետք է լինի որոշակի շեմ, որպեսզի եթե մեկ հատվածը կորչի (կամ եթե մարդ մեկնում է արձակուրդ), ամբողջ բանալին մնա գործունակ:
Ինչպես կիսվել գաղտնիքով
Հիմնական կառավարման այս սխեմայի մասին Ադի Շամիրը մտածեց 1979 թվականին, երբ նա հրապարակեց իր աշխատանքը . Հոդվածում հակիրճ բացատրվում է այսպես կոչված 
շեմի սխեման՝ գաղտնի արժեքը (օրինակ՝ ծածկագրային բանալի) արդյունավետորեն բաժանելու համար մասեր. Հետո, երբ և միայն երբ գոնե - ից մասերը հավաքվում են, դուք հեշտությամբ կարող եք վերականգնել գաղտնիքը .
Անվտանգության տեսանկյունից այս սխեմայի կարևոր հատկությունն այն է, որ հարձակվողը չպետք է բացարձակապես որևէ բան իմանա, եթե նա առնվազն չունի մասեր. Նույնիսկ ներկայությունը մասերը չպետք է որևէ տեղեկատվություն տրամադրեն: Մենք կոչում ենք այս գույքը իմաստային անվտանգություն.
Բազմանդամների ինտերպոլացիա
Շամիրի շեմի սխեման կառուցված հայեցակարգի շուրջ բազմանդամ ինտերպոլացիա. Եթե դուք ծանոթ չեք այս հայեցակարգին, ապա այն իրականում բավականին պարզ է: Իրականում, եթե դուք երբևէ գծել եք կետերը գրաֆիկի վրա և այնուհետև դրանք միացրել եք գծերով կամ կորերով, դուք արդեն օգտագործել եք այն:
Երկու կետերի միջոցով կարելի է գծել 2-րդ աստիճանի անսահմանափակ թվով բազմանդամներ։ Դրանցից միակը ընտրելու համար անհրաժեշտ է երրորդ կետ։ Նկարազարդում:
Դիտարկենք առաջին աստիճանով բազմանդամը, . Եթե ցանկանում եք այս ֆունկցիան գծել գրաֆիկի վրա, քանի՞ միավոր է ձեզ անհրաժեշտ: Դե, մենք գիտենք, որ սա գծային ֆունկցիա է, որը կազմում է ուղիղ, և դրա համար անհրաժեշտ է առնվազն երկու կետ: Այնուհետև դիտարկեք XNUMX աստիճանով բազմանդամ ֆունկցիան, . Սա քառակուսի ֆունկցիա է, ուստի գրաֆիկը գծելու համար պահանջվում է առնվազն երեք կետ: Ի՞նչ կասեք երրորդ աստիճանով բազմանդամի մասին: Առնվազն չորս միավոր. Եվ այլն, և այլն:
Այս հատկության իսկապես հետաքրքիր բանն այն է, որ հաշվի առնելով բազմանդամ ֆունկցիայի աստիճանը և առնվազն միավորներ, մենք կարող ենք լրացուցիչ միավորներ ստանալ այս բազմանդամ ֆունկցիայի համար: Մենք անվանում ենք այս լրացուցիչ կետերի էքստրապոլացիա բազմանդամ ինտերպոլացիա.
Գաղտնիք հորինելը
Երևի արդեն հասկացել եք, որ հենց այստեղ է գործում Շամիրի խելացի սխեման: Ասենք մեր գաղտնիքը - Ից . Մենք կարող ենք շրջվել դեպի գրաֆիկի մի կետ և ստացիր աստիճանով բազմանդամ ֆունկցիա , որը բավարարում է այս կետը։ Հիշեցնենք, որ կլինի մեր պահանջվող բեկորների շեմը, ուստի, եթե շեմը սահմանենք երեք ֆրագմենտի, մենք պետք է ընտրենք XNUMX աստիճանով բազմանդամ ֆունկցիա:
Մեր բազմանդամը կունենա ձև Որտեղ и - պատահականորեն ընտրված դրական ամբողջ թվեր: Մենք պարզապես կառուցում ենք աստիճանով բազմանդամ , որտեղ ազատ գործակիցը -Սա է մեր գաղտնիքը , և յուրաքանչյուր հաջորդի համար պայմաններով կա պատահականորեն ընտրված դրական գործակից: Եթե վերադառնանք սկզբնական օրինակին և ենթադրենք, որ , ապա ստանում ենք ֆունկցիան .
Այս պահին մենք կարող ենք միացնելով բեկորներ առաջացնել եզակի ամբողջ թվեր մեջ Որտեղ (որովհետև դա մեր գաղտնիքն է): Այս օրինակում մենք ցանկանում ենք բաժանել չորս բեկորներ երեքի շեմով, այնպես որ մենք պատահականորեն միավորներ ենք ստեղծում և մեկական միավոր ուղարկիր չորս վստահելի մարդկանցից յուրաքանչյուրին՝ բանալին պահապաններին: Այդ մասին մենք էլ մարդկանց տեղյակ ենք պահում , քանի որ սա համարվում է հանրային տեղեկատվություն և անհրաժեշտ է վերականգնման համար .
Գաղտնիքի վերականգնում
Մենք արդեն քննարկել ենք բազմանդամների ինտերպոլացիայի հայեցակարգը և թե ինչպես է այն ընկած Շամիրի շեմային սխեմայի հիմքում։ . Երբ չորս հոգաբարձուներից որևէ մեկը ցանկանում է վերականգնել , նրանց միայն պետք է ինտերպոլացիա անել իր յուրահատուկ կետերով։ Դա անելու համար նրանք կարող են որոշել իրենց միավորները և հաշվարկել Լագրանժի ինտերպոլացիայի բազմանդամը՝ օգտագործելով հետևյալ բանաձևը. Եթե ծրագրավորումը ձեզ համար ավելի պարզ է, քան մաթեմատիկան, ապա pi-ն ըստ էության օպերատոր է for, որը բազմապատկում է բոլոր արդյունքները, իսկ սիգմա է for, որը գումարում է ամեն ինչ:
Ի մենք կարող ենք լուծել այն այսպես և վերադարձնել մեր սկզբնական բազմանդամ ֆունկցիան.
Քանի որ մենք դա գիտենք , վերականգնում արված պարզապես.
Օգտագործելով անապահով ամբողջ թվային թվաբանություն
Չնայած մենք հաջողությամբ կիրառել ենք Շամիրի հիմնական գաղափարը , մնացել ենք մի խնդրի առաջ, որը մինչ այժմ անտեսել ենք։ Մեր բազմանդամ ֆունկցիան օգտագործում է անապահով ամբողջ թվային թվաբանություն։ Նկատի ունեցեք, որ յուրաքանչյուր լրացուցիչ կետի համար, որը հարձակվողը ստանում է մեր ֆունկցիայի գրաֆիկի վրա, այլ կետերի համար ավելի քիչ հնարավորություններ կան: Դուք կարող եք դա տեսնել ձեր սեփական աչքերով, երբ բազմանդամ ֆունկցիայի համար ավելացող միավորներ եք գծում՝ օգտագործելով ամբողջ թվաբանությունը: Սա հակաարդյունավետ է մեր հայտարարած անվտանգության նպատակին, քանի որ հարձակվողը պետք է բացարձակապես ոչինչ իմանա այնքան ժամանակ, քանի դեռ չի ունեցել առնվազն բեկորներ.
Ցույց տալու համար, թե որքան թույլ է ամբողջ թվային թվաբանական սխեման, դիտարկենք մի սցենար, որտեղ հարձակվողը ստացել է երկու միավոր և գիտի հանրային տեղեկատվություն, որ . Այս տեղեկություններից նա կարող է եզրակացնել , հավասար է երկուսի և միացրեք հայտնի արժեքները բանաձևի մեջ и .
Այնուհետև հարձակվողը կարող է գտնել , հաշվելով :
Քանի որ մենք սահմանել ենք Որպես պատահականորեն ընտրված դրական ամբողջ թվեր, հնարավոր է սահմանափակ թվով . Օգտագործելով այս տեղեկությունը՝ հարձակվողը կարող է եզրակացնել , քանի որ 5-ից մեծ ցանկացած բան կարող է անել բացասական. Պարզվում է, որ դա ճիշտ է, քանի որ մենք որոշել ենք
Այնուհետև հարձակվողը կարող է հաշվարկել հնարավոր արժեքները փոխարինելով в :
Սահմանափակ տարբերակներով պարզ է դառնում, թե որքան հեշտ է ընտրել և ստուգել արժեքները . Այստեղ ընդամենը հինգ տարբերակ կա:
Խնդրի լուծում անապահով ամբողջ թվային թվաբանությամբ
Այս խոցելիությունը վերացնելու համար Շամիրն առաջարկում է օգտագործել մոդուլային թվաբանություն՝ փոխարինելով մասին Որտեղ и - բոլոր պարզ թվերի բազմությունը:
Եկեք արագ հիշենք, թե ինչպես է աշխատում մոդուլային թվաբանությունը: Սլաքներով ժամացույցը ծանոթ հասկացություն է: Նա օգտագործում է ժամացույց, որը . Հենց որ ժամացույցը անցնում է տասներկուսին, այն վերադառնում է մեկի: Այս համակարգի հետաքրքիր հատկությունն այն է, որ պարզապես ժամացույցին նայելով՝ մենք չենք կարող եզրակացնել, թե քանի պտույտ է կատարել ժամացույցի սլաքը: Այնուամենայնիվ, եթե մենք իմանանք, որ ժամացույցը անցել է 12 չորս անգամ, մենք կարող ենք ամբողջությամբ որոշել անցած ժամերի քանակը՝ օգտագործելով պարզ բանաձևը. Որտեղ մեր բաժանարարն է (այստեղ ), գործակիցն է (քանի անգամ է բաժանարարը մտնում սկզբնական թվի մեջ առանց մնացորդի, այստեղ ), և մնացորդն է, որը սովորաբար վերադարձնում է մոդուլային օպերատորի զանգ (այստեղ ) Այս բոլոր արժեքների իմացությունը թույլ է տալիս մեզ լուծել հավասարումը , բայց եթե բաց թողնենք գործակիցը, մենք երբեք չենք կարողանա վերականգնել սկզբնական արժեքը։
Մենք կարող ենք ցույց տալ, թե ինչպես է դա բարելավում մեր սխեմայի անվտանգությունը՝ կիրառելով սխեման մեր նախորդ օրինակին և օգտագործելով . Մեր նոր բազմանդամ ֆունկցիան , և նոր կետերը . Այժմ առանցքային պահապանները կարող են ևս մեկ անգամ օգտագործել բազմանդամ ինտերպոլացիա՝ մեր ֆունկցիան վերականգնելու համար, միայն թե այս անգամ գումարման և բազմապատկման գործողությունները պետք է ուղեկցվեն մոդուլային կրճատմամբ։ (օրինակ ).
Օգտագործելով այս նոր օրինակը՝ ենթադրենք, որ հարձակվողը սովորել է այս նոր կետերից երկուսը. , և հանրային տեղեկատվություն . Այս անգամ հարձակվողը, հիմնվելով իր ունեցած ողջ տեղեկատվության վրա, դուրս է բերում հետևյալ գործառույթները, որտեղ բոլոր դրական ամբողջ թվերի բազմությունն է, և ներկայացնում է մոդուլի գործակիցը .
Հիմա մեր հարձակվողը կրկին գտնում է , հաշվարկելով :
Հետո նորից փորձում է փոխարինելով в :
Այս անգամ նա լուրջ խնդիր ունի. Բանաձևում բացակայող արժեքներ , и . Քանի որ կան այս փոփոխականների անսահման թվով համակցություններ, նա չի կարող լրացուցիչ տեղեկություններ ստանալ։
Անվտանգության նկատառումներ
Շամիրի գաղտնի փոխանակման սխեման հուշում է անվտանգությունը տեղեկատվության տեսության տեսանկյունից. Սա նշանակում է, որ մաթեմատիկան դիմացկուն է նույնիսկ անսահմանափակ հաշվողական հզորությամբ հարձակվողի դեմ: Այնուամենայնիվ, շղթան դեռ պարունակում է մի քանի հայտնի խնդիրներ:
Օրինակ, Շամիրի սխեման չի ստեղծում բեկորներ, որոնք պետք է ստուգվեն, այսինքն՝ մարդիկ կարող են ազատորեն ներկայացնել կեղծ բեկորներ և խոչընդոտել ճիշտ գաղտնիքի վերականգնմանը։ Բավարար տեղեկություններ ունեցող թշնամական բեկոր պահողը կարող էր նույնիսկ փոխել մեկ այլ բեկոր ձեր հայեցողությամբ: Այս խնդիրը լուծվում է օգտագործելով Գաղտնի փոխանակման ստուգելի սխեմաներ, ինչպիսին է Ֆելդմանի սխեման։
Մյուս խնդիրն այն է, որ ցանկացած հատվածի երկարությունը հավասար է համապատասխան գաղտնիքի երկարությանը, ուստի գաղտնիքի երկարությունը հեշտ է որոշել: Այս խնդիրը կարելի է լուծել մանրուքներով լիցքավորում գաղտնիք կամայական թվերով մինչև ֆիքսված երկարություն։
Վերջապես, կարևոր է նշել, որ մեր անվտանգության մտահոգությունները կարող են դուրս գալ բուն դիզայնից: Իրական աշխարհի կրիպտոգրաֆիկ հավելվածների համար հաճախ կա կողային ալիքի հարձակումների վտանգ, որտեղ հարձակվողը փորձում է օգտակար տեղեկատվություն կորզել հավելվածի կատարման ժամանակից, քեշից, խափանումներից և այլն: Եթե դա մտահոգիչ է, մշակման ընթացքում պետք է զգույշ ուշադրություն դարձնել պաշտպանիչ միջոցների կիրառմանը, ինչպիսիք են գործառույթները և մշտական ժամանակի որոնումները, հիշողությունը սկավառակի վրա պահելու կանխումը և մի շարք այլ նկատառումներ, որոնք դուրս են այս հոդվածի շրջանակներից:
Դեմո
On Կա Շամիրի գաղտնի փոխանակման սխեմայի ինտերակտիվ ցուցադրություն: Ցուցադրություն՝ հիմնված գրադարանի վրա , որն ինքնին հայտնի ծրագրի JavaScript պորտն է . Նկատի ունեցեք, որ հաշվարկելով մեծ արժեքներ , и կարող է մի քիչ տևել:
Source: www.habr.com