1 /*******************************************************************************
2 * Copyright 2010-2018 Intel Corporation
3 * All Rights Reserved.
4 *
5 * If this software was obtained under the Intel Simplified Software License,
6 * the following terms apply:
7 *
8 * The source code, information and material ("Material") contained herein is
9 * owned by Intel Corporation or its suppliers or licensors, and title to such
10 * Material remains with Intel Corporation or its suppliers or licensors. The
11 * Material contains proprietary information of Intel or its suppliers and
12 * licensors. The Material is protected by worldwide copyright laws and treaty
13 * provisions. No part of the Material may be used, copied, reproduced,
14 * modified, published, uploaded, posted, transmitted, distributed or disclosed
15 * in any way without Intel's prior express written permission. No license under
16 * any patent, copyright or other intellectual property rights in the Material
17 * is granted to or conferred upon you, either expressly, by implication,
18 * inducement, estoppel or otherwise. Any license under such intellectual
19 * property rights must be express and approved by Intel in writing.
20 *
21 * Unless otherwise agreed by Intel in writing, you may not remove or alter this
22 * notice or any other notice embedded in Materials by Intel or Intel's
23 * suppliers or licensors in any way.
24 *
25 *
26 * If this software was obtained under the Apache License, Version 2.0 (the
27 * "License"), the following terms apply:
28 *
29 * You may not use this file except in compliance with the License. You may
30 * obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0
31 *
32 *
33 * Unless required by applicable law or agreed to in writing, software
34 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
35 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
36 *
37 * See the License for the specific language governing permissions and
38 * limitations under the License.
39 *******************************************************************************/
40
41 /*
42 // Intel(R) Integrated Performance Primitives. Cryptography Primitives.
43 // Internal operations over GF(p) extension.
44 //
45 // Context:
46 // cpGFpxInv()
47 //
48 */
49
50 #include "owncp.h"
51 #include "pcpbnumisc.h"
52 #include "pcpgfpxstuff.h"
53 #include "gsscramble.h"
54
55 //tbcd: temporary excluded: #include <assert.h>
56
gfpxPolyDiv(BNU_CHUNK_T * pQ,BNU_CHUNK_T * pR,const BNU_CHUNK_T * pA,const BNU_CHUNK_T * pB,gsModEngine * pGFEx)57 static BNU_CHUNK_T* gfpxPolyDiv(BNU_CHUNK_T* pQ, BNU_CHUNK_T* pR,
58 const BNU_CHUNK_T* pA,
59 const BNU_CHUNK_T* pB,
60 gsModEngine* pGFEx)
61 {
62 if( GFP_IS_BASIC(pGFEx) )
63 return NULL;
64
65 else {
66 int elemLen = GFP_FELEN(pGFEx);
67 gsModEngine* pGroundGFE = GFP_PARENT(pGFEx);
68 int termLen = GFP_FELEN(pGroundGFE);
69
70 int degA = degree(pA, pGFEx);
71 int degB = degree(pB, pGFEx);
72
73 if(degB==0) {
74 if( GFP_IS_ZERO(pB, termLen) )
75 return NULL;
76 else {
77 gsModEngine* pBasicGFE = cpGFpBasic(pGroundGFE);
78
79 cpGFpInv(pR, pB, pBasicGFE);
80 cpGFpElementPadd(pR+GFP_FELEN(pGroundGFE), termLen-GFP_FELEN(pGroundGFE), 0);
81 cpGFpxMul_GFE(pQ, pA, pR, pGFEx);
82 cpGFpElementPadd(pR, elemLen, 0);
83 return pR;
84 }
85 }
86
87 if(degA < degB) {
88 cpGFpElementPadd(pQ, elemLen, 0);
89 cpGFpElementCopyPadd(pR, elemLen, pA, (degA+1)*termLen);
90 return pR;
91 }
92
93 else {
94 mod_mul mulF = GFP_METHOD(pGroundGFE)->mul;
95 mod_sub subF = GFP_METHOD(pGroundGFE)->sub;
96
97 int i, j;
98 BNU_CHUNK_T* pProduct = cpGFpGetPool(2, pGroundGFE);
99 BNU_CHUNK_T* pInvB = pProduct + GFP_PELEN(pGroundGFE);
100 //tbcd: temporary excluded: assert(NULL!=pProduct);
101
102 cpGFpElementCopyPadd(pR, elemLen, pA, (degA+1)*termLen);
103 cpGFpElementPadd(pQ, elemLen, 0);
104
105 cpGFpxInv(pInvB, GFPX_IDX_ELEMENT(pB, degB, termLen), pGroundGFE);
106
107 for(i=0; i<=degA-degB && !GFP_IS_ZERO(GFPX_IDX_ELEMENT(pR, degA-i, termLen), termLen); i++) {
108 /* compute q term */
109 mulF(GFPX_IDX_ELEMENT(pQ, degA-degB-i, termLen),
110 GFPX_IDX_ELEMENT(pR, degA-i, termLen),
111 pInvB,
112 pGroundGFE);
113
114 /* R -= B * q */
115 cpGFpElementPadd(GFPX_IDX_ELEMENT(pR, degA-i, termLen), termLen, 0);
116 for(j=0; j<degB; j++) {
117 mulF(pProduct,
118 GFPX_IDX_ELEMENT(pB, j ,termLen),
119 GFPX_IDX_ELEMENT(pQ, degA-degB-i, termLen),
120 pGroundGFE);
121 subF(GFPX_IDX_ELEMENT(pR, degA-degB-i+j, termLen),
122 GFPX_IDX_ELEMENT(pR, degA-degB-i+j, termLen),
123 pProduct,
124 pGroundGFE);
125 }
126 }
127
128 cpGFpReleasePool(2, pGroundGFE);
129 return pR;
130 }
131 }
132 }
133
134
gfpxGeneratorDiv(BNU_CHUNK_T * pQ,BNU_CHUNK_T * pR,const BNU_CHUNK_T * pB,gsModEngine * pGFEx)135 static BNU_CHUNK_T* gfpxGeneratorDiv(BNU_CHUNK_T* pQ, BNU_CHUNK_T* pR, const BNU_CHUNK_T* pB, gsModEngine* pGFEx)
136 {
137 if( GFP_IS_BASIC(pGFEx) )
138 return NULL;
139
140 else {
141 int elemLen = GFP_FELEN(pGFEx);
142
143 gsModEngine* pGroundGFE = GFP_PARENT(pGFEx);
144 mod_mul mulF = GFP_METHOD(pGroundGFE)->mul;
145 mod_sub subF = GFP_METHOD(pGroundGFE)->sub;
146
147 int termLen = GFP_FELEN(pGroundGFE);
148
149 BNU_CHUNK_T* pInvB = cpGFpGetPool(2, pGroundGFE);
150 BNU_CHUNK_T* pTmp = pInvB + GFP_PELEN(pGroundGFE);
151
152 int degB = degree(pB, pGFEx);
153 int i;
154
155 //tbcd: temporary excluded: assert(NULL!=pInvB);
156
157 cpGFpElementCopy(pR, GFP_MODULUS(pGFEx), elemLen);
158 cpGFpElementPadd(pQ, elemLen, 0);
159
160 cpGFpxInv(pInvB, GFPX_IDX_ELEMENT(pB, degB, termLen), pGroundGFE);
161
162 for(i=0; i<degB; i++) {
163 BNU_CHUNK_T* ptr;
164 mulF(pTmp, pInvB, GFPX_IDX_ELEMENT(pB, i, termLen), pGroundGFE);
165 ptr = GFPX_IDX_ELEMENT(pR, GFP_EXTDEGREE(pGFEx)-degB+i, termLen);
166 subF(ptr, ptr, pTmp, pGroundGFE);
167 }
168
169 gfpxPolyDiv(pQ, pR, pR, pB, pGFEx);
170
171 cpGFpElementCopy(GFPX_IDX_ELEMENT(pQ, GFP_EXTDEGREE(pGFEx)-degB, termLen), pInvB, termLen);
172
173 cpGFpReleasePool(2, pGroundGFE);
174 return pR;
175 }
176 }
177
cpGFpxInv(BNU_CHUNK_T * pR,const BNU_CHUNK_T * pA,gsModEngine * pGFEx)178 BNU_CHUNK_T* cpGFpxInv(BNU_CHUNK_T* pR, const BNU_CHUNK_T* pA, gsModEngine* pGFEx)
179 {
180 if( GFP_IS_BASIC(pGFEx) )
181 return cpGFpInv(pR, pA, pGFEx);
182
183 if(0==degree(pA, pGFEx)) {
184 gsModEngine* pGroundGFE = GFP_PARENT(pGFEx);
185 BNU_CHUNK_T* tmpR = cpGFpGetPool(1, pGroundGFE);
186 //tbcd: temporary excluded: assert(NULL!=tmpR);
187
188 cpGFpxInv(tmpR, pA, pGroundGFE);
189
190 cpGFpElementCopyPadd(pR, GFP_FELEN(pGFEx), tmpR, GFP_FELEN(pGroundGFE));
191 cpGFpReleasePool(1, pGroundGFE);
192 return pR;
193 }
194
195 else {
196 int elemLen = GFP_FELEN(pGFEx);
197 gsModEngine* pGroundGFE = GFP_PARENT(pGFEx);
198 gsModEngine* pBasicGFE = cpGFpBasic(pGFEx);
199
200 int pxVars = 6;
201 int pelemLen = GFP_PELEN(pGFEx);
202 BNU_CHUNK_T* lastrem = cpGFpGetPool(pxVars, pGFEx);
203 BNU_CHUNK_T* rem = lastrem + pelemLen;
204 BNU_CHUNK_T* quo = rem + pelemLen;
205 BNU_CHUNK_T* lastaux = quo + pelemLen;
206 BNU_CHUNK_T* aux = lastaux + pelemLen;
207 BNU_CHUNK_T* temp = aux + pelemLen;
208 //tbcd: temporary excluded: assert(NULL!=lastrem);
209
210 cpGFpElementCopy(lastrem, pA, elemLen);
211 cpGFpElementCopyPadd(lastaux, elemLen, GFP_MNT_R(pBasicGFE), GFP_FELEN(pBasicGFE));
212
213 gfpxGeneratorDiv(quo, rem, pA, pGFEx);
214 cpGFpxNeg(aux, quo, pGFEx);
215
216 while(degree(rem, pGFEx) > 0) {
217 gfpxPolyDiv(quo, temp, lastrem, rem, pGFEx);
218 SWAP_PTR(BNU_CHUNK_T, rem, lastrem); //
219 SWAP_PTR(BNU_CHUNK_T, temp, rem);
220
221 GFP_METHOD(pGFEx)->neg(quo, quo, pGFEx);
222 GFP_METHOD(pGFEx)->mul(temp, quo, aux, pGFEx);
223 GFP_METHOD(pGFEx)->add(temp, lastaux, temp, pGFEx);
224 SWAP_PTR(BNU_CHUNK_T, aux, lastaux);
225 SWAP_PTR(BNU_CHUNK_T, temp, aux);
226 }
227 if (GFP_IS_ZERO(rem, elemLen)) { /* gcd != 1 */
228 cpGFpReleasePool(pxVars, pGFEx);
229 return NULL;
230 }
231
232 {
233 BNU_CHUNK_T* invRem = cpGFpGetPool(1, pGroundGFE);
234 //tbcd: temporary excluded: assert(NULL!=invRem);
235
236 cpGFpxInv(invRem, rem, pGroundGFE);
237 cpGFpxMul_GFE(pR, aux, invRem, pGFEx);
238
239 cpGFpReleasePool(1, pGroundGFE);
240 }
241
242 cpGFpReleasePool(pxVars, pGFEx);
243
244 return pR;
245 }
246 }
247