Информационная безопасность. Стандарты и алгоритмы шифрования

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

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

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

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

Наиболее современные системы шифрования используют асимметричные алгоритмы с открытым и секретным ключами, где нет проблемы безопасной транспортировки ключа. К числу таких систем относится алгоритм RSA (Rivest-Shamir-Adleman — разработчики этой системы — Рональд Ривест, Ади Шамир и Леонард Адлеман, 1977 год), базирующийся на сложности разложения больших чисел на множители.

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

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

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

Если хакер умудрится вставить свою ЭВМ в разрыв канала, соединяющего субъектов А и В, у него появляется возможность перехватывать в том числе и шифрованные сообщения. Пусть субъект А сформировал пару ключей К1А и К2А (ключ с индексом 2 является секретным), аналогичную пару ключей сгенерировал субъект В ( К1В и К2В ). Хакер же тем временем подготовил две пары ключей ( К1ХА: К2ХА и К1ХВ: К2ХВ ). Когда субъект А пошлет открытый ключ К1А субъекту В, хакер его подменит ключом К1ХА. Аналогичную процедуру он проделает с ключом К1В, посланным от В к А. Теперь сообщение А к В, зашифрованное с помощью ключа К1ХА, будет послано В. Хакер его перехватывает, дешифрует с помощью ключа К2ХА, шифрует с помощью ключа К1В и посылает В. Субъект В, получив послание, дешифрует его с помощью своего секретного ключа К2В. Аналогичная процедура будет проведена и при посылки сообщения от В к А. В сущности, единственным параметром, который изменится существенным образом, будет время доставки сообщения, так как это время будет включать дешифровку и повторную шифровку сообщения. Но при использовании быстродействующей ЭВМ и при работе с традиционной электронной почтой это может оказаться незаметным. Понятно, что между А и В появится дополнительный шаг (hop). Но и это может быть легко замаскировано под прокси сервер или Firewall.

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

Начиная с 1997 года NIST (National Institute for Standards and Technology) совместно с промышленностью и криптографическим сообществом разрабатывал преемника для алгоритма DES (длина ключа 56 бит). В результате был создан алгоритм , http://csrc.nist.gov и http://www.x9.org) специфицирует еще шесть различных блочных шифров (см. таблицу 14.2.)

