Ryggsäcksproblemet i kryptografi

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 maj 2020; kontroller kräver 4 redigeringar .

Ryggsäcksproblemet (eller ryggsäcksproblemet ) i kryptografi ( eng. Knapsackproblem ) är ett problem på grundval av vilket de amerikanska kryptograferna Ralph Merkle och Martin Hellman utvecklade den första krypteringsalgoritmen för offentlig nyckel . Det kallas Merkle-Hellmans kryptosystem. För att kryptera meddelanden använde vi lösningen av ryggsäcksproblemet, som är känt för att vara NP-hårt . Därför trodde man att det kunde säkerställa systemets kryptografiska stabilitet. För tillfället har många ryggsäckskryptosystem skapats. Men nästan alla befintliga idag är hackade eller erkända som potentiellt osäkra.

Historik

Ryggsäcksproblemet är kärnan i den första asymmetriska krypteringsalgoritmen (eller annan offentlig nyckelkryptering). Idén om kryptografi med offentlig nyckel lades fram av de amerikanska kryptograferna Whitfield Diffie , Martin Hellman och oberoende Ralph Merkle . Den presenterades först av Diffie och Hellman vid National Computer Conference 1976, samma år som deras gemensamma arbete om detta ämne, New Directions in Cryptography, publicerades . ) [1] . Merkles artikel "Secure Communication Over Insecure Channels" publicerades först 1978 [2] . Nyheten i förhållande till de symmetriska kryptosystemen som var vanliga vid den tiden var användningen av parade nycklar - hemlig ( eng. privat nyckel, hemlig nyckel, SK ) och offentlig ( eng. offentlig nyckel, PK ), skapade av användaren. Den hemliga nyckel som används för att dekryptera informationen måste hållas hemlig av användaren, medan den publika nyckeln, som endast behövs för kryptering, kan göras offentlig. I många kryptosystem erhålls den publika nyckeln från den hemliga nyckeln [3] [4] .

Den första krypteringsalgoritmen baserad på ryggsäcksproblemet utvecklades av Merkle och Hellman 1978 och kallades " Merkle-Hellman Algorithm " [3] . Den publicerades i enstegsversioner ( engelsk singly-iterated ) och flerstegsversioner ( engelsk multiply-iterated ). Algoritmen kunde bara användas för kryptering, men den israeliska kryptoanalytikern Adi Shamir anpassade den för användning i digitala signaturer [3] . Efter att schemat publicerats erbjöd Merkle en belöning på 100 $ till alla som lyckades knäcka enstegsalgoritmen. 1982 genomförde Shamir en framgångsrik attack och fick den utlovade belöningen. Men även efter att ha betalat det, var Merkle säker på den kryptografiska styrkan hos flerstegssystemet och erbjöd 1 000 dollar om det lyckades knäckas. 1984 lyckades den amerikanske matematikern Ernest Brickell genomföra ett hack för en fyrtiostegsvariant på drygt 1 timme på en Cray-1- maskin [5] [6] .

Oberoende av varandra, redan 1980, upptäckte den amerikanska matematikern Ron Graham och Adi Shamir ett sätt att öka den kryptografiska styrkan hos Merkle-Hellman-schemat, men redan 1983 knäcktes det resulterande Graham-Shamir-schemat av den amerikanske vetenskapsmannen Leonard Adleman . Men sökandet efter ändringar utan bristerna i Merkle-Hellman-schemat fortsatte. År 1985 skapade den brittiske docenten Rodney Goodman och den amerikanske ingenjören Anthony McAuley en krets baserad på modulära ryggsäckar med ett hemligt kryphål som inte baseras på superincreasing vektorer , utan med hjälp av den kinesiska restsatsen [7] [8] .

Därefter stod det klart att systemet var sårbart för attacker baserat på sökandet efter hemliga kryphål. Men 1990 föreslog Valtteri Niemi ett nytt schema baserat på samma uppgift som en modulär ryggsäck. Det knäcktes redan nästa år av Chi Ye Meng , Antoine Zhu och Jacques Stern [9] oberoende av varandra, med lite olika metoder. Utöver användningen av modulära ryggsäckar har det gjorts försök att använda andra typer av ryggsäckar.

Så 1986 publicerade Harald Niederreiter ett ryggsäckskryptosystem baserat på algebraisk kodningsteori, som senare bröts, och 1988 utvecklade Masakatsu Morii och Masao Kasahara ett ryggsäckskryptosystem med hjälp av en multiplikativ ryggsäck [10] . Denna idé visade sig vara framgångsrik och hittills har systemet på multiplikativa ryggsäckar inte blivit hackat.

