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

Лемма-1. Фараз қилайлик, А=(a₁, ..., a_n) вектор тез ўсувчан ва В вектор А дан m ва t ларга нисбатан кучли модул бўйича кўпайтириш орқали ҳосил қилинган бўлсин. Шунингдек, u=t^-1 (mod m), ( —ихтиёрий натурал сон ва =(u, mod m) бўлсин. У холда қуйидаги тасдиқлар ўринли:
а) (А, ) рюкзак ҳақидаги масалани чизиқли вақтга нисбатан ечиш мумкин. Агар бу масаланинг ечими мавжуд бўлса, у ягона;
б) (В, ) рюкзак ҳақидаги масала биттадан ортиқ ечимга эга эмас;
в) Агар (В, ) бошланғич маълумотлар учун ечим мавжуд бўлса, у (А,) бошланғич маълумотлар учун ечим билан устма-уст тушади. .
Исбот. а) 1-мисолда А тез ўсувчан векторли рюкзак масаласи А ни ўнгдан чапга қараб чизиқли вақт мобайнида бир марта ўқиш орқали ечим мумкинлиги кўрсатилган эди. Бу усул масаланинг ечимлари кўпи билан битта эканлигини хам кўрсатади. (б) ва (в). Фараз қилайлик, узунлиги n га тенг бўлган D иккилик вектор (В, ) масаланинг ечими, яъни BD= бўлсин. Демак,

m сони А вектор компоненталари йиғиндисидан катта бўлгани учун AD. Шунингдек, <m бўлгани учун таърифга кўра =AD деб ёза оламиз. Шундай қилиб, D вектори (А, ) масаланинг ечими билан устма-уст тушади. Бу в) шартни кўрсатади. Биз (B, ) масаланинг ихтиёрий ечимини қараётганимиз ва у (А, ) масаланинг ечими билан устма-уст тушишини кўрсатганимиз учун б) хам келиб чиқади.
Биз лемма иловасидан бидламизки, (В, ) масала олдиндан ечимга эга.  буни кафолатлайдиган усул билан ҳисоблаб топилган эди.
Мисол-2. n=10 бўлсин. Қуйидаги тез ўсувчан векторни кўрайлик:
А = (103, 107, 211, 430, 863, 1718, 3449, 6907, 13807, 27610) .
А нинг копоненталаридан 2 га катта бўлган m=55207 модулини олайлик. Шунингдек, t=25236 кўпайтувчини ҳам танлаймиз. У холда (t, m)=1 ва t^-1 = u = 1061. Ҳақиқатдан ҳам,
1061  25236 - 1 = 485  55207 .
Кучли модул бўйича кўпайтириш натижасида қуйидаги векторга эга бўламиз:
В=(4579, 50316, 24924, 30908, 27110,17953, 32732,16553, 22075, 53620) .
Масалан,
25236  103 = 4579 + 47  55207 ва 1061  4579 = 103 + 88  55207 ,
25236  1718 = 17953 + 785  55207 ва 1061  17953 = 1718 + 345  55207 ,
2523627610 = 53620 + 1262055207 ва 106153620 = 27610+103055207.
B вектор шифрлашнинг очиқ калити ҳисобланади. A, t, u ва m лар эса махфий калитни ташкил қилади. Албатта, m ва t ларни билган киши қолган миқдорларни ҳам ҳисоблаб топиши мумкин.
Очиқ B калитдан фойдаланиб, “BITIRUV MALAKAVIY ISHI HIMOYASI” матнини шифрлаймиз. Бунинг учун матнни рақамлар ёрдамида кодлаб оламиз. Унда “бўш жой” белгиси-0, қолган ҳарфлар эса лотин алифбесида турган ўрнига қараб, 1-26 бўлган қийматларни олади. Рақамли кодларни иккилик саноқ системасида ифодалаймиз. Бунда 1-мисол учун ёзилган жадвалдан фойдаланамиз.
B вектор узунлиги 10 га тенг бўлган иккиталик блокларни шифрлашга мўлжаллангани учун биз матнни иккитадан харфли блокларга ажратамиз. Қуйидаги жадвалда ана шу блоклар, уларнинг иккилик саноқ системаисдаги ифодаси ва блокнинг 10 лик саноқ системасидаги шифри келтирилган.

