Види асиметричних алгоритмів ЕП

 

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

 

Забезпечення цього у всіх асиметричних алгоритмах цифрового підпису спирається на наступні обчислювальні завдання:

 

Ø Завдання дискретного логарифмування (EGSA)

Ø Завдання факторизації, тобто розкладання числа на прості множники (RSA)

 

Обчислення теж можуть проводитися двома способами: на базі математичного апарату еліптичних кривих (ГОСТ Р 34.10-2001) і на базі полів Галуа (АДС) [10].

 

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

 

Алгоритми ЕП поділяються на звичайні цифрові підписи і на цифрові підписи з відновленням документа.[11] При верифікації цифрових підписів з відновленням документа тіло документа відновлюється автоматично, його не потрібно прикріплювати до підпису. Звичайні цифрові підписи вимагають приєднання документа до підпису. Зрозіміло, що всі алгоритми, що підписують хеш документа, відносяться до звичайних ЕП. До ЕП з відновленням документа відноситься, зокрема, RSA.

 

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

 

Також алгоритми ЕП діляться на детерміновані і імовірнісні. [11]Детерміновані ЕП при однакових вхідних даних обчислюють однаковий підпис. Реалізація імовірнісних алгоритмів складніша, оскільки вимагає надійне джерело ентропії, але при однакових вхідних даних підписи можуть бути різні, що збільшує криптостійкість. В даний час багато детермінованих схем модифіковані в імовірнісні.

 

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

 

Перелік алгоритмів ЕП

 

Асиметричні схеми:

Ø FDH (FullDomainHash), імовірнісна схема RSA-PSS (ProbabilisticSignatureScheme), схеми стандарту PKCS # 1 і інші схеми, засновані на алгоритмі RSA

Ø Схема Ель-Гамаля

Ø Американські стандарти електронного цифрового підпису: DSA, ECDSA (АДС на основі апарату еліптичних кривих)

Ø Російські стандарти електронного цифрового підпису: ГОСТ Р 34.10-94 (на даний час не діє), ГОСТ Р 34.10-2001

Ø Схема Диффи-Лампорта

Ø Український стандарт електронного цифрового підпису ДСТУ 4145-2002

Ø Білоруський стандарт електронного цифрового підпису СТБ 1176.2-99

Ø Схема Шнорра

Ø Pointcheval-Sternsignaturealgorithm

Ø Імовірнісна схема підпису Рабина

Ø Схема BLS (Boneh-Lynn-Shacham)

Ø Схема GMR (Goldwasser-Micali-Rivest)

 

На основі асиметричних схем створені модифікації цифрового підпису, які відповідають різним вимогам:

Ø Груповий цифровий підпис

Ø Незаперечний цифровий підпис

Ø «Сліпий» цифровий підпис і справедливий «сліпий» підпис

Ø Конфіденційний цифровий підпис

Ø Цифровий підпис з доказом підробки

Ø Довірений цифровий підпис

Ø Разовий цифровий підпис

 

Підробка підписів

 

Аналіз можливостей підробки підписів називається криптоаналіз. Спробу сфальсифікувати підпис або підписаний документ криптоаналітики називають «атака».

 

Моделі атак та їх можливі результати

 

У своїй роботі Гольдвассер, Мікалі і Ривест моделі описують Наступні Атак, Які актуальні і в теперішній час [4 - Rivest R. L., Shamir A., Adleman L.A methodforobtainingdigitalsignaturesandpublic-keycryptosystems (англ.) // Communications ofthe ACM. — New York, NY, USA: ACM, 1978. — Т. 21. — № 2, Feb. 1978. — С. 120—126. — ISSN0001-0782. — DOI:10.1.1.40.5588]:

Ø Атака з використанням відкритого ключа. Криптоаналітик володіє тільки відкритим ключем.

Ø Атака на основі відомих повідомлень. Противник володіє допустимими підписами набору електронних документів, відомих йому, але не обираєїх.

Ø Адаптивна атака на основі вибраних повідомлень. Криптоаналітик може отримати підписи електронних документів, які він обирає сам.

 

Також в роботі описана класифікація можливих результатів атак:

 

Ø Повний злом цифрового підпису. Отримання закритого ключа, що означає повний злом алгоритму.

Ø Універсальна підробка цифрового підпису. Знаходження алгоритму, аналогічного алгоритму підпису, що дозволяє підробляти підписи для будь-якого електронного документа.

Ø Вибіркова підробка цифрового підпису. Можливість підробляти підписи для документів, обраних криптоаналітиком.

Ø Екзистенціальна підробка цифрового підпису. Можливість отримання допустимої підписи для якогось документа, що не обирається криптоаналітиком.

 

Зрозуміло, що самоюнебезпечною атакою є адаптивна атака на основі обраних повідомлень, і при аналізі алгоритмів ЕП на криптостійкість потрібно розглядати саме її (якщо немає яких-небудь особливих умов).

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