projects / u / mdw / catacomb / blob
? search:


3a46ac97f4846582c333ce34f249c6932e062c91
[u/mdw/catacomb] / field.h
1 /* -*-c-*-
2 *
3 * $Id: field.h,v 1.10 2004/04/01 21:28:41 mdw Exp $
4 *
5 * Definitions for field arithmetic
6 *
7 * (c) 2000 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: field.h,v $
33 * Revision 1.10 2004/04/01 21:28:41 mdw
34 * Normal basis support (translates to poly basis internally). Rewrite
35 * EC and prime group table generators in awk, so that they can reuse data
36 * for repeated constants.
37 *
38 * Revision 1.9 2004/04/01 12:50:09 mdw
39 * Add cyclic group abstraction, with test code. Separate off exponentation
40 * functions for better static linking. Fix a buttload of bugs on the way.
41 * Generally ensure that negative exponents do inversion correctly. Add
42 * table of standard prime-field subgroups. (Binary field subgroups are
43 * currently unimplemented but easy to add if anyone ever finds a good one.)
44 *
45 * Revision 1.8 2004/03/27 17:54:11 mdw
46 * Standard curves and curve checking.
47 *
48 * Revision 1.7 2004/03/27 00:04:46 mdw
49 * Implement efficient reduction for pleasant-looking primes.
50 *
51 * Revision 1.6 2004/03/23 15:19:32 mdw
52 * Test elliptic curves more thoroughly.
53 *
54 * Revision 1.5 2004/03/23 12:08:26 mdw
55 * Random field-element selection.
56 *
57 * Revision 1.4 2004/03/21 22:52:06 mdw
58 * Merge and close elliptic curve branch.
59 *
60 * Revision 1.3.4.2 2004/03/21 22:39:46 mdw
61 * Elliptic curves on binary fields work.
62 *
63 * Revision 1.3.4.1 2004/03/20 00:13:31 mdw
64 * Projective coordinates for prime curves
65 *
66 * Revision 1.3 2002/01/13 13:48:44 mdw
67 * Further progress.
68 *
69 * Revision 1.2 2001/05/07 17:30:13 mdw
70 * Add an internal-representation no-op function.
71 *
72 * Revision 1.1 2001/04/29 18:12:33 mdw
73 * Prototype version.
74 *
75 */
76
77 #ifndef CATACOMB_FIELD_H
78 #define CATACOMB_FIELD_H
79
80 #ifdef __cplusplus
81 extern "C" {
82 #endif
83
84 /*----- Header files ------------------------------------------------------*/
85
86 #ifndef CATACOMB_GRAND_H
87 # include "grand.h"
88 #endif
89
90 #ifndef CATACOMB_MP_H
91 # include "mp.h"
92 #endif
93
94 #ifndef CATACOMB_QDPARSE_H
95 # include "qdparse.h"
96 #endif
97
98 /*----- Data structures ---------------------------------------------------*/
99
100 typedef struct field {
101 const struct field_ops *ops; /* Field operations */
102 mp *zero, *one; /* Identities in the field */
103 mp *m; /* Modulus (prime and binary) */
104 unsigned long nbits; /* Length of field element in bits */
105 size_t noctets; /* Length of element in octets */
106 } field;
107
108 enum {
109 FTY_PRIME,
110 FTY_BINARY
111 };
112
113 typedef struct field_ops {
114
115 /* --- General information --- */
116
117 unsigned ty; /* What kind of field this is */
118 const char *name; /* Human-readable name string */
119
120 /* --- Universal operations --- */
121
122 void (*destroy)(field */*f*/);
123 mp *(*rand)(field */*f*/, mp */*d*/, grand */*r*/);
124 int (*samep)(field */*f*/, field */*g*/);
125
126 mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/);
127 mp *(*out)(field */*f*/, mp */*d*/, mp */*x*/);
128
129 int (*zerop)(field */*f*/, mp */*x*/);
130 mp *(*neg)(field */*f*/, mp */*d*/, mp */*x*/);
131 mp *(*add)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
132 mp *(*sub)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
133 mp *(*mul)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
134 mp *(*sqr)(field */*f*/, mp */*d*/, mp */*x*/);
135 mp *(*inv)(field */*f*/, mp */*d*/, mp */*x*/);
136 mp *(*reduce)(field */*f*/, mp */*d*/, mp */*x*/);
137 mp *(*sqrt)(field */*f*/, mp */*d*/, mp */*x*/);
138
139 /* --- Operations for binary fields only --- */
140
141 mp *(*quadsolve)(field */*f*/, mp */*d*/, mp */*x*/);
142
143 /* --- Operations for prime fields only --- */
144
145 mp *(*dbl)(field */*f*/, mp */*d*/, mp */*x*/);
146 mp *(*tpl)(field */*f*/, mp */*d*/, mp */*x*/);
147 mp *(*qdl)(field */*f*/, mp */*d*/, mp */*x*/);
148 mp *(*hlv)(field */*f*/, mp */*d*/, mp */*x*/);
149
150 } field_ops;
151
152 #define F_TYPE(f) (f)->ops->ty
153 #define F_NAME(f) (f)->ops->name
154
155 #define F_DESTROY(f) (f)->ops->destroy((f))
156 #define F_RAND(f, d, r) (f)->ops->rand((f), (d), (r))
157 #define F_SAMEP(f, g) (f)->ops->samep((f), (g))
158
159 #define F_IN(f, d, x) (f)->ops->in((f), (d), (x))
160 #define F_OUT(f, d, x) (f)->ops->out((f), (d), (x))
161
162 #define F_ZEROP(f, x) (f)->ops->zerop((f), (x))
163 #define F_NEG(f, d, x) (f)->ops->neg((f), (d), (x))
164 #define F_ADD(f, d, x, y) (f)->ops->add((f), (d), (x), (y))
165 #define F_SUB(f, d, x, y) (f)->ops->sub((f), (d), (x), (y))
166 #define F_MUL(f, d, x, y) (f)->ops->mul((f), (d), (x), (y))
167 #define F_SQR(f, d, x) (f)->ops->sqr((f), (d), (x))
168 #define F_INV(f, d, x) (f)->ops->inv((f), (d), (x))
169 #define F_REDUCE(f, d, x) (f)->ops->reduce((f), (d), (x))
170 #define F_SQRT(f, d, x) (f)->ops->sqrt((f), (d), (x))
171
172 #define F_QUADSOLVE(f, d, x) (f)->ops->quadsolve((f), (d), (x))
173
174 #define F_DBL(f, d, x) (f)->ops->dbl((f), (d), (x))
175 #define F_TPL(f, d, x) (f)->ops->tpl((f), (d), (x))
176 #define F_QDL(f, d, x) (f)->ops->qdl((f), (d), (x))
177 #define F_HLV(f, d, x) (f)->ops->hlv((f), (d), (x))
178
179 /*----- Helpful field operations ------------------------------------------*/
180
181 /* --- @field_id@ --- *
182 *
183 * Arguments: @field *f@ = pointer to a field
184 * @mp *d@ = a destination element
185 * @mp *x@ = a source element
186 *
187 * Returns: The result element.
188 *
189 * Use: An identity operation which can be used if your field has no
190 * internal representation.
191 */
192
193 extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/);
194
195 /* --- @field_samep@ --- *
196 *
197 * Arguments: @field *f, *g@ = two fields
198 *
199 * Returns: Nonzero if the fields are identical (not just isomorphic).
200 *
201 * Use: Checks for sameness of fields. This function does the full
202 * check, not just the field-type-specific check done by the
203 * @sampep@ field operation.
204 */
205
206 extern int field_samep(field */*f*/, field */*g*/);
207
208 /* --- @field_stdsamep@ --- *
209 *
210 * Arguments: @field *f, *g@ = two fields
211 *
212 * Returns: Nonzero if the fields are identical (not just isomorphic).
213 *
214 * Use: Standard sameness check, based on equality of the @m@
215 * member.
216 */
217
218 extern int field_stdsamep(field */*f*/, field */*g*/);
219
220 /*----- Creating fields ---------------------------------------------------*/
221
222 /* --- @field_prime@ --- *
223 *
224 * Arguments: @mp *p@ = the characteristic of the field
225 *
226 * Returns: A pointer to the field.
227 *
228 * Use: Creates a field structure for a prime field of size %$p$%,
229 * using Montgomery reduction for arithmetic.
230 */
231
232 extern field *field_prime(mp */*p*/);
233
234 /* --- @field_niceprime@ --- *
235 *
236 * Arguments: @mp *p@ = the characteristic of the field
237 *
238 * Returns: A pointer to the field.
239 *
240 * Use: Creates a field structure for a prime field of size %$p$%,
241 * using efficient reduction for nice primes.
242 */
243
244 extern field *field_niceprime(mp */*p*/);
245
246 /* --- @field_binpoly@ --- *
247 *
248 * Arguments: @mp *p@ = an irreducible polynomial over %$\gf{2}$%
249 *
250 * Returns: A pointer to the field.
251 *
252 * Use: Creates a field structure for a binary field using naive
253 * arithmetic.
254 */
255
256 extern field *field_binpoly(mp */*p*/);
257
258 /* --- @field_binnorm@ --- *
259 *
260 * Arguments: @mp *p@ = the reduction polynomial
261 * @mp *beta@ = representation of normal point
262 *
263 * Returns: A pointer to the field.
264 *
265 * Use: Creates a field structure for a binary field mod @p@ which
266 * uses a normal basis representation externally. Computations
267 * are still done on a polynomial-basis representation.
268 */
269
270 extern field *field_binnorm(mp */*p*/, mp */*beta*/);
271
272 /* --- @field_parse@ --- *
273 *
274 * Arguments: @qd_parse *qd@ = parser context
275 *
276 * Returns: Field pointer if OK, or null.
277 *
278 * Use: Parses a field description, which has the form
279 *
280 * * `prime', `niceprime', `binpoly', or `binnorm'
281 * * an optional `:'
282 * * the field modulus
283 * * for `binnorm', an optional `,' and the beta value
284 */
285
286 extern field *field_parse(qd_parse */*qd*/);
287
288 /*----- That's all, folks -------------------------------------------------*/
289
290 #ifdef __cplusplus
291 }
292 #endif
293
294 #endif
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)