Problema rucsacului în criptografie

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 mai 2020; verificările necesită 4 modificări .

Problema rucsacului (sau problema rucsacului ) în criptografie ( ing. Problema rucsacului ) este o problemă pe baza căreia criptografii americani Ralph Merkle și Martin Hellman au dezvoltat primul algoritm de criptare cu cheie publică . Se numește criptosistemul Merkle-Hellman. Pentru a cripta mesajele, am folosit soluția problemei rucsacului, despre care se știe că este NP-hard . Prin urmare, s-a crezut că ar putea asigura stabilitatea criptografică a sistemului. În acest moment, au fost create multe criptosisteme de rucsac. Cu toate acestea, aproape toate cele existente astăzi sunt piratate sau recunoscute ca potențial nesigure.

Istorie

Problema rucsacului se află în centrul primului algoritm de criptare asimetrică (sau criptare cu cheie publică). Ideea criptografiei cu cheie publică a fost propusă de criptografii americani Whitfield Diffie , Martin Hellman și, în mod independent, Ralph Merkle . A fost prezentat pentru prima dată de Diffie și Hellman la Conferința Națională de Calculatoare în 1976, în același an fiind publicată lucrarea lor comună pe această temă, New Directions in Cryptography . ) [1] . Articolul lui Merkle „Secure Communication Over Insecure Channels” a fost publicat abia în 1978 [2] . Noutatea în raport cu criptosistemele simetrice comune la acea vreme a fost utilizarea cheilor împerecheate - secrete ( ing. cheie privată, cheie secretă, SK ) și public ( ing. cheie publică, PK ), create de utilizator. Cheia secretă folosită pentru decriptarea informațiilor trebuie să fie păstrată secretă de către utilizator, în timp ce cheia publică, care este necesară doar pentru criptare, poate fi făcută publică. În multe criptosisteme, cheia publică se obține din cheia secretă [3] [4] .

Primul algoritm de criptare bazat pe problema rucsacului a fost dezvoltat de Merkle și Hellman în 1978 și a fost numit „ Algoritmul Merkle-Hellman ” [3] . A fost publicată în versiuni cu o singură etapă (în engleză cu repetare unică ) și în versiuni în mai multe etape ( în engleză cu repetare multiplă ). Algoritmul a putut fi folosit doar pentru criptare, dar criptoanalistul israelian Adi Shamir l-a adaptat pentru utilizarea în semnăturile digitale [3] . După ce schema a fost publicată, Merkle a oferit o recompensă de 100 de dolari oricărei persoane care a spart cu succes algoritmul într-o etapă. În 1982, Shamir a efectuat un atac cu succes și a primit recompensa promisă. Dar chiar și după ce a plătit-o, Merkle a fost încrezătoare în puterea criptografică a sistemului în mai multe etape și a oferit 1.000 de dolari dacă a fost spart cu succes. În 1984, matematicianul american Ernest Brickell a reușit să finalizeze un hack pentru o variantă cu patruzeci de etape în puțin peste 1 oră pe o mașină Cray-1 [5] [6] .

Independent unul de celălalt, în 1980, matematicianul american Ron Graham și Adi Shamir au descoperit o modalitate de a crește puterea criptografică a schemei Merkle-Hellman, dar deja în 1983 schema Graham-Shamir rezultată a fost spartă de omul de știință american Leonard Adleman. . Cu toate acestea, căutarea modificărilor lipsite de deficiențele schemei Merkle-Hellman a continuat. În 1985, profesorul asociat britanic Rodney Goodman și inginerul american Anthony McAuley au creat un circuit bazat pe rucsacuri modulare cu o lacună secretă, care nu se bazează pe vectori supracrescători , ci folosind teorema chineză a restului [7] [8] .

Ulterior, a devenit clar că schema era vulnerabilă la atacuri bazate pe căutarea lacune secrete. Cu toate acestea, în 1990, Valtteri Niemi a propus o nouă schemă bazată pe aceeași sarcină a unui rucsac modular. A fost spart chiar în anul următor de către Chi Ye Meng , Antoine Zhu și Jacques Stern [9] independent unul de celălalt, folosind metode ușor diferite. Pe lângă utilizarea de rucsacuri modulare, au existat încercări de a folosi alte tipuri de rucsacuri.

Așadar, în 1986, Harald Niederreiter a publicat un criptosistem de rucsac bazat pe teoria codificării algebrice, care mai târziu a fost rupt, iar în 1988 Masakatsu Morii și Masao Kasahara au dezvoltat un criptosistem de rucsac folosind un rucsac multiplicativ [10] . Această idee s-a dovedit a fi de succes și până acum sistemul pe rucsacuri multiplicative nu a fost piratat.

În 2001, Shinya Kiuchi , Yasuyuki Murakami și Masao Kasahara au propus o îmbunătățire a schemei Moriya-Kasahara bazată pe rucsacuri multiplicative folosind algoritmul Schalkwijk [11] .

