Автореферат (1137233), страница 4
Текст из файла (страница 4)
Алгебра: Учебник. В 2-х т. Т. I - М.: Гелиос АРВ, 2003.(с. 185,Следствие из Теоремы 1)3Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2004.4Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.15средств противостоять идентифицированным угрозам. Глава содержит такжеописание экспериментальных исследований, направленных на оценку и повышение эффективности разработанного алгоритма решения СЛУ в КВ.В разделе 4.1 определен набор основных требований к инструментальнымсредствам криптоанализа асимметричных шифров, на основе которого в разделе 4.2 проведен сравнительный анализ существующих программных решений и обоснована целесообразность разработки новых инструментальныхсредств.В разделе 4.3 описана реализация программного комплекса «Инструментальные средства криптоанализа асимметричных шифров» (далее –КРИПТО).
КРИПТО включает два компонента: динамическую библиотекуКОНСТРУКТОР и приложение АНАЛИТИК. В КРИПТО реализованы самыеэффективные на сегодня алгоритмы дискретного логарифмирования, которыеимеют субэкспоненциальную временную сложность: алгоритм КопперсмитаОдлыжко-Шреппеля и решето числового поля.
В числе алгоритмов факторизации – метод Полларда и «ECM» (вероятностный алгоритм Ленстры дляфакторизации целых чисел с помощью эллиптических кривых). Для проверкичисел на простоту реализованы вероятностный алгоритм Миллера-Рабина идетерминированный алгоритм Миллера.Для выполнения операций с длинными числами в библиотеке КОНСТРУКТОР использована известная свободно распространяемая математическая библиотека NTL (a Library for doing Number Theory). Выбор базовойбиблиотеки обусловлен её функциональностью, скоростью, компактностью ипереносимостью.
Приложение АНАЛИТИК написано на языке C#, обладаетудобным графическим интерфейсом и обеспечивает пользователю доступ кфункциям библиотеки КОНСТРУКТОР.Целью проведения экспериментов, описанных в разделе 4.4, была проверка гипотез 1 и 2, а также экспериментальная оценка эффективности разработанного алгоритма решения СЛУ в КВ по сравнению с наилучшим из существующих аналогов – методом сведения к семейству систем над полями Галуа. Алгоритмы были реализованы в составе КРИПТО.Эксперименты проводились на наборе исходных данных из матриц различных размерностей (от n ~ 10 до n ~ 103 ), полученных на первом этапе алгоритмов «index-calculus». На экспериментальных данных разработанный алгоритм показал время работы в 1,4 - 2 раза лучше, чем метод сведения к семейству систем над полями Галуа.В результате проведенных экспериментов подтвердилась гипотеза 1 оструктуре матриц, выдвинутая в разделе 3.2.
Кроме того, было обнаружено,что в исходной матрице среди ненулевых элементов практически отсутствуют значения, по величине сравнимые с p .С целью проверки гипотезы 2 для двух модификации разработанного алгоритма («прямой» и «обратный» ход) были построены графики функцииплотности матрицы на i-й итерации алгоритма D(i) , которая вычислялась по16формуле D(i) =Νin ⋅i{}⋅100% , где Ν i = akj ∈ An×m | a ≠ 0, k = 1, n, j = 1, n − i - множествоненулевых коэффициентов на i-й итерации – см.
рис. 6 (а). На рис. 6 (б) представлен график зависимости количества элементарных операций от плотности элементов в матрице, описываемый функцией O(i) =n(n − i ) D(i ).100%На рис. 7 показаны графики зависимости процентного соотношения«больших» элементов M матрицы от номера i итерации алгоритмаM (i ) =ΛiΝi{}⋅100% , где Λ i = akj ∈ An×m | a ≠ 0, aij = Θ( p ), k = 1, n, j = 1, n − i - множествобольших коэффициентов на i-й итерации.(а)( б)Рис. 6 – Плотность матрицы (а) и количество операций (б) на i-мшаге алгоритма: 1 – «прямой» ход, 2 – «обратный» ходВидно, что изменение порядка исключения неизвестных с учетом знанияструктуры матрицы позволяет вдвое сократить мультипликативную постоянную в оценке временной сложности обобщенного алгоритма решения СЛУ вКВ, что подтверждает гипотезу 2 ( c ≈ 2 ).Рис.
7 – Процентное соотношение «больших» элементов матрицы к общему числуэлементов на i-м шаге алгоритма: 1 – «прямой» ход, 2 – «обратный» ходПолученные результаты по улучшению методов решения СЛУ в КВ длязадачи дискретного логарифмирования имеют большое значение для достижения цели работы, т.к. прогресс в критоанализе приводит к пересмотру безопасности шифров и поэтому является важной частью комплексной оценкиаппаратно-программных средств обеспечения конфиденциальности и целостности информации.17В заключении приведены основные результаты, полученные в процессепроведенных исследований:- разработаны требования к новому методу комплексной оценки аппаратнопрограммных средств обеспечения конфиденциальности и целостности информации на основе анализа стандартов семейства ИСО МЭК 27000 и изучения существующих моделей и методов;- разработаны новые многокритериальные классификации злоумышленников, атак и средств обеспечения конфиденциальности и целостности;- разработана модель угроз безопасности информационных ресурсов организации;- разработан метод анализа рисков реализации угроз нарушения безопасности, использующий предложенные модели;- разработан метод комплексной оценки аппаратно-программных средствобеспечения конфиденциальности и целостности информации;- разработан комплекс программ для решения задач дискретного логарифмирования, факторизации и проверки чисел на простоту;- разработан новый детерминированный метод решения систем линейныхуравнений в кольцах вычетов, позволяющий ускорить работу алгоритмовдискретного логарифмирования типа index-calculus.Приложение содержит копию документа, подтверждающего внедрениерезультатов диссертационной работы, а также копии авторских свидетельств.ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ1.
Авдошин С.М., Савельева А.А. О новом подходе к проблеме анализа эффективности криптосистем// Информационные технологии, № 8, 2009, С. 2-9.2. Авдошин С.М., Савельева А.А. Криптоанализ: вчера, сегодня, завтра. // Открытые системы. № 3, 2009, с. 22-25.3. Авдошин С.М., Савельева А.А. Алгоритм решения систем линейных уравнений вкольцах вычетов // Информационные технологии, №2, 2006, С. 50-54.4. Савельева А.А. Инструментальные средства криптоанализа // Сборник материаловВсероссийского конкурса инновационных проектов аспирантов и студентов по приоритетномунаправлениюразвитиянаукиитехники«Информационнотелекоммуникационные системы». М.
- ГНИИ ИТТ «Информика», 2005. – 132 с. С. 44.5. Савельева А.А. Метод решения систем линейных уравнений в кольцах вычетов //XXXI Гагаринские чтения. Тезисы докладов Международной молодежной научной конференции. Т.4. М. - МАТИ, 2005. – C. 29-30.6. Савельева А.А. Анализ стойкости криптосистем, основанных на сложности задачидискретного логарифмирования// Информационные технологии в бизнесе: Тезисы докладов научно-технической конференции студентов, аспирантов и молодых специалистов. Москва, 2006. С.
130-134.7. Савельева А.А. Криптоанализ шифров, основанных на сложности задачи дискретногологарифмирования в конечных полях. // XXXII Гагаринские чтения. Тезисы докладовМеждународной молодежной научной конференции. Т.4. М.- МАТИ, 2006. – 154 с.8. Авдошин С.М., Савельева А.А. Криптографические методы защиты информационныхсистем // Известия АИН им. А.М. Прохорова. Бизнес-информатика. 2006.
Т. 17. С.91-99.189. Савельева А.А. Исследование алгоритмов дискретного логарифмирования и способыповышения их эффективности // «Новые информационные технологии: Сб. тез. докладовXIV Международной студенческой школы-семинара». М.- МИЭМ, 2006. С. 411-412.10. Савельева А.А. Новый подход к решению систем уравнений в задачах дискретного логарифмирования // Программное и информационное обеспечение систем различногоназначения на базе персональных ЭВМ: Межвузовский сборник научных трудов / Подред.
д.т.н., проф. Михайлова Б. М. М.- МГУПИ, 2006. Вып. 9 - С. 193-197.11. Авдошин С.М., Савельева А.А. Криптоанализ: современное состояние и перспективыразвития // Новые технологии; М.: Машиностроение, 2007. – 24 с. – (Приложение к журналу «Информационные технологии»; N 3). С. 1-24.12. Савельева А.А. Исследование эффективности алгоритмов дискретного логарифмирования, использующих факторную базу // Модернизация экономики и общественное развитие: сб. студенч. работ. М.: Изд.
Дом ГУ ВШЭ , 2007. – 498 с.13. Авдошин С.М., Савельева А.А. Криптотехнологии Microsoft // М.: Новые технологии,2008. (Приложение к журналу «Информационные технологии»; N9, 2008).14. Авдошин С.М., Савельева А.А. Проблемы оценки криптозащищенности информационных систем // «Новые информационные технологии». Тезисы докладов XVI Международной студенческой школы-семинара - М.: МИЭМ, 2008. – 297 с. С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
