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


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

Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы

URSS. 2006. 328 с. Мягкая обложка. ISBN 5-484-00443-8. Уценка. Состояние: 5-. Блок текста: 5. Обложка: 4+.

 Аннотация

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

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

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


 Анонс

Быстрые алгоритмы арифметики конечного поля

Особенности схемной и программной реализации

База перспективных криптосистем с открытым ключом и методов кодирования информации

35 алгоритмов, 60 примеров, 190 упражнений


 Оглавление

Предисловие
1 Введение
 1.1.Криптография с открытым ключом
 1.2.Группы, кольца, поля
  1.2.1.Группы
  1.2.2.Кольца. Поля. Многочлены над полем
  1.2.3.Алгоритм Евклида и его варианты
2 Конечные поля и эллиптические кривые
 2.1.Поля Галуа
  2.1.1.Характеристика поля
  2.1.2.Мультипликативная группа конечного поля
  2.1.3.Конечное расширение поля
  2.1.4.Поле разложения многочлена
  2.1.5.Минимальные многочлены. Существование неприводимых многочленов
  2.1.6.След и норма элемента конечного поля
  2.1.7.Алгоритмическое представление конечного поля
  2.1.8.Поле Галуа как векторное пространство
  2.1.9.Проверка, является ли нормальная система базисом. Переход от нормального базиса к стандартному
  2.1.10.Переход от стандартного базиса к нормальному
  2.1.11.О быстрой линейной алгебре
  2.1.12.Быстрый алгоритм для решения систем линейных уравнений над конечным полем
  2.1.13.Оптимальные и гауссовы нормальные базисы
  2.1.14.Алгебраическое замыкание конечного поля
  2.1.15.Квадратичные вычеты и извлечение квадратных корней в конечных полях
 2.2.Эллиптические кривые
  2.2.1.Алгебраические кривые и эллиптические кривые
  2.2.2.Группа точек эллиптической кривой
  2.2.3.Эллиптические кривые над полями действительных и рациональных чисел
 2.3.Эллиптические кривые над конечными полями
  2.3.1.Порядок эллиптической кривой
  2.3.2.Легко ли вычислить порядок группы точек эллиптической кривой
  2.3.3.Применения теоремы Хассе
  2.3.4.О структуре групп эллиптических кривых
3 Неприводимые многочлены
 3.1.Тестирование и поиск неприводимых многочленов
  3.1.1.Чем интересны неприводимые многочлены
  3.1.2.Тест на неприводимость. Алгоритм Берлекемпа
  3.1.3.Оценка сложности алгоритма Евклида
  3.1.4.Тестирование неприводимости многочленов
  3.1.5.О тестировании неприводимости многочленов малого веса
  3.1.6.Асимптотически быстрый алгоритм тестирования неприводимости многочленов
  3.1.7.Вероятностные алгоритмы тестирования неприводимости многочленов
  3.1.8.Генерация неприводимых многочленов
 3.2.Тестирование примитивных многочленов
  3.2.1.Тестирование примитивности неприводимого многочлена
  3.2.2.Генерация примитивных многочленов
  3.2.3.Генерация примитивных элементов в поле GF(pn)
 3.3.Алгоритмы вычисления минимального многочлена
  3.3.1.О сложности вычисления минимальных многочленов
  3.3.2.Быстрый алгоритм вычисления минимального многочлена
 3.4. Генерация нормальных базисов
  3.4.1.Критерии базисности нормальной системы
  3.4.2.Быстрое тестирование базисности нормальных систем
  3.4.3.O нормальных базисах, порождаемых многочленами малого веса