År 2001 föreslog Shinya Kiuchi , Yasuyuki Murakami och Masao Kasahara en förbättring av Moriya-Kasahara-schemat baserat på multiplikativa ryggsäckar med Schalkwijk-algoritmen [11] .

Också framgångsrik var idén från Hussein Ali Hussein , Jafar Wadi Abdul Sad och M. Khalifa , som 1991 föreslog ett flerstegs ryggsäckskryptosystem ( engelsk flerstegs ryggsäckskryptosystem ). Den fixar ryggsäcksvektorn för varje steg, och utdata (chiffertext) efter varje steg i algoritmen används som indata (text) till nästa steg. Ingen framgångsrik attack på detta system är känd (från och med 2001) [12] .

Qu Minghua och Scott Vanstone föreslog 1992 ett hybridkryptosystem som i första hand är baserat på ryggsäcksproblemet, men som också innehåller logaritmiska signaturer. 1994 visade R. Blackburn , Murphy, Sean och Jacques Stern att en förenklad version av U-Wastons kryptosystem inte är säker. Dessa kryptosystem studerades mer ingående av Fong Nguyen och Jacques Stern 1997 [5] .

Förbättringar av den klassiska Merkle-Hellman-algoritmen fortsatte också. 1994 föreslog Orton en modifiering av Merkle-Hellman-schemat i flera steg, men två år senare hackades det av Ritter [13] .

1995 föreslogs två nya tillvägagångssätt till problemet på en gång. Den första, baserad på diofantiska ekvationer , beror på Lin Zhuxing , Zhang Zhencheng och Li Jia Tong . Nästan omedelbart visade Lai Qisong och Blackburn, Murphy, Sean och S. G. Paterson oberoende att detta kryptosystem inte är säkert.

Andra tillvägagångssättet, baserat på det multiplikativa ryggsäcksproblemet, föreslogs av David Naccache och Jacques Stern [14] . Nakkashe och Stern erbjöd DM 1024 till någon som lyckades knäcka sitt kryptoschema, men det fanns ingen information om att någon fått denna belöning ännu (från 2001) [5] .

1996 föreslog Kunikatsu Kobayashi och Masaki Kimura ett förbättrat ryggsäckskryptosystem baserat på ett nytt koncept, där avsändaren kan välja en krypteringsnyckel från en hel uppsättning nycklar. Två år senare visade Hidenori Kuwakado och Hatsukazu Tanaka att systemet var potentiellt osäkert [15] .

Den sista versionen av algoritmen föreslogs av B. Shor och R. L. Rivest 2006. 2002 ansågs Chor-Rivest-algoritmen vara säker [3] .

2015 rapporterades det att Nathan Hamlin och William Webb från Washington State University hade skapat en ryggsäcksalgoritm utan bristerna i tidigare implementeringar [16] .

Sedan dess har många offentliga nyckelalgoritmer föreslagits som inte är baserade på ryggsäckssystem. De mest kända av dem är: RSA , EIGamal och Rabin . De kan användas för både kryptering och digitala signaturer. De är dock långsamma och inte lämpliga för snabb kryptering/dekryptering av stora volymer meddelanden. Lösningen på detta problem är hybridkryptosystem, meddelanden krypteras med en snabb symmetrisk algoritm med en slumpmässig nyckel, och den publika nyckelalgoritmen används för att kryptera själva slumpnyckeln (sessionsnyckeln).

Förklaring av problemet

Ryggsäcksproblemet är som följer: givet en uppsättning distinkta positiva heltal. Låt det finnas ett tal som också är heltal och positivt. Uppgiften är att hitta en sådan uppsättning som de summerar till exakt . Det är tydligt att det inte alltid finns en lösning på detta problem. $A=(a_{1},...,a_{n})$ $n$ $k$ $a_{i}$ $k$

Enligt definitionen av system med offentliga nyckel måste du ha två nycklar för att lyckas kryptera/dekryptera. Den legitima mottagaren av meddelandet känner till den hemliga nyckeln A, medan avsändaren bara har den offentliga nyckeln B. Hur kan du förhindra en angripare från att dekryptera meddelandet om han känner till den offentliga nyckeln? Svaret är enkelt, den publika nyckeln måste härledas från den privata nyckeln med hjälp av någon transformation f som har följande två egenskaper [17] :

