Наука о тайнах

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

Довоенная криптография

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

Кроме того, для алгоритма шифрования с секретным ключом оказалось возможным сделать механическую реализацию, которой удобно пользоваться в полевых условиях. Даже если подобная шифромашина и попадала в руки врага, без знания ключей расшифровать сообщения было сложно. Такие машины преобразовывали открытый текст в тайный, который состоял из букв того же алфавита. В результате тайный текст, не опасаясь его разглашения, можно было передавать либо азбукой Морзе через эфир, либо другим способом передачи текстов. Одной из самых известных шифромашин была «Энигма», разработанная в Германии в 1932 году.

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

Второе поколение

После первых удач механизированного криптоанализа возникла необходимость в разработке криптоалгоритмов, стойких к взлому с помощью существующих на тот момент вычислительных ресурсов. Так началась работа над новым поколением шифров, которую инициировал Клод Шеннон, разработав теорию секретных коммуникаций. Первый стандарт на шифрование, появившийся после Второй мировой войны, был опубликован корпорацией IBM в 1969 году и носил имя Data Encryption Standard (DES). (Впрочем, строго говоря, стандартом он стал в 1977 году после утверждения его в американской федеральной системе стандартизации под номером FIPS 46-3.) Этот стандарт стал результатом компромисса нескольких заинтересованных групп в государственных ведомствах США; любопытно, что одна из этих групп опасалась публикации слишком надежной системы шифрования, которую будет сложно в случае необходимости вскрыть. Есть даже мнение, что под ее влиянием пришлось встроить лазейку для вскрытия в алгоритм шифрования, точнее, в блок перестановок — так называемый S-box.

В нашей стране первый стандарт шифрования появился в 1989 году. Его до сих пор считают достаточно надежным: дело в том, что ГОСТ 28147-89 использует ключи длиной 256 разрядов, что значительно больше, чем у 56-разрядного варианта DES. К тому же, в отличие от полностью опубликованного алгоритма DES, в ГОСТе не предусмотрено никакой «лазейки». Перестановки для российского стандарта выдавались при сертификации средства шифрования органом сертификации, ФАПСИ, а после — ФСБ. Впрочем, сейчас российский ГОСТ опубликован в качестве документов RFC 4490, 4491 и 4357, и отныне этот стандарт открыт для использования.

В 2001 году американское правительство провело конкурс по выбору нового стандарта шифрования, который решено было назвать Advanced Encryption Standard (AES). Судя по результату голосования, качество алгоритма оценивалось не столько по его стойкости, сколько по удобству и быстроте реализации. В итоге победил алгоритм Rijndael, разработанный двумя бельгийскими криптографами. Этот алгоритм перешел в собственность американского правительства и получил наименование FIPS 197. Стандарт предполагает возможность использовать его с тремя длинами ключей — 128, 192 и 256 разрядов. Для AES характерно то, что процесс шифрования и дешифрования с его помощью можно распараллелить. Развитие симметричной криптографии, как направления в науке, на этом, казалось бы, завершилось: остались лишь практические проблемы реализации алгоритмов. Тем не менее криптография начала развиваться в новых направлениях.

Новые направления

В 1976 году, в то же самое время, когда шел процесс согласования DES, американские исследователи Уитфилд Диффи и Мартин Хеллман опубликовали статью «Новые направления в криптографии», где описали систему распределения ключей для симметричного шифра. Статья стимулировала развитие нового класса несимметричных криптографических алгоритмов, или криптографии с открытыми ключами. Принципиальным отличием этого направления от традиционной симметричной криптографии было наличие двух ключей, открытого и закрытого, связанных между собой. Для шифрования используется один ключ, а для дешифрования — другой. Таким свойством обладал, в том числе, и алгоритм RSA — первый получивший широкую известность шифр с открытым ключом. Возможность публиковать открытый ключ, не опасаясь разглашения секретного, позволяет строить системы шифрования, в которых сторонам нет необходимости иметь заранее согласованные секретные ключи.

Для шифрования с открытым ключом требуется преобразование, которое легко выполнить в одну сторону, но очень сложно — в другую. И в алгоритме Диффи-Хеллмана, и в RSA в качестве такой задачи выступает возведение в степень в поле вычетов по достаточно большому модулю. Оказывается, что в таком поле задача возведения в степень решается достаточно просто, а вот логарифмирование сильно затруднено. Однако, зная определенный «секрет», процесс поиска логарифма можно сильно упростить. Эти свойства логарифмирования и используются в большинстве криптографических систем с открытым ключом.

