Детерминированная функция цифровой подписи

Подход RSA.

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

29. Вероятностные алгоритмы ЭЦП. Алгоритм Эль-Гамаля цифровая подпись. DSS. ГОСТ 3410-94

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

8. Генерация ключейГенерируется случайное простое число p длины n.

Выбирается произвольное целое число g, являющеесяпервообразным корнем по модулю p.

Выбирается случайное число x из интервала (1,p), взаимнопростое с p-1.

Вычисляется y = gxmod p.

Открытым ключом является тройка (p,g,y), закрытым ключом —число x.

Работа в режиме подписиПри работе в режиме подписи предполагается наличиефиксированной хеш-функции h(), значения которой лежат винтервале (1,p − 1).

Подпись сообщенийДля подписи сообщения M выполняются следующиеоперации:

1. Вычисляется дайджест сообщения M: m = h(M).

2. Выбирается случайное число 1 < k < p − 1 взаимно простое сp-1 и вычисляется

3. С помощью расширенного алгоритма Евклида вычисляетсячисло s, удовлетворяющее сравнению:

4. Подписью сообщения M является пара (r,s).Проверка подписи

Зная открытый ключ (p,g,y), подпись (r,s) сообщения M проверяется следующимобразом:

1. Проверяется выполнимость условий: 0 < r < p и 0 < s < p − 1.

Если хотя бы одно из них не выполняется, то подписьсчитается неверной.

2. Вычисляется дайджест m = h(M).

3. Подпись считается верной, если выполняется сравнениеОтечественный стандарт цифровой подписи ГОСТ 3410-94В отечественном стандарте ГОСТ 3410-94, принятом в 1994 году, используетсяалгоритм, аналогичный алгоритму, реализованному в стандарте DSS.

DSS

DSS основан на трудности вычисления дискретных логарифмов и базируется насхеме ElGamal.

Общие компоненты группы пользователейСуществует три параметра, которые являются открытыми и могут быть общимидля большой группы пользователей.

160-битное простое число q, т.е. 2 159< q < 2 160.

Простое число р длиной между 512 и 1024 битами должно быть таким, чтобы qбыло делителем (р - 1), т.е. 2L-1< p < 2L, где 512 < L < 1024 и (p-1)/q являетсяцелым.

g = h(p-1)/qmod p, где h является целым между 1 и (р-1) .

Зная эти числа, каждый пользователь выбирает закрытый ключ и создаетоткрытый ключ.

Закрытый ключ отправителяЗакрытый ключ х должен быть числом между 1 и (q-1) и должен быть выбранслучайно или псевдослучайно.

x - случайное или псевдослучайное целое,0 < x < q ,Открытый ключ отправителяОткрытый ключ вычисляется из закрытого ключа как у = gxmod p.

Случайное число, уникальное для каждой подписи.

k - случайное или псевдослучайное целое, 0 < k < q, уникальное для каждогоподписывания.

Подписывание

Для создания подписи отправитель вычисляет две величины, r и s, которыеявляются функцией от компонент открытого ключа (p, q, g), закрытого ключапользователя (х), хэш-кода сообщения Н (М) и целого k, которое должно бытьсоздано случайно или псевдослучайно и должно быть уникальным при каждомподписывании.

r = (gkmodp) modqs = [ k-1(H (M) + xr) ] modqПодпись = (r, s)Проверка подписи

Получатель выполняет проверку подписи с использованием следующих формул.

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

w = s-1mod qu1 = [ H (M) w ] mod qu2 = r w mod q

v = [ (gu1yu2) mod p ] mod q

подпись корректна, если v = r

В стандарте ГОСТ 3410-94 используется хэш-функция ГОСТ 3411, котораясоздает хэш-код длиной 256 бит. Это во многом обуславливает требования квыбираемым простым числам p и q:

1. р должно быть простым числом в диапазоне2. 2 509< p < 2 512

3. либо21020< p < 21024

4. q должно быть простым числом в диапазоне2 254< q < 2 256

q также должно быть делителем (р-1).

Аналогично выбирается и параметр g. При этом требуется, чтобы gq(mod p) = 1.

Закрытым ключом является произвольное число х0 < x < q

Открытым ключом является число yy = gxmod p

Для создания подписи выбирается случайное число k0 < k < q

Подпись состоит из двух чисел (r, s), вычисляемых по следующим формулам:

r = (gkmod p) mod q

s = (kH(M) + xr) modq

Получатель вычисляет

w = H(M)-1mod qu1 = w s mod qu2 = (q-r) w mod q

v = [(gu1yu2) mod p] mod q

Подпись корректна, если v = r.

30. Инфраструктура открытого ключа ЭЦП.

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

Задача защиты ключей от подмены решается с помощью сертификатов.

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

 централизованные децентрализованные.

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

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

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

В настоящее время существуют следующие устройства хранения закрытогоключа:

 Дискеты

 Смарт-карты

 USB-брелок

 Таблетки Touch-Memory

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

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

