Problém batohu v kryptografii

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. května 2020; kontroly vyžadují 4 úpravy .

Problém batohu (neboli problém batohu ) v kryptografii ( angl. Knapsack problem ) je problém, na jehož základě američtí kryptografové Ralph Merkle a Martin Hellman vyvinuli první šifrovací algoritmus veřejného klíče . Říká se tomu Merkle-Hellmanův kryptosystém. K šifrování zpráv jsme použili řešení problému s batohem, o kterém je známo, že je NP-hard . Proto se věřilo, že by to mohlo zajistit kryptografickou stabilitu systému. V současné době bylo vytvořeno mnoho kryptosystémů batohů. Téměř všechny existující jsou však dnes hacknuté nebo rozpoznány jako potenciálně nebezpečné.

Historie

Problém batohu je jádrem prvního asymetrického šifrovacího algoritmu (nebo jinak šifrování pomocí veřejného klíče). Myšlenku kryptografie s veřejným klíčem předložili američtí kryptografové Whitfield Diffie , Martin Hellman a nezávisle Ralph Merkle . Poprvé ji představili Diffie a Hellman na National Computer Conference v roce 1976, ve stejném roce vyšla jejich společná práce na toto téma New Directions in Cryptography . ) [1] . Merkleův článek „Secure Communication Over Insecure Channels“ vyšel až v roce 1978 [2] . Novinkou ve vztahu k v té době běžným symetrickým kryptosystémům bylo použití párových klíčů - tajného ( angl. private key, secret key, SK ) a veřejného ( angl. public key, PK ), vytvořených uživatelem. Tajný klíč použitý k dešifrování informací musí uživatel udržovat v tajnosti, zatímco veřejný klíč, který je potřebný pouze pro šifrování, může být zveřejněn. V mnoha kryptosystémech se veřejný klíč získává z tajného klíče [3] [4] .

První šifrovací algoritmus založený na problému batohu byl vyvinut Merklem a Hellmanem v roce 1978 a byl nazván „ Merkle-Hellman Algorithm “ [3] . Vycházel v jednostupňové ( anglicky singly-iterated ) a vícestupňové verzi ( anglicky multiply-iterated ). Algoritmus mohl být použit pouze pro šifrování, ale izraelský kryptoanalytik Adi Shamir jej upravil pro použití v digitálních podpisech [3] . Po zveřejnění schématu nabídl Merkle odměnu 100 dolarů každému, kdo úspěšně prolomí jednofázový algoritmus. V roce 1982 provedl Shamir úspěšný útok a dostal slíbenou odměnu. Ale i po zaplacení byl Merkle přesvědčen o kryptografické síle vícestupňového systému a nabídl 1 000 $ , pokud bude úspěšně prolomen. V roce 1984 se americkému matematikovi Ernestu Brickellovi podařilo dokončit hack pro čtyřicetistupňovou variantu za něco málo přes 1 hodinu na stroji Cray-1 [5] [6] .

Nezávisle na sobě objevili v roce 1980 americký matematik Ron Graham a Adi Shamir způsob, jak zvýšit kryptografickou sílu Merkle-Hellmanova schématu, ale již v roce 1983 bylo výsledné Grahamovo-Shamirovo schéma rozlousknuto americkým vědcem Leonardem Adlemanem . . Pokračovalo však hledání modifikací zbavených nedostatků Merkle-Hellmanova schématu. V roce 1985 britský docent Rodney Goodman a americký inženýr Anthony McAuley vytvořili obvod založený na modulárních zádách s tajnou mezerou, která není založena na superzvyšujících vektorech , ale s použitím čínské věty o zbytku [7] [8] .

Následně se ukázalo, že schéma je zranitelné vůči útokům založeným na hledání tajných mezer. V roce 1990 však Valtteri Niemi navrhl nové schéma založené na stejném úkolu modulárního batohu. To bylo rozluštěno hned příští rok Chi Ye Meng , Antoine Zhu , a Jacques Stern [9] nezávisle na sobě, s použitím mírně odlišných metod. Kromě použití modulárních batohů se objevily pokusy použít i jiné typy batohů.

V roce 1986 tedy Harald Niederreiter publikoval batohový kryptosystém založený na teorii algebraického kódování, který byl později rozbit a v roce 1988 Masakatsu Morii a Masao Kasahara vyvinuli batohový kryptosystém využívající multiplikativní batoh [10] . Tento nápad se ukázal jako úspěšný a zatím nebyl systém na multiplikativních batozích hacknut.

