Результаты поиска по запросу «[эллиптические кривые]» / Хабр

Как стать автором

Публикации Хабы Компании Пользователи Комментарии

Scratch 10 июня 2010 в 19:23

Некоторые аспекты разработки платежных систем. Часть II. One time passwords и ECDSA

Платежные системы *

Доброго здравия, %username%!

В первой части я рассказал как можно минимальными усилиями защитить БД нашей платежной системы. Но, как заметил один из комментирующих, при компрометации web сервера появляется возможность подсмотреть все логины и пароли пользователей. Тут нам на помощь приходят One time passwords (OTP).
Под катом моя вольная интерпритация данного термина с использованием криптографии эллиптических кривых (ECC). Кстати говоря, платежные системы далеко не единственная сфера применения этой технологии.
Upd:
Ахтунг! При взломе веб сервера все таки есть вероятность подмены платежных реквизитов, так что все таки подписывать лучше не случайную строку (хоть это и защитит от полной компрометации системы, но не защитит от случаев, когда подменяются реквизиты прямо во время платежа), а хэш платежного документа, показывая юзеру при этом все реквизиты платежа в программе.
З.Ы. Генерировать ключ лучше тоже на стороне клиента

Читать дальше →

+13

3.2K

Scratch 11 июня 2010 в 09:50

Генерируем цепочку сертификатов с эллиптическими кривыми при помощи OpenSSL

Криптография *

график функции y^2 = x^3-x+1

Думаю многие слышали о криптографии эллиптических кривых, о том
что работает она во много раз быстрее RSA и при несоизмеримо меньшей длине ключа обеспечивает несоизмеримо большую стойкость ко взлому. Если не слышали, то можно глянуть на wiki или почитать в книгах А.А. Болотова.
К сожалению, данный вид шифрования слабо распространен. Я постараюсь объяснить как им пользоваться и поможет мне в этом OpenSSL.

Чтобы не быть голословным приведу сравнение необходимых длин ключей для обеспечения сравнимой стойкости ко взлому для различных алгоритмов. Нам интересна правая часть.
Сравнение алгоритмов

Сравнение алгоритмов

Видно, что популярным сегодня ключам RSA длиной 1024-2048 бит соответствует всего навсего 160-224битный ключ ECC (Elliptic Curve Cryptography)

Ну а чтобы понять какой RSA тормоз достаточно попробовать сгенерировать самый длинный из предложенных в таблице ключей (и пойти вздремнуть):

openssl genrsa 15360

Желающих прикоснуться к «next gen» криптографии, придуманной аж в 1985 году, прошу под кат.

Читать дальше →

+73

23K

Tthread 9 августа 2010 в 08:11

Популярно о длине ключа на эллиптических кривых

Ключ построенный на эллиптической кривой над конечным полем втрое короче ключа построенном над полем целых чисел. Если вчитаться в это предложение, то любому здравомыслящему человеку покажется это абсурдом, почему короче, а если я хочу длиннее, что у него какое-то ограничение что-ли? Если же его переформулировать и сказать: ключ построенный на эллиптической кривой над конечным полем обеспечивает криптостойкость алгоритма сопоставимую с ключом втрое большей длины но над полем целых чисел это будет звучать более правдоподобно. Давайте попробуем разобраться в чем же кроется «сокращение» длины ключа.

Читать дальше →

+5

886

NeverWalkAloner 13 октября 2010 в 11:23

Пара слов о гибридном шифровании и эллиптических кривых

Криптография *

Здравствуйте, уважаемые читатели. В качестве предисловия позвольте напомнить, что представляют собой гибридные криптосистемы и почему они получили такое широкое распространение.
Итак, гибридной криптосистемой принято называть способ передачи большого объема зашифрованных данных, при котором данные шифруются секретным ключом с применением симметричного алгоритма (например, AES или DES), а сам ключ передается зашифрованным асимметричным шифром (как, скажем, RSA). Такой способ получил широкое распространение за то, что он вбирает в себя преимущества как симметричной, так и асимметричной криптографии. Большой блок данных шифруется очень быстрым симметричным алгоритмом (и это избавляет от серьезных временных затрат), а ключ шифрования передается надежно зашифрованным с помощью асимметричного алгоритма (и это решает проблему распределения ключей, свойственную только симметричным методам). Все это достаточно широко известно, а поэтому перейдем к самому главному, а именно к вопросам реализации. И вот тут начинается много интересного.

