Содержание

Введение

Асимметричное шифрование

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

  • Получатель генерирует пару ключей - открытый и закрытый

  • Получатель предоставляет отправителю открытый ключ (передача может производиться по незащищенному каналу)

  • Отправитель для шифрования сообщения использует некую функцию, параметром которой является открытый ключ

  • Получатель расшифровывает сообщение, используя закрытый ключ

Что обеспечивает надёжность такого подхода? 

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

  • Нахождение делителей числа, являющегося произведением двух больших простых чисел (алгоритм RSA)

  • Вычисление дискретного логарифма (например, схема Эль-Гамаля)

  • Вычисления на эллиптических кривых (например, подпись ГОСТ 34.10–2012)

Цифровые подписи

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

Как устроена подпись Ниберга-Руппеля

Подпись Ниберга-Руппеля основана на сложности дискретного логарифмирования и является примером схемы с восстановлением сообщения. На самом деле схема Ниберга-Руппеля - это скорее не конкретная реализация, а некий подход, преобразовывающий схему Эль-Гамаля в схему с восстановлением сообщения. При этом немного видоизменяются требования, накладываемые на используемые переменные. Есть множество вариаций этой подписи, рассмотрим одну конкретную.

Генерация подписи

  • p- большое простое число

  • q- большой делитель числа p-1

  • \mathbb{Z}_p- поле Галуа порядка p

  • m_0- сообщение из \mathbb{Z}_q

  • F- биективная, легко обратимая функция, m = F(m_0)" alt="m = F(m_0)

  • g- генератор \mathbb{Z}_p

  • x- случайное число из \mathbb{Z}_q- закрытый ключ

  • y \equiv g^x \pmod{p} - открытый ключ

  • k- случайное число из \mathbb{Z}_p- генерируется для каждого сообщения

  • r \equiv m g^{-k} \pmod{p}, \qquad r' \equiv r \pmod{q}

  • s \equiv k - xr' \pmod{q}

  • пара (r, s)- итоговая подпись

  • данные p, g, y, F, (r, s) - публичные, то есть доступны получателям

Проверка подписи и восстановление сообщения

  • Проверяется, что r \in \mathbb{Z}_p, \quad s \in \mathbb{Z}_p

  • Если это не выполнено, то подпись не принимается

  • Вычисляется: a \equiv g^sy^{r’}r \pmod{p}

  • Извлечение сообщения: m_0 = F^{-1}(a)

  • Если сообщение возможно извлечь - подпись принимается

Доказательство корректности

  • b \equiv g^sy^{r’} \equiv g^{s+r’x} \equiv g^{k+qw} \equiv g^k g^{\frac{p-1}{z}w} \equiv g^k (g^{p-1})^\frac{w}{z} \equiv g^k \pmod{p}

  • последний переход - по малой теореме Ферма g^{p-1} \equiv 1 \pmod{p}

  • w- число, такое что s + xr’ = k + wq, а z = \frac{p-1}{q}

  • a = br = g^k m g^{-k} = m, \qquad m_0 = F^{-1}(a) = F^{-1}(m)

Особенности и применение

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

F: \mathcal{M} \to \mathcal{D}, где \mathcal{M}- множество сообщений. При этом образ F(\mathcal{M})=\mathcal{S}

Таким образом, вероятность того, что случайный элемент из \mathcal{D} является элементом \mathcal{S}, мала. То есть \mathcal{D} гораздо шире множества образов сообщений.

Именно на этой особенности строится проверка подписи в схеме Ниберга-Руппеля. Подпись принимается, если существует прообраз. Такой подход позволяет избежать уязвимости цифровой подписи, которая называется экзистенциальная подделка (подделка существования, Existential forgery). Этой уязвимости, например, подвержена широко распространённая схема RSA.

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

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

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