Overweeg een scenario waarin u een bankkluis moet beveiligen. Het wordt als absoluut onneembaar beschouwd zonder sleutel, die u op de allereerste werkdag krijgt. Jouw doel is om de sleutel veilig op te bergen.

Stel dat u besluit de sleutel altijd bij u te houden, zodat u indien nodig toegang heeft tot de opslagruimte. Maar u zult snel merken dat een dergelijke oplossing in de praktijk niet goed opschaalt, omdat uw fysieke aanwezigheid vereist is elke keer dat u de opslag opent. Hoe zit het met de vakantie die je was beloofd? Bovendien is de vraag nog beangstigender: 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 begrijpt echter dat dit ook niet ideaal is. Door het aantal sleutels te verdubbelen, verdubbelt u ook de kans op sleuteldiefstal.

Wanhopig vernietig je het duplicaat en besluit je de originele sleutel in tweeën te splitsen. Nu zou je denken dat er twee vertrouwde mensen met sleutelfragmenten fysiek aanwezig zouden moeten zijn om de sleutel op te halen en de kluis te openen. Dit betekent dat een dief twee stukken moet stelen, wat twee keer zo moeilijk is als het stelen van één sleutel. Je komt er echter al snel achter dat dit schema niet veel beter is dan slechts één sleutel, want als iemand een halve sleutel verliest, kan de volledige sleutel niet worden teruggevorderd.

Het probleem kan worden opgelost met een reeks extra sleutels en sloten, maar deze aanpak zal snel nodig zijn много sleutels en sloten. U besluit dat het ideaal zou zijn om de sleutel te delen, zodat de beveiliging niet volledig afhankelijk is van één persoon. Je concludeert ook dat er een bepaalde drempel moet zijn voor het aantal fragmenten, zodat als één fragment verloren gaat (of als iemand op vakantie gaat), de hele sleutel functioneel blijft.

Hoe een geheim te delen

Dit soort sleutelbeheerschema werd in 1979 door Adi Shamir bedacht toen hij zijn werk publiceerde "Hoe een geheim te delen". Het artikel legt kort de zogenaamde uit drempelschema voor het efficiënt verdelen van een geheime waarde (zoals een cryptografische sleutel). onderdelen. Dan, wanneer en alleen wanneer tenminste van onderdelen zijn gemonteerd, kunt u het geheim eenvoudig herstellen .

Vanuit veiligheidsoogpunt is een belangrijke eigenschap van dit plan dat de aanvaller absoluut niets mag weten, tenzij hij tenminste onderdelen. Zelfs de aanwezigheid onderdelen mogen geen informatie verschaffen. Dit noemen wij eigendom semantische veiligheid.

Polynomiale interpolatie

Shamir-drempelschema gebouwd rond het concept polynomiale interpolatie. Als u niet bekend bent met dit concept, is het eigenlijk vrij eenvoudig. Als je ooit punten in een grafiek hebt getekend en deze vervolgens met lijnen of curven hebt verbonden, heb je deze functie al gebruikt!

Door twee punten kun je een onbeperkt aantal polynomen van graad 2 tekenen. Om er de enige uit te kiezen, heb je een derde punt nodig. Illustratie: Wikipedia

Beschouw een polynoom met graad één, . Hoeveel punten heb je nodig als je deze functie in een grafiek wilt weergeven? Welnu, we weten dat dit een lineaire functie is die een lijn vormt en dus minstens twee punten nodig heeft. Beschouw vervolgens een polynoomfunctie met graad twee, . Dit is een kwadratische functie, dus er zijn minimaal drie punten nodig om de grafiek te plotten. Wat dacht je van een polynoom met graad drie? Minimaal vier punten. Enzovoort.

Het leuke aan deze eigenschap is dat, gezien de mate van de polynomiale functie, 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 je misschien al gerealiseerd dat dit is waar het slimme plan van Shamir in het spel komt. Laten we ons geheim zeggen - Is . Wij kunnen draaien naar een punt op de grafiek en bedenk een polynomiale functie met graad , wat aan dit punt voldoet. Laten we u daaraan herinneren zal onze drempel van vereiste fragmenten zijn, dus als we de drempel instellen op drie fragmenten, moeten we een polynoomfunctie met graad twee kiezen.

Onze polynoom heeft de vorm Waar и — willekeurig geselecteerde positieve gehele getallen. We construeren alleen maar een polynoom met graad , waarbij de vrije coëfficiënt  - Dit is ons geheim , en voor elk van de volgende Er is sprake van een willekeurig gekozen positieve coëfficiënt. Als we terugkeren naar het oorspronkelijke voorbeeld en dat aannemen , dan krijgen we de functie .

Op dit punt kunnen we fragmenten genereren door verbinding te maken unieke gehele getallen in Waar (omdat het ons geheim is). In dit voorbeeld willen we vier fragmenten verdelen met een drempelwaarde van drie, dus genereren we willekeurig punten en stuur één punt naar elk van de vier vertrouwde mensen, de bewaarders van de sleutel. Dat laten we mensen ook weten , aangezien dit als openbare informatie wordt beschouwd en noodzakelijk is voor herstel .

Het geheim terugvinden

We hebben het concept van polynomiale interpolatie al besproken en hoe dit ten grondslag ligt aan het drempelschema van Shamir . Wanneer drie van de vier curatoren willen herstellen , hoeven ze alleen maar te interpoleren met zijn eigen unieke punten. Om dit te doen, kunnen ze hun punten bepalen en bereken het Lagrange-interpolatiepolynoom met behulp van de volgende formule. Als programmeren voor jou duidelijker is dan wiskunde, dan is pi in wezen een operator for, die alle resultaten vermenigvuldigt, en sigma is for, wat alles optelt.

