Электронная подпись на базе шифра RSA

Если А планирует подписывать документ, то он должен выбрать параметры RSA.

А выбирает два простых числа P и Q, вычисляет N=P∙Q и f=(P-1)∙(Q-1). Затем выбирает d, взаимно простое с f, вычисляет c=d^-1 mod f. Публикует открытый ключ (N, d), с – закрытый ключ, держит в секрете.

Пусть А хочет подписать сообщение m=m₁…m_n. Тогда вначале он вычисляет хеш-функцию y=h(m₁…m_n), которая ставит в соответствие сообщению m число y. Предполагается, что алгоритм вычисления хеш-функции всем известен. Важное свойство: практически невозможно изменить m₁…m_n, не изменив y. Поэтому А достаточно снабдить подписью только число y, и эта подпись будет относиться ко всему сообщению m₁…m_n.

А вычисляет число s= y^c mod N. Число s - это цифровая подпись. Она добавляется к сообщению m, тем самым А имеет подписанное сообщение <m,s>.

Теперь каждый, кто знает открытые параметры абонента А, ассоциированные с его именем, т.е. числа (N, d), может проверить подлинность его подписи. Для этого необходимо, взяв подписанное сообщение вычислить значение хеш-функции y=h(m₁…m_n), число w=s^d mod N и проверить равенство w= y. Если подпись подлинная, то w= y

Стойкость основана на сложности задачи факторизации.