De asemenea, a avut succes ideea lui Hussein Ali Hussein , Jafar Wadi Abdul Sad și M. Khalifa , care au propus în 1991 un criptosistem de rucsac multistage ( în engleză multistage trapdoor knapsack cryptosystem ). Fixează vectorul de rucsac pentru fiecare etapă, iar rezultatul (text cifrat) după fiecare etapă a algoritmului este folosit ca intrare (text) pentru etapa următoare. Nu se cunoaște niciun atac de succes asupra acestei scheme (din 2001) [12] .

Qu Minghua și Scott Vanstone au propus în 1992 un criptosistem hibrid care se bazează în primul rând pe problema rucsacului, dar include și semnături logaritmice. În 1994, R. Blackburn , Murphy, Sean și Jacques Stern au arătat că o versiune simplificată a criptosistemului U-Waston nu este sigură. Aceste criptosisteme au fost studiate mai amănunțit de Fong Nguyen și Jacques Stern în 1997 [5] .

Au continuat, de asemenea, îmbunătățirile ale algoritmului clasic Merkle-Hellman. În 1994, Orton a propus o modificare a schemei Merkle-Hellman în mai multe etape, dar doi ani mai târziu a fost piratată de Ritter [13] .

În 1995, au fost propuse simultan două noi abordări ale problemei. Prima, bazată pe ecuații diofantine , se datorează lui Lin Zhuxing , Zhang Zhencheng și Li Jia Tong . Aproape imediat, Lai Qisong și Blackburn, Murphy, Sean și S. G. Paterson au arătat în mod independent că acest criptosistem nu este sigur.

A doua abordare, bazat pe problema rucsacului multiplicativ, a fost propus de David Naccache și Jacques Stern [14] . Nakkashe și Stern au oferit DM 1024 cuiva care și-a spart cu succes schema cripto, dar nu existau informații că cineva a primit această recompensă încă (din 2001) [5] .

În 1996, Kunikatsu Kobayashi și Masaki Kimura au propus un criptosistem îmbunătățit de rucsac bazat pe un nou concept, în care expeditorul poate alege o cheie de criptare dintr-un întreg set de chei. Doi ani mai târziu, Hidenori Kuwakado și Hatsukazu Tanaka au arătat că sistemul era potențial nesigur [15] .

Ultima versiune a algoritmului a fost propusă de B. Shor și R. L. Rivest în 2006. În 2002, algoritmul Chor-Rivest a fost considerat sigur [3] .

În 2015, a fost raportat că Nathan Hamlin și William Webb de la Universitatea de Stat din Washington au creat un algoritm de rucsac fără deficiențele implementărilor anterioare [16] .

De atunci, au fost propuși mulți algoritmi cu cheie publică care nu se bazează pe sisteme de rucsac. Cele mai cunoscute dintre ele sunt: RSA , EIGamal și Rabin . Ele pot fi folosite atât pentru criptare, cât și pentru semnături digitale. Cu toate acestea, sunt lente și nu sunt potrivite pentru criptarea/decriptarea rapidă a unor volume mari de mesaje. Soluția la această problemă o reprezintă criptosistemele hibride, mesajele sunt criptate cu un algoritm rapid simetric cu o cheie aleatorie, iar algoritmul cu cheie publică este folosit pentru a cripta cheia aleatoare (de sesiune) în sine.

Enunțul problemei

Problema rucsacului este următoarea: dat un set de numere întregi pozitive distincte. Să existe un număr care este, de asemenea, întreg și pozitiv. Sarcina este să găsești un astfel de set care să însumeze exact . Este clar că o soluție la această problemă nu există întotdeauna. $A=(a_{1},...,a_{n})$ $n$ $k$ $a_{i}$ $k$

Conform definiției sistemelor cu chei publice, trebuie să aveți două chei pentru a cripta/decripta cu succes. Destinatarul legitim al mesajului cunoaște cheia secretă A, în timp ce expeditorul are doar cheia publică B. Cum poți împiedica un atacator să decripteze mesajul dacă cunoaște cheia publică? Răspunsul este simplu, cheia publică trebuie să fie derivată din cheia privată folosind o transformare f care are următoarele două proprietăți [17] :

Este ușor să calculezi știind $B=f(A)$ $A$
Determinarea , cunoașterea , este probabil o sarcină dificilă. $A=f^{-1}(B)$ $B$

Ca probleme dificile, problemele NP-complete sunt de obicei considerate, astfel încât problema rucsacului este potrivită pentru construirea de sisteme cu cheie publică.

Criptare cu problema rucsacului

Mesajul este criptat ca o soluție la un set de probleme la rucsac [2] .

Def. Un vector rucsac este un set ordonat de n articole [18] .

A=(a_{1},...,a_{n})

