Материал: Криптографические методы обеспечения информационной безопасности. методические указания к практическим занятиям по дисциплине Криптографические методы и средства ИБ. Радько Н.М., Мокроусов А.Н

При разумном накоплении промежуточных результатов потребуется только шесть умножений:

(((((((a² mod n) * a) mod n)² mod n)² mod n)² mod n) * a) mod n

Этот метод уменьшает трудоемкость вычислений до 1,5хк операций в среднем, где к - длина числа в битах. Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю n , целесообразно использовать алгоритмы быстрого возведения в степень.

Контрольные вопросы:

14. Как можно выполнить вычисление степени числа а по модулю n?

15. В чём смысл гомоморфного отображения из кольца целых в кольцо целых?

16. Что такое приведение по модулю?

17

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №7

ВЫЧИСЛЕНИЯ В КОНЕЧНЫХ ПОЛЯХ

Поле F есть множество, на котором определены операции сложения и умножения, удовлетворяющие требованиям: ассоциативности, коммутативности, дистрибутивности, существования аддитивного 0 и мультипликативной 1, аддитивных обратных и мультипликативных обратных для всех элементов за исключением 0 [2,7].

Конечное поле F (p) с конечным числом р элементов играет важную роль в криптографии. В общем случае число элементов

P = qⁿ,

где q - некоторое простое число и n≠1. Такие конечные поля называют полями Галуа и обозначают GF (qⁿ) или GF (q) при n=1. (Эварист Галуа - французский математик начала XIX века.) Многие криптосистемы базируются на полях Галуа GF (q), где q - большое простое число.

Пример. Поле Галуа GF (5) имеет элементы 0, 1, 2, 3, 4 и описывается таблицами сложения и умножения (табл.6):

										Таблица 6
+	0	1	2	3	4		X	1	2	3	4
0	0	1	2	3	4		1	1	2	3	4
1	1	2	3	4	0		2	2	4	1	3
2	2	3	4	0	1		3	3	1	4	2
3	3	4	0	1	2		4	4	3	2	1
4	4	0	1	2	3

Если q - простое число, то число a є [1, q - 1] является взаимно простым с q, и поэтому обратный элемент а^-1 имеет единственное значение. Тем самым однозначно определяется операция деления.

О

18

бозначим через GF *(q) множество всех ненулевых элементов поля GF (q). Некоторый элемент g из GF *(q) называют образующим или порождающим элементом GF *(q), если для всех а из GF*(q) найдется такое целое х, что g^x = a mod q. Всего имеется φ(q-1) образующих элементов g. Число х называют дискретным логарифмом элемента а по основанию g и модулю q. Вычисление дискретных логарифмов (когда заданы g, а и q) примерно такая же труднорешаемая задача, как и разложение на множители.

Еще один тип поля Галуа, используемый в криптографии, основывается на арифметике по модулю неприводимых многочленов степени n, чьи коэффициенты - целые числа по модулю q, где q - простое. Эти поля Галуа обозначают как GF (qⁿ). Они имеют элементы, которые описываются многочленами степени не выше (n-1) в форме

а (х) = a_n-1X^n-1 + ... + a₁, Х + а₀.

Каждый элемент а (Х) является вычетом по модулю р(Х), где р(Х)- неприводимый многочлен степени n (т. е. р(Х) нельзя разложить на сомножители - многочлены степени меньше n).

Арифметические действия над коэффициентами a_i выполняются по модулю q, а наивысшая степень X равна (n-1), так как выполняется приведение по модулю многочлена р(Х), имеющего старшую степень n.

Особый интерес представляют поля GF (2ⁿ). Здесь коэффициентами а, являются 0 и 1. Поэтому многочлен а(Х) степени не выше (n-1) можно представить как вектор из n двоичных цифр:

a_n-1a_n-2 ... a₁a₀

Каждый из n-битовых векторов соответствует конкретному элементу поля GF (2ⁿ).

Например, поле Галуа GF (2³) имеет элементы:

Таблица 7

Многочлены		Двоичная форма
0		000
1		001
x		010
x + 1		011
x2		100
x2 + 1		101
x2 + x		110
x2 + x + 1		111

Организация вычислений в полях Галуа предполагает знание некоторых свойств многочленов и их корней в двоичном поле GF (2). Кратко приведем некоторые из них:

С

19

войство 1. Ненулевые элементы поля GF (2ⁿ) являются корнями обобщенного многочлена .

Свойство 2. Каждый многочлен р(Х) степени n, неприводимый над полем GF (2), является делителем двучлена , и каждый делитель двучлена , неприводимый над полем GF (2), имеет степень, равную n и менее.

Свойство 3. Все элементы поля GF (2ⁿ) можно получить как совокупность остатков от деления 100...00 на неприводимый многочлен р (Х), входящий в разложение двучлена ( ). Эти остатки - корни двучлена ( ), т. е. обращают его в нуль. Число остатков равно (2ⁿ-1).

Свойство 4. В поле GF (2ⁿ) существует примитивный элемент α, такой, что каждый ненулевой элемент поля GF (2ⁿ) может быть представлен как некоторая степень α, т. е. мультипликативная группа GF (2ⁿ) является циклической.

Пример. Определение элементов α_i поля GF (2⁴). Согласно свойству 1 ненулевые элементы поля GF (2⁴) являются корнями обобщенного двучлена ( ) = (X¹⁵+1). Двучлен (X¹⁵+1) можно представить в виде произведения неприводимых многочленов - сомножителей:

(X¹⁵+1) = P(Х¹) * Р (Х²) * Р₁(Х⁴) * Р₂(Х⁴) * Р₃(Х⁴),

где

