Русская Википедия:SPHINCS

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

SPHINCS (stateless hash-based signatures) — криптографическая схема, основанная на криптографической стойкости хеш-функции. Схема включает в себя алгоритм формирования и проверки электронной цифровой подписи.

NIST[1] (Национальный институт стандартов и технологий США) опубликовал запрос[2] на разработку новых криптографических алгоритмов с открытым ключом, которые были бы устойчивы к атакам с использованием квантового компьютера. Уже сейчас IBM располагает готовым технологическим решением[3] — квантовой системой, состоящей из 20 кубитов. Возможно, масштабирование квантовой системы, до размеров которые представляли бы угрозу широко употребительным сейчас алгоритмам цифровой подписи, это вопрос ближайших десятилетий.[4] Одним из возможных решений описанной проблемы может являться cхема SPHINCS.

Предпосылки появления, альтернативы, описание

В настоящее время нет однозначного ответы на вопрос: «Как обеспечить функциональность электронной цифровой подписи в постквантовом мире?»

Под функциональностью обычно понимают:

  • аутентификация источника сообщения
  • контроль целостности сообщения
  • защита сообщения от подделывания
  • малый объём цифровой подписи
  • высокая скорость генерации/проверки цифровой подписи

Рассмотрим известные схемы цифровой подписи:

  1. RSA и ECC, широко распространенные в настоящее время, достаточно компактны и быстры, но взламываются за полиномиальное время с помощью алгоритма Шора(при наличии квантового компьютера)
  2. GGH и другие схемы, построенные на решетках, имеют неясные перспективы роста уровня безопасности (только 80 % от заявленных разработчиками «100 bit» к 2013 году)
  3. Схемы многомерной криптографии, построенные на решениях уравнений, основанных на многомерных полиномах над конечным полем, имеют очень короткие и быстро обрабатываемые подписи, приемлемого размера ключи для использования в распространенных приложениях, но такие же неопределенные перспективы криптографической стойкости для квантового компьютера

Альтернативы

Тип Схема подписи Тип Схема подписи
Криптография на решётках Криптография с использованием хеш-функций
  • Gravity-SPHINCS
  • SPHINCS+
Алгоритмы алгебраического кодирования
  • pqsigRM
  • RaCoSS
  • RankSign
 Многомерная криптография
  • DualModeMS
  • GeMSS
  • Gui
  • HiMQ-3
  • LUOV
  • MQDSS
  • Rainbow

***Полная версия таблицы

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

SPHINCS представляет из себя высоконадежную систему цифровой подписи, основанную на хеш-функции, соответствующую криптографическим стандартам(в случае hash-based подписи это означает схему без контроля состояний ***в англ. литературе stateless), которая предоставляет безопасность «128 bit» против атак квантового компьютера и может быть реализована на существующей элементной базе (4-core 3.5 GHz Intel CPU).

История развития hash-based подписей (предшественники SPHINCS)

  • Идея создания подписи, основанной на хеш-функции, восходит к американскому учёному, Лесли Лэмпорту. Подпись Лэмпорта предполагает использование одноразовой пары ключей(OTS key pair). Очевидно, что секретный ключ такой подписи нельзя использовать дважды, кроме того для подписи N-бит сообщения требуется использовать последовательность из N открытых ключей, что делает схему трудно применимой на практике.

Пример подписи Лэмпорта

Пример подписи 1 бита сообщения по схеме Лэмпорта

Имеем: 

Криптостойкую хеш-функцию + Генератор случайных чисел

Сгенерируем секретный и открытый ключ: 

     SK = пара случайных чисел
      PK = 2 числа, результат хеширования SK

Подпишем сообщение: 

     Хешируем сообщение
      Биту хешированного сообщения ставим в соответствие число(X) из пары секретного ключа
      Это число(X) + PK = Подпись

Проверка подписи: 

     Хешируем сообщение
      Биту хешированного сообщения ставим в соответствие число из PK(Y) по тому же правилу, что и при подписи
      Хешируем число(X), переданное в подписи
      Если Y = X , то подпись верна
  • Чтобы иметь возможность подписывать компактным открытым ключом множество сообщений, Меркл предложил алгоритм, который сейчас называется «дерево Меркла». Он взял за основу подпись Лампорта(OTS схему). Чтобы создать многоразовую схему подписей, Меркл инициализировал 2Шаблон:Sup OTS(пар одноразовых ключей), используя бинарное дерево высоты h. Листья бинарного дерева* есть ни что иное как хешированные открытые ключи из схемы OTS. Секретные ключи из OTS становятся секретными ключами схемы Меркла без изменений. А вот открытым ключом в этой схеме является корень бинарного дерева.
Файл:Mercl tree.png
Процесс построения дерева Меркла

Дерево Меркла

Таким образом полная подпись Меркла включает в себя:

  1. Индекс использованных ключей OTS(one-time signature) в бинарном дереве (они используются в определённом порядке)
  2. Открытый ключ и подпись схемы OTS
  3. Вспомогательные данные, которые позволят дойти от листа дерева до его корня
  • Даже после изобретения дерева Меркла схемы подписей основанные на хеш-функциях имели нерешенные проблемы:
  1. Необходимость контролировать использованные ключи, как неизбежный побочный эффект лежащей в основе OTS(one-time signature) схемы. Это ставило под угрозу целостность таких схем(перенос с одного устройства на другое, восстановление данных)
  2. Экспоненциальный рост временны́х затрат на генерацию подписей и ключей с ростом высоты дерева n

___________________________________________________________________________________________________________________

  • Вышеизложенные проблемы решили две идеи:
  1. Одед Голдрейх предложил вместо определённого порядка использования ключей и индексирования по листьям бинарного дерева высоты n использовать хеш-функцию, которая бы принимала подписываемое сообщение и возвращала число h от 0 до (2Шаблон:Sup)-1. Это число(h) и определяло бы пару ключей OTS. Также возможно использование генератора случайных чисел с равномерным распределением в том же диапазоне. Тогда криптографическая стойкость схемы будет зависеть от вероятности коллизий. Практика показывает, что можно достигнуть вероятности повторного использования пары ключей 2Шаблон:Sup, при количестве подписей 2Шаблон:Sup.
  2. Проблема чрезмерных временных затрат решается путем использования «гипердеревьев», состоящих из слоёв обычных бинарных деревьев. Например, использование d слоёв из деревьев высоты h/d позволяет сократить время генерации ключей c O(2Шаблон:Sup) до O(d*2Шаблон:Sup/d), а время генерации подписи с O(2Шаблон:Sup) до O(h)

Устройство схемы электронно-цифровой подписи SPHINCS

Составляющие схемы

SPHINCS[6] использует в своей работе некоторый набор параметров, функций и примитивов(побочных схем):

Функции

Примитивы

  • Гипердерево[6](дерево деревьев) высоты h∈N, которое состоит из d слоёв, каждый из которых имеет высоту h/d
  • Усовершенствованная схема Winternitz one-time signature (WOTS+[6])
  • Усовершенствованная tree-based few-time signature scheme (HORST[6])

Параметры

  • Главный параметр криптографической безопасности n ∈ N
  • Параметры для достижения пространственно-временного компромисса w ∈ N(WOTS+), t = 2Шаблон:Sup ∈ N(HORST), k∈N(HORST) !(k*τ = m)

Например, для схемы SPHINCS-256 имеют место такие параметры n = 256, m =512, h = 60, d = 12, w = 16, t = 2^16, k = 32 _______________________________________________________________________________________________________________

Примитивы

Далее будут рассмотрены примитивы(составные части подписи SPHINCS)

WOTS+[6]

На входе имеются параметры n и w. 

     - Определить l1  и l2:

     - Использовать функцию F (F:{0,1}Шаблон:Sup→{0,1}Шаблон:Sup) для построения 
       следующей "связывающей функции"(Chaining function)
  • Chaining function ci(x,r)

