RSASSA-PSS

RSASSA-PSS (RSA Signature Scheme with Appendix-Probabilistic Signature Scheme) — асимметричный алгоритм цифровой подписи. Основан на принципе кодирования PSS, предложенном в 1996 году авторами Mihir Bellare и Phillip Rogaway^[1]. Внесён в стандарт PKCS#1 v2.1 от 2002 года, выработанный RSA Laboratories, США.

Описание алгоритма

Пусть Алиса (A) хочет послать сообщение M Бобу(B), заверив его электронной подписью S. B, получив сообщение от A, должен верифицировать подпись (проверить на подлинность).

• (n, e) — открытый ключ, и (n, e,d) — соответствующий закрытый ключ A. n — целое положительное число длинной modBits бит или k байт (Например: двоичная запись n требует 1028 символов, тогда modBits = 1028, k = 129, так как $k = \lceil y/8 \rceil$).
• emBits = modBits — 1
• $emLen = \lceil emBits/8 \rceil$
• zBits = 8emLen — emBits

В данной статье под «старший байт (бит)» понимается самый первый, левый байт (бит). Под «младший байт (бит)» соответственно понимается самый последний, правый байт (бит).
Также под «строка» следует понимать некий массив, элементами которого являются одиночные байты. Таким образом «строковым представлением числа n» является строка N, полученная разбиением двоичной записи n на байты. Например:

n = 258 {100000010}

N = [1|2] {00000001|00000010}

При этом [1] - старший байт, а [2] - младший байт.
Далее описаны функции создания и верификации электронной подписи.

Создание подписи

---

RSASSA-PSS-Sign((n, e,d), M)

Входные данные:

(n, e,d) — закрытый ключ

M — подписываемое сообщение, строка

Выходные данные:

S — подпись, строка длины k

Возможные ошибки:

"сообщение слишком длинное"; «ошибка кодирования»

Последовательность действий:

1. PSS-кодирование:

   Применим функцию PSS-Encode (которая будет описана ниже) к строке M для получения строки EM длины x.

   EM такова, что длина в битах целочисленного представления EM не превышает emBits, и zBits старших бит равны 0.

   EM = PSS-Encode(M,emBits)

   Заметим, что длина EM равна (k-1), если emBits делится на 8 без остатка, и равна k в противном случае.

   Если PSS-encoding возвращает ошибку «сообщение слишком длинное», выводится сообщение об ошибке и работа прекращается.

   Если PSS-encoding возвращает ошибку «ошибка кодирования», выводится сообщение об ошибке и работа прекращается.

2. RSA-подпись:
   • Присвоим m целочисленное представление строки EM.

   m = str-to-int(EM)

   • Используем закрытый ключ.

   s = m^d mod n

   • Представим m, как байтовую строку длины k.

   S = int-to-str(m, k)

3. Вывод S

PSS-кодирование

PSS-Encode(M, emBits)

Опции:

Hash — хэш-функция, возвращает байтовую строку длины hLen

MGF — mask generation function. Преобразует входную байтовую строку в строку заданной длины (будет подробно описана ниже).

sLen — длина байтовой строки salt

Входные данные:

M — подписываемое сообщение, строка

emBits — максимальная длина в битах целочисленного представления выходной строки EM, по меньшей мере (8hLen + 8sLen + 9)

PSS-Encode

Выходные данные:

EM — закодированное сообщение, строка длины emLen

Возможные ошибки:

«сообщение слишком длинное»; «ошибка кодирования»

Последовательность действий:

