Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра



Скачать 144.73 Kb.
Дата08.07.2013
Размер144.73 Kb.
ТипДокументы
УДК 004.021

Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра

Городилов А.Ю., Митраков А.А.

Пермский государственный университет,
Россия, 614990, Пермь, ул. Букирева, 15

e-mail: gora830@yandex.ru, tom-trix@ya.ru

В статье описывается общий подход к решению задачи с помощью генетических алгоритмов, и предлагаются два способа распараллелить вычисления: островная модель и кластерные вычисления в MPI. Проведенные практические исследования подтверждают, что данные модели позволяют существенно снизить время решения задачи без потери качества результата.

Введение


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

В данной статье рассматривается один из таких новых алгоритмов шифрования, предложенный В.П. Сизовым [1], и криптоатака на него на основе только известного шифртекста. При этом будем предполагать, что исходный текст является осмысленным текстом на некотором естественном языке.

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

В данной статье описано применение двух подходов. Первый является универсальным и основан на использовании так называемой островной модели генетических алгоритмов. Второй подход является оригинальным и основан на использовании особенностей конкретной решаемой задачи.

Тригонометрический шифр


Шифр, разработанный Владимиром Сизовым [1], классифицируется как поточный шифр простой подстановки с использованием закрытого симметричного ключа.

В основе шифрования лежит использование непрерывных на всём числовом промежутке периодических функций. В простейшем варианте рассматривается y=cos(x) и соответствующее уравнение волны y=cos(x+ndx). Далее мы будем рассматривать именно эту схему. В данном случае шифрование выполняется по формуле:

gif" name="object1" align=absmiddle width=222 height=19> (1)

где y – новый символ, x – исходный символ, n – номер шифруемого символа (n=1,2,3,…), z и dx – ключ (пара вещественных чисел), N – мощность алфавита.

При шифровании/дешифровании число округляется до целого. Из формулы (1) выразим х и получим формулу для расшифрования:

(2)

Напомним, что криптостойкость обеспечивается только за счёт секретного ключа – пары вещественных чисел z и dx.

В работе В.П. Сизова доказано, что при алгоритм имеет бесконечный период гаммирования, из чего делается вывод, что при больших объемах текста «вскрыть» шифр, не зная ключа, представляется невозможным. Получаемые шифртексты хорошо исследованы на предмет наличия в них статистических закономерностей, и в этом плане теоретическая криптостойкость не вызывает сомнений. Однако в данной статье мы рассмотрим другой аспект – возможную атаку на эту криптосхему на основе шифртекста и знаний о наличии в исходном тексте определенных статистических закономерностей.

Генетический алгоритм. Представление особи


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

Можно показать, что, во-первых, правильное решение (пара (z, dx)) гарантированно существует в прямоугольнике и, во-вторых, если при расшифровке вместо правильной точки (z, dx) использовать любую точку из ее -окрестности, то будет получен текст, близкий к исходному, то есть для решения задачи не обязательно находить точное значение z и dx, а достаточно просто «попасть» в -окрестность. При этом для дешифровки текста длиной в несколько сотен символов достаточно взять  = 10-5.

На прямоугольнике построим равномерную сетку с шагом . Таким образом, решение будем искать не во всем пространстве R2, а лишь в узлах построенной сетки. При этом для представления решений потребуется хранить 5 разрядов после запятой по каждой координате.

Для кодирования мы будем использовать двоичный алфавит {0,1}. Хромосома будет представлять собой конкатенацию двух битовых строк. В структуре особи будет храниться дробная часть чисел z и dx. Т.к. log210000016.684, то для хранения 5 десятичных разрядов потребуется 17 двоичных. Таким образом, особь есть упорядоченная последовательность 34 бит, хранящая дробные части ключа (рис. 1).




Рис. 1. Структура особи


Фитнесс-функция


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

Рассмотрим следующую модель. Алфавит есть множество A мощности N, состоящее из прописных букв русского алфавита и некоторых знаков препинания, наиболее часто используемых в письменной речи. Под биграммой будем понимать упорядоченный набор из двух символов данного алфавита . Множество всех возможных биграмм обозначим B. Определим функцию частотности , которая каждой биграмме ставит в соответствие число – частоту возникновения этой биграммы в осмысленных текстах, а также функцию дешифрования:

