Ystyriwch senario lle mae angen i chi ddiogelu claddgell banc. Fe'i hystyrir yn gwbl anhreiddiadwy heb allwedd, a roddir i chi ar y diwrnod cyntaf o waith. Eich nod yw storio'r allwedd yn ddiogel.
Tybiwch eich bod yn penderfynu cadw'r allwedd gyda chi bob amser, gan ddarparu mynediad i'r gladdgell yn Γ΄l yr angen. Ond byddwch yn sylweddoli'n gyflym nad yw datrysiad o'r fath yn graddio'n dda yn ymarferol, oherwydd bob tro mae angen i chi fod yn bresennol yn gorfforol i agor y gladdgell. Beth am y gwyliau a addawyd i chi? Yn ogystal, mae'r cwestiwn hyd yn oed yn fwy brawychus: beth os byddwch chi'n colli'r unig allwedd?
Gyda'r syniad o wyliau, rydych chi'n penderfynu gwneud copi o'r allwedd a'i ymddiried i weithiwr arall. Fodd bynnag, rydych yn deall nad yw hyn yn ddelfrydol ychwaith. Trwy ddyblu nifer yr allweddi, rydych hefyd wedi dyblu'r siawns o ddwyn allweddi.
Yn anobeithiol, rydych chi'n dinistrio'r dyblyg ac yn penderfynu rhannu'r allwedd wreiddiol yn ei hanner. Nawr, rydych chi'n meddwl bod yn rhaid i ddau berson dibynadwy gyda darnau allweddol fod yn bresennol yn gorfforol i gasglu'r allwedd ac agor y gladdgell. Mae hyn yn golygu bod angen i'r lleidr ddwyn dau ddarn, sydd ddwywaith mor anodd Γ’ dwyn un allwedd. Fodd bynnag, sylweddolwch yn fuan nad ywβr cynllun hwn yn llawer gwell nag un allwedd yn unig, oherwydd os bydd rhywun yn colli hanner yr allwedd, ni ellir adennill yr allwedd lawn.
Gellir datrys y broblem gyda chyfres o allweddi a chloeon ychwanegol, ond bydd angen y dull hwn yn gyflym ΠΌΠ½ΠΎΠ³ΠΎ allweddi a chloeon. Rydych chi'n penderfynu mai'r cynllun delfrydol yw rhannu'r allwedd fel nad yw diogelwch yn dibynnu'n llwyr ar un person. Rydych hefyd yn dod i'r casgliad bod yn rhaid cael rhywfaint o drothwy ar gyfer nifer y darnau fel, os bydd un darn yn cael ei golli (neu os yw'r person yn mynd ar wyliau), mae'r allwedd gyfan yn parhau i fod yn weithredol.
Sut i rannu cyfrinach
Meddyliodd Adi Shamir am y math hwn o gynllun rheoli allweddol ym 1979 pan gyhoeddodd ei waith . Mae'r erthygl yn egluro'n fyr yr hyn a elwir 
cynllun trothwy ar gyfer rhannu gwerth cyfrinachol yn effeithiol (er enghraifft, allwedd cryptograffig). rhannau. Yna, pryd a dim ond pan o leiaf o mae rhannau wedi'u cydosod, gallwch chi adfer y gyfrinach yn hawdd .
O safbwynt diogelwch, un o nodweddion pwysig y cynllun hwn yw y dylai ymosodwr ddysgu dim byd o gwbl os nad oes ganddo o leiaf rhannau. Hyd yn oed y presenoldeb ni ddylai rhannau roi unrhyw wybodaeth. Rydyn ni'n galw'r eiddo hwn diogelwch semantig.
Rhyngosod Polynomaidd
Cynllun Trothwy Shamir adeiladu o amgylch y cysyniad rhyngosodiad polynomaidd. Os nad ydych chi'n gyfarwydd Γ’'r cysyniad hwn, mae'n eithaf syml mewn gwirionedd. Yn gyffredinol, os ydych chi erioed wedi tynnu pwyntiau ar siart ac yna eu cysylltu Γ’ llinellau neu gromliniau, rydych chi eisoes wedi'i ddefnyddio!
Trwy ddau bwynt, gallwch chi dynnu nifer anghyfyngedig o polynomialau gradd 2. I ddewis yr unig un ohonyn nhw, mae angen trydydd pwynt arnoch chi. Darlun:
Ystyriwch polynomial gyda gradd un, . Os ydych chi eisiau plotio'r ffwythiant hwn ar graff, faint o bwyntiau sydd eu hangen arnoch chi? Wel, gwyddom fod hon yn swyddogaeth linellol sy'n ffurfio llinell ac felly mae angen o leiaf ddau bwynt arnom. Nesaf, ystyriwch swyddogaeth polynomaidd gyda gradd dau, . Mae hon yn ffwythiant cwadratig, felly mae angen o leiaf dri phwynt i blotio'r graff. Beth am polynomial gyda gradd tri? O leiaf pedwar dot. Ac yn y blaen ac yn y blaen.
Y peth cΕ΅l iawn am yr eiddo hwn yw, o ystyried graddau'r swyddogaeth polynomaidd ac o leiaf pwyntiau, gallwn ddeillio pwyntiau ychwanegol ar gyfer y swyddogaeth polynomaidd hon. Rydym yn galw allosod y pwyntiau ychwanegol hyn rhyngosodiad polynomaidd.
Gwneud cyfrinach
Efallai eich bod eisoes wedi darganfod mai dyma lle mae cynllun clyfar Shamir yn dod i rym. Tybiwch ein cyfrinach - A yw . Gallwn droi i'r pwynt ar y graff a dod o hyd i swyddogaeth polynomial gyda gradd , sy'n bodloni'r pwynt hwn. Dwyn i gof hynny fydd ein trothwy o ddarnau gofynnol, felly os byddwn yn gosod y trothwy i dri darn, mae'n rhaid i ni ddewis swyddogaeth polynomaidd gyda gradd o ddau.
Bydd gan ein polynomial y ffurf lle ΠΈ yn gyfanrifau positif a ddewiswyd ar hap. Rydyn ni'n adeiladu polynomial gyda gradd , lle mae'r cyfernod rhad ac am ddim - Dyma ein cyfrinach , a phob un o'r canlynol Termau yw cyfernod positif a ddewisir ar hap. Os dychwelwn at yr enghraifft wreiddiol a thybio hynny , yna byddwn yn cael y swyddogaeth .
Ar y pwynt hwn, gallwn gynhyrchu darnau trwy gysylltu cyfanrifau unigryw yn lle (oherwydd ein cyfrinach ni ydyw). Yn yr enghraifft hon, rydym am ddosbarthu pedwar darn gyda throthwy o dri, felly rydym yn cynhyrchu pwyntiau ar hap ac anfon un pwynt at bob un o'r pedwar person ymddiried, ceidwaid yr allwedd. Rydym hefyd yn dweud hynny wrth bobl , gan ei fod yn cael ei ystyried yn wybodaeth gyhoeddus ac yn angenrheidiol ar gyfer adferiad .
Adferiad Cyfrinachol
Rydym eisoes wedi trafod y cysyniad o ryngosodiad polynomaidd a sut mae'n sail i gynllun trothwy Shamir. . Pan fydd unrhyw dri o bob pedwar ymddiriedolwr am adfer , nid oes angen iddynt ond rhyngosod gyda'u pwyntiau unigryw. I wneud hyn, gallant ddiffinio eu pwyntiau a chyfrifo polynomial rhyngosodiad Lagrange gan ddefnyddio'r fformiwla ganlynol. Os yw rhaglennu'n gliriach i chi na mathemateg, yna gweithredwr yw pi yn ei hanfod for, sy'n lluosi pob canlyniad, a sigma yw forsy'n adio popeth.
Ar gallwn ei ddatrys fel hyn a dychwelyd ein swyddogaeth polynomaidd wreiddiol:
Gan ein bod yn gwybod hynny , adferiad yn cael ei wneud yn syml:
Defnyddio rhifyddeg cyfanrif anniogel
Er ein bod wedi cymhwyso'r syniad sylfaenol o Shamir yn llwyddiannus , rydym yn cael ein gadael Γ’ phroblem yr ydym wediβi hanwybyddu hyd yn hyn. Mae ein swyddogaeth polynomaidd yn defnyddio rhifyddeg cyfanrif anniogel. Sylwch, am bob pwynt ychwanegol y mae ymosodwr yn ei gael ar ein graff swyddogaeth, mae llai o bosibiliadau ar gyfer pwyntiau eraill. Gallwch weld hyn Γ’'ch llygaid eich hun pan fyddwch chi'n plotio nifer cynyddol o bwyntiau ar gyfer swyddogaeth polynomaidd gan ddefnyddio rhifyddeg cyfanrif. Mae hyn yn wrthgynhyrchiol i'n nod diogelwch a nodwyd oherwydd ni ddylai'r ymosodwr wybod dim byd nes bod ganddo o leiaf darnau.
I ddangos pa mor wan yw'r cynllun rhifyddeg cyfanrif, ystyriwch senario lle cafodd yr ymosodwr ddau bwynt ac yn gwybod gwybodaeth gyhoeddus hynny . O'r wybodaeth hon, gall gasglu , yn hafal i ddau, ac yn cysylltu'r gwerthoedd hysbys Γ’'r fformiwla ΠΈ .
Yna gall yr ymosodwr ddod o hyd , cyfrif :
Ers i ni ddiffinio fel cyfanrifau positif a ddewiswyd ar hap, mae nifer cyfyngedig o bosibl . Gyda'r wybodaeth hon, gall ymosodwr ddiddwytho , oherwydd bydd unrhyw beth mwy na 5 yn gwneud negyddol. Mae hyn yn troi allan i fod yn wir, gan ein bod wedi penderfynu
Yna gall yr ymosodwr gyfrifo'r gwerthoedd posibl ailosod Π² :
Gydag opsiynau cyfyngedig ar gyfer daw'n amlwg pa mor hawdd yw hi i godi a gwirio gwerthoedd . Dim ond pum opsiwn sydd yma.
Datrys y broblem gyda rhifyddeg cyfanrif anniogel
Er mwyn trwsio'r bregusrwydd hwn, mae Shamir yn awgrymu defnyddio rhifyddeg modiwlaidd trwy amnewid ar lle ΠΈ yw set yr holl rifau cysefin.
Gadewch i ni gofio'n gyflym sut mae rhifyddeg fodiwlaidd yn gweithio. Mae clociau llaw yn gysyniad cyfarwydd. Mae hi'n defnyddio oriawr hynny yw . Cyn gynted ag y bydd y llaw awr yn mynd heibio deuddeg, mae'n dychwelyd i un. Un o nodweddion diddorol y system hon yw na allwn ddidynnu faint o chwyldroadau y mae'r awr law wedi'u gwneud wrth edrych ar y cloc. Fodd bynnag, os ydym yn gwybod bod y llaw awr wedi mynd heibio 12 bedair gwaith, gallwn bennu'n llawn nifer yr oriau sydd wedi mynd heibio gyda fformiwla syml. lle yw ein rhanydd (yma ), - dyma'r cyfernod (sawl gwaith mae'r rhannydd heb weddill yn mynd i mewn i'r rhif gwreiddiol, yma ), a ywβr gweddill, sydd fel arfer yn dychwelyd galwad i weithredwr y modwlo (yma ). Mae gwybod yr holl werthoedd hyn yn ein galluogi i ddatrys yr hafaliad ar gyfer , ond os byddwn yn hepgor y cyfernod, ni fyddwn byth yn gallu adfer y gwerth gwreiddiol.
Gallwn ddangos sut mae hyn yn gwella diogelwch ein cylched trwy gymhwyso'r gylched i'n hesiampl flaenorol a defnyddio . Ein swyddogaeth polynomaidd newydd , a'r pwyntiau newydd . Nawr gall y ceidwaid allweddi unwaith eto ddefnyddio rhyngosodiad polynomaidd i ail-greu ein swyddogaeth, dim ond y tro hwn y mae'n rhaid i'r gweithrediadau adio a lluosi gael eu dilyn gan ostyngiad modwlo. (ee ).
Gan ddefnyddio'r enghraifft newydd hon, mae'n debyg bod yr ymosodwr wedi dysgu dau o'r pwyntiau newydd hyn, , a gwybodaeth gyhoeddus . Y tro hwn, mae'r ymosodwr, yn seiliedig ar yr holl wybodaeth sydd ganddo, yn arddangos y swyddogaethau canlynol, lle yw set yr holl gyfanrifau cadarnhaol, a yn cynrychioli'r cyfernod modwlws .
Nawr mae ein tresmaswr yn canfod eto , cyfrifo :
Yna mae'n ceisio tynnu'n Γ΄l eto ailosod Π² :
Y tro hwn mae ganddo broblem ddifrifol. Fformiwla gwerthoedd ar goll , ΠΈ . Gan fod nifer anfeidrol o gyfuniadau o'r newidynnau hyn, ni all gael unrhyw wybodaeth ychwanegol.
Ystyriaethau Diogelwch
Mae cynllun rhannu cyfrinachol Shamir yn awgrymu diogelwch gwybodaeth. Mae hyn yn golygu bod y mathemateg yn gryf hyd yn oed yn erbyn ymosodwr sydd Γ’ phΕ΅er cyfrifiadurol diderfyn. Fodd bynnag, mae'r sgema yn dal i gynnwys nifer o faterion hysbys.
Er enghraifft, nid yw cynllun Shamir yn creu darnau i'w gwirio, hynny yw, mae pobl yn rhydd i gyflwyno darnau ffug ac ymyrryd ag adferiad y gyfrinach gywir. Gall ceidwad darn gelyniaethus gyda digon o wybodaeth hyd yn oed gynhyrchu darn arall trwy newid yn Γ΄l eich disgresiwn. Mae'r broblem hon yn cael ei datrys gyda cynlluniau rhannu cyfrinachol gwiriadwy, megis cynllun Feldman.
Problem arall yw bod hyd unrhyw ddarn yn hafal i hyd y gyfrinach gyfatebol, felly mae hyd y gyfrinach yn hawdd ei bennu. Mae'r broblem hon yn cael ei datrys gan y dibwys padin cyfrinach gan rifau mympwyol hyd at hyd sefydlog.
Yn olaf, mae'n bwysig nodi y gallai ein pryderon diogelwch fynd y tu hwnt i'r cynllun ei hun. Ar gyfer cymwysiadau cryptograffig go iawn, yn aml mae bygythiad o ymosodiadau sianel ochr, pan fydd ymosodwr yn ceisio tynnu gwybodaeth ddefnyddiol o amser gweithredu'r cais, caching, damweiniau, ac ati. Os yw hyn yn bryder, dylech ystyried yn ofalus y defnydd o fesurau diogelu yn ystod datblygiad, megis swyddogaethau a chwiliadau amser cyson, atal arbed cof ar ddisg, ac ystyried nifer o bethau eraill sydd y tu hwnt i gwmpas yr erthygl hon.
ΠΠ΅ΠΌΠΎ
Ar mae arddangosiad rhyngweithiol o gynllun rhannu cyfrinachol Shamir. Gwnaed yr arddangosiad ar sail y llyfrgell , sydd ei hun yn borthladd JavaScript o raglen boblogaidd . Sylwch fod cyfrifo gwerthoedd mawr , ΠΈ gall gymryd peth amser.
Ffynhonnell: hab.com