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

• Дата: 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

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.