Alternative Elliptic Curve Representations
draft-ietf-lwig-curve-representations-08

Appendix G.  Further Cousins of Curve25519

G.1.  Further Alternative Representations

   The Weierstrass curve Wei25519 is isomorphic to the Weierstrass curve
   Wei25519.2 defined over GF(p), with as base point the pair (G2X,G2Y),
   and isogenous to the Weierstrass curve Wei25519.-3 defined over
   GF(p), with as base point the pair (G3X, G3Y), where parameters are
   as specified in Appendix G.3 and where the related mappings are as
   specified in Appendix G.2.

G.2.  Further Switching

   Each affine point (X, Y) of Wei25519 corresponds to the point (X',
   Y'):=(X*s^2,Y*s^3) of Wei25519.2, where s is the element of GF(p)
   defined by

   s   20343593038935618591794247374137143598394058341193943326473831977
       39407761440

       (=0x047f6814 6d568b44 7e4552ea a5ed633d 02d62964 a2b0a120
       5e7941e9 375de020),

   while the point at infinity of Wei25519 corresponds to the point at
   infinity of Wei25519.2.  (Here, we used the mapping of Appendix F.3.)

Struik                  Expires January 25, 2020               [Page 33]
Internet-Draft         lwig-curve-representations              July 2019

   Under this mapping, the base point (GX, GY) of Wei25519 corresponds
   to the base point (G2X,G2Y) of Wei25519.2.  The inverse mapping maps
   the affine point (X', Y') of Wei25519.2 to (X,Y):=(X'/s^2,Y'/s^3) of
   Wei25519, while mapping the point at infinity O of Wei25519.2 to the
   point at infinity O of Wei25519.  Note that this mapping (and its
   inverse) involves a modular multiplication of both coordinates with
   fixed constants s^2 and s^3 (respectively, 1/s^2 and 1/s^3), which
   can be precomputed.

   Each affine point (X,Y) of Wei25519 corresponds to the point
   (X',Y'):=(X1*t^2,Y1*t^3) of Wei25519.-3, where
   (X1,Y1)=(u(X)/w(X)^2,Y*v(X)/w(X)^3), where u, v, and w are the
   polynomials with coefficients in GF(p) as defined in Appendix H.1 and
   where t is the element of GF(p) defined by

   t   35728133398289175649586938605660542688691615699169662967154525084
       644181596229

       (=0x4efd6829 88ff8526 e189f712 5999550c e9ef729b ed1a7015
       73b1bab8 8bfcd845),

   while the point at infinity of Wei25519 corresponds to the point at
   infinity of Wei25519.-3.  (Here, we used the isogenous mapping of
   Appendix F.4.)  Under this isogenous mapping, the base point (GX,GY)
   of Wei25519 corresponds to the base point (G3X,G3Y) of Wei25519.-3.
   The dual isogeny maps the affine point (X',Y') of Wei25519.-3 to the
   affine point (X,Y):=(u'(X1)/w'(X1)^2,Y1*v'(X1)/w'(X1)^3) of Wei25519,
   where (X1,Y1)=(X'/t^2,Y'/t^3) and where u', v', and w' are the
   polynomials with coefficients in GF(p) as defined in Appendix H.2,
   while mapping the point at infinity O of Wei25519.-3 to the point at
   infinity O of Wei25519.  Under this dual isogenous mapping, the base
   point (G3X, G3Y) of Wei25519.-3 corresponds to a multiple of the base
   point (GX, GY) of Wei25519, where this multiple is l=47 (the degree
   of the isogeny; see the description in Appendix F.4).  Note that this
   isogenous map (and its dual) primarily involves the evaluation of
   three fixed polynomials involving the x-coordinate, which takes
   roughly 140 modular multiplications (or less than 5-10% relative
   incremental cost compared to the cost of an elliptic curve scalar
   multiplication).

G.3.  Further Domain Parameters

   The parameters of the Weierstrass curve with a=2 that is isomorphic
   with Wei25519 and the parameters of the Weierstrass curve with a=-3
   that is isogenous with Wei25519 are as indicated below.  Both domain
   parameter sets can be exploited directly to derive more efficient
   point addition formulae, should an implementation facilitate this.

Struik                  Expires January 25, 2020               [Page 34]
Internet-Draft         lwig-curve-representations              July 2019

   General parameters: same as for Wei25519 (see Appendix E.3)

   Weierstrass curve-specific parameters (for Wei25519.2, i.e., with
   a=2):

   a   2 (=0x02)

   b   12102640281269758552371076649779977768474709596484288167752775713
       178787220689

       (=0x1ac1da05 b55bc146 33bd39e4 7f94302e f19843dc f669916f
       6a5dfd01 65538cd1)

   G2X 10770553138368400518417020196796161136792368198326337823149502681
       097436401658

       (=0x17cfeac3 78aed661 318e8634 582275b6 d9ad4def 072ea193
       5ee3c4e8 7a940ffa)

   G2Y 54430575861508405653098668984457528616807103332502577521161439773
       88639873869

       (=0x0c08a952 c55dfad6 2c4f13f1 a8f68dca dc5c331d 297a37b6
       f0d7fdcc 51e16b4d)

   Weierstrass curve-specific parameters (for Wei25519.-3, i.e., with
   a=-3):

   a   -3

       (=0x7fffffff ffffffff ffffffff ffffffff ffffffff ffffffff
       ffffffff ffffffea)

   b   29689592517550930188872794512874050362622433571298029721775200646
       451501277098

       (=0x41a3b6bf c668778e be2954a4 b1df36d1 485ecef1 ea614295
       796e1022 40891faa)

   G3X 53837179229940872434942723257480777370451127212339198133697207846
       219400243292

       (=0x7706c37b 5a84128a 3884a5d7 1811f1b5 5da3230f fb17a8ab
       0b32e48d 31a6685c)

   G3Y 69548073091100184414402055529279970392514867422855141773070804184
       60388229929

Struik                  Expires January 25, 2020               [Page 35]
Internet-Draft         lwig-curve-representations              July 2019

       (=0x0f60480c 7a5c0e11 40340adc 79d6a2bf 0cb57ad0 49d025dc
       38d80c77 985f0329)

Appendix H.  Isogeny Details

   The isogeny and dual isogeny are both isogenies with degree l=47.
   Both are specified by a triple of polynomials u, v, and w (resp. u',
   v', and w') of degree 47, 69, and 23, respectively, with coefficients
   in GF(p).  The coeffients of each of these polynomials are specified
   in Appendix H.1 (for the isogeny) and in Appendix H.2 (for the dual
   isogeny).  For each polynomial in variable x, the coefficients are
   tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
   hexadecimal format.

H.1.  Isogeny Parameters

H.1.1.  Coefficients of u(x)

   0  0x670ed14828b6f1791ceb3a9cc0edfe127dee8729c5a72ddf77bb1abaebbba1e8

   1  0x1135ca8bd5383cb3545402c8bce2ced14b45c29b241e4751b035f27524a9f932

   2  0x3223806ff5f669c430efd74df8389f058d180e2fcffa5cdef3eacecdd2c34771

   3  0x31b8fecf3f17a819c228517f6cd9814466c8c8bea2efccc47a29bfc14c364266

   4  0x2541305c958c5a326f44efad2bec284e7abee840fadb08f2d994cd382fd8ce42

   5  0x6e6f9c5792f3ff497f860f44a9c469cec42bd711526b733e10915be5b2dbd8c6

   6  0x3e9ad2e5f594b9ce6b06d4565891d28a1be8790000b396ef0bf59215d6cabfde

   7  0x278448895d236403bbc161347d19c913e7df5f372732a823ed807ee1d30206be

   8  0x42f9d171ea8dc2f4a14ea46cc0ee54967175ecfe83a975137b753cb127c35060

   9  0x128e40efa2d3ccb51567e73bae91e7c31eac45700fa13ce5781cbe5ddc985648

   10 0x450e5086c065430b496d88952dd2d5f2c5102bc27074d4d1e98bfa47413e0645

   11 0x487ef93da70dfd44a4db8cb41542e33d1aa32237bdca3a59b3ce1c59585f253d

   12 0x33d209270026b1d2db96efb36cc2fa0a49be1307f49689022eab1892b010b785

   13 0x4732b5996a20ebc4d5c5e2375d3b6c4b700c681bd9904343a14a0555ef0ecd48

   14 0x64dc9e8272b9f5c6ad3470db543238386f42b18cb1c592cc6caf7893141b2107

Struik                  Expires January 25, 2020               [Page 36]
Internet-Draft         lwig-curve-representations              July 2019

   15 0x52bbacd1f85c61ef7eafd8da27260fa2821f7a961867ed449b283036508ac5c5

   16 0x320447ed91210985e2c401cfe1a93db1379424cf748f92fd61ab5cc356bc89a2

   17 0x23d23a49bbcdf8cf4c4ce8a4ff7dd87d1ad1970317686254d5b4d2ec050d019f

   18 0x1601fca063f0bbbf15f198b3c20e474c2170294fa981f73365732d2372b40cd4

   19 0x7bf3f93840035e9688cfff402cee204a17c0de9779fc33503537dd78021bf4c4

   20 0x311998ce59fb7e1cd6af591ece3e84dfcb1c330cbcf28c0349e37b9581452853

   21 0x7ae5e41acfd28a9add2216dfed34756575a19b16984c1f3847b694326dad7f99

   22 0x704957e279244a5b107a6c57bd0ab9afe5227b7c0be2052cd3513772a40efee7

   23 0x56b918b5a0c583cb763550f8f71481e57c13bdcef2e5cfc8091d0821266f233b

   24 0x677073fed43ab291e496f798fbcf217bac3f014e35d0c2fa07f041ae746a04d7

   25 0x22225388e76f9688c7d4053b50ba41d0d8b71a2f21da8353d98472243ef50170

   26 0x66930b3dffdd3995a2502cef790d78b091c875192d8074bb5d5639f736400555

   27 0x79eb677c5e36971e8d64d56ebc0dedb4e9b7dd2d7b01343ebbd4d358d376e490

   28 0x48a204c2ca6d8636e9994842605bd648b91b637844e38d6c7dd707edce8256e2

   29 0x0fb3529b0d4b9ce2d70760f33e8ce997a58999718e9277caf48623d27ae6a788

   30 0x4352604bffd0c7d7a9ed898a2c6e7cf2512ffb89407271ba1f2c2d0ead8cc5aa

   31 0x6667697b29785fb6f0bd5e04d828991a5fe525370216f347ec767a26e7aac936

   32 0x09fc950b083c56dbd989badf9887255e203c879f123a7cb28901e50aea6d64dc

   33 0x41e51b51b5caadd1c15436bbf37596a1d7288a5f495d6b5b1ae66f8b2942b31d

   34 0x073b59fec709aa1cabd429e981c6284822a8b7b07620c831ab41fd31d5cf7430

   35 0x67e9b88e9a1bfbc2554107d67d814986f1b09c3107a060cba21c019a2d5dc848

   36 0x6881494a1066ca176c5e174713786040affb4268b19d2abf28ef4293429f89c1

   37 0x5f4d30502ff1e1ccd624e6f506569454ab771869d7483e26afc09dea0c5ccd3d

   38 0x02a814cfc5859bca51e539c159955cbe729a58978b52329575d09bc6c3bf97ad

Struik                  Expires January 25, 2020               [Page 37]
Internet-Draft         lwig-curve-representations              July 2019

   39 0x1313c8aaae20d6f4397f0d8b19e52cfcdf8d8e10fba144aec1778fd10ddf4e9c

   40 0x7008d38f434b98953a996d4cc79fcbef9502411dcdf92005f725cea7ce82ad47

   41 0x5a74d1296aaaa245ffb848f434531fa3ba9e5cb9098a7091d36c2777d4cf5a13

   42 0x4bd3b700606397083f8038177bdaa1ac6edbba0447537582723cae0fd29341a9

   43 0x573453fb2b093016f3368356c786519d54ed05f5372c01723b4da520597ec217

   44 0x77f5c605bdb3a30d7d9c8840fce38650910d4418eed707a212c8927f41c2c812

   45 0x16d6b9f7ff57ca32350057de1204cc6d69d4ef1b255dfef8080118e2fef6ace3

   46 0x34e8595832a4021f8b5744014c6b4f7da7df0d0329e8b6b4d44c8fadad6513b7

   47 0x01

H.1.2.  Coefficients of v(x)

   0  0x0f9f5eb7134e6f8dafa30c45afa58d7bfc6d4e3ccbb5de87b562fd77403972b2

   1  0x36c2dcd9e88f0d2d517a15fc453a098bbbb5a05eb6e8da906fae418a4e1a13f7

   2  0x0b40078302c24fa394a834880d5bf46732ca1b4894172fb7f775821276f558b3

   3  0x53dd8e2234573f7f3f7df11e90a7bdd7b75d807f9712f521d4fb18af59aa5f26

   4  0x6d4d7bb08de9061988a8cf6ff3beb10e933d4d2fbb8872d256a38c74c8c2ceda

   5  0x71bfe5831b30e28cd0fbe1e9916ab2291c6beacc5af08e2c9165c632e61dd2f5

   6  0x7c524f4d17ff2ee88463da012fc12a5b67d7fb5bd0ab59f4bbf162d76be1c89c

   7  0x758183d5e07878d3364e3fd4c863a5dc1fe723f48c4ab4273fc034f5454d59a4

   8  0x1eb41ef2479444ecdccbc200f64bde53f434a02b6c3f485d32f14da6aa7700e1

   9  0x1490f3851f016cc3cf8a1e3c16a53317253d232ed425297531b560d70770315c

   10 0x09bc43131964e46d905c3489c9d465c3abbd26eab9371c10e429b36d4b86469c

   11 0x5f27c173d94c7a413a288348d3fc88daa0bcf5af8f436a47262050f240e9be3b

   12 0x1d20010ec741aaa393cd19f0133b35f067adab0d105babe75fe45c8ba2732ceb

   13 0x01b3c669ae49b86be2f0c946a9ff6c48e44740d7d9804146915747c3c025996a

Struik                  Expires January 25, 2020               [Page 38]
Internet-Draft         lwig-curve-representations              July 2019

   14 0x24c6090f79ec13e3ae454d8f0f98e0c30a8938180595f79602f2ba013b3c10db

   15 0x4650c5b5648c6c43ac75a2042048c699e44437929268661726e7182a31b1532f

   16 0x0957a835fb8bac3360b5008790e4c1f3389589ba74c8e8bf648b856ba7f22ba5

   17 0x1cd1300bc534880f95c7885d8df04a82bd54ed3e904b0749e0e3f8cb3240c7c7

   18 0x760b486e0d3c6ee0833b34b64b7ebc846055d4d1e0beeb6aedd5132399ada0ea

   19 0x1c666846c63965ef7edf519d6ada738f2b676ae38ff1f4621533373931b3220e

   20 0x365055118b38d4bc0df86648044affea2ef33e9a392ad336444e7d15e45585d1

   21 0x736487bde4b555abfccd3ea7ddcda98eda0d7c879664117dee906a88bc551194

   22 0x70de05ab9520222a37c7a84c61eedff71cb50c5f6647fc2a5d6e0ff2305cea37

   23 0x59053f6cdf6517ab3fe4bd9c9271d1892f8cf353d8041b98409e1e341a01f8b5

   24 0x375db54ed12fe8df9a198ea40200e812c2660b7022681d7932d89fafe7c6e88d

   25 0x2a070c31d1c1a064daf56c79a044bd1cd6d13f1ddb0ff039b03a6469aaa9ed77

   26 0x41482351e7f69a756a5a2c0b3fa0681c03c550341d0ca0f76c5b394db9d2de8d

   27 0x747ac1109c9e9368d94a302cb5a1d23fcc7f0fd8a574efb7ddcaa738297c407a

   28 0x45682f1f2aab6358247e364834e2181ad0448bb815c587675fb2fee5a2119064

   29 0x148c5bf44870dfd307317f0a0e4a8c163940bee1d2f01455a2e658aa92c13620

   30 0x6add1361e56ffa2d2fbbddba284b35be5845aec8069fc28af009d53290a705ce

   31 0x6631614c617400dc00f2c55357f67a94268e7b5369b02e55d5db46c935be3af5

   32 0x17cffb496c64bb89d91c8c082f4c288c3c87feabd6b08591fe5a92216c094637

   33 0x648ff88155969f54c955a1834ad227b93062bb191170dd8c4d759f79ad5da250

   34 0x73e50900b89e5f295052b97f9d0c9edb0fc7d97b7fa5e3cfeefe33dd6a9cb223

   35 0x6afcb2f2ffe6c08508477aa4956cbd3dc864257f5059685adf2c68d4f2338f00

   36 0x372fd49701954c1b8f00926a8cb4b157d4165b75d53fa0476716554bf101b74c

   37 0x0334ed41325f3724ff8becbf2b3443fea6d30fa543d1ca13188aceb2bdaf5f4e

Struik                  Expires January 25, 2020               [Page 39]
Internet-Draft         lwig-curve-representations              July 2019

   38 0x70e629c95a94e8e1b3974acb25e18ba42f8d5991786f0931f650c283adfe82fd

   39 0x738a625f4c62d3d645f1274e09ab344e72d441f3c0e82989d3e21e19212f23f3

   40 0x7093737294b29f21522f5664a9941c9b476f75d443b647bd2c777040bcd12a6a

   41 0x0a996bad5863d821ccb8b89fa329ddbe5317a46bcb32552db396bea933765436

   42 0x2da237e3741b75dd0264836e7ef634fc0bc36ab187ebc790591a77c257b06f53

   43 0x1902f3daa86fa4f430b57212924fdc9e40f09e809f3991a0b3a10ab186c50ee5

   44 0x12baffec1bf20c921afd3cdf67a7f1d87c00d5326a3e5c83841593c214dadcb1

   45 0x6460f5a68123cb9e7bc1289cd5023c0c9ccd2d98eea24484fb3825b59dcd09aa

   46 0x2c7d63a868ffc9f0fd034f821d84736c5bc33325ce98aba5f0d95fef6f230ec8

   47 0x756e0063349a702db7406984c285a9b6bfba48177950d4361d8efa77408dc860

   48 0x037f3e30032b21e0279738e0a2b689625447831a2ccf15c638672da9aa7255ae

   49 0x1107c0dbe15d6ca9e790768317a40bcf23c80f1841f03ca79dd3e3ef4ea1ae30

   50 0x61ff7f25721d6206041c59a788316b09e05135a2aad94d539c65daa68b302cc2

   51 0x5dbfe346cbd0d61b9a3b5c42ec0518d3ae81cabcc32245060d7b0cd982b8d071

   52 0x4b6595e8501e9ec3e75f46107d2fd76511764efca179f69196eb45c0aa6fade3

   53 0x72d17a5aa7bd8a2540aa9b02d9605f2a714f44abfb4c35d518b7abc39b477870

   54 0x658d8c134bac37729ec40d27d50b637201abbf1ab4157316358953548c49cf22

   55 0x36ac53b9118581ace574d5a08f9647e6a916f92dda684a4dbc405e2646b0243f

   56 0x1917a98f387d1e323e84a0f02d53307b1dd949e1a27b0de14514f89d9c0ef4b6

   57 0x21573434fde7ce56e8777c79539479441942dba535ade8ecb77763f7eb05d797

   58 0x0e0bf482dc40884719bea5503422b603f3a8edb582f52838caa6eaab6eeac7ef

   59 0x3b0471eb53bd83e14fbc13928fe1691820349a963be8f7e9815848a53d03f5eb

   60 0x1e92cb067b24a729c42d3abb7a1179c577970f0ab3e6b0ce8d66c5b8f7001262

   61 0x74ea885c1ebed6f74964262402432ef184c42884fceb2f8dba3a9d67a1344dd7

Struik                  Expires January 25, 2020               [Page 40]
Internet-Draft         lwig-curve-representations              July 2019

   62 0x433ebce2ce9b0dc314425cfc2b234614d3c34f2c9da9fff4fdddd1ce242d035b

   63 0x33ac69e6be858dde7b83a9ff6f11de443128b39cec6e410e8d3b570e405ff896

   64 0x0dab71e2ae94e6530a501ed8cf3df26731dd1d41cd81578341e12dca3cb71aa3

   65 0x537f58d52d18ce5b1d5a6bd3a420e796e64173491ad43dd4d1083a7dcc7dd201

   66 0x49c2f6afa93fdcc4e0f8128a8b06da4c75049be14edf3e103821ab604c60f8ae

   67 0x10a333eabd6135aeaa3f5f5f7e73d102e4fd7e4bf0902fc55b00da235fa1ad08

   68 0x0f5c86044bf6032f5102e601f2a0f73c7bce9384bedd120f3e72d78484179d9c

   69 0x01

H.1.3.  Coefficients of w(x)

   0  0x3da24d42421264f30939ff00203880f2b017eb3fecf8933ae61e18df8c8ba116

   1  0x0457f20bc393cdc9a66848ce174e2fa41d77e6dbae05a317a1fb6e3ae78760f8

   2  0x7f608a2285c480d5c9592c435431fae94695beef79d770bb6d029c1d10a53295

   3  0x3832accc520a485100a0a1695792465142a5572bed1b2e50e1f8f662ac7289bb

   4  0x2df1b0559e31b328eb34beedd5e537c3f4d7b9befb0749f75d6d0d866d26fbaa

   5  0x25396820381d04015a9f655ddd41c74303ded05d54a7750e2f58006659adda28

   6  0x6fa070a70ca2bc6d4d0795fb28d4990b2cc80cd72d48b603a8ac8c8268bef6a6

   7  0x27f488578357388b20fbc7503328e1d10de602b082b3c7b8ceb33c29fea7a0d2

   8  0x15776851a7cabcfe84c632118306915c0c15c75068a47021968c7438d46076e6

   9  0x101565b08a9af015c172fb194b940a4df25c4fb1d85f72d153efc79131d45e8f

   10 0x196b0ffbf92f3229fea1dac0d74591b905ccaab6b83f905ee813ee8449f8a62c

   11 0x01f55784691719f765f04ee9051ec95d5deb42ae45405a9d87833855a6d95a94

   12 0x628858f79cca86305739d084d365d5a9e56e51a4485d253ae3f2e4a379fa8aff

   13 0x4a842dcd943a80d1e6e1dab3622a8c4d390da1592d1e56d1c14c4d3f72dd01a5

   14 0x0f3bfc9cb17a1125f94766a4097d0f1018963bc11cb7bc0c7a1d94d65e282477

Struik                  Expires January 25, 2020               [Page 41]
Internet-Draft         lwig-curve-representations              July 2019

   15 0x1c4bd70488c4882846500691fa7543b7ef694446d9c3e3b4707ea2c99383e53c

   16 0x2d7017e47b24b89b0528932c4ade43f09091b91db0072e6ebdc5e777cb215e35

   17 0x781d69243b6c86f59416f91f7decaca93eab9cdc36a184191810c56ed85e0fdc

   18 0x5f20526f4177357da40a18da054731d442ad2a5a4727322ba8ed10d32eca24fb

   19 0x33e4cab64ed8a00d8012104fe8f928e6173c428eff95bbbe569ea46126a4f3cd

   20 0x050555b6f07e308d33776922b6566829d122e19b25b7bbacbb0a4b1a7dc40192

   21 0x533fa4bf1e2a2aae2f979065fdbb5b667ede2f85543fddbba146aa3a4ef2d281

   22 0x5a742cac1952010fc5aba200a635a7bed3ef868194f45b5a6a2647d6d6b289d2

   23 0x01

H.2.  Dual Isogeny Parameters

H.2.1.  Coefficients of u'(x)

   0  0x0f0eddb584a20aaac8f1419efdd02a5cca77b21e4cfae78c49b5127d98bc5882

   1  0x7115e60d44a58630417df33dd45b8a546fa00b79fea3b2bdc449694bade87c0a

   2  0x0b3f3a6f3c445c7dc1f91121275414e88c32ff3f367ba0edad4d75b7e7b94b65

   3  0x1eb31bb333d7048b87f2b3d4ec76d69035927b41c30274368649c87c52e1ab30

   4  0x552c886c2044153e280832264066cce2a7da1127dc9720e2a380e9d37049ac64

   5  0x4504f27908db2e1f5840b74ae42445298755d9493141f5417c02f04d47797dda

   6  0x082c242cce1eb19698a4fa30b5affe64e5051c04ae8b52cb68d89ee85222e628

   7  0x480473406add76cf1d77661b3ff506c038d9cdd5ad6e1ea41969430bb876d223

   8  0x25f47bb506fba80c79d1763365fa9076d4c4cb6644f73ed37918074397e88588

   9  0x10f13ed36eab593fa20817f6bb70cac292e18d300498f6642e35cbdf772f0855

   10 0x7d28329d695fb3305620f83a58df1531e89a43c7b3151d16f3b60a8246c36ade

   11 0x02c5ec8c42b16dc6409bdd2c7b4ffe9d65d7209e886badbd5f865dec35e4ab4a

   12 0x7f4f33cd50255537e6cde15a4a327a5790c37e081802654b56c956434354e133

Struik                  Expires January 25, 2020               [Page 42]
Internet-Draft         lwig-curve-representations              July 2019

   13 0x7d30431a121d9240c761998cf83d228237e80c3ef5c7191ec9617208e0ab8cec

   14 0x4d2a7d6609610c1deed56425a4615b92f70a507e1079b2681d96a2b874cf0630

   15 0x74676df60a9906901d1dc316c639ff6ae0fcdb02b5571d4b83fc2eedcd2936a8

   16 0x22f8212219aca01410f06eb234ed53bd5b8fbe7c08652b8002bcd1ea3cdae387

   17 0x7edb04449565d7c566b934a87fadade5515f23bda1ce25daa19fff0c6a5ccc2f

   18 0x106ef71aa3aa34e8ecf4c07a67d03f0949d7d015ef2c1e32eb698dd3bec5a18c

   19 0x0017913eb705db126ac3172447bcd811a62744d505ad0eea94cfcfdde5ca7428

   20 0x2cc793e6d3b592dcf5472057a991ff1a5ab43b4680bb34c0f5faffc5307827c1

   21 0x6dafcc0b16f98300cddb5e0a7d7ff04a0e73ca558c54461781d5a5ccb1ea0122

   22 0x7e418891cf222c021b0ae5f5232b9c0dc8270d4925a13174a0f0ac5e7a4c8045

   23 0x76553bd26fecb019ead31142684789fea7754c2dc9ab9197c623f45d60749058

   24 0x693efb3f81086043656d81840902b6f3a9a4b0e8f2a5a5edf5ce1c7f50a3898e

   25 0x46c630eac2b86d36f18a061882b756917718a359f44752a5caf41be506788921

   26 0x01dcfa01773628753bc6f448ac11be8a3bffa0011b9284967629b827e064f614

   27 0x08430b5b97d49b0938d1f66ecb9d2043025c6eec624f8f02042b9621b2b5cb19

   28 0x66f66a6669272d47d3ec1efea36ee01d4a54ed50e9ec84475f668a5a9850f9be

   29 0x539128823b5ef3e87e901ab22f06d518a9bad15f5d375b49fe1e893ab38b1345

   30 0x2bd01c49d6fff22c213a8688924c10bf29269388a69a08d7f326695b3c213931

   31 0x3f7bea1baeccea3980201dc40d67c26db0e3b15b5a19b6cdac6de477aa717ac1

   32 0x6e0a72d94867807f7150fcb1233062f911b46e2ad11a3eac3c6c4c91e0f4a3fa

   33 0x5963f3cc262253f56fc103e50217e7e5b823ae8e1617f9e11f4c9c595fbb5bf6

   34 0x41440b6fe787777bc7b63afac9f4a38ddadcebc3d72f8fc73835247ba05f3a1d

   35 0x66d185401c1d2d0b84fcf6758a6a985bf9695651271c08f4b69ce89175fb7b34

   36 0x2673fb8c65bc4fe41905381093429a2601c46a309c03077ca229bac7d6ccf239

Struik                  Expires January 25, 2020               [Page 43]
Internet-Draft         lwig-curve-representations              July 2019

   37 0x1ce4d895ee601918a080de353633c82b75a3f61e8247763767d146554dd2f862

   38 0x18efa6c72fa908347547a89028a44f79f22542baa588601f2b3ed25a5e56d27c

   39 0x53de362e2f8ff220f8921620a71e8faa1aa57f8886fcbb6808fa3a5560570543

   40 0x0dc29a73b97f08aa8774911474e651130ed364e8d8cffd4a80dee633aacecc47

   41 0x4e7eb8584ae4de525389d1e9300fc4480b3d9c8a5a45ecfbe33311029d8f6b99

   42 0x6c3cba4aa9229550fa82e1cfaee4b02f2c0cb86f79e0d412b8e32b00b7959d80

   43 0x5a9d104ae585b94af68eeb16b1349776b601f97b7ce716701645b1a75b68dcf3

   44 0x754e014b5e87af035b3d5fe6fb49f4631e32549f6341c6693c5172a6388e273e

   45 0x6710d8265118e22eaceba09566c86f642ab42da58c435083a353eaa12d866c39

   46 0x6e88ac659ce146c369f8b24c3a49f8dca547827250cf7963a455851cfc4f8d22

   47 0x0971eb5f253356cd1fde9fb21f4a4902aa5b8d804a2b57ba775dc130181ae2e8

H.2.2.  Coefficients of v'(x)

   0  0x043c9b67cc5b16e167b55f190db61e44d48d813a7112910f10e3fd8da85d61d3

   1  0x72046db07e0e7882ff3f0f38b54b45ca84153be47a7fd1dd8f6402e17c47966f

   2  0x1593d97b65a070b6b3f879fe3dc4d1ef03c0e781c997111d5c1748f956f1ffc0

   3  0x54e5fec076b8779338432bdc5a449e36823a0a7c905fd37f232330b026a143a0

   4  0x46328dd9bc336e0873abd453db472468393333fbf2010c6ac283933216e98038

   5  0x25d0c64de1dfe1c6d5f5f2d98ab637d8b39bcf0d886a23dabac18c80d7eb03ce

   6  0x3a175c46b2cd8e2b313dde2d5f3097b78114a6295f283cf58a33844b0c8d8b34

   7  0x5cf4e6f745bdd61181a7d1b4db31dc4c30c84957f63cdf163bee5e466a7a8d38

   8  0x639071c39b723eea51cfd870478331d60396b31f39a593ebdd9b1eb543875283

   9  0x7ea8f895dcd85fc6cb2b58793789bd9246e62fa7a8c7116936876f4d8dff869b

   10 0x503818acb535bcaacf8ad44a83c213a9ce83af7c937dc9b3e5b6efedc0a7428c

   11 0x0e815373920ec3cbf3f8cae20d4389d367dc4398e01691244af90edc3e6d42b8

Struik                  Expires January 25, 2020               [Page 44]
Internet-Draft         lwig-curve-representations              July 2019

   12 0x7e4b23e1e0b739087f77910cc635a92a3dc184a791400cbceae056c19c853815

   13 0x145322201db4b5ec0a643229e07c0ab7c36e4274745689be2c19cfa8a702129d

   14 0x0fde79514935d9b40f52e33429621a200acc092f6e5dec14b49e73f2f59c780d

   15 0x37517ac5c04dc48145a9d6e14803b8ce9cb6a5d01c6f0ad1b04ff3353d02d815

   16 0x58ae96b8eefe9e80f24d3b886932fe3c27aaea810fa189c702f93987c8c97854

   17 0x6f6402c90fa379096d5f436035bebc9d29302126e9b117887abfa7d4b3c5709a

   18 0x01dbdf2b9ec09a8defeb485cc16ea98d0d45c5b9877ff16bd04c0110d2f64961

   19 0x53c51706af523ab5b32291de6c6b1ee7c5cbd0a5b317218f917b12ff38421452

   20 0x1b1051c7aec7d37a349208e3950b679d14e39f979db4fcd7b50d7d27dc918650

   21 0x1547e8d36262d5434cfb029cdd29385353124c3c35b1423c6cca1f87910b305b

   22 0x198efe984efc817835e28f704d41e4583a1e2398f7ce14045c4575d0445c6ce7

   23 0x492276dfe9588ee5cd9f553d990f377935d721822ecd0333ce2eb1d4324d539c

   24 0x77bad5319bacd5ed99e1905ce2ae89294efa7ee1f74314e4095c618a4e580c9b

   25 0x2cb3d532b8eac41c61b683f7b02feb9c2761f8b4286a54c3c4b60dd8081a312e

   26 0x37d189ea60443e2fee9b7ba8a34ed79ff3883dcefc06592836d2a9dd2ee3656e

   27 0x79a80f9a0e6b8ded17a3d6ccf71eb565e3704c3543b77d70bca854345e880aba

   28 0x47718530ef8e8c75f069acb2d9925c5537908e220b28c8a2859b856f46d5f8db

   29 0x7dc518f82b55a36b4fa084b05bf21e3efce481d278a9f5c6a49701e56dac01ec

   30 0x340a318dad4b8d348a0838659672792a0f00b7105881e6080a340f708a9c7f94

   31 0x55f04d9d8891636d4e9c808a1fa95ad0dae7a8492257b20448023aad3203278e

   32 0x39dc465d58259f9f70bb430d27e2f0ab384a550e1259655443e14bdecba85530

   33 0x757385464cff265379a1adfadfd6f6a03fa8a2278761d4889ab097eff4d1ac28

   34 0x4d575654dbe39778857f4e688cc657416ce524d54864ebe8995ba766efa7ca2b

   35 0x47adb6aecc1949f2dc9f01206cc23eb4a0c29585d475dd24dc463c5087809298

Struik                  Expires January 25, 2020               [Page 45]
Internet-Draft         lwig-curve-representations              July 2019

   36 0x30d39e8b0c451a8fcf3d2abab4b86ffa374265abbe77c5903db4c1be8cec7672

   37 0x28cf47b39112297f0daeaa621f8e777875adc26f35dec0ba475c2ee148562b41

   38 0x36199723cc59867e2e309fe9941cd33722c807bb2d0a06eeb41de93f1b93f2f5

   39 0x5cdeb1f2ee1c7d694bdd884cb1c5c22de206684e1cafb8d3adb9a33cb85e19a2

   40 0x0f6e6b3fc54c2d25871011b1499bb0ef015c6d0da802ae7eccf1d8c3fb73856c

   41 0x0c1422c98b672414344a9c05492b926f473f05033b9f85b8788b4bb9a080053c

   42 0x19a8527de35d4faacb00184e0423962247319703a815eecf355f143c2c18f17f

   43 0x7812dc3313e6cf093da4617f06062e8e8969d648dfe6b5c331bccd58eb428383

   44 0x61e537180c84c79e1fd2d4f9d386e1c4f0442247605b8d8904d122ee7ef9f7be

   45 0x544d8621d05540576cfc9b58a3dab19145332b88eb0b86f4c15567c37205adf9

   46 0x11be3ef96e6e07556356b51e2479436d9966b7b083892b390caec22a117aa48e

   47 0x205cda31289cf75ab0759c14c43cb30f7287969ea3dc0d5286a3853a4d403187

   48 0x048d8fc6934f4f0a99f0f2cc59010389e2a0b20d6909bfcf8d7d0249f360acdc

   49 0x42cecc6d9bdca6d382e97fcea46a79c3eda2853091a8f399a2252115bf9a1454

   50 0x0117d41b24f2f69cb3270b359c181607931f62c56d070bbd14dc9e3f9ab1432e

   51 0x7c51564c66f68e2ad4ce6ea0d68f920fafa375376709c606c88a0ed44207aa1e

   52 0x48f25191fc8ac7d9f21adf6df23b76ccbca9cb02b815acdbebfa3f4eddc71b34

   53 0x4fc21a62c4688de70e28ad3d5956633fc9833bc7be09dc7bc500b7fae1e1c9a8

   54 0x1f23f25be0912173c3ef98e1c9990205a69d0bf2303d201d27a5499247f06789

   55 0x3131495618a0ac4cb11a702f3f8bab66c4fa1066d0a741af3c92d5c246edd579

   56 0x0d93fe40faa53913638e497328a1b47603cb062c7afc9e96278603f29fd11fd4

   57 0x6b348bc59e984c91d696d1e3c3cfae44021f06f74798c787c355437fb696093d

   58 0x65af00e73043edcb479620c8b48098b89809d577a4071c8e33e8678829138b8a

   59 0x5e62ffb032b2ddb06591f86a46a18effd5d6ecf3f129bb2bacfd51a3739a98b6

Struik                  Expires January 25, 2020               [Page 46]
Internet-Draft         lwig-curve-representations              July 2019

   60 0x62c974ef3593fc86f7d78883b8727a2f7359a282cbc0196948e7a793e60ce1a1

   61 0x204d708e3f500aad64283f753e7d9bab976aa42a4ca1ce5e9d2264639e8b1110

   62 0x0a90f0059da81a012e9d0a756809fab2ce61cb45965d4d1513a06227783ee4ea

   63 0x39fa55971c9e833f61139c39e243d40869fd7e8a1417ee4e7719dd2dd242766f

   64 0x22677c1e659caa324f0c74a013921facf62d0d78f273563145cc1ddccfcc4421

   65 0x3468cf6df7e93f7ff1fe1dd7e180a89dec3ed4f72843b4ea8a8d780011a245b2

   66 0x68f75a0e2210f52a90704ed5f511918d1f6bcfcd26b462cc4975252369db6e9d

   67 0x6220c0699696e9bcab0fe3a80d437519bd2bdf3caef665e106b2dd47585ddd9f

   68 0x553ad47b129fb347992b576479b0a89f8d71f1196f83e5eaab5f533a1dd6f6d7

   69 0x239aef387e116ec8730fa15af053485ca707650d9f8917a75f22acf6213197df

H.2.3.  Coefficients of w'(x)

   0  0x6bd7f1fc5dd51b7d832848c180f019bcbdb101d4b3435230a79cc4f95c35e15e

   1  0x17413bb3ee505184a504e14419b8d7c8517a0d268f65b0d7f5b0ba68d6166dd0

   2  0x47f4471beed06e5e2b6d5569c20e30346bdba2921d9676603c58e55431572f90

   3  0x2af7eaafd04f6910a5b01cdb0c27dca09487f1cd1116b38db34563e7b0b414eb

   4  0x57f0a593459732eef11d2e2f7085bf9adf534879ba56f7afd17c4a40d3d3477b

   5  0x4da04e912f145c8d1e5957e0a9e44cca83e74345b38583b70840bdfdbd0288ed

   6  0x7cc9c3a51a3767d9d37c6652c349adc09bfe477d99f249a2a7bc803c1c5f39ed

   7  0x425d7e58b8adf87eebf445b424ba308ee7880228921651995a7eab548180ad49

   8  0x48156db5c99248234c09f43fedf509005943d3d5f5d7422621617467b06d314f

   9  0x0d837dbbd1af32d04e2699cb026399c1928472aa1a7f0a1d3afd24bc9923456a

   10 0x5b8806e0f924e67c1f207464a9d025758c078b43ddc0ea9afe9993641e5650be

   11 0x29c91284e5d14939a6c9bc848908bd9df1f8346c259bbd40f3ed65182f3a2f39

   12 0x25550b0f3bceef18a6bf4a46c45bf1b92f22a76d456bfdf19d07398c80b0f946

Struik                  Expires January 25, 2020               [Page 47]
Internet-Draft         lwig-curve-representations              July 2019

   13 0x495d289b1db16229d7d4630cb65d52500256547401f121a9b09fb8e82cf01953

   14 0x718c8c610ea7048a370eabfd9888c633ee31dd70f8bcc58361962bb08619963e

   15 0x55d8a5ceef588ab52a07fa6047d6045550a5c52c91cc8b6b82eeb033c8ca557d

   16 0x620b5a4974cc3395f96b2a0fa9e6454202ef2c00d82b0e6c534b3b1d20f9a572

   17 0x4991b763929b00241a1a9a68e00e90c5df087f90b3352c0f4d8094a51429524e

   18 0x18b6b49c5650fb82e36e25fd4eb6decfdd40b46c37425e6597c7444a1b6afb4e

   19 0x6868305b4f40654460aad63af3cb9151ab67c775eaac5e5df90d3aea58dee141

   20 0x16bc90219a36063a22889db810730a8b719c267d538cd28fa7c0d04f124c8580

   21 0x3628f9cf1fbe3eb559854e3b1c06a4cd6a26906b4e2d2e70616a493bba2dc574

   22 0x64abcc6759f1ce1ab57d41e17c2633f717064e35a7233a6682f8cf8e9538afec

   23 0x01

Appendix I.  Point Compression

   Point compression allows a shorter representation of affine points of
   an elliptic curve by exploiting algebraic relationships between the
   coordinate values based on the defining equation of the curve in
   question.  Point decompression refers to the reverse process, where
   one tries and recover the affine point from its compressed
   representation and information on the domain parameters of the curve.
   Consequently, point compression followed by point decompression is
   the identity map.

   The description below makes use of an auxiliary function (the parity
   function), which we first define for prime fields GF(p) and then
   extend to all fields GF(q), where q is an odd prime power.  We assume
   each finite field to be unambiguously defined.

   Let y be a nonzero element of GF(q).  If q:=p is an odd prime number,
   y and p-y can be uniquely represented as integers in the interval
   [1,p-1] and have odd sum p.  Consequently, one can distinguish y from
   -y via the parity of this representation, i.e., via par(y):=y (mod
   2).  If q:=p^m, where p is an odd prime number and where m>0, both y
   and -y can be uniquely represented as vectors of length m, with
   coefficients in GF(p) (see Appendix B.2).  In this case, the leftmost
   nonzero coordinate values of y and -y are in the same position and
   have representations in [1,p-1] with different parity.  As a result,
   one can distinguish y from -y via the parity of the representation of

Struik                  Expires January 25, 2020               [Page 48]
Internet-Draft         lwig-curve-representations              July 2019

   this coordinate value.  This extends the definition of the parity
   function to any odd-size field GF(q), where one defines par(0):=0.

I.1.  Point Compression for Weierstrass Curves

   If P:=(X, Y) is an affine point of the Weierstrass curve W_{a,b}
   defined over the field GF(q), then so is -P:=(X, -Y).  Since the
   defining equation Y^2=X^2+a*X+b has at most two solutions with fixed
   X-value, one can represent P by its X-coordinate and one bit of
   information that allows one to distinguish P from -P, i.e., one can
   represent P as the ordered pair compr(P):=(X, par(Y)).  If P is a
   point of order two, one can uniquely represent P by its X-coordinate
   alone, since Y=0 and has fixed parity.  Conversely, given the ordered
   pair (X, t), where X is an element of GF(q) and where t=0 or t=1, and
   the domain parameters of the curve, one can use the defining equation
   of the curve to try and determine candidate values for the
   Y-coordinate given X, by solving the quadratic equation Y^2:=alpha,
   where alpha:=X^3+a*X+b.  If alpha is not a square in GF(q), this
   equation does not have a solution in GF(q) and the ordered pair (X,
   t) does not correspond to a point of this curve.  Otherwise, there
   are two solutions, viz. Y=sqrt(alpha) and -Y.  If alpha is a nonzero
   element of GF(q), one can uniquely recover the Y-coordinate for which
   par(Y):=t and, thereby, the point P:=(X, Y).  This is also the case
   if alpha=0 and t=0, in which case Y=0 and the point P has order two.
   However, if alpha=0 and t=1, the ordered pair (X, t) does not
   correspond to the outcome of the point compression function.

   We extend the definition of the point compression function to all
   points of the curve W_{a,b}, by associating the (non-affine) point at
   infinity O with any ordered pair compr(O):=(X,0), where X is any
   element of GF(q) for which alpha:=X^3+a*X+b is not a square in GF(q),
   and recover this point accordingly.  In this case, the point at
   infinity O can be represented by any ordered pair (X,0) of elements
   of GF(q) for which X^3+a*X+b is not a square in GF(q).  Note that
   this ordered pair does not satisfy the defining equation of the curve
   in question.  An application may fix a specific suitable value of X
   or choose multiple such values and use this to encode additonal
   information.  Further details are out of scope.

I.2.  Point Compression for Montgomery Curves

   If P:=(u, v) is an affine point of the Montgomery curve M_{A,B}
   defined over the field GF(q), then so is -P:=(u, -v).  Since the
   defining equation B*v^2=u^3+A*u^2+u has at most two solutions with
   fixed u-value, one can represent P by its u-coordinate and one bit of
   information that allows one to distinguish P from -P, i.e., one can
   represent P as the ordered pair compr(P):=(u, par(v)).  If P is a
   point of order two, one can uniquely represent P by its u-coordinate

Struik                  Expires January 25, 2020               [Page 49]
Internet-Draft         lwig-curve-representations              July 2019

   alone, since v=0 and has fixed parity.  Conversely, given the ordered
   pair (u, t), where u is an element of GF(q) and where t=0 or t=1, and
   the domain parameters of the curve, one can use the defining equation
   of the curve to try and determine candidate values for the
   v-coordinate given u, by solving the quadratic equation v^2:=alpha,
   where alpha:=(u^3+A*u^2+u)/B.  If alpha is not a square in GF(q),
   this equation does not have a solution in GF(q) and the ordered pair
   (u, t) does not correspond to a point of this curve.  Otherwise,
   there are two solutions, viz. v=sqrt(alpha) and -v.  If alpha is a
   nonzero element of GF(q), one can uniquely recover the v-coordinate
   for which par(v):=t and, thereby, the affine point P:=(u, v).  This
   is also the case if alpha=0 and t=0, in which case v=0 and the point
   P has order two.  However, if alpha=0 and t=1, the ordered pair (u,
   t) does not correspond to the outcome of the point compression
   function.

   We extend the definition of the point compression function to all
   points of the curve M_{A,B}, by associating the (non-affine) point at
   infinity O with the ordered pair compr(O):=(0,1) and recover this
   point accordingly.  (Note that this corresponds to the case alpha=0
   and t=1 above.)  The point at infinity O can be represented by the
   ordered pair (0, 1) of elements of GF(q).  Note that this ordered
   pair does not satisfy the defining equation of the curve in question.

I.3.  Point Compression for Twisted Edwards Curves

   If P:=(x, y) is an affine point of the twisted Edwards curve E_{a,d}
   defined over the field GF(q), then so is -P:=(-x, y).  Since the
   defining equation a*x^2+y^2=1+d*x^2*y^2 has at most two solutions
   with fixed y-value, one can represent P by its y-coordinate and one
   bit of information that allows one to distinguish P from -P, i.e.,
   one can represent P as the ordered pair compr(P):=(par(x), y).  If P
   is a point of order one or two, one can uniquely represent P by its
   y-coordinate alone, since x=0 and has fixed parity.  Conversely,
   given the ordered pair (t, y), where y is an element of GF(q) and
   where t=0 or t=1, and the domain parameters of the curve, one can use
   the defining equation of the curve to try and determine candidate
   values for the x-coordinate given y, by solving the quadratic
   equation x^2:=alpha, where alpha:=(1-y^2)/(a-d*y^2).  If alpha is not
   a square in GF(q), this equation does not have a solution in GF(q)
   and the ordered pair (t, y) does not correspond to a point of this
   curve.  Otherwise, there are two solutions, viz. x=sqrt(alpha) and
   -x.  If alpha is a nonzero element of GF(q), one can uniquely recover
   the x-coordinate for which par(x):=t and, thereby, the affine point
   P:=(x, y).  This is also the case if alpha=0 and t=0, in which case
   x=0 and the point P has order one or two.  However, if alpha=0 and
   t=1, the ordered pair (t, y) does not correspond to the outcome of
   the point compression function.

Struik                  Expires January 25, 2020               [Page 50]
Internet-Draft         lwig-curve-representations              July 2019

   Note that the point compression function is defined for all points of
   the twisted Edwards curve E_{a,d} (subject to the Note in
   Appendix C.3).  Here, the identity element O:=(0,1) is associated
   with the compressed point compr(O):=(0,1).  (Note that this
   corresponds to the case alpha=0 and t=0 above.)

   We extend the definition of the compression function further, to also
   include a special marker element 'btm', by associating this marker
   element with the ordered pair compr(btm):=(1,1) and recover this
   marker element accordingly.  (Note that this corresponds to the case
   alpha=0 and t=1 above.)  The marker element 'btm' can be represented
   by the ordered pair (1,1) of elements of GF(q).  Note that this
   ordered pair does not satisfy the defining equation of the curve in
   question.

Appendix J.  Data Conversions

   The string over some alphabet S consisting of the symbols x_{l-1},
   x_{l-2}, ..., x_1, x_0 (each in S), in this order, is denoted by
   str(x_{l-1}, x_{l-2}, ..., x_1, x_0).  The length of this string
   (over S) is the number of symbols it contains (here: l).  The empty
   string is the (unique) string of length l=0.

   The right-concatenation of two strings X and Y (defined over the same
   alphabet) is the string Z consisting of the symbols of X (in the same
   order) followed by the symbols of Y (in the same order).  The length
   of the resulting string Z is the sum of the lengths of X and Y.  This
   string operation is denoted by Z:=X||Y.  The string X is called a
   prefix of Z; the string Y a postfix.  The t-prefix of a string Z of
   length l is its unique prefix X of length t; the t-postfix its unique
   postfix Y of length t (where we define these notions as well if t is
   outside the interval [0,l]: a t-prefix or t-postfix is the empty
   string if t is negative and is the entire string Z if t is larger
   than l).  Sometimes, a t-prefix of a string Z is denoted by trunc-
   left(Z,t); a t-postfix by trunc-right(Z,t).  A string X is called a
   substring of Z if it is a prefix of some postfix of Z.  The string
   resulting from prepending the string Y with X is the string X||Y.

   An octet is an integer in the interval [0,256).  An octet string is a
   string, where the alphabet is the set of all octets.  A binary string
   (or bit string, for short) is a string, where the alphabet is the set
   {0,1}. Note that the length of a string is defined in terms of the
   underlying alphabet, as are the operations in the previous paragraph.

Struik                  Expires January 25, 2020               [Page 51]
Internet-Draft         lwig-curve-representations              July 2019

J.1.  Conversion between Bit Strings and Integers

   There is a 1-1 correspondence between bit strings of length l and the
   integers in the interval [0, 2^l), where the bit string
   X:=str(x_{l-1}, x_{l-2}, ..., x_1, x_0) corresponds to the integer
   x:=x_{l-1}*2^{l-1} + x_{l-2}*2^{l-2} + ... + x_1*2 + x_0*1.  (If l=0,
   the empty bit string corresponds to the integer zero.)  Note that
   while the mapping from bit strings to integers is uniquely defined,
   the inverse mapping from integers to bit strings is not, since any
   non-negative integer smaller than 2^t can be represented as a bit
   string of length at least t (due to leading zero coefficients in base
   2 representation).  The latter representation is called tight if the
   bit string representation has minimal length.

J.2.  Conversion between Octet Strings and Integers (OS2I, I2OS)

   There is a 1-1 correspondence between octet strings of length l and
   the integers in the interval [0, 256^l), where the octet string
   X:=str(X_{l-1}, X_{l-2}, ..., X_1, X_0) corresponds to the integer
   x:=X_{l-1}*256^{l-1} + X^{l-2}*256^{l-2} + ... + X_1*256 + X_0*1.
   (If l=0, the empty string corresponds to the integer zero.)  Note
   that while the mapping from octet strings to integers is uniquely
   defined, the inverse mapping from integers to octet strings is not,
   since any non-negative integer smaller than 256^t can be represented
   as an octet string of length at least t (due to leading zero
   coefficients in base 256 representation).  The latter representation
   is called tight if the octet string representation has minimal
   length.  This defines the mapping OS2I from octet strings to integers
   and the mapping I2OS(x,l) from non-negative integers smaller than
   256^l to octet strings of length l.

J.3.  Conversion between Octet Strings and Bit Strings (BS2OS, OS2BS)

   There is a 1-1 correspondence between octet strings of length l and
   and bit strings of length 8*l, where the octet string X:=str(X_{l-1},
   X_{l-2}, ..., X_1, X_0) corresponds to the right-concatenation of the
   8-bit strings x_{l-1}, x_{l-2}, ..., x_1, x_0, where each octet X_i
   corresponds to the 8-bit string x_i according to the mapping of
   Appendix J.1 above.  Note that the mapping from octet strings to bit
   strings is uniquely defined and so is the inverse mapping from bit
   strings to octet strings, if one prepends each bit string with the
   smallest number of 0 bits so as to result in a bit string of length
   divisible by eight (i.e., one uses pre-padding).  This defines the
   mapping OS2BS from octet strings to bit strings and the corresponding
   mapping BS2OS from bit strings to octet strings.

Struik                  Expires January 25, 2020               [Page 52]
Internet-Draft         lwig-curve-representations              July 2019

J.4.  Conversion between Field Elements and Octet Strings (FE2OS, OS2FE)

   There is a 1-1 correspondence between elements of a fixed finite
   field GF(q), where q=p^m and m>0, and vectors of length m, with
   coefficients in GF(p), where each element x of GF(q) is a vector
   (x_{m-1}, x_{m-2}, ..., x_1, x_0) according to the conventions of
   Appendix B.2.  In this case, this field element can be uniquely
   represented by the right-concatenation of the octet strings X_{m-1},
   X_{m-2}, ..., X_1, X_0, where each octet string X_i corresponds to
   the integer x_i in the interval [0,p-1] according to the mapping of
   Appendix J.2 above.  Note that both the mapping from field elements
   to octet strings and the inverse mapping are only uniquely defined if
   each octet string X_i has the same fixed size (e.g., the smallest
   integer l so that 256^l >= p) and if all integers are reduced modulo
   p.  If so, the latter representation is called tight if l is minimal
   so that 256^l >= p.  This defines the mapping FE2OS(x,l) from field
   elements to octet strings and the mapping OS2FE(X,l) from octet
   strings to field elements, where the underlying field is implicit and
   assumed to be known from context.  In this case, the octet string has
   length l*m.

J.5.  Conversion between Elements of Z mod n and Octet Strings (ZnE2OS,
      OS2ZnE)

   There is a 1-1 correspondence between elements of a fixed set Z(n) of
   integers modulo n and integers in the interval [0,n), where each
   element x can be uniquely represented by the octet string
   corresponding to the integer x modulo n according to the mapping of
   Appendix J.2 above.  Note that both the mapping from elements of Z(n)
   to octet strings and the inverse mapping are only uniquely defined if
   the octet string has a fixed size (e.g., the smallest integer l so
   that 256^l >= n) and if all integers are reduced modulo n.  If so,
   the latter representation is called tight if l is minimal so that
   256^l >= n.  This defines the mapping ZnE2OS(x,l) from elements of
   Z(n) to octet strings and the mapping OS2ZnE(X,l) from octet strings
   to elements of Z(n), where the underlying modulus n is implicit and
   assumed to be known from context.  In this case, the octet string has
   length l.

   Note that if n is a prime number p, the conversions ZnE2OS and FE2OS
   are consistent, as are OS2ZnE and OS2FE.  This is, however, no longer
   the case if n is a strict prime power.

   The conversion rules for composite n values are useful, e.g., when
   encoding the modulus n of RSA (or elements of any other non-prime set
   Z(n), for that matter).

Struik                  Expires January 25, 2020               [Page 53]
Internet-Draft         lwig-curve-representations              July 2019

J.6.  Ordering Conventions

   One can consider various representation functions, depending on bit-
   ordering and octet-ordering conventions.

   The description below makes use of an auxiliary function (the
   reversion function), which we define both for bit strings and octet
   strings.  For a bit string [octet string] X:=str(x_{l-1}, x_{l-2},
   ..., x_1, x_0), its reverse is the bit string [octet string]
   X':=rev(X):=str(x_0, x_1, ..., x_{l-2}, x_{l-1}).

   We now describe representations in most-significant-bit first (msb)
   or least-significant-bit first (lsb) order and those in most-
   significant-byte first (MSB) or least-significant-byte first (LSB)
   order.

   One distinguishes the following octet-string representations of
   integers and field elements:

   1.  MSB, msb: represent field elements and integers as above,
       yielding the octet string str(X_{l-1}, X_{l-2}, ..., X_1, X_0).

   2.  MSB, lsb: reverse the bit-order of each octet, viewed as 8-bit
       string, yielding the octet string str((rev(X_{l-1}),
       rev(X_{l-2}), ..., rev(X_1), rev(X_0)).

   3.  LSB, lsb: reverse the octet string and bit-order of each octet,
       yielding the octet string str(rev(X_{0}), rev(X_{1}), ...,
       rev(X_{l-2}), rev(X_{l-1})).

   4.  LSB, msb: reverse the octet string, yielding the octet string
       str(X_{0}, X_{1}, ..., X_{l-2}, X_{l-1}).

   Thus, the 2-octet string "07e3" represents the integer 2019 (=0x07e3)
   in MSB/msb order, the integer 57,543 (0xe0c7) in MSB/lsb order, the
   integer 51,168 (0xc7e0) in LSB/lsb order, and the integer 58,119
   (=0xe307) in LSB/msb order.

   Note that, with the above data conversions, there is still some
   ambiguity as to how to represent an integer or a field element as a
   bit string or octet string (due to leading zeros).  However, tight
   representations (as defined above) are non-ambiguous.  (Note, in
   particular, that tightness implies that elements of GF(q) are always
   uniquely represented.)

   Note that elements of a prime field GF(p), where p is a 255-bit prime
   number, have a tight representation as a 32-byte string, where a
   fixed bit position is always set to zero.  (This is the leftmost bit

Struik                  Expires January 25, 2020               [Page 54]
Internet-Draft         lwig-curve-representations              July 2019

   position of this octet string if one follows the MSB/msb
   representation conventions.)  This allows the parity bit of a
   compressed point (see Appendix I) to be encoded in this bit position
   and, thereby, allows a compressed point and a field element of GF(p)
   to be represented by an octet string of the same length.  This is
   called the squeezed point representation.  Obviously, other
   representations (e.g., those of elements of Z(n)) may also have fixed
   bit values on certain positions, which can be used to squeeze-in
   additional information.  Further details are out of scope.

Appendix K.  Representation Examples Curve25519 Family Members

   We present some examples of computations using the curves introduced
   in this document.  In each case, we indicate the values of P, k*P,
   and (k+1)*P, where P is a fixed multiple (here: 2019) of the base
   point of the curve in question and where the private key k is the
   integer

   k   45467544759954639344191351164156560595299236761702065033670739677
       691372543056

       (=0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
       c08d5abd 15e29c50).

K.1.  Example with Curve25519

   Pm=(u, v), k*Pm=(u1, v1), and (k+1)*Pm=(u2, v2) with Curve25519:

   u   53025657538808013645618620393754461319535915376830819974982289332
       088255623750

       (=0x753b7566 df35d574 4734142c 9abf931c ea290160 aa75853c
       7f972467 b7f13246).

   v   53327798092436462013048370302019946300826511459161905709144645521
       233690313086

       (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b
       ae35ca26 df75417e).

   u1  42039618818474335439333192910143029294450651736166602435248528442
       691717668056

       (=0x5cf194be f0bdd6d6 be58e18a 8f16740a ec25f4b0 67f7980a
       23bb6468 88bb9cd8).

   v1  76981661982917351630937517222412729130882368858134322156485762195
       67913357634

Struik                  Expires January 25, 2020               [Page 55]
Internet-Draft         lwig-curve-representations              July 2019

       (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd
       f5771306 479ad142).

   u2  34175116482377882355440137752573651838273760818624557524643126101
       82464621878

       (=0x078e3e38 41c3e0d0 373e5454 ecffae33 2798b10a 55c72117
       62629f97 f1394d36).

   v2  43046985853631671610553834968785204191967171967937842531656254539
       962663994648

       (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e
       fbc17f7f 7fda8518).

   As suggested in Appendix C.2, the v-coordinate of k*Pm can be
   indirectly computed from the u-coordinates of Pm, k*Pm, and (k+1)*Pm,
   and the v-coordinate of Pm, which allows computation of the entire
   point k*Pm (and not just its u-coordinate) if k*Pm is computed using
   the Montgomery ladder (as, e.g., [RFC7748] recommends), since that
   algorithm computes both u1 and u2 and the v-coordinate of the point
   Pm may be available from context.

   The representation of k and the compressed representations of Pm and
   k*Pm in tight LSB/msb-order are given by

   repr(k)     0x509ce215 bd5a8dc0 c3328c77 5dc6f59c 4d4915f9 e4bf5d0d
               c2e583cd e6b78564

   repr(Pm)    0x4632f1b7 6724977f 3c8575aa 600129ea 1c93bf9a 2c143447
               74d535df 66753b75;

   repr(k*Pm)  0xd89cbb88 6864bb23 0a98f767 b0f425ec 0a74168f 8ae158be
               d6d6bdf0 be94f15c,

   where the leftmost bit of the rightmost octet indicates the parity of
   the v-coordinate of the point of Curve25519 in question (which, in
   this case, are both zero, since v and v1 are even).  See Appendix I.2
   and Appendix J for further detail on (squeezed) point compression.

   The scalar representation and (squeezed) point representation
   illustrated above are consistent with the representations specified
   in [RFC7748], except that in [RFC7748] only an affine point's
   u-coordinate is represented (i.e., the v-coordinate of any point is
   always implicitly assumed to have an even value) and that the
   representation of the point at infinity is not specified.  Another
   difference is that [RFC7748] allows non-unique representations of

Struik                  Expires January 25, 2020               [Page 56]
Internet-Draft         lwig-curve-representations              July 2019

   some elements of GF(p), whereas our representation conventions do not
   (since tight).

   A randomized representation (t1, t2) of the point k*Pm in tight LSB/
   msb order is given by

   t1          409531317901122685707535715924445398426503483189854716584
               37762538294289253464

               (=0x5844b232 8c4586dc 62f593c5 599c2a8c e61ba893 bb052de6
               77510a42 b3a68a5a)

   t2          451856098332889407421278004628150814449259902023388533929
               08848927625430980881

               (=0x11598452 e65138dc ce948d7e d8f46a18 b640722c 8e170957
               751b7729 1b26e663),

   where this representation is defined in Appendix L.4 and uses the
   mapping of Appendix L.3.2 with the default square root function.

K.2.  Example with Edwards25519

   Pe=(x, y), k*Pe=(x1, y1), and (k+1)*Pe=(x2, y2) with Edwards25519:

   x   25301662348702136092602268236183361085863932475593120475382959053
       365387223252

       (=0x37f03bc0 1070ed12 d3218f8b ba1abb74 fd6b94eb 62033d09
       83851e21 d6a460d4).

   y   54434749145175762798550436656748568411099702168121592090608501578
       942019473360

       (=0x7858f9e7 6774ed8e 23d614d2 36715fc7 56813b02 9aa13c18
       960705c5 b3a30fd0).

   x1  42966967796585460733861724865699548279978730460766025087444502812
       416557284873

       (=0x5efe7124 465b5bdb b364bb3e e4f106e2 18d59b36 48f4fe83
       c11afc91 785d7e09).

   y1  46006463385134057167371782068441558951541960707376246310705917936
       352255317084

       (=0x65b6bc49 985badaf bc5fdd96 fb189502 35d5effd 540b439d
       60508827 80bc945c).

Struik                  Expires January 25, 2020               [Page 57]
Internet-Draft         lwig-curve-representations              July 2019

   x2  42629294840915692510487991904657367226900127896202625319538173473
       104931719808

       (=0x5e3f536a 3be2364a 1fa775a3 5f8f65ae 93f4a89d 81a04a2e
       87783748 00120a80).

   y2  29739282897206659585364020239089516293417836047563355347155817358
       737209129078

       (=0x41bfd66e 64bdd801 c581a720 f48172a8 187445fa 350924a2
       c92c791e 38d57876).

   The representation of k and the compressed representations of Pe and
   k*Pe in tight LSB/lsb-order are given by

   repr(k)     =0x0a3947a8 bd5ab103 c34c31ee ba63af39 b292a89f 27fdbab0
               43a7c1b3 67eda126;

   repr(Pe)    =0x0bf0c5cd a3a0e069 183c8559 40dc816a e3fa8e6c 4b286bc4
               71b72ee6 e79f1a1e;

   repr(k*Pe)  =0x3a293d01 e4110a06 b9c2d02a bff7abac 40a918df 69bbfa3d
               f5b5da19 923d6da7,

   where the rightmost bit of the rightmost octet indicates the parity
   of the x-coordinate of the point of Edwards25519 in question (which,
   in this case, are zero and one, respectively, since x is even and x1
   is odd).  See Appendix I.3 and Appendix J for further detail on
   (squeezed) point compression.

   The scalar representation and (squeezed) point representation
   illustrated above are fully consistent with the representations
   specified in [RFC8032].  Note that, contrary to [RFC7748], [RFC8032]
   requires unique representations of all elements of GF(p).

   A randomized representation (t1, t2) of the point k*Pe in tight LSB/
   lsb order is given by

   t1          577913017083163641949634219017190182170288776648725395935
               97750427519399254040

               (=0x181a32c5 10e06dbc ea321882 f3519055 535e289e 8faac654
               82e26f61 aded23fe)

   t2          454881407940919718426608573125377401686255068210624245884
               05479716220480287974

Struik                  Expires January 25, 2020               [Page 58]
Internet-Draft         lwig-curve-representations              July 2019

               (=0x672e36c5 ae353073 cdfac343 e8297b05 1b010d0f 5b1016db
               dd4baf54 28068926),

   where this representation is defined in Appendix L.4 and uses the
   mapping of Appendix L.3.3 with the default square root function and
   underlying isomorphic mapping between Edwards25519 and Curve25519 of
   Appendix E.2.

K.3.  Example with Wei25519

   Pw=(X, Y), k*Pw=(X1, Y1), and (k+1)*Pw=(X2, Y2) with Wei25519:

   X   14428294459702615171094958724191825368445920488283965295163094662
       783879239338

       (=0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
       2a41cf12 629e56aa).

   Y   53327798092436462013048370302019946300826511459161905709144645521
       233690313086

       (=0x75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b
       ae35ca26 df75417e).

   X1  34422557393689369648095312405803933433606568476197477554293337733
       87341283644

       (=0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4
       ce660f13 3368c13c).

   Y1  76981661982917351630937517222412729130882368858134322156485762195
       67913357634

       (=0x110501f6 1dff511e d6c4e9b9 bfd5acbe 8bf043b8 c3e381dd
       f5771306 479ad142).

   X2  22716193187790487472805844610038683159372373526135883092373909944
       834653057415

       (=0x3238e8e2 ec6e8b7a e1e8feff 97aa58dd d2435bb5 0071cbc2
       0d0d4a42 9be67187).

   Y2  43046985853631671610553834968785204191967171967937842531656254539
       962663994648

       (=0x5f2bbb06 f7ec5953 2c2a1a62 21124585 1d2682e0 cc37307e
       fbc17f7f 7fda8518).

Struik                  Expires January 25, 2020               [Page 59]
Internet-Draft         lwig-curve-representations              July 2019

   The representation of k and the compressed representations of Pw and
   k*Pw in tight MSB/msb-order are given by

   repr(k)     =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
               c08d5abd 15e29c50;

   repr(Pw)    =0x1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b 55202fe7
               2a41cf12 629e56aa;

   repr(k*Pw)  =0x079c3f69 9b688181 69038c35 39c11eb5 96d09f5b 12a242b4
               ce660f13 3368c13c,

   where the leftmost bit of the leftmost octet indicates the parity of
   the Y-coordinate of the point of Wei25519 in question (which, in this
   case, are both zero, since Y and Y1 are even).  See Appendix I.1 and
   Appendix J for further detail on (squeezed) point compression.

   The scalar representation is consistent with the representations
   specified in [SEC1]; the (squeezed) point representation illustrated
   above is "new".  For completeness, we include a SEC1-consistent
   representation of the point Pw in affine format and in compressed
   format below.

   The SEC1-compliant affine representation of the point Pw in tight
   MSB/msb-order is given by

   aff(Pw)     =0x04 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b
               55202fe7 2a41cf12 629e56aa

               75e676ce deee3b3c 12942357 22f1d884 ac06de07 330fb07b
               ae35ca26 df75417e,

   whereas the SEC1-compliant compressed representation of the point Pw
   in tight MSB/msb-order is given by

   compr(Pw)   =0x02 1fe62011 89e0801e f1debed7 456a3dc7 94d3ac0b
               55202fe7 2a41cf12 629e56aa;

   The SEC1-compliant uncompressed format aff(Pw) of an affine point Pw
   corresponds to the right-concatenation of its X- and Y-coordinates,
   each in tight MSB/msb-order, prepended by the string 0x04, where the
   reverse procedure is uniquely defined, since elements of GF(p) have a
   unique fixed-size representation.  The (squeezed) compressed format
   repr(Pw) corresponds to the SEC1-compliant compressed format by
   extracting the parity bit t from the leftmost bit of the leftmost
   octet of repr(Pw), replacing the bit position by the value zero, and
   prepending the octet string with 0x02 or 0x03, depending on whether
   t=0 or t=1, respectively, where the reverse procedure is uniquely

Struik                  Expires January 25, 2020               [Page 60]
Internet-Draft         lwig-curve-representations              July 2019

   defined, since GF(p) is a 255-bit prime field.  For further details,
   see [SEC1].

   A randomized representation (t1, t2) of the point k*Pw in tight MSB/
   msb order is given by

   t1          446363445988889734093446280484122107283059206243307955388
               84223152228795899590

               (=0x62af4697 4dd469ac 96c64809 c16c8517 b6a0cee5 40ba0e2e
               6dd2b36a fcc75ec6)

   t2          213890166610228613105792710708385961712211281744756216061
               11930888059603107561

               (=0x2f49c121 8fed7912 031157ee ae066507 a972320b 6180e267
               4025b006 2e67bee9),

   where this representation is defined in Appendix L.4 and uses the
   mapping of Appendix L.3.1 with the default square root function.

K.4.  Example with Wei25519.2

   Pw2=(X, Y), k*Pw2=(X1, Y1), and (k+1)*Pw2=(X2, Y2) with Wei25519.2:

   X   17830493209951148331008014701079988862634531394137235438571836389
       227198459763

       (=0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
       f21c8672 d1ecaf73).

   Y   21064492012933896105338241940477778461866060481408222122979836206
       137075789640

       (=0x2e921479 5ad47af7 784831de 572ed8e9 7e20e137 cc67378c
       184ca19f f9136f48).

   X1  65470988951686461979789632362377759464688342154017353834939203791
       39281908968

       (=0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183
       e242192d 3b87f4e8).

   Y1  51489590494292183562535790579480033229043271539297275888817125227
       35262330110

       (=0x0b623521 c1ff84bc 1522ff26 3376796d be77fcad 1fcabc28
       98f1be85 d7576cfe).

Struik                  Expires January 25, 2020               [Page 61]
Internet-Draft         lwig-curve-representations              July 2019

   X2  83741788501517200942826153677682120998854086551751663061374935388
       3494226693

       (=0x01d9f633 b2ac2606 9e6e93f7 6917446c 2b27c16f 729121d7
       709c0a58 00ef9b05).

   Y2  42567334190622848157611574766896093933050043101247319937794684825
       168161540336

       (=0x5e1c41e1 fb74e41b 3a19ce50 e1b2caf7 7cabcbb3 0c1c1474
       a4fd13e6 6c4c08f0).

   The representation of k and the compressed representations of Pw2 and
   k*Pw2 in tight MSB/msb-order are given by

   repr(k)     =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
               c08d5abd 15e29c50;

   repr(Pw2)   =0x276bb396 d766b695 bfe60ab1 3c0260dd c09f5bcf 7b3ca47c
               f21c8672 d1ecaf73;

   repr(k*Pw2) =0x0e7986d2 e94354ab 8abd8806 3154536a 4dcf8e6e 65557183
               e242192d 3b87f4e8,

   where the leftmost bit of the leftmost octet indicates the parity of
   the Y-coordinate of the point of Wei25519.2 in question (which, in
   this case, are both zero, since Y and Y1 are even).  See
   Appendix Appendix I.1 and Appendix J for further detail on (squeezed)
   point compression.

   A randomized representation (t1, t2) of the point k*Pw2 in tight MSB/
   msb order is given by

   t1          416669672354928148679758598803660112405431159793278161879
               36189858804289581274

               (=0x5c1eaaef 80f9d4af 33c119fc c99acd58 f81e7d69 999c7048
               e4043a77 87a930da)

   t2          361115271162391608083096560179337391059615651279123199921
               18531180247832114098

               (=0x4fd66668 e7174775 de44c852 92df8cfe b9832ef8 2570b3b8
               fe5ec21a b2d4b3b2),

   where this representation is defined in Appendix L.4 and uses the
   mapping of Appendix L.3.1 with the default square root function.

Struik                  Expires January 25, 2020               [Page 62]
Internet-Draft         lwig-curve-representations              July 2019

K.5.  Example with Wei25519.-3

   Pw3=(X, Y), k*Pw3=(X1, Y1), and (k+1)*Pw3=(X2, Y2) with Wei25519.-3:

   X   14780197759513083469009623947734627174363231692126610860256057394
       455099634096

       (=0x20ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
       eb4c9272 03ca71b0).

   Y   45596733430378470319805536538617129933663237960146030424392249401
       952949482817

       (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062
       b43ef4c9 73f7b541).

   X1  47362979975244556396292400751828272600887612546997532158738958926
       60745725532

       (=0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
       63b8455e 2e04e65c).

   Y1  30318112837157047703426636957515037640997356617656007157255559136
       153389790354

       (=0x64ced628 e982648e 4bfcf30c 71c4d267 ba48b0ce fee20062
       b43ef4c9 73f7b541).

   X2  23778942085873786433506063022059853212880296499622328201295446580
       293591664363

       (=0x3492677e 6ae9d1c3 e08f908b 61033f3d 4e8322c9 fba6da81
       2c95b067 9b1486eb).

   Y2  44846366394651736248316749170687053272682847823018287439056537991
       969511150494

       (=0x632624d4 ab94c83a 796511c0 5f5412a3 876e56d2 ed18eca3
       21b95bef 7bf9939e).

   The representation of k and the compressed representations of Pw3 and
   k*Pw3 in tight MSB/msb-order are given by

   repr(k)     =0x6485b7e6 cd83e5c2 0d5dbfe4 f915494d 9cf5c65d 778c32c3
               c08d5abd 15e29c50;

   repr(Pw3)   =0xa0ad4ba4 612f0586 221787b0 d01ba46c d1d8cd5a 0348ef00
               eb4c9272 03ca71b0;

Struik                  Expires January 25, 2020               [Page 63]
Internet-Draft         lwig-curve-representations              July 2019

   repr(k*Pw3) =0x0a78a650 a39995ef dcf4de88 940d4ce9 5b2ca35c c5d70e06
               63b8455e 2e04e65c,

   where the leftmost bit of the leftmost octet indicates the parity of
   the Y-coordinate of the point of Wei25519.-3 in question (which, in
   this case, are one and zero, respectively, since Y is odd and Y1 is
   even).  See Appendix I.1 and Appendix J for further detail on
   (squeezed) point compression.

   A randomized representation (t1, t2) of the point k*Pw3 in tight MSB/
   msb order is given by

   t1          573714937613596601525680684642155667097217474964816246889
               88981227297409008259

               (=0x7ed71d5f 566d2259 99bdb404 bfb9d6cf d2e86ccb 1894d4a6
               c75e3c69 e5eb0283)

   t2          269945781324580189815142015663892935722419453863927287235
               57891665397640090729

               (=0x3bae63c8 70f60de0 c2e35f94 d24220f1 bb6efd00 37625869
               f84923de ff4c5469),

   where this representation is defined in Appendix L.4 and uses the
   mapping of Appendix L.3.1 with the default square root function.

Appendix L.  Auxiliary Functions

L.1.  Square Roots in GF(q)

   Square roots are easy to compute in GF(q) if q = 3 (mod 4) (see
   Appendix L.1.1) or if q = 5 (mod 8) (see Appendix L.1.2).  Details on
   how to compute square roots for other values of q are out of scope.
   If square roots are easy to compute in GF(q), then so are these in
   GF(q^2).

L.1.1.  Square Roots in GF(q), where q = 3 (mod 4)

   If y is a nonzero element of GF(q) and z:= y^{(q-3)/4}, then y is a
   square in GF(q) only if y*z^2=1.  If y*z^2=1, z is a square root of
   1/y and y*z is a square root of y in GF(q).

L.1.2.  Square Roots in GF(q), where q = 5 (mod 8)

   If y is a nonzero element of GF(q) and z:=y^{z-5)/8}, then y is a
   square in GF(q) only if y^2*z^4=1.

Struik                  Expires January 25, 2020               [Page 64]
Internet-Draft         lwig-curve-representations              July 2019

   a.  If y*z^2=+1, z is a square root of 1/y and y*z is a square root
       of y in GF(q);

   b.  If y*z^2=-1, i*z is a square root of 1/y and i*y*z is a square
       root of y.

   Here, i is an element of GF(q) for which i^2=-1 (e.g.,
   i:=2^{(q-1)/4}).  This field element can be precomputed.

L.2.  Inversion

   If y is an integer and gcd(y,n)=1, one can efficiently compute 1/y
   (mod n) via the extended Euclidean Algorithm (see Section 2.2.5 of
   [GECC]).  One can use this algorithm as well to compute the inverse
   of a nonzero element y of a prime field GF(p), since gcd(y,p)=1.

   The inverse of a nonzero element y of GF(q) can be computed as

       1/y:=y^{q-2} (since y^{q-1}=1).

   Further details are out of scope.  If inverses are easy to compute in
   GF(q), then so are these in GF(q^2).

   The inverses of two nonzero elements y1 and y2 of GF(q) can be
   computed by first computing the inverse z of y1*y2 and by
   subsequently computing y2*z=:1/y1 and y1*z=:1/y2.

L.3.  Mapping to Curve Points

   One can map elements of GF(q) that are not a square in GF(q) to
   points of a Weierstrass curve (see Appendix L.3.1), to points of a
   Montgomery curve (see Appendix L.3.2), or to points of a twisted
   Edwards curve (see Appendix L.3.3), under some mild conditions on the
   domain parameters.  Full details on mappings that apply if these
   conditions are not satisfied are out of scope.

L.3.1.  Mapping to Points of Weierstrass Curve

   The description below assumes that the domain parameters a and b of
   the Weierstrass curve W_{a,b} are nonzero.  For ease of exposition,
   we define f(z):=z^3+a*z+b.  (Note that for an affine point (X,Y) of
   W_{a,b} one has Y^2=f(X).)

   If t is an element of GF(q) that is not a square in GF(q) and that is
   unequal to -1, then the element X:=(-b/a)*(1+1/(t+t^2)) is the unique
   solution of the equation f(t*X)=t^3*f(X) and is nonzero.
   Consequently, either X or X':=t*X is the x-coordinate of an affine
   point of W{a,b}, depending on whether f(X) is a square in GF(q).

Struik                  Expires January 25, 2020               [Page 65]
Internet-Draft         lwig-curve-representations              July 2019

   a.  If f(X) is a square in GF(q) and Y:=sqrt(f(X)), then t is mapped
       to the point P(t):=(X, Y);

   b.  If f(X) is not a square in GF(q) and Y':=sqrt(f(X')), then t is
       mapped to the point P(t):=(X', -Y').

   Formally, this mapping is not properly defined, since a nonzero
   square y:=x^2 in GF(q) has two solutions, viz. x and -x; it is
   properly defined, however, if one designates for each element in
   GF(q) that is a square in GF(q) precisely one square root as "the"
   square root of this element.  Note that always picking the square
   root with zero parity (see Appendix I) satisfies this condition
   (henceforth called the default square root function).

   If -1 is not a square in GF(q), this element is mapped to the point
   at infinity O of W_{a,b}.

   The set of points of W_{a,b} that arises this way has size roughly
   3/8 of the order of the curve and each such point arises as image of
   one or two t values.  Further details are out of scope.

   NOTE 1: If -1 is not a square in GF(q), the mapping above yields the
   point at infinity for t=-1.  One can modify this mapping to always
   yield an affine point, by mapping the element -1 to, e.g., the base
   point G of W_{a,b} and leaving the remainder of the mapping the same.
   Suitability of such a modification is application-specific.  Details
   are out of scope.

   NOTE 2: The description above assumes that the domain parameters a
   and b of the Weierstrass curve are nonzero.  If this is not the case,
   one can often find an isogenous curve W_{a',b'} for which the domain
   parameters a' and b' are nonzero.  If so, one can map elements of
   GF(q) that are not a square in GF(q) to points of W_{a,b} via
   function composition, where one uses the mapping above to arrive at a
   point of W_{a',b'} and where one subsequently uses the dual isogeny
   from W_{a',b'} to W_{a,b} to arrive at a point of W_{a,b}. As an
   example, one can show that if a is zero and -4*b is a cube in GF(q)
   (such as is the case with, e.g., the "BitCoin" curve secp256k1
   [SEC2]), this curve is 3-isogenous to a curve with this property and
   the strategy above applies (for an example with secp256k1, see
   Appendix M).  Further details are out of scope.