Читать дальше →

+24

9.3K

codecity 28 октября 2010 в 07:09

Открытая библиотека украинского стандарта ЭЦП (приглашаются разработчики)

Криптография *

Примерно 2 года назад у меня возникла идея создания открытой библиотеки украинского стандарта электронно-цифровой подписи ДСТУ 4145-2002. Украинский стандарт, как и российский, основан на эллиптических кривых, но отличается в деталях.

С большим трудом был найден текст стандарта (странно, текст российского стандарта в свободном доступе) и вроде как дело осталось за малым…

За последние два года, к сожалению, удалось сделать очень мало: задача сложная, готовых открытых библиотек или примеров нет, времени мало. По этому было принято решение попытать счастья, вдруг кто-то захочет принять участие в проекте. Более подробно о проекте — читайте под катом.

Читать дальше →

+23

9.4K

NeverWalkAloner 9 августа 2013 в 12:58

Эллиптическая криптография: теория

Информационная безопасность *Криптография *

Туториал

Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.

Читать дальше →

+126

151K

grechnik 10 августа 2013 в 21:24

Представление чисел суммой двух квадратов и эллиптические кривые

Криптография *Математика *

Пусть p — нечётное простое число. Довольно широко известно, что p представимо в виде суммы двух квадратов целых чисел p=a²+b² тогда и только тогда, когда p при делении на 4 даёт остаток 1: 5=1²+2², 13=3²+2², 17=1²+4², ...; 3, 7, 11,… непредставимы. Куда менее известно, что a и b можно записать красивой формулой, имеющей непосредственное отношение к одной эллиптической кривой. Об этом результате 1907 года за авторством немца по фамилии Jacobsthal и о связанных вещах мы сегодня и поговорим.

Совсем легко понять, почему 3, 7, 11 и прочие числа, дающие при делении на 4 остаток 3, непредставимы в виде a²+b²: квадрат чётного числа всегда делится на 4, квадрат нечётного числа всегда даёт остаток 1 при делении на 4, сумма двух квадратов при делении на 4 может давать остатки 0, 1 или 2, но никак не 3. Представимость простых чисел вида 4k+1 неочевидна (особенно если заметить, что простота существенна: число 21 хотя и имеет нужный остаток, но суммой двух квадратов не представляется).

Читать дальше →

+39

41K

NeverWalkAloner 26 августа 2013 в 10:23

Эллиптическая криптография: практика

Информационная безопасность *Криптография *

Туториал

Привет, %username%!

Пару недель назад я опубликовал пост Эллиптическая криптография: теория, в котором постарался описать основные аспекты использования эллиптических кривых в криптографии. Тот мой пост носил исключительно ознакомительный характер, и не предусматривал никакой иной работы с компилятором, кроме созерцательной. Но что за теория без практики? С целью исправить это упущение я, собравшись с духом, ринулся в бой с ГОСТ-ом 34.10-2012, схемой ЭЦП на эллиптических кривых. Если вам интересно посмотреть что из всего этого получилось, тогда добро пожаловать под кат.

Читать дальше →

+40

68K

grechnik 16 декабря 2014 в 12:05

Гипотеза Бёрча — Свиннертон-Дайера

Математика *

Эта примечательная гипотеза связывает поведение функции L там, где в настоящее время неизвестно, определена ли она, и порядок группы Ш, про которую неизвестно, конечна ли она!
J.T.Tate, The arithmetic of elliptic curves, Inventiones mathematicae 23 (1974)

Оригинал

This remarkable conjecture relates the behaviour of a function L at a point where it is not at present known to be defined to the order of a group Ш which is not known to be finite!

