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

Ответ 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 байтов, поэтому подсчет подписи может применяться для любого произвольного сообщения.

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