Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Иногда нет необходимости различать группы, кольца и поля. В этих ситуациях они называются алгебраическими структурами (algebraic structure).
Понятия конечной группы, подгруппы, фактор-группы и порядка группы легко распространяются на кольца и поля.
Определение 5.14. Алгебраическая структура называется конечной, если она* состоит из конечного количества элементов. Количество элементов конечном структуры называется ее порядком.
Подструктурой алгебраической структуры А называется непустое подмножество S, которое само является алгебраической структурой относительно операций, определенных в структуре А Если S ф А, то подструктура S называется собственной подструктурой структуры А.
Пусть А — алгебраическая структура, а В С А — подструктура структуры А. Фактор-структурой А по модулю В, обозначаемой А/В, называется множество всех смежных классов а о В, где элемент а пробегает по всей структуре А, относительно операции *, определенной по правилу [ао В) * (bo В) — (аоЬ) о В, с нейтральными элементами О о В и 1 о В.
Из определения 5.14 следует, что кольцо (соответственно поле) может содержать не только подкольцо (соответственно подполе), но и подгруппу (соответственно подкольцо и подгруппу). Соответствующие примеры будут приведены в разделе 5.4.
5.4 Структура конечных полей
Конечные поля широко применяются в криптографии и криптографических протоколах. В частности, основополагающая работа Диффи (Dime) и Хеллмана (Hellman) по криптографии с открытым ключом, в которой был предложен протокол обмена ключами Диффи-Хеллмана [98] (раздел 8.3), была посвящена конечным полям конкретного вида. С тех пор появилось много криптосистем и прото-
Глава 5. Алгебраические основы
191
колов, основанных на применении конечных полей: криптосистемы Эль-Гамаля (ElGamal) [102], протокол идентификации и схема цифровой подписи Шнорра (Schnorr) [257], алгоритм неоспоримых подписей Чаума (Chaum) и протоколы доказательства знания с нулевым разглашением Чаума и Педерсена (Pedersen) [73] и другие. Некоторые современные криптосистемы, такие как современный стандарт шифрования данных (Advanced Encryption Standard) [219] (раздел 7.7) и криптосистема XTR [175], используют конечные поля, имеющие более общий вид. Кроме того, конечные поля лежат в основе эллиптических кривых, которые в свою очередь образуют фундамент целого класса криптосистем [166].
5.4.1 Конечные поля, содержащие простое число элементов
Наиболее простую структуру имеют конечные поля, порядок которых (т.е. количество элементов) является простым числом. Такие поля получили наиболее широкое применение в криптографии.
Определение 5.15 (Простое поле). Поле, не содержащее собственного подполя, называется простым.
Например, поле Q — простое, а множество R — нет, поскольку множество Q является собственным подполем поля R. Однако поле Q является бесконечным. Как мы вскоре убедимся, конечное простое поле содержит простое число элементов, т.е. его порядок является простым числом.
Определение 5.16 (Гомоморфизм и изоморфизм). Пусть А и В — алгебраические структуры. Отображение f : At-* В называется гомоморфизмом из структуры А в структуру В, если отображение f сохраняет операции, определенные в структуре А. Иначе говоря, если о — операция, определенная в структуре А, а * — операция, определенная в структуре В, то \/х, у € Af(x о у) = f(x) * f(y). Взаимно-однозначный гомеоморфизм f из структуры А на структур В называется изоморфизмом, а структуры А и В — изоморфными.
Если f : At-* В является гомоморфизмом, а е — нейтральный элемент структуры А (относительно сложения или умножения), то
/(е)*/(е) = /(еое) = /(е).
Следовательно, элемент /(е) является нейтральным элементом структуры В. Кроме того, для любого аЕ А
f(a)*f(a-1) = f(aoa-1) = f(e),
192 Часть II. Математические основы
поэтому /(а-1) = /(а)-1 для всех а € А. Более того, если структуры Л и Я являются изоморфными, они содержат одинаковое количество элементов. Таким образом, две изоморфные структуры устроены одинаково.
Пример 5.13 (Изоморфные алгебраические структуры).
1. Обозначим через F2 множество {0,1} с операциями + и ¦ целочисленного| сложения по модулю 2 и целочисленного умножения соответственно. Струк^ тура F2 является полем, поскольку оно изоморфно полю В, определенном]! в примере 5.12.2. Легко проверить, что отображение /(0) = F, /(1) = 21 является изоморфизмом.
2. Для любого простого числа р аддитивная группа Zp_i изоморфна мульти^ пликативной группе Z*. Легко проверить, что функция /(х) = gx(modp) является изоморфизмом между этими двумя множествами. ?
Очевидно, все поля, состоящие из двух элементов, изоморфны друг другу' и полю F2. Поле, состоящее из двух элементов, является простейшим: в нем еств! нуль и единица и больше ничего. Благодаря изоморфизму можно не различать эти поля и рассматривать поле F2 в качестве единственного поля порядка 2.
Пример 5.14 (Конечное поле простого порядка). Пусть р — произвольное проч стое число. Тогда множество Zp, состоящее из целых чисел по модулю р, является конечным полем порядка р (т.е. состоит из р элементов) относительно сложение и умножения по модулю р. В примере 5.11.2 показано, что множество Zp является, аддитивным кольцом, а в примере 5.1.5 — что множество ненулевых элементов) множества Zp, обозначаемое как Z*, образует мультипликативную группу. ?