V roce 2001 Shinya Kiuchi , Yasuyuki Murakami a Masao Kasahara navrhli vylepšení schématu Moriya-Kasahara založeného na multiplikativních batohech využívajících algoritmus Schalkwijk [11] .

Úspěšný byl také nápad Husseina Aliho Husseina , Jafara Wadiho Abdula Sada a M. Khalify , kteří v roce 1991 navrhli vícestupňový zádový kryptosystém ( anglicky multistage trapdoor knapsack cryptosystem ). Opraví zádový vektor pro každou fázi a výstup (šifrovaný text) po každé fázi algoritmu se použije jako vstup (text) do další fáze. Žádný úspěšný útok na toto schéma není znám (k roku 2001) [12] .

Qu Minghua a Scott Vanstone v roce 1992 navrhli hybridní kryptosystém, který je primárně založen na problému batohu, ale zahrnuje také logaritmické podpisy. V roce 1994 R. Blackburn , Murphy, Sean a Jacques Sternovi ukázali, že zjednodušená verze kryptosystému U-Waston není bezpečná. Tyto kryptosystémy důkladněji studovali Fong Nguyen a Jacques Stern v roce 1997 [5] .

Pokračovalo také vylepšování klasického Merkle-Hellmanova algoritmu. V roce 1994 navrhl Orton modifikaci vícestupňového Merkle-Hellmanova schématu, ale o dva roky později jej naboural Ritter [13] .

V roce 1995 byly navrženy dva nové přístupy k problému najednou. První, založený na diofantických rovnicích , je způsoben Lin Zhuxingem , Zhang Zhenchengem a Li Jia Tongem . Téměř okamžitě Lai Qisong a Blackburn, Murphy, Sean a S. G. Paterson nezávisle na sobě ukázali, že tento kryptosystém není bezpečný.

Druhý přístup, založený na multiplikativním problému batohu, navrhl David Naccache a Jacques Stern [14] . Nakkashe a Stern nabídli DM 1024 někomu, kdo úspěšně prolomil jejich krypto schéma, ale nebyly žádné informace, že by tuto odměnu ještě někdo dostal (stav 2001) [5] .

V roce 1996 Kunikatsu Kobayashi a Masaki Kimura navrhli vylepšený kryptosystém batohu založený na nové koncepci, kde si odesílatel může vybrat šifrovací klíč z celé sady klíčů. O dva roky později Hidenori Kuwakado a Hatsukazu Tanaka ukázali, že systém je potenciálně nejistý [15] .

Poslední verzi algoritmu navrhli B. Shor a R. L. Rivest v roce 2006. V roce 2002 byl algoritmus Chor-Rivest považován za bezpečný [3] .

V roce 2015 bylo oznámeno, že Nathan Hamlin a William Webb z Washington State University vytvořili algoritmus batohu bez nedostatků předchozích implementací [16] .

Od té doby bylo navrženo mnoho algoritmů veřejného klíče, které nejsou založeny na systémech batohů. Nejznámější z nich jsou: RSA , EIGamal a Rabin . Lze je použít jak pro šifrování, tak pro digitální podpisy. Jsou však pomalé a nehodí se pro rychlé šifrování/dešifrování velkých objemů zpráv. Řešením tohoto problému jsou hybridní kryptosystémy, zprávy jsou šifrovány rychlým symetrickým algoritmem s náhodným klíčem a algoritmus veřejného klíče se používá k šifrování samotného náhodného (relačního) klíče.

Prohlášení o problému

Problém batohu je následující: je dána množina odlišných kladných celých čísel. Nechť existuje číslo , které je také celé a kladné. Úkolem je najít takovou množinu , aby se sčítaly přesně . Je jasné, že řešení tohoto problému ne vždy existuje. $A=(a_{1},...,a_{n})$ $n$ $k$ $a_{i}$ $k$

Podle definice systémů s veřejným klíčem potřebujete k úspěšnému šifrování/dešifrování mít dva klíče. Oprávněný příjemce zprávy zná tajný klíč A, zatímco odesílatel má pouze veřejný klíč B. Jak můžete zabránit útočníkovi v dešifrování zprávy, když zná veřejný klíč? Odpověď je jednoduchá, veřejný klíč musí být odvozen od soukromého klíče pomocí nějaké transformace f, která má následující dvě vlastnosti [17] :

