id: Гость   вход   регистрация
текущее время 16:20 28/03/2024
Владелец: SATtva (создано 14/09/2006 22:50), редакция от 05/08/2007 20:00 (автор: Гость) Печать
Категории: криптография, софт, pgp, openpgp, алгоритмы, сайт проекта, статьи, стандарты
http://www.pgpru.com/Библиотека/Статьи/СравнительныйОбзорАлгоритмовPGP
создать
просмотр
редакции
ссылки

Сравнительный обзор алгоритмов PGP


Оглавление документа:


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


В процессах шифрования PGP использует три основных типа алгоритмов: алгоритмы криптосистем с открытым ключом (RSA, DSA, Эльгамаль), алгоритмы односторонних хэш-функций (SHA1, MD5) и итеративные блочные шифры (AES, CAST, 3DES, IDEA, Blowfish, Twofish). Эти типы имеют серьёзные сущностные различия, поэтому сравниваться будут алгоритмы одних типов, поскольку иное некорректно; кроме того, дополнительные алгоритмы, входящие в модифицированные версии PGP, описываться не будут. Я не стану сильно вдаваться в то, как действует криптография: об этом можете почитать во "Введении в криптографию" и, более подробно, в разделе литературы.


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

Блочные шифры


Итак, начнём с последнего. Суть симметричного шифрования состоит в применении сложных математических преобразованних над информацией на входе алгоритма для её смешения и рассеивания и получения абсолютно нечитаемой абракадабры (шифртекста) на выходе, но таким образом, чтобы операция была обратимой. Алгоритм приводится в действие ключом, идентичным как для операции зашифрования, так и для расшифрования. Обычно, чем больше ключ (т.е. составляющее его число бит), тем сложнее его взломать простым перебором, или "в лоб", проверяя все возможные значения в попытке угадать ваше. Каждый дополнительный бит в длине ключа увеличивает время подбора примерно в два раза – затраты времени/ресурсов происходят экспоненциально.


Блочный шифр (симметричный алгоритм) используется в PGP для зашифрования открытого текста случайным сеансовым ключом.

Triple-DES


Он же 3DES, или тройной DES. Базовый алгоритм DES был разработан IBM в середине 1970-х и несколько лет спустя принят в качестве государственного стандарта шифрования США (и весьма распространился по миру). 3DES – это его вариация, в которой базовый DES выполняется трижды на одном блоке данных. В PGP он реализован в режиме EDE (зашифрование-расшифрование-зашифрование) с тремя независимыми подключами. Длина общего ключа – 168 бит, оперирует на 64-битовых блоках данных. Расчётная стойкость такого алгоритма к лобовой атаке составляет 112 бит, что, вкупе с его высокой скоростью и проверенной годами надёжностью, весьма неплохо.


В то же время, некоторые скептически относятся к DES и его вариациям. Во-первых, алгоритм был разработан довольно давно. На то время это был один из немногих доступных алгоритмов стойкого шифрования (20 лет назад 56-битовый ключ базового DES был стоек). Во-вторых его популяризации способствовало принятие алгоритма ISO (Международной организацией стандартизации) в качестве международного стандарта и удачная архитектура, позволявшая легко реализовывать алгоритм в шифровальных микросхемах электронного оборудования. Этот фактор сфокусировал на DES огромное внимание и попытки криптоанализа со стороны научного сообщества и спецслужб всего мира. В итоге DES поддался. Вернее, он просто устарел, и сегодня может быть легко взломан полным перебором ("в лоб") за несколько десятков минут на суперкомпьютере или распределённой системе; криптоаналитический взлом сегодня, как и прежде, – более сложная задача, в этом смысле DES выдержал испытание временем. В-третьих, в разработке алгоритма участвовало АНБ США, ведомство, аналогичное нашему теперь уже бывшему ФАПСИ. В частности, АНБ разработало узлы замены (S-блоки) алгоритма. Несмотря на то, что они долгое время анализировались, никто не может гарантировать, что в их разработке АНБ не использовало иных засекреченных методик, кроме усиления стойкости шифртекста к дифференциальному криптоанализу. Но вы помните, что в PGP используется более стойкий вариант – тройной DES. Он сохранил все достоинства DES, попутно увеличив стойкость ключа в два раза (а также унаследовав классы слабых и полуслабых ключей, которые, однако, в реализации PGP отсеиваются). Криптоанализу он не подвержен, как и базовый DES (тот поддавался только в ослабленных вариантах с меньшим числом раундов). Единственным вопросом остаются разработанные в АНБ S-блоки, но, в то же время, неизвестно, может ли АНБ вскрыть тройной DES, если при разработке такой не предполагался. На эти вопросы никто вам ответа не даст, исходите исключительно из своего уровня паранойи.

