Реализация крипто-системы Merkle и ее анализ
Криптосистемы, основанные на хешировании как альтернатива RSA (криптосистемы открытого ключа) для пост квантовой эпохи. Эффективность генерации открытого ключа, шифрование подписи и ее верификация. Уменьшение размера подписи и оптимизации алгоритма.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 04.12.2018 |
| Размер файла | 250,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1Университет Грузии
Реализация крипто-системы Merkle и ее анализ
Явич Максим Павлович1, Аракелян Артуро Ашотович1
Аннотация
криптосистема хеширование верификация шифрование
Идет активная работа по разработке квантовых компьютеров. Данные компьютеры, используя алгоритм Шора, могут легко взломать системы основанные на факторизации целых чисел. Соответственно самая распространённая криптосистема открытого ключа RSA является уязвимой.
Альтернативой RSA для пост квантовой эпохи являются крипто системы, основанные на хешировании. Безопасность, которых основывается на безопасности хеш-функции. Система Merkle является самой актуальной крипто-системой данного семейства.
В статье приведена реализация алгоритма данной системы и показано, что генерация открытого ключа, шифрование подписи и ее верификация являются довольно эффективными, но длина подписей является большой.
Показано, что данная система является актуальной пост квантовой альтернативой RSA, но нужно провести работу на уменьшением размера подписи и оптимизации алгоритма.
Ключевые слова: безопасность, квантовые комппьютеры, кибер, Пост квантовая криптография, уязвимости
Идет активная работа по разработке квантовых компьютеров. Данные компьютеры, используя алгоритм Шора, могут легко взломать системы основанные на факторизации целых чисел. Соответственно самая распространённая криптосистема открытого ключа RSA является уязвимой [1].
Альтернативой RSA для пост квантовой эпохи являются крипто системы, основанные на хешировании. Безопасность, которых основывается на безопасности хеш-функции. Были предложены системы одноразовых подписей [2]
Данные системы являются неэффективными из-за, передачи открытого ключа множество раз. Криптосистема Меркле улаживает эту проблему. В этой системе один и тот же открытый ключ используется для шифрования множества сообщений. В данной системе генерируются ключи Xi и Yi для N записей и вычисляется hi=h(Yi), и строится дерево Merkle[3,4].
В данном дереве последующий узел является хешированием объединения своих потомков. a1,0 = h(a0,0|| a0,1); Корень дерева an,0 является открытым ключом public.
Для того, чтобы получить подпись мы используем криптосистему одноразовой подписи и объединяем ее с каждым братским узлом. sig = (signew ||auth0||auth1||…||authn?1). Для верификации подписи проверяется одноразовая подпись и открытый ключ, используя братские узлы.
Мы реализовали данный алгоритм, на языке программирования Python, ниже приведен псевдо код данной реализации:
· Importing necessary libs
· Define class
· Defining “ alt_hashes(hashes) “ method
· Set list “ arr ”
· If hashes == “ ”, raise Exception
· Foreach loop
o sorting hashes and appending into arr
· Length_of_block == length of arr
· While loop, if length is odd, copy last element in list
o append it into arr list
· Set list “ another_arr ”
· Foreach loop
o For loop with range from 0 to length of “ arr “ and iteration by 2
§ Define variable with “ sha512() “ value
§ Hash elements that are in “ arr “ list
§ Apennd them into new “ another_arr “ list
§ Return this listin hex
· Set list “ hash_arr ”
· Foreach loop
o Generate Hex and put it into “ hash_arr ” list
· Create message put it in “ st “ variable
· Convert “ st “ value in binary
· First_secret_key = hash_arr[0]
· Second_secret_key = hash_arr[1]
· Generate “ one-time signature ”
o If st == 0
§ Choose “First_secret_key “ bit
o Else
§ Choose “Second _secret_key “ bit
· First_pub_key = hash(hash_arr[0])
· Second_pub_key = hash (hash_arr[1])
· Encryption
o Concatenate “ one-time signature ” with message's hash
· Verification of “ one-time signature ”
o If bit of “ one-time signature ” == 0
§ Compare with “First_secret_key “ bit
o Else
§ Compare with “Second _secret_key “ bit
· Verification of “ signature ”
o Concatenate siblings with each other
o If this equals to public key
§ Sign is correct
o Else
§ Sign is not correct
Мы протестировали данный алгоритм на компьютере с процессором I3 и оперативной памятью 4 гб.
Размер хешированного сообщения составляет 400 бит. Генерация открытого ключа происходит за 0.000835152757866 с., время шифрования сообщения - 0.000888468500357 с., время подтверждения подписи - 0.00144478985986.
Как мы видим мы получили довольно хорошие результаты во времени.
Длина подписи получилась - 166 800 бит. Что является довольно большим размером.
Как мы видим данная система является актуальной пост квантовой альтернативой RSA, но нужно провести работу на уменьшением размера подписи и оптимизации алгоритма.
Библиографический список
1. Gagnidze, M. Iavich, G. Iashvili, Some Aspects of Post-Quantum Cryptosystems, Eurasian Journal of Business and Management, 5(1), 2017
2. Gagnidze A.G., Iavich M.P., Iashvili G.U. Improved version of Merkle crypto system // Modern scientific researches and innovations. 2017. № 5 [Electronic journal]. URL: http://web.snauka.ru/issues/2017/05/81949
3. Buchmann, J., Dahmen, E., Schneider, M.: Merkle tree traversal revisited. 2nd International Workshop on Post-Quantum Cryptography - PQCrypto 2008, LNCS 5299, pages 63-77. Springer, 2008.Dahmen, E., Okeya, K., Takagi, T., Vuillaume, C.: Digital
4. Signatures out of Second-Preimage Resistant Hash Functions. 2nd International Workshop on Post-Quantum Cryptography - PQCrypto 2008, LNCS 5299, pages 109-123. Springer, 2008.
Размещено на Allbest.ru
...Подобные документы
Инфраструктура открытых ключей PKI. Преимущество сетевой архитектуры. Программные средства поддержки PKI. Описание логики работы программы. Форма генерации и экспорта ключа для подписи, создания нового пользователя, добавления нового сертификата.
курсовая работа [450,8 K], добавлен 22.07.2012Разработка криптографического алгоритма программы ручного шифра по таблице Виженера. Разработка программы, выполняющей шифрование и расшифрование. Особенности использования в качестве ключа самого открытого текста. Алгоритмы решения "обратных" задач.
курсовая работа [45,0 K], добавлен 13.11.2009Основные алгоритмы реализации электронной цифровой подписи. Понятие секретного и открытого ключа. Программные модули, сроки действия и порядок функционирования электронной подписи. Технология работы с информационной системой "ЭЦП", перспективы развития.
курсовая работа [1,1 M], добавлен 07.12.2010Традиционные симметричные криптосистемы. Основные понятия и определения. Методы шифрования. Метод перестановок на основе маршрутов Гамильтона. Асимметричная криптосистема RSA. Расширенный алгоритм Евклида. Алгоритмы электронной цифровой подписи Гамаля.
курсовая работа [235,6 K], добавлен 06.01.2017Симметричные и асиметричные методы шифрования. Шифрование с помощью датчика псевдослучайных чисел. Алгоритм шифрования DES. Российский стандарт цифровой подписи. Описание шифрования исходного сообщения асимметричным методом с открытым ключом RSA.
курсовая работа [101,1 K], добавлен 09.03.2009Формирование ключей для шифрования сообщения. Описание алгоритма RSA: шифрование и дешифрование. Понятие и история изобретения криптосистемы с открытым ключом. Свойства односторонней функции и сложность раскрытия шифра. Сущность цифровой подписи.
лабораторная работа [326,0 K], добавлен 04.11.2013Рассмотрение основных понятий криптографии: конфиденциальности, целостности, аутентификации и цифровой подписи. Описание криптографических средств защиты (криптосистемы, принципы работы криптосистемы, распространение ключей, алгоритмы шифрования).
дипломная работа [802,2 K], добавлен 08.06.2013История возникновения криптографии. Открытый ключ криптосистемы. Шифрование секреторного ключа. Математические методы обеспечения конфиденциальности и аутентичности информации. Преобразование текста на основе секретного алгоритма в шифрованный текст.
презентация [260,8 K], добавлен 11.10.2015Закон "Об электронной подписи". Определение, технологии применения и принципы формирования электронной подписи. Стандартные криптографические алгоритмы. Понятие сертификата ключа подписи и проверка его подлинности. Системы электронного документооборота.
презентация [219,0 K], добавлен 19.01.2014История электронной подписи в мире. Создание электронной цифровой подписи в электронном документе с использованием закрытого ключа. Модели атак и их возможные результаты. Алгоритм генерации ключевых пар пользователя. Новые направления в криптографии.
курсовая работа [106,1 K], добавлен 07.06.2014Разложение на простые сомножители. Понятия теории сравнений. Вычисление мультипликативного обратного. Существование конечного поля. Шифрование потока данных. Принцип работы RSA-криптосистемы. Криптографический анализ асимметричных систем шифрования.
дипломная работа [390,4 K], добавлен 14.08.2015Реализация алгоритма DES и режимов шифрования для любой длины сообщения и любой длины ключа. Шифрование сообщений различной длины и ключа с замериванием времени и скорости шифрования. Реализация алгоритма RSA. Сохранение зашифрованного файла на диск.
курсовая работа [398,4 K], добавлен 26.01.2010Симметричные криптосистемы; алгоритмы шифрования и дешифрования данных, их применение в компьютерной технике в системах защиты конфиденциальной и коммерческой информации. Основные режимы работы алгоритма DES, разработка программной реализации ключа.
курсовая работа [129,6 K], добавлен 17.02.2011Общая характеристика электронной подписи, ее признаки и составляющие, основные принципы и преимущества применения. Использование электронной цифровой подписи в России и за рубежом. Правовое признание ее действительности. Сертификат ключа проверки ЭЦП.
курсовая работа [27,2 K], добавлен 11.12.2014Симметрическое шифрование как способ шифрования, в котором применяется один и тот же криптографический ключ. Функции стандартного диалогового окна открытия и сохранения файла. Характерная схема действий при генерации подписи. Цифровая подпись файла.
курсовая работа [641,5 K], добавлен 14.06.2011Назначение и особенности применения электронной цифровой подписи, история ее возникновения, алгоритмы, схемы. Использование хэш-функций. Подделка подписей, модели атак и их возможные результаты. Управление ключами открытого типа. Хранение закрытого ключа.
презентация [883,5 K], добавлен 18.05.2017Организационно-правовое обеспечение электронной цифровой подписи. Закон "Об электронной цифровой подписи". Функционирование ЭЦП: открытый и закрытый ключи, формирование подписи и отправка сообщения. Проверка (верификация) и сфера применения ЭЦП.
курсовая работа [22,9 K], добавлен 14.12.2011Состав, параметры технических средств. Выработка общего ключа для шифрования/расшифровки сообщения. Структура подключения ПЛИС с персональным компьютером по Ethernet. Модули формирования электронно-цифровой подписи. Архитектура стандарта Gigabit Ethernet.
дипломная работа [3,6 M], добавлен 13.09.2017Криптографические методы обеспечения конфиденциальности, невозможности прочтения информации посторонним. Современные методы шифрования информации как обратимого преобразования открытого текста в шифрованный на основе секретного алгоритма или ключа.
презентация [514,3 K], добавлен 06.02.2016Основы криптографических систем. Алгоритм создания открытого и секретного ключей. Схема передачи шифрованной информации и алгоритм для цифровой подписи. Преимущества и недостатки системы RSA. Основные формулы для создания RSA-ключей шифрования.
курсовая работа [683,6 K], добавлен 18.12.2011
