автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Исследование алгоритма RSA и разработка практических рекомендация по повышению его эффективности

РГБ О Л

На правах рукописи

САЛЬНИКОВ СЕРГЕЙ АЛЕКСАНДРОВИЧ

ИССЛЕДОВАНИЕ АЛГОРИТМА RSA И РАЗРАБОТКА ПРАКТИЧЕСКИХ РЕКОМЕНДАЦИЙ ПО ПОВЫШЕНИЮ ЕГО ЭФФЕКТИВНОСТИ

05.13.06 - Автоматизированные системы управления.

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва 1996

Работа выполнена на Кафедре информационно-вычислительных систем Российского государственного гуманитарного университета и в Отделении "Гуманитарная экология" Международной академии информатизации.

Научный руководитель:

доктор технических наук, профессор Квасницкий В.Н.

Научный консультант:

доктор технических наук, профессор Аветисян Д.О.

Официальные оппоненты:

доктор технических наук, профессор Герасименко В.А. кандидат технических наук Попов Г. А.

Ведущая организация:

Институт проблем управления РАН

Автореферат разослан "<?-? " августа 1996г.

Защита состоится " о " $$тября 1996г. в

Аг

часов

на заседании специализированного совета Д163.01.01 при ВШИ

Отзывы просьба присылать па адресу: 113114, Москва, Второй кожевнический пер., 4/6.

ПВТИ.

/ученый секретарь

специализированного совета

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Актуальность настоящей работы вытекает из необходимости

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

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

Задачи исследования. В соответствии с поставленной целью проводимое исследование было направлено на решение следующих задач:

- сопоставительный анализ функционального назначения и возможностей различных алгоритмов открытого шифрования;

- подробное изучение криптосистемы RSA, выявление ее предельных теоретических возможностей;

- выявление возможных путей рассекречивания RSA и уменьшение вероятности ее взлома;

- разработка метода простых, составных и полных степеней и использование этого метода для повышения эффективности R3A.

Объект исследования. Объектом исследования является математическая модель криптосистемы RSA.

Методика исследования. В исследованиях были применены методы математического анализа, абстрактной алгебры, вероятностного анализа и прикладной теории информации.

Научная новизна результатов диссертационной работы состоит в следующем:

1) разработана и подробно изучена алгебраическая модель

- 6 -

функционирования криптосистемы RSA;

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

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

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

- разработанный метод простых, составных и полных степеней позволяет устанавливать зависимость криптостойкости системы от характера ее параметров;

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

Реализация и внедрение результатов работы. Результаты, полученные в диссертационной работе, были внедрены в

АО "ЛУКОЙЛ" (Тюмень),

АО "ОЛМИС" (Москва),

"Роскоминформ" (Тула),

ШЦИ МИД РФ,

Sumdeks (Сингапур).

Публикации. По теме диссертации опубликовано 8 научных работ, отражающих основное содержание диссертации.

п

- I

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе осуществлен сопоставительный анализ традиционных криптосистем с секретными ключами шифрования с криптосистемами открытого шифрования. Непредсказуемые темпы и масштабы расширения современных компьютерных сетей создают крайне затруднительные условия для дальнейшей эксплуатации криптосистем, ориентированных на использование секретных ключей шифрования. Более комфортными оказались системы открытого шифрования, широкое внедрение которых неразрывно связано с преодолением ряда проблем теоретического и прикладного характеров. При рассмотрении, например, криптосистемы {\5А, остается открытым вопрос о том, существуют ли эффективные методы разложения больших чисел на простые множители. С переходом на системы открытого шифрования возникают дополнительные трудности по организации электронной подписи. Важным недостатком существующих криптосистем открытого шифрования являются их плохие скоростные показатели. Чрезвычайно важным представляется круг вопросов, связанных с выбором подходящей криптосистемы открытого шифрования и оптимальной настройки ее параметров, обеспечивающих приемлемую криптостойкость (с

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

Во второй главе разработана алгебраическая модель функционирования алгоритма RSA. Сущность алгоритма RSA заключается в следующем:

каждый I -й абонент сети выбирает произвольно два различных достаточно больших простых числа (обычно по 100 десятичных знаков каждое) Pi и %¿ ■ ,. вычисляет число j/i = Pi . и значение арифметической функции Эйлера от числа jfi :

Далее выбирает произвольное достаточно большое и взаимно простое с с) число с , а также достаточно большое число clI , такое, чтобы имело место

-ecofù - f m о4 (ff^-j), (2)

Числа €.с и «ч/j в качестве открытого ключа шифрования рассылает всем абонентам сети. Число ofi хранит в тайне в качестве секретного ключа, которым вместе с -^L он будет пользоваться при расшифрованными конфиденциальных сообщений. После этого числа Pi , <í-¿ и данному абоненту не

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

При необходимости посылки в адрес I -го абонента конфиденциальных текстов, отправитель предварительно разбивает их на фрагменты (разумеется, если в этом есть необходимость), так, чтобы числовые представления этих фрагментов оказались меньше числа itfI . Шифрование каждого из этих

фрагментов ( ) сводится к вычислению отправителем числа

С1(Г):

Это число по открытому каналу посылается в адрес I -го абонента сети - получателя конфиденциальных сообщений. Последний, для расшифрования текста Т~ вычисляет:

С«'¿СО- (41

Если необходимо, чтобы j -й абонент поставил свсао подпись под конфиденциальным сообщением Т . то кроме числа

Сь С^) он вычисляет также числ°

г)* Т^ ж (5)

