Алгоритм подписи Рабина

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

, но криптосистема RSA играет заметную роль на заре криптографии с открытым ключом, и алгоритм подписи Рабина не рассматривается. в большинстве вводных курсов по криптографии.

• 1 Уравнения
• 2 Исходный алгоритм - небезопасен без хэш-функции
• 3 Безопасный и упрощенный алгоритм
  • 3.1 Замечания
• 4 Безопасность
• 5 Ссылки
• 6 Внешние ссылки

Если H - устойчивая к коллизиям хеш-функция, m сообщение для подписи и

$H\; (m)\; p\; -\; 1\; 2\; mod\; p\; =\; 1\; \{\backslash \; displaystyle\; H\; (\; m)\; ^\; \{\backslash \; frac\; \{p-1\}\; \{2\}\}\; \{\backslash \; bmod\; \{p\}\}\; =\; 1\}$и

$H\; (m)\; q\; -\; 1\; 2\; mod\; q\; =\; 1\; \{\backslash \; displaystyle\; H\; (m)\; ^\; \{\backslash \; frac\; \{q-1\}\; \{2\}\}\; \{\backslash \; bmod\; \{q\}\}\; =\; 1\}$

сигнатура S задается уравнением

$S\; =\; ((pq\; -\; 2\; H\; (\; м)\; q\; +\; 1\; 4\; модуль\; q)\; п\; +\; (qp\; -\; 2\; ЧАС\; (м)\; п\; +\; 1\; 4\; модуль\; p)\; q)\; модуль\; (p\; \cdot \; q)\; \{\backslash \; displaystyle\; S\; =\; \backslash \; left\; (\backslash \; left\; (p\; ^\; \{q-\; 2\}\; H\; (m)\; ^\; \{\backslash \; frac\; \{q\; +\; 1\}\; \{4\}\}\; \{\backslash \; bmod\; \{q\}\}\; \backslash \; right)\; p\; +\; \backslash \; left\; (q\; ^\; \{p-2\}\; H\; (m)\; ^\; \{\backslash \; frac\; \{p\; +1\}\; \{4\}\}\; \{\backslash \; bmod\; \{p\}\}\; \backslash \; right)\; q\; \backslash \; right)\; \{\backslash \; bmod\; \{(\}\}\; p\; \backslash \; cdot\; q)\}$.

Каждый может проверить

$H\; (m)\; =\; S\; 2\; mod\; (p\; \cdot \; q)\; \{\backslash \; displaystyle\; H\; (m)\; =\; S\; ^\; \{2\}\; \{\backslash \; bmod\; \{(\}\}\; p\; \backslash \; cdot\; q)\}$,

, если значение $n\; =\; p\; \cdot \; q\; \{\backslash \; displaystyle\; n\; =\; p\; \backslash \; cdot\; q\}$является общедоступным.

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

• • Если решения нет, S выбирает новую площадку U и пытается снова.

• • Подпись на m - это пара (U, x)
• Проверка
  • Имеется сообщение m и подпись (U, x), проверяющий V вычисляет x (x + b) mod n и $m\; \cdot \; U\; mod\; n\; \{\backslash \; displaystyle\; m\; \backslash \; cdot\; U\; \backslash \; mod\; n\}$и проверяет, что они равны.

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

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

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

1. подписывающая сторона S выбирает простые числа p, q, каждое размером примерно k / 2 бита, и p, q mod 4 равно 3. Он вычисляет произведение $n\; =\; p\; \cdot \; q\; \{\backslash \; displaystyle\; n\; =\; p\; \backslash \; cdot\; q\}$.
2. Открытый ключ - n.
3. закрытый ключ - (p, q).

Подпись

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

Проверка

1. Учитывая сообщение m и подпись (U, x), проверяющий V вычисляет x mod n и H (m, U) и проверяет, что они равны.

Примечания

В некоторых случаях случайная набивка U исключается. Вместо этого мы можем в конечном итоге умножить хеш-значение на два числа a или b со свойствами $(ap)\; =\; -\; (aq)\; =\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; tfrac\; \{a\}\; \{p\}\}\; \backslash \; right)\; =\; -\; \backslash \; left\; (\{\backslash \; tfrac\; \{a\}\; \{q\}\}\; \backslash \; right)\; =\; -\; 1\}$и $(bq)\; =\; -\; (bp)\; =\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; left\; (\{\; \backslash \; tfrac\; \{b\}\; \{q\}\}\; \backslash \; right)\; =\; -\; \backslash \; left\; (\{\backslash \; tfrac\; \{b\}\; \{p\}\}\; \backslash \; right)\; =\; -\; 1\}$, где $(\cdot )\; \{\backslash \; displaystyle\; (\backslash \; cdot)\}$обозначает легендарный символ . Тогда для любого H по модулю n ровно одно из четырех чисел $H,\; a\; H,\; b\; H,\; ab\; H\; \{\backslash \; displaystyle\; 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 ("Записать расширенное сообщение в файл m.txt") f = open ('m.txt', 'w') f.write (m) f.close () break m = m + '' return sig

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

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

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

Теперь мы предполагаем, что существует эффективный алгоритм для нахождения хотя бы одного квадратного корня. Затем мы выбираем случайное r по модулю n и возводим его в квадрат $r\; 2\; =\; R\; mod\; n\; \{\backslash \; displaystyle\; r\; ^\; \{2\}\; =\; R\; \backslash \; mod\; n\}$, затем, используя алгоритм, берем один квадрат корень из R по модулю n, мы получим новый квадратный корень $r\; \prime \; \{\backslash \; displaystyle\; r\; ^\; \{\backslash \; prime\}\}$, и с вероятностью половинной $r\; \ne \; \pm \; r\; \prime \; mod\; n\; \{\; \backslash \; displaystyle\; r\; \backslash \; neq\; \backslash \; pm\; r\; ^\; \{\backslash \; prime\}\; \backslash \; mod\; n\}$.

• Мишель Элиа, Давиде Скипани, О подписи Рабина, 2011 PDF
• Бухманн, Йоханнес. Einführung in die Kryptographie. Второе издание. Берлин: Springer, 2001. ISBN 3-540-41283-2
• Менезес, Альфред; van Oorschot, Paul C.; и Ванстон, Скотт А. Справочник по прикладной криптографии. CRC Press, октябрь 1996 г. ISBN 0-8493-8523-7
• Рабин, Майкл. Оцифрованные подписи и функции открытого ключа как трудноразрешимые как факторизация (в формате PDF). Лаборатория компьютерных наук Массачусетского технологического института, январь 1979 г.
• Скотт Линдхерст, Анализ алгоритма Шанка для вычисления квадратных корней в конечных полях. in R Gupta and KS Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc Lec Notes, AMS, Aug 1999.
• Р. Кумандури и К. Ромеро, Теория чисел с компьютерными приложениями, Alg 9.2.9, Prentice Hall, 1997. Вероятность квадратного корня из квадратичного остатка по модулю простого числа.

• Программная реализация на языке программирования Python