Методы и алгоритмы защиты информации

Руководитель семинара

Аржанцев Иван Владимирович

д.ф.-м.н., профессор

 

    

Аннотация 

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

Часть 1. Теория кодирования 

  Основные задачи теории кодирования. Коды, исправляющие ошибки. Расстояние Хэмминга и неравенство треугольника. Предварительные сведения из алгебры: вычеты, многочлены и конечные поля.
  Линейные коды и их характеристики. Код Хэмминга. Совершенные коды. Порождающая и проверочная матрицы. Двойственный код и тождество Мак-Вильямса. Эквивалентность кодов. Методы вычисления минимального расстояния для подпространства. Оценка Плоткина.
  Алгоритмы декодирования. Синдромы и минимальные представители.
  Циклические коды и главные идеалы. БЧХ коды. Бинарный и тернарный коды Голея. Конечные геометрии и системы Штейнера.
  Линейные рекуррентные последовательности и их свойства. 

Литература.

[1] С.Г.Влэдуц, Д.Ю.Ногин и М.А.Цфасман. Алгеброгеометрические коды. М.: МЦНМО, 2003
[2] П.Камерон и Дж.ван Линт. Теория графов, теория кодирования и блок-схемы. М.: Наука, 1980
[3] Р.Лидл и Г.Нидеррайтер. Конечные поля. М.: Мир, 1988 
[4] А.Ромащенко, А.Руменцев и А.Шень. Заметки по теории кодирования. М.: МЦНМО, 2011

Часть 2. Криптография 

  Простейшие криптографические системы. Открытый ключ и система RSA. Задача о рюкзаке и криптосистема Меркла-Хеллмана. 
  Циклические группы. Дискретное логарифмирование в абелевой группе и система Диффи-Хеллмана обмена ключами. Система Эль-Гамаля. 
  Необходимые сведения из алгебры и теории чисел. Проверка числа на простоту и проблема факторизации. Псевдопростые числа. Числа Кармайкла. Метод Поклингтона. (p-1)-метод Полларда. 
  Эллиптические кривые. Групповой закон и его свойства. Криптосистемы на эллиптических кривых: аналоги ключевого обмена Диффи-Хеллмана, системы Мэсси-Омуры и системы Эль-Гамаля. Задача дискретного логарифмирования на эллиптической кривой. 
  Проверка числа на простоту: обобщение метода Поклингтона и алгоритм Гольдвассера-Килиана. Числа Ферма и числа Мерсенна. Разложение числа на множители: метод Ленстры. Электронная цифровая подпись Эль-Гамаля. 

Литература. 

[1] Введение в криптографию. Под общей редакцией В.В.Ященко. М.: МЦНМО, 2012   
[2] Н.Коблиц. Курс теории чисел и криптографии. М.; ТВП, 2001
[3] Х.В.Ленстра-мл. Эллиптические кривые и теоретико-числовые алгоритмы. Международный конгресс математиков в Беркли (1986): обзорные доклады. М.: Мир, 1991, 164-193
[4] Ю.Г.Прохоров. Эллиптические кривые и криптография. М.: МГУ, 2007
[5] А.Саломаа. Криптография с открытым ключом. М.: Мир, 1986