Застосування алгоритму BKW для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів

Важливою практичною задачею у галузі інформаційної безпеки є розробка методів відновлення дискретних відображень, які використовуються в сучасних системах передачі, обробки та зберігання даних, за наборами спотворених значень цих відображень, що отримуються під впливом шумів (випадкових спотворень,...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
1. Verfasser:	Мітін, С.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Математичне та комп'ютерне моделювання. Серія: Технічні науки
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/168576
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:	Застосування алгоритму BKW для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів / С.В. Мітін // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 88-94. — Бібліогр.: 6 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-168576
record_format	dspace
spelling	irk-123456789-1685762020-05-05T01:27:17Z Застосування алгоритму BKW для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів Мітін, С.В. Важливою практичною задачею у галузі інформаційної безпеки є розробка методів відновлення дискретних відображень, які використовуються в сучасних системах передачі, обробки та зберігання даних, за наборами спотворених значень цих відображень, що отримуються під впливом шумів (випадкових спотворень, навмисних перешкод, внутрішніх збоїв тощо). При розв'язанні цієї задачі додаткові складнощі виникають у разі відсутності повних відомостей про алгоритми, що визначають зазначені відображення, та використовуються для перетворення інформації. Окремим випадком поставленої задачі є відновлення систематичних лінійних блокових кодів з невідомими твірними матрицями за наборами спотворених кодових слів, що спостерігаються на виході двійкового симетричного каналу зв’язку. У даній статті запропоновано метод розв’язання останньої задачі, який базується на застосуванні алгоритму 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. 2019 Article Застосування алгоритму BKW для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів / С.В. Мітін // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 88-94. — Бібліогр.: 6 назв. — укр. 2308-5916 DOI: 10.32626/2308-5916.2019-19.88-94 http://dspace.nbuv.gov.ua/handle/123456789/168576 621.391:519.2 uk Математичне та комп'ютерне моделювання. Серія: Технічні науки Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Важливою практичною задачею у галузі інформаційної безпеки є розробка методів відновлення дискретних відображень, які використовуються в сучасних системах передачі, обробки та зберігання даних, за наборами спотворених значень цих відображень, що отримуються під впливом шумів (випадкових спотворень, навмисних перешкод, внутрішніх збоїв тощо). При розв'язанні цієї задачі додаткові складнощі виникають у разі відсутності повних відомостей про алгоритми, що визначають зазначені відображення, та використовуються для перетворення інформації. Окремим випадком поставленої задачі є відновлення систематичних лінійних блокових кодів з невідомими твірними матрицями за наборами спотворених кодових слів, що спостерігаються на виході двійкового симетричного каналу зв’язку. У даній статті запропоновано метод розв’язання останньої задачі, який базується на застосуванні алгоритму BKW, що використовується при побудові кореляційних атак на потокові шифри.
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 для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
url	http://dspace.nbuv.gov.ua/handle/123456789/168576
citation_txt	Застосування алгоритму BKW для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів / С.В. Мітін // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 88-94. — Бібліогр.: 6 назв. — укр.
series	Математичне та комп'ютерне моделювання. Серія: Технічні науки
work_keys_str_mv	AT mítínsv zastosuvannâalgoritmubkwdlâvídnovlennâsistematičnihlíníjnihblokovihkodívzanaboramispotvorenihkodovihslív
first_indexed	2025-07-15T03:23:10Z
last_indexed	2025-07-15T03:23:10Z
_version_	1837681649731502080
fulltext	Математичне та комп’ютерне моделювання 88 УДК 621.391:519.2 DOI: 10.32626/2308-5916.2019-19.88-94 С. В. Мітін Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського», м. Київ ЗАСТОСУВАННЯ АЛГОРИТМУ BKW ДЛЯ ВІДНОВЛЕННЯ СИСТЕМАТИЧНИХ ЛІНІЙНИХ БЛОКОВИХ КОДІВ ЗА НАБОРАМИ СПОТВОРЕНИХ КОДОВИХ СЛІВ Важливою практичною задачею у галузі інформаційної без- пеки є розробка методів відновлення дискретних відображень, які використовуються в сучасних системах передачі, обробки та зберігання даних, за наборами спотворених значень цих відо- бражень, що отримуються під впливом шумів (випадкових спо- творень, навмисних перешкод, внутрішніх збоїв тощо). При ро- зв'язанні цієї задачі додаткові складнощі виникають у разі відсу- тності повних відомостей про алгоритми, що визначають зазна- чені відображення, та використовуються для перетворення ін- формації. Окремим випадком поставленої задачі є відновлення систематичних лінійних блокових кодів з невідомими твірними матрицями за наборами спотворених кодових слів, що спостері- гаються на виході двійкового симетричного каналу зв’язку. У даній статті запропоновано метод розв’язання останньої задачі, який базується на застосуванні алгоритму BKW, що використо- вується при побудові кореляційних атак на потокові шифри. Ал- горитм застосовується для розв’язання не однієї, а (одночасно) багатьох систем лінійних рівнянь зі спотвореними правими час- тинами шляхом одноразового перетворення їх спільної матриці коефіцієнтів. Наведено обґрунтування коректності та отримано оцінку ефективності запропонованого методу. Здійснено його порівняння з раніше відомим методом. Показано, що запропо- нований метод має більшу ефективність за трудомісткістю та обсягом потрібної пам’яті, хоча й потребує більше спотворених кодових слів, які необхідні для відновлення твірної матриці ко- ду. В залежності від параметрів кодів, що відновлюються, та ймовірності спотворення у каналі зв’язку, виграш у трудоміст- кості запропонованого методу в порівнянні з раніше відомим складає приблизно від 36 2 до 67 2 разів. Підтверджено також практичну застосовність запропонованого методу для випадків, коли раніше відомий метод є практично не реалізованим. Ключові слова: інформаційна безпека, вивідування інфор- мації, відновлення дискретних відображень, лінійний блоковий код, система рівнянь зі спотвореними правими частинами, ал- горитм BKW. © С. В. Мітін, 2019 Серія: Технічні науки. Випуск 19 89 Вступ. Важливою практичною задачею є відновлення невідомого лінійного блокового коду за набором спотворених кодових слів. Ця за- дача є NP-повною [1], а відомі алгоритми її розв’язання є практично за- стосовними лише у випадку помірної довжини кодів, що відновлюються, або малої ймовірності спотворень символів у каналі зв’язку [1, 2]. В роботі [3] запропоновано метод вирішення зазначеної задачі для систематичних лінійних блокових кодів з використанням методу максимуму правдоподібності, який за відомих умов характеризується найменшою ймовірністю помилки [4]. Метою даної статті є розробка методу, який удосконалює метод роботи [3] і має в порівнянні з ним більш високу ефективність. Постановка задачі та основні результати. Використовуватиме такі позначення: C — невідомий двійковий лінійний ( , )n k -код з твірною матрицею ( , )kG I X , де kI — одинична матриця порядку k , X — матриця розміру ( )k n k  над полем з двох елементів. Нехай jx j -й стовпець матриці X . Припустимо, що вага (чис- ло ненульових координат) вектора jx знаходиться в межах від 3 до  , де  — ціле число, 3  , 1,j n k  . Треба відновити матрицю X за набором m незалежних випадкових рівноймовірних слів коду C , спотворених у двійковому симетричному каналі (ДСК) зв’язку з імовірністю помилки (0, 1 2)p . Поставлену задачу можна формулювати також наступним чи- ном. Розглянемо лінійне відображення :{0, 1} {0, 1} k n CL  , що зада- ється кодом C зазначеного вигляду: ( )CL u uG , {0, 1} k u  . Спосте- рігається послідовність, яка складається з m спотворених значень цього відображення: i i iY U G   , 1,i m , (1) де iU — незалежні випадкові рівноймовірні вектори довжини k , ,1 ,( , ... , )i i i n   — вектори спотворень, координати яких не зале- жать від 1, ... , mU U та є незалежними в сукупності випадковими ве- личинами, що розподілені за законом , ,{ 1} 1 { 0} (0, 1 2)i s i s p      P P , 1,s n , 1,i m . Треба відновити відображення CL (тобто матрицю X ) за відомими значеннями , , ,n k p  та послідовністю (1). Метод розв’язання поставленої задачі запропоновано в робо- ті [3]. Сутність методу полягає у складанні та розв’язанні за допомо- Математичне та комп’ютерне моделювання 90 гою методу максимуму правдоподібності [4] систем лінійних рівнянь (СЛР) із спотвореними правими частинами ( ) ( )j j jAx b Ax    , 1,j n k  , (2) де A — відома реалізація випадкової рівноймовірної двійкової мат- риці розміру m k , ( ) T 1, ,( , ... , ) j j m j   — випадковий вектор з не- залежними координатами, що розподілені за законом , ,{ 1} 1 { 0}i j i j    P P 1 1 2 (1 (1 2 ) )p p        , (3) 1,i m , 1,j n k  . В роботі [3] показано, що для відновлення матриці X з імовірністю не менше 1  , (0,1 2)  , потрібно не більше ніж 2 1 1 3 8(1 2 ) ln ( ) i k m p n k i                      (4) спотворених кодових слів. При цьому трудомісткість методу складає 1 1 3 ( )( 1) i k T O m n k i                (5) операцій. Далі викладено метод відновлення матриці X , який удоскона- лює метод роботи [3] і дозволяє суттєво підвищити його ефективність шляхом одночасного розв’язання усіх СЛР (2) із застосуванням мо- дифікованого алгоритму BKW [5]. Алгоритм реалізації методу (алгоритм B ) залежить від натураль- них параметрів 1k , l , t , де 11 3k k   , m lt , та допоміжного алго- ритму Α розв’язання задачі про адитивне представлення з параметрами 1, ,k k r l . Останній являє собою відомий алгоритм BKW [6] і дозволяє знаходити для довільного списку L , що складається з l випадкових незалежних рівноймовірних 1( )k k -вимірних двійкових векторів 1, ... , lz z r (не обов’язково різних) номерів 1, ... , {1, 2, ... , }r l   таких, що 1 0 r z z       . Алгоритм B складається з двох етапів і дозволяє відновлювати перші 1k координат усіх стовпців матриці X з ймовірністю помилки не вище ніж 1 1k k        . Застосовуючи цей алгоритм 1k k   разів до наборів координат (зазначених стовпців), що попарно не перети- наються, можна відновити матрицю X в цілому з ймовірністю поми- лки не вище ніж  . Для будь-якого k z R позначимо z та z підвектори вектора z , що складаються з його перших 1k та останніх 1k k координат Серія: Технічні науки. Випуск 19 91 відповідно. Далі, позначимо iA i -й рядок матриці A , ijb — i -ту координату вектора ( )j b та запишемо системи рівнянь (2) у вигляді i j i j ijA x A x b     , 1,i m , 1,j n k  . Алгоритм В має такий вигляд. 1. Розіб’ємо систему рядків 1, ... , mA A  на t списків sL довжини l кожний та застосуємо для кожного 1,s t алгоритм Α до списку sL . Якщо хоча б в одному випадку алгоритм Α завершується неус- пішно, то алгоритм В припиняє роботу. Інакше отримаємо рівності вигляду 1 ( ) ( ) 0 r s sA A        , де 1 ( ) ( ), ... , r s s sA A L     , 1,s t . 2. Складемо n – k СЛР із спотвореними правими частинами ( ) ( , )jA s x b s j   , 1,s t , 1,j n k  , (6) де 1 ( ) ( )( ) r s sA s A A          , 1 ( ), ( ),( , ) r s j s jb s j b b       1 ( ), ( ),( ) ( ) r j s j s jA s x          та розв’яжемо їх методом максимуму правдоподібності. Усі системи рівнянь (6) мають однакову матрицю коефіцієнтів, яка складається з t рядків ( )A s довжини 1k , 1,s t . Внаслідок неза- лежності випадкових величин ,i j , 1,i m , 1,j n k  , та форму- ли (3), спотворення у правих частинах рівнянь системи (6) є незалеж- ними випадковими величинами, розподіленими за законом 1 1 ( ), ( ), ( 1) ( ), ( ), { 0} 1 { 1} 1 2 (1 (1 2 ) ), r r s j s j r s j s j p                            P P (7) де 1,s t , 1,j n k  . Для обґрунтування коректності та оцінки ефективності запропо- нованого методу сформулюємо наступну теорему (доведення якої виходить за межі статті). Теорема. Нехай (0, 1 2)  , 1 1, 3k k  і параметри алгоритму B визначаються наступним чином: 1log( ) 2 k k u        , 1 1 2( ) log( ) k k v k k        , 1 2 u r   , 2 ( 1) 1 1 0 2(1 2 ) ln 2( )( ) r i k t p n k i                        , 1 ( ln(2 ( ) ) 1)2 v l u t        . Математичне та комп’ютерне моделювання 92 Алгоритм відновлює перші k1 координат усіх стовпців матриці X з ймовірністю помилки не вище ніж   , використовуючи 1 1 0 ( ) ( )( 1) i k T k O ult n k t i                 , (8) операцій, m(k1) = lt спотворених кодових слів та N(k1) = O (l + t) біт пам’яті. Зауважимо, що, згідно з формулою (8), трудомісткість (при за- даній верхній межі ймовірності помилки) алгоритму B залежить від допоміжного параметра 1 1, 3k k  , який слід вибирати, виходячи з умови 1 1( ) min{ ( ) : 1, 3}T k T k k k   . Тоді обсяг пам’яті та число спотворених кодових слів, потрібних для виконання алгоритму, скла- дає відповідно ( ) ( ) ( )N k l k t k  та ( ) ( ) ( )m k l k t k . В таблиці наведені значення (двійкових) логарифмів трудомісткості, обсягу пам’яті та числа спотворених кодових слів, яких достатньо для відновлення матриці X з імовірністю не менше 1 – δ за допомогою запро- понованого методу. Значення t, l та m отримані з використанням теореми. В останніх двох колонках таблиці наведені значення параметрів (4), (5). Таблиця Чисельні значення параметрів, що характеризують ефективність методів відновлення систематичних лінійних блокових кодів ( 128n  , 80k  , 0,1    ) p  Запропонований метод Метод роботи [3] k log ( )T k log ( )N k log ( )m k 1 logT 1 m 0,1000 20 18 88,42 59,36 85,91 94,29 4632991 30 76 108,75 26,78 35,24 113,42 469177075 50 76 126,99 39,73 48,69 133,03 3781005896745 0,0500 20 16 59,30 30,79 57,46 87,15 32920 30 16 71,87 42,86 69,99 102,89 316141 50 16 96,79 67,18 94,88 115,69 22911318 0,0300 20 16 48,35 26,27 46,41 84,52 5300 30 16 55,88 27,99 53,89 99,00 21330 50 16 70,72 41,58 68,68 109,29 271485 0,0100 20 16 37,76 25,58 35,65 81,99 921 30 16 40,42 25,81 38,20 95,27 1611 50 16 45,54 26,09 43,15 103,16 3871 0,0010 20 16 33,09 25,17 30,84 80,89 429 30 16 33,64 25,32 31,23 93,64 521 50 16 34,45 25,32 31,67 100,48 605 0,0001 20 14 32,63 25,32 30,49 80,78 398 30 14 32,73 25,32 30,53 93,48 466 50 14 32,95 25,32 30,64 100,22 504 Серія: Технічні науки. Випуск 19 93 Висновки. Отримані результати показують, що виграш у трудо- місткості запропонованого методу в порівнянні з раніше відомим [3] складає приблизно від 36 2 до 67 2 разів в залежності від параметрів кодів, що відновлюються, та ймовірності спотворення у ДСК. Для забезпечення потрібної надійності відновлення кодів запропонований метод потребує більше спотворених слів у порівнянні з методом [3], але характеризується суттєво меншою трудомісткістю. В окремих (визначених) випадках запропонований метод вияв- ляється практично застосовним, водночас як раніше відомий метод є практично не реалізованим. Список використаних джерел: 1. Valembios A. Detection and recognition of a binary linear code. Discrete Ap- plied Mathematics. 2001. Vol. 111 (1-2). P. 199–218. 2. Cluzeau M., Finiasz M. Recovering a code’s length and synchronization from a noisy intercepted bitstream. IEEE Conference ISIT’09. Proc. IEEE Press. 2009. P. 2737–2731. 3. Алексейчук А. Н., Грязнухин А. Ю. Метод восстановления систематиче- ских линейных кодов по наборам искаженных кодовых слов. Прикладная радиоэлектроника. 2013. Т. 12. № 2. С. 313–318. 4. Балакин Г. В. Введение в теорию случайных систем уравнений. Труды по дискретной математике. М. : ТВП. 1997. Т. 1. С. 1–18. 5. Zhang B., Xu C., Meier W. Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0. Cryptology ePrint Archive, Report 2016/311. URL: http://eprint.iacr.org/2016/311. 6. Blum A., Kalai A., Wasserman H. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM. 2003. Vol. 50, N 3. P. 506–519. APPLICATION OF BKW ALGORITHM FOR RECOVERING SYSTEMATIC LINEAR BLOCK CODES FROM SAMPLES OF NOISY CODEWORDS 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 distor- tion, deliberate interference, internal faults, etc.). In solving this problem ad- ditional difficulties arise in the absence of complete information about the al- gorithms, 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 Математичне та комп’ютерне моделювання 94 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 nec- essary memory, although it requires more noised codewords that are neces- sary 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 36 2 up 67 2 once. The practical applica- bility of the proposed method for cases, where the previously known method is practically not realizable, is confirmed. Key words: information security, deducing of information, discrete mappings recovering, linear block code, system of liner equations with noised right-hand sides, BKW algorithm. Одержано 21.01.2019 УДК 004.383.3:004.9.347 DOI: 10.32626/2308-5916.2019-19.94-100 Л. М. Николайчук, канд. юрид. наук, А. Р. Воронич, канд. техн. наук, Т. О. Заведюк, канд. техн. наук Івано-Франківський національний технічний університет нафти і газу м. Івано-Франківськ, ** Надвірнянський коледж Національного транспортного університету м. Надвірна МЕТОДИ НЕЙРОПРОЦЕСОРНОГО ОПРАЦЮВАННЯ СИГНАЛІВ ТА КОМУНІКАЦІЙНИХ ВЗАЄМОДІЙ У СЕРЕДОВИЩІ СУБ’ЄКТІВ ПРАВА Обгрунтована концепція адекватності моделей нейропроце- сорного опрацювання сигналів та комунікаційних взаємодій в ін- формаційному середовищі суб’єктів права. Показано взає- мозв’язок понять ймовірнісної та суб’єктивної ентропії в теорії інформації та юриспруденції. Запропоновані моделі імпульсно- квадратичного перетворення гармонічних сигналів на вході фор- мального нейрона, модель аксона нейрона, рекурентного кореля- ційного нейрона та інформаційної нейромоделі суб’єкта права. Ключові слова: нейропроцесори, компоненти біологічних нейронів, ймовірнісна та суб’єктивна ентропія, моделі компо- нентів нейрона та суб’єктів права. Вступ. Широкомасштабне застосування ІТ-технологій та комп’ю- теризованих систем керування є одним з істотних факторів соціально- економічного і технологічного розвитку. Комп’ютеризовані та хмарні © Л. М. Николайчук, А. Р. Воронич, Т. О. Заведюк, 2019

Застосування алгоритму BKW для відновлення систематичних лінійних блокових кодів за наборами спотворених кодових слів

Institution

Ähnliche Einträge