Lad os overveje et scenarie, hvor det er nødvendigt at sikre et bankskabet. Det betragtes som fuldstændig utilgængeligt uden nøglen, som du får udleveret den første arbejdsdag. Dit mål er at opbevare nøglen sikkert.

Antag, at du beslutter at opbevare nøglen hos dig selv hele tiden og kun give adgang til skabet efter behov. Men du vil hurtigt indse, at en sådan løsning ikke skalerer godt i praksis, fordi dit fysiske nærvær altid er nødvendigt for at åbne skabet. Hvad med den ferie, de lovede dig? Desuden er der et endnu mere skræmmende spørgsmål: hvad nu hvis du mister den eneste nøgle?

Med tanken om ferien besluttede du at lave en kopi af nøglen og betro den til en anden medarbejder. Men du forstår, at det heller ikke er ideelt. Ved at fordoble antallet af nøgler har du også fordoblet mulighederne for, at nøglen kan blive stjålet.

Fortvivlet ødelægger du kopien og beslutter at dele den originale nøgle i to. Nu tænker du, at to betroede personer med fragmenter af nøglen skal være til stede fysisk for at samle nøglen og åbne skabet. Det betyder, at tyven skal stjæle to fragmenter, hvilket gør det sværere end at stjæle en enkelt nøgle. Men snart indser du, at denne ordning ikke er meget bedre end blot én nøgle, fordi hvis nogen mister halvdelen af nøglen, kan den fulde nøgle ikke genoprettes.

Problemet kan løses med en række ekstra nøgler og låse, men med denne tilgang vil der hurtigt være brug for mange nøgler og låse. Du beslutter, at i en ideel ordning skal nøglen deles, 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å ved tab af et fragment (eller hvis en person tager på ferie), forbliver den samlede nøgle funktionel.

Hvordan man deler et hemmelighed

Om denne type nøglehåndteringsordning tænkte Adi Shamir i 1979, da han publicerede sit arbejde »Hvordan man deler et hemmelighed«. Artiklen forklarer kort den såkaldte tærskelsordning for effektivt at dele en hemmelig værdi (f.eks. en kryptografisk nøgle) op i dele. Derefter, når og kun når mindst af dele er samlet, kan hemmeligheden let genoprettes. .

Set fra et sikkerhedsmæssigt synspunkt er en vigtig egenskab ved denne skema, at en angriber ikke skal vide noget som helst, hvis han ikke har mindst dele. Selv tilstedeværelsen af dele må ikke give nogen information. Vi kalder denne egenskab semantisk sikkerhed.

Polynomiel interpolation

Shamir's tærskelskema er bygget op omkring begrebet polynomiel interpolation. Hvis du ikke er bekendt med dette begreb, er det faktisk ret enkelt. Generelt, hvis du nogensinde har tegnet punkter på en graf og derefter forbundet dem med linjer eller kurver, så har du allerede brugt det!

Gennem to punkter kan der trækkes et ubegribelig antal polynomer af grad 2. For at vælge et unikt polynom kræves et tredje punkt. Illustration: Wikipedia

Lad os overveje et polynom af grad én, . Hvis du vil opbygge denne funktion på grafen, hvor mange punkter har du brug for? Nå, vi ved, at det er en lineær funktion, der danner en linje, og derfor kræver det mindst to punkter. Lad os dernæst overveje en polynomiel funktion af grad to, . Dette er en kvadratisk funktion, så til opbygning af grafen kræves mindst tre punkter. Hvad med et polynom af grad tre? Mindst fire punkter. Og så videre og så videre.

Det virkelig fede ved denne egenskab er, at givet graden af den polynomielle funktion og mindst punkter, kan vi udlede yderligere punkter for denne polynomielle funktion. Ekstrapoleringen af disse yderligere punkter kalder vi polynomiel interpolation.

Sammensætning af hemmeligheden

Måske har du allerede indset, at den smarte Shamir's skema træder i kraft her. Lad os antage, at vores hemmelighed — det er . Vi kan omdanne til et punkt på grafen og finde på en polynomiel funktion af grad , som opfylder dette punkt. Lad os huske, at vil være vores tærskel for de nødvendige fragmenter, så hvis vi sætter tærsklen til tre fragmenter, skal vi vælge en polynomiel funktion af grad to.

Vores polynom vil have formen , hvor og — tilfældigt valgte positive heltal. Vi bygger kun et polynom af grad , hvor konstantleddet  er vores hemmelighed , og hver af de efterfølgende medlemmer er tilfældigt valgt med en positiv koefficient. Hvis vi vender tilbage til det oprindelige eksempel og antager, at , så vil vi få en funktion .

På dette stadium kan vi generere fragmenter ved at tilslutte unikke hele tal i , hvor (for det er vores hemmelighed). I dette eksempel ønsker vi at tildele fire fragmenter med en tærskel på tre, så vi genererer tilfældigt punkter og sender et punkt til hver af de fire betroede personer, nøglebevarerne. Vi informerer også folk om, at , da dette betragtes som offentlig information og er nødvendigt for gendannelse .

Gendannelse af hemmeligheden

Vi har allerede diskuteret konceptet om polynomiel interpolation og at det ligger til grund for Shamirs tærskelschema . Når som helst tre af de fire betroede personer ønsker at gendanne , skal de blot interpolere med deres unikke punkter. For dette kan de definere deres punkter og beregne Lagranges interpolationspolynomium ved at bruge følgende formel. Hvis programmering er mere forståeligt for dig end matematik, så er pi i bund og grund en operator til, der multiplicerer alle resultaterne, mens sigma er til, der lægger alt sammen.

