Криптосистемы Рабина является асимметричный криптографический метод, чья безопасность, как и RSA , связана с трудностью целочисленной факторизации . Однако криптосистема Рабина имеет то преимущество, что математически доказана ее вычислительная безопасность против атаки с выбранным открытым текстом до тех пор, пока злоумышленник не может эффективно разложить на множители целые числа, в то время как для RSA такое доказательство не известно. [1] : 145 Недостатком этого метода является то, что каждый выход функции Рабина может быть сгенерирован любым из четырех возможных входов; если каждый вывод представляет собой зашифрованный текст, требуется дополнительная сложность при расшифровке, чтобы определить, какой из четырех возможных входов был истинным открытым текстом.
История
Алгоритм был опубликован в январе 1979 года Майклом О. Рабином . [2] Криптосистема Рабина была первой асимметричной криптосистемой, в которой восстановление открытого текста из зашифрованного текста оказалось столь же сложным, как факторинг.
Алгоритм шифрования
Как и все асимметричные криптосистемы, система Рабина использует пару ключей: открытый ключ для шифрования и закрытый ключ для дешифрования. Открытый ключ публикуется для всех, а закрытый ключ остается известным только получателю сообщения.
Генерация ключей
Ключи для криптосистемы Рабина генерируются следующим образом:
- Выберите два больших различных простых числа а также такой, что а также .
- Вычислить .
потом открытый ключ и пара это закрытый ключ.
Шифрование
Сообщение можно зашифровать, предварительно преобразовав его в число используя обратимое отображение, затем вычисляя . Зашифрованный текст.
Расшифровка
Сообщение можно восстановить из зашифрованного текста извлекая квадратный корень по модулю следующим образом.
- Вычислить квадратный корень из по модулю а также используя эти формулы:
- Используйте расширенный алгоритм Евклида, чтобы найти а также такой, что .
- Воспользуйтесь китайской теоремой об остатках, чтобы найти четыре квадратных корня из по модулю :
Одно из этих четырех значений - исходный открытый текст. , хотя какой из четырех является правильным, невозможно определить без дополнительной информации.
Вычисление квадратных корней
Мы можем показать, что формулы на шаге 1 выше фактически дают квадратные корни из следующим образом. Для первой формулы мы хотим доказать, что. С показатель степени целое число. Доказательство тривиально, если, поэтому мы можем считать, что не делит . Обратите внимание, что подразумевает, что , поэтому c - квадратичный вычет по модулю. потом
Последний шаг оправдан критерием Эйлера .
Пример
В качестве примера возьмем а также , тогда . Братькак наш открытый текст. Таким образом, зашифрованный текст.
Расшифровка происходит следующим образом:
- Вычислить а также .
- Используйте расширенный алгоритм Евклида для вычисления а также . Мы можем подтвердить, что.
- Вычислите четырех кандидатов в виде открытого текста:
и мы видим, что желаемый открытый текст. Обратите внимание, что все четыре кандидата являются квадратными корнями из 15 по модулю 77. То есть для каждого кандидата, так что каждый шифрует то же значение, 15.
Алгоритм цифровой подписи
Криптосистема Рабина может использоваться для создания и проверки цифровых подписей . Для создания подписи требуется закрытый ключ. Для проверки подписи требуется открытый ключ.
Подписание
Сообщение можно подписать закрытым ключом следующим образом.
- Сгенерировать случайное значение .
- Используйте криптографическую хеш-функцию вычислить , где черта обозначает конкатенацию. должно быть целым числом меньше, чем .
- Удовольствие как значение, зашифрованное Рабином, и попытаться расшифровать его, используя закрытый ключ . Это даст четыре обычных результата:.
- Можно было ожидать, что шифрование каждого произвел бы . Однако это будет верно только в том случае, еслиоказывается квадратичным вычетом по модулю а также . Чтобы определить, так ли это, зашифруйте первый результат дешифрования.. Если он не шифруется на, повторите этот алгоритм с новым случайным . Ожидаемое количество раз, которое необходимо повторить этот алгоритм, прежде чем найти подходящий равно 4.
- Найдя который шифрует , подпись .
Проверка подписи
Подпись для сообщения можно проверить с помощью открытого ключа следующим образом.
- Вычислить .
- Зашифровать используя открытый ключ .
- Подпись действительна тогда и только тогда, когда шифрование равно .
Оценка алгоритма
Эффективность
Расшифровка дает три ложных результата в дополнение к правильному, поэтому необходимо угадать правильный результат. Это главный недостаток криптосистемы Рабина и один из факторов, не позволивших ей найти широкое практическое применение.
Если открытый текст предназначен для представления текстового сообщения, угадать несложно; однако, если открытый текст предназначен для представления числового значения, эта проблема становится проблемой, которую необходимо решить с помощью какой-либо схемы устранения неоднозначности. Для устранения этой проблемы можно выбрать открытые тексты со специальной структурой или добавить отступы . Способ устранения неоднозначности инверсии был предложен Блюмом и Уильямсом: два используемых простых числа ограничиваются простыми числами, конгруэнтными 3 по модулю 4, а область возведения в квадрат ограничивается набором квадратичных вычетов. Эти ограничения превращают функцию возведения в квадрат в перестановку лазейки , устраняя двусмысленность. [3]
Эффективность
Для шифрования необходимо вычислить квадрат по модулю n . Это более эффективно, чем RSA , который требует вычисления хотя бы куба.
Для дешифрования применяется китайская теорема об остатках , а также два модульных возведения в степень . Здесь эффективность сопоставима с RSA.
Устранение неоднозначности приводит к дополнительным вычислительным затратам, и это то, что не позволяет криптосистеме Рабина найти широкое практическое применение. [ необходима цитата ]
Безопасность
Было доказано, что любой алгоритм, который расшифровывает зашифрованное Рабином значение, может быть использован для факторизации модуля . Таким образом, расшифровка Рабина не менее сложна, чем проблема целочисленной факторизации, что не было доказано для RSA. Обычно считается, что не существует алгоритма полиномиального времени для факторизации, что означает, что не существует эффективного алгоритма для дешифрования зашифрованного Рабином значения без закрытого ключа..
Криптосистема Рабина не обеспечивает неотличимости от выбранных атак с открытым текстом, поскольку процесс шифрования является детерминированным. Злоумышленник, учитывая зашифрованный текст и сообщение кандидата, может легко определить, кодирует ли зашифрованный текст сообщение кандидата (просто проверив, дает ли шифрование сообщения кандидата данный зашифрованный текст).
Криптосистема Рабина не защищена от выбранной атаки зашифрованного текста (даже когда сообщения с вызовом выбираются равномерно случайным образом из пространства сообщений). [1] : 150 За счет добавления избыточности, например, повторения последних 64 бит, система может быть создана для создания единого корня. Это предотвращает эту конкретную атаку с выбранным зашифрованным текстом, поскольку алгоритм дешифрования создает только корень, который злоумышленник уже знает. Если применить этот метод, доказательство эквивалентности с проблемой факторизации не удастся, поэтому с 2004 года неясно, является ли этот вариант безопасным. Справочник по Applied Cryptography Менезесом, Oorschot и Ванстоун считает эту эквивалентность вероятно, однако, до тех пор , как нахождение корней остается в два этапа (1. Корни а также и 2. применение китайской теоремы об остатках).
Смотрите также
Заметки
- ^ a b Стинсон, Дуглас (1995). Криптография: теория и практика . CRC Press LLC.
- ^ Рабин, Майкл (январь 1979). «Оцифрованные подписи и функции открытого ключа, как трудноразрешимые, как факторизация» (PDF) . Лаборатория компьютерных наук Массачусетского технологического института.
- ^ Шафи Гольдвассер и Михир Белларе «Лекции по криптографии» . Летний курс по криптографии, Массачусетский технологический институт, 1996-2001 гг.
Рекомендации
- Бухманн, Йоханнес. 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, август 1999.
- Р. Кумандури и С. Ромеро, Теория чисел с компьютерными приложениями, Alg 9.2.9, Прентис Холл, 1997. Вероятностный коэффициент для квадратного корня из квадратичного вычета по простому модулю.