L.3.2.  Mapping to Points of Montgomery Curve

   The description below assumes that the domain parameter A of the
   Montgomery curve M_{A,B} is nonzero.  For ease of exposition, we
   define f(z):=z^3+A*z^2+z.  (Note that for an affine point (u,v) of
   M_{A,B} one has B*v^2=f(u).)

Struik                  Expires January 25, 2020               [Page 66]
Internet-Draft         lwig-curve-representations              July 2019

   If t is an element of GF(q) that is not a square in GF(q) and that is
   unequal to -1, then the element u:=-(1+1/t)/A is the unique nonzero
   solution of the equation f(t*u)=t^3*f(u).  Consequently, either u or
   u':=t*u is the u-coordinate of an affine point of M{A,B}, depending
   on whether f(u)/B is a square in GF(q).

   a.  If f(u)/B is a square in GF(q) and v:=sqrt(f(u)/B), then t is
       mapped to the point P(t):=(u, v);

   b.  If f(u)/B is a not a square in GF(q) and v':=sqrt(f(u')/B), then
       t is mapped to the point P(t):=(u', -v').

   As before, formally, this mapping is not properly defined, since a
   nonzero square y:=x^2 in GF(q) has two solutions, viz. x and -x; it
   is properly defined, however, if one designates for each element in
   GF(q) that is a square in GF(q) precisely one square root as "the"
   square root of this element.  Note that always picking the square
   root with zero parity (see Appendix I) satisfies this condition
   (henceforth called the default square root function).

   If -1 is not a square in GF(q), this element is mapped to the point
   at infinity O of M_{A,B}.

   The set of points of M_{A,B} that arises this way has size roughly
   1/2 of the order of the curve and each such point arises as image of
   precisely one t value.  Further details are out of scope.

   NOTE 1: If -1 is not a square in GF(q), the mapping above yields the
   point at infinity for t=-1.  One can modify this mapping to always
   yield an affine point, by mapping the element -1 to, e.g., the base
   point G of M_{A,B} and leaving the remainder of the mapping the same.
   Suitability of such a modification is application-specific.  Details
   are out of scope.

   NOTE 2: The description above assumes that the domain parameter A of
   the Montgomery curve is nonzero.  If this is not the case, the curve
   is a Weierstrass curve for which the domain parameter b is zero and
   Note 2 of Appendix L.3.1 applies.  If q = 3 (mod 4), an even simpler
   approach is possible, where one modifies the construction above and
   simply takes u:=t and u':=-t (which works, since -1 is not a square
   in GF(q) and f(-t)=-f(t)).  In this case, this construction can be
   extended to all elements t of GF(q) and, if so, yields a 1-1 mapping
   between GF(q) and all affine curve points.

