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

КРИПТОГРАФИЯ (от крипто... и ...графия),

1) наука о методах преобразования информации для её защиты при передаче по незащищённым каналам связи и о способах практической реализации этих методов.

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

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

Криптографические методы широко используются в различных системах защиты информации. Для решения задач разработки шифров и методов дешифрования в разное время привлекались многие учёные, среди которых были математики, например Ф. Виет, Х. Гольдбах, Н. Винер, А. Тьюринг. Основы современной теоретической криптографии и теории информации были заложены в годы 2-й мировой войны К. Шенноном. Он предложил рассматривать шифр как отображение прямого произведения множества Ζ всех потенциально возможных сообщений и множества К ключей в множество Е зашифрованных текстов; при любом фиксированном ключе это отображение Ζ в Е должно быть обратимым. Шеннон доказал, что шифр может быть совершенным (т. е. принципиально не дешифруемым) только в случае, когда число различных ключей не меньше числа возможных сообщений, и что если это условие выполнено, то можно построить совершенный шифр. Примером совершенного шифра является шифр гаммирования. Если исходное сообщение представлено в виде двоичной последовательности m₁, m₂,..., m_T, состоящей из нулей и единиц, то в качестве ключа нужно случайно и равновероятно выбрать двоичную последовательность γ₁, γ₂, γ_Т, из множества всех 2^Т двоичных последовательностей длины Т; тогда совершенным будет шифр, переводящий m₁, m₂, ..., m_T в m₁ + γ₁, m₂ + γ₂, ..., m_T + γ_T (все сложения проводятся по модулю 2), и получатель, зная γ₁, γ₂, ... γ_Т, может восстановить исходное сообщение, вычислив (m₁ + γ₁) + γ₁ = m₁, (m₂+γ₂)+γ₂ = m₂, ..., (m_T + γ_T) + γ_T = m_T. При этом отправитель и получатель должны заранее согласовать значение ключа γ₁, γ₂, ..., γ_Т пользуясь каналом связи, который заведомо защищён от всех посторонних (например, переслать ключ в запечатанном конверте с надёжным курьером). Если посторонний, у которого нет никакой информации о γ₁, γ₂, ..., γ_Т, попытается восстановить исходное сообщение, перебирая все возможные варианты последовательности γ₁, γ₂, ..., γ_Т, то он получит все возможные двоичные последовательности длины Т, в том числе и m₁, m₂, ..., m_T, но у него не будет оснований выделить сообщение m₁, m₂, ..., m_T из множества всех остальных комбинаций Т двоичных знаков. Неудобство указанного шифра связано с необходимостью использования защищённого канала связи для передачи ключей, суммарная длина которых не меньше суммарной длины будущих секретных сообщений. Поэтому на практике используются шифры, в которых объём ключей существенно меньше объёма передаваемых секретных сообщений. Такие шифры не могут быть совершенными; вообще говоря, зашифрованные с их помощью сообщения можно дешифровывать с помощью полного перебора всех возможных ключей. Под стойкостью шифра обычно понимают время работы наилучшего алгоритма вычисления секретного ключа по известным парам исходных и зашифрованных сообщений и известным правилам зашифрования. Однако существующие методы позволяют получать только верхние оценки стойкости шифров (а именно, оценки времени работы конкретных алгоритмов вычисления ключа).

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

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

Современные шифраторы делятся на 2 класса: поточные и блочные. Поточные шифраторы представляют собой электронные устройства с ячейками памяти и специализированными процессорами; они вырабатывают последовательности некоторых знаков и используют их вместо случайной равновероятной последовательности в шифре гаммирования. Последовательность, вырабатываемая потоковым шифратором, однозначно определяется ключевыми параметрами, задающими начальные состояния ячеек памяти конечного автомата и выбор тех или иных вариантов работы процессоров. Это позволяет отправителю и получателю, согласовавшим заранее значения ключевых параметров, вырабатывать одну и ту же последовательность γ₁, γ₂, ..., γ_Т. Блочные шифраторы разбивают исходное сообщение, представленное в виде двоичной последовательности, на блоки одинакового размера (например, по 64, 128 или более битов), вычисляют образы этих блоков при взаимно однозначном отображении, конкретный вид которого зависит от секретного ключа, и объединяют образы блоков в зашифрованное сообщение. Получатель, используя тот же секретный ключ, что и отправитель, разбивает полученное сообщение на блоки и, применяя к ним обратное отображение, восстанавливает исходное сообщение.

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

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

отображений зашифрования и расшифрования соответственно, действующие на конечном множестве К (например, на множестве ключей шифратора) и обладающие следующими свойствами:

а) для каждого е ∈ М существует такое d ∈  M что Ее и D_d - взаимно обратные отображения;

б) задача нахождения значения k из множества К по отображению Е_е и значению z = E_e(k) вычислительно неразрешима за заданное время;

в) существуют не очень сложные способы вычисления значений отображений Е_е и D_d и построения пар взаимно обратных отображений (Е_е, D_d).

Если такие семейства выбраны, то любой абонент А может выработать пару взаимно обратных отображений (Е_е, D_d), сообщить всем желающим правило вычисления отображения Е_е (открытый ключ), а правило вычисления D_d (секретный ключ) держать в секрете. Любой абонент В, чтобы передать абоненту А значение k в виде, защищённом от посторонних, может передать абоненту А по общедоступному каналу связи значение z = E_e(k). Тогда абонент А, знающий отображение D_d, сможет восстановить k по z, а посторонние, не знающие D_d и не имеющие возможности построить D_d по Е_е, не смогут этого сделать. Т. к. математически строго обоснованные примеры отображений, удовлетворяющих условию б), ещё не найдены, У. Диффи и М. Хеллман предложили использовать для построения систем шифрования с открытым ключом алгоритмические задачи, считающиеся вычислительно сложными. Ныне предложен ряд систем шифрования с открытым ключом, основанных на сложности решения задач типа разложения натуральных чисел на простые множители, вычисления квадратного корня в мультипликативной группе вычетов по составному модулю, дискретного логарифмирования [т. е. решения сравнения вида a^x = b (mod n), где n - достаточно большое натуральное число], аналогичных задач для групп эллиптических кривых над конечными полями и некоторых других.

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

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

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

Лит.: Шеннон К. Э. Работы по теории информации и кибернетике. М., 1963; Diffie W., Hellman М. Е. New directions in cryptography // IEEE Transactions on Information Theory. 1976. Vol. 22. Р. 644-654; Саломаа А. Криптография с открытым ключом. М., 1996; Menezes А. J., Oorschot Р. С. van, Vanstone Scott А. Handbook of applied cryptography. Boca Raton, 1997; Кан Д. Взломщики кодов. М., 2000; Коблиц Н. Курс теории чисел и криптографии. М., 2001; Соболева Т. А. История шифровального дела в России. М., 2002; Шнайер Б. Прикладная криптография. М., 2002; Основы криптографии. 3-е изд. М., 2005.