Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
198
Часть II. Математические основы
Следствие 5.4. Для каждого простого числа р и каждого положительного числа п существует конечное поле, состоящее из рп элементов. о
Как указано в следствии 5.4, если в качестве F выбрать простое поле Fp, структура поля Fp[x]f становится очень ясной: оно представляет собой множество всех полиномов, степень которых меньше п, а коэффициенты принадлежат полю ?р. Учитывая изоморфизм, можно даже сказать, что поле ?р[х]f — это конечное поле порядка рп.
Пример 5.17 (Целочисленное представление элемента конечного поля). Полином /(х) = х8+х4+х3+х+1 является неприводимым над полем ?2. Множество всех полиномов по модулю /(х) над полем ?2 образует поле, состоящее из 28 элементов. Их степени меньше 8. Следовательно, произвольный элемент поля Р2[х] / имеет вид
bjx7 + Ь6х6 + Ьъхъ + Ь4х4 + 63х3 + 62х2 + bxx + Ьо,
где bj, be, 65,64,03, b2, b\, bo G ?2. Следовательно, любой элемент этого поля можно представить в виде целого числа, состоящего из восьми двоичных цифр ^766^5^463^2^1^0, т.е. в виде байта Используя шестнадцатеричную систему счисления, можно представить это число с помощью четырех бит.
'О' = 0000(= 0),..., '9' = 1001(= 9), 'А' = 1010(= 10),..., = 1111(= 15).
Поскольку байт состоит из восьми бит, для шестнадцатеричной кодировки байта можно использовать две буквы, заключенные в одинарные кавычки: 'XY', где '0' ^ 'X' ^ 'F' и '0' < 'У ^. Иначе говоря, любой элемент поля ?2[х]f можно представить в виде байта, лежащего в интервале ['00', 'FF'].
И наоборот, любой байт из интервала ['00', 'FF'] можно считать элементом поля F2[x]/. Например, байт 01010111 (или шестнадцатеричное число '57') соответствует полиному
х6 + х4 + x2 + x + 1. 0
Следствие 5.4 и пример 5.17 означают, что поле F2[x]f можно считать полем всех неотрицательных целых чисел, двоичная запись которых состоит из менее чем deg(/) бит. Легко видеть, что это поле содержит 2deg^ элементов. Следовательно, для любого натурального числа п > 0 множество {0,1}п образует поле, состоящее из 2п элементов. Операции в этом поле являются операциями с полиномами над полем F2, степень которых меньше п.
Пример 5.18. Пусть / — неприводимый полином степени 8 над полем ?2. В поле восьмибитовых двоичных чисел сложение полиномов сводится к сложению полиномов по модулю 2 (т.е. 1 + 1 = 0). Например, '57' + '83' = 'jD4'.
(х6 + х4 + х2 + х + 1) + (х7 + х + 1) = х7 + х6 + х4 + х2.
Итак, сложение в этом поле не зависит от определяющего полинома /. ?
Глава 5. Алгебраические основы
199
Умножение в поле Рг[ж]/ зависит от определяющего полинома /: оно представляет собой умножение двух полиномов по модулю /. Эту операцию можно выполнить, применяя к полиномам обобщенный алгоритм Евклида. Позднее (пример 5.19) мы продемонстрируем другой метод умножения, который использует иное представление элементов поля.
Поле n-битовых двоичных чисел оказалось весьма полезным, поскольку допускает естественную интерпретацию целых чисел. Оно получило широкое распространение в теории кодирования и криптографии. Новый стандарт шифрования — Advanced Encryption Standard (AES) — основан на применении именно восьмибитового двоичного поля. Этот стандарт рассматривается в главе 7.
В заключение отметим, что в теореме 5.6 мы нигде не предполагали, что число р — простое. Фактически в теореме 5.5 поле F сможет быть произвольным, а поле РгМ/ называется расширенным полем (extended field), которое получено путем расширения базового подполя F (underlying subfield). Поскольку поле F может быть любым, оно само может быть получено в результате расширения другого базового подполя. Во многих приложениях конечных полей необходимо знать взаимосвязи между расширенными и базовыми полями (например, это необходимо при изучении стандарта AES). Кроме того, иное представление элементов конечного поля иногда позволяет упростить вычисления (например, если иначе представить элементы поля в примере 5.18, операцию умножения можно упростить, не прибегая в алгоритму Евклида). В следующем разделе мы подробнее рассмотрим структуру конечных полей.
5.4.3 Конечные поля, построенные с помощью полиномиального базиса
Информация, приведенная в этом разделе, позволит лучше понять некоторые криптосистемы, использующие общее представление конечных полей. Предполагается, что читатель владеет основами линейной алгебры и знаком с понятием векторного пространства. Впрочем, этот раздел можно пропустить без ущерба для дальнейшего изложения.
В разделе 5.4.2 показано, что с учетом изоморфизма поле Fp[a;]/ можно считать конечным полем порядка pdee(/). Однако часто оказывается неудобным работать с полями по модулю неприводимых полиномов. Завершая изложение алгебраических основ криптографии, построим конечные поля, используя корни неприводимых полиномов над конечным полем F. Такие поля чаще применяются в приложениях.
Пусть F — конечное поле, an — произвольное целое число. Кроме того, пусть /(ж) — неприводимый полином степени п над полем F. Полином /(ж) имеет в некотором пространстве ровно п корней, поскольку в этом пространстве его
