Laten we een scenario bekijken waarin we de beveiliging van een bankkluis moeten waarborgen. Deze wordt als volledig ontoegankelijk beschouwd zonder de sleutel, die je op je eerste werkdag ontvangt. Jouw doel is om de sleutel veilig te bewaren.

Stel je voor dat je hebt besloten de sleutel altijd bij je te houden en toegang tot de kluis te geven wanneer dat nodig is. Maar je zult al snel merken dat deze oplossing in de praktijk niet goed opschaalt, omdat je fysiek aanwezig moet zijn om de kluis te openen. Wat als je bijvoorbeeld op vakantie gaat? Bovendien is er nog een verontrustende vraag: wat als je de enige sleutel verliest?

Met het idee van vakantie in gedachten besluit je een kopie van de sleutel te maken en deze aan een andere medewerker te vertrouwen. Echter, je beseft dat dit ook niet ideaal is. Door het aantal sleutels te verdubbelen, heb je ook de kansen op diefstal verdubbeld.

In wanhoop vernietig je de kopie en besluit je de originele sleutel in tweeën te splitsen. Nu denk je dat twee vertrouwde personen met delen van de sleutel fysiek aanwezig moeten zijn om de sleutel samen te voegen en de kluis te openen. Dit betekent dat de dief twee delen moet stelen, wat dubbel zo moeilijk is als het stelen van één sleutel. Maar al snel besef je dat deze aanpak niet veel beter is dan slechts één sleutel, omdat als iemand de helft van de sleutel verliest, de volledige sleutel niet kan worden hersteld.

Het probleem kan worden opgelost met een reeks extra sleutels en sloten, maar deze aanpak vereist snel veel sleutels en sloten. Je besluit dat in een ideale regeling de sleutel moet worden verdeeld, zodat de beveiliging niet volledig op één persoon steunt. Je komt ook tot de conclusie dat er een bepaalde drempel moet zijn voor het aantal fragmenten, zodat bij verlies van één fragment (of als iemand op vakantie is) de hele sleutel functioneel blijft.

Hoe een geheim te splitsen

Over dit type sleutelschema dacht Adi Shamir in 1979, toen hij zijn werk publiceerde ‘Hoe een geheim te splitsen’. In het artikel wordt kort uitgelegd wat de zogenaamde drempelstructuur is voor effectieve verdeling van een geheim (bijvoorbeeld een cryptografische sleutel) in delen. Alleen wanneer en als ten minste uit delen zijn verzameld, kan het geheim gemakkelijk worden hersteld. .

Vanuit beveiligingsperspectief is een belangrijk kenmerk van dit schema dat een aanvaller absoluut niets moet weten, tenzij hij tenminste delen heeft. Zelfs de aanwezigheid van delen mag geen informatie geven. Dit kenmerk noemen we semantieke veiligheid.

Polynomiale interpolatie

Het drempelschema van Shamir is opgebouwd rond het concept van polynomiale interpolatie. Als je niet bekend bent met dit concept, is het eigenlijk behoorlijk eenvoudig. In feite, als je ooit punten op een grafiek hebt getekend en deze met lijnen of krommen hebt verbonden, heb je het al gebruikt!

Door twee punten kunnen oneindig veel polynomen van graad 2 worden getekend. Om er één uit te kiezen, is een derde punt nodig. Illustratie: KB van Fortinet

Laten we een polynoom van graad één overwegen, . Als je deze functie op een grafiek wilt tekenen, hoeveel punten heb je dan nodig? Nou, we weten dat dit een lineaire functie is die een lijn vormt, dus je hebt minstens twee punten nodig. Laten we vervolgens een polynomiale functie van graad twee beschouwen, . Dit is een kwadratische functie, dus om de grafiek te tekenen, zijn minstens drie punten vereist. Hoe zit het met een veelterm van graad drie? Ten minste vier punten. En zo verder.

Het echt coole aan deze eigenschap is dat, gezien de graad van de polynomiale functie en minstens punten, we aanvullende punten voor deze polynomiale functie kunnen afleiden. Het extrapoleren van deze aanvullende punten noemen we polynomiale interpolatie.

Het samenstellen van een geheim

