Протокол Жиро

Протокол Жиро (фр. Marc Girault) — криптографический протокол, позволяющий двум сторонам получить общий секретный ключ, не используя явную сертификацию (схема распределения ключей с доверенным центром). Полученный ключ используется для шифрования дальнейшей обмениваемой информации с помощью симметричного шифрования.

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

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

В схеме Жиро пользователь может сам выбрать свой закрытый ключ. Надёжность схемы Жиро строится на стойкости криптосистемы RSA (сложности факторизации больших чисел и вычисления дискретного корня).

Описание алгоритма

Схемы распределения ключей Жиро с доверенным центром состоят из трёх этапов:

1) На первом этапе доверенный центр создаёт некоторый секрет, известный только ему: пара из закрытого и открытого ключей.

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

3) На третьем этапе, когда начинается протокол общения двух легальных участников, они предъявляют друг другу идентификаторы и/или дополнительную информацию от доверенного центра. Используя её, без дополнительного обращения к центру, они могут сгенерировать секретный сеансовый ключ для общения между собой.

Алгоритм

Пусть два абонента Алиса и Боб обмениваются сообщениями с целью неявно удостоверенного соглашения на публичный ключ. Пусть Трент — доверенный центр.

Подготовительный этап

• Доверенный центр (Трент, 𝑇):
  1. Выбирает общий модуль $n=pq$, где $p$ и $q$ — большие простые числа;
  2. Выбирает пару из закрытого и открытого ключей: $K_{T,public}:(e,n)$, $K_{T,private}:(d,n)$;
  3. Выбирает элемент $g$ поля $\mathbb {Z} _{n}^{*}$ максимального порядка;
  4. Публикует в общедоступном для всех участников месте параметры схемы $n$, $e$ и $g$
• Каждый из легальных участников (Алиса и Боб):
  1. Выбирает себе закрытый ключ $s_{i}$ и идентификатор $I_{i}$;
  2. Вычисляет и отправляет доверенному центру $v_{i}=g^{-s_{i}}\mod n$;
  3. Используя протокол аутентификации сторон участник доказывает доверенному центру 𝑇, что владеет закрытым ключом, не раскрывая его значение;
  4. Получает от доверенного центр свой открытый ключ: $P_{i}=(v_{i}-I_{i})^{d}=(g^{-s_{i}}-I_{i})^{d}\mod n$;

В результате для каждого участника, например, Алисы, которая владеет $P_{A}$, $I_{A}$, $s_{a}$ будет выполняться утверждение:

$P_{A}^{e}+I_{A}=g^{-s_{A}}\mod n$.

Схема Жиро

Протокол генерации сессионного ключа, называемый схемой Жиро, как и другие схемы, состоит из проходов обмена открытой информацией и вычисления ключа.

1. $Alice\rightarrow \{P_{A},I_{A}\}\rightarrow Bob$
2. Боб вычисляет $K_{BA}=(P_{A}^{e}+I_{A})^{s_{B}}\mod n$
3. $Bob\rightarrow \{P_{B},I_{B}\}\rightarrow Alice$
4. Алиса вычисляет $K_{AB}=(P_{B}^{e}+I_{B})^{s_{A}}\mod n$

В результате работы схемы стороны сгенерировали одинаковый общий сеансовый ключ.

$K_{AB}=(P_{A}^{e}+I_{A})^{s_{B}}=(g^{-s_{A}})^{-s_{B}}=g^{-s_{A}s_{B}}\mod n$

$K_{BA}=(P_{B}^{e}+I_{B})^{s_{A}}=(g^{-s_{B}})^{-s_{A}}=g^{-s_{A}s_{B}}\mod n$

$K=K_{AB}=K_{BA}=g^{-s_{A}s_{B}}\mod n$

Схема обеспечивает аутентификацию ключа, так как только легальные пользователи смогут вычислить корректное значение общего сессионного ключа.

Пример

Предположим $p=919,q=839$, соответственно $n=771041$ является модулем RSA для протокола Жиро.

