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, так как $\text{[math]}$ $\text{[math]}$ $k=\lceil y/8\rceil$ ).
emBits = modBits — 1
$\text{[math]}$ $\text{[math]}$ $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
Возможные ошибки:: "сообщение слишком длинное"; «ошибка кодирования»
Последовательность действий:

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 возвращает ошибку «ошибка кодирования», выводится сообщение об ошибке и работа прекращается.
RSA-подпись:
- Присвоим m целочисленное представление строки EM.
m = str-to-int(EM)
- Используем закрытый ключ.
s = m^d mod n
- Представим s, как байтовую строку длины k.
S = int-to-str(s, k)
Вывод S

PSS-кодированиеПравить

PSS-Encode(M, emBits)

Опции:: Hash — хеш-функция, возвращает байтовую строку длины hLen; MGF — mask generation function. Преобразует входную байтовую строку в строку заданной длины (будет подробно описана ниже).; sLen — длина байтовой строки salt
Входные данные:: M — подписываемое сообщение, строка; emBits — максимальная длина в битах целочисленного представления выходной строки EM, по меньшей мере (8hLen + 8sLen + 9)

PSS-Encode

Выходные данные:: EM — закодированное сообщение, строка длины emLen
Возможные ошибки:: «сообщение слишком длинное»; «ошибка кодирования»
Последовательность действий:

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

Верификация подписиПравить

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

Входные данные:: (n, e) — открытый ключ; M — полученное сообщение, строка; S — подпись, подлежащая проверке, строка длины k
Выходные данные:: "подпись действительна" или «подпись недействительна»
Последовательность действий:

Проверка длины:
Если длина подписи S больше k байт, то выносится решение «подпись недействительна», и работа прекращается.
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 байт, то выносится решение «подпись недействительна», и работа прекращается.
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).
Выходные данные:: "подпись действительна" или «подпись недействительна»
Последовательность действий:

Если длина M больше максимально возможной длины входной строки выбранной хеш-функции ( $\text{[math]}$ $\text{[math]}$ $2^{61}-1$ байт для SHA-1), выносится решение «подпись недействительна» и работа прекращается.
mHash = Hash(M), строка длины hLen.
Если emLen < (hLen + sLen + 2), выносится решение «подпись недействительна» и работа прекращается.
Если младший байт EM (поле TF) не равен 0xBC, то выносится решение «подпись недействительна» и работа прекращается.
Старшие (emLen — hLen — 1) байт EM записываются в строку maskedDB, а последующие hLen байт — в строку H.
Если старшие zBits бит старшего байта maskedDB не нулевые, то выносится решение «подпись недействительна» и работа прекращается.
dbMask = MGF(H, emLen — hLen — 1), строка длины (emLen — hLen — 1).
DB = maskedDB ⊕ dbMask.
zBits старших бит в старшем байте DB устанавливаются в 0.
Если старшие (emLen — hLen — sLen — 2) байт DB не равны 0 или если, последующий байт (байт на позиции (emLen — hLen — sLen — 1), приняв позицию старшего байта равной 1) не равен 0x01, то выносится решение «подпись недействительна» и работа прекращается.
В байтовую строку salt записываются последние sLen байт DB.
M’ = (0x)00 00 00 00 00 00 00 00||mHash||salt, строка длины (8 + hLen + sLen), первые 8 байт которой — нулевые.
H' = Hash(M’), строка длины hLen.
Если 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.
Возможные ошибки:: «длина маски слишком велика»
Последовательность действий:

Если maskLen > 2³²hLen, выводится сообщение «длина маски слишком велика» и работа прекращается.
Пусть T — пустая строка.
В цикле ДЛЯ i ОТ 0 ДО ⌈ m a s k L e n / h L e n ⌉ − 1 ВЫПОЛНЯЕТСЯ:
- Представим i как байтовую строку C длины 4 байта.
C = int-to-str(i,4)
- M' = M||C.
- Допишем в конец строки T результат хеширования M'.
T = T||Hash(M')
Запишем в mask старшие maskLen байт строки T.
Вывод 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].

ПримечанияПравить

↑ ¹ ² ³ Mihir Bellare, Phillip Rogaway "The Exact Security of Digital Signatures - How to Sign with RSA and Rabin" (неопр.). Дата обращения: 1 ноября 2010. Архивировано 13 июня 2010 года.
↑ Jacob Jonsson «Security proofs for the RSA-PSS signature scheme and its variants» (PDF) (неопр.). Дата обращения: 1 ноября 2010. Архивировано 6 марта 2016 года.

ИсточникиПравить

PKCS #1 v2.1 Архивная копия от 31 июля 2013 на Wayback Machine
Alfred Menezes "Evaluation of Security Level of Cryptography: RSA-OAEP, RSA-PSS, RSA Signature"

[Bellare_and_Rogaway-1] ¹ ² ³ Mihir Bellare, Phillip Rogaway "The Exact Security of Digital Signatures - How to Sign with RSA and Rabin" (неопр.). Дата обращения: 1 ноября 2010. Архивировано 13 июня 2010 года.

[2] Jacob Jonsson «Security proofs for the RSA-PSS signature scheme and its variants» (PDF) (неопр.). Дата обращения: 1 ноября 2010. Архивировано 6 марта 2016 года.

[1]

[2]