URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы
Id: 123873
 
449 руб.

Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. №3. Изд.2, доп.

URSS. 2012. 356 с. Мягкая обложка. ISBN 978-5-484-01290-9.

 Аннотация

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

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


 Оглавление

Предисловие
1 Введение
 .1.Криптография с открытым ключом
 .2.Группы, кольца, поля
  .2.1.Группы
  Определение порядка элемента группы при известной факторизации порядка $n$ группы
  Поиск образующего элемента циклической группы
  Поиск элемента высокого порядка циклической группы
  .2.2.Кольца. Поля. Многочлены над полем
  .2.3.Алгоритм Евклида и его варианты
   Кольцо вычетов по данному модулю
2 Конечные поля и эллиптические кривые
 .1.Поля Галуа
  .1.1.Характеристика поля
  .1.2.Мультипликативная группа конечного поля
  .1.3.Конечное расширение поля
  .1.4.Поле разложения многочлена
  .1.5.Минимальные многочлены. Существование неприводимых многочленов
  .1.6.След и норма элемента конечного поля
  .1.7.Алгоритмическое представление конечного поля
  .1.8.Поле Галуа как векторное пространство
  Векторное пространство над полем Галуа
  Полиномиальные и нормальные базисы
  .1.9.Проверка, является ли нормальная система базисом. Переход от нормального базиса к стандартному
  .1.10.Переход от стандартного базиса к нормальному
  .1.11.О быстрой линейной алгебре
  Алгоритм "четырех русских" для умножения матриц над конечным полем
  .1.12.Быстрый алгоритм для решения систем линейных уравнений над конечным полем
  .1.13.Оптимальные и гауссовы нормальные базисы
  .1.14.Алгебраическое замыкание конечного поля
  .1.15.Квадратичные вычеты и извлечение квадратных корней в конечных полях
  Символ Якоби и алгоритм Кронекера
 .2.Эллиптические кривые
  .2.1.Алгебраические кривые и эллиптические кривые
  Дискриминант и инвариант эллиптической кривой
  .2.2.Группа точек эллиптической кривой
  .2.3.Эллиптические кривые над полями действительных и рациональных чисел
 .3.Эллиптические кривые над конечными полями
  .3.1.Порядок эллиптической кривой
  .3.2.Легко ли вычислить порядок группы точек эллиптической кривой
  .3.3.Применения теоремы Хассе
  .3.4.О структуре групп эллиптических кривых
3 Неприводимые многочлены
 .1.Тестирование и поиск неприводимых многочленов
  .1.1.Чем интересны неприводимые многочлены
  .1.2.Тест на неприводимость. Алгоритм Берлекемпа
  .1.3.Оценка сложности алгоритма Евклида
  .1.4.Тестирование неприводимости многочленов
  Об оценках сложности модулярного возведения многочленов в степень
  .1.5.О тестировании неприводимости многочленов малого веса
  Ускорение тестирования неприводимости многочленов малого веса специального вида
  .1.6.Асимптотически быстрый алгоритм тестирования неприводимости многочленов
  Быстрая модулярная композиция многочленов
  О схемной реализации модулярной композиции
  О возможности использования алгоритма Штрассена умножения матриц
  Оценка сложности тестирования неприводимости
  .1.7.Вероятностные алгоритмы тестирования неприводимости многочленов
  Еще один вероятностный алгоритм
  .1.8.Генерация неприводимых многочленов
 .2.Тестирование примитивных многочленов
  .2.1.Тестирование примитивности неприводимого многочлена
  Факторизация чисел вида $p^{n}-1$
  Оценка сложности совместного вычисления системы степеней
  Оценка сложности теста на примитивность в конечном поле малой характеристики
  .2.2.Генерация примитивных многочленов
  .2.3.Генерация примитивных элементов в поле $GF(p^n)$
 .3.Алгоритмы вычисления минимального многочлена
  .3.1.О сложности вычисления минимальных многочленов
  .3.2.Быстрый алгоритм вычисления минимального многочлена
 .4. Генерация нормальных базисов
  .4.1.Критерии базисности нормальной системы
  .4.2.Быстрое тестирование базисности нормальных систем
  .4.3.O нормальных базисах, порождаемых многочленами малого веса
