Следующие лекции посвящены обсуждению современных симметрично-ключевых n -битовыми словами. Понимание и анализ этих шифров требуют некоторого знания разделов современной алгебры, называемых алгебраическими структурами. В начале этой лекции делается обзор алгебраических структур, а затем показывается, как выполнить сложение или умножение c n -битовыми словами.
В лекциях 2-3 мы обсуждали некоторые множества чисел, таких как Z, Zn, Zn*, Zp^ и Zp*. Криптография требует, чтобы были заданы множества целых чисел, и операции, определенные для них. Комбинация множеств и операций, которые могут быть применены к элементам множества, называются алгебраической структурой. В этой лекции мы определим три общих алгебраических структуры: группы, кольца и поля ( рис. 5.1).
(рис 5.1) Общие алгебраические структуры Группа ( G ) — набор элементов с "•" обладает четырьмя свойствами (или удовлетворяет
Коммутативная группа, также называемая абелева, — группа, в которой оператор обладает теми же четырьмя свойствами для групп плюс дополнительным — коммутативностью. Эти пять свойств определены ниже
a и b — элементы G, то c = a • b — также элемент G.
Это означает, что результат применения операции с любыми двумя элементами множества есть элемент этого множества.a, b и c — элементы G, то верно (a• b) • c = a• (b •c)
Другими словами, не имеет значения, в каком порядке мы применяем операцию более чем с двумя элементами.a и b в G мы имеем a • b = b • a. Обратите внимание, что это свойство должно быть верно только для коммутативной группы.G существует элемент e, который называется нейтральным элементом, такой, что e • a = a • e = a.a в G существует элемент a', называемый инверсией, такой, что a • a' = a' • a = e.Рисунок 5.2 иллюстрирует понятие группы.
Хотя группа включает единственный оператор, свойства, присущие каждой операции, позволяют использование пары операций, если они — инверсии друг друга. Например, если определенный выше оператор — сложение, то группа поддерживает и сложение, и вычитание, ибо вычитание и сложение — аддитивно инверсные операции. Это также верно для умножения и деления. Однако группа может поддержать только сложение/вычитание или умножение/деление, но не оба сочетания операторов одновременно.
(рис 5.2) Группа Пример 5.1
Множество целых чисел, входящих в вычет с оператором сложения, G = <Zn, +>, является коммутативной группой. Мы можем выполнить сложение и вычитание на элементах этого множества, не выходя за его пределы.
Проверим эти свойства.
Zn — другое целое число в Zn.4 + (3 + 2) тот же самый, что в случае (4 + 3) + 2.3 + 5 = 5 + 3.0. Мы имеем 3 + 0 = 0 + 3 = 3.3 — это –3 ( n – 3 в Zn ), и –3 — это 3. Пример 5.2
Множество Zn* с оператором умножения G = <Zn*, >, является также абелевой группой. Мы можем выполнить умножение и деление на элементах этого множества, не выходя за его пределы. Это облегчает проверку первых трех свойств. Нейтральный элемент равен 1. Каждый элемент имеет
Пример 5.3
Хотя мы обычно представляем группу как множество чисел с обычными операторами, такими, как сложение или вычитание, определения группы позволяют нам определять любое множество объектов и операций, которые удовлетворяют вышеупомянутым свойствам. Определим множество G = <{a, b, c, d,}, •> и операцию, показанную с помощью таблицы 5.1.
| a | b | c | d | |
|---|---|---|---|---|
| a | a | b | c | d |
| b | b | c | d | a |
| c | c | d | a | b |
| d | d | a | b | c |
Это — абелева группа. Все пять свойств удовлетворены.
(a+ b) + c = a+ (b + c) = d.a + b = b + a.a.(a, a), (b, d), (c, c).Пример 5.4
В группе элементы в множестве не обязательно должны быть числами или объектами; они могут быть правилами, отображениями, функциями или действиями. Очень интересная группа — группа подстановок. Множество всех перестановок и оператор является композицией: применения одной перестановки за другой. Рисунок 5.3 показывает композиции двух перестановок, которые перемещают три входных сигнала, чтобы создать три выходных сигнала.
(рис 5.3) Композиции перестановок (Пример 5.4)Входные сигналы и выходные сигналы могут быть символами (лекции 2-3) или битами. Мы изобразили каждую перестановку прямоугольником, внутри которого показано, где исходящий входной сигнал и индекс ( 1,2,3 ) определяет выходной сигнал. Композиция состоит из двух перестановок одна за другой. При трех входных сигналах и трех выходных сигналах может быть 3! или 6 различных перестановок. Таблица 5.2 дает определение этого оператора. Первая строка — первая перестановка; первый столбец — вторая перестановка. Результат содержится на пересечении.
В этом случае удовлетворены только четыре свойства; поэтому группа — не абелева.
[1 2 3] (перестановка отсутствует). Эти элементы показаны другим цветом.| [1 2 3] | [1 3 2] | [2 1 3] | [2 3 1] | [3 1 2] | [3 2 1] | |
|---|---|---|---|---|---|---|
| [1 2 3] | [1 2 3] | [1 3 2] | [2 1 3] | [2 3 1] | [3 1 2] | [3 2 1] |
| [1 3 2] | [1 3 2] | [1 2 3] | [2 3 1] | [2 1 3] | [3 2 1] | [3 1 2] |
| [2 1 3] | [2 1 3] | [3 1 2] | [1 2 3] | [3 2 1] | [1 3 2] | [2 3 1] |
| [2 3 1] | [2 3 1] | [3 2 1] | [1 3 2] | [3 1 2] | [1 2 3] | [2 1 3] |
| [3 1 2] | [3 1 2] | [2 1 3] | [3 2 1] | [1 2 3] | [2 3 1] | [1 3 2] |
| [3 2 1] | [3 2 1] | [2 3 1] | [3 1 2] | [1 3 2] | [2 1 3] | [1 2 3] |
Пример 5.5
В предыдущем примере мы показали, что множество перестановок с композицией операций — группа. Поэтому использование двух перестановок (одна за другой) не могут усилить безопасность шифра. Мы сможем всегда найти перестановку, которая может сделать ту же самую операцию, используя свойства замкнутости.
Группа называется конечной группой, если множество имеет конечное число элементов; иначе это — бесконечная группа.
Порядок группы, G, — это число элементов в группе. Если группа не конечна, ее порядок бесконечен; если конечна, порядок конечен.
Подмножество H группы G — подгруппа G, если само H — группа относительно операции на G. Другими словами, если G = <S, •> — группа, то H = <T, •> — группа для той же самой операции, и T — непустое подмножество S, то H — G. Вышеупомянутое определение подразумевает, что:
a и b — члены обеих групп, то c = a • b — также элемент обеих групп;a — также элемент обеих групп;G, H = <{e}, •>, является G ;Пример 5.6
Является ли группа H = <Z10, +> G = <Z12, +>?
Решение
Ответ — нет. Хотя H — подмножество G, операции, определенные для этих двух групп, различны. Операция H — сложение по модулю 10 ; операция в G — сложение по модулю 12.
Если
Множество, полученное в результате этого процесса, обозначается в тексте как <a>. Обратите внимание также, что a0 = e.
Пример 5.7
Из группы G = < Z6, +> могут быть получены четыре циклических подгруппы. Это H1 = <{0},+>, H2 =<{0, 2, 4}, +>, H3 = <{0, 3}, +> и H4 = G. Заметим, что когда операция — сложение, то an означает умножение n на a. Заметим также, что во всех этих группах операция — это сложение по модулю 6. Ниже показано, как мы находим элементы этих циклических
a. Циклическая 0, — это H1, имеет только один элемент (нейтральный элемент).
00 mod 6 = 0 (остановка, далее процесс повторяется).
б. Циклическая 1, — это H4, которая есть сама группа G.
10 mod 6 = 0 11 mod 6 = 1 12 mod 6 = (1 + 1) mod 6 = 2 13 mod 6 = (1 + 1 + 1) mod 6 = 3 14 mod 6 = (1 + 1 + 1 + 1) mod 6 = 4 15 mod 6 = (1 + 1 + 1 + 1 + 1) mod 6 = 5(остановка, далее процесс повторяется)
в. Циклическая 2, — это H2, которая имеет три элемента: 0, 2, и 4.
20 mod 6 = 0 21 mod 6 = 2 22 mod 6 = (2 + 2) mod 6 = 4 (остановка, далее процесс повторяется)
г. Циклическая 3, — это H3, которая имеет два элемента: 0 и 3.
30 mod 6 = 0 31 mod 6 = 3 (остановка, далее процесс повторяется)
д. Циклическая 4, — H2 ; это — не новая
40 mod 6 = 0 41 mod 6 = 4 42 mod 6 = (4 + 4) mod 6 = 2 (остановка, далее процесс повторяется)
е. Циклическая 5, — это H4, она есть сама группа G.
50 mod 6 = 0 51 mod 6 = 5 52 mod 6 = 4 53 mod 6 = 3 54 mod 6 = 2 55 mod 6 = 1 (остановка, далее процесс повторяется)
Пример 5.8
Из группы $${\text{G}} = < {{\text{Z}}_{{\text{1}}0*}}, \times >$$ можно получить три циклических подгруппы. G имеет только четыре элемента: 1, 3, 7 и 9. Циклические подгруппы — $${H_1} = \<\left\{ 1 \right\}, \times \>,$$ $${H_2} = \<\left\{ {1,{\text{ }}9} \right\}, \times \>$$ и $${H_3} = G $$. Ниже показано, как мы находим элементы этих
a. Циклическая 1, — это H1.
10 mod 10 = 1 (остановка, далее процесс повторяется)
б. Циклическая 3, — это H3, которая есть группа G.
30 mod 10 = 1 31 mod 10 = 3 32 mod 10 = 9 33 mod 10 = 7 (остановка, далее процесс повторяется)
в. Циклическая 7, — это H3, которая есть группа G.
70 mod 10 = 1 71 mod 10 = 7 72 mod 10 = 9 73 mod 10 = 3 (остановка, далее процесс повторяется)
г. Циклическая 9, — это H2.
90 mod 10 = 1 91 mod 10 = 9 (остановка, далее процесс повторяется)
Циклическая группа — группа, которая является собственной циклической G имеет циклическую подгруппу H5 = G. Это означает, что группа G — циклическая группа. В этом случае элемент, который генерирует циклическую подгруппу, может также генерировать саму группу. Этот элемент далее именуется "генератор". Если g — генератор, элементы в конечной циклической группе могут быть записаны как
{e,g,g2,….., gn-1}, где gn = e.
Заметим, что циклическая группа может иметь много генераторов.
Пример 5.9
а. Группа G = <Z6, +> — циклическая группа с двумя генераторами, g = 1 и g = 5.
б. Группа $${\text{G}} = < {{\text{Z}}_{{\text{1}}0*}}, \times >$$ — циклическая группа с двумя генераторами, g = 3 и g = 7.
Теорема Лагранжа показывает отношение между порядком группы к порядку ее подгруппы. Предположим, что G — группа и H — G. Если порядок G и H — |G| и |H|, соответственно, то согласно этой теореме |H| делит |G|. В примере 5.7 |G| = 6. Порядок подгруппы — |H1| = 1, | H2| = 3, |H3| = 2 и |H4| = 6. Очевидно, все эти порядки есть делители 6.
Теорема Лагранжа имеет очень интересное приложение. Когда дана группа G и ее порядок |G|, могут быть легко определены порядки потенциальных G = <Z17, +> — это |17|. Делители 17 есть 1 и 17. Это означает, что эта группа может иметь только две подгруппы — нейтральный элемент и H2 = G.
Порядок элемента в группе ord (a) (порядок (a)) является наименьшим целым числом n, таким, что a n = e. Иными словами: порядок элемента — порядок группы, которую он генерирует.
Пример 5.10
a. В группе G = <Z6, +>, порядки элементов: порядок ord(0) = 1, порядок ord (1) = 6, порядок ord (2) = 3, порядок ord (3) = 2, порядок ord (4) = 3, порядок ord (5) = 6.
b. В группе G = <Z10, * >, порядки элементов: порядок ord (1) = 1, порядок ord (3) = 4, порядок ord (7) =4, порядок (9) = 2.
Кольцо, обозначенное как $$R = \<\left\{ {...} \right\}, ullet , \bot \>$$, является алгебраической структурой с двумя операциями. Первая операция должна удовлетворять всем пяти свойствам, требуемым для абелевой группы. Вторая операция должна удовлетворять только первым двум свойствам абелевой группы. Кроме того, вторая операция должна быть распределена с помощью первой. Дистрибутивность означает, что для всех a, b и c элементов из R мы имеем $$a \bot (b ullet c) = (a \bot b) ullet (a \bot c)$$ и $$(a ullet b) \bot c = (a \bot c) ullet (b \bot c)$$.
Кольцо включает две операции. Однако вторая операция может не соответствовать третьему и четвертому свойствам. Другими словами, первая операция — фактически операция пары операций, таких как сложение и вычитание; вторая операция может содержать единственную операцию, например умножение, но может не содержать деление.
Пример 5.11
Множество Z с двумя операциями — сложением и умножением — является коммутативным кольцом, которое обозначается $$R = \<Z, + , \times \>$$. Сложение удовлетворяет всем пяти свойствам; умножение удовлетворяет только трем свойствам.
(рис 5.4) Кольцо Умножение дистрибутивно с помощью сложения. Например, $$5 \times (3 + 2) = (5 \times 3) + (5 \times 2) = 25$$. Хотя, мы можем выполнить на этом множестве сложение и вычитание и умножение, но не деление. Деление не может применяться в этой структуре, потому что оно приводит к элементу из другого множества. Результат деления 12 на 5 есть 2,4, и он не находится в заданном множестве.
Поле, обозначенное $$F = \<\left\{ {...} \right\}, ullet , \bot \>$$ —
(рис 5.5) Поле Поле — структура, которая поддерживает две пары операций, используемые в математике: сложение/вычитание и умножение/деление. Есть одно исключение: не разрешено деление на нуль.
Хотя общее определение касается полей бесконечного порядка, в криптографии используются экстенсивно только конечные поля. Конечное поле — поле с конечным числом элементов — является очень важной структурой в криптографии. Галуа показал что поля, чтобы быть конечными, должны иметь число элементов pn, где p — простое, а n — положительное целое число. Конечные поля обычно называют полями Галуа и обозначают как GF(pn).
Когда n = 1, мы имеем поле GF (p). Это поле может быть множеством Zp,
(0, 1, …p–1) с двумя арифметическими операциями (сложение и умножение). Любой элемент в этом множестве имеет аддитивную 0 отсутствует).
Пример 5.12
Очень общее поле в этой категории — GF (2) с множеством {0,1} и двумя операциями, сложением и умножением, как показано на рисунке 5.6.
(рис 5.6) Поле GF (2) Есть несколько моментов, которые следует отметить в определении этого поля. Первый: множество имеет только два элемента, которые являются двоичными цифрами или битами ( 0 и 1 ). Второй: операция сложения — фактически ИСКЛЮЧАЮЩЕЕ ИЛИ ( XOR ), операция, которую мы используем с двумя двоичными цифрами. Третий: операция умножения — AND, операция, которую мы используем с двумя двоичными цифрами. Четвертый: сложение и операции вычитания — те же самые (операция XOR ). Пятый: умножение и операции деления — те же самые (ОПЕРАЦИЯ AND ).
Пример 5.13
Мы можем определить GF(5) на множестве Z5 ( 5 простое) с операторами сложения и умножения, показанными на рис. 5.7.
Хотя мы можем использовать расширенный алгоритм Евклида, чтобы найти мультипликативные инверсии элементов в GF(5), проще составить таблицу умножения и находить каждую пару, произведение которой равняется 1. Это (1, 1), (2, 3), (3, 2) и (4, 4). Заметим, что мы можем на этом множестве применить вычитание и умножение/деление (за исключением запрещенного деления на 0 ).
(рис 5.7) Поле GF (5)
В дополнение к полям GF(p) в криптографии мы также интересуемся полями GF(pn). Однако множества Z, Zn, Zn* и Zp, которые мы использовали до сих пор с операциями сложения и умножения, не могут удовлетворить требованиям поля. Поэтому должны быть определены некоторые новые множества и некоторые новые операции на этих множествах. В следующей лекции мы рассматриваем очень полезное в криптографии поле GF(2n).
Изучение трех алгебраических структур позволяет нам использовать множества, в которых могут применяться операции, подобные сложению/вычитанию и умножению/делению. Мы должны различать эти три структуры. Первая структура — группа, поддерживает одну пару связанных операций. Вторая структура — кольцо, поддерживает одну пару связанных операций и одну одиночную операцию. Третья структура — поле, поддерживает две пары операций. Таблица 5.3 может помочь нам увидеть эту разницу.
| Алгебраическая структура | Используемые операции | Используемые наборы целых чисел |
|---|---|---|
| Группа | (+ -) или (x /) | Zn или Zn* |
| Кольцо | (+ -) и (x) | Z |
| Поле | (+ -) и (x /) | Zp |
Следующие лекции посвящены обсуждению современных симметрично-ключевых n -битовыми словами. Понимание и анализ этих шифров требуют некоторого знания разделов современной алгебры, называемых алгебраическими структурами. В начале этой лекции делается обзор алгебраических структур, а затем показывается, как выполнить сложение или умножение c n -битовыми словами.
В лекциях 2-3 мы обсуждали некоторые множества чисел, таких как Z, Zn, Zn*, Zp^ и Zp*. Криптография требует, чтобы были заданы множества целых чисел, и операции, определенные для них. Комбинация множеств и операций, которые могут быть применены к элементам множества, называются алгебраической структурой. В этой лекции мы определим три общих алгебраических структуры: группы, кольца и поля ( рис. 5.1).
(рис 5.1) Общие алгебраические структуры Группа ( G ) — набор элементов с "•" обладает четырьмя свойствами (или удовлетворяет
Коммутативная группа, также называемая абелева, — группа, в которой оператор обладает теми же четырьмя свойствами для групп плюс дополнительным — коммутативностью. Эти пять свойств определены ниже
a и b — элементы G, то c = a • b — также элемент G.
Это означает, что результат применения операции с любыми двумя элементами множества есть элемент этого множества.a, b и c — элементы G, то верно (a• b) • c = a• (b •c)
Другими словами, не имеет значения, в каком порядке мы применяем операцию более чем с двумя элементами.a и b в G мы имеем a • b = b • a. Обратите внимание, что это свойство должно быть верно только для коммутативной группы.G существует элемент e, который называется нейтральным элементом, такой, что e • a = a • e = a.a в G существует элемент a', называемый инверсией, такой, что a • a' = a' • a = e.Рисунок 5.2 иллюстрирует понятие группы.
Хотя группа включает единственный оператор, свойства, присущие каждой операции, позволяют использование пары операций, если они — инверсии друг друга. Например, если определенный выше оператор — сложение, то группа поддерживает и сложение, и вычитание, ибо вычитание и сложение — аддитивно инверсные операции. Это также верно для умножения и деления. Однако группа может поддержать только сложение/вычитание или умножение/деление, но не оба сочетания операторов одновременно.
(рис 5.2) Группа Пример 5.1
Множество целых чисел, входящих в вычет с оператором сложения, G = <Zn, +>, является коммутативной группой. Мы можем выполнить сложение и вычитание на элементах этого множества, не выходя за его пределы.
Проверим эти свойства.
Zn — другое целое число в Zn.4 + (3 + 2) тот же самый, что в случае (4 + 3) + 2.3 + 5 = 5 + 3.0. Мы имеем 3 + 0 = 0 + 3 = 3.3 — это –3 ( n – 3 в Zn ), и –3 — это 3. Пример 5.2
Множество Zn* с оператором умножения G = <Zn*, >, является также абелевой группой. Мы можем выполнить умножение и деление на элементах этого множества, не выходя за его пределы. Это облегчает проверку первых трех свойств. Нейтральный элемент равен 1. Каждый элемент имеет
Пример 5.3
Хотя мы обычно представляем группу как множество чисел с обычными операторами, такими, как сложение или вычитание, определения группы позволяют нам определять любое множество объектов и операций, которые удовлетворяют вышеупомянутым свойствам. Определим множество G = <{a, b, c, d,}, •> и операцию, показанную с помощью таблицы 5.1.
| a | b | c | d | |
|---|---|---|---|---|
| a | a | b | c | d |
| b | b | c | d | a |
| c | c | d | a | b |
| d | d | a | b | c |
Это — абелева группа. Все пять свойств удовлетворены.
(a+ b) + c = a+ (b + c) = d.a + b = b + a.a.(a, a), (b, d), (c, c).Пример 5.4
В группе элементы в множестве не обязательно должны быть числами или объектами; они могут быть правилами, отображениями, функциями или действиями. Очень интересная группа — группа подстановок. Множество всех перестановок и оператор является композицией: применения одной перестановки за другой. Рисунок 5.3 показывает композиции двух перестановок, которые перемещают три входных сигнала, чтобы создать три выходных сигнала.
(рис 5.3) Композиции перестановок (Пример 5.4)Входные сигналы и выходные сигналы могут быть символами (лекции 2-3) или битами. Мы изобразили каждую перестановку прямоугольником, внутри которого показано, где исходящий входной сигнал и индекс ( 1,2,3 ) определяет выходной сигнал. Композиция состоит из двух перестановок одна за другой. При трех входных сигналах и трех выходных сигналах может быть 3! или 6 различных перестановок. Таблица 5.2 дает определение этого оператора. Первая строка — первая перестановка; первый столбец — вторая перестановка. Результат содержится на пересечении.
В этом случае удовлетворены только четыре свойства; поэтому группа — не абелева.
[1 2 3] (перестановка отсутствует). Эти элементы показаны другим цветом.| [1 2 3] | [1 3 2] | [2 1 3] | [2 3 1] | [3 1 2] | [3 2 1] | |
|---|---|---|---|---|---|---|
| [1 2 3] | [1 2 3] | [1 3 2] | [2 1 3] | [2 3 1] | [3 1 2] | [3 2 1] |
| [1 3 2] | [1 3 2] | [1 2 3] | [2 3 1] | [2 1 3] | [3 2 1] | [3 1 2] |
| [2 1 3] | [2 1 3] | [3 1 2] | [1 2 3] | [3 2 1] | [1 3 2] | [2 3 1] |
| [2 3 1] | [2 3 1] | [3 2 1] | [1 3 2] | [3 1 2] | [1 2 3] | [2 1 3] |
| [3 1 2] | [3 1 2] | [2 1 3] | [3 2 1] | [1 2 3] | [2 3 1] | [1 3 2] |
| [3 2 1] | [3 2 1] | [2 3 1] | [3 1 2] | [1 3 2] | [2 1 3] | [1 2 3] |
Пример 5.5
В предыдущем примере мы показали, что множество перестановок с композицией операций — группа. Поэтому использование двух перестановок (одна за другой) не могут усилить безопасность шифра. Мы сможем всегда найти перестановку, которая может сделать ту же самую операцию, используя свойства замкнутости.
Группа называется конечной группой, если множество имеет конечное число элементов; иначе это — бесконечная группа.
Порядок группы, G, — это число элементов в группе. Если группа не конечна, ее порядок бесконечен; если конечна, порядок конечен.
Подмножество H группы G — подгруппа G, если само H — группа относительно операции на G. Другими словами, если G = <S, •> — группа, то H = <T, •> — группа для той же самой операции, и T — непустое подмножество S, то H — G. Вышеупомянутое определение подразумевает, что:
a и b — члены обеих групп, то c = a • b — также элемент обеих групп;a — также элемент обеих групп;G, H = <{e}, •>, является G ;Пример 5.6
Является ли группа H = <Z10, +> G = <Z12, +>?
Решение
Ответ — нет. Хотя H — подмножество G, операции, определенные для этих двух групп, различны. Операция H — сложение по модулю 10 ; операция в G — сложение по модулю 12.
Если
Множество, полученное в результате этого процесса, обозначается в тексте как <a>. Обратите внимание также, что a0 = e.
Пример 5.7
Из группы G = < Z6, +> могут быть получены четыре циклических подгруппы. Это H1 = <{0},+>, H2 =<{0, 2, 4}, +>, H3 = <{0, 3}, +> и H4 = G. Заметим, что когда операция — сложение, то an означает умножение n на a. Заметим также, что во всех этих группах операция — это сложение по модулю 6. Ниже показано, как мы находим элементы этих циклических
a. Циклическая 0, — это H1, имеет только один элемент (нейтральный элемент).
00 mod 6 = 0 (остановка, далее процесс повторяется).
б. Циклическая 1, — это H4, которая есть сама группа G.
10 mod 6 = 0 11 mod 6 = 1 12 mod 6 = (1 + 1) mod 6 = 2 13 mod 6 = (1 + 1 + 1) mod 6 = 3 14 mod 6 = (1 + 1 + 1 + 1) mod 6 = 4 15 mod 6 = (1 + 1 + 1 + 1 + 1) mod 6 = 5(остановка, далее процесс повторяется)
в. Циклическая 2, — это H2, которая имеет три элемента: 0, 2, и 4.
20 mod 6 = 0 21 mod 6 = 2 22 mod 6 = (2 + 2) mod 6 = 4 (остановка, далее процесс повторяется)
г. Циклическая 3, — это H3, которая имеет два элемента: 0 и 3.
30 mod 6 = 0 31 mod 6 = 3 (остановка, далее процесс повторяется)
д. Циклическая 4, — H2 ; это — не новая
40 mod 6 = 0 41 mod 6 = 4 42 mod 6 = (4 + 4) mod 6 = 2 (остановка, далее процесс повторяется)
е. Циклическая 5, — это H4, она есть сама группа G.
50 mod 6 = 0 51 mod 6 = 5 52 mod 6 = 4 53 mod 6 = 3 54 mod 6 = 2 55 mod 6 = 1 (остановка, далее процесс повторяется)
Пример 5.8
Из группы $${\text{G}} = < {{\text{Z}}_{{\text{1}}0*}}, \times >$$ можно получить три циклических подгруппы. G имеет только четыре элемента: 1, 3, 7 и 9. Циклические подгруппы — $${H_1} = \<\left\{ 1 \right\}, \times \>,$$ $${H_2} = \<\left\{ {1,{\text{ }}9} \right\}, \times \>$$ и $${H_3} = G $$. Ниже показано, как мы находим элементы этих
a. Циклическая 1, — это H1.
10 mod 10 = 1 (остановка, далее процесс повторяется)
б. Циклическая 3, — это H3, которая есть группа G.
30 mod 10 = 1 31 mod 10 = 3 32 mod 10 = 9 33 mod 10 = 7 (остановка, далее процесс повторяется)
в. Циклическая 7, — это H3, которая есть группа G.
70 mod 10 = 1 71 mod 10 = 7 72 mod 10 = 9 73 mod 10 = 3 (остановка, далее процесс повторяется)
г. Циклическая 9, — это H2.
90 mod 10 = 1 91 mod 10 = 9 (остановка, далее процесс повторяется)
Циклическая группа — группа, которая является собственной циклической G имеет циклическую подгруппу H5 = G. Это означает, что группа G — циклическая группа. В этом случае элемент, который генерирует циклическую подгруппу, может также генерировать саму группу. Этот элемент далее именуется "генератор". Если g — генератор, элементы в конечной циклической группе могут быть записаны как
{e,g,g2,….., gn-1}, где gn = e.
Заметим, что циклическая группа может иметь много генераторов.
Пример 5.9
а. Группа G = <Z6, +> — циклическая группа с двумя генераторами, g = 1 и g = 5.
б. Группа $${\text{G}} = < {{\text{Z}}_{{\text{1}}0*}}, \times >$$ — циклическая группа с двумя генераторами, g = 3 и g = 7.
Теорема Лагранжа показывает отношение между порядком группы к порядку ее подгруппы. Предположим, что G — группа и H — G. Если порядок G и H — |G| и |H|, соответственно, то согласно этой теореме |H| делит |G|. В примере 5.7 |G| = 6. Порядок подгруппы — |H1| = 1, | H2| = 3, |H3| = 2 и |H4| = 6. Очевидно, все эти порядки есть делители 6.
Теорема Лагранжа имеет очень интересное приложение. Когда дана группа G и ее порядок |G|, могут быть легко определены порядки потенциальных G = <Z17, +> — это |17|. Делители 17 есть 1 и 17. Это означает, что эта группа может иметь только две подгруппы — нейтральный элемент и H2 = G.
Порядок элемента в группе ord (a) (порядок (a)) является наименьшим целым числом n, таким, что a n = e. Иными словами: порядок элемента — порядок группы, которую он генерирует.
Пример 5.10
a. В группе G = <Z6, +>, порядки элементов: порядок ord(0) = 1, порядок ord (1) = 6, порядок ord (2) = 3, порядок ord (3) = 2, порядок ord (4) = 3, порядок ord (5) = 6.
b. В группе G = <Z10, * >, порядки элементов: порядок ord (1) = 1, порядок ord (3) = 4, порядок ord (7) =4, порядок (9) = 2.
Кольцо, обозначенное как $$R = \<\left\{ {...} \right\}, ullet , \bot \>$$, является алгебраической структурой с двумя операциями. Первая операция должна удовлетворять всем пяти свойствам, требуемым для абелевой группы. Вторая операция должна удовлетворять только первым двум свойствам абелевой группы. Кроме того, вторая операция должна быть распределена с помощью первой. Дистрибутивность означает, что для всех a, b и c элементов из R мы имеем $$a \bot (b ullet c) = (a \bot b) ullet (a \bot c)$$ и $$(a ullet b) \bot c = (a \bot c) ullet (b \bot c)$$.
Кольцо включает две операции. Однако вторая операция может не соответствовать третьему и четвертому свойствам. Другими словами, первая операция — фактически операция пары операций, таких как сложение и вычитание; вторая операция может содержать единственную операцию, например умножение, но может не содержать деление.
Пример 5.11
Множество Z с двумя операциями — сложением и умножением — является коммутативным кольцом, которое обозначается $$R = \<Z, + , \times \>$$. Сложение удовлетворяет всем пяти свойствам; умножение удовлетворяет только трем свойствам.
(рис 5.4) Кольцо Умножение дистрибутивно с помощью сложения. Например, $$5 \times (3 + 2) = (5 \times 3) + (5 \times 2) = 25$$. Хотя, мы можем выполнить на этом множестве сложение и вычитание и умножение, но не деление. Деление не может применяться в этой структуре, потому что оно приводит к элементу из другого множества. Результат деления 12 на 5 есть 2,4, и он не находится в заданном множестве.
Поле, обозначенное $$F = \<\left\{ {...} \right\}, ullet , \bot \>$$ —
(рис 5.5) Поле Поле — структура, которая поддерживает две пары операций, используемые в математике: сложение/вычитание и умножение/деление. Есть одно исключение: не разрешено деление на нуль.
Хотя общее определение касается полей бесконечного порядка, в криптографии используются экстенсивно только конечные поля. Конечное поле — поле с конечным числом элементов — является очень важной структурой в криптографии. Галуа показал что поля, чтобы быть конечными, должны иметь число элементов pn, где p — простое, а n — положительное целое число. Конечные поля обычно называют полями Галуа и обозначают как GF(pn).
Когда n = 1, мы имеем поле GF (p). Это поле может быть множеством Zp,
(0, 1, …p–1) с двумя арифметическими операциями (сложение и умножение). Любой элемент в этом множестве имеет аддитивную 0 отсутствует).
Пример 5.12
Очень общее поле в этой категории — GF (2) с множеством {0,1} и двумя операциями, сложением и умножением, как показано на рисунке 5.6.
(рис 5.6) Поле GF (2) Есть несколько моментов, которые следует отметить в определении этого поля. Первый: множество имеет только два элемента, которые являются двоичными цифрами или битами ( 0 и 1 ). Второй: операция сложения — фактически ИСКЛЮЧАЮЩЕЕ ИЛИ ( XOR ), операция, которую мы используем с двумя двоичными цифрами. Третий: операция умножения — AND, операция, которую мы используем с двумя двоичными цифрами. Четвертый: сложение и операции вычитания — те же самые (операция XOR ). Пятый: умножение и операции деления — те же самые (ОПЕРАЦИЯ AND ).
Пример 5.13
Мы можем определить GF(5) на множестве Z5 ( 5 простое) с операторами сложения и умножения, показанными на рис. 5.7.
Хотя мы можем использовать расширенный алгоритм Евклида, чтобы найти мультипликативные инверсии элементов в GF(5), проще составить таблицу умножения и находить каждую пару, произведение которой равняется 1. Это (1, 1), (2, 3), (3, 2) и (4, 4). Заметим, что мы можем на этом множестве применить вычитание и умножение/деление (за исключением запрещенного деления на 0 ).
(рис 5.7) Поле GF (5)
В дополнение к полям GF(p) в криптографии мы также интересуемся полями GF(pn). Однако множества Z, Zn, Zn* и Zp, которые мы использовали до сих пор с операциями сложения и умножения, не могут удовлетворить требованиям поля. Поэтому должны быть определены некоторые новые множества и некоторые новые операции на этих множествах. В следующей лекции мы рассматриваем очень полезное в криптографии поле GF(2n).
Изучение трех алгебраических структур позволяет нам использовать множества, в которых могут применяться операции, подобные сложению/вычитанию и умножению/делению. Мы должны различать эти три структуры. Первая структура — группа, поддерживает одну пару связанных операций. Вторая структура — кольцо, поддерживает одну пару связанных операций и одну одиночную операцию. Третья структура — поле, поддерживает две пары операций. Таблица 5.3 может помочь нам увидеть эту разницу.
| Алгебраическая структура | Используемые операции | Используемые наборы целых чисел |
|---|---|---|
| Группа | (+ -) или (x /) | Zn или Zn* |
| Кольцо | (+ -) и (x) | Z |
| Поле | (+ -) и (x /) | Zp |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.