Открытая криптография сейчас применяется очень активно. В частности, протокол SSL, который встроен в большинство браузеров для организации защищенных соединений через Internet, построен на базе криптографии с открытыми ключами. Точнее, с помощью криптографии с открытыми ключами стороны обмениваются секретными ключами, а дальше переходят на более скоростное симметричное шифрование. На тех же принципах построены системы открытых сертификатов или PKI (public key infrastructure — «инфраструктура шифрования с открытыми ключами»), которую сейчас активно пытаются применять для изготовления цифровых подписей к документам.

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

В России в 2004 году был принят стандарт на шифрование с использованием эллиптических кривых ГОСТ 34.310-2004. Это большой шаг вперед, поскольку до 2004 года у нас не было системы шифрования с открытыми ключами, но потребность в ней (точнее в электронной подписи на ее основе) была. Этот стандарт также вошел в набор спецификаций RFC, наравне с другими российскими шифрами. Однако российские стандарты отличаются тем, что они разрабатываются и принимаются закрытой группой исследователей, и повлиять на процесс разработки практически невозможно. К тому же ряд существенных параметров алгоритмов, такие как блок перестановок в ГОСТ 28147-89 и некоторые параметры эллиптических кривых в ГОСТ 34.310-2004, по-прежнему выдаются компетентными органами. В результате российские стандарты сильно привязаны к российскому государству, чего нельзя сказать об AES.

Перспективная криптография

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

Подобные системы уже разработаны, и пока они связаны со способом передачи данных — волоконно-оптическими линиями связи, поскольку в качестве ключа выступают фотоны света, передаваемые в том же канале.

Белый маг криптографии

Уитфилд Диффи — один из разработчиков классической схемы распространения ключей Диффи-Хеллмана. Сегодня он работает в Sun Microsystems и определяет стратегию развития продуктов этой компании, связанных с вопросами информационной безопасности. Обозреватель еженедельника Computerworld Россия Валерий Коржов попытался выяснить у Диффи перспективы развития криптографической науки.

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

Разработанный тридцать лет назад американский национальный стандарт шифрования DES имел слабый дизайн, однако он оказал существенное влияние на весь мир. А десять лет назад американские власти сделали неожиданный шаг, выбрав в качестве национального стандарта шифрования адаптированную версию криптографической системы Rijndael, первоначально разработанной в Бельгии. Эта система не похожа на предыдущий национальный стандарт, поскольку при ее разработке уже не было необходимости согласовывать алгоритм шифрования с какими бы то ни было организациями, заинтересованными во взломе шифра. К сожалению, этого не удалось избежать во время принятия DES. Когда он принимался в 1977 году,его создателям пришлось пойти на компромисс между требованиями правительства по защите данных и органов, которые эту защиту должны были взламывать. При разработке нового стандарта AES идти на компромисс не потребовалось. Из пятнадцати заявленных на конкурс алгоритмов на первом этапе было выбрано пять, которые были достаточно надежны. Алгоритм Rijndael победил потому, что его можно было эффективно реализовать как аппаратно, так и программно.

Алгоритмы DES и ГОСТ имеют блоки перестановок (так называемые «S-блоки»), однако определены они по-разному. В DES блоки перестановок, хотя и являются частью алгоритма, определены отдельным стандартом — FIPS46. В ГОСТ 28147-89 блоки перестановок не включены в алгоритм и фактически представляют собой ключевой материал. В американской военной терминологии — это вторичный ключ, аналогичный ротору в механической шифровальной машине. AES также использует блок перестановок, который представляет собой таблицу 8х8 бит, которая обладает свойством инверсии в определенных ограниченных полях. Впрочем, есть алгоритмы, в которых не предусмотрены блоки перестановок — это, например, Daemon и Rijmon.

Вопрос сложный. Разработка методов вскрытия этого алгоритма будет главным исследованием XXI века в области криптографии. Похоже, должна сложиться ситуация, которая возникла во время Второй мировой войны, когда были взломаны существовавшие на тот момент криптографические системы. Это было связано со значительным увеличением производительности вычислений в 50-х годах по сравнению с началом XX века, когда были разработаны первые системы шифрования для радио. Тогда возникла потребность в разработке новых криптографических систем. Американский DES, появившийся в 1977 году, был ответом на все возрастающий уровень вычислительной мощности. В 90-х годах эта же причина привела к появлению новых криптографических продуктов, хотя принципы их разработки не изменились. На текущий момент симметричная криптография, по моему мнению, является очень стабильной отраслью.

