General solving linear Diophantine equations based on a modular transformation for risk assessment in information security

Authors

  • Степан Дмитрович Винничук Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины
  • Володимир Володимирович Мохор Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, Институт специальной связи и защиты информации НТУ Украины «КПИ»
  • Віталій Михайлович Безштанько Институт специальной связи и защиты информации НТУ Украины «КПИ»

DOI:

https://doi.org/10.18372/2225-5036.22.10457

Keywords:

Linear Diophantine equations with an arbitrary number of unknowns, the general solution, formalized algorithms, modular transformations

Abstract

Strictly formalized algorithms for solving linear Diophantine equations (LDE) of arbitrary order based on the use of modular transformations to determine quantitative values of information security risks. At every step of algorithms offered instead of one primary LDE formed two, the first of which is used on the reverse course of the algorithm, and the second - to further reduce the coefficients of the variables, to obtain one of the coefficients equal to unity. In the second equation, the coefficients of the unknowns are the remnants of the division of the primary coefficients of the equation for a minimum coefficient of this LDE. Due to this, there is a simultaneous decrease in the values of the coefficients of all the variables, instead of one of them, as it is implemented in the methods of change of variables. This provides a reduction the computational complexity of the algorithms and the values of the coefficients in the general solution of equations. Determine their time complexity T(n), where n - the number of unknowns in the equation. For algorithm A1 shown, that T1(n)= O(n*m*log2M) , where M – the maximum coefficient in equation, and m –the average labor input of a division operation with the remainder. For algorithm A2 asymptotic limit rating M it is of the order O(n*lognM*m).

Author Biographies

Степан Дмитрович Винничук, Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины

Рік та місце народження: 1955 рік, с. Кулачківці, Івано-Франківської обл., Україна.

Освіта: Чернівецький державний університет, 1977 рік.

Посада: в.о. завідувача відділом «Автоматизації проектування енергетичних установок» Інституту проблем моделювання в енергетиці НАН України.

Наукові інтереси: математичне і комп’ютерне моделювання, теорія алгоритмів.

Публікації: близько 100 наукових публікацій.

Володимир Володимирович Мохор, Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, Институт специальной связи и защиты информации НТУ Украины «КПИ»

Рік та місце народження: 1955 рік, м. Київ, Україна.

Освіта: Київський інститут інженерів цивільної авіації (з 2000 року – НАУ), 1977 рік.

Посада: завідувач кафедри кібербезпеки та застосування інформаційнихсистем та технологій.

Наукові інтереси: теорія ризиків, інформаційна безпека, кібербезпека, математичне і комп’ютерне моделювання.

Публікації: більше 150 наукових публікацій.

Віталій Михайлович Безштанько, Институт специальной связи и защиты информации НТУ Украины «КПИ»

Рік та місце народження: 1970 рік, с. Фурси, Білоцерківського району, Київської обл, Україна.

Освіта: Київський військовий інститут управління та зв’язку, 1997 рік.

Посада: начальник лабораторії кафедри кібербезпеки та застосування інформаційних систем та технологій.

Наукові інтереси: теорія ризиків, інформаційна безпека, кібербезпека.

Публікації: більше 30 наукових публікацій.

References

Боревич З.И. Теория чисел. / З.И. Боревич. И.Р. Шафаревич // М.:Наука. Глав. Ред. физ.-мат. лит. — 1985. — 504 с.

Схрейвер А. Теория линейного целочисленного программирования. В двух томах. Т.1 / А. Схрейвер // Пер. с анг. – М.: Мир, 1991. — 360 с.

Eisenbeis C , Temam O., WijshofFH. On efficiently characterizing solutions of linear Diophantine equations and its application to data dependence analysis: Research Report / Utrecht University (Netherlands); — RUU-CS-92-01. — 1992. — 22p. [Електронный ресурс] – Режим доступа: https://hal.inria.fr/inria-00074944/PDF/RR-1616.pdf – Дата доступа: январь 2016. – Название с экрана.

Безштанько В. М. Диофантов метод определения частости нанесения ущерба вследствие реализации угроз информационной безопасности / В. М. Безштанько, В. В. Цуркан // Захист інформації. — 2013. — № 4 (15). — с. 278–283.

Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. —328 с.

Серпинский В. О решении уравнений в целых числах./Государственное издательство физико-математической литературы. / Пер. с польського И.Г. Мельникова. — М.: Физматгиз., 1961 — 88 с.

Саати Т.Л. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. — М.: Мир, 1973. — 181 с.

Published

2016-03-23

Issue

Section

Information Security Management