RSASSA-PSS

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з RSA-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, так як ).
  • emBits = modBits — 1
  • zBits = 8emLen — emBits[2]

У даній статті під словосполученням «старший байт (біт)» розуміється перший, лівий байт (біт). Під «молодший байт (біт)» відповідно розуміється найостанній, правий байт (біт). Також під словом «рядок» слід розуміти певний масив, елементами якого є поодинокі байти. Таким чином «рядковим поданням числа 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
Можливі помилки: «повідомлення дуже довге»; «помилка кодування»
Послідовність дій:[2]
  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 = md mod n
    • Уявімо s, як байтовий рядок довжини k.
    S = int-to-str(s, k)
  3. Висновок S[2]

PSS-кодування[ред. | ред. код]

PSS-Encode(M, emBits)

Опції:
Hash — геш-функція, що повертає байтовий рядок довжини hLen
MGF — mask generation function. Перетворює вхідний байтовий рядок в рядок заданої довжини (буде докладно описано нижче).
sLen — довжина байтового рядка salt
Вхідні дані:
M — підписане повідомлення, рядок
emBits — максимальна довжина в бітах цілочисельного подання вихідний рядка EMщонайменше (8hLen + 8sLen + 9)
PSS-Encode
Вихідні дані:
EM — закодоване повідомлення, рядок довжини emLen
Можливі помилки:
«повідомлення дуже довге»; «помилка кодування»
Послідовність дій:[2]
  1. Якщо довжина M більша максимально можливої довжини вхідного рядка обраної хеш-функції ( байт для 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 = me 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)[2]

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 більша максимально можливої довжини вхідного рядка обраної геш-функції ( байт для 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’, то виноситься рішення «підпис дійсний», інакше виноситься рішення: «підпис недійсний»[2].

Mask Generation Function[ред. | ред. код]

Опишемо MGF, яка використана в PSS-функціях. MGF приймає на вхід байтовий рядок довільної довжини і бажану довжину вихідного рядка й видає байтовий рядок бажаної довжини. На довжину вхідний і вихідний рядків можуть накладатися обмеження, але вони зазвичай дуже великі. MGF детермінована; вихідий рядок повністю визначається вхідним рядком. Вихідні дані MGF повинні бути псевдовипадковми, тобто знаючи частину вихідного рядка, має бути практично неможливо передбачити частину вихідного рядка. Цього можна домогтися, поклавши в основу MGF геш-функцію з аналогічною властивістю. Ця властивість необхідна, так як на неї покладається доказ надійності алгоритму. У стандарті PKCS#1 v2.1 в якості MGF пропонується використовувати наступну функцію:

MGF1(M, maskLen)

Опції:
Hash — геш-функція, що повертає байтовий рядок довжини hLen.
Вхідні дані:
M — Рядок, який перетворюється
maskLen — необхідна довжина вихідного байтового рядка, не перевищує 232hLen.
Вихідні дані:
mask — рядок довжини maskLen.
Можливі помилки:
«довжина маски занадто велика»
Послідовність дій:
  1. Якщо maskLen > 232hLen, виводиться повідомлення «довжина маски занадто велика» і робота припиняється.
  2. Нехай T — порожній рядок.
  3. У циклі ДЛЯ i ВІД 0 ДО ВИКОНУЄТЬСЯ:
    • Уявімо 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 посилює надійність схеми.

Надійність[ред. | ред. код]

Вважаючи, що обчислення кореня довільного степеня за модулем n є нездійсненним з практичної точки зору операцією, і геш-функція і MGF володіють необхідними властивостями, RSA-PSS забезпечує захищеність підпису. Надійність доказова в тому сенсі, що складність злому підпису може бути безпосередньо пов'язана зі складністю злому криптографічного примітиву (математичної проблеми, що лежить в основі RSA). Імовірність успішного злому й час роботи найкращого методу злому RSA-PSS дуже близькі до тих же параметрів алгоритму знаходження оберненої функції RSA[3].

Описана раніше схема підпису відрізняється від оригінального алгоритму, запропонованого Mihir Bellare і Phillip Rogaway. Однак, необхідний доказ для даної схеми наведено в роботі Джейкоба Джонссона (Jacob Jonsson)[4].

Примітки[ред. | ред. код]

  1. ↑ Mihir Bellare, Phillip Rogaway «The Exact Security of Digital Signatures — How to Sign with RSA and Rabin» (PDF). Архів оригіналу (PDF) за 13 червня 2010. Процитовано 21 квітня 2018.
  2. ↑ а б в г д е Alfred Menezes «Evaluation of Security Level of Cryptography: RSA-OAEP, RSA-PSS, RSA Signature» (PDF). Архів оригіналу (PDF) за 4 березня 2016. Процитовано 21 квітня 2018.
  3. ↑ PKCS #1 v2.1. Архів оригіналу за 31 липня 2013. Процитовано 21 квітня 2018.
  4. ↑ Jacob Jonsson «Security proofs for the RSA-PSS signature scheme and its variants» (PDF). Архів оригіналу за 6 березня 2016. Процитовано 21 квітня 2018.

Джерела[ред. | ред. код]

На цю статтю не посилаються інші статті Вікіпедії.
Будь ласка розставте посилання відповідно до прийнятих рекомендацій.
Отримано з https://uk.wikipedia.org/w/index.php?title=RSASSA-PSS&oldid=38364621