В соответствии с законом «ОБ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ»,ответственность за хранение закрытого ключа владелец несет сам.

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

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

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

12. Формальное описаниеПусть имеются две стороны информационного обмена — A1,A2— и третьясторона A3, которой доверяют A1и A2. Стороне A1принадлежит пара (K1o, K1s),где K1o— открытый ключ, K1s— закрытый (секретный) ключ. Стороне A3принадлежит пара (K3o, K3s).A1регистрируется у A3, указывая данные о себе и свой K1o. A3выдает стороне A1сертификат S, устанавливающий соответствие между A1и K1o. S содержит K1o,сведения о A1, название стороны A3, подпись A3(результат применения хеш-функции к данным сертификата, зашифрованный с помощью K3s) и другуюинформацию.

A1посылает стороне A2свой сертификат S и его копию Ss, зашифрованную спомощью K1s. A2извлекает из S ключ K1oи расшифровывает с помощью него Ss.

Совпадение результата расшифровки с S подтверждает, что K1oдействительно

принадлежит A1.

Затем с помощью широко известного K3oрасшифровывается подпись стороны A3.

Если в результате получается тот же сертификат с теми же сведениями о A1иключом K1o— значит A1действительно прошел регистрацию у A3.

13. Структура сертификата

Электронная форма сертификата определяется стандартом X.509. Переченьобязательных и необязательных полей, которые могут присутствовать всертификате, определяется данным стандартом, а также законодательством.Согласно законодательству России и Украины (закон "Об электронной цифровойподписи") сертификат должен содержать следующие поля:Украина Россияуникальный регистрационный номер сертификата + +даты и время начала и окончания срока действиясертификата+ +фамилия, имя и отчество владельца сертификатаключа подписи или псевдоним владельца+ +открытый ключ + +наименование и реквизиты ЦС + +наименование криптографического алгоритма + +информацию об ограничении использованияподписи+ +указание, что сертификат выдан в Украине + -Кроме этого в сертификат могут вноситься дополнительные поля.

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

31. Выбор длины ключа. Закон Мура.

128-битный ключ в два раза устойчивее к взлому, чем 64-битный?НЕТ! Это распространенная ошибка. Каждый дополнительныйбит удваивает количество возможных ключей и затраты наполный перебор. Ключ длиной 128 бит является в18446744073709551616 раз более сложным для подбора, посравнению с ключом длиной 64 бита (который уже неназовешь совсем легким).

Закон Мура

Для заданной стоимости вычислительная мощностьувеличивается в 2 раза каждый год.

года 72 через ключ битный - 56 ~ ключ битный - 128

32. Современные способы оценки требуемой длины ключа.

1.

2.

33. Одноразовые ключи. S-Key.

S/Key—система одноразовых паролей на основе стандартов MD4 иMD5. Она предназначена для борьбы с так называемыми«повторными атаками», когда хакер подслушивает канал, выделяетиз трафика аутентификатор пользователя и его пароль и вдальнейшем использует их для несанкционированного доступа.

1)Клиент выбирает случайный пароль W.

2)Клиент вычисляет одностороннюю функцию от W:Hn(W).

3)Это значение передается серверу.

4)Сеансовые ключи:

5)K1= Hn-1(W).…Kn= H(W)

Парольная фраза соединяется с «зерном», полученным отсервера в незашифрованном виде. Это несекретное«зерно» дает клиенту возможность использовать одну иту же парольную фразу на множестве машин (с разными«зернами») и повторно использовать пароли, заменяя«зерно».

34. Разбиение секрета. Разделение секрета. Схема Шамира.

Разбиение секрета

Ключ

Пользователь 1

Пользователь 2

Пользователь 3

Пользователь 4

Разделение секрета

В отличии от прыоцедуры разбиения секрета, в процедуреразделения секрета количество долей, которые нужны длявосстановления секрета, может отличаться от того, на сколько долеймы разделили секрет. Такая схема носит названия пороговой схемы, где n—количество долей, на которые был разделѐн секрет, а t-количество долей, которые нужны для восстановления секрета.В тривиальном случае t= nмы получаем схему разбиения секрета.Интерполяционныймногочлен Лагранжа—многочленминимальной степени, принимающий данные значения вданном наборе точек. Для n+ 1 пар чисел (xi,yi), где все xiразличны, существует единственный многочлен L(x) степени неболее n, для которого L(xi) = yi.

Схема Шамира

Идея схемы заключается в том, что двух точек достаточнодля задания прямой, трех точек—для задания параболы,четырех точек—для кубической параболы, и так далее. Чтобызадать многочлен степени kтребуется k+ 1 точек.Если мы хотим разделить секрет таким образом, чтобывосстановить его могли только kчеловек, мы «прячем» его вформулу (k− 1)-мерного многочлена. Восстановить этотмногочлен можно по kточкам. Количество же различныхточек многочлена не ограничено (на практике оноограничивается размером числового поля, в котором ведутсярасчѐты).