Цифровий підпис на основі криптосистеми Ель-Гамаля.
Загальна методика цифрового підпису
Ідея цифрового підпису на основі криптосистемы RSA.
Цифровим підписом (ЦП)називається результат спеціального криптографічного перетворення, здійснюється над електронним документом його власником.
Мета перетворення – довести неспростовність тексту документа і факту перетворення даних конкретною особою.
Основний метод – перевірка факту використання секретного параметра (ключа)підпису, без знання ключа.
Підпис являє собою блок даних. Підписане повідомлення являє собою повідомлення, передане разом із ЦП.
Наприклад, власник секретного ключа криптосистемы RSA в якості підпісаного повідомлення міг би надати пару .
Дійсно, перетворення може здійснити тільки він. Оскільки присутнє в повідомленні у вихідному виді, будь-який абонент в стані перевірити співвідношення , що буде виконуватися лише в тому випадку, коли дійсно .
Однак подібний підхід не забезпечує стійкість підпису при передачі випадкових даних. Дійсно, виберемо число і побудуємо повідомлення . Тоді, очевидно, , тобто підпис можна побудувати без знання секретного ключа.
З цієї причини, краще замість використовувати пари , де - т.зв. гэш-функция повідомлення : несекретне, заздалегідь обумовлене перетворення. Перевірка підпису починається з обчислення , потім результат порівнюється з
Реальні гэш-функции являють собою складні алгоритми, рекомендовані у відповідних стандартах.
Визначення хэш-функции. Гэш-функция - перетворення бітового рядка довільної довжини в бітовий рядок (блок) фіксованої довжини (звичайно, 160-512 битов), яке має наступнимі властивостямі.
1. Відновлення по , виходячи зі співвідношення , обчислювально неможливо.
2. Виходячи з і , обчислювально неможливо визначення другого прообразу для , тобто такого повідомлення , що .
На практиці, як правило, використовуються хэш-функции, що задовольняють більш жорсткій, ниж остання, умові: має бути гарантована обчислювальна неможливість знаходження довільної колізії, тобто пари повідомлень , таких, що .
Гэш-функции, що задовольняють зазначеним трьом умовам, називаються стійкими проти колізій.
Цифровий підпис Ель-Гамаля складається з пари блоків .
У механізмі цього підпису використовуються ті ж параметри що й у криптосистеме Эль-Гамаля. Перетворення виробляється особою, що володіє секретним ключем. Крім того, використовується хэш-функция повідомлення .
Особа, що підписує документ, повинне для кожного повідомлення, що підписується, вибрати рандомизатор і обчислити «предподпись » .
Потім необхідно використовувати секретний ключ як один з коефіцієнтів порівняння, з якого визначається блок підпису .
Порівняння має вигляд . Тут модулем порівняння обране число , оскільки обидві частини порівняння в перевірочному співвідношенні будуть брати участь у показниках.
Помітимо, що число може дорівнювати , оскільки воно визначається з порівняння по модулі .
Підпис вважається дійсної, якщо .
Оскільки і , те остаточний вид перевірочного співвідношення наступний: . Таким чином, для перевірки підпису досить знання відкритого ключа.
Очевидно, необхідність вибору рандомизатора вимагає застосування криптографически стійких датчиків (генераторів) псевдослучайных чисел.
Вихідні послідовності таких генераторів є непередбаченими. Крім того, структура вихідної послідовності не дозволяє визначити початковий стан і, можливо, інші параметри відповідного датчика.
У Державному Стандарті України ДСТУ 4145-2002 для побудови рандомизаторов цифрового підпису застосовується датчик псевдовипадкових чисел, елементом схеми якого є криптоалгоритм ДСТ 28147-89 у режимі простої заміни.