4 Арифметика GF(2n) в полиномиальном базисе
 4.1. Особенности реализации операций
  4.1.1.Выбор поля и способов реализации
 4.2.Классический алгоритм умножения в GF(2)[X]
  4.2.1.Элементарные многочлены. Таблица умножения
  4.2.2.Умножение многочленов с использованием таблицы умножения
  4.2.3.Модификация классического алгоритма и гибридный алгоритм умножения
  4.2.4.Еще две модификации классического алгоритма умножения
 4.3.Алгоритм Карацубы и его реализация
  4.3.1.О методе Карацубы
  4.3.2.Умножение многочленов по методу Карацубы
  4.3.3.Декомпозиционная схема умножения многочленов над GF(2)
  4.3.4.Умножение многочленов
 4.4.Приведение по модулю неприводимого многочлена
  4.4.1.Классический алгоритм деления многочленов
  4.4.2.Приведение многочлена по модулю многочлена малого веса
  4.4.3.Обобщение алгоритма
  4.4.4.Приведение по модулю многочлена высокого веса
 4.5.Возведение в степень и инвертирование
  4.5.1.Возведение в степень 2m в стандартном базисе
  4.5.2.Инвертирование в полиномиальном или нормальном базисах
  4.5.3.Быстрый алгоритм возведения в степень в стандартном базисе
  4.5.4.Быстрое инвертирование в стандартном базисе поля GF(pn)
  4.5.5.Быстрое программное инвертирование на основе алгоритма Евклида
  4.5.6.Деление с помощью алгоритма Евклида
 4.6.Асимптотически быстрые алгоритмы
  4.6.1.Быстрое умножение чисел и многочленов
  4.6.2.Аддитивные цепочки
  4.6.3.Приложения аддитивных цепочек
  4.6.4.Аддитивные цепочки с вычитаниями
  4.6.5.Алгоритмы возведения в степень с фиксированной базой
  4.6.6.Ускорение проверки электронной подписи
  4.6.7.Метод Монтгомери быстрого возведения в степень
  4.6.8.Пример реализации метода Монтгомери логическими схемами
  4.6.9.Быстрое возведения в степень через модулярную композицию
  4.6.10.Быстрое инвертирование в стандартном базисе через модулярную композицию
  4.6.11.Некоторые уточнения в случае q = 2
5 Арифметика в нормальных базисах
 5.1.Оптимальные нормальные базисы
  5.1.1.Три типа оптимальных нормальных базисов
  5.1.2.Некоторые примеры примитивных элементов по модулю p
  5.1.3.Алгоритм генерации оптимальных нормальных базисов первого типа и доказательство их оптимальности
  5.1.4.Алгоритм генерации оптимальных нормальных базисов второго типа и доказательство их оптимальности
  5.1.5.Алгоритм генерации оптимальных нормальных базисов третьего типа и доказательство их оптимальности
 5.2.Оптимизация преобразований базисов
  5.2.1.О комбинированном использовании полиномиального и нормального базисов
  5.2.2.Пример выполнения алгоритма перехода от оптимального базиса первого типа к стандартному и обратно
  5.2.3.Примеры построения логических схем для умножения в стандартном и оптимальном нормальном базисе первого типа
  5.2.4.Оценка сложности перехода от оптимальных нормальных базисов второго и третьего типа к стандартным и обратно
  5.2.5.О явном вычислении формул перехода и минимальных многочленов для оптимальных нормальных базисов
  5.2.6.Оценка сложности перехода от оптимальных нормальных базисов второго и третьего типа к стандартным в общем случае
  5.2.7.Пример выполнения алгоритма перехода от оптимального базиса 2-го или 3-го типа к стандартному и обратно
  5.2.8.Замечание о программной реализации
  5.2.9.О сложности арифметических операций в конечных полях
  5.2.10.Об оценках сложности возведения в степень и инвертирования в конечных полях
 5.3. Гауссовы нормальные базисы
  5.3.1.Построение гауссовых нормальных базисов
  5.3.2.Сложность умножения, инвертирования и возведения в степень в ГНБ
  5.3.3.Гауссовы базисы и гауссовы периоды
  5.3.4.Еще один вывод таблицы умножения для ГНБ
  5.3.5.Примеры гауссовых нормальных базисов в полях GF(2n)
  5.3.6.Порядки генераторов базисов низкой сложности и быстрый алгоритм возведения в степень
  5.3.7.О сложности порождения нормальных базисов, примитивных элементов и неприводимых многочленов
  5.3.8.Редундантные базисы
 5.4.Операции в нормальных базисах
  5.4.1.Пример построения схемы для умножения и инвертирования в оптимальных нормальных базисах второго типа
  5.4.2.Пример схемного инвертирования с использованием редундантного базиса
  5.4.3.Пример схемы умножения в ГНБ
  5.4.4.Быстрое программное инвертирование с помощью ГНБ
Литература
Предметный указатель

 Предисловие

Посвящается Арато Саломаа, математику, криптографу и другу

Настоящее издание публикуется параллельно с книгой "Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых" (М.: URSS, 2006) [18], которая является сходной по тематике. Поэтому ссылки на нее в тексте помечены как вторая книга.

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 Об авторах

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

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

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

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

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

Доктор технических наук, профессор кафедры математического моделирования МЭИ и профессор кафедры информационной безопасности РГСУ.

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

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


 Опечатки


Стр.61, строка снизу 17

Напечатано: ...равно сумме (дизъюнкции) элементов вектора...

Следует читать: ...равно сумме по модулю два элементов вектора

Таблица изменений в тексте


Таблица изменений в подписях к рисункам

Страница 155, строка сверху 13:

Из последовательности D(0),... все, что в верхнем индексе, опустить в нормальную строку

Страница 157, строка сверху 6:

Убрать в конце "ч" перед "суммы"

 
© URSS 2016.

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