Pentru a cripta textul simplu în reprezentare binară, acesta este împărțit în blocuri de lungime (de exemplu, corespunde la 5 articole dintr-un rucsac). Se crede că unul indică prezența unui articol în rucsac, iar zero indică absența acestuia. Există două moduri de a cripta: $n$ $(11100)$

1) Cifrul mesajului se obține prin ridicarea elementelor vectorului rucsac la puterea biților mesajului criptat corespunzător acestora și înmulțirea în continuare a rezultatelor, adică dacă , și mesajul , atunci cifrul va fi numărul . Această metodă se numește multiplicativă [5] . $A=(2,3,5)$ $(100)$ $2^{1}*3^{0}*5^{0}=2$

2) Cifrul mesajului se obține prin înmulțirea elementelor vectorului rucsac cu bitul corespunzător al mesajului criptat și apoi adăugarea rezultatelor, adică dacă , și mesajul , atunci cifrul va fi numărul . Această metodă se numește aditiv [5] . $A=(2,3,5)$ $(100)$ $2*1+3*0+5*0=2$

Un exemplu de text cifrat obținut printr-un algoritm aditiv.

Să fie dat un vector rucsac Α = (3 4 6 7 10 11) cu lungimea n = 6.

text simplu	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
lucruri într-un rucsac	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11
text cifrat	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	unsprezece

Pentru un anumit Α, toate criptosistemele sunt numere care nu depășesc 41, greutatea totală a tuturor articolelor din vectorul rucsac. Există un singur criptotext pentru fiecare text simplu.

Complexitatea cifrului constă în faptul că există două probleme ale rucsacului: „ușor” și „greu”. O problemă „ușoară” poate fi rezolvată în timp liniar, una „grea” nu. Cheia publică este o problemă „grea”, deoarece este ușor de utilizat pentru a cripta și imposibil de a decripta un mesaj. Cheia privată este o problemă „ușoară”, deoarece facilitează decriptarea mesajului. În absența unei chei private, problema rucsacului „dur” trebuie rezolvată. Merkle și Hellman, folosind aritmetica modulară, au dezvoltat o modalitate de a transforma un rucsac „ușor” într-unul „dificil” [2] .

Problemă „ușoară”

Pentru unii vectori Α, problema rucsacului este ușor de rezolvat. Vectorii supercrescători au această proprietate [2] .

Def. Un vector de rucsac se numește supergrowing dacă pentru , adică fiecare membru al secvenței este mai mare decât suma celor anterioare [18] .

A=(a_{1},...,a_{n})

\sum _{i=1}^{j-1}a_{i}<a_{j)

j=2,...,n

Exemplu

Fie ca greutatea totală a rucsacului și a vectorului rucsacului să fie dată ca supercreștere . $P=70$ $A=(2,3,6,13,27,52)$

Pentru acest vector rucsac, algoritmul de rezolvare a problemei rucsacului este simplu. Se ia cea mai mare greutate, 52. Deoarece 52 < 70, articolul corespunzător este pus în rucsac. Spațiul liber din rucsac a devenit egal cu 70 - 52 = 18. Apoi, luați un articol cu o greutate de 27. Deoarece 27 > 18, acest articol nu va intra în rucsac. Al treilea articol cu o greutate de 13 < 18 va încăpea în rucsac, lăsând spațiu liber 5. Următorul articol cu o greutate de 6 nu se va potrivi. În mod similar, articolele cu greutățile 2 și 3 sunt plasate într-un rucsac. Greutatea reziduala a rucsacului a devenit 0, solutia a fost gasita!

Problema „grea”

Un rucsac normal nu este cu un vector de rucsac A supracrescător. Singura modalitate de a rezolva o astfel de problemă este să testați toate cele posibile până când este găsită soluția corectă. Cel mai rapid algoritm are o dependență exponențială de numărul de elemente [2] .

Un criptosistem cu cheie publică bazat pe problema rucsacului

Ca și înainte, vectorul A este cheia secretă, iar vectorul B este cheia publică.

Crearea unei chei publice dintr-o cheie privată

Pentru numere întregi și notează . $X$ $m\geq 2$ $(x,modm)=x-[x/m]m$

Să fie un vector de rucsac în creștere. Să introducem un număr întreg și un număr natural astfel încât cel mai mare divizor comun să fie . $A=(a_{1},...,a_{n})$ $m>\sum _{i=1}^{n}a_{i}$ $t<m$ $(t,m)=1$

Def. Dacă astfel încât pentru , atunci spunem că se obține din înmulțirea modulară puternică [18] .

B=(b_{1},...,b_{n})

b_{i}=(ta_{i},modm)

i=1,..,n

B

A

Creatorul criptosistemului alege parametrii astfel încât A să fie în creștere și B să fie obținut din A prin înmulțire modulară puternică în raport cu m și t. $A,B,t,m$

