{"draftJsState":{"blocks":[{"data":{"image":{"id":"630dd65939ab7d17217eee5f"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"2tc3b"},{"data":{},"depth":0,"entityRanges":[{"key":0,"length":16,"offset":0}],"inlineStyleRanges":[],"text":"CRYPTO DEEP TECH","type":"unstyled","key":"6hnbt"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":97,"style":"BOLD"},{"length":5,"offset":114,"style":"BOLD"},{"length":1,"offset":97,"style":"ITALIC"},{"length":5,"offset":114,"style":"ITALIC"}],"text":"In this article, we will consider several useful and efficient algorithms for an elliptic curve E over a field GF(p) given by the short Weierstrass equation","type":"unstyled","key":"fnc5j"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"у^2 = х^3 + Ах + В","type":"unstyled","key":"du691"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":44,"offset":0,"style":"BOLD"},{"length":1,"offset":43,"style":"ITALIC"}],"text":"Algorithm for generating a point on curve E","type":"unordered-list-item","key":"7he7a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":27,"offset":0,"style":"BOLD"}],"text":"Algorithm for adding points","type":"unordered-list-item","key":"d1glm"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":24,"offset":0,"style":"BOLD"}],"text":"Doubling Point Algorithm","type":"unordered-list-item","key":"2vd8d"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":47,"offset":0,"style":"BOLD"}],"text":"Algorithm for finding an integer multiple point","type":"unordered-list-item","key":"8neiq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":71,"offset":0,"style":"BOLD"}],"text":"Algorithm for finding an integer multiple point (scalar multiplication)","type":"unordered-list-item","key":"74ip5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":99,"offset":0,"style":"BOLD"},{"length":1,"offset":38,"style":"ITALIC"},{"length":1,"offset":55,"style":"ITALIC"},{"length":7,"offset":72,"style":"ITALIC"},{"length":1,"offset":98,"style":"ITALIC"}],"text":"Algorithm for constructing a divisor D over a curve E with support supp(D) of a given size d","type":"unordered-list-item","key":"3g8th"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":106,"offset":0,"style":"BOLD"},{"length":7,"offset":67,"style":"ITALIC"},{"length":1,"offset":92,"style":"ITALIC"},{"length":7,"offset":106,"style":"ITALIC"}],"text":"Miller’s algorithm for calculating the value of the Weyl function f n, P from a divisor D such that supp(D) ∩ {P, O} = ∅","type":"unordered-list-item","key":"53pgg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":8,"offset":0,"style":"BOLD"},{"length":4,"offset":9,"style":"ITALIC"}],"text":"Pairing Weil","type":"unordered-list-item","key":"lcok"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Modular operations (integers) on a finite field (or Galois field)","type":"header-three","key":"d36ft"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"ITALIC"},{"length":10,"offset":74,"style":"ITALIC"},{"length":11,"offset":136,"style":"ITALIC"}],"text":"x mod n means «the remainder of n after dividing x». In other words, if x = an + b and a, b ∈ integer, and also 0 ≤ b ≤ n − 1, then x mod n = b .","type":"ordered-list-item","key":"9q79i"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"BOLD"},{"length":8,"offset":119,"style":"BOLD"},{"length":8,"offset":188,"style":"BOLD"},{"length":12,"offset":15,"style":"ITALIC"},{"length":1,"offset":37,"style":"ITALIC"},{"length":7,"offset":62,"style":"ITALIC"},{"length":8,"offset":96,"style":"ITALIC"},{"length":8,"offset":119,"style":"ITALIC"},{"length":8,"offset":151,"style":"ITALIC"},{"length":12,"offset":170,"style":"ITALIC"},{"length":8,"offset":188,"style":"ITALIC"}],"text":"Reverse : if ax = 1 mod n , then a is the reciprocal of x mod n . There are two popular solution methods : • Method 1 : Try each value for a < n as long as xa mod n = 1 .• Method 2 : Euclidean method which is usually used to solve the inverse problem of large integers, so it is recommended to use method 1 to solve inverse problem of small integers.","type":"ordered-list-item","key":"5neai"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Elliptic Curve Point Operation","type":"header-three","key":"5s28t"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":17,"offset":11,"style":"ITALIC"},{"length":1,"offset":53,"style":"ITALIC"},{"length":4,"offset":80,"style":"ITALIC"},{"length":4,"offset":91,"style":"ITALIC"},{"length":4,"offset":145,"style":"ITALIC"},{"length":4,"offset":156,"style":"ITALIC"}],"text":"The point P(x 0 , y 0 ) on the elliptic curve E means: its coordinates x 0 and y 0 are elements of the field, and the coordinates x 0 and y 0 satisfy the equation.","type":"unstyled","key":"apl3v"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":34,"offset":0,"style":"BOLD"},{"length":4,"offset":43,"style":"ITALIC"},{"length":1,"offset":54,"style":"ITALIC"}],"text":"Adding points on an elliptic curve : Let P, Q and R be three points on an elliptic curve. Adding points P + Q = R.","type":"ordered-list-item","key":"7mi3h"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":36,"offset":0,"style":"BOLD"},{"length":4,"offset":45,"style":"ITALIC"}],"text":"Doubling points on an elliptic curve : Let P, Q be two points on an elliptic curve. Doubling Points P + P = 2P = Q","type":"ordered-list-item","key":"7bhcn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":18,"offset":0,"style":"BOLD"},{"length":11,"offset":287,"style":"BOLD"},{"length":1,"offset":27,"style":"ITALIC"},{"length":1,"offset":55,"style":"ITALIC"},{"length":2,"offset":103,"style":"ITALIC"},{"length":22,"offset":122,"style":"ITALIC"},{"length":1,"offset":149,"style":"ITALIC"},{"length":1,"offset":167,"style":"ITALIC"},{"length":2,"offset":185,"style":"ITALIC"},{"length":1,"offset":218,"style":"ITALIC"},{"length":6,"offset":264,"style":"ITALIC"},{"length":1,"offset":297,"style":"ITALIC"}],"text":"Dot multiplication : let P be a point on the curve E , defined in the equationDot multiplication nP is defined as nP = P + P + P + … + P ( n times), where n is an integer; nP is also a point on the same E curve .\nThe minimal natural number a with aP = O is called the order of P .\nDot multiplication is widely required in elliptic curve cryptosystems.\n","type":"ordered-list-item","key":"v208"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Divider","type":"header-three","key":"5e6b0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":0,"style":"BOLD"},{"length":24,"offset":71,"style":"BOLD"},{"length":1,"offset":20,"style":"ITALIC"},{"length":1,"offset":35,"style":"ITALIC"},{"length":1,"offset":94,"style":"ITALIC"}],"text":"Divisor (Divisor) D on a curve E is a convenient way to denote a multiset of points on E , written as a formal sum","type":"unstyled","key":"7p0c2"},{"data":{"image":{"id":"630dd66cc140de62a26e9fae"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"evo5j"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":28,"style":"ITALIC"},{"length":13,"offset":46,"style":"ITALIC"}],"text":"The set of all divisors on E is denoted by Div F q (E) and forms a group in which the addition of divisors is natural.","type":"unordered-list-item","key":"ftppu"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":17,"offset":74,"style":"ITALIC"}],"text":"Zero Divisor: This is the divisor for all n P = 0, the zero divisor is 0 ∈ Div F q (E) .","type":"unordered-list-item","key":"9ejgr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":14,"style":"ITALIC"},{"length":6,"offset":78,"style":"ITALIC"}],"text":"If the field F q is not specific, it can be omitted and simply written as Div(E) to denote the divisor group.","type":"unordered-list-item","key":"amk03"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Function f divided by E","type":"header-three","key":"e9gl1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":27,"style":"ITALIC"},{"length":1,"offset":34,"style":"ITALIC"},{"length":1,"offset":124,"style":"ITALIC"},{"length":1,"offset":132,"style":"ITALIC"}],"text":"The divisor of a function f by E is used to denote the intersection points (and their multiplicities) of the functions f and E .","type":"unstyled","key":"etbal"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Pairing Weil","type":"header-three","key":"9t3mj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":39,"style":"ITALIC"},{"length":25,"offset":80,"style":"ITALIC"},{"length":14,"offset":137,"style":"ITALIC"}],"text":"The Weil pairing, which is denoted by e m , takes as input a pair of points P, Q ∈ E[m] and produces as output a root _m of unity e m ( P , Q) . The bilinearity of the Weyl pairing is expressed by the equations","type":"unstyled","key":"fou01"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":67,"offset":0,"style":"ITALIC"}],"text":"e m (P 1 + P 2 , Q) \\u003d e m (P 1 , Q) * e m (P2, B),","type":"unstyled","key":"a6c33"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":66,"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":"cutdr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":9,"offset":0,"style":"BOLD"},{"length":1,"offset":16,"style":"ITALIC"},{"length":1,"offset":24,"style":"ITALIC"}],"text":"The Weil pair P and Q is the number","type":"unstyled","key":"boa83"},{"data":{"image":{"id":"630dd66c3d860117b0f631c8"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"6cr5q"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":7,"style":"ITALIC"},{"length":21,"offset":53,"style":"ITALIC"},{"length":11,"offset":195,"style":"ITALIC"},{"length":4,"offset":242,"style":"ITALIC"},{"length":4,"offset":251,"style":"ITALIC"},{"length":1,"offset":262,"style":"ITALIC"}],"text":"where S ∈ E is any point satisfying the condition S ∉ {O, P, −Q, P − Q} . (This ensures that all quantities on the right hand side are defined and non-zero.) One can check that the value of e m (P,Q) does not depend on the choice of f P , f Q and S .","type":"unstyled","key":"bmhp"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"An Efficient Weil Pairing Computation Algorithm","type":"header-three","key":"26ghg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":5,"style":"ITALIC"},{"length":1,"offset":104,"style":"ITALIC"}],"text":"Let E be an elliptic curve and let P = (x P ,y P ) and Q = (x Q , y Q ) be nonzero points on E .","type":"unstyled","key":"b5mfd"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":5,"style":"ITALIC"},{"length":1,"offset":45,"style":"ITALIC"},{"length":1,"offset":53,"style":"ITALIC"},{"length":1,"offset":90,"style":"ITALIC"},{"length":3,"offset":102,"style":"ITALIC"},{"length":1,"offset":144,"style":"ITALIC"},{"length":1,"offset":184,"style":"ITALIC"}],"text":"Let λ be the slope of the line connecting P and Q , or the slope of the tangent to E at P if P = Q. (If the line is vertical, we set λ = ∞.) Define a function g P, Q on E as follows:","type":"unstyled","key":"2nlmf"},{"data":{"image":{"id":"630dd66c67e19b0968ced12a"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"9l69e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"then","type":"unstyled","key":"89dhq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":42,"style":"ITALIC"}],"text":"div(g P, Q ) = [P] + [Q] — [P + Q] — [ O ].","type":"unstyled","key":"frvo9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":18,"offset":0,"style":"BOLD"}],"text":"Miller’s algorithm","type":"unstyled","key":"jufi"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":3,"offset":5,"style":"ITALIC"},{"length":1,"offset":45,"style":"ITALIC"}],"text":"Let m ≥ and write the binary extension of m as","type":"unstyled","key":"170sp"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":65,"offset":0,"style":"ITALIC"}],"text":"m \\u003d m 0 + m 1 * 2 + m 2 * 2 2 + + m n — 1 2 n — 1","type":"unstyled","key":"eajfl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":14,"offset":5,"style":"ITALIC"},{"length":13,"offset":26,"style":"ITALIC"},{"length":4,"offset":87,"style":"ITALIC"}],"text":"for m i ∈ {0, 1} and m n — 1 ≠ 0 . The following algorithm returns a function f P whose divisor satisfies the condition","type":"unstyled","key":"7j75p"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":6,"style":"ITALIC"},{"length":1,"offset":17,"style":"ITALIC"},{"length":1,"offset":23,"style":"ITALIC"},{"length":2,"offset":33,"style":"ITALIC"},{"length":5,"offset":44,"style":"ITALIC"},{"length":1,"offset":56,"style":"ITALIC"}],"text":"div( f P ) = m [ P ] — [ mP ] — ( m — 1 ) [ O ],","type":"unstyled","key":"4v2ad"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":7,"offset":21,"style":"ITALIC"},{"length":7,"offset":35,"style":"ITALIC"}],"text":"where the functions g T, T and g T, P used by the algorithm are defined in (a).","type":"unstyled","key":"bot6f"},{"data":{"image":{"id":"630dd66c196d4006a229c144"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"770l"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":8,"offset":19,"style":"ITALIC"},{"length":4,"offset":42,"style":"ITALIC"},{"length":1,"offset":53,"style":"ITALIC"},{"length":1,"offset":59,"style":"ITALIC"},{"length":1,"offset":67,"style":"ITALIC"},{"length":1,"offset":73,"style":"ITALIC"}],"text":"In particular, if P ∈ E[m] , then div( f P ) = m [ P ] − m [ O ].","type":"unstyled","key":"6sv29"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Requirement","type":"header-three","key":"bn75b"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Python 3.5","type":"unordered-list-item","key":"fkpt4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"numpy","type":"unordered-list-item","key":"4c81q"},{"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":"auh36"},{"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":"60tnr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"header-three","key":"7vcpt"},{"data":{},"depth":0,"entityRanges":[{"key":1,"length":6,"offset":0}],"inlineStyleRanges":[{"length":6,"offset":0,"style":"BOLD"}],"text":"Source","type":"unstyled","key":"asmlf"},{"data":{},"depth":0,"entityRanges":[{"key":2,"length":27,"offset":11}],"inlineStyleRanges":[{"length":38,"offset":0,"style":"BOLD"}],"text":"Telegram: https://t.me/cryptodeeptech","type":"unstyled","key":"75qc7"},{"data":{},"depth":0,"entityRanges":[{"key":3,"length":28,"offset":8}],"inlineStyleRanges":[{"length":36,"offset":0,"style":"BOLD"}],"text":"Video: https://youtu.be/gFbiBCNPsFk","type":"unstyled","key":"8mtig"},{"data":{},"depth":0,"entityRanges":[{"key":4,"length":49,"offset":8}],"inlineStyleRanges":[{"length":57,"offset":0,"style":"BOLD"}],"text":"Source: https://cryptodeeptech.ru/algorithms-for-secp256k","type":"unstyled","key":"25vu9"},{"data":{},"depth":0,"entityRanges":[{"key":5,"length":11,"offset":0}],"inlineStyleRanges":[],"text":"Без рубрики","type":"unstyled","key":"4hsll"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"flL7RQxaQsIL2JqlIAIo"}],"entityMap":{"0":{"data":{"href":"https://cryptodeeptech.ru/author/cryptodeeptech/","url":"https://cryptodeeptech.ru/author/cryptodeeptech/"},"mutability":"MUTABLE","type":"LINK"},"1":{"data":{"href":"https://github.com/demining/CryptoDeepTools/tree/main/04AlgorithmsForSecp256k","url":"https://github.com/demining/CryptoDeepTools/tree/main/04AlgorithmsForSecp256k"},"mutability":"MUTABLE","type":"LINK"},"2":{"data":{"href":"https://t.me/cryptodeeptech","url":"https://t.me/cryptodeeptech"},"mutability":"MUTABLE","type":"LINK"},"3":{"data":{"href":"https://youtu.be/gFbiBCNPsFk","url":"https://youtu.be/gFbiBCNPsFk"},"mutability":"MUTABLE","type":"LINK"},"4":{"data":{"href":"https://cryptodeeptech.ru/algorithms-for-secp256k","url":"https://cryptodeeptech.ru/algorithms-for-secp256k"},"mutability":"MUTABLE","type":"LINK"},"5":{"data":{"href":"https://cryptodeeptech.ru/category/%d0%b1%d0%b5%d0%b7-%d1%80%d1%83%d0%b1%d1%80%d0%b8%d0%ba%d0%b8/","url":"https://cryptodeeptech.ru/category/%d0%b1%d0%b5%d0%b7-%d1%80%d1%83%d0%b1%d1%80%d0%b8%d0%ba%d0%b8/"},"mutability":"MUTABLE","type":"LINK"}}},"mentions":[]}