Трент в свою очередь выбирает $(e,d)=(53,420929)$ как пару ключей RSA, и $a=77$ как элемент максимально допустимого порядка $384642=lcm(838,918)$мультипликативной группы $(Z_{n}^{*})$.

$I_{A}=19$ и $I_{B}=39$ идентификаторы.

Алиса выбирает $d_{A}=5$ и вычисляет $c_{A}=a^{d_{A}}=430247(mod(n))$.

Боб выбирает $d_{B}=89$ и вычисляет $c_{B}=a^{d_{B}}=264373(mod(n))$.

Потом $c_{A}$ и $c_{B}$ высылаются Тренту.

Трент вычисляет:

$p_{A}=(c_{A}-I_{A})^{d}=(430247-19)^{420929}=907(mod(n))$

$p_{B}=(c_{B}-I_{B})^{d}=(264373-39)^{420929}=682111(mod(n))$

$p_{A}$и $p_{B}$ высылаются Алисе и Бобу соответственно.

Алиса выбирает $e_{A}=15$ , вычисляет $s_{A}=a^{e_{A}}=77^{15}=297843(mod(n))$ и высылает $(I_{A},p_{A},s_{A})=(19,907,297843)$ Бобу.

Боб выбирает $e_{B}=83$ , вычисляет $s_{B}=a^{e_{B}}=77^{83}=312102(mod(n))$ и высылает $(I_{B},p_{B},s_{B})=(39,682111,312102)$ Алисе.

Алиса вычисляет $k=s_{B}^{d_{A}}(p_{B}^{e}+I_{B})^{e_{A}}=312102^{5}(682111^{53}+39)^{15}=517619(mod(n))$

Боб вычисляет $k=s_{A}^{d_{B}}(p_{A}^{e}+I_{A})^{e_{B}}=297843^{89}(907^{53}+19)^{83}=517619(mod(n))$

Таким образом они согласились на $k=517619(mod(n))$ через неявную проверку подлинности ключа.

Криптографическая стойкость

Защита от атаки подменой

Давайте рассмотрим, как самостоятельно удостоверенные ключи защищают от атаки подменой. Так как значения $(I_{A},p_{A},s_{A})$ не подтверждены Трентом, нет никакого способа для кого-либо правильно проверить их подлинность. Предположим, что эта информация подделана Мэллори, которая хочет претвориться Алисой.

Мэллори возьмет $I_{A}$ и поддельный ключ $s_{A}'$. Она может легко вычислить $c_{A}=p_{A}^{e}+I_{A}=a^{d_{A}}(mod(n))$.

Однако, нет способа вычислить $d_{A}$, который соответствует $c_{A}$, при условии, что задача дискретного логарифмирования неразрешима для $(Z_{n}^{*})$.

Следовательно, без $d_{A}$, формирования ключа не может быть реализовано Мэллори, которая выдаёт себя за Алису. Поэтому, Мэллори не может обмануть Трента, который должен быть уверен, что Алиса знает $d_{A}$. Такова причина, почему Алиса должна посылать $d_{A}$ Тренту. Он может легко высчитать $p_{A}$ из $c_{A}$ без знания $d_{A}$, но Алиса должна убедить его, что она знает $d_{A}$.

Проиллюстрируем ситуацию атаки на схему, если бы Трент без разбора выдавал публичный ключ $p_{A}$ людям, без проверки знают ли они значение $d_{A}$, соответствующее их $c_{A}$. Предположим Мэллори выбирает поддельное значение $d_{A}'$ и вычисляет соответствующее значение $c_{A}'=a^{d_{A}'}(mod(n))$

Здесь она вычисляет соответствующий открытый ключ $p_{A}'=(c_{A}'-I_{A})^{d}(mod(n))$

Мэллори вычисляет $c_{M}'=c_{A}'-I_{A}+I_{M}$ и дает $c_{M}'$ и $I_{M}'$ Тренту.

Трент выдает открытый ключ Мэллори.

$p_{M}'=(c_{M}'-I_{M})^{d}(mod(n))$

Используя факт о том, что $c_{M}'-I_{M}=c_{A}'-I_{A}(mod(n))$, получаем $p_{M}'=p_{A}'$

