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

В криптографии алгоритм подписи Рабина — это метод цифровой подписи, первоначально предложенный Майклом О. Рабином в 1978 году. ^[1]^[2]^[3]

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

Подписи Рабина напоминают подписи RSA с экспонентой $e=2$ ', но это приводит к качественным различиям, которые позволяют более эффективно реализовать ^[4] и гарантия безопасности относительно сложности факторизации целых чисел , ^[2]^[3]^[5] что не было доказано для RSA .Однако подписи Рабина сравнительно мало использовались или стандартизировались за пределами IEEE P1363. ^[6] по сравнению со схемами подписи RSA, такими как RSASSA-PKCS1-v1_5 и RSASSA-PSS .

Определение

Схема подписи Рабина параметризуется рандомизированной хеш-функцией. $H(m,u)$ сообщения $m$ и $k$ -битная строка рандомизации $u$ .

Открытый ключ: Открытый ключ — это пара целых чисел $(n,b)$ с $0\leq b<n$ и $n$ странный.
Подпись: Подпись в сообщении $m$ это пара $(u,x)$ из $k$ -битовая строка $u$ и целое число $x$ такой, что $x(x+b)\equiv H(m,u){\pmod {n}}.$
Закрытый ключ: Закрытый ключ для открытого ключа $(n,b)$ это секретная факторизация нечетных простых чисел $p\cdot q$ из $n$ , выбранное равномерно и случайно из некоторого пространства больших простых чисел. Позволять $d=(b/2){\bmod {n}}$ , $d_{p}=(b/2){\bmod {p}}$ , и $d_{q}=(b/2){\bmod {q}}$ . Чтобы поставить подпись в сообщении $m$ , подписывающийся выбирает $k$ -битовая строка $u$ равномерно случайным образом и вычисляет $c:=H(m,u)$ . Если $c+d^{2}$ является квадратичным безвычетом по модулю $n$ , затем подписывающий выбрасывает $u$ и пытается еще раз. В противном случае подписывающая сторона вычисляет ${\begin{aligned}x_{p}&:={\Bigl (}-d_{p}\pm {\sqrt {c+{d_{p}}^{2}}}{\Bigr )}{\bmod {p}}\\x_{q}&:={\Bigl (}-d_{q}\pm {\sqrt {c+{d_{q}}^{2}}}{\Bigr )}{\bmod {q}},\end{aligned}}$ используя стандартный алгоритм вычисления квадратных корней по модулю простого числа — выбор $p\equiv q\equiv 3{\pmod {4}}$ делает это проще всего. Квадратные корни не уникальны, и разные варианты схемы подписи требуют разного выбора квадратного корня; ^[4] в любом случае подписывающая сторона должна гарантировать, что не будет раскрыто два разных корня для одного и того же хеша. $c$ . Затем подписывающая сторона использует китайскую теорему об остатках для решения системы. ${\begin{aligned}x&\equiv x_{q}{\pmod {n}}\\x&\equiv x_{p}{\pmod {n}}\end{aligned}}$ для $x$ . Подписавшийся наконец раскрывает $(u,x)$ .

Правильность процедуры подписания определяется оценкой $x(x+b)-H(m,u)$ модуль $p$ и $q$ с $x$ как построено. Например, в простом случае, когда $b=0$ , $x$ это просто квадратный корень из $H(m,u)$ модуль $n$ . Количество испытаний для $u$ геометрически распределено с математическим ожиданием около 4, поскольку около 1/4 всех целых чисел представляют собой квадратичные вычеты по модулю $n$ .

Безопасность

Защита от любого злоумышленника, определяемая в общих чертах с помощью хэш-функции. $H$ (т.е. безопасность в модели случайного оракула ) следует из сложности факторизации $n$ :Любой такой злоумышленник с высокой вероятностью успеха в подделке может с почти такой же высокой вероятностью найти два различных квадратных корня. $x_{1}$ и $x_{2}$ случайного целого числа $c$ модуль $n$ .Если $x_{1}\pm x_{2}\not \equiv 0{\pmod {n}}$ затем $\gcd(x_{1}\pm x_{2},n)$ является нетривиальным фактором $n$ , с ${x_{1}}^{2}\equiv {x_{2}}^{2}\equiv c{\pmod {n}}$ так $n\mid {x_{1}}^{2}-{x_{2}}^{2}=(x_{1}+x_{2})(x_{1}-x_{2})$ но $n\nmid x_{1}\pm x_{2}$ . ^[3]Формализация безопасности в современных условиях требует заполнения некоторых дополнительных деталей, таких как кодомен $H$ ; если мы установим стандартный размер $K$ для простых факторов, $2^{K-1}<p<q<2^{K}$ , то мы могли бы указать $H\colon \{0,1\}^{*}\times \{0,1\}^{k}\to \{0,1\}^{K}$ . ^[5]

