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