Сравнение одной хеш-функции и RSA

Question

Я хочу сравнить хэш-функцию и RSA-шифрование с другим параметром. У меня есть алгоритм с некоторой хэш-функцией, и я хочу утверждать, что вычислительная нагрузка этих хэшей меньше одного RSA.

Можно ли сравнить их с параметром умножения, например, сколько умножений у каждого из них есть?

Как я могу сравнить их в нагрузке связи? Как я могу сказать, какова длина вывода в RSA?

Answer 1

Похоже, вы пытаетесь сравнить яблоки и апельсины.

Ожидается, что A hash function принимает произвольно большие входы, а время, необходимое для его вычисления, обычно должно линейно масштабироваться с длиной ввода. Таким образом, полезной мерой hash function performance будет, скажем, «мегабайт в секунду».

(В частности, это было бы мера throughput, которая является соответствующей мерой, когда хэширования длинных входов. Для коротких сообщений, более актуальная мера является latency, который является в основном минимальное временем, необходимым для хэширования входа нулевой длины . Учитывая пропускную способность и латентность, можно в общем вычислить достаточно хорошее приближение времени, необходимого для хэширования ввода любой заданной длины, как времени = задержка + длина/пропускной способности.)

RSA, с другой стороны вручную, может шифровать сообщения короче, чем модуль, который выбирается в момент генерации ключа. (Typical modulus sizes может быть, скажем, от 1024 до 4096 бит.) Для «шифрования длинного сообщения с помощью RSA» обычно используется hybrid encryption: сначала зашифруйте сообщение с использованием симметричного шифра, такого как AES, используя подходящий mode of operation и случайно выбранный ключ, а затем зашифровать ключ AES с помощью RSA.

То же ограничение длины относится к signing сообщениям с RSA — само по себе, RSA может только подписывать сообщения короче, чем модуль. Стандартное обходное решение в этом случае - это сначала передать сообщение, а затем подписать значение хэша. (Также есть много важных деталей, таких как , что я не собираюсь входить сюда, так как мы не на crypto.SE, но которые абсолютно необходимы для обеспечения безопасности.)

Дело в том, что в обоих случаев, операция RSA сама принимает фиксированное количество времени независимо от длины сообщения, и, таким образом, для достаточно длинных сообщений большая часть времени будет потребляться AES или хэш-функцией, а не самой RSA. Поэтому, когда вы говорите, что хотите «утверждать, что вычислительная нагрузка этих хэшей меньше одного RSA», я бы сказал, что это бессмысленно, по крайней мере, если вы не установили определенную длину ввода для вашего хэша. (И если бы вы это сделали, мой следующий вопрос был бы «в чем особенность этой конкретной длины ввода?»)