Сергей Панасенко ,
начальник отдела разработки программного обеспечения фирмы «Анкад»,
[email protected]

Основные понятия

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

С = Ek1(M)

M" = Dk2(C),

где M (message) - открытая информация (в литературе по защите информации часто носит название "исходный текст");
C (cipher text) - полученный в результате зашифрования шифртекст (или криптограмма);
E (encryption) - функция зашифрования, выполняющая криптографические преобразования над исходным текстом;
k1 (key) - параметр функции E, называемый ключом зашифрования;
M" - информация, полученная в результате расшифрования;
D (decryption) - функция расшифрования, выполняющая обратные зашифрованию криптографические преобразования над шифртекстом;
k2 - ключ, с помощью которого выполняется расшифрование информации.

Понятие "ключ" в стандарте ГОСТ 28147-89 (алгоритм симметричного шифрования) определено следующим образом: "конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований". Иными словами, ключ представляет собой уникальный элемент, с помощью которого можно изменять результаты работы алгоритма шифрования: один и тот же исходный текст при использовании различных ключей будет зашифрован по-разному.

Для того, чтобы результат расшифрования совпал с исходным сообщением (т. е. чтобы M" = M), необходимо одновременное выполнение двух условий. Во-первых, функция расшифрования D должна соответствовать функции зашифрования E. Во-вторых, ключ расшифрования k2 должен соответствовать ключу зашифрования k1.

Если для зашифрования использовался криптостойкий алгоритм шифрования, то при отсутствии правильного ключа k2 получить M" = M невозможно. Криптостойкость - основная характеристика алгоритмов шифрования и указывает прежде всего на степень сложности получения исходного текста из зашифрованного без ключа k2.

Алгоритмы шифрования можно разделить на две категории: симметричного и асимметричного шифрования. Для первых соотношение ключей зашифрования и расшифрования определяется как k1 = k2 = k (т. е. функции E и D используют один и тот же ключ шифрования). При асимметричном шифровании ключ зашифрования k1 вычисляется по ключу k2 таким образом, что обратное преобразование невозможно, например, по формуле k1 = ak2 mod p (a и p - параметры используемого алгоритма).

Симметричное шифрование

Свою историю алгоритмы симметричного шифрования ведут с древности: именно этим способом сокрытия информации пользовался римский император Гай Юлий Цезарь в I веке до н. э., а изобретенный им алгоритм известен как "криптосистема Цезаря".

В настоящее время наиболее известен алгоритм симметричного шифрования DES (Data Encryption Standard), разработанный в 1977 г. До недавнего времени он был "стандартом США", поскольку правительство этой страны рекомендовало применять его для реализации различных систем шифрования данных. Несмотря на то, что изначально DES планировалось использовать не более 10-15 лет, попытки его замены начались только в 1997 г.

Мы не будем рассматривать DES подробно (почти во всех книгах из списка дополнительных материалов есть его подробнейшее описание), а обратимся к более современным алгоритмам шифрования. Стоит только отметить, что основная причина изменения стандарта шифрования - его относительно слабая криптостойкость, причина которой в том, что длина ключа DES составляет всего 56 значащих бит. Известно, что любой криптостойкий алгоритм можно взломать, перебрав все возможные варианты ключей шифрования (так называемый метод грубой силы - brute force attack). Легко подсчитать, что кластер из 1 млн процессоров, каждый из которых вычисляет 1 млн ключей в секунду, проверит 256 вариантов ключей DES почти за 20 ч. А поскольку по нынешним меркам такие вычислительные мощности вполне реальны, ясно, что 56-бит ключ слишком короток и алгоритм DES необходимо заменить на более "сильный".

Сегодня все шире используются два современных криптостойких алгоритма шифрования: отечественный стандарт ГОСТ 28147-89 и новый криптостандарт США - AES (Advanced Encryption Standard).

Стандарт ГОСТ 28147-89

Алгоритм, определяемый ГОСТ 28147-89 (рис. 1), имеет длину ключа шифрования 256 бит. Он шифрует информацию блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2). Субблок N1 обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - "исключающее или"), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз ("раундов"): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции.

Первая - наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-бит частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-бит подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.

Вторая операция - табличная замена. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.

Табличные замены (Substitution box - S-box) часто используются в современных алгоритмах шифрования, поэтому стоит пояснить, как организуется подобная операция. В таблицу записываются выходные значения блоков. Блок данных определенной размерности (в нашем случае - 4-бит) имеет свое числовое представление, которое определяет номер выходного значения. Например, если S-box имеет вид 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 и на вход пришел 4-бит блок "0100" (значение 4), то, согласно таблице, выходное значение будет равно 15, т. е. "1111" (0 а 4, 1 а 11, 2 а 2 ...).

Алгоритм, определяемый ГОСТ 28147-89, предусматривает четыре режима работы: простой замены, гаммирования, гаммирования с обратной связью и генерации имитоприставок. В них используется одно и то же описанное выше шифрующее преобразование, но, поскольку назначение режимов различно, осуществляется это преобразование в каждом из них по-разному.

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

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;

K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.

Расшифрование в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:

K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.

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

В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2 (см. рис. 1).

1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.

2. Выполняется зашифрование содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.

3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.

4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.

5. Содержимое регистров N1 и N2 подается на выход в качестве 64-бит блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).

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

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

Зашифрование и расшифрование в режиме гаммирования

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

В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не секретна, однако есть системы, где синхропосылка - такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бит секретной синхропосылки, которую также можно рассматривать как ключевой элемент.

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

Рис. 2. Выработка гаммы шифра в режиме гаммирования с обратной связью.

Рассматривая режим генерации имитоприставок , следует определить понятие предмета генерации. Имитоприставка - это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-бит блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.

Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-бит содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-бит имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.

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

Алгоритм ГОСТ 28147-89 считается очень сильным алгоритмом - в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод "грубой силы". Его высокая стойкость достигается в первую очередь за счет большой длины ключа - 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).

Стандарт AES

В отличие от алгоритма ГОСТ 28147-89, который долгое время оставался секретным, американский стандарт шифрования AES, призванный заменить DES, выбирался на открытом конкурсе, где все заинтересованные организации и частные лица могли изучать и комментировать алгоритмы-претенденты.

Конкурс на замену DES был объявлен в 1997 г. Национальным институтом стандартов и технологий США (NIST - National Institute of Standards and Technology). На конкурс было представлено 15 алгоритмов-претендентов, разработанных как известными в области криптографии организациями (RSA Security, Counterpane и т. д.), так и частными лицами. Итоги конкурса были подведены в октябре 2000 г.: победителем был объявлен алгоритм Rijndael, разработанный двумя криптографами из Бельгии, Винсентом Риджменом (Vincent Rijmen) и Джоан Даймен (Joan Daemen).

Алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, структура которых носит название "сеть Фейстеля" и аналогична российскому ГОСТ 28147-89. Особенность сети Фейстеля состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки (см. рис. 1).

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

Алгоритм Rijndael выполняет четыре преобразования: BS (ByteSub) - табличная замена каждого байта массива (рис. 3); SR (ShiftRow) - сдвиг строк массива (рис. 4). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байт, зависящее от размера массива. Например, для массива размером 4X4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта. Далее идет MC (MixColumn) - операция над независимыми столбцами массива (рис. 5), когда каждый столбец по определенному правилу умножается на фиксированную матрицу c(x). И, наконец, AK (AddRoundKey) - добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 6).

Рис. 3. Операция BS.

Рис. 4. Операция SR.

Рис. 5. Операция MC.

Количество раундов шифрования (R) в алгоритме Rijndael переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

