git.distorted.org.uk Git - u/mdw/catacomb/blob - f-prime.c

   1 /* -*-c-*-
   2  *
   3  * $Id: f-prime.c,v 1.7 2004/03/27 17:54:11 mdw Exp $
   4  *
   5  * Prime fields with Montgomery arithmetic
   6  *
   7  * (c) 2001 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: f-prime.c,v $
  33  * Revision 1.7  2004/03/27 17:54:11  mdw
  34  * Standard curves and curve checking.
  35  *
  36  * Revision 1.6  2004/03/23 15:19:32  mdw
  37  * Test elliptic curves more thoroughly.
  38  *
  39  * Revision 1.5  2004/03/23 12:08:26  mdw
  40  * Random field-element selection.
  41  *
  42  * Revision 1.4  2004/03/21 22:52:06  mdw
  43  * Merge and close elliptic curve branch.
  44  *
  45  * Revision 1.3.4.3  2004/03/21 22:39:46  mdw
  46  * Elliptic curves on binary fields work.
  47  *
  48  * Revision 1.3.4.2  2004/03/20 00:13:31  mdw
  49  * Projective coordinates for prime curves
  50  *
  51  * Revision 1.3.4.1  2003/06/10 13:43:53  mdw
  52  * Simple (non-projective) curves over prime fields now seem to work.
  53  *
  54  * Revision 1.3  2003/05/15 23:25:59  mdw
  55  * Make elliptic curve stuff build.
  56  *
  57  * Revision 1.2  2002/01/13 13:48:44  mdw
  58  * Further progress.
  59  *
  60  * Revision 1.1  2001/04/29 18:12:33  mdw
  61  * Prototype version.
  62  *
  63  */
  64
  65 /*----- Header files ------------------------------------------------------*/
  66
  67 #include <mLib/sub.h>
  68
  69 #include "field.h"
  70 #include "mpmont.h"
  71 #include "mprand.h"
  72
  73 /*----- Data structures ---------------------------------------------------*/
  74
  75 typedef struct fctx {
  76   field f;
  77   mpmont mm;
  78 } fctx;
  79
  80 /*----- Main code ---------------------------------------------------------*/
  81
  82 /* --- Field operations --- */
  83
  84 static void fdestroy(field *ff)
  85 {
  86   fctx *f = (fctx *)ff;
  87   mpmont_destroy(&f->mm);
  88   DESTROY(f);
  89 }
  90
  91 static mp *frand(field *ff, mp *d, grand *r)
  92 {
  93   fctx *f = (fctx *)ff;
  94   return (mprand_range(d, f->mm.m, r, 0));
  95 }
  96
  97 static mp *fin(field *ff, mp *d, mp *x)
  98 {
  99   fctx *f = (fctx *)ff;
 100   mp_div(0, &d, x, f->mm.m);
 101   return (mpmont_mul(&f->mm, d, d, f->mm.r2));
 102 }
 103
 104 static mp *fout(field *ff, mp *d, mp *x)
 105 {
 106   fctx *f = (fctx *)ff;
 107   return (mpmont_reduce(&f->mm, d, x));
 108 }
 109
 110 static int fzerop(field *ff, mp *x)
 111 {
 112   return (!MP_LEN(x));
 113 }
 114
 115 static mp *fneg(field *ff, mp *d, mp *x)
 116 {
 117   fctx *f = (fctx *)ff;
 118   return (mp_sub(d, f->mm.m, x));
 119 }
 120
 121 static mp *fadd(field *ff, mp *d, mp *x, mp *y)
 122 {
 123   fctx *f = (fctx *)ff;
 124   d = mp_add(d, x, y);
 125   if (d->f & MP_NEG)
 126     d = mp_add(d, d, f->mm.m);
 127   else if (MP_CMP(d, >, f->mm.m))
 128     d = mp_sub(d, d, f->mm.m);
 129   return (d);
 130 }
 131
 132 static mp *fsub(field *ff, mp *d, mp *x, mp *y)
 133 {
 134   fctx *f = (fctx *)ff;
 135   d = mp_sub(d, x, y);
 136   if (d->f & MP_NEG)
 137     d = mp_add(d, d, f->mm.m);
 138   else if (MP_CMP(d, >, f->mm.m))
 139     d = mp_sub(d, d, f->mm.m);
 140   return (d);
 141 }
 142
 143 static mp *fmul(field *ff, mp *d, mp *x, mp *y)
 144 {
 145   fctx *f = (fctx *)ff;
 146   return (mpmont_mul(&f->mm, d, x, y));
 147 }
 148
 149 static mp *fsqr(field *ff, mp *d, mp *x)
 150 {
 151   fctx *f = (fctx *)ff;
 152   d = mp_sqr(d, x);
 153   return (mpmont_reduce(&f->mm, d, d));
 154 }
 155
 156 static mp *finv(field *ff, mp *d, mp *x)
 157 {
 158   fctx *f = (fctx *)ff;
 159   d = mpmont_reduce(&f->mm, d, x);
 160   mp_gcd(0, 0, &d, f->mm.m, d);
 161   return (mpmont_mul(&f->mm, d, d, f->mm.r2));
 162 }
 163
 164 static mp *freduce(field *ff, mp *d, mp *x)
 165 {
 166   fctx *f = (fctx *)ff;
 167   mp_div(0, &d, x, f->mm.m);
 168   return (d);
 169 }
 170
 171 static mp *fsqrt(field *ff, mp *d, mp *x)
 172 {
 173   fctx *f = (fctx *)ff;
 174   d = mpmont_reduce(&f->mm, d, x);
 175   d = mp_modsqrt(d, d, f->mm.m);
 176   if (!d)
 177     return (d);
 178   return (mpmont_mul(&f->mm, d, d, f->mm.r2));
 179 }
 180
 181 static mp *fdbl(field *ff, mp *d, mp *x)
 182 {
 183   fctx *f = (fctx *)ff;
 184   d = mp_lsl(d, x, 1);
 185   if (MP_CMP(d, >, f->mm.m))
 186     d = mp_sub(d, d, f->mm.m);
 187   return (d);
 188 }
 189
 190 static mp *ftpl(field *ff, mp *d, mp *x)
 191 {
 192   fctx *f = (fctx *)ff;
 193   MP_DEST(d, MP_LEN(x) + 1, x->f);
 194   MPX_UMULN(d->v, d->vl, x->v, x->vl, 3);
 195   while (MP_CMP(d, >, f->mm.m))
 196     d = mp_sub(d, d, f->mm.m);
 197   return (d);
 198 }
 199
 200 static mp *fqdl(field *ff, mp *d, mp *x)
 201 {
 202   fctx *f = (fctx *)ff;
 203   d = mp_lsl(d, x, 2);
 204   while (MP_CMP(d, >, f->mm.m))
 205     d = mp_sub(d, d, f->mm.m);
 206   return (d);
 207 }
 208
 209 static mp *fhlv(field *ff, mp *d, mp *x)
 210 {
 211   fctx *f = (fctx *)ff;
 212   if (!MP_LEN(x)) {
 213     MP_COPY(x);
 214     MP_DROP(d);
 215     return (x);
 216   }
 217   if (x->v[0] & 1) {
 218     d = mp_add(d, x, f->mm.m);
 219     x = d;
 220   }
 221   return (mp_lsr(d, x, 1));
 222 }
 223
 224 /* --- Field operations table --- */
 225
 226 static field_ops fops = {
 227   FTY_PRIME, "prime",
 228   fdestroy, frand,
 229   fin, fout,
 230   fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
 231   0,
 232   fdbl, ftpl, fqdl, fhlv
 233 };
 234
 235 /* --- @field_prime@ --- *
 236  *
 237  * Arguments:   @mp *p@ = the characteristic of the field
 238  *
 239  * Returns:     A pointer to the field.
 240  *
 241  * Use:         Creates a field structure for a prime field of size %$p$%,
 242  *              using Montgomery reduction for arithmetic.
 243  */
 244
 245 field *field_prime(mp *p)
 246 {
 247   fctx *f = CREATE(fctx);
 248   f->f.ops = &fops;
 249   mpmont_create(&f->mm, p);
 250   f->f.zero = MP_ZERO;
 251   f->f.one = f->mm.r;
 252   f->f.m = f->mm.m;
 253   f->f.nbits = mp_bits(p);
 254   f->f.noctets = (f->f.nbits + 7) >> 3;
 255   return (&f->f);
 256 }
 257
 258 /*----- That's all, folks -------------------------------------------------*/