Överväg ett scenario där du behöver säkra ett bankvalv. Det anses absolut ointagligt utan nyckel, som du får redan första arbetsdagen. Ditt mål är att förvara nyckeln på ett säkert sätt.
Låt oss säga att du bestämmer dig för att ha nyckeln med dig hela tiden, och ge tillgång till lagringen efter behov. Men du kommer snabbt att inse att en sådan lösning inte skalar bra i praktiken, eftersom din fysiska närvaro krävs varje gång du öppnar förrådet. Hur är det med semestern du blev lovad? Dessutom är frågan ännu mer skrämmande: tänk om du tappade bort din enda nyckel?
Med din semester i åtanke bestämmer du dig för att göra en kopia av nyckeln och anförtro den till en annan anställd. Du förstår dock att detta inte heller är idealiskt. Genom att dubbla antalet nycklar fördubblar du också chansen för nyckelstöld.
I desperation förstör du dubbletten och bestämmer dig för att dela originalnyckeln på mitten. Nu skulle du kunna tro att två betrodda personer med nyckelfragment måste vara fysiskt närvarande för att hämta nyckeln och öppna valvet. Det betyder att en tjuv behöver stjäla två bitar, vilket är dubbelt så svårt som att stjäla en nyckel. Men du inser snart att det här schemat inte är mycket bättre än bara en nyckel, för om någon tappar en halv nyckel kan hela nyckeln inte återställas.
Problemet kan lösas med en rad ytterligare nycklar och lås, men detta tillvägagångssätt kommer snabbt att kräva много nycklar och lås. Du bestämmer dig för att den idealiska designen skulle vara att dela nyckeln så att säkerheten inte helt förlitar sig på en person. Du drar också slutsatsen att det måste finnas någon tröskel för antalet fragment så att om ett fragment försvinner (eller om en person åker på semester) förblir hela nyckeln funktionell.
Hur man delar en hemlighet
Den här typen av nyckelhanteringsplan tänkte Adi Shamir på 1979 när han publicerade sitt arbete . Artikeln förklarar kort den sk 
tröskelschema för att effektivt dela upp ett hemligt värde (såsom en kryptografisk nyckel) i delar. Då, när och bara när åtminstone av delar är monterade, kan du enkelt återställa hemligheten .
Ur säkerhetssynpunkt är en viktig egenskap hos detta system att angriparen inte ska veta absolut någonting om han inte har minst delar. Till och med närvaron delar ska inte ge någon information. Vi kallar denna fastighet semantisk säkerhet.
Polynominterpolation
Shamir tröskelschema uppbyggd kring konceptet polynominterpolation. Om du inte är bekant med detta koncept är det faktiskt ganska enkelt. Faktum är att om du någonsin har ritat punkter på en graf och sedan kopplat dem med linjer eller kurvor, har du redan använt det!
Genom två punkter kan du rita ett obegränsat antal polynom av grad 2. För att välja den enda av dem behöver du en tredje poäng. Illustration:
Betrakta ett polynom med grad ett, . Om du vill rita den här funktionen på en graf, hur många poäng behöver du? Tja, vi vet att detta är en linjär funktion som bildar en linje och därför behöver den minst två punkter. Betrakta sedan en polynomfunktion med grad två, . Detta är en kvadratisk funktion, så det krävs minst tre punkter för att plotta grafen. Vad sägs om ett polynom med grad tre? Minst fyra poäng. Och så vidare.
Det riktigt coola med den här egenskapen är att, givet graden av polynomfunktionen och åtminstone poäng, kan vi härleda ytterligare poäng för denna polynomfunktion. Vi kallar extrapolering av dessa ytterligare punkter polynominterpolation.
Att hitta på en hemlighet
Du kanske redan har insett att det är här Shamirs smarta plan kommer in i bilden. Låt oss säga vår hemlighet - Är . Vi kan vända till en punkt på grafen och kom fram till en polynomfunktion med grad , vilket uppfyller denna punkt. Låt oss komma ihåg det kommer att vara vår tröskel för nödvändiga fragment, så om vi sätter tröskeln till tre fragment måste vi välja en polynomfunktion med grad två.
Vårt polynom kommer att ha formen var и — Slumpmässigt valda positiva heltal. Vi konstruerar bara ett polynom med grad , där den fria koefficienten – Det här är vår hemlighet , och för var och en av de efterföljande termer finns en slumpmässigt vald positiv koefficient. Om vi återgår till det ursprungliga exemplet och antar det , då får vi funktionen .
Vid denna tidpunkt kan vi generera fragment genom att ansluta unika heltal i var (eftersom det är vår hemlighet). I det här exemplet vill vi fördela fyra fragment med en tröskel på tre, så vi genererar slumpmässigt poäng och skicka en poäng till var och en av de fyra betrodda personerna, nyckelns väktare. Vi låter också folk veta det , eftersom detta anses vara offentlig information och är nödvändigt för återvinning .
Återställa hemligheten
Vi har redan diskuterat begreppet polynominterpolation och hur det ligger till grund för Shamirs tröskelschema . När någon av tre av de fyra förvaltarna vill återställa , de behöver bara interpolera med sina egna unika poäng. För att göra detta kan de bestämma sina poäng och beräkna Lagrange-interpolationspolynomet med hjälp av följande formel. Om programmering är tydligare för dig än matematik, så är pi i huvudsak en operatör for, vilket multiplicerar alla resultat, och sigma är for, vilket lägger ihop allt.
vid vi kan lösa det så här och returnera vår ursprungliga polynomfunktion:
Eftersom vi vet det , återhämtning gjort helt enkelt:
Använder osäker heltalsaritmetik
Även om vi framgångsrikt har tillämpat Shamirs grundidé , vi har ett problem som vi har ignorerat fram till nu. Vår polynomfunktion använder osäker heltalsaritmetik. Observera att för varje ytterligare poäng en angripare får på grafen för vår funktion, finns det färre möjligheter för andra poäng. Du kan se detta med dina egna ögon när du ritar ett ökande antal punkter för en polynomfunktion med heltalsaritmetik. Detta är kontraproduktivt för vårt uttalade säkerhetsmål, eftersom angriparen borde veta absolut ingenting förrän de åtminstone har det fragment.
För att visa hur svag den aritmetiska heltalskretsen är, överväg ett scenario där en angripare fick två poäng och vet offentlig information som . Av denna information kan han utläsa , lika med två, och koppla in de kända värdena i formeln и .
Angriparen kan sedan hitta , räknar :
Sedan vi har definierat som slumpmässigt valda positiva heltal finns det ett begränsat antal möjliga . Med hjälp av denna information kan en angripare härleda , eftersom allt större än 5 duger negativ. Detta visar sig vara sant eftersom vi har bestämt oss
Angriparen kan sedan beräkna de möjliga värdena byter ut в :
Med begränsade alternativ för det blir tydligt hur enkelt det är att välja och kontrollera värdena . Det finns bara fem alternativ här.
Lös problemet med osäker heltalsaritmetik
För att eliminera denna sårbarhet föreslår Shamir att du använder modulär aritmetik, ersätter på var и — mängden av alla primtal.
Låt oss snabbt komma ihåg hur modulär aritmetik fungerar. En klocka med visare är ett bekant koncept. Hon använder en klocka alltså . Så snart timvisaren passerar tolv återgår den till ett. En intressant egenskap hos detta system är att vi bara genom att titta på klockan inte kan härleda hur många varv timvisaren har gjort. Men om vi vet att timvisaren har passerat 12 fyra gånger, kan vi helt bestämma antalet timmar som har gått med en enkel formel var är vår divisor (här ), är koefficienten (hur många gånger divisorn går in i det ursprungliga talet utan en rest, här ) och är resten, vilket vanligtvis returnerar ett modulo-operatörsanrop (här ). Att känna till alla dessa värden gör att vi kan lösa ekvationen för , men om vi missar koefficienten kommer vi aldrig att kunna återställa det ursprungliga värdet.
Vi kan visa hur detta förbättrar säkerheten för vårt system genom att tillämpa schemat på vårt tidigare exempel och använda . Vår nya polynomfunktion , och de nya punkterna . Nu kan nyckelhållarna återigen använda polynominterpolation för att rekonstruera vår funktion, men denna gång måste additions- och multiplikationsoperationerna åtföljas av moduloreduktion (t.ex ).
Med det här nya exemplet, låt oss anta att angriparen lärde sig två av dessa nya punkter, och offentlig information . Den här gången matar angriparen, baserat på all information han har, följande funktioner, var är mängden av alla positiva heltal, och representerar modulkoefficienten .
Nu hittar vår angripare igen , beräknar :
Sedan försöker han igen byter ut в :
Den här gången har han ett allvarligt problem. Formel saknar värden , и . Eftersom det finns ett oändligt antal kombinationer av dessa variabler kan han inte få någon ytterligare information.
Säkerhetsöverväganden
Shamirs hemliga delningsschema antyder säkerhet ur informationsteoretisk synvinkel. Det betyder att matematiken är motståndskraftig även mot en angripare med obegränsad datorkraft. Kretsen innehåller dock fortfarande flera kända problem.
Till exempel skapar inte Shamirs plan fragment som ska kontrolleras, det vill säga människor kan fritt presentera falska fragment och störa återställningen av den korrekta hemligheten. En fientlig fragmenthållare med tillräcklig information kan till och med producera ett annat fragment genom att byta efter eget gottfinnande. Detta problem löses med hjälp av verifierbara hemlighetsdelningssystem, såsom Feldmans schema.
Ett annat problem är att längden på ett fragment är lika med längden på motsvarande hemlighet, så längden på hemligheten är lätt att bestämma. Detta problem kan lösas med trivial stoppning hemlig med godtyckliga nummer upp till en fast längd.
Slutligen är det viktigt att notera att våra säkerhetsproblem kan sträcka sig längre än själva designen. För kryptografiska applikationer i den verkliga världen finns det ofta hot om sidokanalattacker där en angripare försöker extrahera användbar information från applikationskörningstid, cachning, krascher, etc. Om detta är ett problem, bör man under utvecklingen noggrant överväga att använda skyddsåtgärder som funktioner och konstanttidsuppslagningar, förhindra att minne sparas på disk och ett antal andra överväganden som ligger utanför den här artikelns räckvidd.
Демо
På Det finns en interaktiv demonstration av Shamirs hemliga delningsschema. Demonstration baserad på biblioteket , som i sig är en JavaScript-port för det populära programmet . Observera att man beräknar stora värden , и kan ta ett tag.
Källa: will.com