Det är lätt att räkna med att veta $B=f(A)$ $A$
Att bestämma , veta , är förmodligen en svår uppgift. $A=f^{-1}(B)$ $B$

Som svåra problem betraktas vanligtvis NP-kompletta problem, så ryggsäcksproblemet är lämpligt för att bygga system med public-key.

Kryptering med ryggsäcksproblemet

Meddelandet är krypterat som en lösning på en uppsättning ryggsäcksproblem [2] .

Def. En ryggsäcksvektor är en ordnad uppsättning av n objekt [18] .

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

För att kryptera klartexten i binär representation är den uppdelad i längdblock ( motsvarar till exempel 5 föremål i en ryggsäck). Man tror att en indikerar närvaron av ett föremål i ryggsäcken, och noll indikerar dess frånvaro. Det finns två sätt att kryptera: $n$ $(11100)$

1) Meddelandechifferet erhålls genom att höja elementen i ryggsäcksvektorn till styrkan av bitarna i det krypterade meddelandet som motsvarar dem och ytterligare multiplicera resultaten, det vill säga om , och meddelandet , då blir chiffern numret . Denna metod kallas multiplikativ [5] . $A=(2,3,5)$ $(100)$ $2^{1}*3^{0}*5^{0}=2$

2) Meddelandechifferet erhålls genom att multiplicera elementen i ryggsäcksvektorn med motsvarande bit i det krypterade meddelandet och sedan lägga till resultaten, det vill säga om , och meddelandet , då blir chiffern numret . Denna metod kallas för additiv [5] . $A=(2,3,5)$ $(100)$ $2*1+3*0+5*0=2$

Ett exempel på en chiffertext erhållen med en additiv algoritm.

Låt en ryggsäcksvektor Α = (3 4 6 7 10 11) med längden n = 6 anges.

oformatterad text	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
saker i en ryggsäck	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11
chiffertext	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	elva

För en given Α är alla kryptosystem siffror som inte överstiger 41, den totala vikten av alla föremål i ryggsäcksvektorn. Det finns bara en kryptotext för varje klartext.

Komplexiteten i chifferet ligger i det faktum att det finns två problem med ryggsäcken: "lätt" och "hårt". Ett "lätt" problem kan lösas i linjär tid, ett "hårt" kan inte. Den publika nyckeln är ett "svårt" problem eftersom det är lätt att använda för att kryptera och omöjligt att dekryptera ett meddelande. Den privata nyckeln är ett "lätt" problem, eftersom det gör det enkelt att dekryptera meddelandet. I avsaknad av en privat nyckel måste det "hårda" ryggsäcksproblemet lösas. Merkle och Hellman, med hjälp av modulär aritmetik, utvecklade ett sätt att förvandla en "lätt" ryggsäck till en "svår" [2] .

"Lätt" problem

För vissa vektorer Α är ryggsäcksproblemet enkelt att lösa. Superväxande vektorer har denna egenskap [2] .

Def. En ryggsäcksvektor kallas supergrowing om för , dvs varje medlem av sekvensen är större än summan av de föregående [18] .

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

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

j=2,...,n

Exempel

Låt den totala vikten av ryggsäcken och ryggsäcksvektorn anges som superväxt . $P=70$ $A=(2,3,6,13,27,52)$

För denna ryggsäcksvektor är algoritmen för att lösa ryggsäcksproblemet enkel. Den största vikten tas, 52. Eftersom 52 < 70 läggs motsvarande föremål i ryggsäcken. Fritt utrymme i ryggsäcken blev lika med 70 - 52 = 18. Ta sedan ett föremål med vikten 27. Eftersom 27 > 18 kommer detta föremål inte in i ryggsäcken. Det tredje föremålet med vikten 13 < 18 får plats i ryggsäcken, vilket ger 5 ledigt utrymme. Nästa föremål med vikten 6 får inte plats. På samma sätt placeras föremål med vikterna 2 och 3 i en ryggsäck. Restvikten på ryggsäcken har blivit 0, lösningen har hittats!

Det "hårda" problemet

En normal ryggsäck är inte med en superökande ryggsäcksvektor A. Det enda sättet att lösa ett sådant problem är att testa alla möjliga tills rätt lösning hittas. Den snabbaste algoritmen har ett exponentiellt beroende av antalet objekt [2] .

Ett kryptosystem med offentlig nyckel baserat på ryggsäcksproblemet

Som tidigare är vektorn A den hemliga nyckeln och vektorn B den publika nyckeln.

Skapa en offentlig nyckel från en privat

