Apsveriet situāciju, kad jums ir nepieciešams nodrošināt bankas glabātuvi. Tas tiek uzskatīts par absolūti neieņemamu bez atslēgas, kas jums tiek izsniegta jau pirmajā darba dienā. Jūsu mērķis ir droši uzglabāt atslēgu.

Pieņemsim, ka nolemjat vienmēr paturēt atslēgu sev līdzi, nodrošinot piekļuvi krātuvei pēc vajadzības. Taču jūs ātri sapratīsit, ka šāds risinājums praksē neder, jo jūsu fiziskā klātbūtne ir nepieciešama ikreiz, kad atverat krātuvi. Kā ar jums apsolītajām brīvdienām? Turklāt jautājums ir vēl biedējošāks: kā būtu, ja pazaudētu savu vienīgo atslēgu?

Domājot par atvaļinājumu, jūs nolemjat izgatavot atslēgas kopiju un uzticēt to citam darbiniekam. Tomēr jūs saprotat, ka arī tas nav ideāli. Divkāršojot atslēgu skaitu, jūs arī dubultojat atslēgu zādzības iespējas.

Izmisumā jūs iznīcināt dublikātu un nolemjat sadalīt sākotnējo atslēgu uz pusēm. Tagad jūs domājat, ka diviem uzticamiem cilvēkiem ar atslēgu fragmentiem ir jābūt fiziski klāt, lai savāktu atslēgu un atvērtu glabātuvi. Tas nozīmē, ka zaglim ir jānozag divi gabali, kas ir divreiz grūtāk nekā vienas atslēgas nozagšana. Taču drīz vien saproti, ka šī shēma nav daudz labāka par vienu atslēgu, jo, ja kāds pazaudē pusi atslēgas, pilnu atslēgu nevar atgūt.

Problēmu var atrisināt ar papildu atslēgu un slēdzeņu sēriju, taču šī pieeja ātri prasīs много atslēgas un slēdzenes. Jūs nolemjat, ka ideāls dizains būtu koplietot atslēgu, lai drošība nebūtu pilnībā atkarīga tikai no vienas personas. Jūs arī secināt, ka ir jābūt kādam fragmentu skaita slieksnim, lai, ja kāds fragments tiek pazaudēts (vai ja cilvēks dodas atvaļinājumā), visa atslēga paliktu funkcionāla.

Kā dalīties noslēpumā

Par šāda veida atslēgu pārvaldības shēmu Adi Šamirs domāja 1979. gadā, kad viņš publicēja savu darbu "Kā dalīties noslēpumā". Rakstā īsi izskaidrots t.s sliekšņa shēma slepenas vērtības (piemēram, kriptogrāfiskās atslēgas) efektīvai sadalīšanai daļas. Tad, kad un tikai tad, kad vismaz no daļas ir samontētas, jūs varat viegli atjaunot noslēpumu .

No drošības viedokļa svarīga šīs shēmas īpašība ir tāda, ka uzbrucējam nav jāzina pilnīgi nekas, ja vien viņam nav vismaz daļas. Pat klātbūtne daļām nevajadzētu sniegt nekādu informāciju. Mēs to saucam par īpašumu semantiskā drošība.

Polinomu interpolācija

Šamira sliekšņa shēma veidota ap koncepciju polinoma interpolācija. Ja jūs neesat pazīstams ar šo koncepciju, tas patiesībā ir diezgan vienkārši. Patiesībā, ja jūs kādreiz esat zīmējis punktus grafikā un pēc tam savienojis tos ar līnijām vai līknēm, jūs to jau esat izmantojis!

Caur diviem punktiem var uzzīmēt neierobežotu skaitu 2. pakāpes polinomu. Lai no tiem izvēlētos vienīgo, nepieciešams trešais punkts. Ilustrācija: Wikipedia

Apsveriet polinomu ar pirmo pakāpi, . Ja vēlaties attēlot šo funkciju grafikā, cik punktu jums ir nepieciešams? Mēs zinām, ka šī ir lineāra funkcija, kas veido līniju, un tāpēc tai ir nepieciešami vismaz divi punkti. Pēc tam apsveriet polinoma funkciju ar otro pakāpi, . Šī ir kvadrātiskā funkcija, tāpēc, lai izveidotu grafiku, ir nepieciešami vismaz trīs punkti. Kā būtu ar polinomu ar trešo pakāpi? Vismaz četri punkti. Un tā tālāk un tā tālāk.

Patiešām foršs šajā īpašumā ir tas, ka, ņemot vērā polinoma funkcijas pakāpi un vismaz punktu, mēs varam iegūt papildu punktus šai polinoma funkcijai. Mēs saucam par šo papildu punktu ekstrapolāciju polinoma interpolācija.

