Konsideru scenaron, kie vi devas sekurigi bankan trezorejon. Ĝi estas konsiderata absolute nepenetrebla sen ŝlosilo, kiun vi ricevas en la unua labortago. Via celo estas sekure konservi la ŝlosilon.
Ni diru, ke vi decidas konservi la ŝlosilon ĉe vi ĉiam, provizante aliron al la stokado laŭbezone. Sed vi rapide rimarkos, ke tia solvo ne bone skalas praktike, ĉar via fizika ĉeesto estas postulata ĉiufoje kiam vi malfermas la stokadon. Kio pri la ferio al vi estis promesita? Krome, la demando estas eĉ pli timiga: kio se vi perdus vian solan ŝlosilon?
Konsiderante viajn feriojn, vi decidas fari kopion de la ŝlosilo kaj konfidi ĝin al alia dungito. Tamen vi komprenas, ke ĉi tio ankaŭ ne estas ideala. Duobligante la nombron da ŝlosiloj, vi ankaŭ duobligas la ŝancojn de ŝtelo de ŝlosiloj.
En malespero, vi detruas la duplikaton kaj decidas dividi la originalan ŝlosilon en duono. Nun, vi pensus, ke du fidindaj homoj kun ŝlosilaj fragmentoj devus ĉeesti fizike por kolekti la ŝlosilon kaj malfermi la trezorejon. Ĉi tio signifas, ke ŝtelisto bezonas ŝteli du pecojn, kio estas duoble pli malfacila ol ŝteli unu ŝlosilon. Tamen, vi baldaŭ rimarkas, ke ĉi tiu skemo ne estas multe pli bona ol nur unu ŝlosilo, ĉar se iu perdas duonon de ŝlosilo, la plena ŝlosilo ne povas esti reakirita.
La problemo povas esti solvita per serio de pliaj ŝlosiloj kaj seruroj, sed ĉi tiu aliro rapide postulos multe ŝlosiloj kaj seruroj. Vi decidas, ke la ideala dezajno estus dividi la ŝlosilon por ke sekureco ne dependu tute de unu persono. Vi ankaŭ konkludas, ke devas ekzisti iu sojlo por la nombro da fragmentoj, por ke se unu fragmento estas perdita (aŭ se homo ferias), la tuta ŝlosilo restas funkcia.
Kiel dividi sekreton
Tiu speco de esenca administradskemo estis pripensita fare de Adi Shamir en 1979 kiam li publikigis sian laboron . La artikolo mallonge klarigas la tn 
sojla skemo por efike dividi sekretan valoron (kiel ekzemple kriptografa ŝlosilo) en partoj. Tiam, kiam kaj nur kiam almenaŭ el partoj estas kunvenitaj, vi povas facile restarigi la sekreton .
De sekureca vidpunkto, grava eco de ĉi tiu skemo estas, ke la atakanto ne devus scii absolute ion ajn krom se li havas almenaŭ partoj. Eĉ la ĉeesto partoj ne devus provizi ajnan informon. Ni nomas ĉi tiun posedaĵon semantika sekureco.
Polinoma interpolado
Shamir-sojloskemo konstruita ĉirkaŭ la koncepto polinoma interpolado. Se vi ne konas ĉi tiun koncepton, ĝi fakte estas sufiĉe simpla. Fakte, se vi iam desegnis punktojn sur grafeo kaj poste kunligis ilin per linioj aŭ kurboj, vi jam uzis ĝin!
Per du punktoj oni povas desegni senliman nombron da polinomoj de grado 2. Por elekti la solan el ili, oni bezonas trian punkton. Ilustraĵo:
Konsideru polinomon kun grado unu, . Se vi volas bildigi ĉi tiun funkcion sur grafeo, kiom da punktoj vi bezonas? Nu, ni scias, ke ĉi tio estas lineara funkcio kiu formas linion kaj do ĝi bezonas almenaŭ du punktojn. Poste, konsideru polinoman funkcion kun grado du, . Ĉi tio estas kvadrata funkcio, do almenaŭ tri punktoj estas postulataj por bildigi la grafeon. Kio pri polinomo kun grado tri? Almenaŭ kvar poentoj. Kaj tiel plu kaj tiel plu.
La vere bonega afero pri ĉi tiu posedaĵo estas tio, donita la gradon de la polinoma funkcio kaj almenaŭ punktoj, ni povas derivi pliajn punktojn por ĉi tiu polinoma funkcio. Ni nomas la ekstrapolon de ĉi tiuj aldonaj punktoj polinoma interpolado.
Farante sekreton
Eble vi jam konsciis, ke ĉi tie eniras la lerta skemo de Shamir. Ni diru nian sekreton Estas . Ni povas turni nin al punkto sur la grafeo kaj elpensu polinoman funkcion kun grado , kiu kontentigas ĉi tiun punkton. Ni rememoru tion estos nia sojlo de postulataj fragmentoj, do se ni fiksas la sojlon al tri fragmentoj, ni devas elekti polinoman funkcion kun grado du.
Nia polinomo havos la formon kie и — hazarde elektitaj pozitivaj entjeroj. Ni nur konstruas polinomon kun grado , kie la libera koeficiento - Jen nia sekreto , kaj por ĉiu el la postaj terminoj estas hazarde elektita pozitiva koeficiento. Se ni revenos al la originala ekzemplo kaj supozas tion , tiam ni ricevas la funkcion .
Je ĉi tiu punkto ni povas generi fragmentojn per konekto unikaj entjeroj en kie (ĉar ĝi estas nia sekreto). En ĉi tiu ekzemplo, ni volas distribui kvar fragmentojn kun sojlo de tri, do ni hazarde generas punktojn. kaj sendu po unu poenton al ĉiu el la kvar fidindaj homoj, la gardantoj de la ŝlosilo. Ni ankaŭ sciigas tion al homoj , ĉar tio estas konsiderata publika informo kaj necesas por reakiro .
Retrovi la sekreton
Ni jam diskutis la koncepton de polinoma interpolado kaj kiel ĝi subestas la sojloskemon de Shamir . Kiam iuj tri el la kvar kuratoroj volas restarigi , ili bezonas nur interpoli kun siaj propraj unikaj punktoj. Por fari tion, ili povas determini siajn punktojn kaj kalkulu la polinomon de interpolado de Lagrange uzante la sekvan formulon. Se programado estas pli klara al vi ol matematiko, tiam pi estas esence operatoro for, kiu multobligas ĉiujn rezultojn, kaj sigma estas for, kiu aldonas ĉion.
ĉe ni povas solvi ĝin tiel kaj redoni nian originalan polinoman funkcion:
Ĉar ni scias tion , Retrovo farita simple:
Uzante nesekuran entjeran aritmetikon
Kvankam ni sukcese aplikis la bazan ideon de Shamir , ni restas kun problemo, kiun ni ignoris ĝis nun. Nia polinoma funkcio uzas nesekuran entjeran aritmetikon. Notu, ke por ĉiu plia punkto, kiun atakanto akiras sur la grafikaĵo de nia funkcio, estas malpli da eblecoj por aliaj punktoj. Vi povas vidi ĉi tion per viaj propraj okuloj kiam vi grafikas kreskantan nombron da punktoj por polinoma funkcio uzante entjeran aritmetikon. Ĉi tio estas kontraŭprodukta al nia deklarita sekureccelo, ĉar la atakanto devus scii absolute nenion ĝis ili havas almenaŭ fragmentoj.
Por pruvi kiom malforta estas la entjera aritmetika cirkvito, konsideru scenaron en kiu atakanto akiris du poentojn kaj konas publikan informon tion . El ĉi tiu informo li povas dedukti , egala al du, kaj enigu la konatajn valorojn en la formulon и .
La atakanto tiam povas trovi , kalkulante :
Ĉar ni difinis kiel hazarde elektitaj pozitivaj entjeroj, estas limigita nombro da eblaj . Uzante ĉi tiujn informojn, atakanto povas dedukti , ĉar io pli granda ol 5 faros negativa. Ĉi tio rezultas vera ĉar ni determinis
La atakanto tiam povas kalkuli la eblajn valorojn anstataŭigante в :
Kun limigitaj ebloj por evidentiĝas kiom facile estas elekti kaj kontroli la valorojn . Estas nur kvin elektoj ĉi tie.
Solvante la problemon kun nesekura entjera aritmetiko
Por forigi ĉi tiun vundeblecon, Shamir sugestas uzi modulan aritmetikon, anstataŭigante sur kie и — la aro de ĉiuj primoj.
Ni rapide memoru kiel funkcias modula aritmetiko. Horloĝo kun manetoj estas konata koncepto. Ŝi uzas horloĝon kiu estas . Tuj kiam la hormontrilo pasas dek du, ĝi revenas al unu. Interesa eco de ĉi tiu sistemo estas, ke simple rigardante la horloĝon, ni ne povas dedukti kiom da revolucioj faris la hormontrilo. Tamen, se ni scias, ke la horo pasis 12 kvar fojojn, ni povas tute determini la nombron da horoj kiuj pasis uzante simplan formulon. kie estas nia dividanto (ĉi tie ), estas la koeficiento (kiom da fojoj la dividanto iras en la originan nombron sen resto, ĉi tie ), kaj estas la resto, kiu kutime resendas modulan operatorvokon (ĉi tie ). Koni ĉiujn ĉi tiujn valorojn permesas al ni solvi la ekvacion por , sed se ni maltrafas la koeficienton, ni neniam povos restarigi la originan valoron.
Ni povas pruvi kiel ĉi tio plibonigas la sekurecon de nia skemo aplikante la skemon al nia antaŭa ekzemplo kaj uzante . Nia nova polinoma funkcio , kaj la novaj punktoj . Nun la ŝlosilaj gardantoj povas denove uzi polinoman interpoladon por rekonstrui nian funkcion, nur ĉi-foje la operacioj de aldono kaj multipliko devas esti akompanataj de modula redukto. (ekz ).
Uzante ĉi tiun novan ekzemplon, ni supozu, ke la atakanto lernis du el ĉi tiuj novaj punktoj, , kaj publika informo . Ĉi-foje, la atakanto, surbaze de ĉiuj informoj, kiujn li havas, eligas la sekvajn funkciojn, kie estas la aro de ĉiuj pozitivaj entjeroj, kaj reprezentas la modulan koeficienton .
Nun nia atakanto trovas denove , kalkulante :
Poste li provas denove anstataŭigante в :
Ĉi-foje li havas gravan problemon. Formulo mankas valoroj , и . Ĉar ekzistas senfina nombro da kombinaĵoj de ĉi tiuj variabloj, li ne povas akiri ajnan kroman informon.
Sekurecaj Konsideroj
La sekreta kundivida skemo de Shamir sugestas sekureco el la vidpunkto de informa teorio. Ĉi tio signifas, ke la matematiko estas imuna eĉ kontraŭ atakanto kun senlima komputika potenco. Tamen, la cirkvito daŭre enhavas plurajn konatajn problemojn.
Ekzemple, la skemo de Shamir ne kreas kontrolendaj fragmentoj, tio estas, homoj povas libere prezenti falsajn fragmentojn kaj malhelpi la reakiron de la ĝusta sekreto. Malfavora fragmentgardanto kun sufiĉaj informoj eĉ povus produkti alian fragmenton per ŝanĝado laŭ via bontrovo. Ĉi tiu problemo estas solvita uzante kontroleblaj sekretaj kundividaj skemoj, kiel ekzemple la skemo de Feldman.
Alia problemo estas ke la longo de iu fragmento estas egala al la longo de la responda sekreto, do la longo de la sekreto estas facile determini. Ĉi tiu problemo povas esti solvita per bagatela remburaĵo sekreta kun arbitraj nombroj ĝis fiksa longo.
Fine, estas grave noti, ke niaj zorgoj pri sekureco povas etendiĝi preter la dezajno mem. Por real-mondaj kriptografiaj aplikoj, ekzistas ofte la minaco de flankkanalaj atakoj kie atakanto provas ĉerpi utilajn informojn de aplikaĵa ekzekuttempo, kaŝmemoro, kraŝoj, ktp. Se ĉi tio estas maltrankvilo, zorge konsideru dum evoluo al uzado de protektaj rimedoj kiel funkcioj kaj konstantaj serĉoj, malebligante ke memoro estu konservita al disko, kaj kelkaj aliaj konsideroj, kiuj estas ekster la amplekso de ĉi tiu artikolo.
Demo
En Estas interaga pruvo de la sekreta kundivida skemo de Shamir. Manifestacio bazita sur la biblioteko , kiu mem estas JavaScript-pordo de la populara programo . Notu ke kalkulante grandajn valorojn , и eble daŭros iom da tempo.
fonto: www.habr.com