Русская Википедия:Вероятностная схема подписи Рабина
Вероятностная схема подписи Рабина — метод цифровой подписи, первоначально предложенный Михаэлем О. Рабином в 1979 году[1]. Схема подписи Рабина была одной из первых предложенных схем цифровой подписи и является единственной, которая напрямую связывает сложность подделки подписи с проблемой целочисленной факторизации. Алгоритм подписи Рабина непригоден в случайной модели вычислений с оракулом, предполагающей, что проблема целочисленной факторизации неразрешима. Схема подписи Рабина также тесно связана с криптосистемой Рабина.
Оригинальный алгоритм
- Генерация ключа
- Выбираются простые числа <math>p</math>, <math>q</math> каждое приблизительно размера <math>k/2</math> бит и считается произведение <math>n = p \cdot q</math>.
- Далее выбирается случайное <math>b</math> из <math>\{1,\ldots,n\}</math>.
- Открытым ключом является пара <math>(n, b)</math>.
- Закрытым ключом соответственно <math>(p, q)</math>.
- Подпись
- Чтобы подписать сообщение <math>m</math>, подбирается случайное число <math>U</math> и вычисляется <math>m \cdot U \mod n</math>.
- Затем решается уравнение <math>x(x+b) \mod n = m \cdot U \mod n</math>.
- Если решения уравнения не существует, выбирается новое значение <math>U</math> и заново решаем уравнение.
- Подписью сообщения <math>m</math> будет пара <math>(U, x)</math>
- Проверка
- По данным сообщению <math>m</math> и подписи <math>(U,x)</math> верификатор <math>V</math> производит вычисления <math>x(x+b) mod n</math> и <math>m \cdot U \mod n</math> и затем проверяет, что они равны.
Оригинальный алгоритм не использует хеш-функции и считается ненадежным.[2]
Безопасный и упрощенный алгоритм
Безопасный и надежный алгоритм[3] основан на хеш-функции, устойчивой к коллизиям <math>H : \{0,1\}^* \rightarrow \{0,1\}^k</math>.
В большинстве представлений алгоритм упрощается путем выбора <math>
b = 0 </math>. Предполагается, что хеш-функция <math>H</math> с количеством выходных битов <math>k</math> является случайным оракулом и алгоритм работает следующим образом:
- Генерация ключа
- Шаблон:Ordered list
- Подпись
- Шаблон:Ordered list
- Проверка
- Шаблон:Ordered list
Замечания
В некоторых реализациях алгоритма величина <math>U</math> не используется. Вместо этого возможно ,в конечном итоге, умножить значение хеша на два числа a или b со свойствами <math>\left(\tfrac{a}{p}\right) = -\left(\tfrac{a}{q}\right) = -1</math> и <math>\left(\tfrac{b}{q}\right) = -\left(\tfrac{b}{p}\right) = -1</math>, где <math>(\cdot)</math> обозначает символ Лежандра. Тогда для любого <math>H</math> по модулю <math>n</math> только одно из четырех чисел <math>H, aH, bH, abH</math> будет квадратом по модулю <math>n</math>, и именно оно выбирается для цифровой подписи сообщения.
Чтобы еще больше упростить алгоритм, необходимо менять сообщение <math>m</math> до тех пор, пока подпись не пройдет проверку.
\\Функция смены сообщения для верификации подписи
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
Безопасность
Если хеш-функция <math>H</math> является случайным оракулом, то есть его выходные данные действительно случайны в <math>\mathbb{Z}/n\mathbb{Z}</math>, то подделка подписи для любого сообщения <math>m</math> так же сложна́, как вычисление квадратного корня случайного элемента из <math>\mathbb{Z}/n\mathbb{Z}</math>.
Чтобы доказать[4], что получение случайного квадратного корня так же сложно, как факторизация, необходимо отметить, что в большинстве случаев существует четыре различных квадратных корня, поскольку <math>n</math> имеет два квадратных корня по модулю <math>p</math> и два квадратных корня по модулю <math>q</math>, и каждая пара дает квадратный корень по модулю <math>n</math> по Китайской теореме об остатках. Некоторые из корней могут иметь одинаковое значение, но вероятность этого крайне мала.
Если возможно найти два разных квадратных корня <math>x</math>,<math>y</math> таких, что <math>x^2 = y^2 \mod n</math> но <math>x \ne \pm y \mod n</math>, то это немедленно приводит к факторизации <math>n</math>, так как на <math>n</math> делится <math>x^2 - y^2 = (x-y)(x+y)</math> , но не делятся простые множители. Таким образом, вычисление <math>\operatorname{gcd}(x\pm y,n)</math> приведет к нетривиальной факторизации <math>n</math>.
Теперь предполагается, что существует эффективный алгоритм для нахождения хотя бы одного квадратного корня. Затем выбирается случайное <math>r</math> по модулю <math>n</math> и возводится в квадрат <math>r^2 = R \mod n</math>,после, используя алгоритм, берется квадратный корень от <math>R</math> по модулю <math>n</math>, и получается новый корень <math>r^\prime</math>, который с вероятностью 50% <math>r \ne \pm r^\prime \mod n</math>.
См. также
Примечания
Литература
- 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.
Ссылки
Источник
Смарт Н. Криптография. — М.: Техносфера, 2005. С. 525.
