Cтр. 22

О применениях математики в криптографии
Поделиться…

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

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

Основы современной теории секретной связи были разработаны Клодом Шенноном во время Второй мировой войны. Им была теоретически обоснована возможность построения совершенного шифра — такого способа шифрования, что у перехватившего преобразованное сообщение злоумышленника не будет ни одной «зацепки» для выделения исходного сообщения.

Допустим, что есть сообщение, которое надо зашифровать и передать получателю. Сначала исходное сообщение «оцифровывают», записав его в виде двоичной последовательности, состоящей из нулей и единиц. Способы преобразования сообщения (и шифрование, и расшифрование) можно подготовить заранее, если условиться, что сообщение в виде двоичной последовательности должно иметь не более $T$ знаков. Строится секретная случайная двоичная последовательность длины $T$ (например, её можно получить, подбрасывая $T$ раз идеальную монету и полагая очередной знак равным 1, если выпал «орёл», и 0, если выпала «решка»). Эту секретную последовательность («ключ») необходимо доставить отправителю и получателю так, чтобы никому, кроме них, она не была известна. Когда придёт время передачи, отправитель воспользуется ключом: «сложит по модулю 2» (т. е. по правилу $0+0=0$, $0+1=1$, $1+1=0$) каждый знак передаваемого сообщения с соответствующим знаком ключа. Полученная последовательность и будет зашифрованным сообщением. Приняв зашифрованное сообщение, получатель также воспользуется секретным ключом: прибавит (по модулю 2) к каждому знаку зашифрованного сообщения соответствующий знак ключа и восстановит исходное сообщение.

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

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

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

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

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

Литература

  • Дориченко С. А., Ященко В. В. 25 этюдов о шифрах. — М.: ТЕИС, 1994.
  • Введение в криптографию / Под. ред. Ященко В. В. — М.: МЦНМО, 2012.