Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами
Для криптосхемы Меркля—Хеллмана шифрования ранцами разработан алгоритм формирования обычной последовательности из сверхвозрастающей, основанный на введенных понятиях непрямых модульных преобразований и частичных инверсий, в котором для формирования «лазейки» применяются удвоенные последовательности...
Gespeichert in:
| Veröffentlicht in: | Электронное моделирование |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/100843 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами / С.Д. Винничук // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 3-22 . — Бібліогр.: 2 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-100843 |
|---|---|
| record_format |
dspace |
| spelling |
Винничук, С.Д. 2016-05-27T15:56:35Z 2016-05-27T15:56:35Z 2013 Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами / С.Д. Винничук // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 3-22 . — Бібліогр.: 2 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/100843 621.391.7 + 681.3.067 Для криптосхемы Меркля—Хеллмана шифрования ранцами разработан алгоритм формирования обычной последовательности из сверхвозрастающей, основанный на введенных понятиях непрямых модульных преобразований и частичных инверсий, в котором для формирования «лазейки» применяются удвоенные последовательности весов предметов. Показано, что при таком подходе для 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. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами |
| spellingShingle |
Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами Винничук, С.Д. Математические методы и модели |
| title_short |
Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами |
| title_full |
Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами |
| title_fullStr |
Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами |
| title_full_unstemmed |
Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами |
| title_sort |
метод удвоения последовательности весов предметов в задаче меркля—хеллмана шифрования ранцами |
| author |
Винничук, С.Д. |
| author_facet |
Винничук, С.Д. |
| topic |
Математические методы и модели |
| topic_facet |
Математические методы и модели |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| description |
Для криптосхемы Меркля—Хеллмана шифрования ранцами разработан алгоритм формирования обычной последовательности из сверхвозрастающей, основанный на введенных понятиях непрямых модульных преобразований и частичных инверсий, в котором для формирования «лазейки» применяются удвоенные последовательности весов предметов. Показано, что при таком подходе для 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.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/100843 |
| citation_txt |
Метод удвоения последовательности весов предметов в задаче Меркля—Хеллмана шифрования ранцами / С.Д. Винничук // Электронное моделирование. — 2013. — Т. 35, № 3. — С. 3-22 . — Бібліогр.: 2 назв. — рос. |
| work_keys_str_mv |
AT vinničuksd metodudvoeniâposledovatelʹnostivesovpredmetovvzadačemerklâhellmanašifrovaniârancami |
| first_indexed |
2025-12-07T16:58:45Z |
| last_indexed |
2025-12-07T16:58:45Z |
| _version_ |
1850869521223516160 |