Misschien heb je al begrepen dat hier het slimme Shamir-schema in het spel komt. Laten we aannemen dat ons geheim is . We kunnen omzetten in een punt op de grafiek en een polynomiale functie van graad , bedenken die aan dit punt voldoet. Laten we herinneren dat onze drempel zal zijn voor de vereiste fracties, dus als we de drempel op drie fracties stellen, moeten we een polynomiale functie van graad twee kiezen.

Onze polynoom zal de vorm hebben van , waar en — willekeurig gekozen positieve gehele getallen. We bouwen gewoon een polynoom van graad , waarbij de constante term  ons geheim is , en aan elke van de volgende leden hebben een willekeurig gekozen positieve coëfficiënt. Als we terugkeren naar het oorspronkelijke voorbeeld en aannemen dat , dan krijgen we de functie .

Op dit moment kunnen we fragmenten genereren door unieke gehele getallen in , waar (omdat dit ons geheim is). In dit voorbeeld willen we vier fragmenten uitdelen met een drempel van drie, dus genereren we willekeurig punten en sturen we elk van de vier vertrouwde mensen, de sleutelhouders, één punt. We vertellen de mensen ook dat , omdat dit als openbare informatie wordt beschouwd en nodig is voor het herstel. .

Herstellen van het geheim

We hebben al het concept van polynomiale interpolatie besproken en dat dit de basis vormt voor Shamir's drempelschema. . Wanneer drie van de vier vertrouwde personen het geheim willen herstellen, , hoeven ze alleen maar te interpoleren met hun unieke punten. Hiervoor kunnen ze hun punten definiëren en de interpolerende Lagrange-polynoom berekenen met behulp van de volgende formule. Als programmeren voor jou duidelijker is dan wiskunde, dan is pi in wezen de operator voor, die alle resultaten vermenigvuldigt, en sigma is de voor, die alles optelt.

Bij we kunnen dit op de volgende manier oplossen en onze oorspronkelijke polynoomfunctie teruggeven:

Aangezien we weten dat , wordt het herstel simpelweg uitgevoerd:

Gebruik van onveilige gehele rekensom

Hoewel we het basisidee van Shamir met succes hebben toegepast, , hebben we nog een probleem dat we tot nu toe genegeerd hebben. Onze polynoomfunctie gebruikt onveilige gehele rekenkunde. Houd er rekening mee dat voor elk extra punt dat een aanvaller ontvangt op de grafiek van onze functie, er minder mogelijkheden overblijven voor andere punten. Je kunt dit met eigen ogen zien wanneer je de grafiek bouwt met een toenemend aantal punten voor de polynoomfunctie met behulp van gehele rekenkunde. Dit is contradictorisch voor ons geclaimde beveiligingsdoel, omdat een aanvaller absoluut niets mag weten, totdat ze ten minste fragmenten hebben.

Om te demonstreren hoe zwak de schema met gehele rekenkunde is, beschouwen we een scenario waarin een aanvaller twee punten heeft gekregen en de openbare informatie kent dat . Uit deze informatie kan hij afleiden , gelijk aan twee, en de bekende waarden in de formule aansluiten en .

Vervolgens kan de aanvaller vinden , door te berekenen :

Omdat we hebben gedefinieerd als willekeurig gekozen positieve gehele getallen, zijn er een beperkt aantal mogelijke . Met behulp van deze informatie kan de aanvaller afleiden , aangezien alles wat groter is dan 5 ervoor zorgt dat negatief is. Dit blijkt waar te zijn, omdat we hebben gedefinieerd

Vervolgens kan de aanvaller mogelijke waarden berekenen , door te vervangen in :

Met een beperkte set opties voor wordt duidelijk hoe gemakkelijk het is om waarden te raden en te verifiëren . Hier zijn slechts vijf opties.

Het probleem met onveilige gehele getal rekenkunde oplossen

Om deze kwetsbaarheid te verhelpen, stelt Shamir voor om modulaire rekenkunde te gebruiken door en een werkende opdracht krijgen. , waar en — de verzameling van alle priemgetallen.

