Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра ЕОМ Лабораторна робота №3 «Алгоритм електронного цифрового підпису RSA» Львів-2006 1.Мета: засвоїти алгоритм електронного цифрового підпису RSA. 2.Теоретична частина: Технологія застосування системи електронного цифрового підпису (ЕЦП) враховує наявність мережі абонентів, що посилають оди одному підписані цифрові документи. Для кожного абонента генерується пара ключів: секретний та відкритий. Секретний ключ зберігається абонентом у таємниці і використовується їм для формування ЕЦП. Відкритий ключ відомий усім іншим користувачам і призначений для перевірки ЕЦП одержувачем підписаного електронного документа. В алгоритмах ЕЦП, як і в асиметричних системах шифрування, використовується різні математичні схеми, засновані на застосуванні одно направлених функцій. Ці схеми розділяються на дві групи. В основі такого поділу лежать відомі складні обчислювальні задачі: задача факторизації (розкладання на множники) великих цілих чисел; задача дискретного логарифмування; Першою і найбільш відомою у всьому світі конкретною системою ЕЦП стала система RSA, математична схема якого була розроблена у 1977 році в Массачусетскому технологічному інституті США.  EMBED Equation.3 
 і значення функції  EMBED Equation.3 
. Далі відправник обчислює число Е з умов:  EMBED Equation.3 
 та число D з умов:  EMBED Equation.3 

Рис.1. Узагальнена схема система цифрового підпису RSA Припустимо, що відправник хоче підписати повідомлення Ь перед його відправкою. Спочатку повідомлення М (блок інформації, файл, таблиця) стискаються з допомогою хеш-функції h(∙) у ціле число m: m=h(M). Потім обчислюють цифровий підпис S під електронним документом М, використовуючи хеш-значення m і секретний ключ D:  EMBED Equation.3 
. Пара (M,S) передається партнеру-одержувачу як електронний документ М, підписаний цифровим підписом S, причому підпис S сформований власником секретного ключа D. Після приймання пари (M,S) отримувач обчислює хеш-значення повідомлення М двома різними способами. Насамперед він відновлює хеш-значення m’,застосовуючи криптографічне перетворення підпису S з використанням відкритого ключа Е:  EMBED Equation.3 
. Крім того, він знаходить результат хешування прийнятого повідомлення М з допомогою токої ж хеш-функції h(∙): m=h(M). Якщо спостерігається рівність обчислених значень, тобто  EMBED Equation.3 
 одержувач признає пару (M,S) дійсною. Доведено, що тільки власник секретного ключа D може сформувати цифровий підпис S по документу M, а визначити секретне число D по відкритому числу E не легше, ніж розкласти модуль N на множники. Крім того, можна строго математично довести, що результат перевірки цифрового підпису S буде позитивним лише у тому випадку, якщо при обчисленні S був використаний секретний ключ D, що відповідає відкритому ключу E. Тому відкритий ключ E іноді називають «ідентифікатором» того, хто підписався. Недоліки алгоритму цифрового підпису RSA: При обчисленні модуля N, ключів E та D для системи цифрового підпису RSA необхідно перевіряти велику кількість додаткових умов, що зробити практично важко. Не виконання будь-якого з цих правил робить можливим фальсифікацію цифрового підпису з боку того, хто виявить таке не виконання. При підписанні важливих документів неможна допускати подібного риску навіть теоретично. Для забезпечення крипостійкості цифрового підпису RSA по відношенню до спроби фальсифікації на рівні, наприклад, алгоритму шифрування DES, тобто 1018, необхідно використовувати при обчисленнях N,D та E цілі числа не менше 2512 (або біля 10154) кожне, що потребує більших обчислювальних затрат, що перевищують на 20-30% обчислювальні затрати інших алгоритмів цифрового підпису при збереженні того ж рівня крипостійкості. Цифровий підпис RSA уразливий до так званої мультиплікативної атаки. Інакше кажучи, алгоритм цифрового підпису RSA дозволяє зловмиснику без знання секретного ключа D сформувати підписи під тими документами, в яких результат хешування можна обчислити як добуток хешування вже підписаних документів. Приклад. Припустимо, що зловмисник може сконструювати три повідомлення М1, М2, М3, в яких хеш-значення  EMBED Equation.3 
 причому  EMBED Equation.3 
. Припустимо також, що для двох повідомлень М1 та М2 отримані законні підписи  EMBED Equation.3 
та  EMBED Equation.3 
. Тоді зловмисник може легко обчислити підпис S3 для документа М3, навіть не знаючи секретного ключа D:  EMBED Equation.3 
. Дійсно,  EMBED Equation.3 
. Більш надійний і зручний для реалізації на персональних ЕОМ алгоритм цифрового підпису був розроблений у 1984 році американцем арабського походження Тахером Ель Гама лем. В 1991 році НІСТ США обґрунтував перед комісією Конгресу США вибір алгоритма цифрового підпису Ель Гамаля в якості основи для національного стандарта. 3.Текст програми: