Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів
The important practical problem in the information security sphere is the development of methods for recovering discrete mappings, which are used in modern systems for transmitting, processing and storing data, from samples of noisy values of these mappings caused by noise impact (random distortion,...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Kamianets-Podilskyi National Ivan Ohiienko University
2019
|
| Онлайн доступ: | http://mcm-tech.kpnu.edu.ua/article/view/173744 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Mathematical and computer modelling. Series: Technical sciences |
Репозитарії
Mathematical and computer modelling. Series: Technical sciences| id |
mcmtechkpnueduua-article-173744 |
|---|---|
| record_format |
ojs |
| institution |
Mathematical and computer modelling. Series: Technical sciences |
| collection |
OJS |
| language |
Ukrainian |
| format |
Article |
| author |
Мітін, Сергій В'ячеславович |
| spellingShingle |
Мітін, Сергій В'ячеславович Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів |
| author_facet |
Мітін, Сергій В'ячеславович |
| author_sort |
Мітін, Сергій В'ячеславович |
| title |
Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів |
| title_short |
Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів |
| title_full |
Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів |
| title_fullStr |
Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів |
| title_full_unstemmed |
Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів |
| title_sort |
застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів |
| title_alt |
Application of BKW Algorithm for Recovering Systematic Linear Block Codes from Samples of Noisy Codewords |
| description |
The important practical problem in the information security sphere is the development of methods for recovering discrete mappings, which are used in modern systems for transmitting, processing and storing data, from samples of noisy values of these mappings caused by noise impact (random distortion, deliberate interference, internal faults, etc.). In solving this problem additional difficulties arise in the absence of complete information about the algorithms, which define these mappings and used to transform information. А special case of the problem is systematic linear block codes recovering with unknown generating matrix from samples of corrupted codewords observed at the output of a binary symmetric channel. In this paper, the problem-solving method, which based on the BKW algorithm application, which is used for building the correlation attack on streams ciphers, is suggested. The algorithm is applied for solving not one but (simultaneously) many systems of linear equations with noised right-hand sides by single transformation of their co-coefficients matrix. The justification for the correctness is given and an estimation of the proposed method efficiency is obtained. Its comparison with the previously known method is made. It is shown that the proposed method has greater efficiency in terms of the complexity and volume of necessary memory, although it requires more noised codewords that are necessary for code generating matrix recovering. Depending on recovered codes parameters and the probabilities of distortion in the communication channel, benefits in terms of the complexity of the proposed method in comparison with the previously known is from up once. The practical applicability of the proposed method for cases, where the previously known method is practically not realizable, is confirmed. |
| publisher |
Kamianets-Podilskyi National Ivan Ohiienko University |
| publishDate |
2019 |
| url |
http://mcm-tech.kpnu.edu.ua/article/view/173744 |
| work_keys_str_mv |
AT mítínsergíjvâčeslavovič applicationofbkwalgorithmforrecoveringsystematiclinearblockcodesfromsamplesofnoisycodewords AT mítínsergíjvâčeslavovič zastosuvannâalgoritmubkwdlâvídnovlennâsistematičnihlíníjnihblokovihkodívzanaboramispotvorenihkodovihslív |
| first_indexed |
2024-04-08T14:59:07Z |
| last_indexed |
2024-04-08T14:59:07Z |
| _version_ |
1795779039456133120 |
| spelling |
mcmtechkpnueduua-article-1737442019-07-18T12:45:04Z Application of BKW Algorithm for Recovering Systematic Linear Block Codes from Samples of Noisy Codewords Застосування алгоритму bkw для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів Мітін, Сергій В'ячеславович The important practical problem in the information security sphere is the development of methods for recovering discrete mappings, which are used in modern systems for transmitting, processing and storing data, from samples of noisy values of these mappings caused by noise impact (random distortion, deliberate interference, internal faults, etc.). In solving this problem additional difficulties arise in the absence of complete information about the algorithms, which define these mappings and used to transform information. А special case of the problem is systematic linear block codes recovering with unknown generating matrix from samples of corrupted codewords observed at the output of a binary symmetric channel. In this paper, the problem-solving method, which based on the BKW algorithm application, which is used for building the correlation attack on streams ciphers, is suggested. The algorithm is applied for solving not one but (simultaneously) many systems of linear equations with noised right-hand sides by single transformation of their co-coefficients matrix. The justification for the correctness is given and an estimation of the proposed method efficiency is obtained. Its comparison with the previously known method is made. It is shown that the proposed method has greater efficiency in terms of the complexity and volume of necessary memory, although it requires more noised codewords that are necessary for code generating matrix recovering. Depending on recovered codes parameters and the probabilities of distortion in the communication channel, benefits in terms of the complexity of the proposed method in comparison with the previously known is from up once. The practical applicability of the proposed method for cases, where the previously known method is practically not realizable, is confirmed. Важливою практичною задачею у галузі інформаційної безпеки є розробка методів відновлення дискретних відображень, які використовуються в сучасних системах передачі, обробки та зберігання даних, за наборами спотворених значень цих відображень, що отримуються під впливом шумів (випадкових спотворень, навмисних перешкод, внутрішніх збоїв тощо). При розв'язанні цієї задачі додаткові складнощі виникають у разі відсутності повних відомостей про алгоритми, що визначають зазначені відображення, та використовуються для перетворення інформації. Окремим випадком поставленої задачі є відновлення систематичних лінійних блокових кодів з невідомими твірними матрицями за наборами спотворених кодових слів, що спостерігаються на виході двійкового симетричного каналу зв’язку. У даній статті запропоновано метод розв’язання останньої задачі, який базується на застосуванні алгоритму BKW, що використовується при побудові кореляційних атак на потокові шифри. Алгоритм застосовується для розв’язання не однієї, а (одночасно) багатьох систем лінійних рівнянь зі спотвореними правими частинами шляхом одноразового перетворення їх спільної матриці коефіцієнтів. Наведено обґрунтування коректності та отримано оцінку ефективності запропонованого методу. Здійснено його порівняння з раніше відомим методом. Показано, що запропонований метод має більшу ефективність за трудомісткістю та обсягом потрібної пам’яті, хоча й потребує більше спотворених кодових слів, які необхідні для відновлення твірної матриці коду. В залежності від параметрів кодів, що відновлюються, та ймовірності спотворення у каналі зв’язку, виграш у трудомісткості запропонованого методу в порівнянні з раніше відомим складає приблизно від до разів. Підтверджено також практичну застосовність запропонованого методу для випадків, коли раніше відомий метод є практично не реалізованим. Kamianets-Podilskyi National Ivan Ohiienko University 2019-01-21 Article Article application/pdf http://mcm-tech.kpnu.edu.ua/article/view/173744 10.32626/2308-5916.2019-19.88-94 Mathematical and computer modelling. Series: Technical sciences; 2019: Mathematical and computer modelling. Series: Technical sciences. Issue 19; 88-94 Математичне та комп'ютерне моделювання. Серія: Технічні науки ; 2019: Математичне та комп'ютерне моделювання. Серія: Технічні науки. Випуск 19; 88-94 2308-5916 10.32626/2308-5916.2019-19 uk http://mcm-tech.kpnu.edu.ua/article/view/173744/173522 Авторське право (c) 2021 Математичне та комп'ютерне моделювання. Серія: Технічні науки |