{"draftJsState":{"blocks":[{"data":{"embedData":{"type":"yandex-zen-video","uuid":"v1xWRk7V16VM","previewImageData":{"id":"62d46c1073d68b4415e09223","groupId":1108048,"imageName":"pub_62d46b725f37c2164669020c_62d46c1073d68b4415e09223","namespace":"zen_doc","meta":{"mainColor":"#0088C8","origFormat":"PNG"}},"publisherId":"62a289464f3f811ccb28f02b","publicationId":"62d46b725f37c2164669020c","publisherName":"CRYPTO DEEP TECH","publisherAvatar":{"id":"62a28a1c361703532ebef76b","groupId":246004,"imageName":"pub_62a289464f3f811ccb28f02b_62a28a1c361703532ebef76b","namespace":"zen-logos","meta":{"mainColor":"#0888C8","origFormat":"JPEG"}},"isPublisherVerified":false,"publishTime":1658088602433,"title":"Полезные и эффективные алгоритмы для эллиптической кривой secp256k1","duration":395000,"customParams":{"signed_url":"AsAM7HWtjYTho0D_TxWM2Jp1RBXDvhONnoCryYfe2OYgKi1QniSggQVf1pcFHriOmybTNfZ8YTg"}}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:embed","key":"dpmta"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":97,"style":"BOLD"},{"length":5,"offset":109,"style":"BOLD"},{"length":1,"offset":97,"style":"ITALIC"},{"length":5,"offset":109,"style":"ITALIC"}],"text":"В этой статье мы рассмотрим несколько полезных и эффективных алгоритмов для эллиптической кривой E над полем GF(p) , заданной коротким уравнением Вейерштрасса","type":"unstyled","key":"8o5cc"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"у^2 = х^3 + Ах + В","type":"unstyled","key":"ael6a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":36,"offset":0,"style":"BOLD"},{"length":1,"offset":35,"style":"ITALIC"}],"text":"Алгоритм генерации точки на кривой E","type":"unordered-list-item","key":"bbuil"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":25,"offset":0,"style":"BOLD"}],"text":"Алгоритм добавления точек","type":"unordered-list-item","key":"6c3og"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":23,"offset":0,"style":"BOLD"}],"text":"Алгоритм удвоения точек","type":"unordered-list-item","key":"dnv6s"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":39,"offset":0,"style":"BOLD"}],"text":"Алгоритм нахождения целой кратной точки","type":"unordered-list-item","key":"drefi"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":61,"offset":0,"style":"BOLD"}],"text":"Алгоритм нахождения целой кратной точки (скалярное умножение)","type":"unordered-list-item","key":"4m3bi"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":83,"offset":0,"style":"BOLD"},{"length":1,"offset":29,"style":"ITALIC"},{"length":1,"offset":42,"style":"ITALIC"},{"length":7,"offset":56,"style":"ITALIC"},{"length":1,"offset":82,"style":"ITALIC"}],"text":"Алгоритм построения делителя D над кривой E с носителем supp(D) заданного размера d","type":"unordered-list-item","key":"bd5qu"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":88,"offset":0,"style":"BOLD"},{"length":6,"offset":55,"style":"ITALIC"},{"length":1,"offset":74,"style":"ITALIC"},{"length":7,"offset":88,"style":"ITALIC"}],"text":"Алгоритм Миллера для вычисления значения функции Вейля f n, P по делителю D такому, что supp(D) ∩ {P, O} = ∅","type":"unordered-list-item","key":"4in9t"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":12,"offset":0,"style":"BOLD"},{"length":18,"offset":13,"style":"ITALIC"}],"text":"Pairing Weil (Спаривание Вейля)","type":"unordered-list-item","key":"9961m"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Модульные операции (целые числа) в конечном поле (или поле Галуа)","type":"header-three","key":"bdhvo"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"ITALIC"},{"length":10,"offset":65,"style":"ITALIC"},{"length":11,"offset":120,"style":"ITALIC"}],"text":"x mod n означает «остаток n от деления x». Другими словами, если x = an + b и a, b ∈ integer, а также 0 ≤ b ≤ n − 1, то x mod n = b .","type":"ordered-list-item","key":"a5pen"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":8,"offset":0,"style":"BOLD"},{"length":7,"offset":112,"style":"BOLD"},{"length":7,"offset":181,"style":"BOLD"},{"length":12,"offset":16,"style":"ITALIC"},{"length":1,"offset":34,"style":"ITALIC"},{"length":7,"offset":64,"style":"ITALIC"},{"length":7,"offset":101,"style":"ITALIC"},{"length":7,"offset":112,"style":"ITALIC"},{"length":6,"offset":153,"style":"ITALIC"},{"length":12,"offset":165,"style":"ITALIC"},{"length":7,"offset":181,"style":"ITALIC"}],"text":"Обратное : если ax = 1 mod n , то a является обратным значением x mod n . Есть два популярных метода решения :• Метод 1 : Попробуйте каждое значение для a < n, пока xa mod n = 1 .• Метод 2 : евклидов метод, который обычно используется для решения обратной задачи больших целых чисел, поэтому рекомендуется использовать метод 1 для решения обратной задачи малых целых чисел.","type":"ordered-list-item","key":"9t59h"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Операция с точками эллиптической кривой","type":"header-three","key":"2pdi0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":13,"offset":6,"style":"ITALIC"},{"length":1,"offset":44,"style":"ITALIC"},{"length":3,"offset":70,"style":"ITALIC"},{"length":3,"offset":76,"style":"ITALIC"},{"length":3,"offset":119,"style":"ITALIC"},{"length":3,"offset":125,"style":"ITALIC"}],"text":"Точка P(x 0 , y 0 ) на эллиптической кривой E означает: ее координаты x 0 и y 0 являются элементами поля, а координаты x 0 и y 0 удовлетворяют уравнению.","type":"unstyled","key":"9c07"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":40,"offset":0,"style":"BOLD"},{"length":4,"offset":49,"style":"ITALIC"},{"length":1,"offset":56,"style":"ITALIC"}],"text":"Добавление точек на эллиптической кривой : пусть P, Q и R будут тремя точками на эллиптической кривой. Добавление очков P + Q = R.","type":"ordered-list-item","key":"9hion"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":38,"offset":0,"style":"BOLD"},{"length":4,"offset":47,"style":"ITALIC"}],"text":"Удвоение точек на эллиптической кривой : пусть P, Q — две точки на эллиптической кривой. Удвоение очков P + P = 2P = Q","type":"ordered-list-item","key":"b7t8i"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":19,"offset":0,"style":"BOLD"},{"length":10,"offset":276,"style":"BOLD"},{"length":1,"offset":28,"style":"ITALIC"},{"length":1,"offset":53,"style":"ITALIC"},{"length":2,"offset":102,"style":"ITALIC"},{"length":22,"offset":122,"style":"ITALIC"},{"length":1,"offset":147,"style":"ITALIC"},{"length":1,"offset":159,"style":"ITALIC"},{"length":2,"offset":176,"style":"ITALIC"},{"length":1,"offset":218,"style":"ITALIC"},{"length":6,"offset":258,"style":"ITALIC"},{"length":1,"offset":285,"style":"ITALIC"}],"text":"Скалярное умножение : пусть P будет точкой на кривой E , определенной в уравнении\nСкалярное умножение nP определяется как nP = P + P + P + … + P ( n раз), где n — целое число; nP также является точкой на той же кривой E .\nМинимальное натуральное число a при aP = O называется порядком P .\nСкалярное умножение широко требуется в криптосистемах с эллиптическими кривыми.","type":"ordered-list-item","key":"db46p"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Делитель","type":"header-three","key":"8ou6f"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"BOLD"},{"length":26,"offset":65,"style":"BOLD"},{"length":1,"offset":19,"style":"ITALIC"},{"length":1,"offset":31,"style":"ITALIC"},{"length":1,"offset":90,"style":"ITALIC"}],"text":"Divisor (Делитель) D на кривой E — это удобный способ обозначить мультимножество точек на E , записанное в виде формальной суммы","type":"unstyled","key":"1fq92"},{"data":{"image":{"id":"62d46d1b9f801562d75481e4"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"dmk6a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":28,"style":"ITALIC"},{"length":11,"offset":43,"style":"ITALIC"}],"text":"Множество всех делителей на E обозначается Div F q (E) и образует группу, в которой сложение делителей естественно.","type":"unordered-list-item","key":"9srno"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":15,"offset":60,"style":"ITALIC"}],"text":"Делитель нуля: это делитель для всех n P = 0, делитель нуля 0 ∈ Div F q (E) .","type":"unordered-list-item","key":"7r57k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":10,"style":"ITALIC"},{"length":6,"offset":79,"style":"ITALIC"}],"text":"Если поле F q не является конкретным, его можно опустить и просто записать как Div(E) для обозначения группы делителей.","type":"unordered-list-item","key":"f8h5s"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Делитель функции f на E","type":"header-three","key":"96hus"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":17,"style":"ITALIC"},{"length":1,"offset":22,"style":"ITALIC"},{"length":1,"offset":97,"style":"ITALIC"},{"length":1,"offset":101,"style":"ITALIC"}],"text":"Делитель функции f на E используется для обозначения точек пересечения (и их кратностей) функций f и E .","type":"unstyled","key":"4qoom"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Pairing Weil","type":"header-three","key":"bqj6a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":39,"style":"ITALIC"},{"length":18,"offset":74,"style":"ITALIC"},{"length":11,"offset":124,"style":"ITALIC"}],"text":"Спаривание Вейля, которое обозначается e m , принимает на вход пару точек P, Q ∈ E[m] и дает на выходе корень _m из единицы e m( P , Q) . Билинейность спаривания Вейля выражается уравнениями","type":"unstyled","key":"7rgvt"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":50,"offset":0,"style":"ITALIC"}],"text":"e m (P 1 + P 2 , Q) = e m (P 1 , Q) * e m (P2, В),","type":"unstyled","key":"643rv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":52,"offset":0,"style":"ITALIC"}],"text":"e m (P, Q 1 + Q 2 ) = e m (P, Q 1 ) * e m (P, Q 2 ).","type":"unstyled","key":"81olr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":6,"offset":5,"style":"BOLD"},{"length":1,"offset":11,"style":"ITALIC"},{"length":1,"offset":15,"style":"ITALIC"}],"text":"Пара Вейля P и Q — это количество","type":"unstyled","key":"5unln"},{"data":{"image":{"id":"62d46d1c996e500f07df254a"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"93a52"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":4,"style":"ITALIC"},{"length":21,"offset":49,"style":"ITALIC"},{"length":9,"offset":184,"style":"ITALIC"},{"length":3,"offset":215,"style":"ITALIC"},{"length":3,"offset":221,"style":"ITALIC"},{"length":1,"offset":227,"style":"ITALIC"}],"text":"где S ∈ E — любая точка, удовлетворяющая условию S ∉ {O, P, −Q, P − Q} . (Это гарантирует, что все величины в правой части определены и отличны от нуля.) Можно проверить, что значение e m (P,Q) не зависит от выбора f P , f Q и S .","type":"unstyled","key":"1ncgb"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Эффективный алгоритм вычисления спаривания Вейля","type":"header-three","key":"8gomq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":6,"style":"ITALIC"},{"length":1,"offset":96,"style":"ITALIC"}],"text":"Пусть E — эллиптическая кривая, и пусть P = (x P ,y P ) и Q = (x Q , y Q ) — ненулевые точки на E .","type":"unstyled","key":"1398l"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":6,"style":"ITALIC"},{"length":1,"offset":42,"style":"ITALIC"},{"length":1,"offset":46,"style":"ITALIC"},{"length":1,"offset":77,"style":"ITALIC"},{"length":3,"offset":89,"style":"ITALIC"},{"length":1,"offset":133,"style":"ITALIC"},{"length":1,"offset":169,"style":"ITALIC"}],"text":"Пусть λ будет наклоном линии, соединяющей P и Q , или наклоном касательной к E в P, если P = Q. (Если линия вертикальна, мы полагаем λ = ∞.) Определим функцию g P, Q на E следующим образом:","type":"unstyled","key":"61bl3"},{"data":{"image":{"id":"62d46d1cdcd5e07f1f612f4f"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"bn9vd"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"затем","type":"unstyled","key":"au07e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":39,"style":"ITALIC"}],"text":"div(g P, Q ) = [P] + [Q] — [P + Q] — [ O ].","type":"unstyled","key":"b9qrr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":16,"offset":0,"style":"BOLD"}],"text":"Алгоритм Миллера","type":"unstyled","key":"2gl6k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":6,"style":"ITALIC"},{"length":1,"offset":41,"style":"ITALIC"}],"text":"Пусть m ≥ и запишите двоичное расширение m как","type":"unstyled","key":"lvep"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":51,"offset":0,"style":"ITALIC"}],"text":"m = m 0 + m 1 * 2 + m 2 * 2 2 +···+ m n — 1 2 n — 1","type":"unstyled","key":"26d6k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":12,"offset":4,"style":"ITALIC"},{"length":11,"offset":19,"style":"ITALIC"},{"length":3,"offset":71,"style":"ITALIC"}],"text":"при m i ∈ {0, 1} и m n — 1 ≠ 0 . Следующий алгоритм возвращает функцию f P , делитель которой удовлетворяет условию","type":"unstyled","key":"dfu63"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":5,"style":"ITALIC"},{"length":1,"offset":13,"style":"ITALIC"},{"length":1,"offset":17,"style":"ITALIC"},{"length":2,"offset":25,"style":"ITALIC"},{"length":5,"offset":34,"style":"ITALIC"},{"length":1,"offset":44,"style":"ITALIC"}],"text":"div( f P ) = m [ P ] — [ mP ] — ( m — 1 ) [ O ],","type":"unstyled","key":"9vr4c"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":6,"offset":12,"style":"ITALIC"},{"length":7,"offset":21,"style":"ITALIC"}],"text":"где функции g T, T и g T, P, используемые алгоритмом, определены в (a).","type":"unstyled","key":"5jek0"},{"data":{"image":{"id":"62d46d1c996e500f07df254b"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"fmo7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":8,"offset":18,"style":"ITALIC"},{"length":3,"offset":37,"style":"ITALIC"},{"length":1,"offset":45,"style":"ITALIC"},{"length":1,"offset":49,"style":"ITALIC"},{"length":1,"offset":55,"style":"ITALIC"},{"length":1,"offset":59,"style":"ITALIC"}],"text":"В частности, если P ∈ E[m] , то div( f P ) = m [ P ] − m [ O ].","type":"unstyled","key":"fb93f"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Требование","type":"header-three","key":"e9sm6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Python 3.5","type":"unordered-list-item","key":"8ddoj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"numpy","type":"unordered-list-item","key":"ftcd3"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"git clone https://github.com/demining/CryptoDeepTools.git\n\ncd CryptoDeepTools/04AlgorithmsForSecp256k/\n\npip3 install numpy","type":"unstyled","key":"fioi7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"├── Curves.py <- Набор данных эллиптических кривых\n├── Divisor.py <- Создать делитель\n├── EllipticCurve.py <- Классы эллиптической кривой и точки на эллиптической кривой\n├── EuclideanAlg.py <- Расширенный алгоритм Евклида\n├── Helper.py <- Вспомогательные функции (обратные биты, мощность по модулю) \n├── Pairing.py <- Спаривания Вейля, а так же Алгоритм Миллера\n├── Tests.py <- Модульные тесты для функций\n├── Tonelli_ShanksAlg.py <- Алгоритм Тонелли – Шенкса\n├── main.py <- main","type":"unstyled","key":"1hhio"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"header-three","key":"ffsba"},{"data":{},"depth":0,"entityRanges":[{"key":0,"length":12,"offset":0}],"inlineStyleRanges":[{"length":12,"offset":0,"style":"BOLD"}],"text":"Исходный код","type":"unstyled","key":"e6rv"},{"data":{},"depth":0,"entityRanges":[{"key":1,"length":27,"offset":10}],"inlineStyleRanges":[{"length":37,"offset":0,"style":"BOLD"}],"text":"Telegram: https://t.me/cryptodeeptech","type":"unstyled","key":"1jhmv"},{"data":{},"depth":0,"entityRanges":[{"key":2,"length":28,"offset":15}],"inlineStyleRanges":[{"length":43,"offset":0,"style":"BOLD"}],"text":"Видеоматериал: https://youtu.be/gFbiBCNPsFk","type":"unstyled","key":"1q9t6"},{"data":{},"depth":0,"entityRanges":[{"key":3,"length":46,"offset":10}],"inlineStyleRanges":[{"length":56,"offset":0,"style":"BOLD"}],"text":"Источник: https://cryptodeep.ru/algorithms-for-secp256k/","type":"unstyled","key":"6a7qs"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"1e03c"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"8qb1v"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"pH52RtyPcdUd0m9PeObl"}],"entityMap":{"0":{"data":{"href":"https://github.com/demining/CryptoDeepTools/tree/main/04AlgorithmsForSecp256k","url":"https://github.com/demining/CryptoDeepTools/tree/main/04AlgorithmsForSecp256k"},"mutability":"MUTABLE","type":"LINK"},"1":{"data":{"href":"https://t.me/cryptodeeptech","url":"https://t.me/cryptodeeptech"},"mutability":"MUTABLE","type":"LINK"},"2":{"data":{"href":"https://youtu.be/gFbiBCNPsFk","url":"https://youtu.be/gFbiBCNPsFk"},"mutability":"MUTABLE","type":"LINK"},"3":{"data":{"href":"https://cryptodeep.ru/algorithms-for-secp256k/","url":"https://cryptodeep.ru/algorithms-for-secp256k/"},"mutability":"MUTABLE","type":"LINK"}}},"mentions":[]}