4885

УДК 004.056.5

Чевычелов Ю.А.

Информационная безопасность и защита информации [Текст]: Методические указания к выполнению лабораторных работ для студентов направления подготовки 09.03.02 - Информационные системы и технологии./ Ю.А. Чевычелов; М-во образования и науки РФ ФГОБУ ВО «ВГЛТУ» им. Г.Ф.Морозова. Воронеж. 2015

Указания содержат методический материал к выполнению лабораторных работ по дисциплине «Информационная безопасность т защита информации». Защиту информации в настоящее время необходимо рассматривать как часть интегрированной системы безопасности. Актуальность вопросов защиты информации обусловлена двумя обстоятельствами: первое – современные системы охранной безопасности, применяемые для противодействия проникновениям на объекты собственности являются сложными информационнотелекоммуникационными системами, базирующимися на современных информационных технологиях; второе – информация, хранящаяся и обрабатываемая в информационных системах, также является объектом охраны.

Рецензент К.Т.Н Яньков Е.И.

Лабораторная работа 1

Тема: Простые числа.

исло — основное понятие математики, используемое для количественной характеристики, сравнения, нумерации объектов и их частей. Письменными знаками для обозначения чисел служат цифры, а также символы математических операций. Возникнув ещѐ в первобытном обществе из потребностей счѐта, понятие числа с развитием науки значительно расширилось.