Расшифрование выполняется с помощью следующих обратных операций. Выполняется обращение таблицы и табличная замена на инверсной таблице (относительно применяемой при зашифровании). Обратная операция к SR - это циклический сдвиг строк вправо, а не влево. Обратная операция для MC - умножение по тем же правилам на другую матрицу d(x), удовлетворяющую условию: c(x) * d(x) = 1. Добавление ключа AK является обратным самому себе, поскольку в нем используется только операция XOR. Эти обратные операции применяются при расшифровании в последовательности, обратной той, что использовалась при зашифровании.

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

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

Асимметричное шифрование

Алгоритмы асимметричного шифрования, как уже отмечалось, используют два ключа: k1 - ключ зашифрования, или открытый, и k2 - ключ расшифрования, или секретный. Открытый ключ вычисляется из секретного: k1 = f(k2).

Асимметричные алгоритмы шифрования основаны на применении однонаправленных функций. Согласно определению, функция y = f(x) является однонаправленной, если: ее легко вычислить для всех возможных вариантов x и для большинства возможных значений y достаточно сложно вычислить такое значение x, при котором y = f(x).

Примером однонаправленной функции может служить умножение двух больших чисел: N = P*Q. Само по себе такое умножение - простая операция. Однако обратная функция (разложение N на два больших множителя), называемая факторизацией, по современным временным оценкам представляет собой достаточно сложную математическую задачу. Например, разложение на множители N размерностью 664 бит при P ? Q потребует выполнения примерно 1023 операций, а для обратного вычисления х для модульной экспоненты y = ax mod p при известных a, p и y (при такой же размерности a и p) нужно выполнить примерно 1026 операций. Последний из приведенных примеров носит название - "Проблема дискретного логарифма" (DLP - Discrete Logarithm Problem), и такого рода функции часто используются в алгоритмах асимметричного шифрования, а также в алгоритмах, используемых для создания электронной цифровой подписи.

Еще один важный класс функций, используемых в асимметричном шифровании, - однонаправленные функции с потайным ходом. Их определение гласит, что функция является однонаправленной с потайным ходом, если она является однонаправленной и существует возможность эффективного вычисления обратной функции x = f-1(y), т. е. если известен "потайной ход" (некое секретное число, в применении к алгоритмам асимметричного шифрования - значение секретного ключа).

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

Алгоритм RSA

Разработанный в 1978 г. тремя авторами (Rivest, Shamir, Adleman), он получил свое название по первым буквам фамилий разработчиков. Надежность алгоритма основывается на сложности факторизации больших чисел и вычисления дискретных логарифмов. Основной параметр алгоритма RSA - модуль системы N, по которому проводятся все вычисления в системе, а N = P*Q (P и Q - секретные случайные простые большие числа, обычно одинаковой размерности).

Секретный ключ k2 выбирается случайным образом и должен соответствовать следующим условиям:

1

где НОД - наибольший общий делитель, т. е. k1 должен быть взаимно простым со значением функции Эйлера F(N), причем последнее равно количеству положительных целых чисел в диапазоне от 1 до N, взаимно простых с N, и вычисляется как F(N) = (P - 1)*(Q - 1) .

Открытый ключ k1 вычисляется из соотношения (k2*k1) = 1 mod F(N) , и для этого используется обобщенный алгоритм Евклида (алгоритм вычисления наибольшего общего делителя). Зашифрование блока данных M по алгоритму RSA выполняется следующим образом: C = M[в степени k1] mod N . Заметим, что, поскольку в реальной криптосистеме с использованием RSA число k1 весьма велико (в настоящее время его размерность может доходить до 2048 бит), прямое вычисление M[в степени k1] нереально. Для его получения применяется комбинация многократного возведения M в квадрат с перемножением результатов.

Обращение данной функции при больших размерностях неосуществимо; иными словами, невозможно найти M по известным C, N и k1. Однако, имея секретный ключ k2, при помощи несложных преобразований можно вычислить M = Ck2 mod N. Очевидно, что, помимо собственно секретного ключа, необходимо обеспечивать секретность параметров P и Q. Если злоумышленник добудет их значения, то сможет вычислить и секретный ключ k2.

Какое шифрование лучше?

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

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

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

Дополнительные источники информации Тем читателям, которые непраздно интересуются шифрованием, автор рекомендует расширить свой кругозор с помощью следующих книг. Брассар Ж. "Современная криптология". Петров А. А. "Компьютерная безопасность: криптографические методы защиты". Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. "Защита информации в современных компьютерных системах". Соколов А. В., Шаньгин В. Ф. "Защита информации в распределенных корпоративных сетях и системах". Полное описание алгоритмов шифрования можно найти в следующих документах: ГОСТ 28147-89. Система обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР, 1989. Алгоритм AES: http://www.nist.gov/ae . Алгоритм RSA: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1 .

Государственным стандартом шифрования в России является алгоритм, зарегистрированный как ГОСТ 28147-89. Он является блочным шифром, то есть шифрует не отдельные символы, а 64-битные блоки. В алгоритме предусмотрено 32 цикла преобразования данных с 256-битным ключом, за счет этого он очень надежен (обладает высокой криптостойкостью). На современных компьютерах раскрытие этого шифра путем перебора ключей (“методом грубой силы”) займет не менее сотен лет, что делает такую атаку бес­смысленной. В США используется аналогичный блочный шифр AES .

В Интернете популярен алгоритм RSA, названный так по начальным буквам фамилий его авторов - Р.Райвеста (R.Rivest), А.Шамира (A.Shamir) и ЛАдлемана (L.Adleman). Это алгоритм с открытым ключом, стойкость которого основана на использовании свойств простых чисел. Для его взлома нужно разложить очень большое число на простые сомножители. Эту задачу сейчас умеют решать только перебором вариантов. Поскольку количество вариантов огромно, для раскрытия шифра требуется много лет работы со­временных компьютеров.

Для применения алгоритма RSA требуется построить открытый и секретный ключи следующим образом.

1. Выбрать два больших простых числа, р и q.
2. Найти их произведение n = p * q и значение f = (р - 1) (q - 1)
3. Выбрать число e (1 < e < k), которое не имеет общих делителей с f.
4. Найти число d, которое удовлетворяет условию d e = k f + 1 для некоторого целого k
5. Пара значений (e, n) - это открытый ключ RSA (его можно свободно публиковать), а пара (d, n) - это секретный ключ .

Передаваемое сообщение нужно сначала представить в виде последовательности чисел в интервале от 0 до n - 1. Для шифрования используют формулу y = х e mod n, где х - число исходного сообщения, (e, n) - открытый ключ, y - число закодированного сообщения, а запись х e mod n обозначает остаток от деления х на n. Расшифровка сообщения выполняется по формуле х = y d mod n.
Это значит, что зашифровать сообщение может каждый (открытый ключ общеизвестен), а прочитать его - только тот, кто знает секретный показатель степени d.
Для лучшего понимания мы покажем работу алгоритма RSA на простом примере. ПРИМЕР: Возьмем р = 3 и q = 7, тогда находим n = р q = 21 и f = (р - 1) (q - 1) = 12. Выберем e = 5, тогда равенство d e = к f + 1 выполняется, например, при d = 17 (и к = 7). Таким образом, мы получили открытый ключ (5, 21) и секретный ключ (17, 21).

Зашифруем сообщение “123” с помощью открытого ключа (5,21). Получаем

1 → 1 5 mod 21 = 1 ,
2 → 2 5 mod 21 = 11 ,

3 → 3 5 mod 21 = 12,
то есть зашифрованное сообщение состоит из чисел 1 ,11и 12. Зная секретный ключ (17, 21), можно его расшифровать:

1 → 1 17 mod 21 = 1 ,

11 → 11 17 mod 21 = 2 ,
12 → 12 17 mod 21 = 3 .

Мы получили исходное сообщение.

