|
|
Оглавление1. Понятие информационной безопасности 2. Основные классификации угроз информационной безопасности 3. Программы с потенциально опасными последствиями 5. Элементарные методы цифрового шифрования 6. Симметричные системы защиты информации 7. Криптография с открытым ключом. 8. Аутентификация 9. Методы криптоанализа классических шифров Методические указания к лабораторным работам Контрольно-измерительные материалы Методические рекомендации по разработке курсовых работ Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгуМЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМЛабораторная работа № 1Алгоритмы вычисления наибольшего общего делителя Цель работы – изучение алгоритмов вычисления наибольшего общего делителя целых чисел и анализ их быстродействия. Теоретические сведения. Пусть a1, а2, ..., аk ∈ Z. Число d ∈ Z называется наибольшим общим делителем чисел а1, а2, ..., аk (обозначается d = НОД (а1, а2, ..., аk)), если, во-первых, a1 d, а2 d, ..., аk d; и, во-вторых, если d1 – другой общий делитель чисел а1, а2, ..., аk, то d d1. Целые числа а и b называются ассоциированными (обозначается а ~ b), если а b, b а. Теорема 1.1 (об ассоциированных числах), а ~ b тогда и только тогда, когда а = ±b. Теорема 1.2 (о единственности наибольшего общего делителя). Пусть а1, а2, ..., аk ∈ Z. Если d1 = НОД (а1, а2, ..., аk) и d2 = НОД (а1, а2, ..., аk), то d1 ~ d2. И обратно, если d1 = НОД (а1, а2, ..., аk) и d1 ~ d2, то d2 – тоже наибольший общий делитель чисел а1, а2, ..., аk. Теорема 1.3 (о существовании и линейном представлении наибольшего общего делителя). Пусть числа a1, а2, ..., аk ∈ Z. Тогда существует наибольший общий делитель d этих чисел, при этом d = c1а1 + с2а2+...+ сkаk, где ci ∈ Z. Для вычисления наибольшего общего делителя двух целых чисел применяется способ повторного деления с остатком, называемый алгоритмом Евклида. Расширенный алгоритм Евклида помимо наибольшего общего делителя d чисел а и b находит его линейное представление, т.е. целые числа х и у, для которых выполняется равенство ах + bу = d. Алгоритм 1.1 (алгоритм Евклида). Вход. Целые числа а, b такие, что 0 < b ≤ а. Выход. d=НОД(а, b). Метод. 1. Пока b ≠ 0, выполнять следующие действия: 1.1. q ← [a/b]; r ← a— qb. 1.2. a ← b; b ← г. 2. Положить d ← а. 3. Результат: d. Сложность алгоритма Евклида равна 0{lоg3а}. Алгоритм 1.2 (расширенный алгоритм Евклида). Вход. Целые числа а, b такие, что 0 < b ≤ а. Выход. d=НОД(а,b); целые числа х, у такие, что d = ах + bу. Метод. 1. Положить A ← 1; B ← 0; C ← 0; D ← 1. 2. Пока b ≠ 0, выполнять следующие действия: 2.1. q ← [a/b]; r ← a— qb;x ← A— qC; y ← B— qD. 2.2. a ← b; b ← r, A ← C; C ← x; B ← D; D ← y. 3. Положить d ← a, x ← А; у ← В. 4. Результат: d, x, у. Алгоритм 1.3 (бинарный алгоритм Евклида). Вход. Целые числа a, b такие, что 0 < b ≤ а. Выход. d=HOД(a,b). Метод. 1. Положить g ← 1. 2. Пока а и b оба четные, выполнять а ← a/2; b ← b/2; g ← 2g до получения хотя бы одного нечетного значения а или b. 3. Положить и ← a; v ← b. 4. Пока и четное, выполнять и ← u/2. 5. Пока v четное, выполнять v ← v/2. 6. Если u ≥ v, то положить и ← u - v; иначе – положить v ← v - и. 7. Если и = 0, то положить d ← gv; иначе – вернуться на шаг 4. 8. Результат: d. Сложность бинарного алгоритма Евклида равна 0{log2a}. Алгоритм 1.4 (расширенный бинарный алгоритм Евклида). Вход. Целые числа a, b такие, что 0 < b ≤ а. Выход. d=HOД(a,b); целые числа х, у такие, что d = ax + by. Метод. 1. Положить g ← 1. 2. Пока a и b оба четные, выполнять а ← a/2; b ← b/2; g ← 2g до получения хотя бы одного нечетного значения а или b. 3. Положить и ← a; v ← b; А ← 1; В ← 0; С ← 0; D ← 1. 4. Пока и четное, выполнять следующие действия: 4.1. Положить и ← и/2. 4.2. Если А В 0 (mod 2), то положить А ← A/2; В ← B/2; иначе – положить А ← (А + b)/2; В ← (В— а) /2. 5. Пока v четное, выполнять следующие действия: 5.1 Положить v ← v/2. 5.2 Если С D 0 (mod 2), то положить С ← С/2; D ← D/2; иначе – положить С ← (С + b)/2; D ← (D - a)/2. 6. Если и ≥ v, то положить и ← и— v; А ← А— С; В ←В— D; иначе – положить v ← v — и; С ← С—A; D ← D— В. 7. Если и = 0, то положить d ← gv; х ← C; у ← D; иначе – вернуться на шаг 4. 8. Результат: d, х, у. Порядок выполнения работы 1. Написать программу, реализующую алгоритмы нахождения наибольшего общего делителя и его линейного представления, убедиться в ее работоспособности. 2. Сравнить время работы алгоритмов для различных входных данных: – для пар чисел из одного диапазона (отличающихся на один-два десятичных разряда); – для пар чисел из различных диапазонов (отличающихся на три и более десятичных разрядов); – в обоих случаях провести измерения для чисел как небольших, так и высоких порядков. 3. Обосновать полученные результаты. Содержание отчета 1. Постановка задачи. 2. Теоретические сведения. 3. Результаты работы, в том числе: – текст программы, реализующей приведенные выше алгоритмы; – примеры работы программ: наибольший общий делитель (для каждого алгоритма) и его линейное представление (для расширенных алгоритмов); – результаты исследования скорости работы алгоритмов для различных входных данных (на определенной аппаратной платформе). 4. Теоретическое обоснование полученных результатов. 5. Ответы на контрольные вопросы. 6. Выводы по работе. 7. Список использованной литературы. Контрольные вопросы 1. Предложите варианты оптимизации алгоритмов. 2. В каком случае обычный алгоритм Евклида может опережать бинарный? 3. Как влияет способ выбора чисел на результаты тестирования того или иного алгоритма? Рассмотреть диапазоны, из которых выбираются числа, вид этих чисел и фактор их случайности. 4. Предложите способы проверки быстродействия алгоритмов. 5. Является ли линейное представление наибольшего общего делителя двух чисел единственным и почему? Пример отчета 1. Постановка задачи формулируется с использованием данного руководства и уточняется преподавателем. 2. Теоретические сведения приводятся студентом самостоятельно с использованием данного руководства и указанной литературы. 3. Выполненная работа. В ходе работы был рассмотрен алгоритм Евклида нахождения наибольшего общего делителя, а также его модификации: бинарный алгоритм Евклида, расширенный алгоритм Евклида, бинарный расширенный алгоритм Евклида. Для проверки работоспособности и эффективности этих алгоритмов была написана программа на языке С (текст программы приводится студентом самостоятельно). Алгоритмы реализованы в виде подпрограмм, что позволяет тестировать как корректность их работы, так и быстродействие. Оценка скорости алгоритмов производилась с использованием библиотечной функции языка С для измерения времени совместно с различными искусственными способами замедления работы программы. Первый из них (тест 1) – многократное повторение вызова функции вычисления наибольшего общего делителя для одних и тех же входных данных. Тесты такого рода позволяют экспериментально установить зависимость скорости работы алгоритмов от вида входных данных (см. контрольный вопрос 3). Второй (тест 2) – вычисление наибольшего общего делителя всех комбинаций чисел из достаточно большого отрезка. Такой тест позволит получить более общие характеристики алгоритмов. (Возможно совмещение этих и подобных тестов быстродействия алгоритмов.) Примеры работы алгоритмов (анализ корректности)
Результаты тестирования алгоритмов на быстродействие (Репtiит 166, 80 Мб ОЗУ) Тест 1 (1 000 000 прогонов)
Внимание! Авторские права на книгу "Современные технологии информационной безопасности. Учебно-методический комплекс" ( Шаханова М.В. ) охраняются законодательством! |
||||||||||||||||||||||||||||||||||||||||||||||||||||
