Решенные билеты (1085496), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Скрытый канал (subliminal channel). Создатель подписи может прятать в цифровой подписи сообщения для проверяющего, которому известен закрытый ключ х. Шифруем сообщение b (например, k=k_ib modq, где k_i выбираются из списка, известного подписывающему и проверяющему) и используем в качестве значения k.

Возможны более «узкие», т. е. несущие меньше информации, каналы, не требующие знания проверяющим закрытого ключа.[1]

Вопрос 16

Распределение открытых ключей

Основное отличие распределения открытых ключей от распределения ключей для криптосистем с секретным ключом состоит в том, что передаваемые ключи не надо прятать, но зато их надо защищать от подделки. Для этого открытые ключи передаются вместе с сертификатами подлинности.

Сертификат открытого ключа А создается участником X и имеет вид

где S_X — цифровая подпись X, a k_A — открытый ключ А.

Чтобы можно было доверять сертификату С_ХА, требуются две не зависящие друг от друга вещи:

• уверенность в том, что ключ, с помощью которого создана цифровая подпись, действительно принадлежит участнику X. Такая уверенность может, в свою очередь, основываться на другом сертификате C_YX;

• доверие по отношению к участнику X, т. е. уверенность в том, что X по злому умыслу или по ошибке не подпишет поддельный ключ.

Имеется несколько схем использования сертификатов.

• Централизованная схема применяется при организации защищенного WWW-обмена с помощью протокола SSL в продуктах Microsoft и Netscape. При этом выделяется несколько специальных участников, называемых Certification Authority. Открытый ключ любого другого участника должен быть подписан одним из выделенных участников.

• Иерархическая схема применяется в системе защищенной электронной почты РЕМ. Участники образуют дерево, причем каждый из них доверяет подписывать ключи всем своим предкам в дереве и сам подписывает ключи своих непосредственных потомков.

• «Демократическая» схема применяется в программе pgp. Все участники равноправны, и каждый может подписать ключ любого участника. Предлагается доверять ключу участника А, если существует цепочка сертификатов

При этом следует быть уверенным в ключе Х₀ и доверять всем Х_i- подписывать ключи. Для перестраховки длина цепочки не должна превышать некоторого небольшого значения, например 3.

Интересное применение можно найти для сертификата вида

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

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

Вопрос 17

Построение криптографически стойких хэш-функций

К используемой для аутентификации не зависящей от ключа хэш-функции h:MA предъявляются следующие требования по криптографической стойкости:

• Стойкость к нахождению прообраза: для любого значения у должно быть невозможно подобрать прообраз x такой, что h(x)=y.

• Стойкость к нахождению второго прообраза: для любого сообщения х должно быть невозможно подобрать х' такое, что h(x}=h(х').

• Стойкость к нахождению коллизий: должно быть невозможно подобрать сообщения х и х' такие, что h (х)=h (х').

Криптографически стойкую хэш-функцию можно пытаться строить с использованием алгоритма шифрования. Основная идея состоит в том, что если E_k— функция шифрования, стойкая к атакам с известным сообщением, то h(x) = E_x(c),c=const, —хэш-функция, стойкая к нахождению прообраза.

Для сообщений, состоящих из нескольких блоков, предложены различные итеративные схемы, среди которых:

• схема Дэвиса — Мейера (Davies — Meyer)

• схема Миягучи (Miyaguchi)

• модифицированная схема Дэвиса — Мейера (Xuejia Lai и James Massey) для алгоритма шифрования IDEA, в котором секретный ключ в 2 раза длиннее блока

• если ключ в 2 раза длиннее блока, можно удвоить длину хэш-суммы с помощью тандемной схемы Дэвиса— Мейера (Xuejia Lai и James Massey):

где

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

Функция MD5 (Message Digest 5, Ronald L. Rivest и Steve Dusse, RSA Data Security, 1991) широко используется в приложениях Internet. Длина результата 128 бит. Каждая итерация алгоритма состоит из 64 операций. Недавно обнаружена нестойкость к нахождению коллизий, но пока не построена настоящая атака на эту функцию.

Функция SHA (Secure Hash Algorithm, NIST, NSA) предложена в качестве национального стандарта США. Длина результата 160 бит. Каждая итерация алгоритма состоит из 80 операций.

Обе функции имеют в качестве внутреннего состояния несколько (в MD5 — 4, в SHA — 5) 32-битовых переменных. На каждом шаге значения переменных в определенном порядке меняются местами, циклически сдвигаются и складываются по модулю 2³² друг с другом и с результатом вычисления нелинейных относительно сложения функций от этих переменных. Нелинейные функции строятся с использованием побитовых операций — отрицания, дизъюнкции и суммы по модулю 2 (операция ). В настоящее время многие специалисты считают наиболее надежной хэш-функцией SHA.[1]

Вопрос 18

Схема идентификации Фиата — Шамира

Авторы схемы и ее расширений — Amos Fiat, Adi Shamir, Uriel Feige. В качестве односторонней функции используется возведение в квадрат по составному модулю. В качестве значения обратной функции берется наименьший квадратный корень. Схема решает следующие проблемы:

• Не может ли участник протокола с помощью многократных специально подобранных запросов узнать закрытый ключ другого участника?

• Большой объем вычислений (например, при использовании RSA) мешает реализовать протокол на пластиковой карте с процессором.

• Требуется некоторая схема распределения открытых ключей.

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

Протокол Фиата—Шамира идентификации клиента Р в системе V.

Параметры

• n=pq, p и q — простые.

• t  N— параметр надежности.

Ключи

• Открытый ключ: v  QR_n.

• Закрытый ключ: s=v^-1/2 порождается центром распределения ключей (ЦРК), если для всех участников используется одно и то же значение n, или каждым участником самостоятельно, если каждый участник сам для себя порождает n.

Повторять t раз.

Утверждение. Не зная s, участник Р не может на одной итерации протокола представить верное значение у с вероятностью, большей ¹/2.

Доказательство. Если z=y²v^b, то для некоторого r Z_n* y=rs^b. Если Р может представить для некоторого значения r Z_n* одновременно rs и r, то он знает, чему равно s. Следовательно, оптимальной тактикой для Р, не знающего значения s, является:

• угадать значение b;

• выбрать y Z_n* и вычислить z=у² v^b.

За t итераций протокола вероятность подбора можно свести к 2^-t.

Утверждение. Это протокол с нулевым раскрытием, т. е. даже без участия Р проверяющий V может изготовить сколько угодно правильных пар (x,у), распределенных так же, как соответствующие пары при участии Р.

Можно уменьшить количество итераций протокола и отказаться от централизованного хранения ключей с помощью модификации протокола. Клиент Р доказывает знание квадратных корней из нескольких значений v_i , связанных с его идентификатором с помощью хэш-функции. Протокол Фиата — Шамира (модифицированный) идентификации клиента Р в системе V. Пусть клиент однозначно идентифицируется строкой I{0,1}^*.

Характеристики

Список файлов ответов (шпаргалок)