Коды аутентичности. Перебором

Способность противостоять атаке перебором всех вариантов дляфункции хэширования определяется длиной хэш-кода.

Слабая сопротивляемостьколлизиямn2

Сильная сопротивляемостьколлизиям2 /2n

128-битовый хэш-код в настоящее время считается достаточнымдля сильной сопротивляемости коллизиям. Предложена машинадля поиска коллизий в MD5 стоимостью 10 млн. $, позволяющаяобнаружить коллизию за 24 дня для 128 битного хэш-кода MD5.

Для 160 битного – более 4000 лет. В настоящее время 2 наиболеепопулярных алгоритма вычисления хэш-кода –SHA-1 иRIPEMD-160 как раз обеспечивают хэш-код 160-битной длины.

Хэш

Проведенный анализ показал, что на однонаправленные и бесколлизионныехэш-функ-ции возможны следующие атаки:

1) нахождение прообраза x по заданному значению y=h(x)

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

2) нахождение прообраза x′ по заданному прообразу x, для которого выполняетсяусловие h(x)=h(x′). Эта атака может быть использована для фальсификации со-общения, подписанного цифровой подписью;

3) нахождение двух прообразов x и x′,x ≠ x′, для которых выполнялось бы усло-вие h(x)=h(x′).

26. Цифровая подпись. Требования у цифровой подписи. Виды коллизий. Прямая цифровая подпись (Алгоритмы. Недостатки). Арбитражная цифровая подпись. Алгоритмы: симметричное шифрование, арбитр видит сообщение, симметричное шифрование, арбитр не видит сообщения, асимметричное шифрование, арбитр не видит сообщения)

Цифровая подпись

Цифровая подпись предназначена для осуществления 2 функций:

 Контроль целостности передаваемого документа: при любомслучайном или преднамеренном изменении документаподпись станет недействительной, потому что вычислена онана основании исходного состояния документа и соответствуетлишь ему.

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

 Декларирование товаров и услуг (таможенные декларации) Регистрация сделок по объектам недвижимости

 Использование в банковских системах

 Электронная торговля и госзаказы

 Контроль исполнения государственного бюджета

 В системах обращения к органам власти

 Для обязательной отчетности перед государственнымиучреждениями

 Организация юридически значимого электронногодокументооборота

 В расчетных и трейдинговых системахСимметричная схема

Симметричные схемы ЭЦП менее распространены чем асимметричные, так какпосле появления концепции цифровой подписи не удалось реализоватьэффективные алгоритмы подписи, основанные на известных в то времясимметричных шифрах. Первыми, кто обратил внимание на возможностьсимметричной схемы цифровой подписи, были основоположники самого понятияЭЦП Диффи и Хеллман, которые опубликовали описание алгоритма подписиодного бита с помощью блочного шифра. Асимметричные схемы цифровойподписи опираются на вычислительно сложные задачи, сложность которых ещене доказана, поэтому невозможно определить, будут ли эти схемы сломаны вближайшее время, (как это произошло со схемой, основанной на задаче обукладке ранца). Также для увеличения криптостойкости нужно увеличивать длинуключей, что приводит к необходимости переписывать программы, реализующиеасимметричные схемы, и в некоторых случаях перепроектироватьаппаратуру.Симметричные схемы основаны на хорошо изученных блочныхшифрах.

В связи с этим симметричные схемы имеют следующие преимущества:

 Стойкость симметричных схем ЭЦП вытекает из стойкостииспользуемых блочных шифров, надежность которых такжехорошо изучена.

 Если стойкость шифра окажется недостаточной, его легкоможно будет заменить на более стойкий с минимальнымиизменениями в реализации.

