Vurder et scenario der du må sikre et bankhvelv. Det anses som absolutt uinntakelig uten nøkkel, som du får utlevert allerede første arbeidsdag. Målet ditt er å oppbevare nøkkelen på en sikker måte.
La oss si at du bestemmer deg for å ha nøkkelen med deg til enhver tid, og gir tilgang til lagringen etter behov. Men du vil raskt innse at en slik løsning ikke skalerer godt i praksis, fordi din fysiske tilstedeværelse kreves hver gang du åpner lageret. Hva med ferien du ble lovet? I tillegg er spørsmålet enda mer skremmende: hva om du mistet din eneste nøkkel?
Med ferien i tankene bestemmer du deg for å lage en kopi av nøkkelen og overlate den til en annen ansatt. Du forstår imidlertid at dette heller ikke er ideelt. Ved å doble antall nøkler dobler du også sjansene for nøkkeltyveri.
I desperasjon ødelegger du duplikatet og bestemmer deg for å dele den originale nøkkelen i to. Nå skulle du tro at to pålitelige personer med nøkkelfragmenter måtte være fysisk til stede for å hente nøkkelen og åpne hvelvet. Dette betyr at en tyv må stjele to stykker, noe som er dobbelt så vanskelig som å stjele en nøkkel. Imidlertid innser du snart at denne ordningen ikke er mye bedre enn bare én nøkkel, for hvis noen mister en halv nøkkel, kan ikke hele nøkkelen gjenopprettes.
Problemet kan løses med en rekke ekstra nøkler og låser, men denne tilnærmingen vil raskt kreve много nøkler og låser. Du bestemmer deg for at det ideelle designet vil være å dele nøkkelen slik at sikkerheten ikke er helt avhengig av én person. Du konkluderer også med at det må være en terskel for antall fragmenter, slik at hvis ett fragment går tapt (eller hvis en person drar på ferie), forblir hele nøkkelen funksjonell.
Hvordan dele en hemmelighet
Denne typen nøkkelstyringsordning ble tenkt på av Adi Shamir i 1979 da han publiserte arbeidet sitt . Artikkelen forklarer kort den såkalte 
terskelskjema for effektivt å dele en hemmelig verdi (som en kryptografisk nøkkel) inn i deler. Da, når og bare når i det minste av deler er satt sammen, kan du enkelt gjenopprette hemmeligheten .
Fra et sikkerhetssynspunkt er en viktig egenskap ved denne ordningen at angriperen ikke skal vite absolutt noe med mindre han har minst deler. Til og med tilstedeværelsen deler skal ikke gi noen informasjon. Vi kaller denne eiendommen semantisk sikkerhet.
Polynominterpolasjon
Shamir terskelordning bygget rundt konseptet polynom interpolasjon. Hvis du ikke er kjent med dette konseptet, er det faktisk ganske enkelt. Faktisk, hvis du noen gang har tegnet punkter på en graf og deretter koblet dem sammen med linjer eller kurver, har du allerede brukt det!
Gjennom to punkter kan du tegne et ubegrenset antall polynomer av grad 2. For å velge det eneste fra dem, trenger du et tredje poeng. Illustrasjon:
Tenk på et polynom med grad én, . Hvis du vil plotte denne funksjonen på en graf, hvor mange punkter trenger du? Vel, vi vet at dette er en lineær funksjon som danner en linje, og derfor trenger den minst to punkter. Tenk deretter på en polynomfunksjon med grad to, . Dette er en kvadratisk funksjon, så det kreves minst tre punkter for å plotte grafen. Hva med et polynom med grad tre? Minst fire poeng. Og så videre.
Det virkelig kule med denne egenskapen er at, gitt graden av polynomfunksjonen og minst poeng, kan vi utlede tilleggspoeng for denne polynomfunksjonen. Vi kaller ekstrapolering av disse tilleggspunktene polynom interpolasjon.
Å finne på en hemmelighet
Du har kanskje allerede innsett at det er her Shamirs smarte opplegg kommer inn i bildet. La oss si vår hemmelighet - Er . Vi kan snu til et punkt på grafen og kom opp med en polynomfunksjon med grad , som tilfredsstiller dette punktet. La oss huske det vil være vår terskel for nødvendige fragmenter, så hvis vi setter terskelen til tre fragmenter, må vi velge en polynomfunksjon med grad to.
Polynomet vårt vil ha formen Der и — tilfeldig valgte positive heltall. Vi konstruerer bare et polynom med grad , hvor den frie koeffisienten – Dette er vår hemmelighet , og for hver av de påfølgende termer er det en tilfeldig valgt positiv koeffisient. Hvis vi går tilbake til det opprinnelige eksemplet og antar det , så får vi funksjonen .
På dette tidspunktet kan vi generere fragmenter ved å koble til unike heltall i Der (fordi det er vår hemmelighet). I dette eksemplet ønsker vi å fordele fire fragmenter med en terskel på tre, så vi genererer poeng tilfeldig og send ett poeng til hver av de fire betrodde personene, nøkkelvokterne. Det lar vi også folk få vite , siden dette regnes som offentlig informasjon og er nødvendig for gjenoppretting .
Å gjenopprette hemmeligheten
Vi har allerede diskutert begrepet polynomisk interpolasjon og hvordan det ligger til grunn for Shamirs terskelskjema . Når tre av de fire tillitsmennene ønsker å gjenopprette , de trenger bare å interpolere med sine egne unike poeng. For å gjøre dette kan de bestemme poengene sine og beregne Lagrange-interpolasjonspolynomet ved å bruke følgende formel. Hvis programmering er klarere for deg enn matematikk, så er pi egentlig en operatør for, som multipliserer alle resultater, og sigma er for, som legger alt sammen.
ved vi kan løse det slik og returnere vår opprinnelige polynomfunksjon:
For det vet vi , gjenoppretting enkelt gjort:
Bruker usikker heltallsaritmetikk
Selv om vi har brukt Shamirs grunnleggende idé , sitter vi igjen med et problem som vi har ignorert til nå. Polynomfunksjonen vår bruker usikker heltallsaritmetikk. Merk at for hvert ekstra poeng en angriper får på grafen til funksjonen vår, er det færre muligheter for andre poeng. Du kan se dette med egne øyne når du plotter et økende antall poeng for en polynomfunksjon ved å bruke heltallsaritmetikk. Dette er kontraproduktivt for vårt uttalte sikkerhetsmål, fordi angriperen skal vite absolutt ingenting før de har minst fragmenter.
For å demonstrere hvor svak den aritmetiske heltallskretsen er, vurdere et scenario der en angriper oppnådde to poeng og vet offentlig informasjon som . Fra denne informasjonen kan han utlede , lik to, og plugg inn de kjente verdiene i formelen и .
Angriperen kan da finne , teller :
Siden vi har definert som tilfeldig utvalgte positive heltall er det et begrenset antall mulige . Ved å bruke denne informasjonen kan en angriper utlede , siden noe større enn 5 vil gjøre negativ. Dette viser seg å være sant siden vi har bestemt oss
Angriperen kan deretter beregne de mulige verdiene erstatte в :
Med begrensede muligheter for det blir tydelig hvor enkelt det er å velge og kontrollere verdiene . Det er bare fem alternativer her.
Løser problemet med usikker heltallsaritmetikk
For å eliminere denne sårbarheten foreslår Shamir å bruke modulær aritmetikk, og erstatte på Der и — settet med alle primtall.
La oss raskt huske hvordan modulær aritmetikk fungerer. En klokke med visere er et kjent konsept. Hun bruker en klokke altså . Så snart timeviseren passerer tolv, går den tilbake til én. En interessant egenskap ved dette systemet er at bare ved å se på klokken, kan vi ikke utlede hvor mange omdreininger timeviseren har gjort. Men hvis vi vet at timeviseren har passert 12 fire ganger, kan vi fullstendig bestemme antall timer som har gått ved hjelp av en enkel formel Der er vår divisor (her ), er koeffisienten (hvor mange ganger divisoren går inn i det opprinnelige tallet uten en rest, her ), a er resten, som vanligvis returnerer et modulo-operatøranrop (her ). Å kjenne alle disse verdiene gjør at vi kan løse ligningen for , men hvis vi savner koeffisienten, vil vi aldri kunne gjenopprette den opprinnelige verdien.
Vi kan demonstrere hvordan dette forbedrer sikkerheten til ordningen vår ved å bruke ordningen på vårt tidligere eksempel og bruke . Vår nye polynomfunksjon , og de nye punktene . Nå kan nøkkelholderne igjen bruke polynomiell interpolasjon for å rekonstruere funksjonen vår, bare denne gangen må addisjons- og multiplikasjonsoperasjonene ledsages av moduloreduksjon (f.eks ).
Ved å bruke dette nye eksemplet, la oss anta at angriperen lærte to av disse nye punktene, og offentlig informasjon . Denne gangen gir angriperen, basert på all informasjonen han har, følgende funksjoner, hvor er settet av alle positive heltall, og representerer modulkoeffisienten .
Nå finner angriperen vår igjen , beregner :
Så prøver han igjen erstatte в :
Denne gangen har han et alvorlig problem. Formelen mangler verdier , и . Siden det finnes et uendelig antall kombinasjoner av disse variablene, kan han ikke få ytterligere informasjon.
Sikkerhetshensyn
Shamirs hemmelige delingsordning antyder sikkerhet fra et informasjonsteoretisk synspunkt. Dette betyr at matematikken er motstandsdyktig selv mot en angriper med ubegrenset datakraft. Imidlertid inneholder kretsen fortsatt flere kjente problemer.
For eksempel skaper ikke Shamirs opplegg fragmenter som skal sjekkes, det vil si at folk fritt kan presentere falske fragmenter og forstyrre gjenopprettingen av den riktige hemmeligheten. En fiendtlig fragmentholder med tilstrekkelig informasjon kan til og med produsere et annet fragment ved å bytte etter eget skjønn. Dette problemet løses ved hjelp av verifiserbare hemmelige delingsordninger, for eksempel Feldmans opplegg.
Et annet problem er at lengden på ethvert fragment er lik lengden på den tilsvarende hemmeligheten, så lengden på hemmeligheten er lett å bestemme. Dette problemet kan løses med trivielt polstring hemmelig med vilkårlige tall opp til en fast lengde.
Til slutt er det viktig å merke seg at våre sikkerhetsproblemer kan strekke seg utover selve designet. For kryptografiske applikasjoner i den virkelige verden er det ofte trusselen om sidekanalangrep der en angriper prøver å trekke ut nyttig informasjon fra applikasjonskjøringstid, caching, krasjer osv. Hvis dette er en bekymring, bør det under utvikling vurderes nøye om å bruke beskyttelsestiltak som funksjoner og konstanttidsoppslag, forhindre at minne lagres på disk, og en rekke andre hensyn som ligger utenfor denne artikkelens omfang.
demo
På Det er en interaktiv demonstrasjon av Shamirs hemmelige delingsopplegg. Demonstrasjon basert på biblioteket , som i seg selv er en JavaScript-port for det populære programmet . Merk at å beregne store verdier , и kan ta en stund.
Kilde: www.habr.com