Натуральные числа, получаемые при естественном счѐте; множество натуральных чисел обозначается . То есть (иногда к множеству натуральных чисел также относят ноль, то есть . Натуральные числа замкнуты относительно сложения и умножения (но не вычитания или деления). Сложение и умножение натуральных чисел коммутативны и ассоциативны, а умножение натуральных чисел дистрибутивно относительно сложения и вычитания.

Важным подмножеством натуральных чисел являются простые числа Простое число — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и самого себя. Все остальные натуральные числа, кроме единицы, называются составными. Ряд простых чисел начинается так:P = { } Любое натуральное число, большее единицы, представимо в виде произведения степеней простых чисел, причѐм единственным способом с точностью до порядка следования сомножителей. Например,

Целые числа, получаемые объединением натуральных чисел с множеством чисел противоположных натуральным и нулѐм, обозначаются . Любое целое число можно представить как разность двух натуральных. Целые числа замкнуты относительно сложения, вычитания и умножения (но не деления). Такая алгебраическая структура называется кольцом.

Рациональные числа — числа, представимые в виде дроби m/n (n ≠ 0), где m — целое число, а n — натуральное число. Рациональные числа замкнуты уже относительно всех четырѐх арифметических действий: сложения, вычитания, умножения и деления (кроме деления на ноль). Для обозначения рациональных чисел используется знак (от англ. quotient).

Действительные (вещественные) числа представляют собой расши-

рение множества рациональных чисел, замкнутое относительно некоторых (важных для математического анализа) операций предельного перехода. Множество вещественных чисел обозначается .. Кроме рациональных чисел, включает множество иррациональных чисел , не представимых в виде отношения целых.

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причѐм единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа — элементарные «строительные блоки» натуральных чисел.

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема RSA и некоторые другие.

Большие простые числа (порядка) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел. Понятия «замкнутое множество» и «не-

замкнутое множество» обычно используют относительно множеств чисел и операций над ними.

Если над двумя элементами одного множества выполняется какая-либо арифметическая операция, и полученный результат также принадлежит этому множеству, то говорится, что это множество замкнуто относительно данной операции.

Если же результат арифметической операции над элементами множества не принадлежит этому множеству, то говорят, что данное множество незамкнуто относительно данной операции. Множество натуральных чисел (N) замкнуто относительно операций сложения и умножения, так как какие бы мы не взяли натуральные числа, перемножив их или сложив, всегда получим натуральное число.

Однако множество натуральных чисел не замкнуто относительно операций вычитания и деления. Например, если вычесть из меньшего числа большее, то получится отрицательное число, которое не принадлежит N. При делении может быть получено дробное число, которое также не принадлежит N. Если же говорить о множестве целых чисел (Z), то оно будет замкнуто уже относительно операций сложения, умножения и вычитания. Натуральные и целые числа замкнуты также относительно возведения в натуральную степень.

Множество действительных чисел (R) замкнуто относительно всех операций. В случае конкретных числовых промежутков множество может оказаться не замкнутым.

Алгоритмы нахождения простых чисел.

Задача 1

Составить программу, которая будет проверять, является ли введенное число простым. Самый простой путь решения этой задачи - проверить, имеет ли данное число n (n > 2) делители в интервале [2; n-1]. Если делители есть, число n - составное, если - нет, то - простое. При реализации алгорит-

ма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Ввести логическую переменную flag, в программе выступаете в роли "флаговой" переменной и повышает наглядность программы, так, если flag = true, то n -простое число; если у числа n есть делители, то "флаг выключается" с помощью оператора присваивания flag:=false, таким образом, если flag = false, то n - составное число.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество. Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, - простое оно или нет. Однако для этого машине пришлось бы потратить много времени. подумать, каким образом можно оптимизировать алгоритм, описанный в задаче 1. При реализации решения выполнять следующие действия:

1.рассматривать только нечетные числа;

2.использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;

3.прерывать работу цикла, реализующего поиск делителей числа, при

нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

4.Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, увеличивать k на 1, Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке.

НОД(a,n)=1

Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида. Эвклид описал этот алгоритм в своей книге, Элементы, написанной в 300 году до нашей эры. Он не изобрел его. Историки считают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации y на языке С:

/* возвращает НОД(gcd) x и у */

int gcd (int x, int у)

{

int g;

if (x < 0) x = -x;

if (y < 0) у = -у;

if (x + у == 0

ERROR;

g=y;

While (x>0){ q=x;

x=y % x; y=q;

}

return q;

}

Задача 3 Используя алгоритм Евклида найти простые чис-

ла при N = 150,...

Вотчете по лабораторной работе должно содержаться:

1.Титульный лист в соответствии со стандартом оформления титульного листа работы..

2.Задание на лабораторную работу.

3.Краткую теорию.

4.Ход выполнения работы: алгоритмы, программное обеспечение (исходный код

5.Результаты тестирования.

6.Вил формы приложения.

7. Выводы.

Лабораторная работа 2 1. ВЗАИМНОПРОСТЫЕ ЧИСЛА

Два числа называются взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, если наибольший общий делитель а и n равен 1. Это записывается как:

НОД(а,n)=1

Примеры:

14 и 25 взаимно просты — у них нет общих делителей.

15 и 25 не взаимно просты (у них имеется общий делитель 5).

6, 8, 9 взаимно просты — у них нет делителей, общих для всех трѐх чисел. Для указания взаимной простоты чисел и используется обозначение:

словесная формулировка или эквивалентная запись , что означает: «наибольший общий делитель чисел a и b равен 1».

Если в наборе чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми. Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.

8, 15 — не простые, но взаимно простые.

6, 8, 9 — взаимно простые числа, но не попарно взаимно простые. 8, 15, 49 — попарно взаимно простые.

Числа a и b взаимно просты тогда и только тогда, когда выполняется одно из эквивалентных условий:

Наибольший общий делитель a и b равен единице;

Существуют целые x и y такие, что (соотношение Безу);

Любые два (различных) простых числа взаимно просты;

Если a — делитель произведения bc, и a взаимно просто с b, то a — делитель c.

Если числа a1,…, an — попарно взаимно простые числа, то НОК(a1, …, an) = |a1·…·an|. Например, НОК

2.Нахождение взаимно простых чисел

При решении задач криптографии (алгоритм RSA) предполагается нахождение числа d взаимно простое с m. Число d должно быть меньше m. Для нахождения взаимно простых чисел используется алгоритм Евклида который находит наибольший общий делитель двух чисел. Если найденный делитель больше единицы, то необходимо выбрать другое число d и повторить попытку. При вычислении наибольшего делителя с помощью алгоритма Евклида будет выполнено не более 5*p, операций деления с остатком, где p есть количество цифр в десятичной записи наименьшего из чисел a и b.

3.Решение уравнения вида a*x + b*y = 1

При решении задач криптографии (алгоритм RSA) предполагается нахождение такого числа e чтобы e*d = 1(mod m). Для решения этого уравнения нужно использовать модифицированный алгоритм Евклида, который работает, если числа d и m взаимно простые числа. Вычисление числа e сводится к решению уравнения m*x + d*e = 1 в натуральных числах. Число х не существенно.

Задание на выполнение работы

1.Реализовать алгоритм формирования массива взаимно простых чисел.

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

Программное обеспечение вывести в файл.

2. Создать программу реализующую решение уравнения m*х + d*e = 1 на базе модифицированного алгоритма Евклида.

Должна быть обеспечена наглядность выполнения алгоритма. Для создания программного обеспечения и подтверждения его работоспособности тестирование проводить не менее чем на 10 различных наборах данных.

Вотчете по лабораторной работе должно содержаться:

8.Титульный лист в соответствии со стандартом оформления титульного листа работы..

9.Задание на лабораторную работу.

10.Краткую теорию.

11.Ход выполнения работы: алгоритмы, программное обеспечение (исходный код 12.Результаты тестирования.

13.Вил формы приложения.

14. Выводы.