Цифровий підпис на основі криптосистеми Ель-Гамаля.

Загальна методика цифрового підпису

 

Ідея цифрового підпису на основі криптосистемы RSA.

Цифровим підписом (ЦП)називається результат спеціального криптографічного перетворення, здійснюється над електронним документом його власником.

Мета перетворення – довести неспростовність тексту документа і факту перетворення даних конкретною особою.

Основний метод – перевірка факту використання секретного параметра (ключа)підпису, без знання ключа.

Підпис являє собою блок даних. Підписане повідомлення являє собою повідомлення, передане разом із ЦП.

Наприклад, власник секретного ключа криптосистемы RSA в якості підпісаного повідомлення міг би надати пару .

Дійсно, перетворення може здійснити тільки він. Оскільки присутнє в повідомленні у вихідному виді, будь-який абонент в стані перевірити співвідношення , що буде виконуватися лише в тому випадку, коли дійсно .

Однак подібний підхід не забезпечує стійкість підпису при передачі випадкових даних. Дійсно, виберемо число і побудуємо повідомлення . Тоді, очевидно, , тобто підпис можна побудувати без знання секретного ключа.

З цієї причини, краще замість використовувати пари , де - т.зв. гэш-функция повідомлення : несекретне, заздалегідь обумовлене перетворення. Перевірка підпису починається з обчислення , потім результат порівнюється з

Реальні гэш-функции являють собою складні алгоритми, рекомендовані у відповідних стандартах.

Визначення хэш-функции. Гэш-функция - перетворення бітового рядка довільної довжини в бітовий рядок (блок) фіксованої довжини (звичайно, 160-512 битов), яке має наступнимі властивостямі.

1. Відновлення по , виходячи зі співвідношення , обчислювально неможливо.

2. Виходячи з і , обчислювально неможливо визначення другого прообразу для , тобто такого повідомлення , що .

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

Гэш-функции, що задовольняють зазначеним трьом умовам, називаються стійкими проти колізій.

 

 

Цифровий підпис Ель-Гамаля складається з пари блоків .

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

Особа, що підписує документ, повинне для кожного повідомлення, що підписується, вибрати рандомизатор і обчислити «предподпись » .

Потім необхідно використовувати секретний ключ як один з коефіцієнтів порівняння, з якого визначається блок підпису .

Порівняння має вигляд . Тут модулем порівняння обране число , оскільки обидві частини порівняння в перевірочному співвідношенні будуть брати участь у показниках.

Помітимо, що число може дорівнювати , оскільки воно визначається з порівняння по модулі .

Підпис вважається дійсної, якщо .

Оскільки і , те остаточний вид перевірочного співвідношення наступний: . Таким чином, для перевірки підпису досить знання відкритого ключа.

Очевидно, необхідність вибору рандомизатора вимагає застосування криптографически стійких датчиків (генераторів) псевдослучайных чисел.

Вихідні послідовності таких генераторів є непередбаченими. Крім того, структура вихідної послідовності не дозволяє визначити початковий стан і, можливо, інші параметри відповідного датчика.

У Державному Стандарті України ДСТУ 4145-2002 для побудови рандомизаторов цифрового підпису застосовується датчик псевдовипадкових чисел, елементом схеми якого є криптоалгоритм ДСТ 28147-89 у режимі простої заміни.