Создание и проверка подписи

Создание и проверка подписи состоит из следующих шагов:

- пользователь А создает пару ключей KR_A и KU_A, используемых для создания и проверки подписи передаваемых сообщений;

- пользователь А делает доступным некоторым надежным способом свой ключ проверки, т.е. открытый ключ KU_A. Составляющий пару закрытый ключ KR_A держится в секрете.

 

Рис.8. Создание и проверка подписи

Если А хочет послать подписанное сообщение В, он создает подпись E_KRa[M] для этого сообщения, используя свой закрытый ключ KRA.

Когда В получает подписанное сообщение, он проверяет подпись D_KUa[M], используя открытый ключ А KUA. Никто другой не может подписать сообщение, так как этот закрытый ключ знает только А.

До тех пор, пока пользователь или прикладная система надежно хранит свой закрытый ключ, их подписи достоверны.

Кроме того, невозможно изменить сообщение, не имея доступа к закрытому ключу А; тем самым обеспечивается аутентификация и целостность данных.

В этой схеме все сообщение подписывается, причем для подтверждения целостности сообщения требуется много памяти. Каждое сообщение должно храниться в незашифрованном виде для использования в практических целях. Кроме того, копия сообщения также должна храниться в зашифрованном виде, чтобы можно было проверить в случае необходимости подпись. Более эффективным способом является шифрование небольшого блока битов, который является функцией от сообщения. Такой блок, называемый аутентификатором, должен обладать свойством невозможности изменения сообщения без изменения аутентификатора. Если аутентификатор зашифрован закрытым ключом отправителя, он является цифровой подписью, с помощью которой можно проверить исходное сообщение. Далее эта технология будет рассматриваться в деталях.

Важно подчеркнуть, что описанный процесс создания подписи не обеспечивает конфиденциальность. Это означает, что сообщение, посланное таким способом, невозможно изменить, но можно подсмотреть. Это очевидно в том случае, если подпись основана на аутентификаторе, так как само сообщение передается в явном виде. Но даже если осуществляется шифрование всего сообщения, конфиденциальность не обеспечивается, так как любой может расшифровать сообщение, используя открытый ключ отправителя.

Обмен ключей: две стороны взаимодействуют для обмена ключом сессии, который в дальнейшем можно использовать в алгоритме симметричного шифрования.

Некоторые алгоритмы можно задействовать тремя способами, в то время как другие могут использоваться одним или двумя способами.

Перечислим наиболее популярные алгоритмы с открытым ключом и возможные способы их применения.

Алгоритм	Шифрование/ дешифрование	Цифровая подпись	Обмен ключей
RSA	да; непригоден для больших блоков	да	да
DSS	нет	да	нет
Диффи-Хеллман	нет	нет	да

Алгоритм RSA

Диффи и Хеллман определили новый подход к шифрованию, что вызвало к жизни разработку алгоритмов шифрования, удовлетворяющих требованиям систем с открытым ключом. Одним из первых результатов был алгоритм, разработанный в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.

Алгоритм основан на использовании того факта, что задача факторизации является трудной, т.е. легко перемножить два числа, в то время как не существует полиномиального алгоритма нахождения простых сомножителей большого числа.

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n.

Алгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n. Шифрование и дешифрование имеют следующий вид для некоторого незашифрованного блока М и зашифрованного блока С:

С = М_е (mod n)

M = C_d (mod n) = (M_e)_d (mod n) = M_ed (mod n)

Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, получатель знает значение d. Таким образом, открытый ключ есть KU = {e, n} и закрытый ключ есть KR = {d, n}. При этом должны выполняться следующие условия:

Возможность найти значения е, d и n такие, что M_ed = M mod n для всех М < n.

Относительная легкость вычисления М_е и С_d для всех значений М < n.

Невозможность определить d, зная е и n.

Определим функцию Эйлера следующим образом: Φ(n) - число положительных чисел, меньших n и взаимнопростых с n. Если p - простое, то Φ(р) = p-1.

Если p и q - простые, то Φ(p · q) = (p-1) · (q-1).

Теперь рассмотрим все элементы алгоритма RSA.

p, q - два простых целых числа	- открыто, вычисляемо.
n = p · q	- закрыто, вычисляемо.
d, gcd (Φ(n), d) = 1;	- открыто, выбираемо.
1 < d < Φ(n)
е d-1 mod Φ(n)	- закрыты, выбираемы.

Закрытый ключ состоит из {d, n}, открытый ключ состоит из {e, n}. Предположим, что пользователь А опубликовал свой открытый ключ, и что пользователь В хочет послать пользователю А сообщение М. Тогда В вычисляет С = М_е (mod n) и передает С. При получении этого зашифрованного текста пользователь А дешифрует вычислением М = С_d (mod n).

Суммируем алгоритм RSA:

Создание ключей производится следующим образом:

- Выбрать простые р и q

- Вычислить n = p · q

- Выбрать d: gcd (Φ(n), d) = 1; 1 < d < Φ(n)

- Вычислить е: е = d-1 mod Φ(n)

Открытый ключ KU = {e, n}

Закрытый ключ KR = {d, n}

Процедура шифрования:

Незашифрованный текст: М < n

Зашифрованный текст: С = Ме (mod n)

Дешифрование:

Зашифрованный текст: С

Незашифрованный текст: М = Сd (mod n)

Рассмотрим конкретный пример:

Выбрать два простых числа: р = 7, q = 17.

Вычислить n = p · q = 7 · 17 = 119.

Вычислить Φ(n) = (p - 1) · (q - 1) = 96.

Выбрать е так, чтобы е было взаимнопростым с Φ(n) = 96 и меньше, чем Φ(n): е = 5.

Определить d так, чтобы d · e 1 mod 96 и d < 96.

d = 77, так как 77 · 5 = 385 = 4 · 96 + 1.

Результирующие ключи открытый KU = {5, 119} и закрытый KR = {77, 119}.

Например, требуется зашифровать сообщение М = 19.

195 = 66 (mod 119); С = 66.

Для дешифрования вычисляется 6677 (mod 119) = 19.