AES


"Улучшенный стандарт шифрования" (Advanced Encryption Standard), принятый Национальным институтом стандартов и технологий (NIST) США в 1999 году в качестве стандарта шифрования важных несекретных коммуникаций. Пришёл на смену устаревшему DES. Авторское название – Rijndael ("рэйн долл"), блочный шифр со 128-, 192- или 256-битовым размером ключа и 128-битовым блоком.


За три года проведения конкурса на звание нового стандарта шифрования каждый из пяти финалистов (Twofish, Serpent, Rijndael, RC6 и MARS) подвергся столь же тщательному исследованию государственного и гражданского криптологического сообщества, и не только США, но и всего мира, сколь и DES за 20 лет своей жизни. Rijndael был избран благодаря простому дизайну, облегчающему его анализ, малому размеру исполняемого кода и требованиям к памяти, высокой скорости и некоторым другим параметрам, отличающим его от конкурентов, даже несмотря на незначительно меньший "запас прочности" (т.е. способность противостоять атакам в своих ослабленных вариантах с меньшим числом раундов), тем не менее, не несущий практической угрозы безопасности алгоритма. Хотя простой дизайн был в целом оценен положительно, из-за этой простоты взломщику потребуется изучить более ограниченный математический аппарат, и если где-то в Rijndael есть скрытые недостатки, то рано или поздно их кто-нибудь обнаружит.


Подводя итог, можно сказать, что хотя Rijndael обладает меньшим запасом прочности, чем другие финалисты на звание AES, это не несёт в себе никакого практического риска. Если сравнивать различных финалистов с сейфами из закалённой стали, то на изготовление Rijndael потрачено меньше стали, чем на его конкурентов, но этого количества оказалось достаточно, чтобы надежно запереть секрет.

CAST


Разработанный в 1993 году шифр со 128-битовым ключом и 64-битовым блоком. Дизайн основан на формальной архитектуре DES с доказанной стойкостью. Не имеет слабых и полуслабых ключей. Совершенно устойчив к линейному и дифференциальному криптоанализу, может быть взломан только "в лоб".


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

IDEA


Опубликованный в 1990, именно он лёг в основу первых версий PGP. Имеет ключи длиной 128 бит и оперирует на 64-битовых блоках открытого и шифртекста. Построен на концепции смешения операций различных алгебраических групп, а именно: XOR, сложение по модулю 216 и умножение по модулю 216+1. В ослабленных вариантах может быть подвержен криптоанализу, но в базовом, который реализован в PGP, – нет.


Наряду с AES, является алгоритмом, не представляющим собой сеть Файстеля (DES-подбную архитектуру). Считается одним из лучших опубликованных шифров, отчасти благодаря своей прочной теоретической базе. Имеет класс слабых ключей, однако такие в PGP не используются. Единственное предостережение состоит в том, что ряд групп академических и военных исследователей не опубликовали свои результаты криптоанализа шифра. Возможно, кто-нибудь уже добился успеха в его взломе.

Twofish


Один из пяти финалистов на звание AES. Группу разработчиков возглавлял Брюс Шнайер. В реализации PGP использует 256-битовый ключ и 128-битовый блок данных.


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


