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

Иначе говоря, функция (n) - это количество положительных целых, меньших n, которые взаимно просты с n.

Малая теорема Ферма: если n - простое и НОД (а, n) = 1, то

a^n-1 1(mod n).

Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД (а, n)= 1, то

a ⁽ⁿ⁾ 1(mod n).

Если n - простое число, то предыдущий результат, учитывая , что (n) = n-1, приводится к виду (малой теоремы Ферма)

a^n-1 1(mod n).

О

8

сновные способы нахождения обратных величин

a^-1 1( mod n).

•  Проверить поочередно значения 1, 2 ,..., n -1, пока не будет найден a^-1 1(mod n), такой, что a*a^-1 (mod n) 1 .

•  Если известна функция Эйлера (n), то можно вычислить

a^-1(mod n) a ^(n)-1 (mod n),

используя алгоритм быстрого возведения в степень.

3. Если функция Эйлера (n) не известна, можно использовать расширенный алгоритм Евклида.

Проиллюстрируем эти способы на числовых примерах .

1. Поочередная проверка значений 1, 2, ..., n-1, пока не будет найден x=a^-1 (mod n), такой что a * x 1(mod n).

Пусть n = 7, а = 5. Требуется найти x = a^-1 (mod n).

a*x 1(mod n) или 5*x 1 (mod 7).

n-1 = 7-1 = 6.

Получаем x = 5^-1 (mod 7) = 3.

Результаты проверки сведены в табл.4.

Таблица 4

x	5 * х	5 * х (mod 7)
1	5	5
2	10	3
3	15	1
4	20	6
5	25	4
6	30	2

2. Нахождение a^-1 (mod n), если известна функция Эйлера (n). Пусть n=7, а=5. Найти x = a^-1 (mod n) = 5^-1 (mod 7). Модуль n=7 - простое число. Поэтому функция Эйлера (n) = (7) = n-1=6. Обратная величина от 5 по mod 7

a^-1 (mod n) = a ^(n)-1(mod n) = 5^6-1 mod 7 = 5⁵ mod 7 = (5² mod 7)(5³ mod 7) mod 7 = (25 mod 7)(125 mod 7) mod 7 = (4 * 6) mod 7 = 24 mod 7= 3.

И

9

так, x =5^-1 (mod 7) = 3.

3. Нахождение обратной величины a^-1 (mod n) с помощью расширенного алгоритма Евклида.

Алгоритм Евклида можно обобщить способом, который имеет большое практическое значение. При этом способе во время вычисления НОД (а, Ь) можно попутно вычислить такие целые числа u₁, и u₂, что

а * u₁ + b * u₂ = НОД (a, b).

Это обобщение (расширение) алгоритма Евклида удобно описать, используя векторные обозначения.

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

6. Что такое мультипликативная обратная величина?

7. Что такое полный набор вычетов по модулю?

8. В чём смысл малой теоремы Ферма?

10

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

КВАДРАТИЧНЫЕ ВЫЧЕТЫ

Рассмотрим некоторое простое р>2 и число а<р [2]. Если число а сравнимо с квадратом некоторого числа х по модулю р, т. е. выполняется сравнение x² a (mod p), тогда а называют квадратичным вычетом по модулю р. В противном случае а называют квадратичным невычетом по модулю р.

Если а - квадратичный вычет, сравнение x² a (mod p) имеет два решения: + х и - х, т. е. а имеет два квадратных корня по модулю р.

Все квадратичные вычеты находят возведением в квадрат элементов 1, 2, 3, ..., (р-1)/2.

Не все значения а<р являются квадратичными вычетами. Например, при р=7 квадратичные вычеты это 1, 2, 4:

1² =1 1(mod 7),

2² = 4 4(mod 7),

3² = 9 2(mod 7),

4² = 16 2(mod 7),

6² = 36 1(mod 7).

Заметим, что каждый квадратичный вычет появляется в этом списке дважды. Не существует никаких значений х, которые удовлетворяли бы любому из следующих уравнений:

x² 3(mod 7),

x² 5(mod 7),

x² 6(mod 7),