Конечно, вы заметили, что при шифровании и расшифровке приходится вычислять остаток от деления очень больших чисел (например, 12 17) на n. Оказывается, само число 12 17 в этом случае находить не нужно. Достаточно записать в обычную целочисленную пере­менную, например х, единицу, а потом 17 раз выпол­нить преобразование х = 12*х mod 21. После этого в переменной х будет значение 12 17 mod 21 = 3. Попро­буйте доказать правильность этого алгоритма.
Для того чтобы расшифровать сообщение, нужно знать секретный показатель степени d. А для этого, в свою очередь, нужно найти сомножители р и q, такие что n = р q. Если n велико, это очень сложная задача, ее решение перебором вариантов на современном ком­пьютере займет сотни лет. В 2009 году группа ученых из разных стран в результате многомесячных расчетов на сотнях компьютеров смогла расшифровать сообще­ние, зашифрованное алгоритмом RSA с 768-битным ключом. Поэтому сейчас надежными считаются ключи с длиной 1024 бита и более. Если будет построен рабо­тающий квантовый компьютер, взлом алгоритма RSA будет возможен за очень небольшое время.
При использовании симметричных шифров всегда возникает проблема: как передать ключ, если канал связи ненадежный? Ведь, получив ключ, противник сможет расшифровать все дальнейшие сообщения. Для алгоритма RSA этой проблемы нет, сторонам достаточно обменяться открытыми ключами, которые можно показывать всем желающим.
У алгоритма RSA есть еще одно достоинство: его можно использовать для цифровой подписи сообщений. Она служит для доказательства авторства документов, защиты сообщений от подделки и умышленных изменений.

Цифровая подпись - это набор символов, который получен в результате шифрования сообщения с помощью личного секретного кода отправителя.