1. Если длина M больше максимально возможной длины входной строки выбранной хэш-функции ($2^{61} - 1$ байт для SHA-1), возвращается сообщение «сообщение слишком длинное» и работа прекращается.
2. mHash = Hash(M), строка длины hLen.
3. Если emLen < (hLen + sLen + 2), возвращается сообщение «ошибка кодирования» и работа прекращается.
4. Генерируется случайная строка salt длины sLen; если sLen = 0, salt — пустая строка.
5. M’ = (0x)00 00 00 00 00 00 00 00||mHash||salt, строка длины (8 + hLen + sLen), первые 8 байт которой — нулевые.
6. H = Hash(M’), строка длины hLen.
7. Генерируется строка PS состоящая из (emLen — hLen — sLen — 2) нулевых байтов. Длина PS может оказаться равной нулю.
8. DB = PS||0x01||salt, строка длины (emLen — hLen — 1).
9. dbMask = MGF(H, emLen — hLen — 1), строка длины (emLen — hLen — 1).
10. maskedDB = DB ⊕ dbMask.
11. zBits старших бит в старшем байте maskedDB устанавливаются в 0.
12. TF = 0xBC.
13. EM = maskedDB||H||TF
14. Вывод EM.

Верификация подписи

---

RSASSA-PSS-Verify((n, e), M, S)

Входные данные:

(n, e) — открытый ключ

M — полученное сообщение, строка

S — подпись, подлежащая проверке, строка длины k

Выходные данные:

"подпись действительна" или «подпись недействительна»

Последовательность действий:

1. Проверка длины:

   Если длина подписи S больше k байт, то выносится решение «подпись недействительна», и работа прекращается.

2. RSA-проверка:
   • Присвоим m целочисленное представление строки S.

   m = str-to-int(S)

   • Используем открытый ключ.

   s = m^e mod n

   • Представим m, как байтовую строку длины emLen.

   EM = int-to-str(m, emLen)

   Заметим, что emLen равна (k-1), если emBits делится на 8 без остатка и равна k в противном случае. Если же запись числа m занимает больше emLen байт, то выносится решение «подпись недействительна», и работа прекращается.

3. PSS-проверка:

   Применим функцию PSS-Verify (которая будет описана ниже). Окончательное решение совпадает с решением, вынесенным PSS-Verify.

   Output = PSS-Verify(M, EM, emBits)

PSS-проверка

PSS-Verify(M, EM, emBits)

Опции:

Hash — хэш-функция, возвращает байтовую строку длины hLen.

MGF — mask generation function. Преобразует входную байтовую строку в строку заданной длины (будет подробно описана ниже).

sLen — длина байтовой строки salt.

Входные данные:

M — полученное сообщение, строка.

PSS-Verify

EM — закодированное сообщение, строка длины emLen.

emBits — максимальная длина в битах целочисленного представления строки EM, по меньшей мере (8hLen + 8sLen + 9).

Выходные данные:

"подпись действительна" или «подпись недействительна»

Последовательность действий:

1. Если длина M больше максимально возможной длины входной строки выбранной хэш-функции ($2^{61} - 1$ байт для SHA-1), выносится решение «подпись недействительна» и работа прекращается.
2. mHash = Hash(M), строка длины hLen.
3. Если emLen < (hLen + sLen + 2), выносится решение «подпись недействительна» и работа прекращается.
4. Если младший байт EM (поле TF) не равен 0xBC, то выносится решение «подпись недействительна» и работа прекращается.
5. Старшие (emLen — hLen — 1) байт EM записываются в строку maskedDB, а последующие hLen байт — в строку H.
6. Если старшие zBits бит старшего байта maskedDB не нулевые, то выносится решение «подпись недействительна» и работа прекращается.
7. dbMask = MGF(H, emLen — hLen — 1), строка длины (emLen — hLen — 1).
8. DB = maskedDB ⊕ dbMask.
9. zBits старших бит в старшем байте DB устанавливаются в 0.
10. Если старшие (emLen — hLen — sLen — 2) байт DB не равны 0 или если, последующий байт (байт на позиции (emLen — hLen — sLen — 1), приняв позицию старшего байта равной 1) не равен 0x01, то выносится решение «подпись недействительна» и работа прекращается.
11. В байтовую строку salt записываются последние sLen байт DB.
12. M’ = (0x)00 00 00 00 00 00 00 00||mHash||salt, строка длины (8 + hLen + sLen), первые 8 байт которой — нулевые.
13. H' = Hash(M’), строка длины hLen.
14. Если H = H', то выносится решение «подпись действительна», иначе выносится решение «подпись недействительна».

Mask Generation Function

---

