1
2 /***************************************************************************
3 *
4 Copyright 2012 CertiVox IOM Ltd. *
5 *
6 This file is part of CertiVox MIRACL Crypto SDK. *
7 *
8 The CertiVox MIRACL Crypto SDK provides developers with an *
9 extensive and efficient set of cryptographic functions. *
10 For further information about its features and functionalities please *
11 refer to http://www.certivox.com *
12 *
13 * The CertiVox MIRACL Crypto SDK is free software: you can *
14 redistribute it and/or modify it under the terms of the *
15 GNU Affero General Public License as published by the *
16 Free Software Foundation, either version 3 of the License, *
17 or (at your option) any later version. *
18 *
19 * The CertiVox MIRACL Crypto SDK is distributed in the hope *
20 that it will be useful, but WITHOUT ANY WARRANTY; without even the *
21 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *
22 See the GNU Affero General Public License for more details. *
23 *
24 * You should have received a copy of the GNU Affero General Public *
25 License along with CertiVox MIRACL Crypto SDK. *
26 If not, see <http://www.gnu.org/licenses/>. *
27 *
28 You can be released from the requirements of the license by purchasing *
29 a commercial license. Buying such a license is mandatory as soon as you *
30 develop commercial activities involving the CertiVox MIRACL Crypto SDK *
31 without disclosing the source code of your own applications, or shipping *
32 the CertiVox MIRACL Crypto SDK with a closed source product. *
33 *
34 ***************************************************************************/
35 /*
36 * Module to implement Comb method for fast
37 * computation of x*G mod n, for fixed G and n, using precomputation.
38 *
39 * Elliptic curve version of mrbrick.c
40 *
41 * This idea can be used to substantially speed up certain phases
42 * of the Digital Signature Standard (ECS) for example.
43 *
44 * See "Handbook of Applied Cryptography"
45 */
46
47 #include <stdlib.h>
48 #include "miracl.h"
49 #ifdef MR_STATIC
50 #include <string.h>
51 #endif
52
53 #ifndef MR_STATIC
54
ebrick_init(_MIPD_ ebrick * B,big x,big y,big a,big b,big n,int window,int nb)55 BOOL ebrick_init(_MIPD_ ebrick *B,big x,big y,big a,big b,big n,int window,int nb)
56 { /* Uses Montgomery arithmetic internally *
57 * (x,y) is the fixed base *
58 * a,b and n are parameters and modulus of the curve *
59 * window is the window size in bits and *
60 * nb is the maximum number of bits in the multiplier */
61 int i,j,k,t,bp,len,bptr,is;
62 epoint **table;
63 epoint *w;
64
65 #ifdef MR_OS_THREADS
66 miracl *mr_mip=get_mip();
67 #endif
68 if (nb<2 || window<1 || window>nb || mr_mip->ERNUM) return FALSE;
69
70 t=MR_ROUNDUP(nb,window);
71 if (t<2) return FALSE;
72
73 MR_IN(115)
74
75 #ifndef MR_ALWAYS_BINARY
76 if (mr_mip->base != mr_mip->base2)
77 {
78 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
79 MR_OUT
80 return FALSE;
81 }
82 #endif
83
84 B->window=window;
85 B->max=nb;
86 table=(epoint **)mr_alloc(_MIPP_ (1<<window),sizeof(epoint *));
87 if (table==NULL)
88 {
89 mr_berror(_MIPP_ MR_ERR_OUT_OF_MEMORY);
90 MR_OUT
91 return FALSE;
92 }
93 B->a=mirvar(_MIPP_ 0);
94 B->b=mirvar(_MIPP_ 0);
95 B->n=mirvar(_MIPP_ 0);
96 copy(a,B->a);
97 copy(b,B->b);
98 copy(n,B->n);
99
100 ecurve_init(_MIPP_ a,b,n,MR_BEST);
101 w=epoint_init(_MIPPO_ );
102 epoint_set(_MIPP_ x,y,0,w);
103 table[0]=epoint_init(_MIPPO_ );
104 table[1]=epoint_init(_MIPPO_ );
105 epoint_copy(w,table[1]);
106 for (j=0;j<t;j++)
107 ecurve_double(_MIPP_ w);
108 k=1;
109 for (i=2;i<(1<<window);i++)
110 {
111 table[i]=epoint_init(_MIPPO_ );
112 if (i==(1<<k))
113 {
114 k++;
115 epoint_norm(_MIPP_ w);
116 epoint_copy(w,table[i]);
117
118 for (j=0;j<t;j++)
119 ecurve_double(_MIPP_ w);
120 continue;
121 }
122 bp=1;
123 for (j=0;j<k;j++)
124 {
125 if (i&bp)
126 {
127 is=1<<j;
128 ecurve_add(_MIPP_ table[is],table[i]);
129 }
130 bp<<=1;
131 }
132 epoint_norm(_MIPP_ table[i]);
133 }
134 epoint_free(w);
135
136 /* create the table */
137
138 len=n->len;
139 bptr=0;
140 B->table=(mr_small *)mr_alloc(_MIPP_ 2*len*(1<<window),sizeof(mr_small));
141
142 for (i=0;i<(1<<window);i++)
143 {
144 for (j=0;j<len;j++)
145 {
146 B->table[bptr++]=table[i]->X->w[j];
147 }
148 for (j=0;j<len;j++)
149 {
150 B->table[bptr++]=table[i]->Y->w[j];
151 }
152
153 epoint_free(table[i]);
154 }
155
156 mr_free(table);
157
158 MR_OUT
159 return TRUE;
160 }
161
ebrick_end(ebrick * B)162 void ebrick_end(ebrick *B)
163 {
164 mirkill(B->n);
165 mirkill(B->b);
166 mirkill(B->a);
167 mr_free(B->table);
168 }
169
170 #else
171
172 /* use precomputated table in ROM - see romaker.c to create the table, and ecdhp.c
173 for an example of use */
174
ebrick_init(ebrick * B,const mr_small * rom,big a,big b,big n,int window,int nb)175 void ebrick_init(ebrick *B,const mr_small* rom,big a,big b,big n,int window,int nb)
176 {
177 B->table=rom;
178 B->a=a; /* just pass a pointer */
179 B->b=b;
180 B->n=n;
181 B->window=window; /* 2^4=16 stored values */
182 B->max=nb;
183 }
184
185 #endif
186
mul_brick(_MIPD_ ebrick * B,big e,big x,big y)187 int mul_brick(_MIPD_ ebrick *B,big e,big x,big y)
188 {
189 int i,j,t,d,len,maxsize,promptr;
190 epoint *w,*z;
191
192 #ifdef MR_STATIC
193 char mem[MR_ECP_RESERVE(2)];
194 #else
195 char *mem;
196 #endif
197 #ifdef MR_OS_THREADS
198 miracl *mr_mip=get_mip();
199 #endif
200
201 if (size(e)<0) mr_berror(_MIPP_ MR_ERR_NEG_POWER);
202 t=MR_ROUNDUP(B->max,B->window);
203
204 MR_IN(116)
205
206 #ifndef MR_ALWAYS_BINARY
207 if (mr_mip->base != mr_mip->base2)
208 {
209 mr_berror(_MIPP_ MR_ERR_NOT_SUPPORTED);
210 MR_OUT
211 return 0;
212 }
213 #endif
214
215 if (logb2(_MIPP_ e) > B->max)
216 {
217 mr_berror(_MIPP_ MR_ERR_EXP_TOO_BIG);
218 MR_OUT
219 return 0;
220 }
221
222 ecurve_init(_MIPP_ B->a,B->b,B->n,MR_BEST);
223 #ifdef MR_STATIC
224 memset(mem,0,MR_ECP_RESERVE(2));
225 #else
226 mem=(char *)ecp_memalloc(_MIPP_ 2);
227 #endif
228 w=epoint_init_mem(_MIPP_ mem,0);
229 z=epoint_init_mem(_MIPP_ mem,1);
230
231 len=B->n->len;
232 maxsize=2*(1<<B->window)*len;
233
234 j=recode(_MIPP_ e,t,B->window,t-1);
235 if (j>0)
236 {
237 promptr=2*j*len;
238 init_point_from_rom(w,len,B->table,maxsize,&promptr);
239 }
240 for (i=t-2;i>=0;i--)
241 {
242 j=recode(_MIPP_ e,t,B->window,i);
243 ecurve_double(_MIPP_ w);
244 if (j>0)
245 {
246 promptr=2*j*len;
247 init_point_from_rom(z,len,B->table,maxsize,&promptr);
248 ecurve_add(_MIPP_ z,w);
249 }
250 }
251
252 d=epoint_get(_MIPP_ w,x,y);
253 #ifndef MR_STATIC
254 ecp_memkill(_MIPP_ mem,2);
255 #else
256 memset(mem,0,MR_ECP_RESERVE(2));
257 #endif
258 MR_OUT
259 return d;
260 }
261