För heltal och beteckna . $x$ $m\geq 2$ $(x,modm)=x-[x/m]m$

Låt vara en superincreasing ryggsäcksvektor. Låt oss introducera ett heltal och ett naturligt tal så att den största gemensamma divisorn är . $A=(a_{1},...,a_{n})$ ${\displaystyle m>\sum _{i=1}^{n}a_{i))$ $t<m$ $(t,m)=1$

Def. Om så att för , då säger vi att det erhålls från stark modulär multiplikation [18] .

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

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

i=1,..,n

B

A

Skaparen av kryptosystemet väljer parametrarna så att A är superväxande och B erhålls från A genom stark modulär multiplikation med avseende på m och t. $A,B,t,m$

Giltigt Lemma [19] : Låt A vara en superväxande vektor, och B erhålls från A genom stark modulär multiplikation med avseende på m och t. Antag att u = 1/t, β är ett godtyckligt naturligt tal, och α =(uβ,modm). Då är det sant att:

Ryggsäcksproblemet med indata (A,α) är lösbart i linjär tid, och om det finns en lösning så är den unik;
Ryggsäcksproblemet med indata (B,β) har som mest en lösning;
Om det finns en ingångslösning (B,β), så är den samma som den enda ingångslösningen (A,α).

Exempel

Skapa vektor B från vektor A [18] .

Låt en superväxande vektor (hemlig nyckel) med ges . Summan av dess komponenter är 55 205. Välj , och . Då är villkoret uppfyllt. $A=(103,107,211,430,863,1718,3449,6907,13807,27610)$ $n=10$ $m=55207$ $t=25236$ $(t,m)=1$

Det hittas enligt formeln . I detta fall: $t^{-1}modm$ $(tu)modm=1$

1061 * 25236 - 1= 485 * 55207

Därav . $t^{-1}=u=1061$

Den publika nyckeln B beräknas av och a =(uβ,modm). Till exempel för $b_{i}=(ta_{i},modm)$ ${\displaystyle a_{1},a_{6},a_{10))$

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

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

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

Efter att ha gjort liknande beräkningar för de återstående elementen erhålls en vektor $B=(4579,50316,24924,30908,27110,17953,32732,16553,22075,53620)$

Kryptering

Använd den publika nyckeln B och kryptera meddelandet: DÖDSGUDER EAT ONLY APPLES

Numerisk kodning används först, mellanrummet tilldelas värdet 0, bokstäverna A till Z tilldelas värdet 1 till 26. Numeriska koder uttrycks i binära mängder. Eftersom vektor B har längden 10 kan den användas för att kryptera block med två bokstäver samtidigt. Blockkoden, som tidigare, erhålls genom att summera vikterna för de föremål som ingår i ryggsäcken. $bi}$

Källtextblock	binär kod	Blockkod
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	11 001 00 000	82005
AP	00001 10000	45063
PL	10 000 01 100	53864
ES	00101 10011	149480

Dekryptering

Låt oss dechiffrera den första siffran 95 097. Det är värt att notera det

1061*95097 = 1827*55207 + 34728

Ryggsäcksproblemet (A.34728) beaktas. Lösningen erhålls genom att titta på ryggsäcksvektorn A från höger till vänster. När talet i den vänstra kolumnen inte är mindre än den aktuella visade komponenten A, skrivs 1, och det nya talet i den vänstra kolumnen erhålls genom att subtrahera komponenten från föregående tal. Annars skrivs 0 och siffran i den vänstra kolumnen ändras inte. Resultatet visas i tabellen:

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

Att läsa den högra kolumnen från botten till toppen resulterar i den binära vektorn 00100 00101, dvs DE.

Anta att vi försökte agera i omvänd ordning. Kryptering skulle utföras med användning av vektorn A och ett visst antal a skulle erhållas. Men då hade paret (B,a) ingen lösning, eftersom den vanliga likheten av tal inte kan härledas från deras likhetsmodulo.

Säkerhet

Säkerhet för ryggsäckssystem

För små ryggsäcksvektorer är ryggsäcksproblemet lätt att lösa även för hand. En riktig ryggsäck ska innehålla ett stort antal element. Att öppna en sådan ryggsäck med brute force, d.v.s. spränga, kommer att vara en svår (omöjlig) uppgift. Ryggsäckssystem är dock inte säkra för kryptoanalys . Shamir och Zippel ( eng. Zippel ) fann att genom att känna till siffrorna ( "hemligt kryphål" ) kan du återställa en superökande vektor från en normal öppen vektor [3] . Det viktiga är att siffrorna ("det hemliga paret") inte behöver vara desamma som de som användes när systemet skapades av den lagliga användaren. Det räcker med att hitta vilket par som helst som ger oss en superväxande vektor [20] . $t,t^{-1},m$ $A$ $B$ $t,m$ $(t',m')$ $B*(t'modm')$