Изучение вариантов Twofish с сокращенным числом раундов показало, что он обладает высоким запасом прочности. Однако, как и в случае с некоторыми другими финалистами, его необычная структура породила определенные сомнения в качестве этой прочности. Некоторые аналитики отмечали, что из-за сложности Twofish проанализировать его детально в отведенные для этого сроки оказалось очень сложно.


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

Blowfish


Blowfish, автором которого также является Брюс Шнайер, представляет собой блочный алгоритм с ключом переменной длины (влоть до 448 бит), оперирующий на 64-битовых блоках. Это самый быстрый из трёх симметричных алгоритмов, включённых в PGPfone, где он используется в 128-битовом режиме.


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


Таблица 1. Сравнение основных параметров итеративных блочных шифров в реализации PGP.

АлгоритмКлючБлокПримечания
Triple-DES168 бит64 битСеть Файстеля; имеет пространство слабых и полуслабых ключей; быстр; устойчив к криптоанализу; сравнительно низкая стойкость ключа к лобовой атаке (112 бит); проверенная 20 годами надёжность; в разработке участвовало АНБ.
AES (Rijndael)256 бит128 битУникальный, но простой дизайн (операции с таблицами массивов данных), облегчающий анализ на наличие брешей; принят в качестве гос. стандарта США после открытого конкурса; в сравнении с высокой стойкостью очень быстр; относительно нов.
CAST128 бит64 битСеть Файстеля (DES-подобный дизайн); не имеет слабых ключей; быстр; устойчив к криптоанализу; существует уже 10 лет.
IDEA128 бит64 битОснован на уникальной концепции (смешение операций разных алгебраических групп); имеет пространство слабых ключей; послужной список в 13 лет; не все работы по криптоанализу были опубликованы.
Twofish256 бит128 битСеть Файстеля; один из финалистов конкурса AES; быстрое шифрование, медленная установка ключа; сложный дизайн, затрудняющий формальный анализ; имеет большой запас прочности.
Blowfishmax 448 бит64 битСеть Файстеля; простой дизайн; быстрое шифрование, медленная установка ключа; имеет небольшое пространство слабых ключей; имеет высокий запас прочности.

Хэш-функции


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


Хэш-функции используются в PGP для генерирования цифровых подписей и и для защиты симметричных и закрытыйх асимметричных ключей шифрования.

MD5


Этот алгоритм, разработанный Рональдом Ривестом из RSA Data Security, для каждого входного сообщения возвращает 128-битовое хэш-значение. По сегодняшним меркам этого становится недостаточно, и в PGP эта хэш-функция используется только для совместимости со старыми версиями программы, где ей не было альтернатив.


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

SHA-1


В целом, принципы алгоритма SHA1, разработанного АНБ и NIST США, схожи с MD4 (предшественника MD5), но эта хэш-функция гораздо более стойка, возвращая 160-битовое хэш-значение для любого сообщения-прообраза. В PGP 5.0 и выше используется именно она.


Факт, что источником SHA1 является АНБ, не должен располагать ни к чему предосудительному: алгоритм был опубликован и тщательно проанализирован. Более того, нельзя сравнивать алгоритмы шифрования и хэш-функции из-за явных различий стоящих перед ними задач; АНБ не заинтересовано в подделываемых хэш-значениях, поскольку это полностью дискредитирует в целом всю национальную криптосистему США с открытым ключом.


Таблица 2. Сравнение основных параметров односторонних хэш-функций в реализации PGP.

АлгоритмСвёрткаПримечания
MD5128 битБыстра; большая часть документации по разработке была опубликована; относительно короткая свёртка; проведён ряд успешных криптоаналитических атак, серьёзно ослабивших алгоритм.
SHA-1160 битМедлительна; принята в качестве гос. стандарта США; большая часть документации по разработке закрыта; разработчиком является АНБ; факты успешных криптоатак неизвестны.

Асимметричные алгоритмы


