КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Алгоритм электронной цифровой подписи DSA.Алгоритм цифровой подписи DSА (Digital Signature Algorithm) предложен в 1991 г. в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSА является развитием алгоритмов цифровой подписи Эль Гамаля и К.Шнорра. Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р - простые числа, L бит каждое (512 £ L £ 1024); q - простое число длиной 160 бит (делитель числа (Р-1)). Числа G, Р, q являются открытыми и могут быть общими для всех пользователей сети. Отправитель выбирает случайное целое число X, 1 < Х < q. Число Х является секретным ключом отправителя для формирования электронной цифровой подписи. Затем отправитель вычисляет значение Y = GX mod Р. Число Y является открытым ключом для проверки подписи отправителя и передается всем получателям документов. Этот алгоритм также предусматривает использование односторонней функции хэширования h(·). В стандарте DSS определен алгоритм безопасного хэширования SНА (Secure Hash Algorithm). Для того чтобы подписать документ М, отправитель хэширует его в целое хэш-значение m: m = h(М), 1<m<q , затем генерирует случайное целое число К, 1< К< q, и вычисляет число r: r = (GK mod Р) mod q . Затем отправитель вычисляет с помощью секретного ключа Х целое число s: s = ((m + r * X)/K) mod q . Пара чисел (r,s) образует цифровую подпись S = (r,s) под документом М. Таким образом, подписанное сообщение представляет собой тройку чисел (М,r,s). Получатель подписанного сообщения (М,r,s) проверяет выполнение условий 0 < r < q, 0 < s < q и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение w = (1/s) mod q , хэш-значение m = h(М) и числа u1 = (m * w) mod q , u2 = (r * w) mod q . Далее получатель с помощью открытого ключа Y вычисляет значение v = ((Gu1 * Yu2 ) mod Р) mod q и проверяет выполнение условия v = r . Если условие v = r выполняется, тогда подпись S=(r,s) под документом М признается получателем подлинной. Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(r,s) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом Х (не раскрывая при этом значения ключа X) и что отправитель подписал именно данный документ М. По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм DSА имеет следующие основные преимущества:
Недостатком алгоритма DSА является то, что при подписывании и при проверке подписи приходится выполнять сложные операции деления по модулю q: s = ((m + rX)/K) (mod q), w = (1/s) (mod q) , что не позволяет получать максимальное быстродействие. Следует отметить, что реальное исполнение алгоритма DSА может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m. Можно заранее создать строку случайных значений К и затем для каждого из этих значений вычислить значения r. Можно также заранее вычислить обратные значения К-1 для каждого из значений К. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и К-1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSА.
|