Здравствуйте, дорогие хабровчане! Поскольку я делаю все возможное в криптографии для своих скромных нужд, пытаясь поддерживать достойный уровень безопасности данных (я ориентируюсь на уровни, указанные в разделе шифрования).
здесь ) Я начал беспокоиться о падении производительности при использовании криптоалгоритма RSA. К сожалению, этот алгоритм оказался единственным в openssl, который позволяет шифровать/дешифровать небольшие блоки данных (предположительно, в смысле статьи, ключи для симметричных алгоритмов шифрования) с использованием асимметричных криптографических алгоритмов.
Покопавшись в Интернете, мы выяснили, что: 1. Эль-Гамаль умеет успешно шифровать/дешифровать, но эти операции не реализованы в openssl (есть реализация в libgcrypt).
По производительности Эль-Гамаль в 3 раза быстрее RSA с одинаковой длиной ключа и одинаковой криптографической стойкостью на 1 бит ключа.
2. Криптосистема с эллиптической кривой (ECC) приятно удивила скоростью и криптостойкостью на 1 бит ключа, но операции шифрования/дешифрования на основе ECC не реализованы в openssl. В libgcrypt есть реализация ECC-шифрования, но она очень специфическая.
Короче говоря, зашифрованное сообщение m отображается в точку на эллиптической кривой mG, из которой исходное сообщение m невозможно получить, кроме как путем взлома ECC или перебора всех возможных значений m. 3. ЭХК Менезеса-Вэнстона описана в литературе [1], но имеются замечания о ее «уязвимости» [2] Давайте рассмотрим этот вопрос более подробно.
Немного математики:
Для простоты будем говорить только об эллиптических кривых, вид которых описывается уравнением Вейерштрасса
над полями целых чисел, определяемыми как Zp, где Zp — множество целых чисел, меньших некоторого простого числа p и больших нуля.
Тогда E(p,a,b) – где a,b принадлежат Zp – является эллиптической кривой над полем Zp, определяемой простым числом p и числами a,b. Далее необходимо определить абстрактный нулевой элемент O (если коэффициент уравнения Вейершрасса b не равен 0, то координаты x=0,y=0 можно принять за условную точку O, даже если эта точка не является решением уравнения) и операцию сложения элементов кривой (точек), что даст новую точку, принадлежащую той же кривой.
Естественно, должно оказаться, что P+Q=Q+P, (P+Q)+R = P+(Q+R), P+O=O+P=P и если существует P(x,y), то есть -P=(x,-y) и P+(-P)=P-P=O. Все это математические операции, определенные для группы точек эллиптической кривой.
В литературе [1] можно найти математические подробности определения этих операций.
Вы можете добавлять разные точки (P=G+Q) или точку саму с собой (P=Q+Q).
То, что мы будем говорить об «умножении», — это всего лишь способ сократить запись и не писать P=Q+Q+Q+Q+.
+Q m раз, а просто написать, что P=mQ. На самом деле нет операции «умножения» и соответственно «деления», как нет и «возведения в степень» и «логарифма».
Эту терминологию используют часто, но для эллиптических кривых она означает не то, что под ней обычно понимают. Суммирование точки эллиптической кривой с самой собой m раз можно назвать «умножением на m» или даже «возведением в степень m».
Суть от этого не меняется, а поскольку обратной операции «деление» или «логарифмирование» не существует, то получить m из точки m*G невозможно, даже зная G, говорят о «дискретном Задача логарифмирования на эллиптических кривых».
Это устоявшаяся терминология.
На этой кривой выбирается (произвольная) точка G(Gx,Gy), которая является образующей группы точек, то есть, задавая разные m, получаем результат умножения mG, образующий циклическую группу точек (поскольку мы находимся в конечном поле Zp).
Размер этой циклической группы называется порядком точки образующей G.
Таким образом, эллиптическая группа полностью описывается параметрами кривой E(p,a,b), образующей точки G(Gx,Gy) и порядком группы ord, при этом ord*G=O. Все они называются параметрами эллиптической кривой, которые обычно хорошо известны и обозначаются такими именами, как secp192k1 или prime256v1.
Закрытый ключ пользователя — это (секретный, случайный) номер 1. < d < ord-1
Открытый ключ пользователя — это точка Q, которая является произведением закрытого ключа d и генератора группы G, Q=dG.
Что предлагает криптосистема Менезеса-Ванстона [1] (MVC) на основе эллиптической кривой?
Сторона отправителя: 1. Зашифрованное сообщение m разбивается на две части x1 и x2, каждая из которых должна быть элементом поля Zp; для этого достаточно проверить их длину и сравнить ее с длиной кривой параметра p. 2. Отправитель выбирает (секретное, случайное) число 1. < ks < ord-1. 3. Отправитель умножает точку генератора G на число ks, y0=ks*G. 4. Отправитель вычисляет точку Z(Zx,Zy) путем умножения открытого ключа Q получателя на число ks, Z=ks*Q. 5. Отправитель вычисляет y1=x1*Zx(mod p), y2=x2*Zy(mod p) Вычислительные затраты отправителя: генерация случайного числа необходимой длины, 2 операции умножения точки на число, 2 операции умножения по модулю p. Зашифрованный текст — это точка y0, число y1, число y2. Точка содержит 2 числа — координаты x,y. Общий размер зашифрованного текста составляет примерно 4*p, для длины ключа ECC 192 бита (24 байта) примерно 24*4=96 байт. Получающая сторона: 1. Получатель проверяет принадлежность точки y0 кривой, заданной параметрами E(p,a,b),G,ord. 2. Получатель вычисляет точку Z, умножая зашифрованный текст y0 на свой закрытый ключ d, Z=d*y0=d*ks*G=ks*d*G=ks*Q. 3. Приемник вычисляет мультипликативную обратную компоненту Z(Zx,Zy), e1=inv(Zx)(mod p), e2=inv(Zy)(mod p).4. Получатель восстанавливает x1, x2: x1=y1*e1(mod p), x2=y2*e2(mod p).
Вычислительные затраты для получателя: проверка принадлежности точки кривой, 1 операция умножения точки на число, 2 операции вычисления мультипликативного обращения по модулю p,
2 операции умножения по модулю p.
Уязвимость или слабость MVC
В 1997 году Клаус Кифер [2] показал, что MVC не является вероятностной системой шифрования, вопреки своему замыслу.Зная зашифрованный текст, зная параметры кривой, можно провести «атаку по известному открытому тексту» (атаку с угадыванием открытого текста).
На что это похоже: Параметры кривой E(p,a,b),G,ord известны.
Шифрованный текст y0,y1,y2 известен.
Мы предполагаем, что открытый текст равен x1,x2. Если точка F(f1,f2) f1=y1*(inv(x1))(mod p), f2=y2*(inv(x2))(mod p) принадлежит кривой E(p,a,b) , то с вероятностью ошибки 1/p x1,x2 действительно является искомым открытым текстом.
Что это значит на практике? Найти тот факт, что можно перечислить все значения х1,х2 с вычислительными затратами 2 операций вычисления мультипликативного обращения по модулю р, 2 операций умножения по модулю р для каждого варианта х1,х2 и с вероятностью ошибки 1/р.
открытый текст, соответствующий зашифрованному.
Отрицательный результат теста всегда правильный, положительный может содержать ошибочное распознавание с вероятностью 1/p. Операция перечисления x1,x2 хорошо распараллеливается; многие процессы могут самостоятельно пересчитывать свои непересекающиеся диапазоны значений x1,x2. Для справки: я хотел бы посмотреть на перебор (просто перебор, без вычислений) всех возможных 192- или 256-битных значений ключей.
Да хоть 128-168 бит. Понятно, что перебором можно открыть лишь небольшие фрагменты зашифрованных данных, до 48-64 бит. И этот поиск можно выполнить без MVC; для задачи поиска ключа путем перебора всех возможных значений использование MVC не обязательно, это дополнительная сущность.
Что мы имеем в итоге?
Если вы шифруете тексты достаточно большого размера (128 бит и более), так что их невозможно найти перебором за разумное время и за приемлемую стоимость, эта «уязвимость» не играет никакой роли.Сегодня минимальная рекомендуемая длина ключа ECC составляет 192 бита (24 байта).
Длина зашифрованных данных MVC в этом случае не должна превышать 2*24=48 байт, а самый сильный ключ AES или ГОСТ имеет длину 256 бит (32 байта).
Зато мы получаем криптоустойчивый и достаточно быстрый (по моим оценкам, ECC-224 в 5 раз быстрее RSA-2048, в 3 раза быстрее ElGamal-2048) алгоритм асимметричного шифрования.
Я считаю, что криптосистема Менезеса-Ванстона «Эллиптическая кривая» совершенно незаслуженно забыта.
Пытаясь восполнить этот пробел, выкладываю исходники на C с использованием API openssl. Литература: 1. КОМПЬЮТЕРНАЯ БЕЗОПАСНОСТЬ И КРИПТОГРАФИЯ, АЛАН Г.
КОНХЕЙМ, Опубликовано John Wiley & Sons, Inc., Хобокен, Нью-Джерси, 2007. ISBN-13: 978-0-471-94783-7 ISBN-10: 0-471- 94783-0 2. «Слабость криптосистемы Менезеса-Вэнстона» , Клаус Кифер, член исследовательской группы проф.
Дж.
Бухманн, 1997 г.
Теги: #криптография на основе эллиптических кривых #openssl #открытый ключ #криптография #программирование// // DESCRIPTION 'EC Menezes-Vanstone cryptosystem functions openssl/Linux' // COMPILER 'gcc (GCC) 4.8.2' // FILE 'ecmv.h' // AUTHOR "Nick Korepanov" // Linux-3.10.104, glibc-2.17, OpenSSL 1.0.1u // ECC-192/224/256 // This program is free software; you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation; either version 2 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, //
-
Flipboard Оказался Недоступен В России
19 Oct, 24 -
Сравнение Фондовых Индексов С Ценой Биткойна
19 Oct, 24 -
Занимательная Физика
19 Oct, 24 -
Компактное Хранилище Емкостью 2 Тб.
19 Oct, 24
