⭐ Merited by chimk (2)
Приветствую местных криптогуру!
Вижу в этой теме обсуждают в т.ч. и криптографию на эллиптических кривых, как раз есть вопрос в тему.
Дали в школе домашку - помогите решить:
Необходимо написать алго вычисления (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 )
нутром чую, тут надо какие-то итеративные численные методы задействовать, но не получается наткнуться - вводных мало(
Вижу в этой теме обсуждают в т.ч. и криптографию на эллиптических кривых, как раз есть вопрос в тему.
Дали в школе домашку - помогите решить:
Необходимо написать алго вычисления (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
Я вот из всего обсуждения вынес для себя единственную основную мысль:
публичный_ключ = рэндом * константу
все остальное (хитрость алгоритма умножения) это уже заумные частности.
По конкретно вашему вопросу у меня сразу возникают вопросы встречные: как вы определяете операцию деления по модулю? Вся криптография вроде как на том и строится, что в пространстве модулей умножать можно легко, а вот делить - хер вам, никак кроме перебора умножений.