Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 27
Мне приходила на ум эта же идея, но применительно к факторизации целых чисел.
К слову, если таки найдете способ — кирдык будет не только биткойну, но и всей мировой банковской систем, где передача тех же SWIFT-сообщений основана на ЭЦП.
Будем надеяться что при нашей жизни этого не произойдет.
К слову, если таки найдете способ — кирдык будет не только биткойну, но и всей мировой банковской систем, где передача тех же SWIFT-сообщений основана на ЭЦП.
Будем надеяться что при нашей жизни этого не произойдет.
Эм, а разве эллиптическая кривая — это CSPRNG? А если нет — то какая уязвимость в том, что взятые с нее точки отличимы от случайной последовательности?
Ну да. Если оперировать понятими сложности, а не вероятности, то последовательность точек кривой это более простой объект, чем случайная последовательность. И если случайную последовательность принципиально трудно вычислить, то последовательность точек более предсказуема. И, кстати, почти все генераторы псевдослучайных последовательностей основываются на вычислении точек.
Ну да
"Ну да" — что? Эллиптическая кривая — это CSPRNG?
Если оперировать понятими сложности, а не вероятности, то последовательность точек кривой это более простой объект, чем случайная последовательность.
Что за понятие "сложности", и как оно формулируется математически?
Прочтите труды Колмогорова о сложности и определение случайной последовательности Мартина Лёфа.
ru.m.wikipedia.org/wiki/Колмогоровская_сложность
ru.m.wikipedia.org/wiki/Колмогоровская_сложность
Окей, со сложностью разобрались. Вернемся к первому вопросу: эллиптическая кривая — это CSPRNG?
Так кто ж проверял то? В основе многих CSPRNG лежит сложная задача и в том числе дискретного логафмирования на эллиптической кривой.
Думаю, что такую последовательность никто не проверял на соответствие требованиям CSPRNG.
Думаю, что такую последовательность никто не проверял на соответствие требованиям CSPRNG.
Так кто ж проверял то?
Для начала — а кто-то обещал?
В основе многих CSPRNG лежит сложная задача и в том числе дискретного логафмирования на эллиптической кривой.
Эм, не совсем так. Более того, есть мнение, что эллиптические кривые не надо использовать для CSPRNG.
Это общая проблема, не только эллиптических кривых. Недавно баловался, скачал криптослучайные данные на основе грозовых облаков, и обучил нейронную сеть.
В итоге в случайных данных, которые должны быть абсолютно непредсказуемы (!), можно в 50% случаях предсказывать данные. То есть вместо непредсказуемости, нейронная сеть уменьшает непредсказуемость в два раза.
Как рассчитывал:
Взял криптостойкую непредсказуемость равную x = 100%.
Затем обработал случайные данные в нейронной сети (1 мегабайт), и получил в результате новые данные. И они совпадают с исходными в полумиллионе случаев! Таким образом, непредсказуемость сбросилась вдвое, 100%/50% = 2.
Благодаря этому можно улучшить ИИ в играх, ведь как минимум в половине случаев (это доказано только что) действия игрока не будут для ИИ непредсказуемыми и он сможет использовать более правильную стратегию. Во второй половине игр действия будут непредсказуемыми, и человек победит. Таким образом игра подстраивается под любого человека — от чемпиона до новичка.
В итоге в случайных данных, которые должны быть абсолютно непредсказуемы (!), можно в 50% случаях предсказывать данные. То есть вместо непредсказуемости, нейронная сеть уменьшает непредсказуемость в два раза.
Как рассчитывал:
Взял криптостойкую непредсказуемость равную x = 100%.
Затем обработал случайные данные в нейронной сети (1 мегабайт), и получил в результате новые данные. И они совпадают с исходными в полумиллионе случаев! Таким образом, непредсказуемость сбросилась вдвое, 100%/50% = 2.
Благодаря этому можно улучшить ИИ в играх, ведь как минимум в половине случаев (это доказано только что) действия игрока не будут для ИИ непредсказуемыми и он сможет использовать более правильную стратегию. Во второй половине игр действия будут непредсказуемыми, и человек победит. Таким образом игра подстраивается под любого человека — от чемпиона до новичка.
Затем обработал случайные данные в нейронной сети (1 мегабайт), и получил в результате новые данные. И они совпадают с исходными в полумиллионе случаев! Таким образом, непредсказуемость сбросилась вдвое
Пожалуйста, объясните ваш алгоритм и расчет.
В итоге в случайных данных, которые должны быть абсолютно непредсказуемы (!), можно в 50% случаях предсказывать данные.Я, когда монетку подкидываю, тоже в 50% случаев предсказываю результат!
Мне кажется, это неспроста:)
Сомневаюсь в монетке.
1. Она может не упасть, совсем и никогда, после того как ее подбросили.
2. Она может упасть на ребро
3,4. Орел, решка
Это дает 4 варианта, каждый из которых имеет ненулевую вероятность.
Более того, если ее бросать так, чтобы падала на песок, то она может зафиксироваться в песке с любым углом наклона и считать все эти выпадения одинаковыми мне не кажется корректным.
1. Она может не упасть, совсем и никогда, после того как ее подбросили.
2. Она может упасть на ребро
3,4. Орел, решка
Это дает 4 варианта, каждый из которых имеет ненулевую вероятность.
Более того, если ее бросать так, чтобы падала на песок, то она может зафиксироваться в песке с любым углом наклона и считать все эти выпадения одинаковыми мне не кажется корректным.
Координата Y в этих кривых симметрична относительно оси X. Поэтому точки всегда имеют пару, что уже отличает указанную последовательность от случайной.
Теория Рамсея
Имхо Вам нужно привести рельеф полученной нейросети к какой то метрике (хз, что типа числа используемых нейронов), убедиться что эта метрика меньше чем число возможных точек, ДОКАЗАТЬ что нейросеть в каком то проценте оказывается права (да, согласен, будет хардкор) и тогда можно утверждать есть какая то закономерность. Но вообще интересная мысль.
Имхо Вам нужно привести рельеф полученной нейросети к какой то метрике (хз, что типа числа используемых нейронов), убедиться что эта метрика меньше чем число возможных точек, ДОКАЗАТЬ что нейросеть в каком то проценте оказывается права (да, согласен, будет хардкор) и тогда можно утверждать есть какая то закономерность. Но вообще интересная мысль.
1) Вы научили нейросеть отличать x-координату точки эллиптической кривой от случайных чисел. При этом никакой вывод о самой последовательности точек сделать нельзя, так как нейросеть у вас за один раз обрабатывает только одну координату. По сути у вас нейросеть проверяет есть ли вообще квадратный корень от x^3+a*x + b по модулю p (a,b и p из secp256k1) для заданного x или нет. Это очень несложная задача и она ни разу не является какой-либо атакой на secp256k1 или ECDLP.
2) Последовательность P(i) не является сложной для предсказания, т.к., например, P(i+1) = P(i) + G, т.е. считается довольно просто даже без знания i.
Атакой была бы возможность получить несколько бит n для данной точки P (таких что P = n*G), т.е. сократить область поиска возможных n.
Но нейросети или ГА тут врядли помогут, т.к. криптографические функции имеют слишком «узкие» минимумы среди ровного плато, чтобы их нащупал случайный или градиентный поиск.
2) Последовательность P(i) не является сложной для предсказания, т.к., например, P(i+1) = P(i) + G, т.е. считается довольно просто даже без знания i.
Атакой была бы возможность получить несколько бит n для данной точки P (таких что P = n*G), т.е. сократить область поиска возможных n.
Но нейросети или ГА тут врядли помогут, т.к. криптографические функции имеют слишком «узкие» минимумы среди ровного плато, чтобы их нащупал случайный или градиентный поиск.
А тут про атаку нет ни слова. Изучается некоторое свойство двух последовательностей.
И нейронная сеть их отличает — вот весь смысл статьи.
И кстати не X-координату, а Y.
И последовательность P(I) является очень сложной, если не знать i, G, a,b,c — параметры кривой.
Но как оказалось не сложней генератора случайных чисел. Сеть то не использует ни один из этих параметров.
Если знать параметры генератора псевдослучайной последовательности и начальное состояние — тоже очень просто вычислить всю случайную последовательность.
И нейронная сеть их отличает — вот весь смысл статьи.
И кстати не X-координату, а Y.
И последовательность P(I) является очень сложной, если не знать i, G, a,b,c — параметры кривой.
Но как оказалось не сложней генератора случайных чисел. Сеть то не использует ни один из этих параметров.
Если знать параметры генератора псевдослучайной последовательности и начальное состояние — тоже очень просто вычислить всю случайную последовательность.
> А тут про атаку нет ни слова.
Что тогда значат слова «На сегодняшний день, 01.04.18, это самая серьезная уязвимость кривой secp256k1»?
> И кстати не X-координату, а Y.
Как скажете, по коду сразу не увидел. Ну значит проверяется, есть ли x для уравнения x^3+a*x = q mod p для некоторых a,q и p. Для нейросети это не сильно сложнее, т.к. алгоритм поиска точного решения не очень сложный math.stackexchange.com/a/893074
Нейросети же достаточно понять, есть ли корни вообще и то можно ошибиться чуть-чуть.
Нейросеть у вас примерно так работает:
Скорее всего не может быть корня => на вход подан рандом, возвращаем 0.
Скорее всего может быть корень => на вход подана Y-координата точки, возвращаем 1.
> И последовательность P(I) является очень сложной, если не знать i, G, a,b,c
G и i знать не надо. Ваша нейросеть каждую Y-координату проверяет отдельно и не сопоставляет их между собой. Вы с равным успехом можете туда случайных точек кривой накидать (а не P(i) = i*G ) и результат обучения и проверки будет тот же самый.
Последовательности тут ни при чём.
Что тогда значат слова «На сегодняшний день, 01.04.18, это самая серьезная уязвимость кривой secp256k1»?
> И кстати не X-координату, а Y.
Как скажете, по коду сразу не увидел. Ну значит проверяется, есть ли x для уравнения x^3+a*x = q mod p для некоторых a,q и p. Для нейросети это не сильно сложнее, т.к. алгоритм поиска точного решения не очень сложный math.stackexchange.com/a/893074
Нейросети же достаточно понять, есть ли корни вообще и то можно ошибиться чуть-чуть.
Нейросеть у вас примерно так работает:
Скорее всего не может быть корня => на вход подан рандом, возвращаем 0.
Скорее всего может быть корень => на вход подана Y-координата точки, возвращаем 1.
> И последовательность P(I) является очень сложной, если не знать i, G, a,b,c
G и i знать не надо. Ваша нейросеть каждую Y-координату проверяет отдельно и не сопоставляет их между собой. Вы с равным успехом можете туда случайных точек кривой накидать (а не P(i) = i*G ) и результат обучения и проверки будет тот же самый.
Последовательности тут ни при чём.
«для некоторых a,q и p» — сеть их перебором находит. Смешно.
«Вы с равным успехом можете туда случайных точек кривой накидать (а не P(i) = i*G ) и результат обучения и проверки будет тот же самый.» — а Вы вместо пустых слов выложите код.
Сравните любой нейросетью (любой!) два множества случайных точек! Так я Вам без всякой нейросети и гауссиана могу сказать результат. Вы удивитесь, но это будет 0.5 accuracy. Или очень рядом. ))
«Вы с равным успехом можете туда случайных точек кривой накидать (а не P(i) = i*G ) и результат обучения и проверки будет тот же самый.» — а Вы вместо пустых слов выложите код.
Сравните любой нейросетью (любой!) два множества случайных точек! Так я Вам без всякой нейросети и гауссиана могу сказать результат. Вы удивитесь, но это будет 0.5 accuracy. Или очень рядом. ))
Если случайных байт насыпать — да, 0.5 accuracy.
А я вам предлагаю случайных точек кривой secp256k1. Вместо BN_add_word(n, 1L); делайте n рандомным.
А я вам предлагаю случайных точек кривой secp256k1. Вместо BN_add_word(n, 1L); делайте n рандомным.
Так они там случайно и начинаются. Начало последовательности выбирается случайно.
Тем же генератором, что строится случайная последовательность. Из openssl.
Если сделать n рандомным, то будет accuracy 0.5. Попробуйте, это же Ваша гипотеза и ее нужно доказать.
Если последовательность случайная, то её логарифм не сделает ее ни на бит предсказуемой.
Тем же генератором, что строится случайная последовательность. Из openssl.
Если сделать n рандомным, то будет accuracy 0.5. Попробуйте, это же Ваша гипотеза и ее нужно доказать.
Если последовательность случайная, то её логарифм не сделает ее ни на бит предсказуемой.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Bitcoin & AI. Победа неизбежна