Криптосистема Рабина
Зарегистрируйся в два клика и получи неограниченный доступ к материалам,а также
промокод
на новый заказ в Автор24. Это бесплатно.
Введение
Криптосистема Рабина-это метод криптосистемы с открытым ключом, безопасность которой, как и безопасность криптосистемы RSA, связана с трудностью факторизации целых чисел. Эта криптосистема была предложена в 1979 году Майклом Рабином как вариант криптосистемы RSA, для которой факторизация по модулю n имеет почти ту же вычислительную сложность, что и получение преобразования дешифрования из преобразования шифрования. Преимущество криптосистемы Рабина заключается в том, что было доказано, что расшифровка криптосистемы Рабина так же сложна, как и целочисленная факторизация, что в настоящее время не известно о проблеме RSA. Недостатком этого является то, что каждый выход алгоритма Рабина может быть сгенерирован четырьмя возможными входами. Таким образом, каждый вывод, представляющий собой блок зашифрованного текста, представляется в процедуре дешифрования на четыре возможных входа, которые представляют собой блок исходного открытого текста. Преимущества использования этого показателя 2 по сравнению с более крупными показателями заключаются в следующем: 1) меньшая вычислительная нагрузка и 2) решение (1) эквивалентно факторингу N . Недостатками являются: 1) вычисление на этапе шифрования информации, необходимой для идентификации правильного корня, и доставка этой информации на этап дешифрования, 2) уязвимость к атаке с использованием открытого текста [4, 19, 24, 15]. Несколько методов наивного выбора основывают выбор правильного корня на семантике сообщения, то есть они сохраняют корень, соответствующий сообщению, которое выглядит наиболее значимым, или корень, содержащий известную строку битов. Однако эти методы либо непригодны для использования, например, когда сообщение является секретным ключом, либо являются только вероятностными; в любом случае они влияют на эквивалентность между разрывом схемы Рабина и факторингом [4]. Тем не менее, для схем, использующих пары простых чисел, конгруэнтных 3 по модулю 4 (простые числа Блюма), Уильямс [27] предложил схему идентификации корня, основанную на вычислении символа Якоби, используя дополнительный параметр в открытом ключе и два дополнительных бита в зашифрованном сообщении. Криптосистема Рабина также может быть использована для создания подписи, используя обратное отображение: для того, чтобы подписать m, уравнение x2 = m MOD N решается, и любой из четырех корней, скажем S, может быть использован для формирования подписанного сообщения (m, S). Однако, если x2 = m MOD N не имеет решения, подпись не может быть сгенерирована напрямую; для преодоления этой проблемы используется случайная накладка U до тех пор, пока x2 = mU MOD N не будет разрешима, и подпись является тройкой (m, U, S) [21]. Верификатор сравнивает S 2 с m U MOD N и принимает подпись как действительную, когда эти два числа равны. Что касается применения электронной подписи, то углубленный анализ преимуществ/недостатков можно найти в [3].
Понятие криптосистемы Рабина
Криптосистема Рабина - это асимметричный криптографический метод, безопасность которого, связана со сложностью целочисленной факторизации. Криптосистема Рабина математически доказана как вычислительно безопасная против атаки с выбранным открытым текс...
Открыть главуИдентификация корня для любой пары простых чисел
b0 = xi MOD 2 и b1 = (xi MOD p) + (xi MOD q) MOD 2 , как следствие леммы 1. Бит b0 может быть вычислен на этапе шифрования, не зная ни p, ни q, в то время как b1 требует, чтобы в этом определении были известны p и q, и не может быть непосредственно в...
Открыть главуЗаключение
В принципе, схема Рабина очень эффективна, потому что для шифрования требуется только один квадрат; кроме того, она доказуемо так же безопасна, как и факторинг. Тем не менее, хорошо известно [4, 15], что он имеет некоторые недостатки, главным образом из-за сопоставления четыре к одному, которые могут препятствовать его использованию для сокрытия содержания сообщения, а именно: идентификация корня требует предоставления дополнительной информации, что может увеличить вычислительные затраты.; многие предлагаемые методы идентификации корней, основанные на семантике сообщения, имеют вероятностный характер и не могут быть использованы в некоторых обстоятельствах.; доставка двух битов вместе с зашифрованным сообщением подвергает процесс активным атакам путем злонамеренного изменения этих битов. Например, предположим, что злоумышленник A отправляет зашифрованное сообщение B с просьбой доставить расшифрованное сообщение третьей стороне C (другу A). Если в зашифрованном сообщении бит, идентифицирующий корень среди двух корней одной и той же четности, был намеренно изменен, A может получить корень из C, который в сочетании с исходным сообщением позволяет учитывать открытый ключ Рабина. Даже вариант II не застрахован от таких активных атак. В заключение следует отметить, что схема Рабина может страдать от некоторых препятствий при использовании для сокрытия сообщения, в то время как она кажется эффективной, когда применяется для создания электронной подписи или в качестве хэш-функции. Однако эти наблюдения не исключают практического использования схемы Рабина (как это на самом деле выгодно делается в некоторых стандартизированных протоколах), когда в протоколе публичного шифрования необходимо позаботиться о других свойствах, таких как целостность и подлинность, наряду с секретностью сообщений.
Список литературы
Т. М. Апостол, Введение в аналитическую теорию чисел, Спрингер, Нью-Йорк, 1976. Э. Бах, Дж. Шаллит, Алгоритмическая теория чисел, Массачусетский технологический институт, Кембридж, Массачусетс, 1996. Д. Дж. Бернштейн, Доказательство строгой безопасности подписей Рабина-Уильямса, EUROCRYPT 2008 (N. P. Smart, ред.), LNCS, vol. 4965, Springer, 2008, стр. 70-87. Бухман, Введение в криптографию, Спрингер, Нью-Йорк, 1999. Д. Г. Кантор, Х. Зассенхаус, Новый алгоритм факторинга многочленов над конечными полями, Математика. Сост., Том 36, № 154, апрель 1981, с. 587-592. Р. Дедекинд, Шрайбен ан ХеррнБорхардт, Дж.РейнАнгью. Математика, 83, 1877, с. 265-292. Г. Эйзенштейн, UbereinigeallgemeineEigenschaften der Gleichung, von welcher die Theilung der ganzenLemniscateabhangt, nebstAnwendungenderselben auf die Zahlentheorie, J. ReineAngew. Математика., 39 (1850), 224-274; 275-287. М. Элиа, Д. Схипани, О подписи Рабина, чтобы появиться в J. Дискретная математика. Sci. Cryptogr.. М. Элиа, Д. Схипани, Улучшения алгоритма факторизации Кантора-Зассенхауса, которые появятся в математике. Богем. D. M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, G. Segev, More Constructions of Lossy and Correlation-Secure Trapdoor Functions, PKC 2010, Springer LNCS 6056 (2010), стр. 279-295. Тейлор, Алгебраическая теория чисел, Кембриджский университет. Пресса, 1994. С. Гэлбрейт, Математика криптографии с открытым ключом, Кембриджский университет. Пресса, 2012. Э. Гроссвальд, Темы из теории чисел, Биркхаузер, Базель, 2009. Г. Х. Харди, Э. М. Райт, Введение в теорию чисел, Оксфорд, издательство "Кларендон Пресс", 1971. J. Хоффштейн, Дж. Пайпер, Дж. Х. Сильверман, Введение в математическую криптографию, Спрингер, Нью-Йорк, 2008. К. Ирландия, М. Розен, Классическое введение в современную теорию чисел, Спрингер, Нью-Йорк, 1998. Н. Кайблингер, Циклотомические кольца с простым евклидовым алгоритмом, JP J. Теория чисел алгебры, Приложение, 23, № 1, 2011, с. 6176. Ф. Леммермейер, Законы взаимности, Спрингер, Нью-Йорк, 2000. J. Menezes, P. C. vanOorschot, S. A. Vanstone, Справочник по прикладной криптографии, CRCPress, Бока-Ратон, 1997. Монико, М. Элиа, О представлении простых чисел в Q( 2) в виде сумм квадратов, JPANTA, vol. 8, Выпуск 1, июнь 2007, стр. 121-133. J. Pieprzyk, T. Hardjono, J. Sebberry, Основы компьютерной безопасности, Springer, Нью-Йорк, 2003. М. Рабин, Цифровая подпись так же трудноразрешима, как и факторизация, Технический отчет MIT/LCS/TR-212, Лаборатория компьютерных наук Массачусетского технологического института, январь 1978 года. Х. Радемахер, Э. Гроссвальд, Дедекинд, МАА, Нью-Йорк, 1972. Б. Шнайер, Прикладная криптография, Уайли, 1996. Т. Такаги, С. Найто, Расширение криптосистемы Рабина на поля Эйзенштейна и Гаусса, IEICE Trans. Основы, Том E80-A, № 4, апрель 1997 года. Дж.Герхард, Современная компьютерная алгебра, Кембриджский университет. Пресса, 1999. Модификация процедуры шифрования с открытым ключом RSA, IEEE Trans. на Информ. Т., IT-26(6), ноябрь 1980, с. 726-729.
