Часть 2. Шифрование

$ 2.1. Понятие шифрования.

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

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

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

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

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

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

Шифрование — это кодирование данных с целью защиты от несанкционирован­ного доступа.

Процесс кодирования сообщения называется шифрованием (или зашифровкой), а процесс декодирования — расшифровыванием (или расшифровкой). Само коди­рованное сообщение называется шифрованным (или просто шифровкой), а при­меняемый метод называется шифром.

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

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

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

Примечание.

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

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

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

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

T_i+1=(aTi + b) mod c,

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

В этом случае последовательность псевдослучайных, чисел имеет период с.

Процесс шифрования определяется следующим образом. Шифруемое сообще­ние представляется в виде последовательности слов S₀,S_1,..., каждое длины п, которые складываются по модулю 2 со словами последовательности T₀,T₁,..., то есть Ci=Si+₂Ti.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) определяется первая часть открытого ключа n=pq

3) определяется вторая часть открытого ключа — выбирается небольшое не­четное число е, взаимно простое с числом (р - 1)(q - 1) (заметим, что (р - 1)(q - 1) = pq(1 - 1/р)(1 - 1/q) = F(п)- фукнкция Эйлера);

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

Пояснение: d есть такое число, что e*d сравнимо с 1 по mod ((p-1)(q-1)).

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

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

Ci=(Si)^e mod n

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

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

Pi=(Ci)^d mod n.

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

Пример 1.

Генерация ключей:

1) p=3, q=11

2) n: = pq = 3*11 = 33;

3) (p-l)(q-l) = 2*10 = 20, e: = 7;

4) d: = 7^-1mod 20 = 3, (пояснение: 7 * 3 mod 20 = 1).

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

1. C₁: = 3⁷ mod33 = 2187 mod 33 = 9;

2. C₂: = I⁷ 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₂: = I³ mod 33 = 1 mod 33 = 1;

3. P₃: = 29³ mod 33 = 24389 mod 33 = 2.

Пример 2.

Зашифровать с помощью открытого ключа сообщение S.

Решение. Сообщение S представляем как последовательность 0 и 1-совокупность бинарных записей символов сообщения. Далее разбиваем эту последовательность на слова длины менее log₂ n разрядов справа налево. Если длины не хватает, то последнее слово дополняется слева нулями. Получаем последовательность двоичных чисел. Переводим их в десятичную запись. Получим последовательность десятичных чисел S₁, S₂, S_{3, …,} кототую шифруем согласно выше описанной процедуре _.

Замечание.

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

Поиск по сайту: