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

ФГБОУВПО «Воронежский государственный

технический университет»

Кафедра систем информационной безопасности

Криптографические методы обеспечения информационной безопасности методические указания

к практическим занятиям

по дисциплине “Криптографические методы

и средства ИБ” для студентов специальностей

090102 “Компьютерная безопасность”, 090105 “Комплексное обеспечение информационной безопасности

автоматизированных систем”, 090106 “Информационная

безопасность телекоммуникационных

систем” очной формы обучения

Воронеж 2011

Составители: преп. Н.М. Радько, преп. А.Н. Мокроусов

УДК 681.326

Криптографические методы обеспечения информационной безопасности: методические указания к практическим занятиям по дисциплине "Криптографические методы и средства ИБ" для студентов специальностей 090102 “Компьютерная безопасность”, 090105 “Комплексное обеспечение информационной безопасности автоматизированных систем”, 090106 “Информационная безопасность телекоммуникационных систем” очной формы обучения / ФГБОУВПО «Воронежский государственный технический университет»; сост. Н.М. Радько, А Н. Мокроусов. Воронеж, 2011. 36 с.

Методические указания предназначены для студентов четвертого и пятого курсов, выполняющих практические занятия по изучению основ криптографии. Рассмотрены элементы теории чисел в разделах модулярная арифметика и алгебраические структуры

Методические указания подготовлены в электронном виде в текстовом редакторе MS WORD и содержатся в файле Криптометоды ИБ.doc.

Табл. 8. Ил. 3. Библиогр.: 13 назв.

Рецензент д-р техн. наук, проф. Н.Н. Толстых

Ответственный за выпуск зав. кафедрой д-р техн. наук, проф. А.Г. Остапенко

Издаётся по решению редакционно-издательского совета Воронежского государственного технического университета

 ФГБОУВПО “Воронежский государственный технический университет”, 2011

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

АЛГОРИТМ ЕВКЛИДА ДЛЯ НАХОЖДЕНИЯ

ОБЩЕГО ДЕЛИТЕЛЯ

Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел [1].

Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:

НОД(12, 18) = 6.

Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом: Дано: М, N Найти: НОД(М, N).

В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.

Идея алгоритма Евклида

Идея этого алгоритма основана на том свойстве, что если M>N, то

НОД(М, N) = НОД(М - N, N).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

Легко доказать это свойство. Пусть К - общий делитель М u N (M> N). Это значит, что М = mК, N = nК, где m, n - натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.

Второе очевидное свойство:

НОД(М, М) = М.

Для "ручного" счета алгоритм Евклида выглядит так:

1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;

2) заменить большее число разностью большего и меньшего из чисел;

3) вернуться к выполнению п. 1.

Рассмотрим этот алгоритм на примере М=32, N=24:

Получили: НОД(32, 24) =НОД(8, 8) = 8, что верно.

На рис.1 приведена блок-схема алгоритма Евклида.

С

2

Ниже представлена табл.1 алгоритма для исходных значений М = 32, N = 24.

Таблица 1

В итоге получился верный результат.

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

1. Что такое наибольший общий делитель двух натуральных чисел?

2. На каком свойстве основана идея алгоритма Евклида?

3. Какова блок-схема алгоритма Евклида?

3

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

РАСШИРЕННЫЙ АЛГОРИТМ ЕВКЛИДА

При заданных неотрицательных целых [2,3,9,10] числах а и b этот алгоритм определяет вектор

(u₁, u₂, u₃),

такой, что

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

В процессе вычисления используются вспомогательные векторы (v₁, v₂, v₃), (t₁, t₂, t₃). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

а * t₁ + b * t₂ = t₃,

a * u₁ + b * u₂= u₃,

a * v₁ + b * v₂ = v₃.

Для вычисления обратной величины a^-1 (mod n) используется частный режим работы расширенного алгоритма Евклида, при котором Ь = n , НОД (а, n)=1, и этот алгоритм определяет вектор

(u₁, u₂, u₃),

такой, что

u₃ = 1, a * u₁ + n * u₂ = НОД (а, n) = 1,

(а * u₁+ n * u₂) mod n а * u₁(mod n) 1.

a^-1 (mod n) u₁ (mod n).

Шаги алгоритма :

1. Начальная установка . Установить (u₁, u₂, u₃) := (0, 1, n),

(v₁, v₂, v₃) := (1, 0, a).

2. u₃ = 1?. Если u₃ = 1, то алгоритм заканчивается.

3. Разделить, вычесть. Установить q :=[ u₃ / v₃ ]. Затем установить

(t₁, t₂, t₃) := (u₁, u₂, u₃) - (v₁, v₂, v₃) * q,

(u₁, u₂, u₃) := (v₁, v₂, v₃),

(v₁, v₂, v₃) := (t₁, t₂, t₃).

Возвратиться к шагу 2.

