ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Development and research of a parallel ant colony algorithm for a block cryptosystem cryptanalysis

Date of submission article: 24.06.2015
UDC: 004.056.55
The article was published in issue no. № 4, 2015 [ pp. 148-157 ]
Abstract:The article considers the possibility of parallel implementation of ant colonies algorithms for block cryptosystems cryptanalysis. The authors specify that a new scientific direction “natural calculations” is relevant, provide the block diagram of DES standard cryptanalysis using a method of ant colonies. The parallel version of cryptanalysis algorithm is described on the basis of a data-logical flow graph, sequence matrices, logical incompatibility and independence. The minimum number of the processors for a cryptanalysisis algorithm is defined on the basis of a technique of defining the number of processors. This technique includes finding of a mutually independent operators maximal set in an independence matrix, consecutive fictive linking in a data-logical graph provided that these links don\'t increase a critical way length. A bioinspired cryptanalysis method application is distinguished by the possibility of using an encryption (decryption) algorithm as an objective function of key assessment defined by genetic operations. Therefore, when using the bioinspired cryptanalysis methods the process of private key definition (for example, at type 2 cryptanalysis) depends not on encryption complexity, but on the bioinspired method itself that provides a sufficient variety of key generation. This proves the relevance of the problem connected with a research on the bioinspired algorithms application possibility for block cryptosystems cryptanalysis.
Аннотация:В статье рассматривается возможность параллельной реализации алгоритмов муравьиных колоний для криптоанализа блочных криптосистем. Отмечена актуальность нового научного направления «природные вычисления», приведена структурная схема криптоанализа стандарта DES с использованием метода муравьиных колоний. Приводится описание параллельной версии алгоритма криптоанализа на основе информационно-логической граф-схемы, матриц следования, логической несовместимости и независимости. На основе методики определения числа процессоров, сущность которой заключается в нахождении максимального множества взаимно независимых операторов в матрице независимости, последовательном проведении фиктивных связей в информационно-логическом графе, не увеличивающих длину критического пути, определено минимальное число процессоров, необходимых для реализации алгоритма криптоанализа. Отмечается, что отличительной особенностью применения биоинспирированных методов криптоанализа является возможность использования самого алгоритма шифрования (или расшифрования) в качестве целевой функции для оценки пригодности ключа, определенного с помощью генетических операций. Вследствие этого при использовании биоинспирированных методов криптоанализа процесс определения секретного ключа (например, при криптоанализе 2-го типа) зависит не столько от сложности шифрующих преобразований, сколько от самого биоинспирированного метода, который должен обеспечивать достаточное разнообразие генерации ключей, что свидетельствует об актуальности задачи исследования возможности применения биоинспирированных алгоритмов (в частности, методов генетического поиска) для криптоанализа блочных криптосистем.
Authors: Chernyshev Yu.O. (sergeev00765@mail.ru) - Don State Technical University, Rostov-on-Don, Russia, Ph.D, Sergeev A.S. (sergeev00765@mail.ru) - Don State Technical University, Rostov-on-Don, Russia, Ph.D, Ryazanov A.N. (sergeev00765@mail.ru) - Don State Technical University, Rostov-on-Don, Russia, Kapustin S.A. (skappa@yandex.ru) - Military Academy of Communications (Associate Professor), Krasnodar, Russia, Ph.D
Keywords: mutually independent operators maximal set, matrix of independence, matrix of logical incompatibility, ant colony optimization, cryptanalysis
Page views: 9797
Print version
Full issue in PDF (9.58Mb)
Download the cover in PDF (1.29Мб)

Font size:       Font:

В последние годы интенсивно разрабатывается новое научное направление «природные вычисления», объединяющее математические методы, в которых заложен принцип природных механизмов принятия решений. К таким методам относятся методы моделирования отжига, эволюционного моделирования, генетические алгоритмы, методы эволюционной адаптации, алгоритмы роевого интеллекта, муравьиные алгоритмы. В моделях и алгоритмах эволюционных вычислений ключевым элементом является построение начальной модели и правил, по которым она может изменяться (эволюционировать). Были предложены разнообразные схемы эволюционных вычислений, в том числе генетический алгоритм, генетическое программирование, эволюционные стратегии, эволюционное программирование. Общие концепции и методологический подход к построению эволюционных вычислений, основанных на природных системах, а также основные гипотезы, закономерности и положения концепции эволюционных вычислений отмечены в [1, 2]. В настоящее время известно применение генетических алгоритмов для оптимизации широкого круга задач, в том числе задач криптоанализа. В [3–10] рассматривались методы организации криптографических атак на традиционные симметричные криптосистемы, использующие шифры перестановки и замены, а также на блочные криптосистемы с использованием методов эволюционной оптимизации и генетического поиска.