(Краткая справка насчёт актуальности цитаты 40-летней давности: после Уайлса и Ко таки стало известно, что функцию L можно определить на всей комплексной плоскости. Конечность группы Ш в общем случае остаётся неизвестной.)

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

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

B.J.Birch and H.P.F.Swinnerton-Dyer, Notes on elliptic curves. I, Journal für die reine und angewandte Mathematik 212 (1963)

Оригинал

It remains to discuss the question of error. One can take precautions against machine errors either by running all the calculations twice or by checks included in the program. Moreover, machines — unlike human beings — are so designed that the errors they make are usually too gross to be overlooked. We are satisfied that there are in our results no undetected errors of this sort. On the other hand, in translating an elaborate scheme of calculation into a machine program one is bound to make mistakes. Most of these are found before the program is used for production runs; they show up because the program grinds to a halt or produces ridiculous results. But a program which is believed to work may still contain logical errors which only have an effect in rare circumstances: and indeed most computers have anomalies which cause them occasionally not to behave in the way that their specifications suggest. In fact, our program for stage (ii) was imperfect in that a very few equivalences were missed by the machine.

For these reasons we believe that results obtained from a computer should not be automatically trusted. In some cases they can be checked because they have properties which were not essentially used in the course of the calculation and which would be unlikely to survive if an error had been made. (For example, if a table of a smooth function has been calculated without the use of interpolation, it can be checked by differencing.) But if checks of this sort are not available, results should not be fully trusted until they have been independently reproduced by a different programmer using a different machine. We do not think this sets an unreasonable standard, now that computers are becoming so widely available; and we are satisfied that lower standards have already led to a number of untrue results being published and believed.

Под катом не будет формулировки гипотезы; знающие выражения вроде «Euler product» и «holomorphic continuation» (и в смысле языка, и в смысле обозначаемых понятий) могут прочитать пятистраничный pdf с сайта института Клэя. Под катом — некоторая попытка пояснить, на каком направлении развития математической мысли вообще находится гипотеза Бёрча — Свиннертон-Дайера. А также — как можно досчитать до больших чисел вроде тех, что показаны на КДПВ, менее чем за секунду.

Читать дальше →

+21

16K

NeverWalkAloner 19 мая 2016 в 10:03

ЭЦП стран СНГ на Python

Блог компании Virgil Security, Inc. Информационная безопасность *Криптография *Open source *Python *

Привет!
Я уже писал на Хабре о своей реализации блочных шифров стран СНГ. Выдалась еще одна свободная неделька в результате чего к симметричным стандартам добавились алгоритмы электронной цифровой подписи: российский ГОСТ 34.10-2012, украинский ДСТУ 4145-2002 и белорусский СТБ 34.101.45-2013.
Все три алгоритма основаны на эллиптических кривых. Но реализация каждого из стандартов имеет свои тонкости, о которых я хочу кратко рассказать в этой статье.

Читать дальше →

+12

17K

Qwarri 9 февраля 2017 в 15:03

Анализ эффективности метода факторизации на эллиптических кривых. Практика

Алгоритмы *Математика *

Из песочницы

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

Читать дальше →

+12

7.5K

Crittografo 17 июля 2017 в 16:57

Постквантовая реинкарнация алгоритма Диффи-Хеллмана: вероятное будущее (изогении)

Блог компании «Актив» Информационная безопасность *Криптография *Алгоритмы *

