Проектирование электроники, научные статьи

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

Идея арифметики остатков по существу очень проста и похожа на «арифметику часов», с которой Вы знакомитесь в детстве. «Арифметика часов» связана с пересчетом времени из 24-часовой системы в 12-часовую и обратно, ведь в сутках 24 часа, а на циферблате их всего 12. Делается это довольно просто. Чтобы перевести значение в 24-часовой системе в 12-часовую, достаточно разделить его на 12. Остаток от деления и будет искомым значением в 12-часовой системе. Например, 13:00 в 24-часовой системе — то же самое, что и один час в 12-часовой, поскольку остаток от деления 13 на 12 равен 1.

Сложение и умножение по модулю N работают почти так же, как арифметические операции над вещественными и целыми числами. В частности, они обладают следующими свойствами.

1. Замкнутость сложения:

2. Ассоциативность сложения:

Одна из центральных задач арифметики остатков — это решение уравнения

а • х = b (mod N),

т. е. поиск элементаудовлетворяющего этому равенству.

Линейное уравнение ах = b с вещественными коэффициентами при всегда разрешимо. Если же рассматривать его над кольцом целых чисел, то ответ найдется не всегда. Например, не существует целого числа x, обращающего уравнение 2х = 5 в верное равенство. Случай же кольца вычетов еще более сложный, а потому и интересный с любой точки зрения. Действительно, существует ровно одно решение уравнения

Решая уравнение вида

ах = b (mod N),

мы приходим к вопросу о существовании мультипликативного обратного у числа а по модулю N. Иначе говоря, необходимо выяснить, существует ли число с, удовлетворяющее равенству

Целые числа по простому модулю — не единственный пример конечных полей. Здесь мы разберем еще один, более общий, тип конечных полей, представляющий интерес для криптографии. Упомянутый общий тип полей будет использоваться лишь при обсуждении блочного шифра Rijndael, поточного шифра, основывающегося на регистре сдвига с обратными связями, и при изучении криптосистем, связанных с эллиптической кривой. Поэтому при первом чтении этот параграф можно пропустить.

1. 1.3. Основные алгоритмы
2. 1.3.1. Наибольший общий делитель
3. 1.3.1.1. Алгоритм Евклида.
4. 1.3.1.2. Расширенный алгоритм Евклида.
5. 1.3.2. Китайская теорема об остатках
6. 1.3.3. Символы Лежандра и Якоби
7. 1.4. Вероятность
8. 1.4.1. Теорема Байеса
9. 1.4.2. Парадокс дней рождения
10. Эллиптические кривые
11. 2.2. Групповой закон
12. 2.3. Эллиптические кривые над конечными полями
13. 2.3.1. Кривые над полем характеристики р > 3
14. 2.3.2. Кривые над полем характеристики 2
15. 2.4. Проективные координаты
16. 2.4.1. Большая характеристика
17. 2.4.2. Четная характеристика
18. 2.5. Сжатие точек
19. 2.5.1. Случай большой характеристики поля
20. 2.5.2. Четная характеристика
21. Краткое содержание главы
22. Дополнительная литература
23. Контрольные вопросы
24. Симметричное шифрование
25. 3.2. Шифр сдвига
26. 3.4. Шифр Виженера
27. 3.5. Перестановочные шифры
28. 3.7. Роторные машины и «Энигма»
29. Теоретико-информационная стойкость
30. 4.2. Вероятность и шифры
31. 4.2.1. Модифицированный шифр сдвига
32. 4.2.2. Шифр Вернама
33. 4.3. Энтропия
34. 4.4. Ложные ключи и расстояние единственности
35. 5.1.1. Упрощенная модель
36. 5.1.2. Поточные шифры
37. 5.1.3. Блочные шифры
38. 5.2. Шифр Фейстеля и DES
39. 5.2.1. Обзор действия шифра DES
40. 5.2.1.1. Начальная перестановка, IP.
41. 5.2.1.2. Перестановка с расширением Е.
42. 5.2.1.3. Перестановка в Р-блоке, Р.
43. 5.2.2. Разворачивание ключа в DES
44. 5.3. Rijndael
45. 5.3.1. Операции алгоритма Rijndael
46. 5.3.1.2. ShiftRows.
47. 5.3.1.3. MixColumns.
48. 5.3.1.4. AddRoundKey.
49. 5.3.2. Структура раундов
50. 5.3.3. Разворачивание ключа