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

Введение в криптографию

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

На рисунке 1 приведена схема преобразования данных при шифровании:

Рис.1. Схема преобразования данных при шифровании.

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

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

T = D(E(T))

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

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

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

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

 

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

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

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

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

Рис. 2. Схема работы симметричного криптоалгоритма.

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

Для целей конфиденциальности схема обмена информацией такова:

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

Рис. 3. Схема работы асимметричного криптоалгоритма для целей конфиденциальности.

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

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

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

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

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

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

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

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

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

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

Поточные криптоалгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

Сеть Фейстеля

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

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

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


Рис. 4. I-ый раунд сети Фейстеля

Функция F называется образующей. Каждый раунд состоит из вычисления функции F для одной ветви и побитового выполнения операции XOR результата F с другой ветвью. После этого ветви меняются местами. Считается, что оптимальное число раундов - от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостойкость алгоритма. Возможно, эта особенность и повлияла на столь активное распространение сети Фейстеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алгоритм. В последнее время количество раундов не фиксируется, а лишь указываются допустимые пределы.

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

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

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

Криптоанализ

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

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

  1. Цена расшифровки сообщения больше цены самого сообщения.
  2. Время, необходимое для расшифровки сообщения, больше срока жизни сообщения.