Stel je een scenario voor waarin je een bankkluis moet beveiligen. Deze wordt als volledig ontoegankelijk beschouwd zonder de sleutel die je op je eerste werkdag krijgt. Je doel is om de sleutel veilig te bewaren.

Stel dat u besluit de sleutel altijd bij u te houden en toegang tot de kluis te verlenen wanneer nodig. Maar u zult al snel merken dat zo'n oplossing in de praktijk niet goed schaalbaar is, omdat uw fysieke aanwezigheid vereist is om de kluis elke keer te openen. En hoe zit het dan met de vakantie die u beloofd is? En nog angstaanjagender is de vraag: wat als u uw enige sleutel kwijtraakt?

Met het oog op uw vakantie besluit u een kopie van de sleutel te maken en deze aan een andere medewerker toe te vertrouwen. U realiseert zich echter dat ook dit niet ideaal is. Door het aantal sleutels te verdubbelen, verdubbelt u ook de kans op diefstal.

In wanhoop vernietig je de duplicaatsleutel en besluit je de originele sleutel doormidden te splitsen. Nu, zo denk je, moeten er twee betrouwbare mensen met sleutelfragmenten fysiek aanwezig zijn om de sleutel te verzamelen en de kluis te openen. Dit betekent dat een dief twee fragmenten moet stelen, wat twee keer zo moeilijk is als het stelen van één sleutel. Je beseft echter al snel dat deze aanpak niet veel beter is dan slechts één sleutel, want als iemand de helft van de sleutel verliest, kan de volledige sleutel niet worden teruggevonden.

Het probleem kan worden opgelost met een reeks extra sleutels en sloten, maar deze aanpak vereist al snel много Sleutels en sloten. U besluit dat het ideale ontwerp zou zijn om de sleutel te splitsen, zodat de beveiliging niet volledig afhankelijk is van één persoon. U concludeert ook dat er een drempelwaarde moet zijn voor het aantal fragmenten, zodat bij verlies van één fragment (of als de persoon op vakantie gaat), de hele sleutel nog steeds bruikbaar is.

Hoe je een geheim deelt

Dit type sleutelbeheerschema werd in 1979 bedacht door Adi Shamir toen hij zijn werk publiceerde "Hoe deel je een geheim"In het artikel wordt kort de zogenaamde een drempelschema voor het efficiënt splitsen van een geheime waarde (bijvoorbeeld een cryptografische sleutel) in onderdelen. Dan, wanneer en alleen wanneer ten minste van onderdelen worden verzameld, het is gemakkelijk om het geheim te herstellen .

Vanuit een veiligheidsperspectief is een belangrijke eigenschap van dit schema dat een aanvaller absoluut niets mag leren, tenzij hij ten minste onderdelen. Zelfs de aanwezigheid onderdelen mogen geen informatie verstrekken. We noemen dit eigenschap semantische beveiliging.

Polynomiale interpolatie

Shamir's drempelregeling gebouwd rond het concept polynomiale interpolatieAls je dit concept nog niet kent, is het eigenlijk vrij eenvoudig. Sterker nog, als je ooit punten in een grafiek hebt getekend en ze vervolgens met lijnen of krommen hebt verbonden, heb je het al gebruikt!

Een onbeperkt aantal polynomen van graad 2 kan door twee punten worden getrokken. Om er slechts één te selecteren, is een derde punt nodig. Illustratie: Wikipedia

Laten we een polynoom van graad één beschouwen, Als je deze functie in een grafiek wilt weergeven, hoeveel punten heb je dan nodig? We weten dat het een lineaire functie is die een lijn vormt, dus er zijn minstens twee punten nodig. Beschouw vervolgens een polynomiale functie van graad twee, Het is een kwadratische functie, dus er zijn minstens drie punten nodig om hem te tekenen. Wat dacht je van een polynoom van graad drie? Minstens vier punten. En zo verder.

Het echt coole aan deze eigenschap is dat, gegeven de graad van de polynoomfunctie en op zijn minst punten, kunnen we extra punten afleiden voor deze polynoomfunctie. We noemen de extrapolatie van deze extra punten polynomiale interpolatie.

Een geheim verzinnen

