Математические методы защиты информации: Методические указания (90,00 руб.)

Стр.1

Стр.2

Стр.3

Стр.4

Стр.5

Министерство образования и науки Российской Федерации Ярославский государственный университет им. П.Г. Демидова Кафедра компьютерных сетей Математические методы защиты информации Методические указания Ярославль 2004 1

Стр.1

ББК В 311 М 33 УДК 519.6 Составитель М.В. Краснов Математические методы защиты информации: Метод. указания / Сост. М.В. Краснов; Яросл. гос. ун-т. – Ярославль, 2004. – 27 с. В работе сформулированы основные идеи алгоритмов с открытым ключом. Наиболее известные из них подробно описаны. Особое внимание уделено электронной цифровой подписи как решению задач, связанных с аутентификацией документов. Указания предназначены для студентов, обучающихся по направлению 510200 Прикладная математика и информатика (дисциплина "Математические методы защиты информации", блок СД), очной формы обучения. Рецензент: кафедра компьютерных сетей Ярославского государственного университета им. П.Г. Демидова; д-р физ.-мат. наук Л.С. Казарин. © Ярославский государственный университет, 2004 © Краснов М.В., 2004 2

Стр.2

В настоящее время использование электронной вычислительной техники в различных областях человеческой деятельности все более и более возрастает. Однако чаще всего вычислительная техника используется для хранения и передачи информации. Естественно, возникает задача защиты информации от несанкционированного использования. Среди способов защиты информации одним из наиболее распространенных методов является криптографический метод. Он предусматривает такое преобразование информации, при котором она становится доступной для прочтения лишь обладателю некоторого секретного параметра (ключа). Опишем задачу защиты информации с помощью криптографического метода. Отправитель хочет послать получателю по каналу, который не является безопасным, текст Т. Взломщик хочет перехватить передаваемую информацию. Отправителю нужно так послать сообщение, чтобы взломщик не смог прочитать исходный текст Т из перехваченного сообщения, а получатель мог бы за приемлемое время восстановить исходный текст из полученного сообщения. Чтобы решить поставленную задачу, отправитель шифрует исходный текст Т с помощью некоторого преобразования Ek , где k – ключ шифрования. Шифр-текст С = Еk(T) передается по каналу связи. Получатель должен уметь расшифровать шифр-текст – восстаногде k вить исходный текст Т с помощью некоторого преобразования Dk ~ - ключ расшифрования: = ~ ( ). Если отправитель знает ключ k, то он может зашифровывать информацию; если получатель знает ключ ,~ ключ ,~ то он может расшифровывать сообщение. Перед взломщиком стоит более сложная задача: он должен найти или свой способ дешифровки. Алгоритмы, используемые в современных криптосистемах, можно разделить на два типа: ♦ симметричные, в которых ключ расшифрования легко находится по ключу шифрования; ♦ с открытым ключом, в которых ключ расшифрования трудно найти даже при известном ключе зашифрования. В представленных методических указаниях основное внимание уделяется алгоритмам с открытым ключом. 3 ~ , T DC k k k

Стр.3

Алгоритм Евклида Пусть , – целые числа, однозначно определенные Элементы теории чисел ≥1 , , Z∈ , что = + , 0 ≤ < . Величину r (остаток от деления) будем обозначать = m .od общим делителем. Наибольший из общих делителей для чисел а и b называется наибольшим общим делителем и обозначается Всякое целое, делящее числа a и b без остатка, называется их НО ( , ).baД что Утверждение. Для любых + = ( , ). Напомним обобщенный алгоритм Евклида, который находит как наибольший общий делитель d НО ( , )baД= a b∈Z , b ≥1, так и числа , утверждения. Вход алгоритма Выход алгоритма , Z∈ . = 1. [Инициализация] :  =     ; 0 : 1; x y∈ Z, ( , ), 1 : 0; = , ∈Z. Алгоритм Вводим четыре дополнительных переменных = 0 : 0; = 2. [Основной цикл] Пока := − := − * ; 0 := 1; := ; 0 1 1 := ; } 3. [ Выход ] Вернуть Алгоритм завершен. := ; := − * ; 0 1 0 := 1; := ; 1 := ; := 0; 4 := 0 1 : 1 . 0 , = > 0 , выполнять следующий цикл{ ; 1, 0 , 1∈Z . двух целых чисел из сформулированного , ∈ Z существуют , ∈ Z такие, тогда существуют такие b r b a a b qb r ab a ab b a r q ab a b b x x r x x y qb y y y r qr axby НО Д ab НОДab d x qy y y qx x x d a x y x xy y x y xxyy y b xy

Стр.4

Пример. Найти числа x и y такие, что Итерация 0 1 2 3 4 5 6 - 0 1 1 3 1 3 Простые числа Натуральное число 342 612 342 270 72 54 18 612 342 270 72 54 18 0 Получаем 18=342*9+612*(-5). p ≥ 2 называется простым, если оно не имеет других натуральных делителей, кроме 1 и p. Утверждение. Существует бесконечно много простых чисел. Два целых числа a и b называются взаимно простыми, если ( , ) 1 .= Определение. Функцией Эйлера ( )a называется количество целых чисел на отрезке [1, , взаимно простых с a. , Утверждения: 1) ( ) 2) если 3) если = 1 ] = −1, если p - простое число; ( , ) 1 ,= 1 .... = 4) если p – простое число, то ( )= − −1, N∈     , то ( ) ∏1 1  =1 то ( )= ( ) ( );  −  ; . Вычеты Рассмотрим кольцо nZ по модулю n (остатков от деления на n). Операции сложения и умножения выполняются по m .od Если НО ( , ) 1 ,≠naД то элемент противном случае элемент найти, используя обобщенный алгоритм Евклида. 5 ∈Z не имеет обратного, в ∈Z имеет обратный, который можно 1 0 1 -1 2 -7 9 = Рассмотрим обобщенный алгоритм Евклида. 0 (342,612) = + 1 0 1 -1 2 -7 9 -34 0 0 1 0 1 -1 4 -5 1 1 0 1 -1 4 -5 19 . ax НО d Д by k p k НОДab φ НОДab p k p k y y x x b a q φ a φ p φp n pk ek p e n a ab φ φ n n a a k φ b pi n i n

Стр.5