projects / u / mdw / catacomb / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Standard curves and curve checking.
[u/mdw/catacomb] / field.h
CommitLineData
b0ab12e6 1/* -*-c-*-
2 *
432c4e18 3 * $Id: field.h,v 1.8 2004/03/27 17:54:11 mdw Exp $
b0ab12e6 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 $
432c4e18 33 * Revision 1.8 2004/03/27 17:54:11 mdw
34 * Standard curves and curve checking.
35 *
f46efa79 36 * Revision 1.7 2004/03/27 00:04:46 mdw
37 * Implement efficient reduction for pleasant-looking primes.
38 *
bc985cef 39 * Revision 1.6 2004/03/23 15:19:32 mdw
40 * Test elliptic curves more thoroughly.
41 *
9b8b6877 42 * Revision 1.5 2004/03/23 12:08:26 mdw
43 * Random field-element selection.
44 *
c3caa2fa 45 * Revision 1.4 2004/03/21 22:52:06 mdw
46 * Merge and close elliptic curve branch.
47 *
ceb3f0c0 48 * Revision 1.3.4.2 2004/03/21 22:39:46 mdw
49 * Elliptic curves on binary fields work.
50 *
8823192f 51 * Revision 1.3.4.1 2004/03/20 00:13:31 mdw
52 * Projective coordinates for prime curves
53 *
b085fd91 54 * Revision 1.3 2002/01/13 13:48:44 mdw
55 * Further progress.
56 *
2685767a 57 * Revision 1.2 2001/05/07 17:30:13 mdw
58 * Add an internal-representation no-op function.
59 *
b0ab12e6 60 * Revision 1.1 2001/04/29 18:12:33 mdw
61 * Prototype version.
62 *
63 */
64
65#ifndef CATACOMB_FIELD_H
66#define CATACOMB_FIELD_H
67
68#ifdef __cplusplus
69 extern "C" {
70#endif
71
72/*----- Header files ------------------------------------------------------*/
73
9b8b6877 74#ifndef CATACOMB_GRAND_H
75# include "grand.h"
76#endif
77
b0ab12e6 78#ifndef CATACOMB_MP_H
79# include "mp.h"
80#endif
81
432c4e18 82#ifndef CATACOMB_QDPARSE_H
83# include "qdparse.h"
84#endif
85
b0ab12e6 86/*----- Data structures ---------------------------------------------------*/
87
88typedef struct field {
89 const struct field_ops *ops; /* Field operations */
90 mp *zero, *one; /* Identities in the field */
432c4e18 91 mp *m; /* Modulus (prime and binary) */
92 unsigned long nbits; /* Length of field element in bits */
93 size_t noctets; /* Length of element in octets */
b0ab12e6 94} field;
95
bc985cef 96enum {
97 FTY_PRIME,
98 FTY_BINARY
99};
100
b0ab12e6 101typedef struct field_ops {
102
bc985cef 103 /* --- General information --- */
104
105 unsigned ty; /* What kind of field this is */
106 const char *name; /* Human-readable name string */
107
b0ab12e6 108 /* --- Universal operations --- */
109
110 void (*destroy)(field */*f*/);
9b8b6877 111 mp *(*rand)(field */*f*/, mp */*d*/, grand */*r*/);
b0ab12e6 112
113 mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/);
114 mp *(*out)(field */*f*/, mp */*d*/, mp */*x*/);
115
8823192f 116 int (*zerop)(field */*f*/, mp */*x*/);
b085fd91 117 mp *(*neg)(field */*f*/, mp */*d*/, mp */*x*/);
b0ab12e6 118 mp *(*add)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
119 mp *(*sub)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
120 mp *(*mul)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
121 mp *(*sqr)(field */*f*/, mp */*d*/, mp */*x*/);
122 mp *(*inv)(field */*f*/, mp */*d*/, mp */*x*/);
123 mp *(*reduce)(field */*f*/, mp */*d*/, mp */*x*/);
ceb3f0c0 124 mp *(*sqrt)(field */*f*/, mp */*d*/, mp */*x*/);
125
126 /* --- Operations for binary fields only --- */
127
128 mp *(*quadsolve)(field */*f*/, mp */*d*/, mp */*x*/);
b0ab12e6 129
130 /* --- Operations for prime fields only --- */
131
132 mp *(*dbl)(field */*f*/, mp */*d*/, mp */*x*/);
133 mp *(*tpl)(field */*f*/, mp */*d*/, mp */*x*/);
8823192f 134 mp *(*qdl)(field */*f*/, mp */*d*/, mp */*x*/);
135 mp *(*hlv)(field */*f*/, mp */*d*/, mp */*x*/);
b0ab12e6 136
137} field_ops;
138
bc985cef 139#define F_TYPE(f) (f)->ops->ty
140#define F_NAME(f) (f)->ops->name
141
b0ab12e6 142#define F_DESTROY(f) (f)->ops->destroy((f))
bc985cef 143#define F_RAND(f, d, r) (f)->ops->rand((f), (d), (r))
b0ab12e6 144
145#define F_IN(f, d, x) (f)->ops->in((f), (d), (x))
146#define F_OUT(f, d, x) (f)->ops->out((f), (d), (x))
8823192f 147
148#define F_ZEROP(f, x) (f)->ops->zerop((f), (x))
b085fd91 149#define F_NEG(f, d, x) (f)->ops->neg((f), (d), (x))
b0ab12e6 150#define F_ADD(f, d, x, y) (f)->ops->add((f), (d), (x), (y))
151#define F_SUB(f, d, x, y) (f)->ops->sub((f), (d), (x), (y))
152#define F_MUL(f, d, x, y) (f)->ops->mul((f), (d), (x), (y))
153#define F_SQR(f, d, x) (f)->ops->sqr((f), (d), (x))
154#define F_INV(f, d, x) (f)->ops->inv((f), (d), (x))
155#define F_REDUCE(f, d, x) (f)->ops->reduce((f), (d), (x))
ceb3f0c0 156#define F_SQRT(f, d, x) (f)->ops->sqrt((f), (d), (x))
157
158#define F_QUADSOLVE(f, d, x) (f)->ops->quadsolve((f), (d), (x))
b0ab12e6 159
160#define F_DBL(f, d, x) (f)->ops->dbl((f), (d), (x))
161#define F_TPL(f, d, x) (f)->ops->tpl((f), (d), (x))
8823192f 162#define F_QDL(f, d, x) (f)->ops->qdl((f), (d), (x))
163#define F_HLV(f, d, x) (f)->ops->hlv((f), (d), (x))
b0ab12e6 164
2685767a 165/*----- Helpful field operations ------------------------------------------*/
166
167/* --- @field_id@ --- *
168 *
169 * Arguments: @field *f@ = pointer to a field
170 * @mp *d@ = a destination element
171 * @mp *x@ = a source element
172 *
173 * Returns: The result element.
174 *
175 * Use: An identity operation which can be used if your field has no
176 * internal representation.
177 */
178
179extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/);
180
b0ab12e6 181/*----- Creating fields ---------------------------------------------------*/
182
183/* --- @field_prime@ --- *
184 *
185 * Arguments: @mp *p@ = the characteristic of the field
186 *
187 * Returns: A pointer to the field.
188 *
189 * Use: Creates a field structure for a prime field of size %$p$%,
190 * using Montgomery reduction for arithmetic.
191 */
192
193extern field *field_prime(mp */*p*/);
194
f46efa79 195/* --- @field_niceprime@ --- *
196 *
197 * Arguments: @mp *p@ = the characteristic of the field
198 *
199 * Returns: A pointer to the field.
200 *
201 * Use: Creates a field structure for a prime field of size %$p$%,
202 * using efficient reduction for nice primes.
203 */
204
205extern field *field_niceprime(mp */*p*/);
206
b0ab12e6 207/* --- @field_binpoly@ --- *
208 *
209 * Arguments: @mp *p@ = an irreducible polynomial over %$\gf{2}$%
210 *
211 * Returns: A pointer to the field.
212 *
213 * Use: Creates a field structure for a binary field using naive
214 * arithmetic.
215 */
216
217extern field *field_binpoly(mp */*p*/);
218
432c4e18 219/* --- @field_parse@ --- *
220 *
221 * Arguments: @qd_parse *qd@ = parser context
222 *
223 * Returns: Field pointer if OK, or null.
224 *
225 * Use: Parses a field description, which has the form
226 *
227 * * `prime', `niceprime' or `binpoly'
228 * * an optional `:'
229 * * the field modulus
230 */
231
232extern field *field_parse(qd_parse */*qd*/);
233
b0ab12e6 234/*----- That's all, folks -------------------------------------------------*/
235
236#ifdef __cplusplus
237 }
238#endif
239
240#endif
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)