Je snadné vypočítat vědět $B=f(A)$ $A$
Určit , znát , je pravděpodobně obtížný úkol. $A=f^{-1}(B)$ $B$

Jako obtížné problémy jsou obvykle považovány NP-úplné problémy, takže problém s batohem je vhodný pro budování systémů s veřejným klíčem.

Šifrování s problémem batohu

Zpráva je zašifrována jako řešení sady problémů s batohem [2] .

Def. Batohový vektor je uspořádaná množina n položek [18] .

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

Pro šifrování otevřeného textu v binární reprezentaci je rozdělen do bloků délky ( odpovídá například 5 položkám v batohu). Předpokládá se, že jednička označuje přítomnost předmětu v batohu a nula jeho nepřítomnost. Existují dva způsoby šifrování: $n$ $(11100)$

1) Šifru zprávy získáme zvýšením prvků batohového vektoru na mocninu jim odpovídajících bitů zašifrované zprávy a dalším vynásobením výsledků, tedy pokud , a zprávy , pak bude šifra číslo . Tato metoda se nazývá multiplikativní [5] . $A=(2,3,5)$ $(100)$ $2^{1}*3^{0}*5^{0}=2$

2) Šifru zprávy získáme vynásobením prvků batohového vektoru odpovídajícím bitem zašifrované zprávy a následným sečtením výsledků, tedy if , a zprávy , pak bude šifrou číslo . Tato metoda se nazývá aditivní [5] . $A=(2,3,5)$ $(100)$ $2*1+3*0+5*0=2$

Příklad šifrovaného textu získaného aditivním algoritmem.

Nechť je dán vektor batohu Α = (3 4 6 7 10 11) o délce n = 6.

prostý 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
věci v batohu	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11
šifrovaný text	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	jedenáct

Pro dané Α jsou všechny kryptosystémy čísly nepřesahujícími 41, celkovou hmotností všech položek ve vektoru batohu. Pro každý otevřený text existuje pouze jeden kryptotext.

Složitost šifry spočívá ve skutečnosti, že existují dva problémy batohu: „snadný“ a „těžký“. „Snadný“ problém lze vyřešit v lineárním čase, „těžký“ nikoli. Veřejný klíč je „těžký“ problém, protože jej lze snadno zašifrovat a nelze jej dešifrovat. Soukromý klíč je „snadný“ problém, protože usnadňuje dešifrování zprávy. Při absenci soukromého klíče je třeba vyřešit problém „tvrdého“ batohu. Merkle a Hellman pomocí modulární aritmetiky vyvinuli způsob, jak přeměnit „snadný“ batoh na „obtížný“ [2] .

"Snadný" problém

Pro některé vektory Α je problém s batohem snadno vyřešen. Tuto vlastnost mají superrostoucí vektory [2] .

Def. Batohový vektor se nazývá supergrowing , jestliže for , tj. každý člen posloupnosti je větší než součet předchozích [18] .

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

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

j=2,...,n

Příklad

Nechť celkovou hmotnost batohu a batohového vektoru uvedeme jako superrostoucí . $P=70$ $A=(2,3,6,13,27,52)$

Pro tento batohový vektor je algoritmus pro řešení problému s batohem jednoduchý. Vezme se největší váha, 52. Od 52 < 70 se odpovídající předmět umístí do batohu. Volný prostor v batohu se rovnal 70 - 52 = 18. Dále si vezměte předmět s hmotností 27. Od 27 > 18 se tento předmět do batohu nedostane. Do batohu se vejde třetí předmět o váze 13 < 18, zbyde volných 5. Další předmět o váze 6 se nevejde. Podobně se do batohu vkládají předměty s hmotností 2 a 3. Zbytková hmotnost batohu se stala 0, řešení bylo nalezeno!

"Tvrdý" problém

Normální batoh není se supernarůstajícím batohovým vektorem A. Jediný způsob, jak vyřešit takový problém, je testovat všechny možné, dokud se nenajde správné řešení. Nejrychlejší algoritmus má exponenciální závislost na počtu položek [2] .

Šifrovací systém s veřejným klíčem založený na problému batohu

Stejně jako dříve je vektor A tajný klíč a vektor B je veřejný klíč.

Vytvoření veřejného klíče ze soukromého

Pro celá čísla a označte . $X$ $m\geq 2$ $(x,modm)=x-[x/m]m$