(3)

где – ключ (), – множество всех ключей, – множество символьных строк длины m, состоящих из букв алфавита A.

Функция дешифрования (3) преобразует входную строку шифртекста в строку такой же длины с помощью ключа x по формуле (2).

Наконец, определяем фитнесс-функцию порядка m:



(4)

Построенная таким образом функция не идеальна, но с ростом m в случае осмысленных текстов даёт очень хорошие результаты: чем больше строка похожа на фрагмент нормальной речи, тем выше значение функции. Таблицы частотностей биграмм выбираются в зависимости от конкретного естественного языка.

Генетические операторы


В качестве операторов редукции/репродукции используется отбор усечением (особи сортируются по приспособленности, делятся на несколько групп, и далее для скрещивания случайно выбираются особи из первой и второй группы, в то время как последняя группа покидает популяцию).

Для скрещивания применяется модификация соответствующего кроссинговера. В ходе скрещивания два родителя дают единственного потомка. Биты родителей с вероятностью 1/3 складываются по модулю 2 либо с такой же вероятностью наследуются от одного из них. Кроме того, на практике дополнительно возможен второй вариант скрещивания для особо удачных особей (принцип строительных блоков). В этом случае сохраняются несколько первых бит дробной части для каждого из чисел z и dx. Такой способ гарантирует, что потомок окажется в окрестности одного из своих родителей, и используется лишь для улучшения возможно найденного решения.

В качестве оператора мутации можно использовать инвертирование битов хромосомы с вероятностью 1/2.

Островная модель


Островная модель генетического алгоритма вновь имитирует естественные природные процессы (рис. 2). Исходная популяция делится на несколько частей, каждая из которых развивается обособленно от всех остальных (на своем «острове»). Каждому острову выделяется 1 процесс. Через определённое количество поколений процессы обмениваются лучшими на текущий момент особями (мигрантами). Данный процесс называется миграцией. Каждый процесс может функционировать на отдельном вычислительном узле, коммуникация между узлами происходит только в моменты выполнения миграций.



Рис. 2. Островная модель генетического алгоритма

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

В островной модели очень важно правильно подобрать параметры – количество мигрантов и частоту их переселения. Очень частая миграция приводит к тому, что на остров могут попасть доминантные особи (когда, например, один остров получил более хорошее развитие, чем другой). Такие особи быстро вытеснят «местные», и популяция станет аналогична популяции «развитого» острова, что приведёт к однотипным решениям. При редкой миграции наоборот, увеличивается уровень обособленности, что приведёт к преждевременному схождению подпопуляций (мигранты будут просто не в силах исправить локальный процесс эволюции).

Переходя к техническим особенностям, отметим два момента:

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

  2. Миграция будет происходить синхронно, то есть будет запускаться только после того, как все процессы дошли до данного этапа и подготовили набор мигрантов. Таким образом, производительность сети будет определяться производительностью ее самого слабого узла.

Схема работы островной модели


Общая схема работы распределённого алгоритма приведена на рис. 3. Рассмотрим его подробнее:

  1. Формирование начальной популяции. Перед запуском основного цикла алгоритма на каждом острове независимо от остальных случайным образом формируется популяция из n особей. Размер популяции может изменяться только в пределах одной эпохи эволюции.

  2. Добавление h мигрантов с других островов. Особи смешиваются, что увеличивает размер популяции.

  3. Вычисление функции приспособленности порядка m для каждой особи.



Рис.3. Схема работы островной модели

  1. Сортировка популяции по убыванию приспособленности особей.

  2. Отсортированная популяция делится на 5 групп.

  3. Первые две группы (с лучшими хромосомами) допускаются к кроссоверу. Полученные потомки добавляются в начало популяции.

  4. Четвёртая группа (с особями низкой приспособленности) претерпевает мутацию.

  5. Особи с номерами n, n+1, n+2… в отсортированной последовательности удаляются.

  6. Производится отправка мигрантов («копии» лучших h особей). При этом оригинальные экземпляры остаются на острове.

