[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

Шифрование

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

• Поставить между злоумышленником и данными в компьютере непреодолимый барьер, то есть исключить саму возможность доступа к данным путем физической изоляции компьютера с данными, применения аппаратных ключей защиты и т. п. Такой подход надежен, но он затрудняет доступ к данным и легальным пользователям, а потому постепенно уходит в прошлое.
• Поставить между злоумышленником и данными в компьютере логический барьер, то есть проверять наличие прав на доступ к данным и блокировать доступ при отсутствии таких прав. Для этого применяются различные системы паролей, регистрация и идентификация пользователей, разграничения прав доступа и т. п. Практика показывает, что борьба между “хакерами” и модулями защиты операционных систем идет с переменным успехом.
• Хранить данные таким образом, чтобы они могли “сами за себя постоять”. Другими словами, так закодировать данные, чтобы даже получив их, злоумышленник не смог бы нанести ущерба.

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

1. Криптография

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

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

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

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

Пусть имеется датчик псевдослучайных чисел, работающий по некоторому определенному алгоритму. Часто используют следующий алгоритм:
T_i+1:= (а * T_i + b) mod c,
где Т_i — предыдущее псевдослучайное число, T_i+1 — следующее псевдослучайное число, а коэффициенты a, b, с постоянны и хорошо известны. Обычно с = 2ⁿ, где n — разрядность процессора, а mod 4 = 1, а b — нечетное.
В этом случае последовательность псевдослучайных чисел имеет период с.
Процесс шифрования определяется следующим образом. Шифруемое сообщение представляется в виде последовательности слов S₀, S₁, ..., каждое длины n, которые складываются по модулю 2 со словами последовательности T₀, T₁, ..., то есть
C_i := S_i A T_i.
Последовательность Т₀, T₁, ... называется гаммой шифра.
Процесс расшифровывания заключается в том, чтобы еще раз сложить шифрованную последовательность с той же самой гаммой шифра:
S_i := C_i A T_i.
Ключом шифра является начальное значение Т₀, которое является секретным и должно быть известно только отправителю и получателю шифрованного сообщения.

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

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

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

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

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

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

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

1. вычисление гаммы шифра по ключу более сложным (или секретным) способом;
2. применение вместо A более сложной (но обратимой) операции для вычисления шифровки;
3. предварительное перемешивание битов исходного сообщения по фиксированному алгоритму.

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

4. Модулярная арифметика

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

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

Легко видеть, что <Z_n; +_n> образует абелеву группу, а <Z_n; +_n, •_n> — коммутативное кольцо с единицей.
Рассмотрим Z*_n — подмножество Z_n чисел, взаимно простых с n.

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

Можно показать, что <Z_n; •_n> — абелева группа. Таким образом, для чисел из множества Z*_n существуют обратные по умножению по модулю n.

Замечание
Если n — простое число, то <Z*n; +n, *n> является полем.

Функция (n): = |Z*_n| называется функцией Эйлера.

Замечание
Если р — простое число, то (р) = р - 1, и вообще, (n) < n.

Можно показать, что

где p₁, ..., p_k — все простые делители n. Имеет место следующая теорема.

Теорема (Эйлера)
Если n > 1, то a Z*n      aφ(n) 1 (mod n).

Отсюда непосредственно выводима

Теорема (малая теорема Ферма)
Если р > 1 — простое число, то a Z*p       ap-1 1 (mod p).

Имеет место, следующее утверждение.

Теорема
Если числа n1, ..., nk попарно взаимно простые, число n = n1n2 ... nk — их произведение, х и а — целые числа, то x a (mod n) ↔  i 1..k   x a (mod ni).

Замечание
Последнее утверждение является следствием теоремы, которая известна как ″китайская теорема об остатках″.

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

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

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

• выбираются два простых числа р и q;
• определяется первая часть открытого ключа n: = pq;
• определяется вторая часть открытого ключа — выбирается небольшое нечетное число е, взаимно простое с числом (р - 1)(q - 1) (заметим, что (р - 1)(q - 1) = pq(1 - 1/р)(1 - 1/q) = (n));
• определяется закрытый ключ: d: = е^-1 mod ((р - 1)(q - 1)).

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

1. Отправитель шифрует сообщение (разбивая его, если нужно, на слова S_i длиной менее log₂ n разрядов): C_i:= (S_i)^e mod n
   и отправляет получателю.
   
2. Получатель расшифровывает сообщение с помощью закрытого ключа d:

P_i:= (C_i)^d mod n.

Теорема
Шифрование с открытым ключом корректно, то есть в предыдущих обозначениях Pi = Si.

Доказательство
Легко видеть, что Р_i = (S_i)^ed mod n. Покажем, что M < n      М^ed М mod n. Действительно, числа d и е взаимно обратны по модулю (р - 1)(q - 1), то есть
ed =1 + k(p-1)(q-1) при некотором k.
Если М 0 (mod р), то по малой теореме Ферма имеем:

Если М 0 (mod р), то сравнение      М^ed М (mod р), очевидно, выполняется. Таким образом,
0 <= M < n      M^ed М (mod р).
Совершенно аналогично имеем
0 <= M < n      M^ed М (mod q),
и по следствию к китайской теореме об остатках
M < n      M^ed М (mod n).
Поскольку S_i < n и P_i < n, заключаем, что i Р_i = S_i.
Пример
Генерация ключей:

1. р:= 3, q:= 11;
2. n:= рq = 3*11 = 33;
3. (р - 1)(q - 1) = 2 * 10 = 20, е:= 7;
4. d:= 7^-1 mod 20 = 3, (7 * 3 mod 20 = 1).

Пусть S₁:= 3, S₂:= 1, S₃:= 2 (S₁, S₂, S₃ < n = 33). Тогда код определяется следующим образом.

1. C₁:= 3⁷ mod 33 = 2187 mod 33 = 9;
2. C₂:= 1⁷ mod 33 = 1 mod 33 = 1;
3. C₃:= 2⁷ mod 33 = 128 mod 33 = 29.

При расшифровке имеем:

1. P₁:= 9³ mod 33 = 729 mod 33 = 3;
2. P₂:= 1³ mod 33 = 1 mod 33 = 1;
3. P₃:= 29³ mod 33 = 24389 mod 33 = 2.

6. Цифровая подпись

Шифр с открытым ключом позволяет выполнять и многие другие полезные операции, помимо шифрования и посылки сообщений в одну сторону. Прежде всего, для организации многосторонней секретной связи каждому из участников достаточно сгенерировать свою пару ключей (открытый и закрытый), а затем сообщить всем партнерам свой открытый ключ.
Заметим, что операции зашифровки и расшифровки по существу одинаковы, и различаются только показателем степени, а потому коммутируют:
М = (M^e)^d mod n = М^ed mod n = М^de mod n = (М^e)^d mod n = М.
Это обстоятельство позволяет применять различные приемы, известные как цифровая (или электронная) подпись.
Рассмотрим следующую схему взаимодействия корреспондентов Х и Y. Отправитель Х кодирует сообщение S своим закрытым ключом (С:= М^d mod n) и посылает получателю Y пару <S, С>, то есть подписанное сообщение. Получатель Y, получив такое сообщение, кодирует подпись сообщения открытым ключом X, то есть вычисляет S':= C^е mod n. Если оказывается, что S = S', то это означает, что (нешифрованное!) сообщение S действительно было отправлено корреспондентом X. Если же S S', то сообщение было искажено при передаче или фальсифицировано.

Отступление

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

Можно подписывать и шифрованные сообщения. Для этого отправитель Х сначала кодирует своим закрытым ключом сообщение S, получая цифровую подпись С, а затем кодирует полученную пару <S, С> открытым ключом получателя Y. Получив такое сообщение, Y сначала расшифровывает его своим закрытым ключом, а потом убеждается в подлинности полученного сообщения, сравнив его с результатом применения открытого ключа Х к подписи С.

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

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

Упражнения:

1. Является ли схема алфавитного кодирования
   <а 0, b 10, c 011, d 1011, е 1111>
   префиксной? разделимой?

2. Построить оптимальное префиксное алфавитное кодирование для алфавита {а, b, с, d} со следующим распределением вероятностей появления букв:
   р_а = 1/2, р_b = 1/4, р_с = 1/8, p_d = 1/8.

3. Показать, что для несимметричных ошибок функция
   

   является расстоянием.

4. Проследить работу алгоритма сжатия Лемпела—Зива на примере следующего исходного текста: abaabaaab.

5. Пусть в системе программирования имеется процедура Randomize, которая получает целочисленный параметр и инициализирует датчик псевдослучайных чисел, и функция без параметров Rnd, которая выдает следующее псевдослучайное число в интервале [0, 1]. Составить алгоритмы шифровки и расшифровки с закрытым ключом.

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]