Отправитель может передать вместе с исходным сообщением такое же сообщение, зашифрованное с помощью своего секретного ключа (это и есть цифровая подпись). Получатель расшифровывает цифровую подпись с помощью открытого ключа. Если она совпа­ла с незашифрованным сообщением, можно быть уве­ренным, что его отправил тот человек, который знает секретный код. Если сообщение было изменено при передаче, оно не совпадет с расшифрованной цифровой подписью. Так как сообщение может быть очень длинным, для сокращения объема передаваемых дан­ных чаще всего шифруется не все сообщение, а только его хэш-код.
Во многих современных программах есть возможность шифровать данные с паролем. Например, офисные пакеты OpenOffice.org и Microsoft Office позволяют шифровать все создаваемые документы (для их просмотра и/или изменения нужно ввести пароль). При создании архива (например, в архиваторах 7Zip,WinRAR, WinZip ) также можно установить пароль, без которого извлечь файлы невозможно.
В простейших задачах для шифрования файлов можно использовать бесплатную программу Шифро­вальщик (http://www.familytree.ru/ru/cipher.htm), версии которой существуют для Linux и Windows . Програм­мы TnieCrypt (http://www.truecrypt.org/), BestCrypt (www. jetico.com) и FreeOTFE (freeotfe.org) создают логические диски-контейнеры, информация на которых шифруется. Свободно распространяемая программа DiskCrypto r (diskcryptor.net) позволяет шифровать разделы жестких дисков и даже создавать шифрованные флэш-диски и CD/DVD-диски.
Программа GnuPG (gnupg.org) также относится к свободному программному обеспечению. В ней под­держиваются симметричные и несимметричные шиф­ры, а также различные алгоритмы электронной циф­ровой подписи.

Стеганография

Видео YouTube

При передаче сообщений можно не только применять шифрование, но и скрывать сам факт передачи сообщения.

Стеганография - это наука о скрытой передаче информации путем скрытия самого факта передачи информации.

Древнегреческий историк Геродот описывал, например, такой метод: на бритую голову раба записывалось сообщение, а когда его волосы отрастали, он отправлялся к получателю, который брил его голову и читал сообщение.
Классический метод стеганографии - симпатические (невидимые) чернила, которые проявляются только при определенных условиях (нагрев, освещение, хиический проявитель). Например, текст, написанный молоком, можно прочитать при нагреве.
Сейчас стеганография занимается скрытием информации в текстовых, графических, звуковых и видеофайлах с помощью программного “внедрения” в них нужных сообщений.
Простейший способ - заменять младшие биты файла, в котором закодировано изображение. Причем это нужно сделать так, чтобы разница между исходным и полученным рисунками была неощутима для человека. Например, если в черно-белом рисунке (256 оттенков серого) яркость каждого пикселя кодируется 8 битами. Если поменять 1-2 младших бита этого кода, ““встроив” туда текстовое сообщение, фотография, в которой нет четких границ, почти не изменится. При замене 1 бита каждый байт исходного текстового сообщения хранится в млад­ших битах кодов 8 пикселей. Например, пусть первые 8 пикселей рисунка имеют такие коды:

10101101	10010100	00101010	01010010
10101010	10101010	10101011	10101111

Чтобы закодировать в них код буквы “И” (110010002), нужно изменить младшие биты кодов:

1010110 1	1001010 1	0010101 0	0101001 0
1010101 1	1010101 0	1010101 0	1010111 0

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

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

Контрольные вопросы:

1. Какой алгоритм шифрования принят в России в качестве государственного стандарта?
2. Что такое блочный алгоритм шифрования?
3. К какому типу относится алгоритм RSA? На чем основана его криптостойкость?
4. Что такое цифровая подпись?
5. Как можно использовать алгоритм RSA для цифровой подписи?
6. Что такое стеганография?
7. Какие методы стеганографии существовали до изобретения компьютеров?
8. Как можно добавить текст в закодированное изображение?
9. На чем основаны методы стеганографии для звуковых и видеоданных?
10. Что такое цифровые водяные знаки? Зачем они используются?

Задание:

1.Просмотреть материал лекции и ответить на контрольные вопросы.
2. Пройдитесь по ссылкам и познакомьтесь с программами для шифрования файлов.
3. Зашифруйте любой документ в любом из офисных пакетов OpenOffice.org или Microsoft Office и пришлите мне.

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

Симметричные алгоритмы
Алгоритмы шифрования делятся на два больших класса: симметричные (AES, ГОСТ, Blowfish, CAST, DES) и асимметричные (RSA, El-Gamal). Симметричные алгоритмы шифрования используют один и тот же ключ для зашифровывания информации и для ее расшифровывания, а асимметричные алгоритмы используют два ключа - один для зашифровывания, другой для расшифровывания.

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

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

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

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

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

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

Теоретическая и практическая стойкость.
В 1949 г. К.Э. Шеннон опубликовал статью "Теория связи в секретных системах". Шеннон рассматривал стойкость криптографических систем как Практическую и Теоритическую. Вывод по теоритической стойкости до сих пор остается пессимистическим: длина ключа должна быть равна длине открытого текста.
Поэтому Шеннон также рассмотрел вопрос и по практической стойкости криптографических систем. Надежна ли система, если злоумышленник обладает ограниченным временем и вычислительными ресурсами для анализа перехваченных сообщений?

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

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

В криптологии есть подраздел - криптоанализ, который изучает вопросы взлома или подделывания зашифрованных сообщений. Существует много способов и методов криптоанализа. Самый популярный - это метод прямого перебора всех возможных значений ключа шифрования (так называемым методом "грубой силы" или brute force). Суть данного метода состоит в переборе всех возможных значений ключа шифрования до тех пор, пока не будет подобран нужный ключ.

На практике это означает, что злоумышленник должен:

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

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

Алгоритмы шифрования
AES (Rijndael) . В настоящее время является федеральным стандартом шифрования США. Утвержден министерством торговли в качестве стандарта 4 декабря 2001 года. Решение вступило в силу с момента опубликования в федеральном реестре (06.12.01). В качестве стандарта принят вариант шифра только с размером блока 128 бит.

ГОСТ 28147-8. Стандарт Российской Федерации на шифрование и имитозащиту данных. Первоначально имел гриф (ОВ или СС - точно не известно), затем гриф последовательно снижался, и к моменту официального проведения алгоритма через Госстандарт СССР в 1989 году был снят. Алгоритм остался ДСП (как известно, ДСП не считается грифом). В 1989 году стал официальным стандартом СССР, а позже, после распада СССР, федеральным стандартом Российской Федерации.

Blowfish Сложная схема выработки ключевых элементов существенно затрудняет атаку на алгоритм методом перебора, однако делает его непригодным для использования в системах, где ключ часто меняется, и на каждом ключе шифруется небольшие по объему данные. Алгоритм лучше всего подходит для систем, в которых на одном и том же ключе шифруются большие массивы данных.

DES Федеральный стандарт шифрования США в 1977-2001 годах. В качестве федерального стандарта США принят в 1977 году. В декабре 2001 года утратил свой статус в связи с введением в действие нового стандарта.

CAST В некотором смысле аналог DES.

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

Шифрование - метод защиты информации

Испокон веков не было ценности большей, чем информация. ХХ век - век информатики и информатизации. Технология дает возможность передавать и хранить все большие объемы информации. Это благо имеет и оборотную сторону. Информация становится все более уязвимой по разным причинам:

возрастающие объемы хранимых и передаваемых данных;

расширение круга пользователей, имеющих доступ к ресурсам ЭВМ, программам и данным;

усложнение режимов эксплуатации вычислительных систем.

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

Характеристики составных алгоритмов шифрования

Защита информации - совокупность мероприятий, методов и средств, обеспечивающих:

• исключение НСД к ресурсам ЭВМ, программам и данным;
• проверку целостности информации;
• исключение несанкционированного использования программ (защита программ от копирования).

Очевидная тенденция к переходу на цифровые методы передачи и хранени информации позволяет применять унифицированные методы и алгоритмы для защиты дискретной (текст, факс, телекс) и непрерывной (речь) информации.

Испытанный метод защиты информации от НСД - шифрование (криптография). Шифрованием (encryption) называют процесс преобразования открытых данных (plaintext) в зашифрованные (шифртекст, ciphertext) или зашифрованных данных в открытые по определенным правилам с применением ключей. В англоязычной литературе зашифрование/расшифрование - enciphering/deciphering.

С помощью криптографических методов возможно:

шифрование информации;

реализация электронной подписи;

распределение ключей шифрования;

защита от случайного или умышленного изменения информации.

К алгоритмам шифровани предъявляются определенные требования:

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

Предания старины глубокой...

Борис Оболикшто

Криптология - древняя наука и обычно это подчеркивают рассказом о Юлии Цезаре (100 - 44 гг. до н. э.), переписка которого с Цицероном (106 - 43 гг. до н. э.) и другими "абонентами" в Древнем Риме шифровалась. Шифр Цезаря, иначе шифр циклических подстановок, состоит в замене каждой буквы в сообщении буквой алфавита, отстоящей от нее на фиксированное число букв. Алфавит считаетс циклическим, то есть после Z следует A. Цезарь заменял букву буквой, отстоящей от исходной на три.
Сегодня в криптологии принято оперировать символами не в виде букв, а в виде чисел, им соответствующих. Так, в латинском алфавите можем использовать числа от 0 (соответствующего A) до 25 (Z). Обозначая число, соответствующее исходному символу, x, а закодированному - y, можем записать правило применения подстановочного шифра:

y = x + z (mod N), (1)

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

Шифр Цезаря в принятых обозначениях соответствует значению секретного ключа z = 3 (а у Цезаря Августа z = 4 ). Такие шифры раскрываютс чрезвычайно просто даже без знания значени ключа: достаточно знать лишь алгоритм шифрования, а ключ можно подобрать простым перебором (так называемой силовой атакой). Криптология и состоит из двух частей - криптографии, изучающей способы шифрования и/или проверки подлинности сообщений, и криптоанализа, рассматривающего пути расшифровки и подмены криптограмм. Неустойчивость первых шифров на многие столетия породила атмосферу секретности вокруг работы криптографа, затормозила развитие криптологии как науки.

Так называемая "донаучная" криптография более чем за две тысячи лет полуинтуитивно "нащупала" довольно много интересных решений. Простейшее действие - выполнить подстановку не в алфавитном порядке. Неплохо также переставить символы в сообщении местами (шифры перестановок).

Первым систематическим трудом по криптографии принято считать работу великого архитектора Леона Баттиста Альберти (1404 - 1472 гг.). Период до середины XVII века уже насыщен работами по криптографии и криптоанализу. Интриги вокруг шифрограмм в Европе того времени удивительно интересны. Увы, ограниченные возможностями журнала, мы выберем только одну известную со школы фамилию - Франсуа Виет (1540 - 1603 гг.), который при дворе короля Франции Генриха IV так успешно занимался криптоанализом (тогда еще не носившим этого гордого названия), что испанский король Филипп II жаловался Папе Римскому на применение французами черной магии. Но все обошлось без кровопролития - при дворе Папы в это время уже служили советники из семейства Ардженти, которых мы сегодня назвали бы криптоаналитиками.

Можно утверждать, что на протяжении веков дешифрованию криптограмм помогает частотный анализ появления отдельных символов и их сочетаний. Вероятности появления отдельных букв в тексте сильно разнятся (для русского языка, например, буква "о" появляется в 45 раз чаще буквы "ф"). Это, с одной стороны, служит основой как для раскрытия ключей, так и дл анализа алгоритмов шифрования, а с другой - является причиной значительной избыточности (в информационном смысле) текста на естественном языке. Любая простая подстановка не позволяет спрятать частоту появления символа - как шило из мешка торчат в русском тексте символы, соответствующие буквам "о", "е", "а", "и", "т", "н". Но теори информации и мера избыточности еще не созданы, и для борьбы с врагом криптографа - частотным анализом - предлагается РАНДОМИЗАЦИЯ. Ее автор Карл Фридрих Гаусс (1777 - 1855 гг.) ошибочно полагал, что создал нераскрываемый шифр.

Следующая заметная личность в истории криптологии, которую мы не должны пропустить, - голландец Огюст Керкхофф (1835 - 1903 гг.). Ему принадлежит замечательное "правило Керкхоффа": стойкость шифра должна определяться ТОЛЬКО секретностью ключа. Учитывая время, когда это правило было сформулировано, его можно признать величайшим открытием (до создания систематической теории еще более полувека!). Это правило полагает, что АЛГОРИТМ шифрования НЕ ЯВЛЯЕТСЯ СЕКРЕТНЫМ, а значит, можно вести открытое обсуждение достоинств и недостатков алгоритма.Таким образом, это правило переводит работы по криптологии в разряд ОТКРЫТЫХ научных работ, допускающих дискуссии, публикации и т. п.

ХХ век - от интуиции к науке

Последнее имя, которое мы назовем в донаучной криптологии, - инженер AT&T Жильбер Вернам (G.S. Vernam). В 1926 году он предложил действительно нераскрываемый шифр. Идея шифра состоит в том, чтобы в уравнении (1) для каждого следующего символа выбирать новое значение z. Другими словами, секретный ключ должен использоваться только один раз. Если такой ключ выбирается случайным образом, то, как было строго доказано Шенноном через 23 года, шифр являетс нераскрываемым. Этот шифр являетс теоретическим обоснованием для использовани так называемых "шифроблокнотов", широкое применение которых началось в годы второй мировой войны. Шифроблокнот содержит множество ключей однократного использования, последовательно выбираемых при шифровании сообщений. Предложение Вернама, однако, не решает задачи секретной связи: вместо способа передачи секретного сообщения теперь необходимо найти способ передачи секретного ключа, РАВНОГО ему ПО ДЛИНЕ, т. е. содержащего столько же символов, сколько имеется в открытом тексте.

В 1949 году статья Клода Шеннона "Теори связи в секретных системах" положила начало научной криптологии. Шеннон показал, что дл некоторого "случайного шифра" количество знаков шифротекста, получив которые криптоаналитик при неограниченных ресурсах может восстановить ключ (и раскрыть шифр),

H (Z)/(rlog N), (2)

где H (Z) - энтропия ключа, r - избыточность открытого текста, а N - объем алфавита.

По эффективности, с которой архиваторы сжимают текстовые файлы, нам хорошо известно, как велика избыточность обычного текста - ведь их работа и состоит в снижении избыточности (причем только на наиболее легко устраняемой ее части). При избыточности обычного текста порядка 0,75 и использовании 56-битового ключа (такого, как предполагает DES), достаточно 11 символов шифротекста дл восстановления ключа при неограниченных ресурсах криптоаналитика.

Строго говоря, соотношение (2) не доказано для произвольного шифра, но верно для известных частных случаев. Из (2) следует замечательный вывод: работу криптоаналитика можно затруднить не только совершенствованием криптосистемы, но и снижением избыточности открытого текста. Более того, если избыточность открытого текста снизить до нуля, то даже короткий ключ даст шифр, который криптоаналитик не сможет раскрыть.

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

Классификация алгоритмов шифрования

1. Симметричные (с секретным, единым ключом, одноключевые, single-key).
1.1. Потоковые (шифрование потока данных):

с одноразовым или бесконечным ключом (infinite-key cipher);

с конечным ключом (система Вернама - Vernam);

на основе генератора псевдослучайных чисел (ПСЧ).

1.2. Блочные (шифрование данных поблочно):
1.2.1. Шифры перестановки (permutation, P-блоки);
1.2.2. Шифры замены (подстановки, substitution, S-блоки):

• моноалфавитные (код Цезаря);
• полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma);

