Rygsækproblemet i kryptografi

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 1. maj 2020; checks kræver 4 redigeringer .

Rygsækproblemet (eller rygsækproblemet ) i kryptografi ( eng. Knapsackproblem ) er et problem, på grundlag af hvilket de amerikanske kryptografer Ralph Merkle og Martin Hellman udviklede den første offentlige nøglekrypteringsalgoritme . Det kaldes Merkle-Hellman-kryptosystemet. Til at kryptere meddelelser brugte vi løsningen af rygsækproblemet, som er kendt for at være NP-hårdt . Derfor mente man, at det kunne sikre systemets kryptografiske stabilitet. I øjeblikket er der skabt mange rygsækkryptosystemer. Men næsten alle eksisterende i dag er hacket eller anerkendt som potentielt usikre.

Historie

Rygsækproblemet er kernen i den første asymmetriske krypteringsalgoritme (eller på anden måde offentlig nøglekryptering). Ideen om offentlig nøglekryptografi blev fremsat af de amerikanske kryptografer Whitfield Diffie , Martin Hellman og uafhængigt af Ralph Merkle . Det blev første gang præsenteret af Diffie og Hellman ved National Computer Conference i 1976, samme år som deres fælles arbejde om dette emne, New Directions in Cryptography, blev offentliggjort . ) [1] . Merkles artikel "Sikker kommunikation over usikre kanaler" blev først offentliggjort i 1978 [2] . Det nye i forhold til de symmetriske kryptosystemer , der var almindelige på det tidspunkt, var brugen af parrede nøgler - hemmelige ( eng. private key, secret key, SK ) og public ( eng. public key, PK ), skabt af brugeren. Den hemmelige nøgle, der bruges til at dekryptere informationen, skal holdes hemmelig af brugeren, mens den offentlige nøgle, som kun er nødvendig for kryptering, kan offentliggøres. I mange kryptosystemer hentes den offentlige nøgle fra den hemmelige nøgle [3] [4] .

Den første krypteringsalgoritme baseret på rygsækproblemet blev udviklet af Merkle og Hellman i 1978 og blev kaldt " Merkle-Hellman Algorithm " [3] . Den blev udgivet i enkelttrins ( engelsk single- iterated ) og multi-stage versioner ( engelsk multiply-iterated ). Algoritmen kunne kun bruges til kryptering, men den israelske kryptoanalytiker Adi Shamir tilpassede den til brug i digitale signaturer [3] . Efter at ordningen blev offentliggjort, tilbød Merkle en belønning på 100 dollars til enhver, der med succes knækkede et-trins-algoritmen. I 1982 udførte Shamir et vellykket angreb og modtog den lovede belønning. Men selv efter at have betalt det, var Merkle overbevist om flertrinssystemets kryptografiske styrke og tilbød 1.000 dollars , hvis det blev knækket. I 1984 lykkedes det den amerikanske matematiker Ernest Brickell at gennemføre et hack til en 40-trins variant på lidt over 1 time på en Cray-1 maskine [5] [6] .

Uafhængigt af hinanden opdagede den amerikanske matematiker Ron Graham og Adi Shamir tilbage i 1980 en måde at øge den kryptografiske styrke af Merkle-Hellman-skemaet, men allerede i 1983 blev det resulterende Graham-Shamir-skema knækket af den amerikanske videnskabsmand Leonard Adleman . Men søgen efter ændringer uden manglerne ved Merkle-Hellman-ordningen fortsatte. I 1985 skabte den britiske lektor Rodney Goodman og den amerikanske ingeniør Anthony McAuley et kredsløb baseret på modulære rygsække med et hemmeligt smuthul, der ikke var baseret på supertiltagende vektorer , men ved hjælp af den kinesiske restsætning [7] [8] .

Efterfølgende stod det klart, at ordningen var sårbar over for angreb baseret på eftersøgningen efter hemmelige smuthuller. Men i 1990 foreslog Valtteri Niemi en ny ordning baseret på den samme opgave som en modulær rygsæk. Det blev knækket allerede næste år af Chi Ye Meng , Antoine Zhu og Jacques Stern [9] uafhængigt af hinanden, ved hjælp af lidt forskellige metoder. Udover brugen af modulære rygsække, har der været forsøg på at bruge andre typer rygsække.

Så i 1986 udgav Harald Niederreiter et rygsæk - kryptosystem baseret på algebraisk kodningsteori, som senere blev brudt, og i 1988 udviklede Masakatsu Morii og Masao Kasahara et rygsæk-kryptosystem ved hjælp af en multiplikativ rygsæk [10] . Denne idé viste sig at være en succes, og indtil videre er systemet på multiplikative rygsække ikke blevet hacket.