Недостатком генетических алгоритмов является наличие «слепого» поиска. Это в общем случае приводит к генерации решений с нарушениями, что увеличивает время поиска и требует дополнительного контроля, к генерации большого количества одинаковых решений, генерации большого количества плохо приспособленных решений, что в общем случае может привести к попаданию в локальный оптимум [11]. Поэтому представляет интерес применение эвристических методов, инспирированных природными системами, в которых осуществляется поэтапное построение решения задачи (то есть добавление нового оптимального частичного решения к уже построенному частичному оптимальному решению). К методам данного вида относят и муравьиные алгоритмы, идея которых состоит в моделировании поведения муравьев, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи. Как отмечено в [12], колония муравьев рассматривается как многоагентная система, в которой каждый муравей-агент функционирует автономно на основе простых правил. Однако в противоположность примитивному поведению отдельных аген- тов поведение всей колонии оказывается достаточно разумным. Исследования в этой области проводятся с середины 90-х годов, и на сегодняшний день известно их применение к задаче о коммивояжере, квадратичной задаче о назначениях, к задачам о раскраске графа, определения оптимальных маршрутов в коммутационных сетях, маршрутизации транспортных средств, борьбы с вредоносным ПО. В [13] рассмотрен возможный подход к реализации криптоанализа блочных алгоритмов шифрования и показано сведение криптоанализа к классической задаче о назначении, решаемой с помощью алгоритма муравьиных колоний.

В настоящее время актуальной является задача криптоанализа блочных криптосистем, так как переход к блочному шифрованию открывает дополнительные возможности для повышения стойкости криптоалгоритмов. Сведения по криптостойкости ряда блочных алгоритмов, в частности, к линейному и дифференциальному криптоанализу, а также результаты его применения к алгоритму DES приведены в [14, 15]. Описание некоторых блочных стандартов шифрования (в том числе стандарта DES) с введенными терминами и обозначениями дано в [15–17].

Oтличительной особенностью применения биоинспирированных методов криптоанализа является возможность использования самого алгоритма шифрования (или расшифрования) в качестве целевой функции для оценки пригодности ключа, определенного с помощью генетических операций. Это особенно существенно при реализации криптоанализа блочных алгоритмов шифрования, в которых применяется многократная обработка блоков текста и на каждом цикле данные преобразуются при участии вспомогательного ключа, сформированного из секретного ключа. Как отмечено в [15], выбор числа циклов определяется требованиями криптостойкости, то есть чем больше циклов, тем выше криптостойкость и больше времени требуется на шифрование (расшифрование). В связи с этим процесс криптоанализа, связанный с какими-либо преобразованиями самого алгоритма шифрования, может оказаться затруднительным и актуальной становится задача исследования возможности применения биоинспирированных алгоритмов для криптоанализа блочных криптосистем, поскольку при использовании данных алгоритмов процесс определения секретного ключа (например при криптоанализе 2-го типа) зависит не столько от сложности шифрующих преобразований, сколько от самого биоинспирированного метода, который должен обеспечивать достаточное разнообразие генерации ключей.

Увеличение производительности «природных» алгоритмов наряду с параллельной реализацией на «низшем» уровне (то есть при параллельной реализации самого алгоритма криптоанализа, используемого для оценки целевой функции пригодности ключа) возможно также при распараллеливании на «высшем» уровне (то есть при реализации самого «природного» алгоритма, используемого для формирования популяции решений, их оценки и проведения множества операций, имитирующих эволюцию живой природы).

Чрезвычайно важным свойством эволюционных стратегий является их естественный внутренний параллелизм. При этом по сравнению с градиентными методами различие во времени расчета целевой функции при различных значениях параметров не оказывает влияния на эффективность распараллеливания [18]. Основные технологии распараллеливания алгоритмов (глобальные параллельные алгоритмы, островная модель, клеточный алгоритм) описаны в [18, 19], методы разработки параллельных программ – в [20, 21].