Nechť je superzvyšující se vektor batohu. Zaveďme celé číslo a přirozené číslo takové, že největší společný dělitel je . $A=(a_{1},...,a_{n})$ ${\displaystyle m>\sum _{i=1}^{n}a_{i))$ $t<m$ $(t,m)=1$

Def. Pokud takové, že pro , pak říkáme, že je získáno ze silného modulárního násobení [18] .

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

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

i=1,..,n

B

A

Tvůrce kryptosystému volí parametry tak, že A je superrostoucí a B se získává z A silným modulárním násobením vzhledem k mat. $A,B,t,m$

Platné lemma [19] : Nechť A je superrostoucí vektor a B získáme z A silným modulárním násobením vzhledem k mat. Předpokládejme, že u = 1/t, β je libovolné přirozené číslo a α =(uβ,modm). Pak platí, že:

Problém batohu se vstupními daty (A,α) je řešitelný v lineárním čase, a pokud řešení existuje, pak je jedinečné;
Problém batohu se vstupními daty (B,β) má nejvýše jedno řešení;
Pokud existuje vstupní řešení (B,β), pak je stejné jako jediné vstupní řešení (A,α).

Příklad

Vytvoření vektoru B z vektoru A [18] .

Nechť je dán superrostoucí vektor (tajný klíč) s . Součet jeho složek je 55 205. Zvolte , a . Pak je podmínka splněna. $A=(103,107,211,430,863,1718,3449,6907,13807,27610)$ $n=10$ $m=55207$ $t=25236$ $(t,m)=1$

Nachází se podle vzorce . V tomto případě: $t^{-1}modm$ $(tu)modm=1$

1061 * 25236 - 1= 485 * 55207

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

Veřejný klíč B se vypočítá podle a α =(uβ,modm). Například pro $b_{i}=(ta_{i},modm)$ ${\displaystyle a_{1},a_{6},a_{10))$

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

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

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

Po provedení podobných výpočtů pro zbývající prvky se získá vektor $B=(4579,50316,24924,30908,27110,17953,32732,16553,22075,53620)$

Šifrování

Použijte veřejný klíč B a zašifrujte zprávu: DEATH GODS EAT ONLY APPLES

Nejprve je použito číselné kódování, mezera má přiřazenu hodnotu 0, písmena A až Z mají hodnotu 1 až 26. Číselné kódy jsou vyjádřeny v binárních množinách. Protože vektor B má délku 10, lze jej použít k šifrování bloků dvou písmen najednou. Blokový kód se stejně jako dříve získá sečtením hmotností položek obsažených v batohu. $bi}$

Zdrojový textový blok	binární kód	Blokový kód
DE	00100 00101	95097
V	00001 10100	61616
H	01000 00000	50316
JÍT	00111 01111	207922
D.S.	00100 10011	118572
E	00000 00101	70173
V	00001 10100	61616
Ó	00000 01111	124980
NL	01110 01100	155433
Y	11001 00000	82005
AP	00001 10000	45063
PL	10 000 01 100	53864
ES	00101 10011	149480

Dešifrování

Pojďme dešifrovat první číslo 95 097. To stojí za zmínku

1061*95097 = 1827*55207 + 34728

Zvažuje se problém batohu (A.34728). Řešení se získá pohledem na zádový vektor A zprava doleva. Když číslo v levém sloupci není menší než aktuálně zobrazená složka A, zapíše se 1 a nové číslo v levém sloupci se získá odečtením složky od předchozího čísla. Jinak se zapíše 0 a číslo v levém sloupci se nemění. Výsledek je uveden v tabulce:

Číslo	Složka A	Symbol
34728	27610	jeden
7118	13807	0
7118	6907	jeden
211	3449	0
211	1718	0
211	863	0
211	430	0
211	211	jeden
0	107	0
0	103	0

Čtením pravého sloupce odspodu nahoru vznikne binární vektor 00100 00101, tj. DE.

Předpokládejme, že jsme se pokusili jednat v opačném pořadí. Šifrování by bylo provedeno pomocí vektoru A a získalo by se určité číslo a. Pak ale dvojice (B,a) neměla řešení, protože obvyklou rovnost čísel nelze odvodit z jejich rovnosti modulo.

Zabezpečení

Bezpečnost batohových systémů

