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

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

Оригинальный алгоритм 
Генерация ключа
Выбираются простые числа ,  каждое приблизительно размера  бит и считается произведение .
Далее выбирается случайное  из .
Открытым ключом является пара .
Закрытым ключом соответственно .
Подпись
Чтобы подписать сообщение , подбирается случайное число  и вычисляется .
Затем решается уравнение .
Если решения уравнения не существует, выбирается новое значение  и заново решаем уравнение.  
Подписью сообщения  будет пара 
Проверка
По данным сообщению  и подписи  верификатор  производит вычисления  и  и затем проверяет, что они равны.

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

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

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

Генерация ключа  
Подпись
Проверка

Замечания 
В некоторых реализациях алгоритма величина  не используется. Вместо этого возможно ,в конечном итоге, умножить значение хеша на два числа a или b со свойствами  и , где  обозначает символ Лежандра.  Тогда для любого  по модулю  только одно из четырех чисел  будет квадратом по модулю , и именно оно выбирается для цифровой подписи сообщения.

Чтобы еще больше упростить алгоритм, необходимо менять сообщение  до тех пор, пока подпись не пройдет проверку. 
\\Функция смены сообщения для верификации подписи
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

Безопасность 
Если хеш-функция  является случайным оракулом, то есть его выходные данные действительно случайны в  , то подделка подписи для любого сообщения  так же сложна́,
как вычисление квадратного корня случайного элемента из  .

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

Если возможно найти два разных квадратных корня , таких, что  но   , то это немедленно приводит к факторизации , так как на  делится  , но не делятся простые множители.  Таким образом, вычисление  приведет к нетривиальной факторизации .  

Теперь предполагается, что существует эффективный алгоритм для нахождения хотя бы одного квадратного корня. Затем выбирается случайное  по модулю  и возводится в квадрат ,после, используя алгоритм, берется квадратный корень от  по модулю , и получается новый корень , который с вероятностью 50%  .

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

Примечания

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

Электронная подпись
Криптография с открытым ключом