Разработку параллельной версии алгоритма рассмотрим на примере стандарта DES. Структурная схема криптоанализа с использованием метода муравьиных колоний и структурная схема цикла алгоритма DES приведены на рисунках 1, 2 и в работе [13].

 

На основе структурной схемы алгоритма муравьиных колоний и информационно-логической граф-схемы алгоритма DES, приведенных в [5, 6], получим информационно-логическую граф-схему алгоритма криптоанализа (рис. 3). Связи по управлению показаны на рисунке двойной линией, по информации – одинарной. Для упрощения будем предполагать, что число ключей Кi равно 2 (блоки 1, 2), вычисление целевой функции R для ключей К1, К2 производится на одной группе процессоров, реализующих блоки 3–23, число комбинаций ikkk и число m*d маршрутов, образующих расширенную популяцию, равны 2, оценка их целевой функции пригодности проводится в одном блоке. Применительно к структурной схеме алгоритма DES будем предполагать, что в выходном блоке формируется блок исходного текста, на входной блок поступает блок шифртекста (поскольку процессы шифрования и расшифрования выполняются аналогично за исключением порядка использования ключа и матриц перестановок IP и IP-1).

Для данного графа введем в рассмотрение матрицу следования S. Элемент Sij =*, если существует связь по управлению (jÞi), и Sij =1, если существует связь по информации (j ®i). Данная матрица будет содержать следующие ненулевые элементы:

S(3, 1) = S(3, 2)= S(5, 3) = S(6, 5) = S(7, 5) = S(8, 1) = S(8, 2) = S(9, 8) = S(10, 8) = S(11, 8) = S(12, 8) = S(13, 8) = S(14, 8) = S(15, 8) = S(16, 8) = 1; S(9, 4) = S(10, 4) = S(11, 4) = S(12, 4) = S(13, 4) = S(14, 4) = S(15, 4) = S(16 ,4)=*;

S(17, 7) = S(17, 9) = S(17, 10) = S(17, 11) = S(17, 12) = S(17, 13) = S(17, 14) = S(17, 15) = S(17, 16) = S(18, 17) = S(19, 18) = S(20, 5) = S(20, 19) = S(21, 6) = S(21, 20) = S(24, 22) = S(28, 26) = S(27, 29) = S(28, 30) = S(29, 31) = S(32, 1) = S(32, 2) = S(32, 30) = S(32, 31) = S(33, 1) = S(33, 2) = S(33, 30) = S(33, 31) = S(34, 32) = S(34, 33) = S(35, 34) =1;

S(22, 21) = S(23, 21) = S(25, 24) = S(26, 24) = S(27, 24)=*.

Используя алгоритм нахождения транзитивных связей [20, 21] и вводя для элементов 1 и * матрицы S обозначения 1, получим матрицу SТ (матрицу следования, дополненную транзитивными связями), представленную по адресу http://www.swsys.ru/uploaded/image/2015-4-dop/1.jpg.

Далее введем в рассмотрение матрицу L логической несовместимости операторов, используя алгоритм, составленный для треугольной матрицы S и описанный в [21]. Данная матрица будет содержать следующие ненулевые элементы:

