Secvență supracrescătoare

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 18 martie 2018; verificările necesită 16 modificări .

O secvență se numește supracreștere , fiecare termen fiind mai mare decât suma tuturor termenilor anteriori. Mai formal, o succesiune de numere întregi pozitive este supracrescătoare dacă condiția [1] [2] este îndeplinită : $s_{1},s_{2},\dots$

$\forall n>1\ :\ s_{n}>\sum _{j=1}^{n-1}s_{j}$

Această clasă de secvențe este utilizată pe scară largă în criptosistemul de rucsac Merkle-Hellman .

De exemplu, este în creștere, dar nu. $\{1,3,6,13,27,52\)$ $\{1,3,4,9,15,25\)$

Metode pentru construirea unei secvențe de supracreștere

Să presupunem că ne confruntăm cu sarcina de a construi o secvență supracrescătoare pentru un anumit număr de obiecte . Elementul este ales aleatoriu dintr-o distribuție uniformă a numerelor naturale pe următorul segment: . Următorul element este ales uniform din segment , membrul secvenței care îl urmează este ales din segment , elementul este selectat aleatoriu din segment . Evident, cu astfel de distribuții ale membrilor secvenței, condiția de supercreștere va fi satisfăcută, deoarece limita inferioară a fiecărui segment este exact egală cu suma tuturor limitelor drepte ale segmentelor anterioare crescută cu unu [3] . De exemplu, să construim mai multe secvențe supracrescătoare în acest fel pentru : $\{s_{n}\}_{1}^{N)$ $N$ $s_{1}$ $[1,2^{N}]$ $s_{2}$ $[1\cdot 2^{N}+1,2\cdot 2^{N}]$ $[3\cdot 2^{N}+1,4\cdot 2^{N}]$ $s_{n}$ $[(2^{n-1}-1)\cdot 2^{N}+1,2^{n-1}\cdot 2^{N}]$ $N=5$

n	Segment de linie	Exemplul 1	Exemplul 2	Exemplul 3
unu	$[1,32]$	5	zece	32
2	$[33,64]$	56	49	64
3	$[97.128]$	98	113	97
patru	$[225.256]$	225	225	225
5	$[481.512]$	481	510	493

Construcție cu o etapă aleasă aleatoriu

Dacă sunt numere alese aleatoriu, atunci elementele rămase ale șirului supracrescător pot fi găsite din inegalitatea [4] : $h,s_{1}\geq 1$

$s_{n}>h+\sum _{j=1}^{n-1}s_{j)$

Să , . Apoi, de exemplu, secvența satisface condiția și este în creștere. $h=10$ $s_{1}=9$ $\{9,20,52,100,192\)$

Construcție bazată pe succesiunea Fibonacci

Fiecare element al sirului Fibonacci satisface relatia: , ai carei zero si primii membri sunt: . Din aceasta se poate observa că primii membri ai șirului Fibonacci: . Uneori puteți întâlni o secvență Fibonacci generalizată . Aceasta este o secvență ai cărei membri îndeplinesc condiția ecuației: . Adică șirul generalizat se obține din cel clasic prin modificarea primilor doi termeni ai șirului Fibonacci și reține principiul formării următorilor termeni. Pentru a construi o secvență supracrescătoare, se folosește forma secvenței generalizate de Fibonacci. Pentru a calcula orice membru al secvenței supracrescătoare este necesar să se aleagă patru elemente: doi factori inițiali ( și ) și doi factori pozitivi ( și ) [5] . ${\displaystyle u_{n+1}=u_{n}+u_{n-1))$ $u_{0}=0,u_{1}=1$ $\{0,1,1,2,3,5,8,13,21,34,55,89,...\)$ $u_{n+1}=a\cdot u_{n}+b\cdot u_{n-1)$ $\{s_{n}\}_{1}^{N)$ $s_{1)$ $s_{2}$ $A$ $b$

Primim următoarele cazuri:

Secvența satisface condiția de supracreștere pentru . $s_{1}<s_{2},a\leq b$
Secvența nu este supracrescătoare pentru . $a>b$
Căci , secvența începe să satisfacă condiția de supercreștere după mai multe iterații . $s_{1}>s_{2},a\leq b$
Pentru , secvența rămâne supracrescătoare. $s_{1}<s_{2},T={a \over b}<0,669$