Рандомизация хеш-функции была введена, чтобы позволить подписавшемуся найти квадратичный остаток, но рандомизированное хеширование для подписей позже стало актуальным само по себе для более строгих теорем безопасности. ^[3] и устойчивость к коллизионным атакам на фиксированные хэш-функции. ^[7]^[8]^[9]

Варианты

Количество $b$ в открытом ключе не добавляет безопасности, поскольку любой алгоритм решения сравнений $x(x+b)\equiv c{\pmod {n}}$ для $x$ данный $b$ и $c$ может быть тривиально использован как подпрограмма в алгоритме для вычисления квадратных корней по модулю $n$ и наоборот, поэтому реализации могут безопасно устанавливать $b=0$ для простоты; $b$ был полностью исключен при лечении после первоначального предложения. ^[10]^[3]^[6]^[4]

Схема подписи Рабина была позже изменена Уильямсом в 1980 году. ^[10] выбирать $p\equiv 3{\pmod {8}}$ и $q\equiv 7{\pmod {8}}$ и заменим квадратный корень $x$ с помощью измененного квадратного корня $(e,f,x)$ , с $e=\pm 1$ и $f\in \{1,2\}$ , так что подпись вместо этого удовлетворяет $efx^{2}\equiv H(m,u){\pmod {n}},$ что позволяет подписавшему создать подпись за одну попытку без ущерба для безопасности.Этот вариант известен как Рабин-Вильямс . ^[4]^[6]Дальнейшие варианты позволяют найти компромисс между размером подписи и скоростью проверки, частичным восстановлением сообщений, сжатием подписи (до половины размера) и сжатием открытого ключа (до одной трети размера), при этом без ущерба для безопасности. ^[4]

Варианты без хэш-функции опубликованы в учебниках. ^[11]^[12] приписывая Рабину показатель степени 2, но не использование хэш-функции.Эти варианты тривиально нарушены — например, подпись $x=2$ может быть подделано кем угодно как действительная подпись в сообщении $m=4$ если уравнение проверки подписи имеет вид $x^{2}\equiv m{\pmod {n}}$ вместо $x^{2}\equiv H(m,u){\pmod {n}}$ .

В оригинальной статье ^[2] хеш-функция $H(m,u)$ было написано с обозначением $C(MU)$ , C для сжатия и использование сопоставления для обозначения конкатенации $M$ и $U$ как битовые строки:

По соглашению, когда вы хотите подписать данное сообщение, $M$ , [подписавший] $P$ добавляет в качестве суффикса слово $U$ согласованной длины $k$ .Выбор $U$ рандомизируется каждый раз, когда сообщение должно быть подписано.Подписавшаяся сторона теперь сжимает $M_{1}=MU$ с помощью хеш-функции к слову $C(M_{1})=c$ , так что как двоичное число $c\leq n$ …

Это обозначение впоследствии привело к некоторой путанице среди некоторых авторов, которые игнорировали $C$ часть и неправильно поняли $MU$ означает умножение, что приводит к неправильному пониманию тривиально нарушенной схемы подписи. ^[13]

Ссылки

