Технології цифрових підписів

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

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

У принципі, можна знайти інший текст, що дає те ж саме значення хеш-функції, але змінити в нашому тексті десять-двадцять байт так, щоб текст залишився повністю осмисленим, так ще й змінився у вигідну нам сторону (наприклад, зменшив суму до оплати у два рази) – надзвичайно складно. Саме для усунення цієї можливості хеш-функції створюють такими ж складними як і криптоалгоритми – якщо текст із таким же значенням хеш-функції можна буде підібрати тільки методом повного перебору, а множина значень буде складати як і для блокових шифрів 2³²–2¹²⁸ можливих варіантів, то для пошуку подібного тексту зловмисникові будуть потрібні мільйони років.

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

Представимо тепер готову до передачі хеш-суму у вигляді декількох k -бітних блоків h_i, де k – це розмір повідомлень за алгоритмом RSA. Обчислимо над кожним блоком значення s_i=((h_i)^d)mod n, де d – це закритий ключ відправника. Тепер повідомлення, що складається із блоків s_i можна "спокійно" передавати по мережі. Ніякої небезпеки за відомими h_i й s_i знайти секретний ключ немає – це настільки ж складна задача, як і задача "логарифмування в кінцевому полі". А от будь-який одержувач повідомлення може легко прочитати вихідне значення h_i, виконавши операцію ((s_i)^e)modn=((h_i)^d*e)modn=h_i – відкритий ключ (e,n) є у всіх, а те, що піднесення будь-якого числа до степеня (e*d) за модулем n дає вихідне число, доведено вище. При цьому ніхто інший, крім Вас, не знаючи Вашого закритого ключа d не може, змінивши текст, а отже, і хеш-суму, обчислити такі s'_i, щоб при їхньому піднесенні до степеня e вийшла хеш-сума h'_i, що збігається з хеш-сумою фальсифікованого тексту.

Таким чином, маніпуляції з хеш-сумою тексту представляють із себе "асиметричне шифрування навпаки": при відправленні використовується закритий ключ відправника, а для перевірки повідомлення – відкритий ключ відправника. Подібна технологія одержала назву "електронний підпис". Інформацією, що унікально ідентифікує відправника (його віртуальним підписом), є закритий ключ d. Жодна людина, що не володіє цією інформацією, не може створити таку пару (текст, s_i), що описаний вище алгоритм перевірки дав би позитивний результат.

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