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

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