Lad os overveje et scenario, hvor det er nødvendigt at sikre sikkerheden i en bankboks. Det anses for absolut uigennemtrængeligt uden nøgle, som du får udleveret på din første arbejdsdag. Dit mål er at holde nøglen sikker.

Lad os sige, at du beslutter dig for at have nøglen med dig til enhver tid og give adgang til boksen efter behov. Men du vil hurtigt indse, at denne løsning ikke skalerer godt i praksis, fordi din fysiske tilstedeværelse er påkrævet, hver gang lageret åbnes. Hvad med den ferie, du blev lovet? Desuden er et endnu mere skræmmende spørgsmål: hvad nu hvis du mistede din eneste nøgle?

Med din ferie i tankerne 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 fordobler du også chancerne for, at en nøgle bliver stjålet.

I desperation ø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 samle nøglen og åbne boksen. Det betyder, at tyven bliver nødt til at 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 ville være at opdele nøglen, så sikkerheden ikke helt 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 "Sådan deler man en hemmelighed". Artiklen forklarer kort det såkaldte et tærskelskema 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, er det nemt at genoprette hemmeligheden .

Fra et sikkerhedssynspunkt er en vigtig egenskab ved denne ordning, at en angriber ikke bør lære absolut noget, medmindre han har mindst dele. Selv tilstedeværelsen dele bør ikke give nogen information. Vi kalder denne ejendom semantisk sikkerhed.

Polynomisk interpolation

Shamirs tærskelordning bygget op omkring konceptet polynomisk interpolation. Hvis du ikke er bekendt med dette koncept, er det faktisk ret simpelt. Faktisk, hvis du nogensinde har tegnet prikker på en graf og derefter forbundet dem med linjer eller kurver, har du allerede brugt det!

Et ubegrænset antal polynomier af grad 2 kan trækkes gennem to punkter. For at vælge den eneste ene kræves et tredje punkt. Illustration: Wikipedia

Lad os overveje et polynomium af grad 1, . Hvis du vil plotte denne funktion på en graf, hvor mange point skal du så bruge? Nå, vi ved, at det er en lineær funktion, der danner en linje, og derfor skal der mindst to punkter til. Dernæst betragter vi 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 af grad tre? Mindst fire point. 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 finde på en hemmelighed

Du har måske allerede indset, at Shamirs smarte plan kommer i spil her. Lad os antage, at vores hemmelighed - Er . Vi kan transformere til et punkt på grafen og kom op med en polynomiel funktion med grad , hvilket opfylder dette punkt. Lad os huske 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 grad to.

Vores polynomium vil have formen Hvor и — tilfældigt udvalgte positive heltal. Vi konstruerer bare et polynomium med en grad , hvor er den frie koefficient  - det er vores hemmelighed , og hver af de efterfølgende medlemmer har en tilfældigt udvalgt positiv koefficient. Hvis vi går tilbage til det oprindelige eksempel og antager det , så får vi funktionen .

På dette stadium 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 vi sender et point til hver af de fire betroede personer, nøglebevogterne. Det informerer vi også folk om , da dette betragtes som offentlig information og er nødvendigt for inddrivelse .

Genskabelse af hemmeligheden

Vi har allerede diskuteret begrebet polynomisk interpolation, og hvordan det ligger til grund for Shamirs tærskelskema. . Når en hvilken som helst tre af de fire administratorer ønsker at genoprette , de skal bare interpolere med sine egne unikke pointer. For at gøre dette kan de definere deres point og beregn Lagrange-interpolationspolynomiet ved hjælp af følgende formel. Hvis du forstår programmering bedre end matematik, så er pi i bund og grund en operatør for, som multiplicerer alle resultaterne, og sigma er for, som sætter det hele sammen.

på vi kan løse dette på følgende måde og få vores oprindelige polynomiefunktion tilbage:

Siden vi ved det , bedring det udføres ganske enkelt:

Bruger usikker heltalsaritmetik

Selvom vi med succes har anvendt Shamirs grundlæggende idé , 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 angriberen 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 en graf med stigende antal punkter for en polynomiefunktion ved hjælp af heltalsaritmetik. Dette er kontraproduktivt i forhold til vores erklærede sikkerhedsmål, fordi angriberen absolut ikke burde vide noget, før de i det mindste har fragmenter.