На входе имеется значение x∈{0, 1}Шаблон:Sup, счетчик итераций i∈N, и матрица битовых масок r = (r1, . . . , rj) ∈ {0, 1}Шаблон:Sup, где j ≥ i 

     - Если   i = 0, c возвращает x(cШаблон:Sup(x, r) = x
     - Для    i > 0  функция определяется рекурсивно: ci(x,r) = F(cШаблон:Sup(x, r) ⊕ ri)
  • Key Generation Algorithm (sk, pk ← WOTS.kg(S, r))

На входе имеется некоторое значение(семя) S∈{0, 1}Шаблон:Sup и матрицу битовых масок r = (rШаблон:Sub, . . . , rШаблон:Sub)∈{0, 1}Шаблон:Sup 

     - Вычислить секретный ключ: sk = (skШаблон:Sub, . . . ,skШаблон:Sub) ← GШаблон:Sub(S)
     - Вычислить открытый ключ:  pk = (pkШаблон:Sub, . . . , pkШаблон:Sub) = (cШаблон:Sup(skШаблон:Sub, r), . . . , cШаблон:Sup(skШаблон:Sub, r))
!Семя S занимает меньше памяти, чем ключи, поэтому их можно вычислять по мере необходимости
  • Signature Algorithm (σ ← WOTS.sign(M, S, r))

На входе имеется значение(семя) S∈{0, 1}Шаблон:Sup, матрица битовых масок r, и n-битное сообщение M 

     - Вычислить представление сообщения M в поле Fw: M = (M1 . . . MШаблон:Sub), MШаблон:Sub ∈ {0, . . . , w − 1}
     - Вычислить контрольную сумму   C  = ∑Шаблон:Sup Шаблон:Sub(w − 1 − MШаблон:Sub) 
       И её представление в поле Fw: C = (CШаблон:Sub, . . . , CШаблон:Sub)
     - Вычислить конкатенацию M||C : B = (bШаблон:Sub, . . .,bШаблон:Sub) = M || C
     - Вычислить подпись             σ = (σШаблон:Sub, . . . , σШаблон:Sub) = (cШаблон:Sup(skШаблон:Sub, r), . . . , cbШаблон:Sup(skШаблон:Sub, r))
  • Verification Algorithm (pk' ← WOTS.vf(M, σ, r))

На входе имеется значение матрицы битовых масок r, n-битное сообщение M, и подпись σ 

     - Вычислить bШаблон:Sub, 1 ≤ i ≤ l так же, как описано в алгоритме генерации подписи
     - Вычислить открытый ключ на стороне приема pk' = (pk'Шаблон:Sub, . . . , pk'Шаблон:Sub) = (cШаблон:Sup(σШаблон:Sub, rШаблон:Sub), . . . , cШаблон:Sup(σШаблон:Sub,rШаблон:Sub))

!Подпись считается верной, если вычисленный на стороне приема открытый ключ pk'совпадает с сеансовым отрытым ключом
Бинарное дерево хешей, использующееся в схеме SPHINCS[6]
Файл:Binary hash tree.png
Бинарное дерево хешей

Бинарное дерево высоты h. Оно всегда имеет 2Шаблон:Sup листьев, которые содержат n-битные строки LШаблон:Sub, i ∈ [2Шаблон:Sup − 1]. Для вычисления остальных узлов дерева NШаблон:Sub используется битовая маска подходящей длины QШаблон:Sub ∈ {0, 1}Шаблон:Sup, 0 < j ≤ h. NШаблон:Sub вычисляются по следующему алгоритму: 

             NШаблон:Sub = H((NШаблон:Sub||NШаблон:Sub) ⊕ QШаблон:Sub )
HORST[6]
  • Key Generation Algorithm (pk ← HORST.kg(S, Q))

На входе имеется некоторое значение(семя) S∈{0, 1}Шаблон:Sup и матрица битовых масок Q∈ {0, 1}Шаблон:Sup 

        - Вычислить секретный ключ            sk = (skШаблон:Sub, . . . ,skШаблон:Sub) ← GШаблон:Sub(S)
        - Вычислить значение листьев дерева   LШаблон:Sub = F(skШаблон:Sub),   для i ∈ [t − 1]
        - Построить бинарное дерево хешей высотой log(t), используя матрицу битовых масок Q()
        - Положить в качестве открытого ключа pk значение корня бинарного дерева хешей
  • Signature Algorithm m ((σ, pk) ← HORST.sign(M, S, Q))

На входе имеется значение(семя) S∈{0, 1}Шаблон:Sup, матрица битовых масок Q∈ {0, 1}Шаблон:Sup и сообщение M ∈ {0, 1}Шаблон:Sup 

        - Вычислить секретный ключ sk как описано выше
        - Разбить сообщение на k битовых строк длиной log(t) каждая:  M = (MШаблон:Sub, . . . , MШаблон:Sub). 
          Интерпретировать каждую строку как беззнаковое целое число
        - Составить подпись σШаблон:Sub = (skШаблон:Sub, AuthШаблон:Sub) для i ∈ [k−1]. Подпись включает в себя Mi-ый элемент секретного ключа и данные
          необходимые для нахождения корня бинарного дерева хешей.
        - Добавить к подписи открытый ключ
  • Verification Algorithm (pk' ← HORST.vf(M, σ, Q))

На входе имеется подпись σ, матрица битовых масок Q∈ {0, 1}Шаблон:Sup и сообщение M ∈ {0, 1}Шаблон:Sup 

        - Разбить сообщение на k битовых строк длиной log(t) каждая:  M = (MШаблон:Sub, . . . , MШаблон:Sub). Интерпретировать каждую строку как
           беззнаковое целое число MШаблон:Sub
        - Вычислить значение корня бинарного дерева хешей для каждого MШаблон:Sub. Это легко сделать, так как подпись содержит все
          необходимое для построения дерева: листья LШаблон:Sub = F(σШаблон:SupШаблон:Sub), вспомогательные данные для продвижения вверх по дереву
          Q и AuthШаблон:Sub = σШаблон:SupШаблон:Sub
        - Сравнить вычисленные значения корня дерева с переданным открытым ключом. Если совпадают, то подпись верна

SPHINCS[6]

Логическая структура схемы SPHINCS

SPHINCS представляет из себя «гипердерево» высоты h, которое состоит из d слоёв. Каждый слой представляет из себя деревья высотой h/d. Каждое из деревьев является бинарным деревом хешей и имеет описываемую ниже структуру. Листья каждого дерева содержат в себе открытые ключи схемы WOTS+. При этом корни деревьев одного слоя, оказываются подписаны по той же схеме WOTS+, примененной к дереву на старшем(ближе к корню) слое. !Слой, содержащий одно единственное дерево, договоримся нумеровать индексом d-1, индекс каждого последующего слоя будем получать вычитанием единицы. И так до слоя с индексом 0. Листья деревьев нулевого слоя(они же пары ключей схемы WOTS+) имеют значения открытых ключей схем HORST

Key Generation Algorithm ((SK, PK) ← kg(1Шаблон:Sup)

    -Сгенерировать два n-битных секретных ключа (SK1, SK2) ∈ {0, 1}Шаблон:Sup × {0, 1)Шаблон:Sup
         SK1 используется для псевдослучайной генерации вспомогательных ключей
         SK2 используется для непредсказуемого выбора индексов "гипердерева" и для того, 
             чтобы сделать случайным хеширование сообщения
    - Сгенерировать матрицу n-битных масок с равномерным распределением избыточного размера 
      Q ← {0, 1}Шаблон:Sup, достаточного для использования в схемах WOTS+, HORST и построений 
      деревьев хешей.
    - Осталось сгенерировать значение корня единственного дерева на слое d-1.
      Для этого вычислить специальное значение(семя) с помощью адреса, первого секретного 
      ключа и псевдослучайной функции: SШаблон:Sub ← KШаблон:Sub(A, SKШаблон:Sub), где A = (d − 1||0||i). 
      Инициализируем значение листьев дерева, поставив им в соответствие значения ключа, 
      вычисленного по схеме WOTS+: pkШаблон:Sub ← WOTS.kg(SШаблон:Sub, QШаблон:Sub ). Используя матрицу битовых 
      масок Q, построить бинарное дерево хешей и вычислим значение корня
    - Положить открытый ключ PKШаблон:Sub равным корню "гипердерева"

Signature Algorithm (Σ ← sign(M, SK))

На входе имеется сообщение M ∈ {0, 1}Шаблон:Sup и секретный ключ (SK1, SK2,Q) 

    - Вычислить контрольную сумму сообщения D. Для этого нужно сгенерировать псевдослучайное 
      R = (RШаблон:Sub, RШаблон:Sub) ∈ {0, 1}Шаблон:Sup × {0, 1}Шаблон:Sup(R ← E(M, SKШаблон:Sub)). 
      Затем, собственно, сгенерировать саму контрольную сумму D ← M(RШаблон:Sub, M), используя первые n-бит числа R.
    - Использовать последние n-бит числа R для определения индекса пары ключей схемы HORST i.
    - Вычислить подпись и открытый ключ по схеме HORST:  
      (σШаблон:Sub, pkШаблон:Sub) ← (D, SШаблон:Sub ,QШаблон:Sub), используя специальное значение(семя)
      SШаблон:Sub ←Ka(AHORST, SKШаблон:Sub) и матрицу битовых масок, где AШаблон:Sub = (d||i(0,(d −1)h/d)||i((d − 1)h/d, h/d))

    - Заполнить "гипердерево", на каждом слое(от 0 до d-1) выполняя один и тот же алгоритм: 
      принять значения в листьях за открытый ключ схемы WOTS+, вычислить подпись по схеме WOTS+,
      заполнить узлы деревьев слоя по правилам построения бинарного дерева хешей.
    - Использовать в качестве подпись схемы SPHINCS такую структуру
      Σ = (i, RШаблон:Sub, σШаблон:Sub, σШаблон:Sub, AuthШаблон:Sub, . . . , σШаблон:Sub, AuthШаблон:Sub), где Auth это вспомогательные данные для
      вычисления корня дерева, начиная с соответствующего листа

Verification Algorithm (b ← vf(M, Σ, PK))

На входе имеется сообщение M ∈ {0, 1}Шаблон:Sup, подпись Σ и открытый ключ PK 

    - Вычислить контрольную сумму сообщения D ← H(RШаблон:Sub, M)
    - Вычислить открытый ключ схемы HORTS pkШаблон:Sub ← HORST.vf(D, σШаблон:Sub, QШаблон:Sub), используя подпись этой схемы σШаблон:Sub.
      Проверить правильность данной подписи. Если она не верна, то не верна и подпись общей схемы SPHINCS
    - Проверить подписи для схем WOTS+ на каждом слое "гипердерева":  
      pkШаблон:Sub ← WOTS.vf(pkШаблон:Sub или pkШаблон:Sub, σШаблон:Sub, QШаблон:Sub), вычисляя корни бинарных деревьев хешей.
    - Проверить совпадение PKШаблон:Sub = RootШаблон:Sub. Если равенство верно, то вынести вердикт о правильности подписи

Пример подписи на основе SPHINCS

На примере SPHINCS-256[7] можно увидеть как можно сочетать параметры схемы SPHINCS для обеспечения требований безопасности(128-бит даже при использовании квантового компьютера), а также требований к размерам подписей и ключей

Примечания

Шаблон:Примечания

Дополнительная литература

Ссылки

Шаблон:Изолированная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Cite web
  6. ↑ 6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 Шаблон:Статья
  7. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:SPHINCS&oldid=8797600