Базовые характеристики блочных алгоритмов шифрования представлены в таблице 14.3 (смотри http://book.itep.ru/6/idea_647.htm, ~6/des_641.htm и ~6/safr_648.htm).

Относительные уровни безопасности разных алгоритмов представлены в таблице 14.4.

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

В настоящее время имеется три семейства криптосистем с открытым ключом.

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

Согласно закону Мура, плотность компонентов на чип удваивается каждые 18 месяцев. Это можно интерпретировать как удвоение вычислительной мощности ЭВМ каждые 18 месяцев.

Развитие методов программирования и повышение быстродействия ЭВМ приводит к понижению надежности систем шифрования. Симметричные шифры теряют один бит безопасности в год. Хэш-функции и схемы, основанные на эллиптических кривых (ISO/IEC 15946-2), теряют два бит безопасности в год. RSA -схемы теряют 30 бит безопасности в год. На рис 14.2 показана временная зависимость деградации безопасности шифров (см. Network Security, V2004, Issue 12, декабрь 2004, стр. 6-11).

Полезную информацию по системам шифрования можно получить на следующих серверах:

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

Из числа широко используемых приложений можно выделить безопасную электронную почту PGP (Pretty Good Privacy, см. http://book.itep.ru/6/pgp_644.htm), которая базируется на двух ключевой системе шифрования RSA и алгоритме IDEA (International Data Encryption Algorithm).

Но наиболее важным приложением современной криптографии являются электронные платежные системы (например, протокол SET, см. http://book.itep.ru/4/6/set_66.htm) и кредитные smart-карты. Несколько особняком стоят электронные монеты, формирование которых базируется формировании кодов с кратными хэш-совпадениями. Современный документооборот немыслим без электронных подписей.

Далее более детально будут описаны алгоритмы AES и RSA.

Алгоритм шифрования RSA

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

Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M), и только адресату известно, как выполнить операцию f-1 (дешифрацию) Адресат выбирает два больших простых числа p и q, которые делает секретными. Он объявляет n=pq и число e, c (e,p-1)=(e,q-1)=1 (e,p-1) и (e,q-1) – наибольший общий делитель для e и р-1 (соответственно e и q-1 ). Один из возможных способов выполнить это условие, выбрать e больше чем p/2 и q/2 ). Комбинация n и e представляет собой открытый ключ. Шифрование производится по формуле:

где M и f(M) оба <= n-1. Такое преобразование может быть выполнено за разумное время, даже если M, e и n содержит весьма большое число знаков. Адресат вычисляет M на основе Me, используя свое знание p и q.

Исходный текст M получается адресатом из зашифрованного f(M) путем преобразования:

M = (f(M))d (mod n).

Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа. Значение d вычисляется из e, если известны p и q, на основе соотношения.

Так как (Me)d - M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA -алгоритм запатентован (20 сентября 1983, патент действовал до 2000 года).

Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.

Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно — надо знать все возможные значения Mi.

Поясним использование алгоритма RSA на конкретном примере. Выбираем два простые числа p=7; q=17 (на практике эти числа во много раз длиннее). В этом случае n = p*q будет равно 119. Теперь необходимо выбрать e, выбираем e=5. Следующий шаг связан с формированием числа d так, чтобы d*e=1 mod [(p-1)(q-1)]. d=77 (использован расширенный алгоритм Эвклида). d — секретный ключ, а e и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать, представляется M=19. С = Memod n. Получаем зашифрованный текст C=66. Этот "текст" может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М=Cdmod n и C=66. В результате получается M=19.

На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1 Мбайт/сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма.

Стандарт шифрования AES

Стандарт (смотри также http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf). Этот алгоритм представляет собой симметричный блочный шифр, который работает с блоками данных длиной 128 бит и использует ключи длиной 128, 192 и 256 бит (версии AES-28; AES-192 и AES-256). Сам алгоритм может работать и с другими длинами блоков данных и ключей, но эта возможность в стандарт не вошла.

Биты данных нумеруются с нуля, начиная со старших. В AES основным является полиномиальное представлением кодов. Так, байт { 01100011 } следует представлять как: x6 +x5 + x + 1.

Алгоритм AES производит операции над двумерными массивами байт, называемыми структурами (state). Структура состоит из 4 рядов по Nb байт. Nb равно длине блока, деленной на 32 (в данном стандарте Nb=4 ). Это позволяет обозначать структуру как sr,c или s[r,c], где 0<=r<4 и 0<=c<4.

Входной код (in), который является последовательностью 16 байт можно представить как:

s[r,c] =in[r +4c]

При реализации алгоритма AES используются операции сложения байт (по модулю 2 = XOR) и умножения. В алгоритме AES при умножении байтов используется неприводимый многочлен:

m(x) = x8 + x4 + x3 + x + 1

Вычисление произведения М байтов {b1} на {b2} здесь выполняется согласно следующему алгоритму:

В этом случае обратная величина байта равна:

{b}-1 ={b} mod m(x)

для умножения полубайтов (коды длиной 4 бита) используется неприводимый полином:

m2(x) = x4 + 1

Вычисление произведения М полубайтов {a} на {b} здесь выполняется следующим образом:

M представляет собой полубайт d. Операцию умножения полубайтов {a} на {b} можно записать в матричном виде:

Как было сказано выше, длины ключей Nk (длина, измеренная в 32 битных словах) могут принимать значения 4, 6 или 8 (для AES-128, -192 и -256, соответственно). Число итераций Nr (round), реализуемых в алгоритме AES составляет соответственно 10, 12 и 14.

Шифрование

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

Описание алгоритма в С-подобном представлении отображено на рис 14.3. Преобразования SubByte(), ShiftRows(), MixColumns() и AddRoundKey() осуществляют обработку массива state. Массив w[i] описан ниже.

Преобразование SubByte()

Преобразование SubByte() является нелинейной подстановкой байтов, которое работает независимо для каждого байта State и использует таблицу подстановок S. Эта замена включает в себя две операции.

Преобразование ShiftRows()
В преобразованиях ShiftRows()  байты в последних трех рядах State  циклически сдвигаются на разное число байт. Первый ряд ( r=0 ) не сдвигается. Преобразование ShiftRows() осуществляется следующим образом:
s'= S
r,c   r,(c + shift(r, Nb)) mod Nb  для 0<r<4 и 0<=c<Nb
где величина сдвига shift(r,Nb)  зависит от номера ряда r  следующим образом:
shift(1,4)=1;  shift(2,4)=2;  shift(3,4)=3.

Преобразование MixColumns()
Преобразование MixColumns()  обрабатывает State  колонка за колонкой, каждая из колонок представляет собой 4-битный код. Колонки рассматриваются как полиномы над полем GF(28). Колонка умножается на фиксированный полином {a}={03}x3+{01}x2+{01}x+ {02} по модулю x4+1  (см. формулу 2а).

Преобразование AddRoundKey()
В преобразовании AddRoundKey()  к State  добавляется ключ итерации (Round Key; побитовая операция XOR). Операция производится для каждого байта State.

Процедура расширения ключа
Ключи итерации вычисляются на основе ключа шифрования с помощью процедуры преобразования ключа (Key expansion). Эта процедура формирует 
Функция SubWord()  работает с входными байтами, преобразуя их с помощью S-таблиц. Операция выполняется для каждого из 4 входных байт.
Функция RotWord()  использует в качестве входного слова [a0,a1,a2,a3]  и возвращает слово [a1,a2,a3,a0].
(рис 14.4) Псевдокод реализации процедуры преобразования ключа.
Расшифровка
Все процедуры, описанные в предыдущем разделе, являются обратимыми. Целью дешифровки является обработка зашифрованного массива данных с целью получения исходного блока данных. Процедуры дешифровки включают в себя функции .
(рис 14.5) Псевдокод процедуры дешифровки
Преобразование InvShiftRows()
Процедура InvShiftRows()  является обратной по отношению ShiftRows(). Байты в последних трех рядах State  циклически сдвигаются на разное число байт. Первый ряд ( r=0 ) не сдвигается.

Преобразование InvSubBytes()
Преобразование InvSubBytes()  является обратной подстановкой байт, в которой S-таблица последовательно применяется для каждого из байтов State. Это достигается за счет обратного аффинного преобразования.

Преобразование InvMixColumns()
Процедура InvMixColumns()  является обратной по отношению MixColumns(). Колонки рассматриваются как полиномы над полем GF(28).

Обратное преобразование AddRoundKey()
Преобразование AddRoundKey()  является обратимым, так как содержит только операции XOR.

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