Основе эволюционно-оптимизационных методов - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Миазма человечества – псоры 5 957.07kb.
Техническое задание на выполнение исследовательского проекта «Разработка... 1 93.18kb.
Инструкция пользовател 1 323.99kb.
2 Понятие и классификации психологических методов 3 Виды основных... 1 61.26kb.
Эволюционно стабильная информационная структура верификации программ... 1 109.91kb.
Комбинированные методы обработки сейсмической информации для решения... 1 86.46kb.
Совершенствование методов управления конкурентоспособностью текстильного... 1 298.05kb.
11 августа, воскресенье 1 53.92kb.
Разработка принципов и методов построения программных систем поддержки... 1 457.73kb.
Методы и модели стохастического программирования 1 41.25kb.
Техническое задание на дипломное проектирование 7 3автоматизация... 4 746.08kb.
Множество вопросов к экзамену по курсу «Криптографические методы... 1 16.58kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Основе эволюционно-оптимизационных методов - страница №1/1

УДК 004.056.55

РАЗРАБОТКА МЕТОДОВ ИНФОРМАЦИОННОЙ ЗАЩИТЫ В

ЭКОНОМИЧЕСКИХ ИНФОРМАЦИОННЫХ СИСТЕМАХ НА

ОСНОВЕ ЭВОЛЮЦИОННО-ОПТИМИЗАЦИОННЫХ МЕТОДОВ
Ю.О. Чернышев, А.С. Сергеев, Е.О. Дубров, А.Н. Рязанов

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

Ключевые слова. Криптоанализ, генетический алгоритм, эволюционная оптимизация, шифры перестановок и замены, хромосома, кроссинговер, функция приспособленности.
DEVELOPMENT OF METHODS OF INFORMATION PROTECTION IN

ECONOMIC INFORMATION SYSTEMS ON THE BASIS OF EVOLUTIONARY AND OPTIMISING METHODS
Ju.O Chernyshev, A.S. Sergeev, E.O. Dubrov, A.N. Rjazanov
Summary. The problem of cryptanalysis of methods of cryptographic protection in information systems of economy with use of methods of evolutionary optimization and genetic search is considered. Methods of cryptanalysis of symmetric codes of shifts, and also methods of cryptanalysis of codes of simple and difficult replacement are considered, the results of experimental realization testifying to possibility of application of evolutionary methods for a problem of cryptanalysis by development of systems of ensuring information security in economy are given.
Keywords. Cryptanalysis, genetic algorithm, evolutionary optimization, codes of shifts and replacement, chromosome, crossover, fitness function.
Известно, что основной проблемой при разработке информационных систем в экономике является проблема обеспечения информационной безопасности и защиты информации, для чего широкое применение находят криптографические методы защиты. Данная статья посвящена проблеме разработки методов защиты информации на основе криптографических методов и алгоритмов, а также задаче криптоанализа методов криптографической защиты. Как отмечено в [1], основными задачами в криптографии являются разработка новых способов шифрования, сложных для вскрытия, и нахождение новых способов вскрытия существующих шифров (задача криптоанализа).

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

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

Вначале рассмотрим методы криптоанализа симметричных шифров перестановок, описанных в [2]. Поскольку, как отмечено в [2], при использовании шифрующих таблиц ключом является перестановка (р1, р2,…рn), то хромосома в генетическом алгоритме (ГА) должна также задавать перестановку, при этом основной вопрос – как осуществить представление отдельных генов особи. В простейшем случае кодирование осуществляется путем присвоения отдельным генам соответствующих элементов ключа, т.е. i –м геном хромосомы Р считать элемент pi. Как отмечено в [1], основным недостатком такого подхода является то, что гены получаются зависимыми друг от друга, тем не менее, такое определение генов не требует дополнительных затрат на их формирование. Для предотвращения получения нелегальных решений при десятичном кодировании хромосом используется правило: при появлении в хромосоме одинаковых генов второй повторяющийся ген заменяется на отсутствующий. В качестве функции приспособленности особей использовался факт совпадения открытого текста и шифртекста при реализации криптоанализа 2 типа для определения секретного ключа. В [1] в качестве целевой функции предлагается использовать функцию Якобсена о распределении частот биграмм, описанную в [3].

