Комментарии 72
Спасибо за статью.
Сложно то оно сложно, но не обязательно сильно вникать, чтобы сгенерить себе сертификат, например. Просто выбираешь заранее посчитанную кривую с желаемым количеством бит и всё. В кишках RSA тоже мало кто парит, но пользуются же.
Сложно то оно сложно, но не обязательно сильно вникать, чтобы сгенерить себе сертификат, например. Просто выбираешь заранее посчитанную кривую с желаемым количеством бит и всё. В кишках RSA тоже мало кто парит, но пользуются же.
В принципе согласен конечно. Если использовать проверенные библиотеки типа openSSL, то ошибок будет значительно меньше. Просто я полез в описание стандарта ECDSA, а там алгоритмы, алгоритмы, алгоритмы. Каждое генерируемое число проверяется, чтоб выполнялись определенные критерии. Я понимаю в RSA тоже есть свои тонкости, но их там все таки поменьше. А чем сложнее система, тем вероятность ошибки больше.
В RSA тонкостей очень много. Описание алгоритма простое, но есть куча деталей, которые могут обрушить всю защиту в момент.
Недавно выполнял домашнее задание из курса на Coursera, так там было задание, где p и q находятся недалеко друг от друга. Т. е. они большие, случайные, но просто |p — q| достаточно мал. Ключи можно было посчитать за O(1) :)
Недавно выполнял домашнее задание из курса на Coursera, так там было задание, где p и q находятся недалеко друг от друга. Т. е. они большие, случайные, но просто |p — q| достаточно мал. Ключи можно было посчитать за O(1) :)
Помню помню) Тоже прорешал все задачи к тому курсу, весьма познавательно.
разве O(1)? всё-таки, брутфорс от корня, просто очень мало надо проверять вариантов…
Именно O(1) (не считая сложности арифметики с большими числами).
Там было три задания, в первом числа близко — O(1), во втором числа чуть дальше, там брутфорс — но очень быстрый, в третьем чуть более сложная формула зависимости, но находится опять-таки за O(1).
И есть ссылка на исследование, которое обобщает ускорение факторизации при известных старших битах: dl.acm.org/citation.cfm?id=1754517
Там было три задания, в первом числа близко — O(1), во втором числа чуть дальше, там брутфорс — но очень быстрый, в третьем чуть более сложная формула зависимости, но находится опять-таки за O(1).
И есть ссылка на исследование, которое обобщает ускорение факторизации при известных старших битах: dl.acm.org/citation.cfm?id=1754517
У эллиптических кривых над полем GF(2^m), а это поля расширений с модулями и необходимо задавать неприводимый многочлен.
Такой многочлен не просматривается ни в тексте ни в комментариях
Такой многочлен не просматривается ни в тексте ни в комментариях
А как (и почему) был взломан алгоритм подписи архивов WinRAR? Помню там как раз использовались эллиптические кривые.
Соответственно мы можем представить умножение числа k на точку G как G+G+..+G с k слагаемыми.
Судя по алгебраическому представлению, операция сложения точки с самой собой не определена.
Да вы правы, сложение двух одинаковых точек вычисляет по другому закону. Не стал заострять на этом особого внимания, т.к. все что касается математики на эллиптических кривых уже достаточно хорошо освещено в рунете. Например на википедии есть алгебраическое описание сложения двух точек
Но тогда зачем статья, если все и так есть в интернете?
Чтобы люди имели представление, о чем эти разговоры про «эллиптику». А заострять внимание на мелочах в роде того, что не всегда прямая пересекает кривую еще раз — слишком занудно получилось бы.
Почему? Предельным переходом отлично определяется так: строим касательную к этой точке, где пересечёт — там 2x.
В точках излома не определено.
Где вы нашли точки излома в гладких кривых?
Во-первых, излом будет на кривых с дискриминантом, равным нулю, а мы о них не говорим — они «слабые».
Во-вторых, в данном случаев в точках излома касательная доппределяема. Вы можете определить «касательную справа» от излома и «слева» (относительно картинок в статье — это «снизу» и «сверху»), и на кривых указанного вида эти касательные совпадут, так что их можно принять как значение касательной в точке излома. Это называется «устранимый разрыв первого рода» (в самой точке не определено, но существуют пределы справа и слева, и они совпадают, так что значениями пределов можно устранить разрыв).
Во-вторых, в данном случаев в точках излома касательная доппределяема. Вы можете определить «касательную справа» от излома и «слева» (относительно картинок в статье — это «снизу» и «сверху»), и на кривых указанного вида эти касательные совпадут, так что их можно принять как значение касательной в точке излома. Это называется «устранимый разрыв первого рода» (в самой точке не определено, но существуют пределы справа и слева, и они совпадают, так что значениями пределов можно устранить разрыв).
Спасибо автору, довольно содержательно, не так давно также разбирался с этим вопросом.
Единственное, что можно было бы добавить, это атака с помошью Pollard’s rho method, которая очень хорошо распараллеливается, на хабре вроде как была статья про кластер из PS3 на котором ломали 112-битный ключ. Если кому интересны детали: Solving a 112-bit Prime Elliptic Curve Discrete
Logarithm Problem on Game Consoles using Sloppy Reduction, написано хорошо практически с самых низов.
Единственное, что можно было бы добавить, это атака с помошью Pollard’s rho method, которая очень хорошо распараллеливается, на хабре вроде как была статья про кластер из PS3 на котором ломали 112-битный ключ. Если кому интересны детали: Solving a 112-bit Prime Elliptic Curve Discrete
Logarithm Problem on Game Consoles using Sloppy Reduction, написано хорошо практически с самых низов.
Как-то вы лихо перешли от вещественной кривой к кольцу вычетов и кривой над полем Галуа. Этот же переход — самое интересное! На каком основании утверждается, что это одно и то же? Как это вы так предлагаете данные, относящиеся к непрерывным кривым, применять к дискретным?
Не стал даже пытаться описать матиматические аспекты эллиптических кривых над конечным полем, потому что во первых: не ставил перед собой такой задачи, хотел в общей, как можно более доступной, форме описать что такой эллиптическая криптография. А во-вторых: если говорить честно сомневаюсь что мне бы хватило математических знаний вникнуть во все эти матановские дебри.
А про применение данных относящихся к непрерывним кривым в криптографии я вроде не писал. А наоборот сразу оговорился, что под эллиптической кривой в криптографии понимается всего лишь набор точек.
А про применение данных относящихся к непрерывним кривым в криптографии я вроде не писал. А наоборот сразу оговорился, что под эллиптической кривой в криптографии понимается всего лишь набор точек.
Тогда зачем нужна первая половина статьи (про вещественные кривые)? Она вообще абсолютно из другой оперы, никак не связана со второй половиной и, в общем, только занимает место и время у тех, кто читает. А они ещё думают, что это что-то значит.
Первая половина статьи нужна для того чтобы ввести читателей в курс дела, что такое эллиптическа кривая, дать определение «сложение точек», без которого вообще было бы непонятно что такое kG и как это можно вычислить
Так каким образом оно вводит в курс дело? В какой курс? Связи-то со второй половиной вообще никакой нет. Вы не поясняете, какое отношение вещественная кривая вида y^2 = x^2+x+1 имеет к полю Галуа. С какого перепугу вообще это поле похоже на кривую? Кривая — она вон нарисована, а поле — так это конечный набор чисел. Каким образом набор чисел похож на кривую?
На кривой понятно, складываем таким образом. А как из этого понять, каким образом происходит сложение в кольце? Если бы можно было это понять, это да, было бы введение в курс дела. А сейчас это объяснение в духе: вот у нас есть частица, она как бы одновременно волна. А теперь запишем уравнение Клейна-Гордона. А потом называть первое предложение «введением в курс дела».
На кривой понятно, складываем таким образом. А как из этого понять, каким образом происходит сложение в кольце? Если бы можно было это понять, это да, было бы введение в курс дела. А сейчас это объяснение в духе: вот у нас есть частица, она как бы одновременно волна. А теперь запишем уравнение Клейна-Гордона. А потом называть первое предложение «введением в курс дела».
Хорошо. Учел ваше замечание и добавил следующий текст:
Надеюсь, теперь это можно назвать введением в курс дела?)
Все математические операции на эллиптических кривых над конечным полем производятся по законам конечного поля над которым построена эллиптическая кривая. Т.е. для вычисления, например, суммы двух точек кривой E над кольцом вычетов все операции производятся по модулю числа p.
Надеюсь, теперь это можно назвать введением в курс дела?)
Речь вроде бы шла об Эллиптических кривых (ЭК), а это что «вещественная кривая вида y^2 = x^2+x+1», где ЭК — то. Вижу только конику. А народ плюсует!
а как же особая точка «О»? Про нее даже упоминания нет в статье, а это нейтральный элемент как никак :)
Без него бы не было все так математически красиво.
Без него бы не было все так математически красиво.
ждем продолжения статей про криптографию, но не только сетевую.
вот, например, достойный претендент на обзор — XTEA
ru.wikipedia.org/wiki/XTEA
вот, например, достойный претендент на обзор — XTEA
ru.wikipedia.org/wiki/XTEA
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA.
Причина этому только одна — Windows XP, которая до сих пор крайне распространена, не поддерживает ECC-сертификаты.
Часть ведущих центров сертификации (например, Symantec и их бренды) уже умеют выписывать ECC-сертификаты, мы даже иногда даём их клиентам :)
Когда мы говорим про умножение на скаляр, G' = k*G = G+G+...+G (k раз), а потом нахождение множителя k называем дискретным логарифмом, это выглядит как-то… внезапно.
Но если бы мы говорили не про сложение, а про умножение, G' = G*G*...*G (k раз), то эта операция называлась бы возведением в степень, G' = Gk, а обратная операция к возведению в степень и есть логарифм: k = logG(G')
Разумеется, это вопрос в именовании. Нет большой разницы, как назвать единственную операцию в группе, если мы не делаем из группы кольцо.
Но существуют же традиции.
Но если бы мы говорили не про сложение, а про умножение, G' = G*G*...*G (k раз), то эта операция называлась бы возведением в степень, G' = Gk, а обратная операция к возведению в степень и есть логарифм: k = logG(G')
Разумеется, это вопрос в именовании. Нет большой разницы, как назвать единственную операцию в группе, если мы не делаем из группы кольцо.
Но существуют же традиции.
Тема действительно очень интересная, много чего в ней есть для исследований.
Меня, когда я пытался реализовать протокол криптографический с использованием EC в учебных целях, сбило с толку, что нет заведомо быстрых алгоритмов по подсчету (генерации) точек эллиптической кривой. Преподаватель меня направил в сторону алгоритма Чуфа для расчета точек EC, но там в описании все довольно сложно. Может, кто знает какие быстрые способы для генерации точек EC (со словарным описанием)? Может, модули нужно по особому генерить, чтобы знать наверняка количество точек?
p.s. Конечно можно (а, скорее всего, лучше) использовать кривые, опубликованные в стандартах. Все-таки их свойства проверены должны быть, но для практики хотелось бы свою кривую получить :)
Меня, когда я пытался реализовать протокол криптографический с использованием EC в учебных целях, сбило с толку, что нет заведомо быстрых алгоритмов по подсчету (генерации) точек эллиптической кривой. Преподаватель меня направил в сторону алгоритма Чуфа для расчета точек EC, но там в описании все довольно сложно. Может, кто знает какие быстрые способы для генерации точек EC (со словарным описанием)? Может, модули нужно по особому генерить, чтобы знать наверняка количество точек?
p.s. Конечно можно (а, скорее всего, лучше) использовать кривые, опубликованные в стандартах. Все-таки их свойства проверены должны быть, но для практики хотелось бы свою кривую получить :)
Да, тема невероятно интересная согласен. И ЭЦП это еще только видимая часть айсберга. Те же самые суперсингулярные кривые, которые очень слабы для ЭЦП используются в личностной криптографии, и там их «слабость» это как раз преимущество.
PS про алгоритм Шуфа можно почитать у Василенко «Теоретико численные методы в криптографии».
PS про алгоритм Шуфа можно почитать у Василенко «Теоретико численные методы в криптографии».
Можно генерировать кривые с заранее известным числом точек при некоторых условиях: habrahabr.ru/post/189618/.
Вопрос для тех, кто понял теорию эллиптической криптографии:
Пусть есть известная точка на эллиптической кривой, назовем ее G. И есть число n. n1=n*G. Вопрос, доказано ли, что не существует такой точки G1, которая дает противоположный эффект, то есть n1*G1=n для любого n?
Пусть есть известная точка на эллиптической кривой, назовем ее G. И есть число n. n1=n*G. Вопрос, доказано ли, что не существует такой точки G1, которая дает противоположный эффект, то есть n1*G1=n для любого n?
Что-то либо я не понимаю, либо у Вас изначально неправильный посыл.
n1 — будет точкой EC.
Операции <точка>*<точка>=<число> в поле EC нет. Есть только <точка>+<точка>=<точка> и <число>*<точка>=<точка>.
n1 — будет точкой EC.
Операции <точка>*<точка>=<число> в поле EC нет. Есть только <точка>+<точка>=<точка> и <число>*<точка>=<точка>.
да, извиняюсь, перепутал. Идея была в том, что при обмене ключами стороны передают na*G и nb*G. И как из этой информации возможно было бы вычислить na*nb*G, не зная ни na ни nb.
Алиса (А) придумывает число Na
Боб (B) придумывает число Nb
Стороны согласовывают параметры протокола (открытые).
А -> B следующее сообщение: Na*G
B -> A следующее сообщение Nb*G
А умножает Na*(Nb*G) = Na*Nb*G
B умножает Nb*(Na*G)=Na*Nb*G
Вуа-ля. Общий секретный ключ. Вычислить Na и Nb — равносильно разрешению трудноразрешимой задачи о нахождении дискретного логарифма в поле EC.
Я это себе так представлял :)
Хотя, возможно, где-то и просчитался.
Боб (B) придумывает число Nb
Стороны согласовывают параметры протокола (открытые).
А -> B следующее сообщение: Na*G
B -> A следующее сообщение Nb*G
А умножает Na*(Nb*G) = Na*Nb*G
B умножает Nb*(Na*G)=Na*Nb*G
Вуа-ля. Общий секретный ключ. Вычислить Na и Nb — равносильно разрешению трудноразрешимой задачи о нахождении дискретного логарифма в поле EC.
Я это себе так представлял :)
Хотя, возможно, где-то и просчитался.
Ну да, вроде бы так происходит. А теперь представим себе, что нам удалось ввести для двух точек кривой операцию, как векторное умножение G1*G2=G3. Если бы такое удалось, то для дешифровки достаточно было бы найти точку кривой обратную относительно такого произведения. Но я подозреваю, что такое умножение невозможно ввести. Вопрос только, почему?
Потому что умножение не определно изначально как операция над точками. Нету умножения. Совсем. Есть только сложение двух точек, в том числе точки с самой собой.
А умножение на число это в общем — то и не умножение, а просто сложение точки с самой собой определённое количество раз. Т.е. n*G = G + G + G… n раз. Просто умножение на число это удобное представление такого вот длинного сложения.
А умножение на число это в общем — то и не умножение, а просто сложение точки с самой собой определённое количество раз. Т.е. n*G = G + G + G… n раз. Просто умножение на число это удобное представление такого вот длинного сложения.
Для этого и приводят вводную геометрическую часть, где вводится операция сложения точек. Взяли две точки, провели через них прямую, нашли где пересакает и отразили относительно икс. Такая операция есть и удовлетворяет всем свойствам сложения и не зависит от выбора начальной точки и т.д. и т.п. Специально для этого вводят бесконечность, то бишь ноль. А операции умножения нету. К примеру тогда понадобилась точка, которая бы при умножении на все другие точки давала их же, то бишь еденица. Где такую взять? Если Вы придумаете как такое умножение провернуть, то да, сразу получите все биткоины и прочие секреты :)
Чтобы математически это доказать/опровергнуть нужно почитать книжек.
Векторное умножение… первой страницей в гугле выпала Вики, где векторным произведением будет перпендикуляр к плоскости… Отсюда пропадет замкнутость операции. Выходит, неприменимо для EC.
Векторное умножение… первой страницей в гугле выпала Вики, где векторным произведением будет перпендикуляр к плоскости… Отсюда пропадет замкнутость операции. Выходит, неприменимо для EC.
О! Вот этого, как работает собственно криптография, в статье нет.
Получается, это известный Диффи-Хеллман, но не над обычной числовой группой, а над более сложной.
Получается, это известный Диффи-Хеллман, но не над обычной числовой группой, а над более сложной.
Нельзя путать число и точку. Точка имеет две координаты, а число?
Что-то я такое смутно припоминаю, что в ГОСТ как-то используются криптография на эллиптических кривых?
Один из примеров использования ECDSA на практике — криптовалюта Bitcoin, где данный алгоритм применяется для подписи транзакций.
Хотел добавить, что криптография на эллиптических кривых, к сожалению, не устойчива к отаке на квантовом компьютере. Вероятно, можно рассчитывать, что в ближайшие 10-20 лет квантовых компьютеров необходимого размера построено не будет, но тем не менее.
НЛО прилетело и опубликовало эту надпись здесь
Разложили по полочкам.
Интересно. Название мифической «точки G» родом из эллиптической криптографии ))
Вопрос в том, насколько сложно восстановить M зная параметры кривой E(a,b), шифротекст С и точку G.
Достаточно найти точку G, и тогда она вам расскажет любую тайну. :-)
G — известна. Является частью протокола и передается вместе с открытым ключом ;-)
Я подозреваю, это была такая шутка.
Товарищи, давайте говорить правду:
Сингулярных эллиптических кривых не существует. Все ЭК — гладкие (non-singular). Последние две кривые на графиках — это кривые, живущие в аффинном пр-ве, т.е. к эллиптическим кривым не относятся.
Первый параграф первой главы
В то время как две нижние кривые относятся к т.н. сингулярным эллиптическим кривым.
Сингулярных эллиптических кривых не существует. Все ЭК — гладкие (non-singular). Последние две кривые на графиках — это кривые, живущие в аффинном пр-ве, т.е. к эллиптическим кривым не относятся.
Первый параграф первой главы
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Эллиптическая криптография: теория