Генераторы случайных последовательностей
Введение Среди способов защиты информации наиболее важным считается криптографический. Он предусматривает такое преобразование информации, при котором она становится доступной для прочтения лишь обладателю некоторого секретного параметра (ключа). В последние годы область применения криптографии значительно расширилась. Ее стали повседневно использовать многие организации, коммерческие фирмы, частные лица. При этом законного пользователя того или иного криптографического средства, прежде всего беспокоит его надежность. Одним из способов оценки надежности является попытка «взлома», т.е. получение доступа к информации без знания ключа. Подобные задачи призвано решать смежное научное направление, называемое криптоанализом. Криптоанализ и криптография объединены общим названием – криптология. Вводная лекция. Защита информации – это всевозможные средства и функции, обеспечивающие доступность, конфиденциальность или целостность информации или связи, исключая средства и функции, предохраняющие от неисправностей. Защита информации включает в себя криптографию, криптоанализ, защиту от собственного излучения и защиту (компьютера) от несанкционированного доступа. Криптография – это раздел прикладной математики, изучающий модели, методы, алгоритмы, программные и аппаратные средства преобразования информации (шифрования) в целях сокрытия ее содержания, предотвращения видоизменения или несанкционированного использования. Криптосистема – это система, реализованная программно, аппаратно или программно-аппаратно и осуществляющая криптографическое преобразование информации. Криптоанализ – это раздел прикладной математики, изучающей модели, методы, алгоритмы, программные и аппаратные средства анализа криптосистемы или ее входных и выходных сигналов с целью извлечения конфиденциальных параметров, включая открытый текст. Из данных определений видно, что криптоанализ занимается задачами, которые в математическом смысле обратные задачи криптографии. Система криптографии и криптоанализа образует новую науку – криптологию. В развитии криптологии принято выделять три этапа. Первый этап. (С древних времен до 1949г). Этот этап характеризуется частными, узкоспециальными и вычислительно простыми алгоритмами криптографии и криптоанализа без использования компьютеров. Его часто называют этапом до компьютерной криптографии. Второй этап. (1949-1976гг.) Этот этап принято отсчитывать с момента публикации американского математика-прикладника К. Шеннона «Теория связи в секретных системах». В этот период принято активно проводились систематические исследования по криптологии с использованием компьютера. Криптология становится математической наукой. Третий этап. (1976г. – настоящее время). Этот этап можно назвать и «эрой открытой криптологии». Этот этап принято отсчитывать с момента публикации работы американских математиков У.Дифори, М.Хеллмана «Новые направления в криптографии».В этой работе было показано, что «секретная» передача информации возможна (вотличие от результатов Шеннона) без предварительной передачи «секретного ключа». Главной особенностью этого этапа становится массовое применение криптографии в банковском деле, электронной торговле, компьютерных сетях и других сферах жизнедеятельности. Современная криптология широко использует теорию вероятностей, математическую статистику, алгебру, теорию чисел и теорию алгоритмов. Некоторые определения и формулы. В криптологии общеприняты следующие понятия: · Пространство сообщений · Пространство ключей · Пространство зашифрованных сообщений Остается уточнить понятие текста. При этом обычно фиксируют некоторую сумму символов, называемую алфавита. Это может быть английский, русский или какой-нибудь другой алфавит. Часто в качестве алфавита используются натуральные числа или символы 0 и 1. Словом называется упорядоченный набор букв данного алфавита. Множество слов обозначают через Арифметические основы Основные обозначения.
Простые числа. Натуральное число Взаимно простые числа. Два целых числа Наибольший общий делитель. Всякое целое, делящее числа Алгоритм Евклида. Способ нахождения наибольшего общего делителя двух целых Для случая положительных чисел
(где все
Последний положительный остаток /Пример/
Найдем НОД (175,77). 175=77*2+21; 77=21*3+14; 21=14*1+7; 14-7*2.
Последний положительный остаток равен 7. Следовательно (175,77)=7. Наименьшее общее кратное. Всякое целое, кратное всех данных чисел, называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным (НОК) и обозначается Классы вычетов. Числа, сравнимые по модулю Функция Эйлера. Арифметическая функция Сравнения. Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное число
это читается следующим образом: *Доказательство*
Из
( откуда
Обратно, из
выводим
т.е.
Сравнимость чисел Свойства сравнений. 1. Два числа, сравнимые с третьим, сравнимы между собой. 2. Сравнения можно почленно складывать. 3. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, переменив знак на обратный. 4. Сравнения можно почленно перемножать. 5. Обе части сравнения можно возвести в одну и ту же степень. 6. Обе части сравнения можно умножить на одно и то же целое число. 7. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем. 8. Обе части сравнения и модуль можно умножить на одно и то же целое. 9. Обе части сравнения и модуль можно разделить любой их общий делитель. 10. Если сравнение 11. Если сравнение имеет место по модулю 12. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число. Первообразные корни. При Если Если Пусть Символ Лежандра. Функция чисел
Символ Якоби. Символ Якоби является обобщением символа Лежандра и служит для упрощения вычисления последнего. Пусть
Цепные дроби. Цепная дробь – один из важнейших способов представления чисел и функций. Цепная дробь есть выражение вида
где Алгебраические основы Понятие группы. Группой называется непустое множество 1). Операция * ассоциативна, т.е. для любых
2). В G имеется единичный элемент (или единица) e такой, что для любого
3). Для каждого a Î G существует обратный элемент
4). Для любых
Если дополнительно группа удовлетворяет четвертой аксиоме, то группа называется абелевой или коммутативной. Множество Через Если взять все классы вычетов, взаимно простые с модулем m, и определить их умножение по модулю m, то получится группа, обозначаемая через Группа Циклическими являются группы Циклическая группа всегда коммутативна. Подгруппы групп. Подмножество Подгруппы группы Гамоморфизмы групп. Отображение Кольца и поля. Кольцом называется множество 1). 2). Операция умножения ассоциативна, т.е. для всех 3). Выполняются законы дистрибутивности, т.е. для всех
Подкольца. Подмножество Гомоморфизмы колец. Пусть
Генераторы случайных последовательностей
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... ![]() ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (229)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |