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

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

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

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

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

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

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

Стойкость шифров, помимо собственно алгоритма шифрования, во многом определяется и длиной ключа. Современная криптография исходит из того, что сам алгоритм рано или поздно все равно станет известен противнику. Все сообщения, передаваемые по открытым каналам связи, могут быть перехвачены, так что ключ шифра остается его единственным секретом. Американский стандарт симметричного шифрования DES использует длину ключа 56 бит, что дает 255 вариантов ключей. В настоящее время симметричный шифр считается стойким, только если длина его ключа не менее 128 бит. Из-за экспоненциального характера роста количества ключей увеличение длины ключа всего в два раза дает невероятный рост криптостойкости шифра. Достаточно сказать, что взлом шифра со 128-битным ключом займет не менее 1020 лет. К числу таких шифров относятся BlowFish и TwoFish, автор Брюс Шнайер (Bruce Schneier), отечественный ГОСТ 28147-89, MARS корпорации IBM и финалист конкурса AES бельгийский шифр Rijndael.

Типы шифров.

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

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

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

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