Глава 15

Арифметические и алгебраические основы

криптографии

15.1. Литература

1. Н. Коблиц, Курс теории чисел и криптографии, Москва, ТВП, 2001 г, 154 с.

2. Ю.С. Харин и др., Математические основы криптологии, Учеб. Пособие/ Мн. БГУ, 1999 г.

15.2. Арифметические основы

Сравнения

Будем рассматривать целые числа в связи с остатками от их деления на натуральное m, называемое модулем.

Если два целых a и b имеют одинаковые остатки от деления на m, то они называются сравнимыми по модулю m.

Сравнимость числе a, b записывают в виде

a ≡ b(

mod m).

Свойства сравнений

1. a ≡ b( mod m) ⇔ m|a − b

2. a ≡ b( mod m), b ≡ c( mod m) ⇒ a ≡ c( mod m)

Действительно, m|a − b, m|b − c ⇒ m|((a − b) + (b − c)) ⇒ m|a − c

3. Сравнения можно почленно складывать

Пусть a1 ≡ b2( mod m), a2 ≡ b2( mod m). Тогда m|a1 − b1, m|a2 − b2. В силу свойства 1 m|a1 − b1 + a2 − b2, т.е.

m|(a1 + a2) − (b1 − b2)

4. Сравнения можно почленно перемножать.

Пусть a1 = mq1 + r1, b1 = mq2 + r1, a2 = mq3 + r2, b2 = mq4 + r2. Тогда a1a2 = m(mq2 + q1r1 + q2r1) + r1r2, т.е.

a1a2 ≡ r1r2( mod m). Аналогично b1b2 ≡ r1r2( mod m)

5. К обеим частям сравнения можно прибавить одно и то же число.

6. Обе части сравнения можно умножить на одно и то же число

7. Обе части сравнения можно разделить на их общий делитель, если он взаимно просто с модулем.

Пусть a1d ≡ b1d( mod m). Тогда m|d(a1 − b1). В силу свойства 2 m|a1 − b1, поскольку (m, d) = 1.

8. Обе части сравнения и модуль можно сокращать на их общий делитель.

9. a ≡ b( mod m1), a ≡ b( mod m2) ⇒ a ≡ b( mod [m1, m2])

10. a ≡ b( mod m), d|b, d|m ⇒ d|a

Действительно, m|a − b ⇒ d|a − b ⇒ d|a − b + b ⇒ d|a

11. a ≡ b( mod m) ⇒ (a, m) = (b, m)

Классы вычетов

Числа, сравнимые по модулю m, образуют класс вычетов по модулю m. Все числа из одного класса имеют

один и тот же остаток r от деления на m. Любое число a из класса вычетов называется вычетов по модулю m.

Соответствующий класс обозначается через a. Поскольку отношения a ≡ b( mod m) является бинарным отношением

эквивалентности, имеем разбиение целых чисел на классы вычетов. Всего имеется m классов вычетов по модулю m:

0, 1, 2, . . . , m − 1.

Взяв из каждого класса по одному вычету, получим полную систему вычетов. Например, наряду с 0, 1, 2, . . . , m−

1 полной системой вычетов будет 1, 2, . . . , m.

Согласно свойству 11 числа одного класса вычетов имеют с модулем m один и тот же общий делитель. Рассмотрим

те классы, для которых этот делитель равен 1. Взяв от каждого такого класса по одному вычету, получим приве-

дённую систему вычетов. Например, приведённая система по модулю 42 будет 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37,

41.

¯

¯ ¯ ¯

15.3. Алгебраические основы

Свойства классов вычетов

1. a ≡ b( mod m) ⇔ a = ¯

2. a ≡ b( mod m) ⇔ a ∩ ¯

3. Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов.