Hur man letar efter ett hemligt kryphål

Problem: Det är känt att en ryggsäcksvektor används som den offentliga nyckeln. Den erhålls från A, en superökande vektor, genom stark modulär multiplikation med avseende på modulen m och talet t. Vi måste hitta A,t, m som inte är kända för oss, eller snarare m och (vi kan beräkna A från dem). Genom att känna till dem kan man dekryptera kryptotexten [21] . $B=(b_{1},...,b_{n})$ $t^{-1}=u$

Att hitta det hemliga paret

Tillvägagångssättet som beskrivs nedan föreslogs av A. Shamir . Den resulterande algoritmen kommer att köras i polynomtid. Man bör dock vara försiktig med att välja storleken på vektorn B med avseende på vilken algoritmen är polynom. Det är värt att komma ihåg att storleken på vektorn B beror på antalet komponenter n och storleken på . Därför finns det begränsningar för deras val. $bi}$

Vi fixar proportionalitetskonstanten , och komponenterna i superväxande vektor A, bestående av bitar. Eftersom den mest signifikanta siffran i var och en av komponenterna är en, är A superväxande och m väljs till att vara större än summan av komponenterna i ryggsäcksvektorn A [20] . $d>1$ $a_{i},i=[1,n]$ $[dn]-1-n+i$

För att konstruera en algoritm är det inte nödvändigt att leta efter de u och m som faktiskt används för kryptering. Vilket par som helst (u, m) kommer att göra, låt oss kalla det ett hemligt par , som uppfyller begränsningarna för stark modulär multiplikation med avseende på B, att vektorn A superväxer som ett resultat av denna multiplikation, och m är större än summan av dess komponenter. Efter att ha hittat minst ett hemligt par tillämpar vi lemmat och börjar dekryptera. Dess existens är uppenbar, eftersom skaparen av kryptosystemet använde ett sådant par vid kryptering.

För tydlighetens skull konstruerar vi grafer över funktioner . Dessa är räta linjesegment med diskontinuitetspunkter , . $b_{i}u$ $(modm)$ ${\displaystyle u=pm/b_{i))$ $p=1,2,...$

Kom ihåg att vi kommer att skriva: $b_{i}=(ta_{i},modm)$ $t^{-1}=u$

$(b_{1}u,modm)=a_{1}$ , där är den önskade inversa faktorn, är den första komponenten i vektorn , är, enligt antagande, mycket liten jämfört med . Det betyder att värdet är nära funktionens minimum . $u$ $a_{1}$ $A$ $m$ $u$ $b_{1}$

För , värdet är nära funktionens minimum . Då är de två minima av funktionerna och nära varandra. Därmed kan även resten av sågtandskurvorna beaktas. Det är tydligt att minima för alla dessa kurvor ligger nära varandra. Det är möjligt att bygga ett litet intervall som innehåller "ackumuleringspunkterna" för sågtandskurvornas minima [22] . Baserat på detta lilla intervall hittas också värdet av det hemliga paret. $(b_{2}u,modm)=a_{2}$ $u$ $b_{2}$ $b_{1}$ $b_{2}$ $n$ $u$

Eftersom vi inte vet värdet på modulen kommer vi att ändra skalan på figuren så att den blir lika med 1 (dividera alla längder med ). $m$ $m$ $m$

Algoritm för att hitta ett hemligt par:

1) Hitta kandidater för heltal så att det minsta av funktionen är den önskade ackumuleringspunkten. $sid$ $sid$ $b_{1}$

För att antalet kandidater inte ska bli för stort inför vi en fast parameter - det maximala antalet tillåtna kandidater. $r$

I den första delen av algoritmen är det inte nödvändigt att överväga allt på en gång , man bör införa en parameter och överväga komponenten. ${\displaystyle b_{2},...,b_{n))$ $s<n$ $s$

${\displaystyle p/b_{1))$ -koordinaten för det -:e minimumet på kurvan . $u$ $sid$ $b_{1}$

Villkoret för närheten till kurvornas minima och kan skrivas som följande ojämlikheter: $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$