Центром PGP, ради которого и создавалась программа, являются криптосистемы с открытым ключом. Назначение их в том же, что и у блочных шифров – сделать информацию непонятной всякому постороннему. Основное отличие состоит в использовании для операций зашифрования / расшифрования двух разных, но взаимосвязных ключей однонаправленного действия, каждый из которых может зашифровать информацию, но расшифровать её может только другой. Благодаря этой особенности некоторые алгоритмы с открытым ключом совместно с хэш-функцией могут применяться и для другой цели: для выработки имитовставки (электронной цифровой подписи), подтверждающей авторство информации. Асимметричные алгоритмы основаны на ряде математических проблем (т.н. NP-полных задач), на которых и базируется их стойкость. Пока учёные-математики не найдут решение этих проблем, данные алгоритмы будут стойки. В этом заключается ещё одно отличие симметричного и асимметричного шифрования: стойкость первого является непосредственной и научно доказуемой, стойкость второго – феноменальной, т.е. основанной на некоем явлении, и научно не доказана (так же, как не доказана их нестойкость).


В PGP асимметричные алгоритмы применяются а) для генерации ЭЦП и б) для зашифрования симметричных сеансовых ключей.

RSA


RSA – криптографическая система с открытым ключом, обеспечивающая оба механизма защиты: шифрование и цифровую подпись. Криптосистема RSA была разработана в 1977 году и названа в честь авторов: Рональда Ривеста, Ади Шамира и Леонарда Адельмана. В PGP алгоритм RSA также используется для шифрования и генерации ЭЦП.


Принцип её действия в следующем. Для начала сгенерируем пару ключей:


  1. Возьмём два больших случайных простых числа p и q (т.е. числа делящихся только на себя и на 1) приблизительно равной разрядности, и вычислим их произведение n=p*q.
  2. Выберем число e, взаимно простое с произведением (p–1)*(q–1). Взаимно простыми называют числа, у которых нет общих множителей кроме 1 (например, 15 и 28 – являются, 15 и 27 – нет: кроме 1 их общий множитель – 3).
  3. Вычисляется число d=e-1mod((p–1)*(q–1)), взаимно простое с n.

Числа e и n становятся открытым ключом. Число d – закрытым. Теперь предположим, что Анне нужно отправить Борису сообщение m. Чтобы создать шифртекст c, она возводит m в степень e и умножает всё на модуль n, где e и n – показатели открытого ключа Бориса:


c = me mod n

Чтобы расшифровать полученный шифртекст, Борис возводит c в степень d и умножает на модуль n, где d – показатель закрытого ключа, который Борис хранит в секрете:


m = cd mod n

Подписание в целом аналогично, но вместо зашифрования сообщения открытым ключом Бориса, Анна зашифровывает его собственным закрытым ключом. Расшифрование шифртекста открытым ключом Анны докажет, что отправителем является именно она.


До тех пор, пока не найдены эффективные методы разложения чисел на множители, невозможно факторизовав n получить p и q, а, следовательно, и показатель закрытого ключа d. Таким образом, надежность криптосистемы RSA базируется на трудноразрешимой задаче разложения n на множители. В то же время, надёжность RSA, как и иных асимметричных криптосистем, можно выразить как T(RSA)<=T(факторизации), где T(RSA) – трудозатраты на вычисление закрытого ключа, а T(факторизации) – трудозатраты на факторизацию показателя n, поскольку не исключено, что может быть найден альтернативный метод взлома ключа, тогда как задача разложения на множители по-прежнему останется невыполнимой. Также стоит отметить, что, несмотря на фактическую сложность разложения больших чисел на множители, научно не доказано, что факторизация является трудной, или NP-полной, задачей. Но и доказательств обратного тоже никто не представил.

Эльгамаль


Схема Эльгамаля реализована в PGP исключительно для целей шифрования (хотя потенциально может применяться для создания цифровых подписей). В терминологии PGP она называется Diffie-Hellman (алгоритм Диффи-Хеллмана), что было необходимо вследствие определённых юридических нюансов. Cхема Эльгамаля основана на трудной задаче вычисления дискретных логарифмов в конечном поле в сравнении с лёгкостью возведения в степень в том же самом поле.


