[catacomb] / math / ec-raw.c

/* -*-c-*-
 *
 * Raw formatting of elliptic curve points
 *
 * (c) 2004 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Header files ------------------------------------------------------*/

#include "ec.h"
#include "ec-raw.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @ec_ec2osp@ --- *
 *
 * Arguments:	@ec_curve *c@ = elliptic curve
 *		@unsigned f@ = format flags for output
 *		@buf *b@ = pointer to a buffer
 *		@const ec *p@ = an elliptic curve point
 *
 * Returns:	Zero on success, nonzero on failure.
 *
 * Use:		Puts an elliptic curve point to the given buffer using the
 *		standard uncompressed format described in P1363 and SEC1.
 *		This requires at most @1 + 2 * c->f->noctets@ space in the
 *		buffer.
 *
 *		Point compression features are determined by @f@ as follows.
 *		If @EC_CMPR@ is set then point compression is performed and a
 *		compressed form of the %$y$%-coordinate is contained in the
 *		first output byte; if @EC_SORT@ is set then P1363a `SORT'
 *		compression is used, otherwise LSB compression.  If
 *		@EC_EXPLY@ is set, then an explicit %$y$%-coordinate is
 *		output in full.  Otherwise the %$y$%-coordinate is
 *		suppressed.
 *
 *		Returns failure (@-1@) if the flags are invalid, or if there
 *		isn't enough space in the output buffer.
 */

int ec_ec2osp(ec_curve *c, unsigned f, buf *b, const ec *p)
{
  octet *q;
  size_t n;
  ec t = EC_INIT;

  /* --- Check the requested flags for sanity --- */

  if (!f) f = EC_XONLY;
  if (f & ~((f & EC_XONLY) ? EC_XONLY :
	    (f & EC_CMPR) ? (EC_CMPR | EC_EXPLY | EC_SORT) :
	    (f & EC_EXPLY) ? EC_EXPLY :
	    0u))
    return (-1);

  /* --- Point at infinity --- */

  if (EC_ATINF(p)) return (buf_putbyte(b, 0));

  /* --- Fix up the format byte, compressing the %$y$%-coordinate --- */

  if (f & EC_CMPR) {
    if (!(f & EC_SORT))
      f |= EC_COMPR(c, p) ? EC_YBIT : 0;
    else {
      ec_neg(c, &t, p);
      f |= MP_CMP(p->y, >, t.y);
      EC_DESTROY(&t);
    }
  }

  /* --- Write the format byte --- */

  if (buf_putbyte(b, f)) return (-1);

  /* --- Write the %$x$%-coordinate --- */

  n = c->f->noctets;
  if ((q = buf_get(b, n)) == 0) return (-1);
  mp_storeb(p->x, q, n);

  /* --- Write the %$y$%-coordinate if we need one --- */

  if (f & EC_EXPLY) {
    if ((q = buf_get(b, n)) == 0) return (-1);
    mp_storeb(p->y, q, n);
  }

  /* --- All done --- */

  return (0);
}

/* --- @ec_os2ecp@ --- *
 *
 * Arguments:	@ec_curve *c = elliptic curve
 *		@unsigned f@ = format flags for input
 *		@buf *b@ = pointer to a buffer
 *		@ec *d@ = an elliptic curve point
 *
 * Returns:	Zero on success, nonzero on failure.
 *
 * Use:		Reads an elliptic curve point from the given buffer using the
 *		standard uncompressed format described in P1363 and SEC1.
 *
 *		Point compression features are determined by @f@ as follows.
 *		If @EC_LSB@ is set, then accept an LSB-compressed %$y$%-
 *		coordinate; if @EC_SORT@ is set, then accept a SORT-
 *		compressed %$y$%-coordinate; if @EC_EXPLY@ is set, then
 *		accept an explicit %$y$%-coordinate; if @EC_XONLY@ is set
 *		then accept a bare %$x$%-coordinate (a correct
 *		%$y$%-coordinate is chosen arbitrarily).  Hybrid forms are
 *		acceptable, and the input is checked to verify that the
 *		redundant representations are consistent.  If no flags are
 *		set in @f@, then no input (other than the point at infinity)
 *		will be acceptable.
 */

int ec_os2ecp(ec_curve *c, unsigned f, buf *b, ec *d)
{
  const octet *q;
  size_t n;
  ec t = EC_INIT, tt = EC_INIT;
  mp *x = MP_NEW, *y = MP_NEW;
  int g, gwant;
  int rc = -1;

  /* --- Read the format byte --- */

  if ((g = buf_getbyte(b)) < 0) goto done;

  /* --- Point at infinity --- */

  if (!g) { EC_SETINF(d); rc = 0; goto done; }

  /* --- Fetch the %$x$%-coordinate --- */

  n = c->f->noctets;
  if ((q = buf_get(b, n)) == 0) goto done;
  x = mp_loadb(x, q, n);

  /* --- If we're compressing then figure out the right value --- *
   *
   * Also check that the format is acceptable to the caller.
   */

  switch (g & ~EC_EXPLY) {
    case 0:
      t.x = x; x = MP_NEW; break;
    case EC_XONLY:
      gwant = EC_XONLY; goto decompr;
    case EC_CMPR: case EC_CMPR | EC_YBIT:
      gwant = EC_LSB; goto decompr;
    case EC_CMPR | EC_SORT: case EC_CMPR | EC_SORT | EC_YBIT:
      gwant = EC_SORT; goto decompr;
    default: goto done;
    decompr:
      if (!(f & gwant)) goto done;
      if (!ec_find(c, &t, x)) goto done;
      switch (gwant) {
	case EC_LSB:
	  if (!EC_COMPR(c, &t) != !(g & EC_YBIT)) ec_neg(c, &t, &t);
	  if (!EC_COMPR(c, &t) != !(g & EC_YBIT)) goto done;
	  break;
	case EC_SORT:
	  ec_neg(c, &tt, &t);
	  if (!MP_CMP(t.y, >, tt.y) != !(g & EC_YBIT)) {
	    if (MP_EQ(t.y, tt.y)) goto done;
	    MP_DROP(t.y); t.y = MP_COPY(tt.y);
	  }
	  break;
	case EC_XONLY:
	  break;
	default:
	  abort();
      }
  }

  /* --- If an explicit %$y$%-coordinate is specified, read it in --- */

  if (g & EC_EXPLY) {
    if (!(f & EC_EXPLY)) goto done;
    if ((q = buf_get(b, n)) == 0) goto done;
    y = mp_loadb(y, q, n);
    if (!t.y) t.y = MP_COPY(y);
    else if (!MP_EQ(y, t.y)) goto done;
  }

  /* --- We're ready --- */

  EC_COPY(d, &t);
  rc = 0;

  /* --- Clean up --- */

done:
  if (x) MP_DROP(x);
  if (y) MP_DROP(y);
  if (t.x) MP_DROP(t.x); if (t.y) MP_DROP(t.y);
  EC_DESTROY(&tt);
  return (rc);
}

/* --- @ec_putraw@ --- *
 *
 * Arguments:	@ec_curve *c@ = elliptic curve
 *		@buf *b@ = pointer to a buffer
 *		@const ec *p@ = an elliptic curve point
 *
 * Returns:	Zero on success, nonzero on failure.
 *
 * Use:		Puts an elliptic curve point to the given buffer using the
 *		standard uncompressed format described in P1363 and SEC1.
 *		This requires at most @1 + 2 * c->f->noctets@ space in the
 *		buffer.  We don't do point compression.
 */

int ec_putraw(ec_curve *c, buf *b, const ec *p)
  { return (ec_ec2osp(c, EC_EXPLY, b, p)); }

/* --- @ec_getraw@ --- *
 *
 * Arguments:	@ec_curve *c@ = elliptic curve
 *		@buf *b@ = pointer to a buffer
 *		@ec *d@ = an elliptic curve point
 *
 * Returns:	Zero on success, nonzero on failure.
 *
 * Use:		Reads an elliptic curve point from the given buffer using the
 *		standard uncompressed format described in P1363 and SEC1.
 *		We don't do point compression.
 */

int ec_getraw(ec_curve *c, buf *b, ec *d)
  { return (ec_os2ecp(c, EC_LSB | EC_SORT | EC_EXPLY, b, d)); }

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
0f3faccd	1	/* --c--
0f3faccd	2	*
0f3faccd	3	* Raw formatting of elliptic curve points
	4	*
	5	* (c) 2004 Straylight/Edgeware
	6	*/
	7
45c0fd36	8	/----- Licensing notice --------------------------------------------------
0f3faccd	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.
45c0fd36	16	*
0f3faccd	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.
45c0fd36	21	*
0f3faccd	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
0f3faccd	28	/----- Header files ------------------------------------------------------/
	29
	30	#include "ec.h"
	31	#include "ec-raw.h"
	32
	33	/----- Main code ---------------------------------------------------------/
	34
6775a491	35	/* --- @ec_ec2osp@ --- *
0f3faccd	36	*
0f3faccd	37	* Arguments: @ec_curve *c@ = elliptic curve
6775a491	38	* @unsigned f@ = format flags for output
0f3faccd	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
6775a491	45	* standard uncompressed format described in P1363 and SEC1.
0f3faccd	46	* This requires at most @1 + 2 * c->f->noctets@ space in the
6775a491 MW	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.
d5d30579 MW	57	*
	58	* Returns failure (@-1@) if the flags are invalid, or if there
	59	* isn't enough space in the output buffer.
0f3faccd	60	*/
0f3faccd	61
6775a491	62	int ec_ec2osp(ec_curve c, unsigned f, buf b, const ec *p)
0f3faccd	63	{
	64	octet *q;
	65	size_t n;
6775a491 MW	66	ec t = EC_INIT;
6775a491 MW	67
d5d30579 MW	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
6775a491	77	/* --- Point at infinity --- */
0f3faccd	78
0f3faccd	79	if (EC_ATINF(p)) return (buf_putbyte(b, 0));
6775a491 MW	80
	81	/* --- Fix up the format byte, compressing the %$y$%-coordinate --- */
	82
d5d30579	83	if (f & EC_CMPR) {
6775a491 MW	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
0f3faccd	99	n = c->f->noctets;
6775a491	100	if ((q = buf_get(b, n)) == 0) return (-1);
0f3faccd	101	mp_storeb(p->x, q, n);
6775a491 MW	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
0f3faccd	112	return (0);
	113	}
	114
6775a491	115	/* --- @ec_os2ecp@ --- *
0f3faccd	116	*
6775a491 MW	117	* Arguments: @ec_curve *c = elliptic curve
6775a491 MW	118	* @unsigned f@ = format flags for input
0f3faccd	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
6775a491 MW	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.
0f3faccd	138	*/
0f3faccd	139
6775a491	140	int ec_os2ecp(ec_curve c, unsigned f, buf b, ec *d)
0f3faccd	141	{
	142	const octet *q;
	143	size_t n;
6775a491 MW	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 --- */
0f3faccd	158
0f3faccd	159	n = c->f->noctets;
6775a491 MW	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);
0f3faccd	223	}
0f3faccd	224
6775a491 MW	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
0f3faccd	258	/----- That's all, folks -------------------------------------------------/