L(9, 10) = L(9, 11) = L(9, 12) = L(9, 13) = L(9, 14) = L(9, 15) = L(9, 16) = L(10, 9) = L(10, 11) = L(10, 12) = L(10, 13) = L(10, 14) = L(10, 15) = L(10, 16) = L(11, 9) = L(11, 10) = L(11, 12) = L(11, 13) = L(11, 14) = L11, 15) = L(11, 16) = L(12, 9) = L(12, 10) = L(12, 11) = L(12, 13) = L(12, 14) = L(12, 15) = L(12, 16) =  L(13, 9) = L(13, 10) = L(13, 11) = L(13, 12) = L(13, 14) = L(13, 15) = L(13, 16) = L(14, 9) = L(14, 10) = L(14, 11) = L(14, 12) =  L(14, 13) = L(14, 15) = L(14, 16) = L(15, 9) = L(15, 10) = L(15, 11) = L(15, 12) = L(15, 13) = L(15, 14) = L(15, 16) = L(16, 9) = L(16, 10) = L(16, 11) = L(16, 12) = L(16, 13) = L(16, 14) = L(16, 15) =  L(22, 23) = L(23, 22) = L(23, 24) = L(23, 25) = L(23, 26) = L(23, 27) = L(23, 28) = L(23, 29) = L(23, 30) = L(23, 31) = L(23, 32) = L(23, 33) = L(23, 34) = L(23, 35) = L(24, 23) = L(25, 23) = L(25, 26) = L(25, 27) = L(25, 28) = L(25, 29) = L(25, 30) = L(25, 31) = L(25, 32) = L(25, 33) = L(25, 34) = L(25, 35) = L(26, 23) = L(26, 25) = L(27, 23) = L(27, 25) = L(28, 23) = L(28, 25) = L(29, 23) = L(29, 25) = L(30, 23) = L(30, 25) = L(31, 23) = L(31, 25) = L(32, 23) = L(32, 25) = L(33, 23) = L(33, 25) = L(34, 23) =  L(34, 25) = L(35, 23) = L(35, 25) = 1.