1.2.3. составные (таблица 1):

• Lucipher (фирма IBM, США);
• DES (Data Encryption Standard, США);
• FEAL-1 (Fast Enciphering Algoritm, Япония);
• IDEA/IPES (International Data Encryption Algorithm/
• Improved Proposed Encryption Standard, фирма Ascom-Tech AG, Швейцария);
• B-Crypt (фирма British Telecom, Великобритания);
• ГОСТ 28147-89 (СССР); * Skipjack (США).

2. Асимметричные (с открытым ключом, public-key):

• Диффи-Хеллман DH (Diffie, Hellman);
• Райвест-Шамир-Адлeман RSA (Rivest, Shamir, Adleman);
• Эль-Гамаль ElGamal.

Кроме того, есть разделение алгоритмов шифрования на собственно шифры (ciphers) и коды (codes). Шифры работают с отдельными битами, буквами, символами. Коды оперируют лингвистическими элементами (слоги, слова, фразы).

Симметричные алгоритмы шифрования

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

Обмен информацией осуществляется в 3 этапа:

отправитель передает получателю ключ (в случае сети с несколькими абонентами у каждой пары абонентов должен быть свой ключ, отличный от ключей других пар);

отправитель, используя ключ, зашифровывает сообщение, которое пересылаетс получателю;

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

Потоковые шифры

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

Гаммирование - наложение на открытые данные гаммы шифра (случайной или псевдослучайной последовательности единиц и нулей) по определенному правилу. Обычно используется "исключающее ИЛИ", называемое также сложением по модулю 2 и реализуемое в ассемблерных программах командой XOR. Дл расшифровывания та же гамма накладывается на зашифрованные данные.

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

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

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

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

При использовании генератора ПСЧ возможны несколько вариантов :

Побитовое шифрование потока данных. Цифровой ключ используется в качестве начального значения генератора ПСЧ, а выходной поток битов суммируется по модулю 2 с исходной информацией. В таких системах отсутствует свойство распространения ошибок.

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

Побитовое шифрование потока данных с ОС по исходному тексту. Базой генератора ПСЧ являетс исходная информация. Характерно свойство неограниченного распространения ошибки.

Побитовое шифрование потока данных с ОС по шифртексту и по исходному тексту.

Блочные шифры

При блочном шифровании информация разбивается на блоки фиксированной длины и шифруется поблочно. Блочные шифры бывают двух основных видов:

шифры перестановки (transposition, permutation, P-блоки);

шифры замены (подстановки, substitution, S-блоки).

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

Шифры замены заменяют элементы открытых данных на другие элементы по определенному правилу. Paзличают шифры простой, сложной, парной замены, буквенно-слоговое шифрование и шифры колонной замены. Шифры замены делятся на две группы:

моноалфавитные (код Цезаря) ;

полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma).

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

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

В современных криптографических системах, как правило, используют оба способа шифрования (замены и перестановки). Такой шифратор называют составным (product cipher). Oн более стойкий, чем шифратор, использующий только замены или перестановки.

Блочное шифрование можно осуществлять двояко :

Без обратной связи (ОС). Несколько битов (блок) исходного текста шифруютс одновременно, и каждый бит исходного текста влияет на каждый бит шифртекста. Однако взаимного влияния блоков нет, то есть два одинаковых блока исходного текста будут представлены одинаковым шифртекстом. Поэтому подобные алгоритмы можно использовать только для шифрования случайной последовательности битов (например, ключей). Примерами являются DES в режиме ECB и ГОСТ 28147-89 в режиме простой замены.

С обратной связью. Обычно ОС организуется так: предыдущий шифрованный блок складывается по модулю 2 с текущим блоком. В качестве первого блока в цепи ОС используетс инициализирующее значение. Ошибка в одном бите влияет на два блока - ошибочный и следующий за ним. Пример - DES в режиме CBC.

Генератор ПСЧ может применяться и при блочном шифровании :

1. Поблочное шифрование потока данных. Шифрование последовательных блоков (подстановки и перестановки) зависит от генератора ПСЧ, управляемого ключом.
2. Поблочное шифрование потока данных с ОС. Генератор ПСЧ управляется шифрованным или исходным текстом или обоими вместе.

Весьма распространен федеральный стандарт США DES (Data Encryption Standard) , на котором основан международный стандарт ISO 8372-87. DES был поддержан Американским национальным институтом стандартов (American National Standards Institute, ANSI) и рекомендован для применения Американской ассоциацией банков (American Bankers Association, ABA). DES предусматривает 4 режима работы:

• ECB (Electronic Codebook) электронный шифрблокнот;
• CBC (Cipher Block Chaining) цепочка блоков;
• CFB (Cipher Feedback) обратная связь по шифртексту;
• OFB (Output Feedback) обратная связь по выходу.

ГОСТ 28147-89 - отечественный стандарт на шифрование данных . Стандарт включает три алгоритма зашифровывани (расшифровывания) данных: режим простой замены, режим гаммирования, режим гаммирования с обратной связью - и режим выработки имитовставки.

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

Алгоритмы шифрования ГОСТ 28147-89 обладают достоинствами других алгоритмов дл симметричных систем и превосходят их своими возможностями. Так, ГОСТ 28147-89 (256-битовый ключ, 32 цикла шифрования) по сравнению с такими алгоритмами, как DES (56-битовый ключ, 16 циклов шифрования) и FEAL-1 (64-битовый ключ, 4 цикла шифрования) обладает более высокой криптостойкостью за счет более длинного ключа и большего числа циклов шифрования.

Следует отметить, что в отличие от DES, у ГОСТ 28147-89 блок подстановки можно произвольно изменять, то есть он является дополнительным 512-битовым ключом.

Алгоритмы гаммирования ГОСТ 28147-89 (256-битовый ключ, 512-битовый блок подстановок, 64-битовый вектор инициализации) превосходят по криптостойкости и алгоритм B-Crypt (56-битовый ключ, 64-битовый вектор инициализации).

Достоинствами ГОСТ 28147-89 являютс также наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТа.

Блочные алгоритмы могут использоваться и для выработки гаммы. В этом случае гамма вырабатывается блоками и поблочно складывается по модулю 2 с исходным текстом. В качестве примера можно назвать B-Crypt, DES в режимах CFB и OFB, ГОСТ 28147-89 в режимах гаммирования и гаммирования c обратной связью.