I 2001 foreslog Shinya Kiuchi , Yasuyuki Murakami og Masao Kasahara en forbedring af Moriya-Kasahara-ordningen baseret på multiplikative knapsække ved hjælp af Schalkwijk-algoritmen [11] .

Også en succes var idéen fra Hussein Ali Hussein , Jafar Wadi Abdul Sad og M. Khalifa , som i 1991 foreslog et flertrins rygsæk-kryptosystem ( engelsk multistage trapdoor knapsack cryptosystem ). Den fikserer rygsækvektoren for hvert trin, og outputtet (chiffertekst) efter hvert trin i algoritmen bruges som input (tekst) til næste trin. Der kendes ikke noget vellykket angreb på denne ordning (fra 2001) [12] .

Qu Minghua og Scott Vanstone foreslog i 1992 et hybridkryptosystem, der primært er baseret på rygsækproblemet, men som også inkluderer logaritmiske signaturer. I 1994 viste R. Blackburn , Murphy, Sean og Jacques Stern , at en forenklet version af U-Waston-kryptosystemet ikke er sikker. Disse kryptosystemer blev undersøgt mere grundigt af Fong Nguyen og Jacques Stern i 1997 [5] .

Forbedringer af den klassiske Merkle-Hellman-algoritme fortsatte også. I 1994 foreslog Orton en ændring af flertrins Merkle-Hellman-ordningen, men to år senere blev den hacket af Ritter [13] .

I 1995 blev to nye tilgange til problemet foreslået på én gang. Den første, baseret på diofantiske ligninger , skyldes Lin Zhuxing , Zhang Zhencheng og Li Jia Tong . Næsten øjeblikkeligt viste Lai Qisong og Blackburn, Murphy, Sean og S. G. Paterson uafhængigt af hinanden, at dette kryptosystem ikke er sikkert.

Anden tilgang, baseret på det multiplikative ranselproblem, blev foreslået af David Naccache og Jacques Stern [14] . Nakkashe og Stern tilbød DM 1024 til en person, der med succes knækkede deres kryptoskema, men der var ingen oplysninger om, at nogen har modtaget denne belønning endnu (fra 2001) [5] .

I 1996 foreslog Kunikatsu Kobayashi og Masaki Kimura et forbedret rygsækkryptosystem baseret på et nyt koncept, hvor afsenderen kan vælge en krypteringsnøgle fra et helt sæt nøgler. To år senere viste Hidenori Kuwakado og Hatsukazu Tanaka , at systemet potentielt var usikkert [15] .

Den sidste version af algoritmen blev foreslået af B. Shor og R. L. Rivest i 2006. I 2002 blev Chor-Rivest-algoritmen betragtet som sikker [3] .

I 2015 blev det rapporteret, at Nathan Hamlin og William Webb fra Washington State University havde skabt en rygsækalgoritme uden manglerne ved tidligere implementeringer [16] .

Siden da er der blevet foreslået mange offentlige nøglealgoritmer, som ikke er baseret på rygsæksystemer. De mest berømte af dem er: RSA , EIGamal og Rabin . De kan bruges til både kryptering og digitale signaturer. De er dog langsomme og ikke egnede til hurtig kryptering/dekryptering af store mængder meddelelser. Løsningen på dette problem er hybride kryptosystemer, beskeder krypteres med en hurtig symmetrisk algoritme med en tilfældig nøgle, og den offentlige nøglealgoritme bruges til at kryptere selve den tilfældige (sessions) nøgle.

Udtalelse af problemet

Rygselproblemet er som følger: givet et sæt forskellige positive heltal. Lad der være et tal , der også er heltal og positivt. Opgaven er at finde sådan et sæt , som de tæller helt præcist . Det er klart, at der ikke altid findes en løsning på dette problem. $A=(a_{1},...,a_{n})$ $n$ $k$ $a_{i}$ $k$

Ifølge definitionen af offentlige nøglesystemer skal du have to nøgler for at kryptere/dekryptere. Den legitime modtager af beskeden kender den hemmelige nøgle A, mens afsenderen kun har den offentlige nøgle B. Hvordan kan du forhindre en angriber i at dekryptere beskeden, hvis han kender den offentlige nøgle? Svaret er enkelt, den offentlige nøgle skal afledes fra den private nøgle ved hjælp af en transformation f, der har følgende to egenskaber [17] :