Цикл повторяется M раз. Шаги 2 и 9 выполняются не на каждой итерации, а только в моменты миграций, через каждые ψ поколений.

Всего данная процедура выполняется 49 раз для , т.к. особи хранят только дробную часть чисел {z, dx}.

Распределённое приложение на основе классического алгоритма


Если внимательно проследить перебор пространства решений, то можно обнаружить, что мы 49 раз абсолютно независимо друг от друга запускаем ГА с разными целыми частями чисел z и dx. Таким образом, данную схему можно рассматривать в некотором роде как «векторную» операцию:



Таким образом, взяв, например, 49-процессорную машину, можно сократить время работы примерно в 49 раз.

Единственная проблема – контроль качества. Так как в островной модели узлы обменивались между собой хромосомами, и каждый остров в совокупности обладал набором хороших решений, то ответ, рано или поздно, мог быть получен на любом из них. В данном же случае хороший результат должен появиться, теоретически, только на одном узле, и далее требуется дополнительный анализ. Можно, например, переслать ответы на главный узел и сравнить фитнесс-функцию.

В практической реализации данного подхода была предусмотрена поддержка вычислений MPI для 2, 3 или 7 процессов.

Сравнение классической и островной модели


Экспериментальным путём для классического ГА были подобраны следующие оптимальные параметры, обеспечивающие сходимость алгоритма к приближенному решению в подавляющем большинстве случаев: размер популяции n = 200; количество поколений M = 200; порядок фитнесс-функции m = 60; процент скрещивания особей в популяции p =20%; процент мутации особей в популяции λ = 20%. Однако для сравнения моделей возьмем уменьшенные значения: n = 60, M = 60, m = 40, p =20%, λ = 10%. Для распределенного алгоритма возьмем следующие значения параметров: число островов k = 2; количество мигрантов h = 5; частота миграции ψ = 10.

Всего было протестировано 20 текстов. Каждый из них дешифровывался с помощью классической и островной модели, после чего подсчитывалось количество букв, дешифрованных неверно. Сравнительные результаты можно увидеть в табл. 1.

Таблица 1. Количество ошибочно дешифрованных букв

Номер текста

1

2

3

4

5

6

7

8

9

10




Классическая модель

4

14

20

43

14

25

0

44

4

6




Островная модель

6

2

15

12

10

2

9

4

40

2




Номер текста

11

12

13

14

15

16

17

18

19

20

Среднее

Классическая модель

24

8

50

73

43

3

27

9

36

63

25,52

Островная модель

7

8

0

9

4

3

1

30

1

14

8,95

Если проанализировать значение фитнесс-функции лучшей особи в конце работы алгоритма, результаты будут схожи друг с другом: только в 5 из 20 тестов значение фитнесс-функции в классической модели больше, чем в островной. Таким образом, островная модель позволила существенно улучшить качество находимого решения, причем время работы выросло незначительно.

Анализ вычислений в MPI


Испытания распределённого приложения на основе классического алгоритма были проведены на двухъядерном процессоре. Распараллеливание велось по параметру z: первый процесс перебирал целые значения от 0 до 2, второй – от 3 до 6. В результате первый процесс запускает 21 генетический алгоритм, второй – 28. Решение, очевидно, будет получено только одним из них.

Сводные результаты тестирования приведены в табл. 2.

Результаты дешифрования, как и значения фитнесс-функции, оказываются очень близкими. Если сравнить время выполнения алгоритма без MPI с суммой двух процессов при распараллеливании, можно увидеть, что они почти равны (разница не превышает 1-2 секунд). Таким образом, если бы работа между процессами была разделена равномерно, был бы получен почти двукратный выигрыш по времени. Объясняется это тем, что всю организацию распараллеливания между узлами берёт на себя интерфейс MPI.

Таблица 2. Результаты тестирования вычислений в MPI для 2-х процессов



Текст №

Fitness (без MPI)

Время (без MPI)

Fitness (1 й процесс)

Fitness (2 й процесс)