Аcимметричные алгоритмы шифрования

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

Схема обмена информацией такова:

получатель вычисляет открытый и секретный ключи, секретный ключ хранит в тайне, открытый же делает доступным (сообщает отправителю, группе пользователей сети, публикует);

отправитель, используя открытый ключ получателя, зашифровывает сообщение, которое пересылается получателю;

получатель получает сообщение и расшифровывает его, используя свой секретный ключ.

RSA

Защищен патентом США N 4405829. Разработан в 1977 году в Массачусетском технологическом институте (США). Получил название по первым буквам фамилий авторов (Rivest, Shamir, Adleman). Криптостойкость основана на вычислительной сложности задачи разложени большого числа на простые множители.

ElGamal

Разработан в 1985 году. Назван по фамилии автора - Эль-Гамаль. Используется в стандарте США на цифровую подпись DSS (Digital Signature Standard). Криптостойкость основана на вычислительной сложности задачи логарифмирования целых чисел в конечных полях.

Сравнение cимметричных и аcимметричных алгоритмов шифрования

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

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

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

Обмен информацией можно осуществлять следующим образом:

получатель вычисляет открытый и секретный ключи, секретный ключ хранит в тайне, открытый же делает доступным;

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

получатель получает сеансовый ключ и расшифровывает его, используя свой секретный ключ;

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

получатель получает сообщение и расшифровывает его.

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

Проверка подлинности информации. Цифровая подпись

При передаче информации должны быть обеспечены вместе или по отдельности:

• Конфиденциальность (privacy) - злоумышленник не должен иметь возможности узнать содержание передаваемого сообщения.
• Подлинность (authenticity), которая включает два понятия:

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

Шифрование может обеспечить конфиденциальность, а в некоторых системах и целостность.

Целостность сообщения проверяетс вычислением контрольной функции (check function) от сообщения - некоего числа небольшой длины. Эта контрольная функция должна с высокой вероятностью изменяться даже при малых изменениях сообщения (удаление, включение, перестановки или переупорядочивание информации). Называют и вычисляют контрольную функцию по-разному:

код подлинности сообщения (Message Authentical Code, MAC);

квадратичный конгруэнтный алгоритм (Quadratic Congruentical Manipulation Detection Code, QCMDС);

Manipulation Detection Code (MDС);

Message Digest Algorithm (MD5);

контрольная сумма;

символ контроля блока (Block Check Character, BCC);

циклический избыточный код (ЦИК, Cyclic Redundancy Check, CRC);

хеш-функция (hash);

имитовставка в ГОСТ 28147-89;

алгоритм с усечением до n битов (n-bit Algorithm with Truncation).

При вычислении контрольной функции может использоваться какой-либо алгоритм шифрования. Возможно шифрование самой контрольной суммы.

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

Для использования алгоритма RSA сообщение следует сжать функцией хешировани (алгоритм MD5 - Message Digest Algorithm) до 256-битового хеша (H). Сигнатура сообщения S вычисляется следующим образом:

d
S = H mod n

Сигнатура пересылаетс вместе с сообщением.