U malých batohových vektorů je problém s batohem snadno řešitelný i ručně. Skutečný batoh by měl obsahovat velké množství prvků. Otevření takového batohu hrubou silou, tedy rozbití, bude obtížný (nemožný) úkol. Systémy batohů však nejsou bezpečné pro kryptoanalýzu . Shamir a Zippel ( angl. Zippel ) zjistili, že se znalostí čísel ( "tajná mezera" ) můžete obnovit supernarůstající vektor z normálního otevřeného vektoru [3] . Důležité je, že čísla („tajná dvojice“) nemusí být stejná jako ta, která byla použita při vytváření systému legálním uživatelem. Stačí najít libovolný pár , takový, který nám dá superrostoucí vektor [20] . $t,t^{-1},m$ $A$ $B$ $t,m$ $(t',m')$ $B*(t'modm')$

Jak hledat tajnou skulinku

Problém: Je známo, že jako veřejný klíč se používá zádový vektor. Získává se z A, supernarůstajícího vektoru, silným modulárním násobením vzhledem k modulu m a číslu t. Potřebujeme najít A,t, m, které nám nejsou známy, nebo spíše m a (můžeme z nich vypočítat A). S jejich znalostí lze dešifrovat kryptotext [21] . $B=(b_{1},...,b_{n})$ $t^{-1}=u$

Hledání tajného páru

Níže popsaný přístup navrhl A. Shamir . Výsledný algoritmus poběží v polynomiálním čase. Měli bychom však být opatrní při výběru velikosti vektoru B, s ohledem na který je algoritmus polynomiální. Stojí za to připomenout, že velikost vektoru B závisí na počtu složek n a velikosti . Proto existují omezení pro jejich výběr. $bi}$

Fixujeme konstantu úměrnosti a složky superrostoucího vektoru A, skládající se z bitů. Protože nejvýznamnější číslice v každé ze složek je jedna, pak A je superrostoucí a m je zvoleno tak, aby bylo větší než součet složek zádového vektoru A [20] . $d>1$ $a_{i},i=[1,n]$ $[dn]-1-n+i$

Pro konstrukci algoritmu není nutné hledat u a m, která se skutečně používají pro šifrování. Jakýkoli pár (u, m) způsobí, říkejme tomu tajný pár , splňující omezení pro silné modulární násobení s ohledem na B, že vektor A v důsledku tohoto násobení superroste a m je větší než součet jeho součásti. Po nalezení alespoň jednoho tajného páru aplikujeme lemma a zahájíme dešifrování. Jeho existence je zřejmá, jelikož tvůrce kryptosystému jeden takový pár při šifrování použil.

Pro přehlednost sestrojíme grafy funkcí . Jedná se o přímé úsečky s body nespojitosti , . $b_{i}u$ $(modm)$ ${\displaystyle u=pm/b_{i))$ $p=1,2,...$

Pamatujte, že budeme psát: $b_{i}=(ta_{i},modm)$ $t^{-1}=u$

$(b_{1}u,modm)=a_{1}$ , kde je požadovaný inverzní faktor, je první složkou vektoru , je podle předpokladu velmi malý ve srovnání s . To znamená, že hodnota je blízká minimu funkce . $u$ $a_{1}$ $A$ $m$ $u$ $b_{1}$

Hodnota pro je blízká minimu funkce . Pak dvě minima funkcí a jsou blízko u sebe. Lze tedy uvažovat i o zbytku pilových křivek. Je jasné, že minima všech těchto křivek jsou blízko u sebe. Je možné sestavit malý interval obsahující „akumulační body“ minim pilových křivek [22] . Na základě tohoto malého intervalu je také nalezena hodnota tajného páru. $(b_{2}u,modm)=a_{2}$ $u$ $b_{2}$ $b_{1}$ $b_{2}$ $n$ $u$

Protože neznáme hodnotu modulu, změníme měřítko obrázku tak, aby se rovnal 1 (všechny délky vydělte ). $m$ $m$ $m$

Algoritmus pro nalezení tajného páru:

1) Nalezení kandidátů na celé číslo tak, aby té minimum funkce bylo požadovaným akumulačním bodem. $p$ $p$ $b_{1}$

Aby počet kandidátů nebyl příliš velký, zavádíme pevný parametr – maximální počet povolených kandidátů. $r$

V první části algoritmu není nutné uvažovat všechny najednou , je třeba zavést parametr a zvážit komponentu. ${\displaystyle b_{2},...,b_{n))$ $s<n$ $s$

$p/b_{1}$ -souřadnice -tého minima na křivce . $u$ $p$ $b_{1}$