Отметим, что результаты экспериментальной реализации для криптоанализа 2 типа методов одиночной, двойной и простой перестановки по ключу приведены в [4].

Рассмотрим применение данных подходов для реализации шифров простой замены, при которых символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. Реализацию криптоанализа шифров простой замены на основе генетических методов рассмотрим на примере аффинной системы подстановок Цезаря и системы подстановок с ключевым словом [2].

Отметим, что в случае аффинного шифра для вскрытия шифра требуется определить два значения – это a и b, которые и служат ключом этого шифртекста. В качестве хромосомы используются эти значения (в виде а|b). Использовался разрезающий кроссинговер с одной точкой и десятичное кодирование. Pезультаты сходимости ГА при использовании стандартного английского алфавита, который содержит 26 букв (N = 26) при a = 9, b = 17 приведены в таблице 1. Количество потомков от популяции составляло 50% . Как показывают полученные результаты, с увеличением размера начальной популяции, количество итераций до сходимости целевой функции уменьшается. Отметим, что в таблицах ниже обозначены: t - номер запуска, n - размер популяции, IT - количество итераций, КР – тип кроссинговера. N - мощность алфавита.

Рассмотрим применение ГА для криптоанализа системы Цезаря с

ключевым словом, в которой наряду с числовым ключом, задающим

Таблица 1.Сходимость ГА при N=26 аффинного шифра.


t


1

2

3

4

1

2

3

4

1

2

3

4

n

8

8

8

8

16

16

16

16

64

64

64

64

IT

45

48

47

47

39

37

40

38

18

15

19

17

смещение, используется ключевое слово для изменения порядка символов в заменяющем алфавите. В этом случае предлагается использовать два варианта применения генетического алгоритма. В первом случае будем считать, что априорно известна информация о длине ключевого слова. В этом случае зная длину ключевого слова необходимо подобрать числа, представляющие его, что и будет являться целью поиска ГА. Множество этих чисел, таким образом, может быть использовано в качестве хромосомы, Для определения числового ключа использовалась параллельная реализация ГА для каждой позиции ключа к, т.е. осуществлялась реализация распараллеливания поиска по алфавиту. После определения кодового слова и кодового числа осуществляется формирование таблицы подстановки, Результаты cходимости ГА для N=26 символов представлены в таблице 2.



Таблица 2. Результаты сходимости ГА при N=26 шифра Цезаря при известной длине ключа.

t

1

2

1

2

1

2

1

2

1

2

1

KP

1 т.

1 т.

2 т.

2 т.

1 т.

1 т.

2 т.

2 т.

1 т.

1 т.

2 т.

n

1024

1024

1024

1024

2048

2048

2048

2048

8192

8192

8192

IT

489

502

524

530

452

458

470

489

402

395

435

Рассмотрим случай, когда нам неизвестна длина кодового слова. Хромосома представляет собой весь набор чисел, который содержится в алфавите, при этом число вариантов, которым можно сформировать алфавит длины N, равняется N!. Результаты исследования сходимости ГА при различных длинах алфавита N показаны в таблице 3.

Рассмотрим применение ГА для криптоанализа блочных шифров замены (шифры Плейфейра и «двойной квадрат»). Шифр Плейфейра предусматривает шифрование пар символов (биграмм) вместо одиночных

символов и более устойчив к криптоанализу, чем шифр простой замены,



Таблица 3. Результаты сходимости ГА при N=26 шифра Цезаря при неизвестной длине ключа.

N

16

16

16

16

32

32

32

32

38

38

38

38

KP

2 т.

4 т.

2 т.

4 т.

2 т.

4 т.

2 т.

4 т.

2 т.

4 т.

3 т.

5 т.

n.

2048

2048

4096

4096

2048

2048

4096

4096

4096

4096

8192

8192

IT

587

602

489

460

1548

1644

1493

1512

4529

5024

4217

4475

так как затрудняется частотный анализ. Криптоанализ шифра Плейфейра с помощью ГА также производится двумя способами: при известной и неизвестной длине ключевого слова. В качестве хромосомы использоваться это слово, буквы в алфавите представляются цифрами от 0 до 36. Результаты исследования при известной длине ключевого слова представлены в таблице 4.

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

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

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

Отметим применение ГА для криптоанализа шифров многоалфавитной



