Дискретная математика (998286), страница 33
Текст из файла (страница 33)
п. Такой подход надежен, но он затрудняет доступ к данным и легальным пользователям, а потому постепенно уходит в пропглое. в Поставить между злоумышленником н данными в компьютере логический барьер, то есть проверять наличие прав на доступ к данным и блокировать доступ при отсутствии таких прав. Для этого применяются различные системы паролей, регистрация и идентификация пользователей, разграничения прав доступа и т.
п. Практика показывает, что борьба между чхакерами» и модулями заШиты операционных систем идет с переменным успехом. М Хранить данные таким образом, чтобы они могли «сами за себя постоятык Другими словами, так закодировать данные, чтобы даже получив их, злоумышленник не смог бы нанести ушерба. Этот разлел посвящен обсуждению методов кодирования, применяемых в последнем случае.
161 6.5. Шифрование 6Л.1. Криптография Шифрование — это кодирование данных с целью защиты от несанкционирован- ного доступа. Процесс кодирования сообщения называется шифрованием (или зашифровкой), а процесс декодирования — расшифровыеаниеж (или расшифровкой). Само коди- рованное сообщение называется шифроеанньцв (или просто шифровкой), а при- меняемый метод называется шифром. Основное требование к шифру состоит в том, чтобы расшифровка (и, может быть, зашифровка) была возможна только при наличии санкции, то есть некото- рой дополнительной информации (или устройства), которая называется ключом шифра. Процесс декодирования шифровки без ключа называется дешифрованием (или дешифрацией, или просто раскрытием шифра)., Область знаний о шифрах, методах их создания и раскрытия называется шш- итографией (или тайнописью).
Свойство шифра противостоять раскрытию называется криптостойкостью (или надеясностью) и обычно измеряется сложностью алгоритма дешифрации. ОТСТУПЛЕНИЕ В практической криптографии криптостойкость шифра оценивается из экономических соображений.. Если раскрытие шифра стоит (в денежном выражении, включая необходимые компьютерные ресурсы, специальные устройства и т. и.) больше, чем сама зашифрованная информация, то шифр считается достаточно надежным. Криптография известна с глубокой древности и использует самые разнообразные шифры, как чисто ипформационные, так и механические.
В настоящее время наибольшее практическое значение имеет защита данных в компьютере, поэтому далее рассматриваются программные шифры для сообщений в алфавите (О, Ц. 6.5.2. Шифрование с помощью случайных чисел Пусть имеется датчик псевдослучайных чисел, работающий по некоторому опре- деленному алгоритму. Часто используют следующий алгоритм: Тг+1 . '=(о Т; + Ь) шод с, где Т, — предыдущее псевдослучайное число, Т,+, — следующее псевдослучайное число„а коэффициенты а, Ь, с постоянны и хорошр известны. Обычно с = 2", где п — разрядность процессора, а пюй 4 = 1, а Ь вЂ” нечетное (см.
)9)). В этом случае последовательность псевдослучайных чисел имеет период с (см. 19]). Процесс шифрования определяется следующим образом. Шнфруемое сообще- ние представляется в виде последовательности слов Яо, Я„..., каждое длины и, которые складываются по модулю 2 со словами последовательности То, Тг,..., то есть С;:=Я;еоТе. 182 Глава Б. Кодирование ЗАМЕЧАНИЕ Послецоззтельность Те, Тг,... называется ганкой Процесс расшифровывания заключается в том, чтобы еше раз сложить шифрованную последовательность с тай же самой гаммой шифра: Яе: = С; ® Т;. Ключом шифра является начальное значение То, которое является секретным н должно быть известно только отправителю и получателю шифрованного сообщения.
ЗАМЕЧАНИЕ Шифры, в которых лля зашифровки и расшифровки используется олин и тот же ключ, называются симметричными. Если период последовательности псевдослучайных чисел достаточно велик, чтобы гамма шифра была длиннее сообщения, то дешифровать сообщение можно только подбором ключа. При увеличении н зкспоненциально увеличивается криптостойкость шифра, ОТСТУПЛЕНИЕ Это очень простой и эффективный метод часто применяют езнутрн» программных систем, например, для защиты данных на локальном диске.
Для защиты данных, передаваемых по открытым каналам связи, особенно в случае многостороннего обмена сообщениями, этот метод применяют не так часто, поскольку возникают трудности с надежной передачей секретного ключа многим пользователям. 6.5.3. Криптостойкость Описанный в предыдущем подразделе метод шифрования обладает существенным недостатком. Если известна хотя бы часть исходного сообщения, то все сообщение может быть легко дешифровано.
Действительно, пусть известна одно исходное слово Еь Тогла Т;:=С; ее Ем и далее вся правая часть гаммы шифра определяется по укаэанной формуле датчика псевдослучайных чисел. ЗАМЕЧАНИЕ На практике часть сообщения вполне может быть известна злоумышленнику. Например, многие текстовые редакторы помещают в начало файла документа одну и ту же служебную информацию. Если злоумышленнику известно, что исходное сообщение подготовлено в данном редакторе, то он сможет легко дешифровать сообщение. Для повышения криптостойкости симметричных шифров применяют различные приемы; 183 бэп Шифрование Е вычисление гаммы шифра по ключу более сложным (или секретным) способом; 2.
применение вместо еэ более сложной (но обратимой) операции для вычисления шифровки„ 3. предварительное перемешивание битов исходного сообщения цо фиксированному алгоритму. Наиболее надежным симметричным шифром считается гзЕБ (Раса Епсгураоп Ягапдагд), в котором используется сразу несколько методов повышения криптостойкости. В настоящее время широкое распространение получили шифры с открытым ключом. Эти шифры не являются симметричными — ' для зашифровки и расшифровки используются разные ключи. При этом ключ, используемый для зашифровки, является открытым (не секретным) и может быть сообщен всем желающим отправить шифрованное сообщение, а ключ, используемый для расшифровки, является закрытым и хранится В секрете получателем шифрованных сообщений.
Даже знание всего зашифрованного сообщения и открытого ключа, с помощью которого оно было зашифровано, не позволяет дешифровать сообщение (без знания закрытого ключа). Для описания метода шифрования с открытым ключом нужны некоторые факты из теории чисел, изложенные (без доказательств) в следующем подразделе. 6.5.4.
Модулярная арифметика В этом подразделе все числа целые. Говорят, что число а сравнимо по модули п с числом Ь (обозначение: а = 6 (гаод и)), если а и Ь при деленян на п дают один и тот же остаток; а = 6 (шод п):=апгойп = Ьшод и. Отношение сравнимости рефлексивно, симметрично и транзитивно и является отношением эквивалентности.
Классы эквивалентности по отношению сравни- мости (по модулю и) называются вычетами (по модулю и). Множество вычетов по модулю п обозначается ю„. Обычно из каждого вычета выбирают одного представителя — неотрицательное число, которое при делении на п дает частное О. Это позволяет считать, что Е„= (0,1,2,...,п — Ц, и упростить обозначения.
Над вычетами (по модулю и) определены операции сложения и умножения по модулю и, обозначаемые, соответственно, +„и .„и определйемые 'следующим образом: а+„Ь:=(а+ Ь) пюд и, а.„Ь: =(а ° 6) пюд и. ЗАМЕЧАНИЕ Если из контекста ясно, что подразумеваются операции по модулю п, то индекс в опускается. Легко видеть, что (К„;+„) образует абелеву группу, а (Е„;+„, „) — коммутатив- ное кольцо с единицей, 184 Глава 6. Кодирование рассмотрим Ж„' — подмножество Ж„чисел, взаимно простыл с п ЗАМЕЧАНИЕ Числа о н Ь называются взаимно простыми, если нх наибольший общий делитель равен 1,. Можно показать, что (Ж„"; „) — абелева группа.
Таким образом, для чисел из множества Я„' существуют обратные по умножению по модулю п. ЗАМЕЧАНИЕ Если и — простое число, то (Е„', +„, „) является полем. Функция Р(п):= (Ж„'( называется функцией Эйлера. ЗАМЕЧАНИЕ Если р — простое число, то Р(р) = р — 1, и вообще, Р(п) < п. Можно показать, что (в(п)=п 1 — — ...
1 —— где ры..., рь — все простые делители п. Имеет место следующая теорема. ТЕОРЕМА (Эйлера) Если п > 1, то Уа б Е„' аи(") ьз 1 (тпоб и). Отсюда непосредственно выводима ТЕОРЕМА (маяая теорема Ферма) Если р > 1 — простое число, то 'ч'а б Ж" аа ав 1 (щос1 р). Имеет место следующее утверждение. ТЕОРЕМА Если числа пм..., иь попарно взаимно простыв, число п = птпз... пь — ил произведение, х и а — целые числа, то ища (шоб п) е=ь'ч'г' б 1..)с льва (шоб п);.
ЗАМЕЧАНИЕ Последнее утверждение является следствием теоремы, которая известна как екнтайская теорема об остаткахь. 185 ЕВ. Шифрование 6.5.5. ШиФрование с открытым ключом Шифрование с открытым ключом производится следующим образом. 1. Получателем сообщений производится генерация открытого ключа (пара чисел и и е) и закрытого ключа (число д). Для этого: ь выбираются два простых числа р и д; М определяется первая часть открытого ключа и: =щ; ь определяется вторая часть открытого ключа — выбирается небольшое нечетное число е, взаимно простое с числом (р — 1)(д — 1) (заметнм, что (р - 1)(д - 1) = рд(1 — 1/р)(1 - 1~у) = р(п))' ы определяется закрытый ключ: Ы: = е ' шод ((р — 1)(у — 1)).
После чего открытый ключ (числа и и е) сообщается всем отправителям сообщений. 2. Отправитель шифрует сообщение (разбивая его, если нужно, на слова Яз длиной менее 1оязп разрядов): С;: =(Яз)' шод и и отправляет получателю; 3. Получатель расшифровывает сообщение с помощью закрытого ключа И; Р;: =(С;)в шод и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