Сегодня мы снова поговорим про протокол Диффи-Хеллмана, но уже построенный на более необычных конструкциях — изогениях, которые признаны устойчивыми к атакам на будущем квантовом компьютере. Квантовый компьютер, который сможет удержать в связанном состоянии порядка нескольких тысяч кубит, позволит находить закрытые ключи по открытым ключам у всех используемых сейчас асимметричных криптосистем. Число кубит для взлома RSA равно удвоенному числу бит в модуле (т.е. для разложения на множители модуля RSA длиной 2048 бит потребуется 4096 кубит). Для взлома эллиптических кривых необходимы более скромные мощности «квантового железа»: для решения задачи ECDLP для кривых над простым полем (такие кривые есть и в отечественном стандарте подписи ГОСТ Р 34.10-2012 и в американском ECDSS) c модулем кривой длиной n бит требуется 6n кубит (т. е. для модуля в 256 бит надо ~ 1536 кубит, а для 512 бит ~ 3072 кубит). На днях российско-американская группа ученых установила мировой рекорд, удержав в связанном состоянии 51 кубит. Так что у нас есть еще немного времени для изучения изогений (а также решеток, кодов, multivariate и подписей, основанных на хэшах).
Кстати, изогении считаются одним из наиболее вероятных кандидатов на победу на конкурсе NIST постквантовых алгоритмов для замены RSA и эллиптических кривых в ближайшие несколько лет.

Читать дальше →

+39

15K

NWOcs 17 июля 2017 в 08:44

Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее?

Блог компании НеоБИТ Информационная безопасность *Криптография *Математика *CTF *

RSA, эллиптические кривые, квантовый компьютер, изогении… На первый взгляд, эти слова напоминают какие-то заклинания, но все куда ~~проще~~ сложнее, чем кажется!

Необходимость перехода к криптографии, устойчивой к атаке на квантовом компьютере, уже официально анонсирована NIST и NSA, из чего вывод довольно-таки простой: пора вылезать из зоны комфорта!

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

Чтобы разобраться в тонкостях криптографии на эллиптических кривых, проследить новомодные веяния постквантовой криптографии и даже прикоснуться к ней с помощью библиотеки Microsoft SIDH, добро пожаловать под кат, %username%!

Читать дальше →

+35

37K

PatientZero 28 августа 2017 в 09:00

Доступно о криптографии на эллиптических кривых

Криптография *Алгоритмы *Математика *

Перевод

Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.

Сегодня криптосистемы на эллиптических кривых используются в TLS, PGP и SSH, важнейших технологиях, на которых базируются современный веб и мир ИТ. Я уже не говорю о Bitcoin и других криптовалютах.

До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.

В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.

Читать дальше →

+123

199K

GlobalSign_admin 16 апреля 2018 в 11:44

Правильные ответы по криптографии: 2018 год

Блог компании GlobalSign Информационная безопасность *Разработка веб-сайтов *Криптография *

Перевод статьи, автор – Latacora

В литературе и самых сложных современных системах есть «лучшие» ответы на многие вопросы. Если вы разрабатываете встроенные приложения, то предлагают использовать STROBE и модный современный криптографический стек для аутентификации полностью из одиночных SHA-3-подобных функций губки. Советуют использовать NOISE для разработки безопасного транспортного протокола с формированием общего ключа аутентификации (AKE). Говоря об AKE, есть около 30 различных парольных AKE на выбор.

Но если вы разработчик, а не криптограф, то не должны делать ничего такого. Следует придерживаться простых и обычных решений, которые легко поддаются анализу — «скучных», как говорят люди из Google TLS.

Читать дальше →

+24

19K

SLY_G 23 ноября 2018 в 11:49

Какие свидетельства могут убедить математиков, если строгого доказательства нет?

Математика *Научно-популярное

Перевод

Новая статистическая модель, кажется, подрывает давно принятые предположения из теории чисел. Насколько ей можно доверять, если на самом деле имеет значение только строгое доказательство?

Какие точки на эллиптической кривой y² = x³ – 4x + 1 рациональные? Чтобы их найти, нужно провести прямые через пары рациональных точек. Все точки, через которые проходят прямые, также будут рациональными.

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

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

+13

13K

SLY_G 26 ноября 2018 в 15:00

Новое доказательство демонстрирует существование двух видов бесконечных кривых

Математика *Научно-популярное

Перевод

Работа Александра Смита по гипотезе Голдфелда раскрыла фундаментальные свойства эллиптических кривых

Две эллиптические кривые демонстрируют странности концепции ранга. Кривая слева описывается уравнением y² = x³ + 1, проходит только через пять рациональных точек и имеет ранг 0. Кривая справа описывается уравнением y² = x³ + 8, проходит через бесконечное число рациональных точек, и имеет ранг 1.

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

