Comments 35
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.
Во второй паре графиков опечатка 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?
Много лет назад, во время обучения в аспирантуре готовил для одной из публикаций аналогичный контент (разве что без блокчейна). У Вас лучше и доходчивее, респект :)
Подпись на эллиптических кривых: всё, что нужно знать, чтобы подписать транзакцию в Bitcoin с полного нуля