Криптография: защищайтесь, сударь!

Текст впервые опубликован в журнале Подводная лодка N2, 2002.

Все существующие шифры относятся к одному из трех видов — шифр замены, шифр перестановки или комбинация этих двух типов. При использовании шифра замены каждый символ незакодированного сообщения меняется на соответствующий символ шифра, при этом взаимное расположение символов остается неизменным. Может показаться, что чем вычурнее символы, применяемые для шифрования, тем сложнее расшифровать исходный текст, но это совсем не так. В естественном языке каждая буква встречается с частотой, которую легко подсчитать самостоятельно. Кроме того, существует множество запрещенных комбинаций букв (например, «оь» или «юъ» в русском языке). Поэтому достаточно длинный текст, закодированный шифром простой замены, легко вскрывается квалифицированным специалистом. Хороший пример — те самые пляшущие человечки, с которыми блестяще справился Шерлок Холмс. Другим вариантом шифра замены является шифр Цезаря, когда каждая буква заменяется на третью справа от нее по алфавиту. Обобщением такого шифра является шифр замены с повторяющимся кодовым словом. Каждая буква заменяется на букву, отстоящую от исходной на число, соответствующее очередной букве такого слова. Например, если в качестве кодового слова выбрать слово АББА, то результатом шифрования слова КОМПЬЮТЕР будет ЛРОРЭАФЖС. Кодовое слово также называется гаммой шифра, а его длина — периодом гаммы.

Большинство реально используемых систем шифрования основаны на комбинации шифра замены и шифра перестановки и не являются абсолютно стойкими, а значит, могут быть вскрыты противником за то или иное время. Возникает законный вопрос, можно ли как-то оценить это время и от чего вообще зависит стойкость шифра? Вы будете долго смеяться, но факт остается фактом — строго доказанных оценок стойкости не существует (за исключением шифра Вернама). Вообще говоря, шифр считается стойким, если его можно вскрыть только полным перебором всех возможных ключей. Но в том-то все и дело, что никто пока не может дать окончательного ответа, является ли метод полного перебора (известный также как метод грубой силы или brute force) единственным для вскрытия существующих шифров или нет. Для того чтобы немного разобраться в этой проблеме, придется еще немного углубиться в науку.

Современная криптография основана на понятии односторонней функции f(x). Не вдаваясь в формальные математические определения, отметим одно ее свойство: инвертировать функцию, т. е. вычислить x, зная только f(x), крайне сложно (на строгий язык математики слова «крайне сложно» переводятся в виде трех абзацев текста, набитых формулами, которыми не стоит утомлять читателя). Расширением этого понятия является функция с ключом, в которой к x добавляется секретный элемент K. Забавно, но существование односторонних функций до сих пор не доказано. Равно как и их отсутствие. Существует только предположение, что некоторые из известных функций могут оказаться односторонними, и именно они используются в современных схемах шифрования. Некоторую уверенность в правильном выборе этих функций дает тот факт, что их инвертирование эквивалентно сложным математическим задачам, которые изучаются уже многие годы и для которых не найдено эффективного решения (помимо полного перебора). Одна из этих задач по формулировке весьма проста — найти разложение числа на сомножители. Если в качестве примера выбрать простые числа приблизительно равной и достаточно большой величины, то современная математика не даст практически никаких рецептов решения, за исключением полного перебора. Второй задачей является дискретное логарифмирование, т. е. инвертирование функции F(x) = ax mod p, где p — простое число. Кстати, на этой формуле зиждется известная схема шифрования RSA, названная так по первым буквам фамилий ее изобретателей. Над проблемой инвертирования вышеупомянутых функций бьются лучшие математические умы человечества, но пока безрезультатно. Может, это и к лучшему — Нобелевская премия математикам все равно не светит, а ущерб для криптографии в случае успеха экспериментов окажется весьма значительным. Ведь придется где-то срочно искать новых кандидатов в односторонние функции и менять все программное обеспечение, связанное с криптографией. Это будет посильнее проблемы 2000 г.!

Криптография постепенно становится обыденным явлением. Достаточно широко распространенные системы связи «Клиент-Банк» используют шифрование для аутентификации клиента и для обеспечения безопасности банковских транзакций. Хотя при этом обычно не афишируются используемые алгоритмы и их стойкость, само намерение похвально. То же самое можно сказать и про системы управления базами данных, и про хранение паролей доступа к ресурсам локальных и глобальных сетей. Даже Microsoft Word/Excel допускает шифрование документов.