Асимметричные схемы ЭЦП относятся к криптосистемам с открытым ключом. Вотличие от асимметричных алгоритмов шифрования, в которых зашифрованиепроизводится с помощью открытого ключа, а расшифрование — с помощьюзакрытого, в схемах цифровой подписи подписывание производится сприменением закрытого ключа, а проверка — с применением открытого.

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

 Формирование подписи. Для заданного электронногодокумента с помощью закрытого ключа вычисляется подпись.

 Проверка (верификация) подписи. Для данных документа иподписи с помощью открытого ключа определяетсядействительность подписи.

Для того, чтобы использование цифровой подписи имело смысл, необходимовыполнение двух условий:

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

 Без обладания закрытым ключом должно быть вычислительносложно создать легитимную цифровую подпись.

Следует отличать электронную цифровую подпись от кода аутентичностисообщения (MAC).

ЭЦП должна отвечать следующим требованиям:

1. Достоверность. Она убеждает получателя документа в том, что подписавший сознательно подписал документ.

2. Неподдельность. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.

3. Единственность. Она является частью документа, преступник не сможет перенести подпись на другой документ.

4. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изменить.

5. От подписи невозможно отречься. Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ.

Прямая цифровая подпись.

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

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

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

Все прямые схемы, рассматриваемые далее, имеют общее слабое место.

Действенность схемы зависит от безопасности закрытого ключа отправителя.

Если отправитель впоследствии не захочет признать факт отправки сообщения,он может утверждать, что закрытый ключ был потерян или украден, и в результатекто-то подделал его подпись. Можно применить административное управление,обеспечивающее безопасность закрытых ключей, для того чтобы, по крайнеймере, хоть в какой-то степени ослабить эти угрозы. Один из возможных способовсостоит в требовании в каждую подпись сообщения включать отметку времени(дату и время) и сообщать о скомпрометированных ключах в специальный центр.Другая угроза состоит в том, что закрытый ключ может быть действительноукраден у Х в момент времени Т. Нарушитель может затем послать сообщение,подписанное подписью Х и помеченное временной меткой, которая меньше илиравна Т.

2. Арбитражная цифровая подпись.

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

Арбитр играет важную роль в подобного рода схемах, и все участники должны емуДоверять

симметричное шифрование, арбитр видит сообщения,

Предполагается, что отправитель Х и арбитр А разделяют секретный ключ KХАичто А и Y разделяют секретный ключ KАY. Х создает сообщение М и вычисляет егохэш-значение Н (М). Затем Х передает сообщение и подпись А. Подпись состоитиз идентификатора Х и хэш-значения, все зашифровано с использованием ключаKХА. А дешифрует подпись и проверяет хэш-значение.

Затем А передает сообщение к Y, шифруя его KAY. Сообщение включает IDX,первоначальное сообщение от Х, подпись и отметку времени. Y можетдешифровать его для получения сообщения и подписи. Отметка времениинформирует Y о том, что данное сообщение не устарело и не являетсяповтором. Y может сохранить М и подпись к нему. В случае спора Y, которыйутверждает, что получил сообщение М от Х, посылает следующее сообщение к А:

Арбитр использует KAYдля получения IDХ, М и подписи, а затем, используя KХА,может дешифровать подпись и проверить хэш-код. По этой схеме Y не можетпрямо проверить подпись Х; подпись используется исключительно дляразрешения споров. Y считает сообщение от Х аутентифицированным, потому чтооно прошло через А. В данном сценарии обе стороны должны иметь высокуюстепень доверия к А:1. Х должен доверять А в том, что тот не будет раскрывать KХА И создавать фальшивые подписи в форме ЕKка[IDX|| H (M)].2. Y должен доверять А в том, что он будет посылать ЕKay[ IDX||M || EKxa[IDX|| H (M)] ] только в том случае, если хэш-значение является корректным и подпись была создана Х.

3. Обе стороны должны доверять А в решении спорныхвопросов.

Симметричное шифрование, арбитр не видит сообщение:

Если арбитр не является такой доверенной стороной, то Х должен добиться того,чтобы никто не мог подделать его подпись, а Y должен добиться того, чтобы Х немог отвергнуть свою подпись.

