Låt oss överväga ett scenario där det är nödvändigt att säkerställa säkerheten för ett bankvalv. Det anses vara helt oåtkomligt utan nyckeln, som du får den första dagen av din anställning. Ditt mål är att på ett tillförlitligt sätt bevara nyckeln.

Anta att du beslutat att alltid ha nyckeln på dig, och ge tillgång till valvet vid behov. Men du kommer snabbt att inse att en sådan lösning inte skalar praktiskt, eftersom det varje gång krävs att du är fysiskt närvarande för att öppna valvet. Vad händer med semestern som du lovades? Dessutom är det ännu mer oroande frågan: vad om du förlorar den enda nyckeln?

Med tanken på semestern beslutade du att göra en kopia av nyckeln och överlämna den till en annan anställd. Men du förstår att detta inte är perfekt heller. Genom att dubblera antalet nycklar har du också dubblerat möjligheterna för nyckeln att stjälas.

I desperation förstör du kopian och beslutar att dela upp den ursprungliga nyckeln i två delar. Nu tänker du att två betrodda personer med nyckeldela måste vara fysiskt närvarande för att sätta ihop nyckeln och öppna valvet. Detta innebär att tjuven måste stjäla två delar, vilket är dubbelt så svårt som att stjäla en nyckel. Men snart inser du att denna lösning inte är mycket bättre än en enda nyckel, eftersom om någon förlorar en del av nyckeln, kan den fullständiga nyckeln inte återställas.

Problemet kan lösas med hjälp av en serie ytterligare nycklar och lås, men med ett sådant tillvägagångssätt kommer det snart att krävas män fler nycklar och lås. Du beslutar att den idealiska lösningen är att dela upp nyckeln så att säkerheten inte helt beror på en enda person. Du drar också slutsatsen att det måste finnas en viss tröskel för antalet delar, så att om en del går förlorad (eller om personen går på semester) kvarstår den fullständiga nyckeln funktionell.

Hur man delar en hemlighet

Denna typ av nyckelhanteringsschema reflekterade Adi Shamir över 1979 när han publicerade sitt arbete «Hur man delar en hemlighet». I artikeln förklaras kort den så kallade tröskelschema för effektiv delning av ett hemligt värde (till exempel en kryptografisk nyckel) i delar. När och endast när minst från delar har samlats in kan hemligheten enkelt återställas. .

Ur säkerhetssynpunkt är en viktig egenskap hos detta schema att en angripare inte bör veta något alls om han inte har minst delar. Även närvaron av delar bör inte ge någon information. Vi kallar denna egenskap semantisk säkerhet.

Polynominterpolation

Shamir's tröskelschema är uppbyggd kring konceptet polynominterpolation. Om du inte är bekant med detta koncept är det faktiskt ganska enkelt. Om du någonsin har ritat punkter på ett diagram och sedan kopplat dem med linjer eller kurvor, har du redan använt det!

Genom två punkter kan ett obegränsat antal polynom av grad 2 dras. För att välja en unik från dem behövs en tredje punkt. Exempel: Wikipedia

Låt oss betrakta ett polynom av grad ett, . Om du vill avbilda denna funktion på ett diagram, hur många punkter behöver du? Tja, vi vet att det är en linjär funktion som bildar en linje, så det krävs minst två punkter. Låt oss sedan titta på en polynomfunktion av grad två, . Det är en kvadratisk funktion, så för att avbilda den krävs minst tre punkter. Hur är det med ett polynom av grad tre? Minst fyra punkter. Och så vidare.

Den riktigt häftiga saken med denna egenskap är att, med hänsyn till graden av den polynomfunktion och minst punkter, kan vi generera ytterligare punkter för denna polynomfunktion. Extrapoleringen av dessa ytterligare punkter kallas polynominterpolation.

Att skapa en hemlighet

Du har kanske redan förstått att Shamir's smarta schema kommer in här. Anta att vår hemlighet är — detta är . Vi kan omvandla till en punkt på grafen och skapa en polynomfunktion av graden , som uppfyller denna punkt. Kom ihåg att vara vår tröskel för de nödvändiga delarna, så om vi sätter tröskeln till tre delar måste vi välja en polynomfunktion av graden två.

Vårt polynom kommer att ha formen , där och — slumpmässigt valda positiva heltal. Vi bygger helt enkelt ett polynom av graden , där konstanten  är vår hemlighet , och var och en av de följande medlemmar finns en slumpmässigt vald positiv koefficient. Om vi återgår till det ursprungliga exemplet och antar att , då får vi en funktion .

Vid det här stadiet kan vi generera fragment genom att ansluta unika hela tal i , där (eftersom det är vår hemlighet). I detta exempel vill vi dela ut fyra fragment med en tröskel på tre, så vi genererar slumpmässigt punkter och skickar en punkt till var och en av de fyra betrodda personerna, nyckelns förvaltare. Vi informerar också människor att , eftersom det anses vara offentlig information och nödvändigt för återställning .

Återställning av hemligheten

Vi har redan diskuterat begreppet polynomial interpolation och vad som ligger till grund för Shamir's tröskelschema . När vilka tre av fyra betrodda personer vill återställa , behöver de bara interpolera med sina unika punkter. För detta kan de bestämma sina punkter och beräkna Lagrange-interpolationspolynomet med hjälp av följande formel. Om programmering är mer begriplig för dig än matematik, är pi i huvudsak en operator for, som multiplicerar alla resultat, och sigma är for, som adderar allt.

