Wikisage is op 1 na de grootste internet-encyclopedie in het Nederlands. Iedereen kan de hier verzamelde kennis gratis gebruiken, zonder storende advertenties. De Koninklijke Bibliotheek van Nederland heeft Wikisage in 2018 aangemerkt als digitaal erfgoed.
- Wilt u meehelpen om Wikisage te laten groeien? Maak dan een account aan. U bent van harte welkom. Zie: Portaal:Gebruikers.
- Bent u blij met Wikisage, of wilt u juist meer? Dan stellen we een bescheiden donatie om de kosten te bestrijden zeer op prijs. Zie: Portaal:Donaties.
Shamirs Secret Sharing
Shamirs Secret Sharing is een cryptografisch algoritme van het type secret sharing, dat ontworpen is door de Israëlische informaticus Adi Shamir. Met dit algoritme kan een geheime sleutel S (= secret), die bijvoorbeeld toegang geeft tot een kluis van een bedrijf, omgevormd worden naar n deelsleutels, die verdeeld worden (= sharing) over n bedrijfsleiders. Om de kluis te openen zijn niet alle n deelsleutels nodig. Als één of meer bedrijfsleiders sterven, op vakantie zijn of verdere medewerking weigeren, kan de volledige geheime sleutel S toch berekend worden zodat de kluis kan geopend worden.
Hieronder een schematische voorstelling, waarbij de geheime sleutel over n=5 bedrijfsleiders verdeeld wordt en waarbij achteraf k=3 bedrijfsleiders hun deelsleutel aanbieden.
Versleutelen van de geheime sleutel S naar n punten
Bij het versleutelen van de geheime sleutel S wordt een veeltermfunctie gebruikt. Wij nemen als voorbeeld een veeltermfunctie van de 2e graad, die grafisch kan voorgesteld worden door een parabool. Die functie heeft 3 parameters (a0 , a1 en a2 ≠ 0) in de verzameling van natuurlijke getallen ( 0, 1, 2, 3, 4, 5 ...) en wordt ondubbelzinnig bepaald door 3 punten. Deze functie kan als volgt genoteerd worden:
- f(x) = a0 + a1 x + a2 x2
De eerste parameter a0 kiezen we gelijk aan onze geheime sleutel S, die we de waarde "1234" geven om de zaak te concretiseren:
- a0 = geheime sleutel S
Voor de twee andere parameters berekenen we twee random natuurlijke getallen, bijvoorbeeld 3105 en 771, zodat onze veeltermfunctie er als volgt uit ziet:
- f(x) = 1234 + 3105 x + 771 x2
Die twee parameters moeten random bepaald worden en geheim blijven. Ook de bedrijfsleiders mogen die parameters niet kennen. Een bedrijfsleider, die deze twee parameters zou kennen, zou de derde parameter (namelijk onze geheime sleutel) kunnen berekenen met zijn eigen deelsleutel (zie verder).
We berekenen nu n=5 functiewaarden voor de getallen 1, 2, 3, 4 en 5 met het functievoorschrift:
En we verkrijgen bijgevolg n=5 verschillende punten van de parabool:
- (1,5110), (2,10528), (3,17488), (4,25990) en (5,36034)
Deze punten zijn de n=5 deelsleutels, die we verdelen over de 5 bedrijfsleiders.
Ontcijferen van de geheime sleutel S uit k punten
Veronderstel dat we de kluis willen openen. We roepen de bedrijfsleiders samen. Zodra er k=3 (of meer) bedrijfsleiders aanwezig zijn, kunnen we de veeltermfunctie van de 2e graad reconstrueren (met de 3 deelsleutels van de aanwezige bedrijfsleiders) door de 3 parameters (a0 , a1 en a2) van de veeltermfunctie te berekenen. Deze berekening kan op vele manieren gebeuren. We demonstreren de berekening met de techniek van de Lagrange-polynoom en we veronderstellen dat de 2e, 4e en 5e bedrijfsleider hun deelsleutel aanbieden:
De veeltermfunctie is perfect gereconstrueerd en de geheime sleutel verschijnt als constante term a0 in het functievoorschrift.
(k,n) Treshold Scheme
Dit systeem Shamirs Secret Sharing wordt in het Engels (k,n) treshold scheme of kortweg treshold genoemd, wat we naar drempelsysteem of grenssysteem kunnen vertalen. De drempel of grens is het getal k, dat verwijst naar het minimum aantal deelsleutels dat nodig is om de geheime sleutel te berekenen. Het getal n is het totaal aantal deelsleutels dat gecreëerd wordt. Daarbij moeten we rekening houden met de voorwaarde: n ≥ k.
Ons voorbeeld met 5 bedrijfsleiders beschrijft een (3,5) treshold scheme. Er zijn k=3 deelsleutels nodig om de geheime sleutel te berekenen, terwijl er n=5 deelsleutels gecreëerd werden.
Volgende voorwaarden werden door Adi Shamir voorop gesteld om een (k,n) treshold scheme te realiseren:
- Als k of meer van de n deelsleutels gekend zijn, kan de geheime sleutel op een eenvoudige en vlugge manier berekend worden.
- Als k-1 of minder van de n deelsleutels gekend zijn, is de berekening van de geheime sleutel onmogelijk.
In ons voorbeeld (met k=3 en n=5) kan de geheime sleutel berekend worden als er 3, 4 of 5 deelsleutels gekend zijn. Die berekening is onmogelijk als er slechts 1 of 2 deelsleutels gekend zijn.
Probleem bij gebruik van natuurlijke getallen
Bij gebruik van natuurlijke getallen voor de parameters a0 , a1 en a2 is het systeem Shamirs Secret Sharing niet waterdicht. Een bedrijfsleider kan het aantal mogelijkheden voor de parameter a0 en bijgevolg ook het aantal mogelijkheden voor de geheime sleutel beperken.
In ons voorbeeld kan de bedrijfsleider met sleutel (1,5110) achterhalen dat de geheime sleutel S kleiner is dan 5110, want:
- f(x) = a0 + a1 x + a2 x2
- → f(1) = a0 + a1 (1) + a2 (1)2
- → 5110 = a0 + a1 + a2
- → 5110 - a1 - a2 = a0 , a1 ≥ 0 , a2 › 0
- → 5110 > a0
- → a0 < 5110
De eerste bedrijfsleider kan nu alle mogelijkheden 0, 1, 2, 3 ... 5108, 5109 als geheime sleutel uitproberen.
Ook de andere bedrijfsleiders kunnen op een gelijkaardige manier informatie achterhalen over de geheime sleutel S. Als 2 bedrijfsleiders samenwerken kunnen ze het aantal mogelijkheden nog verminderen. Het systeem is dus niet betrouwbaar.
Oplossing van het probleem via "modulair rekenen"
Om de geheimhouding te versterken wordt er gebruikt gemaakt van modulair rekenen. Er wordt niet meer gewerkt in de verzameling natuurlijke getallen maar in een eindig veld GL(q) bepaald door een groot priemgetal q (groter dan het getal n).
Dat eindig veld GL(q) = { 0, 1, 2, 3 ... q-2, q-1} is een eindige deelverzameling van de oneindige verzameling van natuurlijke getallen.
In ons voorbeeld kan de eerste bedrijfsleider met sleutel (1,5110) niet meer besluiten dat de geheime sleutel kleiner is dan 5110. We geven een verklaring via modulair rekenen met het priemgetal q = 100003. (In de praktijk wordt er gewerkt met een enorm groot priemgetal om de geheimhouding te versterken.)
In het eindig veld GL(q) kan de eerste bedrijfsleider het volgende besluiten:
- a0 = (5110 - a1 - a2) mod 100003
Dat betekent weer (zoals hoger vermeld) dat alle getallen 0, 1, 2, 3 ... 5108, 5109 de geheime sleutel kunnen zijn. Hieronder tonen we dat 5108 en 5109 de geheime sleutel kunnen zijn:
- 5108 = (5110 - 1 - 1) mod 100003
- 5109 = (5110 - 0 - 1) mod 100003
Maar ook 5110 en grotere getallen kunnen de geheime sleutel zijn. Als we de waarde 100003 verdelen over de parameters a1 en a2, dan wordt die waarde 100003 achteraf weer uit de uitdrukking verwijderd, omdat we modulair rekenen (modulo 100003). Op die manier besluiten we dat ook 5110, 5111, 5112 ... de geheime sleutel kunnen zijn, want de volgende vergelijkingen zijn correct:
- 5110 = (5110 - 100002 - 1) mod 100003
- 5111 = (5110 - 100001 - 1) mod 100003
- 5112 = (5110 - 100000 - 1) mod 100003
Men kan narekenen dat er 100003 geheime sleutels mogelijk zijn voor de eerste bedrijfsleider. Ook de andere bedrijfsleiders kunnen het aantal mogelijkheden niet beperken, zelfs niet als 2 bedrijfsleiders hun sleutels samenbrengen. Zodra 3 (of meer) bedrijfsleiders hun sleutels samenbrengen, kan de geheime sleutel wel berekend worden.
Via het modulair rekenen - met een enorm groot priemgetal q - wordt het kraken van de geheime sleutel S quasi onmogelijk gemaakt, als slechts k-1 of minder deelsleutels gekend zijn.
