Ранцевая криптосистема Шора-Ривеста была предложена в 1985 году (Chor, 1985; Chor and Rivest, 1988). В настоящее время она является единственной известной схемой шифрования, основанной на задаче о ранце, которая не использует модульного умножения для маскировки простой задачи о ранце На данный момент создано множество рюкзачных криптосистем, например ранцевая криптосистема Меркла — Хеллмана. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными, примечательным исключением является схема Шор-Ривеста. Криптосистема Шора-Ривеста является одной из немногих не взломанных систем.
Описание алгоритма Пусть пользователь B хочет отправить зашифрованное сообщение A. Для этого:
Для генерации открытого и закрытого ключей нужно: Выбрать конечное поле характеристики , где , , и для которого возможно эффективно решать задачу дискретного логарифмирования (см. Особенности криптосистемы 3) Выбрать случайный монотонный неприводимый многочлен степени над . Элементы будут представлены как многочлены от степени меньше , причем умножение можно выполняться по модулю . Выбрать случайный примитивный многочлен поля . Вычислить дискретный логарифм элемента поля . Выбрать случайную перестановку на множестве целых чисел Выбрать случайное целое число , Вычислить , Открытым ключом является ; закрытым ключом является
Для генерации случайного мононического неприводимого многочлена можно использовать следующий алгоритм:
ВХОД: простое и положительное целое число .
ВЫХОД: монотонный неприводимый многочлен степени в .
Полученный многочлен будет неприводимым, ввиду следующей теоремы: Случайно выбрать целые числа между и с . Представить многочлен в виде" Выбрать Для от до сделать следующие действия: Вычислить . (Заметить, что является многочленом от степени меньше ) Вычислить Если вернуть «приводимый». Если приводимый — повторить шаги алгоритма. Иначе вернуть Неприводимый многочлен степени является примитивным многочленом тогда и только тогда, когда делит для и для не меньшего положительного целого .
Для генерации случайного мононического примитивного многочлена можно использовать следующий алгоритм:
ВХОД: простое , целое число ≥ 1 и различные простые множители из .
ВЫХОД: монотонный примитивный многочлен степени в . Генерировать случайный монотонный неприводимый многочлен над . Для от до сделать следующие действия: Вычислить Если вернуть «не примитивный». Если примитивный — повторить шаги алгоритма. Иначе вернуть
Шифрование Для шифрования с открытым ключом нужно сделать следующее: Получить открытый ключ Представить сообщение как двоичную строку длины , где является биномиальным коэффициентом Рассмотреть как двоичное представление целого числа. Преобразовать это целое число в двоичный вектор длины , имеющий ровно единиц следующим образом: Выбрать Для от до выполнить следующие действия: Если то выбрать , , . В противном случае выбрать . (Примечание: для ; для ) Вычислить Отправить зашифрованный текст в
Дешифрование Для дешифрования с открытым ключом нужно сделать следующее: Вычислить Вычислить Вычислить , монотонный многочлен степени над Разложить на произведение линейных множителей над : , где (см. Особенности криптосистемы 5) Вычислить двоичный вектор следующим образом. Компоненты , которые равны , имеют индексы . Остальные компоненты равны . Сообщение восстанавливается из следующим образом: Выбрать , Для от до выполнить следующие действия: Если , то выбрать и
Доказательство Для доказательства работы схемы можно заметить, что
Так как и — монические многочлены степени и конгруэнтны по модулю , то:
Следовательно, корней все лежат в , и применение к этим корням дает координаты , которые равны .
Пример В качестве примера можно рассмотреть работу схемы в случае, когда параметры относительно малы
Генерация ключей Для генерации ключей A выполняет следующее: Выбирает и Выбирает неприводимый многочлен степени над . Элементы конечного поля представлены как многочлены от степени меньше , причем умножение выполняется по модулю . Выбирает случайный примитивный элемент Вычисляет следующие дискретные логарифмы
Выбирает случайную перестановку на , определяемой Выбирает случайное целое число Вычисляет
Открытым ключом является , а закрытый ключ
Шифрование Чтобы зашифровать сообщение для , делает следующее: Получает открытый ключ открытого ключа Представляет как двоичную строку длиной : . (так как ) Использует метод, описанный на шаге 3 " алгоритма Шифрования ", для преобразования в бинарный вектор длины . Вычисляет Отправляет в
Дешифрование Чтобы расшифровать зашифрованный текст , делает следующие действия: Вычисляет Вычисляет Вычисляет Факторизует (так , , , ) Компоненты , которые равны , имеют индексы , , и . Следовательно, Использует метод, описанный на шаге 6 " алгоритма дешифрования ", чтобы преобразовать в целое число , тем самым восстанавливая исходный текст.
Особенности криптосистемы Известно, что система небезопасна, если раскрыты части секретного ключа, например, если известны и в некотором представлении или если известно, или если известен Хотя схема Шор-Ривеста была описана только для случая простой, она распространяется на случай, когда базовое поле заменяется полем первичного степенного порядка Чтобы сделать задачу дискретного логарифма выполнимой на шаге 1 алгоритма " Генерация ключей ", параметры и могут быть выбраны так, что имеет только малые множители. В этом случае для эффективного вычисления дискретных логарифмов можно использовать алгоритм Полига — Хеллмана в конечном поле На практике рекомендуемый размер параметров: и . Один конкретный выбор первоначально предложенных параметров: и ; в этом случае наибольший простой коэффициент составляет , а плотность набора ранца составляет около . Другие первоначально заданные параметры: , (базовое поле ) и (базовое поле ) Шифрование — очень быстрая операция. Расшифровка выполняется намного медленнее, узким местом является вычисление на шаге 2 " алгоритма дешифрования ". Корни на шаге 4 можно найти, просто попробовав все возможности в Основным недостатком схемы Шор-Ривеста является то, что открытый ключ довольно велик, а именно бит . Для параметров и это около 36000 бит Расширение сообщения происходит в . Для и , это
Атаки с раскрытием частичного ключа В этом разделе показывает, что он может монтировать атаку, когда раскрывается какая-либо часть секретного ключа. Несколько таких атак уже опубликованы в документе и некоторые из них были улучшены ниже.
Секретные ключи состоят из: элемент с степенью генератор целое число перестановка на множестве целых чисел Атака с раскрытием части
Если предположим, что и (из-за симметрии в секретном ключе мы знаем, что будет выполняться произвольный выбор ), мы можем вычислить и , то решим систему уравнения:
с неизвестными и
Атака с раскрытием части
Если предположим, что и (из-за симметрии в секретном ключе мы знаем, что будет выполняться произвольный выбор ), мы можем вычислить:
затем разрешить
Атака с раскрытием части
Найдем линейную комбинацию с формой с относительно небольшими интегральными коэффициентами . Это можно выполнить с помощью алгоритма Lenstra-Lenstra-Lovász. Мы можем ожидать, что с . Обозначая это, получаем некоторое уравнение:
с неотрицательными малыми степенями, который является полиномиальным уравнением с малой степенью, которое может быть эффективно разрешено.
Атака с раскрытием части и
Мы можем интерполировать полином с парами . Таким образом, мы получаем многочлен — степени, корни которого являются сопряженными . Потом мы можем решить его, чтобы получить и выполнить атаку с раскрытием части
См. также Криптосистема с открытым ключом Шифрование Класс NP Задача о ранце в криптографии Ранцевая криптосистема Меркла — Хеллмана Конечное поле Дискретное логарифмирование Неприводимый многочлен Биномиальный коэффициент
Примечания
Категория:Криптография