Схеми електронного підпису

Розглянемо тепер приклад практичної схеми електронного підпису зі схемою аутентифікації Шнорра. У цьому протоколі інтерактивність потрібна тільки для того, щоб одержати випадковий запит від того, що перевіряє. Тому якби в того, що доводить було надійне джерело випадковості, що користається довірою у того, що перевіряє, то протокол можна було б зробити не інтерактивним. Фіат і Шамір запропонували спосіб перетворення протоколу аутентифікації в схему електронного підпису шляхом заміни випадкового запиту деяким «сурогатом». А саме, нехай - повідомлення, того, хто підписується, - криптографічна хеш-функція. Тоді замість звертання до того, що перевіряє (він же - одержувач повідомлення) той, що доводить (він же - Той, хто підписує) обчислює величину і використовує її як запит . Цей метод універсальний, тому що може бути застосований до широкого класу протоколів аутентифікації. Опишемо тепер одержувану в результаті такого перетворення схему електронного підпису Шнорра. Відкритий і таємний ключі тим, хто підписує генеруються в цій схемі в такий же спосіб, як у схемі аутентифікації Шнорра. Відкритий ключ міститься в загальнодоступному сертифікованому довіднику.

1. Той, хто підписує вибирає випадкове число й обчислює .

2. Той, хто підписує обчислює , де - повідомлення, Той, хто підписується.

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

4. Одержувач обчислює і перевіряє, чи виконується рівність . Якщо так, то підпис правильний, у противному випадку - відкидається.

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

Легко перевірити, що для підпису, генерованого відповідно до протоколу, перевірка п.4 завжди буде виконана.

Стійкість схеми Шнорра в значній мірі залежить від властивостей функції . Якщо супротивник уміє відшукувати колізії спеціального виду, тобто по заданій парі знаходити інше повідомлення , , таке, що , то він може здійснювати екзистенційну підробку підписів. Для цього досить перехопити повідомлення і підпис для нього, а також знайти колізію зазначеного виду. Тоді пари буде також підписом і для повідомлення .

Хеш-функція є невід’ємною частиною конструкції схем електронного підпису. Це є наслідком необхідності підписувати повідомлення різної довжини. Звичайно, довгі повідомлення можна розбивати на блоки, що мають необхідну для схеми підпису довжину, і підписувати кожен блок. Але це рішення неефективне. На практиці використовуються хеш-функції, що перетворюють повідомлення довільної довжини в хеш-значення необхідної довжини. Ясно, що така хеш-функція повинна бути в якомусь сенсі стійкою проти спроб знайти колізії. Але оскільки практичні хеш-функції конструюються для конкретних довжин хеш-значень (скажемо, 256 бітів), формалізувати цю вимогу не вдається.

На відміну від протоколів аутентифікації, для практичних схем електронного підпису невідомі методи доказу стійкості. Стійкі схеми підпису не можуть бути доказами з нульовим розголошенням. Це легко зрозуміти, якщо згадати, що визначення нульового розголошення вимагає існування моделюючої машини, що, не знаючи таємного ключа, створює для усіх величин, що спостерігаються що перевіряє, розподіл імовірностей, невідрізнимий від того, який виникає при виконанні протоколу. Але усе, що бачить той, що перевіряє (він же - одержувач) у процесі виконання протоколу, це - повідомлення з підписами. Отже, моделююча машина, якщо вона існує, може підробляти підпис, тому що створювані нею «підписи» повинні бути невідрізнимі від справжніх, зокрема, і для алгоритму перевірки підписів.

Стійкість схем електронного підпису проти пасивного супротивника, що, знає тільки відкритий ключ і намагається підробляти підпис, може бути доведена в так званій моделі з випадковим оракулом. У цій моделі той, хто підписує і перевіряє замість обчислення функції звертаються до оракула, що для кожного вхідного значення вибирає випадкове вихідне значення і видає його як відповідь. При цьому пара запам’ятовується й у випадку повторного звертання з вхідним значенням оракул знову видасть значення  . Як помітили Фіат і Шамір, ідея доказу коректності схем аутентифікації може бути застосована в даній моделі для доказу стійкості схем підпису проти пасивного супротивника. Цей результат справедливий для широкого класу схем підпису, що включає схему Шнорра. Фактично це означає, що схеми підпису є стійкими (проти зазначеного вище пасивного супротивника), якщо хеш-функція поводиться, як випадкова функція. Це твердження є по суті єдиним результатом теоретичної криптографії, що стосується стійкості практичних схем електронного підпису.

Таким чином використання цифрового підпису забезпечує:

- по-перше, можливість ідентифікації приналежності підпису на основі об’єктивних показників;

- по-друге, високу захищеність від підробки;

- по-третє, це твердий зв’язок із документом, що підписується.

Якщо перші дві переваги ще можна реалізувати для традиційного підпису, то виконання третього можливе тільки у випадку застосування електронного цифрового підпису (ЕЦП ). Питання про застосування інших аналогів власноручного підпису виходить за рамки розглянутої тематики.

Виконання всіх трьох вимог стає можливим виходячи із самої природи ЕЦП. ЕЦП є деяке досить довге число, отримане в результаті перетворення електронного образу документа, що захищається, із використанням секретного (особистого) ключа відправника. Будь-хто може перевірити ЕЦП під документом за допомогою відповідних перетворень із використанням, знову таки, електронного образу документа, відкритого (публічного) ключа відправника і власне значення ЕЦП. Відкритий і Таємний ключі однозначно зв’язані між собою, однак неможливо обчислити Таємний ключ за відкритим. Точніше, якщо формулювати зовсім строго, то в даний момент не знайдено алгоритмів, що дозволяють здійснити таке обчислення за прийнятний час, з урахуванням сучасного рівня розвитку обчислювальної техніки і використовуваної довжини ключів.

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