Betruecht e Szenario wou Dir e Bankgewelt muss sécheren. Et gëtt als absolut impregnable ugesinn ouni Schlëssel, deen Dir op den éischten Dag vun der Aarbecht kritt. Äert Zil ass de Schlëssel sécher ze späicheren.

Loosst eis soen datt Dir décidéiert de Schlëssel zu all Moment ze halen, fir Zougang zu der Späichere wéi néideg. Awer Dir wäert séier feststellen datt sou eng Léisung an der Praxis net gutt skaléiert, well Är kierperlech Präsenz all Kéier wann Dir d'Späichere opmaacht, erfuerderlech ass. Wat iwwer d'Vakanz, déi Dir versprach gouf? Zousätzlech ass d'Fro nach méi erschreckend: wat wann Dir Ären eenzege Schlëssel verluer hutt?

Mat Ärer Vakanz am Kapp, decidéiert Dir eng Kopie vum Schlëssel ze maachen an en aneren Employé uvertraut. Wéi och ëmmer, Dir verstitt datt dëst och net ideal ass. Andeems Dir d'Zuel vun de Schlësselen duebel, Dir duebel och d'Chancen vun Schlëssel Vol.

An der Verzweiflung zerstéiert Dir den Duplikat an entscheet den ursprénglechen Schlëssel an der Halschent ze splécken. Elo géift Dir mengen datt zwee vertrauenswürdege Leit mat Schlësselfragmenter kierperlech präsent musse sinn fir de Schlëssel ze sammelen an de Vault opzemaachen. Dëst bedeit datt en Déif muss zwee Stécker klauen, wat duebel sou schwéier ass wéi ee Schlëssel ze klauen. Wéi och ëmmer, Dir mierkt séier datt dëst Schema net vill besser ass wéi just ee Schlëssel, well wann een en hallwe Schlëssel verléiert, kann de ganze Schlëssel net erëmfonnt ginn.

