Рюкзак системалари

РЮКЗАК СИСТЕМАЛАРИ
Биз энди маълумотларни шифрлашнинг рюкзак усулининг математик аппаратини кўрайлик.
Таъриф-1. Рюкзак вектори деб n (n3) та тартибланган натурал сонлардан ташкил топган А = (a₁,...,a_n) векторга айтилади.
Таъриф-2. Рюкзак масаласининг бошланғич маълумотлари деб (A, ) жуфтликка айтилади. Бу ерда A - рюкзак вектори,  - натурал сон. (A, ) маълумотлар учун рюкзак масаласининг ечими деб А нинг шундай қисм тўпламига айтиладики, унинг элементлари йиғиндиси  га тенг бўлади. Бу йиғиндида А нинг ҳар бир элементи фақат бир марта иштирок этади.
Одатда рюкзак масаласи қўйилганда, (A, ) маълумотлар учун масала ечимга эга бўлишини аниқлашга тўғри келади. Криптографияда қўлланаётган вариантда эса шундай ечим мавжуд деган нуқтаи-назардан деб ҳисобланади. Масала NP-тўлиқ масалалар синфига киради.
А рюкзак векторидан фақат иккилик саноқ системасидаги сонлардан ташкил топган С матн блогини шифрлаш учун фойдаланилади. Унда С нинг бир сонига А векторнинг мос ўринларида турган элементлари йиғиндиси олинади. Агар бу йиғиндини  билан белгиласак, рюкзак масаласи А дан фойдаланиб  ни, ёки  дан фойдаланиб А топиш масаласига келади. Бу масалани бошқача қилиб,

кўринишида ҳам ёзиш мумкин. Масалан, n=6 ва А=(3, 41, 5, 1, 21, 10) бўлсин. У ҳолда иккилик (1, 1, 0, 0, 1, 0) ва (1, 0, 1, 1, 0, 1) блоклар мос равишда 65 ва 19 тарзида шифрланади. Берилган А вектор учун шифрланган матн 81 дан кичик бўлган сонлардан ташкил топади ва хар бир матнга фақат битта шифрланган матн мос келади.
А=(14, 28, 56, 82, 90, 132, 197, 284, 341, 455) бўлган вектор учун =515 га мос келувчи шифрланган матн иккита бошланғич матнга мос келади:
f(0, 1, 1, 0, 1, 0, 0, 0, 1, 0)=28+56+90+341=515
f(1, 0, 0, 1, 1, 1, 1, 0, 0, 0)=14+82+90+132+197=515
Аммо, =517 учун (1, 1, 1, 0, 1, 1, 1, 0, 0, 0) вектор ягона бошланғич матн бўлади:
f(1, 1, 1, 0, 1, 1, 1, 0, 0, 0)=14+28+56+90+132+197=517. мкита
Қайта шифрлашнинг бир қийматли бўлиши учун А рюкзак вектори ҳар бир  да барча (А, ) бошланғич маълумотлар учун биттадан ортиқ ечимга эга бўла олмайди. Бундай рюкзак векторларини инъектив деб аталади. Чунки, 1-мисолда қаралган А вектор ёрдамида ҳосил қилинган функция инъективдир.