Je hebt misschien al begrepen dat dit is waar Shamirs slimme plan om de hoek komt kijken. Laten we aannemen dat ons geheim - Is Wij kunnen transformeren naar een punt op de grafiek en kom met een polynoomfunctie met graad , wat aan dit punt voldoet. Bedenk dat zal onze drempelwaarde zijn voor de benodigde fragmenten. Als we de drempelwaarde dus op drie fragmenten instellen, moeten we een polynoomfunctie met graad twee kiezen.

Onze polynoom zal de vorm hebben Waar и — willekeurig geselecteerde positieve gehele getallen. We construeren simpelweg een polynoom met graad , waar is de vrije coëfficiënt  - dit is ons geheim , en elk van de volgende leden is een willekeurig geselecteerde positieve coëfficiënt. Als we terugkeren naar het oorspronkelijke voorbeeld en aannemen dat , dan krijgen we de functie .

In dit stadium kunnen we fragmenten genereren door ze te verbinden unieke gehele getallen in Waar (want dat is ons geheim). In dit voorbeeld willen we vier fragmenten verdelen met een drempelwaarde van drie, dus we genereren willekeurig punten en stuur een stip naar elk van de vier vertrouwde personen die de sleutel bewaren. We vertellen mensen ook dat , aangezien dit als openbare informatie wordt beschouwd en noodzakelijk is voor het herstel .

Het geheim herstellen

We hebben het concept van polynomiale interpolatie en de manier waarop dit ten grondslag ligt aan Shamir's drempelwaardeschema al besproken. . Wanneer drie van de vier beheerders de schulden willen herstellen , ze hoeven alleen maar te interpoleren met hun eigen unieke punten. Om dit te doen, kunnen ze hun punten definiëren en bereken de Lagrange-interpolatiepolynoom met behulp van de volgende formule. Als programmeren je meer ligt dan wiskunde, is pi in wezen de operator for, die alle resultaten vermenigvuldigt, en sigma is for, wat het allemaal samenvat.

bij We kunnen dit als volgt oplossen en zo onze oorspronkelijke polynoomfunctie terugkrijgen:

Omdat wij dat weten , herstel het wordt eenvoudig uitgevoerd:

Het gebruik van onveilige gehele getallenrekenkunde

Hoewel we Shamir's basisidee succesvol hebben toegepast , blijven we zitten met een probleem dat we tot nu toe hebben genegeerd. Onze polynoomfunctie gebruikt onveilige gehele getallenrekenkunde. Bedenk dat voor elk extra punt dat een aanvaller op de grafiek van onze functie krijgt, er minder mogelijkheden zijn voor andere punten. U kunt dit zelf zien wanneer u een toenemend aantal punten voor een polynoomfunctie plot met behulp van gehele getallenrekenkunde. Dit is contraproductief voor ons gestelde beveiligingsdoel, omdat een aanvaller absoluut niets zou moeten weten totdat hij ten minste... fragmenten.

Om te laten zien hoe zwak het rekenschema met gehele getallen is, moet je een scenario overwegen waarin de aanvaller twee punten heeft en kent openbare informatie die Uit deze informatie kan hij afleiden , gelijk aan twee, en vul de bekende waarden in de formule in и .

De aanvaller kan dan , na geteld te hebben :

Sinds we hebben gedefinieerd als willekeurig geselecteerde positieve gehele getallen zijn er een beperkt aantal mogelijke Met behulp van deze informatie kan een aanvaller afleiden , aangezien alles groter dan 5 voldoende is negatief. Dit blijkt waar te zijn, aangezien we hebben vastgesteld

De aanvaller kan vervolgens de mogelijke waarden berekenen , ter vervanging van в :

Met een beperkt aantal opties voor het wordt duidelijk hoe gemakkelijk het is om waarden te selecteren en te controleren Er zijn hier slechts vijf opties.

Het oplossen van het probleem met onveilige gehele getallenrekenkunde

Om deze kwetsbaarheid te elimineren, stelt Shamir voor om modulaire rekenkunde te gebruiken, ter vervanging van op Waar и — de verzameling van alle priemgetallen.