BI	00010 01001	117260	Y	11001 00000	82005
TI	10100 01001	115855	IS	01001 10011	171074
RU	10010 10101	123613	HI	01000 01001	136668
V	10110 00000	60411	H	00000 01000	32732
MA	01101 00001	155970	IM	01001 01101	180331
LA	01100 00001	128860	OY	01111 11001	237563
KA	01011 00001	161954	AS	00001 10011	120758
VI	10101 01001	142965	I	01001 00000	77426

Биринчи сонни, яъни 117260 ни қайта шифрлайлик. Шуни таъкидлаш жоизки,
1061 • 117260 = 2253 • 55207 + 31489 .
Энди рюкзак масаласини (А, 25133) бошланғич маълумотлар учун ечамиз. Бунинг учун А векторни ўнгдан чапга қараб кўриб чиқамиз. Чап устундаги сон А нинг қаралаётган компонентасидан кичик бўлмаса, бирни ёзамиз ва янги сонни А нинг компонентасини қаралаётган сондан айирамиз. Акс холда 0 ёзамиз ва А нинг навбатдаги чап компонентасига ўтамиз. Ушбу амалларнинг натижаси қуйидаги тартибда ҳосил қилинади.

қаралаётган сон	А нинг компонентаси	харф
31489	27610	1
3879	13807	0
3879	6907	0
430	3449	1
430	1718	0
430	863	0
0	430	1
0	211	0
0	107	0
0	103	0

Ўнг томондаги устунни пастдан юқорига қараб ўқиймиз: 0001001001. Бу иккилик кодларни биринчи мисолдаги алфавит жадвали бўйича бошланғич матннинг дастлабки икки харфини, яъни “BI” ни билдиради. Иккинчи сонни хам шу усул билан қайта шифрлайлик.
1061 • 115855 = 2226 • 55207 + 31373 .

қаралаётган сон	А нинг компонентаси	харф
31373	27610	1
3763	13807	0
3763	6907	0
3763	3449	1
314	1718	0
314	863	0
314	430	0
314	211	1
103	107	0
103	103	1

Охирги устунни пастдан юқорига қараб ўқиймиз ва 1010001001 ни ҳосил қиламиз. Бу эса алфавит жадвали бўйича “ TI ” блогини англатади. Қолган сонларни ҳам шу тариқа қайта шифрлаб, биз бошланғич матнни ҳосил қиламиз.
Биз келтирган хар икки мисол рюкзак масаласи алгоритмини баён этиш учун турли параметрларни кичиклаштириб олинди. Уларни оддий чўнтак калькулятори ёрдамида ҳам бажариш мумкин.
Ҳақиқатда эса бу параметрлар етарлича катта сонлардан иборат бўлади. Масалан, n=20 бўлган ҳолини Киммо-Кари томонидан бажарилган. У бундай ҳолат учун m=53939986 ва t=54377 деб олиб, бу параметрлар учун t^-1 =u=17521047 ни танлаб олган. А тез ўсувчан вектор сифатида эса қуйидаги векторни қабул қилган:
A=(101, 102, 206, 412, 823, 1647, 3292, 6584, 13169, 26337, 52676, 105352, 210703, 421407, 842812, 1685624, 3371249, 6742497, 13484996, 26969992)
Энди биз бу масалага криптоаналитик нуқтаи-назаридан қарайлик. Унинг олдида қуйидаги криптоаналитик масала турибди. B=(b₁, b₂, …, b_n) рюкзаr вектори маълум. Ундан шифрлашнинг очиқ калити сифатида фойдаланилади. Шунингдек, B вектор тез ўсувчан вектор А ни m модул ва t кўпайтувчига кўпайтириш орқали ҳосил қилинганлиги ҳам маълум. Криптоаналитикка А вектор ва u сони номаълум ва уларни топиш талаб қилинади. Бу ерда энг муҳими m ва ни аниқлашдан иборат. Бу параметрларни аниқлагандан сўнг А векторни осонгина ҳисоблаб топиш ва шифрланган матнни қайта шифрлаш мумкинн бўлади.