Overvej et scenario, hvor du skal sikre dig en bankboks. Det anses for absolut uindtageligt uden nøgle, som gives til dig på den første arbejdsdag. Dit mål er at opbevare nøglen sikkert.
Antag, at du beslutter dig for altid at have nøglen med dig og give adgang til boksen efter behov. Men du vil hurtigt indse, at sådan en løsning ikke skalerer godt i praksis, for hver gang skal du være fysisk til stede for at åbne boksen. Hvad med den ferie, du blev lovet? Derudover er spørgsmålet endnu mere skræmmende: hvad nu hvis du mistede den eneste nøgle?
Med ideen om en ferie beslutter du dig for at lave en kopi af nøglen og overlade den til en anden medarbejder. Du forstår dog, at dette heller ikke er ideelt. Ved at fordoble antallet af nøgler har du også fordoblet chancerne for nøgletyveri.
Desperat ødelægger du duplikatet og beslutter dig for at dele den originale nøgle i to. Nu tror du, at to betroede personer med nøglefragmenter skal være fysisk til stede for at hente nøglen og åbne boksen. Det betyder, at tyven skal stjæle to fragmenter, hvilket er dobbelt så svært som at stjæle en nøgle. Du indser dog hurtigt, at denne ordning ikke er meget bedre end blot én nøgle, for hvis nogen mister halvdelen af nøglen, kan den fulde nøgle ikke gendannes.
Problemet kan løses med en række ekstra nøgler og låse, men denne tilgang vil hurtigt kræve много nøgler og låse. Du beslutter dig for, at den ideelle ordning er at dele nøglen, så sikkerheden ikke udelukkende afhænger af én person. Du konkluderer også, at der skal være en tærskel for antallet af fragmenter, så hvis et fragment går tabt (eller hvis personen tager på ferie), forbliver hele nøglen funktionsdygtig.
Sådan deler du en hemmelighed
Denne type nøglestyringsordning blev tænkt på af Adi Shamir i 1979, da han udgav sit arbejde . Artiklen forklarer kort det såkaldte 
tærskelordning til effektivt at opdele en hemmelig værdi (f.eks. en kryptografisk nøgle) i dele. Så, hvornår og kun når i det mindste af dele er samlet, kan du nemt genoprette hemmeligheden .
Fra et sikkerhedssynspunkt er en vigtig egenskab ved denne ordning, at en angriber absolut intet skal lære, hvis han ikke har mindst dele. Selv tilstedeværelsen dele bør ikke give nogen information. Vi kalder denne ejendom semantisk sikkerhed.
Polynomisk interpolation
Tærskel Shamir-ordning bygget op omkring konceptet polynomisk interpolation. Hvis du ikke er bekendt med dette koncept, er det faktisk ret simpelt. Generelt, hvis du nogensinde har tegnet punkter på et diagram og derefter forbundet dem med linjer eller kurver, har du allerede brugt det!
Gennem to punkter kan du tegne et ubegrænset antal polynomier af grad 2. For at vælge det eneste fra dem, skal du bruge et tredje punkt. Illustration:
Overvej et polynomium med grad et, . Hvis du vil plotte denne funktion på en graf, hvor mange point skal du så bruge? Nå, vi ved, at dette er en lineær funktion, der danner en linje, og derfor har vi brug for mindst to punkter. Overvej derefter en polynomisk funktion med grad to, . Dette er en kvadratisk funktion, så der kræves mindst tre punkter for at plotte grafen. Hvad med et polynomium med grad tre? Mindst fire prikker. Og så videre og så videre.
Det virkelig fede ved denne egenskab er, at givet graden af polynomiets funktion og mindst point, kan vi udlede yderligere point for denne polynomiefunktion. Vi kalder ekstrapolering af disse yderligere punkter polynomisk interpolation.
At gøre en hemmelighed
Du har måske allerede fundet ud af, at det er her, Shamirs smarte plan kommer ind i billedet. Antag vores hemmelighed - Er . Vi kan vende til punktet på grafen og kom op med en polynomiel funktion med en grad , hvilket opfylder dette punkt. Husk det vil være vores tærskel for nødvendige fragmenter, så hvis vi sætter tærsklen til tre fragmenter, skal vi vælge en polynomiefunktion med en grad på to.
Vores polynomium vil have formen Hvor и er tilfældigt udvalgte positive heltal. Vi bygger bare et polynomium med en grad , hvor den frie koefficient - Det er vores hemmelighed , og hver af de efterfølgende termer er en tilfældigt valgt positiv koefficient. Hvis vi vender tilbage til det oprindelige eksempel og antager det , så får vi funktionen .
På dette tidspunkt kan vi generere fragmenter ved at forbinde unikke heltal i Hvor (fordi det er vores hemmelighed). I dette eksempel ønsker vi at fordele fire fragmenter med en tærskel på tre, så vi genererer tilfældigt point og send et point til hver af de fire betroede personer, nøglebevogterne. Det fortæller vi også folk , da det anses for offentlig oplysning og er nødvendigt for inddrivelse .
Hemmelig genopretning
Vi har allerede diskuteret begrebet polynomisk interpolation, og hvordan det ligger til grund for Shamirs tærskelskema. . Når en hvilken som helst tre ud af fire administratorer ønsker at genoprette , skal de kun interpolere med deres unikke pointer. For at gøre dette kan de definere deres point og beregn Lagrange-interpolationspolynomiet ved hjælp af følgende formel. Hvis programmering er klarere for dig end matematik, så er pi i det væsentlige en operatør for, som multiplicerer alle resultater, og sigma er forder lægger alt sammen.
på vi kan løse det sådan her og returnere vores oprindelige polynomiefunktion:
Siden vi ved det , genopretning gøres ganske enkelt:
Bruger usikker heltalsaritmetik
Selvom vi med succes har anvendt den grundlæggende idé om Shamir , står vi tilbage med et problem, som vi har ignoreret indtil nu. Vores polynomiefunktion bruger usikker heltalsaritmetik. Bemærk, at for hvert ekstra point en angriber får på vores funktionsgraf, er der færre muligheder for andre point. Du kan se dette med dine egne øjne, når du plotter et stigende antal punkter for en polynomiefunktion ved hjælp af heltalsaritmetik. Dette er kontraproduktivt i forhold til vores erklærede sikkerhedsmål, fordi en angriber bør vide absolut intet, før de i det mindste har fragmenter.
For at demonstrere, hvor svag det aritmetiske heltalsskema er, skal du overveje et scenarie, hvor angriberen fik to point og kender offentlig information, der . Ud fra disse oplysninger kan han udlede , lig med to, og forbind de kendte værdier til formlen и .
Angriberen kan derefter finde , tæller :
Siden vi har defineret som tilfældigt udvalgte positive heltal er der et begrænset antal mulige . Med disse oplysninger kan en angriber udlede , fordi alt større end 5 vil gøre negativ. Dette viser sig at være sandt, da vi har bestemt
Angriberen kan derefter beregne de mulige værdier udskiftning в :
Med begrænsede muligheder for det bliver tydeligt, hvor nemt det er at opfange og kontrollere værdier . Der er kun fem muligheder her.
Løsning af problemet med usikker heltal aritmetik
For at rette op på denne sårbarhed foreslår Shamir at bruge modulær aritmetik ved at erstatte på Hvor и er mængden af alle primtal.
Lad os hurtigt huske, hvordan modulær aritmetik fungerer. Håndure er et kendt begreb. Hun bruger altså et ur . Så snart timeviseren passerer tolv, vender den tilbage til en. En interessant egenskab ved dette system er, at blot ved at se på uret, kan vi ikke udlede, hvor mange omdrejninger timeviseren har lavet. Men hvis vi ved, at timeviseren har passeret 12 fire gange, kan vi fuldt ud bestemme antallet af timer, der er forløbet med en simpel formel Hvor er vores divisor (her ), - dette er koefficienten (hvor mange gange divisoren uden en rest går ind i det oprindelige tal, her ), og er resten, som normalt returnerer et opkald til modulo-operatøren (her ). At kende alle disse værdier giver os mulighed for at løse ligningen for , men hvis vi springer koefficienten over, vil vi aldrig være i stand til at genoprette den oprindelige værdi.
Vi kan demonstrere, hvordan dette forbedrer sikkerheden i vores kredsløb ved at anvende kredsløbet til vores tidligere eksempel og bruge . Vores nye polynomiefunktion , og de nye punkter . Nu kan nøgleholderne igen bruge polynomiel interpolation til at rekonstruere vores funktion, kun denne gang skal additions- og multiplikationsoperationerne efterfølges af moduloreduktion. (f.eks ).
Brug dette nye eksempel, antag, at angriberen har lært to af disse nye punkter, og offentlig information . Denne gang viser angriberen, baseret på al den information han har, følgende funktioner, hvor er mængden af alle positive heltal, og repræsenterer modulkoefficienten .
Nu finder vores ubudne gæst igen , beregner :
Så forsøger han igen at trække sig udskiftning в :
Denne gang har han et alvorligt problem. Formlen mangler værdier , и . Da der er et uendeligt antal kombinationer af disse variable, kan han ikke få yderligere information.
Sikkerhedshensyn
Shamirs hemmelige delingsordning antyder informationssikkerhed. Det betyder, at matematikken er stærk selv mod en angriber med ubegrænset computerkraft. Skemaet indeholder dog stadig flere kendte problemer.
For eksempel skaber Shamir-ordningen ikke fragmenter, der skal kontrolleres, det vil sige, at folk frit kan præsentere falske fragmenter og forstyrre gendannelsen af den korrekte hemmelighed. En fjendtlig fragmentholder med tilstrækkelig information kan endda producere et andet fragment ved at ændre efter eget skøn. Dette problem er løst med verificerbare hemmelige deleordninger, såsom Feldman-ordningen.
Et andet problem er, at længden af ethvert fragment er lig med længden af den tilsvarende hemmelighed, så længden af hemmeligheden er let at bestemme. Dette problem er løst af det trivielle polstring hemmelig ved vilkårlige tal op til en fast længde.
Endelig er det vigtigt at bemærke, at vores sikkerhedsproblemer kan gå ud over selve ordningen. For rigtige kryptografiske applikationer er der ofte en trussel om sidekanalangreb, når en angriber forsøger at udtrække nyttig information fra applikationens eksekveringstid, caching, nedbrud osv. Hvis dette er et problem, bør du nøje overveje brugen af sikkerhedsforanstaltninger under udviklingen, såsom funktioner og konstant-tidsopslag, forhindre lagring af hukommelse på disk og overveje en række andre ting, der ligger uden for denne artikels omfang.
Демо
On der er en interaktiv demonstration af Shamirs hemmelige deleplan. Demonstrationen blev lavet med udgangspunkt i biblioteket , som i sig selv er en JavaScript-port af et populært program . Bemærk, at beregne store værdier , и kan tage noget tid.
Kilde: www.habr.com