Для генерации пары ключей сначала выбирается простое число p и два случайных числа, g и x; оба эти числа должны быть меньше p. Затем вычисляется:


y = gx mod p

Открытым ключом становятся y, g и p. И g, и p можно сделать общими для группы пользователей (именно это и делает опция Faster key generation в настройках PGP). Закрытым ключом является x. Теперь, чтобы зашифровать сообщение m, сначала выбирается случайное k, взаимно простое с p–1. Затем вычисляются:


a = gk mod p
b = yk m * mod p

Пара a и b является шифртекстом, что увеличивает исходное сообщение в два раза. Для расшифрования вычисляется:


m = b/ax mod p

DSA


В августе 1991 года Digital Signature Algorithm в паре с хэш-функцией SHA1 был избран NIST США для использования в рамках Стандарта цифровой подписи DSS. В PGP он используется для генерации ЭЦП.


Описания алгоритма и генерации простых чисел включают довольно много скучных формул, но в общем DSA представляет собой вариант алгоритма подписи по схеме Эльгамаля (не рассматривавшегося здесь). Более интересным читателю в рамках данной работы может быть ряд заявлений и претензий научного сообщества и коммерческих организаций, опубликованных сразу после первоначального появления упоминаний о DSA в Федеральном Регистре. Всего к концу первого периода обсуждений (28 февраля 1992 года) NIST получил 109 замечаний. Вот пара наиболее важных:


  • Размер ключа слишком мал.

Это действительно так. При использовании ключей DH/DSS в PGP вы могли видеть, что часть, соответствующая DSS всегда составляет 1024 бит, независимо от того, сколь крупный ключ используется для шифрования по схеме Эльгамаля. Первоначально же предполагалось использовать модуль длиной всего 512 бит. Но на справедливые замечания, что "даже безопасность, обеспечиваемая 512-битовыми простыми числами, по-видимому, находится на пределе", NIST сделал длину ключа переменной, в пределах 1024 бит.


  • Алгоритм разработан АНБ, и в нём могут быть предусмотрены лазейки.

В своём первом заявлении АНБ так прокомментировало утверждение по поводу "люков":


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

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


Более того, предположение о наличии лазеек справедливо для любой системы аутентификации с открытым ключом, включая RSA. Утверждение, что это касается только стандарта DSS (аргумент, популярный в прессе), полностью неверно. <...>


Наконец, мы изучили все утверждения о небезопаности DSS, и они нас не убедили. Стандарт DSS был тщательно изучен в АНБ, что позволило нашему Директору по безопасности информационных систем разрешить использовать этот стандарт для подписания несекретных данных, обрабатываемых в определённых разведывательных системах, и даже для подписания секретных данных в ряде систем. Мы считаем, что подобное признание свидетельствует о невозможности какого-либо вероятного вскрытия системы защиты, обеспечиваемой DSS при его правильной реализации и использовании. Основываясь на требованиях правительства США к технике и безопасности цифровых подписей, мы считаем, что DSS является лучшим выбором. В действительности, DSS выступает в качестве экспериментального проекта Системы оборонных сообщений (DMS), призванного гарантировать подлинность электронных сообщений для жизненно важных команд и контрольной информации. Эта первоначальная демострация включает участие Комитета начальников штабов, военных служб и оборонных ведомств и проводится в кооперации с NIST.»

Это сложно комментировать. Оценивайте самостоятельно, в зависимости от вашего отношения к подобным организациям.


Таблица 3. Сравнение основных параметров криптосистем с открытм ключом в реализации PGP.

