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

Правда, могу ошибаться — пробежал по всем абзацам, но прочитать подробно и с нормальным пониманием оставил на попозже.

Базовых — это курса три профильного вуза?
Я, вообще говоря, не понимаю, как это вообще можно даже пытаться излагать доступно, ведь сложность криптографии на элиптических кривых является одной из ее базовых фич

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

сложность криптографии на элиптических кривых является одной из ее базовых фич

Сложность изучения вы имеете в виду? Как это может вообще быть фичей, в чём преимущество?
Полторы лекции — если на пальцах, на веру. Если с доказательствами — то поля это 3 семестр.

Эээ, 3его семестра нужно дожидаться, чтобы рассказать определение поля, или что?
Да, есть разные факты о полях, которые доказываются в разных курсах алгебры, но эта статья вроде бы на них не опирается (или я ошибаюсь?)


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


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

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

Как это может вообще быть фичей, в чём преимущество?
Шифры изначально (окей, не все, но конкретно эти точно) разрабатываются не для защиты котиков в интернетиках. Чем меньше человек способны вникнуть в теорию и заниматься анализом, тем лучше. Это не требование, конечно (иначе StO), но как фича вполне себе
Готов поспорить на что-нибудь, что случайный человек без высшего профильного после одной лекции эту статью не осилит. Ну и просто перечисление понятий — это сильно, вот именно их-то для понимания криптографии людям и не хватает.

Там нет ничего ужасного. Насколько я помню, теорию множеств преподают ещё в школе.
Если вы программист, то в модульной арифметике разбираетесь, так или иначе.
Понятие группы и кольца вводится прямо в этой статье. Больше ничего сложного вроде нет. Главное — внимательно следить за выкладками.

Чем меньше человек способны вникнуть в теорию и заниматься анализом, тем лучше.

Тем хуже. Чем больше людей могут понять и найти проблему — тем больше шансов что об этой проблеме узнаю все, а не только те-кому-надо. См. ту же историю с DES и дифференциальным криптоанализом (я её уже упоминал тут).
Главное — внимательно следить за выкладками
За фокусниками тоже следят внимательно, но ход трюка улавливают не все. Без базы ни домохозяйка, ни кодер не поймет эту тему сам по себе. В лучшем случае он будет думать, что понял

Тем хуже.
Вот глупые люди в разведке сидели-то (а может, и сидят), наверное, со своей секретностью. Нет, это правда не очевидно? Повышенный порог входа потенциального противника для криптоанализа — это явная фича
Ну и DES в качестве аналогии — сильно. Это ведь коммерческий шифр, созданный с кучей ограничений (иначе стандартом не приняли бы), давайте еще с шифром Цезаря сравнивать
За фокусниками тоже следят внимательно, но ход трюка улавливают не все. Без базы ни домохозяйка, ни кодер не поймет эту тему сам по себе. В лучшем случае он будет думать, что понял.

Ну очевидно что это — не справочник. Тем не менее эта статься дает довольно глубокое понимание того как работают эллиптические кривые.

Вот глупые люди в разведке сидели-то (а может, и сидят), наверное, со своей секретностью.

Аргумент к авторитету. Не катит.

Нет, это правда не очевидно? Повышенный порог входа потенциального противника для криптоанализа — это явная фича.

Абсолютно не очевидно. Вся информация есть в свободном доступе. Исходить из предположения что у вероятного противника сидят более глупые математики — неправильно. Надежность алгоритма должна обеспечиваться математическими средствами, а не тем фактом что в нем никто не может разобраться. Эллиптические кривые используют не потому что они такие сложные.

Ну и DES в качестве аналогии — сильно. Это ведь коммерческий шифр, созданный с кучей ограничений (иначе стандартом не приняли бы),

Тем не менее АНБ принимали участие в разработке. И сделали его надежнее, вместо того что бы ослабить. Потому что они тоже не дураки и не хотят что бы вероятный противник сломал их банковскую систему, например.
Они понимают, что если они изобрели новый способ криптоанализа, значит его может изобрести и вероятный противник. Если они сделали закладку, значит эту закладку может найти вероятный противник. Зачем подставлять свою страну?
Как вы думаете, что опаснее в современном мире — то что вероятный противник будет читать ваши военные шифры, или то что он сможет сломать вам банкинг, Интерент и телефонию?

Цитат не будет, так как с телефона, пардон заранее.


Про понимание я ничего не говорил, лишь про необходимый для него уровень подготовки.


Анб не разрабатывали, они контролировать результат. И вместе с устойчивостью к дифф. анализу сделали его уязвимее к брутфорсу.


Про авторитеты и интернеты (какой интернет и банковские системы с шифрами, разговор про шифры, что в 70х делались, до des вообще не шифровали, считай) комментировать отказываюсь, это уровень пикабу

Готов найти матшкольника, который осилит эту статью. Может, даже, и без лекции вовсе.
Без высшего профильного, как вы и говорите.

Погуглите программу матклассов 57 школы, например)

