Математика и алгоритмы биткоина.

[n00by]

Факторизацию числа.

Факторизацию числа делает любой ленивый с помощью компьютера. Функция divmod в любом языке программирования дает идентичный результат. Другое дело EC шифрование и связанное с ним.
Согласен, что знание публичного ключа существенно увеличивает шансы стырить приватный, но они все еще призрачные (в сравнении с количеством значений). Однако, факторизация заранее неизвестного целого числа это задача, у которой нет решения в принципе.

[kzv]

В смысле: "сумели разложить"?
Что конкретно китайцы сделали с этим числом?

Факторизацию числа.

Простите за тупой вопрос: китайцы годятся тем, что сумели разложить на простые множители число 1 005 973
Это которые китайцы? Те, что строили Великую Стену или их прадедушки?

[kzv]

В смысле: "сумели разложить"?
Что конкретно китайцы сделали с этим числом?

Факторизацию числа.

Простите за тупой вопрос: китайцы годятся тем, что сумели разложить на простые множители число 1 005 973
Это которые китайцы? Те, что строили Великую Стену или их прадедушки?

Я вам ссылочку на статью скину

https://www.quintessencelabs.com/blog/breaking-rsa-encryption-update-state-art/

А, ну так бы сразу и говорили: "китайские ученые на якобы квантовом компьютере научились делать то, что любой школьник умеет делать калькулятором".
Вообще конечно вещь захватывающая: несколько лабораторий в мире заявляют, что у них есть настоящие квантовые компьютеры и даже предоставляют онлайн доступ для всех желающих попробовать свои алгоритмы. Беда в том, что эти типа компьютеры состоят из менее чем сотни кубитов и поэтому придумать хоть какой-то рабочий алгоритм для такого  - это само по себе научное открытие!

[kzv]

Особенно более захватывает, что NIST сообщил об устойчивости ECDSA до 2030 года.
Но с текущими тенденциями сроки могут слегка сдвинутся.
 

В 2010 году обычные компьютеры смогли разложить на множители 768-битное число. Чтобы сделать то же самое квантовыми компьютерами, нужно 147,454 кубитов (так в вашей ссылке написано).

Смотрим прогресс кубитов по википедии
В 2001 году IBM сообщила, что у нее есть 7-кубитный квантовый компьютер
В 2017 году заявлено об изобретении 53-кубитного квантового компьютера
В 2018 году типа изобрели 72-кубитный квантовый компьютер
В 2019 китайцы обрадовали 89-кубитным компьютером.

За последние три года, прогресс действительно на лицо: в среднем добавляют 15 кубитов в год!
Похоже и правда, сроки когда квантовый компьютер сможет делать то же, что компьютеры прошлого - слегка сдвигаются... На 10 000 лет в будущее примерно ))

[kzv]

Тогда вот новость: D-Wave анонсировала квантовый компьютер с 5640 кубитами.

Да-да. Это в статье из вашей ссылки написано. А в википедии написано, что IBM сделала 7-кубитный компьютер еще в 2001 году...

Квантовых компьютеров уже огромное кол-во с разными архитектурами, как и методов оптимизации.

Ага, их тысячи миллионов и на их разработку уже потрачено и еще потратят не один миллиард, но за последние 20 лет все они вместе взятые смогли решить задачу которую грамотный пятикласник способен решить за 10 минут с помощью блокнота, ручки и китайского калькулятора )))

Советую Вам получше изучить тематику квантовых компьютеров

Я вижу вы большой специалист в этой области? Помогите мне тоже ее изучить.

[investgroup]

В смысле: "сумели разложить"?
Что конкретно китайцы сделали с этим числом?

Факторизацию числа.

Простите за тупой вопрос: китайцы годятся тем, что сумели разложить на простые множители число 1 005 973
Это которые китайцы? Те, что строили Великую Стену или их прадедушки?

я такие числа потрошил на простые множители еще на IBM PC XT лет 20 назад...

Советую Вам получше изучить тематику квантовых компьютеров

Я вижу вы большой специалист в этой области? Помогите мне тоже ее изучить.

получи фашист гранату...


Меняюсь - ссылку на перевод статьи с научного на человеческий

https://arxiv.org/pdf/1108.3445.pdf

[kzv]

Пока что квантовые компьютеры похожи на такую секту и пирамиду, по сравнению с которой биткоин - детские шалости )

[investgroup]

e-mail взломать не пробовали?   С паролем всего-то 5-10 лоховских символов...


PS  после N попытки подбирать дальше просто не сможете.  N = например 5

PPS  в SCO-юниксе тоже такой прикол был - после каждой попытки задержка увеличивалась...

[Doka]