Struik                  Expires January 25, 2020               [Page 67]
Internet-Draft         lwig-curve-representations              July 2019

L.3.3.  Mapping to Points of Twisted Edwards Curve

   One can map elements of GF(q) that are not a square in GF(q) to
   points of the twisted Edwards curve E_{a,d} via function composition,
   where one uses the mapping of Appendix L.3.1 to arrive at a point of
   the Weierstrass curve W_{a,b} and where one subsequently uses the
   isomorphic mapping between twisted Edwards curves and Weierstrass
   curves of Appendix D.3 to arrive at a point of E_{a,d}. Another
   mapping is obtained by function composition, where one instead uses
   the mapping of Appendix L.3.2 to arrive at a point of the Montgomery
   curve M_{A,B} and where one subsequently uses the isomorphic mapping
   between twisted Edwards curves and Montgomery curves of Appendix D.1
   to arrive at a point of E_{a,d}. Obviously, one can use function
   composition (now using the respective pre-images - if these exist) to
   realize the pre-images of either mapping.

L.4.  Randomized Representation of Curve Points

   The mappings of Appendix L.3.1, Appendix L.3.2, and Appendix L.3.3
   allow one to represent a curve point Q as a specific element of
   GF(q), provided this point arises as a point in the range of the
   mapping at hand.  For Montgomery curves and twisted Edwards curves,
   this covers roughly half of the curve points; for Weierstrass curves,
   roughly 3/8 of the curve points.  One can extend the mappings above,
   by mapping a pair (t1, t2) of inputs to the point Q:=P2(t1,
   t2):=P(t1) + P(t2).  In this case, each curve point has roughly q/4
   representations as an ordered pair (t1, t2) on average.  In fact, one
   can show that if the input pairs are generated uniformly at random,
   then the corresponding curve points follow a distribution that is
   also (statistically indistinguishable from) a uniform distribution,
   and vice-versa.  Here, each pair (t1, t2) deterministically yields a
   curve point, whereas for each curve point Q, a randomized algorithm
   yields an ordered pair (t1, t2) of pre-images of Q, where the
   expected number of randomized pre-images one has to try is small
   (four if one uses the mapping of Appendix L.3.1; two if one uses the
   mapping of Appendix L.3.2).  For further details, see Algorithm 1 of
   [Tibouchi].