АлгоритмКлючНазначениеПримечания
RSAДо 4096 битШифрование и подписьОснован на трудной задаче факторизации больших чисел; NP-полнота задачи не доказана и не опровергнута; один из первых асимметричных алгоритмов.
ElGamalДо 4096 битТолько шифрованиеОснован на трудной задаче вычисления дискретных логарифмов в конечном поле; в PGP используется только для шифрования; позволяет быстро генерировать ключи без снижения стойкости.
DSAДо 1024 битТолько подписаниеОснован на трудной задаче вычисления дискретных логарифмов в конечном поле; используется только для подписания; длина ключа ограничена 1024 битами; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.

* Продолжение сравнения стойкости криптосистем RSA и Эльгамаль можете прочитать в FAQ нашего сайта.

Прочие алгоритмы


Кроме непосредственно алгоритмов шифрования в PGP используются и некоторые другие, например, пороговая схема Блейкли-Шамира для разделения ключа и гамма-генератор (генератор ПСЧ) для создания случайных симметричных ключей шифрования. Первый использует простую математику, не имеющую никаких слабых мест. Второй соответствует проверенному стандарту ANSI X9.17 и работает со столь большим объёмом энтропийных данных, что у взломщика нет никакой возможности предсказать любой из предыдущих или последующих сеансовых ключей.

Парадокс "дней рождений" и стойкость PGP


Как отмечалось в описании хэш-функций, кроме корреляции между длиной свёртки и устойчивостью алгоритма к коллизиям существует один важный нюанс. Он проистекает из так называемого парадокса дней рождений, часто используемого в математической статистике. Ответьте, сколько человек должно собраться в одной комнате, чтобы с вероятностью более 1/2 хотя бы у одного из них был бы общий с вами день рождения? Ответ – 253. А сколько людей должно собраться, чтобы с той же вероятностью хотя бы у двоих из них был общий день рождения? Ответ поразителен – 23, поскольку, если в комнате находятся 23 человека, они образуют 253 различные пары.


Этот же принцип применяется для поиска коллизий хэш-функций. При использовании MD5, чтобы изготовить поддельное сообщение, производящее дайджест заданного, нужно перебрать максимум 2128 вариантов. Но чтобы изготовить два сообщения, производящих одно хэш-значение, нужно перебрать максимум 264 вариантов, что вполне реально. Добавляя слово "максимум" я подразумеваю, что исходя из теории вероятности искомый результат с 50-процентным успехом будет найден уже после проверки 263 вариантов при поиске пары с идентичным хэш-значением. Проблема всей современной криптографии – это отсутствие нижней границы стойкости; длина ключа задаёт лишь общий объём пространства ключей, но всегда есть вероятность ткнув пальцем в небо угадать решение. Вот почему настоятельно рекомендуется перейти к новым версиям PGP использующим SHA1 как основной алгоритм односторонней хэш-функции.


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


* * *

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


© 2003 SATtva

 
— Гость (25/09/2006 18:09)   <#>
Отличная статья! Все предельно понятно и грамотно рассказано! Ничего лишнего, все факты интересны и хорошо структурированы.

Ton
— Виталий_ (24/01/2007 14:39)   <#>
"совершенно устойчив к криптоанализу" – пожалуйста, уберите эту бредовую фразу из текста.
— gaws (15/05/2007 20:42)   <#>
Однозначно, в закладки.
— spinore (16/05/2007 21:24)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
не вижу статьи
— SATtva (17/05/2007 09:48)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Типографический парсер накрылся соломенной шляпой, так что при последней правке документа он выдал пустую строку. (Что интересно, код парсера не обновлялся; вероятно, какая-то несовместимость с действующей версией PHP.) Отключил это хозяйство, пока не разберусь в ситуации.
— cooshoo (02/08/2007 08:38)   <#>
Хотелось бы небольшое изменение в описание Twofish. Для выработки зависящих от ключа S-боксов действительно используется только половина ключевого материала, но каждый подключ раунда вырабатывается с использованием всех бит ключа. И насчет скорости – Twofish медленный при частой смене ключа, но при полностью выполненном ключевом расширении он быстрее AES.
— SATtva (03/08/2007 00:59)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Хотелось бы небольшое изменение в описание Twofish

/Проект/Вики
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3