Vid vi kan lösa detta på följande sätt och återfå vår ursprungliga polynomialfunktion:

Eftersom vi vet att , återställningen utförs enkelt:

Användning av osäker heltalsarithmetic

Trots att vi framgångsrikt har tillämpat Shamir's grundidé , har vi ett problem som vi har ignorerat fram till nu. Vår polynomialfunktion använder osäker heltalsarithmetic. Tänk på att för varje ytterligare punkt som angriparen får på grafen av vår funktion, finns det färre möjliga alternativ för andra punkter. Du kan se det med egna ögon när du bygger en graf med ökat antal punkter för en polynomialfunktion med hjälp av heltalsarithmetic. Detta är kontraproduktivt för vårt angivna säkerhetsmål, eftersom en angripare inte bör veta någonting förrän de har minst fragment.

För att visa hur svag schemat med heltalsarithmetic är, överväg ett scenario där angriparen har fått två punkter och vet den offentliga informationen att . Utifrån denna information kan den utföra , som är lika med två, och koppla in kända värden i formeln och .

Sedan kan angriparen hitta , genom att räkna :

Eftersom vi har definierat som slumpmässigt valda positiva heltal, finns det ett begränsat antal möjliga . Med denna information kan angriparen utföra , eftersom allt över 5 gör att blir negativt. Detta visar sig vara sant eftersom vi har definierat

Sedan kan angriparen beräkna möjliga värden , genom att ersätta på :

Med en begränsad uppsättning alternativ för blir det uppenbart hur lätt det är att gissa och verifiera värden . Här finns bara fem alternativ.

Lösning på problemet med osäker heltalsaritmetik

För att åtgärda denna sårbarhet föreslår Shamir att använda modulär aritmetik, genom att ersätta till , där och — mängden av alla primtal.

Låt oss snabbt friska upp minnet om hur modulär aritmetik fungerar. Klockor med visare är ett bekant koncept. Det använder klockor som är . Så snart klockvisaren passerar tolv, återgår den till ett. En intressant egenskap hos detta system är att vi bara genom att titta på klockan inte kan avgöra hur många varv klockvisaren har gjort. Men om vi vet att klockvisaren har passerat 12 fyra gånger, kan vi helt bestämma antalet passerade timmar med hjälp av en enkel formel , där  — det är vår delare (här ),  — det är koefficienten (hur många gånger delaren utan rest går in i det ursprungliga talet, här ), och  — det är resten, som vanligtvis returneras av modulusoperatorn (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 återskapa det ursprungliga värdet.

Man kan visa hur detta förbättrar säkerheten i vårt system genom att tillämpa systemet på vårt tidigare exempel och använda . Vår nya polynomfunktion , och de nya punkterna . Nu kan nyckelvårdare återigen använda polynominterpolering för att återställa vår funktion, men den här gången måste addition och multiplikation åtföljas av reduktion mod (t.ex. ).

Med detta nya exempel, anta att angriparen har fått kännedom om två av dessa nya punkter, , och den offentliga informationen . Den här gången använder angriparen all tillgänglig information för att extrahera följande funktioner, där  — mängden av alla positiva heltal, och representerar modulkoefficienten .

Nu finner vår angripare återigen , genom att beräkna :

Därefter försöker han åter igen att extrahera , genom att ersätta på :

Den här gången har han ett allvarligt problem. Det saknas värden i formeln , och . Eftersom det finns oändligt många kombinationer av dessa variabler kan han inte få någon ytterligare information.

Säkerhetsöverväganden

Shamir’s hemlighetsdelning erbjuder säkerhet ur informationsteoretiskt perspektiv. Det innebär att matematiken är robust även mot en angripare med oändlig datorkapacitet. Dock innehåller systemet fortfarande flera kända problem.

Till exempel skapar Shamir’s schema inte verifierbara fragment, vilket innebär att personer fritt kan presentera falska fragment och försvåra återställandet av den korrekta hemligheten. En illvillig fragmentförvarare med tillräcklig information kan till och med producera ett annat fragment genom att ändra som han eller hon behagar. Detta problem löses med verifierbara hemlighetsdelningssystem, såsom Feldmans schema.

Ett annat problem är att längden av vilket fragment som helst är lika med längden av den motsvarande hemligheten, så att hemlighetens längd enkelt kan bestämmas. Detta problem löses med trivial fyllning av hemligheten med slumpmässiga siffror till en fast längd.

Slutligen är det viktigt att notera att våra säkerhetsoro kan sträcka sig bortom själva systemet. För verkliga kryptografiska tillämpningar finns ofta hot om sidokanalsattacker, där angriparen försöker extrahera känslig information från applikationens körning, cacheminne, kraschar, osv. Om detta är en oro, bör man noggrant överväga användningen av skyddsåtgärder, såsom konstant tidsfunktioner och sökningar, förhindra skrivningar till disk och tänka på en rad andra aspekter som går bortom denna artikel.

Demo

På denna sida det finns en interaktiv demonstration av Shamir’s hemlighetsdelning. Demonstrationen bygger på biblioteket ssss-js, som i sig är en JavaScript-port av det populära programmet ssss. Observera att beräkning av stora värden , och kan ta lite tid.

Källa: habr.com