П.с. упс, простите, промахнулся
Комментарий для Labunsky

Можете переводить мне деньги, я физфак, что точно не является профильным ,) ТГ, IIRC, в школе не было.

Готов перевести максимум тысячу догекоинов (и я серьезен!), потому что высшая математика вроде из профиля физфака никуда не исчезала)

Дисциплины которые у нас были: матан, ангем, линал, диффуры, интуры+вариационка, теорвер, тфкп, урчипы (в рамках курса "методы матфизики"), омм. Ни в одном из этих курсов теории групп, к сожалению, нет.

Присоединюсь к флуду. Учился в киевском Физтехе. Теория групп появилась в курсе симметрии на 4 курсе.
А вот в полях не шарю.
Странно, даже в линале не упоминались (у меня вместе с ним еще на первом курсе шла)?
Но это все офтоп, изначально у меня была претензия к изложению материала. То, что его можно понять (особенно имея высшее математическое в том или ином виде) — ну с этим трудно поспорить
P.S.
1к догекоинов точно не нужно?)

Как не странно, полугруппы/группы не упоминались. Упоминались, естественно, поля, векторные пространства, оболочки и прочие радости. Естественно, ввести определение поля вполне можно и без определения группы или, например, моноида.


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


Re: P.S.

Точно не нужно. Це биль такой щютк ,)

"Чем меньше человек способны вникнуть в теорию и заниматься анализом, тем лучше"
Интересный подход, при таком подходе после широкого внедрения может быть очень больно когда кто-то со стороны таки раскопает втихую в "не хороших целях".
Т.к. алгоритмы то по умолчанию открыты.

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

UFO landed and left these words here
Ну почему же? Я до этого пару раз пытался вникнуть в тему — не получалось. После этой статьи всё наконец-то сошлось в голове. Большое спасибо автору и переводчику!
Сумма трёх точек, находящихся на одной прямой, равна 0

В оригинале так: «The sum of three aligned point is 0.»
Понимаю как складывать векторы, а как складывать точки?!
Можете пояснить, без этого остальное сложно разобрать.
В конкретном случае сложение определяется, как ассоциативная бинарная операция, которая берет какие-либо две точки и выдает третью на их основе. Поправьте меня, если я не прав.
«Сумма трёх точек, находящихся на одной прямой, равна 0» — и есть определение того, что мы понимаем под операцией сложения в нашей группе, элементами которой мы решили считать точки на кривой. Чуть выше в статье кратко рассказывается, что такое группа, а чуть ниже показывается, как из знания способа складывать три точки на одной прямой мы можем узнать, как сложить просто две любые точки.
Как раз сразу после этого абзаца объясняется операция сложения точек (основана на понятии обратной точки — симметричной относительно оси x).

Не нужно к операции "+" относится именно как к сложению в стандартном его понимании. Считайте это просто какой-то операцией, выполняя которую над определенным множеством это множество можно назвать группой.

Возможно ли, что 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 принадлежит кривой, иначе — нет. Поправьте меня, если не прав.
Действительно, для того, чтобы подставить в уравнение точку R, нам сначала необходимо найти эту самую точку R, которую, в свою очередь, необходимо будет вычислить с помощью кубического уравнения. Автор же приводит более изящный метод проверки результата.

Нет, автор с самого начала дал нам формулу для координат этой точки, а потом сказал что подставить их в уравнение кривой — слишком сложно.

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

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

А сам стиль изложения и сложность материала в самый раз, спасибо.
Ну во-первых, мы чисто технически не умеем работать с действительными числами. В смысле, не мы, а наши цифровые компьютеры. Они работают только с целыми. При печати мы можем выводить десятичную запятую где нам нравится (вычисления с фиксированной запятой, например, банковский софт обычно хранит все суммы в целых копейках/центах, а запятая/точка ставится только при выводе итога тупым гуманоидам), либо даже заставить компьютер помнить, где в конкретном числе должна стоять десятичная запятая (классические форматы с плавающей запятой, float/double/чётамувас). Но это всё равно целые.
Есть либы для псевдо-настоящих действительных чисел (арифметика с произвольной точностью), но они все упираются в память. Т.е. это просто double, только с более длинной мантиссой. Для числа пи вы можете хранить не 18 цифр как в double, а скажем миллион, но это всё равно не будет число пи, а будет некое целочисленное приближение к нему. Ну это как в некоторых школах для даунов принимают пи равно 3, только здесь чуть больше цифр.
Квантовые компьютеры по своей природе аналоговые, и могут хранить действительно число пи (пусть и с некоторыми шумами).
Вторая причина связана с тем, что ВНЕЗАПНО целочисленная арифметика по модулю значительно более сложная и трудоёмкая, чем обычная. В частности, такие задачи, как логарифмирование и решение СЛАУ в целых числах вообще не имеют полиномиальных решений для общего случая, по крайней мере известных.

Квантовые компьютеры по своей природе аналоговые, и могут хранить действительно число пи (пусть и с некоторыми шумами).