P(Х¹) = (X+1), Р(Х²) = Х² + X + 1,

Р₁(Х⁴) = Х⁴ + X + 1, Р₂(Х⁴) = Х⁴ + Х³ +1,

Р₃(Х⁴) = Х⁴ + Х³ + Х² + X + 1

В соответствии со свойством 3 вычислим элементы α_i поля GF (2⁴) как совокупность остатков отделения 100...00 на неприводимый многочлен Р₁(Х⁴) = Х⁴ + X + 1.

Процедура определения остатков

Делят на Р₁(Х⁴) = Х⁴ + X + 1 <--> 10011 единицу с возрастающим числом нулей, т. е. делят одночлены X^j, где j = 0, 1, 2, 3 ... на многочлен (Х⁴ + X + 1). Степени одночленов Х⁰, Х¹, Х², Х³ меньше степени многочлена Р₁(Х⁴), поэтому первые четыре остатка от деления на Р₁(Х⁴) равны делимым, т. е. одночленам Х⁰, Х¹, Х², Х³. Для одночлена Х⁴ <--> 10000 получаем остаток

Для одночлена Х⁵ <--> 100000 получаем остаток

С

20

хема вычисления остатков:

Вычисленные остатки и нулевые элементы α₀ - α₁₄ поля Галуа GF (2⁴) сведены в табл.8.

Таблица 8

Xi	Остаток	αi
Х0	0001	α0
X1	0010	α1
X2	0100	α2
X3	1000	α3
X4	0011	α4
X5	0110	α5
X6	1100	α6
X7	1011	α7
X8	0101	α8
X9	1010	α9
X10	0111	α10
X11	1110	α11
X12	1111	α12
X13	1101	α13
X14	1001	α14

Поле Галуа GF (2⁴) построено как поле многочленов с коэффициентами 0 и 1 по модулю неприводимого многочлена:

Р

21

(Х⁴)=Х⁴ + Х + 1<--> 10011.

В поле Галуа GF (2ⁿ) определены четыре алгебраические операции. Операции сложения и вычитания выполняются как опера­ ции поразрядного сложения по модулю 2; операция умножения элементов поля выполняется как умножение соответствующих многочленов с приведением по модулю неприводимого многочлена Р (Х), т. е. многочлена, по модулю которого построены элементы поля GF (2ⁿ).

Пример. α₅ = 0110, α₆ = 1100, α₅+ α₆ = 1010, так как

Пример. α₁₄ = 1001,

α₁₄ * α₁₄ = α²₁₄= α₁₃ по mod Р₁(Х⁴) <-->1 0 0 1 1.

Чтобы выполнить деление элемента b на элемент а в поле модулю Р (Х), сначала находят обратный элемент a^-1(mod P (X)), а затем вычисляют

b * a^-1(mod P (X)).

Каждый двоичный вектор длиной n, исключая 0, является взаимно простым с неприводимым многочленом Р (Х) независимо от значения Р (Х). Поэтому число вычетов, взаимно простых с Р(Х), равно φ(Р(Х)) = 2ⁿ - 1 (расширение функции Эйлера для многочленов). Поэтому

a^-1= a^φ(P(X))-1 mod Р(Х) = mod P(Х)

Пример. Пусть a = 100 и P(X) = 1011 в поле GF (2³).

a^-1= (mod 1011) = 100⁶ (mod 1011) = 100² * 100⁴(mod 1011). 100² (mod 1011) = 10000 10110 = 110

или

1

22

00⁴ (mod 1011) = 110² (mod 1011) = 010

или

100² * 100⁴ (mod 1011)= 110 * 010 (mod 1011) = 1100 (mod 1011) = 111

или

Итак, a^-1 = 111. Проверка: a=100, a^-1 = 111, P(X)=1011, a*a^-1=110*100=11100

т. е. a*a^-1(mod 1011) = 1.

Достоинства вычислений в поле GF (2ⁿ):

•  Все элементы поля Галуа имеют конечный размер, деление элементов не имеет каких-либо ошибок округления.

•  Сложение и вычитание элементов поля GF (2ⁿ) не требует деления на модуль.

•  Алгоритмы вычислений в поле GF (2ⁿ) допускают парал­ лельную реализацию.

•  Для поля GF (2ⁿ) обычно применяют в качестве модуля трех­ член Р (Хⁿ) = Хⁿ + Х + 1.

Длинная строка нулей между коэффициентами при Xⁿ и X обеспечивает более простую реализацию быстрого умножения (с приведением по модулю). Трехчлен Р (Хⁿ ) должен быть неприводимым и примитивным.

Т

23

рехчлен Р (Хⁿ)= Хⁿ + Х + 1 является примитивным для следующих значений n (n<1000):

1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900.

Контрольные вопросы:

17. Что такое конечное поле?

18. В чём смысл свойств многочленов и их корней в двоичном поле GF (2)?

19. Каковы достоинства вычислений в поле GF (2ⁿ)?

24

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №8

ТЕСТИРОВАНИЕ ПРОСТОТЫ ЧИСЛА

МЕТОДОМ ПЕРЕБОРА ДЕЛИТЕЛЕЙ

Перебор делителей – это алгоритм, применяемый для определения, какое число перед нами: простое или составное [4].

Алгоритм заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню тестируемого числа. Если хотя бы один делитель делит тестируемое число без остатка, то оно является составным. Если у тестируемого числа нет ни одного делителя, делящего его без остатка, то такое число является простым. Блок-схема данного алгоритма представлена на рис.2.

Контрольные вопросы:

20. В чем смысл алгоритма перебора делителей?

21. Какова блок-схема алгоритма перебора делителей?

25