Lema validă [19] : Fie A un vector supercrescător, iar B se obține din A prin înmulțire modulară puternică față de m și t. Să presupunem că u = 1/t, β este un număr natural arbitrar și α =(uβ,modm). Atunci este adevărat că:

Problema rucsacului cu datele de intrare (A,α) este rezolvabilă în timp liniar, iar dacă există o soluție, atunci este unică;
Problema rucsacului cu datele de intrare (B,β) are cel mult o soluție;
Dacă există o soluție de intrare (B,β), atunci este aceeași cu singura soluție de intrare (A,α).

Exemplu

Crearea vectorului B din vectorul A [18] .

Fie dat un vector supercrescent (cheie secretă) cu . Suma componentelor sale este 55 205. Alegeți și . Atunci condiția este îndeplinită. $A=(103,107,211,430,863,1718,3449,6907,13807,27610)$ $n=10$ $m=55207$ $t=25236$ $(t,m)=1$

Se găsește după formula . În acest caz: $t^{-1}modm$ $(tu)modm=1$

1061 * 25236 - 1= 485 * 55207

Prin urmare . $t^{-1}=u=1061$

Cheia publică B este calculată de și α =(uβ,modm). De exemplu, pentru $b_{i}=(ta_{i},modm)$ ${\displaystyle a_{1},a_{6},a_{10))$

$b_{1}=103*25236=4579+47*55207=4579$ și α1 = 1061 * 4579 = 103 + 88 * 55 207 = 103,

$b_{6}=1718*25236=17953+785*55207=17953$ și α6 = 1061 * 17 953 = 1718 + 345 * 55 207 = 1718,

$b_{10}=27610*25236=53620+12620*55207=53620$ și α10 = 1061 * 53 620 = 27 610 + 1030 * 55 207 = 27 610

După ce au făcut calcule similare pentru elementele rămase, se obține un vector $B=(4579,50316,24924,30908,27110,17953,32732,16553,22075,53620)$

Criptare

Aplicați cheia publică B și criptați mesajul: DEATH GODS EAT ONLY APPLES

Codificarea numerică este folosită mai întâi, spațiului i se atribuie valoarea 0, literelor de la A la Z li se atribuie valoarea de la 1 la 26. Codurile numerice sunt exprimate în seturi binare. Deoarece vectorul B are lungimea de 10, poate fi folosit pentru a cripta blocuri de două litere simultan. Codul de bloc, ca și înainte, se obține prin însumarea greutăților articolelor incluse în rucsac. $b_{i}$

Bloc de text sursă	cod binar	Cod de blocare
DE	00100 00101	95097
LA	00001 10100	61616
H	01000 00000	50316
MERGE	00111 01111	207922
D.S.	00100 10011	118572
E	00000 00101	70173
LA	00001 10100	61616
O	00000 01111	124980
NL	01110 01100	155433
Y	11001 00000	82005
AP	00001 10000	45063
PL	10000 01100	53864
ES	00101 10011	149480

Decriptare

Să descifrăm primul număr 95 097. Merită remarcat faptul că

1061*95097 = 1827*55207 + 34728

Se ia în considerare problema rucsacului (A.34728). Soluția se obține prin vizualizarea vectorului rucsac A de la dreapta la stânga. Când numărul din coloana din stânga nu este mai mic decât componenta A vizualizată în prezent, se scrie 1, iar noul număr din coloana din stânga se obține prin scăderea componentului din numărul anterior. În caz contrar, se scrie 0 și numărul din coloana din stânga nu se modifică. Rezultatul este prezentat în tabel:

Număr	Componenta A	Simbol
34728	27610	unu
7118	13807	0
7118	6907	unu
211	3449	0
211	1718	0
211	863	0
211	430	0
211	211	unu
0	107	0
0	103	0

Citirea coloanei din dreapta de jos în sus are ca rezultat vectorul binar 00100 00101, adică DE.

Să presupunem că am încercat să acționăm în ordine inversă. Criptarea ar fi efectuată folosind vectorul A și s-ar obține un anumit număr a. Dar atunci perechea (B,a) nu a avut o soluție, deoarece egalitatea obișnuită a numerelor nu poate fi dedusă din modul lor de egalitate.

Securitate

Siguranța sistemelor de rucsac

Pentru vectorii de rucsac mici, problema rucsacului este ușor de rezolvat chiar și manual. Un rucsac adevărat ar trebui să conțină un număr mare de elemente. Deschiderea unui astfel de rucsac cu forță brută, adică spargerea, va fi o sarcină dificilă (imposibilă). Cu toate acestea, sistemele de rucsac nu sunt sigure pentru criptoanaliza . Shamir și Zippel ( ing. Zippel ) au descoperit că, cunoscând numerele ( „lacună secretă” ), puteți restabili un vector supracrescător dintr-un vector normal deschis [3] . Important este că numerele („perechea secretă”) nu trebuie să fie neapărat aceleași cu cele folosite atunci când sistemul a fost creat de utilizatorul legal. Este suficient să găsim orice pereche , astfel încât să ne dea un vector supercrescent [20] . $t,t^{-1},m$ $A$ $B$ $t,m$ $(t',m')$ $B*(t'modm')$

