Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами

• Опубліковано в: : Электронное моделирование
• Дата: 2013
• Автор: Винничук, С.Д.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2013
• Теми: Математические методы и модели
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/100843
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами / С.Д. Винничук // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 3-22 . — Бібліогр.: 2 назв. — рос.

Для криптосхемы Меркля—Хеллмана шифрования ранцами разработан алгоритм формирования обычной последовательности из сверхвозрастающей, основанный на введенных понятиях непрямых модульных преобразований и частичных инверсий, в котором для формирования «лазейки» применяются удвоенные последовательности весов предметов. Показано, что при таком подходе для k-кратно итерируемой ранцевой системы каждому элементу сверхвозрастающей последовательности может соответствовать 2^k вариантов элемента обычной последовательности, а число вариантов обычной последовательности, при всех одинаковых параметрах модульных преобразований, может достигать 2^kL, где L — число бит в блоке информации. При этом обратная задача определения сверхвозрастающей последовательности по обычной может быть сведена к задаче целочисленного линейного программирования как вариантная при большом числе вариантов. Для криптосхеми Меркля—Хеллмана шифрування рюкзаками розроблено алгоритм формування звичайної послідовності із надзростаючої, що грунтується на введених поняттях непрямих модульних перетворень і часткових інверсій, в якому при формуванні «люка» використовуються подвоєні послідовності ваг предметів. Показано, що при такому підході для k-кратно ітерованої системи кожному з елементів надзростаючої послідовності може відповідати 2^k варіантів елемента звичайної послідовності, а число варіантів звичайної послідовності при всіх однакових параметрах модульних перетворень, може досягати 2^kL,де L —число біт в блоці інформації. При цьому обернена задача визначення надзростаючої послідовності по звичайній може бути зведена до задачі цілочисельного лінійного програмування як варіантна при значному числі варіантів. The algorithm for forming the normal sequence of eccessively ascending one, based on the introduced concepts of indirect modular transformations and partial inversions with the «loophole» formation on the basis of duplicate sequences of the items weights has been developed as part of the Merkle-Hellman cryptoscheme of knapsack encryption . It is shown that under such an approach 2^k options of the element of normal sequence may correspond to each element above the ascending sequence for the k-fold iterated backpack system, and the number of options of normal sequence, with all the same parameters of the modular transformations, may achieve 2^kL, where L is the number of bits in the data block. In this case, the inverse problem of determining the excessively ascending sequence of the normal one can be reduced to the problem of integer linear programming only as a variant with the great number of options.