Читать онлайн «Введение в теоретико-числовые методы криптографии»

•САНКТПЕТЕРБУРГ• •МОСКВА• •КРАСНОДАР• 2011  M. М. ГЛУХОВ, И. А. КРУГЛОВ А. Б. ПИЧКУР, А. В. ЧЕРЕМУШКИН ВВЕДЕНИЕ В ТЕОРЕТИКО ЧИСЛОВЫЕ МЕТОДЫ КРИПТОГРАФИИ УЧЕБНОЕ ПОСОБИЕ • ДОПУЩЕНО Учебнометодическим объединением вузов по образованию в области информационной безопасности в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 090101 «Криптография» САНКТПЕТЕРБУРГ•МОСКВА•КРАСНОДАР 2011 ББК 22. 131я73 Г 55 Глухов М. М. , Круглов И. А. , Пичкур А. Б. , Черемушкин А. В. Г 55 Введение в теоретико$числовые методы крипто$ графии: Учебное пособие. — СПб. : Издательство «Лань», 2011. — 400 с. — (Учебники для вузов. Спе$ циальная литература). ISBN 9785811411160 Учебное пособие содержит полное изложение материала учеб$ ной дисциплины «Теоретико$числовые методы в криптографии» Государственного образовательного стандарта высшего профес$ сионального образования по направлению подготовки «Компью$ терная безопасность». Основу учебного пособия составляют результаты элементар$ ной теории чисел (главы 1–4). В последующих главах рассматри$ вается материал, имеющий многочисленные приложения в со$ временной криптографии: проверка простоты целых чисел, раз$ ложение целых чисел на множители, эллиптические кривые, дискретное логарифмирование, теория целочисленных решеток. Особое внимание в пособии уделено алгоритмическим аспектам теории чисел. Предназначено для студентов вузов, обучающихся по направ$ лениям подготовки в области информационной безопасности, а также для аспирантов. ББК 22. 131я73 Рецензенты: В. П. ЗЯЗИН, профессор кафедры «Информационная безопасность» МИРЭА, кандидат физико$математических наук, Э. А. ПРИМЕНКО, доцент кафедры математической кибернетики факультета ВМК МГУ им. М. В. Ломоносова. Обложка Л. А. АРНДТ Охраняется законом РФ об авторском праве. Воспроизведение всей книги или любой ее части запрещается без письменного разрешения издателя. Любые попытки нарушения закона будут преследоваться в судебном порядке. © Издательство «Лань», 2011 © М. М. Глухов, И. А. Круглов, А. Б. Пичкур, А. В. Черемушкин, 2011 © Издательство «Лань», художественное оформление, 2011  ВВЕДЕНИЕ На протяжении последних 30 лет в криптографии ак тивно исследуются криптографические системы с откры тым ключом. Каждая конкретная реализация этих систем требует выбора однонаправленной функции y = f(x), кото рая бы обеспечивала относительную простоту вычисления y по x и сложность решения обратной задачи. Из всех предла гавшихся к настоящему времени на эту роль функций прак тически наиболее интересными (с точки зрения обоснован ности и реализуемости) являются функции, основанные на некоторых сложных задачах теории чисел.