Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
728
Часть VI. Криптографические протоколы
собой неоднозначное отображение. Боб может лишь угадывать корень с вероятностью 1/2.
Эта оценка характеризует вероятность события, сформулированного в первом свойстве "волшебной" функции.
19.3 Эффективность
Анализируя протокол, мы можем измерить вычислительные затраты его участников.
Затраты Алисы
Основные затраты Алисы связаны с 1) выполнением т операций возведения в квадрат; 2) вычислением т символов Якоби и 3) проверкой числа на простоту. Для возведения в квадрат и вычисления символа Якоби необходимо выполнить OsiQogN)3) операций Для проверки простоты числа нужно выполнить OsiOogN)2) операций. Итак, если т — log А7, то общие затраты Алисы равны C(logAr)3, где С — небольшая константа. В эту оценку входят затраты на создание и верификацию цифровых подписей. Проще говоря, полные вычислительные затраты Алисы сравнимы с затратами на выполнение нескольких шифровок по схеме RSA.
С точки зрения пропускной способности канала Алиса посылает 2(logAr)26HT (при условии, что т = log N).
Затраты Боба
Легко видеть, что вычислительные затраты Боба равны затратам Алисы плюс затраты на генерацию модулей RSA. Иначе говоря, вычислительные затраты Боба равны сумме затрат на создание ключа RSA и многократное шифрование по схеме RSA. Чтобы сформулировать этот результат точнее, заменим константу С в выражении для оценки затрат Алисы величиной log А7: (^((logA7)4).
Затраты Боба на связь намного меньше, чем у Алисы, поскольку он должен пересылать только модули, т случайных битов и множитель модулей, т.е. 3 log N бит.
Очевидно, что эти затраты вполне разумны.
19.4 Резюме
В главе получены количественные оценки эффективности и стойкости протокола Блюма "Подбрасывание монеты по телефону".
• Сильная измеримая стойкость
• Анализ стойкости, проведенный в разделе 19.2, показывает, что реализация однонаправленной функции в протоколе подбрасывания монеты является
Глава 19. Еще раз о "подбрасывании монеты по телефону"
729
очень строгой и допускает количественную оценку: одно из свойств "волшебной" функции связано с решением трудноразрешимой задачи (факторизации целого числа), а второе носит безусловный характер.
• Практическая эффективность
• Анализ эффективности, проведенный в разделе 19.3, показывает, что протокол позволяет участникам согласовать строку, состоящую из т случайных бит, затратив на это количество операций, сравнимое с обычным шифрованием в криптосистеме с открытым ключом, имеющим длину т. Легко видеть, что эта оценка вполне приемлема для практических приложений.
• Использование практичных конструкций
• Протокол может использовать обычные схемы цифровой подписи, предусматривающее возведение в квадрат, вычисление символа Якоби большого числа и проверку простоты числа по методу Монте-Карло. Эти алгоритмы и операции являются стандартными и доступны в большинстве библиотек криптографических алгоритмов.
Таким образом, протокол Блюма полностью соответствует всем требованиям, предъявляемым к криптографическим алгоритмам, протоколам и системам, перечисленным в главе 1.
Глава 20
Послесловие
В середине 1970-х годов криптография вступила в новую эру. Ее начало ознаменовало два события: опубликование стандарта шифрования данных (US Data Encryption Standard) и изобретение криптографии с открытым ключом. Теоретическое и практическое значение криптографии стимулировало рост академических исследований и активизацию коммерческих приложений. В настоящее время криптография представляет собой обширное поле деятельности, в котором постоянно рождаются новые идеи и методы.
В книге рассмотрена относительно небольшая, но важная часть современной криптографии. Избранные темы включают в себя методы, схемы, протоколы и системы, либо ставшие строительными конструкциями современных систем защиты информации (например, криптографические примитивы, описанные в главах 7-10 и основные конструкции протоколов аутентификации, изложенные в главе 11), либо получившие широкое распространение (например, реальные системы аутентификации, описанные в главе 12, и прикладные схемы шифрования и цифровой подписи, которым посвящены главы 15-16), либо имеющие большое значение для будущих приложений в области электронной коммерции и услуг (например, схемы идентификации сущностей из главы 13 и протоколы с нулевым разглашением из главы 18).
Книга содержит систематическое и глубокое изложение избранных методов, имеющих не только прикладное, но и теоретическое значение. Особое внимание в книге уделено следующим темам.
• Преодоление слабости "учебных" криптографических схем и протоколов.
• Усиление понятия стойкости для применения не только в теории, но и на практике.
• Описание прикладных криптографических схем и протоколов.
• Формальная методология и методы анализа стойкости.
• Иллюстрация формального доказательства сильной стойкости некоторых схем и протоколов.
Кроме того, в книге изложены теоретические основы современной криптографии, позволяющие читателям самостоятельно продолжить освоение этой обширной области знаний.
