Файл: Методы кодирования данных.pdf

3.4. Шифрование

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

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

Поставить между злоумышленником и данными в компьютере «логический» барьер, то есть проверять наличие прав на доступ к данным и блокировать доступ при отсутствии таких прав. Для этого применяются различные системы паролей, регистрация и идентификация пользователей, разграничение прав доступа и т. п. Практика показывает, что борьба между «хакерами» и разработчиками модулей защиты операционных систем идёт с переменным успехом.^[29]

Хранить данные таким образом, чтобы они могли «сами за себя постоять». Другими словами, так закодировать данные, чтобы, даже получив к ним доступ, злоумышленник не смог бы нанести ущерба.

Этот раздел посвящён обсуждению методов кодирования, применяемых в последнем случае.

Криптография.^[30]

Шифрование — это кодирование данных с целью защиты от несанкционированного доступа. Процесс кодирования сообщения называется шифрованием (или зашифровкой), а процесс декодирования — расшифровыванием (или расшифровкой). Само кодированное сообщение называется шифрованным (или просто шифровкой), а применяемый метод называется шифром.

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

Область знаний о методах создания и раскрытия шифров называется криптографией (или тайнописью).

Свойство шифра противостоять раскрытию называется криптостойкостью (или надёжностью) и обычно оценивается сложностью алгоритма дешифрации.

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

Криптография известна с глубокой древности и использует самые разнообразные шифры, как чисто информационные, так и механические. В настоящее время наибольшее практическое значение имеет защита данных в компьютере, поэтому далее рассматриваются программные шифры для сообщений в алфавите {0,1}.

Шифрование с помощью случайных чисел.

Пусть имеется датчик псевдослучайных чисел, работающий по некоторому определённому алгоритму. Часто используют следующий алгоритм:

T_i+1: =(а * Т_i+ b ) mod с,

где T_i — предыдущее псевдослучайное число, T_i+1 — следующее псевдослучайное число, а коэффициенты а, b, c - постоянны и хорошо известны. Обычно с = 2ⁿ, где n — разрядность процессора, a mod 4 = 1, а b — нечётное. В этом случае последовательность псевдослучайных чисел имеет период с.

Процесс шифрования определяется следующим образом. Шифруемое сообщение представляется в виде последовательности слов S₀,S₁,..., каждое длины n, которые поразрядно складываются по модулю 2 со словами последовательности T₀,T₁,..., то есть

C_i: = S_{i +2} T_i.

Последовательность Т₀, Т₁,... называется гаммой шифра.

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

S_i: = C_{i +2} T_i.

Ключом шифра является начальное значение Т₀, которое является секретным и должно быть известно только отправителю и получателю шифрованного сообщения.

Шифры, в которых для зашифровки и расшифровки используется один и тот же ключ, называются симметричными.

Если период последовательности псевдослучайных чисел достаточно велик, чтобы гамма шифра была длиннее сообщения, то дешифровать сообщение можно только подбором ключа. При увеличении п экспоненциально увеличивается криптостойкость шифра.^[31]

Этот очень простой и эффективный метод часто применяют «внутри» программных систем, например, для защиты данных на локальном диске. Для защиты данных, передаваемых по открытым каналам связи, особенно в случае многостороннего обмена сообщениями, этот метод применяют не так часто, поскольку возникают трудности с надёжной передачей секретного ключа многим пользователям.

Криптостойкость.

Описанный выше метод шифрования обладает существенным недостатком. Если известна хотя бы часть исходного сообщения, то всё сообщение может быть легко дешифровано. Действительно, пусть известно одно исходное слово S_i. Тогда

Т_i: = С_{i +2} S_i,

и далее вся правая часть гаммы шифра определяется по указанной формуле датчика псевдослучайных чисел.

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

Для повышения криптостойкости симметричных шифров применяют различные приёмы:

1. Вычисление гаммы шифра по ключу более сложным (или секретным) способом.

2. Применение вместо +2 более сложной (но обратимой) операции для вычисления шифровки.

3. Предварительное перемешивание битов исходного сообщения по фиксированному алгоритму.

Наиболее надёжным симметричным шифром считается DES (Data Encryption Standard), в котором используется сразу несколько методов повышения криптостойкости.

Модулярная арифметика.^[32]

Для объяснения метода шифрования с открытым ключом нужны некоторые факты из теории чисел, изложенные здесь без доказательств.

В этом подразделе рассматриваются только целые числа. Говорят, что число а сравнимо по модулю n с числом b (обозначение а = b mod n), если а и b при делении на n дают один и тот же остаток:

а = b mod n = a mod n = b mod n

В левой части этого определения слово mod является частью обозначения трехместного отношения, а в правой части слово mod является обозначением двухместной операции определения остатка от деления.