Самый стойкий шифр

Люди занимаются криптографией уже достаточно длительное время, и возникает законный вопрос, неужели не придумано еще шифра, который нельзя было бы вскрыть в принципе? Как ни странно, такой шифр существует, и его теоретическая стойкость доказана Клодом Шенноном еще в 40-х гг. XX в. Он заключается в том, что для шифрования применяется секретный случайный ключ такой же длины, как и исходное сообщение. При этом он должен использоваться только один раз. Примером такого подхода является шифр Вернама, в котором сообщение, представленное в виде потока байт, побитно складывается с секретным ключом. Для достижения абсолютной стойкости необходимо и достаточно, чтобы ключ был случайным, использовался только один раз и имел равную с сообщением длину. К сожалению, именно эти три условия делают подобные шифры малопригодными на практике. Во-первых, получить полностью случайный ключ достаточно сложно. Все известные способы генерации потока случайных чисел не лишены недостатков. Кроме того, чтобы расшифровать сообщение, адресат должен каким-то образом получить тот единственный секретный ключ, который использовался. Передать его по открытым каналам связи невозможно — очевидно, что весь смысл шифрования пропадет. Значит, для его передачи необходимо использовать особый полностью защищенный канал связи. Но если есть такой канал, то зачем тогда передавать зашифрованное сообщение, ведь его длина совпадает с длиной ключа, так что проще передать исходный текст по секретному каналу. Если же ключ является не случайным, а псевдослучайным и генерируется по какому-то сложному закону (в этом случае его передача уже не требуется), то противник рано или поздно может определить этот закон и расшифровать все секретные сообщения. Поэтому шифр Вернама на практике нашел свое применение только при передаче небольших объемов совершенно секретной информации.

Деньги на бочку!

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

Типы шифров

Все используемые в настоящее время шифры делятся на симметричные и асимметричные. В первом случае для шифрования и расшифровки требуется один и тот же секретный ключ. При этом стороны, которые обмениваются данными, должны либо заранее иметь у себя копии секретного ключа, либо (что встречается гораздо более часто) выработать его в результате обмена открытыми данными — так называемый протокол выработки общего ключа. В асимметричных шифрах применяется пара из двух ключей для каждого абонента. Один из них называется открытым. Второй — секретный — держится в тайне. Свойства шифра таковы, что сообщение, закодированное при помощи одного из ключей, может быть расшифровано только при наличии второго. Открытый ключ абонента доступен свободно в специальном хранилище, например на сервере в Интернете. Если кто-то хочет послать адресату секретное сообщение, он шифрует его открытым ключом. Получатель же раскрывает его соответствующим секретным ключом. Кроме собственно тайной передачи данных, такая схема может реализовать и электронную подпись, т. е. доказательство того, что сообщение исходит от определенного человека. В этом случае сообщение шифруется с использованием секретного ключа отправителя, а получатель расшифровывает его соответствующим открытым ключом. Комбинация этих двух приемов дает гарантию, что сообщение доставлено от конкретного отправителя заданному получателю и никто другой прочесть его не в состоянии. Поскольку алгоритмы асимметричного шифрования более медленны по сравнению с симметричными, на практике обычно используют их комбинацию. Например, для каждого сеанса обмена данными вырабатывается свой уникальный секретный сеансовый ключ, который необходим для быстрого симметричного шифрования. Для того чтобы обменяться сеансовыми ключами, прибегают к асимметричному шифрованию с применением заранее известных секретных и открытых ключей абонента. Одним из потенциально слабых мест асимметричной системы также является хранилище открытых ключей. Злоумышленник, получив доступ к открытому ключу честного абонента, может осуществить подделку. Это не очень страшно в частной переписке, но является серьезной угрозой, например, для систем банковских расчетов. Поэтому подобные хранилища должны гарантировать известную степень безопасности. Помимо этого, алгоритмы шифрования делятся на блочные и потоковые. Первые имеют дело с фиксированными порциями информации. Как правило, их длина кратна степени двойки. На практике применяются блоки от 32 до 128 бит. Потоковые алгоритмы кодируют непрерывный поток данных (например, телефонный разговор), при этом кодирование каждого бита информации осуществляется независимо от остальных битов, что позволяет допускать пропуски в потоке данных. Кодирующие устройства, реализующие потоковые алгоритмы, обычно называют скремблерами. Общий недостаток любого скремблера — наличие фиксированного периода, начиная с которого кодовое слово, дающее возможность осуществлять шифрование, начинает повторяться.