Podmínku pro blízkost minim křivek a lze zapsat jako následující nerovnosti: $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$

Vynásobte první nerovnost : ${\displaystyle b_{1}b_{2))$

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

Celkem takové nerovnosti , jedna pro každou $s-1$ $b$

První část algoritmu tedy dává všechna taková přirozenost, pro která existují přirozená , taková, že jsou splněny všechny nerovnosti. $p$ $q$ $s-1$

2) Postupné ověřování každého z kandidátů.

V druhé části algoritmu jsou všechny zkontrolovány . Kandidát bude odmítnut, pokud pro některé neexistuje žádné minimum křivky ležící blízko --tého minima křivky . $i=[2,n]$ $p$ $i$ $bi}$ $p$ $b_{1}$

Opravit . Uspořádejte ve vzestupném pořadí všechny body přerušení v intervalu . Vezměme dva sousední body ze seřazeného seznamu a . V jimi tvořeném intervalu je každá křivka úsečkou (rovnice tyto úseky popisuje). $p$ $[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))$

Na základě výše uvedeného zapíšeme systém nerovností:

$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]$ - stav přerůstání

Pro dvě čísla a pro vytvoření tajné dvojice je nutné a postačující, aby patřila do takto konstruovaného intervalu pro nějakou dvojici . , kandidát z první části algoritmu a index bodů ze seřazeného seznamu bodů odpovídajících danému . $u$ $m$ $u/m$ $(p,j)$ $p$ $j$ $p$

Vyhledávání se ukončí, když je nalezen neprázdný interval . $[x_{i},x_{i}+1]$

Příklad [23] .

Nechť má veřejný klíč tři složky $B=(7,3,2)$

1) Podle výše uvedených nerovností:

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

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

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

V tabulce jsou uvedeny nejmenší hodnoty , u kterých nerovnosti platí: $E$

p	jeden	2	3	čtyři	5	6
E	5	3	2	2	3	5

2) Je vidět, že všechny hodnoty jsou vhodnými kandidáty (v obecném případě to tak být nemusí). Proto rozdělíme interval na dílčí intervaly: takové, že všechny tři křivky jsou v každém redukovaném intervalu úsečky . $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)$ $bi}$ $(b_{i}u-const_{i}^{j})$

Zapišme si nerovnosti:

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

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

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

Konstanty se mění v rámci , , v závislosti na volbě intervalu. $0\leq i\leq 6$ $0\leq i'\leq 2$ $0\leq i'''\leq 1$

