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

26

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

РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ

Разложить число на множители - значит найти его простые сомножители [4].

10 = 2*5

60 = 2*2*3*5

252601=41*61*101

2113- 1 =3391*23279*65993*1868569*1066818132868207

Разложение на множители является одной из древнейших проблем теории чисел. Этот процесс несложен, но требует времени. Это пока остается так, но ряд сдвигов в этом искусстве все же произошел.

Решето Эратосфена – это алгоритм нахождения простых чисел до заданного числа n. В процессе выполнения данного алгоритма постепенно отсеиваются составные числа, кратные простым, начиная с 2. Блок-схема данного алгоритма представлена на рис.3.

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

22. Что означает разложить число на множители?

23. В чём смысл решета Эратосфена?

27

28

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

СИМВОЛЫ ЛЕЖАНДРА И ЯКОБИ

Символ Лежандра, L(a,/p), определен, если a - это любое целое число, а p - простое число, большее, чем 2. Он равен 0, 1 или -1 [6].

L(a,p) = 0, если a делится на p.

L(a,p) = 1, если a - квадратичный вычет по модулю p.

L(a,p) = -1, если a не является квадратичным вычетом по модулю p.

L(a,p) можно рассчитать следующим образом:

L(a,p = a(p-1)/2 mod p

Или можно воспользоваться следующим алгоритмом:

1.Если a = 1, то L(a,p) = 1

2.Если a четно, то L( a,p) = L(a/2,p) * "2-1)/8

3.Если a нечетно (и Ф 1), то L(a,p)= L(p mod a, p)*(-1)(a-1)(p-1)/4

Этот метод также является эффективным способом определить, является ли a квадратичным вычетом по модулю p (для простого числа p).

С

29

имвол Якоби, J(a,n), представляет собой обобщение символа Лежандра на составные модули, он определяется для любого целого а и любого нечетного целого п. Функция удобна при проверке на простоту. Символ Як о-би является функцией на множестве полученных вычетов делителей п и может быть вычислен по различным формулам. Вот один из способов: Определение 1: J (а,п) определен, только если п нечетно. Определение 2: J(0,«) = 0. Определение 3: Если п - простое число, то символ Якоби J (а,п) = О, если а делится на п. Определение 4: Если п - простое число, то символ Якоби J(a,n) = 1, если а - квадратичный вычет по модулю п. Определение 5: Если п - простое число, то символ Якоби ](а,п) = -1, если а не является квадратичным выче­том по модулю п. Определение 6: Если п - составное число, то символ Якоби J(a,n) = J(a,p1)* ... * J(a,pm), где р1, ... , рт - это разложение п на простые сомножители.

Следующий алгоритм рекурсивно рассчитывает символ Якоби: Правило 1: J(l,n) = 1 Правило 2: J(a*b,n) = J(а,п)* J(b,n) Правило 3: J(2,n) =, если (n2-1) /8 нечетно, и -1 в противном случае Правило 4: J(а,п)= J((a mod n),n) Правило 5: J(a, b1*b2) = J(a, b1)* J(a, b2) Правило 6: Если наибольший общий делитель а и b = 1, а также а и b нечетны: Правило 6а: J(a,b)= J(b, а), если (a - 1)(b - l)/4 четно Правило 6b: J(a,b)= -J(b, а), если (а - 1)(b - 1)/4 нечетно

Если заранее известно, что n - простое число, вместо использования предыдущего алгоритма просто вычислите а((n-1)/2) mod n, в этом случае J(а,п) эквивалентен символу Лежандра.

Символ Якоби нельзя использовать для определения того, является ли а квадратичным вычетом по модулю п (если, конечно, п не является простым числом). Обратите внимание, что если J( а,п) = 1 и п - составное число, то утверждение, что а является квадратичным вычетом по модулю п, не обязательно будет истиной. Например: J(7,143) = J(7, l l)* J(7,13) = (-1)(-1) = 1 Однако не существует таких целых чисел х, что х2 = 7 (mod 143).

Если р и q - два простых числа, конгруэнтных 3 по модулю 4, то п = pq иногда называют целым числом Блюма. Если п - это целое число Блюма, у каждого квадратичного вычета ровно четыре квадратных корня, один из которых также является квадратом - это главный квадратный корень. Например, главный квадратный корень 139 mod 437 - это 24. Остальные три корня - это 185, 252 и 413.

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

24. Как определяется символ Лежандра?

25. Что представляет из себя символ Якоби?

26. Что называют целым числом Блюма?

30

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

ГЕНЕРАТОРЫ

Если р - простое число, и g меньше, чем р, то g называется генератором по модулю р, если для каждого числа b от 1 до р-1 существует некоторое число а, что ga = b (mod p) [6].

Иными словами, g является примитивом по отношению к р. Например, если р = 11, то 2 - это генератор по модулю 11:

2*6 = 12=1 (mod 11) 2*1 = 2 = 2 (mod 11) 2*7 = 14 = 3 (mod 11) 2*2 = 4 = 4 (mod l l) 2*8 =16 = 5 (mod l l) 2*3 = 6 = 6 (mod 11) 2*9 = 18 = 7 (mod 11) 2*4 = 8 = 8 (mod l l) 2*10 = 20 = 9 (mod l l) 2*5 = 32 = 10 (mod 11)

Каждое число от 1 до 10 может быть представлено как 2a (mod p). Для р = 11 генераторами являются 2, 6, 7 и 8. Другие числа не являются генераторами. Например, генератором не является число 3, потому что не существует решения для 3a = 2 (mod 11)

