3 * $Id: ec-prime.c,v 1.3 2003/05/15 23:25:59 mdw Exp $
5 * Elliptic curves over prime fields
7 * (c) 2001 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
32 * $Log: ec-prime.c,v $
33 * Revision 1.3 2003/05/15 23:25:59 mdw
34 * Make elliptic curve stuff build.
36 * Revision 1.2 2002/01/13 13:48:44 mdw
39 * Revision 1.1 2001/04/29 18:12:33 mdw
44 /*----- Header files ------------------------------------------------------*/
50 /*----- Data structures ---------------------------------------------------*/
52 typedef struct ecctx
{
57 /*----- Main code ---------------------------------------------------------*/
59 static const ec_ops ec_primeops
;
61 static ec
*ecneg(ec_curve
*c
, ec
*d
, const ec
*p
)
64 d
->y
= F_NEG(c
->f
, d
->y
, d
->y
);
68 static ec
*ecdbl(ec_curve
*c
, ec
*d
, const ec
*a
)
72 else if (!MP_LEN(a
->y
))
76 ecctx
*cc
= (ecctx
*)c
;
80 dx
= F_SQR(f
, MP_NEW
, a
->x
);
81 dy
= F_DBL(f
, MP_NEW
, a
->y
);
82 dx
= F_TPL(f
, dx
, dx
);
83 dx
= F_ADD(f
, dx
, dx
, cc
->a
);
84 dy
= F_INV(f
, dy
, dy
);
85 lambda
= F_MUL(f
, MP_NEW
, dx
, dy
);
87 dx
= F_SQR(f
, dx
, lambda
);
88 dy
= F_DBL(f
, dy
, a
->x
);
89 dx
= F_SUB(f
, dx
, dx
, dy
);
90 dy
= F_SUB(f
, dy
, a
->x
, dx
);
91 dy
= F_MUL(f
, dy
, lambda
, dy
);
92 dy
= F_SUB(f
, dy
, dy
, a
->y
);
103 static ec
*ecadd(ec_curve
*c
, ec
*d
, const ec
*a
, const ec
*b
)
107 else if (EC_ATINF(a
))
109 else if (EC_ATINF(b
))
116 if (!MP_EQ(a
->x
, b
->x
)) {
117 dy
= F_SUB(f
, MP_NEW
, a
->y
, b
->y
);
118 dx
= F_SUB(f
, MP_NEW
, a
->x
, b
->x
);
119 dx
= F_INV(f
, dx
, dx
);
120 lambda
= F_MUL(f
, MP_NEW
, dy
, dx
);
121 } else if (!MP_LEN(a
->y
) || !MP_EQ(a
->y
, b
->y
)) {
125 ecctx
*cc
= (ecctx
*)c
;
126 dx
= F_SQR(f
, MP_NEW
, a
->x
);
127 dx
= F_TPL(f
, dx
, dx
);
128 dx
= F_ADD(f
, dx
, dx
, cc
->a
);
129 dy
= F_DBL(f
, MP_NEW
, a
->y
);
130 dy
= F_INV(f
, dy
, dy
);
131 lambda
= F_MUL(f
, MP_NEW
, dx
, dy
);
134 dx
= F_SQR(f
, dx
, lambda
);
135 dx
= F_SUB(f
, dx
, dx
, a
->x
);
136 dx
= F_SUB(f
, dx
, dx
, b
->x
);
137 dy
= F_SUB(f
, dy
, b
->x
, dx
);
138 dy
= F_MUL(f
, dy
, lambda
, dy
);
139 dy
= F_SUB(f
, dy
, dy
, b
->y
);
150 static void ecdestroy(ec_curve
*c
)
152 ecctx
*cc
= (ecctx
*)c
;
158 /* --- @ec_prime@, @ec_primeproj@ --- *
160 * Arguments: @field *f@ = the underyling field for this elliptic curve
161 * @mp *a, *b@ = the coefficients for this curve
163 * Returns: A pointer to the curve.
165 * Use: Creates a curve structure for an elliptic curve defined over
166 * a prime field. The @primeproj@ variant uses projective
167 * coordinates, which can be a win.
170 extern ec_curve
*ec_prime(field
*f
, mp
*a
, mp
*b
)
172 ecctx
*cc
= CREATE(ecctx
);
173 cc
->c
.ops
= &ec_primeops
;
180 static const ec_ops ec_primeops
= {
181 ecdestroy
, ec_idin
, ec_idout
, 0, ecneg
, ecadd
, ec_stdsub
, ecdbl
184 /*----- Test rig ----------------------------------------------------------*/
188 #define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
194 ec g
= EC_INIT
, d
= EC_INIT
;
198 b
= MP(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1);
199 p
= MP(6277101735386680763835789423207666416083908700390324961279);
200 r
= MP(6277101735386680763835789423176059013767194773182842284081);
203 c
= ec_prime(f
, a
, b
);
205 g
.x
= MP(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012);
206 g
.y
= MP(0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811);
208 ec_mul(c
, &d
, &g
, r
);
209 MP_PRINT("d.x", d
.x
);
210 MP_PRINT("d.y", d
.y
);
222 /*----- That's all, folks -------------------------------------------------*/