Процесс идентификации заключается в получении хеш-функции сообщения (H") и сравнении с

e
H = S mod n

где H - хеш сообщения,

S - его сигнатура,

d - секретный ключ,
e - открытый ключ.

Проверке подлинности посвящены стандарты:

• проверка подлинности (аутентификация, authentication) - ISO 8730-90, ISO/IES 9594-90 и ITU X.509;
• целостность - ГОСТ 28147-89, ISO 8731-90;
• цифровая подпись - ISO 7498, P 34.10-94 (Россия), DSS (Digital Signature Standard, США).

ISO - Международная организация по стандартизации /МОС/,
ITU - Международный союз электросвязи /МСЭ/.

Реализаци алгоритмов шифрования

Алгоритмы шифровани реализуются программными или аппаратными средствами. Есть великое множество чисто программных реализаций различных алгоритмов. Из-за своей дешевизны (некoторые и вовсе бесплатны), а также все большего быстродействи процессоров ПЭВМ, простоты работы и безотказности они весьма конкурентоспособны. Широко известна программа Diskreet из пакета Norton Utilities, реализующая DES.

Нельзя не упомянуть пакет PGP (Pretty Good Privacy, версия 2.1, автор Philip Zimmermann), в котором комплексно решены практически все проблемы защиты передаваемой информации. Применены сжатие данных перед шифрованием, мощное управление ключами, симметричный (IDEA) и асимметричный (RSA) алгоритмы шифрования, вычисление контрольной функции для цифровой подписи, надежная генерация ключей.

Публикации журнала "Монитор" с подробными описаниями различных алгоритмов и соответствующими листингами дают возможность каждому желающему написать свою программу (или воспользоваться готовым листингом).

Аппаратная реализация алгоритмов возможна с помощью специализированных микросхем (производятся кристаллы для алгоритмов DH, RSA, DES, Skipjack, ГОСТ 28147-89) или с использованием компонентов широкого назначения (ввиду дешевизны и высокого быстродействия перспективны цифровые сигнальные процессоры - ЦСП, Digital Signal Processor, DSP).

Среди российских разработок следует отметить платы "Криптон" (фирма "Анкад") и "Грим" (методология и алгоритмы фирмы "ЛАН-Крипто", техническая разработка НПЦ "ЭЛиПС") .

"Криптон" - одноплатные устройства, использующие криптопроцессоры (специализированные 32-разрядные микроЭВМ, которые также называются "блюминг"). Блюминги аппаратно реализуют алгоритмы ГОСТ 28147-89, они состоят из вычислителя и ОЗУ дл хранения ключей. Причем в криптопроцессоре есть три области для хранения ключей, что позволяет строить многоуровневые ключевые системы.

Для большей надежности шифровани одновременно работают два криптопроцессора, и блок данных в 64 битов считается правильно зашифрованным, только если совпадает информаци на выходе обоих блюмингов. Скорость шифрования - 250 КБ/c.

Кроме двух блюмингов на плате расположены:

контроллер сопряжения с шиной компьютера (за исключением "Криптон-ЕС" платы рассчитаны на работу с шиной ISA);

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

датчик случайных чисел (ДСЧ) дл выработки ключей шифрования, выполненный на шумовых диодах.

Выпускаются следующие разновидности плат "Криптон":

• "Криптон-ЕС" предназначена дл ПЭВМ серии ЕС 1841-1845;
• "Криптон-3";
• "Криптон-4" (сокращены габаритные размеры за счет перемещения ряда дискретных элементов в базовые кристаллы, повышена скoрость обмена благодаря внутреннему буферу на 8 байт);
• "Криптон-ИК" дополнительно оснащена контроллером ИК (интеллектуальна карточка, смарт-карта, smart card).

В устройствах "Криптон-ЕС", "Криптон-3", "Криптон-4" ключи хранятся в виде файла на дискете. В "Криптон-ИК" ключи находятся на ИК, что затрудняет подделку и копирование.

В плате "Грим" используютс цифровые сигнальные процессоры фирмы Analog Devices ADSP-2105 и ADSP-2101, что дает скорость шифровани соответственно 125 и 210 КБ/c. На плате есть физический ДСЧ и ПЗУ с программами начального теста, проверки прав доступа, загрузки и генерации ключей. Ключи хранятся на нестандартно форматированной дискете. Плата реализует алгоритмы ГОСТ 28147-89 и цифровой подписи.

Для защиты информации, передаваемой по каналам связи, служат устройства канального шифрования, которые изготовляются в виде интерфейсной карты или автономного модуля. Скорость шифрования различных моделей от 9600 бит/с до 35 Мбит/c.

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

Криптология с открытым ключом

Борис Оболикшто

Казалось бы, толчок, данный Шенноном, должен был вызвать обвал результатов в научной криптологии. Но этого не произошло. Только бурное развитие телекоммуникаций, удаленного доступа к ЭВМ при несовершенстве существовавших криптосистем с секретным ключом вызвало к жизни следующий и, пожалуй, самый интересный этап криптологии, отсчет которому ведут от появившейся в ноябре 1976 года статьи Уитфилда Диффи и Марти E. Хеллмана "Новые направления в криптографии". Сам У. Диффи датирует получение опубликованных в ноябре 1976 года результатов маем того же года; таким образом, у нас есть повод с ма до ноября отмечать ДВАДЦАТИЛЕТНИЙ ЮБИЛЕЙ криптологии с открытым ключом.

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

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

• Алиса и Боб (привлечение в качестве сторон не абстрактных "А" и "Б", а симпатичных Алисы и Боба, стало традицией в этой области криптологии) выбирают случайные числа Хa и Хb соответственно.
• Алиса передает Бобу Ya =aXa (mod q) , а Боб Алисе - Yb =aXb (mod q) .

Здесь a - так называемый примитивный элемент конечного поля Галуа GF (q), замечательное для нас свойство которого заключается в том, что его степени дают все ненулевые значени элементов поля. В качестве секретного ключа используется значение

Ya =aXaXb (mod q) ,

которое Алиса получает возведением переданного Бобом числа в степень Xa , известную только ей, а Боб - полученного от Алисы числа в известную только ему степень Хb . Криптоаналитик вынужден вычислять логарифм по крайней мере одного из передаваемых чисел.

Устойчивость экспоненциального ключевого обмена базируется на так называемой односторонности функции возведения в степень: вычислительная сложность получения Ya из Xa при q длиной 1000 битов - порядка 2000 умножений 1000 битовых чисел, в то время как обратная операция потребует примерно 1030 операций. ОДНОСТОРОННИЕ функции, обладающие подобной асимметрией вычислительной сложности прямой и обратной задачи, играют ведущую роль в криптографии с открытым ключом.

Еще более интересна односторонн функция с потайным ходом ("лазейкой"). Иде состоит в том, чтобы построить функцию, обратить которую можно только зная некоторую "лазейку" - секретный ключ. Тогда параметры функции служат открытым ключом, который Алиса может передать по незащищенному каналу Бобу; Боб, используя полученный открытый ключ, выполняет шифрование (вычисление прямой функции) и передает по тому же каналу результат Алисе; Алиса, зная "лазейку" (секретный ключ), легко вычисляет обратную функцию, тогда как криптоаналитик, не зная секретного ключа, обречен на решение намного более сложной задачи.

Такую функцию в 1976 году удалось построить Р. Мерклю (R.C. Merkle) на основе задачи об укладке ранца. Сама по себе задача - односторонняя: зна подмножество грузов, уложенных в ранец, легко подсчитать суммарный вес, но зная вес, непросто определить подмножество грузов. В нашем случае использовался одномерный вариант задачи: вектор грузов и сумма компонентов его подвекторов. Встроив "лазейку", удалось получить так называемую ранцевую систему Меркля-Хелмана. Первая криптосистема с открытым ключом заработала, и Меркль предложил $100 тому, кто сможет ее раскрыть.

Награда досталась А. Шамиру (Adi Shamir) шесть лет спустя после публикации им в марте 1982 года сообщения о раскрытии ранцевой системы Меркля-Хелмана с одной итерацией. На конференции Crypto"82 Л. Адлман (L. Adleman) продемонстрировал на компьютере Apple II раскрытие ранцевой системы. Заметим, что Шамир не построил способ обращени задачи - получения значения секретного ключа, он сумел построить ключ, не обязательно равный секретному, но позволяющий раскрыть шифр. В этом таится одна из наибольших опасностей дл криптографии с открытым ключом: нет строгого доказательства односторонности используемых алгоритмов, т. е. никто не гарантирован от возможности нахождения способа дешифрования, вероятно, и не требующего решения обратной задачи, высокая сложность которой позволяет надеяться на практическую стойкость шифра. Хорошо, если раскрытие той или иной системы проведет ученый с мировым именем (в 1982 году А. Шамир уже был известен как один из авторов системы RSA). А если это удастся нечестолюбивому хакеру?

В заключение драмы о ранцевой системе упомянем еще об одном пари, которое Меркль заключил с желающими раскрыть усовершенствованную систему с многими итерациями на сумму $1000. И эту сумму пришлось заплатить. Ее получил Э. Брикелл, раскрыв летом 1984 года систему с сорока итерациями и со ста посылками за час работы Cray-1.

Значительно более удачна на сегодняшний день судьба системы RSA, названной так по первым буквам фамилий ее авторов Р. Ривеста (Ronald Rivest) и уже знакомых нам А. Шамира и Л. Адлмана. Кстати, именно первому систематическому изложению алгоритма RSA обязаны своим появлением на свет Алиса и Боб. С их "помощью" авторы в 1977 году описали систему на основе односторонних свойств функции разложения на простые множители (умножать просто, а разлагать - нет).

Развитие криптологии с открытым ключом позволило криптологическим системам довольно быстро найти широкое коммерческое применение. Но интенсивное использование криптографии не обходится без "накладок". Время от времени мы узнаем о неприятностях в той или иной системе защиты. Последним нашумевшим в мире происшествием стал взлом системы Kerberos. Система эта, разработанная в середине 80-х годов, довольно популярна в мире, и ее взлом вызвал немалое беспокойство пользователей.

В случае с Kerberos неприятность заключалась не в алгоритме шифрования, а в способе получени случайных чисел, т. е. в методе реализации алгоритма. Когда в октябре прошлого года пришло известие о просчетах в системе генерации случайных чисел в программных продуктах Netscape, обнаруженных студентами университета Беркли, Стивен Лодин обнаружил подобную неприятность в Kerberos. Совместно с Брайаном Доулом он сумел найти брешь и в системе Kerberos. Действующие лица этой истории - не дилетанты. Выпускники университета Purdue (штат Иллинойс) сотрудничали с лабораторией COAST (Computer Operations, Audit, and Security Technology), профессионально занятой вопросами компьютерной безопасности и руководимой проф. Спаффордом, который является также основателем PCERT (Purdue Computer Emergency Response Team) - университетского отряда "быстрого реагирования" на компьютерные ЧП. PCERT, в свою очередь, член аналогичной международной организации FIRST (Forum of Incident Response Teams). Как видим, мину нашли саперы, а это внушает надежду, что пользователи криптосистем не останутся беззащитными даже в случае выявлени недоработок.

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

Не обошли ошибки и наши пенаты. К счастью, есть в наших краях профессионалы, способные своевременно найти и показать слабые места системы защиты. Еще месяц не прошел с тех пор, как специалистами киевского ООО "Финтроник" П.В. Лесковым и В.В. Татьяниным продемонстрированы недостатки одной из популярных банковских систем защиты: время вскрытия шифротекстов составило менее 6 минут, а время, необходимое дл неконтролируемого нарушения целостности документа (обход системы аутентификации), - менее 5 минут. И здесь нам, читатель, также придетс подождать, пока разработчики внесут необходимые изменения. А уж затем мы сможем рассказать подробнее о том, как и что было сделано.

Литература:

1. Водолазский В. Коммерческие системы шифрования: основные алгоритмы и их реализация. Часть 1. // Монитор. - 1992. - N 6-7. - c. 14 - 19.
2. Игнатенко Ю.И. Как сделать так, чтобы?.. // Мир ПК. - 1994. - N 8. - c. 52 - 54.
3. Ковалевский В., Максимов В. Криптографические методы. // КомпьютерПресс. - 1993. - N 5. - c. 31 - 34.
4. Мафтик С. Механизмы защиты в сетях ЭВМ. - М.: Мир, 1993.
5. Спесивцев А.В., Вегнер В.А., Крутяков А.Ю. и др. Защита информации в персональных ЭВМ. - M.: Радио и связь, 1992.
6. Сяо Д., Керр Д., Мэдник С. Защита ЭВМ. - М.: Мир, 1982.
7. Шмелева А. Грим - что это? // Hard"н"Soft. - 1994. - N 5.
8. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

09.07.2003

Что такое шифрование?

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

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

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

Основные современные методы шифрования

Среди разнообразнейших способов шифровании можно выделить следующие основные методы:

• Алгоритмы замены или подстановки - символы исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой криптостойкости.
• Алгоритмы перестановки - символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.
• Алгоритмы гаммирования - символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов "имя пользователя.pwl", в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUp-доступа в Интернет и т.д.).

Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.

