Вероятностная схема подписи Рабина (Fyjkxmukvmugx v]ybg hk;hnvn JgQnug)

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

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

Генерация ключа
- Выбираются простые числа $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$ и затем проверяет, что они равны.

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

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

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

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

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

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

Подпись

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

Проверка

По данным сообщению $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}$ .

Чтобы доказать^[4], что получение случайного квадратного корня так же сложно, как факторизация, необходимо отметить, что в большинстве случаев существует четыре различных квадратных корня, поскольку $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$ .

См. также

Примечания

↑ Digitalized Signatures and Public-Key Functions as Intractable as Factorization (недоступная ссылка)
↑ |Michele Elia, Davide Schipani, On the Rabin Signature c.1-3 (неопр.). Дата обращения: 13 декабря 2019. Архивировано 22 сентября 2019 года.
↑ |Michele Elia, Davide Schipani, On the Rabin Signature c.5-9 (неопр.). Дата обращения: 13 декабря 2019. Архивировано 22 сентября 2019 года.
↑ Digitalized Signatures and Public-Key Functions as Intractable as Factorization c.15-19 (недоступная ссылка)

Литература

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.

Ссылки

Источник

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

[1] Digitalized Signatures and Public-Key Functions as Intractable as Factorization (недоступная ссылка)

[2] |Michele Elia, Davide Schipani, On the Rabin Signature c.1-3 (неопр.). Дата обращения: 13 декабря 2019. Архивировано 22 сентября 2019 года.

[3] |Michele Elia, Davide Schipani, On the Rabin Signature c.5-9 (неопр.). Дата обращения: 13 декабря 2019. Архивировано 22 сентября 2019 года.

[4] Digitalized Signatures and Public-Key Functions as Intractable as Factorization c.15-19 (недоступная ссылка)

[1]

[2]

[3]

[4]