Laten we even snel kijken hoe modulaire rekenkunde werkt. Een klok met wijzers is een bekend concept. Het maakt gebruik van een klok die Zodra de uurwijzer de twaalf passeert, keert hij terug naar één. Een interessante eigenschap van dit systeem is dat we niet kunnen afleiden hoeveel omwentelingen de uurwijzer heeft gemaakt door simpelweg naar de klok te kijken. Als we echter weten dat de uurwijzer vier keer de twaalf heeft gepasseerd, kunnen we het aantal verstreken uren volledig bepalen met behulp van een eenvoudige formule. Waar  - dit is onze deler (hier ),  — dit is de coëfficiënt (hoe vaak de deler zonder rest in het oorspronkelijke getal gaat, hier ), en  — dit is de rest, die gewoonlijk wordt geretourneerd door de modulo-operator aan te roepen (hier ). Als we al deze waarden kennen, kunnen we de vergelijking voor oplossen , maar als we een coëfficiënt missen, kunnen we nooit de oorspronkelijke waarde herstellen.

We kunnen aantonen hoe dit de beveiliging van ons schema verbetert door het schema toe te passen op ons vorige voorbeeld en Onze nieuwe polynoomfunctie , en nieuwe punten Nu kunnen de sleutelbewaarders opnieuw polynomiale interpolatie gebruiken om onze functie te reconstrueren, alleen moeten de optel- en vermenigvuldigingsbewerkingen dit keer gepaard gaan met modulaire reductie. (bv ).

Stel dat de aanvaller, met behulp van dit nieuwe voorbeeld, twee van deze nieuwe punten heeft geleerd, en openbare informatie Deze keer leidt de aanvaller, op basis van alle informatie die hij heeft, de volgende functies af, waarbij  — de verzameling van alle positieve gehele getallen, en vertegenwoordigt de coëfficiënt van de module .

Nu vindt onze aanvaller het weer , na berekend te hebben :

Dan probeert hij zich opnieuw terug te trekken , ter vervanging van в :

Deze keer heeft hij een serieus probleem: de formule mist waarden. , и Omdat er oneindig veel combinaties van deze variabelen zijn, kan hij geen aanvullende informatie verkrijgen.

Beveiligingsoverwegingen

Shamirs geheime deelplan suggereert veiligheid vanuit het oogpunt van de informatietheorieDit betekent dat de berekeningen robuust zijn, zelfs tegen een aanvaller met onbeperkte rekenkracht. De methode kent echter nog steeds verschillende bekende problemen.

Het plan van Shamir creëert bijvoorbeeld geen gecontroleerde fragmenten, dat wil zeggen dat mensen vrij zijn om valse fragmenten te presenteren en zo de ontdekking van het juiste geheim te verstoren. Een vijandige fragmentbewaarder met voldoende informatie kan zelfs een ander fragment produceren door de informatie te veranderen. naar eigen goeddunken. Dit probleem wordt opgelost met behulp van verifieerbare geheimendelingsschema's, zoals het Feldman-plan.

Een ander probleem is dat de lengte van elk fragment gelijk is aan de lengte van het bijbehorende geheim, waardoor de lengte van het geheim gemakkelijk te bepalen is. Dit probleem is triviaal opgelost. vulling geheim met willekeurige getallen tot een vaste lengte.

Tot slot is het belangrijk om te weten dat onze beveiligingszorgen verder kunnen reiken dan het ontwerp zelf. Bij echte cryptografische toepassingen bestaat vaak de dreiging van side-channel-aanvallen, waarbij een aanvaller probeert nuttige informatie te extraheren uit de runtime van de applicatie, caching, crashes, enz. Als dit een probleem is, moet tijdens het ontwerp zorgvuldig worden nagedacht over het gebruik van beschermende maatregelen zoals constant-time functies en opzoekacties, het voorkomen dat geheugen op schijf wordt opgeslagen, en een aantal andere zaken die buiten het bestek van dit artikel vallen.

Демо

Op deze pagina Er is een interactieve demonstratie van het Shamir-geheimenuitwisselingsprogramma. De demonstratie is gebaseerd op de bibliotheek. ssss-js, dat zelf een JavaScript-poort is van een populair programma ssssHoud er rekening mee dat de berekening van grote waarden , и Het kan even duren.

Bron: www.habr.com