Через некоторое время, предположим, что Алиса и Боб захотят использовать схему, и Мэллори заменит информацию, пересылаемую от Алисы к Бобу, как показано на рисунке.

Тогда Боб будет вычислять ключ как

$k'=a^{e_{A}'*d_{B}+e_{B}*d_{A}'}(mod(n))$

Алиса как

$k=a^{e_{A}*d_{B}+e_{B}*d_{A}}(mod(n))$

Мэллори может вычислить $k'=s_{B}^{d_{A}'}(p_{B}^{e}+I_{B})^{e_{A}'}(mod(n))$

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

Защита от атаки повтором

Теперь давайте рассмотрим, как данный протокол защищён от атаки повтором. Предположим, что Мелори перехватила сообщение Алисы $(I_{A},c_{A},d_{A})$ и через некоторое время пытается переслать его Тренту. Трент проверит параметры сообщения и по временному идентификатору $I_{A}$ поймёт, что сообщение передано повторно, затем завершит сеанс. Таким образом, Меллори не удастся обмануть Трента.

Рассмотрим ситуацию атаки, если бы Трент не проверял временной идентификатор $I_{A}$. В таком случае Трент принимает сообщение Мелори $(I_{A},c_{A},d_{A})$, полностью идентичное сообщению Алисы. Трент, действуя по алгоритму, высылает Меллори и Бобу открытые ключи $p_{A}$, $p_{B}$. Таким образом, Меллори и Боб обменялись ключами, и Меллори сможет расшифровать сообщение Боба Алисе.

Протокол Аунтентификации Жиро

В протоколе Жиро, есть необходимость в доказательстве того, что участник знает закрытый ключ, при этом не раскрывая его значение. Для этого используется протокол с нулевым разглашением, который связан с протоколом Окамото и Охта.

Протокол аутентификации сторон в общем случае выглядит следующим образом:

1. Алиса Выбирает случайное $R_{A}$ и $Alice\rightarrow \{I_{A},P_{A},t=g^{R_{A}}\mod n\}\rightarrow Bob$
2. Боб Выбирает случайное $R_{B}$ и $Bob\rightarrow \{R_{B}\}\rightarrow Alice$
3. $Alice\rightarrow \{y=R_{A}+s_{A}\times R_{B}\mod n\}\rightarrow Bob$
4. Боб вычисляет $v_{A}=P_{A}^{e}+I_{A}\mod n$
5. Боб проверяет, что $t=g^{y}v_{A}^{R_{B}}\mod n$

Может быть доказано, что:

• Алиса будет принята Бобом, с вероятностью почти 100 %
• Самозванец, который не знает закрытый ключ, будет определён с вероятностью $1-2^{-30}$
• Протокол с трудом раскрывает что-либо о закрытом ключе, что подтверждает нулевое разглашение

Конечно, Боб все ещё может вычислять «ложные» ключи, связанные с Алисой, но существование двух или более действительных открытых ключей само по себе является доказательством нарушения.

Особенности схемы Жиро

Самостоятельно удостоверяющиеся открытые ключи в схеме Жиро обладают преимуществом личностной схемы Шамира: они не нуждаются в проверке дополнительного сертификата ключа, выданного его владельцу доверенным посредником. Она выполняется неявно с проверкой криптографических способностей владельца ключа. Однако проверяющая сторона должна знать, кроме идентификатора пользователя, его открытый ключ. При этом возможность определить этот ключ по идентификатору исключена. Таким образом, верификатор должен знать открытый ключ владельца до его использования. В итоге, в протоколе возникает дополнительный этап, который нагружает канал связи.

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

Литература

• Richard A. Mollin. RSA and Public-Key Cryptography
• Colin Boyd,Anish Mathuria. Protocols for Authentication and Key Establishment
• Douglas R. Stinson. Cryptography: Theory and Practice, Third Edition
• M. Girault. Self-certified public keys
• Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6
• Владимиров С. М. и др. Учебное пособие по защите информации кафедры радиотехники и систем управления МФТИ. — 6 ноября 2021г