Oorweeg 'n scenario waar jy 'n bankkluis moet beveilig. Dit word as absoluut onneembaar beskou sonder 'n sleutel, wat op die eerste dag van werk aan jou gegee word. Jou doel is om die sleutel veilig te stoor.

Gestel jy besluit om die sleutel te alle tye by jou te hou, en verskaf toegang tot die kluis soos nodig. Maar jy sal vinnig besef dat so 'n oplossing in die praktyk nie goed skaal nie, want elke keer moet jy fisies teenwoordig wees om die kluis oop te maak. Wat van die vakansie wat jy belowe is? Daarbenewens is die vraag selfs meer angswekkend: wat as jy die enigste sleutel verloor het?

Met die idee van 'n vakansie besluit jy om 'n afskrif van die sleutel te maak en dit aan 'n ander werknemer toe te vertrou. U verstaan ​​egter dat dit ook nie ideaal is nie. Deur die aantal sleutels te verdubbel, het jy ook die kanse op sleuteldiefstal verdubbel.

Desperaat vernietig jy die duplikaat en besluit om die oorspronklike sleutel in die helfte te verdeel. Nou dink jy twee vertroude mense met sleutelfragmente moet fisies teenwoordig wees om die sleutel af te haal en die kluis oop te maak. Dit beteken dat die dief twee fragmente moet steel, wat twee keer so moeilik is as om een ​​sleutel te steel. Jy besef egter gou dat hierdie skema nie veel beter is as net een sleutel nie, want as iemand die helfte van die sleutel verloor, kan die volle sleutel nie herwin word nie.

Die probleem kan opgelos word met 'n reeks bykomende sleutels en slotte, maar hierdie benadering sal vinnig vereis много sleutels en slotte. Jy besluit dat die ideale skema is om die sleutel te deel sodat sekuriteit nie heeltemal op een persoon staatmaak nie. Jy kom ook tot die gevolgtrekking dat daar een of ander drempel moet wees vir die aantal fragmente sodat as een fragment verlore gaan (of as die persoon met vakansie gaan), die hele sleutel funksioneel bly.

Hoe om 'n geheim te deel

Adi Shamir het in 1979 aan hierdie tipe sleutelbestuurskema gedink toe hy sy werk gepubliseer het "Hoe om 'n geheim te deel". Die artikel verduidelik kortliks die sg drempelskema vir die effektiewe verdeling van 'n geheime waarde (byvoorbeeld 'n kriptografiese sleutel) in dele. Dan, wanneer en net wanneer ten minste van dele saamgestel is, kan jy die geheim maklik herstel .

Uit 'n sekuriteitsoogpunt is 'n belangrike eienskap van hierdie skema dat 'n aanvaller absoluut niks moet leer as hy nie ten minste het nie dele. Selfs die teenwoordigheid dele moet geen inligting gee nie. Ons noem hierdie eiendom semantiese sekuriteit.

Polinoom interpolasie

Drempel Shamir-skema rondom die konsep gebou polinoom interpolasie. As jy nie met hierdie konsep vertroud is nie, is dit eintlik redelik eenvoudig. Oor die algemeen, as jy al ooit punte op 'n grafiek geteken het en dit dan met lyne of kurwes verbind het, het jy dit reeds gebruik!

Deur twee punte kan jy 'n onbeperkte aantal polinome van graad 2 teken. Om die enigste een uit hulle te kies, benodig jy 'n derde punt. Illustrasie: Wikipedia

Beskou 'n polinoom met graad een, . As jy hierdie funksie op 'n grafiek wil teken, hoeveel punte het jy nodig? Wel, ons weet dat dit 'n lineêre funksie is wat 'n lyn vorm en daarom benodig ons ten minste twee punte. Beskou dan 'n polinoomfunksie met graad twee, . Dit is 'n kwadratiese funksie, so ten minste drie punte is nodig om die grafiek te teken. Wat van 'n polinoom met graad drie? Ten minste vier kolletjies. Ensovoorts ensovoorts.

Die baie oulike ding van hierdie eienskap is dat, gegewe die graad van die polinoomfunksie en ten minste punte, kan ons addisionele punte vir hierdie polinoomfunksie aflei. Ons noem die ekstrapolasie van hierdie bykomende punte polinoom interpolasie.