De exemplu, să luăm . Primele elemente ale secvenței supracrescătoare rezultate sunt: . $s_{1}=2,s_{2}=3,a=5,b=7$ $\{2,3,5\cdot 3+7\cdot 2,5\cdot 29+7\cdot 3,5\cdot 166+7\cdot 29\}=\{2,3,29,166\}$

Bazându-se pe secvența de supracreștere existentă

Condiția de supracreștere este îndeplinită de un număr de puteri de . Cunoscând secvența supracrescătoare , putem construi una nouă folosind mulțimea . Pentru implementare, este necesar să se aplice setului următoarelor operațiuni [6] : $2$ $\{s_{n}\}_{1}^{N)$ ${\displaystyle \{s_{n}^{'}\}_{1}^{N))$ $\{1,2,2^{2},...,2^{N-1}\}$ $\{s_{n}\}_{1}^{N)$

$n=1:\{s_{1}+1,s_{2}+1,s_{3}+2,...,s_{N-1}+2^{N-3},s_ {N}+2^{N-2}}\$

$\ldots$

$n=k:\{s_{1},s_{2},s_{3},...,s_{k}+1,s_{k+1}+1,...,s_{ N-1}+2^{Nk-2},s_{N}+2^{Nk-1}}\$

$...$

$n=N-1:\{s_{1},s_{2},s_{3},...,s_{N-1}+1,s_{N}+1}\$

$n=N:\{s_{1},s_{2},s_{3},...,s_{N-1},s_{N}+1}\$

Exemplu detaliat pentru o secvență de supracreștere selectată : $\{3,6,13,27,52,105\}$

	$s_{1)$	$s_{2}$	$s_{3)$	$s_{4)$	$s_{5}$	$s_{6}$
	$3$	$6$	$13$	$27$	$52$	$105$
$n=1$	$3+1=4$	$6+1=7$	$13+2=15$	$27+2^{2}=31$	$52+2^{3}=60$	$105+2^{4}=121$
$n=2$	$4$	$7+1=8$	$15+1=16$	$31+2=33$	$60+2^{2}=64$	$121+2^{3}=129$
$n=3$	$4$	$8$	$16+1=17$	$33+1=34$	$64+2=66$	$129+2^{2}=133$
$n=4$	$4$	$8$	$17$	$34+1=35$	$66+1=67$	$133+2=135$
$n=5$	$4$	$8$	$17$	$35$	$67+1=68$	$135+1=136$
$n=6$	$4$	$8$	$17$	$35$	$68$	$136+1=137$

Avem o nouă secvență de supra-creștere . $\{s_{n}^{'}\}_{1}^{N}=\{4,8,17,35,68,137\)$

Utilizarea secvenței supercrescente în criptografie

Rucsacuri super-creștere

Criptosistemul Merkle-Hellman se bazează pe „problema rucsacului” – un algoritm de criptare cu cheie publică – descrisă mai jos. Problema arată astfel: dată fiind o secvență de numere întregi pozitive nerepetabile. Fie numărul să aparțină și mulțimii numerelor naturale. Dacă acest lucru este posibil, este necesar să se găsească un set de secvențe binare pseudoaleatoare pentru a satisface condiția: [2] . $\{a_{n}\}_{1}^{N}$ $k$ $\{b_{n}\}_{1}^{N)$ ${\displaystyle k=b_{1}a_{1}+b_{2}a_{2}+...+b_{n}a_{n))$

Să fie o secvență supracrescătoare. În acest caz, ne confruntăm cu o problemă „ușoară” a unui rucsac, care nu este greu de rezolvat. Pentru a face acest lucru, se compară cu elementul . Dacă , atunci valoarea este decrementată cu și săriți la membrul secvenței . Acțiunea se repetă până la încheierea procesului. Dacă până la urmă , atunci soluția problemei se găsește sub forma unei secvențe , altfel nu există [2] . $\{a_{n}\}_{1}^{N}$ $k$ $a_{n}$ $k\geq a_{n)$ $b_{n}=1$ $k$ $a_{n}$ $a_{n-1}$ $k=0$ $\{b_{n}\}_{1}^{N)$

Dacă secvența nu este în creștere (sau normală), atunci rucsacii sunt o problemă „grea” care poate fi rezolvată doar prin enumerarea tuturor opțiunilor posibile. $\{a_{n}\}_{1}^{N}$

Cheia privată din algoritmul Merkle-Hellman este secvența de greutăți a problemei rucsacului cu supracreștere, în timp ce cheia publică este secvența de greutăți a problemei normale a rucsacului cu aceeași soluție. Există o modalitate de a converti problema rucsacului cu supra-creștere într-o problemă normală de rucsac folosind aritmetica modulară. Pentru a obține o secvență normală de rucsac, vom folosi o secvență de rucsac cu supra-creștere. De exemplu, să luăm o succesiune de numere: , și modulo înmulțim fiecare element al acestei secvențe cu numărul . Se impune o condiție: valoarea modulului trebuie să fie mai mare decât suma tuturor elementelor secvenței, de exemplu, . Și multiplicatorul trebuie să fie un număr relativ prim cu un modulo, de exemplu, . Într-un astfel de caz, secvența normală de rucsac ar fi [2] : $\{2,3,7,13,27,61\)$ $m$ $n$ $m$ $m=115$ $n$ $n=31$

$2\cdot 31mod115=62;$

$3\cdot 31mod115=93;$

$7\cdot 31mod115=102;$

$13\cdot 31mod115=58;$

$27\cdot 31mod115=32;$

$61\cdot 31mod115=51.$

Obținem o succesiune normală de numere: . Secvența de rucsac în creștere este cheia privată, în timp ce secvența normală de rucsac este cheia publică. $\{62,93,102,58,32,51\)$

Schema de partajare a secretelor multilaterale

În 2017, a fost propusă o schemă de partajare a secretelor cu mai multe părți, folosind o secvență de supra-creștere. Unicitatea schemei constă în faptul că nu este doar multilaterală, ci implementează și o structură de acces secvenţial pe niveluri. Algoritmul folosește schema Shamir , sau mai degrabă generarea de acțiuni secrete, urmată de faza de recuperare secretă [7] .

Să prezentăm un algoritm pentru implementarea unei scheme multilaterale de partajare a secretelor.

Generarea de acțiuni secrete [8]

Pasul 1.1. Se alege un secret , unde este un număr prim care este cunoscut de toate părțile și stabilește dimensiunea finală a câmpului . Să , unde este numărul de participanți între care trebuie să împărtășiți secretul . $s\in \mathbb {Z} _{p}-\{0\)$ $p$ $p$ $p=2^{l-1}$ $l$ $s$

Pasul 1.2. Să transformăm secretul în sistem de numere binar pseudo-aleatoriu de biți și să formăm secvența . $s$ $(l-1)$ ${\displaystyle st=\{s_{l-1},s_{l-2},s_{l-3},...,s_{3},s_{2},s_{1}\))$

Pasul 1.3. Să compunem o secvență binară de lungime din elemente selectate aleatoriu: . $l-1$ ${\displaystyle \{e_{l-1},e_{l-2},e_{l-3},...,e_{3},e_{2},e_{1}\))$

Pasul 1.4. Folosim operația XOR între elementele secvențelor de la Pasul 1.2 și Pasul 1.3. Ca rezultat, obținem o nouă secvență: . $st^{'}=\{s_{l-1}\oplus e_{l-1},s_{l-2}\oplus e_{l-2},s_{l-3}\oplus e_ {l-3},...,s_{3}\oplus e_{3},s_{2}\oplus e_{2},s_{1}\oplus e_{1}\}=\{s_{l -1}^{'},s_{l-2}^{'},s_{l-3}^{'},...,s_{3}^{'},s_{2}^{' },s_{1}^{'}\}$

Pasul 1.5. Să construim o succesiune supracrescătoare de numere aleatoare de lungime : . $l-1$ ${\displaystyle w=\{w_{l-1},w_{l-2},w_{l-3},...,w_{3},w_{2},w_{1}\))$

Pasul 1.6. Calculăm suma , care va fi cunoscută de toți participanții. Pseudocod funcție: $u=bagsum(st^{'},w)$

funcția bugsum(a, b); Intrare: și . ieșire: suma. suma ; pentru i r do sum sum ; Sfârşit

a=\{a_{1},...,a_{r}}\

b=\{b_{1},...,b_{r}\}

\leftarrow 0

\în

\leftarrow

+

a_{i}\times b_{i)

suma returnată;

Pasul 1.7. Alegeți un număr prim , care va fi anunțat tuturor participanților și astfel încât: și pentru , unde numărul de niveluri și numărul total de participanți la nivel . $q$ $w_{1}+w_{2}+w_{3}+...+w_{l-1}<q$ $\max(n_{i})$ $1\leq i\leq l$ $i-$ $n_{i}-$ $i$

Pasul 1.8. Distribuim între toți participanții la nivel folosind , unde determină gradul polinomului schemei Shamir la nivel . Apoi, trebuie să convertiți elementele secvenței pasului 1.3 în sistemul zecimal și, de asemenea, să le distribuiți pe nivel folosind . $w_{i}$ $i$ $(t_{i},n_{i})$ $t_{i}<n_{i}$ $F(x)$ $i$ $l$ $(t_{l},n_{l})$

Faza de recuperare secretă [8]

Pasul 2.1. Cel puțin, participanții recuperează secretul la nivel și primesc o cotă pentru . $t_{i)$ $i$ $w_{i)$ $1\leq i\leq l-1$

Pasul 2.2. Primul nivel verifică dacă este într-adevăr adevărat pentru suma obținută în Pasul 1.6. Dacă inegalitatea este adevărată, primul nivel emite și trimite la al doilea nivel o nouă valoare de sumă: . În caz contrar, emite și trimite la stratul următor și adaugă bitul său de ieșire la secvența goală . Este necesar să treceți prin toate nivelurile, umplând treptat secvența . $u\geq w_{1}$ $unu$ $u_{1,2}^{'}=u-w_{1)$ $0$ $u_{1,2}^{'}=u$ $0$ $st^{''}$ $st^{''}$

Pasul 2.3. Nivelul efectuează recuperarea secretă și însămânțarea secvenței . Repetăm calculele care au fost efectuate în Pasul 1.4 cu operația XOR: . $l$ $\{e_{l-1}^{'},e_{l-2}^{'},e_{l-3}^{'},...,e_{3}^{'} ,e_{2}^{'},e_{1}^{'}\}$ $st=\{e_{l-1}^{'}\oplus s_{l-1}^{'},e_{l-2}^{'}\oplus s_{l-2}^{ '},e_{l-3}^{'}\oplus s_{l-3}^{'},...,e_{3}^{'}\oplus s_{3}^{'},e_ {2}^{'}\oplus s_{2}^{'},e_{1}^{'}\oplus s_{1}^{'}\}$

Pasul 2.4 . În cele din urmă, avem o secvență binară secretă care poate fi convertită în zecimal pentru a obține secretul . $s$

Note

↑ Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematical & Applications) , Chapman & Hall/CRC; 1 ediție (10 august 2000), ISBN 1-58488-127-5
↑ 1 2 3 4 Schneier, 1993 .
↑ Merkle, Hellman, 1978 .
↑ Salomaa, 1995 .
↑ Merzouga, Ali-Pachab, Hadj-Saidb, Ali-Pachab, 2019 .
↑ Murin, 2011 .
↑ Basit, Chanakya, Venkaiah, Abdul Moiz, 2020 .
↑ 1 2 Harsha, Chanakya, Vadlamudi China Venkaiah, 2017 .

Literatură

Bruce Schneier. Criptografie aplicată: protocoale, algoritmi și cod sursă în C. - 1993. - P. 463-465. — ISBN 978-0471117094 .
Rucsac Merkle RC și Hellman ME Trapdoor. - 1978. - S. 525-526.
Salomaa A. Public-Key Criptography. — 1995.
A. Merzouga, A. Ali-Pachab, N. Hadj-Saidb, H. Ali-Pachab. Producerea unei secvențe super-crescătoare bazată pe secvența Fibonaci . — 2019.
P. Harsha, P. Chanakya și Vadlamudi China Venkaiah. O schemă reutilizabilă de partajare a secretelor multipartite, bazată pe secvență de supracreștere . — 2017.
A. Basit, P. Chanakya, V. Ch. Venkaiah și S. Abdul Moiz. Nouă schemă de partajare a mai multor secrete bazată pe secvența de supracreștere pentru structura de acces ordonată la nivel . — 2020.
Murin DM În ordinea creșterii numărului de vectori de rucsac injectivi și supercrescători . — 2011.

Link -uri

Secvențe supracrescătoare