так ведь мы же должны найти 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, что тоже "в теме"
статья вызвала у меня неоднозначные чувства. с одной стороны - монументальный труд, явно выходящий за рамки простого обзора. Чего стоят только формулы, выложенные в виде картинок (да. Тогда еще хабр не позволял вставлять формулы - автор, мягко сказано, знатно помучился). При внимательном чтении все вроде бы сходится. Но при попытке реализовать самостоятельно тесты по описанным алгоритмам, сразу бросаются в глаза грубые опечатки с первой же главы. Например решил я реализовать Частотный блочный тест. и впал в ступор. а как рассчитываются числа pi?
считаю так - не сходится, считаю по-другому - не сходится. нарыл исходники тестов с сайта nist.gov - стало чуть понятнее, но не сильно. и подобных косяков в статье море. чтобы все их вскрыть, потребуется писать новую отдельную и не менее монументальную статью. я не готов, сорян.
И да - вишенка на торте. В середине статьи автор признается, что последовательность, которую он гонял в тестах - вообще ни разу не случайна, и автор привел формулы, ее порождающие (читай главу Тест на линейную сложность). Но внимание: все предыдущие тесты проходили очень успешно. И сразу доверие к таким тестам куда-то испарилось. Масло мне в огонь подкинул комментатор @vasiatka, после чего доверие к тестам NIST вообще упало. Неслучайность последовательности, перманентно мелькавшей в тексте, на мой проф.деформированный взгляд видна невооруженным глазом, однако проходит все тесты. Вот взгяните на такие последовательности: 1011010101 - предложенная в статье 11011001111111011110010101011110001010101111101101110001001100000 - цифры числа Пи 110010001111100011001010001010001101111100011100000111 - цифры корня из двух Не знаю, как по мне, видно что нижние 2 последовательности более сложны и имеют меньше повторяющихся паттернов.
А вообще статья шикарна, несмотря на выявленные недостатки. Автору плюс в карму. Хабр - торт.
Прошу меня простить за столь резкий комментарий. Вы не обязаны ничего представлять общественности, наоборот это я должен доказывать. Но проблемы сортировки на GPU что я озвучил выше - никуда не делись. И я действительно не встречал годные реализации сортировок на GPU для, например, использования СУБД
Тогда Nlogk=10^9*10(примерно 10 - логарифма тут двоичный).
Итого почти 10 млд. Операций экономия. Среди этих операций-операции сравнения ключей, которые для составных ключей могут быть очень не быстрыми. Стоимость сравнения строк, например, O(n). Так что насчет мизерной выгоды нисколько не согласен.
Я специально для вас опубликую код и замеры на массиве из 1 миллиарда записей. Но чуть позже. Просто мне необходимо привести свой экспериментальный проект в божеский вид. А то в процессе экспериментов там лапша по-гуще ассамблера сейчас
Такой размер подойдёт? Сортируемые данные будут находить на диске в момент выполнения сортировки. В оперативную память моего старенького компьютера они не поместится. Поэтому сортироваться будут по факту индексы( указатели на json-записи).Сортируемые данные будут являться json-записями , ключом сортировки - будет текстовое поле объекта длиной до 16 символов.
Сделаем замеры скорости в операциях и по времени. Вас устроит такой вариант теста?
Да тут один человек сказал, что выигрыш мизерный . Даже если бы я представил измерения для 100ГБ элементов - вряд ли это бы повлияло на столь высокую оценку.
На основе представленных измерений тенденция видна. Как доказательство, что концепция верна .
Представьте общественности алгоритм сортировки на GPU составных объектов, физически размещаемых на файловых носителях. большинство авторов больше как сортировку натуральных чисел предложить не могут. даже сортировку строк никто не предложил. А все потому что при сортировке подобных данных вас необходимо работать с указателями. Т.е. вы фактически перемещаете указатели, а сами данные физически не сортируются. В этом проблема
так ведь мы же должны найти 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, что тоже "в теме"
статья вызвала у меня неоднозначные чувства. с одной стороны - монументальный труд, явно выходящий за рамки простого обзора. Чего стоят только формулы, выложенные в виде картинок (да. Тогда еще хабр не позволял вставлять формулы - автор, мягко сказано, знатно помучился). При внимательном чтении все вроде бы сходится. Но при попытке реализовать самостоятельно тесты по описанным алгоритмам, сразу бросаются в глаза грубые опечатки с первой же главы. Например решил я реализовать Частотный блочный тест. и впал в ступор. а как рассчитываются числа pi?
считаю так - не сходится, считаю по-другому - не сходится. нарыл исходники тестов с сайта nist.gov - стало чуть понятнее, но не сильно. и подобных косяков в статье море. чтобы все их вскрыть, потребуется писать новую отдельную и не менее монументальную статью. я не готов, сорян.
И да - вишенка на торте. В середине статьи автор признается, что последовательность,
которую он гонял в тестах - вообще ни разу не случайна, и автор привел формулы, ее порождающие (читай главу Тест на линейную сложность).
Но внимание: все предыдущие тесты проходили очень успешно. И сразу доверие к таким тестам куда-то испарилось. Масло мне в огонь подкинул комментатор @vasiatka, после чего
доверие к тестам NIST вообще упало.
Неслучайность последовательности, перманентно мелькавшей в тексте, на мой проф.деформированный взгляд
видна невооруженным глазом, однако проходит все тесты. Вот взгяните на такие последовательности:
1011010101 - предложенная в статье
11011001111111011110010101011110001010101111101101110001001100000 - цифры числа Пи
110010001111100011001010001010001101111100011100000111 - цифры корня из двух
Не знаю, как по мне, видно что нижние 2 последовательности более сложны и имеют меньше повторяющихся паттернов.
А вообще статья шикарна, несмотря на выявленные недостатки. Автору плюс в карму. Хабр - торт.
Интересное мнение. А можете провести примеры когда кластеризация невозможна?
Сложность плавной сортировки брал на Википедии. Об оценке, что вы привели - не слышал.
Спасибо за конструктивный комментарий
Прошу меня простить за столь резкий комментарий. Вы не обязаны ничего представлять общественности, наоборот это я должен доказывать. Но проблемы сортировки на GPU что я озвучил выше - никуда не делись. И я действительно не встречал годные реализации сортировок на GPU для, например, использования СУБД
Хорошо. Пусть N=10^9, k=1000,
Тогда Nlogk=10^9*10(примерно 10 - логарифма тут двоичный).
Итого почти 10 млд. Операций экономия. Среди этих операций-операции сравнения ключей, которые для составных ключей могут быть очень не быстрыми. Стоимость сравнения строк, например, O(n). Так что насчет мизерной выгоды нисколько не согласен.
Я специально для вас опубликую код и замеры на массиве из 1 миллиарда записей. Но чуть позже. Просто мне необходимо привести свой экспериментальный проект в божеский вид. А то в процессе экспериментов там лапша по-гуще ассамблера сейчас
Такой размер подойдёт? Сортируемые данные будут находить на диске в момент выполнения сортировки. В оперативную память моего старенького компьютера они не поместится. Поэтому сортироваться будут по факту индексы( указатели на json-записи).Сортируемые данные будут являться json-записями , ключом сортировки - будет текстовое поле объекта длиной до 16 символов.
Сделаем замеры скорости в операциях и по времени. Вас устроит такой вариант теста?
Да тут один человек сказал, что выигрыш мизерный . Даже если бы я представил измерения для 100ГБ элементов - вряд ли это бы повлияло на столь высокую оценку.
На основе представленных измерений тенденция видна. Как доказательство, что концепция верна .
Представьте общественности алгоритм сортировки на GPU составных объектов, физически размещаемых на файловых носителях. большинство авторов больше как сортировку натуральных чисел предложить не могут. даже сортировку строк никто не предложил. А все потому что при сортировке подобных данных вас необходимо работать с указателями. Т.е. вы фактически перемещаете указатели, а сами данные физически не сортируются. В этом проблема