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

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

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

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

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

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

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

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

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

Шаблон:Ordered list

Подпись

Шаблон:Ordered list

Проверка

Шаблон:Ordered list

Замечания

В некоторых реализациях алгоритма величина $U$ не используется. Вместо этого возможно ,в конечном итоге, умножить значение хеша на два числа a или b со свойствами $\left(\frac{a}{p}\right)=-\left(\frac{a}{q}\right)=-1$ и $\left(\frac{b}{q}\right)=-\left(\frac{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}modn$ но $x\ne \pm ymodn$, то это немедленно приводит к факторизации $n$, так как на $n$ делится $x^2-y^2=(x-y)(x+y)$ , но не делятся простые множители. Таким образом, вычисление $\gcd (x\pm y,n)$ приведет к нетривиальной факторизации $n$.

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

См. также

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

Литература

• Michele Elia, Davide Schipani, On the Rabin Signature, 2011 PDF
• Buchmann, Johannes. Einführung in die Kryptographie. Second Edition. Berlin: Springer, 2001. Шаблон:ISBN
• Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. Шаблон:ISBN
• 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.