Noslēpuma izdomāšana

Jūs, iespējams, jau esat sapratis, ka tieši šeit parādās Šamira gudrā shēma. Teiksim savu noslēpumu -Šo . Mēs varam pagriezties līdz punktam grafikā un izdomāt polinoma funkciju ar pakāpi , kas atbilst šim punktam. Atgādināsim jums to būs mūsu nepieciešamo fragmentu slieksnis, tādēļ, ja mēs iestatām slieksni uz trim fragmentiem, mums jāizvēlas polinoma funkcija ar otro pakāpi.

Mūsu polinomam būs forma Kur и — nejauši izvēlēti pozitīvi veseli skaitļi. Mēs tikai konstruējam polinomu ar pakāpi , kur brīvais koeficients  – Tas ir mūsu noslēpums , un katram nākamajam terminos ir nejauši izvēlēts pozitīvs koeficients. Ja atgriezīsimies pie sākotnējā piemēra un pieņemam, ka , tad mēs iegūstam funkciju .

Šajā brīdī mēs varam ģenerēt fragmentus, savienojot unikāli veseli skaitļi Kur (jo tas ir mūsu noslēpums). Šajā piemērā mēs vēlamies izplatīt četrus fragmentus ar trīs slieksni, tāpēc mēs nejauši ģenerējam punktus un nosūtiet vienu punktu katram no četriem uzticamiem cilvēkiem, atslēgas glabātājiem. Mēs arī darām to zināmu cilvēkiem , jo tā tiek uzskatīta par publisku informāciju un ir nepieciešama atkopšanai .

Noslēpuma atgūšana

Mēs jau esam apsprieduši polinoma interpolācijas jēdzienu un to, kā tas ir Šamira sliekšņa shēmas pamatā. . Kad kādi trīs no četriem pilnvarotajiem vēlas atjaunot , viņiem ir tikai jāinterpolē ar saviem unikālajiem punktiem. Lai to izdarītu, viņi var noteikt savus punktus un aprēķiniet Lagranža interpolācijas polinomu, izmantojot šādu formulu. Ja programmēšana jums ir skaidrāka nekā matemātika, tad pi būtībā ir operators for, kas reizina visus rezultātus, un sigma ir for, kas visu saskaita.

Pie mēs varam to atrisināt šādi un atgriezt savu sākotnējo polinoma funkciju:

Jo mēs to zinām , atveseļošanās darīts vienkārši:

Nedrošas veselu skaitļu aritmētikas izmantošana

Lai gan esam veiksmīgi pielietojuši Šamira pamatideju , mums ir radusies problēma, kuru līdz šim esam ignorējuši. Mūsu polinoma funkcija izmanto nedrošu veselu skaitļu aritmētiku. Ņemiet vērā, ka katram papildu punktam, ko uzbrucējs iegūst mūsu funkcijas grafikā, citiem punktiem ir mazāk iespēju. To var redzēt savām acīm, kad, izmantojot veselu skaitļu aritmētiku, uzzīmējat arvien lielāku punktu skaitu polinoma funkcijai. Tas ir neproduktīvs mūsu izvirzītajam drošības mērķim, jo ​​uzbrucējam nevajadzētu zināt pilnīgi neko, kamēr viņam tas ir vismaz fragmenti.

Lai parādītu, cik vāja ir veselo skaitļu aritmētiskā ķēde, apsveriet scenāriju, kurā uzbrucējs ieguva divus punktus un zina publisko informāciju, ka . No šīs informācijas viņš var secināt , vienāds ar diviem, un pievienojiet zināmās vērtības formulā и .

Pēc tam uzbrucējs var atrast , skaitot :

Tā kā mēs esam definējuši kā nejauši atlasīti pozitīvi veseli skaitļi, ir ierobežots skaits iespējamo . Izmantojot šo informāciju, uzbrucējs var secināt , jo derēs viss, kas lielāks par 5 negatīvs. Tas izrādās taisnība, jo mēs esam noteikuši

Pēc tam uzbrucējs var aprēķināt iespējamās vērtības aizstājot в :

Ar ierobežotām iespējām priekš kļūst skaidrs, cik viegli ir izvēlēties un pārbaudīt vērtības . Šeit ir tikai piecas iespējas.

Uzdevuma atrisināšana ar nedrošu veselu skaitļu aritmētiku

Lai novērstu šo ievainojamību, Šamirs iesaka izmantot modulāro aritmētiku, aizstājot par Kur и — visu pirmskaitļu kopa.

