Банкны агуулахыг хамгаалах шаардлагатай хувилбарыг авч үзье. Энэ нь ажлын эхний өдөр танд өгдөг түлхүүргүйгээр бүрэн гүйцэд боломжгүй гэж тооцогддог. Таны зорилго бол түлхүүрийг найдвартай хадгалах явдал юм.
Та түлхүүрээ үргэлж өөртэйгөө хамт байлгахаар шийдсэн гэж бодъё. Гэхдээ ийм шийдэл нь бодит байдал дээр тийм ч сайн биш гэдгийг та хурдан ойлгох болно, учир нь та хадгалах сангаа нээх бүрт таны бие махбодийг байлгах шаардлагатай байдаг. Чамд амласан амралтаа яах вэ? Үүнээс гадна асуулт нь бүр ч аймшигтай: хэрэв та цорын ганц түлхүүрээ алдсан бол яах вэ?
Амралтаа бодож байгаад түлхүүрийн хуулбарыг хийж, өөр ажилтанд даатгах шийдвэр гаргана. Гэсэн хэдий ч энэ нь тийм ч тохиромжтой биш гэдгийг та ойлгож байна. Түлхүүрийн тоог хоёр дахин нэмэгдүүлснээр та түлхүүр хулгайлах магадлалыг хоёр дахин нэмэгдүүлнэ.
Цөхрөнгөө барсандаа та хуулбарыг устгаж, анхны түлхүүрийг хагасаар хуваахаар шийднэ. Одоо түлхүүрийг цуглуулж, агуулахыг онгойлгохын тулд түлхүүрийн хэлтэрхий бүхий хоёр итгэмжлэгдсэн хүн биечлэн байх ёстой гэж та бодож байна. Энэ нь хулгайч хоёр ширхэг хулгайлах шаардлагатай гэсэн үг бөгөөд энэ нь нэг түлхүүр хулгайлсанаас хоёр дахин хэцүү байдаг. Гэсэн хэдий ч, энэ схем нь зөвхөн нэг түлхүүрээс хамаагүй дээр биш гэдгийг та удахгүй ойлгох болно, учир нь хэн нэгэн хагас түлхүүрээ алдсан тохиолдолд бүрэн түлхүүрийг сэргээх боломжгүй юм.
Асуудлыг хэд хэдэн нэмэлт түлхүүр, цоожны тусламжтайгаар шийдэж болох боловч энэ аргыг хурдан шаардах болно много түлхүүр ба түгжээ. Аюулгүй байдал нь нэг хүнээс бүрэн хамаарахгүйн тулд түлхүүрийг хуваалцах нь хамгийн тохиромжтой загвар гэж та шийднэ. Хэрэв нэг фрагмент алдагдсан (эсвэл хүн амралтаараа явах юм бол) түлхүүр бүхэлдээ ажиллах боломжтой байхын тулд фрагментийн тоонд тодорхой босго байх ёстой гэж та дүгнэж байна.
Нууцыг хэрхэн хуваалцах вэ
Энэ төрлийн гол удирдлагын схемийн талаар Ади Шамир 1979 онд бүтээлээ нийтлэхдээ бодож байжээ . Нийтлэлд гэж нэрлэгддэг зүйлийг товч тайлбарлав 
нууц утгыг (криптограф түлхүүр гэх мэт) үр ашигтай хуваах босго схем хэсгүүд. Дараа нь, хэзээ, зөвхөн хэзээ, ядаж л нь эд ангиудыг угсарсан тул та нууцыг хялбархан сэргээж чадна .
Аюулгүй байдлын үүднээс авч үзвэл энэ схемийн чухал шинж чанар нь халдагч дор хаяж ямар ч мэдээлэлгүй бол юу ч мэдэхгүй байх ёстой. хэсгүүд. Тэр ч байтугай оршихуй хэсгүүд нь ямар ч мэдээлэл өгөх ёсгүй. Бид үүнийг өмч гэж нэрлэдэг семантик аюулгүй байдал.
Олон гишүүнт интерполяци
Шамирын босго схем үзэл баримтлалын хүрээнд бүтээгдсэн олон гишүүнт интерполяци. Хэрэв та энэ ойлголтыг сайн мэдэхгүй бол энэ нь үнэхээр энгийн зүйл юм. Үнэн хэрэгтээ, хэрэв та график дээр цэг зурж, дараа нь тэдгээрийг шугам эсвэл муруйгаар холбосон бол та үүнийг аль хэдийн ашигласан байна!
Хоёр цэгээр дамжуулан та 2-р зэрэглэлийн хязгааргүй олон тооны олон гишүүнт зурж болно. Тэднээс цорын ганцыг нь сонгохын тулд танд гурав дахь цэг хэрэгтэй. Дүрслэл:
Нэгдүгээр зэрэгтэй олон гишүүнтийг авч үзье. . Хэрэв та энэ функцийг график дээр зурахыг хүсвэл хэдэн цэг хэрэгтэй вэ? Энэ нь шугам үүсгэдэг шугаман функц бөгөөд дор хаяж хоёр цэг хэрэгтэй гэдгийг бид мэднэ. Дараа нь хоёрдугаар зэрэгтэй олон гишүүнт функцийг авч үзье. . Энэ нь квадрат функц тул графикийг зурахын тулд дор хаяж гурван цэг шаардлагатай. Гуравдугаар зэрэгтэй олон гишүүнтийг яах вэ? Дор хаяж дөрвөн оноо. Гэх мэтчилэн.
Энэ өмчийн хамгийн гайхалтай зүйл бол олон гишүүнт функцийн зэрэг болон наад зах нь Хэрэв бид энэ олон гишүүнт функцийн нэмэлт цэгүүдийг гаргаж авах боломжтой. Бид эдгээр нэмэлт цэгүүдийн экстраполяци гэж нэрлэдэг олон гишүүнт интерполяци.
Нууц зохиож байна
Эндээс л Шамирын ухаалаг арга хэрэгждэг гэдгийг та аль хэдийн ойлгосон байх. Нууцаа хэлье Байна уу . Бид эргэж чадна график дээрх цэг хүртэл зэрэгтэй олон гишүүнт функцийг гарга , энэ нь энэ цэгийг хангаж байна. Үүнийг эргэн санацгаая нь бидний шаардлагатай фрагментуудын босго байх тул хэрэв бид босгыг гурван фрагментээр тогтоовол хоёр дахь зэрэгтэй олон гишүүнт функцийг сонгох ёстой.
Манай олон гишүүнт хэлбэр хэлбэртэй байна хаана и - санамсаргүй байдлаар сонгосон эерэг бүхэл тоо. Бид зүгээр л зэрэгтэй олон гишүүнт байгуулж байна , энд чөлөөт коэффициент - Энэ бол бидний нууц , мөн дараагийнх бүрийн хувьд санамсаргүй байдлаар сонгосон эерэг коэффициент байдаг. Хэрэв бид анхны жишээ рүү буцаж очоод үүнийг төсөөлвөл , дараа нь бид функцийг авна .
Энэ үед бид холбох замаар фрагментуудыг үүсгэж болно дахь өвөрмөц бүхэл тоо хаана (Учир нь энэ бол бидний нууц). Энэ жишээн дээр бид гурван босготой дөрвөн фрагментийг тараахыг хүсч байгаа тул санамсаргүй байдлаар оноо үүсгэдэг. мөн түлхүүрийг хадгалагч дөрвөн итгэмжлэгдсэн хүнд тус бүр нэг оноо илгээ. Үүнийг бид ч хүмүүст мэдэгддэг , учир нь энэ нь олон нийтийн мэдээлэлд тооцогддог бөгөөд сэргээхэд зайлшгүй шаардлагатай .
Нууцыг сэргээж байна
Бид олон гишүүнт интерполяцийн тухай ойлголт, энэ нь Шамирын босго схемийн үндэс суурь болох талаар аль хэдийн ярилцсан. . Дөрвөн итгэмжлэгдсэн төлөөлөгчийн гурав нь сэргээхийг хүссэн үед , тэд зөвхөн интерполяци хийх хэрэгтэй өөрийн гэсэн өвөрмөц оноотой. Үүнийг хийхийн тулд тэд оноогоо тодорхойлж болно Дараах томьёог ашиглан Лагранжийн интерполяцийн олон гишүүнтийг тооцоол. Хэрэв програмчлал нь танд математикаас илүү ойлгомжтой байвал pi нь үндсэндээ оператор юм for, энэ нь бүх үр дүнг үржүүлдэг ба сигма нь for, энэ нь бүх зүйлийг нэмдэг.
үед Бид үүнийг ингэж шийдэж, анхны олон гишүүнт функцийг буцаана:
Учир нь бид үүнийг мэднэ , сэргээх энгийн хийсэн:
Аюулгүй бүхэл арифметик ашиглах
Хэдийгээр бид Шамирын үндсэн санааг амжилттай хэрэгжүүлсэн , бидэнд өнөөг хүртэл үл тоомсорлож ирсэн асуудал үлдлээ. Манай олон гишүүнт функц нь аюултай бүхэл тооны арифметикийг ашигладаг. Манай функцын график дээр халдагчийн олж авсан нэмэлт цэг болгонд бусад цэгүүдийн боломж бага байгааг анхаарна уу. Бүхэл тооны арифметик ашиглан олон гишүүнт функцийн өсөн нэмэгдэж буй цэгүүдийг зурахдаа та үүнийг өөрийн нүдээр харж болно. Энэ нь бидний тодорхойлсон аюулгүй байдлын зорилгод сөрөг нөлөө үзүүлж байна, учир нь халдлага үйлдэгч ядаж байх хүртлээ юу ч мэдэхгүй байх ёстой хэлтэрхий.
Бүхэл тооны арифметик хэлхээ хэр сул болохыг харуулахын тулд халдагч хоёр оноо авсан хувилбарыг авч үзье. олон нийтийн мэдээллийг мэддэг . Энэ мэдээллээс тэрээр дүгнэлт хийж чадна , хоёртой тэнцүү бөгөөд мэдэгдэж буй утгуудыг томъёонд оруулна уу и .
Халдагчид дараа нь олох боломжтой , тоолох :
Бид тодорхойлсоноос хойш санамсаргүй байдлаар сонгосон эерэг бүхэл тоонуудын хувьд боломжит тоо хязгаарлагдмал . Энэ мэдээллийг ашиглан халдагчид дүгнэлт хийж чадна , учир нь 5-аас их зүйл хийх болно сөрөг. Бид тодорхойлсны дараа энэ нь үнэн болж байна
Дараа нь халдагч боломжит утгыг тооцоолж болно сольж байна в :
Хязгаарлагдмал сонголттой утгыг сонгох, шалгах нь хэр хялбар болох нь тодорхой болно . Энд зөвхөн таван сонголт байна.
Аюулгүй бүхэл арифметикийн асуудлыг шийдвэрлэх
Энэхүү эмзэг байдлыг арилгахын тулд Шамир модуль арифметикийг солихыг санал болгож байна тухай хаана и - бүх анхны тооны олонлог.
Модульчлагдсан арифметик хэрхэн ажилладагийг хурдан санацгаая. Гартай цаг бол танил ойлголт юм. Тэр цаг ашигладаг . Цагийн зүү арван хоёр өнгөрмэгц нэг рүү буцдаг. Энэ системийн сонирхолтой шинж чанар бол зүгээр л цагийг хараад л бид цагийн зүү хэдэн эргэлт хийснийг хэлж чадахгүй. Гэсэн хэдий ч, хэрэв бид цагийн зүү 12 дөрвөн удаа өнгөрснийг мэдвэл энгийн томъёогоор хэдэн цаг өнгөрснийг бүрэн тодорхойлж чадна. хаана нь бидний хуваагч (энд ), коэффициент (хуваагч анхны тоонд үлдэгдэлгүй хэдэн удаа ордог, энд ), ба Үлдэгдэл нь ихэвчлэн модулийн операторын дуудлагыг буцаадаг (энд ). Эдгээр бүх утгыг мэдэх нь бидэнд тэгшитгэлийг шийдэх боломжийг олгодог , гэхдээ бид коэффициентийг алдсан тохиолдолд анхны утгыг хэзээ ч сэргээж чадахгүй.
Энэ нь бидний схемийн аюулгүй байдлыг хэрхэн сайжруулж байгааг бид өмнөх жишээн дээр схемийг ашиглаж, ашиглан харуулж чадна. . Манай шинэ олон гишүүнт функц , мөн шинэ оноо . Одоо гол хамгаалагчид бидний функцийг сэргээхийн тулд полиномын интерполяцийг дахин ашиглах боломжтой, зөвхөн энэ удаад нэмэх, үржүүлэх үйлдлүүд нь модулийн бууралттай хамт байх ёстой. (жишээ нь ).
Энэхүү шинэ жишээн дээр халдагч эдгээр шинэ онооны хоёрыг сурсан гэж бодъё. , олон нийтийн мэдээлэл . Энэ удаад халдагч өөрт байгаа бүх мэдээлэлдээ тулгуурлан дараах функцуудыг гаргана, хаана бүх эерэг бүхэл тоонуудын олонлог ба модулийн коэффициентийг илэрхийлнэ .
Одоо манай халдагч дахин оллоо , тооцоолох :
Дараа нь тэр дахин оролдоно сольж байна в :
Энэ удаад түүнд ноцтой асуудал тулгараад байна. Формула дутуу утгууд , и . Эдгээр хувьсагчийн хязгааргүй тооны хослол байдаг тул тэрээр нэмэлт мэдээлэл авч чадахгүй.
Аюулгүй байдлын талаар анхаарах зүйлс
Шамирын нууц хуваалцах схемийг санал болгож байна мэдээллийн онолын үүднээс аюулгүй байдал. Энэ нь математик нь хязгааргүй тооцоолох хүчин чадалтай халдагчдад тэсвэртэй гэсэн үг юм. Гэсэн хэдий ч хэлхээнд мэдэгдэж байгаа хэд хэдэн асуудал байсаар байна.
Жишээлбэл, Шамирын схемийг бий болгодоггүй шалгах шаардлагатай хэсгүүд, өөрөөр хэлбэл хүмүүс хуурамч хэлтэрхийг чөлөөтэй танилцуулж, зөв нууцыг сэргээхэд саад учруулж болно. Хангалттай мэдээлэлтэй дайсагнасан фрагмент хадгалагч нь өөрчлөх замаар өөр фрагмент үүсгэж болно өөрийн үзэмжээр. Энэ асуудлыг ашиглан шийддэг баталгаажуулах боломжтой нууц хуваалцах схемүүдФельдманы схем гэх мэт.
Өөр нэг асуудал бол аливаа фрагментийн урт нь харгалзах нууцын урттай тэнцүү байдаг тул нууцын уртыг тодорхойлоход хялбар байдаг. Энэ асуудлыг өчүүхэн аргаар шийдэж болно дэвсгэр тогтмол урт хүртэл дурын тоо бүхий нууц.
Эцэст нь хэлэхэд, бидний аюулгүй байдлын асуудал нь загвараас хэтэрч магадгүй гэдгийг анхаарах нь чухал юм. Бодит ертөнцийн криптограф програмуудын хувьд халдагчид програмын гүйцэтгэлийн хугацаа, кэш, эвдрэл гэх мэт хэрэгтэй мэдээллийг гаргаж авахыг оролддог хажуугийн сувгийн халдлагын аюул ихэвчлэн байдаг. Хэрэв энэ нь санаа зовоож байгаа бол функцууд болон байнгын хайлт зэрэг хамгаалалтын арга хэмжээг ашиглах, санах ойг дискэнд хадгалахаас урьдчилан сэргийлэх болон энэ зүйлийн хамрах хүрээнээс гадуур бусад хэд хэдэн зүйлийг анхаарч үзэх хэрэгтэй.
Демо
дээр Шамирын нууц хуваалцах схемийн интерактив үзүүлбэр байдаг. Номын санд суурилсан үзүүлбэр , энэ нь өөрөө алдартай програмын JavaScript порт юм . Том утгыг тооцоолж байгааг анхаарна уу , и хэсэг хугацаа шаардагдаж магадгүй юм.
Эх сурвалж: www.habr.com