которое, так же как и число С1 (т) , посылает по открытому каналу в адрес I -го абонента. Последний вычисляет число

ЬЛ4 Л Л / хА/ / )

(б)

и сверяет его с числом Т . Совпадение этих чисел и служит доказательством того, что конфиденциальный текст 7~ С -А абонент получил от j -го абонента. Иными словами, условие Т1= Т эквивалентно наличию подписи -го абонента под текстом Т ■

Для всех Т , взаимно простых с ^I , справедливость (4) непосредственно следует из теоремы Эйлера (малой теоремы ферма) - при любых взаимно простых натуральных числах Т и ф/ число 7" - { делится без остатка на л/ .

В этой главе диссертационной работы приведено доказательство того, что (4) остается верным даже тогда, когда

7> жо^О

число 7" не является взаимно простым с У i , т.е. когда теорема Эйлера не имеет место. Здесь же приведено доказательство того, что формула (4) остается в силе при замене в ней функции f функцией , равной наименьшему

общему кратному чисел ^f(Pù) и Vffo) :

56^0- нок (7)

Это обстоятельство может привести к значительному уменьшению криптостойкости RSA, что следует учесть при выборе чисел И %1 •

При известном диапазоне , Л J чисел, откуда могут быть выбраны Р^ и i , криптостойкость системы RSA монотонно уменьшается с приближением величины Jj/i к граничным значениям Cf или Л .

В третьей главе, опираясь на алгебраическую модель функционирования криптосистемы RSA, разработан метод простых, составных и полных степеней. В этой главе рассматривается коммутативное кольцо Ks(^) классов вычетов по модулю S («V ) , где определены операции сложения и умножения по этому модулю. Среди элементов этого кольца можно выделить подмножество взаимно простых с числом S(_элементов, которые образуют коммутативную группу C{S (*t) • Число элементов этой группы равно ^f (s ) ^ .

В диссертационной работе рассматривается множество натуральных чисел, меньших л/ и взаимно простых с ним. Очевидно, они образуют коммутативную группу С/*/ относительно операции умножения по модулю и/ , причем число элементов этой группы равно У(^) • Доказывается, что возведение элементов группы Cfs/ в степень - Х + Л по мо-

дулю y/J эквивалентно к некоторой перестановке этих элемен-

тов тогда и только тогда, когда число )( является элементом группы ■ Таким образом, каждому элементу группы соответствует некоторая перестановка элементов

группы Ç

При возведении же элементов группы С и/ в степень ¡L- X + Л . где % не принадлежит к группе С/ s(*</) , всегда найдутся элементы, X степени которых равны между собой. В частности, найдется хотя бы один не равный единице элемент группы Q^ , такой, что его х ~я степень равна единице. Исходя из этого, в диссертационной работе элементы группы Q $(*/) названы простыми степенями для элементов группы (у jj . Показано, что порядки всех элементов коммутативной группы CjS(^) являются делителями числа S(S{*S)J. А поскольку числа G. и о/ непременно являются элементами группы CfS ) , то для элементов группы Q они являются простыми степенями. Более того, эти два элемента группы являются обратными друг другу, т.е. при из-

вестных числах е. и <*/ необходимое число ( м ) попыток по нахождению числа ej оказывается делителем числа ■ Это обстоятельство непременно следует учесть при эксплуатации RSA, так как при произвольном выборе числа Ç, , число W» , характеризующий фактическую криптостой-кость системы, может оказаться недопустимо маленьким. Такая опасность в диссертационной работе иллюстрируется на конкретных примерах.

В приложении приведен текст программного модуля на языке СИ, разработанного нами для экспериментальной проверки на конкретных числовых примерах результатов исследования алгебраической модели RSA.

- 12 -

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

Основные результаты и выводы.

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

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

3. На основе анализа алгебраической модели указана на несостоятельность случайного (произвольного) выбора параметров криптосистемы Р, % и 6. .

4. Разработаны рекомендации по выбору р и f, , таких, чтобы повысить криптостойкость системы.

5. Разработан метод простых составных и полных степеней.

6. Пользуясь этим методом удалось найти формулы, на основе которых разработаны практические рекомендации при выборе чисел е и d .

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

- 13 -

Основные положения диссертации опубликованы в следующих работах:

1. Исследование и устранение возможных каналов утечки информации ТС ЭВМ. Отчет по НИР. М., НИИ "Квант", 1987, 49 стр.

2. Исследование возможных каналов утечки закрытой информации за счет ПЭМИН. Научно-технический отчет по НИР. Ы., НИИ "Квант", 1988, 92 стр.

3. Создание и апробация перспективных методов технической диагностики, поиска неисправностей и ремонта радиоэлектронной аппаратуры (устройств хранения, обработки и визуализации аналоговой информации). М., 1991, 81стр.

4. Концепция построения информационной системы региона. Роскоминформ, М., 1995, 31стр.

5. Информационно-управляемая система корпорации Лукойл. Концепция построения. М., 1996, 41стр.

6. Аветисян Д.О., Сальников С. А. Об обеспечении конфиденциальности научно-технической информации, циркулируемой в сетях ЭВМ //НТИ. Сер.2.-1996.-N7.

7. Аветисян Д.О., Сальников С. А. К оценке криптостойкости алгоритма RSA //Защита информации.-1996.-N3(34).

8. Сальников С.А., Аветисян Д.О. О надежности электронной подписи, организуемой в сетях ЭВМ посредством криптосистемы RSA//Информационные ресурсы России.-1996.-N4