Алгоритм подписи Рабина
В криптографии алгоритм подписи Рабина — это метод цифровой подписи, первоначально предложенный Майклом О. Рабином в 1978 году. [1] [2] [3]
Алгоритм подписи Рабина был одной из первых предложенных схем цифровой подписи. Введя использование хеширования в качестве важного шага при подписании, это был первый проект, который соответствовал современному стандарту безопасности от подделки, экзистенциальной невозможности подделки при атаке по выбранному сообщению , при условии соответствующего масштабирования параметров.
Подписи Рабина напоминают подписи RSA с экспонентой ', но это приводит к качественным различиям, которые позволяют более эффективно реализовать [4] и гарантия безопасности относительно сложности факторизации целых чисел , [2] [3] [5] что не было доказано для RSA .Однако подписи Рабина сравнительно мало использовались или стандартизировались за пределами IEEE P1363. [6] по сравнению со схемами подписи RSA, такими как RSASSA-PKCS1-v1_5 и RSASSA-PSS .
Определение
[ редактировать ]Схема подписи Рабина параметризуется рандомизированной хеш-функцией. сообщения и -битная строка рандомизации .
- Открытый ключ
- Открытый ключ — это пара целых чисел с и странный.
- Подпись
- Подпись в сообщении это пара из -битовая строка и целое число такой, что
- Закрытый ключ
- Закрытый ключ для открытого ключа это секретная факторизация нечетных простых чисел из , выбранное равномерно и случайно из некоторого пространства больших простых чисел. Позволять , , и . Чтобы поставить подпись в сообщении , подписывающийся выбирает -битовая строка равномерно случайным образом и вычисляет . Если является квадратичным безвычетом по модулю , затем подписывающий выбрасывает и пытается еще раз. В противном случае подписывающая сторона вычисляет используя стандартный алгоритм вычисления квадратных корней по модулю простого числа — выбор делает это проще всего. Квадратные корни не уникальны, и разные варианты схемы подписи требуют разного выбора квадратного корня; [4] в любом случае подписывающая сторона должна гарантировать, что не будет раскрыто два разных корня для одного и того же хеша. . Затем подписывающая сторона использует китайскую теорему об остатках для решения системы. для . Подписавшийся наконец раскрывает .
Правильность процедуры подписания определяется оценкой модуль и с как построено. Например, в простом случае, когда , это просто квадратный корень из модуль . Количество испытаний для геометрически распределено с математическим ожиданием около 4, поскольку около 1/4 всех целых чисел представляют собой квадратичные вычеты по модулю .
Безопасность
[ редактировать ]Защита от любого злоумышленника, определяемая в общих чертах с помощью хэш-функции. (т.е. безопасность в модели случайного оракула ) следует из сложности факторизации :Любой такой злоумышленник с высокой вероятностью успеха в подделке может с почти такой же высокой вероятностью найти два различных квадратных корня. и случайного целого числа модуль .Если затем является нетривиальным фактором , с так но . [3] Формализация безопасности в современных условиях требует заполнения некоторых дополнительных деталей, таких как кодомен ; если мы установим стандартный размер для простых факторов, , то мы могли бы указать . [5]
Рандомизация хеш-функции была введена, чтобы позволить подписавшемуся найти квадратичный остаток, но рандомизированное хеширование для подписей позже стало актуальным само по себе для более строгих теорем безопасности. [3] и устойчивость к коллизионным атакам на фиксированные хэш-функции. [7] [8] [9]
Варианты
[ редактировать ]Количество в открытом ключе не добавляет безопасности, поскольку любой алгоритм решения сравнений для данный и может быть тривиально использован как подпрограмма в алгоритме для вычисления квадратных корней по модулю и наоборот, поэтому реализации могут безопасно устанавливать для простоты; был полностью исключен при лечении после первоначального предложения. [10] [3] [6] [4]
Схема подписи Рабина была позже изменена Уильямсом в 1980 году. [10] выбирать и и заменим квадратный корень с помощью измененного квадратного корня , с и , так что подпись вместо этого удовлетворяет что позволяет подписавшему создать подпись за одну попытку без ущерба для безопасности.Этот вариант известен как Рабин-Вильямс . [4] [6] Дальнейшие варианты позволяют найти компромисс между размером подписи и скоростью проверки, частичным восстановлением сообщений, сжатием подписи (до половины размера) и сжатием открытого ключа (до одной трети размера), при этом без ущерба для безопасности. [4]
Варианты без хэш-функции опубликованы в учебниках. [11] [12] приписывая Рабину показатель степени 2, но не использование хэш-функции.Эти варианты тривиально нарушены — например, подпись может быть подделано кем угодно как действительная подпись в сообщении если уравнение проверки подписи имеет вид вместо .
В оригинальной статье [2] хеш-функция было написано с обозначением , C для сжатия и использование сопоставления для обозначения конкатенации и как битовые строки:
По соглашению, когда вы хотите подписать данное сообщение, , [подписавший] добавляет в качестве суффикса слово согласованной длины .Выбор рандомизируется каждый раз, когда сообщение должно быть подписано.Подписавшаяся сторона теперь сжимает с помощью хеш-функции к слову , так что как двоичное число …
Это обозначение впоследствии привело к некоторой путанице среди некоторых авторов, которые игнорировали часть и неправильно поняли означает умножение, что приводит к неправильному пониманию тривиально нарушенной схемы подписи. [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) . Семинар по вычислительной безопасности. Центр математических исследований, Барселона, Испания.