Предыдущий сценарий также предполагает, что А имеет возможность читатьсообщения от Х к Y и что возможно любое подсматривание. Рассмотримсценарий, который, как и прежде, использует арбитраж, но при этом ещеобеспечивает конфиденциальность. В таком случае также предполагается, что Хи Y разделяют секретный ключ KXY. Х передает А свой идентификатор, сообщение, зашифрованное KXY, и подпись.

Подпись состоит из идентификатора и хэш-значения зашифрованного сообщения,которые зашифрованы с использованием ключа KХА. А дешифрует подпись ипроверяет хэш-значение. В данном случае А работает только с зашифрованнойверсией сообщения, что предотвращает его чтение.А передает Y все, что он получил от Х плюс отметку времени, все шифруя сиспользованием ключа KAY.

Хотя арбитр и не может прочитать сообщение, он в состоянии предотвратитьподделку любого из участников, Х или Y. Остается проблема, как и в первомсценарии, что арбитр может сговориться с отправителем, отрицающимподписанное сообщение, или с получателем, для подделки подписи отправителя.

27. Асимметричные алгоритмы ЭЦП.

Виды асимметричных алгоритмов ЭЦП

Как было сказано выше, чтобы применение ЭЦП имело смысл, необходимо, чтобывычисление легитимной подписи без знания закрытого ключа быловычислительно сложным процессом.

Обеспечение этого во всех асимметричных алгоритмах цифровой подписиопирается на следующие вычислительные задачи:

 Задачу дискретного логарифмирования (EGSA)

 Задачу факторизации, то есть разложения числа на простыемножители (RSA)Вычисления тоже могут производиться двумя способами: на базематематического аппарата эллиптических кривых (ГОСТ Р 34.10-2001) и на базеполей Галуа (DSAАлгоритмы ЭЦП подразделяются на обычные цифровые подписи

 ифровые подписи с восстановлением документа.

При верификации цифровых подписей с восстановлением документа телодокумента восстанавливается автоматически, его не нужно прикреплять кподписи. Обычные цифровые подписи требуют присоединение документа кподписи. Ясно, что все алгоритмы, подписывающие хеш документа, относятся кобычным ЭЦП. К ЭЦП с восстановлением документа относится, в частности, RSA.

Схемы цифровой подписи могут быть

 одноразовыми

 многоразовыми.

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

Также алгоритмы ЭЦП делятся на

 детерминированные

 вероятностные.

Детерминированные ЭЦП при одинаковых входных данных вычисляютодинаковую подпись. Реализация вероятностных алгоритмов более сложна, таккак требует надежный источник энтропии, но при одинаковых входных данныхподписи могут быть различны, что увеличивает криптостойкость. В настоящеевремя многие детерминированные схемы модифицированы в вероятностныеПеречень алгоритмов ЭЦП

Асимметричные схемы:

 FDH (FullDomainHash), вероятностная схема RSA-PSS(ProbabilisticSignatureScheme), схемы стандарта PKCS#1 идругие схемы, основанные на алгоритме RSA

 Схема Эль-Гамаля

 Американские стандарты электронной цифровой подписи:

DSA, ECDSA (DSA на основе аппарата эллиптическихкривых)

 Российские стандарты электронной цифровой подписи: ГОСТР 34.10-94 (в настоящее время не действует), ГОСТ Р 34.10-2001

 Схема Диффи-Лампорта

 Украинский стандарт электронной цифровой подписи ДСТУ4145-2002

 Белорусский стандарт электронной цифровой подписи СТБ1176.2-99

СхемаШнорра

Pointcheval-Stern signature algorithm

 Вероятностная схема подписи Рабина

 Схема BLS (Boneh-Lynn-Shacham)

Схема GMR (Goldwasser-Micali-Rivest)

28. Детерминированный алгоритм ЭЦП RSA. Преодоление детерминированности.