Эллиптические кривые кажутся чем-то экзотическим, однако это непримечательные геометрические объекты, не сложнее прямых, парабол или эллипсов. В своей работе, опубликованной в онлайне в прошлом году, Алексадр Смит доказал гипотезу сорокалетней давности, касающуюся фундаментальной особенности эллиптических кривых, ранга. Смит доказал, что из определённого семейства кривых, имеющих одну характеристику, половина имеют ранг, равный 0, а половина – 1.

Читать дальше →

+19

13K

Data_center_MIRAN 6 ноября 2019 в 16:33

Рукопожатие SSH простыми словами

Блог компании Дата-центр «Миран» Информационная безопасность *Криптография *Серверное администрирование *Софт

Перевод

Secure Shell (SSH) — широко используемый протокол транспортного уровня для защиты соединений между клиентами и серверами. Это базовый протокол в нашей программе Teleport для защищённого доступа к инфраструктуре. Ниже относительно краткое описание рукопожатия, которое происходит перед установлением безопасного канала между клиентом и сервером и перед началом полного шифрования трафика.

Обмен версиями

Рукопожатие начинается с того, что обе стороны посылают друг другу строку с номером версии. В этой части рукопожатия не происходит ничего чрезвычайно захватывающего, но следует отметить, что большинство относительно современных клиентов и серверов поддерживают только SSH 2.0 из-за недостатков в дизайне версии 1.0.

Обмен ключами

В процессе обмена ключами (иногда называемого KEX) стороны обмениваются общедоступной информацией и выводят секрет, совместно используемый клиентом и сервером. Этот секрет невозможно обнаружить или получить из общедоступной информации.

Читать дальше →

+38

36K

Ostrie_Brevna 5 февраля 2020 в 11:00

SageMath и CoCalc: как всё начиналось. Часть первая

Open source *Математика *Управление сообществом *Биографии гиков

Перевод

Публикуется с разрешения автора.

От переводчика

Текст, перевод которого я намерен представить вашему вниманию, — краткая автобиография (называющаяся в оригинале «Mathematical Software and Me: A Very Personal Recollection», то есть «Математическое ПО и я: очень личные размышления»), написанная в 2009-м году Уильямом Стайном (имя которого по-русски иногда пишут как «Вильям Стейн»), бывшим профессором математики Вашингтонского Универститета, получившим степень Ph. D. в Беркли (Калифорния). Математическая составляющая профессиональных интересов доктора Стайна — теория чисел. Этот текст — о его, возможно, главном деле — системе компьютерной математики, ранее называвшейся Sage, в настоящее время переименованной в SageMath, существующей также в облачной версии, которая раньше называлась SageMathCloud, а теперь — CoCalc. (На Хабре эти системы неоднократно упоминались: например, freetonik написал о Sage, а sindzicat поведал о SageMathCloud.) Когда я прочитал «Mathematical Sofrware and Me» первый раз, этот текст меня очень впечатлил. И прежде, чем перейти к самому переводу, я попробую кратко объяснить, чем же именно.

(UPD. Вторая часть опубликована здесь: habr.com/ru/post/484960.)

Автор оригинального текста (слева). Источкик фото: Facebook.

Читать дальше →

+17

4.1K

Ostrie_Brevna 7 февраля 2020 в 09:57

SageMath и CoCalc: как всё начиналось. Часть вторая

Open source *Математика *Управление сообществом *Биографии гиков

Перевод

Вторая часть перевода автобиографической статьи Уильяма Стайна «Mathematical Software and Me: A Very Personal Recollection», в которой он рассказывает о предпосылках и первых годах разработки системы SageMath (ранее называвшейся Sage). Первая часть перевода, предисловие переводчика и описание соглашений, принятых в тексте (использование жирного и подчёркнутого шрифтов, а также ссылок), — в этом посте: habr.com/ru/post/484476.

Публикуется с разрешения автора.

Источник фото: страница Стайна в Facebook.

Читать дальше →

+1

1.2K

1