1.6.2. Схема цифровой подписи с опережающей безопасностью
Для этого вводится понятие эволюции ключа. Участник схемы цифровой подписи начинает свою работу в системе как обычно, ре-гистрируя открытый ключ РК и храня в тайне соответствующий ему секретный ключ SK0. Отрезок времени, в течение которого откры-тый ключ РК предполагается сделать действительным для санкцио-нированного использования в системе, делится на периоды, обозна-чаемые 1, 2, ..., Т. Открытый ключ остается всегда фиксированным, тогда как секретный ключ «эволюционирует» с течением времени. Так, в каждом из этих периодов участник системы генерирует под-пись, используя различные секретные ключи: SKi в 1-м периоде, SK2 во 2-м периоде и т. д. Секретный ключ i-ro периода вырабатывается как функция ключа (z-l)-ro периода, а именно с началом г-го периода участник схемы применяет к 5АГ,-. і однонаправленную функцию h, чтобы получить в результате SKj. Сразу после этого он удаляет SKiA. Теперь злоумышленник, атаковавший участника в течение i-ro пе-риода, сможет завладеть ключом SKi, но не ключами SKQ,...,SKi.u так как они уже были удалены. Более того, злоумышленник не сможет получить и прежние ключи из SK,, поскольку они получаются из предыдущих с помощью однонаправленной функции.
Подпись всегда включает в себя номер периода j, в течение которого она была сгенерирована, так что она рассматривается как пара {j, Q.
Алгоритм проверки подписи берет фиксированный откры-тый ключ РК, сообщение и подпись, подлежащую проверке, и про-веряет, что подпись является действительной в том смысле, что была сгенерирована легальным участником системы в период времени, указанный в подписи. Заметим, что, хотя секретный ключ уча-стника эволюционирует с течением времени, открытый ключ остается неизменным, так что и процесс проверки подписи всегда оди-наков. Также остаются постоянными и процессы управления открытыми ключами.Число периодов и длина каждого периода - параметры, выбор которых зависит от каждого конкретного случая. Например, мы мо-жем пожелать использовать схему цифровой подписи с одним и тем же открытым ключом в течение года, с ежедневными обновлениями секретного ключа. В таком случае Т— 365, а каждый период имеет длину в одни сутки.
Схемой цифровой подписи с эволюцией ключа KE-SIG = (KG, Upd, Sgn, Vf) называется совокупность четырех алгоритмов:
1. Алгоритм генерации ключей KG берет в качестве входного па-раметра безопасности число ke N, суммарное количество перио- 70 Запечников С. В. Криптографические протоколы и wc прішеиеиие
дов Т, в течение которых будет функционировать схема, а также, возможно, некоторые другие параметры (алгоритм является вероят-ностным), и возвращает базовый открытый ключ РК и соответствующий ему базовый секретный ключ SKQ)
Алгоритм обновления секретного ключа Upd берет в качестве входной величины секретный ключ подписи предыдущего периода SK;.i и возвращает секретный ключ подписи текущего периода SK-, (алгоритм обычно детерминированный).
Алгоритм подписи Sgn берет секретный ключ подписи текущего периода SKi и подписываемое сообщение М и возвращает под-пись М для периода у, что записывается следующим образом:
—SgnSK (М). Алгоритм может быть вероятностным, а
подпись всегда состоит из номера текущего периода j и тега С.
Алгоритм проверки подписи Vf берет открытый ключ РК, со-общение М и проверяемую подпись (j, ?), чтобы возвратить бит, ко-торый означает принятие подписи в случае равенства единице и от-клонение ее в случае равенства нулю, что записывается следующим
образом: b VfPK(M Этот алгоритм обычно является де
терминированным.
Пара (j,С) считается действительной подписью сообщения М
для периода j, если VfPK(MТребуется, чтобы подпись сообщения М, сгенерированная алгоритмом SgnSK^ (М), была дей-ствительной подписью М для периода j.
Предполагается, что секрет-ный ключ SKj для периода j є {1,2,... ,7і} уже содержит в себе величину j и суммарное количество периодов Т. Наконец, договоримся, что SKT+\ - пустая строка и что UpdSK возвращает SKT+\-В табл. 1.25 в качестве примера приведена схема цифровой подписи с опережающей безопасностью Bellare - Miner, полностью удовлетворяющая приведенному выше определению.
1. Базовые криптографические протоколы 71
Таблица 1.25. Схема цифровой подписи с опережающей
безопасностью Bellare - Miner
Алгоритм KG(k,l,T):
Выбрать два случайных числа p,q = 3(mod4) длиной к!2 бита, вычис-лить N = pq .
Для каждого / = 1,...,/ выбрать St <— -—Z*N и вычислить U^SF^ {ТОЙ N).
ВЫЧИСЛИТЬ SK0 Алгоритм Upd(SKj-l), где SKM =(N,TJ-l,S1J_}1...,Sl j_l) И 1< у <7 + 1: Если j = T+l, возвратить пустую строку. В противном случае: Для каждого і = 1,...,/вычислить SLJ Sfj^ (modN). ВЫЧИСЛИТЬ SKj Алгоритм Sgn"K {M )ы, где Выбрать Re R Z'N . Вычислить Y <- R (T+1'jy> (modN). Для всех j = 1,...,/ вычислить Cj H (j,Y,M). і Вычислить Z <^R-Y[S-;j (mod/V). i=i Возвратить 72 Запечников С. В. Криптографические протоколы и их применение Эта схема цифровой подписи может быть достаточно просто преобразована в схему аутентификации, сохраняющую свойство опережающей безопасности.