Время (1 й процесс)

Время (2 й процесс)

1

0,4281

55,18

0,1833

0,4737

24,53

32,45

2

0,5693

59,91

0,2152

0,5693

26,12

35,51

3

0,3267

47,43

0,1847

0,3341

21,37

27,84

4

0,4172

52,09

0,2189

0,4825

23,51

30,53

5

0,5018

73,03

0,2133

0,4829

32,96

42,64

Заключение


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

Кроме того, с учетом специфики задачи, была предложена вторая, оригинальная распределенная модель генетического алгоритма, которая также позволила сократить время решения: при использовании кластера из k узлов без потери качества вычисления ускоряются почти в k раз.

Библиографический список

1. Сизов В.П. Криптографические алгоритмы на основе тригонометрических функций [HTML] (http://www.ruscrypto.ru/sources/conference/rc2005).

2. Jakobsen T. A Fast Method for the Cryptanalysis of Substitution Ciphers. Dragoer, Denmark, 1995.

3. Харин Ю.С., Берник В.И., Матвеев Г.Е. Математические и компьютерные основы криптологии: Учеб. пособие. – Минск: Новое знание, 2003.

4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. – М.: Физматлит, 2006.
Distributed models of genetic algorithms as a way to parallel computations in cryptanalysis of trigonometric cipher task

GorodilovA.Yu., Mitrakov A.A.

Perm State University, Russia, 614990, Perm, Bukireva st., 15

e-mail: gora830@yandex.ru, tom-trix@ya.ru

In the article the possibility of constructing distributed models of genetic algorithms in cryptanalysis of trigonometric cipher task is considered. The common approach for solving the task with genetic algorithms is described; two ways to parallel computations are suggested: island model and cluster computations in MPI. Practical experiments confirm, that suggested models allow reducing task solving time without reducing result quality.

Похожие:

Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconГенетические алгоритмы как способ решения оптимизационной задачи расположения новых сейсмических станций
Целью данной работы является применения генетических алгоритмов к оптимизационной задаче расположения новых сейсмических станций...
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconАппаратная реализация генетических алгоритмов
Как следствие расширения области применения, наиболее остро встает вопрос разработки методов повышения эффективности генетических...
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconТеория сложности вычислений
Разрешимые и перечислимые множества. Нумерации вычислимых функций. Модели вычислений. Примеры неразрешимых проблем. Сводимость одних...
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconРассмотрим подробнее ситуацию, в которой ведется криптоанализ. В определение шифра входят следующие параметры
В определение шифра входят следующие параметры Т, х, у, k, Т. Защищаемая информация описывается параметром х. Сама идея криптоанализа...
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconН. В. Нуждин, В. В. Пекунов, С. Г. Сидоров, Л. П. Чернышева, Ф. Н. Ясинский (г. Иваново) Опыт распараллеливания вычислений для моделей процессов в сплошных средах
Рассматриваются пути оптимизации вычислений на многопроцессорном компьютере для течений, осложненных физико-химической кинетикой
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconОтображение численных алгоритмов на параллельные и распределенные вычислительные системы
Эффективная реализация предложенных алгоритмов на массивно-параллельных компьютерах осуществлялась за счет выбора стратегии распределения...
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconПрименение методов интервальной арифметики к задаче построения псевдотраектрий
В работе описан алгоритм, поиска псевдотраекторий[1], основанный на использовании аппарата интервальных вычислений. Приводится описание...
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconРаспараллеливание вычислений при интегрировании уравнений химической кинетики в задачах математического моделирования сложных экологических процессов
Принципы распараллеливания вычислений при интегрировании уравнений химической кинетики существенно зависят от наличия или отсутствия...
Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconПовышение эффективности комплексного управления материальными ресурсами с применением генетических алгоритмов

Распределенные модели генетических алгоритмов как способ распараллеливания вычислений в задаче криптоанализа тригонометрического шифра iconПрограмма: Специализированный программный комплекс "Факторизация полиномов "
Программа предназначена для автоматизации вычислений с полиномами от одной и двух переменных над кольцами целых и целых гауссовых...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org