Multiplicera den första ojämlikheten med : ${\displaystyle b_{1}b_{2))$

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

Sammanlagt sådana ojämlikheter , en för varje $s-1$ $b$

Så, den första delen av algoritmen ger alla sådana naturvärden för vilka det finns naturvärden så att alla ojämlikheter uppfylls. $sid$ $q$ $s-1$

2) Sekventiell verifiering av var och en av kandidaterna.

I den andra delen av algoritmen är alla kontrollerade . Kandidaten kommer att avvisas om det för vissa inte finns något minimum av kurvan som ligger nära kurvans -:e minimum . $i=[2,n]$ $sid$ $i$ $bi}$ $sid$ $b_{1}$

Fixa . Ordna i stigande ordning alla brytpunkter i intervallet . Låt oss ta två intilliggande punkter från den sorterade listan och . I intervallet som bildas av dem är varje kurva ett rakt linjesegment (ekvationen beskriver dessa segment). $sid$ $[p/b_{1},(p+1)/b_{1}]$ $x_{i}$ $x_{i}+1$ $[x_{i},x_{i}+1]$ $bi}$ ${\displaystyle b_{i}u-const_{i}^{j))$

Baserat på det föregående skriver vi ner systemet med ojämlikheter:

$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]$ - igenväxttillstånd

För två siffror och för att bilda ett hemligt par är det nödvändigt och tillräckligt att det hör till intervallet som är konstruerat på detta sätt för något par . , kandidaten från den första delen av algoritmen och punktindexet från den sorterade listan med punkter som motsvarar den givna . $u$ $m$ $u/m$ $(p,j)$ $sid$ $j$ $sid$

Sökningen avslutas när ett icke-tomt intervall hittas . $[x_{i},x_{i}+1]$

Exempel [23] .

Låt den publika nyckeln ha tre komponenter $B=(7,3,2)$

1) Enligt ovanstående ojämlikheter:

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

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

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

Tabellen listar de minsta värdena så att ojämlikheterna håller: $E$

sid	ett	2	3	fyra	5	6
E	5	3	2	2	3	5

2) Det kan ses att alla värden är lämpliga kandidater (i det allmänna fallet kanske det inte är fallet). Därför delar vi in intervallet i delintervall: så att alla tre kurvorna är rätlinjesegment i varje reducerat intervall. $sid$ $(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)$ $bi}$ $(b_{i}u-const_{i}^{j})$

Låt oss skriva ojämlikheterna:

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

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

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

Konstanterna ändras inom , , beroende på valet av intervall. $0\leq i\leq 6$ $0\leq i'\leq 2$ $0\leq i'''\leq 1$

