|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Разновидности схем электронной цифровой подписи и их применение
Существует несколько схем построения ЭП: 1. На основе алгоритмов симметричного шифрования. Данная схема предусматривает наличие в системе третьего лица — арбитра, пользующегося доверием обеих сторон. Авторизацией документа является сам факт зашифрования его секретным ключом и передача его арбитру. 2. На основе алгоритмов асимметричного шифрования. На данный момент такие схемы ЭП наиболее распространены и находят широкое применение. Кроме этого, существуют другие разновидности электронных подписей (групповая подпись, неоспоримая подпись, доверенная подпись), которые являются модификациями описанных выше схем. Их появление обусловлено разнообразием задач, решаемых с помощью ЭП.
7. Простое конечное поле. Расширенное конечное поле. Алгебраическая структура конечного поля. Минимальные многочлены. Неприводимые и примитивные многочлены над конечными полями. Мультипликативная группа конечного поля. Простое конечное поле Полем называют множество элементов, на котором определены две операции. Одна из них называется сложением и обозначается a+b, а другая – умножением и обозначается a ·b, даже если эти операции не являются обычными операциями сложения и умножения чисел. Для того, чтобы множество элементов, на котором заданы операции сложения и умножения, было полем, необходимо, чтобы по каждой из этих операций выполнялись все групповые аксиомы, а также выполнялся дистрибутивный закон, т. е. для трех любых элементов поля а, b, с были справедливы равенства а ·(b+с) = а ·b+а ·с и (b+с) ·а = b · а+с ·а. Группой G называется множество элементов, для которых определена некоторая операция * и выполняются следующие аксиомы: 1. G.1. Операция может быть применена к любым двум элементам группы, в результате чего получается третий элемент группы, т.е., если 2. G.2. Для любых трех элементов 3. G.3. В 4. G.4. Для любого элемента Аксиома G.1 определяет замкнутость операции в группе. Обычно операции над элементами записывают в виде Свойство операции, сформулированное в виде аксиомы G.2, называют ассоциативностью. Она означает, что порядок выполнения операций несущественен, и поэтому скобки не нужны. Аксиома G.3 постулирует обязательное существование единичного элемента. Для аддитивной группы единичный элемент называют нулем, обозначают 0 и определяют из уравнения Аксиома G.4 требует для каждого элемента группы существования обратного элемента. Если групповая операция – сложение, то элемент, обратный Группа называется коммутативной или абелевой, если кроме аксиом G.1 – G.5 выполняется следующая аксиома коммутативности. G.5. Для двух произвольных элементов Кроме того, по каждой операции группа должна быть коммутативной, т. е. должно выполняться а + b = b + a и а · b = b · а. Следует заметить, что групповые свойства по операции умножения справедливы для всех ненулевых элементов поля. Конечным полем GF называется конечное множество элементов, замкнутое по отношению к двум заданным в нем операциям комбинирования элементов. Под замкнутостью понимается тот факт, что результаты операций не выходят за пределы конечного множества введенных элементов. Для конечных полей выполняются следующие аксиомы. 1. GF.1. Из введенных операций над элементами поля одна называется сложением и обозначается как 2. GF.2. Для любого элемента 3. GF.3. Поле всегда содержит мультипликативную единицу 1 и аддитивную единицу 0, такие что 4. GF.4. Для введенных операций выполняются обычные правила ассоциативности 5. GF.5. Результатом сложения или умножения двух элементов поля является третий элемент из того же конечного множества. Поля с конечным числом элементов q называют полями Галуа и обозначают GF(q). Число элементов поля q называют порядком поля. Конечные поля используются для построения большинства известных кодов и их декодирования. В зависимости от значения q различают простые или расширенные поля. Поле называют простым, если q – простое число. Для обозначения простых чисел будем использовать символ p. Простое поле образуют числа по модулю p: 0, 1, 2, …, p–1, а операции сложения и умножения выполняются по модулю p. Наименьшее число элементов, образующих поле, равно 2. Такое поле должно содержать 2 единичных элемента: 0 относительно операции сложения и 1 относительно операции умножения. Это поле GF(2), или двоичное. Правила сложения и умножений для элементов GF(2)приводятся рис. П1.1.
GF(3) –троичное поле с элементами 0, 1, 2. Для него правила сложения и умножения приводятся на рис. П1.2.
Изучим возможность построения полей с элементами в виде последовательностей чисел. Определим условия, при которых последовательности длины m с элементами из поля GF(p) образуют поле. Рассмотрим последовательности длины 4 с элементами из GF(2). Такие последовательности можно складывать как векторы, и нулевым элементом по операции сложения является 0000. Для задания операции умножения сопоставим каждой последовательности многочлен от
Умножение таких многочленов может дать степень, большую чем 3, т. е. последовательность, не принадлежащую рассматриваемому множеству. Например, (1101) · (1001) Π (α ) = 1+α +α 4 = 0, или α 4 = 1+α. Тогда α 5 =α +α 2, α 6 =α 2+α 3; 1+α +α 4+α 6 = 1+α +1+α +α 2+α 3 = α 2+α 3. Это эквивалентно делению на многочлен 1+α +α 4 и нахождению остатка от деления:
Таким образом, имеет место аналогия при формировании поля из чисел и последовательностей чисел (многочленов). Эта аналогия распространяется и на то, что для обратимости введенной операции умножения (чтобы система элементов в виде последовательностей длины m или многочленов степени меньшей m, образовывала поле) многочлен Π (α ) должен быть неприводим над полем своих коэффициентов. Поле, образованное многочленами над полем GF(р) по модулю неприводимого многочлена p(x) степени m, называется расширением поля степени m над GF(p) или расширенным полем. Оно содержит pm элементов и обозначается GF(pm). Поле, образованное шестнадцатью двоичными последовательностями длины 4, или многочленами степени 3 и менее с коэффициентами из GF(2) по модулю многочлена x4+ x+1, неприводимого над GF(2), является примером расширенного поля GF(24), которое может быть обозначено также GF(16) Важнейшим свойством конечных полей является следующее. Множество всех ненулевых элементов конечного поля образует группу по операции умножения, т. е. мультипликативную группу порядка q–1. Рассмотрим совокупность элементов мультипликативной группы, образованную некоторым элементом a и всеми его степенями α 2, α 3 и т. д. Так как группа конечна, должно появиться повторение, т. е. α i = α j. Умножая это равенство на (α i)–1 = (α –1)i, получим 1 = α j-i. Следовательно, некоторая степень α равна 1. Наименьшее положительное число e, такое, что α e= 1, называется порядком элемента α. Совокупность элементов 1, α, α 2, …, α e–1 образует подгруппу, поскольку произведение любых двух элементов принадлежит этой совокупности, а элемент, обратный α j, равен α e–j и тоже входит в эту совокупность. Группа, которая состоит из всех степеней одного из ее элементов, называется циклической группой. Из рассмотренного свойства конечных полей вытекают два важных следствия. Первое из них утверждает, что многочлен xq–1–1 имеет своими корнями все q–1 ненулевых элементов поля GF(q), т. е.
В поле GF(q) элемент a, имеющий порядок e = q–1, называется примитивным. Отсюда следует, что любой ненулевой элемент GF(q) является степенью примитивного элемента. Второе следствие из рассмотренного свойства утверждает, что любое конечное поле GF(q) содержит примитивный элемент, т. е. мультипликативная группа GF(q) является циклической. Мультипликативная группа любого конечного поля является циклической (она порождается элементом поля наибольшего порядка). В табл. П.1.1 представлены различными способами элементы GF(24). Таблица П.1.1
Поле GF(24), представленное в табл. П.1.1, построено по модулю x4+x+1. Примитивный элемент поля a является корнем этого многочлена. Многочлен, корнем которого является примитивный элемент, называется примитивным многочленом. Если в качестве Π (x) выбрать примитивный неприводимый многочлен степени m над полем GF(2), то получим полеGF(2m) из всех 2m двоичных последовательностей длины m. Выше было показано, что GF(4) нельзя представить в виде совокупности чисел 0, 1, 2, 3. · Характеристика поля всегда 0 или простое число (n•1=0, n – хар-ка) o Поле характеристики 0 содержит Q, поле рациональных чисел. o Поле характеристики p содержит Zp, поле вычетов по модулю p. · Количество элементов в конечном поле всегда равно pn, степени простого числа. o При этом для любого числа вида pn существует единственное (с точностью до изоморфизма) поле из pn элементов, обычно обозначаемое Fpn. · Любой ненулевой гомоморфизм полей является вложением. Примеры поля: множества рациональных, вещественных, комплексных чисел. Конечное поле или поле Галуа — поле, состоящее из конечного числа элементов. Обычно обозначается GF(p), где p — число элементов поля. Простое поле Галуа GF(p) = {S, ⊕ , ⊗ } с бинарными операциями ⊕, ⊗. Пусть надо построить поле GF(9) = GF(32). Для этого необходимо найти многочлен степени 2, неприводимый в Z3. Такими многочленами являются:
Возьмем, например, Таблица сложения в GF(9)
Таблица умножения в GF(9)
Расширенное поле Галуа GF (pn) с бинарными операциями ⊕ , ⊗ по mod p, mod(M(x): deg(M(x)) = n) Элементами расширенного поля Галуа являются многочлены, коэффициенты которых являются элементами простого поля Галуа (элементы - числа). Для выполнения операций в конечном поле Галуа степени n необходимо использовать приведение по двойному модулю (moddp, f(x)). Для произведения операций над полем нужно задаться конкретным видом неприводимого многочлена, так как в зависимости от многочлена результаты умножения 2 элементов поля будут разными. Неприводимый многочлен — многочлен, неразложимый на нетривиальные (неконстантные) многочлены. В кольце многочленов неприводимые многочлены играют роль сходную с простыми числами в кольце целых чисел. Многочленом f(x) над конечным полем GF(q) степени m > = 0 называется сумма следующего вида Полином является неприводимым над полем GF(q), если он среди своих делителей не имеет других полиномов. Число неприводимых полиномов степени n для поля GF(p)
µ(a) – функцияМебиуса µ(a) = 1, a = 1 0, ki> = 2 -1, число сомножителей нечетное 1, число сомножителей четное Популярное:
|
Последнее изменение этой страницы: 2016-04-11; Просмотров: 933; Нарушение авторского права страницы
и 
, то 
.
, 
и 
из 
.
существует единичный элемент 
, т.е. такой, что 
для любого 
существует обратный элемент 
такой, что 
.
и называют сложением или в виде 
и называют умножением, даже если они не являются обычными сложением и умножением. В соответствии с двумя записями операций различают аддитивную и мультипликативную группы.
. Для мультипликативной группы единичный элемент называют единицей и определяют из уравнения 
.
, обозначается 
и находится из уравнения 
. Для мультипликативной группы обратный к 
и находится из уравнения 
.
из 
справедливо 
.
, а другая - умножением и обозначается как 
.
и обратный элемент по умножению 
(если 
) такие, что 
и 
. Наличие обратных элементов позволяет наряду с операциями сложения и умножения выполнять также вычитание и деление: 
, 
. Поэтому иногда просто говорят, что в поле определены все четыре арифметические операции (кроме деления на 0).
, и 
для любого элемента поля.
, 
, коммутативности 
, 
и дистрибутивности 
.
: 
(1+α +α 3) · (1+α 3) = 1+α +α 4+α 6. Для того чтобы свести ответ к многочлену степени не более 3, положим, что α удовлетворяет уравнению степени 4, например, 
; 
; 
; 
; 
; 
; 
; 
; 
; 