1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
/* Uses Montgomery reduction for field arithmetic. See mpi/mpmontg.c for
* code implementation. */
#include "mpi.h"
#include "mplogic.h"
#include "mpi-priv.h"
#include "ecl-priv.h"
#include "ecp.h"
#include <stdlib.h>
#include <stdio.h>
/* Construct a generic GFMethod for arithmetic over prime fields with
* irreducible irr. */
GFMethod *
GFMethod_consGFp_mont(const mp_int *irr)
{
mp_err res = MP_OKAY;
GFMethod *meth = NULL;
mp_mont_modulus *mmm;
meth = GFMethod_consGFp(irr);
if (meth == NULL)
return NULL;
mmm = (mp_mont_modulus *)malloc(sizeof(mp_mont_modulus));
if (mmm == NULL) {
res = MP_MEM;
goto CLEANUP;
}
meth->field_mul = &ec_GFp_mul_mont;
meth->field_sqr = &ec_GFp_sqr_mont;
meth->field_div = &ec_GFp_div_mont;
meth->field_enc = &ec_GFp_enc_mont;
meth->field_dec = &ec_GFp_dec_mont;
meth->extra1 = mmm;
meth->extra2 = NULL;
meth->extra_free = &ec_GFp_extra_free_mont;
mmm->N = meth->irr;
mmm->n0prime = 0 - s_mp_invmod_radix(MP_DIGIT(&meth->irr, 0));
CLEANUP:
if (res != MP_OKAY) {
GFMethod_free(meth);
return NULL;
}
return meth;
}
/* Wrapper functions for generic prime field arithmetic. */
/* Field multiplication using Montgomery reduction. */
mp_err
ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,
const GFMethod *meth)
{
mp_err res = MP_OKAY;
#ifdef MP_MONT_USE_MP_MUL
/* if MP_MONT_USE_MP_MUL is defined, then the function s_mp_mul_mont
* is not implemented and we have to use mp_mul and s_mp_redc directly
*/
MP_CHECKOK(mp_mul(a, b, r));
MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *)meth->extra1));
#else
mp_int s;
MP_DIGITS(&s) = 0;
/* s_mp_mul_mont doesn't allow source and destination to be the same */
if ((a == r) || (b == r)) {
MP_CHECKOK(mp_init(&s));
MP_CHECKOK(s_mp_mul_mont(a, b, &s, (mp_mont_modulus *)meth->extra1));
MP_CHECKOK(mp_copy(&s, r));
mp_clear(&s);
} else {
return s_mp_mul_mont(a, b, r, (mp_mont_modulus *)meth->extra1);
}
#endif
CLEANUP:
return res;
}
/* Field squaring using Montgomery reduction. */
mp_err
ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
{
return ec_GFp_mul_mont(a, a, r, meth);
}
/* Field division using Montgomery reduction. */
mp_err
ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,
const GFMethod *meth)
{
mp_err res = MP_OKAY;
/* if A=aZ represents a encoded in montgomery coordinates with Z and #
* and \ respectively represent multiplication and division in
* montgomery coordinates, then A\B = (a/b)Z = (A/B)Z and Binv =
* (1/b)Z = (1/B)(Z^2) where B # Binv = Z */
MP_CHECKOK(ec_GFp_div(a, b, r, meth));
MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
if (a == NULL) {
MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
}
CLEANUP:
return res;
}
/* Encode a field element in Montgomery form. See s_mp_to_mont in
* mpi/mpmontg.c */
mp_err
ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
{
mp_mont_modulus *mmm;
mp_err res = MP_OKAY;
mmm = (mp_mont_modulus *)meth->extra1;
MP_CHECKOK(mp_copy(a, r));
MP_CHECKOK(s_mp_lshd(r, MP_USED(&mmm->N)));
MP_CHECKOK(mp_mod(r, &mmm->N, r));
CLEANUP:
return res;
}
/* Decode a field element from Montgomery form. */
mp_err
ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
{
mp_err res = MP_OKAY;
if (a != r) {
MP_CHECKOK(mp_copy(a, r));
}
MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *)meth->extra1));
CLEANUP:
return res;
}
/* Free the memory allocated to the extra fields of Montgomery GFMethod
* object. */
void
ec_GFp_extra_free_mont(GFMethod *meth)
{
if (meth->extra1 != NULL) {
free(meth->extra1);
meth->extra1 = NULL;
}
}
|
