Оценка вычислительной стойкости защиты информации алгоритмами "распределенных согласований" тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат технических наук Курилкина, Анастасия Михайловна

• Курилкина, Анастасия Михайловна
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Курилкина, Анастасия Михайловна

ВВЕДЕНИЕ.

1. АНАЛИЗ ЗАДАЧ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ И ОЦЕНКИ БЕЗОПАСНОСТИ КАСКАДНЫХ ШИФРОВ.

1.1. Задача дискретного логарифмирования в конечных полях.

1.1.1. Постановка задачи дискретного логарифмирования в конечных полях.

1.1.2. Особенности применения дискретного логарифмирования в конечных полях.

1.2. Задача дискретного логарифмирования на эллиптической кривой.

1.2.1. Постановка задачи дискретного логарифмирования на эллиптической кривой.

1.2.2. Особенности применения дискретного логарифмирования на эллиптической кривой.

1.3. Задача анализа безопасности каскадных шифров.

1.3.1. Каскадные шифры.

1.3.2. Анализ безопасности каскадных шифров.

1.3.3. Оценка анализа безопасности каскадных шифров.

1.4. Выводы.

2. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ МЕТОДА СОГЛАСОВАНИЯ И МЕТОДА "РАЗДЕЛЯЙ И ПОБЕЖДАЙ".

2.1. Методы согласования и "разделяй и побеждай", и их анализ.

2.2. Оценка трудоемкости методов.

2.3. Возможные принципы распараллеливания методов и алгоритмы "распределенных согласований".

2.4. Оценка эффективности разработанных алгоритмов.

2.5 Выводы.

3. РАЗРАБОТКА И ОЦЕНКА ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ

АЛГОРИТМОВ АНАЛИЗА КАСКАДНЫХ КЛАССИЧЕСКИХ ШИФРОВ.

3.1. Анализ каскадных шифров алгоритмами "распределённых согласований".

3.2. Алгоритмы "распределённых согласований" анализа безопасности двойного DES.

3.3. Оценка эффективности разработанных алгоритмов.

3.4 Выводы.

4. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ МЕТОДОМ СОГЛАСОВАНИЯ.

4.1. Математическая основа алгоритмов "распределённых согласований" для задачи дискретного логарифмирования в конечных полях.

4.2. Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования в конечных полях.

4.3. Математическая основа алгоритмов "распределённых согласований" для задачи дискретного логарифмирования на эллиптической кривой.

4.4. Алгоритмы "распределённых согласований" для задачи дискретного логарифмирования на эллиптической кривой.

4.5. Оценка эффективности разработанных алгоритмов.

4.6. Выводы.ИЗ

5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК РАЗРАБОТАННЫХ АЛГОРИТМОВ.

5.1. Среда реализации алгоритмов.

5.2. Описание программы разработанного алгоритма "распределённых согласований" для анализа безопасности двойного DES.

5.3. Описание программы разработанного алгоритма "распределённых согласований" для задачи дискретного логарифмирования в конечном поле.

5.4. Экспериментальные оценки разработанных алгоритмов.

5.5. Выводы.

Введение диссертации (часть автореферата) на тему «Оценка вычислительной стойкости защиты информации алгоритмами "распределенных согласований"»

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

разделяют на теоретическую и практическую.

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

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

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

Ф {а,к) = Ь, (1) где Ф(а,к)- нелинейная функция, секретный ключ к е Fn, а и b некоторые известные постоянные величины. Не малая часть этих уравнений представляет собой уравнение вида

Ик') = г(П, (2) где у/{к'),у{к")~ нелинейные функции, {к\к") = к, k'eFni, k"eFn2,

