МЕНЮ

Каталог

ПРОТОКОЛ, ОБЕСПЕЧИВАЮЩИЙ ЗАШИФРОВАНИЕ СООБЩЕНИЙ, РАСШИФРОВАНИЕ КОТОРЫХ БУДЕТ ВОЗМОЖНО НЕ РАНЕЕ ЗАДАННОГО ВРЕМЕНИ (TIME-LAPSE CRYPTOGRAPHY) Протокол TLC

 

Постановка задачи

В некоторый момент времени Т Алиса хочет отправить Бобу зашифрованное сообщение m так, чтобы Боб смог расшифровать его не раньше установленного будущего момента времени Т+g, причем без дальнейшего участия Алисы.
Описание протокола

В некоторый момент времени $ T$ Алиса хочет отправить Бобу зашифрованное сообщение $ m$ так, чтобы Боб смог расшифровать его не раньше установленного будущего момента времени $ T+delta$, причем без дальнейшего участия Алисы.

Протокол осуществляется при помощи Сервиса (Time-Lapse Cryptography Service), состоящего из $ n$ участников (parties) $ P_1$, ..., $ P_n$. Каждый участник Сервиса $ P_i$ может быть предстален автономным компьютером (сервером), безошибочно и секретно выполняющим вычисления, предусмотренные протоколом, надежно хранящим все свои секретные данные, имеющим безопасный способ резервного копирования данных для аварийного восстановления. Все участники Сервиса могут приватно и секретно обмениваться информацией между собой, образуя сеть. Предполагается пороговое значение $ t$ такое, что самое большее $ t – 1$ участников могут нарушить протокол, и самое меньшее $ t$ участников являются надежными. Должно выполняться условие $ n geq 2t – 1$ ( $ t leq (n+1)/2$), например, если $ n = 3$, то $ t leq 2$.). Для дальнейшей эффективности, надежности и устойчивости к атакам, используется небольшая сеть $ М$ из $ K$ менеджеров, которые действуют как “команда управления” Сервисом. Эта управляющая команда должна создавать расписание открытых и соответствующих закрытых ключей, создаваемых Сервисом; вести внутреннюю доску объявлений для использования участниками Сервиса; вести открытую доску объявлений для пользователей Сервиса. Целостность этих досок объявлений достигается каждым менеджером, ведущим собственные копии этих двух досок объявлений. Участники и пользователи Сервиса будут смотреть на сообщения, размещенные на каждом из копий досок объявлений, и определять правильные значения большинством записей. Каждый участник Сервиса сопровождает каждое сообщение цифровой подписью. Действия всех участников протокола синхронизируются при помощи общедоступных и надежных часов таких, как предоставляемых NIST. Протокол предусматривает использование соглаcованных параметров алгоритма шифрования Эль-Гамаля: простое число $ p$, порождающий элемент $ g$ простого порядка $ q$. Эти параметры можно найти, например, в документах RFC 3526 и RFC 5114.

Алиса и Боб являются пользователями (клиентами) Сервиса.

1) Алиса запрашивает или выбирает у Сервиса подходящую ключевую структуру $ K_{ID}$. Ключевая структура $ K_{ID}=(ID, T_{ID} , delta_{ID} , PK_{ID})$ состоит из уникального идентификатора $ ID$, времени публикации $ T_{ID}$, промежутка времени $ delta_{ID}$ и открытого ключа $ PK_{ID}$.

2) Сервис может генерировать ключевые структуры на периодической основе; например, каждый день он может создавать ключи со сроком службы 1 неделю, или каждые 30 минут создавать ключи со сроком службы 2 часа. Такое расписание размещается менеджерами на открытой доске объявлений. Кроме того, Сервис может принимать запросы от пользователей генерировать новые ключи с заданным сроком службы; менеджеры принимают эти запросы и размещают их на открытой доске объявлений. Участники Сервиса создают ключи согласно протокола, подписывают их и опубликовывают подписанные ключевые структуры на открытой доске объявлений.

Генерация ключевых структур происходит следующим образом:

Каждый участник $ P_i$ должен сгенерировать случайное значение $ x_{i}$. Это значение представляет собой претендента от участника $ P_i$ на составляющую часть закрытого ключа. Получится, что закрытый ключ будет равен $ x = sum_{i in Q} x_{i} pmod q$. Затем каждый участник $ P_i$ должен вычислить $ h_{i} = g^{x_{i}} pmod p$ и опубликовать $ (h_{i}, SIGN_{i}(h_{i}))$ на внутренней доске объявлений. Это значение представляет собой претендента от участника$ P_i$ на составляющую часть открытого ключа. Получится, что открытый ключ будет равен$ h = prod_{i in Q} h_{i} pmod p$.