Med hjälp av notationen , , skriver vi om ojämlikheterna i en enklare form: $i=1+i'+i''+i'''$ $j=i'-i''$ $k=i'+i''-i'''$

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

Låt oss i tabellen samla alla värden för konstanterna för olika intervall:

Intervall	1/7	2/7	1/3	3/7	1/2	4/7	2/3	5/7	6/7	ett
jag'	0	ett	2	2	3	3	fyra	fyra	5	6
i	0	0	0	ett	ett	ett	ett	2	2	2
i	0	0	0	0	0	ett	ett	ett	ett	ett
i	ett	2	3	fyra	5	6	7	åtta	9	tio
j	0	ett	2	ett	2	2	3	2	3	fyra
k	0	ett	2	3	fyra	3	fyra	5	6	7
12u<i	DEL	DEL	INTE	INTE	INTE	INTE	DEL	INTE	DEL	INTE
4u<j	INTE	DEL	SAT	INTE	SAT	INTE	SAT	INTE	DEL	SAT
8u<k	INTE	INTE	INTE	DEL	SAT	INTE	INTE	INTE	DEL	DEL

De sista tre raderna indikerar om var och en av ojämlikheterna är sanna eller inte: SAT - sant, DEL-partiellt sant (visas när olikheten är sann på höger sida av delintervallet), NOT - inte sant (visas när olikheten inte är sant sant på vänster sida av delintervallet).

Ett intervall genererar ett hemligt par om och endast om alla tre av antingen SAT eller PART finns i kolumnen. Det enda sådana intervallet Väljer vi ett tal från intervallet, till exempel (dvs ), får vi en superväxande vektor . $(5/7,3/4)$ $8/11$ $m=11$ $A=(1,2,5)$

Varianter av ryggsäcksproblemet i kryptografi

1) Merkle-Hellman Ryggsäck ( eng. Merkle-Hellman Cryptosystem ).

Den publika nyckeln A är en superökande vektor, den hemliga nyckeln B erhålls från A genom stark modulär multiplikation.

2) Ryggsäck av Graham-Shamir ( eng. Graham-Shamir Cryptosystem ) [5] .

Den publika nyckeln A är en superökande vektor. Dess element är skrivna i bitrepresentation. Därefter genereras slumptal, som kallas brus. Deras bitrepresentation läggs till bitarna i ryggsäcksvektorn till vänster, det vill säga i den mest signifikanta biten.

Låt oss säga att vi väljer vektorer . Vi lägger till prefix från slumpmässigt valda nummer i den: $A=(1,3,5)$

binär representation	med slumpmässigt prefix
1=001	101 001 = 41
3=011	111 011 = 59
5 = 101	100 101 = 37

Den resulterande ryggsäcksvektorn har inte den superincreasing-egenskapen. Att lägga till slumpmässigt brus döljer därför överväxtegenskapen för den ursprungliga vektorn A och kretsen blir säkrare [24] . $(41,59,37)$

3) Morii-Kasahara Ryggsäck ( eng. Morii-Kasahara Cryptosystem ) [10]

Schemat liknar Merkle-Hellman-schemat, men använder en multiplikativ krypteringsmetod för både den offentliga nyckeln och hemligheten.

Låt vektor . Vi väljer , ett primtal (i detta schema ) och , så att . Den hemliga nyckeln B erhålls från A genom formeln , dvs. Låt meddelandet krypteras , sedan 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-ryggsäck [ 8] .

Som i det första schemat i Goodman-McCauley-ryggsäcken, används modulär multiplikation för att erhålla den publika nyckeln från hemligheten, men den hemliga nyckeln är inte en superökande vektor. Schemat är baserat på komplexiteten i heltalsfaktorisering, därför liknar det RSA-kryptosystemet.

5) Ryggsäck Nakashe-Stern ( eng. Naccache-Stern Cryptosystem ) [14] .

Detta schema kombinerar två metoder: Merkle-Hellman-ryggsäcken och Polyg-Hellman-algoritmen . Givet ett primtal är S en delmängd ( eng. delmängd produkt ), och en ryggsäcksvektor , där alla är relativt primtal. Vi måste hitta en binär vektor sådan $sid$ $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) Ryggsäck Shor-Rivest ( eng. Chor-Rivest ) [24] [25]

Baserat på algebra i finita fält (Galois-fält) . Låt den publika nyckeln A bestå av element i fältets underfält , det vill säga . Den hemliga nyckeln består av följande element: ${\displaystyle q=p^{h))$ $GF(p)$ $GF(q)$ $(a_{1},a_{2},...a_{p})=GF(p)\in GF(q)$

element av med algebraisk grad $t$ $GF(q)$ $h$
generator från $g$ $GF^{*}(q)$
hela _ $d$ $\mathbb {Z} (q-1)$

Då består den publika nyckeln B av elementen [5] . $b_{i}=d+\log _{g}(t+a_{i})mod(q-1)$

Framtiden för ryggsäckssystem

Idag fokuserar kryptografernas huvudsakliga uppmärksamhet på kryptosystem baserade på heltalsfaktorisering , diskret logaritm och elliptiska kurvor . Forskningen om ryggsäckssystem fortsätter dock, men sådana kryptosystem är inte populära och inger inte förtroende, med tanke på tidigare algoritmers misslyckanden. Om en algoritm kan skapas som fullt ut utnyttjar svårigheten med ryggsäcksproblemet (NP-fullständighet), med hög densitet och med hemliga kryphål svåra att upptäcka, så kommer detta att vara ett system bättre än system baserade på heltalsfaktorisering och diskret logaritm (deras NP-fullständighet har inte bevisats). Dessutom kommer detta system att vara snabbt, vilket innebär att det kommer att kunna konkurrera i hastighet med klassiska system med offentliga nyckel [5] .

För en ryggsäcksvikt kan en iteration av Merkle-Hellman-algoritmen vara mer än 100 gånger snabbare än RSA (med en modul på 500 bitar) [26] . $n=100$

Anteckningar

↑ Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Theory / 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 , sid. 19.1.
↑ 1 2 3 4 5 Schnaer, 2002 , sid. 19.2.
↑ Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssäkerhet : lärobok - M .: MIPT , 2011. - 225 sid. — ISBN 978-5-7417-0377-9
↑ 1 2 3 4 5 6 7 8 Kin Ming Lai. Knapsack Cryptosystems: The Past and the Future . – 2001.
↑ . Math Matrix (engelska) . – 2001.
↑ Publikationer _ _ (inte tillgänglig länk)
↑ 1 2 Ett nytt krypteringssystem med offentlig nyckel för falldörrsryggsäck . — springer.
↑ Jacques Stern- Wikiartikel . — springer.
↑ 1 2 Masakatu Morii, Masao Kasahara. Nytt kryptosystem med offentlig nyckel som använder diskreta logaritmer över GF(p ) . — springer.
↑ Shinya Kiuchi, Yasuyuki Murakami, Masao Kasahara. Nya multiplikativa kryptosystem med offentlig nyckel av knäppsäckstyp .
↑ Hussain Ali Hussain, Jafar Wadi Abdul Sada , Klipha SM Nytt krypteringssystem med offentlig nyckel i flera steg . Arkiverad från originalet den 26 december 2014.
↑ Harald Ritter. Breaking Knapsack Cryptosystems by l-Norm Enumeration . Arkiverad från originalet den 31 mars 2012.
↑ 1 2 Davis Naccache, Jacques Stern. Ett nytt kryptosystem med offentlig nyckel . – 2006.
↑ Om säkerheten för den förbättrade kryptosystemryggsäcken .
↑ En dataskyddsalgoritm har utvecklats som inte ens kvantdatorer kan knäcka . Hämtad 2 november 2015. Arkiverad från originalet 17 augusti 2015. (obestämd)
↑ Salomaa, 1990 , sid. 76.
↑ 1 2 3 4 Salomaa, 1990 , sid. 103.
↑ Salomaa, 1990 , sid. 104.
↑ 1 2 Salomaa, 1990 , sid. 113.
↑ Salomaa, 1990 , sid. 112.
↑ Salomaa, 1990 , sid. 114.
↑ Salomaa, 1990 , sid. 117.
↑ 1 2 B. Chor, R. L. Rivest. Ett kryptosystem med offentlig nyckel av ryggsäckstyp baserat på aritmetik i ändliga fält . — 1988.
↑ Serge Vaudenay. Kryptanalys av Chor-Rivest-kryptosystemet . (inte tillgänglig länk)
↑ A. M. Odlyzko. Uppgång och fall för Knapsack Cryptosystems .

Litteratur

på ryska

Levitin A. V. Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 160-163. — 576 sid. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Robert Sedgwick . Grundläggande algoritmer i C++. Delarna 1-4. Analys. Data struktur. Sortering. Sök = Algoritmer i C++. Delarna 1-4. grunderna. data struktur. Sortering. Sökande. - 3:a. - Ryssland, St. Petersburg: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Tillämpade problem inom grafteori. - M. , 1974. - 232 sid.
V.N. Burkov, D.A. Novikov. Element i grafteori . - 2001. - S. 28.
S. Okulov. Programmering i algoritmer. - 2007. - S. 383.
B. Schneier. Tillämpad kryptografi . - 2:a. - 2002. Arkiverad 28 februari 2014 på Wayback Machine
A. Salomaa. Public Key Cryptography = Public Key Cryptography. - Springer-Verlag, 1990. - S. 102-150. Arkiverad 19 november 2011 på Wayback Machine
Koblitz N. Kurs i talteori och kryptografi - 2:a upplagan - M .: Det vetenskapliga förlaget TVP , 2001. - 254 sid. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5

på engelska

Silvano Martelo, Paolo Toth. Ryggsäcksproblem. - Wiley, 1990. - 306 sid.
David Pisinger. Knapsäcksproblem . - 1995. Arkiverad 22 december 2012 på Wayback Machine
Hans Kellerer, Ulrich Pferschy, David Pisinger. Ryggsäcksproblem. — 1995.

Länkar

Denis Alekseev. Ryggsäcksalgoritm . Yandex.People . _ Datum för åtkomst: 6 december 2012. Arkiverad från originalet den 7 januari 2013. (ryska)
Mikhail Chegodar. Användningen av kryptografi i frågor om dataskydd, till exempel ett ryggsäckskrypteringssystem . Underground Information Center. Hämtad: 6 december 2012. (ryska)

ryggsäcksproblemet
Ansökningar	Knapsäcksproblem i kryptografi Skärningsuppgift
Kryptosystem baserade på ryggsäcksproblemet	Merkla-Hellman Naccasha - Stern Graham - Shamira
Dessutom	Lista över uppgifter om ryggsäck