{"id":311,"date":"2018-07-23T11:34:09","date_gmt":"2018-07-23T11:34:09","guid":{"rendered":"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=311"},"modified":"2018-12-27T11:56:00","modified_gmt":"2018-12-27T11:56:00","slug":"elliptic-curve-cryptosystem","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/chapter\/elliptic-curve-cryptosystem\/","title":{"rendered":"Elliptic Curve Cryptosystem"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/bBvHGWo6Yn0\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<strong>Objectives<\/strong>\r\n<ul>\r\n \t<li>\u00a0To learn about elliptic curves<\/li>\r\n \t<li>\u00a0To discuss about elliptic curve cryptosystems<\/li>\r\n \t<li>\u00a0Compare with Elgamal Cryptosystem<\/li>\r\n \t<li>To discuss about security of ECC<\/li>\r\n<\/ul>\r\n<strong>1 <\/strong><strong>Introduction<\/strong>\r\n\r\nMathematically definition of a \"Elliptic Curve\" is a smooth, projective algebraic curve of genus one and third degree with a distinct point O (at infinity).\r\n\r\n&nbsp;\r\n\r\n<strong>1.1 Elliptic Curve Equation<\/strong>\r\n\r\n&nbsp;\r\n\r\nIf we're talking about an elliptic curve in Fp, what we're talking about is a cloud of points which fulfil the \"curve equation\". This equation is:\r\n\r\n<img class=\"alignnone size-full wp-image-312\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-53.jpg\" alt=\"\" width=\"273\" height=\"34\" \/>\r\n\r\n&nbsp;\r\n\r\nHere, y, x, a and b are all within Fp, i.e. they are integers modulo p. The coefficients a and b are the so-called characteristic coefficients of the curve -- they determine what points will be on the curve.\r\n\r\n&nbsp;\r\n\r\nNote that the curve coefficients have to fulfill one condition:\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-313\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-54.jpg\" alt=\"\" width=\"179\" height=\"46\" \/>\r\n\r\n&nbsp;\r\n\r\nThis condition guarantees that the curve will not contain any singularities.\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<ol start=\"2\">\r\n \t<li><strong>Point Operations<\/strong><\/li>\r\n<\/ol>\r\nTo do any meaningful operations on an elliptic curve, one has to be able to do calculations with points of the curve. The two basic operations to perform with on-curve points are:\r\n<ol>\r\n \t<li>Point addition: R = P + Q<\/li>\r\n \t<li>Point doubling: R = P + P<\/li>\r\n<\/ol>\r\n<p style=\"text-align: justify\">Out of these operations, there's one compound operation, scalar point multiplication, which can be implemented by the two above. This will also be described. Note that adding any point to the special point at infinity yields the point, or mathematically speaking:<\/p>\r\n<img class=\"alignnone size-full wp-image-314\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-55.jpg\" alt=\"\" width=\"203\" height=\"39\" \/>\r\n<div>\r\n\r\n<strong>2.1 Point Addition<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Adding two points is not as easy as simply adding their x- and y-components and taking them modulo p. Instead it is more like connecting the two points via a line and then intersecting that line with the curve (although this operation will not yield the resulting point, but its conjugate). What it exactly relates to is not really important, however.<\/p>\r\nWhat is important is how you perform the calculation based on what you've already implemented.\r\n\r\n<\/div>\r\n<img class=\"alignnone size-full wp-image-315\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/2-44.png\" alt=\"\" width=\"309\" height=\"297\" \/>\r\n\r\nNote that point addition only works on two points which are not the same:\r\n\r\n<img class=\"alignnone size-full wp-image-316\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-56.jpg\" alt=\"\" width=\"406\" height=\"385\" \/>\r\n\r\nPoint doubling comes into play if two points shall be added which are identical, i.e.:\r\n\r\n<img class=\"alignnone size-full wp-image-318\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-58.jpg\" alt=\"\" width=\"342\" height=\"350\" \/>\r\n\r\nThese are the calculations needed to get R. Note that a, which is needed for calculating s, is one of the curve parameters:\r\n\r\n&nbsp;\r\n\r\n2.2 <strong>Scalar Point Multiplication<\/strong>\r\n\r\n&nbsp;\r\n\r\nWhen point multiplication and point doubling are implemented, one can derive from those two basic building blocks scalar point multiplication, i.e. multiplying a scalar value (a integer) with a point:\r\n\r\n&nbsp;\r\n\r\nR= KA\r\n<div>\r\n<p style=\"text-align: justify\">The inverse of that operation, i.e. finding k for a given A and R, is called the \"discrete logarithm\". This is an operation which is (without any further tricks like knowing a secret \"helper\" value) considered computationally infeasible. Therefore it lays the foundation for the ECC cryptosystem: Finding R for given k and A is easy, the opposite direction is hard -- unless you have the \"helper\" value called \"private key\".<\/p>\r\n\r\n<\/div>\r\n<strong>Elliptic Curve Cryptography<\/strong>\r\n<ul>\r\n \t<li>Elliptic curve cryptography is a public key cryptosystem just like RSA, Rabin, and El Gamal. Every user has a public and a private key. Public key is used for encryption\/signature verification. Private key is used for decryption\/signature generation. Elliptic curves are used as an extension to other current cryptosystems.\r\n<ul>\r\n \t<li>Elliptic Curve Diffie-Hellman Key Exchange<\/li>\r\n \t<li>Elliptic Curve Digital Signature Algorithm<\/li>\r\n<\/ul>\r\n<\/li>\r\n<\/ul>\r\n3.1 Curve cryptosystem parameters\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In order to turn all these mathematical basics into a cryptosystem, some parameters have to be defined that are sufficient to do meaningful operations. There are 6 distinct values for the Fp case and they comprise the so-called \"domain parameters\":<\/p>\r\n\r\n<div>\r\n<p style=\"text-align: justify\">1.\u00a0 \u00a0p: The prime number which defines the field in which the curve operates, Fp. All point operations are taken modulo p.<\/p>\r\n<p style=\"text-align: justify\">2.\u00a0\u00a0\u00a0\u00a0 a, b: The two coefficients which define the curve. These are integers.<\/p>\r\n<p style=\"text-align: justify\">3.\u00a0\u00a0\u00a0\u00a0 G: The generator or base point. A distinct point of the curve which resembles the \"start\" of the curve. This is either given in point form G or as two separate integers gx and gy<\/p>\r\n<p style=\"text-align: justify\">4.\u00a0\u00a0\u00a0\u00a0 n: The order of the curve generator point G. This is, in layman's terms, the number of different points on the curve which can be gained by multiplying a scalar with G. For most operations this value is not needed, but for digital signing using ECDSA the operations are congruent modulo n, not p.<\/p>\r\n<p style=\"text-align: justify\">5.\u00a0\u00a0\u00a0\u00a0 h: The cofactor of the curve. It is the quotient of the number of curve-points, or #E(Fp), divided by n.<\/p>\r\n\r\n<\/div>\r\n3.2 Generating a keypair\r\n\r\n&nbsp;\r\n\r\nGenerating a keypair for ECC is trivial. To get the private key, choose a random integer dA, so that\r\n<p style=\"text-align: justify\"><img class=\"alignnone size-full wp-image-319\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-59.jpg\" alt=\"\" width=\"139\" height=\"45\" \/><\/p>\r\n<p style=\"text-align: justify\">Then getting the accompanying public key QA is equally trivial, you just have to use scalar point multiplication of the private key with the generator point G:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-320\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-60.jpg\" alt=\"\" width=\"145\" height=\"37\" \/>\r\n\r\n&nbsp;\r\n\r\nNote that the public and private key are not equally exchangeable (like in RSA, where both are integers): the private key dA is a integer, but the public key QA is a point on the curve.\r\n\r\n&nbsp;\r\n<ol start=\"4\">\r\n \t<li>Encrypting using ECIES 4.1 Encryption<\/li>\r\n<\/ol>\r\n<p style=\"text-align: justify\">Performing encryption using <a href=\"http:\/\/en.wikipedia.org\/wiki\/Integrated_Encryption_Scheme\">ECIES <\/a>is then relatively easy. Let's assume we want to encrypt data with the public key QA that we just generated. Again, first choose a random number r so that<\/p>\r\n<img class=\"alignnone size-full wp-image-321\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-61.jpg\" alt=\"\" width=\"615\" height=\"314\" \/>\r\n\r\nNow, R is publicly transmitted with the message and from the point S a symmetric key is derived with which the message is encrypted. A HMAC will also be appended, but we'll skip that part here and just show the basic functionality.\r\n\r\n&nbsp;\r\n\r\n4.3.2 Decryption\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now assume that you receive a message, which is encrypted with a symmetric key. Together with that message you receive a value of R in plain text. How can you -- with the aid of your private key, of course -- recover the symmetric key? Well, that's also easy:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-324\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-62.jpg\" alt=\"\" width=\"120\" height=\"30\" \/>\r\n<p style=\"text-align: justify\">By just multiplying your private key with the publicly transmitted point R, you will receive the shared secret point S, from which you can then derive the symmetric key (with the same mechanism that the sender did generate it, of course).<\/p>\r\n&nbsp;\r\n\r\nTo see why this works so beautifully, you just have to take a look at the equations and substitute:\r\n\r\n<img class=\"alignnone size-full wp-image-325\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-63.jpg\" alt=\"\" width=\"393\" height=\"37\" \/>\r\n<div>\r\n\r\n5\u00a0\u00a0\u00a0\u00a0 Elliptic Curve Cryptosystem Analog to El Gamal\r\n\r\n&nbsp;\r\n\r\n\u2013\u00a0 Alice chooses another random integer, k from the interval [1, p-1]\r\n\r\n\u2013\u00a0 The ciphertext is a pair of points\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 PC = [ (kB), (PM + kPB) ]\r\n\r\n&nbsp;\r\n\r\nTo decrypt, Bob computes the product of the first point from PC and his private key, b\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 b * (kB)\r\n\r\n&nbsp;\r\n\r\n\u2013 Bob then takes this product and subtracts it from the second point from PC\r\n\r\n<\/div>\r\n<ul>\r\n \t<li>(PM + kPB) \u2013 [b(kB)] = PM + k(bB) \u2013 b(kB) = PM<\/li>\r\n<\/ul>\r\n\u2013\u00a0 Bob then decodes PM to get the message, M.\r\n<ol start=\"5\">\r\n \t<li><strong>Security of ECC<\/strong><\/li>\r\n<\/ol>\r\nTo protect a 128 bit AES key it would take a:\r\n\r\n&nbsp;\r\n\r\nRSA Key Size: 3072 bits\r\n\r\n&nbsp;\r\n\r\nECC Key Size: 256 bits\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-326\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/2-45.png\" alt=\"\" width=\"383\" height=\"249\" \/>\r\n\r\n&nbsp;\r\n<ol start=\"7\">\r\n \t<li><strong> Applications of ECC<\/strong><\/li>\r\n<\/ol>\r\n<ul>\r\n \t<li>Many devices are small and have limited storage and computational power. Since key size of ECC is less when compared to other public key cryptosystems, it is applicable for the following systems:\r\n<ul>\r\n \t<li>Wireless communication<\/li>\r\n \t<li>devices Smart cards<\/li>\r\n<\/ul>\r\n<\/li>\r\n \t<li>Web servers that need to handle many encryption sessions\r\n<ul>\r\n \t<li>Any application where security is needed but lacks the power, storage and computational power that is necessary for our current cryptosystems<\/li>\r\n<\/ul>\r\n<\/li>\r\n<\/ul>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n\r\n&nbsp;\r\n\r\nWe studied :\r\n\r\n&nbsp;\r\n\r\n\u2013\u00a0 about elliptic curves\r\n\r\n\u2013\u00a0 Point operations on the elliptic curves\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">\u2013\u00a0 Encryption and decryption operations using elliptic curves<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">\u2013\u00a0 Different usage of ECC.<\/span>\r\n\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Elliptic Curve Cryptosystem<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/bBvHGWo6Yn0\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n<\/div>\r\n<img class=\"alignnone size-full wp-image-328\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-64.jpg\" alt=\"\" width=\"601\" height=\"372\" \/>\r\n\r\n&nbsp;","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/bBvHGWo6Yn0\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Objectives<\/strong><\/p>\n<ul>\n<li>\u00a0To learn about elliptic curves<\/li>\n<li>\u00a0To discuss about elliptic curve cryptosystems<\/li>\n<li>\u00a0Compare with Elgamal Cryptosystem<\/li>\n<li>To discuss about security of ECC<\/li>\n<\/ul>\n<p><strong>1 <\/strong><strong>Introduction<\/strong><\/p>\n<p>Mathematically definition of a &#8220;Elliptic Curve&#8221; is a smooth, projective algebraic curve of genus one and third degree with a distinct point O (at infinity).<\/p>\n<p>&nbsp;<\/p>\n<p><strong>1.1 Elliptic Curve Equation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>If we&#8217;re talking about an elliptic curve in Fp, what we&#8217;re talking about is a cloud of points which fulfil the &#8220;curve equation&#8221;. This equation is:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-312\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-53.jpg\" alt=\"\" width=\"273\" height=\"34\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-53.jpg 273w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-53-65x8.jpg 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-53-225x28.jpg 225w\" sizes=\"auto, (max-width: 273px) 100vw, 273px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Here, y, x, a and b are all within Fp, i.e. they are integers modulo p. The coefficients a and b are the so-called characteristic coefficients of the curve &#8212; they determine what points will be on the curve.<\/p>\n<p>&nbsp;<\/p>\n<p>Note that the curve coefficients have to fulfill one condition:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-313\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-54.jpg\" alt=\"\" width=\"179\" height=\"46\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-54.jpg 179w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-54-65x17.jpg 65w\" sizes=\"auto, (max-width: 179px) 100vw, 179px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>This condition guarantees that the curve will not contain any singularities.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<ol start=\"2\">\n<li><strong>Point Operations<\/strong><\/li>\n<\/ol>\n<p>To do any meaningful operations on an elliptic curve, one has to be able to do calculations with points of the curve. The two basic operations to perform with on-curve points are:<\/p>\n<ol>\n<li>Point addition: R = P + Q<\/li>\n<li>Point doubling: R = P + P<\/li>\n<\/ol>\n<p style=\"text-align: justify\">Out of these operations, there&#8217;s one compound operation, scalar point multiplication, which can be implemented by the two above. This will also be described. Note that adding any point to the special point at infinity yields the point, or mathematically speaking:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-314\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-55.jpg\" alt=\"\" width=\"203\" height=\"39\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-55.jpg 203w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-55-65x12.jpg 65w\" sizes=\"auto, (max-width: 203px) 100vw, 203px\" \/><\/p>\n<div>\n<p><strong>2.1 Point Addition<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Adding two points is not as easy as simply adding their x- and y-components and taking them modulo p. Instead it is more like connecting the two points via a line and then intersecting that line with the curve (although this operation will not yield the resulting point, but its conjugate). What it exactly relates to is not really important, however.<\/p>\n<p>What is important is how you perform the calculation based on what you&#8217;ve already implemented.<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-315\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/2-44.png\" alt=\"\" width=\"309\" height=\"297\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-44.png 309w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-44-300x288.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-44-65x62.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-44-225x216.png 225w\" sizes=\"auto, (max-width: 309px) 100vw, 309px\" \/><\/p>\n<p>Note that point addition only works on two points which are not the same:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-316\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-56.jpg\" alt=\"\" width=\"406\" height=\"385\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-56.jpg 406w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-56-300x284.jpg 300w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-56-65x62.jpg 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-56-225x213.jpg 225w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-56-350x332.jpg 350w\" sizes=\"auto, (max-width: 406px) 100vw, 406px\" \/><\/p>\n<p>Point doubling comes into play if two points shall be added which are identical, i.e.:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-318\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-58.jpg\" alt=\"\" width=\"342\" height=\"350\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-58.jpg 342w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-58-293x300.jpg 293w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-58-65x67.jpg 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-58-225x230.jpg 225w\" sizes=\"auto, (max-width: 342px) 100vw, 342px\" \/><\/p>\n<p>These are the calculations needed to get R. Note that a, which is needed for calculating s, is one of the curve parameters:<\/p>\n<p>&nbsp;<\/p>\n<p>2.2 <strong>Scalar Point Multiplication<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>When point multiplication and point doubling are implemented, one can derive from those two basic building blocks scalar point multiplication, i.e. multiplying a scalar value (a integer) with a point:<\/p>\n<p>&nbsp;<\/p>\n<p>R= KA<\/p>\n<div>\n<p style=\"text-align: justify\">The inverse of that operation, i.e. finding k for a given A and R, is called the &#8220;discrete logarithm&#8221;. This is an operation which is (without any further tricks like knowing a secret &#8220;helper&#8221; value) considered computationally infeasible. Therefore it lays the foundation for the ECC cryptosystem: Finding R for given k and A is easy, the opposite direction is hard &#8212; unless you have the &#8220;helper&#8221; value called &#8220;private key&#8221;.<\/p>\n<\/div>\n<p><strong>Elliptic Curve Cryptography<\/strong><\/p>\n<ul>\n<li>Elliptic curve cryptography is a public key cryptosystem just like RSA, Rabin, and El Gamal. Every user has a public and a private key. Public key is used for encryption\/signature verification. Private key is used for decryption\/signature generation. Elliptic curves are used as an extension to other current cryptosystems.\n<ul>\n<li>Elliptic Curve Diffie-Hellman Key Exchange<\/li>\n<li>Elliptic Curve Digital Signature Algorithm<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>3.1 Curve cryptosystem parameters<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In order to turn all these mathematical basics into a cryptosystem, some parameters have to be defined that are sufficient to do meaningful operations. There are 6 distinct values for the Fp case and they comprise the so-called &#8220;domain parameters&#8221;:<\/p>\n<div>\n<p style=\"text-align: justify\">1.\u00a0 \u00a0p: The prime number which defines the field in which the curve operates, Fp. All point operations are taken modulo p.<\/p>\n<p style=\"text-align: justify\">2.\u00a0\u00a0\u00a0\u00a0 a, b: The two coefficients which define the curve. These are integers.<\/p>\n<p style=\"text-align: justify\">3.\u00a0\u00a0\u00a0\u00a0 G: The generator or base point. A distinct point of the curve which resembles the &#8220;start&#8221; of the curve. This is either given in point form G or as two separate integers gx and gy<\/p>\n<p style=\"text-align: justify\">4.\u00a0\u00a0\u00a0\u00a0 n: The order of the curve generator point G. This is, in layman&#8217;s terms, the number of different points on the curve which can be gained by multiplying a scalar with G. For most operations this value is not needed, but for digital signing using ECDSA the operations are congruent modulo n, not p.<\/p>\n<p style=\"text-align: justify\">5.\u00a0\u00a0\u00a0\u00a0 h: The cofactor of the curve. It is the quotient of the number of curve-points, or #E(Fp), divided by n.<\/p>\n<\/div>\n<p>3.2 Generating a keypair<\/p>\n<p>&nbsp;<\/p>\n<p>Generating a keypair for ECC is trivial. To get the private key, choose a random integer dA, so that<\/p>\n<p style=\"text-align: justify\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-319\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-59.jpg\" alt=\"\" width=\"139\" height=\"45\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-59.jpg 139w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-59-65x21.jpg 65w\" sizes=\"auto, (max-width: 139px) 100vw, 139px\" \/><\/p>\n<p style=\"text-align: justify\">Then getting the accompanying public key QA is equally trivial, you just have to use scalar point multiplication of the private key with the generator point G:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-320\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-60.jpg\" alt=\"\" width=\"145\" height=\"37\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-60.jpg 145w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-60-65x17.jpg 65w\" sizes=\"auto, (max-width: 145px) 100vw, 145px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Note that the public and private key are not equally exchangeable (like in RSA, where both are integers): the private key dA is a integer, but the public key QA is a point on the curve.<\/p>\n<p>&nbsp;<\/p>\n<ol start=\"4\">\n<li>Encrypting using ECIES 4.1 Encryption<\/li>\n<\/ol>\n<p style=\"text-align: justify\">Performing encryption using <a href=\"http:\/\/en.wikipedia.org\/wiki\/Integrated_Encryption_Scheme\">ECIES <\/a>is then relatively easy. Let&#8217;s assume we want to encrypt data with the public key QA that we just generated. Again, first choose a random number r so that<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-321\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-61.jpg\" alt=\"\" width=\"615\" height=\"314\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-61.jpg 615w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-61-300x153.jpg 300w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-61-65x33.jpg 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-61-225x115.jpg 225w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-61-350x179.jpg 350w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>Now, R is publicly transmitted with the message and from the point S a symmetric key is derived with which the message is encrypted. A HMAC will also be appended, but we&#8217;ll skip that part here and just show the basic functionality.<\/p>\n<p>&nbsp;<\/p>\n<p>4.3.2 Decryption<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now assume that you receive a message, which is encrypted with a symmetric key. Together with that message you receive a value of R in plain text. How can you &#8212; with the aid of your private key, of course &#8212; recover the symmetric key? Well, that&#8217;s also easy:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-324\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-62.jpg\" alt=\"\" width=\"120\" height=\"30\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-62.jpg 120w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-62-65x16.jpg 65w\" sizes=\"auto, (max-width: 120px) 100vw, 120px\" \/><\/p>\n<p style=\"text-align: justify\">By just multiplying your private key with the publicly transmitted point R, you will receive the shared secret point S, from which you can then derive the symmetric key (with the same mechanism that the sender did generate it, of course).<\/p>\n<p>&nbsp;<\/p>\n<p>To see why this works so beautifully, you just have to take a look at the equations and substitute:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-325\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-63.jpg\" alt=\"\" width=\"393\" height=\"37\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-63.jpg 393w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-63-300x28.jpg 300w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-63-65x6.jpg 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-63-225x21.jpg 225w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-63-350x33.jpg 350w\" sizes=\"auto, (max-width: 393px) 100vw, 393px\" \/><\/p>\n<div>\n<p>5\u00a0\u00a0\u00a0\u00a0 Elliptic Curve Cryptosystem Analog to El Gamal<\/p>\n<p>&nbsp;<\/p>\n<p>\u2013\u00a0 Alice chooses another random integer, k from the interval [1, p-1]<\/p>\n<p>\u2013\u00a0 The ciphertext is a pair of points<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 PC = [ (kB), (PM + kPB) ]<\/p>\n<p>&nbsp;<\/p>\n<p>To decrypt, Bob computes the product of the first point from PC and his private key, b<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 b * (kB)<\/p>\n<p>&nbsp;<\/p>\n<p>\u2013 Bob then takes this product and subtracts it from the second point from PC<\/p>\n<\/div>\n<ul>\n<li>(PM + kPB) \u2013 [b(kB)] = PM + k(bB) \u2013 b(kB) = PM<\/li>\n<\/ul>\n<p>\u2013\u00a0 Bob then decodes PM to get the message, M.<\/p>\n<ol start=\"5\">\n<li><strong>Security of ECC<\/strong><\/li>\n<\/ol>\n<p>To protect a 128 bit AES key it would take a:<\/p>\n<p>&nbsp;<\/p>\n<p>RSA Key Size: 3072 bits<\/p>\n<p>&nbsp;<\/p>\n<p>ECC Key Size: 256 bits<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-326\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/2-45.png\" alt=\"\" width=\"383\" height=\"249\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-45.png 383w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-45-300x195.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-45-65x42.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-45-225x146.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/2-45-350x228.png 350w\" sizes=\"auto, (max-width: 383px) 100vw, 383px\" \/><\/p>\n<p>&nbsp;<\/p>\n<ol start=\"7\">\n<li><strong> Applications of ECC<\/strong><\/li>\n<\/ol>\n<ul>\n<li>Many devices are small and have limited storage and computational power. Since key size of ECC is less when compared to other public key cryptosystems, it is applicable for the following systems:\n<ul>\n<li>Wireless communication<\/li>\n<li>devices Smart cards<\/li>\n<\/ul>\n<\/li>\n<li>Web servers that need to handle many encryption sessions\n<ul>\n<li>Any application where security is needed but lacks the power, storage and computational power that is necessary for our current cryptosystems<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>We studied :<\/p>\n<p>&nbsp;<\/p>\n<p>\u2013\u00a0 about elliptic curves<\/p>\n<p>\u2013\u00a0 Point operations on the elliptic curves<\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">\u2013\u00a0 Encryption and decryption operations using elliptic curves<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">\u2013\u00a0 Different usage of ECC.<\/span><\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Elliptic Curve Cryptosystem<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/bBvHGWo6Yn0\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-328\" src=\"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-64.jpg\" alt=\"\" width=\"601\" height=\"372\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-64.jpg 601w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-64-300x186.jpg 300w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-64-65x40.jpg 65w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-64-225x139.jpg 225w, https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-content\/uploads\/sites\/55\/2018\/07\/Capture-64-350x217.jpg 350w\" sizes=\"auto, (max-width: 601px) 100vw, 601px\" \/><\/p>\n<p>&nbsp;<\/p>\n","protected":false},"author":3,"menu_order":23,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-311","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":7,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/311\/revisions"}],"predecessor-version":[{"id":585,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/311\/revisions\/585"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/311\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/media?parent=311"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapter-type?post=311"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/contributor?post=311"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/license?post=311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}