Det er nemt at beregne velkendende $B=f(A)$ $EN$
At bestemme , vide , er sandsynligvis en vanskelig opgave. $A=f^{-1}(B)$ $B$

Som vanskelige problemer betragtes normalt NP-komplette problemer, så rygproblemet er velegnet til at bygge offentlige nøglesystemer.

Kryptering med rygsækproblemet

Beskeden er krypteret som en løsning på et sæt rygproblemer [2] .

Def. En rygsækvektor er et ordnet sæt af n elementer [18] .

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

For at kryptere klarteksten i binær repræsentation er den opdelt i længdeblokke ( svarer for eksempel til 5 genstande i en rygsæk). Det menes, at man angiver tilstedeværelsen af en genstand i rygsækken, og nul angiver dens fravær. Der er to måder at kryptere på: $n$ $(11100)$

1) Beskedkrypteringen opnås ved at hæve elementerne i rygsækvektoren til styrken af bits af den krypterede meddelelse, der svarer til dem, og yderligere multiplicere resultaterne, det vil sige, hvis , og meddelelsen , så vil chifferen være antallet . Denne metode kaldes multiplikativ [5] . $A=(2,3,5)$ $(100)$ $2^{1}*3^{0}*5^{0}=2$

2) Beskedkrypteringen opnås ved at multiplicere elementerne i rygsækvektoren med den tilsvarende bit af den krypterede meddelelse og derefter tilføje resultaterne, det vil sige, hvis , og meddelelsen , så vil chifferen være tallet . Denne metode kaldes additiv [5] . $A=(2,3,5)$ $(100)$ $2*1+3*0+5*0=2$

Et eksempel på en chiffertekst opnået ved hjælp af en additiv algoritme.

Lad en rygsækvektor Α = (3 4 6 7 10 11) med længden n = 6 gives.

simpel tekst	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0	0 0 0 0 0 1
ting i en rygsæk	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11
chiffertekst	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	elleve

For en given Α er alle kryptosystemer tal, der ikke overstiger 41, den samlede vægt af alle genstande i rygsækvektoren. Der er kun én kryptotekst for hver almindelig tekst.

Kompleksiteten af chifferen ligger i, at der er to problemer med rygsækken: "let" og "hårdt". Et "let" problem kan løses i lineær tid, et "hårdt" kan ikke. Den offentlige nøgle er et "hårdt" problem, fordi den er nem at bruge til at kryptere og umulig at dekryptere en besked. Den private nøgle er et "nemt" problem, da det gør det nemt at dekryptere beskeden. I mangel af en privat nøgle skal det "hårde" rygproblem løses. Merkle og Hellman udviklede ved hjælp af modulær aritmetik en måde at omdanne en "let" rygsæk til en "svær" en [2] .

"Nemt" problem

For nogle vektorer Α er rygsækproblemet let at løse. Supervoksende vektorer har denne egenskab [2] .

Def. En rygsækvektor kaldes supergrowing , hvis for , dvs. hvert medlem af sekvensen er større end summen af de foregående [18] .

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

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

j=2,...,n

Eksempel

Lad den samlede vægt af rygsækken og rygvektoren angives som supergrowing . $P=70$ $A=(2,3,6,13,27,52)$

For denne rygsækvektor er algoritmen til at løse rygsækproblemet enkel. Den største vægt tages, 52. Da 52 < 70, lægges den tilsvarende vare i rygsækken. Fri plads i rygsækken blev lig med 70 - 52 = 18. Dernæst skal du tage en vare med en vægt på 27. Da 27 > 18 kommer denne vare ikke med i rygsækken. Den tredje vare med en vægt på 13 < 18 passer i rygsækken, hvilket giver 5 ledig plads. Den næste vare med en vægt på 6 passer ikke. Tilsvarende lægges genstande med vægt 2 og 3 i en rygsæk. Rygsækkens restvægt er blevet til 0, løsningen er fundet!

Det "hårde" problem

En normal rygsæk er ikke med en supertiltagende rygvektor A. Den eneste måde at løse et sådant problem på er at teste alle mulige indtil den rigtige løsning er fundet. Den hurtigste algoritme har en eksponentiel afhængighed af antallet af elementer [2] .

Et offentligt nøglekryptosystem baseret på rygsækproblemet

Som før er vektoren A den hemmelige nøgle, og vektoren B er den offentlige nøgle.

Oprettelse af en offentlig nøgle fra en privat

For heltal og betegne . $x$ $m\geq 2$ $(x,modm)=x-[x/m]m$

