Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
4.10. Для положительного целого числа п величина \п\ = \og2n представляет собой оценку его длины, т.е. количества битов в двоичном представлении числа п. Однако в большинстве случаев размер числа п можно записать в виде log п (т.е. по основанию натурального логарифма). Покажите, что для любого основания Ъ > 1 величина logj, п правильно оценивает размер числа п, т.е. выражение "полиномиальный размер числа п" остается инвариантным для любого основания Ъ > 1.
4.11. Иногда положительное число записывают в унарном виде, т.е. число п представляют в виде 1". Зачем это нужно?
4.12. Что такое эффективный алгоритм? Что такое практически эффективный алгоритм?
4.13. Докажите корректность алгоритма 4.8, используя свойства функции Эйлера (}>(N) (см. раздел 6.3).
4.14. Приведите два примера неразличимых ансамблей.
4.15. Почему криптосистема, основанная на решении NP-полной задачи, не обязательно является стойкой?
4.16. Дайте определения и раскройте взаимосвязи между следующими понятиями.
а) Вычислимость по Тьюрингу.
б) Трудноразрешимая задача.
в) Разрешимая задача.
г) Детерминированное полиномиальное время.
д) Практическая эффективность.
Глава 5
Алгебраические основы
5.1 Введение
Криптографические алгоритмы и протоколы обрабатывают сообщения в виде чисел или элементов конечного пространства. При этом операции кодирования (шифрования) и декодирования (расшифровки), переводящие сообщения из одного вида в другой, должны обладать свойством замкнутости в конечном пространстве (closure property). Однако обычные арифметические операции над числами — сложение, вычитание, умножение и деление — не обладают этим свойством. По этой причине криптографические алгоритмы, действующие в конечном пространстве сообщений, как правило, не сводятся лишь к обычным арифметическим операциям над числами. Как правило, они работают в пространствах, обладающих определенной алгебраической структурой и обеспечивающих реализацию свойства замкнутости.
В главе рассматриваются три алгебраические структуры, которые не только представляют собой основные понятия абстрактной алгебры, но и являются фундаментом современной криптографии и криптографических протоколов. К этим структурам относятся группа, кольцо и поле.
5.1.1 Структурная схема главы
В разделе 5.2 изучаются группы, в разделе 5.3 — кольца и поля, а в разделе 5.4 — структура конечных полей. В заключение, в разделе 5.5 рассматривается реализация конечной группы с помощью точек на эллиптической кривой.
5.2 Группы
Кратко говоря, группа — это множество, для каждой пары элементов которого определена некая операция. Эта структура вполне естественна. Например, в старину каждый вечер пастухи должны были пересчитывать свое стадо овец. Несмотря на то что пастух мог не знать арифметики, он обязан был выполнить определенную операцию. Он выбирал камешки из мешка и каждому камешку ставил
176
Часть II. Математические основы
в соответствие отдельную овцу. Если количество камешков совпадало с количеством овец, пастух спокойно отправлялся спать. Пастух, не зная этого, генерировал группу, используя операцию "добавить единицу". При этом вид объектов, используемых для сопоставления, не имел никакого значения: главное — чтобы была определена операция над множеством объектов, и результат этой операции оставался внутри множества.
Определение 5.1 (Группа). Группой (G, о) называется пара, состоящая из множества G и операции о, удовлетворяющей следующим условиям.
1. Va, bEGzaobEG (аксиома замкнутости).
2. Va, b,cEG : а о (6 о с) = (а о 6) о с (аксиома ассоциативности).
3. Э единственный элемент еЕ G :Va Е G : ао е = ео а = а
(аксиома тождества). Элемент е называется нейтральным (identity element).
4. Va Е G : За-1 Е G : а о а-1 = а-1 о а = е (аксиома инверсии).
В обозначении группы (G, о) операция о часто пропускается, а группа обозначается символом G.
Определение 5.2 (Конечные и бесконечные группы). Группа G называется конечной, если множество G состоит из конечного количества элементов, в противном случае группа G называется бесконечной.
Определение 5.3 (Абелева группа). Группа G называется абелевой, если для любых a, bEG.aob=boa.
Иначе говоря, абелева группа является коммутативной (commutative). В книге не рассматриваются некоммутативные группы, поэтому мы часто будем опускать прилагательное "абелева".
Пример 5.1 (Группы).
1. Множество целых чисел Z является группой относительно операции +, т.е. пара (Z, +) — это группа, где е = 0 и аГ1 = —а. Эта группа является аддитивной (additive), бесконечной и абелевой. Множество рациональных чисел Q, множество действительных чисел R и множество комплексных чисел С также являются аддитивными и бесконечными группами, в которых нейтральный и обратный элементы определены по тем же правилам.
2. Ненулевые элементы множеств Q, R и С по отношению к умножению • являются группами, в которых е = 1 и а-1 является мультипликативной инверсией, определенной по обычным правилам. Обозначим эти группы через
Глава 5. Алгебраические основы
177
Q*, R* и С* соответственно. Итак, полные обозначения этих групп выглядят следующим образом: (Q*,-)> (К*,-) и (С*,-). Эти группы называются мультипликативными (multiplicative) и они бесконечны.