Откажемся от свойства ориентированности граф-схемы и в матрице следования SТ положим (i, j)=(j, i)=1. На полученную матрицу следования S` наложим матрицу логической несовместимости L, дополненную транзитивными связями. Получим матрицу независимости М, по нулевым элементам которой можно указать множество операторов, каждый из которых может быть выполнен одновременно с оператором, соответствующим номеру строки. Данная матрица будет содержать следующие элементы, равные нулю:

М(1, 1) = М(1, 2) = М(1, 4) = М(2, 1) = М(2, 2) = М(2, 4) = М(3, 3) = М(3, 4) = М(3, 8) = М(3, 9) = М(3, 10) = М(3, 11) = М(3, 12) = М(3, 13) = М(3, 14) = М(3, 15) = М(3, 16) = М(4, 1) = М(4, 2) = М(4, 3) = М(4, 4) = М(4, 5) =  М(4, 6) = М(4, 7) = М(4, 8) = М(5, 4) = М(5, 5) = М(5, 8) = М(5, 9) = М(5, 10) = М(5, 11) = М(5, 12) = М(5, 13) = М(5, 14) =  М(5, 15) = М(5, 16) = М(6, 4) = М(6, 6) = М(6, 7) = М(6, 8) = М(6, 9) = М(6, 10) = М(6, 11) = М(6, 12) =  М(6, 13) = М(6, 14) = М(6, 15) = М(6, 16) = М(6, 17) = М(6, 18) = М(6, 19) = М(6, 20) = М(7, 4) = М(7, 6) = М(7, 7) = М(7, 8) =  М(7, 9) = М(7, 10) = М(7, 11) = М(7, 12) = М(7, 13) = М(7, 14) = М(7, 15) = М(7, 16) = М(8, 3) = М(8, 4) =  М(8, 5) = М(8, 6) = М(8, 7) = М(8, 8) = М(9, 3) = М(9, 5) = М(9, 6) = М(9, 7) = М(9, 9) = М(10, 3) = М(10, 5) = М(10, 6) =  М(10, 7) = М(10, 10) = М(11, 3) = М(11, 5) = М(11, 6) = М(11, 7) = М(11, 11) = М(12, 3) = М(12, 5) = М(12, 6) =  М(12, 7) = М(12, 12) = М(13, 3) = М(13, 5) = М(13, 6) = М(13, 7) = М(13, 13) = М(14, 3) = М(14, 5) = М(14, 6) =  М(14, 7) = М(14, 14) = М(15, 3) = М(15, 5) = М(15, 6) = М(15, 7) = М(15, 15) = М(16, 3) = М(16, 5) = М(16, 6) =  М(16, 7) = М(16, 16) = М(17, 6) = М(17, 17) = М(18, 6) = М(18, 18) = М(19, 6) = М(19, 19) = М(20, 6) = М(20, 20) =  М(21, 21) = М(22, 22) = М(23, 23) = М(24, 24) = М(25, 25) = М(26, 26) = М(26, 27) = М(26, 29) = М(26, 31) = М(27, 26) =  М(27, 27) = М(27, 28) =  М(27, 30) = М(28, 27) = М(28, 28) =  М(28, 29) = М(28, 31) = М(29, 26) = М(29, 28) = М(29, 29) =  М(29, 30) = М(30, 27) =  М(30, 29) = М(30, 30) = М(30, 31) =  М(31, 26) = М(31, 28) = М(31, 30) = М(31, 31) = М(32, 32) =  М(32, 33) = М(33, 32) =  М(33, 33) = М(34, 34) = М(35, 35) = 0.

Таким образом, на основе данной матрицы М можно определить семейство всех внутренне устойчивых множеств. Максимальное внутренне  устойчивое множество даст оценку максимального числа процессоров, требуемых для реализации алгоритма [20]. По матрице М можно определить, что число внутренней устойчивости l=4.

Отсюда с учетом принятых ранее допущений следуют утверждения.

1. При реализации реального алгоритма криптоанализа, использующего множество решений, содержащее n ключей, требуемое число процессоров (P) составит n.

2. Поскольку число процессоров для оценки функции R пригодности ключей составляет 4 (блоки 3–23), при параллельной реализации алгоритмов оценки n ключей число процессоров составит не более 4*n.

3. Аналогично при параллельной обработке результирующих концентраций феромона, его испарения и определения вероятности размещения l символов в k позиций число процессоров составит не более l*k.

4. При параллельном формировании m*d ключей, образующих расширенную популяцию решений и оценки их целевой функции R, число процессоров составит не более n=4*m*d.

Очевидно, что при параллельной реализации алгоритма криптоанализа необходимое число процессоров не превысит максимального из отмеченных в пунктах 1–4 величин, то есть Р=max(4*n, l*k, 4*m*d).

Для определения точной оценки числа процессоров, необходимых для реализации алгоритма при заданных временных ограничениях, воспользуемся методами, описанными в [20, 21]. Рассмотрим следующую задачу: для алгоритма криптоанализа на основе построенного информационно-логического графа и для заданного времени Тзад найти необходимое наименьшее число процессоров однородной вычислительной системы и план выполнения на них операторов.

Данная задача рассматривалась применительно к информационно-логической схеме криптоанализа алгоритма DES с помощью генетического алгоритма в [22]. Аналогичным образом рассмотрим метод решения задачи на примере алгоритма криптоанализа стандарта DES с помощью метода муравьиных колоний, представленного информационно-логическим графом на рисунке 3. На первоначальном этапе определим скалярные веса вершин, отражающих время выполнения операций. Для определения данного времени воспользуемся основными правилами анализа программ, описанными в [23], которые определяют время выполнения операторов присваивания, чтения записи (О(1)), выполнения последовательности операторов (правило сумм), условных операторов, цикла.

Время выполнения операторов присваивания и элементарных логических операций примем равным О(1) (блоки 6, 4, 5, 21, 23, 24, 25, 35), время перестановки с помощью матриц IP и IP-1 – О(32) (блоки 3, 22), время перестановки с помощью матрицы Р – О(16) (блок 19), время выполнения функции G – O(28) (блок 8), время операции циклического сдвига влево на 1 и 2 бита примем равным О(2) (блоки 9–16), время выполнения функции Н и побитового сложения по модулю 2 Ri-1 c ключом Ki примем равным О(48) (блок 17), время выполнения функции расширения Е – О(16) (блок 7), время параллельного поиска в блоках S1…S8 – О(6) (блок 18), время сложения 32-битового блока S1…S8 с Li-1 примем равным О(32) (блок 20).

Далее для упрощения изложения аналогично [22] примем трудоемкость формирования ключей равной О(6) (блоки 1, 2), трудоемкость определения результирующей концентрации феромона, его испарения, определения вероятности размещения символов в позиции – О(36) (блоки 26–31), трудоемкость формирования маршрутов, составляющих расширенное множество решений, и оценку их целевой функции – О(28) (с учетом длины критического пути Ткр=24 в  информационно-логической схеме алгоритма DES) (блоки 32, 33), трудоемкость выбора оптимальных вариантов из расширенной популяции – О(6) (блок 34).

На рисунке 3 веса вершин указаны рядом с их номерами, промасштабированы путем деления на 10 и округлены до ближайшего целого сверху.

По данному графу определим критический путь максимальной длины Ткр=43, проходящий, напри- мер, через вершины 1-3-5-7-17-18-19-20-21-22-24-26-28-30-33-34-35. При решении задачи определения минимального числа процессоров примем заданное время Тзад=Ткр.

Далее по инфомационно-логическому графу со скалярными весами вершин определим ранние (tрi) и поздние (tпi) сроки окончания выполнения оператоpов с помощью алгоритмов, описанных в [21].

Эти значения следующие:

tр1=1, tр2=1, tр3=5, tр4=1, tр5=6, tр6=7, tр7=8, tр8=4, tр9=tр10=tр11=tр12=tр13=tр14=tр15=tр16=5, tр17=13, tр18=14, tр19=16, tр20=20, tр21=21, tр22=25, tр23=22, tр24=26, tр25=27, tр26=tр27=30, tр28=tр29=34, tр30=tр31=38, tр32=tр33 = 41, tр34=42, tр35=43;

tп35=43, tп34=42, tп33=41, tп32=41, tп31=tп30=38, tп29=tп28=34, tп27=tп26=30, tп25=43, tп24=26, tп23=43, tп22=25, tп21=21, tп20=20, tп19=16, tп18=14, tп17=13, tп16=tп15=tп14=tп13=tп12=tп11=tп10=tп9=8, tп8=7, tп7=8, tп6=20, tп5=6, tп4=7, tп3=5, tп2=tп1=11.

Используя значения tрi и tпi и методику, описанную в [21], можно найти оценку минимального числа процессоров, необходимых для выполнения операторов, входящих в каждое множество взаимно независимых операторов (ВНО) матрицы независимости М. Выпишем все множества ВНО, определяемые по матрице М:

{1, 2, 4},  {3, 4, 8},  {3, 9},  {3, 10},  {3, 11},  {3, 12},  {3, 13},  {3, 14},  {3, 15},  {3, 16},  {4, 5, 8},  {4, 6, 7, 8},  {5, 9},  {5, 10},  {5, 11},  {5, 12},  {5, 13},  {5, 14},  {5, 15},  {5, 16},  {6, 9, 7},  {6, 10, 7},  {6, 11, 7},  {6, 12, 7},  {6, 13, 7},  {6, 14, 7},  {6, 15, 7},  {6, 16, 7},  {6, 17},  {6, 18},  {6, 19},  {6, 20},  {26, 27},  {27, 28},  {28, 29},  {29, 26},  {29, 30},  {30, 27},  {30, 31},  {31, 26},  {31, 28}.

Построим диаграммы ранних и поздних сроков окончания выполнения операторов и произведем такое распределение временных границ операторов, при котором число используемых процессоров минимально. Рассмотрим максимальное множество ВНО {4, 6, 7, 8}. Диаграммы ранних и поздних сроков выполнения операторов имеют вид, показанный на рисунке 4.

 

Таким образом, возможно такое распределение выполнения операторов данного множества ВНО, при котором число процессоров равно 1.

Рассмотрим множества ВНО, содержащие 3 элемента. Для множества {3, 4, 8} диаграммы ранних и поздних сроков выполнения показаны на рисунке 5.

Таким образом, для данного множества ВНО минимальное число процессоров составит 2. Для множества ВНО {4, 5, 8} диаграммы будут иметь вид, показанный на рисунке 6.

Для данного множества ВНО требуемое число процессоров составит 1.

Рассмотрим множество ВНО {1, 2, 4} (рис. 7).

Для данного множества ВНО оценка минимального числа процессоров составит 2.

Поскольку остальные множества ВНО содержат операторы с равными ранними и поздними сроками окончания, рассмотрим диаграммы для одного из них, например {6, 9, 7} (рис. 8).

Для данного множества ВНО требуемое число процессоров также составит 1.

Таким образом, поскольку оценка необходимого минимального числа процессоров составляет 2, дальнейшее исследование множеств ВНО, содержащих 2 элемента, не имеет смысла.

Докажем, что эта оценка является минимальной, и определим план выполнения операторов с помощью алгоритма, представленного в [21]. Сущность данного алгоритма заключается в нахождении максимального множества взаимно независимых операторов в матрице независимости, последовательном проведении фиктивных связей в информационно-логическом гра­фе, не увеличивающих дли­ну критического пути. В матрице независимости М определим произвольное множество ВНО, содержащее r элементов, для которого r > Р. Пусть выбрано множество ВНО {3, 4, 8}. Между вершинами этого множества проведем r–Р=1 фиктивных связей в информационно-логическом гра­фе так, чтобы выполнялось соотношение Ткр £ Тзад. Связи 4®3 и 8®4 увеличивают Ткр, связь 3®4 не изменяет его. Отразим данную связь в матрице следования S и сформируем новую матрицу независимости М`.

