chiark - git - mdw - catacomb/blob - math/ec-raw.c

   1 /* -*-c-*-
   2  *
   3  * Raw formatting of elliptic curve points
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "ec.h"
  31 #include "ec-raw.h"
  32
  33 /*----- Main code ---------------------------------------------------------*/
  34
  35 /* --- @ec_ec2osp@ --- *
  36  *
  37  * Arguments:   @ec_curve *c@ = elliptic curve
  38  *              @unsigned f@ = format flags for output
  39  *              @buf *b@ = pointer to a buffer
  40  *              @const ec *p@ = an elliptic curve point
  41  *
  42  * Returns:     Zero on success, nonzero on failure.
  43  *
  44  * Use:         Puts an elliptic curve point to the given buffer using the
  45  *              standard uncompressed format described in P1363 and SEC1.
  46  *              This requires at most @1 + 2 * c->f->noctets@ space in the
  47  *              buffer.
  48  *
  49  *              Point compression features are determined by @f@ as follows.
  50  *              If @EC_CMPR@ is set then point compression is performed and a
  51  *              compressed form of the %$y$%-coordinate is contained in the
  52  *              first output byte; if @EC_SORT@ is set then P1363a `SORT'
  53  *              compression is used, otherwise LSB compression.  If
  54  *              @EC_EXPLY@ is set, then an explicit %$y$%-coordinate is
  55  *              output in full.  Otherwise the %$y$%-coordinate is
  56  *              suppressed.
  57  */
  58
  59 int ec_ec2osp(ec_curve *c, unsigned f, buf *b, const ec *p)
  60 {
  61   octet *q;
  62   size_t n;
  63   ec t = EC_INIT;
  64
  65   /* --- Point at infinity --- */
  66
  67   if (EC_ATINF(p)) return (buf_putbyte(b, 0));
  68
  69   /* --- Fix up the format byte, compressing the %$y$%-coordinate --- */
  70
  71   if (!f)
  72     f = EC_XONLY;
  73   else if (f & EC_CMPR) {
  74     if (!(f & EC_SORT))
  75       f |= EC_COMPR(c, p) ? EC_YBIT : 0;
  76     else {
  77       ec_neg(c, &t, p);
  78       f |= MP_CMP(p->y, >, t.y);
  79       EC_DESTROY(&t);
  80     }
  81   }
  82
  83   /* --- Write the format byte --- */
  84
  85   if (buf_putbyte(b, f)) return (-1);
  86
  87   /* --- Write the %$x$%-coordinate --- */
  88
  89   n = c->f->noctets;
  90   if ((q = buf_get(b, n)) == 0) return (-1);
  91   mp_storeb(p->x, q, n);
  92
  93   /* --- Write the %$y$%-coordinate if we need one --- */
  94
  95   if (f & EC_EXPLY) {
  96     if ((q = buf_get(b, n)) == 0) return (-1);
  97     mp_storeb(p->y, q, n);
  98   }
  99
 100   /* --- All done --- */
 101
 102   return (0);
 103 }
 104
 105 /* --- @ec_os2ecp@ --- *
 106  *
 107  * Arguments:   @ec_curve *c = elliptic curve
 108  *              @unsigned f@ = format flags for input
 109  *              @buf *b@ = pointer to a buffer
 110  *              @ec *d@ = an elliptic curve point
 111  *
 112  * Returns:     Zero on success, nonzero on failure.
 113  *
 114  * Use:         Reads an elliptic curve point from the given buffer using the
 115  *              standard uncompressed format described in P1363 and SEC1.
 116  *
 117  *              Point compression features are determined by @f@ as follows.
 118  *              If @EC_LSB@ is set, then accept an LSB-compressed %$y$%-
 119  *              coordinate; if @EC_SORT@ is set, then accept a SORT-
 120  *              compressed %$y$%-coordinate; if @EC_EXPLY@ is set, then
 121  *              accept an explicit %$y$%-coordinate; if @EC_XONLY@ is set
 122  *              then accept a bare %$x$%-coordinate (a correct
 123  *              %$y$%-coordinate is chosen arbitrarily).  Hybrid forms are
 124  *              acceptable, and the input is checked to verify that the
 125  *              redundant representations are consistent.  If no flags are
 126  *              set in @f@, then no input (other than the point at infinity)
 127  *              will be acceptable.
 128  */
 129
 130 int ec_os2ecp(ec_curve *c, unsigned f, buf *b, ec *d)
 131 {
 132   const octet *q;
 133   size_t n;
 134   ec t = EC_INIT, tt = EC_INIT;
 135   mp *x = MP_NEW, *y = MP_NEW;
 136   int g, gwant;
 137   int rc = -1;
 138
 139   /* --- Read the format byte --- */
 140
 141   if ((g = buf_getbyte(b)) < 0) goto done;
 142
 143   /* --- Point at infinity --- */
 144
 145   if (!g) { EC_SETINF(d); rc = 0; goto done; }
 146
 147   /* --- Fetch the %$x$%-coordinate --- */
 148
 149   n = c->f->noctets;
 150   if ((q = buf_get(b, n)) == 0) goto done;
 151   x = mp_loadb(x, q, n);
 152
 153   /* --- If we're compressing then figure out the right value --- *
 154    *
 155    * Also check that the format is acceptable to the caller.
 156    */
 157
 158   switch (g & ~EC_EXPLY) {
 159     case 0:
 160       t.x = x; x = MP_NEW; break;
 161     case EC_XONLY:
 162       gwant = EC_XONLY; goto decompr;
 163     case EC_CMPR: case EC_CMPR | EC_YBIT:
 164       gwant = EC_LSB; goto decompr;
 165     case EC_CMPR | EC_SORT: case EC_CMPR | EC_SORT | EC_YBIT:
 166       gwant = EC_SORT; goto decompr;
 167     default: goto done;
 168     decompr:
 169       if (!(f & gwant)) goto done;
 170       if (!ec_find(c, &t, x)) goto done;
 171       switch (gwant) {
 172         case EC_LSB:
 173           if (!EC_COMPR(c, &t) != !(g & EC_YBIT)) ec_neg(c, &t, &t);
 174           if (!EC_COMPR(c, &t) != !(g & EC_YBIT)) goto done;
 175           break;
 176         case EC_SORT:
 177           ec_neg(c, &tt, &t);
 178           if (!MP_CMP(t.y, >, tt.y) != !(g & EC_YBIT)) {
 179             if (MP_EQ(t.y, tt.y)) goto done;
 180             MP_DROP(t.y); t.y = MP_COPY(tt.y);
 181           }
 182           break;
 183         case EC_XONLY:
 184           break;
 185         default:
 186           abort();
 187       }
 188   }
 189
 190   /* --- If an explicit %$y$%-coordinate is specified, read it in --- */
 191
 192   if (g & EC_EXPLY) {
 193     if (!(f & EC_EXPLY)) goto done;
 194     if ((q = buf_get(b, n)) == 0) goto done;
 195     y = mp_loadb(y, q, n);
 196     if (!t.y) t.y = MP_COPY(y);
 197     else if (!MP_EQ(y, t.y)) goto done;
 198   }
 199
 200   /* --- We're ready --- */
 201
 202   EC_COPY(d, &t);
 203   rc = 0;
 204
 205   /* --- Clean up --- */
 206
 207 done:
 208   if (x) MP_DROP(x);
 209   if (y) MP_DROP(y);
 210   if (t.x) MP_DROP(t.x); if (t.y) MP_DROP(t.y);
 211   EC_DESTROY(&tt);
 212   return (rc);
 213 }
 214
 215 /* --- @ec_putraw@ --- *
 216  *
 217  * Arguments:   @ec_curve *c@ = elliptic curve
 218  *              @buf *b@ = pointer to a buffer
 219  *              @const ec *p@ = an elliptic curve point
 220  *
 221  * Returns:     Zero on success, nonzero on failure.
 222  *
 223  * Use:         Puts an elliptic curve point to the given buffer using the
 224  *              standard uncompressed format described in P1363 and SEC1.
 225  *              This requires at most @1 + 2 * c->f->noctets@ space in the
 226  *              buffer.  We don't do point compression.
 227  */
 228
 229 int ec_putraw(ec_curve *c, buf *b, const ec *p)
 230   { return (ec_ec2osp(c, EC_EXPLY, b, p)); }
 231
 232 /* --- @ec_getraw@ --- *
 233  *
 234  * Arguments:   @ec_curve *c@ = elliptic curve
 235  *              @buf *b@ = pointer to a buffer
 236  *              @ec *d@ = an elliptic curve point
 237  *
 238  * Returns:     Zero on success, nonzero on failure.
 239  *
 240  * Use:         Reads an elliptic curve point from the given buffer using the
 241  *              standard uncompressed format described in P1363 and SEC1.
 242  *              We don't do point compression.
 243  */
 244
 245 int ec_getraw(ec_curve *c, buf *b, ec *d)
 246   { return (ec_os2ecp(c, EC_LSB | EC_SORT | EC_EXPLY, b, d)); }
 247
 248 /*----- That's all, folks -------------------------------------------------*/