Laten we snel herinneren hoe modulaire rekenkunde werkt. Klokken met wijzers zijn een al bekende concept. Ze gebruiken klokken die . Zodra de uurwijzer voorbij twaalf gaat, keert deze terug naar één. Een interessant kenmerk van dit systeem is dat we door simpelweg naar de klok te kijken, niet kunnen afleiden hoeveel omwentelingen de uurwijzer heeft gemaakt. Maar als we weten dat de uurwijzer vier keer voorbij 12 is gegaan, kunnen we het aantal verstreken uren volledig bepalen met een eenvoudige formule , waar  — dit is onze deler (hier ),  — dit is de coefficient (hoe vaak de deler zonder rest in het oorspronkelijke getal gaat, hier ), terwijl  — dit is de rest, die doorgaans de aanroep van de modulusoperator retourneert (hier ). Het kennen van al deze waarden stelt ons in staat de vergelijking op te lossen voor , maar als we de coefficient overslaan, kunnen we de oorspronkelijke waarde nooit herstellen.

We kunnen laten zien hoe dit de veiligheid van ons schema verbetert door het schema toe te passen op ons eerdere voorbeeld en gebruikmakend van . Onze nieuwe polynomiale functie , en de nieuwe punten . Nu kunnen de sleutelhouders opnieuw polynomiale interpolatie gebruiken om onze functie te herstellen, maar deze keer moeten de optellingen en vermenigvuldigingen gepaard gaan met reductie modulo (bijv. ).

Stel met dit nieuwe voorbeeld dat de aanvaller twee van deze nieuwe punten heeft geleerd, , en openbare informatie . Deze keer geeft de aanvaller, op basis van alle beschikbare informatie, de volgende functies weer, waarbij  — de verzameling van alle positieve gehele getallen, en de modulus-coëfficiënt vertegenwoordigt. .

Onze aanvaller vindt nu opnieuw , door te berekenen :

Vervolgens probeert hij opnieuw te genereren , door te vervangen in :

Deze keer heeft hij een serieus probleem. In de formule ontbreken waarden , en . Aangezien er een oneindig aantal combinaties van deze variabelen is, kan hij geen aanvullende informatie verkrijgen.

Veiligheidsoverwegingen

Shamir's geheimdeling-schema biedt beveiliging vanuit het perspectief van informatie-theorie.. Dit betekent dat de wiskunde bestand is tegen een aanvaller met onbeperkte rekencapaciteit. Het schema heeft echter nog steeds enkele bekende problemen.

Bijvoorbeeld, het Shamir-schema creëert geen verifieerbare segmenten, wat betekent dat mensen eenvoudig vervalste segmenten kunnen indienen en de reconstructie van het juiste geheim kunnen verstoren. Een vijandige fragmentbewaker met voldoende informatie kan zelfs een ander segment genereren door naar eigen inzicht te veranderen. Dit probleem wordt opgelost met verifieerbare geheimdeling-schema's, zoals het Feldman-schema.

Een ander probleem is dat de lengte van elk segment gelijk is aan de lengte van het bijbehorende geheim, waardoor de lengte van het geheim gemakkelijk te bepalen is. Dit probleem wordt opgelost door middel van triviale opvulling van het geheim met willekeurige getallen tot een vaste lengte.

Tot slot is het belangrijk op te merken dat onze zorgen over veiligheid verder kunnen gaan dan het schema zelf. Voor echte cryptografische toepassingen is er vaak een bedreiging van aanvallen via zij-kanalen, waarbij een aanvaller probeert nuttige informatie te extraheren uit de uitvoeringstijd van de applicatie, caching, storingen, enzovoort. Als dit een zorg is, moeten bij de ontwikkeling beschermende maatregelen, zoals functies en constante zoektijden, worden overwogen, om te voorkomen dat het geheugen op de schijf wordt opgeslagen en om een aantal andere zaken te overwegen die buiten dit artikel vallen.

Demo

Op deze pagina er is een interactieve demonstratie van het Shamir's geheimdeling-schema. De demonstratie is gemaakt op basis van de bibliotheek ssss-js, die op zichzelf een JavaScript-port is van een populaire applicatie ssssHoud er rekening mee dat het berekenen van grote waarden , en enkele tijd kan duren.

Bron: habr.com