В матрице M` определим следующее множество ВНО, содержащее более 2 операторов. Выберем множество {4, 5, 8}. Между вершинами этого множества проведем фиктивную связь 5®4, не приводящую к увеличению Ткр. Получим матрицу независимости M``.

В матрице M`` определим следующее мно- жество ВНО, содержащее r>Р операторов. Это множество {4, 6, 7, 8}. Между вершинами этого множества проведем r–Р=2 фиктивных связей, не приводящих к увеличению Ткр. Допустимая комбинация связей 8®4®6. После ее проведения получим матрицу независимости М```.

В матрице M``` найдем множество ВНО {6, 7, 9}. Проведем допустимую фиктивную связь 7®6. После проведения данной связи матрица независимости М```` будет иметь вид, представленный в таблице (см. http://www.swsys.ru/uploaded/image/ 2015-4-dop/2.jpg).

Поскольку матрица М```` не содержит полных множеств  ВНО с числом элементов, большим 2, Р=2 – решение задачи.

Таким образом, на основе фиктивных связей, проведенных в информационно-логическом графе и определяющих порядок выполнения операторов, можно представить план выполнения операторов при заданном времени Ткр =43, показанный на рисунке 9.

Отсюда следует, что сформулированные выше утверждения 1–4 можно обобщить следующим образом.

При реализации реального алгоритма криптоанализа необходимое число процессоров составит max(2*m, l*k, 2*m*d), где m – число используемых ключей; l и k – l символов, размещенных в k позициях; m*d – число ключей, составляющих расширенное множество решений.

Таким образом, рассмотрен подход к реали- зации криптоанализа путем применения параллельной версии алгоритма муравьиных колоний на основе построения матрицы независимости и оп- ределения множеств ВНО. Приведена оценка необходимого минимального числа процессоров при минимальном времени реализации алгоритма. Представленный в работе алгоритм наиболее эффективен при реализации криптоанализа 2-го типа, то есть при определении ключа на основе известных однозначно определенных блоков исходного текста и шифртекста [13]. При реализации криптоанализа 1-го типа в случае неоднозначного получения блоков оптимального текста из заданного блока шифртекста также возможно (как и в случае генетического алгоритма) получение некоторого множества ключей, соответствующих оптимальным вариантам исходного текста. Для каждого варианта ключа в этом случае требуется проверить, является ли он оптимальным для криптоанализа всего текста.

Литература

1.     Родзин С.И. Интеллектуальные системы. О некоторых алгоритмах, инспирированных природными системами: коллектив. монография; [под ред. В.М. Курейчика]. М.: Физматлит, 2009. C. 34–45.

2.     Курейчик В.В., Курейчик В.М., Родзин С.И. Концепция природных вычислений, инспирированных природными системами // Изв. ЮФУ. 2009. № 4. С. 16–24.

3.     Чернышев Ю.О., Сергеев Е.О., Дубров Е.О., Крупе- нин А.В., Третьяков О.П. Криптографические методы и генетические алгоритмы решения задач криптоанализа: монография. Краснодар: Изд-во ФВАС, 2013. 138 с.

4.     Cергеев А.С., Крупенин А.В., Третьяков О.П., Василь- ев А.Е., Чернышев Ю.О. Биоинспирированные алгоритмы крип- тоанализа асимметричных алгоритмов шифрования на основе факторизации составных чисел // Информационная безопасность – актуальная проблема современности. Совершенствование образовательных технологий подготовки специалистов в области информационной безопасности: сб. тр. Краснодар: Изд-во Военной академии связи, 2011. С. 41–47.

5.     Сергеев А.С. Исследование и разработка методов генетического поиска для организации криптоанализа блочных криптосистем в системах управления безопасностью и защиты информации на примере стандарта шифрования DES // Третья Междунар. конф. по проблемам управления: пленар. докл. и избран. тр. М.: Изд-во ИПУ, 2006. С. 328–335.

6.     Сергеев А.С. Применение методов генетического поиска для организации криптоанализа блочных криптосистем на примере стандарта DES // Науч. мысль Кавказа (приложение). 2006. № 15. С. 185–193.

7.     Сергеев А.С., Третьяков О.П., Васильев А.Е., Черны- шев Ю.О. Биоинспирированные методы криптоанализа асимметричных алгоритмов шифрования на основе фактори- зации составных чисел // Вестн. ДГТУ. 2011. Т. 11. № 9 (60). С. 1544–1554.

8.     Чернышев Ю.О., Сергеев А.С., Венцов Н.Н. Исследование и разработка методов генетического поиска для реализации криптоанализа алгоритма IDEA и решения основных теоретико-числовых задач криптографии // Вестн. РГУПС. 2009. № 3 (35). C. 70–79.

9.     Сергеев А.С. Исследование и разработка информационных технологий криптоанализа в системах защиты информации на основе генетического поиска и эволюционной оптимизации на примере стандартов шифрования России // Фундаментальные прикладные проблемы приборостроения, информации и экономики: тр. 10 Междунар. науч.-практич. конф. М.: Изд-во МГУПИ, 2007. Кн. 2. С. 161–167.

10.  Сергеев А.С. Разработка методов криптоанализа на основе генетического поиска при реализации стратегий и технологий информационной защиты на примере стандартов шифрования России // Коммуникативные стратегии информационного общества: тр. Междунар. науч.-технич. конф. СПб: Изд-во политех. ун-та, 2007. С. 56–65.

11.  Лебедев О.Б. Трассировка в канале методом муравьи- ной колонии // Изв. ЮФУ. Сер. Интеллектуальные САПР. 2009. № 4. С. 46–52.

12.  Муравьиные алгоритмы. URL: http://rain.ifmo.ru/cat/da­ta/theory/unsorted/ant-algo-2006/article.pdf (дата обращения: 15.05.2015).

13.  Чернышев Ю.О., Сергеев А.С., Дубров Е.О., Ряза- нов А.Н. Применение метода муравьиных колоний для реализации криптоанализа блочных криптосистем // Программные продукты и системы. 2014. № 1 (105). С. 10–19.

14.  Куликов А.Л., Петрова И.Ю. Выбор оптимального блочного алгоритма шифрования трафика в информационной системе вуза. URL: http://systech.miem.edu.ru/2004/n2/Kuli­kov2.htm (дата обращения: 15.05.2015).

15.  Бабенко Л.К., Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа. М.: Гелиос АРВ, 2006. 376 c.

16.  Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. М.: Радио и связь, 2001. 376 c.

17.  Шнайер Б. Прикладная криптография. М.: Триумф, 2002. 816 c.

18.  Тимченко С.В. Сравнение трех подходов к построению параллельных генетических алгоритмов на примере некоторых задач функциональной оптимизации и генетического программирования. URL: http://www.botik.ru/PSI/RCMS/publications/ publ-texts/2005/grishagine.pdf (дата обращения: 15.05.2015).

19.  Дискретная математика: алгоритмы. URL: http://rain.if­mo.ru/cat/view.php/theory/unsorted/genetic-2005 (дата обращения: 15.05.2015).

20.  Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980. 191 с.

21.  Сергеев А.С. Параллельное программирование. Р-н-Д: Издат. центр ДГТУ, 2002. 77 с.

22.  Сергеев А.С. Разработка генетического метода криптоанализа блочных криптосистем и исследование возможности их параллельной реализации в системах защиты информации на примере стандарта DES // Системный анализ в проектировании и управлении: тр. 10 Междунар. науч.-практич. конф. СПб: Изд-во политехн. ун-та, 2006. С. 258–265.

23.  Ахо Альфред В., Джон Ульман Джеффри Д. Структуры данных и алгоритмы. М.: Вильямс, 2003. 384 с.


Permanent link:
http://swsys.ru/index.php?page=article&id=4084&lang=en
Print version
Full issue in PDF (9.58Mb)
Download the cover in PDF (1.29Мб)
The article was published in issue no. № 4, 2015 [ pp. 148-157 ]

Perhaps, you might be interested in the following articles of similar topics: