следующей итерации, а затем результаты объединяются в 128-битовое хэш-значение [793]. В дальнейшем эта идея была усилена за счет параллельного выполнения четырех итераций с поперечными связями между ними [790, 791]. Эта схема была взломана Копперсмитом [376].

В другом варианте [432, 434] операция сложения заменена XOR, и используются блоки сообщения, намного меньшие p. Кроме того, был задан H0, что превратило алгоритм в однонаправленную хэш-функцию без ключа . После того, как эта схема была вскрыта [612], она была усилена для использования в качестве части проекта European Open Shop Information-TeleTrust [1221], процитирована в CCITT X.509 [304] и принята ISO в 10118 [764, 765]. К сожалению Копперсмит взломал и эту схему [376]. В ряде исследований изучалась возможность использовать отличные от 2 основания экспоненты [603], но ни одно не оказалось перспективным.

RIPE-MAC

RIPE-MAC был изобретен Бартом Пренелом [1262] и использован в проекте RIPE [1305] (см. раздел 18.8). Он основан на ISO 9797 [763] и использует DES в качестве функции блочного шифрования. Существует два варианта RIPE-MAC: один, который использует обычный DES, называется RIPE-MAC1, а другой, использующий для еще большей безопасности тройной DES, называется RIPE-MAC3. RIPE-MAGI использует одно шифрование DES на 64-битовый блок сообщения, а RIPE-MAC3 - три.

Алгоритм состоит из трех частей . Во первых, сообщение увеличивается так, чтобы его длина была кратна 64 битам. Затем, увеличенное сообщение разбивается на 64-битовые блоки. Для хэширования этих блоков в один блок используется функция сжатия, зависящая от секретного ключа . На этом этапе используется либо DES, либо тройной DES. Наконец, выход этой функции сжатия подвергается еще одному DES-шифрованию с другим ключом, полученным из ключа, используемого при сжатии . Подробности можно найти в [1305].

IBC-хэш

IBC-хэш - это еще один MAC, используемый в проекте RIPE [1305] (см. раздел 18.8). Он интересен потому, что его безопасность доказана, вероятность успешного вскрытия может быть оценена количественно . К сожалению каждое сообщение должно хэшироваться новым ключом . Выбранный уровень безопасности ограничивает максимальный размер хэшируемого сообщения, чего не делает ни одна другая из рассмотренных в этой главе функция. С учетом этих соображений в отчете RIPE рекомендуется, чтобы IBC-хэш использовалась бы только для длинных, редко посылаемых сообщений. Ядром функции является

h, = ((M,- mod p) + v) mod 2n

Секретный ключ представляет собой пару p и v, где p - n-битовое простое число, а v - случайное число, меньшее 2n. Значения M, получаются с помощью строго определенной процедуры дополнения . Вероятности вскрыть как однонаправленность, так и устойчивость к столкновениям, могут быть оценены количественно, и пользователи, меняя параметры, могут выбрать нужный уровень безопасности .

Однонаправленная хэш-функция MAC

В качестве MAC может быть использована и однонаправленная хэш-функция [1537]. Пусть Алиса и Боб используют общий ключ K, и Алиса хочет отправить Бобу MAC сообщения M. Алиса объединяет K и M, и вычисляет однонаправленную хэш-функцию объединения: H(K,M). Это хэш-значение и является кодом MAC. Так как Боб знает K, он может воспроизвести результат Алисы, а Мэллори, которому ключ неизвестен, не сможет это сделать.

Со методами MD-усиления этот способ работает, но есть серьезные проблемы. Мэллори всегда может добавить новые блоки к концу сообщения и вычислить правильный MAC. Это вскрытие может быть предотвращено, если к началу сообщения добавить его длину, но Пренел сомневается в этой схеме [1265]. Лучше добавлять ключ к концу сообщения, H(M,K), но при этом также возникают проблемы [1265]. Если H однонаправленная функция, которая не защищена от столкновений , Мэллори может подделывать сообщения. Еще лучше H(K,M,K) или H(Kl,M,K2), где Kl и K2 различны [1537]. Пренел не уверен и в этом [1265].

Безопасными кажутся следующие конструкции :

H(Kl, H(K2, M))

H(K, H(K,M))

H(K, p,M,K)), где p дополняет K до полного блока сообщения.

Лучшим подходом является объединение с каждым блоком сообщения по крайней мере 64 битов ключа. Это делает однонаправленную функцию менее эффективной, так как уменьшаются блоки сообщения, но так она становится намного безопаснее [1265].

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