Om 'n geheim te maak

Jy het dalk al agtergekom dat dit is waar Shamir se slim skema ter sprake kom. Gestel ons geheim - Is . Ons kan draai tot by die punt op die grafiek en kom vorendag met 'n polinoomfunksie met 'n graad , wat aan hierdie punt voldoen. Onthou dit sal ons drumpel van vereiste fragmente wees, dus as ons die drempel op drie fragmente stel, moet ons 'n polinoomfunksie met 'n graad van twee kies.

Ons polinoom sal die vorm hê Waar и is ewekansig gekose positiewe heelgetalle. Ons bou net 'n polinoom met 'n graad , waar die vrye koëffisiënt  - Dit is ons geheim , en elk van die daaropvolgende terme is 'n ewekansig gekose positiewe koëffisiënt. As ons terugkeer na die oorspronklike voorbeeld en aanvaar dat , dan kry ons die funksie .

Op hierdie stadium kan ons fragmente genereer deur te koppel unieke heelgetalle in Waar (want dit is ons geheim). In hierdie voorbeeld wil ons vier fragmente met 'n drempel van drie versprei, so ons genereer ewekansig punte en stuur een punt aan elkeen van die vier vertroude mense, die bewaarders van die sleutel. Ons vertel dit ook vir mense , aangesien dit as openbare inligting beskou word en nodig is vir herstel .

Geheime herstel

Ons het reeds die konsep van polinoominterpolasie bespreek en hoe dit Shamir se drempelskema onderlê. . Wanneer enige drie uit vier trustees wil herstel , hulle hoef net te interpoleer met hul unieke punte. Om dit te doen, kan hulle hul punte definieer en bereken die Lagrange interpolasie polinoom deur die volgende formule te gebruik. As programmering vir jou duideliker is as wiskunde, dan is pi in wese 'n operateur for, wat alle resultate vermenigvuldig, en sigma is forwat alles bymekaar tel.

op ons kan dit so oplos en ons oorspronklike polinoomfunksie terugstuur:

Want ons weet dit , herstel word eenvoudig gedoen:

Gebruik onveilige heelgetalrekenkunde

Alhoewel ons die basiese idee van Shamir suksesvol toegepas het , sit ons met 'n probleem wat ons tot nou toe geïgnoreer het. Ons polinoomfunksie gebruik onveilige heelgetalrekenkunde. Let daarop dat vir elke bykomende punt wat 'n aanvaller op ons funksiegrafiek kry, daar minder moontlikhede vir ander punte is. Jy kan dit met jou eie oë sien wanneer jy 'n toenemende aantal punte vir 'n polinoomfunksie teken deur heelgetalrekenkunde te gebruik. Dit is teenproduktief vir ons gestelde sekuriteitsdoelwit, want 'n aanvaller behoort absoluut niks te weet totdat hulle ten minste het nie fragmente.

Om te demonstreer hoe swak die heelgetalrekenkundige skema is, oorweeg 'n scenario waarin die aanvaller twee punte ontvang het en weet openbare inligting wat . Uit hierdie inligting kan hy aflei , gelyk aan twee, en verbind die bekende waardes met die formule и .

Die aanvaller kan dan vind , tel :

Aangesien ons gedefinieer het as ewekansig gekose positiewe heelgetalle, is daar 'n beperkte aantal moontlike . Met hierdie inligting kan 'n aanvaller aflei , want enigiets groter as 5 sal maak negatief. Dit blyk waar te wees, aangesien ons vasgestel het

Die aanvaller kan dan die moontlike waardes bereken vervang в :

Met beperkte opsies vir dit word duidelik hoe maklik dit is om waardes op te tel en na te gaan . Hier is net vyf opsies.

Los die probleem op met onveilige heelgetalrekenkunde

Om hierdie kwesbaarheid reg te stel, stel Shamir voor om modulêre rekenkunde te gebruik deur te vervang op Waar и is die versameling van alle priemgetalle.

