Comments 43
GP*(n+1) = GP, GP*(n+2) = GP
Исправте GP*(n+2) = GP*2
Не раскрыт вопрос как вычислить порядок n
Спасибо большое!
Не раскрыт вопрос как вычислить порядок nАлгоритм Шуфа
Спасибо, интересная статья.
P.S.: заметил очепятку на картинке с "часами", там дважды используется C34 вместо C34 & C35
И multiply можно проще:
def multiply(self, times):
current_point = self
while times % 2 == 0:
current_point = current_point.add(current_point)
times = times // 2
result = current_point
times = times // 2
while times != 0:
current_point = current_point.add(current_point)
if times % 2 != 0:
result = result.add(current_point)
times = times // 2
return result
Только между циклами надо не делить на 2, а вычесть 1. Кстати, первый цикл не нужен:
def multiply(self, times):
a = self
b = self
n = times - 1
# a * n + b = const = result
while n != 0:
a = a.add(a)
if n % 2 != 0:
b = b.add(a)
n = n // 2
return b
Не понял правило 2 про пересечение в трех точках. Вот у меня получается пересечение только в двух. Что я упустил?
Ниже ваша линия еще раз пересекается с кривой.
допишите ниже уравнения кривой уравнение прямой и соедините эти два уравнения знаком системы уравнений
Решите систему уравнений относительно Х, подставив в уравнение кривой вместо Y значение y=ax+b, где y=ax+b уравнение прямой
Поскольку уравнение кривой станет уравнением третьей степени относительно X, то у нее три корня X0, X1 и X2.
Эти три корня Х однозначно определят У из уравнения прямой, соответственно получите координаты трех точек
Каждый раз, когда рассказывают про математическую криптографию, у меня возникает вопрос - нет ли в распоряжении правительств аналогового или просто специализированного компьютера, который решает именно эту задачу. Потому что весь расчет сложности идет для универсальных стандартных процессоров. А ведь тот же майнинг Биткойна смогли сильно ускорить за счет специализации.
Кто считает что такой вариант не возможен, то вспоминайте опыт Энигмы. Которая продавалась в третьи страны даже тогда, когда уже была эффективно взломана всеми крупными игроками.
Если существует алгоритм вычисления дискретного логарифма, известный только спецслужбам… его рано или поздно переоткроет и опубликует кто-то из математиков, не работающих на спецслужбы. habr.com/ru/post/75193
Ну по вашей ссылке как бы намекают что засекреченный алгоритм СЛИЛИ с точностью до именований переменных.
Что же касается секретных теорем, то они могут кардинально улучшить эффективность. Есть же вероятностные тесты простоты.
либо все эти секретные алгоритмы разрабатываются рептилоидами с нибиру, либо у их разработчиков есть друзья по универсистету, учителя с кафедры, студенты - которые за рюмкой чая обсуждают интересные математичекие трюки (о которых потом пишут что "кто-то, мы не знаем кто, слил засекреченный алгоритм" :) )
Я думаю в вашем примере в Англии было как в СССР. Кто-то, имеющий доступ, идет в "секретку" и набивает себе на открытую диссертацию материала. НО тут ключевой момент - в Англии правительство не заинтересовалось алгоритмом. Если бы заинтересовалось, то алгоритм хранился ГОРАЗДО лучше и чтобы его прочесть/опубликовать потребовался гораздо более серьёзный допуск и там уже человек так бы рисковать не стал.
НО за ссылку на историю - СПАСИБО! Не знал...
да ну, какая секретка, вы о чем? Эти алгоритмы не настолько сложные, чтобы идею нельзя было рассказать "на пальцах" другому такому же математику (студенту, занимающимся подобными областями математики) за парой рюмок чая. Обосновать и доказать - ну, может несколько вечеров. Это же не то же самое, что с нуля придумывать.
Там в криптографии самое сложное для передачи знания о том как шифровать НЯП - это когда для некоторых алгоритмов нужен выбор хороших констант (потому что это длинные числа).
Во-вторых, почему я так думаю - как раз тогда RSA и другие криптографы начали продвигать тему про "хороший криптоалгоритм должен быть публичным".
Вот инфа из Вики:
В 2013 году New York Times заявила, что детерминированная случайная генерация битов с двойной эллиптической кривой (или Dual_EC_DRBG) была включена в качестве национального стандарта NIST из-за влияния АНБ, которое включило преднамеренную слабость в алгоритм и рекомендуемую эллиптическую кривую. RSA Security в сентябре 2013 года выпустила рекомендацию, рекомендующую своим клиентам прекратить использование любого программного обеспечения, основанного на Dual_EC_DRBG. После разоблачения Dual_EC_DRBG как "операции АНБ под прикрытием", эксперты по криптографии также выразили обеспокоенность по поводу безопасности рекомендованных NIST эллиптических кривых[ предлагает вернуться к шифрованию на основе групп неэллиптических кривых.
Как я понимаю, тут мы имеем именно закладку в алгоритм. Кривые недостаточно хороши. НО это наводит на мысль, что возможны и более глобальные уязвимости.
Нужен квантовый компьютер. Schor algorithm.
Накину на вентилятор... Обратите внимание, что в формулах сложения точек вы не встретите параметров кривой (a или b), над которой выполняются вычисления. Я, когда делал свою песочную реализацию эллиптических кривых, был сильно удивлен, что примеры автора у меня работали корректно, даже когда я случайно взял кривую с другими параметрами. работало корректно практически все: сложение, вычитание, умножение, алгоритм Диффи-Хеллмана, даже подпись ECDSA. Ожидаемо упали тесты, проверяющие принадлежность получаемых точек кривой. Вот тут да - все "сигнализация" мработала штатно. Но вот прохождение остальных тестов - удивило.
Обратите внимание, что параметр a кривой используется только в алгоритме удвоения точек. Но для кривой Биткоина, он равен 0 и ничего в рассчетах не меняет. Я гарантирую, что вы можете взять любую другую кривую, вида
с произвольным b и все рассчеты будут по-прежнему корректно работать!
Вопрос: а не существует ли такого b, что он образует кривую на которой дискретный логарифм решается гораздо проще, чем на кривой Биткоина?
Почему автор валюты из всех стандартизированных на тот момент кривых выбрал кривую, с параметром а = 0? Нет ли тут бэкдора?
Обязательно проверьте мои утверждения. Будете удивлены.
Хотя, если бы кто-то сломал криптографию Биткоина , об этом сразу бы узнали многие. Ибо большие деньги...
вы можете взять любую другую кривую, вида
с произвольным b и все расчёты будут по-прежнему корректно работать!
Конечно будут - ведь это просто смещение кривой вдоль оси 
и на геометрический смысл сложения точек никак не влияет. И смещение вдоль оси 
не повлияет тоже.
Нет, дискретный логарифм проще не станет, потому что все кривые одинаково сложные (кроме вырожденной).
Тем не менее, криптографические атаки данное свойство и правда упрощает - ведь благодаря ему атакующему требуется найти не одну конкретную точку, а любую из подходящих точек, каждую для своего параметра b. Фактически, такая атака снижает сложность перебора в два раза (если считать в битах).
Во второй паре графиков опечатка x2 = x3+7 в обоих графиках, хотя они разные.
Не понял.
Любая прямая линия (кроме вертикальной) пересекает эллиптическую кривую ровно в 3 точках.
Контрпример: ось X пересекает график только в одной точке
Огромное спасибо за проделанную работу. Это первая статья в которой все кирпичики сложены в единое целое. Мой вам респект и уважуха!
Если операций деления не существует, почему мы называем это конечным полем, а не конечным кольцом?
Во-первых, операция деления существует, просто она невычислима за разумное время.
Во-вторых, не путайте конечное поле и множество точек эллиптической кривой над конечным полем. Проблемы с делением есть только во втором множестве.
Конечное поле — это коммутативное кольцо с единичным элементом, в котором выполняются коммутативный, ассоциативный и дистрибутивный законы. Наличие единичного элемента означает возможность операции деления в мультипликативной группе, которую можно реализовать как умножение на обратный элемент. Такой элемент всегда существует и вычисляется с полиномиальной трудоёмкостью. Например, для мультипликативной группы простого поля при помощи обобщенного алгоритма Евклида. Помимо мультипликативной группы в конечном поле имеется аддитивная группа. В ней также существует обратный элемент по сложению.
По теореме Римана-Роха группа точек эллиптической кривой (ГТЭК) — конечнопорождённая аддитивная группа. Это значит, что для каждого элемента существует обратный по сложению. Арифметика точек эллиптической кривой над простым полем, задействованная в операциях формирования/проверки ЭЦП по алгоритму ECDSA, предполагает вычисление скалярного произведения вида Q=[k mod m]G, где m — простое число (суть порядок подгруппы ГТЭК), G — образующий элемент (точка) подгруппы. При этом k может задаваться как произвольное выражение, включающее арифметические операции *, ^, /, +, -. Например, k=a*b+c и тому подобное. Может даже фигурировать корень квадратный (в алгоритме ECDSA такого нет, кончено), который вычисляется с полиномиальной трудоёмкостью по алгоритму Tonelli-Shanks. Это значит, что такие вычисления выполняются в мультипликативной и аддитивной группах простого поля. Хотя само скалярное произведение при известном k эффективно вычисляется в подгруппе ГТЭК своими методами. Причём базовый метод был известен ещё в древней Индии и применялся для быстрого экспоненциирования (возведения в степень). Между делом заметим, что этот метод можно применить для вычисления операции ^ в мультипликативной группе простого поля. С развитием computer science появились и другие, более эффективные методы вычислений.
Арифметика мультипликативной/аддитивной групп простого поля также задействована в формулах сложения и удвоения точек из подгруппы ГТЭК.
const a = 0;
const b = 7;
const p = 11;
for (let x = 0; x <= p; x ++) {
for (let y = 0; y <= p; y ++) {
if (y**2 % p === (x**3 + a * x + b) % p) {
console.log(`(${x}, ${y})`);
}
}
}
А почему верхняя граница цикла включает p, т.е. почему x <= p и y <= p, а не x < p и y < p? Учитывая, что вычисления мы ведем по модулю, разве не было бы правильно не включать p?
Много лет назад, во время обучения в аспирантуре готовил для одной из публикаций аналогичный контент (разве что без блокчейна). У Вас лучше и доходчивее, респект :)
Автору огромное спасибо за проделанный труд. Именно благодаря ваше статье, у меня, наконец, заработало вычитание точек. Спасибо за контрольные примеры! Монументальный труд. Хабр - торт!
Если оставить только алгебру, то при умножении на 2 мы имеем
А при умножении на 3
Правильно понимаю, что для взлома нужно "просто" решить такую систему уравнений?
Подпись на эллиптических кривых: всё, что нужно знать, чтобы подписать транзакцию в Bitcoin с полного нуля