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  *              Returns failure (@-1@) if the flags are invalid, or if there
  59  *              isn't enough space in the output buffer.
  60  */
  61
  62 int ec_ec2osp(ec_curve *c, unsigned f, buf *b, const ec *p)
  63 {
  64   octet *q;
  65   size_t n;
  66   ec t = EC_INIT;
  67
  68   /* --- Check the requested flags for sanity --- */
  69
  70   if (!f) f = EC_XONLY;
  71   if (f & ~((f & EC_XONLY) ? EC_XONLY :
  72             (f & EC_CMPR) ? (EC_CMPR | EC_EXPLY | EC_SORT) :
  73             (f & EC_EXPLY) ? EC_EXPLY :
  74             0u))
  75     return (-1);
  76
  77   /* --- Point at infinity --- */
  78
  79   if (EC_ATINF(p)) return (buf_putbyte(b, 0));
  80
  81   /* --- Fix up the format byte, compressing the %$y$%-coordinate --- */
  82
  83   if (f & EC_CMPR) {
  84     if (!(f & EC_SORT))
  85       f |= EC_COMPR(c, p) ? EC_YBIT : 0;
  86     else {
  87       ec_neg(c, &t, p);
  88       f |= MP_CMP(p->y, >, t.y);
  89       EC_DESTROY(&t);
  90     }
  91   }
  92
  93   /* --- Write the format byte --- */
  94
  95   if (buf_putbyte(b, f)) return (-1);
  96
  97   /* --- Write the %$x$%-coordinate --- */
  98
  99   n = c->f->noctets;
 100   if ((q = buf_get(b, n)) == 0) return (-1);
 101   mp_storeb(p->x, q, n);
 102
 103   /* --- Write the %$y$%-coordinate if we need one --- */
 104
 105   if (f & EC_EXPLY) {
 106     if ((q = buf_get(b, n)) == 0) return (-1);
 107     mp_storeb(p->y, q, n);
 108   }
 109
 110   /* --- All done --- */
 111
 112   return (0);
 113 }
 114
 115 /* --- @ec_os2ecp@ --- *
 116  *
 117  * Arguments:   @ec_curve *c = elliptic curve
 118  *              @unsigned f@ = format flags for input
 119  *              @buf *b@ = pointer to a buffer
 120  *              @ec *d@ = an elliptic curve point
 121  *
 122  * Returns:     Zero on success, nonzero on failure.
 123  *
 124  * Use:         Reads an elliptic curve point from the given buffer using the
 125  *              standard uncompressed format described in P1363 and SEC1.
 126  *
 127  *              Point compression features are determined by @f@ as follows.
 128  *              If @EC_LSB@ is set, then accept an LSB-compressed %$y$%-
 129  *              coordinate; if @EC_SORT@ is set, then accept a SORT-
 130  *              compressed %$y$%-coordinate; if @EC_EXPLY@ is set, then
 131  *              accept an explicit %$y$%-coordinate; if @EC_XONLY@ is set
 132  *              then accept a bare %$x$%-coordinate (a correct
 133  *              %$y$%-coordinate is chosen arbitrarily).  Hybrid forms are
 134  *              acceptable, and the input is checked to verify that the
 135  *              redundant representations are consistent.  If no flags are
 136  *              set in @f@, then no input (other than the point at infinity)
 137  *              will be acceptable.
 138  */
 139
 140 int ec_os2ecp(ec_curve *c, unsigned f, buf *b, ec *d)
 141 {
 142   const octet *q;
 143   size_t n;
 144   ec t = EC_INIT, tt = EC_INIT;
 145   mp *x = MP_NEW, *y = MP_NEW;
 146   int g, gwant;
 147   int rc = -1;
 148
 149   /* --- Read the format byte --- */
 150
 151   if ((g = buf_getbyte(b)) < 0) goto done;
 152
 153   /* --- Point at infinity --- */
 154
 155   if (!g) { EC_SETINF(d); rc = 0; goto done; }
 156
 157   /* --- Fetch the %$x$%-coordinate --- */
 158
 159   n = c->f->noctets;
 160   if ((q = buf_get(b, n)) == 0) goto done;
 161   x = mp_loadb(x, q, n);
 162
 163   /* --- If we're compressing then figure out the right value --- *
 164    *
 165    * Also check that the format is acceptable to the caller.
 166    */
 167
 168   switch (g & ~EC_EXPLY) {
 169     case 0:
 170       t.x = x; x = MP_NEW; break;
 171     case EC_XONLY:
 172       gwant = EC_XONLY; goto decompr;
 173     case EC_CMPR: case EC_CMPR | EC_YBIT:
 174       gwant = EC_LSB; goto decompr;
 175     case EC_CMPR | EC_SORT: case EC_CMPR | EC_SORT | EC_YBIT:
 176       gwant = EC_SORT; goto decompr;
 177     default: goto done;
 178     decompr:
 179       if (!(f & gwant)) goto done;
 180       if (!ec_find(c, &t, x)) goto done;
 181       switch (gwant) {
 182         case EC_LSB:
 183           if (!EC_COMPR(c, &t) != !(g & EC_YBIT)) ec_neg(c, &t, &t);
 184           if (!EC_COMPR(c, &t) != !(g & EC_YBIT)) goto done;
 185           break;
 186         case EC_SORT:
 187           ec_neg(c, &tt, &t);
 188           if (!MP_CMP(t.y, >, tt.y) != !(g & EC_YBIT)) {
 189             if (MP_EQ(t.y, tt.y)) goto done;
 190             MP_DROP(t.y); t.y = MP_COPY(tt.y);
 191           }
 192           break;
 193         case EC_XONLY:
 194           break;
 195         default:
 196           abort();
 197       }
 198   }
 199
 200   /* --- If an explicit %$y$%-coordinate is specified, read it in --- */
 201
 202   if (g & EC_EXPLY) {
 203     if (!(f & EC_EXPLY)) goto done;
 204     if ((q = buf_get(b, n)) == 0) goto done;
 205     y = mp_loadb(y, q, n);
 206     if (!t.y) t.y = MP_COPY(y);
 207     else if (!MP_EQ(y, t.y)) goto done;
 208   }
 209
 210   /* --- We're ready --- */
 211
 212   EC_COPY(d, &t);
 213   rc = 0;
 214
 215   /* --- Clean up --- */
 216
 217 done:
 218   if (x) MP_DROP(x);
 219   if (y) MP_DROP(y);
 220   if (t.x) MP_DROP(t.x); if (t.y) MP_DROP(t.y);
 221   EC_DESTROY(&tt);
 222   return (rc);
 223 }
 224
 225 /* --- @ec_putraw@ --- *
 226  *
 227  * Arguments:   @ec_curve *c@ = elliptic curve
 228  *              @buf *b@ = pointer to a buffer
 229  *              @const ec *p@ = an elliptic curve point
 230  *
 231  * Returns:     Zero on success, nonzero on failure.
 232  *
 233  * Use:         Puts an elliptic curve point to the given buffer using the
 234  *              standard uncompressed format described in P1363 and SEC1.
 235  *              This requires at most @1 + 2 * c->f->noctets@ space in the
 236  *              buffer.  We don't do point compression.
 237  */
 238
 239 int ec_putraw(ec_curve *c, buf *b, const ec *p)
 240   { return (ec_ec2osp(c, EC_EXPLY, b, p)); }
 241
 242 /* --- @ec_getraw@ --- *
 243  *
 244  * Arguments:   @ec_curve *c@ = elliptic curve
 245  *              @buf *b@ = pointer to a buffer
 246  *              @ec *d@ = an elliptic curve point
 247  *
 248  * Returns:     Zero on success, nonzero on failure.
 249  *
 250  * Use:         Reads an elliptic curve point from the given buffer using the
 251  *              standard uncompressed format described in P1363 and SEC1.
 252  *              We don't do point compression.
 253  */
 254
 255 int ec_getraw(ec_curve *c, buf *b, ec *d)
 256   { return (ec_os2ecp(c, EC_LSB | EC_SORT | EC_EXPLY, b, d)); }
 257
 258 /*----- That's all, folks -------------------------------------------------*/