Числа 3, 5 и 6 - квадратичные невычеты по модулю 7. Можно доказать, что существует точно (р -1)/2 квадратичных вычетов по модулю р и (р-1)/2 квадратичных невычетов по модулю р.

Если а - квадратичный вычет по модулю р, то а имеет точно два квадратных корня: один корень между 0 и (р-1)/2, другой корень между (р-1)/2 и (р-1).

Один из этих квадратных корней также является квадратичным вычетом по модулю р; он называется главным квадратным корнем.

Пример. Вычисление квадратных корней при р=7 представлено в табл.5.

11

Таблица 5
	Корни
х2 a(mod 7)	x1	x2
12 1(mod 7) 22 4(mod 7) 32 2(mod 7)	+1 +2 +3	-1 = -1 + 7 = 6 -2 = -2 + 7 = 5 -3 = -3 + 7 = 4

Если n - произведение двух простых р и q, т. е. n = p * q, то существуют точно

(p-1)(q-1)/4

квадратичных вычетов по модулю n, взаимно простых с n. Например, по модулю 35 (р=5, q=7, n=5*7=35) существуют

(5-7)(7-1)/4 = 4*6/4 = 6

квадратичных вычетов: 1, 4, 9, 11, 16, 29, взаимно простых с 35.

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

9. Что такое квадратичный невычет по модулю?

10. Как находят квадратичные вычеты?

11. Что такое главный квадратный корень?

12

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

КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ

Любое неотрицательное целое число, не превосходящее произведения модулей, можно однозначно восстановить, если известны его вычеты по этим модулям [2]. Этот результат был известен еще в древнем Китае и носит название китайской теоремы об остатках. Теорема была предложена китайским математиком первого века Сун Це. Китайская теорема об остатках является мощным криптографическим инструментом.

Китайская теорема об остатках формулируется следующим образом.

Пусть m₁, m₂, ..., m_t - модули (целые числа, большие 1), которые являются попарно взаимно простыми, т. е. HOД (m_i, m_j)=1 при i ≠ j .

Пусть a₁, a₂, ..., a_t - тоже целые числа, 0 ≤ a_i ≤ m_i.

Пусть M = m₁ * m₂ *...* m_t- произведение всех m_i. Обозначим М_i = М /m_i

И пусть N_i будет обратным к M_i (mod m_i), i=1, 2, ..., t, т. е. M_i * N_i 1(mod m_i).

Так как HOД (M_i, m_i) = 1, то обратный элемент N_i существует и легко находится из алгоритма Евклида из соотношения

M_i * N_i + m_i * n _i = 1, i = 1, 2, ..., t.

Сравнения x a_i (mod m_i), i = 1, 2, ..., t, имеют в интервале [0, М-1] единственное общее решение

x= a_i * N_i * M_i (mod M).

Рассмотрим частный случай. Пусть M = m₁ * m_2, где m₁, m₂ - взаимно простые числа. Тогда для произвольных целых a₁< m₁ и a₂<m₂ существует единственное число х, х<М, такое, что

х a₁(mod m₁) и x = a₂ (mod m₂).

Чтобы найти значение решения х, сначала используют алгоритм Евклида для вычисления значений N_i и N₂, таких, что

N₁ * M₁ 1 (mod m₁) и N₂ * М₂ 1 (mod m₂).

Здесь M₁ = M / m₁ = m₁* m₂ / m₁= m₂

M₂ = M / m ₂ = m₁

Затем вычисляют значение

x

13

= (a₁* N₁* M₁ + a₂* N₂* M₂)(mod M).

Пример. Решить систему из двух сравнений

x 1(mod 5),

х 10 (mod 11)

и найти общее решение х по модулю 55. Здесь m₁= 5; m₁= 11; M=m₁* m₂ = 5*11=55; a₁ = 1; a₂=10; M₁= M/m₁=m₂=11; M₂=M/m₂=m₁=5.

Найдем значения N₁ и N₂, обратные к M₁ и M₂ соответственно по mod m₁ и - mod m₂:

M₁* N₁ 1 (mod m₁), 11*N₁ 1(mod 5) => N₁ = 1,

M₂* N₂ 1(mod m₂), 5 * N₂ 1 (mod 11) => N₂ = 9.

Вычисляем общее значение

x = (a₁M₁N₁ + a₂M₂N₂)(mod N) = (1 * 11 * 1 + 10 * 5 * 9)(mod 55) =

= (11 + 450)(mod 55) = 461 (mod 55) = 21 (mod 55).

Итак, x=21(mod 55).

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

12. Как можно восстановить любое неотрицательное целое число, не превосходящее произведения модулей?

13. Какие формулируется китайская теорема об остатках?

14

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

МОДУЛЯРНАЯ АРИФМЕТИКА

Модулярная арифметика часто изучается в школе как "арифметика часов" [3,11-13]. Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня:

3+14 5 (mod 12)

или

(3+14) mod 12=5

Это арифметика по модулю 12. Обычная запись в модулярной арифметике

a b(mod n)

читается так: "а сравнимо с b по модулю n". Это соотношение справедливо для целых значений a, b и n≠0, если, и только если

а = b + k * n

для некоторого целого к. Отсюда, в частности, следует

n | (а - b).

Это читается как "n делит (а - b)". Если a b(mod n) то b называют вычетом числа а по модулю n. Операцию нахождения вычета числа а по модулю n

a(mod n)

называют приведением числа а по модулю n или приведением по модулю. В нашем примере

(3 +14) mod 12 = 17 mod 12 = 5

или

17 5(mod 12),

число 5 является вычетом числа 17 по модулю 12. Набор целых чисел от 0 до (n-1) называют полным набором вычетов по модулю n. Это означает, что для любого целого a(а>0) его вычет r по модулю n есть некоторое целое число в интервале от 0 до (n-1), определяемое из соотношения

г

15

=а-к*n,

где к - целое число. Например, для n=12 полный набор вычетов:

{0, 1, 2, …, 11}.

Обычно предпочитают использовать вычеты

rє{0,1,2, ... , n-1},

но иногда полезны вычеты в диапазоне целых:

Заметим, что

-12(mod 7) -5(mod 7) 2(mod 7) 9(mod 7) и т.д.

Модулярная арифметика аналогична во многом обычной арифметике: она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием операций сложения и умножения образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности. Фактически мы можем либо сначала приводить по модулю n, a затем выполнять операции, либо сначала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю n является гомоморфным отображением из кольца целых в кольцо целых по модулю n:

(а + b) mod n = [a(mod n) + b(mod n)] mod n, (а - b) mod n = [a(mod n) - b(mod n)] mod n. (а * b) mod n = [a(mod n) * b(mod n)] mod n, [а * (b + с)] mod n = {[а * b(mod n)] + [а * c(mod n)]} mod n.

16

Криптография использует множество вычислений по модулю n, потому что задачи типа вычисления дискретных логарифмов и квадратных корней очень трудны. Кроме того, с вычислениями по модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и результата. Для модуля n длиной к бит промежуточные результаты любого сложения, вычитания или умножения будут не длиннее 2к бит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации очень больших промежуточных результатов. Вычисление степени числа а по модулю n можно выполнить как ряд умножений и делений. Существуют способы сделать это быстрее. Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более). Например, если нужно вычислить

a⁸mod n,

не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(а*а*а*а*а*а*а*а) mod n.

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

((a² mod n)² mod n)² mod n.

Тем же способом вычисляют

a¹⁶ mod n = (((a² mod n)² mod n)² mod n)² mod n.

Вычисление

a^x mod n,

где х не является степенью 2, лишь немного сложнее. Двоичная запись числа х позволяет представить число х как сумму степеней 2: x = 25₍₁₀₎-> 11001₍₂₎ , поэтому 25 = 2⁴ + 2³ + 2⁰. Тогда

a²⁵ mod n = (а * a²⁴) mod n = (а * а⁸ * a¹⁶) mod n = а * ((а²)²)² * (((a²)²)²)² mod n = ((((а² * *а)²)²)² * a) mod n.