2. Криптографические методы защиты информации

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

2.1. Термины и определения

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

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

{ F_k: X  S, kK },

где XX – кодируемое сообщение из множества открытых текстов;

SS – шифротекст из множества возможных закодированных текстов;

k – ключ шифрования;

F – отображение, выполняемое шифром.

Свойство инъективности шифра означает, что существует отображение F^-1 такое, что

{ F_k^-1: X  S, kK }

Процесс преобразования открытого текста (передаваемого сообщения) в шифротекст называется шифрованием. Обратное преобразование шифротекста в открытый текст называется дешифрованием.

Криптоанализ - наука (и практика ее применения) о методах и способах вскрытия шифров. Под вскрытием понимается задача получения по известному шифротесту соответствующего открытого текста и/или ключа шифрования.

Криптография и криптоанализ вместе образуют криптологию.

2.2. Классификация криптографических алгоритмов

В качестве основного критерия классификации криптографических алгоритмов будем использовать тип выполняемого над исходным текстом преобразования. Классификация по этому критерию представлена на рис. 2.1.

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

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

К риптосистемы с ключом делятся на симметричные и асимметричные системы шифрования. Модель симметричной системы шифрования представлена на рис. 2.2.

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

Асимметричная система шифрования работает по схеме, представленной на рис. 2.3.

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

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

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

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

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

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

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

Атака на основе открытого текста предполагает, что криптоаналитику известны одна или несколько пар «открытый текст/шифротекст», зашифрованных на одном ключе, и на основе этой информации он проводит свой анализ.

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

2.3. Симметричное блочное шифрование

2.3.1. Основные принципы блочного симметричного шифрования

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

Y=Encrypt(X,Key)

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

X=Decrypt(Y,Key)

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

