{"id":80,"date":"2018-11-10T17:18:23","date_gmt":"2018-11-10T16:18:23","guid":{"rendered":"http:\/\/blog.himitsu.eu\/?p=80"},"modified":"2019-10-07T11:18:42","modified_gmt":"2019-10-07T09:18:42","slug":"elliptic-curves-and-how-to-use-them-part-two","status":"publish","type":"post","link":"https:\/\/blog.himitsu.eu\/?p=80","title":{"rendered":"Elliptic curves and how to use them (part two)"},"content":{"rendered":"<p><a href=\"http:\/\/blog.himitsu.eu\/?p=48\">Go to part one<\/a><\/p>\n<p>There should be presented a bit simplistic theory from the so-called &#8220;algebraic structures&#8221; before showing method of implementing elliptic curves on digital devices.<br \/>\nSo what is this <strong>algebraic structure<\/strong>? This is a non-empty set with at least one operation in this set: <img loading=\"lazy\" class=\"mathtex-equation-editor alignnone\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S%3D%20%20%5C%7B%20%20A%2C%20%5Cast_%7B1%7D%2C%20%5Cast_%7B2%7D%2C%20...%7D%20%5C%7D\" alt=\"S= \\{ A, \\ast_{1}, \\ast_{2}, ... \\}\" width=\"113\" height=\"21\" align=\"absmiddle\" \/>. What can contain such a set? Numbers, colors, cities etc:\u00a0 <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=A%3D%20%20%5C%7B%20%20a_%7B1%7D%2C%20a_%7B2%7D%2C%20a_%7B3%7D%2C%20...%7D%20%5C%7D\" alt=\"A= \\{ a_{1}, a_{2}, a_{3}, ...} \\}\" align=\"absmiddle\" \/>. What can this operation be like? Addition, multiplication, but also returning a city lying between two selected cities: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast_%7Bi%7D%3A%20a_%7Bx%7D%20%5Ctimes%20a_%7By%7D%20%5Crightarrow%20a_%7Bz%7D\" alt=\"\\ast_{i}: a_{x} \\times a_{y} \\rightarrow a_{z}\" align=\"absmiddle\" \/> .<img loading=\"lazy\" class=\"alignnone size-full wp-image-82\" src=\"http:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/cities_SA.png\" alt=\"\" width=\"1243\" height=\"601\" srcset=\"https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/cities_SA.png 1243w, https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/cities_SA-300x145.png 300w, https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/cities_SA-768x371.png 768w, https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/cities_SA-1024x495.png 1024w\" sizes=\"(max-width: 1243px) 100vw, 1243px\" \/><\/p>\n<p>For the needs of EC, we will consider structures with finite sets with two-arguments operation or two two-arguments operations: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S%3D%20%5C%7B%20A%2C%20%5Cast%20%5C%7D\" alt=\"S= \\{ A, \\ast \\}\" align=\"absmiddle\" \/> or <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S%3D%20%5C%7B%20A%2C%20%5Cast_%7B1%7D%2C%20%5Cast_%7B2%7D%20%5C%7D\" alt=\"S= \\{ A, \\ast_{1}, \\ast_{2} \\}\" align=\"absmiddle\" \/>.<\/p>\n<p>If the structure <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S%3D%20%5C%7B%20A%2C%20%5Cast%20%5C%7D\" alt=\"S= \\{ A, \\ast \\}\" align=\"absmiddle\" \/> meets the following requirements:<\/p>\n<ul>\n<li>operation <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast\" alt=\"\\ast\" align=\"absmiddle\" \/> is <span id=\"result_box\" class=\"short_text\" lang=\"en\"><span class=\"\">associative<\/span><\/span>: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5C(a_%7B1%7D%20%5Cast%20a_%7B2%7D%5C)%20%5Cast%20a_%7B3%7D%20%3D%20a_%7B1%7D%20%5Cast%20%5C(%20a_%7B2%7D%20%5Cast%20a_%7B3%7D%5C)\" alt=\"\\(a_{1} \\ast a_{2}\\) \\ast a_{3} = a_{1} \\ast \\( a_{2} \\ast a_{3}\\)\" align=\"absmiddle\" \/><\/li>\n<li>set A has a identity element e for operation <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast\" alt=\"\\ast\" align=\"absmiddle\" \/>: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_%7Bi%7D%20%5Cast%20e%20%3D%20e%20%5Cast%20a_%7Bi%7D%20%3D%20a_%7Bi%7D\" alt=\"a_{i} \\ast e = e \\ast a_{i} = a_{i}\" align=\"absmiddle\" \/><\/li>\n<li>each element <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_%7Bi%7D\" alt=\"a_{i}\" align=\"absmiddle\" \/> from set A have it&#8217;s inverse element <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_%7Bj%7D\" alt=\"a_{j}\" align=\"absmiddle\" \/>: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_%7Bi%7D%20%5Cast%20a_%7Bj%7D%20%3D%20a_%7Bj%7D%20*%20a_%7Bi%7D%20%3D%20e\" alt=\"a_{i} \\ast a_{j} = a_{j} * a_{i} = e\" align=\"absmiddle\" \/><\/li>\n<\/ul>\n<p>we can call this kind of algebraic structure a <strong>group<\/strong>.<br \/>\nAdditionally, if the <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast\" alt=\"\\ast\" align=\"absmiddle\" \/> operation is commutative for each <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_%7Bi%7D%2C%20a_%7Bj%7D\" alt=\"a_{i}, a_{j}\" align=\"absmiddle\" \/>: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_%7Bi%7D%20%5Cast%20a_%7Bj%7D%20%3D%20a_%7Bj%7D%20*%20a_%7Bi%7D\" alt=\"a_{i} \\ast a_{j} = a_{j} * a_{i}\" align=\"absmiddle\" \/>, then this group is called an commutative or <strong>abelian<\/strong> group.<\/p>\n<p>There are two ways of group&#8217;s write:<\/p>\n<ul>\n<li>additive: G = {A, +}, where the identity element is presented as &#8216;0&#8217; and the inverse element of a as -a (like in &#8216;traditional&#8217; adding)<\/li>\n<li>multiplicative: G = {A, <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast\" alt=\"\\ast\" align=\"absmiddle\" \/>}, where the identity element is presented as &#8216;1&#8217;, and the inverse element of a as <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a%20%5E%7B-1%7D\" alt=\"a ^{-1}\" align=\"absmiddle\" \/> (like in &#8216;traditional&#8217; multiplication).<\/li>\n<\/ul>\n<p>If element A which is not a identity element is selected from the set A, which will be used to the following operations: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_%7Bg%7D%20%5Cast%20a_%7Bg%7D%20%3D%20a_%7B1%7D%2C%20a_%7Bg%7D%20%5Cast%20a_%7B1%7D%20%3D%20a_%7B2%7D%2C%20a_%7Bg%7D%20%5Cast%20a_%7B2%7D%20%3D%20a_%7B3%7D%2C%20...%2C%20a_%7Bg%7D%20%5Cast%20a_%7Bn%7D%20%3D%20e\" alt=\"a_{g} \\ast a_{g} = a_{1}, a_{g} \\ast a_{1} = a_{2}, a_{g} \\ast a_{2} = a_{3}, ..., a_{g} \\ast a_{n} = e\" align=\"absmiddle\" \/>, it creates a subset <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=H%20%3D%20%5C%7Be%2C%20a_%7Bg%7D%2C%20a_%7B1%7D%2C%20a_%7B2%7D%2C%20a_%7B3%7D%2C%20...%2C%20a_%7Bn%7D%20%20%5C%7D\" alt=\"H = \\{e, a_{g}, a_{1}, a_{2}, a_{3}, ..., a_{n} \\}\" align=\"absmiddle\" \/> (<img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=H%5Csubseteq%20G\" alt=\"H\\subseteq G\" align=\"absmiddle\" \/> &#8211; H is subset of G) which with <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast\" alt=\"\\ast\" align=\"absmiddle\" \/> operation is a subgroup that is called a <strong>cyclic<\/strong> group, and <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_g\" alt=\"a_g\" align=\"absmiddle\" \/> is a <strong>generator<\/strong> of this group. The set H can be also two-element <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5C%7Be%2C%20a_g%5C%7D\" alt=\"\\{e, a_g\\}\" align=\"absmiddle\" \/>, and exactly a set G (H = G). So the whole group G is a cyclic group, if there is at least one element <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_g%20%5Cin%20G\" alt=\"a_g \\in G\" align=\"absmiddle\" \/>, from which any other element of the group can be created: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_i%20%3D%20i%20%5Cast%20a_g\" alt=\"a_i = i \\ast a_g\" align=\"absmiddle\" \/> (additive write) or <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_i%20%3D%20a_g%5Ei\" alt=\"a_i = a_g^i\" align=\"absmiddle\" \/> (multiplicative write).<br \/>\nIf a set of all points lying on a certain elliptical curve is taken and as a set EC and addition of two of these points will be marked as + operation (described in the previous section), then G = {EC, +} is an abelian group. A point g is also selected for creating a cyclic sub-group H = {ECH, +}.<br \/>\nAnd that&#8217;s all to show how elliptic curves work as a theory, however, this is not enough yet to show the way the EC is implemented.<\/p>\n<p>If the structure <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S%3D%5C%7BA%2C%20%5Cast_1%2C%20%5Cast_2%5C%7D\" alt=\"S=\\{A, \\ast_1, \\ast_2\\}\" align=\"absmiddle\" \/> meets the following requirements:<\/p>\n<ul>\n<li>structure <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S_1%3D%5C%7BA%2C%20%5Cast_1%5C%7D\" alt=\"S_1=\\{A, \\ast_1\\}\" align=\"absmiddle\" \/> is an abelian group (commutative)<\/li>\n<li>structure <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S_2%3D%5C%7BA%2F%20%5C%7B0%5C%7D%2C%20%5Cast_2%5C%7D\" alt=\"S_2=\\{A\/ \\{0\\}, \\ast_2\\}\" align=\"absmiddle\" \/> (without a identity element of group <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=S_1\" alt=\"S_1\" align=\"absmiddle\" \/>) is also an abelian group (commutative)<\/li>\n<li>operation <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast_2\" alt=\"\\ast_2\" align=\"absmiddle\" \/> is distributive over <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast_1\" alt=\"\\ast_1\" align=\"absmiddle\" \/>: <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=(a_i%20%5Cast_1%20a_j)%20%5Cast_2%20a_k%20%3D%20(a_i%20%5Cast_2%20a_k)%5Cast_1(a_j%5Cast_2%20a_k)\" alt=\"(a_i \\ast_1 a_j) \\ast_2 a_k = (a_i \\ast_2 a_k)\\ast_1(a_j\\ast_2 a_k)\" align=\"absmiddle\" \/> and <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=a_i%20%5Cast_2%20(a_j%20%5Cast_1%20a_k)%20%3D%20(a_i%20%5Cast_2%20a_j)%5Cast_1(a_i%5Cast_2%20a_k)\" alt=\"a_i \\ast_2 (a_j \\ast_1 a_k) = (a_i \\ast_2 a_j)\\ast_1(a_i\\ast_2 a_k)\" align=\"absmiddle\" \/><\/li>\n<\/ul>\n<p>this is the structure we call the <strong>field<\/strong> and, for simplicity, we write K = {A, +, <img class=\"mathtex-equation-editor\" src=\"http:\/\/chart.apis.google.com\/chart?cht=tx&amp;chl=%5Cast\" alt=\"\\ast\" align=\"absmiddle\" \/>}.<\/p>\n<p>Let&#8217;s now look back at the EC chart from the previous section:<\/p>\n<p><img loading=\"lazy\" class=\"alignnone wp-image-85\" src=\"http:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/ec_R_geneal_mini.png\" alt=\"\" width=\"449\" height=\"300\" srcset=\"https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/ec_R_geneal_mini.png 323w, https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/ec_R_geneal_mini-300x201.png 300w\" sizes=\"(max-width: 449px) 100vw, 449px\" \/><\/p>\n<p>The graph consists of two X, Y coordinates on which the real numbers are located. Real numbers can be added and multiplied. If an algebraic structure consisting of an infinite set of real numbers, additions and multiplication is constructed, it will turn out that such a structure is a field. Thus, it can be seen that the EC lies on a dimensional space over field.<\/p>\n<p><img loading=\"lazy\" class=\"alignnone size-full wp-image-86\" src=\"http:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/sa_elems.png\" alt=\"\" width=\"732\" height=\"333\" srcset=\"https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/sa_elems.png 732w, https:\/\/blog.himitsu.eu\/wp-content\/uploads\/2018\/11\/sa_elems-300x136.png 300w\" sizes=\"(max-width: 732px) 100vw, 732px\" \/><\/p>\n<p>We know that the field of real numbers is not suitable for implementation on digital devices due to its infinite number of elements and the need for infinite accuracy of calculations. So what field can we use? It turns out that there are two types of finite fields that are ideally suited for the software and hardware implementation. In the nearest parts, we will deal with fields for software implementation.<\/p>\n<p><a href=\"http:\/\/blog.himitsu.eu\/?p=118\">Go to part three<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Go to part one There should be presented a bit simplistic theory from the so-called &#8220;algebraic structures&#8221; before showing method of implementing elliptic curves on digital devices. So what is this algebraic structure? This is a non-empty set with at least one operation in this set: . What can contain such a set? Numbers, colors, &hellip; <a href=\"https:\/\/blog.himitsu.eu\/?p=80\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Elliptic curves and how to use them (part two)<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=\/wp\/v2\/posts\/80"}],"collection":[{"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=80"}],"version-history":[{"count":8,"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=\/wp\/v2\/posts\/80\/revisions"}],"predecessor-version":[{"id":136,"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=\/wp\/v2\/posts\/80\/revisions\/136"}],"wp:attachment":[{"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=80"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=80"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.himitsu.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=80"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}