Ātri atcerēsimies, kā darbojas modulārā aritmētika. Pulkstenis ar rādījumiem ir pazīstams jēdziens. Viņa izmanto pulksteni, kas ir . Tiklīdz stundu rādītājs paiet divpadsmit, tas atgriežas pie viena. Interesanta šīs sistēmas īpašība ir tāda, ka, vienkārši skatoties pulkstenī, mēs nevaram izsecināt, cik apgriezienus ir veikusi stundu rādītājs. Tomēr, ja mēs zinām, ka stundu rādītājs ir pagājis 12 četras reizes, mēs varam pilnībā noteikt pagājušo stundu skaitu, izmantojot vienkāršu formulu Kur  ir mūsu dalītājs (šeit ),  ir koeficients (cik reizes dalītājs ieiet sākotnējā skaitļā bez atlikuma, šeit ) un  ir atlikums, kas parasti atgriež modulo operatora zvanu (šeit ). Zinot visas šīs vērtības, mēs varam atrisināt vienādojumu par , bet, ja mēs palaidīsim garām koeficientu, mēs nekad nevarēsim atjaunot sākotnējo vērtību.

Mēs varam parādīt, kā tas uzlabo mūsu shēmas drošību, piemērojot shēmu mūsu iepriekšējā piemērā un izmantojot . Mūsu jaunā polinoma funkcija , un jaunie punkti . Tagad atslēgu turētāji atkal var izmantot polinoma interpolāciju, lai rekonstruētu mūsu funkciju, tikai šoreiz saskaitīšanas un reizināšanas operācijām ir jāpievieno modulo samazināšana (piemēram, ).

Izmantojot šo jauno piemēru, pieņemsim, ka uzbrucējs uzzināja divus no šiem jaunajiem punktiem, un publisko informāciju . Šoreiz uzbrucējs, pamatojoties uz visu viņa rīcībā esošo informāciju, izvada šādas funkcijas, kur  ir visu pozitīvo veselo skaitļu kopa un apzīmē moduļa koeficientu .

Tagad mūsu uzbrucējs atrod vēlreiz , aprēķinot :

Tad viņš mēģina vēlreiz aizstājot в :

Šoreiz viņam ir nopietna problēma. Formulā trūkst vērtību , и . Tā kā ir bezgalīgi daudz šo mainīgo kombināciju, viņš nevar iegūt papildu informāciju.

Drošības apsvērumi

Šamira slepenā koplietošanas shēma liecina drošība no informācijas teorijas viedokļa. Tas nozīmē, ka matemātika ir izturīga pat pret uzbrucēju ar neierobežotu skaitļošanas jaudu. Tomēr ķēdē joprojām ir vairākas zināmas problēmas.

Piemēram, Šamira shēma nerada fragmenti, kas jāpārbauda, tas ir, cilvēki var brīvi uzrādīt viltotus fragmentus un traucēt atgūt pareizo noslēpumu. Naidīgs fragmentu glabātājs ar pietiekamu informāciju var pat radīt citu fragmentu, mainoties pēc saviem ieskatiem. Šī problēma tiek atrisināta, izmantojot pārbaudāmas slepenās koplietošanas shēmas, piemēram, Feldmana shēma.

Vēl viena problēma ir tāda, ka jebkura fragmenta garums ir vienāds ar atbilstošā noslēpuma garumu, tāpēc noslēpuma garumu ir viegli noteikt. Šo problēmu var atrisināt triviāli polsterējums noslēpums ar patvaļīgiem cipariem līdz noteiktam garumam.

Visbeidzot, ir svarīgi atzīmēt, ka mūsu bažas par drošību var pārsniegt pašu dizainu. Reālās pasaules kriptogrāfijas lietojumprogrammām bieži vien pastāv sānu kanālu uzbrukumu draudi, kad uzbrucējs mēģina iegūt noderīgu informāciju no lietojumprogrammas izpildes laika, kešatmiņas, avārijām utt. Ja tas rada bažas, izstrādes laikā rūpīgi jāapsver, vai izmantot aizsardzības pasākumus, piemēram, funkcijas un pastāvīga laika uzmeklēšanu, nepieļaut atmiņas saglabāšanu diskā un vairākus citus apsvērumus, kas neietilpst šī raksta darbības jomā.

Demo

uz šī lapa Ir interaktīva Šamira slepenās koplietošanas shēmas demonstrācija. Demonstrācija, pamatojoties uz bibliotēku ssss-js, kas pati par sevi ir populārās programmas JavaScript ports SSS. Ņemiet vērā, ka lielu vērtību aprēķināšana , и var paiet kāds laiks.

Avots: www.habr.com