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

   1 /* -*-c-*-
   2  *
   3  * $Id: f-prime.c,v 1.6 2004/03/23 15:19:32 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.6  2004/03/23 15:19:32  mdw
  34  * Test elliptic curves more thoroughly.
  35  *
  36  * Revision 1.5  2004/03/23 12:08:26  mdw
  37  * Random field-element selection.
  38  *
  39  * Revision 1.4  2004/03/21 22:52:06  mdw
  40  * Merge and close elliptic curve branch.
  41  *
  42  * Revision 1.3.4.3  2004/03/21 22:39:46  mdw
  43  * Elliptic curves on binary fields work.
  44  *
  45  * Revision 1.3.4.2  2004/03/20 00:13:31  mdw
  46  * Projective coordinates for prime curves
  47  *
  48  * Revision 1.3.4.1  2003/06/10 13:43:53  mdw
  49  * Simple (non-projective) curves over prime fields now seem to work.
  50  *
  51  * Revision 1.3  2003/05/15 23:25:59  mdw
  52  * Make elliptic curve stuff build.
  53  *
  54  * Revision 1.2  2002/01/13 13:48:44  mdw
  55  * Further progress.
  56  *
  57  * Revision 1.1  2001/04/29 18:12:33  mdw
  58  * Prototype version.
  59  *
  60  */
  61
  62 /*----- Header files ------------------------------------------------------*/
  63
  64 #include <mLib/sub.h>
  65
  66 #include "field.h"
  67 #include "mpmont.h"
  68 #include "mprand.h"
  69
  70 /*----- Data structures ---------------------------------------------------*/
  71
  72 typedef struct fctx {
  73   field f;
  74   mpmont mm;
  75 } fctx;
  76
  77 /*----- Main code ---------------------------------------------------------*/
  78
  79 /* --- Field operations --- */
  80
  81 static void fdestroy(field *ff)
  82 {
  83   fctx *f = (fctx *)ff;
  84   mpmont_destroy(&f->mm);
  85   DESTROY(f);
  86 }
  87
  88 static mp *frand(field *ff, mp *d, grand *r)
  89 {
  90   fctx *f = (fctx *)ff;
  91   return (mprand_range(d, f->mm.m, r, 0));
  92 }
  93
  94 static mp *fin(field *ff, mp *d, mp *x)
  95 {
  96   fctx *f = (fctx *)ff;
  97   mp_div(0, &d, x, f->mm.m);
  98   return (mpmont_mul(&f->mm, d, d, f->mm.r2));
  99 }
 100
 101 static mp *fout(field *ff, mp *d, mp *x)
 102 {
 103   fctx *f = (fctx *)ff;
 104   return (mpmont_reduce(&f->mm, d, x));
 105 }
 106
 107 static int fzerop(field *ff, mp *x)
 108 {
 109   return (!MP_LEN(x));
 110 }
 111
 112 static mp *fneg(field *ff, mp *d, mp *x)
 113 {
 114   fctx *f = (fctx *)ff;
 115   return (mp_sub(d, f->mm.m, x));
 116 }
 117
 118 static mp *fadd(field *ff, mp *d, mp *x, mp *y)
 119 {
 120   fctx *f = (fctx *)ff;
 121   d = mp_add(d, x, y);
 122   if (d->f & MP_NEG)
 123     d = mp_add(d, d, f->mm.m);
 124   else if (MP_CMP(d, >, f->mm.m))
 125     d = mp_sub(d, d, f->mm.m);
 126   return (d);
 127 }
 128
 129 static mp *fsub(field *ff, mp *d, mp *x, mp *y)
 130 {
 131   fctx *f = (fctx *)ff;
 132   d = mp_sub(d, x, y);
 133   if (d->f & MP_NEG)
 134     d = mp_add(d, d, f->mm.m);
 135   else if (MP_CMP(d, >, f->mm.m))
 136     d = mp_sub(d, d, f->mm.m);
 137   return (d);
 138 }
 139
 140 static mp *fmul(field *ff, mp *d, mp *x, mp *y)
 141 {
 142   fctx *f = (fctx *)ff;
 143   return (mpmont_mul(&f->mm, d, x, y));
 144 }
 145
 146 static mp *fsqr(field *ff, mp *d, mp *x)
 147 {
 148   fctx *f = (fctx *)ff;
 149   d = mp_sqr(d, x);
 150   return (mpmont_reduce(&f->mm, d, d));
 151 }
 152
 153 static mp *finv(field *ff, mp *d, mp *x)
 154 {
 155   fctx *f = (fctx *)ff;
 156   d = mpmont_reduce(&f->mm, d, x);
 157   mp_gcd(0, 0, &d, f->mm.m, d);
 158   return (mpmont_mul(&f->mm, d, d, f->mm.r2));
 159 }
 160
 161 static mp *freduce(field *ff, mp *d, mp *x)
 162 {
 163   fctx *f = (fctx *)ff;
 164   mp_div(0, &d, x, f->mm.m);
 165   return (d);
 166 }
 167
 168 static mp *fsqrt(field *ff, mp *d, mp *x)
 169 {
 170   fctx *f = (fctx *)ff;
 171   d = mpmont_reduce(&f->mm, d, x);
 172   d = mp_modsqrt(d, d, f->mm.m);
 173   if (!d)
 174     return (d);
 175   return (mpmont_mul(&f->mm, d, d, f->mm.r2));
 176 }
 177
 178 static mp *fdbl(field *ff, mp *d, mp *x)
 179 {
 180   fctx *f = (fctx *)ff;
 181   d = mp_lsl(d, x, 1);
 182   if (MP_CMP(d, >, f->mm.m))
 183     d = mp_sub(d, d, f->mm.m);
 184   return (d);
 185 }
 186
 187 static mp *ftpl(field *ff, mp *d, mp *x)
 188 {
 189   fctx *f = (fctx *)ff;
 190   MP_DEST(d, MP_LEN(x) + 1, x->f);
 191   MPX_UMULN(d->v, d->vl, x->v, x->vl, 3);
 192   while (MP_CMP(d, >, f->mm.m))
 193     d = mp_sub(d, d, f->mm.m);
 194   return (d);
 195 }
 196
 197 static mp *fqdl(field *ff, mp *d, mp *x)
 198 {
 199   fctx *f = (fctx *)ff;
 200   d = mp_lsl(d, x, 2);
 201   while (MP_CMP(d, >, f->mm.m))
 202     d = mp_sub(d, d, f->mm.m);
 203   return (d);
 204 }
 205
 206 static mp *fhlv(field *ff, mp *d, mp *x)
 207 {
 208   fctx *f = (fctx *)ff;
 209   if (!MP_LEN(x)) {
 210     MP_COPY(x);
 211     MP_DROP(d);
 212     return (x);
 213   }
 214   if (x->v[0] & 1) {
 215     d = mp_add(d, x, f->mm.m);
 216     x = d;
 217   }
 218   return (mp_lsr(d, x, 1));
 219 }
 220
 221 /* --- Field operations table --- */
 222
 223 static field_ops fops = {
 224   FTY_PRIME, "prime",
 225   fdestroy, frand,
 226   fin, fout,
 227   fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
 228   0,
 229   fdbl, ftpl, fqdl, fhlv
 230 };
 231
 232 /* --- @field_prime@ --- *
 233  *
 234  * Arguments:   @mp *p@ = the characteristic of the field
 235  *
 236  * Returns:     A pointer to the field.
 237  *
 238  * Use:         Creates a field structure for a prime field of size %$p$%,
 239  *              using Montgomery reduction for arithmetic.
 240  */
 241
 242 field *field_prime(mp *p)
 243 {
 244   fctx *f = CREATE(fctx);
 245   f->f.ops = &fops;
 246   mpmont_create(&f->mm, p);
 247   f->f.zero = MP_ZERO;
 248   f->f.one = f->mm.r;
 249   return (&f->f);
 250 }
 251
 252 /*----- That's all, folks -------------------------------------------------*/