chiark - git - mdw - catacomb/blob - calc/ecp.cal

   1 /* -*-apcalc-*-
   2  *
   3  * Testbed for elliptic curve arithmetic over prime fields
   4  *
   5  * (c) 2000 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 /*----- Object types ------------------------------------------------------*/
  29
  30 obj ecp_curve { a, b, p };
  31 obj ecp_pt { x, y, e };
  32
  33 /*----- Main code ---------------------------------------------------------*/
  34
  35 define ecp_curve(a, b, p)
  36 {
  37   local obj ecp_curve e;
  38   e.a = a;
  39   e.b = b;
  40   e.p = p;
  41   return (e);
  42 }
  43
  44 define ecp_pt(x, y, e)
  45 {
  46   local obj ecp_pt p;
  47   p.x = x % e.p;
  48   p.y = y % e.p;
  49   p.e = e;
  50   return (p);
  51 }
  52
  53 define ecp_pt_print(a)
  54 {
  55   print "(" : a.x : ", " : a.y : ")" :;
  56 }
  57
  58 define ecp_pt_add(a, b)
  59 {
  60   local e, alpha;
  61   local obj ecp_pt d;
  62
  63   if (a == 0)
  64     d = b;
  65   else if (b == 0)
  66     d = a;
  67   else if (!istype(a, b))
  68     quit "bad type arguments to ecp_pt_add";
  69   else if (a.e != b.e)
  70     quit "points from different curves in ecp_pt_add";
  71   else {
  72     e = a.e;
  73     if (a.x == b.x) {
  74       if (a.y != b.y) {
  75         return (0);
  76       }
  77       alpha = (3 * a.x^2 + e.a) * minv(2 * a.y, e.p) % e.p;
  78     } else
  79       alpha = (b.y - a.y) * minv(b.x - a.x, e.p) % e.p;
  80
  81     d.x = (alpha^2 - a.x - b.x) % e.p;
  82     d.y = (-a.y + alpha * (a.x - d.x)) % e.p;
  83     d.e = e;
  84   }
  85
  86   return (d);
  87 }
  88
  89 define ecp_pt_dbl(a)
  90 {
  91   local e, alpha;
  92   local obj ecp_pt d;
  93   if (istype(a, 1))
  94     return (0);
  95   e = a.e;
  96   alpha = (3 * a.x^2 + e.a) * minv(2 * a.y, e.p) % e.p;
  97   d.x = (alpha^2 - 2 * a.x) % e.p;
  98   d.y = (-a.y + alpha * (a.x - d.x)) % e.p;
  99   d.e = e;
 100   return (d);
 101 }
 102
 103 define ecp_pt_neg(a)
 104 {
 105   local obj ecp_pt d;
 106   d.x = a.x;
 107   d.y = a.e.p - a.y;
 108   d.e = a.e;
 109   return (d);
 110 }
 111
 112 define ecp_pt_check(a)
 113 {
 114   local e;
 115
 116   e = a.e;
 117   if (a.y^2 % e.p != (a.x^3 + e.a * a.x + e.b) % e.p)
 118     quit "bad curve point";
 119 }
 120
 121 define ecp_pt_mul(a, b)
 122 {
 123   local p, n;
 124   local d;
 125
 126   if (istype(a, 1)) {
 127     n = a;
 128     p = b;
 129   } else if (istype(b, 1)) {
 130     n = b;
 131     p = a;
 132   } else
 133     return (newerror("bad arguments to ecp_pt_mul"));
 134
 135   d = 0;
 136   while (n) {
 137     if (n & 1)
 138       d += p;
 139     n >>= 1;
 140     p = ecp_pt_dbl(p);
 141   }
 142   return (d);
 143 }
 144
 145 /*----- FIPS186-2 standard curves -----------------------------------------*/
 146
 147 p192 = ecp_curve(-3, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
 148                  6277101735386680763835789423207666416083908700390324961279);
 149 p192_r = 6277101735386680763835789423176059013767194773182842284081;
 150 p192_g = ecp_pt(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
 151                 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811, p192);
 152
 153 /*----- That's all, folks -------------------------------------------------*/