Lad være en supertiltagende rygsækvektor. Lad os introducere et heltal og et naturligt tal , således at den største fælles divisor er . $A=(a_{1},...,a_{n})$ ${\displaystyle m>\sum _{i=1}^{n}a_{i))$ $t<m$ $(t,m)=1$

Def. Hvis sådan, at for , så siger vi, at det er opnået fra stærk modulær multiplikation [18] .

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

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

i=1,..,n

B

EN

Skaberen af kryptosystemet vælger parametrene , så A er supergrowing og B opnås fra A ved stærk modulær multiplikation med hensyn til m og t. $A,B,t,m$

Gyldigt Lemma [19] : Lad A være en supervoksende vektor, og B opnås fra A ved stærk modulær multiplikation med hensyn til m og t. Antag, at u = 1/t, β er et vilkårligt naturligt tal, og α =(uβ,modm). Så er det rigtigt, at:

Rygsækproblemet med inputdata (A,α) kan løses i lineær tid, og hvis der findes en løsning, så er den unik;
Rygsækproblemet med inputdata (B,β) har højst én løsning;
Hvis der er en indgangsløsning (B,β), så er den den samme som den eneste indgangsløsning (A,α).

Eksempel

Oprettelse af vektor B ud fra vektor A [18] .

Lad en supervoksende vektor (hemmelig nøgle) med gives . Summen af dets komponenter er 55 205. Vælg , og . Så er betingelsen opfyldt. $A=(103,107,211,430,863,1718,3449,6907,13807,27610)$ $n=10$ $m=55207$ $t=25236$ $(t,m)=1$

Det findes i henhold til formlen . I dette tilfælde: $t^{-1}modm$ $(tu)modm=1$

1061 * 25236 - 1= 485 * 55207

Derfor . $t^{-1}=u=1061$

Den offentlige nøgle B beregnes af og α =(uβ,modm). For eksempel for $b_{i}=(ta_{i},modm)$ ${\displaystyle a_{1},a_{6},a_{10))$

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

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

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

Efter at have foretaget lignende beregninger for de resterende elementer, opnås en vektor $B=(4579,50316,24924,30908,27110,17953,32732,16553,22075,53620)$

Kryptering

Anvend den offentlige nøgle B og krypter meddelelsen: DØDSGUDER SPISER KUN ÆBLER

Numerisk kodning bruges først, mellemrummet tildeles værdien 0, bogstaverne A til Z tildeles værdien 1 til 26. Numeriske koder er udtrykt i binære mængder. Da vektor B har længde 10, kan den bruges til at kryptere blokke med to bogstaver på én gang. Blokkoden fås som før ved at summere vægten af de varer, der er inkluderet i rygsækken. $b_{i}$

Kildetekstblok	binær kode	Bloker kode
DE	00100 00101	95097
PÅ	00001 10100	61616
H	01000 00000	50316
GÅ	00111 01111	207922
D.S.	00100 10011	118572
E	00000 00101	70173
PÅ	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

Dekryptering

Lad os dechifrere det første tal 95 097. Det er værd at bemærke det

1061*95097 = 1827*55207 + 34728

Rygsækproblemet (A.34728) overvejes. Løsningen fås ved at se rygsækvektoren A fra højre mod venstre. Når tallet i venstre kolonne ikke er mindre end den aktuelt viste komponent A, skrives 1, og det nye tal i venstre kolonne fås ved at trække komponenten fra det foregående tal. Ellers skrives 0 og tallet i venstre kolonne ændres ikke. Resultatet er vist i tabellen:

Nummer	Komponent A	Symbol
34728	27610	en
7118	13807	0
7118	6907	en
211	3449	0
211	1718	0
211	863	0
211	430	0
211	211	en
0	107	0
0	103	0

Læsning af højre kolonne fra bund til top resulterer i den binære vektor 00100 00101, dvs. DE.

Antag, at vi forsøgte at handle i omvendt rækkefølge. Kryptering ville blive udført under anvendelse af vektoren A, og et vist tal a ville blive opnået. Men så havde parret (B,a) ikke en løsning, da den sædvanlige lighed af tal ikke kan udledes af deres lighedsmodulo.

Sikkerhed

Rygsæk systemer sikkerhed