Каждый участник $ P_i$ должен сгенерировать случайный многочлен степени $ t-1$$ f_{i}(z)=x_{i}+a_{1i}z+a_{2i}z^2+...+a_{t-1i}z^{t-1}$ из $ F_{q}[z]$ (т.е. сгенерировать случайную последовательность $ t-1$ значений $ x_{i}$, $ a_{1i}$, $ a_{2i}$, ..., $ a_{t-1i}$). Составляющей частью секретного ключа является $ f_{i}(0)=x_{i}$. Каждый участник $ P_i$ должен вычислить доли секрета $ x_{ij}=f_{i}(j)$ ( $ f_{i}(j)=x_{i}+a_{1i}j+a_{2i}j^2+...+a_{t-1i}j^{t-1}$) и проверочные значения $ c_0 = h_i = g^{x_i} pmod p$, $ c_1 = g^{a_{1i}} pmod p$, ..., $ c_{t-1} = g^{a_{t-1i}} pmod p$. Затем каждый участник $ P_i$ отправляет всем участникам $ P_j$, $ j in [1, n]$$ (j, x_{ij}, SIGN_{i}(j, x_{ij}))$ и публикует на внутренней доске объявлений $ (c_{0}, SIGN_{i}(c_{0}))$$ (c_{t-1}, SIGN_{i}(c_{t-1}))$. Теперь каждый $ P_j$, $ j in [1, n]$ может проверить, что $ x_{ij}$правильная доля секрета, сравнивая $ g^{x_{ij}} equiv c_{0} c_{1}^{j} c_{2}^{j^2} ... c_{t-1}^{j^{t-1}} pmod p$. (*). Если равенство (*) не выполняется, то участник $ P_j$ выражает жалобу против $ P_i$. Если участник $ P_i$получает жалобу против себя, то он опубликовывает значение $ x_{ij}$, удовлетворяющее равенству (*). Каждый участник $ P_i$ отмечает дисквалифицированным каждого участника, который получил более $ k$ жалоб или ответил на жалобу значениями, не удовлетворяющими равенству (*). Каждый участник $ P_i$ создает множество $ Q$ всех не дисквалифицированных участников. Каждый участник $ P_j$, $ j in Q$, вычисляет$ h = prod_{i in Q} h_{i} pmod p$, формирует ключевую структуру$ K_{ID}=(ID, T_{ID} , delta_{ID} , PK_{ID}=h)$ и публикует $ (K_{ID}, SIGN_{j}(K_{ID}))$ на внутренней и открытой досках объявлений.

3) Алиса проверяет соответствие цифровых подписей $ SIGN_{i}(K_{ID})$ опубликованным ключевым структурам $ K_{ID}$ минимум для $ t$ участников и их идентичность.

4) Алиса генерирует случайное значение $ y$, вычисляет $ c_1 = g^{y} pmod p$ и$ c_2 = m cdot PK_{ID}^{y} pmod p$ и отправляет пару $ c= (c_{1}, c_{2})$ Бобу.

5) Боб получает пару $ c= (c_{1}, c_{2})$ и ожидает либо значение $ y$ от Алисы, либо наступления момента времени $ T_{ID} + delta_{ID}$.

6) При наступлении момента времени $ T_{ID} + delta_{ID}$ каждый участник $ P_i$ должен опубликовать свою составляющую часть закрытого ключа $ x = DK_{ID}$ на внутренней доске объявлений. Каждый участник проверяет, что у каждого $ P_i$ из $ Q$ опубликованная составляющая часть $ x_i$ удовлетворяет уравнению $ g^{x_i} equiv h_i pmod p$. Каждый участник $ P_j$ должен опубликовать $ x_{ij}$. Каждый участник $ P_j$ вычисляет сумму$ DK_{ID} = x = sum_{i in Q} x_{i} pmod q$ и публикует $ (ID, DK_{ID}, SIGN_{j}(ID, DK_{ID}))$ на открытой доске объявлений.

7) Если Алиса отправляет Бобу значение $ y$, то Боб расшифровывает сообщение $ m$ и без закрытого ключа, либо при наступлении момента времени $ T_{ID} + delta_{ID}$ Боб получает $ DK_{ID}$ от Сервиса и расшифровывает сообщение $ m$: $ m = c_{2} cdot c_{1}^{p-1-DK_{ID}} pmod p$.

 

Основные сведения

 
Ссылки
  • M.0. Rabin and C. Thorpe. Time-lapse cryptography. Technical report TR-22-06, Harvard University School of Engineering and Computer Science, 2006.