Опишем MGF, используемую в PSS-функциях.
MGF принимает на вход байтовую строку произвольной длины и желаемую длину выходной строки и выдаёт байтовую строку желаемой длины. На длины входной и выходной строк могут накладываться ограничения, но они обычно очень велики. MGF детерминирована; выходная строка полностью определяется входной строкой. Выходные данные MGF должны быть псевдослучайными, т.е. зная часть выходной строки, должно быть практичеки невозможно предугадать оставшуюся часть выходной строки. Этого можно добиться, положив в основу MGF хэш-функцию с аналогичным свойством. Данное свойство необходимо, т.к. на него полагается доказательство надёжности алгоритма.
В стандарте PKCS#1 v2.1 в качестве MGF предлагается использовать следующую функцию:

MGF1(M, maskLen)

Опции:

Hash — хэш-функция, возвращает байтовую строку длины hLen.

Входные данные:

M — преобразуемая строка.

maskLen — требуемая длина выходной байтовой строки, не превышает 2³²hLen.

Выходные данные:

mask — строка длины maskLen.

Возможные ошибки:

«длина маски слишком велика»

Последовательность действий:

1. Если maskLen > 2³²hLen, выводится сообщение «длина маски слишком велика» и работа прекращается.
2. Пусть T — пустая строка.
3. В цикле ДЛЯ i ОТ 0 ДО $\lceil maskLen/hLen \rceil - 1$ ВЫПОЛНЯЕТСЯ:
   • Представим i как байтовую строку C длины 4 байта.

   C = int-to-str(i,4)

   • M' = M||C.
   • Допишем в конец строки T результат хэширования M'.

   T = T||Hash(M')

4. Запишем в mask старшие maskLen байт строки T.
5. Вывод mask.

Параметры

---

В стандарте PKCS#1 v2.1 RSASSA-PSS присвоен идентификатор id-RSASSA-PSS, с которым должна ассоциироваться последовательность четырёх параметров. К этим параметрам относятся хэш-функция, MGF, длина случайно генерируемой строки salt (sLen), trailerField (поле TF). Значения по умолчанию этих параметров, приведённые в рассматриваемом стандарте, даны в таблице.

Праметр	Тип	Значение по умолчанию
hashAlgorithm	HashAlgorithm	sha1
maskGenAlgorithm	MaskGenAlgorithm	mgf1SHA1
saltLength	INTEGER	20
trailerField	TrailerField	trailerFieldBC

• Рекомендуется, чтобы хэш-функция, на которой основана MGF (если такое имеет место) совпадала с той, что задаётся параметром hashAlgorithm.
• Значение по умолчанию параметра saltLength равно длине выходной строки выбранной хэш-функции (hLen). В отличие от остальных параметров, saltLength не обязательно должна быть фиксированной для данной пары RSA-ключей.
• Поле TF введено для совместимости с проектом IEEE P1363a. В рассматриваемом стандарте поддерживается только значение trailerField равное 0xBC. Однако, оно может иметь и другой вид, например HID||0xCC, где HID — идентификатор хэш-функции, указанный в стандарте ISO/IEC 10118.

Особенности

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

RSA-PSS отличается от других схем цифровой подписи на основе RSA тем, что она вероятностная, а не детерминированная, т.к. включает в себя использование случайно сгенерированной величины (salt). Величина salt усиливает надёжность схемы ^[1].

Надёжность

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

Описанная ранее схема подписи отличается от оригинального алгоритма, предложенного Mihir Bellare и Phillip Rogaway^[1]. Однако, необходимое доказательство для данной схемы приведено в работе Джейкоба Джонссона (Jacob Jonsson)^[2].

Примечания

1. ↑ ^{1 2 3} Mihir Bellare, Phillip Rogaway "The Exact Security of Digital Signatures - How to Sign with RSA and Rabin"
2. ↑ Jacob Jonsson «Security proofs for the RSA-PSS signature scheme and its variants» (PDF)

Источники

• PKCS #1 v2.1
• Alfred Menezes "Evaluation of Security Level of Cryptography: RSA-OAEP, RSA-PSS, RSA Signature"