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

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

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

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

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

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

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

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

Подпись

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

Проверка

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

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

Чтобы еще больше упростить алгоритм, необходимо менять сообщение ${\displaystyle 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 

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

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

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

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