Cum să cauți o portiță secretă

Problemă: Se știe că un vector de rucsac este folosit ca cheie publică. Se obține din A, un vector supracrescător, prin înmulțire modulară puternică față de modulul m și numărul t. Trebuie să găsim A,t,m care nu ne sunt cunoscute, sau mai degrabă m și (putem calcula A din ele). Cunoscându-le, se poate decripta criptotextul [21] . $B=(b_{1},...,b_{n})$ $t^{-1}=u$

Găsirea perechii secrete

Abordarea descrisă mai jos a fost propusă de A. Shamir . Algoritmul rezultat va rula în timp polinomial. Cu toate acestea, ar trebui să fiți atenți în alegerea mărimii vectorului B în raport cu care algoritmul este polinom. Merită să ne amintim că dimensiunea vectorului B depinde de numărul de componente n și de dimensiunea lui . Prin urmare, există restricții privind alegerea lor. $b_{i}$

Fixăm constanta de proporționalitate și componentele vectorului supercrescent A, constând din biți. Deoarece cea mai semnificativă cifră din fiecare dintre componente este una, atunci A este în creștere și m este ales să fie mai mare decât suma componentelor vectorului de rucsac A [20] . $d>1$ $a_{i},i=[1,n]$ $[dn]-1-n+i$

Pentru a construi un algoritm, nu este necesar să căutați u și m utilizate efectiv pentru criptare. Orice pereche (u, m) va face, să o numim o pereche secretă , satisfăcând restricțiile privind înmulțirea modulară puternică în raport cu B, că vectorul A este supercrescător ca urmare a acestei înmulțiri și m este mai mare decât suma lui componentele sale. După ce găsim cel puțin o pereche secretă, aplicăm lema și începem decriptarea. Existența sa este evidentă, deoarece creatorul criptosistemului a folosit o astfel de pereche la criptare.

Pentru claritate, construim grafice ale funcțiilor . Acestea sunt segmente drepte cu puncte de discontinuitate , . $b_{i}u$ $(modm)$ $u=pm/b_{i}$ $p=1,2,...$

Amintindu-ne ca vom scrie: $b_{i}=(ta_{i},modm)$ $t^{-1}=u$

$(b_{1}u,modm)=a_{1}$ , unde este factorul invers dorit, este prima componentă a vectorului , este, prin presupunere, foarte mică în comparație cu . Aceasta înseamnă că valoarea este aproape de minimul funcției . $u$ $a_{1}$ $A$ $m$ $u$ $b_{1}$

Pentru , valoarea este apropiată de minimul funcției . Apoi cele două minime ale funcțiilor și sunt apropiate una de alta. Astfel, pot fi luate în considerare și restul curbelor dinților de ferăstrău. Este clar că minimele tuturor acestor curbe sunt apropiate unele de altele. Este posibil să se construiască un interval mic care să conţină „punctele de acumulare” a minimelor curbelor dinţilor de ferăstrău [22] . Pe baza acestui mic interval se găsește și valoarea perechii secrete. $(b_{2}u,modm)=a_{2}$ $u$ $b_{2}$ $b_{1}$ $b_{2}$ $n$ $u$

Deoarece nu cunoaștem valoarea modulului, vom schimba scara figurii astfel încât să devină egală cu 1 (împărțiți toate lungimile la ). $m$ $m$ $m$

Algoritm pentru găsirea unei perechi secrete:

1) Găsirea candidaților pentru întregul astfel încât al- lea minim al funcției să fie punctul de acumulare dorit. $p$ $p$ $b_{1}$

Pentru ca numărul de candidați să nu fie prea mare, introducem un parametru fix - numărul maxim de candidați permis. $r$

În prima parte a algoritmului, nu este necesar să se ia în considerare toate odată ; ar trebui să introduceți un parametru și să luați în considerare componenta. $b_{2},...,b_{n)$ $s<n$ $s$

$p/b_{1)$ -coordonata minimului --lea de pe curba . $u$ $p$ $b_{1}$

Condiția pentru proximitatea minimelor curbelor și poate fi scrisă ca următoarele inegalități: $b_{1}$ $b_{2}$

$-e<p/b_{1}-q/b_{2}<e$ ,

$1\leq p\leq b_{1}-1$ , $1\leq q\leq b_{2}-1$

Înmulțiți prima inegalitate cu : $b_{1}b_{2)$

$-E<pb_{2}-qb_{1}<E$ .

În total, astfel de inegalități , câte una pentru fiecare $s-1$ $b$

Deci, prima parte a algoritmului oferă toate astfel de naturi pentru care există naturi astfel încât toate inegalitățile sunt satisfăcute. $p$ $q$ $s-1$