Условий несколько. Задача сложная, и она не имеет универсального метода решения. Сегодня есть несколько направлений исследования, но мне перспективным кажется только одно — квантовые вычисления. Они уменьшат сложность вскрытия шифра. Симметричный алгоритм с длиной ключа 256 разрядов при наличии квантовых вычислений будет эквивалентен 128 разрядам без них. Однако и такой длины ключа по-прежнему будет достаточно для защиты информации, так что беспокоиться не о чем. Квантовые вычисления могут разрушить существующую систему шифрования с открытыми ключами и тем самым сильно изменить мир, но симметричные шифры должны устоять. Кроме того, сейчас есть и другие национальные стандарты шифрования — в России, Японии, Китае. Все организации и компании по всему миру заинтересованы в защищенном обмене сообщениями. Это основная движущая сила в разработке и принятии международных соглашений по стандартам шифрования.

Я думаю, что сегодня это действительно одна из главных открытых тем в криптографии. Я вижу два типа проблем: в программном обеспечении и в аппаратуре. Например, есть потребность в реализации шифрования на RFID-метках и смарт-картах. В метке очень слабое питание процессора, что накладывает свои ограничения, в том числе и на работу системы шифрования. В смарт-картах очень тяжело защитить устройство чтения от перехвата внутренних сигналов. Криптография сейчас разрабатывает специальные решения для подобных случаев. В отрасли же программного обеспечения возрастает потребность в защищенных вычислениях, для которых требуются эффективные реализации криптографических алгоритмов и хорошо выверенные протоколы их использования. Например, Кеннет Паттерсон из Лондонского университета исследовал корректность исполнения протокола IPSec у различных производителей. Оказалось, что неудачная реализация этого протокола позволяет успешно проводить атаки на него, которые никак не связаны с собственно криптографией.

Шифрование голоса имеет очень старую традицию. Однако если в проектах все выглядит хорошо, то при реализации защищенного телефона возникают некоторые инженерные проблемы с тем, как сделать такой телефон простым и удобным в использовании. Часто очень защищенный телефон оказывается неудобным. Однако у разработчиков систем шифрования видеоконференций еще нет достаточного опыта. Защита видео используется в телевидении, однако там передача информации однонаправленная, поэтому проблем со скоростью шифрования обычно не бывает. Архитектурная особенность AES состоит в том, что он позволяет сделать шифрование параллельно в несколько потоков. Это упрощает разработку устройств для шифрования многогигабитных потоков. Однако, если на том же устройстве выполнять еще и компрессию видео, то предельные скорости могут упасть до нескольких мегабит, при том что не уплотненное видео требует полосы в нескольких сотен мегабайт.

Тем не менее принципиальных проблем для шифрования потоков быть не должно. Основное развитие здесь направлено на интеграцию алгоритмов шифрования в протокол SSL, который поддерживается всеми браузерами, что позволяет строить удобные в использовании публичные сервисы. Однако тогда проблемы возникают с сервером, который должен обработать много защищенных соединений. Это узловое устройство, в котором протокол шифрования стоит реализовать в аппаратуре в виде специализированных микросхем. В этом случае за счет параллельных вычислений удается увеличить количество одновременно установленных соединений до нескольких тысяч. Это главное ограничение, которое не позволяет массово использовать шифрование в Web-сервисах. Традиционно для защиты Web-сервисов используется технология VPN. Но, к примеру, на сайте Amazon.com защищенное соединение используется только при оплате, а при просмотре информации на сайте шифрования нет.

Можно разработать алгоритм, который окажется лучше для реализации в аппаратуре или программном обеспечении, работающем на универсальном процессоре. Российские стандарты шифрования и AES разрабатывались так, чтобы их можно было эффективно реализовать и в «железе», и в программном обеспечении. Например, AES хорошо распараллеливается и реализуется в аппаратуре. А для программной реализации важно, что он хорошо раскладывается на 32-разрядные слова.

Два недавних события стали неожиданностью для всего мирового сообщества. В 2003 году министерство обороны США признало AES адекватным для защиты информации любого уровня секретности и конфиденциальности. Фактически это означает, что теперь нет ограничений на применение криптографии, то есть любой человек может использовать алгоритм AES любой стойкости для защиты своих секретов. Второе — в 2005 году американское правительство расширило национальный стандарт набором новых алгоритмов. Так, в «набор A» (Suite A) входят уже используемые и принятые в качестве стандартов алгоритмы шифрования, а в «набор B» (Suite B) — хеш-функции, разработанные в США, эллиптические кривые, система согласования ключей, частично разработанная в Канаде, и система цифровой подписи на эллиптических кривых, которая может применяться в уже действующем стандарте на цифровую подпись.