Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
44
Часть I. Введение
функцию легко реализовать даже с помощью карманного калькулятора. Ее результатом является строка битов, состоящая из 160 бит, или 20 байт (1 байт = 8 бит). Используя шестнадцатеричную схему кодирования (см. пример 5.17), эту строку можно зашифровать в виде 40 шестнадцатеричных символов2. Алисе или Бобу будет совсем нетрудно продиктовать это число по телефону или записать на клочке бумаги. Такая реализация вполне безопасна, если Алиса и Боб спорят о том, куда идти — в театр или в кино. Если Алиса захочет "сжульничать", она должна будет решить нетривиальную задачу: найти числа х ф y(mod2), такие что f(x) = f(y). Перед Бобом также стоит непростая задача: определить по заданному значению f(x), четным или нечетным является число х.
Однако наши суждения о реализации протокола "Подбрасывание монеты по телефону" с помощью функции SHA-1 основаны на несерьезности последствий, к которым может привести рассматриваемая игра. Во многих более важных приложениях (которые мы рассмотрим в разделе 1.2.4) подобные протоколы требуют от хэш-функции больше надежности, чем может обеспечить функция SHA-1. Следует заметить, что функция, обладающая свойствами 1.1, в которых слово "невозможно" употребляется в буквальном смысле, является абсолютно надежной однонаправленной функцией. Такую функцию нелегко реализовать. Хуже того, даже ее существование до сих пор остается под вопросом (хотя мы придерживаемся оптимистичного мнения (см. раздел 1.1.2), условия существования однонаправленной функции будут рассмотрены в главе 4). Следовательно, в более серьезных приложениях, предусматривающих жеребьевку, хэш-функции нельзя считать приемлемыми — нужны более строгие криптографические средства. С другой стороны, если вы спорите о том, где провести вечер, тяжеловесные криптографические системы совершенно излишни.
Следует заметить, что существуют приложения, в которых слишком сильная защита может нарушить правильное функционирование всей системы безопасности. Например, Райвест (Rivest) и Шамир (Shamir) предложили схему для осуществления микроплатежей под названием MicroMint [242], в которой для повышения эффективности сознательно используются определенные недостатки алгоритма шифрования. Эта система платежей основана на вполне разумном предположении, что только крупная организация, обладающая большими ресурсами (например, большой банк), может эффективно подготовить большое количество "коллизий" для практических хэш-функций. Иначе говоря, только такая организация способна вычислить к разных чисел (xi,x2,.¦ ¦ ,х^), удовлетворяющих условию
/Ы = /Ы = ••• = /(**).
2Множество шестнадцатеричных символов состоит из цифр и букв {0,1,2,..., 9, А, В,..., F}, соответствующих шестнадцати четырехбитовым числам.
Глава 1. Защита информации в игре "орел или решка"
45
Набор чисел (xi,x2, -.. ,х^) называется коллизией однонаправленной функции f. Пара коллизий может быть эффективно проверена, поскольку функция / допускает эффективное вычисление. Коллизии можно рассматривать как результат работы крупного провайдера услуг и, следовательно, считать сертифицированными значениями. Алгоритм DES (Data Encryption Standard — стандарт шифрования данных, см. раздел 7.6) считается приемлемым алгоритмом реализации такой однонаправленной функции [242], порождающим относительно небольшое пространство выходов (64 бит). Итак, в отличие от обычного криптографического использования однонаправленных функций, в которых коллизия практически всегда является результатом успешной атаки на систему (например, на протокол "Подбрасывание монеты по телефону"), в системе MicroMint коллизии используются для того, чтобы обеспечить микроплатежи! Очевидно, стойкая однонаправленная функция, имеющая значительно большее пространство выходов (т.е. намного превышающее 64 бит), сводит к нулю возможности предоставления таких услуг даже для крупных организаций. К числу таких функций относится функция SHA-1, пространство выходов которой состоит из 160 бит. (В разделе 3.6 мы изучим аспекты, связанные с вычислительной сложностью поиска коллизий хэш-функций.)
Вполне понятно, что применение громоздких криптографических технологий при разработке систем защиты данных (например, многослойное шифрование, произвольное использование цифровых подписей, обращение за интерактивными услугами только к доверенному посреднику и даже к большому количеству таких посредников), может создать ложное впечатление полной безопасности. К тому же, иногда такие системы легче разрабатывать. Однако излишнее усердие в этом вопросе нежелательно, поскольку более сильная система защиты повышает сложность всей системы в целом. В свою очередь, более сложная система может затруднить анализ стойкости (поскольку она больше подвержена ошибкам) и реализацию системы защиты информации. Кроме того, такая система менее эффективна, а для ее внедрения и поддержки требуются дополнительные средства.
Гораздо более интересно и сложно разработать криптографическую или другую систему защиты информации, использующую лишь самые необходимые средства для достижения требуемого уровня безопасности. Это весьма важный элемент, который следует учитывать при анализе качества таких систем.