П

4

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

Таблица 2

При u₃= 1, u₁= -9, u₂= 2

(а * u₁ + n * u₂ ) mod n = (5 * (-9) + 23 * 2) mod 23 =

= 5*(-9) mod 23 1,

a^-1 (mod n) = 5^-1 (mod 23) = (-9) mod 23 = (-9 + 23) mod 23 = 14.

Итак , х = 5^-1(mod 23) 14 (mod 23) = 14.

Для решения более сложных сравнений

а * х b (mod n), т. е. Ь≠1, х = ?

используется следующий прием. Сначала решают сравнение

а * у 1(mod n), т. е. определяют

у = a^-1( mod n), а затем находят

х = a^-1 b (mod n) = у * b (mod n).

Пример 2. Найти х для сравнения

5 * х 9 (mod 23).

Сначала решаем сравнение

5 * y 1(mod 23).

Получаем у = 5^-1(mod 23) = 14. Затем находим

х = 5^-1 * 9 (mod 23) = 14 * 9 (mod 23) = 126 (mod 23) 11 (mod 23),

x = 11.

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

4. Какой вектор определяет расширенный алгоритм Евклида?

5. Каковы шаги расширенного алгоритм Евклида?

5

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

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

В арифметике действительных чисел [7, 8] нетрудно вычислить мультипликативную обратную величину а^-1 для ненулевого а:

а^-1 =1/а или а * а^-1 = 1.

Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку

4 * 1/4 = 1.

В модулярной арифметике вычисление обратной величины является более сложной задачей. Например, решение сравнения

4 * x 1( mod 7)

эквивалентно нахождению таких значений х и к, что

4 * х 7 * к +1,

где х и к - целые числа.

Общая формулировка этой задачи - нахождение такого целого числа х , что

a * x (mod n)=1.

Можно также записать

а^-1 x (mod n).

Решение этой задачи иногда существует, а иногда его нет . Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку

5*3=15 1 (mod 14).

С другой стороны, число 2 не имеет обратной величины по модулю 14.

Вообще сравнение a^-1 x (mod n) имеет единственное решение, если а и n - взаимно простые числа.

Если числа а и n не являются взаимно простыми, тогда сравнение a^-1 x ( mod n ) не имеет решения.

Сформулируем основные способы нахождения обратных величин. Пусть целое число aє{0, 1, 2, ..., n -1}. Если НОД (а, n) = 1, то a * i (mod n) при i = 0, 1, 2, ..., n-1 является перестановкой множества {0, 1, 2, ..., n -1}.

Например, если а = 3 и n = 7(НОД (3,7)=1), то

3 * i ( mod 7) при i = 0, 1, 2, ..., 6

я

6

Это становится неверным, когда НОД (а , n)≠1. Например, если а = 2 и n =6, то

2 * i ( mod 6) 0, 2, 4, 0, 2, 4 при i = 0, 1, 2, ..., 5.

Если НОД (а, n)=1, тогда существует обратное число а^-1, 0<а^-1<n , такое, что

а * а^-1 1(mod n).

Действительно, a * i (mod n) является перестановкой 0,1, ..., n-1, поэтому существует i, такое, что

а * i 1(mod n).

Как уже отмечалось, набор целых чисел от 0 до n-1 называют полным набором вычетов по модулю n. Это означает, что для любого целого числа а(а>0) его вычет r=a (mod n) - это некоторое целое число в интервале от 0 до n-1.

Выделим из полного набора вычетов подмножество вычетов, взаимно простых с n . Такое подмножество называют приведенным набором вычетов.

Пример. Пусть модуль n = 11 - простое число. Полный набор вычетов по модулю 11

{0, 1, 2, ..., 10}.

При формировании приведенного набора вычетов из них удаляется только один элемент - 0. Приведенный набор вычетов по модулю 11 имеет 11-1=10 элементов.

Вообще приведенный набор вычетов по модулю простого числа n имеет n-1 элементов.

Пример. Пусть модуль n =10. Полный набор вычетов по модулю n =10

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10. Поэтому приведенный набор вычетов по модулю 10 равен {1, 3, 7, 9}. При формировании этого приведенного набора были исключены элементы:

т

7

Для произведения простых чисел p*q=n приведенный набор вычетов имеет (р - 1)(q - 1) элементов. При n = p*q = 2*5= 10 число элементов в приведенном наборе

(р-1)(q-1) = (2-1)(5-1) = 4.

Пример. Приведенный набор вычетов по модулю 27= З³ имеет 18

элементов:

{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}.

Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов). Для модуля в виде простой степени n^r приведенный набор вычетов имеет n^r-1 1(n-1) элементов.

При n = 3, r = 3 получаем З^3-1(3-1)=3² *2=18.

Функция Эйлера (n) характеризует число элементов в приведенном наборе вычетов (табл.3).

Таблица 3