Comments 4
С его помощью задача по восстановлению числа k из точки kG сводится к определению четности числа k из точки kG. Если число четное, то мы делим его на 2, а если нечётное, то вычитаем единицу и делим на два.
все точки эллиптической кривой четные, вернее делятся на 2. Т.е. есть такая точка, умножив которую на 2, получим искомуую. Именно в этом и есть трудность задачи логарифмирования точек эллиптической кривой.
Шалом, господа! Можно внесу пару корректив?
На эллиптических кривых в конечном поле нет как такового деления точек, есть умножение на мультипликативное обратное, что эквивалентно делению. Так как кривая циклична, то деление произвольной точки на мультипликативное обратное 2 может дать как открытый ключ, чей скаляр в 2 раза меньше исходного, так и вынести получившуюся точку далеко от изначальной, если изначальный открытый ключ соответствовал нечетному скаляру.
Алгоритм Shanks BSGS дает сложность Sqrt(b-a) только при условии сохранения память количества точек равную Sqrt(b-a), что для диапазонов типа 2^120 или не дай бог 2^256 обречено на провал. В случае сохранения в память произвольного количества точек Z, мы получим формулу O(N/Z), где N - порядок кривой или тот диапазон в котором осуществляется поиск. Для больших диапазонов лучше использовать Pollard Lambda/Pollard Rho.
Я уже пол-года как пилю брутфорсеры для BTC головоломки сатоши, перепробовал многое, в том числе и нечто похожее, что ты описал в статье, детская поделка. Коллектим миллиард точек в память и значения их скаляра. После чего открытый ключ, чей скаляр мы ищем, умножаем на производное мультипликативное обратное, если частное (точнее открытый ключ) получившийся в результате "деления" присутствует в массиве сохраненных точек, мы восстанавливаем значение скаляра от известного открытого ключа. Чтобы ненароком не пытаться делить искомый открытый ключ, чей скаляр - простое число или имеет мало делителей, каждый N кусок времени мы вычитаем из открытого ключа произвольное число равное 5% от диапазона поиска и накапливаем оффсет. После чего делим уже новый открытый ключ, получившийся в результате сужения диапазона. Но так можно делить до второго пришествия:)
Также недавно запилил брутфорсер на CUDA, вполне возможно, что с рекордной скоростью в 6.2 Gkeys/s на RTX4090 (результаты достигнуты, есть скрины), но столкнулся с проблемой с железом. После 1.5 часа работы горячая GDDR6X "начинает кипеть" и сбрасывать частоту памяти, что сносит скорость до 4.9 Gkeys/s. Я как GPU майнер, при холодном ядре кипящие и визжащие банки памяти.
Сейчас пытаюсь это победить.
Silicon lottery в чистом виде.
Вот ссылки на проекты: https://github.com/Dookoo2
Шелест карандаша по блокноту сотрудника роскомнадзора слышу я.
Как я НЕ взломал ED25519