X=Encrypt((Encrypt(X,Key),Key)

Преобразования Encrypt и Decrypt трактуют блоки открытого и зашифрованного текста как целые числа и выполняет над ними ряд арифметических либо логических действий, основная задача которых – тщательно «перемешать» биты блока открытого текста между собой, а также связать их с битами используемого ключа шифрования для формирования блока закрытого текста. Для того, чтобы все шифрующее преобразование было обратимым, действия, его составляющие должны быть также обратимы (обратимость действия означает, что по его результату и одному из операндов можно получить второй операнд). В таблице 2.1 приведен список обратимых операций, использующихся в современных криптографических преобразованиях [6].

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

Таблица 2.1

Основные обратимые операции

Название операции	Графическое обозначение	Формула преобразования	Обратное преобразование
Сложение		X’=X+V	Вычитание
Сложения по модулю 2		X’=X  V	Автообратима
Умножение по модулю 2N+1 (N- размер блока)		X’=(XV) mod (2N+1)	Сомножитель можно найти по алгоритму Евклида
Циклические сдвиги вправо/влево		X’=X ROR V X’=X ROL V	Циклический сдвиг в обратном направлении
Табличная подстановка		X’=SBox(X)	Обратная подстановка

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

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

1. фиксированные числовые константы;

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

3. материал ключа – блок информации, вычисленный исключительно на основе информации, хранящейся в ключе шифрования.

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

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

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

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

Если размер блока шифрования криптоалгоритма слишком велик, возможны модификации сети Фейштеля с 4 ветвями, один из вариантов которых приведен на рис. 2.5.

2.3.2. Алгоритмы блочного симметричного шифрования

Схема Фейштеля используется в криптоалгоритмах DES, ГОСТ 28147-89, FEAL, Blowfish, LOKI, CAST и др. Рассмотрим практическую реализацию блочного шифра, построенного по принципу сети Фейштеля, на примере алгоритма TEA (Tiny Encrypton Algorithm) .

А

Рис.2.6. Схема работы алгоритма TEA

лгоритм TEA (рис.2.6) разработан в Кембриджском университете, представляет собой схему сети Фештеля на 64 раунда, размер шифруемого блока 64 бита, размер ключа шифрования 128 бит.

Рис.2.6. Схема работы алгоритма TEA

Д остоинством алгоритма TEA является простота реализации, однако, отсутствие в образующей функции нелинейных операций приходится компенсировать большим количеством раундов. КEY0, КEY1, КEY2, КEY3 на рис.2.6 – это ключи раунда, которые получаются простым делением ключа шифрования на 4 части. Необходимо также отметить, что TEA является несимметричным алгоритмом, поскольку ветви смешиваются обычным арифметическим сложением, поэтому операция дешифрации требует незначительных изменений.

А лгоритмы шифрования, получившие большее признание среди криптографов, используют в функциях преобразования нелинейные операции. Так, например, алгоритм шифрования DES (Data Encryption Standard), который до недавнего времени являлся мировым стандартом шифрования, использует в своей образующей функции операции табличной подстановки, которые существенно усложняют процедуру линейного криптоанализа этого шифра. Схема раунда алгоритма DES представлена на рис. 2.7.

Каждый раунд преобразования включает перестановку правой части блока, причем на вход модуля расширения подается 32-разрядное число, а снимается с него 48-разрядное (некоторые биты входного числа копируются на выход дважды). После сложения с материалом ключа осуществляется табличная подстановка, в результате которой по 8 таблицам подстановки происходит замена 48-битного входа на 32-битный выход (каждая S-таблица подстановки заменяет 6-битный вход на 4-битный выход). Выход S-блока поступает на блок перестановки, где биты переставляются по законам, определяемым специальной P-таблицей. Заканчивается раунд традиционным для сетей Фейштеля смешиванием ветвей между собой. За счет использования нелинейных операций преобразований удалось уменьшить количество раундов до 16 при размере ключа 56 бит.

С момента опубликования алгоритма DES в 1977 году он подвергся серьезному криптоанализу. Так, в частности, были обнаружены 4 слабых ключа DES, которые половину из возможных 2⁶⁴ входных блоков кодируют самих в себя. Был предложен также ряд специфических атак на DES, которые еще в 80-е годы позволяли с использованием компьютеров специализированной архитектуры или распределенных вычислений провести успешную атаку на алгоритм в течение нескольких часов. Для современного технологического уровня время взлома шифра DES составляет несколько десятков минут. В связи с этим, для обеспечения более высокого криптостойкости рекомендуется применять тройное DES-шифрование на трех или двух различных ключах. Такие схемы называются EDE (encrypt-decrypt-encrypt) шифрованием. При двух ключах шифрования блок открытого текста сначала шифруется на ключе K₁, затем дешифруется на ключе K₂, а затем вновь шифруется на ключе K_1. Размер ключевого пространства (общее количество возможных ключей шифрования) в этом случае возрастает до 2¹¹² (у обычного DES – 2⁵⁶). При использовании трех ключей шифрования блок открытого текста сначала шифруется на ключе K₁, затем дешифруется на ключе K₂, а затем шифруется на ключе K₃, что обеспечивает размер ключевого пространства 2¹⁶⁸.

Из-за недостаточной длины ключа шифрования, а также ориентированности шифра DES на аппаратную реализацию (в связи с большим количеством используемых перестановок бит), американским национальным институтом стандартов в 1997 был объявлен конкурс на криптостандарт блочного шифрования AES (Advanced Encryption Standard). В 2000 году победителем конкурса был объявлен алгоритм Rijndael, разработанный бельгийскими криптографами. Его отличительной особенностью является то, что он построен не по принципу сети Фейштеля, а использует нетрадиционную структуру KALST- сети.

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

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

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

Российским стандартом блочного шифрования является алгоритм ГОСТ 28147-89, построенный по структуре сети Фейштеля. Его особенностью следует признать большой размер ключа (256 бит), непубликуемые таблицы подстановки, большое количество раундов (32 раунда).

2.3.3. Режимы шифрования блочных шифров

Применение блочного шифра для нужд практического кодирования информации возможно в одном из четырех основных режимов шифрования (рис. 2.8):

1. режим электронной кодовой книги (Electronic Code Book, ECB);

2. режим сцепления блоков шифра (Cipher Block Changing, CBC);

3. режим обратной связи по шифротексту (Electronic Feedback, CFB);

4. режим обратной связи по выходу (Output Feedback, OFB).

В режиме ECB шифрование/дешифрование i-го блока открытого текста/шифротекста выполняется независимо от остальных блоков:

c_i=E_k(m_i), m_i=D_k(c_i).

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

Режим CBC предполагает следующие алгоритмы шифрации/дешифрации:

c_i=E_k(m_i  c_i-1), m_i=D_k(c_i)  c_i-1

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

В режиме CFB также происходит «маскировка» блока открытого текста уже зашифованными блоками:

c_i=m_i  E_k(c_i-1), m_i=D_k(c_i-1)  c_i

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

В режиме OFB исходное сообщение вообще не подвергается криптопреобразованию, оно складывается с шифруемыми на секретном ключе блоками s_i (s₀ является задаваемым несекретным параметром режима):

c_i=m_i  s_i , m_i=c_i  s_i, s_i=E_k(s_i-1)

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

2.3.4. Криптоанализ блочных шифров

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

C_k(j)=(j+k)(mod n),

где n - количество букв в алфавите, k- ключ шифрования, j – номер шифруемого символа в алфавите. Очевидно, что обратной подстановкой является

C_k(j)=(j+n-k)(mod n)

Частотный анализ использует то свойство зашифрованного текста, что частота встречаемости символов в нем совпадает с частотой встречаемости соответствующих символов в открытом тексте. Если же учесть, что частоты встречаемости различных символов в текстах соответствующего языка распределены неравномерно (так, например, относительная частота встречаемости буквы «А» в текстах на русском языке составляет 0.069, а буквы «Ф» 0.003), то, подсчитав относительную частоту встречаемости букв в шифротексте, можно предположить, что символ, наиболее часто встречающийся в шифротексте, соответствует символу, наиболее часто встречающемуся в текстах на соответствующем языке, и найти таким образом ключ k. Такой метод криптоанализа применим только к моноалфавитным криптоалгоритмам, и для его успешной работы требуются тексты большого размера.

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

Дифференциальный метод криптоанализа был предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ представляет собой атаку на основе выборочного шифротекста. В качестве материала для анализа используется изменение меры несходства двух открытых текстов при их прохождении по основным этапам криптопреобразования. В качестве меры несходства двух двоичных векторов используется расстояние Хэмминга – количество бит, в которых эти вектора отличаются друг от друга.

Успех попыток вскрытия r-циклического шифра зависит от существования дифференциалов (r-1)-го цикла c большей долей вероятности. Дифференциал i-го цикла определяется как пара ( a , b ) _i такая, что пара различных открытых текстов x, x* c расстоянием Хэмминга a может привести к паре выходных текстов y, y* после i-ого цикла, имеющих расстояние Хэмминга b. Вероятность i-циклового дифференциала ( a ,b ) _i - это условная вероятность P( D _y(i)=b | D _x(i)= a ) того, что расстояние Хэмминга пары шифртекстов ( y, y*) после i-ого цикла равна b при условии, что пара текстов (x, x*) имеет расстояние a.

Алгоритм дифференциального криптоанализа включает следующие этапы:

1. На предварительном этапе путем многократного шифрования различных текстов накапливаем статистику для множества (r-1)-цикловых дифференциалов (a1, b1)_r-1 ,

(a2,b2)_r-1 ,.... (as,bs)_r-1 . Упорядочиваем это множество дифференциалов по величине их вероятности.

2. Выбираем открытый текст x произвольным образом и подбираем x* так, чтобы расстояние Хэмминга между x и x* было равно a1 . Тексты x и x* шифруются на подлинном ключе и после r циклов получаем пару шифртекстов y , y*. Предполагаем, что на выходе предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной: D_y(r-1)= b1 . Для тройки ( D _y(r-1), y , y*) находим каждое возможное значение подключа последнего цикла к(r) . Добавляем его к количеству появлений каждого такого значения подключа к(r) .

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

4. Повторяем пп.1-3 для предпоследнего цикла, при этом значения y(r-1) вычисляются расшифрованием шифртекстов на найденном подключе последнего цикла к(r) . Далее действуем аналогично, пока не будут раскрыты ключи всех циклов шифрования.

Для успешного осуществления дифференциального криптоанализа необходимо иметь большой набор пар открытый текст/шифротекст (до 2⁴⁷ подобных пар для атаки на 16 раундов DES). Повышение стойкости шифра к дифференциальному криптоанализу возможно путем увеличения количества раундов: для алгоритма DES при 17 раундах шифрования дифференциальный криптоанализ не эффективнее силовой атаки.

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

m_i1  m_i2  …  m_ir  c_j1  c_j2  … c_js = k_t1  k_t2  … k_tn, (2.1)

где i1..ir, j1..js, t1..tn – позиции некоторых бит открытого текста m, шифротекста c и ключа k.

Пусть p - вероятность того, что (2.1) выполняется для случайно выбранных m и с. Тогда необходимо, чтобы p  1/2 и величина | p -1/2 | должна быть как можно больше. Если | p -1/2 | достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части (2.1) равна наиболее вероятному значению суммы по модулю 2 соответствующих бит открытых и зашифрованных текстов в левой части. Если p > 1/2, то сумма бит ключа в правой части (2.1) равна нулю, если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части (2.1) равна единице, если сумма бит в левой части равна единице больше, чем для половины текстов . Если p < 1/2 , то наоборот, сумма бит ключа в правой части (2.1) равна нулю, если сумма бит в левой части равна единице больше, чем для половины пар открытых и зашифрованных текстов, и сумма бит ключа в правой части (2.1) равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Таким образом формируется система линейных уравнений, неизвестными в которых являются биты ключа, и задача дальнейшего анализа заключается в поиске решения этой системы. Для увеличения стойкости алгоритма к линейному криптоанализу в его состав вносят нелинейные функции преобразования (например, табличные подстановки).

Силовая атака на блочные шифры предполагает полный перебор всех возможных ключей шифрования, и ее эффективность зависит от размера ключевого пространства шифра. Так, если ключ шифрования имеет размер 56 бит, то возможно использование 2⁵⁶ ключей, что, как уже отмечалось, не составляет в настоящее время вычислительных трудностей криптоаналитику, особенно если учесть, что задача полного перебора ключей легко поддается распараллеливанию. Так, при проведении фирмой RSA Data Security inc. в сети Internet конкурса по взлому шифра RC5 количество компьютеров, одновременно участвующих в атаке, достигло 4500 единиц, а пиковая производительность – 440 млн. ключей в секунду[11]. По оценкам ведущих специалистов в области криптографии длина ключа шифрования, гарантирующая криптостойкость к силовой атаке, должна составлять от 75 до 90 бит.

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

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

c_i = m_i  k_i.

Дешифрование происходит аналогичным образом:

m_i = c_i  k_i.

Учитывая свойства операции сложения по модулю 2, можно отметить, что выполняется:

k_i = c_i  m_i,

поэтому криптостойкость поточных шифров полностью зависит от качества генератора потока ключей. Очевидно, что если поток ключей будет включать в себя только двоичные нули, то шифротекст будет представлять собой точную копию открытого текста. Поток ключей поточных шифров принято обозначать греческой буквой  (гамма), вследствие чего подобные шифры получили название шифров гаммирования. Большинство современных генераторов гаммы построено на линейных регистрах сдвига (ЛРС). Он представляет собой (рис.2.9) последовательность бит, которая на каждом такте шифрования сдвигается вправо на 1 разряд, при этом выход из крайнего правого бита является выходом генератора, а на вход крайнего левого бита подается значение, вычисляемое как сумма по модулю 2 нескольких разрядов ЛРС. Ключ шифрования поточного шифра заносится в ЛРС перед началом генерации гаммы.

Рассмотрим работу ЛРС на примере трехразрядного регистра, структура которого приведена на рис.2.10

Занесем в регистр начальное значение 010 и посмотрим, какие значение получим на выходе гаммы.

Таблица 2.2

Результат работы генератора гаммы на основе ЛРС

Номер такта	Значения битов ЛРС			Бит гаммы
	1	2	3
нач.сост	0	1	0	-
1	0	0	1	0
2	1	0	0	1
3	1	1	0	0
4	1	1	1	0
5	0	1	1	1
6	1	0	1	1
7	0	1	0	1
8	0	0	1	0

Из таблицы видно, что состояние ЛРС повторяется через 7 тактов (начальное состояние ЛРС совпадает с его состоянием на 7-м такте). Повтор состояния ЛРС означает, что и гамма будет периодически повторяться. Повторение гаммы снижает криптостойкость поточных шифров, позволяя криптоаналитику проводить анализ шифротекстов, полученных кодированием на одной и той же гамме. Поэтому при проектировании структуры ЛРС встает проблема достижения максимального периода повтора ЛРС. Для ЛРС длиной n бит максимальный период составляет 2ⁿ-1 тактов (состояние, когда все биты равны нулю, недопустимо, поскольку ЛРС любой структуры не выходит из этого состояния, зацикливаясь в нем). Построение ЛРС оптимальной структуры с точки зрения периода повторения гаммы имеет четкую математическую основу в виде теории неприводимых полиномов. Структура ЛРС описывается многочленом вида:

b₁*xⁿ+b₂*x^n-1+b₃*x^n-2+…+b_n-1*x²+ b_n*x+1,

где b_i=0, если i-й бит слева не участвует в обратной связи, и b_i=1, если участвует. ЛРС будет иметь максимально возможный период повторения гаммы, если описывающий его многочлен не раскладывается на произведение многочленов меньшей степени.

Основной проблемой ЛРС является их нестойкость к атаке на основе известного открытого текста. Даже если неизвестна внутренняя структура ЛРС, криптоаналитик с помощью алгоритма Берлекэмпа-Мэсси по известным 2N битам открытого текста и соответствующего шифротекста имеет возможность построить ЛРС, порождающую подобную последовательность. Поэтому современные поточные шифры строятся на основе нелинейных регистров сдвига (НРС). Нелинейные регистры сдвига строятся на основе линейных с добавлением в структуру нелинейных элементов: логического сложения и логического умножения. Наиболее популярными классами нелинейных регистров сдвига на сегодня являются фильтрующие, комбинирующие и динамические поточные шифры [6].

Фильтрующие НРС строятся с использованием дополнительной комбинационной схемы – фильтра – на выходах некоторых бит ЛРС (рис.2.11). Выход комбинационной схемы и является гаммой.

К омбинирующие НРС также используют комбинационную схему с нелинейными преобразованиями бит, но на вход этой комбинационной схемы подаются выходы нескольких ЛРС (рис.2.12).

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

Динамические НРС также строятся на основе нескольких ЛРС, но здесь они вступают друг с другом в отношения «главный-подчиненный» (рис.2.13). В зависимости от выхода управляющего ЛРС на общий выход НРС подается либо выход первого, либо второго ЛРС.

В качестве примера поточного шифра, построенного на основе регистров сдвига, можно привести алгоритм A5, используемый для кодирования в стандарте GSM. A5 включает 3 ЛРС длиной 19, 22 и 23 бита на выход гаммы подается сумма по модулю 2 выходов всех регистров. Используется схема динамического НРС, когда каждый регистр тактируется в зависимости от состояния средних разрядов всех трех регистров сдвига.

Поточными являются также шифры RC4, SEAL, WAKE [12].

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

Симметричное шифрование имеет недостатки, которые ограничивают возможности его применения в ряде конкретных случаев. В частности, зачастую невозможно организовать секретный канал для обмена ключами шифрования между участниками взаимодействия. Еще одним недостатком симметричных шифров является необходимость хранения большого количества ключей: для того чтобы в вычислительной сети могли конфиденциально попарно взаимодействовать N участников, необходимо наличие в системе N*(N-1)/2 ключей. Эти недостатки можно устранить, используя алгоритмы асимметричного шифрования. Например, для асимметричной системы достаточно иметь 2*N пар открытый/закрытый ключ, чтобы можно было организовать секретный канал между каждой парой участников.

2.5.1. Математические основы асимметричного шифрования

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

Для любого положительного целого числа n и любого a при делении a на n мы получаем некоторое целое частное q и остаток r, удовлетворяющий соотношению

a = qn + r,     0 ≤ r < n; q = int(a / n),

где int(x) обозначает наибольшее целое число, не превышающее x.   Если a является целым, а n - положительным, то a mod n определяется как остаток от деления a на n. Таким образом, для любого целого числа a можно записать

a = int(a / n) * n + (a mod n).

Говорят, что два целых числа a и b являются сравнимыми по модулю n, если (a mod n) = (b mod n). Это записывается в виде: a  b mod n.

   Операции сравнения по модулю имеют следующие свойства:

a  b mod n, n | (a - b) (n | x означает, что n делит x нацело). Из (a mod n) = (b mod n) следует a  b mod n. Из  a  b mod n следует b  a mod n. Из a  b mod n  и b  c mod n следует a  c mod n.

   Операции арифметики в классах вычетов обладают следующими свойствами:

[(a mod n) + (b mod n)] mod n = (a + b) mod n. [(a mod n) - (b mod n)] mod n = (a - b) mod n. [(a mod n) * (b mod n)] mod n = (a * b) mod n.

   Пусть Z_n обозначает множество всех не отрицательных целых чисел, которые меньше n:

Zn = {0, 1, 2, ... , (n - 1)}.

   Это множество называется ещё множеством вычетов (остатков) по модулю n. Для арифметических операций по модулю n в этом множестве выполняются следующие свойства:

Свойство	Выражение
Коммутативные законы	(w + x) mod n = (x + w) mod n, (w * x) mod n = (x * w) mod n
Ассоциативные законы	[(w + x) + y] mod n = [w + (x + y)] mod n, [(w * x) * y] mod n = [w * (x * y)] mod n
Дистрибутивный закон	[(w + x) * y] mod n = [(w * y) + (x * y)] mod n
Тождества	(0 + w) mod n = w mod n, (1 * w) mod n = w mod n
Аддитивный обратный (-w)	Для любого w є Zn существует такое z, что w + z ≡ 0 mod n

    Существует одна особенность арифметики в классах вычетов, которая делает её отличной от обычной арифметики.  Заметим сначала, что, как и в обычной арифметике, имеет место следующее свойство

если (a + b)  (a + c) mod n, то b  c mod n.

   Данное свойство согласуется с существованием аддитивного обратного. Прибавив к обеим частям данного равенства аддитивное обратное элемента а, получим:

((-a) + a + b)  ((-a) + a + c) mod n, b  c mod n.

   Однако следующее утверждение:

если (a * b)  (a * c) mod n, то b  c mod n

выполняется только при условии, что a и n взаимно просты (обозначается далее (a,n)=1)

   Если p является простым, то все элементы Z_p будут взаимно простыми с p. Это даёт нам возможность добавить ещё одно свойство к тем, которые были приведены выше:

Свойство	Выражение
Мультипликативный обратный (w-1)	Для любого w є Zp существует z, что w * z ≡ 1 mod p

Для поиска мультипликативного обратного можно использовать расширенный алгоритм Евклида, который позволяет в целых числах найти решение уравнения ax+by=1 при заданных а и b. Очевидно, что если решение существует, то x будет величиной, мультипликативно обратной а по модулю b.

Алгоритм Евклида 1. Определить матрицу E:

2. Вычислить r –остаток от деления числа a на b:

a = bq + r, 0  r < b

3. Если r=0, то первый столбец матрицы E является решением уравнения.

4.Если r 0, заменить матрицу Е:

5.Поменять местами столбцы матрицы Е.

6. Заменить пару чисел a, b на b, r и перейти к шагу 2.

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

Исторически первой системой с открытым ключом стал метод экспоненциального ключевого обмена Диффи - Хеллмана, разработанный в 1976 году. Метод предназначен для передачи секретного ключа симметричного шифрования. В обмене задействованы два участника А и Б. Сначала они выбирают большие простые числа n и g<n (эти числа секретными не являются). Затем участник A выбирает большое целое число х, вычисляет Х=g^x mod n и передает Х участнику Б. Б в свою очередь выбирает большое целое число y, вычисляет Y=g^y mod n и передает Y участнику А. Б вычисляет K^’=X^y mod n, А вычисляет K^’’=Y^x mod n. Легко заметить, что

K^’=K^’’=g^xy mod n, и это значение оба участника могут использовать в качестве ключа симметричного шифрования. Криптостойкость этого метода определяется трудоемкостью вычисления дискретного логарифма в конечном поле. Действительно, злоумышленник может узнать такие параметры алгоритма, как n, g, X, Y, но вычислить по ним значения x или y – задача, требующая очень больших вычислительных мощностей и времени. Метод легко можно обобщить на случай ключевого обмена большего количества участников. Использование метода Диффи - Хеллмана на практике должно сопровождаться сертификацией «открытых» ключей X и Y. Иначе злоумышленник может провести атаку, которая известна под названием «человек посередине» (man-in-the-middle), когда передаваемые участниками А и Б сообщения перехватываются злоумышленником и подменяются сообщениями X^’ и Y^’, вычисленными на основе его закрытого ключа. В итоге будут установлены два соединения «А - зломышленник» и «Б - злоумышленник», причем А и Б будут уверены, что обмениваются сообщениями друг с другом. Необходимо также отметить, что алгоритм Диффи - Хеллмана не является асимметричным алгоритмом шифрования, шифрование при его использовании необходимо выполнять с использованием симметричного шифра. Примером действительно асимметричного алгоритма шифрования, основанного на проблеме дискретного логарифма, является алгоритм Эль-Гемаля, разработанный в 1985 г. Последовательность действий при генерации ключей, шифровании и дешифрации представлена на рис. 2.14.

Н еобходимо пояснить процедуру дешифрования. Так как a^xg^kx mod p, то имеем:

Таким образом, кодируемое сообщение М разбивается на части, каждая из которых m интерпретируется как число в диапазоне [0 .. p-1], и выполняется операция шифрования согласно схеме на рис.2.14. На практике при использовании данного алгоритма рекомендуется выбирать ключи размером 768, 1024 и 1536 бит.

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

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

Н а этапе генерации ключей формируется пара ключей: закрытый d и открытый e. Шифрование данных должно начинаться с его разбиения на блоки m размером k=[log₂ (n)] бит каждое, чтобы блок m можно было рассматривать как целое число в диапазоне [0.. n-1]. Обратимость операции шифрования и дешифрования RSA требует доказательства. Из теоремы Эйлера известно, что для двух целых чисел n и x, таких, что (n,x)=1, выполняется:

x^(n)1 mod n, (2.2)

где (n) – функция Эйлера, значение которой равно количеству чисел меньших n и взаимно простых с ним. Для n=pq из алгоритма RSA, где p и q – простые числа, можно записать (n)=(p-1)(q-1).

Тогда (2.2) можно переписать в виде:

x^(p-1)(q-1)1 mod n (2.3)

Возведем обе части (2.3) в степень –y:

x^{(-y)(p-1)(q-1)}  1^(-y) mod n  1 mod n (2.4)

Умножим обе части (2.4) на x:

x^{(-y)(p-1)(q-1) +1} mod n = x (2.5)

Но при генерации ключей мы получили e и d такие, что ed  1 mod (p-1)(q-1), а это означает, что в (2.5) можно заменить 1-y(p-1)(q-1) на ed:

x^ed mod n = x

Тогда, если мы возведем шифротекста c=m^e mod n в степень d по модулю n, как мы это и делаем при дешифровании, то получим:

(c^d ) mod n= (m^e mod n)^d mod n = m^ed mod n = m

Очевидно, что основная задача криптоаналитика при взломе этого шифра – узнать закрытый ключ d. Для этого он должен выполнить те же действия, что и получатель при генерации ключа – решить в целых числах уравнение ed + y (p-1)(q-1) =1 относительно d и y. Однако, если получателю известны входящие в уравнение параметры p и q, то криптоаналитик знает только число n – произведение p и q. Следовательно, ему необходимо произвести факторизацию числа n, то есть разложить его на множители. Для решения задачи факторизации к настоящему времени разработано множество алгоритмов: квадратичного решета, обобщенного числового решета, метод эллиптических кривых. Но для чисел большой размерности это очень трудоемкая задача. Ее трудоемкость можно подтвердить следующими цифрами [11]: для факторизации числа 100D (число с 100 десятичными разрядами) потребовалась вычислительная мощность 7MY (1 MY – величина, равная годовой производительности компьютера, выполняющего один миллион целочисленных инструкций в секунду), для числа 130D – 500MY, для числа 140D – 2000 MY. Современная криптография к надежным ключам шифрования RSA относит ключи длиной 768, 1024, 2048 бит.

Необходимо отметить, что математически не была доказана единственность способа восстановления m по с и e разложением n на множители. Криптоаналитики не  исключают, что может быть открыт совсем иной способ криптоанализа  RSA, и тогда алгоритм станет абсолютно непригодным для практического использования.

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

Некоторые атаки используют уязвимость протокола использования алгоритма RSA [12]. Важно понимать, что само по себе использование RSA не обеспечивает требуемого уровня безопасности систе­мы. Рассмотрим некоторые возможные атаки на протокол шифрования RSA.

Если злоумышленнику удалось перехватить сообщение c, зашифрованное с помощью откры­того RSA-ключа пользователя А, то для раскрытия m = с^d он сначала выбирает первое случайное число r, меньшее n, и затем, воспользовавшись открытым клю­чом А е, вычисляет

x = r^e mod n,

y = xc mod n,

t = r^-1 mod n.

Если х = r^e mod n , то r= x^dmod n

Далее злоумышленник каким-либо способом вынуждает А закодировать сообщение y на его секретном ключе. А посылает злоумышленнику

u = y^d mod n

Теперь злоумышленник раскрывает m, вычисляя

tu mod n =r^-1y^d mod n = r^-1 x^dc^d mod n =c^d mod n = m