Comments 72
ДоступноПочему-то мне кажется, что доступным это будет только для тех, кто и так уже в курсе
Нужен бэкграунд в виде понимания базовых вещей общей алгебры (надеюсь, вы не заблуждаетесь, считая, что общая алгебра изучается только в рамках криптографии). Но я не нашёл никакого требования к хотя бы какому-нибудь знанию криптографии.
Правда, могу ошибаться — пробежал по всем абзацам, но прочитать подробно и с нормальным пониманием оставил на попозже.
Базовых — это курса три профильного вуза?
Я, вообще говоря, не понимаю, как это вообще можно даже пытаться излагать доступно, ведь сложность криптографии на элиптических кривых является одной из ее базовых фич
Ну это не три. И даже не один. Одна лекция или даже половинка, может быть.
сложность криптографии на элиптических кривых является одной из ее базовых фич
Сложность изучения вы имеете в виду? Как это может вообще быть фичей, в чём преимущество?
Эээ, 3его семестра нужно дожидаться, чтобы рассказать определение поля, или что?
Да, есть разные факты о полях, которые доказываются в разных курсах алгебры, но эта статья вроде бы на них не опирается (или я ошибаюсь?)
В общем-то, все перечисленные мною понятия есть даже в учебнике для инженеров (бауманском), по дискретной математике, правда.
Я не говорю, что в любом курсе алгебры их вводят на первой же лекции, нет. Я говорю, что они все достаточно просты, чтобы объяснить их на первой лекции. А значит, заинтересованный может найти их и осознать сам или даже просто знать из общей эрудиции, как я.
Лично я так и не завершил ни один курс общей алгебры даже наполовину, но всё перечисленное знаю.
Как это может вообще быть фичей, в чём преимущество?Шифры изначально (окей, не все, но конкретно эти точно) разрабатываются не для защиты котиков в интернетиках. Чем меньше человек способны вникнуть в теорию и заниматься анализом, тем лучше. Это не требование, конечно (иначе StO), но как фича вполне себе
Готов поспорить на что-нибудь, что случайный человек без высшего профильного после одной лекции эту статью не осилит. Ну и просто перечисление понятий — это сильно, вот именно их-то для понимания криптографии людям и не хватает.
Там нет ничего ужасного. Насколько я помню, теорию множеств преподают ещё в школе.
Если вы программист, то в модульной арифметике разбираетесь, так или иначе.
Понятие группы и кольца вводится прямо в этой статье. Больше ничего сложного вроде нет. Главное — внимательно следить за выкладками.
Чем меньше человек способны вникнуть в теорию и заниматься анализом, тем лучше.
Тем хуже. Чем больше людей могут понять и найти проблему — тем больше шансов что об этой проблеме узнаю все, а не только те-кому-надо. См. ту же историю с DES и дифференциальным криптоанализом (я её уже упоминал тут).
Главное — внимательно следить за выкладкамиЗа фокусниками тоже следят внимательно, но ход трюка улавливают не все. Без базы ни домохозяйка, ни кодер не поймет эту тему сам по себе. В лучшем случае он будет думать, что понял
Тем хуже.Вот глупые люди в разведке сидели-то (а может, и сидят), наверное, со своей секретностью. Нет, это правда не очевидно? Повышенный порог входа потенциального противника для криптоанализа — это явная фича
Ну и DES в качестве аналогии — сильно. Это ведь коммерческий шифр, созданный с кучей ограничений (иначе стандартом не приняли бы), давайте еще с шифром Цезаря сравнивать
За фокусниками тоже следят внимательно, но ход трюка улавливают не все. Без базы ни домохозяйка, ни кодер не поймет эту тему сам по себе. В лучшем случае он будет думать, что понял.
Ну очевидно что это — не справочник. Тем не менее эта статься дает довольно глубокое понимание того как работают эллиптические кривые.
Вот глупые люди в разведке сидели-то (а может, и сидят), наверное, со своей секретностью.
Аргумент к авторитету. Не катит.
Нет, это правда не очевидно? Повышенный порог входа потенциального противника для криптоанализа — это явная фича.
Абсолютно не очевидно. Вся информация есть в свободном доступе. Исходить из предположения что у вероятного противника сидят более глупые математики — неправильно. Надежность алгоритма должна обеспечиваться математическими средствами, а не тем фактом что в нем никто не может разобраться. Эллиптические кривые используют не потому что они такие сложные.
Ну и DES в качестве аналогии — сильно. Это ведь коммерческий шифр, созданный с кучей ограничений (иначе стандартом не приняли бы),
Тем не менее АНБ принимали участие в разработке. И сделали его надежнее, вместо того что бы ослабить. Потому что они тоже не дураки и не хотят что бы вероятный противник сломал их банковскую систему, например.
Они понимают, что если они изобрели новый способ криптоанализа, значит его может изобрести и вероятный противник. Если они сделали закладку, значит эту закладку может найти вероятный противник. Зачем подставлять свою страну?
Как вы думаете, что опаснее в современном мире — то что вероятный противник будет читать ваши военные шифры, или то что он сможет сломать вам банкинг, Интерент и телефонию?
Цитат не будет, так как с телефона, пардон заранее.
Про понимание я ничего не говорил, лишь про необходимый для него уровень подготовки.
Анб не разрабатывали, они контролировать результат. И вместе с устойчивостью к дифф. анализу сделали его уязвимее к брутфорсу.
Про авторитеты и интернеты (какой интернет и банковские системы с шифрами, разговор про шифры, что в 70х делались, до des вообще не шифровали, считай) комментировать отказываюсь, это уровень пикабу
Без высшего профильного, как вы и говорите.
Погуглите программу матклассов 57 школы, например)
П.с. упс, простите, промахнулся
Комментарий для Labunsky
Можете переводить мне деньги, я физфак, что точно не является профильным ,) ТГ, IIRC, в школе не было.
Готов перевести максимум тысячу догекоинов (и я серьезен!), потому что высшая математика вроде из профиля физфака никуда не исчезала)
Дисциплины которые у нас были: матан, ангем, линал, диффуры, интуры+вариационка, теорвер, тфкп, урчипы (в рамках курса "методы матфизики"), омм. Ни в одном из этих курсов теории групп, к сожалению, нет.
А вот в полях не шарю.
Но это все офтоп, изначально у меня была претензия к изложению материала. То, что его можно понять (особенно имея высшее математическое в том или ином виде) — ну с этим трудно поспорить
Как не странно, полугруппы/группы не упоминались. Упоминались, естественно, поля, векторные пространства, оболочки и прочие радости. Естественно, ввести определение поля вполне можно и без определения группы или, например, моноида.
Знаю, что у людей, связанных с кристаллами ТГ была на спецкурсе, что ожидаемо. Другое дело, что базовое понимание того что такое группа и кольцо легко получить за полчаса.
Точно не нужно. Це биль такой щютк ,)
"Чем меньше человек способны вникнуть в теорию и заниматься анализом, тем лучше"
Интересный подход, при таком подходе после широкого внедрения может быть очень больно когда кто-то со стороны таки раскопает втихую в "не хороших целях".
Т.к. алгоритмы то по умолчанию открыты.
Ну это не три. И даже не один. Одна лекция или даже половинка, может быть.
Вероятно все зависит от того на каком факультете учишься. Если на физмате пол лекции, если на ИЗО то к концу семестра может быть :)
Ну вот я, например, не в курсе (никогда не изучал ни теорию групп, ни эллиптические кривые над конечными полями — последнего термина даже не знал до прочтения этой статьи), но изложено действительно очень доступно — я понял. Бэкграунд — физфак технического вуза, т.е. просто базовые знания высшей математики (матанализ, линейная алгебра, диф геометрия).
Сумма трёх точек, находящихся на одной прямой, равна 0
В оригинале так: «The sum of three aligned point is 0.»
Понимаю как складывать векторы, а как складывать точки?!
Можете пояснить, без этого остальное сложно разобрать.
Не нужно к операции "+" относится именно как к сложению в стандартном его понимании. Считайте это просто какой-то операцией, выполняя которую над определенным множеством это множество можно назвать группой.
Возможно ли, что NIST обнаружил «значительно большой» класс слабых эллиптических кривых, попробовал различные возможные варианты порождающих значений и нашёл уязвимую кривую
С другой стороны можно вспомнить известную историю DES. NSА попросили разработчиков алгоритма изменить содержимое S-boxes (таблиц перестановок), но не сказали почему они должны быть именно такими.
Через 20 лет академическое общество (пере)открыло дифференциальный криптоанализ. Оказалось, что S-boxes, предложенные NSA делают DES защищенным от этой атаки. Если бы S-boxes выбирались случайно, то DES был бы намного уязвимее:
Bruce Schneier observed that «It took the academic community two decades to figure out that the NSA 'tweaks' actually improved the security of DES».
Проверка нахождения на одной прямой тривиальна, а проверка принадлежности R кривой — нет, потому что нам придётся решать кубическое уравнение, что совсем невесело.
Почему проверка принадлежности кривой это нетривиально? Подставляем точку R в уравнение кривой, если левая и правая часть окажутся равны, то точка R принадлежит кривой, иначе — нет. Поправьте меня, если не прав.
А сам стиль изложения и сложность материала в самый раз, спасибо.
Есть либы для псевдо-настоящих действительных чисел (арифметика с произвольной точностью), но они все упираются в память. Т.е. это просто double, только с более длинной мантиссой. Для числа пи вы можете хранить не 18 цифр как в double, а скажем миллион, но это всё равно не будет число пи, а будет некое целочисленное приближение к нему. Ну это как в некоторых школах для даунов принимают пи равно 3, только здесь чуть больше цифр.
Квантовые компьютеры по своей природе аналоговые, и могут хранить действительно число пи (пусть и с некоторыми шумами).
Вторая причина связана с тем, что ВНЕЗАПНО целочисленная арифметика по модулю значительно более сложная и трудоёмкая, чем обычная. В частности, такие задачи, как логарифмирование и решение СЛАУ в целых числах вообще не имеют полиномиальных решений для общего случая, по крайней мере известных.
Квантовые компьютеры по своей природе аналоговые, и могут хранить действительно число пи (пусть и с некоторыми шумами).
А классический компьютер нельзя сделать аналоговым? Хотя бы частично, используя схемы типа такой.
Квантовые компьютеры по своей природе аналоговые, и могут хранить действительно число пи (пусть и с некоторыми шумами).
"Пусть и некоторые шумы" ведут к уменьшению точности вычислений точно так же, как и округления в цифровой технике. Более того, цифровые компьютеры в этих своих "ужасных" double достигают намного большей точности чем аналоговые компьютеры.
Например, ваше «во-первых», было бы хорошим введением к части 2 про конечные поля и дискретное логарифмирование.
Это нужно по двум причинам:
Криптография работает с точными вычислениями, а не с приближенными — структурированные данные надо расшифровывать точно, а не примерно, особенно в области служебных данных; цифровые подписи тоже должны проверяться на точное совпадение. А точные вычисления можно проводить только в целых числах.
- Эллиптические кривые в действительных числах "слишком простые" для криптографии. Криптография построена вокруг вычислительно нерешаемых за приемлемое время задач, а такие задачи проще найти в целочисленной математике.
Есть мнение, что нахождение DLOG на эллиптической кривой (1) сложнее нахождения DLOG в конечном поле (2). В то же время wiki говорит, что задача (1) сводится к (2) (с некоторым расширением поля, на котором была задана эллиптическая кривая).
Верно ли, что если будет найден способ быстро находить DLOG в конечном поле, то это автоматически разрешит и задачу нахождения DLOG на эллиптической кривой (и сделает неактуальной всю эллиптическую криптографию)?
Ну это понятно, имеется в виду, что исходное поле можно расширить.
PS. Ниже дал ссылку на разлел в википедии (понятно, что недостоверный ресурс, но там есть ссылки на научные труды).
А можно подробнее о том как именно задача (1) может быть сведена к (2)? Что-то не вижу в Википедии ничего похожего на это утверждение.
https://ru.m.wikipedia.org/wiki/Дискретное_логарифмирование_на_эллиптической_кривой
Собственно раздел "Теория"
В частных, редких случаях (суперсингулярные кривые и некоторые обычные, которые необходимо генерировать спец. алгоритмом), расширение небольшое и такие кривые используются в криптографии на билинейных отображениях (спариваниях). Вот этот подраздел эллиптической криптографии и будет взломан в случае нахождения быстрого алгоритма для DLOG в конечном поле. В общем-то для полей размера q=2^n (и других полей малой характеристики) он уже и взломан (алгоритм Joux).
Порылся навскидку в статьях с упоминанием «binary elliptic curves» — там y^2.
существует единичный элемент 0, такой, что a+0=0+a=a;
Мне одному кажется, что это соответствует описанию «нейтрального относительно сложения» элемента, а не единичного...? «Единичный элемент 0», должно даже обывателю резать глаз.
Нейтральный элемент (он же единичный в конкретном случае) традиционно обозначается "0". Если тут и докапываться, то до "сложения" (хотя придирка тоже сомнительная: есть коммутативная операция, называть её можно как угодно)
"...117.35-bit elliptic… optimized FPGA implementation of a parallel version of Pollard's rho algorithm. The attack ran for about six months on 64 to 576 FPGAs in parallel…
Так что прогресс чуть-чуть идет. 1е12 месяцев на 192.
The base point G in compressed form is:
G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
and in uncompressed form is:
G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Что такое компрессированная форма (как я понимаю): просто отбросили координату «игрек». Ее можно найти из формулы y=sqrt(x^3+7)
Но вопрос в том, зачем они запрепендили к координате «икс» в одном случае 02, а в другом случае 04?
Кстати говоря, именно этот метод используется в блокчейне Ethereum. Там, кроме параметров R и S в подписи, еще есть параметр V, который содержит в себе идентификатор сети (для предотвращения replay-атаки), а так же индекс публичного ключа из всех возможных вариантов восстановления. Таким образом транзакция содержит только подпись (R,S,V) и по ней определяется как единственный публичный ключ, так и адрес отправителя (который является частью хеша публичного ключа).
Что касается процесса подписи, то в Ethereum блокчейне, вместо случайного числа используют некий nonce, который вычисляется на основе секретного ключа и хеша подписываемого сообщения. То есть функция подписи одного и того же сообщения будет всегда возвращать один и тот же результат. Подробнее об этом можно прочесть в RFC 6979: tools.ietf.org/html/rfc6979#section-3
Например, в в подписи некоторых транзакций такие вот странные значения s:
0x1d
0x820820820820820820820820820820820820820820820820820820820820820
0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Как такое может быть?
Конкретно за этот случай не скажу - но обычно это все переводы между заранее подготовленными кошельками, и на заранее же подсчитанные кошельки. Грубо говоря - сначала считается цепочка транзакий - а потом исполняется, когда уже все числа подгаданы так, как хотелось. Вцелом, какой-то такой принцип. Если цель сохранения монет не ставится - то обычно все не так уж и сложно.
Я высянил откуда такие подписи. Есть какие-то эфириум проекты для которых важно гарантировать, чтобы имелсась транзакция и адрес, который никому не принадлежит, и с которго нельзя больше отправить ни одной транхзакции.
Тогда сначала создается необходимая транзакция, для нее делается подпись с r и v, выбранными неслучайно, как выше. Из r и v вычисляется адрес отправителя с которого нужно отправить тразакцию, чтобы эта подпись была валидной.
Дальше на эот адрес закидывается немного эфира и отпаравляется подписанная транзакция. Все. Приватный ключ никто не знает.
Не могли бы подсказать (а то мозг уже вскипел), как в примере сложения двух точек (80,10), при а = 2, b = 3, p = 97, в результате получается точка (3, 91).
У меня выдает ошибочный вариант (3, 83), но не пойму в чем ошибка?
Считаю вручную:
x1 = 80 x2 = 80
y1 = 10 y2 = 10
m = (3 х x1 х x1 + curve.a) х inverse_mod(2 х y1, curve.p) = (3 х 80 х 80 + 2) х inv(20, 97) = 19202 х 34 = 652868
x3 = m^ 2 — x1 — x2 = 652868^2 — 80 — 80 = 426236625264
y3 = y1 + m х (x3 — x1) = 10 + 652868 х (426236625264 — 80) = 10 + 652868 х 426236625184 = 278276253010627722
x3%p = 426236625264 % 97 = 3
y3%p = 278276253010627722 % 97 = 83 (а должно быть 91!!!)
Подскажите, где ошибка? Или мой калькулятор с такими большими числами не работает?
Простите, кажется, что скрипт-визуазизатор (https://cdn.jsdelivr.net/gh/andreacorbellini/ecc@920b29a/interactive/modk-add.html) не работает. Выводит просто исходный код, а не поля ввода и решётку с точками.
https://rawcdn.githack.com/andreacorbellini/ecc/865b8f9e79ed94a9d004a9b553f4b3add55878be/interactive/modk-add.html - можно использовать сервис https://raw.githack.com/ . Исходники скриптов визуализации тут - https://github.com/andreacorbellini/ecc .
Delete
Так читал статью вначале про группы и поля ясно как бы, потом потерялся. Так и не понял как кривые используются, то есть понял что какие-то координаты кривой это секретный ключ или нет? Я провасянил курс как решать сравнения. А пока в тетрадке не порешаешь ручками что-то не сильно большое - непонятно и не запомнится. На компе нет больших чисел, максимум 4 миллиарда с чем-то. Поэтому посчитать что-то посложнее и приближенное к реальности не получится. Вот кто-то ныл в комментариях: что если кто-то знает способ решения сравнений - то банки и все остальное ограбят. Смешно, ведь чтобы это осуществить надо хотя бы разбираться в API их сервисов и структурах документов передаваемых от сервера к клиенту. Врятли какой-то гений-математик который найдет решение, сможет его применить для обогащения. То есть надо сидеть в роутере между банком и клиентами, получать данные документов, в них подставлять данные и передавать банку/клиенту(не говоря а шифровании и расшифровании). Тут как минимум в одиночку не справиться. Наверное чтобы это провернуть необходимо куча памяти чтобы облапошить крупный банк например. Да и самые активные клиенты забьют тривогу буквально сразу, позвонят - так что на роутере долго не посидишь с компом на кучу памяти впридачу.
Спасибо автору, статья отличная! Конечно, статья не для первого ознакомления, но многие моменты объяснены довольно доступно.
2. вычисляем все остальное
Доступно о криптографии на эллиптических кривых