4 Арифметика $GF(2^n)$ в полиномиальном базисе
 .1. Особенности реализации операций
  .1.1.Выбор поля и способов реализации
 .2.Классический алгоритм умножения в $GF(2)[X]$
  .2.1.Элементарные многочлены. Таблица умножения
  .2.2.Умножение многочленов с использованием таблицы умножения
  .2.3.Модификация классического алгоритма и гибридный алгоритм умножения
  .2.4.Еще две модификации классического алгоритма умножения
 .3.Алгоритм Карацубы и его реализация
  .3.1.О методе Карацубы
  .3.2.Умножение многочленов по методу Карацубы
  .3.3.Декомпозиционная схема умножения многочленов над $GF(2)$
  Умножение "длинных целых чисел"
  .3.4.Умножение многочленов
 .4.Приведение по модулю неприводимого многочлена
  .4.1.Классический алгоритм деления многочленов
  .4.2.Приведение многочлена по модулю многочлена малого веса
  .4.3.Обобщение алгоритма
  .4.4.Приведение по модулю многочлена высокого веса
  Приведение по модулю многочлена максимального веса 
  Приведение по модулю многочлена степени $n$ и веса $n$
 .5.Возведение в степень и инвертирование
  .5.1.Возведение в степень $2^m$ в стандартном базисе
  .5.2.Инвертирование в полиномиальном или нормальном базисах
  .5.3.Быстрый алгоритм возведения в степень в стандартном базисе
  .5.4.Быстрое инвертирование в стандартном базисе поля $GF(p^n)$
  .5.5.Быстрое программное инвертирование на основе алгоритма Евклида
  Инверсный алгоритм
  Почти инверсный алгоритм
  .5.6.Деление с помощью алгоритма Евклида
 .6.Асимптотически быстрые алгоритмы
  .6.1.Быстрое умножение чисел и многочленов
  .6.2.Аддитивные цепочки
  .6.3.Приложения аддитивных цепочек
  Аддитивные цепочки с нулевым весом удвоений
  .6.4.Аддитивные цепочки с вычитаниями
  .6.5.Алгоритмы возведения в степень с фиксированной базой
  .6.6.Ускорение проверки электронной подписи
  .6.7.Метод Монтгомери быстрого возведения в степень
  .6.8.Пример реализации метода Монтгомери логическими схемами
  .6.9.Быстрое возведения в степень через модулярную композицию
  .6.10.Быстрое инвертирование в стандартном базисе через модулярную композицию
  .6.11.Некоторые уточнения в случае $q=2$
5 Арифметика в нормальных базисах
 .1.Оптимальные нормальные базисы
  .1.1.Три типа оптимальных нормальных базисов
  .1.2.Некоторые примеры примитивных элементов по модулю $p$
  .1.3.Алгоритм генерации оптимальных нормальных базисов первого типа и доказательство их оптимальности
  Доказательство оптимальности базисов первого типа
  Вычисление матрицы $T$
  .1.4.Алгоритм генерации оптимальных нормальных базисов второго типа и доказательство их оптимальности
  Доказательство оптимальности
  Свойства матрицы $T$
  .1.5.Алгоритм генерации оптимальных нормальных базисов третьего типа и доказательство их оптимальности
  Доказательство оптимальности
  Вычисление матрицы $T$
 .2.Оптимизация преобразований базисов
  .2.1.О комбинированном использовании полиномиального и нормального базисов
  .2.2.Пример выполнения алгоритма перехода от оптимального базиса первого типа к стандартному и обратно
  Переход от оптимального нормального базиса первого типа поля $GF(2^4)$ к стандартному
  Переход от стандартного базиса поля $GF(2^4)$ к оптимальному нормального базису -го типа
  .2.3.Примеры построения логических схем для умножения в стандартном и оптимальном нормальном базисе первого типа
  .2.4.Оценка сложности перехода от оптимальных нормальных базисов второго и третьего типа к стандартным и обратно
  .2.5.О явном вычислении формул перехода и минимальных многочленов для оптимальных нормальных базисов
  .2.6.Оценка сложности перехода от оптимальных нормальных базисов второго и третьего типа к стандартным в общем случае
  .2.7.Пример выполнения алгоритма перехода от оптимального базиса 2-го или 3-го типа к стандартному и обратно
  Переход от оптимального нормального базиса второго или третьего типа к стандартному
  Переход от стандартного базиса к оптимальному нормальному базису второго или третьего типа
  .2.8.Замечание о программной реализации
  .2.9.О сложности арифметических операций в конечных полях
  .2.10.Об оценках сложности возведения в степень и инвертирования в конечных полях
 .3. Гауссовы нормальные базисы
  .3.1.Построение гауссовых нормальных базисов
  Условия существования ГНБ
  Умножение в ГНБ
  .3.2.Сложность умножения, инвертирования и возведения в степень в ГНБ
  .3.3.Гауссовы базисы и гауссовы периоды
  .3.4.Еще один вывод таблицы умножения для ГНБ
  .3.5.Примеры гауссовых нормальных базисов в полях $GF(2^n)$
  .3.6.Порядки генераторов базисов низкой сложности и быстрый алгоритм возведения в степень
  .3.7.О сложности порождения нормальных базисов, примитивных элементов и неприводимых многочленов
  .3.8.Редундантные базисы
 .4.Операции в нормальных базисах
  .4.1.Пример построения схемы для умножения и инвертирования в оптимальных нормальных базисах второго типа
  .4.2.Пример схемного инвертирования с использованием редундантного базиса
  .4.3.Пример схемы умножения в ГНБ
  .4.4.Быстрое программное инвертирование с помощью ГНБ