Appendix M.  Curve secp256k1 and Friend

M.1.  Curve Definition and Alternative Representation

   The elliptic curve secp256k1 is the Weierstrass curve W_{a,b} defined
   over the prime field GF(p), with p:=2^256-2^32-2^9-2^8-2^7-2^6-2^4-1,
   where a:=0 and b:=7.  This curve has order h*n, where h=1 and where n
   is a prime number.  For this curve, domain parameter a is zero,
   whereas b is not.  The quadratic twist of this curve has order h1*n1,

Struik                  Expires January 25, 2020               [Page 68]
Internet-Draft         lwig-curve-representations              July 2019

   where h1 is a 37-bit integer and where n1 is a prime number.  For
   this curve, the base point is the point (GX, GY).

   The curve secp256k1 is 3-isogenous to the Weierstrass curve
   secp256k1.m defined over GF(p), which has nonzero domain parameters a
   and b and has as base point the pair (GmX,GmY), where parameters are
   as specified in Appendix M.3 and where the related mappings are as
   specified in Appendix M.2.

M.2.  Switching Between Representations

   Each affine point (X,Y) of secp256k1 corresponds to the point
   (X',Y'):=(u(X)/w(X)^2,Y*v(X)/w(X)^3) of secp256k1.m, where u, v, and
   w are the polynomials with coefficients in GF(p) as defined in
   Appendix M.4.1, while the point at infinity of secp256k1 corresponds
   to the point at infinity of secp256k1.m.  Under this isogenous
   mapping, the base point (GX,GY) of secp256k1 corresponds to the base
   point (GmX,GmY) of secp256k1.m.  The dual isogeny maps the affine
   point (X',Y') of secp256k1.m to the affine point
   (X,Y):=(u'(X')/w'(X')^2,Y'*v'(X')/w'(X')^3) of secp256k1, where u',
   v', and w' are the polynomials with coefficients in GF(p) as defined
   in Appendix M.4.2, while mapping the point at infinity O of
   secp256k1.m to the point at infinity O of secp256k1.  Under this dual
   isogenous mapping, the base point (GmX, GmY) of secp256k1.m
   corresponds to a multiple of the base point (GX, GY) of secp256k1,
   where this multiple is l=3 (the degree of the isogeny; see the
   description in Appendix F.4).  Note that this isogenous map (and its
   dual) primarily involves the evaluation of three fixed polynomials
   involving the x-coordinate, which takes roughly 10 modular
   multiplications (or less than 1% relative incremental cost compared
   to the cost of an elliptic curve scalar multiplication).

M.3.  Domain Parameters

   The parameters of the curve sec256k1 and the corresponding
   3-isogenous curve sec256k1.m are as indicated below.  Here, the
   domain parameters of the curve secp256k1 are as specified in [SEC2];
   the domain parameters of secp256k1.m are "new".

   General parameters (for all curves):

   p   2^256-2^32-2^9-2^8-2^7-2^6-2^4-1

       (=0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
       fffffffe fffffc2f)

   h   1

Struik                  Expires January 25, 2020               [Page 69]
Internet-Draft         lwig-curve-representations              July 2019

   n   11579208923731619542357098500868790785283756427907490438260516314
       1518161494337

       (=0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b
       bfd25e8c d0364141)

   h1  23479460174521 (=0x1a 9bfcab89)

   n1  10131766773001318469008702396060356387381009972480920692566974370
       31

       (=0x099ee564 ea5d84f5 08913936 a761b0d5 d792a426 a7779817
       ae2f5b67)

   Weierstrass curve-specific parameters (for secp256k1):

   a   0 (=0x00)

   b   7 (=0x07)

   GX  55066263022277343669578718895168534326250603453777594175500187360
       389116729240

       (=0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9
       59f2815b 16f81798)

   GY  32670510020758816978083085130507043184471273380659243275938904335
       757337482424

       (=0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419
       9c47d08f fb10d4b8)

   Weierstrass curve-specific parameters (for secp256k1.m):

   a   93991599167772749909245591943117186381494883464374162770646538702
       960816911535

       (=0xcfcd5c21 75e2ef7d ccdce737 770b7381 5a2f13c5 09035ca2
       54a14ac9 f08974af)

   b   1771 (=0x06eb)

   GmX 26591621185618668069038227574782692264471832498547635565821216767
       730887659845

       (=0x3aca5300 959fa1d0 baf78dcf f77a616f 395e586d 67aced0a
       88798129 0c279145)

Struik                  Expires January 25, 2020               [Page 70]
Internet-Draft         lwig-curve-representations              July 2019

   GmY 67622516283223102233819216063319565850973524550533340939716651159
       860372686848

       (=0x9580fce5 3a170f4f b744579f f3d62086 12cd6a23 3e2de237
       f976c6a7 8611c800)

M.4.  Isogeny Details

   The isogeny and dual isogeny are both isogenies with degree l=3.
   Both are specified by a triple of polynomials u, v, and w (resp. u',
   v', and w') of degree 3, 3, and 1, respectively, with coefficients in
   GF(p).  The coeffients of each of these polynomials are specified in
   Appendix M.4.1 (for the isogeny) and in Appendix M.4.2 (for the dual
   isogeny).  For each polynomial in variable x, the coefficients are
   tabulated as sequence of coefficients of x^0, x^1, x^2, ..., in
   hexadecimal format.

M.4.1.  Isogeny Parameters

M.4.1.1.  Coefficients of u(x)

   0  0x54

   1  0xa4d89db3ed06c81e6143ec2eca9f761d8d17260dc229e1da1f73f714506872a9

   2  0xcc58ffccbd9febb4a66222c7d1311d988d88c0624bcd68ec4c758a8e67dfd99b

   3  0x01

M.4.1.2.  Coefficients of v(x)

   0  0x1c

   1  0x94c7bc69befd17f2fae2e3ebf24df1f355d181fa1a8056103ba9baad4b40f029

   2  0xb2857fb31c6fe18ef993342bb9c9ac64d44d209371b41d6272b04fd61bcfc851

   3  0x01

M.4.1.3.  Coefficients of w(x)

   0  0xe62c7fe65ecff5da53311163e8988ecc46c4603125e6b476263ac546b3efeae5

   1  0x01

Struik                  Expires January 25, 2020               [Page 71]
Internet-Draft         lwig-curve-representations              July 2019

M.4.2.  Dual Isogeny Parameters

M.4.2.1.  Coefficients of u'(x)

   0  0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7

   1  0x44cd5cd7ce55a801725891578fbe7356bd936355fd0e2f538797cecff7a37244

   2  0x668d0011162006c3c889f4680f9a4b77d0d26a89e6bb87b13bd8d1cfdd600a41

   3  0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c

M.4.2.2.  Coefficients of v'(x)

   0  0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c

   1  0x519ba9c1f48f68054def6a410f0fa6e8b71c6c3b4a8958324681f6508c01fada

   2  0xb34680088b100361e444fa3407cd25bbe8693544f35dc3d89dec68e76eb00338

   3  0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84

M.4.2.3.  Coefficients of w'(x)

   0  0x4d7a804ce3901e71066ccbd44636539b2bb2df6c8e4be29d8d4fb028e43033de

   1  0x01

Author's Address

   Rene Struik
   Struik Security Consultancy

   Email: rstruik.ext@gmail.com

Struik                  Expires January 25, 2020               [Page 72]