Оптимизация выбора параметров для алгоритма Полларда

Актуальные проблемы авиации и космонавтики. Информационные технологии

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

Потеря от каждого электронного преступления оценивается специалистами от 100-400 тыс. до 1,5 млн дол.

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

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

1. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Че-ремушкин А. В. Основы криптографии. М. : Гелиос АРБ, 2002. 480 с.

2. Зайцев А. П., Шелупанов А. А., Мещеряков Р. В. Технические средства и методы защиты информации : учебник для вузов /под ред. А. П. Зайцева и А. А. Ше-лупанова. М. : Машиностроение, 2009. 508 с.

3. Титоренко Г. А. Информационные технологии управления. М. : Юнити, 2002.

4. Мельников Ю. Н., Иванов Д. Ю. Многоуровневая безопасность в корпоративных сетях. Международный форум информатизации - 2000 : докл. Меж-дунар. конф. 17-19 октября 2000 г. В 3-х т. Т. 2. М. : Станкин, 2000. 245 с.

© Гановичева С. С., 2012

УДК 669.713.7

А. С. Климина Научный руководитель - О. Н. Жданов Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

ОПТИМИЗАЦИЯ ВЫБОРА ПАРАМЕТРОВ ДЛЯ АЛГОРИТМА ПОЛЛАРДА

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

Алгоритм Полларда состоит из следующих шагов:

Шаг 1. Выбираем число к.

Шаг 2. Выбираем произвольное а, 1 < а < п.

Шаг 3. Вычисляем d = НОД (а,п). Если d > 1, мы получили нетривиальный делитель п. Если d = 1, переходим к шагу 4.

Шаг 4. Вычисляем Б = (ак - 1, п) и если 1 < Б < п, то Б является делителем п. Если Б = 1,возвращаемся к шагу 1, а при Б = п к шагу 2 и выбираем новое а [1].

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

1) перебор различных степеней простых чисел.

Задается массив простых чисел и максимальная

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

Пример: Допустим будут использованы первые 5 простых чисел: 2, 3, 5, 7, 11, а максимальная степень каждого 4.Тогда в первом случае к будет принимать значения 20305070111, 20305070112, 20305070113, ..., 24345474114, а во втором - наоборот: 24345474114, 24345474114, 24345474114, ..., 20305070111. Таким образом, достигается перебор всех возможных комбинаций простых чисел в разных степенях.

2) к - наименьшее общее кратное нескольких чисел.

Задается интервал чисел, для которых будет вычисляться НОК.

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

НОК от двух чисел:

НОК (6,7,8,9,10) = = НОК(НОК(НОК(НОК(6,7),8),9),Ю) = = НОК(НОК(НОК(42,8),9),Ю) = = НОК(НОК(168,9),Ю) = НОК(504,10) = 2520 = =23325171.

В ходе анализа результата работы программы выяснилось, что большая часть времени уходит на попытки разложить простые числа. Так, например, при работе программы с диапазоном чисел от 100000 до 100500 общее время работы программы составило 3446 секунд, из них 88 секунд было потрачено на удачное нахождение делителей, остальное время было потрачено на 44 числа, из которых 40 оказались простыми. В среднем на каждое простое число было потрачено 80 секунд.

Поэтому было принято решение перед попыткой факторизации проводить тест на простоту, используя алгоритм Рабина-Миллера [2]. Это увеличило время

Секция «Методы и средства зашиты информации»

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

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

В дальнейшем планируется изучение влияния параметра a на работу алгоритма Полларда, а так же реализация алгоритма Ленстры и сравнение эффек-

тивности работы этих двух алгоритмов на числах различной разрядности.

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

1. Маховенко Е. Б. Теоретико-числовые алгоритмы в криптографии. М. : Гелиос АРВ, 2006. 319 с.

2. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. М. : Постмаркет, 2001. 328 с.

© Климина А. С., 2012

УДК 004.056

Н. А. Коромыслов Научный руководитель - М. Н. Жукова Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

О ВОЗМОЖНОСТИ ЭКОНОМИИ РЕСУРСОПОТРЕБЛЕНИЯ ИСКУССТВЕННОЙ ИММУННОЙ СИСТЕМОЙ ПРИ РЕШЕНИИ ЗАДАЧИ КЛАССИФИКАЦИИ

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

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

К сожалению, в настоящее время существует лишь небольшое число вычислительных моделей, основанных на принципах работы иммунной системы. По-видимому, это связано с сохраняющейся неопределенностью основных положений, предложенных для ее описания.

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

- Определим свое как совокупность 8 строк длины 1 над конечным алфавитом, которую необходимо защищать или контролировать. Например, в качестве 8 могут выступать программа, файл данных (любое программное обеспечение) или нормальная форма активности, подразделяемые на подстроки.

- Образуем набор детекторов Я, каждый из которых не должен соответствовать любой строке в 8. Вместо точного, или идеального, соответствия используем правило частичного соответствия, при котором две строки соответствуют друг другу, если и только если они совпадают, по крайней мере, в г следующих друг за другом позициях, где г - некоторый целочисленный параметр.

- Проверим 8 на предмет изменений путем не-

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

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

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

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

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