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 * MIRACL Chinese Remainder Thereom routines (for use with small moduli)
37 * mrscrt.c
38 */
39
40
41 #include <stdlib.h>
42 #include "miracl.h"
43
44 #ifdef MR_FP
45 #include <math.h>
46 #endif
47
in_range(mr_utype x,mr_utype y)48 static mr_utype in_range(mr_utype x,mr_utype y)
49 { /* x=x%y, and positive */
50 mr_utype r;
51 #ifdef MR_FP
52 mr_small dres;
53 #endif
54 r=MR_REMAIN(x,y);
55 if (r<0) r+=y;
56 return r;
57 }
58
59 #ifndef MR_STATIC
60
scrt_init(_MIPD_ small_chinese * c,int r,mr_utype * moduli)61 BOOL scrt_init(_MIPD_ small_chinese *c,int r,mr_utype *moduli)
62 { /* calculate CRT constants - returns FALSE if there is a problem */
63 int i,j,k;
64 if (r<1) return FALSE;
65 if (r==1)
66 {
67 c->NP=1;
68 c->M=(mr_utype *)mr_alloc(_MIPP_ r,sizeof(mr_utype));
69 if (c->M==NULL) return FALSE;
70 c->M[0]=moduli[0];
71 return TRUE;
72 }
73 for (i=0;i<r;i++) if (moduli[i]<2) return FALSE;
74 c->M=(mr_utype *)mr_alloc(_MIPP_ r,sizeof(mr_utype));
75 if (c->M==NULL) return FALSE;
76 c->C=(mr_utype *)mr_alloc(_MIPP_ r*(r-1)/2,sizeof(mr_utype));
77 if (c->C==NULL)
78 { /* no room */
79 mr_free(c->M);
80 return FALSE;
81 }
82 c->V=(mr_utype *)mr_alloc(_MIPP_ r,sizeof(mr_utype));
83 if (c->V==NULL)
84 { /* no room */
85 mr_free(c->M);
86 mr_free(c->C);
87 return FALSE;
88 }
89 for (k=0,i=0;i<r;i++)
90 {
91 c->M[i]=moduli[i];
92 for (j=0;j<i;j++,k++)
93 c->C[k]=invers(c->M[j],c->M[i]);
94 }
95 c->NP=r;
96 return TRUE;
97 }
98
scrt_end(small_chinese * c)99 void scrt_end(small_chinese *c)
100 { /* clean up after CRT */
101 if (c->NP<1)
102 {
103 c->NP=0;
104 return;
105 }
106 if (c->NP==1)
107 {
108 mr_free(c->M);
109 c->NP=0;
110 return;
111 }
112 mr_free(c->M);
113 mr_free(c->V);
114 mr_free(c->C);
115 c->NP=0;
116 }
117
118 #endif
119
scrt(_MIPD_ small_chinese * c,mr_utype * u,big x)120 void scrt(_MIPD_ small_chinese *c,mr_utype *u,big x)
121 { /* Chinese Remainder Thereom *
122 * Calculate x given remainders u[i] mod M[i] */
123 int i,j,k;
124 mr_utype *V,*C,*M;
125 mr_small t;
126 #ifdef MR_OS_THREADS
127 miracl *mr_mip=get_mip();
128 #endif
129 #ifdef MR_FP_ROUNDING
130 mr_large im;
131 #endif
132 V=c->V;
133 C=c->C;
134 M=c->M;
135 if (c->NP<1) return;
136 if (c->NP==1)
137 {
138 t=smul(1,in_range(u[0],M[0]),M[0]);
139 convert(_MIPP_ 1,mr_mip->w5);
140 mr_pmul(_MIPP_ mr_mip->w5,t,x);
141 return;
142 }
143 V[0]=u[0];
144 for (k=0,i=1;i<c->NP;i++)
145 { /* Knuth P. 274 */
146 V[i]=u[i] - V[0];
147 #ifdef MR_FP_ROUNDING
148 im=mr_invert(M[i]);
149 imuldiv(V[i],C[k],(mr_small)0,M[i],im,&V[i]);
150 if (V[i]<0) V[i]+=M[i];
151 #else
152 V[i]=smul(in_range(V[i],M[i]),C[k],M[i]);
153 #endif
154 k++;
155
156 #ifndef MR_FP
157 #ifdef INLINE_ASM
158 #if INLINE_ASM == 3
159 #define MR_IMPASM
160
161 ASM mov ebx,DWORD PTR V
162 ASM mov esi,DWORD PTR M
163 ASM mov edi,DWORD PTR C
164 ASM mov ecx,1
165 ASM mov edx,DWORD PTR i
166 ASM mov esi,[esi+4*edx]
167 s1:
168 ASM cmp ecx,edx
169 ASM jge s2
170
171 ASM mov eax,[ebx+4*edx]
172 ASM push edx
173
174 ASM sub eax,[ebx+4*ecx]
175 ASM cdq
176 ASM idiv esi
177 ASM mov eax,edx
178 ASM add eax,esi
179
180 ASM mov edx,DWORD PTR k
181 ASM mul DWORD PTR [edi+4*edx]
182 ASM div esi
183
184 ASM mov eax,edx
185
186 ASM pop edx
187 ASM mov [ebx+4*edx],eax
188 ASM inc DWORD PTR k
189 ASM inc ecx
190 ASM jmp s1
191 s2:
192 ASM nop
193
194 #endif
195
196 #if INLINE_ASM == 4
197 #define MR_IMPASM
198 ASM (
199 "movl %0,%%ebx\n"
200 "movl %1,%%esi\n"
201 "movl %2,%%edi\n"
202 "movl $1,%%ecx\n"
203 "movl %3,%%edx\n"
204 "movl (%%esi,%%edx,4),%%esi\n"
205 "s1:\n"
206 "cmpl %%edx,%%ecx\n"
207 "jge s2\n"
208
209 "movl (%%ebx,%%edx,4),%%eax\n"
210 "pushl %%edx\n"
211
212 "subl (%%ebx,%%ecx,4),%%eax\n"
213
214 "cltd \n"
215 "idivl %%esi\n"
216 "movl %%edx,%%eax\n"
217 "addl %%esi,%%eax\n"
218
219 "movl %4,%%edx\n"
220 "mull (%%edi,%%edx,4)\n"
221 "divl %%esi\n"
222
223 "movl %%edx,%%eax\n"
224
225 "popl %%edx\n"
226 "movl %%eax,(%%ebx,%%edx,4)\n"
227 "incl %4\n"
228 "incl %%ecx\n"
229 "jmp s1\n"
230 "s2:\n"
231 "nop\n"
232 :
233 :"m"(V),"m"(M),"m"(C),"m"(i),"m"(k)
234 :"eax","ebx","ecx","edx","esi","edi","memory"
235 );
236 #endif
237 #endif
238 #endif
239 #ifndef MR_IMPASM
240 for (j=1;j<i;j++,k++)
241 {
242 V[i]-=V[j];
243 #ifdef MR_FP_ROUNDING
244 imuldiv(V[i],C[k],(mr_small)0,M[i],im,&V[i]);
245 if (V[i]<0) V[i]+=M[i];
246 #else
247 V[i]=smul(in_range(V[i],M[i]),C[k],M[i]);
248 #endif
249 }
250 #endif
251 }
252
253 convert(_MIPP_ 1,x);
254 mr_pmul(_MIPP_ x,(mr_small)V[0],x);
255 convert(_MIPP_ 1,mr_mip->w5);
256 for (j=1;j<c->NP;j++)
257 {
258 mr_pmul(_MIPP_ mr_mip->w5,(mr_small)(M[j-1]),mr_mip->w5);
259 mr_pmul(_MIPP_ mr_mip->w5,(mr_small)(V[j]),mr_mip->w0);
260 mr_padd(_MIPP_ x,mr_mip->w0,x);
261 }
262 }
263