В общем случае проверить, является ли данное число генератором, нелегко. Однако задача упрощается, е сли известно разложение на множители для р - 1. Пусть q1, q2, ... , qn - это различные простые множители р - 1. Чтобы проверить, является ли число g генератором по модулю р, вычислите g(p-1)/q mod p для всех значений q = q1 q2,..., qn.

Если это число равно 1 для некоторого q, то g не является генератором. Если для всех значений q рассчитан­ное значение не равно 1, то g - это генератор.

Например, пусть р = 11. Простые множители р - 1 = 10 - это 2 и 5. Для проверки того, является ли число 2 генератором, вычислим: 2(11-1)/5 (mod 11) = 4

2(11-1)/2 (mod 11) = 10

Н

31

и один из ответов не равен 1, поэтому 2 - это генератор. Проверим, является генератором ли число 3: 3(11-1)/5 (mod 11) = 9 3(11-1)/2 (mod 11) = 1 Следовательно, 3 - это не генератор.

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

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

27. Что называют генератором по модулю р?

28. Как упростить задачу проверки: является ли данное число генератором?

29. Как обнаружить генератор по модулю p?

32

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

ДИОФАНТОВЫ УРАВНЕНИЯ

Диофантовыми называются уравнения вида

P(x₁, x₂, ..., x_n) = 0,

где P(x₁, ..., x_n) – многочлен с целыми коэффициентами.

Рассмотрим алгоритм нахождения решения линейного диофантового уравнения с двумя неизвестными вида a·x + b·y = c (далее для простоты будем опускать знаки умножения и писать прото ax + by = c) [5].

Теорема 1. Уравнение ax + by = c имеет решение в целых числах тогда и только тогда, когда c делится на НОД(a, b).

Теорема 2. Если пара (x₀, y₀) является решением уравнения ax + by = c, то все множество его решений (x, y) описывается формулой:

x = x₀ + kb,

y = y₀ – ka,

   где k Є Z. Очевидно, что если ax₀ + by₀ = c, то a(x₀ + kb) + b(y₀ – ka) = c для любого целого k.

   Для нахождения частичного решения (x₀, y₀) уравнения ax + by = c следует сначала найти решение (x’, y’) уравнения ax + by = d (d – наибольший общий делитель a и b) при помощи расширенного алгоритма Евклида, после чего умножить его на c / d. То есть

x₀ = x’ · c / d,

y₀ = y’ · c / d

Пример. Найти множество решений уравнения 5x + 3y = 7.

   1. Уравнение имеет решение, так как 7 делится на НОД(5, 3) = 1.

   2. Находим решение уравнения 5x’ + 3y’ = 1 при помощи расширенного алгоритма Евклида: (x’, y’) = (-1, 2).

   3. Находим решение (x₀, y₀) исходного диофантового уравнения:

x₀ = -1 · 7 / 1 = -7,

y₀ = 2 · 7 / 1 = 14

   Согласно теореме 2 множество решений исходного диофантового уравнения имеет вид:

(x, y) = (-7 + 3k, 14 – 5k)

33

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

30. Какие уравнения называют диофантовыми?

31. В каком случае уравнение ax + by = c имеет решение в целых числах?

32. Каков алгоритм нахождения решения линейного диофантового уравнения с двумя неизвестными вида a·x + b·y = c?

34

Библиографический список

1. http://www.5byte.ru/

2. http://library.tuit.uz/skanir_knigi/book/zashita_info/zash_info_10.htm

3. http://sti.oskol.ru/about/default.html

4. http://younglinux.info

5. http://www.e-olimp.com

6. http://www.a3print.ru/printer/214/62/index.html

7. Р.Р.Хамидуллин, И.А.Бригаднов, А.В.Морозов “Методы и средства защиты компьютерной информации. Учебное пособие”, Санкт-Петербург, 2005 г.

8. http://nanobukva.ru/09/febu/05_-_ibks_-_kniga_po_kriptografii_46.html

9. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях / под ред. В.Ф. Шаньгина. – 2-е изд., перераб. и доп. – М.: Радио и связь, 2001.

10. Мельников В.В. Защита информации в компьютерных системах. – М.: Финансы и статистика; Электроинформ, 1997.

11. Завгородний В.И. Комплексная защита информации в компьютерных системах: Учебное пособие. – М.: Логос, 2001..

12. Еременко Ю.И., Штангей С.М. Современные информационные технологии Старый Оскол: ООО "ТНТ", 2001.

13. Зегжда Д.П., Ивашко А.М. Основы безопасности информационных систем. М.: Горячая линия - Телеком, 2000.

\

35

Содержание

Практическое занятие 1. Алгоритм Евклида для нахождения общего делителя ………………………………………………………..1

Практическое занятие 2. Расширенный алгоритм Евклида..….4

Практическое занятие 3. Вычисление обратных величин….....6

Практическое занятие 4. Квадратичные вычеты……………...11

Практическое занятие 5. Китайская теорема об остатках……13

Практическое занятие 6. Модулярная арифметика…………..15

Практическое занятие 7. Вычисления в конечных полях……18

Практическое занятие 8. Тестирование простоты числа

методом перебора делителей………………………………………….25

Практическое занятие 9. Разложение на множители…………27

Практическое занятие 10. Символы Лежандра и Якоби……..29

Практическое занятие 11. Генераторы………………………...31

Практическое занятие 12. Диофантовы уравнения…………..33

Библиографический список .......................................................35

36

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

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

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

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

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