53
Введение
Среди способов защиты информации наиболее важным считается криптографический. Он предусматривает такое преобразование информации, при котором она становится доступной для прочтения лишь обладателю некоторого секретного параметра (ключа). В последние годы область применения криптографии значительно расширилась. Ее стали повседневно использовать многие организации, коммерческие фирмы, частные лица. При этом законного пользователя того или иного криптографического средства, прежде всего беспокоит его надежность. Одним из способов оценки надежности является попытка «взлома», т.е. получение доступа к информации без знания ключа. Подобные задачи призвано решать смежное научное направление, называемое криптоанализом. Криптоанализ и криптография объединены общим названием - криптология.
Вводная лекция.
Защита информации - это всевозможные средства и функции, обеспечивающие доступность, конфиденциальность или целостность информации или связи, исключая средства и функции, предохраняющие от неисправностей. Защита информации включает в себя криптографию, криптоанализ, защиту от собственного излучения и защиту (компьютера) от несанкционированного доступа.
Криптография - это раздел прикладной математики, изучающий модели, методы, алгоритмы, программные и аппаратные средства преобразования информации (шифрования) в целях сокрытия ее содержания, предотвращения видоизменения или несанкционированного использования.
Криптосистема - это система, реализованная программно, аппаратно или программно-аппаратно и осуществляющая криптографическое преобразование информации.
Криптоанализ - это раздел прикладной математики, изучающей модели, методы, алгоритмы, программные и аппаратные средства анализа криптосистемы или ее входных и выходных сигналов с целью извлечения конфиденциальных параметров, включая открытый текст.
Из данных определений видно, что криптоанализ занимается задачами, которые в математическом смысле обратные задачи криптографии. Система криптографии и криптоанализа образует новую науку - криптологию.
В развитии криптологии принято выделять три этапа.
Первый этап. (С древних времен до 1949г). Этот этап характеризуется частными, узкоспециальными и вычислительно простыми алгоритмами криптографии и криптоанализа без использования компьютеров. Его часто называют этапом до компьютерной криптографии.
Второй этап. (1949-1976гг.) Этот этап принято отсчитывать с момента публикации американского математика-прикладника К. Шеннона «Теория связи в секретных системах». В этот период принято активно проводились систематические исследования по криптологии с использованием компьютера. Криптология становится математической наукой.
Третий этап. (1976г. - настоящее время). Этот этап можно назвать и «эрой открытой криптологии». Этот этап принято отсчитывать с момента публикации работы американских математиков У.Дифори, М.Хеллмана «Новые направления в криптографии».В этой работе было показано, что «секретная» передача информации возможна (вотличие от результатов Шеннона) без предварительной передачи «секретного ключа».
Главной особенностью этого этапа становится массовое применение криптографии в банковском деле, электронной торговле, компьютерных сетях и других сферах жизнедеятельности.
Современная криптология широко использует теорию вероятностей, математическую статистику, алгебру, теорию чисел и теорию алгоритмов.
Некоторые определения и формулы.
В криптологии общеприняты следующие понятия:
· Пространство сообщений - множество всевозможных сообщений . Для сообщений используется также обозначение .
· Пространство ключей . Каждый ключ к определяет некоторую подстановку на пространство и обратное преобразование .
· Пространство зашифрованных сообщений , состоящее из зашифрованных . Используется также обозначение
Остается уточнить понятие текста. При этом обычно фиксируют некоторую сумму символов, называемую алфавита. Это может быть английский, русский или какой-нибудь другой алфавит. Часто в качестве алфавита используются натуральные числа или символы 0 и 1. Словом называется упорядоченный набор букв данного алфавита. Множество слов обозначают через . Текст набор слов.
1. Арифметические основы
Основные обозначения.
- множество вещественных (действительных) чисел. Вещественное число - любое положительное число, отрицательное число, или нуль.
- множество натуральных чисел.
- множество целых чисел.
- множество комплексных чисел. Комплексное число - число вида , где и - действительные числа, а - т.н. мнимая единица, т.е. число, квадрат которого равен -1.
- множество рациональных чисел. Рациональное число - число, которое может быть представлено в виде дроби , где и - целые числа ().
Простые числа. Натуральное число > 1 называется простым, если оно не имеет других натуральных делителей, кроме 1 и . Простым числом будет наименьший, отличный от единицы делитель целого числа , >1. Простых чисел бесконечно много.
Взаимно простые числа. Два целых числа и будут взаимно простыми тогда и только тогда, когда найдутся и , такие что .
Наибольший общий делитель. Всякое целое, делящее числа и , называется их общим делителем. Наибольший из общих делителей для чисел и называется наибольшим общим делителем (НОД) и обозначается Ввиду конечности числа делителей одного числа существование и единственность наибольшего общего делителя очевидны. Если то числа и называются взаимно простыми.
Алгоритм Евклида. Способ нахождения наибольшего общего делителя двух целых Для случая положительных чисел и , причем этот способ состоит в следующем. Деление с остатком числа на число приводит к результату где частное является целым положительным числом, а остаток - либо 0, либо положительное число, меньше , Производится последовательное деление:
(2.1)
(где все -положительные целые числа и ) до тех пор, пока не получится остаток, равный 0. Этот последний остаток можно не писать, так что ряд равенств (2.1) закончится следующим образом:
(2.2)
Последний положительный остаток в этом процессе и является наибольшим общим делителем чисел и .
/Пример/
Найдем НОД (175,77).
175=77*2+21;
77=21*3+14;
21=14*1+7;
14-7*2.
Последний положительный остаток равен 7. Следовательно (175,77)=7.
Наименьшее общее кратное. Всякое целое, кратное всех данных чисел, называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным (НОК) и обозначается .
Классы вычетов. Числа, сравнимые по модулю , образуют класс вычетов по модулю . Все числа из одного класса имеют один и тот же остаток от деления на . Любое число из класса вычетов называется вычетом по модулю .Соответствующий класс обозначается через . Поскольку соотношение является бинарным отношением эквивалентности, то имеем разбиение целых чисел на классы эквивалентности (классы вычетов). Всего имеется классов вычетов по модулю : .
Функция Эйлера. Арифметическая функция , значение которой равно количеству положительных целых чисел, не превосходящих и взаимно простых с .
Сравнения. Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное число . Каждому целому числу отвечает определенный остаток от деления его на ; если двум целым и отвечает один и тот же остаток , то они называются равностаточными по модулю или сравнимыми по модулю . Сравнимость чисел и по модулю записывается так:
(2.3)
это читается следующим образом: сравнимо с по модулю .
*Доказательство*
Из следует, что
( - остаток от деления на , - неполное частное)
откуда
Обратно, из представляя в виде
выводим
т.е.
. ?
Сравнимость чисел и по модулю равносильна: возможности представить в виде , где - целое.
Свойства сравнений.
1. Два числа, сравнимые с третьим, сравнимы между собой.
2. Сравнения можно почленно складывать.
3. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, переменив знак на обратный.
4. Сравнения можно почленно перемножать.
5. Обе части сравнения можно возвести в одну и ту же степень.
6. Обе части сравнения можно умножить на одно и то же целое число.
7. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
8. Обе части сравнения и модуль можно умножить на одно и то же целое.
9. Обе части сравнения и модуль можно разделить любой их общий делитель.
10. Если сравнение имеет место по нескольким модулям, то оно имеет место и по модулю, равному общему наименьшему кратному этих модулей.
11. Если сравнение имеет место по модулю , то оно имеет место и по модулю , равному любому делителю числа .
12. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.
Первообразные корни. При существуют положительные с условием , например (теорема Эйлера) .Наименьшее из них называется: показатель, которому принадлежит по модулю .
Если по модулю принадлежит показателю , то числа по модулю несравнимы.
Если по модулю принадлежит показателю , то тогда и только тогда, когда в частности (при ), , тогда и только тогда, когда делится на .
Страницы: 1, 2, 3, 4, 5, 6
