Вероятностная схема подписи Рабина

Вероятностная схема подписи Рабина — метод цифровой подписи, первоначально предложенный Михаэлем О. Рабином в 1979 году. Схема подписи Рабина была одной из первых предложенных схем цифровой подписи и является единственной, которая напрямую связывает сложность подделки подписи с проблемой целочисленной факторизации. Алгоритм подписи Рабина непригоден в случайной модели вычислений с оракулом, предполагающей, что проблема целочисленной факторизации неразрешима. Схема подписи Рабина также тесно связана с криптосистемой Рабина.

Оригинальный алгоритм

• Генерация ключа
  • Выбираются простые числа $p$, $q$ каждое приблизительно размера $k/2$ бит и считается произведение $n=p\cdot q$.
  • Далее выбирается случайное $b$ из $\{1,\ldots ,n\}$.
  • Открытым ключом является пара $(n,b)$.
  • Закрытым ключом соответственно $(p,q)$.
• Подпись
  • Чтобы подписать сообщение $m$, подбирается случайное число $U$ и вычисляется $m\cdot U\mod n$.
  • Затем решается уравнение $x(x+b)\mod n=m\cdot U\mod n$.
  • Если решения уравнения не существует, выбирается новое значение $U$ и заново решаем уравнение.
  • Подписью сообщения $m$ будет пара $(U,x)$
• Проверка
  • По данным сообщению $m$ и подписи $(U,x)$ верификатор $V$ производит вычисления $x(x+b)modn$ и $m\cdot U\mod n$ и затем проверяет, что они равны.

Оригинальный алгоритм не использует хеш-функции и считается ненадежным.

Безопасный и упрощенный алгоритм

Безопасный и надежный алгоритм основан на хеш-функции, устойчивой к коллизиям $H:\{0,1\}^{*}\rightarrow \{0,1\}^{k}$.

В большинстве представлений алгоритм упрощается путем выбора $b=0$. Предполагается, что хеш-функция $H$ с количеством выходных битов $k$ является случайным оракулом и алгоритм работает следующим образом:

Генерация ключа

1. Выбираются простые числа $p$, $q$ каждое приблизительно размером $k/2$ бит, и $p$, $q$ mod 4 равно 3. Далее вычисляется произведение $n=p\cdot q$.
2. Открытым ключом в этом случае является $n$.
3. Закрытым ключом будет пара $(p,q)$.

Подпись

1. Чтобы подписать сообщение $m$, подбирается случайное число $U$ и вычисляется $H(m,U)$.
2. Если $H(m,U)$ не является квадратом по модулю $n$, выбирается новое значение $U$.
3. После находится одно значение x, которое является решением уравнения $x^{2}=H(m,U)\mod n$.
4. Подписью сообщения $m$ будет пара $(U,x)$.

Проверка

1. По данным сообщению $m$ и подписи $(U,x)$ верификатор $V$ производит вычисления $x^{2}modn$ и $H(m,U)$ и затем проверяет, что они равны.

Замечания

В некоторых реализациях алгоритма величина $U$ не используется. Вместо этого возможно ,в конечном итоге, умножить значение хеша на два числа a или b со свойствами $\left({\tfrac {a}{p}}\right)=-\left({\tfrac {a}{q}}\right)=-1$ и $\left({\tfrac {b}{q}}\right)=-\left({\tfrac {b}{p}}\right)=-1$, где $(\cdot )$ обозначает символ Лежандра. Тогда для любого $H$ по модулю $n$ только одно из четырех чисел $H,aH,bH,abH$ будет квадратом по модулю $n$, и именно оно выбирается для цифровой подписи сообщения.

Чтобы еще больше упростить алгоритм, необходимо менять сообщение $m$ до тех пор, пока подпись не пройдет проверку.

\\Функция смены сообщения для верификации подписи
def root(m: str, p, q):
    while True:
        x = h(m)
        sig = pow(p, q-2, q) * p * pow(x, (q+1)/4, q)
        sig = (pow(q, p-2, p) * q * pow(x, (p+1)/4, p) + sig) % (nrabin)
        if (sig * sig) % nrabin == x:
            print("Write extended message to file m.txt")
            f = open('m.txt', 'w')
            f.write(m)
            f.close()
            break
        m = m + ' '
    return sig

Безопасность

Если хеш-функция $H$ является случайным оракулом, то есть его выходные данные действительно случайны в $\mathbb {Z} /n\mathbb {Z}$, то подделка подписи для любого сообщения $m$ так же сложна́, как вычисление квадратного корня случайного элемента из $\mathbb {Z} /n\mathbb {Z}$.

Чтобы доказать, что получение случайного квадратного корня так же сложно, как факторизация, необходимо отметить, что в большинстве случаев существует четыре различных квадратных корня, поскольку $n$ имеет два квадратных корня по модулю $p$ и два квадратных корня по модулю $q$, и каждая пара дает квадратный корень по модулю $n$ по Китайской теореме об остатках. Некоторые из корней могут иметь одинаковое значение, но вероятность этого крайне мала.

Если возможно найти два разных квадратных корня $x$,$y$ таких, что $x^{2}=y^{2}\mod n$ но $x\neq \pm y\mod n$, то это немедленно приводит к факторизации $n$, так как на $n$ делится $x^{2}-y^{2}=(x-y)(x+y)$ , но не делятся простые множители. Таким образом, вычисление $\operatorname {gcd} (x\pm y,n)$ приведет к нетривиальной факторизации $n$.

Теперь предполагается, что существует эффективный алгоритм для нахождения хотя бы одного квадратного корня. Затем выбирается случайное $r$ по модулю $n$ и возводится в квадрат $r^{2}=R\mod n$,после, используя алгоритм, берется квадратный корень от $R$ по модулю $n$, и получается новый корень $r^{\prime }$, который с вероятностью 50% $r\neq \pm r^{\prime }\mod n$.

См. также

• Криптосистема Рабина
• Электронная подпись
• Факторизация

Литература

• Michele Elia, Davide Schipani, On the Rabin Signature, 2011 PDF
• Buchmann, Johannes. Einführung in die Kryptographie. Second Edition. Berlin: Springer, 2001. ISBN 3-540-41283-2
• Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7
• Rabin, Michael. Digitalized Signatures and Public-Key Functions as Intractable as Factorization (in PDF). MIT Laboratory for Computer Science, January 1979.
• Scott Lindhurst, An analysis of Shank's algorithm for computing square roots in finite fields. in R Gupta and K S Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, Aug 1999.
• R Kumanduri and C Romero, Number Theory w/ Computer Applications, Alg 9.2.9, Prentice Hall, 1997. A probabilistic for square root of a quadratic residue modulo a prime.

Ссылки

• Оригинальная статья
• Rabin Digital Signature Algorithm

Источник

Смарт Н. Криптография. — М.: Техносфера, 2005. С. 525.