А классический компьютер нельзя сделать аналоговым? Хотя бы частично, используя схемы типа такой.
Квантовые компьютеры по своей природе аналоговые, и могут хранить действительно число пи (пусть и с некоторыми шумами).

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

Вот именно, но когда читаешь статью сверх вниз, то начинается изложение довольно просто, а потом вдруг автор переходит к рассмотрению сложных тем, не объясняя причин зачем же понадобилась эта «ненужная» сложность. Хорошо бы каждый блок текста предварять объяснением почему последующий материал важен.

Например, ваше «во-первых», было бы хорошим введением к части 2 про конечные поля и дискретное логарифмирование.

Это нужно по двум причинам:


  1. Криптография работает с точными вычислениями, а не с приближенными — структурированные данные надо расшифровывать точно, а не примерно, особенно в области служебных данных; цифровые подписи тоже должны проверяться на точное совпадение. А точные вычисления можно проводить только в целых числах.


  2. Эллиптические кривые в действительных числах "слишком простые" для криптографии. Криптография построена вокруг вычислительно нерешаемых за приемлемое время задач, а такие задачи проще найти в целочисленной математике.
Задавал подобный вопрос на тостере, но мне никто ничего не сказал (даже в духе «твой вопрос тупой до невозможности»). Может кто здесь ответит?

Есть мнение, что нахождение DLOG на эллиптической кривой (1) сложнее нахождения DLOG в конечном поле (2). В то же время wiki говорит, что задача (1) сводится к (2) (с некоторым расширением поля, на котором была задана эллиптическая кривая).

Верно ли, что если будет найден способ быстро находить DLOG в конечном поле, то это автоматически разрешит и задачу нахождения DLOG на эллиптической кривой (и сделает неактуальной всю эллиптическую криптографию)?
Думается, что дискретный логарифм для эллиптической кривой не имеет смысла если эта кривая не в поле. То же самое для просто поля, без эллиптической кривой его задающего. Есть dlog для полей заданных параметрами поля И кривой. Как следствие — я вопроса не понял )

Ну это понятно, имеется в виду, что исходное поле можно расширить.
PS. Ниже дал ссылку на разлел в википедии (понятно, что недостоверный ресурс, но там есть ссылки на научные труды).

Статью писал студент преподавателя vlsergey, поэтому можно позвать Сергея Михайловича. К примеру, попросить пояснить условие НОК(m, q — 1) = 1, которое никогда не выполняется просто потому, что НОК не может быть меньше делителей (если это только не какой-то особенный НОК, про который нужно в отдельно пояснить).

А можно подробнее о том как именно задача (1) может быть сведена к (2)? Что-то не вижу в Википедии ничего похожего на это утверждение.

В выражении для двоичных кривых вероятно ошибка: x^2+xy=x^3+x^2+b вероятно следует читать как Y^2+xy=x^3+x^2+b. В оригинале x^2.
Порылся навскидку в статьях с упоминанием «binary elliptic curves» — там y^2.
существует единичный элемент 0, такой, что a+0=0+a=a;

Мне одному кажется, что это соответствует описанию «нейтрального относительно сложения» элемента, а не единичного...? «Единичный элемент 0», должно даже обывателю резать глаз.
Вы правы: в оригинале статьи используется термин «identity element», которому в русскоязычной терминологии соответствует, в зависимости от контекста, либо «нейтральный элемент», либо «единица».
Википедия
"...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.
Для secp256k1, который используется в биткоинах, википедия нам говорит так.
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?
Стоит отметить, что существует метод восстановления публичного ключа из подписи (по крайней мере свести к небольшому числу вариантов), описанный в разделе «4.1.6 Public Key Recovery Operation» здесь: www.secg.org/sec1-v2.pdf
Кстати говоря, именно этот метод используется в блокчейне Ethereum. Там, кроме параметров R и S в подписи, еще есть параметр V, который содержит в себе идентификатор сети (для предотвращения replay-атаки), а так же индекс публичного ключа из всех возможных вариантов восстановления. Таким образом транзакция содержит только подпись (R,S,V) и по ней определяется как единственный публичный ключ, так и адрес отправителя (который является частью хеша публичного ключа).
Что касается процесса подписи, то в Ethereum блокчейне, вместо случайного числа используют некий nonce, который вычисляется на основе секретного ключа и хеша подписываемого сообщения. То есть функция подписи одного и того же сообщения будет всегда возвращать один и тот же результат. Подробнее об этом можно прочесть в RFC 6979: tools.ietf.org/html/rfc6979#section-3
Поискал немного по блокчейну эфириума. В нем встречаются несколько интересных транзакций.
Например, в в подписи некоторых транзакций такие вот странные значения s:
0x1d
0x820820820820820820820820820820820820820820820820820820820820820
0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Как такое может быть?

Не могли бы подсказать (а то мозг уже вскипел), как в примере сложения двух точек (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!!!)


Подскажите, где ошибка? Или мой калькулятор с такими большими числами не работает?

Only those users with full accounts are able to leave comments. Log in, please.