• Алгоритмы, основанные на сложных математических преобразованиях исходного текста по некоторой формуле. Многие из них используют нерешенные математические задачи. Например, широко используемый в Интернете алгоритм шифрования RSA основан на свойствах простых чисел.

Симметричные и асимметричные криптосистемы

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

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

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

В асимметричных системах должно удовлетворяться следующее требование: нет такого алгоритма (или он пока неизвестен), который бы из криптотекста и открытого ключа выводил исходный текст. Пример такой системы - широко известная криптосистема RSA.

Алгоритм RSA

Алгоритм RSA (по первым буквам фамилий его создателей Rivest-Shamir-Adleman) основан на свойствах простых чисел (причем очень больших). Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.

Для начала выберем два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита).

Определим параметр n как результат перемножения p и q . Выберем большое случайное число и назовем его d , причем оно должно быть взаимно простым с результатом умножения (p -1)*(q -1) .

Отыщем такое число e, для которого верно соотношение

(e*d) mod ((p -1)*(q -1)) = 1

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

Открытым ключом является пара чисел e и n , а закрытым - d и n .

При шифровании исходный текст рассматривается как числовой ряд, и над каждым его числом мы совершаем операцию

C(i)= (M(i) e) mod n.

В результате получается последовательность C(i) , которая и составит криптотекст. Декодирование информации происходит по формуле

M(i) = (C(i) d) mod n.

Как видите, расшифровка предполагает знание секретного ключа.

Давайте попробуем на маленьких числах.

Установим p=3, q=7 . Тогда n=p*q=21. Выбираем d как 5. Из формулы (e*5) mod 12=1 вычисляем e=17 . Открытый ключ 17, 21 , секретный - 5, 21 .

Зашифруем последовательность «12345»:

C(1)= 1 17 mod 21= 1

C(2)= 2 17 mod 21 =11

C(3)= 3 17 mod 21= 12

C(4)= 4 17 mod 21= 16

C(5)= 5 17 mod 21= 17

Криптотекст - 1 11 12 16 17.

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

M(1)= 1 5 mod 21= 1

M(2)= 11 5 mod 21= 2

M(3)= 12 5 mod 21= 3

M(4)= 16 5 mod 21= 4

M(5)= 17 5 mod 21= 5

Как видим, результат совпал.

Криптосистема RSA широко применяется в Интернете. Когда вы подсоединяетесь к защищенному серверу по протоколу SSL, устанавливаете на свой ПК сертификат WebMoney либо подключаетесь к удаленному серверу с помощью Open SSH или SecureShell, то все эти программы применяют шифрование открытым ключом с использованием идей алгоритма RSA. Действительно ли эта система так надежна?

Конкурсы по взлому RSA

С момента своего создания RSA постоянно подвергалась атакам типа Brute-force attack (атака методом грубой силы, т. е. перебором). В 1978 г. авторы алгоритма опубликовали статью, где привели строку, зашифрованную только что изобретенным ими методом. Первому, кто расшифрует сообщение, было назначено вознаграждение в размере 100 долл., но для этого требовалось разложить на два сомножителя 129-значное число. Это был первый конкурс на взлом RSA. Задачу решили только через 17 лет после публикации статьи.

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

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

Один из самых распространенных в России почтовых клиентов, программа The Bat!, обладает встроенными возможностями добавлять цифровые подписи к письмам (обратите внимание на пункт меню Privacy при редактировании письма). Подробнее об этой методике читайте в статье (см. «Мир ПК», № 3/02).

Рис. 3

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

Криптография - наука о принципах, средствах и методах преобразования информации для защиты ее от несанкционированного доступа и искажения. В последнее время она развивается очень и очень бурно. Это бесконечная увлекательная гонка, требующая много времени и сил: криптоаналитики взламывают алгоритмы, которые еще недавно были стандартами и повсеместно использовались. Кстати, недавно математики Дэн Голдстон (США) и Кем Илдирим (Турция) доказали первую закономерность в распределении простых чисел (до сих пор таких закономерностей не замечали). Простые числа располагаются на числовой оси некоторыми скоплениями, что несколько облегчает их поиск.

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

Олег Бунин - специалист по разработке ПО для крупных Интернет-проектов, сотрудник компании «Рамблер», [email protected] .

Литература

1. Лукашов И. В. Криптография? Железно! // Мир ПК. 2003. № 3 (
2. Носов В. А. Краткий исторический очерк развития криптографии // Материалы конференции "Московский университет и развитие криптографии в России", МГУ, 17-18 октября 2002 г.
3. Саломаа А. Криптография с открытым ключом. М., 1996 .
4. Циммерман Ф. PGP - кодирование с открытым ключом для всех.

Система шифрования Цезаря

Пример алгоритма замены - система шифрования Цезаря. Этот метод основан на замене каждой буквы сообщения на другую путем смещения от исходной на фиксированное количество символов. Попробуйте расшифровать четверостишие Омара Хайяма (время выполнения - 10 минут).

РЛЗЬ ЁМЭЙЗ АВБЖУ ИЙЗАВЛУ, БЖЩЛУ ЖЩЭЗЬЖЗ ЖЮЁЩЕЗ, ЭЫЩ ЫЩАЖФО ИЙЩЫВЕЩ БЩИЗЁЖВ ЭЕШ ЖЩРЩЕЩ: ЛФ ЕМРСЮ ЪЗЕЗЭЩГ, РЮЁ РЛЗ ИЗИЩЕЗ ЮКЛУ, В ЕМРСЮ ЬМЭУ ЗЭВЖ, РЮЁ ЫЁЮКЛЮ К ДЮЁ ИЗИЩЕЗ.

Успели? Привожу «отгадку»:

Чтоб мудро жизнь прожить, знать надобно немало,

Два важных правила запомни для начала:

Ты лучше голодай, чем что попало есть,

И лучше будь один, чем вместе с кем попало.

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

Windows и пароли

Как Windows шифрует пароли?

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

Конкурс AES (Advanced Encryption Standard)

В 80-х гг. в США приняли стандарт симметричного шифрования для внутреннего применения - DES ((Data Encryption Standard, подобный стандарт есть и в России). Но в 1997 г., когда стало понятно, что 56-битового ключа DES недостаточно для надежной криптосистемы, Американский институт стандартизации объявил конкурс на новый стандартный алгоритм. Из 15 вариантов был выбран лучший: бельгийский алгоритм Rijndael (его название составлено из фамилий авторов - Rijmen и Daemen, читается как «Рэйндал». Этот алгоритм уже встроен в различные криптографические средства, поставляемые на рынок). Другими финалистами конкурса стали MARS, RC6, Serpent, TwoFish. Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.

Криптографические хэш-функции

Криптографические хэш-функции преобразуют входные данные любого размера в строку фиксированного размера. Для них чрезвычайно сложно найти:

• два разных набора данных с одинаковым результатом преобразования (стойкость к коллизиям); например, количество арифметических операций, необходимых для того, чтобы найти блок данных, также имеющий краткое сообщение для хэш-функции MD5, составляет приблизительно 2 64;
• входное значение по известному результату хэширования (необратимость); для MD5 предполагаемое количество операций, необходимых для вычисления исходного сообщения, равно 2 128.

Занимательное шифрование