Fn[ х Fni =Fn. В частности, такие уравнения получаются при анализе стойкости каскадных схем и алгоритмов, основанных на дискретном возведении в степень.

Существуют разнообразные способы решения нелинейного уравнения (2), однако лишь детерминированные методы гарантируют нахождение верного результата. Среди них своей универсальностью выделяются методы тотального опробования, согласования и "разделяй и побеждай".

Известными математиками, занимающимися исследованиями в области защиты информации, Грушо А.А., Ростовцевым А.Г., Маховенко Е.Б., В. Диффи, Хеллман М. было показано, что в среднем трудоемкость метода согласования состоит из (jAr'| + |A:"|)+(jA:'| + |A:"|)ln(jA:'| + |A:"|) опробований. А трудоемкость метода "разделяй и побеждай" составляет |&'|/2 + |&"|/2 опробований. Это значительно меньше \к'\ -|&"|/2 метода тотального опробования. К тому же Нечаев В.И. установил, что среди детерминированных методов оценки стойкости алгоритмов, основанных на дискретном возведении в степень, метод согласования является лучшим.

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

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

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

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

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

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

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

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

5. Проведение экспериментов для подтверждения полученных & теоретических оценок эффективности распараллеливания разработанных алгоритмов.

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

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

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

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

1. Впервые разработанные параллельные алгоритмы "распределенных согласований", позволяющие на п- мерной системе решать важные задачи, сводящиеся к решению уравнения вида ^(к') = у(к"), где у/(к'),у(к")~ нелинейные функции, k'eFnx, k"eFn2, (к',к")-к, к е ^п» Рщ х Fn-> = Fn •

2. Параллельные алгоритмы "распределенных согласований" для анализа каскадных шифров. Полученные оценки эффективности распараллеливания алгоритмов (ускорение R = Tl/Tw, где Тх- время решения задачи на однопроцессорной системе, a Tw - время решения той же задачи на w- процессорной системе) "распределённых согласований" для анализа безопасности двойного DES показывают,

D W что R =-, где w—количество процессоров.

1 + 0,115 ■ w

3. Параллельные алгоритмы "распределенных согласований" для отыскания дискретного логарифма в конечных полях и в группе точек эллиптической кривой над конечным полем. Полученные теоретические оценки эффективности распараллеливания алгоритмов "распределённых согласований" для решения задачи дискретного логарифмирования в конечном поле показывают, что R, например, при w = 2 и t = 1700 будет составлять 1,83.

Практическую ценность работы представляют:

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

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

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

Основные положения, выносимые на защиту:

1. Алгоритмы "распределенных согласований", основанные на детерминированном методе согласования, которые позволяют на многопроцессорной системе решать важные задачи, сводящиеся к решению уравнения вида ч/(к') = у(к"), где у/(к'),у(к")- нелинейные функции, к' е Fm , k" е F„2, (к',к") = к, к eFn Fn{ х Fni = Fn.

2. Алгоритмы "распределённых согласований" для анализа безопасности каскадных шифров.

3. Алгоритмы "распределённых согласований" для решения задачи дискретного логарифмирования в конечных полях и на эллиптической кривой.

4. Теоретические оценки эффективности распараллеливания разработанных алгоритмов.

5. Экспериментальное подтверждение теоретических оценок. Апробация работы. Результаты работы докладывались и обсуждались на научно- практических конференциях: VI международной научно-практической конференции «Информационная безопасность» (Таганрог,

2004), VII всероссийской научной конференции молодых ученых и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2004), II всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2004), VII всероссийской научной конференции с международным участием «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2004), I ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН (Ростов, 2005), VII международной научно-практической конференции «Информационная безопасность» (Таганрог,

2005).

Результаты работы использованы в НИИ МВС ТРТУ при выполнении ОКР «Разработка базового инструментария для параллельно-конвейерной реализации вычислительно трудоемких фрагментов задач проблемной области в оперативно-приемлемое время при различных условиях применения»; в учебном процессе кафедры БИТ ТРТУ по курсу

Криптографические методы и средства обеспечения информационной безопасности", (что подтверждено соответствующими актами).

Публикации. По теме диссертации опубликовано 10 научных работ. Программа, полученная в ходе выполнения работы, зарегистрирована в Ы Реестре программ для ЭВМ (свидетельство об официальной регистрации программы для ЭВМ № 2005611241 от 27 мая 2005г.)

Структура и объем работы. Материал диссертационной работы изложен на 132 странице машинописного текста. Работа состоит из введения, пяти разделов, заключения и списка литературы из 54 наименований.

Заключение диссертации по теме «Методы и системы защиты информации, информационная безопасность», Курилкина, Анастасия Михайловна

5.5. Выводы

1. Для среды Windows NT с использованием пакета MPI 1.3 созданы программы алгоритмов "распределённых согласований" (П-1 и П-2) для анализа безопасности двойного DES и решения задачи дискретного логарифмирования в конечном поле, которые позволяют экспериментально оценивать временные затраты этих алгоритмов при различных значениях параметров (w и f), а также ускорение относительно их последовательных аналогов. В качестве языка программирования использовался Visual Studio 2003.

2. Экспериментальное исследование разработанных алгоритмов с помощью созданных программ показало, что ускорение при наличии двух процессоров для алгоритма анализа безопасности двойного DES (Б-3.1.2) будет не менее 1,892; для алгоритма дискретного логарифмирования в конечном поле при />2770 будет более 1,768. Созданные программы подтверждают теоретические оценки ускорения.

126

ЗАКЛЮЧЕНИЕ

В результате анализа детерминированных методов согласования и "разделяй и побеждай" выявлена возможность и необходимость их распараллеливания. Благодаря чему впервые в данной работе на основе этих методов разработаны алгоритмы "распределенных согласований", позволяющие на п- мерной системе решать важные задачи, сводящиеся к решению нелинейного уравнения вида к') = у{к"), где у/{к'\у(к")~ нелинейные функции, к' efni, &"eF„2, (к',к") = к, keFn, F х Fni = Fn; произведена оценка эффективности их распараллеливания (ускорения R).

Разработаны алгоритмы "распределенных согласований" для анализа стойкости каскадных шифров; получены теоретические оценки эффективности их распараллеливания. Полученные оценки эффективности алгоритмов "распределённых согласований" для анализа безопасности двойного DES проиллюстрированы на конкретных значениях технических w параметров. И показано, что R =-, где w - количество

1 + 0,115- w процессоров, а модифицированного алгоритма (Б-3.1.2), оперирующего w фреймами, Rr » г**/ , с

1 + 0,01356-w

Разработаны алгоритмы "распределённых согласований" для анализа стойкости протоколов защиты цифровой информации основанных на дискретном логарифмировании в конечных полях и в группе точек эллиптической кривой над конечным полем; произведены оценки эффективности распараллеливания разработанных алгоритмов и анализ влияния параметров. Полученные теоретические оценки эффективности алгоритмов "распределённых согласований" для дискретного логарифмирования в конечном поле проиллюстрированы на конкретных значениях технических параметров и показывают, что R, например, при и> = 2 и f = 1700 будет составлять 1,83.

Созданы программы алгоритмов "распределённых согласований" для анализа безопасности двойного DES и решения задачи дискретного логарифмирования в конечном поле, которые позволяют экспериментально оценивать временные затраты этих алгоритмов при различных значениях параметров (w и /). В качестве инструментария программирования использован пакет WMPI 1.3 для среды Windows NT. В качестве языка программирования использовался Visual Studio 2003.

Экспериментальные оценки разработанных алгоритмов с помощью созданных программ показали, что ускорение при наличии двух процессоров модифицированного алгоритма "распределённых согласований" (Б-3.1.2) для анализа безопасности двойного DES будет «1,9, для дискретного логарифмирования в конечном поле при t = 1700 будет «1,65. Созданные программы подтверждают теоретические оценки ускорения.

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

128

Список литературы диссертационного исследования кандидат технических наук Курилкина, Анастасия Михайловна, 2005 год

1. Ростовцев А., Маховенко Е. Подпись и шифрование на эллиптической кривой: анализ безопасности и безопасная реализация// Проблемы информационной безопасности. Компьютерные системы. 2003. №1. С.73-83.

2. Ростовцев А., Маховенко Е. Реализация протоколов на эллиптических кривых// Проблемы информационной безопасности. Компьютерные системы. 1999. №4. С.62-67.

3. ГОСТ Р 34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.

4. Ростовцев А., Маховенко Е. Введение в криптографию с открытым ключом. СПб.: Мир и семья, Интерлайн, 2001.

5. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.

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

7. Грушо А.А., Применко Э.А., Тимонина Е.Е. Анализ и синтез криптоалгоритмов.: Курс лекций.: Йошкар-Ола, 2000.

8. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии./ Москва, МЦНМО, 2003. С. 12-14.

9. Бабенко Л.К., Курилкина A.M. Распараллеливание решения задачи дискретного логарифмирования на эллиптической кривой // Материалы

10. VII международной научно-практической конференции «Информационная безопасность».- Таганрог: ТРТУ, 2005- С. 195-199.

11. Нечаев В.И. Элементы криптографии (Основы теории защиты информации)./Под ред. В.А. Садовничего-М.:Высш.шк.,1999.

12. Maurer U. М. and Massey J.L. Cascade Ciphers: The Importance of Being First. Journal of Cryptology: v.6, n.l, 1993. Pp.55-61.

13. Шнайер Б. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Си. М.:ТРИУМФ:2002. С.401-413.

14. G. В. Purdy, A high security log-in procedure, Comm. ACM 17 (1974), 442445.

15. W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trams. Inform.Theory, IT-22 (1976), 644-654.

16. P. K. S. Wah and M. Z. Wang, Realization and application of the Massey-Omura lock, pp. 175-182 in Proc. Intern. Zurich Seminar, March 6-8, 1984.

17. T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. On Inform. Theory, vol. IT-31, pp. 469-472, July 1985.

18. M. Blum and Micali, How to generate cryptographically strong sequences of pseudo random bits, SIAM J. Computing, 13(4): 850-863, November 1984.28