De Problem kann mat enger Serie vun zousätzlech Schlësselen a Schleisen geléist ginn, mä dës Approche wäert séier verlaangen много Schlësselen a Schleisen. Dir entscheet, datt den ideale Design wier de Schlëssel ze deelen, sou datt d'Sécherheet net ganz op eng Persoun hänkt. Dir schléisst och datt et eng Schwelle fir d'Zuel vun de Fragmenter muss sinn, sou datt wann ee Fragment verluer geet (oder wann eng Persoun an d'Vakanz geet), bleift de ganze Schlëssel funktionell.

Wéi een e Geheimnis deelt

Dës Aart vu Schlësselmanagementschema gouf vum Adi Shamir am Joer 1979 geduecht wéi hien seng Aarbecht publizéiert huet "Wéi e Geheimnis deelen". Den Artikel erkläert kuerz de sougenannte Schwellschema fir effizient e geheime Wäert opzedeelen (wéi e kryptografesche Schlëssel) an Deeler. Dann, wéini a just wann op d'mannst aus Deeler sinn zesummegesat, Dir kënnt d'Geheimnis einfach restauréieren .

Aus Sécherheetssiicht ass e wichtege Besoin vun dësem Schema datt den Ugräifer absolut näischt wësse soll ausser hien huet op d'mannst Deeler. Och d'Präsenz Deeler sollen keng Informatioun ubidden. Mir nennen dës Immobilie semantesch Sécherheet.

Polynomial Interpolatioun

Shamir Schwell Schema ronderëm d'Konzept gebaut polynomial Interpolatioun. Wann Dir net mat dësem Konzept vertraut ass, ass et eigentlech ganz einfach. Tatsächlech, wann Dir jeemools Punkten op enger Grafik gezeechent hutt an se dann mat Linnen oder Kéiren verbonnen hutt, hutt Dir et scho benotzt!

Duerch zwee Punkte kënnt Dir eng onlimitéiert Zuel vu Polynome vum Grad zéien 2. Fir deen eenzegen aus hinnen ze wielen, brauch Dir en drëtte Punkt. Illustratioun: Wikipedia

Betruecht e Polynom mat Grad een, . Wann Dir dës Funktioun op enger Grafik plot wëllt, wéivill Punkte braucht Dir? Gutt, mir wëssen datt dëst eng linear Funktioun ass déi eng Linn bildt an dofir brauch se op d'mannst zwee Punkten. Als nächst, betruecht eng polynomial Funktioun mat Grad zwee, . Dëst ass eng quadratesch Funktioun, sou datt op d'mannst dräi Punkten erfuerderlech sinn fir d'Grafik ze plotten. Wéi wier et mat engem Polynom mat dräi Grad? Op d'mannst véier Punkten. An esou weider a sou weider.

Déi wierklech cool Saach iwwer dës Propriétéit ass, datt, gëtt de Grad vun der polynomial Funktioun an op d'mannst Punkten, kënne mir zousätzlech Punkte fir dës polynomial Funktioun ofgeleet. Mir nennen d'Extrapolatioun vun dësen zousätzleche Punkten polynomial Interpolatioun.

Maacht e Geheimnis

Dir hutt vläicht scho gemierkt datt dëst ass wou dem Shamir säi clevere Schema an d'Spill kënnt. Loosst eis eist Geheimnis soen Ass . Mir kënnen dréinen zu engem Punkt op der Grafik a kommen mat enger polynomial Funktioun mat Grad , déi dëse Punkt entsprécht. Loosst eis dat erënneren wäert eis Schwell vun erfuerderleche Fragmenter sinn, also wa mir d'Schwell op dräi Fragmenter setzen, musse mir eng polynomial Funktioun mat Grad zwee wielen.

Eise Polynom wäert d'Form hunn wou и - zoufälleg ausgewielt positiv ganz Zuelen. Mir konstruéiere just e Polynom mat Grad , wou de fräi Koeffizient  - Dëst ass eist Geheimnis , a fir jiddereng vun de folgende Begrëffer gëtt et e zoufälleg ausgewielte positive Koeffizient. Wa mir zréck op d'Original Beispill an dovun ausgoen, datt , da kréie mir d'Funktioun .

Zu dësem Zäitpunkt kënne mir Fragmenter generéieren andeems Dir verbënnt eenzegaarteg Ganzen an wou (well et eis Geheimnis ass). An dësem Beispill wëlle mir véier Fragmenter mat enger Schwell vun dräi verdeelen, sou datt mir zoufälleg Punkte generéieren a schéckt ee Punkt un jiddereng vun de véier vertrauenswürdege Leit, d'Depote vum Schlëssel. Mir loossen de Leit dat och wëssen , well dëst als ëffentlech Informatioun ugesi gëtt an néideg ass fir d'Erhuelung .

D'Geheimnis erholen

Mir hunn d'Konzept vun der polynomialer Interpolatioun scho diskutéiert a wéi et dem Shamir säi Schwellschema ënnersträicht . Wann all dräi vun de véier Vertrauen wëllen restauréieren , si brauche just ze interpoléieren mat hiren eegene eenzegaartege Punkten. Fir dëst ze maachen, kënnen se hir Punkten bestëmmen a berechent de Lagrange Interpolatiounspolynom mat der folgender Formel. Wann d'Programméierung fir Iech méi kloer ass wéi Mathematik, dann ass pi am Wesentlechen en Bedreiwer for, déi all Resultater multiplizéiert, a sigma ass for, wat alles opzielt.

um mir kënnen et esou léisen an eis ursprénglech Polynom Funktioun zréckginn:

Well mir dat wëssen , Erhuelung einfach gemaach:

Benotzt onsécher ganz Zuelen Arithmetik

Och wa mir dem Shamir seng Basis Iddi erfollegräich applizéiert hunn , mir bleiwen mat engem Problem dee mir bis elo ignoréiert hunn. Eis polynomial Funktioun benotzt onsécher ganzer Arithmetik. Notéiert datt fir all zousätzlech Punkt en Ugräifer op der Grafik vun eiser Funktioun kritt, et gi manner Méiglechkeeten fir aner Punkten. Dir kënnt dat mat Ären eegenen Ae gesinn wann Dir eng ëmmer méi Zuel vu Punkte fir eng polynomial Funktioun mat ganzer Arithmetik plott. Dëst ass kontraproduktiv fir eis deklaréiert Sécherheetsziel, well den Ugräifer absolut näischt wësse soll bis se op d'mannst hunn Fragmenter.

Fir ze weisen wéi schwaach den ganzen arithmetesche Circuit ass, betruecht e Szenario an deem en Ugräifer zwee Punkte krut a weess ëffentlech Informatiounen déi . Vun dëser Informatioun kann hien ofleeden , gläich wéi zwee, a plugg déi bekannte Wäerter an d'Formel и .

Den Ugräifer kann dann fannen , zielen :

Well mir definéiert hunn als zoufälleg ausgewielt positiv ganz Zuelen, ginn et eng limitéiert Zuel vu méiglech . Mat dëser Informatioun kann en Ugräifer entscheeden , well alles méi grouss wéi 5 wäert maachen negativ. Dëst stellt sech eraus well mir bestëmmt hunn

Den Ugräifer kann dann déi méiglech Wäerter berechnen , ersetzen в :

Mat limitéiert Optiounen fir et gëtt kloer wéi einfach et ass d'Wäerter ze wielen an ze kontrolléieren . Et gi just fënnef Optiounen hei.

D'Léisung vum Problem mat onsécher ganzer Arithmetik

Fir dës Schwachstelle ze eliminéieren, proposéiert de Shamir modulär Arithmetik ze benotzen, ersat op wou и - de Satz vun alle Primzuelen.

Loosst eis séier drun erënneren wéi modulär Arithmetik funktionnéiert. Eng Auer mat Hänn ass e vertraute Konzept. Si benotzt eng Auer dat ass . Soubal d'Stonnhand zwielef passéiert, geet et zréck op eng. Eng interessant Propriétéit vun dësem System ass, datt einfach duerch d'Auer kucken, mir kënnen net ofleeën wéivill Revolutiounen der Stonn Hand gemaach huet. Wéi och ëmmer, wa mir wëssen datt d'Stonnhand 12 véiermol passéiert ass, kënne mir d'Zuel vun de Stonnen komplett bestëmmen déi mat enger einfacher Formel passéiert sinn wou  ass eisen Divisor (hei ),  ass de Koeffizient (wéivill Mol den Divisor an déi ursprénglech Zuel geet ouni Rescht, hei ), an  ass de Rescht, deen normalerweis e Modulo Bedreiwer Uruff zréckkënnt (hei ). All dës Wäerter ze kennen erlaabt eis d'Equatioun ze léisen fir , awer wa mir de Koeffizient verpassen, kënne mir ni den urspréngleche Wäert restauréieren.

Mir kënne weisen wéi dëst d'Sécherheet vun eisem Schema verbessert andeems Dir de Schema op eist viregt Beispill applizéiert a benotzt . Eis nei polynomial Funktioun , an déi nei Punkten . Elo kënnen d'Schlësselbehälter nach eng Kéier polynomial Interpolatioun benotzen fir eis Funktioun ze rekonstruéieren, nëmmen dës Kéier mussen d'Additiouns- a Multiplikatiounsoperatioune mat Modulo Reduktioun begleet ginn (z ).

Mat dësem neie Beispill, loosst eis unhuelen datt den Ugräifer zwee vun dësen neie Punkte geléiert huet, , an ëffentlech Informatioun . Dës Kéier, den Ugräifer, baséiert op all d'Informatiounen déi hien huet, Ausgaben déi folgend Funktiounen, wou  ass de Set vun alle positiven ganzen Zuelen, an representéiert de Modulus Koeffizient .

Elo fënnt eisen Ugräifer erëm , berechent :

Da probéiert hien nach eng Kéier , ersetzen в :

Dës Kéier huet hien e seriöse Problem. Formel vermësst Wäerter , и . Well et eng onendlech Zuel vu Kombinatioune vun dëse Variablen gëtt, kann hien keng zousätzlech Informatioun kréien.

Sécherheet Considératiounen

Dem Shamir säi geheime Deeleschema proposéiert Sécherheet aus der Siicht vun der Informatiounstheorie. Dëst bedeit datt d'Mathematik resistent ass och géint en Ugräifer mat onlimitéierter Rechenkraaft. Wéi och ëmmer, de Circuit enthält nach ëmmer e puer bekannt Themen.

Zum Beispill, dem Shamir säi Schema erstellt net Fragmenter ze kontrolléieren, dat heescht, d'Leit kënne fräi gefälschte Fragmenter presentéieren an d'Erhuelung vum richtege Geheimnis stéieren. E feindleche Fragmenterhalter mat genuch Informatioun kéint souguer en anert Fragment produzéieren andeems Dir ännert op Ären eegene Wonsch. Dëse Problem gëtt mat Hëllef geléist verifizéierbar geheime Deeleschemaen, wéi dem Feldman säi Schema.

En anere Problem ass datt d'Längt vun all Fragment gläich ass wéi d'Längt vum entspriechende Geheimnis, sou datt d'Längt vum Geheimnis einfach ass ze bestëmmen. Dëse Problem kann duerch trivial geléist ginn padding geheime mat arbiträr Zuelen bis zu enger fixer Längt.

Schlussendlech ass et wichteg ze bemierken datt eis Sécherheetsbedéngungen iwwer den Design selwer kënne verlängeren. Fir real-Welt kryptografesch Uwendungen gëtt et dacks d'Drohung vu Säitekanalattacken, wou en Ugräifer probéiert nëtzlech Informatioun aus der Ausféierungszäit vun der Applikatioun, Cache, Crashen, etc. Wann dëst eng Suerg ass, sollt suergfälteg berücksichtegt ginn während der Entwécklung fir Schutzmoossnamen ze benotzen wéi Funktiounen a konstante Lookups, ze verhënneren datt d'Erënnerung op Disk gespäichert gëtt an eng Rei aner Iwwerleeungen déi iwwer den Ëmfang vun dësem Artikel sinn.

Demo

op dës Säit Et gëtt eng interaktiv Demonstratioun vum Shamir sengem geheimen Deeleschema. Demonstratioun baséiert op der Bibliothéik sss-js, wat selwer e JavaScript-Port vum populäre Programm ass ssss. Notéiert datt d'Berechnung vu grousse Wäerter , и kann e bëssen Zäit huelen.

Source: will.com