^ Рабин, Майкл О. (1978). «Цифровые подписи». В Демилло, Ричард А .; Добкин, Дэвид П .; Джонс, Анита К .; Липтон, Ричард Дж. (ред.). Основы безопасных вычислений . Нью-Йорк: Академическая пресса. стр. 155–168. ISBN 0-12-210350-5 .
^ Jump up to: ^а ^б ^с Рабин, Майкл О. (январь 1979 г.). Цифровые подписи и функции открытого ключа, столь же неразрешимые, как и факторизация (PDF) (Технический отчет). Кембридж, Массачусетс, США: Лаборатория компьютерных наук Массачусетского технологического института. ТР-212.
^ Jump up to: ^а ^б ^с ^д ^и Белларе, Михир ; Рогауэй, Филипп (май 1996 г.). Маурер, Ули (ред.). Точная безопасность цифровых подписей — как подписывать с помощью RSA и Rabin . Достижения в криптологии – EUROCRYPT '96 . Конспекты лекций по информатике. Том. 1070. Сарагоса, Испания: Спрингер. стр. 399–416. дои : 10.1007/3-540-68339-9_34 . ISBN 978-3-540-61186-8 .
^ Jump up to: ^а ^б ^с ^д ^и Бернштейн, Дэниел Дж. (31 января 2008 г.). Подписи RSA и подписи Рабина-Вильямса: современное состояние (Отчет). (дополнительная информация на https://cr.yp.to/sigs.html )
^ Jump up to: ^а ^б Бернштейн, Дэниел Дж. (апрель 2008 г.). Смарт, Найджел (ред.). Доказательство строгой защиты подписей Рабина-Вильямса . Достижения в криптологии – EUROCRYPT 2008 . Конспекты лекций по информатике. Том. 4965. Стамбул, Турция: Springer. стр. 70–87. дои : 10.1007/978-3-540-78967-3_5 . ISBN 978-3-540-78966-6 .
^ Jump up to: ^а ^б ^с Стандартные спецификации IEEE для криптографии с открытым ключом . Стандарт IEEE 1363-2000. Институт инженеров электротехники и электроники. 25 августа 2000 г. doi : 10.1109/IEESTD.2000.92292 . ISBN 0-7381-1956-3 .
^ Белларе, Михир ; Рогауэй, Филипп (август 1998 г.). Отправка в IEEE P1393 — PSS: Доказуемо безопасный метод кодирования цифровых подписей (PDF) (Отчет). Архивировано из оригинала (PDF) 13 июля 2004 г.
^ Халеви, Шай ; Кравчик, Хьюго (август 2006 г.). Дворк, Синтия (ред.). Укрепление цифровых подписей посредством рандомизированного хеширования (PDF) . Достижения в криптологии – КРИПТО 2006 . Конспекты лекций по информатике. Том. 4117. Санта-Барбара, Калифорния, США: Спрингер. стр. 41–59. дои : 10.1007/11818175_3 .
^ Данг, Куинь (февраль 2009 г.). Рандомизированное хеширование цифровых подписей (отчет). Специальное издание NIST. Том. 800–106. Министерство торговли США, Национальный институт стандартов и технологий. дои : 10.6028/NIST.SP.800-106 .
^ Jump up to: ^а ^б Уильямс, Хью К. «Модификация процедуры шифрования с открытым ключом RSA» . Транзакции IEEE по теории информации . 26 (6): 726–729. дои : 10.1109/TIT.1980.1056264 . ISSN 0018-9448 .
^ Менезес, Альфред Дж .; ван Оршот, Пол С .; Ванстон, Скотт А. (октябрь 1996 г.). «§11.3.4: Схема подписи с открытым ключом Рабина». Справочник по прикладной криптографии (PDF) . ЦРК Пресс. стр. 438–442. ISBN 0-8493-8523-7 .
^ Гэлбрейт, Стивен Д. (2012). «§24.2: Учебник по криптосистеме Рабина». Математика криптографии с открытым ключом . Издательство Кембриджского университета. стр. 491–494. ISBN 978-1-10701392-6 .
^ Элия, Мишель; Скипани, Дэвид (2011). О подписи Рабина (PDF) . Семинар по вычислительной безопасности. Центр математических исследований, Барселона, Испания.

Внешние ссылки

Подписи Рабина-Вильямса на cr.yp.to

[rabin1978digsigs-1] Рабин, Майкл О. (1978). «Цифровые подписи». В Демилло, Ричард А .; Добкин, Дэвид П .; Джонс, Анита К .; Липтон, Ричард Дж. (ред.). Основы безопасных вычислений . Нью-Йорк: Академическая пресса. стр. 155–168. ISBN 0-12-210350-5 .

[rabin1979lcs-tr-2] Jump up to: ^а ^б ^с Рабин, Майкл О. (январь 1979 г.). Цифровые подписи и функции открытого ключа, столь же неразрешимые, как и факторизация (PDF) (Технический отчет). Кембридж, Массачусетс, США: Лаборатория компьютерных наук Массачусетского технологического института. ТР-212.

[bellare-rogaway1996exactsigs-3] Jump up to: ^а ^б ^с ^д ^и Белларе, Михир ; Рогауэй, Филипп (май 1996 г.). Маурер, Ули (ред.). Точная безопасность цифровых подписей — как подписывать с помощью RSA и Rabin . Достижения в криптологии – EUROCRYPT '96 . Конспекты лекций по информатике. Том. 1070. Сарагоса, Испания: Спрингер. стр. 399–416. дои : 10.1007/3-540-68339-9_34 . ISBN 978-3-540-61186-8 .

[djb2008rwsota-4] Jump up to: ^а ^б ^с ^д ^и Бернштейн, Дэниел Дж. (31 января 2008 г.). Подписи RSA и подписи Рабина-Вильямса: современное состояние (Отчет). (дополнительная информация на https://cr.yp.to/sigs.html )

[djb2008rwtight-5] Jump up to: ^а ^б Бернштейн, Дэниел Дж. (апрель 2008 г.). Смарт, Найджел (ред.). Доказательство строгой защиты подписей Рабина-Вильямса . Достижения в криптологии – EUROCRYPT 2008 . Конспекты лекций по информатике. Том. 4965. Стамбул, Турция: Springer. стр. 70–87. дои : 10.1007/978-3-540-78967-3_5 . ISBN 978-3-540-78966-6 .

[ieee-1363-2000-6] Jump up to: ^а ^б ^с Стандартные спецификации IEEE для криптографии с открытым ключом . Стандарт IEEE 1363-2000. Институт инженеров электротехники и электроники. 25 августа 2000 г. doi : 10.1109/IEESTD.2000.92292 . ISBN 0-7381-1956-3 .

[bellare-rogaway1998pssproposal-7] Белларе, Михир ; Рогауэй, Филипп (август 1998 г.). Отправка в IEEE P1393 — PSS: Доказуемо безопасный метод кодирования цифровых подписей (PDF) (Отчет). Архивировано из оригинала (PDF) 13 июля 2004 г.

[halevi-krawczyk2007rhash-8] Халеви, Шай ; Кравчик, Хьюго (август 2006 г.). Дворк, Синтия (ред.). Укрепление цифровых подписей посредством рандомизированного хеширования (PDF) . Достижения в криптологии – КРИПТО 2006 . Конспекты лекций по информатике. Том. 4117. Санта-Барбара, Калифорния, США: Спрингер. стр. 41–59. дои : 10.1007/11818175_3 .

[nist-sp800-106-9] Данг, Куинь (февраль 2009 г.). Рандомизированное хеширование цифровых подписей (отчет). Специальное издание NIST. Том. 800–106. Министерство торговли США, Национальный институт стандартов и технологий. дои : 10.6028/NIST.SP.800-106 .

[williams1980rsamod-10] Jump up to: ^а ^б Уильямс, Хью К. «Модификация процедуры шифрования с открытым ключом RSA» . Транзакции IEEE по теории информации . 26 (6): 726–729. дои : 10.1109/TIT.1980.1056264 . ISSN 0018-9448 .

[hac-11] Менезес, Альфред Дж .; ван Оршот, Пол С .; Ванстон, Скотт А. (октябрь 1996 г.). «§11.3.4: Схема подписи с открытым ключом Рабина». Справочник по прикладной криптографии (PDF) . ЦРК Пресс. стр. 438–442. ISBN 0-8493-8523-7 .

[galbraith2012mathpkc-12] Гэлбрейт, Стивен Д. (2012). «§24.2: Учебник по криптосистеме Рабина». Математика криптографии с открытым ключом . Издательство Кембриджского университета. стр. 491–494. ISBN 978-1-10701392-6 .

[elia-schipani2011rabinsig-13] Элия, Мишель; Скипани, Дэвид (2011). О подписи Рабина (PDF) . Семинар по вычислительной безопасности. Центр математических исследований, Барселона, Испания.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]