Литература
Предметный указатель
Уточнения и дополнения к первому изданию

 Предисловие

Настоящее второе издание публикуется параллельно со вторым изданием (М.: URSS, 2012) книги "Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых", которая является сходной по тематике. Поэтому ссылки на нее в тексте помечены как вторая книга. Во втором издании обеих книг помещен раздел "Уточнения и дополнения к первому изданию". Работа авторов над вторым изданием осуществлена при финансовой поддержке Российского фонда фундаментальных исследований, проекты N08--01--00632а и N11--01--00792а. При этом были учтены замечания наших читателей и использованы научные результаты авторов, полученные при выполнении указанных проектов.

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

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

Вторая глава посвящена теории и алгоритмическому строению конечных полей и групп точек эллиптических кривых.

Третья глава освещает вопросы тестирования и генерации неприводимых многочленов.

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

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

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

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

 Алгебраическая и криптографическая терминология согласуется с учебниками.

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

 При подготовке примеров использована библиотека алгоритмов криптографии эллиптических кривых и "визуализирующий" ее алгебраический процессор, разработанные под руководством авторов студентами МЭИ П.И.Артемьевой, В.С.Гамовым, Я.Ю.Грачевым, А.Б.Дроздовым, Ал.И.Мамонтовым и Е.В.Шестаковым при выполнении дипломных проектов и магистерских диссертаций, и другие программы, разработанные под руководством авторов студентами и аспирантами МГУ и МЭИ. Издание содержит все необходимое для создания таких библиотек и процессоров в вузах, где осуществляется подготовка по специальностям в области обеспечения информационной безопасности.

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

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

В заключение авторы выражают благодарность за замечания О.Н.Василенко и Д.В.Матюхину, прочитавшим рукопись, студентам и аспирантам МЭИ, МГУ и других вузов, заметившим ряд неточностей и осуществившим экспериментальную проверку описаний алгоритмов и числовых параметров, приведенных в книге. Также мы признательны заведующему кафедрой информационной безопасности РГСУ профессору А.В.Бабашу и доценту МГУ Э.А.Применко за поддержку.


 Об авторе

Анатолий Александрович Болотов

Кандидат физико-математических наук, сотрудник лаборатории перспективных исследований фирмы LSI Logic (США). До 2000 г. -- доцент кафедры математического моделирования МЭИ и старший научный сотрудник кафедры математической теории интеллектуальных систем МГУ.

Сергей Борисович Гашков

Доктор физико-математических наук, профессор кафедры дискретной математики МГУ.

Александр Борисович Фролов

Доктор технических наук, профессор кафедры математического моделирования МЭИ.

Анатолий Александрович Часовских

Кандидат физико-математических наук, доцент кафедры математической теории интеллектуальных систем механико-математического факультета МГУ, директор СУНЦ МГУ -- Школы им. А.Н.Колмогорова.

 
© URSS 2016.

Информация о Продавце