Pomocí zápisu , přepíšeme nerovnosti do jednoduššího tvaru : $i=1+i'+i''+i'''$ $j=i'-i''$ $k=i'+i''-i'''$

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

Shromážděme v tabulce všechny hodnoty konstant pro různé intervaly:

Časový úsek	1/7	2/7	1/3	3/7	1/2	4/7	2/3	5/7	6/7	jeden
já'	0	jeden	2	2	3	3	čtyři	čtyři	5	6
i	0	0	0	jeden	jeden	jeden	jeden	2	2	2
i	0	0	0	0	0	jeden	jeden	jeden	jeden	jeden
i	jeden	2	3	čtyři	5	6	7	osm	9	deset
j	0	jeden	2	jeden	2	2	3	2	3	čtyři
k	0	jeden	2	3	čtyři	3	čtyři	5	6	7
12u<i	ČÁST	ČÁST	NE	NE	NE	NE	ČÁST	NE	ČÁST	NE
4u<j	NE	ČÁST	SAT	NE	SAT	NE	SAT	NE	ČÁST	SAT
8u<k	NE	NE	NE	ČÁST	SAT	NE	NE	NE	ČÁST	ČÁST

Poslední tři řádky označují, zda je každá z nerovností pravdivá nebo ne: SAT - pravda, ČÁST-částečně pravdivá (objeví se, když je nerovnost pravdivá na pravé straně podintervalu), NOT - nepravda (objeví se, když nerovnost není true na levé straně subintervalu).

Interval generuje tajný pár tehdy a pouze tehdy, když jsou ve sloupci všechny tři buď SAT nebo PART. Jediný takový interval Výběrem čísla z intervalu, například (tj. ), dostaneme super rostoucí vektor . $(5/7,3/4)$ $8/11$ $m=11$ $A=(1,2,5)$

Varianty problému batohu v kryptografii

1) Batoh Merkle-Hellman ( ang. Merkle-Hellman Cryptosystem ).

Veřejný klíč A je supernarůstající vektor, tajný klíč B se získává z A silným modulárním násobením.

2) Batoh Graham-Shamir ( ang. Graham-Shamir Cryptosystem ) [5] .

Veřejný klíč A je supernarůstající vektor. Jeho prvky jsou zapsány v bitové reprezentaci. Dále jsou generována náhodná čísla, nazývaná šum. Jejich bitová reprezentace je přidána k bitům vektoru batohu vlevo, tedy v nejvýznamnějším bitu.

Řekněme, že zvolíme vektory . Přidáme do něj předpony z náhodně vybraných čísel: $A=(1,3,5)$

binární reprezentace	s náhodnou předponou
1=001	101 001 = 41
3=011	111 011 = 59
5 = 101	100 101 = 37

Výsledný vektor batohu nemá superzvětšovací vlastnost. Přidáním náhodného šumu se tedy skryje vlastnost přerůstání původního vektoru A a obvod se stává bezpečnějším [24] . $(41,59,37)$

3) Morii-Kasahara Backpack ( eng. Morii-Kasahara Cryptosystem ) [10]

Schéma je podobné schématu Merkle-Hellman, ale používá metodu multiplikativního šifrování pro veřejný klíč i tajný klíč.

Nechte vektor . Vybereme , prvočíslo (v tomto schématu ) a , takové, že . Tajný klíč B se získá z A podle vzorce , tj . Nechte zprávu zašifrovat a poté šifru . $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) Batoh Goodman -McAuley Cryptosystem [ 8] .

Stejně jako v prvním schématu v batohu Goodman-McCauley se k získání veřejného klíče z tajemství používá modulární násobení, ale tajný klíč není vektorem supernarůstajícího. Schéma je založeno na složitosti celočíselného faktorizace, proto je podobné kryptosystému RSA.

5) Batoh Nakashe-Stern ( ang. Naccache-Stern Cryptosystem ) [14] .

Toto schéma kombinuje dvě metody: batoh Merkle-Hellman a algoritmus Polyg-Hellman . Dané prvočíslo , S je podmnožina ( eng. subset product ) a batohový vektor , kde všechna jsou relativně prvočísla. Musíme najít takový binární vektor $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) Batoh Shor-Rivest ( ang. Chor-Rivest ) [24] [25]

Na základě algebry v konečných tělesech (Galoisova pole) . Nechť veřejný klíč A sestává z prvků podpole pole , tj . Tajný klíč se skládá z následujících prvků: ${\displaystyle q=p^{h))$ $GF(p)$ $GF(q)$ $(a_{1},a_{2},...a_{p})=GF(p)\in GF(q)$

prvek s algebraickým stupněm $t$ $GF(q)$ $h$
generátor z $G$ $GF^{*}(q)$
celý _ $d$ $\mathbb {Z} (q-1)$

Poté se veřejný klíč B skládá z prvků [5] . $b_{i}=d+\log _{g}(t+a_{i})mod(q-1)$

Budoucnost batohových systémů

Hlavní pozornost kryptografů se dnes soustředí na kryptosystémy založené na celočíselné faktorizaci , diskrétním logaritmu a eliptických křivkách . Výzkum systémů batohů však pokračuje, ale takové kryptosystémy nejsou populární a nevzbuzují důvěru, vzhledem k selháním předchozích algoritmů. Pokud se podaří vytvořit algoritmus, který plně využívá obtížnost problému batohu (NP-úplnost), s vysokou hustotou a s těžko odhalitelnými tajnými mezerami, pak to bude systém lepší než systémy založené na faktorizaci celých čísel a diskrétním logaritmu (jejich NP-úplnost nebyla prokázána) . Navíc bude tento systém rychlý, což znamená, že bude schopen konkurovat v rychlosti klasickým systémům s veřejným klíčem [5] .

Pro hmotnost batohu může být jedna iterace Merkle-Hellmanova algoritmu více než 100krát rychlejší než RSA (s modulem 500 bitů) [26] . $n=100$

Poznámky

↑ Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1976. - Sv. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 – doi:10.1109/TIT.1976.1055638
↑ 1 2 3 4 5 Schnaer, 2002 , str. 19.1.
↑ 1 2 3 4 5 Schnaer, 2002 , str. 19.2.
↑ Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informační bezpečnost : učebnice - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
↑ 1 2 3 4 5 6 7 8 Kin Ming Lai. Kryptosystémy batohu: Minulost a budoucnost . — 2001.
↑ . Matic Matrix (anglicky) . — 2001.
↑ Publikace _ _ (nedostupný odkaz)
↑ 1 2 Nový kryptosystém s veřejným klíčem na padací dveře . — špringer.
↑ Jacques Stern- Wiki Článek . — špringer.
↑ 1 2 Masakatu Morii, Masao Kasahara. Nový kryptosystém s veřejným klíčem využívající diskrétní logaritmy přes GF(p ) . — špringer.
↑ Shinya Kiuchi, Yasuyuki Murakami, Masao Kasahara. Nové multiplikativní kryptosystémy s veřejným klíčem typu batohu .
↑ Hussain Ali Hussain, Jafar Wadi Abdul Sada , Klipha SM Nový vícestupňový kryptosystém s veřejným klíčem . Archivováno z originálu 26. prosince 2014.
↑ Harald Ritter. Prolomení kryptosystémů batohu podle l-Norm Enumeration . Archivováno z originálu 31. března 2012.
↑ 1 2 Davis Naccache, Jacques Stern. Nový kryptosystém s veřejným klíčem . — 2006.
↑ O bezpečnosti vylepšeného batohu kryptosystému .
↑ Byl vyvinut algoritmus ochrany dat, který ani kvantové počítače nemohou prolomit . Získáno 2. listopadu 2015. Archivováno z originálu 17. srpna 2015. (neurčitý)
↑ Salomaa, 1990 , str. 76.
↑ 1 2 3 4 Salomaa, 1990 , str. 103.
↑ Salomaa, 1990 , str. 104.
↑ 1 2 Salomaa, 1990 , str. 113.
↑ Salomaa, 1990 , str. 112.
↑ Salomaa, 1990 , str. 114.
↑ Salomaa, 1990 , str. 117.
↑ 1 2 B. Chor, R. L. Rivest. Kryptosystém s veřejným klíčem typu batohu založený na aritmetice v konečných polích . — 1988.
↑ Serge Vaudenay. Kryptoanalýza kryptosystému Chor-Rivest . (nedostupný odkaz)
↑ A. M. Odlyzko. Vzestup a pád kryptosystémů batohu .

Literatura

v Rusku

Levitin A. V. Algorithms. Úvod do vývoje a analýzy - 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. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Robert Sedgwick . Základní algoritmy v C++. Části 1-4. Analýza. Datové struktury. Řazení. Hledání = Algoritmy v C++. Části 1-4. základy. datové struktury. Řazení. Hledání. - 3. - Rusko, Petrohrad: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
V. N. Burkov, I. A. Gorgidze, S. E. Lovetsky. Aplikované problémy teorie grafů. - M. , 1974. - 232 s.
V. N. Burkov, D. A. Novikov. Prvky teorie grafů . - 2001. - S. 28.
S. Okulov. Programování v algoritmech. - 2007. - S. 383.
B. Schneier. Aplikovaná kryptografie . - 2. - 2002. Archivováno 28. února 2014 na Wayback Machine
A. Salomaa. Šifrování veřejného klíče = Public-Key Cryptography . - Springer-Verlag, 1990. - S. 102-150. Archivováno 19. listopadu 2011 na Wayback Machine
Koblitz N. Kurz teorie čísel a kryptografie - 2. vydání - M .: Vědecké nakladatelství TVP , 2001. - 254 s. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5

v angličtině

Silvano Martelo, Paolo Tóth. Problémy s batohem. - Wiley, 1990. - 306 s.
David Pisinger. Problémy s batohem . - 1995. Archivováno 22. prosince 2012 na Wayback Machine
Hans Kellerer, Ulrich Pferschy, David Pisinger. Problémy s batohem. — 1995.

Odkazy

Denis Alekseev. Algoritmus batohu . Yandex.People _ _ Datum přístupu: 6. prosince 2012. Archivováno z originálu 7. ledna 2013. (Ruština)
Michail Chegodar. Využití kryptografie ve věcech ochrany dat na příkladu šifrovacího systému batohu . Podzemní informační centrum. Staženo: 6. prosince 2012. (Ruština)

Problém s batohem
Aplikace	Problém batohu v kryptografii Řezací úkol
Kryptosystémy založené na problému batohu	Merkla-Hellman Naccasha - Stern Graham - Shamira
dodatečně	Seznam úkolů o batohu