Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Вычислительная неразрешимость задачи ECDLP над относительно малым полем означает, что группы точек эллиптической кривой весьма удобны для реализации более эффективных криптографических систем с открытым ключом. Часто криптография с открытым ключом называется асимметричной. Это означает, что
Глава 5. Алгебраические основы
213
шифрование открытым ключом выполняется легко, а расшифровка без правильного секретного ключа представляет собой трудную задачу. Итак, можно сказать, что криптография с открытым ключом, основанная на группе точек эллиптической кривой, является более асимметричной, чем криптография, основанная на конечных полях.
Однако следует предупредить читателей, что эллиптические кривые имеют слабые места. В этих ситуациях размер поля, равный 2160, слишком мал. Как ни странно, этот факт может иметь положительные последствия (см. главу 13).
5.6 Резюме
Мы рассмотрели абстрактные алгебраические структуры — группу, кольцо и поле, а также конечные варианты арифметических операций. Например, мы показали, что для любого положительного числа п все неотрицательные целые числа, содержащие менее п двоичных цифр, образуют конечное поле, состоящее из 2П элементов, т.е. структуру, замкнутую относительно сложения и умножения (а значит, и относительно всех других алгебраических операций — возведения в степень, извлечения корня и тому подобного, поскольку все они являются производными от основных операций — сложения и умножения). Алгебраические структуры, обладающие свойством замкнутости в конечных пространствах, являются основными строительными блоками при создании криптографических алгоритмов и протоколов.
Эта глава является не только самодостаточным справочником для большинства читателей, но и содержит большое количество примеров, позволяющих глубже освоить математические основы криптографии. Более подробное изложение тем абстрактной алгебры содержится в работе [177], а эллиптические кривые описаны в книге [272].
Упражнения
5.1. В примере 5.2.5 показано, что группа Fermat(n) является подгруппой группы Ъп. Докажите, что если п — нечетное составное целое число, то #Fermat(n) < #Z*/2. Покажите, что это неравенство можно использовать в качестве рабочей основы алгоритма 4.5 для вероятностной проверки простоты числа.
5.2. Докажите, что DIV3 = {0} U 3N (множество DIV3 определено в разделе 4.3 (пример 4.1)).
5.3. Выполните следующие задания для группы 22г1: 1) укажите количество порождающих элементов; 2) перечислите все порождающие элементы; 3) найдите все подгруппы этой группы.
214
Часть II. Математические основы
5.4. Пусть п — нечетное составное число, не являющееся степенью простого числа. Существует ли в группе Z* порождающий элемент?
5.5. Примените "метод шестеренок", описанный в примере 5.10, для того, чтобы доказать, что в группе Щ5 наибольший порядок равен 12, а порядок любого элемента является делителем числа 12.
5.6. Пусть п = ро, где р и q — простые нечетные целые числа, не совпадающие друг с другом. Докажите обобщенный вариант предыдущих утверждений:
1) наибольший порядок элементов в группе Z* равен Л (n) = lcm(p—1,q— 1);
2) порядок любого элемента группы Z* является делителем числа Л(п).
5.7. Почему характеристика конечного кольца или поля должна быть простым числом?
5.8. Выполните обобщенный алгоритм Евклида для деления полиномов, используя процедуру деления столбиком.
5.9. Пусть п — произвольное натуральное число. Постройте конечное поле п-разрядных целых чисел {0,1}п. Подсказка: отобразите поле f2[a:] / в поле {0,1}п, используя отображение, описанное в примере 5.17, где / — полином степени п над полем F2.
5.10. Сколько изоморфных подполей имеет поле F236? Сколько их у поля f28?
5.11. Почему порождающий элемент группы называется первообразным корнем?
5.12. Пусть р — нечетное целое число, причем известно полное разложение числа р — 1 на простые множители. Постройте эффективный алгоритм проверки простоты числа р, который правильно распознавал бы простые числа с вероятностью 1. (Алгоритм Prime_Test(p) применять нельзя, поскольку у него вероятность правильного ответа не равна единице. Пробное деление также неприемлемо, поскольку оно неэффективно.)
5.13. Докажите, что эллиптическая кривая Е : у2 = х3 + ах + Ъ над полем Fp, где р > 3, не имеет точки порядка 2, если полином f(x) — х3+ах+Ь неприводим над полем Fp. Покажите, что в противном случае кривая Е имеет одну или три такие точки.
5.14. Проверьте аксиому ассоциативности для группы (Е,"+"), определенной в разделе 5.5.1.
5.15. Докажите, что точка (1, 2) в примере 5.20 является порождающим элементом группы.
Глава 6
Теория чисел
6.1 Введение
Разложение на простые множители и проверка простоты больших целых чисел, извлечение корня, решение систем уравнений в целых числах — вот лишь несколько задач, лежащих в основе современной криптографии. Кроме того, эти задачи представляют большой интерес с точки зрения теории чисел. В главе рассматриваются основные факты и алгоритмы теории чисел, имеющие непосредственное отношение к современной криптографии.