For små rygsækvektorer er rygsækproblemet nemt at løse selv i hånden. En rigtig rygsæk skal indeholde et stort antal elementer. At åbne sådan en rygsæk med brute force, dvs. sprænge, vil være en vanskelig (umulig) opgave. Rygsæksystemer er dog ikke sikre til kryptoanalyse . Shamir og Zippel ( eng. Zippel ) fandt ud af, at ved at kende tallene ( "hemmeligt smuthul" ), kan du genoprette en superforøgende vektor fra en normal åben vektor [3] . Det vigtige er, at tallene ("det hemmelige par") ikke behøver at være de samme som dem, der blev brugt, da systemet blev oprettet af den lovlige bruger. Det er nok at finde et hvilket som helst par , sådan som vil give os en supervoksende vektor [20] . $t,t^{-1},m$ $EN$ $B$ $t,m$ $(t',m')$ $B*(t'modm')$

Sådan leder du efter et hemmeligt smuthul

Problem: En rygsækvektor er kendt for at blive brugt som den offentlige nøgle. Det opnås fra A, en superforøgende vektor, ved stærk modulær multiplikation med hensyn til modulet m og tallet t. Vi skal finde A,t, m, der ikke er kendt af os, eller rettere m og (vi kan beregne A ud fra dem). Ved at kende dem kan man dekryptere kryptoteksten [21] . $B=(b_{1},...,b_{n})$ $t^{-1}=u$

At finde det hemmelige par

Fremgangsmåden beskrevet nedenfor blev foreslået af A. Shamir . Den resulterende algoritme vil køre i polynomiel tid. Man skal dog være forsigtig med at vælge størrelsen af vektoren B med hensyn til hvilken algoritmen er polynomiel. Det er værd at huske på, at størrelsen af vektoren B afhænger af antallet af komponenter n og størrelsen af . Derfor er der begrænsninger på deres valg. $b_{i}$

Vi fikserer proportionalitetskonstanten , og komponenterne i supergrowing vektor A, bestående af bits. Da det mest signifikante ciffer i hver af komponenterne er et, så er A supergrowing og m er valgt til at være større end summen af komponenterne i rygsækvektoren A [20] . $d>1$ $a_{i},i=[1,n]$ $[dn]-1-n+i$

For at konstruere en algoritme er det ikke nødvendigt at lede efter de u og m, der faktisk bruges til kryptering. Ethvert par (u, m) vil gøre det, lad os kalde det et hemmeligt par , der opfylder begrænsningerne for stærk modulær multiplikation med hensyn til B, at vektoren A er supervoksende som et resultat af denne multiplikation, og m er større end summen af dens komponenter. Efter at have fundet mindst et hemmeligt par, anvender vi lemmaet og starter dekryptering. Dets eksistens er indlysende, da skaberen af kryptosystemet brugte et sådant par ved kryptering.

For klarhedens skyld konstruerer vi grafer over funktioner . Disse er lige linjestykker med diskontinuitetspunkter . $b_{i}u$ $(modm)$ ${\displaystyle u=pm/b_{i))$ $p=1,2,...$

Husk at vi skriver: $b_{i}=(ta_{i},modm)$ $t^{-1}=u$

$(b_{1}u,modm)=a_{1}$ , hvor er den ønskede inverse faktor, er den første komponent af vektoren , er ved antagelse meget lille i forhold til . Det betyder, at værdien er tæt på funktionens minimum . $u$ $a_{1}$ $EN$ $m$ $u$ $b_{1}$

Værdien er nemlig tæt på funktionens minimum . Så er de to minima af funktionerne og tæt på hinanden. Dermed kan resten af savtandskurverne også komme i betragtning. Det er tydeligt, at alle disse kurvers minima er tæt på hinanden. Det er muligt at bygge et lille interval indeholdende "akkumuleringspunkterne" af savtandskurvernes minima [22] . Baseret på dette lille interval findes også værdien af det hemmelige par. $(b_{2}u,modm)=a_{2}$ $u$ $b_{2}$ $b_{1}$ $b_{2}$ $n$ $u$

Da vi ikke kender værdien af modulet, vil vi ændre skalaen på figuren, så den bliver lig med 1 (del alle længder med ). $m$ $m$ $m$

Algoritme til at finde et hemmeligt par:

1) Find kandidater til det heltal , således at det th minimum af funktionen er det ønskede akkumuleringspunkt. $s$ $s$ $b_{1}$

For at antallet af kandidater ikke er for stort, indfører vi en fast parameter - det maksimale antal tilladte kandidater. $r$

I den første del af algoritmen er det ikke nødvendigt at overveje alle på én gang ; man bør indføre en parameter og overveje komponenten. ${\displaystyle b_{2},...,b_{n))$ $s<n$ $s$

${\displaystyle p/b_{1))$ -koordinat af -th minimum på kurven . $u$ $s$ $b_{1}$