потом зашифруйте хэш-значение . Это безопаснее, чем сначала шифровать файл, а затем хэшировать зашифр о-ванный файл, но эта схема чувствительна к тому же вскрытию, что и конструкция H(M,K) [1265].

MAC с использованием потокового шифра

Эта схема MAC использует потоковые шифры (см. 3-й) [932]. Криптографически безопасный генератор псевдослучайных битов демультиплексирует поток сообщения на два подпотока . Если на выходе генератора битов ki единица, то текущий бит сообщения mi отправляется в первый подпоток, если ноль, то mi отправляется во второй подпоток. Каждый подпоток отправляется на свой LFSR (раздел 16.2). Выходом MAC просто является конечное состояние обоих регистров .

К несчастью этот метод небезопасен по отношению к небольшим изменениям в сообщении [1523]. Например, если изменить последний бит сообщения, то для создания поддельного MAC нужно будет изменить только 2 бита соответствующего MAC; это может быть выполнено с заметной вероятностью. Автор предлагает более безопасный, и более сложный, вариант.

Поток сообщения

Сдвиговый регистр 1

Сдвиговый регистр 1

Рис. 18-15. MAC с использованием потокового шифра

Глава 19 Алгоритмы с открытыми ключами

19.1 Основы

Концепция криптографии с открытыми ключами была выдвинута Уитфилдом Диффи ( Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), и независимо Ральфом Мерклом (Ralph Merkle). Их вкладом в криптографию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования -и что может быть невозможно получить один ключ из другого (см. Раздел 2.5 ). Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции ( National Computer Conference ) 1976 года [495], через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptography ("Новые направления в криптографии") [496]. (Из-за бесстрастного процесса публикации первый вклад Меркла в эту область вышел появился только в 1978 году [1064].)

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

Немногие алгоритмы являются и безопасными, и практичными . Обычно эти алгоритмы основаны на одной из трудных проблем, рассмотренных в разделе 11.2. Некоторые из этих безопасных и практичных алгоритмов подходят только для распределения ключей . Другие подходят для шифрования (и для распределения ключей) . Третьи полезны только для цифровых подписей . Только три алгоритма хорошо работают как при шифровании, так и для цифровой подписи: RSA, EIGamal и Rabin. Все эти алгоритмы медленны. Они шифруют и дешифрируют данные намного медленнее, чем симметричные алгоритмы. Обычно их скорость недостаточна для шифр о-вания больших объемов данных.

Гибридные криптосистемы (см. раздел 2.5) позволяют ускорить события: для шифрования сообщения используется симметричный алгоритм со случайным ключом, а алгоритм с открытым ключом применяется для шифрования случайного сеансового ключа.

Безопасность алгоритмов с открытыми ключами

Так как у криптоаналитика есть доступ к открытому ключу, он всегда может выбрать для шифрования любое сообщение. Это означает, что криптоаналитик при заданном C = EK(P) может попробовать угадать значение P и легко проверить свою догадку. Это является серьезной проблемой, если количество возможных открытых те к-стов настолько мало, что делает возможным исчерпывающий поиск, но эту проблему легко можно решить, д о-полняя сообщения строкой случайных битов . Это приводит к тому, что идентичным открытым текстам соотве т-ствуют различные шифротексты. (Более подробно эта идея описана в разделе 23.15.)

Это особенно важно, если алгоритм с открытым ключом используется для шифрования сеансового ключа . Ева может создать базу данных всех возможных сеансовых ключей, зашифрованных открытым ключом Боба . Конечно, это потребует много времени и памяти, но взлом грубой силой разрешенного к экспорту 40-битового ключа или 56-битового ключа DES потребует намного больше времени и памяти . Как только Ева создаст такую базу данных, она получит ключ Боба и сможет читать его почту .

Алгоритмы с открытыми ключами спроектированы так, чтобы противостоять вскрытиям с выбранным о т-крытым текстом. Их безопасность основана как на трудности получения секретного ключа по открытому, так и на трудности получить открытый текст по шифротексту. Однако большинство алгоритмов с открытым ключом особенно чувствительны к вскрытию с выбранным шифротекстом (см. раздел 1.1).

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

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

19.2 Алгоритмы рюкзака

Первым алгоритмом для обобщенного шифрования с открытым ключом стал алгоритм рюкзака, разраб о-танный Ральфом Мерклом и Мартином Хеллманом [713, 1074]. Он мог быть использован только для шифрования, хотя позднее Ади Шамир адаптировал систему для цифровой подписи [1413]. Безопасность алгоритмов рюкзака опирается на проблему рюкзака, NP-полную проблему. Хотя позже было обнаружено, что этот алгоритм небезопасен, его стоит изучить, так как он демонстрирует возможность применения NP-полной проблемы