Отношение сравнимости рефлексивно, симметрично и транзитивно и является отношением эквивалентности. Классы эквивалентности по отношению сравнимости (по модулю n) называются вычетами (по модулю n). Множество вычетов по модулю n обозначается Z_n. Обычно из каждого вычета выбирают одного представителя — неотрицательное число, которое при делении на n дает частное 0. Это позволяет считать, что Z_n = {0,1,2,... ,n — 1}, и упростить обозначения. Над вычетами (по модулю n) определены операции сложения и умножения по модулю n, обозначаемые, соответственно, +n и -n и определяемые следующим образом:

a _+n b (а + b) mod n, a_*nb f (а * b) mod n.

Если из контекста ясно, что подразумеваются операции по модулю n, то индекс n опускается.

Легко видеть, что является абелевой группой, a — коммутативным кольцом с единицей.

Если n — простое число, то (Z_n; +„, -n) является полем.

Рассмотрим — подмножество множества вычетов Z_n, взаимно простых с n.

Числа а и b называются взаимно простыми, если их наибольший общий делитель равен 1.

Можно показать, что (;*n) — абелева группа. Таким образом, для элементов множества существуют обратные по умножению по модулю n.

Функция || называется функцией Эйлера.

Шифрование с открытым ключом.

В настоящее время широкое распространение получили шифры с открытым ключом. Эти шифры не являются симметричными — для зашифровки и расшифровки используются разные ключи. При этом ключ, используемый для зашифровки, является открытым (не секретным) и может быть сообщен всем желающим отправить шифрованное сообщение, а ключ, используемый для расшифровки, является закрытым и хранится в секрете получателем шифрованных сообщений. Даже знание всего зашифрованного сообщения и открытого ключа, с помощью которого оно было зашифровано, не позволяет дешифровать сообщение (без знания закрытого ключа).^[33]

Шифрование с открытым ключом производится следующим образом:

1. Получателем сообщений производится генерация открытого ключа (пара чисел n и e) и закрытого ключа (число d). Для этого

выбираются два простых числа, р и q;

вычисляется первая часть открытого ключа n:=pq;

определяется вторая часть открытого ключа — выбирается небольшое нечётное число е, взаимно простое с числом (р — l)(g — 1) (заметим, что (Р - 1)(9 - 1) = pq( 1 - 1 /р)(1 - l/q) = (n));

определяется закрытый ключ: d: = е^-1 mod (р — 1)(q — 1).

После чего открытый ключ (числа n и е) сообщается всем отправителям сообщений.

2. Отправитель шифрует сообщение (разбивая его, если нужно, на слова S_i длиной менее log₂ n разрядов):

C_i: = mod n,

и отправляет получателю.

3. Получатель расшифровывает сообщение с помощью закрытого ключа d:

P_i: = mod n.

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

В настоящее время известны эффективные алгоритмы определения простоты чисел, которые позволяют за несколько минут подобрать пару очень больших простых чисел (по 100 и больше цифр в десятичной записи). В то же время неизвестны эффективные алгоритмы разложения очень больших чисел на множители. Разложение на множители числа в 200 и больше цифр потребовало бы сотен лет работы самого лучшего суперкомпьютера. При практическом применении шифров с открытым ключом используют действительно большие простые числа (не менее 100 цифр в десятичной записи, а обычно значительно больше). В результате вскрыть этот шифр оказывается невозможно, если не существует эффективных алгоритмов разложения на множители (что очень вероятно, хотя и не доказано строго).

Цифровая подпись.^[34]

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

Заметим, что операции зашифровки и расшифровки, по существу, одинаковы, и различаются только показателем степени, а потому коммутируют:

М = (M^e)^d mod n = M^ed mod n = M^de mod n = (M^d)^e mod n = M.

Это обстоятельство позволяет применять различные приёмы, известные как цифровая (или электронная) подпись.

Рассмотрим следующую схему взаимодействия корреспондентов X и Y. Отправитель X кодирует сообщение S своим закрытым ключом (С: = mod п) и посылает получателю Y пару (S,C), то есть подписанное сообщение. ПолучательY, получив такое сообщение, кодирует подпись сообщения открытым ключом отправителя X, то есть вычисляет S' : — С^е mod п. Если оказывается, что S = S', то это означает, что (нешифрованное!) сообщение S действительно было отправлено корреспондентом X. Если же S ≠ S', то сообщение было искажено при передаче или фальсифицировано.

В подобного рода схемах возможны различные проблемы, которые носят уже не математический, а социальный характер. Например, допустим, что злоумышленник Z имеет техническую возможность контролировать всю входящую корреспонденцию получателя Y незаметно для последнего. Тогда, перехватив сообщение отправителя X, в котором сообщался открытый ключ е, злоумышленник Z может подменить открытый ключ отправителя X своим собственным открытым ключом. После этого злоумышленник сможет фальсифицировать все сообщения отправителя X, подписывая их своей цифровой подписью, и, таким образом, действовать от имени отправителя X. Другими словами, цифровая подпись удостоверяет, что сообщение S пришло из того же источника, из которого был получен открытый ключ е, но не более того.