Приветствую местных криптогуру!
Вижу в этой теме обсуждают в т.ч. и криптографию на эллиптических кривых, как раз есть вопрос в тему.

Дали в школе домашку - помогите решить:

Необходимо написать алго вычисления (1 / a) mod p, используя "Euclidean Inversion"  

Условия:
* а и р тут 256 битные,  
* р - константа ( p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F )
* нету ограничений на число циклов и разрядность машины, на которой это решается (пусть разрядность будет даже 256)
* ALU машины не умеет делать операции в floating point
* ALU машины не умеет делать деление (+ , - и умножение по-прежнему доступны)


mod p традиционным способом можно было бы сделать через итеративное вычитание и проверку условия (1/a) <= p, но как реализовать используя "Euclidean Inversion" непонятно, именно этот кейс не рассматривается в интернетах при описании (есть целая книжка по ней  https://math.ru/lib/files/pdf/mp-seria/035_zhizhilkin.pdf )

нутром чую, тут надо какие-то итеративные численные методы задействовать, но не получается наткнуться - вводных мало(

[kzv]

Приветствую местных криптогуру!
Вижу в этой теме обсуждают в т.ч. и криптографию на эллиптических кривых, как раз есть вопрос в тему.

Дали в школе домашку - помогите решить:

Необходимо написать алго вычисления (1 / a) mod p, используя "Euclidean Inversion" 

Условия:
* а и р тут 256 битные, 
* р - константа ( p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F )
* нету ограничений на число циклов и разрядность машины, на которой это решается (пусть разрядность будет даже 256)
* ALU машины не умеет делать операции в floating point
* ALU машины не умеет делать деление (+ , - и умножение по-прежнему доступны)


mod p традиционным способом можно было бы сделать через итеративное вычитание и проверку условия (1/a) <= p, но как реализовать используя "Euclidean Inversion" непонятно, именно этот кейс не рассматривается в интернетах при описании (есть целая книжка по ней  https://math.ru/lib/files/pdf/mp-seria/035_zhizhilkin.pdf )

нутром чую, тут надо какие-то итеративные численные методы задействовать, но не получается наткнуться - вводных мало(

Где вы тут гуру увидели?
Весь этот топик, по сути, попытка домохозяек разобраться в том, что написано в хабро-статье из седьмого поста https://bitcointalk.org/index.php?topic=5075972.msg48243414#msg48243414

Я вот из всего обсуждения вынес для себя единственную основную мысль:

публичный_ключ = рэндом * константу

все остальное (хитрость алгоритма умножения) это уже заумные частности.

По конкретно вашему вопросу у меня сразу возникают вопросы встречные: как вы определяете операцию деления по модулю? Вся криптография вроде как на том и строится, что в пространстве модулей умножать можно легко, а вот делить - хер вам, никак кроме перебора умножений.

[Coin-1]

Необходимо написать алго вычисления (1 / a) mod p, используя "Euclidean Inversion"  

Условия:
* а и р тут 256 битные,  
* р - константа ( p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F )
* нету ограничений на число циклов и разрядность машины, на которой это решается (пусть разрядность будет даже 256)

Обычно для имплементации очень больших чисел используются специальные классы, позволяющие работать с массивами 32-х или 64-битных чисел как с одним числом. Если рассматривать, например, распространённый язык программирования JavaScript, который по умолчанию функционирует в интернет-браузерах, то можно применять следующие JS-библиотеки BigInteger и BigNumber, например:
https://github.com/silentmatt/javascript-biginteger/
https://github.com/MikeMcl/bignumber.js/

* ALU машины не умеет делать операции в floating point
* ALU машины не умеет делать деление (+ , - и умножение по-прежнему доступны)


mod p традиционным способом можно было бы сделать через итеративное вычитание и проверку условия (1/a) <= p, но как реализовать используя "Euclidean Inversion" непонятно, именно этот кейс не рассматривается в интернетах при описании

По всей видимости, Вам нужно расчитать число по формуле: a^-1 mod p

В общем-то, это стандартная функция, которая применяется в криптографии RSA и называется ModInverse. В протоколе Bitcoin эта криптография не задействована, хотя при обилии недостатков и высокой ресурсоёмкости у RSA есть положительные характеристики.

Можете посмотреть реализацию Вашей задачи, например, здесь:
https://stackoverflow.com/questions/26985808/calculating-the-modular-inverse-in-javascript

Вот более подробная статья на английской Википедии, но перевода на русский язык пока нет:
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

[crypto_trader#43xzEXrP]

Какие на данный момент существуют алгоритмы
для решения задачи дискретного логарифмирования на несуперсингулярной эллиптической кривой в конечном поле?
Имеются ли полиномиальные или хотя-бы субэкспоненциальные алгоритмы? А как насчёт квантовых алго?