4. Если (a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b, где b - любое целое, так же

пробегает полную систему вычетов по модулю m

Доказательство. В силу свойства 3 достаточно проверить, что ax1 +b ≡ ax2 +b( mod m) при x1 ≡ x2( mod m).

Допустив ax1 + b ≡ ax2 + b( mod m) получим ax1 ≡ ax2( mod m) ⇒ x1 ≡ x2( mod m).

5. Если (a, m) = 1 и x пробегает приведённую систему вычетов по модулю m, то ax также будет пробегать приве-

дённую систему вычетов по модулю m

Достаточно показать, что числа ax попарно несравнимы (свойство 3) и взаимно просто с модулем m. Второе

следует из (m, a) = 1 и (m, x) = 1.

Первообразные корни

Говорят, что число a, взаимно простое с модулем m, принадлежит показателю δ, если δ - такое наименьшее нату-

ральное число, что выполняется сравнение aδ ≡ 1 mod m. Справедливы следующие свойства.

1. Числа a0, a1, . . . , aδ−1 попарно несравнимы по модулю m.

Действительно, al ≡ ak ( mod m), l > k ⇒ al−k ≡ 1( mod m), где l − k ∈ N, l − k < δ.

2. aγ ≡ aγ ( mod m) ⇔ γ ≡ γ ( mod δ)

Разделим γ, γ на δ с остатками γ = δp + r, γ = δq + r . Тогда aγ ≡ aγ ⇔ aδq+r ≡ aδq +r ⇔ ar ≡ ar ⇔ r = r.

Отсюда вытекает следующее свойство:

3. δ | ϕ(m)

Число, принадлежащее показателю ϕ(m) называется первообразным корнем по модулю m.

4. По любому модулю p существует первообразный корень.

Примем это без доказательства. Гауссом установлено существование первообразных корней по модулям pk и 2pk

при любом нечётном простом p. Легко убедиться, что при m = 4 первообразный корень так же существует.

Таким образом, первообразные корни существуют по модулям 2, 4, pα, 2pα, где p - нечётное простое, α ∈ N.

15.3. Алгебраические основы

Группой называется непустое множество G с алгебраической операцией * на нём, для которой выполняются

следующие три аксиомы:

1. Операция * ассоциативна, т.е.

∀a, b, c, ∈ G

a ∗ (b ∗ c) = (a ∗ b) ∗ c

2. В G имеется единичный элемент (или единица) e, такой, что

3.

∀a ∈ G

a ∗ e = e ∗ a = a

∀a ∈ G ∃a−1 ∈ G

Здесь a−1 называется обратным к a.

Если дополнительно группа удовлетворяет условию

∀a, b ∈ G

a ∗ a−1 = a−1 ∗ a = e.

a ∗ b = b ∗ a

то она называется абелевой (или коммутативной

Аддитивные и мультипликативные операции в группе

Для групповой операции будем использовать мультипликативное обозначение и вместо a ∗ b писать ab, называя

этот элемент произведением элементов a и b. Иногда для групповой операции используют аддитивную запись и пишут

a + b. В этом случае вместо единицы пишут ноль, а вместо a−1 пишут −a. Такие обозначения обычно резервируют

для абелевых групп.

В группе имеется лишь один единичный элемент. Действительно, если e - ещё одна единица, то e = e e = e. Для

любого элемента имеется лишь один обратный. Действительно, пусть x, y - обратные элементы для a ∈ G. Тогда

55

¯ b

¯ v

15. Арифметические и алгебраические основы криптографии

x = xe = x(ay) = (xa)y) = ey = y

Циклическая группа

Мультипликативная группа G называется циклической, если она порождена одним элементом, т.е. в ней имеется

такой элемент a (образующий), что любой другой элемент b представим в виде b = an, n ∈ Z. Если n - отрицательное,

|n|

то под an понимают a−1 . Циклическими являются группы Z, Zm. Группа Zm оказывается циклической лишь в

случае, когда по модулю m существует первообразный корень. В циклической группе, конечной или нет, может быть

несколько образующих элементов. В аддитивной группе Z образующими будут элементы 1, −1. Циклическая группа

всегда коммутативна.

Подгруппы

Подмножество H группы G называется подгруппой этой группы, если H само образует группу относительно

операции группы G.

Подгруппы группы G, отличные от тривиальный подгрупп {e}, G группы G, называются собственными подгруп-

пами.

Пример группы

Обозначим через 0, 1, 2, 3, ¯ классы вычетов по модулю 5. Определим их сложение по модулю 5. Например, 1+ ¯ = 3,

¯ + ¯ = 0, ¯ + ¯ = 1, т.е. осуществляется обычное сложение и при необходимости берётся остаток от деления на 5. Эта

группа обозначается через Z5 и называется (аддитивной) группой классов вычетов по модулю 5. Аналогичным

образом строится группа классов вычетов Zm по любому модулю m. Если взять все классы вычетов, взаимно простые

с модулем m, и определить их умножение по модулю m, то получится группа, обозначаемая через Zm. Отметим, что

существование обратного элемента для a ∈ Zm вытекает из разрешимости сравнения ax ≡ 1( mod m) при (a, m) = 1.

Гомоморфизм групп

Отображение f : G → G группы G в группу G называется гомоморфизмом, если оно согласовано с операциями

на группах G и G , т.е. f (ab) = f (a)f (b) для любых a, b ∈ G. Если это отображение сюръективно, то оно называется

эпиморфизмом. В этом случае группа H называется гомоморфным образом группы G. Приставка “моно” употребляет-

ся в случае, когда гомоморфизм инъективен. Биективный гомоморфизм называется изоморфизмом. Для изоморфных

групп употребляется обозначение G H. Изоморфизм группы G на себя называется автоморфизмом.

Понятие кольца

Кольцом называется множество R с двумя бинарными операциями, обозначаемыми символами +, ·, такими что

1. R - абелева группа относительно операции +

2. ∀a, b, c ∈ R

3. ∀a, b, c ∈ R

(ab)c = a(bc)

a(b + c) = ab + ac & (b + c)a = ba + ca

Условимся нейтральный элемент аддитивной группы кольца называть нулём и обозначать символом 0. Противо-

положный элемент к a обозначают через −a. Вместо a + (−b) обычно пишут a − b.

Кольцо называется кольцом с единицей, если оно имеет мильтипликативную единицу, т.е. такой элемент e, что

ae = ea = a ∀a ∈ R.

Делитель нуля

Кольцо называется коммутативным, если операция умножения коммутативна.

Два элемента кольца a = 0, b = 0 называются делителями нуля, если ab = 0. Приведём пример делителей нуля.

Рассмотрим кольцо классов вычетов Zm по модулю m. Оно состоит из элементов 0, 1, 2, . . . , m − 1. Операция сложения

над этими элементами была определена ранее. Аналогично определяется умножение. Выполняем обычное умножение

чисел и при необходимости берём остаток от деления на m. Если m - составное, m = ab, то делителями нуля будут

a, b.

Кольцо называется областью целостности, если оно является коммутативным кольцом с единицей и без делителей

нуля.

Понятие поля

Коммутативное кольцо называется полем, если его ненулевые элементы образуют группу относительно операции

умножения. Отметим простейшие свойства полей.

1. В поле нет делителей нуля.

2. В поле второй закон дистрибутивности вытекает из первого.

56

∗

¯ ¯ ¯ ¯ 4 ¯ 2 ¯

2 3 ¯ 2 4 ¯

∗

¯ ∗

¯ ¯ ¯

¯ ¯

15.3. Алгебраические основы

3. Конечная область целостности является полем.

4. Кольцо классов вычетов Zm будет областью целостности, а значит, и полем лишь при простом m.

Поле Zp называется полем Галуа порядка p и обозначается GF (p)

Подкольца и идеалы

Подмножество S кольца R называется подкольцом этого кольца, если оно замкнуто относительно имеющихся

операций сложения и умножения и само образует кольцо относительно этих операций.

Подкольцо H кольца R называется идеалом (двусторонним идеалом) этого кольца, если для всех a ∈ H, r ∈ R

имеет место ar ∈ H, ra ∈ H.

Пусть R - коммутативное кольцо. Идеал H кольца R называется главным идеалом, если существует элемент

a ∈ R такой, что H = {ar|r ∈ R}. В этом случае H называют также главным идеалом, порождённым элементом

a.

Характеристика кольца

Пусть теперь кольцо R содержит 1. Рассмотрим циклическую подгруппу аддитивной группы кольца, порождённую

единицей. Она автоматически будет подкольцом, так как

(1 + . . . + 1) (1 + . . . + 1) = (1 + . . . + 1)

m

n

mn

Она автоматически будет изоморфна любо аддитивной группе кольца Z, либо аддитивной группе одного из колец

вычетов Zm. В первом случае говорят, что характеристика кольца R равно нулю, charR = 0. Во втором случае

полагают charR = m

57