Betingelsen for nærheden af kurvernes minima og kan skrives som følgende uligheder: $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$

Gang den første ulighed med : ${\displaystyle b_{1}b_{2))$

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

I alt sådanne uligheder , en for hver $s-1$ $b$

Så den første del af algoritmen giver alle sådanne naturværdier , for hvilke der er naturværdier , således at alle uligheder er opfyldt. $s$ $q$ $s-1$

2) Sekventiel verifikation af hver af kandidaterne.

I anden del af algoritmen er alle kontrolleret . Kandidaten vil blive afvist, hvis der for nogle ikke er et minimum af kurven, der ligger nær kurvens -th minimum . $i=[2,n]$ $s$ $jeg$ $b_{i}$ $s$ $b_{1}$

Fix . Arranger i stigende rækkefølge alle breakpoints i intervallet . Lad os tage to tilstødende punkter fra den sorterede liste og . I intervallet dannet af dem er hver kurve et lige linjesegment (ligningen beskriver disse segmenter). $s$ $[p/b_{1},(p+1)/b_{1}]$ $x_{i}$ $x_{i}+1$ $[x_{i},x_{i}+1]$ $b_{i}$ ${\displaystyle b_{i}u-const_{i}^{j))$

På baggrund af ovenstående skriver vi systemet af uligheder ned:

$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]$ - tilgroningstilstand

For to tal og for at danne et hemmeligt par, er det nødvendigt og tilstrækkeligt, at det hører til intervallet, der er konstrueret på denne måde for et par . , kandidaten fra den første del af algoritmen og punktindekset fra den sorterede liste af punkter svarende til den givne . $u$ $m$ $u/m$ $(p,j)$ $s$ $j$ $s$

Søgningen afsluttes, når der findes et ikke-tomt interval . $[x_{i},x_{i}+1]$

Eksempel [23] .

Lad den offentlige nøgle have tre komponenter $B=(7,3,2)$

1) Ifølge ovenstående uligheder:

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

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

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

Tabellen viser de mindste værdier , således at ulighederne holder: $E$

s	en	2	3	fire	5	6
E	5	3	2	2	3	5

2) Det kan ses, at alle værdier er egnede kandidater (i det generelle tilfælde er dette muligvis ikke tilfældet). Derfor opdeler vi intervallet i underintervaller: sådan at alle tre kurver er lige linjesegmenter i hvert reduceret interval. $s$ $(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})$

Lad os skrive ulighederne:

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

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

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

Konstanterne ændres inden for , , afhængigt af valget af intervallet. $0\leq i\leq 6$ $0\leq i'\leq 2$ $0\leq i'''\leq 1$

