Размер подписи RSA?

Question

Я хотел бы знать, какова длина подписи RSA? Всегда ли он имеет такой же размер, как и размер ключа RSA, например, если размер ключа равен 1024, тогда сигнатура RSA равна 128 байтам, если размер ключа равен 512 битам, тогда сигнатура RSA составляет 64 байта? что такое модуль RSA? И что означает RSA-sha1? Любые указатели очень ценятся.

Answer 1

Вы правы, размер подписи RSA зависит от размера ключа, размер подписи RSA равен длине модуля в байтах. Это означает, что для "n-битного ключа" результирующая подпись будет иметь длину ровно n бит. Хотя вычисленное значение подписи не обязательно равно n битам, результат будет дополнен, чтобы точно соответствовать n битам.

Теперь вот как это работает: алгоритм RSA основан на модульном возведении в степень. Для такого расчета конечным результатом является остаток от "нормального" результата, деленный на модуль. Модульная арифметика играет большую роль в теории чисел. Там определение конгруэнтности (≡)

m is congruent to n mod k if k divides m - n

Простой пример - пусть n = 2 и k = 7, тогда

2 ≡ 2 (mod 7) because: 7 divides 2 - 2
9 ≡ 2 (mod 7) because: 7 divides 9 - 2
16 ≡ 2 (mod 7) because: 7 divides 16 - 2
...

7 на самом деле делит 0, определение для деления

Целое число a делит целое число b, если существует целое число n со свойством b = na

Для a = 7 и b = 0 выберите n = 0. Это означает, что каждое целое число делит 0, но также подразумевает, что конгруэнтность может быть расширена до отрицательных чисел (здесь не будем вдаваться в подробности, это не важно для RSA).

Таким образом, суть в том, что принцип конгруэнтности расширяет наше наивное понимание остатков, модуль - это "число после мода", в нашем примере это будет 7. Поскольку существует бесконечное количество чисел, которые совпадают с данным модулем, мы говорим это как классы конгруэнтности и обычно выбирают одного представителя (наименьшее конгруэнтное целое число> 0) для наших вычислений, так же, как мы интуитивно делаем, говоря о "остатке" вычисления.

В RSA подписание сообщения m означает возведение в степень с "частным показателем" d, результат r является наименьшим целым числом> 0 и меньше, чем модуль n, так что

m^d ≡ r (mod n)

Это подразумевает две вещи

• Длина r (в битах) ограничена n (в битах)
• Длина m (в битах) должна быть <= n (в битах тоже)

Чтобы длина подписи составляла ровно n битов, применяется некоторая форма заполнения. Ср PKCS#1 для действительных вариантов.

Второй факт подразумевает, что сообщения, большие чем n, должны были бы быть подписаны путем разбиения m на несколько кусков <= n, но на практике это не делается, так как это было бы слишком медленно (возведение в модулярное возведение в вычислительном отношении дорого в вычислительном отношении), поэтому нам нужно другой способ "сжать" наши сообщения, чтобы они были меньше n. Для этой цели мы используем криптографически безопасные хеш-функции, такие как SHA-1, которые вы упомянули. Применение SHA-1 к сообщению m произвольной длины создаст "хэш" длиной 20 байтов, меньший, чем типичный размер модуля RSA, общие размеры составляют 1024 бит или 2048 бит, то есть 128 или 256 байтов, поэтому Расчет подписи может быть применен для любого произвольного сообщения.

Криптографические свойства такой хеш-функции гарантируют (теоретически - подделка сигнатур является огромной темой в исследовательском сообществе), что невозможно подделать подпись иначе, как с помощью грубой силы.