может вопрошающий имел ввиду операцию деления точки на число? такая операция доступна. но так ка мы работаем в конечном поле Fp то деление на n реализуется через умножение на обратную величину n^(-1) (mod p).
В контексте этого существует такая точка G1, и такое число n1, что [n1]G1 = G
Возможно. Вот пруф: https://habr.com/ru/articles/692842/ . Самое лучшее описание эллиптической криптографии с примерами промежуточных рассчетов и живыми демонстрациями. Образец того, как нужно объяснять сложные вещи.
Можете засыпать меня ссаными тряпками , но const pi = 3.12 - ни разу не константа pi. Исправьте в первом примере.
По-моему разъяснять на хабре читателям зачем нужна переменная и что она значит, что такое константа -это даже не знаю как назвать. Неуважение к читателю, что ли?
Даю голову на отсечение, что и сам автор лет через 30, глянув на свой же код будет долго рвать волосы на голове и других местах в попытках понять, что же все-таки в этом коде происходит. Это сейчас: да... по горячим следам, автору все кажется очевидным и само-собой разумеющимся (по себе сужу, да - я уже стар )
Вопрос к автору: чем вам не угодила перегрузка операторов? Вы можете для класса вектор перегрузить операцию - умножение на матрицу и писать примерно так:
Vector a = new Vector(1,2,3);
Matrix m = new Matrix(1, 0, 1
2, 3, 2
1, -1, 4);
Vector c = a*m;
// умножение матриц
Matrix scaling = new Matrix(...);
Matrix translate = new Matrix(...);
Matrix rotate = new Matrix(...);
// деклаем матрицу, котора сразу и масштабирует и переносит и вращает
Matrix transform = scaling * translate * rotate;
// считаем определитель матрицы
double det = transform;
Так будет более понятно и не только вам, но и другим читателям кода. А все потому, что многие уже знают (со школы или университета), как работает умножение вектора на матрицу, и какой в итоге должен быть результат.
Нравится функциональный стиль? - пишите на соответствующем языке. На Haskel, например, можно так загнаться, что вы уже и через неделю не сможете разобраться в своем коде.
так ведь мы же должны найти 3ю точку пересечения прямой и кривой. А в формулах решение кубических уравнений не видно. ничего не понимаю. Я тупой, прошу простить.
Вообще, очень похоже на то. При сложении точек вообще параметры кривой (a,b) не фигурируют (окромя удвоения точки). Как работает эта магия? У меня все контрольные примеры автора работали даже для других кривых и при иных модулях. Магия, магия.
Автору огромное спасибо за проделанный труд. Именно благодаря ваше статье, у меня, наконец, заработало вычитание точек. Спасибо за контрольные примеры! Монументальный труд. Хабр - торт!
Накину на вентилятор... Обратите внимание, что в формулах сложения точек вы не встретите параметров кривой (a или b), над которой выполняются вычисления. Я, когда делал свою песочную реализацию эллиптических кривых, был сильно удивлен, что примеры автора у меня работали корректно, даже когда я случайно взял кривую с другими параметрами. работало корректно практически все: сложение, вычитание, умножение, алгоритм Диффи-Хеллмана, даже подпись ECDSA. Ожидаемо упали тесты, проверяющие принадлежность получаемых точек кривой. Вот тут да - все "сигнализация" мработала штатно. Но вот прохождение остальных тестов - удивило.
Обратите внимание, что параметр a кривой используется только в алгоритме удвоения точек. Но для кривой Биткоина, он равен 0 и ничего в рассчетах не меняет. Я гарантирую, что вы можете взять любую другую кривую, вида
с произвольным b и все рассчеты будут по-прежнему корректно работать!
Вопрос: а не существует ли такого b, что он образует кривую на которой дискретный логарифм решается гораздо проще, чем на кривой Биткоина?
Почему автор валюты из всех стандартизированных на тот момент кривых выбрал кривую, с параметром а = 0? Нет ли тут бэкдора?
Обязательно проверьте мои утверждения. Будете удивлены.
Хотя, если бы кто-то сломал криптографию Биткоина , об этом сразу бы узнали многие. Ибо большие деньги...
У вас всегда g = 2 при разных N. Вообще g - обязан быть примитивным корнем из N, а не просто какое то там простое число. И не для любого простого N = 2q+1 число 2 является примитивным корнем.
Почему вы не взяли значения модулей и генераторов из официального RFC, протокола (из. приложений)? А решили, что все знаете, и имеете право самовольно менять протокол? Вы хоть осознаете, что внося даже мельчайшие нюансы в реализацию в криптопротокола, вы можете серьезно нарушить его стойкость? Обратите внимание, что автор оригинального протокола не с первой попытки закончил его проектировать. Понадобилось аж 6 редакций. И независимая проверка его коллегами. Текущая вессия протокола - 6a. Почитайте оригинальную статью проф. Ву, где он обосновывает те или иные принятые им решения. Вот скажите, зачем в протоколе был принят скремблер u = H(A,B)? какую роль он играет? И почему форма модуля была выбрана автором как N = 2q+1 (где q - тоже простое число)?
Где исследования вашей переделки в профессиональном сообществе криптографов? Или вы свято верите, что ваши специалисты по криптографии самые крутые в мире, что могут вот так левой пяткой не приседая со штангой изобрести новый протокол ? Как вы формировали N? они точно все простые (или раскладываются внезапно на делители - как это проверяли) ? Вы хоть знаете сколько таких вот историй взлома было, когда разработчики забивали на ньансы протоколов и получали эпические фейлы. Как думаете почему защиту Sony взломали? Потому что конкретный программист забил болт на требование генерации уникального k, в момент формирования полписи. Он решил, что чуть умнее тех людей, кто алгоритм ECDSA придумал. Оказалось - он глупее.
Выше вам человек отписал, чем опасны игры с произвольными N. И это только поверхностный анализ вашей переделки. А если копнуть еще глубже...
я пробовал добавлять бобу его публичный верификатор, при помощи которого аналогично алиса могла бы 100% верифицировать боба. но получилось не слишком красиво. и все равно проблематику неудачно выбранных a/b это не решает
Спасибо за Вам ценное замечание. Действительно, Алиса, никак не застрахована от ситуаций, когда Боб в сговоре с Меллори и генерирует "слабые" точки. Боб может генерировать слабые точки и в результате ошибки программиста, или генератор случайных чисел использовать плохой. Тогда действительно, Меллори, сохранив дамп взаимодействия Алисы и Боба, сможет извлечь ключ сессии, подобрав секретный параметр b перебором.
К сожалению (или счастью) нет способов быстрой и достоверной проверки, что за точкой X = [n]G, прячется малое n. Если бы такой способ был, никакой криптографии на эллиптических кривых построить не удалось бы.
В своих частных экспериментах я заметил, что точки с малыми скалярами, группируются ближе к началу координат. Но это работает только в поле вещественных чисел и при "удачно" выбранной базовой точке.
Однако, хороший протокол я предложил, с закладочкой) Всякие АНБ одобряют)
Вообще обмен 6+7 разве не должен идти уже используя общий вычисленный S ?
ну формально точка S (из которой рождается k) на этом этапе используется. Функция HMAC_k - требует знание правильного ключа. Остальные параметры (A, B, i, V) открытые и всем известны (включая всяких Меллори). посылая m1 и m2 стороны демонстрируют друг другу, что пришли к общему знаменателю. Что делать дальше с общим ключом сессии - протокол не определяет. Можно, например, подписывать ajax-запросы той же hmac...
Если b = 0, то Алиса получит от боба точку О(нейтральный элемент группы). В разных реализациях О может фигурировать как (X:Z) = (1:0) или (0:1:0) — в зависимости от выбранного представления (в проектных координатах).
В этом случае Алисе не стоит посылать бобу точку А, ибо она и будет ключом сессии S, передаваемым в открытом виде.
Если a = 0 то Алиса пошлет Бобу точку A = [0x]G+[x]B = O + [x]B = [xb]G. Боб вычтет [b]V = [bx]G из точки Алисы и получит О.
И ключом сессии будет точка О. Что не есть хорошо.
Помимо этого, обоим стоит выбирать a и b большими (например, 128 бит). Для маленьких a и b решение задачи дискретного логарифма решается тупо подбором. Хотя Алиса умножает a на 128-битный x...
В п. 7 (на самом деле это 3 пакет сетевого взаимодействия) Алиса доказывает Бобу, что она выработала такой же ключ сессии, что и Боб. Это калька с оригинального протокола.
И далее Алиса доказывает Бобу своим m2, что тоже "в теме"
так вы сейчас практически озвучили проблему дискретного логарифма, зная точки [a]G и [b]G найти точку [ab]G
может вопрошающий имел ввиду операцию деления точки на число? такая операция доступна. но так ка мы работаем в конечном поле Fp то деление на n реализуется через умножение на обратную величину n^(-1) (mod p).
В контексте этого существует такая точка G1, и такое число n1, что [n1]G1 = G
n1*G1 - буде точка, не скаляр. вот замечательная статья, проясняющая такие моменты https://habr.com/ru/articles/692842/
Возможно. Вот пруф: https://habr.com/ru/articles/692842/ . Самое лучшее описание эллиптической криптографии с примерами промежуточных рассчетов и живыми демонстрациями. Образец того, как нужно объяснять сложные вещи.
Можете засыпать меня ссаными тряпками , но const pi = 3.12 - ни разу не константа pi. Исправьте в первом примере.
По-моему разъяснять на хабре читателям зачем нужна переменная и что она значит, что такое константа -это даже не знаю как назвать. Неуважение к читателю, что ли?
Скажите, на ваш взгляд интерфейсы WebcryptoApi, можно считать примером оверинжиниринга?
Вот такой, например, понятный код. источник https://habr.com/ru/articles/259841/
Даю голову на отсечение, что и сам автор лет через 30, глянув на свой же код будет долго рвать волосы на голове и других местах в попытках понять, что же все-таки в этом коде происходит. Это сейчас: да... по горячим следам, автору все кажется очевидным и само-собой разумеющимся (по себе сужу, да - я уже стар )
Вопрос к автору: чем вам не угодила перегрузка операторов? Вы можете для класса вектор перегрузить операцию - умножение на матрицу и писать примерно так:
Так будет более понятно и не только вам, но и другим читателям кода. А все потому, что многие уже знают (со школы или университета), как работает умножение вектора на матрицу, и какой в итоге должен быть результат.
Нравится функциональный стиль? - пишите на соответствующем языке. На Haskel, например, можно так загнаться, что вы уже и через неделю не сможете разобраться в своем коде.
так ведь мы же должны найти 3ю точку пересечения прямой и кривой. А в формулах решение кубических уравнений не видно. ничего не понимаю. Я тупой, прошу простить.
Вообще, очень похоже на то. При сложении точек вообще параметры кривой (a,b) не фигурируют (окромя удвоения точки). Как работает эта магия? У меня все контрольные примеры автора работали даже для других кривых и при иных модулях. Магия, магия.
Сорри, не видел ваш комментарий выше
Автору огромное спасибо за проделанный труд. Именно благодаря ваше статье, у меня, наконец, заработало вычитание точек. Спасибо за контрольные примеры! Монументальный труд. Хабр - торт!
Накину на вентилятор... Обратите внимание, что в формулах сложения точек вы не встретите параметров кривой (a или b), над которой выполняются вычисления. Я, когда делал свою песочную реализацию эллиптических кривых, был сильно удивлен, что примеры автора у меня работали корректно, даже когда я случайно взял кривую с другими параметрами. работало корректно практически все: сложение, вычитание, умножение, алгоритм Диффи-Хеллмана, даже подпись ECDSA. Ожидаемо упали тесты, проверяющие принадлежность получаемых точек кривой. Вот тут да - все "сигнализация" мработала штатно. Но вот прохождение остальных тестов - удивило.
Обратите внимание, что параметр a кривой используется только в алгоритме удвоения точек. Но для кривой Биткоина, он равен 0 и ничего в рассчетах не меняет. Я гарантирую, что вы можете взять любую другую кривую, вида
с произвольным b и все рассчеты будут по-прежнему корректно работать!
Вопрос: а не существует ли такого b, что он образует кривую на которой дискретный логарифм решается гораздо проще, чем на кривой Биткоина?
Почему автор валюты из всех стандартизированных на тот момент кривых выбрал кривую, с параметром а = 0? Нет ли тут бэкдора?
Обязательно проверьте мои утверждения. Будете удивлены.
Хотя, если бы кто-то сломал криптографию Биткоина , об этом сразу бы узнали многие. Ибо большие деньги...
Малая теорема Ферма: p^(n-1)(mod m) = 1. Используйте для вычисления обратных чисел в поле F(m)
У вас всегда g = 2 при разных N. Вообще g - обязан быть примитивным корнем из N, а не просто какое то там простое число. И не для любого простого N = 2q+1 число 2 является примитивным корнем.
Почему вы не взяли значения модулей и генераторов из официального RFC, протокола (из. приложений)? А решили, что все знаете, и имеете право самовольно менять протокол? Вы хоть осознаете, что внося даже мельчайшие нюансы в реализацию в криптопротокола, вы можете серьезно нарушить его стойкость? Обратите внимание, что автор оригинального протокола не с первой попытки закончил его проектировать. Понадобилось аж 6 редакций. И независимая проверка его коллегами. Текущая вессия протокола - 6a. Почитайте оригинальную статью проф. Ву, где он обосновывает те или иные принятые им решения. Вот скажите, зачем в протоколе был принят скремблер u = H(A,B)? какую роль он играет? И почему форма модуля была выбрана автором как N = 2q+1 (где q - тоже простое число)?
Где исследования вашей переделки в профессиональном сообществе криптографов? Или вы свято верите, что ваши специалисты по криптографии самые крутые в мире, что могут вот так левой пяткой не приседая со штангой изобрести новый протокол ? Как вы формировали N? они точно все простые (или раскладываются внезапно на делители - как это проверяли) ? Вы хоть знаете сколько таких вот историй взлома было, когда разработчики забивали на ньансы протоколов и получали эпические фейлы. Как думаете почему защиту Sony взломали? Потому что конкретный программист забил болт на требование генерации уникального k, в момент формирования полписи. Он решил, что чуть умнее тех людей, кто алгоритм ECDSA придумал. Оказалось - он глупее.
Выше вам человек отписал, чем опасны игры с произвольными N. И это только поверхностный анализ вашей переделки. А если копнуть еще глубже...
Поясните пожалуйста, как реализуется эта уязвимость?
А если к моменту взаимодействия клиента и сервера некий MItM будет обладать верификатором v ? это позволит ему получить сессионный ключ?
я пробовал добавлять бобу его публичный верификатор, при помощи которого аналогично алиса могла бы 100% верифицировать боба. но получилось не слишком красиво. и все равно проблематику неудачно выбранных a/b это не решает
Да, к сожалению, алиса не знает с кем общается: с бобом или кем-то другим. это существенный недостаток схемы. как это исправить - путей пока не вижу.
Спасибо за Вам ценное замечание. Действительно, Алиса, никак не застрахована от ситуаций, когда Боб в сговоре с Меллори и генерирует "слабые" точки. Боб может генерировать слабые точки и в результате ошибки программиста, или генератор случайных чисел использовать плохой. Тогда действительно, Меллори, сохранив дамп взаимодействия Алисы и Боба, сможет извлечь ключ сессии, подобрав секретный параметр b перебором.
К сожалению (или счастью) нет способов быстрой и достоверной проверки, что за точкой X = [n]G, прячется малое n. Если бы такой способ был, никакой криптографии на эллиптических кривых построить не удалось бы.
В своих частных экспериментах я заметил, что точки с малыми скалярами, группируются ближе к началу координат. Но это работает только в поле вещественных чисел и при "удачно" выбранной базовой точке.
Однако, хороший протокол я предложил, с закладочкой) Всякие АНБ одобряют)
ну формально точка S (из которой рождается k) на этом этапе используется. Функция HMAC_k - требует знание правильного ключа. Остальные параметры (A, B, i, V) открытые и всем известны (включая всяких Меллори). посылая m1 и m2 стороны демонстрируют друг другу, что пришли к общему знаменателю. Что делать дальше с общим ключом сессии - протокол не определяет. Можно, например, подписывать ajax-запросы той же hmac...
Если b = 0, то Алиса получит от боба точку О(нейтральный элемент группы). В разных реализациях О может фигурировать как (X:Z) = (1:0) или (0:1:0) — в зависимости от выбранного представления (в проектных координатах).
В этом случае Алисе не стоит посылать бобу точку А, ибо она и будет ключом сессии S, передаваемым в открытом виде.
Если a = 0 то Алиса пошлет Бобу точку A = [0x]G+[x]B = O + [x]B = [xb]G. Боб вычтет [b]V = [bx]G из точки Алисы и получит О.
И ключом сессии будет точка О. Что не есть хорошо.
Помимо этого, обоим стоит выбирать a и b большими (например, 128 бит). Для маленьких a и b решение задачи дискретного логарифма решается тупо подбором. Хотя Алиса умножает a на 128-битный x...
В п. 7 (на самом деле это 3 пакет сетевого взаимодействия) Алиса доказывает Бобу, что она выработала такой же ключ сессии, что и Боб. Это калька с оригинального протокола.
И далее Алиса доказывает Бобу своим m2, что тоже "в теме"