Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Пока что криптография на основе хешей ограничивается схемами цифровых подписей , такими как схема подписи Меркла . Схемы подписи на основе хеша сочетают схему одноразовой подписи с древовидной структурой Меркла . Поскольку ключ схемы одноразовой подписи может безопасно подписывать только одно сообщение, целесообразно объединить множество таких ключей в единую более крупную структуру. Для этого используется древовидная структура Меркла. В этой иерархической структуре данных хэш-функция и конкатенация многократно используются для вычисления узлов дерева. Подписи Лампорта являются примером схемы одноразовой подписи, которую можно комбинировать с древовидной структурой Меркла.

В 2019 году Национальный институт стандартов и технологий США объявил о своем намерении обнародовать стандарты для криптографии на основе хэшей с отслеживанием состояния на основе расширенной схемы подписи Меркла (XMSS) и подписей Лейтон-Микали (LMS), которые применимы в различных обстоятельствах. [1]

История [ править ]

Лесли Лэмпорт изобрел подписи на основе хешей в 1979 году. Схемы подписей на основе хешей XMSS (расширенная схема подписи Меркла) [2] и SPHINCS [3] [4] были представлены в 2011 и 2015 годах соответственно. XMSS был разработан группой исследователей под руководством Йоханнеса Бухманна и основан как на оригинальной схеме Меркла, так и на Обобщенной схеме подписи Меркла 2007 года (GMSS). [5] В 2013 году был описан вариант XMSS с несколькими деревьями, XMSS MT . [6]

Схемы одноразовой подписи [ править ]

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

Обычно используемые схемы одноразовой подписи включают схему Лампорта-Диффи, схему Винтерница [7] и ее усовершенствования, такие как схема W-OTS + . [8] В отличие от оригинальной схемы Лэмпорта-Диффи, схема Винтерница и ее варианты могут подписывать сразу несколько битов. Количество битов, которые должны быть подписаны одновременно, определяется значением: параметром Winternitz. Наличие этого параметра обеспечивает компромисс между размером и скоростью. Большие значения параметра Winternitz приводят к коротким подписям и ключам за счет более медленной подписи и проверки. На практике типичное значение этого параметра - 16.

В случае подписей на основе хэша без сохранения состояния используются схемы с малой тактовой подписью. Такие схемы позволяют постепенно снижать безопасность в случае использования кратковременного ключа более одного раза. HORST - это пример схемы кратной подписи.

Объединение множества одноразовых пар ключей в схему подписи на основе хэша [ править ]

Центральная идея схем подписи на основе хэша состоит в том, чтобы объединить большее количество одноразовых пар ключей в единую структуру, чтобы получить практический способ подписания более одного раза (но ограниченное количество раз). Это делается с использованием древовидной структуры Меркла с возможными вариациями. Один открытый и один закрытый ключи состоят из множества открытых и закрытых ключей базовой одноразовой схемы. Глобальный открытый ключ - это единственный узел на самом верху дерева Меркла. Его значение является результатом выбранной хеш-функции, поэтому типичный размер открытого ключа составляет 32 байта. Действительность этого глобального открытого ключа связана с действительностью данного одноразового открытого ключа с использованием последовательности узлов дерева. Эта последовательность называется путем аутентификации. Он хранится как часть подписи,и позволяет верификатору восстановить путь узла между этими двумя открытыми ключами.

Глобальный закрытый ключ обычно обрабатывается с помощью генератора псевдослучайных чисел. Тогда достаточно сохранить начальное значение. Одноразовые секретные ключи выводятся последовательно из начального значения с помощью генератора. При таком подходе глобальный частный ключ также очень мал, например, обычно 32 байта.

Проблема обхода дерева имеет решающее значение для производительности подписи. Были внедрены все более эффективные подходы, значительно ускоряющие время подписания.

Некоторые схемы подписи на основе хешей используют несколько уровней дерева, предлагая более быстрое подписание по цене более крупных подписей. В таких схемах только самый нижний слой деревьев используется для подписи сообщений, в то время как все остальные деревья подписывают корневые значения нижних деревьев.

В работе Наор-Юнга [9] показан образец, с помощью которого можно преобразовать ограниченную временную сигнатуру семейства типов Меркла в неограниченную (обычную) схему подписи.

Свойства схем подписи на основе хешей [ править ]

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

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

Поскольку они полагаются на базовую схему одноразовой подписи, схемы подписи на основе хэша могут безопасно подписывать только фиксированное количество сообщений. В случае схем Меркла и XMSS можно безопасно подписать максимум сообщений с общей высотой дерева Меркла.

Примеры схем подписи на основе хешей [ править ]