Ved kan vi løse dette som følger og returnere vores oprindelige polynomiefunktion:

Da vi ved, at , gendannelsen udføres ganske enkelt:

Brug af usikker heltalsarithmetic

Selvom vi har anvendt den grundlæggende idé fra Shamir med succes , står vi over for et problem, som vi har ignoreret indtil nu. Vores polynomielle funktion bruger usikker heltalsarithmetic. Husk, at for hver ekstra punkt, en angriber får på grafen af vores funktion, er der færre muligheder for andre punkter tilbage. Du kan se det med egne øjne, når du bygger grafen med et stigende antal punkter for en polynomiel funktion ved brug af heltalsarithmetic. Dette er kontraproduktivt for vores erklærede sikkerhedsmål, fordi en angriber ikke bør lære noget som helst, før de har mindst fragmenter.

For at demonstrere, hvor svagt skemaet med heltalsarithmetic er, lad os overveje et scenarie, hvor angriberen har fået to punkter og kender den offentlige information, at . Fra disse oplysninger kan han udlede , der svarer til to, og indsætte de kendte værdier i formlen og .

Derefter kan angriberen finde , ved at beregne :

Da vi har defineret som tilfældigt valgte hele positive tal, er der et begrænset antal mulige . Ved hjælp af disse oplysninger kan angriberen udlede , da alt over 5 vil gøre negativt. Dette viser sig at være sandt, da vi har defineret

Derefter kan angriberen beregne mulige værdier , ved at erstatte i :

Med et begrænset sæt muligheder for bliver det klart, hvor let det er at gætte og verificere værdierne . Her er der kun fem muligheder.

Løsningen på problemet med usikker heltalsaritmetik

For at afhjælpe denne sårbarhed foreslår Shamir at anvende modulær aritmetik og erstatte og få en fungerende kommando. , hvor og — mængden af alle primtal.

Lad os hurtigt mindes om, hvordan modulær aritmetik fungerer. Vækkere med visere er et velkendt koncept. Det bruger ur, som er . Så snart timeviseren går forbi tolv, vender den tilbage til én. En interessant egenskab ved dette system er, at bare ved at se på klokken kan vi ikke udlede, hvor mange omdrejninger timeviseren har gjort. Men hvis vi ved, at timeviseren har passeret 12 fire gange, kan vi fuldstændig bestemme antallet af forløbne timer ved hjælp af en simpel formel , hvor  — det er vores divisor (her ),  — er kvotienten (hvor mange gange divisoren uden rest går ind i det oprindelige tal, her ), mens  — er resten, som normalt returneres af modulus operatoren (her ). At kende alle disse værdier gør det muligt for os at løse ligningen for , men hvis vi springer kvotienten over, vil vi aldrig kunne genskabe den oprindelige værdi.

Vi kan demonstrere, hvordan dette forbedrer sikkerheden i vores skema ved at anvende skemaet til vores tidligere eksempel og bruge . Vores nye polynomiske funktion , og de nye punkter . Nu kan nøglebevarerne igen bruge polynomiel interpolation til at genskabe vores funktion, men denne gang skal operationerne addition og multiplikation ledsages af reduktion modulo (f.eks. ).

Ved hjælp af dette nye eksempel, antag at angriberen kender to af disse nye punkter, , og de offentlige oplysninger . Denne gang udleder angriberen baseret på al den information, han har, følgende funktioner, hvor  — mængden af alle positive hele tal, og repræsenterer modulkoefficienten. .

Nu finder vores angriber igen , ved at beregne :

Derefter prøver han igen at udlede , ved at erstatte i :

Denne gang har han et alvorligt problem. Værdier mangler i formlen , og . Da der er et uendeligt antal kombinationer af disse variabler, kan han ikke få nogen yderligere information.

Sikkerhedsovervejelser

Shamir's hemmelighedsdeleskema tilbyder sikkerhed set fra informationsteoriens synspunkt.. Det betyder, at matematikken er robust selv mod en angriber med ubegrænsede beregningsressourcer. Dog indeholder skemaet stadig flere kendte problemer.

For eksempel skaber Shamir's skema ikke verificerbare fragmenter,det vil sige, at folk frit kan præsentere falske fragmenter og hindre genoprettelsen af den korrekte hemmelighed. En fjendtlig fragmentopbevarer med tilstrækkelig information kan endda producere et andet fragment ved at ændre som han ønsker. Dette problem løses ved hjælp af verificerbare hemmelighedsdeleskemaer,såsom Feldman's skema.

Et andet problem er, at længden af ethvert fragment er lig med længden af den tilsvarende hemmelighed, så længden af hemmeligheden kan nemt bestemmes. Dette problem løses ved triviel fyldning af hemmeligheden med tilfældige tal op til en fast længde.

Endelig er det vigtigt at bemærke, at vores bekymringer om sikkerhed kan gå ud over selve skemaet. For rigtig kryptografiske applikationer er der ofte trusler fra sidekanaler, hvor angriberen forsøger at udtrække nyttig information fra applikationens kørselstid, cache, nedbrud osv. Hvis dette vækker bekymring, bør der i udviklingsfasen tages nøje overvejelser om brugen af beskyttelsesforanstaltninger som funktioner og søgning med konstant kørselstid for at forhindre skrivning af hukommelse til disk og overveje en række andre ting, der går ud over denne artikel.

Demo

På denne side har en interaktiv demonstration af Shamir's hemmelighedsdeleskema. Demonstrationen er bygget på biblioteket ssss-js, som i sig selv er en JavaScript-port af det populære program ssss. Bemærk, at beregningen af store værdier , og kan tage noget tid.

Kilde: habr.com