For at demonstrere, hvor svag det aritmetiske heltalsskema er, skal du overveje et scenarie, hvor angriberen har to punkter og kender offentlig information, der . Ud fra disse oplysninger kan han udlede , lig med to, og sæt de kendte værdier ind i formlen и .

Angriberen kan derefter finde , efter at have talt :

Siden vi har defineret som tilfældigt udvalgte positive heltal er der et begrænset antal mulige . Ved at bruge disse oplysninger kan en angriber udlede , da 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 et begrænset udvalg af muligheder for det bliver tydeligt, hvor nemt det er at vælge og kontrollere værdier . Der er kun fem muligheder her.

Løsning af problemet med usikker heltal aritmetik

For at eliminere denne sårbarhed foreslår Shamir at bruge modulær aritmetik, der erstatter på Hvor и — mængden af ​​alle primtal.

Lad os hurtigt huske, hvordan modulær aritmetik fungerer. Et ur med visere er et velkendt koncept. Hun bruger altså et ur . Så snart timeviseren passerer tolv, vender den tilbage til en. En interessant egenskab ved dette system er, at vi blot ved at se på uret ikke kan udlede, hvor mange omdrejninger timeviseren har lavet. Men hvis vi ved, at timeviseren har passeret 12 fire gange, kan vi helt bestemme antallet af timer, der er gået ved hjælp af en simpel formel Hvor  - dette er vores divisor (her ),  — dette er koefficienten (hvor mange gange divisoren uden rest går ind i det oprindelige tal, her ), og  — dette er resten, som normalt returneres ved at ringe til modulo-operatøren (her ). At kende alle disse værdier giver os mulighed for at løse ligningen for , men hvis vi savner en koefficient, vil vi aldrig være i stand til at genoprette den oprindelige værdi.

Vi kan demonstrere, hvordan dette forbedrer sikkerheden i vores ordning ved at anvende ordningen på vores tidligere eksempel og bruge . Vores nye polynomiefunktion , og nye punkter . Nu kan nøgleholderne igen bruge polynomiel interpolation til at rekonstruere vores funktion, kun denne gang skal additions- og multiplikationsoperationerne ledsages af moduloreduktion. (f.eks ).

Antag ved at bruge dette nye eksempel, at angriberen lærte to af disse nye punkter, og offentlig information . Denne gang udleder angriberen, baseret på al den information, han har, følgende funktioner, hvor  — sættet af alle positive heltal, og repræsenterer modulets koefficient .

Nu finder vores angriber den igen , efter at have beregnet :

Så forsøger han at trække sig tilbage igen , udskiftning в :

Denne gang har han et alvorligt problem. Der er ingen værdier i formlen , и . Da der er et uendeligt antal kombinationer af disse variable, kan han ikke få yderligere information.

Sikkerhedshensyn

Shamirs hemmelige delingsordning antyder sikkerhed ud fra et informationsteoretisk synspunkt. Det betyder, at matematik er modstandsdygtig selv mod en angriber med ubegrænset computerkraft. Ordningen indeholder dog stadig flere kendte problemstillinger.

For eksempel skaber Shamirs plan ikke kontrollerede fragmenter, det vil sige, at folk frit kan præsentere falske fragmenter og forstyrre genoprettelsen af ​​den korrekte hemmelighed. En fjendtlig fragmentholder med tilstrækkelig information kunne endda producere et andet fragment ved at skifte efter eget skøn. Dette problem løses ved hjælp af 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 trivielt fyld hemmelighed med vilkårlige tal op til en fast længde.

Endelig er det vigtigt at bemærke, at vores sikkerhedsproblemer kan strække sig ud over selve ordningen. For rigtige kryptografiske applikationer er der ofte en trussel om sidekanalangreb, hvor en angriber forsøger at udtrække nyttig information fra applikationens eksekveringstid, caching, nedbrud osv. Hvis dette er et problem, bør det under udvikling overvejes omhyggeligt at bruge beskyttelsesforanstaltninger såsom konstanttidsfunktioner og opslag, der forhindrer hukommelsen i at blive tømt til andre ting, der ligger uden for rækkevidden af ​​dette artikel.

Демо

On denne side Der er en interaktiv demonstration af Shamirs hemmelige deleplan. Demonstrationen blev lavet med udgangspunkt i biblioteket ssss-js, som i sig selv er en JavaScript-port af et populært program ssss. Bemærk venligst, at beregning af store værdier , и det kan tage lidt tid.

Kilde: www.habr.com