Kom ons onthou vinnig hoe modulêre rekenkunde werk. Handhorlosies is 'n bekende konsep. Sy gebruik 'n horlosie dws . Sodra die uurwyser twaalf verbygaan, keer dit terug na een. 'n Interessante eienskap van hierdie stelsel is dat net deur na die horlosie te kyk, ons nie kan aflei hoeveel omwentelinge die uurwyser gemaak het nie. As ons egter weet dat die uurwyser 12 vier keer verby is, kan ons die aantal ure wat verloop het volledig bepaal met 'n eenvoudige formule Waar  is ons deler (hier ),  - dit is die koëffisiënt (hoeveel keer gaan die deler sonder 'n res in die oorspronklike getal, hier ), en  is die res, wat gewoonlik 'n oproep na die modulo-operateur terugstuur (hier ). Om al hierdie waardes te ken, stel ons in staat om die vergelyking op te los , maar as ons die koëffisiënt oorslaan, sal ons nooit die oorspronklike waarde kan herstel nie.

Ons kan demonstreer hoe dit die sekuriteit van ons stroombaan verbeter deur die stroombaan op ons vorige voorbeeld toe te pas en te gebruik . Ons nuwe polinoomfunksie , en die nuwe punte . Nou kan die sleutelhouers weer polinoominterpolasie gebruik om ons funksie te rekonstrueer, maar hierdie keer moet die optel- en vermenigvuldigingsbewerkings gevolg word deur modulo-reduksie. (bv ).

Deur hierdie nuwe voorbeeld te gebruik, veronderstel die aanvaller het twee van hierdie nuwe punte geleer, , en openbare inligting . Hierdie keer vertoon die aanvaller, gebaseer op al die inligting wat hy het, die volgende funksies, waar  is die versameling van alle positiewe heelgetalle, en verteenwoordig die moduluskoëffisiënt .

Nou vind ons indringer weer , bereken :

Dan probeer hy weer om te onttrek vervang в :

Hierdie keer het hy 'n ernstige probleem. Formule ontbrekende waardes , и . Aangesien daar 'n oneindige aantal kombinasies van hierdie veranderlikes is, kan hy geen bykomende inligting bekom nie.

Sekuriteitsoorwegings

Shamir se geheime deelskema dui daarop inligtings sekuriteit. Dit beteken dat die wiskunde sterk is, selfs teen 'n aanvaller met onbeperkte rekenaarkrag. Die skema bevat egter steeds verskeie bekende probleme.

Byvoorbeeld, die Shamir-skema skep nie fragmente wat nagegaan moet word, dit wil sê, mense is vry om vals fragmente aan te bied en in te meng met die herstel van die korrekte geheim. 'n Vyandige fragmenthouer met genoeg inligting kan selfs nog 'n fragment produseer deur te verander na jou goeddunke. Hierdie probleem word opgelos met verifieerbare geheime deelskemas, soos die Feldman-skema.

Nog 'n probleem is dat die lengte van enige fragment gelyk is aan die lengte van die ooreenstemmende geheim, dus is die lengte van die geheim maklik om te bepaal. Hierdie probleem word opgelos deur die triviale vulling geheim deur arbitrêre getalle tot 'n vaste lengte.

Ten slotte is dit belangrik om daarop te let dat ons sekuriteitskwessies verder kan strek as die skema self. Vir regte kriptografiese toepassings is daar dikwels 'n bedreiging van sykanaalaanvalle, wanneer 'n aanvaller probeer om nuttige inligting uit die toepassing se uitvoeringstyd, kas, ineenstortings, ens. As dit 'n bekommernis is, moet u die gebruik van voorsorgmaatreëls tydens ontwikkeling, soos funksies en konstante-tydopsoeke, sorgvuldig oorweeg, verhoed dat u geheue op skyf stoor, en 'n aantal ander dinge oorweeg wat buite die bestek van hierdie artikel val.

Демо

Op Hierdie bladsy daar is 'n interaktiewe demonstrasie van Shamir se geheime deelskema. Die demonstrasie is gemaak op grond van die biblioteek ssss-js, wat self 'n JavaScript-poort van 'n gewilde program is SSSS. Let daarop dat die berekening van groot waardes , и kan 'n tydjie neem.

Bron: will.com