Таблица 4. Исследование сходимости ГА при известной длине ключевого слова для шифра Плейфейра .

t

1

2

1

2

1

2

1

2

1

2

1

2

KP

1 т.

1 т.

2 т.

2 т.

1 т.

1 т.

2 т.

2 т.

1 т.

1 т.

2 т.

2

т.


n

1024

1024

1024

1024

2048

2048

2048

2048

8192

8192

8192

8192

IT

589

592

514

531

452

444

476

489

412

407

370

416

Таблица 5. Исследование сходимости ГА при неизвестной длине ключевого слова.

t

1

2

3

1

2

3

1

2

3

N

16

16

16

16

16

16

32

32

32

KP

2 т.

3 т.

4 т.

2 т

3 т.

4 т.

2 т.

3 т.

4 т.

n

2048

2048

2048

4096

4096

4096

2048

2048

2048

IT

690

702

652

521

497

487

1698

1705

1688




t

1

2

3

1

2

3

1

2

3

N

32

32

32

48

48

48

48

48

48

KP

2 т.

3 т.

4 т.

2 т

3 т.

4 т.

2 т.

3 т.

4 т.

n

4096

4096

4096

4096

4096

4096

8192

8192

8192

IT

1363

1408

1382

5589

5427

5224

4579

4618

4502

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



Таблица 6. Исследование сходимости ГА при размере таблиц 6х6 для шифра «двойной квадрат»



KP

4 т.

6 т.

4 т.

6 т.

4 т.

6 т.

4 т.

6 т.

n

16384

16384

32768

32768

65536

65536

131072

131072

IT

1124

117308

87536

85470

79362

80201

78964

79014


Таблица 7. Исследование сходимости ГА при меньшем размере таблиц для шифра «двойной квадрат»




3x3

3x3

4x4

4x4

5x5

5x5

КР

4 т.

4 т.

4 т.

4 т.

5 т.

5 т.

n

4096

8192

8192

16384

16384

65636

IT

12589

10572

31002

28630

64117

58982

которое представляет собой массив цифр. Результаты экспериментальной реализации при использовании алфавита из 37 символов и ключевого слова из 9 символов приведены в таблице 8.



Таблица 8. Результаты криптоанализа шифра Вижинера.

t

1

2

3

1

2

3

1

2

3

KP

2 т.

3 т.

4 т.

2 т

3 т.

4 т.

2 т.

3 т.

4 т.

n

2048

2048

2048

4096

4096

4096

8192

8192

8192

IT

854

785

806

705

687

699

551

543

574

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



Литература

1. Материалы сайта: http://vestnik.psu.ru/files/articles/8_83883. - Городилов А.Ю. Криптоанализ перестановочного шифра с помощью генетического алгоритма.

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

3 Аграновский А.В., Хади Р.А. Практическая криптография: алгоритмы и их программирование. – М.: СОЛОН-Пресс, 2002.

4. Чернышев Ю.О., Сергеев А.С., Дубров Е.О. Применение биоинспирированных методов оптимизации для реализации криптоанализа классических и блочных криптосистем // Теоретические и прикладные вопросы современных информационных технологий: Материалы 11 Всероссийской научно-технической конференции. - Улан-Удэ: Изд-во ВСГТУ, 2012, с. 121-131.

Сведения об авторах



Место работы – Донской государственный технический университет, 344000, г. Ростов-на-Дону, пл. Гагарина 1.

Чернышев Юрий Олегович - доктор технических наук, профессор кафедры «Автоматизация производственных процессов», заслуженный деятель науки РФ, почетный профессор ДГТУ.

Сергеев Александр Сергеевич - кандидат технических наук, докторант кафедры «Автоматизация производственных процессов».

Дубров Евгений Олегович, Рязанов Александр Николаевич - аспиранты кафедры «Автоматизация производственных процессов».

Контактный адрес для переписки – Сергееву А.С., ул. Инициативная, 44, кв. 12, г. Таганрог, Ростовская обл., Россия, 347942.

Контактный адрес электронной почты - sergeev00765@mail.ru

Контактные телефоны для связи - 8-928-758-57-19.

Область научных интересов – биоинспирированные методы оптимизации, а также

их применение для решения актуальных экономических и научно-технических задач.