2) Verificarea succesivă a fiecăruia dintre candidați.

În a doua parte a algoritmului, toate sunt verificate . Candidatul va fi respins dacă pentru unii nu există un minim al curbei situat în apropierea --lea minim al curbei . $i=[2,n]$ $p$ $i$ $b_{i}$ $p$ $b_{1}$

Fix . Aranjați în ordine crescătoare toate punctele de întrerupere din interval . Să luăm două puncte adiacente din lista sortată și . În intervalul format de acestea , fiecare curbă este un segment de linie dreaptă (ecuația descrie aceste segmente). $p$ $[p/b_{1},(p+1)/b_{1}]$ $x_{i}$ $x_{i}+1$ $[x_{i},x_{i}+1]$ $b_{i}$ $b_{i}u-const_{i}^{j)$

Pe baza celor de mai sus, scriem sistemul de inegalități:

$x_{j}\leq u\leq x_{j}+1$

$\sum _{i=1}^{n}(b_{i}u-const_{i}^{j})<1$

$(b_{1}u-const_{1}^{j})+(b_{2}u-const_{2}^{j})+...+(b_{i}-1u-const_ {i-1}^{j})<(b_{i}u-const_{i}^{j})$ $i=[2,n]$ - starea de creștere excesivă

Pentru două numere și pentru a forma o pereche secretă, este necesar și suficient ca aceasta să aparțină intervalului astfel construit pentru o pereche . , candidatul din prima parte a algoritmului și indicele de puncte din lista sortată de puncte corespunzătoare . $u$ $m$ $u/m$ $(p,j)$ $p$ $j$ $p$

Căutarea se va încheia când se găsește un interval nevid . $[x_{i},x_{i}+1]$

Exemplul [23] .

Lăsați cheia publică să aibă trei componente $B=(7,3,2)$

1) Conform inegalităților de mai sus:

$-E<3p-7q<E$ ,

$-E<2p-7q<E$

$1\leq p\leq 6$ , , . $1\leq q\leq 2$ $r=1$

Tabelul prezintă cele mai mici valori, astfel încât inegalitățile să fie valabile: $E$

p	unu	2	3	patru	5	6
E	5	3	2	2	3	5

2) Se poate observa că toate valorile sunt candidați potriviți (în cazul general, acesta poate să nu fie cazul). Prin urmare, împărțim intervalul în sub-intervale: astfel încât toate cele trei curbe să fie segmente drepte în fiecare interval redus. $p$ $(0,1)$ $(0,1/7),(1/7,2/7),(2/7,1/3),(1/3,3/7),(3/7,1/2),(1/2,4/7),( 4/7,2/3),(2/3,5/7),(5/7,6/7),(6/7,1)$ $b_{i}$ $(b_{i}u-const_{i}^{j})$

Să scriem inegalitățile:

$(7u-i')+(3u-i'')+(2u-i''')<1$

$7u-i'<3u-i''$

$(7u-i')+(3u-i'')<(2u-i''')$

Constantele se modifică în , , în funcție de alegerea intervalului. $0\leq i\leq 6$ $0\leq i'\leq 2$ $0\leq i'''\leq 1$

