Информация Хавфсизлиги

6.4. Рюкзакни тахлаш масаласига асосланган алгоритм

Рюкзакни тахлаш масаласи комбинаториканинг машхур масалаларидан булиб, умуман олиб караганда NP-тулалик масалалари синфига киритилади. Яъни бу масалалар полиномиал вакт оралигида ихтиёрий хисоблаш машинасида ечиш имконияти йук. Буни куйидагича тушунтириш мумкин, агар рюкзакка солинадиган юкни аникловчи а=(а₁, а₂, а₃..., а_n) сонлар вектори берилган булса, у холда фиксирланган кисм вектор элементлари йигиндисини топиш осон. Аммо S бутун сонни бериш билан, элементлари йигиндиси S га тенг булган а кисм векторни топиш осон эмас, хаттоки бундай векторнинг мавжудлиги маълум булса хам.

а сонлар n битли х=(х₁, х₂,..., х_n) ахборотни шифрлаш учун ишлатилади. Шифрматн S=ах скаляр купайтма ёрдамида олинади. х бинар вектор булганлиги сабабли, уни скаляр купайтириш осон амалга ошади. Бунинг учун n та кушиш амали талаб килинади. Бунга тескари функция булган х бинар векторни топиш, яъни ах= S (рюкзакни тахлаш масаласини англатувчи амал) да ихтиёрий а учун тескари функцияни топиш - хисоблаш нуктаи назаридан олиб караганда мумкин эмас. Умуман олиб караганда, бу масала анча мураккаб булсада, уни ечиш мумкин булган куплаб холатлар мавжуд. Бу йуналишдаги ишларнинг фаол олиб борилишига карамасдан 184 йилда Gray-1 компьютерининг 1 соат давомида 40 итерация ва 100 посилка билан ишлаши натижасида рюкзак системасининг уша пайтдаги энг кучли вариантини хам очишга муваффак булинди.


7. Комбинациялашган шифрлар

Комбинациялашган шифрлашда блокли ва потокли шифрлаш принциплари амалга оширилади. Бунинг учун блокли шифрдан потокли режимда (гаммалаш, тескари алокали шифрлаш) ва потокли шифрдан блокли режимда (блокларни шифрлаш) фойдаланиш мумкин.

Комбинациялашган шифрлаш амалда ГОСТ 28147-89 ва DES шифрлаш стандартларининг хар хил режимларида кулланилади.
Бир калитли криптографик алгоритмлар криптография оламида анчагина машхур. 1-жадвалда криптоалгоритмларнинг таккослаш характеристикалари келтирилган.
1-жадвал

Алгоритм	Шифрлаш Режими	Блок узунлиги, бит	Калит узунлиги, бит	Изох
CAST	CFB	64	128	DHE/DSS калитлари билан фойдаланилади
IDEA	CFB	64	128	RSA калити билан фойдаланилади
DES	CFB	64	168	DHE/DSS калитлари билан фойдаланилади

1-жадвалда келтирилган хамма бир калитли алгоритмлар АКШ маълумотларни шифрлаш стандари DES нинг тескари алока режими CFB дан фойдаланади.