Начиная с первоначальной схемы Меркла, были введены многочисленные схемы подписи на основе хешей с улучшенной производительностью. Последние включают схемы XMSS, Leighton-Micali (LMS), SPHINCS и BPQS. Большинство схем подписи на основе хешей имеют состояние , что означает, что для подписания требуется обновление секретного ключа, в отличие от обычных схем цифровой подписи. Для схем подписи на основе хешей с отслеживанием состояния подпись требует сохранения состояния используемых одноразовых ключей и обеспечения того, чтобы они никогда не использовались повторно. Схемы XMSS, LMS и BPQS [10] поддерживают состояние, тогда как схема SPHINCS не имеет состояния. Подписи SPHINCS больше, чем подписи XMSS и LMS, а BPQS был разработан специально для систем блокчейн. В дополнение к схеме одноразовой подписи WOTS + ,[8] SPHINCS также использует схему подписи за несколько раз (на основе хеша), называемую HORST. HORST является усовершенствованием более старой схемы коротких тактовых подписей, HORS (Hash to Obtain Random Subset). [11]

Схемы с отслеживанием состояния XMSS и XMSS MT указаны в RFC 8391 (XMSS: расширенная схема подписи Меркла). [12] Хеш-сигнатуры Лейтон-Микали указаны в RFC 8554. [13] В литературе были предложены практические усовершенствования, которые снимают проблемы, связанные со схемами с отслеживанием состояния. [14] Хеш-функции, подходящие для этих схем, включают SHA-2 , SHA-3 и BLAKE .

Реализации [ править ]

В отличие от других популярных сетей блокчейнов и криптовалют, которые используют уже стандартизированные NIST алгоритмы цифровой подписи на эллиптических кривых ( ECDSA ), [15] Quantum Resistant Ledger (QRL) является первой сетью с открытым исходным кодом, в которой реализована расширенная схема подписи Меркла. [16] В отличие от традиционных подписей ECDSA, эта схема подписи с отслеживанием состояния доказано устойчива к достаточно мощному квантовому компьютеру, выполняющему алгоритм Шора . [17] [18]

Схемы XMSS, GMSS и SPHINCS доступны в криптографических API Java Bouncy Castle . [19] SPHINCS реализован в наборе инструментов тестирования SUPERCOP. [20] Существуют оптимизированные [21] и неоптимизированные [22] эталонные реализации XMSS RFC. Схема LMS была реализована на Python [23] и на C [24] после его Интернет-проекта.