Folosind notația , , rescriem inegalitățile într-o formă mai simplă: $i=1+i'+i''+i'''$ $j=i'-i''$ $k=i'+i''-i'''$

$12u<i,4u<j,8u<k$

Să colectăm în tabel toate valorile constantelor pentru diferite intervale:

Interval	1/7	2/7	1/3	3/7	1/2	4/7	2/3	5/7	6/7	unu
eu	0	unu	2	2	3	3	patru	patru	5	6
i	0	0	0	unu	unu	unu	unu	2	2	2
i	0	0	0	0	0	unu	unu	unu	unu	unu
i	unu	2	3	patru	5	6	7	opt	9	zece
j	0	unu	2	unu	2	2	3	2	3	patru
k	0	unu	2	3	patru	3	patru	5	6	7
12u<i	PARTE	PARTE	NU	NU	NU	NU	PARTE	NU	PARTE	NU
4u<j	NU	PARTE	SAT	NU	SAT	NU	SAT	NU	PARTE	SAT
8u<k	NU	NU	NU	PARTE	SAT	NU	NU	NU	PARTE	PARTE

Ultimele trei linii indică dacă fiecare dintre inegalități este adevărată sau nu: SAT - adevărat, PART - parțial adevărat (apare când inegalitatea este adevărată în partea dreaptă a subintervalului), NOT - nu este adevărat (apare când inegalitatea nu este adevărată). adevărat în partea stângă a subintervalului).

Un interval generează o pereche secretă dacă și numai dacă toate cele trei dintre SAT sau PART sunt în coloană. Singurul astfel de interval Alegând un număr din interval, de exemplu (adică ), obținem un vector super-crescător . $(5/7,3/4)$ $8/11$ $m=11$ $A=(1,2,5)$

Variante ale problemei rucsacului în criptografie

1) Rucsac Merkle-Hellman ( ing. Merkle-Hellman Cryptosystem ).

Cheia publică A este un vector supracrescător, cheia secretă B se obține din A prin multiplicare modulară puternică.

2) Rucsacul lui Graham-Shamir ( ing. Graham-Shamir Cryptosystem ) [5] .

Cheia publică A este un vector supracrescător. Elementele sale sunt scrise în reprezentare de biți. În continuare, sunt generate numere aleatorii, numite zgomot. Reprezentarea lor de biți este adăugată la biții vectorului rucsac din stânga, adică în bitul cel mai semnificativ.

Să presupunem că alegem vectori . Adăugăm în el prefixe din numere selectate aleatoriu: $A=(1,3,5)$

reprezentare binară	cu prefix aleatoriu
1=001	101 001 = 41
3=011	111 011 = 59
5 = 101	100 101 = 37

Vectorul de rucsac rezultat nu are proprietatea de supra-creștere. Prin urmare, adăugarea de zgomot aleatoriu ascunde proprietatea de supracreștere a vectorului original A și circuitul devine mai sigur [24] . $(41,59,37)$

3) Rucsac Morii-Kasahara ( ing. Morii-Kasahara Cryptosystem ) [10]

Schema este similară cu schema Merkle-Hellman, dar folosind o metodă de criptare multiplicativă atât pentru cheia publică, cât și pentru secret.

Fie vector . Alegem , un număr prim (în această schemă ) și , astfel încât . Cheia secretă B se obține de la A prin formula , adică . Lasă mesajul să fie criptat , apoi cifrul . $A=(5,6,7)$ $m=211>5*6*7=210$ $p=211$ $p=m$ $e=19$ $gcd(e,p-1)mod(p-1)=1$ $b_{i}=a_{i}^{e}modp$ $B=(114,66,85)$ $(100)$ $114^{1}*66^{0}*85^{0}=144mod211$

4) Rucsac Goodman -McAuley Cryptosystem [ 8] .

Ca și în prima schemă din rucsacul Goodman-McCauley, înmulțirea modulară este folosită pentru a obține cheia publică din secret, dar cheia secretă nu este un vector supracrescător. Schema se bazează pe complexitatea factorizării întregi, prin urmare este similară cu criptosistemul RSA.

5) Rucsac Nakashe-Stern ( ing. Naccache-Stern Cryptosystem ) [14] .

Această schemă combină două metode: rucsacul Merkle-Hellman și algoritmul Polyg-Hellman . Având în vedere un număr prim , S este o submulțime ( ing. subset product ) și un vector de rucsac , unde toate sunt numere prime relativ. Trebuie să găsim un vector binar astfel încât $p$ $A=(a_{1},a_{2},...a_{n})$ $a_{i}$ $x=(x_{1},...,x_{n})$ $\displaystyle \prod _{i=1}^{n}a_{i}^{x_{i}}mpdp=S$

6) Rucsac Shor-Rivest ( ing. Chor-Rivest ) [24] [25]

Bazat pe algebra în câmpuri finite (câmpuri Galois) . Fie cheia publică A să fie formată din elemente ale subcâmpului câmpului , adică . Cheia secretă constă din următoarele elemente: $q=p^{h)$ $GF(p)$ $GF(q)$ $(a_{1},a_{2},...a_{p})=GF(p)\in GF(q)$

element de cu grad algebric $t$ $GF(q)$ $h$
generator de la $g$ $GF^{*}(q)$
întreg de $d$ $\mathbb {Z} (q-1)$

Atunci cheia publică B este formată din elementele [5] . $b_{i}=d+\log _{g}(t+a_{i})mod(q-1)$

Viitorul sistemelor de rucsacuri

Astăzi, atenția principală a criptografilor se concentrează asupra criptosistemelor bazate pe factorizarea întregilor , logaritmul discret și curbele eliptice . Cu toate acestea, cercetările asupra sistemelor de rucsac continuă, dar astfel de criptosisteme nu sunt populare și nu inspiră încredere, având în vedere eșecurile algoritmilor anteriori. Dacă se poate crea un algoritm care să exploateze pe deplin dificultatea problemei rucsacului (NP-completitudine), cu densitate mare și cu lacune secrete greu de descoperit, atunci acesta va fi un sistem mai bun decât sistemele bazate pe factorizarea întregilor și logaritmul discret (lor Completitudinea NP nu a fost dovedită). În plus, acest sistem va fi rapid, ceea ce înseamnă că va putea concura în viteză cu sistemele clasice de cheie publică [5] .

Pentru o greutate de rucsac, o iterație a algoritmului Merkle-Hellman poate fi de peste 100 de ori mai rapidă decât RSA (cu un modul de 500 de biți) [26] . $n=100$

Note

↑ Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
↑ 1 2 3 4 5 Schnaer, 2002 , p. 19.1.
↑ 1 2 3 4 5 Schnaer, 2002 , p. 19.2.
↑ Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Securitatea informației : manual - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
↑ 1 2 3 4 5 6 7 8 Kin Ming Lai. Criptosisteme de rucsac: trecutul și viitorul . — 2001.
↑ . Math Matrix (engleză) . — 2001.
↑ Publicații _ _ (link indisponibil)
↑ 1 2 Un nou criptosistem cu cheie publică de rucsac cu trapă . — Springer.
↑ Jacques Stern- Articol Wiki . — Springer.
↑ 1 2 Masakatu Morii, Masao Kasahara. Nou criptosistem cu cheie publică care utilizează logaritmi discreti peste GF(p ) . — Springer.
↑ Shinya Kiuchi, Yasuyuki Murakami, Masao Kasahara. Noi Criptosisteme Multiplicative cu Cheie Publică de tip Rucsac .
↑ Hussain Ali Hussain, Jafar Wadi Abdul Sada , Klipha SM Nou criptosistem cu cheie publică de rucsac cu mai multe etape . Arhivat din original pe 26 decembrie 2014.
↑ Harald Ritter. Ruperea criptosistemelor de rucsac prin enumerarea l-Norm . Arhivat din original la 31 martie 2012.
↑ 1 2 Davis Naccache, Jacques Stern. Un nou criptosistem cu cheie publică . — 2006.
↑ Despre securitatea rucsacului îmbunătățit al criptosistemului .
↑ A fost dezvoltat un algoritm de protecție a datelor pe care nici computerele cuantice nu îl pot sparge . Preluat la 2 noiembrie 2015. Arhivat din original la 17 august 2015. (nedefinit)
↑ Salomaa, 1990 , p. 76.
↑ 1 2 3 4 Salomaa, 1990 , p. 103.
↑ Salomaa, 1990 , p. 104.
↑ 1 2 Salomaa, 1990 , p. 113.
↑ Salomaa, 1990 , p. 112.
↑ Salomaa, 1990 , p. 114.
↑ Salomaa, 1990 , p. 117.
↑ 1 2 B. Chor, R. L. Rivest. Un criptosistem cu cheie publică de tip rucsac bazat pe aritmetică în câmpuri finite . — 1988.
↑ Serge Vaudenay. Criptanaliză a Criptosistemului Chor-Rivest . (link indisponibil)
↑ A. M. Odlyzko. Ascensiunea și căderea criptosistemelor de rucsac .

Literatură

in rusa

Levitin A. V. Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 160-163. — 576 p. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: constructie si analiza = Introduction to Algorithms. - al 2-lea. - M .: „Williams” , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Robert Sedgwick . Algoritmi fundamentali în C++. Părțile 1-4. Analiză. Structuri de date. Triere. Căutare = algoritmi în C++. Părțile 1-4. fundamentale. structuri de date. Triere. In cautarea. - al 3-lea. - Rusia, Sankt Petersburg: „DiaSoft” , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Probleme aplicate ale teoriei grafurilor. - M. , 1974. - 232 p.
V. N. Burkov, D. A. Novikov. Elemente ale teoriei grafurilor . - 2001. - S. 28.
S. Okulov. Programare în algoritmi. - 2007. - S. 383.
B. Schneier. Criptografie aplicată . - al 2-lea. - 2002. Arhivat 28 februarie 2014 la Wayback Machine
A. Salomaa. Public Key Cryptography = Public-Key Cryptography. - Springer-Verlag, 1990. - S. 102-150. Arhivat pe 19 noiembrie 2011 la Wayback Machine
Koblitz N. Curs de teoria numerelor și criptografie - ediția a II-a - M. : Editura științifică TVP , 2001. - 254 p. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5

în limba engleză

Silvano Martelo, Paolo Toth. Probleme la rucsac. - Wiley, 1990. - 306 p.
David Pisinger. Probleme la rucsac . - 1995. Arhivat 22 decembrie 2012 la Wayback Machine
Hans Kellerer, Ulrich Pferschy, David Pisinger. Probleme la rucsac. — 1995.

Link -uri

Denis Alekseev. Algoritm de rucsac . Yandex.People . _ Data accesului: 6 decembrie 2012. Arhivat din original pe 7 ianuarie 2013. (Rusă)
Mihail Chegodar. Utilizarea criptografiei în materie de protecție a datelor, pe exemplul unui sistem de criptare în rucsac . Centrul de informare subteran. Preluat: 6 decembrie 2012. (Rusă)

Problema rucsacului
Aplicații	Problemă la rucsac în criptografie Sarcina de tăiere
Criptosisteme bazate pe problema rucsacului	Merkla-Hellman Naccasha - Pupa Graham - Shamira
În plus	Lista sarcinilor despre rucsac