Здравствуй дорогой читатель и почитатель Хабра! Если ты попал на эту страницу, значит твой уровень знаний в области эллиптической криптографии достиг того уровня, когда появляются серьезные вопросы на которых ты пока не нашел ответа. Эта статья посвящена как раз одному из таких. Наверняка ты уже слышал, что в криптографии не используют сингулярные кривые. Напомню сингулярная кривая это то, что описывается уравнением вида
И конечно же любопытство заставляет искать информацию, а что же там такого в них особенного? И вот тут ищущего ж��ет неприятный сюрприз. Информации по уязвимости сингулярной кривой на просторах интернета крайне мало и ограничивается фразой, что используется спаривание Вейля, с переводом задачи из координат XY в плоскость обычного кольца вычетов по модулю и решение с помощью известных алгоритмов типа больших и малых шагов, полларда и т.д. ВСЕ! Ничего больше за много лет мне так и не удалось найти, даже простенького примера. И вот занявшись данной проблемой, я захотел повторить и детально описать алгоритм до которого дошли ведущие умы планеты, дабы новичку было просто и понятно. И вот во время этой работы произошло невероятное... Я вдруг обнаружил то, чего миллионы математиков со всего мира так и не заметили. Решение данной задачи может быть настолько простым и лаконичным, что это просто обескуражило... И не нужно никаких спариваний и алгоритмов. Алгоритм это уже нечто долгое и сложное. Вся задача сводиться к простой формуле
Вот и весь дискретный логарифм. n - это вес точки, x,y - координаты точки, m - модуль. Деление происходит по модулю m, так что надо найти элемент обратный y и умножить на х, это элементарная операция, так что я не буду детально описывать, как найти обратный элемент по модулю.
Давайте теперь проверим как это работает. Возьмем к примеру m=97 и построим график точек.
На любом графике подобной сингулярной кривой всегда есть точка (1,1). Это базовая точка - генератор, и вес остальных точек будет исходить по отношению к ней. Действительно, если единицу разделить на единицу, то в итоге получим точку номер один, которую и будем потом умножать на скаляр для проверки. Если в качестве генератора была задана иная точка, тогда надо найти вес точки генератора, нужной точки и просто сравнить их отношения. Выберем абсолютно любую случайную точку, например (54,79) и найдем ее вес.
Итак, наша точка имеет вес 94. Давайте проверим
Умножаем точку (1,1) на 94 и получаем исходную точку (54,79)! Если вы знаете формулы сложения и удвоения точек на эллиптической кривой, то сейчас наверное понимаете, что обратная операция получается еще быстрее, чем умножить точку на скаляр.
Удивительно, что за столько лет так никто и не догадался до столь простого решения. Кстати m может быть и не простым числом, и можно так же находить вес точек на иных сингулярных кривых, а это открывает дорогу к новым возможностям применения ЭК.
В то же время, это вызывает опасения для всей криптографии. Например биткойн-кривая имеет формулу
Как вы уже знаете, я много лет уже знаю данный способ, и у меня есть мнение, что создатель биткойна Гарольд Томас Финни II тоже нашел его. Иначе я не могу объяснить то, что последним сообщением от "Сатоши" было "использовать для возврата средств новый адрес", после чего он исчез. Вероятно, он понял что вполне возможно существует нечто похожее, очень простое и тогда все что он создал будет очень быстро взломано и непригодно для использования. И последний его совет хотя бы в какой-то мере устраняет брешь в системе.
Ну и последнее что бы я хотел всем сказать. Доверяй, но проверяй. Не стоит слепо доверять криптографии и надеяться что лучшие умы все до вас протестировали. Даже человек который вообще не имеет никакого отношения к математике может найти нечто такое, что не смогли лучшие умы человечества. И... дерзайте, возможно кто-нибудь прочитав эту статью сможет найти решение для secp256k1 и "двинуть" сатошивские биткойны.