Криптография с симметричным ключом

Криптография с открытым ключом: от теории к стандарту

Введение

На протяжении многих веков человечество использовало криптографические методы для защиты информации при ее передаче и хранении. Приблизительно к концу XIX в. эти методы стали объектом математического изучения. Отрасль математики, изучающая защиту информации, традиционно называется криптологией [cryptology] и подразделяется на криптографию [cryptography], занимающуюся разработкой новых методов и обоснованием их корректности, и криптоанализ [cryptanalysis], задача которого - интенсивное изучение существующих методов, часто с целью реального раскрытия секретов другой стороны. Криптография и криптоанализ находятся в тесном взаимодействии друг с другом и с практическими нуждами и развиваются параллельно закрытыми правительственными организациями многих государств и международным научным сообществом.

В настоящее время существуют тысячи криптографических систем, реализованных как программно, так и аппаратно. Среди них можно выделить системы, сам криптографический принцип работы которых держится в секрете, как, например, микросхема Clipper, предлагаемая правительством США в качестве криптографического стандарта для телекоммуникаций, и системы, алгоритм которых открыт, а секретной является только определенная, как правило небольшая, порция информации, называемая (секретным) ключом [(secret) key] - к ним относится большинство систем, реализуемых программно и предназначенных для широкого использования. В дальнейшем мы будем рассматривать только системы второго типа.

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

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

Криптография с симметричным ключом

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

К классу алгоритмов с симметричным ключом относится метод “одноразового блокнота” [one-time pad], заключающийся в побитовом сложении (“гаммировании”) шифруемого текста со случайной последовательностью битов - ключом (см. [S94]). Длина ключа должна совпадать с длиной шифруемого текста и каждый отрезок ключа должен использоваться однократно; в противном случае текст легко поддается несанкционированной расшифровке. При выполнении же этих условий данный метод является единственным методом, теоретически устойчивым против криптоанализа противника с неограниченными вычислительными ресурсами. Несмотря на это, в настоящее время метод “одноразового блокнота” практически не применяется из-за организационных сложностей, связанных с генерацией, передачей и хранением используемых в нем сверхдлинных ключей.

Другим примером схемы с симметричным ключом может служить алгоритм DES (Data Encryption Standard), принятый 23 ноября 1976 г. в качестве официального криптографического стандарта США для защиты некритичной [unclassified] информации (см. [S94], с.219-243). В стандарт было включено положение об обязательной ресертификации (пересмотре) алгоритма каждые пять лет; последняя такая ресертификация состоялась в 1992 г. По мнению экспертов, в связи с определенными успехами в криптоанализе DES и появлением новых методов шифрования с симметричным ключом, алгоритм может не быть ресертифицирован на следующий пятилетний срок. Тем не менее, DES по-прежнему считается криптографически стойким алгоритмом и остается самой распространенной схемой шифрования с симметричным ключом.

Российский стандарт на криптографию с симметричным ключом определен ГОСТ 28147-89 “Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования”, который был введен в действие 1 июля 1990 г. В отличие от DES, стандарт содержит указание на то, что он “по своим возможностям не накладывает ограничений на степень секретности защищаемой информации”. В общих чертах алгоритм ГОСТ 28147 аналогичен DES, но имеется ряд существенных отличий, как, например, длина ключа и трактовка содержимого узлов замены [в схеме DES называемых “S-boxes”]. В то время, как заполнение узлов замены DES оптимизировано с точки зрения криптографической стойкости и явно указано в стандарте, заполнение узлов замены ГОСТ 28147 “является секретным элементом и поставляется в установленном порядке”. Учитывая, что оно в то же время “является долговременным ключевым элементом, общим для сети ЭВМ”, и что “установленный порядок” поставки может не предусматривать криптографическую оптимизацию, этот пункт стандарта представляется одним из его слабых мест, затрудняющим реализацию и не способствующим криптографической стойкости. Однако при задании оптимизированных значений для узлов замены криптографическая стойкость алгоритма сравнима со стойкостью DES.