bij we kunnen het als volgt oplossen en onze oorspronkelijke polynoomfunctie retourneren:

Omdat wij dat weten , herstel eenvoudig gedaan:

Onveilige rekenkunde met gehele getallen gebruiken

Hoewel we het basisidee van Shamir met succes hebben toegepast zitten we met een probleem dat we tot nu toe hebben genegeerd. Onze polynomiale functie maakt gebruik van onveilige rekenkunde met gehele getallen. Merk op dat voor elk extra punt dat een aanvaller verkrijgt op de grafiek van onze functie, er minder mogelijkheden zijn voor andere punten. U kunt dit met eigen ogen zien wanneer u een toenemend aantal punten voor een polynoomfunctie plot met behulp van gehele getallen. Dit is contraproductief voor ons gestelde beveiligingsdoel, omdat de aanvaller absoluut niets zou moeten weten totdat hij dat tenminste heeft gedaan fragmenten.

Om aan te tonen hoe zwak het rekenkundige circuit met gehele getallen is, kunnen we een scenario overwegen waarin een aanvaller twee punten heeft behaald en weet dat publieke informatie . Uit deze informatie kan hij afleiden , gelijk aan twee, en vul de bekende waarden in de formule in и .

De aanvaller kan dan vinden , tellen :

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

De aanvaller kan vervolgens de mogelijke waarden berekenen vervangen в :

Met beperkte mogelijkheden voor het wordt duidelijk hoe eenvoudig het is om de waarden te selecteren en te controleren . Er zijn hier slechts vijf opties.

Het probleem oplossen met onveilige berekeningen met gehele getallen

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

Laten we snel onthouden hoe modulaire rekenkunde werkt. Een klok met wijzers is een bekend concept. Ze gebruikt namelijk een horloge . Zodra de uurwijzer twaalf passeert, keert deze terug naar één. Een interessante eigenschap van dit systeem is dat we door simpelweg naar de klok te kijken niet kunnen afleiden hoeveel omwentelingen de uurwijzer heeft gemaakt. Als we echter weten dat de urenwijzer vier keer de 12 is gepasseerd, kunnen we het aantal verstreken uren volledig bepalen met behulp van een eenvoudige formule Waar  is onze deler (hier ),  is de coëfficiënt (hoe vaak de deler hier zonder rest in het oorspronkelijke getal past). ), en  is de rest, die gewoonlijk een modulo-operatoroproep retourneert (hier ). Als we al deze waarden kennen, kunnen we de vergelijking oplossen , maar als we de coëfficiënt missen, zullen we nooit de oorspronkelijke waarde kunnen herstellen.

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

Laten we met dit nieuwe voorbeeld aannemen dat de aanvaller twee van deze nieuwe punten heeft geleerd: en openbare informatie . Deze keer voert de aanvaller, op basis van alle informatie die hij heeft, de volgende functies uit, waar  is de verzameling van alle positieve gehele getallen, en vertegenwoordigt de moduluscoëfficiënt .

Nu vindt onze aanvaller opnieuw , berekenen :

Dan probeert hij het opnieuw vervangen в :

Deze keer heeft hij een ernstig probleem. Ontbrekende waarden in formule , и . Omdat er een oneindig aantal combinaties van deze variabelen zijn, kan hij geen aanvullende informatie verkrijgen.

Beveiligingsoverwegingen

Shamirs geheime deelplan suggereert dit veiligheid vanuit het perspectief van de informatietheorie. Dit betekent dat de wiskunde zelfs bestand is tegen een aanvaller met onbeperkte rekenkracht. Het circuit bevat echter nog steeds verschillende bekende problemen.

Het plan van Shamir creëert bijvoorbeeld niet fragmenten te controleren, dat wil zeggen dat mensen vrijelijk nepfragmenten kunnen presenteren en zich kunnen bemoeien met het terugvinden van het juiste geheim. Een vijandige fragmentbewaarder met voldoende informatie zou zelfs een ander fragment kunnen produceren door te veranderen naar eigen inzicht. Dit probleem is opgelost met behulp van verifieerbare plannen voor het delen van geheimen, zoals het plan van Feldman.

Een ander probleem is dat de lengte van elk fragment gelijk is aan de lengte van het overeenkomstige geheim, waardoor de lengte van het geheim eenvoudig te bepalen is. Dit probleem kan worden opgelost door triviaal opvulling geheim met willekeurige getallen tot een vaste lengte.

Ten slotte is het belangrijk op te merken dat onze veiligheidsproblemen verder kunnen reiken dan het ontwerp zelf. Voor cryptografische toepassingen in de echte wereld bestaat vaak de dreiging van zijkanaalaanvallen waarbij een aanvaller nuttige informatie probeert te extraheren uit de uitvoeringstijd van toepassingen, caching, crashes, enz. Als dit een probleem is, moet tijdens de ontwikkeling zorgvuldig worden nagedacht over het gebruik van beschermende maatregelen zoals functies en constante lookups, waardoor wordt voorkomen dat geheugen op schijf wordt opgeslagen, en een aantal andere overwegingen die buiten het bestek van dit artikel vallen.

Демо

Op deze pagina Er is een interactieve demonstratie van Shamirs geheime deelplan. Demonstratie op basis van de bibliotheek ssss-js, dat zelf een JavaScript-poort is van het populaire programma ssss. Merk op dat het berekenen van grote waarden , и kan even duren.

Bron: www.habr.com