Ссылки [ править ]

  1. ^ Отдел компьютерной безопасности, Лаборатория информационных технологий (2019-02-01). «Запрос на общественное обсуждение HBS | CSRC с отслеживанием состояния» . CSRC | NIST . Проверено 4 февраля 2019 .
  2. ^ Бухманн, Йоханнес; Дахмен, Эрик; Хюлсинг, Андреас (2011). «XMSS - Практическая схема прямой безопасной подписи, основанная на минимальных предположениях безопасности». Конспект лекций по информатике . 7071 (Постквантовая криптография. PQCrypto 2011): 117–129. CiteSeerX 10.1.1.400.6086 . DOI : 10.1007 / 978-3-642-25405-5_8 . ISSN 0302-9743 .  
  3. ^ Бернштейн, Дэниел Дж .; Хопвуд, Дайра; Хюлсинг, Андреас; Ланге, Таня ; Нидерхаген, Рубен; Папахристодулу, Луиза; Шнайдер, Майкл; Швабе, Питер; Уилкокс-О'Хирн, Зуко (2015). Освальд, Элизабет ; Фишлин, Марк (ред.). SPHINCS: практические подписи на основе хешей без сохранения состояния . Конспект лекций по информатике. 9056 . Springer Berlin Heidelberg. С. 368–397. CiteSeerX 10.1.1.690.6403 . DOI : 10.1007 / 978-3-662-46800-5_15 . ISBN  9783662467992.
  4. ^ «СФИНКЫ: Введение» .
  5. ^ Бухманн, Йоханнес; Дахмен, Эрик; Клинцевич, Елена; Окея, Кацуюки; Вийом, Камилла (2007). «Подписи Меркла с практически неограниченной подписной способностью». Конспект лекций по информатике . 4521 (Прикладная криптография и сетевая безопасность): 31–45. DOI : 10.1007 / 978-3-540-72738-5_3 .
  6. ^ Хюлсинг, Андреас; Рауш, Леа; Бухманн, Йоханнес (2013). Оптимальные параметры для XMSSMT . Конспект лекций по информатике . 8128 . С. 194–208. DOI : 10.1007 / 978-3-642-40588-4_14 . ISBN 978-3-642-40587-7.
  7. ^ Додс, C .; Смарт, НП; Стам, М. (2005). «Схемы цифровой подписи на основе хеша». Конспект лекций по информатике . 3796 (Криптография и кодирование): 96–115. DOI : 10.1007 / 11586821_8 .
  8. ^ а б Хюлсинг, Андреас (2013). W-OTS + - более короткие подписи для схем подписи на основе хеша . Конспект лекций по информатике . 7918 . С. 173–188. DOI : 10.1007 / 978-3-642-38553-7_10 . ISBN 978-3-642-38552-0.
  9. ^ М. Наор, М. Юнг. «Универсальные односторонние хеш-функции и их криптографические приложения». STOC 1989. [1]
  10. ^ Chalkias, Константинос; Браун, Джеймс; Хирн, Майк; Лиллехаген, Томми; Нитто, Игорь; Шрётер, Томас (2018). «Блокчейн-постквантовые подписи» (PDF) . Материалы Международной конференции IEEE по блокчейну (Cybermatics-2018) : 1196–1203.
  11. ^ Рейзин, Леонид; Рейзин, Натан (2002). Лучше, чем BiBa: короткие одноразовые подписи с быстрой подписью и проверкой . Конспект лекций по информатике . 2384 . С. 144–153. CiteSeerX 10.1.1.24.7320 . DOI : 10.1007 / 3-540-45450-0_11 . ISBN  978-3-540-43861-8.
  12. ^ Хюлсинг, Андреас; Бутин, Денис; Газдаг, Стефан; Rijneveld, Joost; Мохайсен, Азиз. «RFC 8391 - XMSS: расширенная схема подписи Меркла» . tools.ietf.org . IETF.
  13. ^ МакГрю, Дэвид; Курчо, Майкл; Флюрер, Скотт. «RFC 8554 - подписи на основе хэша Лейтон-Микали» . tools.ietf.org . IETF.
  14. ^ МакГрю, Дэвид; Кампанакис, Панос; Флюрер, Скотт; Газдаг, Стефан-Лукас; Бутин, Денис; Бухманн, Йоханнес (2016). «Управление состоянием для подписей на основе хеша» (PDF) . Конспект лекций по информатике . 10074 (Исследование стандартизации безопасности): 244–260. DOI : 10.1007 / 978-3-319-49100-4_11 .
  15. ^ Ван, Личэн; Шэнь, Сяоин; Ли, Цзин; Шао, Цзюнь; Ян, Исянь (01.02.2019). «Криптографические примитивы в блокчейнах» . Журнал сетевых и компьютерных приложений . 127 : 43–58. DOI : 10.1016 / j.jnca.2018.11.003 . ISSN 1084-8045 . 
  16. ^ «Квантово стойкая бухгалтерская книга» . theqrl.org . 2019-08-24.
  17. ^ "Подписи на основе хеша с отслеживанием состояния NIST" (PDF) . NIST . 2019-02-04.
  18. ^ Отдел компьютерной безопасности, Лаборатория информационных технологий (2018-12-20). «Подписи на основе хеша | CSRC» . CSRC | NIST . Проверено 6 сентября 2019 .
  19. ^ "bcgit / bc-java" . GitHub . 2018-12-18.
  20. ^ "СУПЕРКОП" . Архивировано из оригинала на 2015-02-15 . Проверено 31 мая 2017 .
  21. ^ "Код" . Андреас Хюльсинг .
  22. ^ "squareUP> Публикации" . www.pqsignatures.org .
  23. ^ Дэвид, МакГрю (2018-05-29). «Пакет hash-sigs: реализация системы иерархической подписи Лейтон-Микали (HSS)» . GitHub .
  24. ^ Дэвид, МакГрю (2018-11-22). «Полнофункциональная реализация схем подписи на основе хэша LMS и HSS из draft-mcgrew-hash-sigs-07» . GitHub .
  • Т. Ланге. «Подписи на основе хеша». Энциклопедия криптографии и безопасности, Springer, США, 2011. [2]
  • Ф. Т. Лейтон, С. Микали. «Крупные доказуемо быстрые и безопасные схемы цифровой подписи, основанные на одной безопасной хэш-функции». Патент США 5432852, [3] 1995.
  • Г. Беккер. «Схемы подписи Меркла, деревья Меркла и их криптоанализ», семинар «Пост квантовая криптология» в Рурском университете Бохума, Германия, 2008 г. [4]
  • Э. Дахмен, М. Дринг, Э. Клинцевич, Дж. Бухманн, LC Coronado Garcia. «CMSS - Улучшенная схема подписи Меркла». Прогресс в криптологии - Indocrypt 2006. [5]
  • Р. Меркл. «Системы секретности, аутентификации и открытого ключа / Сертифицированная цифровая подпись». Кандидат наук. докторская диссертация, кафедра электротехники, Стэнфордский университет, 1979. [6]
  • С. Микали, М. Якобссон, Т. Лейтон, М. Шидло. «Фрактальное представление дерева Меркла и обход». RSA-CT 03. [7]
  • П. Кампанакис, С. Флюрер. «LMS против XMSS: сравнение предложенных стандартов подписи на основе хеша с отслеживанием состояния». Cryptology ePrint Archive, Отчет 2017/349. [8]
  • Д. Наор, А. Шенгав, А. Вул. «Повторение одноразовых подписей: практические быстрые подписи с использованием фрактального обхода дерева Меркла». 24-я Конвенция инженеров по электротехнике и радиоэлектронике в Израиле, IEEE, 2006 г. [9]

Внешние ссылки [ править ]

  • [10] Прокомментированный список литературы о схемах подписи на основе хешей.
  • [11] Еще один список литературы (без комментариев).