Ved at bruge notationen , , omskriver vi ulighederne i en enklere form: $i=1+i'+i''+i'''$ $j=i'-i''$ $k=i'+i''-i'''$

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

Lad os i tabellen samle alle værdierne af konstanterne for forskellige intervaller:

Interval	1/7	2/7	1/3	3/7	1/2	4/7	2/3	5/7	6/7	en
jeg'	0	en	2	2	3	3	fire	fire	5	6
jeg	0	0	0	en	en	en	en	2	2	2
jeg	0	0	0	0	0	en	en	en	en	en
jeg	en	2	3	fire	5	6	7	otte	9	ti
j	0	en	2	en	2	2	3	2	3	fire
k	0	en	2	3	fire	3	fire	5	6	7
12u<i	EN DEL	EN DEL	IKKE	IKKE	IKKE	IKKE	EN DEL	IKKE	EN DEL	IKKE
4u<j	IKKE	EN DEL	SAT	IKKE	SAT	IKKE	SAT	IKKE	EN DEL	SAT
8u<k	IKKE	IKKE	IKKE	EN DEL	SAT	IKKE	IKKE	IKKE	EN DEL	EN DEL

De sidste tre linjer angiver, om hver af ulighederne er sande eller ej: SAT - sand, DEL-delvis sand (vises, når uligheden er sand på højre side af delintervallet), IKKE - ikke sand (vises, når uligheden ikke er sand) sandt i venstre side af delintervallet).

Et interval genererer et hemmeligt par, hvis og kun hvis alle tre af enten SAT eller PART er i kolonnen. Det eneste sådan interval Ved at vælge et tal fra intervallet, for eksempel (dvs. ), får vi en supervoksende vektor . $(5/7,3/4)$ $8/11$ $m=11$ $A=(1,2,5)$

Varianter af rygsækproblemet i kryptografi

1) Merkle-Hellman Rygsæk ( eng. Merkle-Hellman Cryptosystem ).

Den offentlige nøgle A er en superforøgende vektor, den hemmelige nøgle B opnås fra A ved stærk modulær multiplikation.

2) Rygsæk af Graham-Shamir ( eng. Graham-Shamir Cryptosystem ) [5] .

Den offentlige nøgle A er en superforøgende vektor. Dens elementer er skrevet i bitrepræsentation. Dernæst genereres tilfældige tal, kaldet støj. Deres bitrepræsentation føjes til bits af rygsækvektoren til venstre, det vil sige i den mest signifikante bit.

Lad os sige, at vi vælger vektorer . Vi tilføjer præfikser fra tilfældigt udvalgte tal i det: $A=(1,3,5)$

binær repræsentation	med tilfældigt præfiks
1=001	101 001 = 41
3=011	111 011 = 59
5 = 101	100 101 = 37

Den resulterende rygsækvektor har ikke den superforøgende egenskab. Derfor skjuler tilføjelse af tilfældig støj overgrowth-egenskaben for den oprindelige vektor A, og kredsløbet bliver mere sikkert [24] . $(41,59,37)$

3) Morii-Kasahara Rygsæk ( eng. Morii-Kasahara Cryptosystem ) [10]

Ordningen ligner Merkle-Hellman-ordningen, men bruger en multiplikativ krypteringsmetode for både den offentlige nøgle og hemmeligheden.

Lad vektor . Vi vælger , et primtal (i dette skema ) og , sådan at . Den hemmelige nøgle B fås fra A ved formlen , dvs. Lad beskeden blive krypteret , derefter chifferen . $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) Goodman -McAuley Cryptosystem rygsæk [ 8] .

Som i det første skema i Goodman-McCauley-rygsækken, bruges modulær multiplikation til at opnå den offentlige nøgle fra hemmeligheden, men den hemmelige nøgle er ikke en superforøgende vektor. Ordningen er baseret på kompleksiteten af heltalsfaktorisering, derfor ligner den RSA-kryptosystemet.

5) Rygsæk Nakashe-Stern ( eng. Naccache-Stern Cryptosystem ) [14] .

Denne ordning kombinerer to metoder: Merkle-Hellman-rygsækken og Polyg-Hellman-algoritmen . Givet et primtal er S en delmængde ( eng. delmængdeprodukt ), og en rygsækvektor , hvor alle er relativt primtal. Vi skal finde en binær vektor sådan $s$ $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) Rygsæk Shor-Rivest ( eng. Chor-Rivest ) [24] [25]

Baseret på algebra i endelige felter (Galois-felter) . Lad den offentlige nøgle A bestå af elementer fra feltets underfelt , dvs. Den hemmelige nøgle består af følgende elementer: ${\displaystyle q=p^{h))$ $GF(p)$ $GF(q)$ $(a_{1},a_{2},...a_{p})=GF(p)\in GF(q)$

element af med algebraisk grad $t$ $GF(q)$ $h$
generator fra $g$ $GF^{*}(q)$
hele af $d$ $\mathbb {Z} (q-1)$

Så består den offentlige nøgle B af elementerne [5] . $b_{i}=d+\log _{g}(t+a_{i})mod(q-1)$

Fremtiden for rygsæksystemer

I dag er kryptografernes hovedopmærksomhed fokuseret på kryptosystemer baseret på heltalsfaktorisering , diskret logaritme og elliptiske kurver . Forskningen i rygsæksystemer fortsætter dog, men sådanne kryptosystemer er ikke populære og inspirerer ikke tillid på grund af fejlene i tidligere algoritmer. Hvis der kan skabes en algoritme, der fuldt ud udnytter sværhedsgraden ved rygsækproblemet (NP-fuldstændighed), med høj tæthed og med hemmelige smuthuller, der er svære at opdage, så vil dette være et system, der er bedre end systemer baseret på heltalsfaktorisering og diskret logaritme (deres NP-fuldstændighed er ikke blevet bevist). Derudover vil dette system være hurtigt, hvilket betyder, at det vil være i stand til at konkurrere i hastighed med klassiske offentlige nøglesystemer [5] .

For en rygsækvægt kan en iteration af Merkle-Hellman-algoritmen være mere end 100 gange hurtigere end RSA (med et modul på 500 bit) [26] . $n=100$

Noter

↑ Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
↑ 1 2 3 4 5 Schnaer, 2002 , s. 19.1.
↑ 1 2 3 4 5 Schnaer, 2002 , s. 19.2.
↑ Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssikkerhed : lærebog - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
↑ 1 2 3 4 5 6 7 8 Kin Ming Lai. Knapsack Cryptosystems: Fortiden og fremtiden . – 2001.
↑ . Matematrix (engelsk) . – 2001.
↑ Publikationer . _ (utilgængeligt link)
↑ 1 2 Et nyt krypteringssystem med offentlig nøgle til rygsæk . — springer.
↑ Jacques Stern- Wiki - artikel . — springer.
↑ 1 2 Masakatu Morii, Masao Kasahara. Nyt kryptosystem med offentlig nøgle, der bruger diskrete logaritmer over GF(p ) . — springer.
↑ Shinya Kiuchi, Yasuyuki Murakami, Masao Kasahara. Nye multiplikative napsack -type offentlige nøglekryptosystemer .
↑ Hussain Ali Hussain, Jafar Wadi Abdul Sada , Klipha SM Nyt flertrins rygsæk med offentlig nøglekryptosystem . Arkiveret fra originalen den 26. december 2014.
↑ Harald Ritter. Breaking napsack Cryptosystems by l-Norm Enumeration . Arkiveret fra originalen den 31. marts 2012.
↑ 1 2 Davis Naccache, Jacques Stern. Et nyt kryptosystem med offentlig nøgle . – 2006.
↑ Om sikkerheden i den forbedrede kryptosystemrygsæk .
↑ Der er udviklet en databeskyttelsesalgoritme, som selv kvantecomputere ikke kan knække . Hentet 2. november 2015. Arkiveret fra originalen 17. august 2015. (ubestemt)
↑ Salomaa, 1990 , s. 76.
↑ 1 2 3 4 Salomaa, 1990 , s. 103.
↑ Salomaa, 1990 , s. 104.
↑ 1 2 Salomaa, 1990 , s. 113.
↑ Salomaa, 1990 , s. 112.
↑ Salomaa, 1990 , s. 114.
↑ Salomaa, 1990 , s. 117.
↑ 1 2 B. Chor, R. L. Rivest. Et offentlig nøglekryptosystem af rygsæk-type baseret på aritmetik i endelige felter . - 1988.
↑ Serge Vaudenay. Krypteringsanalyse af Chor-Rivest Kryptosystem . (utilgængeligt link)
↑ A. M. Odlyzko. Opkomsten og faldet af Knapsack Cryptosystems .

Litteratur

på russisk

Levitin A. V. Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 160-163. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Robert Sedgwick . Grundlæggende algoritmer i C++. Del 1-4. Analyse. Datastrukturer. Sortering. Søg = Algoritmer i C++. Del 1-4. grundlæggende. datastrukturer. Sortering. Søger. - 3. - Rusland, Skt. Petersborg: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Anvendte problemer med grafteori. - M. , 1974. - 232 s.
V. N. Burkov, D. A. Novikov. Elementer i grafteori . - 2001. - S. 28.
S. Okulov. Programmering i algoritmer. - 2007. - S. 383.
B. Schneier. Anvendt kryptografi . - 2. - 2002. Arkiveret 28. februar 2014 på Wayback Machine
A. Salomaa. Public Key Cryptography = Public Key Cryptography. - Springer-Verlag, 1990. - S. 102-150. Arkiveret 19. november 2011 på Wayback Machine
Koblitz N. Kursus i talteori og kryptografi - 2. udgave - M .: Videnskabeligt forlag TVP , 2001. - 254 s. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5

på engelsk

Silvano Martelo, Paolo Toth. Rygsæk problemer. - Wiley, 1990. - 306 s.
David Pisinger. Rygsæk problemer . - 1995. Arkiveret 22. december 2012 på Wayback Machine
Hans Kellerer, Ulrich Pferschy, David Pisinger. Rygsæk problemer. - 1995.

Links

Denis Alekseev. Rygsæk algoritme . Yandex.People . _ Dato for adgang: 6. december 2012. Arkiveret fra originalen 7. januar 2013. (Russisk)
Mikhail Chegodar. Brugen af kryptografi i spørgsmål om databeskyttelse, f.eks. et rygsækkrypteringssystem . Underjordisk informationscenter. Hentet: 6. december 2012. (Russisk)

Rygsækproblemet
Ansøgninger	Rygsækproblem i kryptografi Skæreopgave
Kryptosystemer baseret på rygsækproblemet	Merkla-Hellman Naccasha - Stern Graham - Shamira
Derudover	Liste over opgaver om rygsæk