ВУЗ:
Составители:
Рубрика:
113
ния из соотношения
)],([)(
,,,
MDECEM
AKAKAK
=
=
и проверкой, является ли М осмысленным текстом. Т.е. здесь
E
K,A
действуют как преобразование расшифрования.
Авторство пользователя
А основано на том, что только он
знает секретное преобразование
D
K,A
. Злоумышленник, желаю-
щий подменить сообщение
М на другое сообщение
M
′
, должен
решить задачу нахождения такого значения
С, что
)(
,
CEM
AK
′
=
′
.
В силу односторонней природы (используется односторон-
няя функция) преобразования сделать это крайне трудно.
Обычно на практике, для сокращения времени подписыва-
ния преобразования
AK
D
,
применяется не для всего исходного
текста
М, а для некоторой его хэш-функции H(M) , которая ото-
бражает любое сообщение
М в сообщение H(M) фиксированно-
го малого размера. Другими словами, цифровая подпись имеет
вид
)].([
,
MHD
AK
Пользователь
В, получив сообщение М и подпись к нему
D
K,A
может вычислить (функция хэширования общеизвестна) и
проверить выполнимость соотношения
).()]]([[
,,
MHmHDE
AKAK
=
С учетом сказанного, общую схему цифровой подписи мо-
жет представить следующим образом: схема включает:
1. Пространство открытых сообщений },{
~
MM = к кото-
рым применяется алгоритм цифровой подписи.
2. Пространство секретных параметров },{
~
KK = которые
выбираются пользователем.
3. Алгоритм генерации за полиномиальное время пары
(E
K
,D
K
) - открытого и секретного ключей по выбранному пара-
метру
К.
4. Алгоритм подписи
Q, который вырабатывает значение Q
[М, D
K
], называемое цифровой подписью сообщению М.
5. Алгоритм проверки подписи, который проверяет пра-
114
вильность подписи и сообщение с использованием открытого
ключа
Е
K
.
Рассмотрим теперь конкретный алгоритм цифровой подпи-
си, предложенный Эль Гамалем (1985)
Все пользователи знают большое простое число и прими-
тивный элемент
)1,2( −∈ pa по модулю Р. Секретная информа-
ция подписывающего пользователя
А состоит из двух частей:
1.
)1,2( −∈ pX
a
- долговременный секретный ключ под-
писи выбирается случайно из интервала
)1,2( −p и хранится в
секрете.
2.
)1,1( −∈ pK
A
- разовый секретный ключ подписи кон-
кретного сообщения, такой что 1)1,(
=
−
pKHOD
A
, т.е.
A
K вза-
имно просто с
p -1.
Открытая информация подписывающего тоже имеет 2 час-
ти:
1. )(mod
pay
A
X
A
= - открытый ключ подписи.
2. )(mod
par
A
K
= - первая из двух частей подписи (r,s).
Подписываемое сообщение представляется числом из ин-
тервала
(0,p -1) точнее его функцией хэширования H(M).
АЛГОРИТМ ПОДПИСИ СООБЩЕНИЯ М:
1. Пользователь А выбирает случайное число из интерва-
ла
(1, 1)P
−
, таким образом, чтобы НОД (, 1)1
A
KP
−
=
2. Вычисляет
1
(mod 1)
A
KP
−
−
т.е. число удовлетворяющее
сравнению 1(mod 1)
A
Kx P
⋅
≡− Именно для разрешимости этого
сравнения при выборе
A
K наложено условие его простоты,
с
1P − .
3. Вычисляем первую часть подписи )(mod
par
A
K
= .
4. Вычисляем вторую часть подписи по формуле
[
]
1
(mod 1)
AA
SK MrX P
−
=− −.
На этом процедура выработки подписи
(r,S) к сообщению
М заканчивается, и эти данные M,r,S сообщаются получателям.
