1 /*******************************************************************************
2 * Copyright 2002-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 // Purpose:
43 // Intel(R) Integrated Performance Primitives. Cryptography Primitives.
44 // Internal Unsigned arithmetic
45 //
46 // Contents:
47 // cpModInv_BNU()
48 //
49 */
50
51 #include "owncp.h"
52 #include "pcpbnuarith.h"
53 #include "pcpbnumisc.h"
54
55
56 /*
57 // cpMAC_BNU
58 //
59 // Multiply with ACcumulation
60 // Computes r <- r + a * b, returns real size of the r in the size_r variable
61 // Returns 0 if there are no enought buffer size to write to r[MAX(size_r + 1, size_a + size_b) - 1]
62 // Returns 1 if no error
63 //
64 // Note:
65 // DO NOT run in inplace mode
66 // The minimum buffer size for the r must be (size_a + size_b - 1)
67 // the maximum buffer size for the r is MAX(size_r + 1, size_a + size_b)
68 */
cpMac_BNU(BNU_CHUNK_T * pR,cpSize nsR,const BNU_CHUNK_T * pA,cpSize nsA,const BNU_CHUNK_T * pB,cpSize nsB)69 static int cpMac_BNU(BNU_CHUNK_T* pR, cpSize nsR,
70 const BNU_CHUNK_T* pA, cpSize nsA,
71 const BNU_CHUNK_T* pB, cpSize nsB)
72 {
73 /* cleanup the rest of destination buffer */
74 ZEXPAND_BNU(pR, nsR, nsA+nsB-1);
75 //nsR = IPP_MAX(nsR, nsA+nsB);
76
77 {
78 BNU_CHUNK_T expansion = 0;
79 cpSize i;
80 for(i=0; i<nsB && !expansion; i++) {
81 expansion = cpAddMulDgt_BNU(pR+i, pA, nsA, pB[i]);
82 if(expansion)
83 expansion = cpInc_BNU(pR+i+nsA, pR+i+nsA, nsR-i-nsA, expansion);
84 }
85
86 if(expansion)
87 return 0;
88 else { /* compute real size */
89 FIX_BNU(pR, nsR);
90 return nsR;
91 }
92 }
93 }
94
95 /*F*
96 // Name: cpModInv_BNU
97 //
98 // Purpose: Multiplicative Inversion BigNum.
99 //
100 // Returns: Reason:
101 //
102 // Parameters:
103 // pA source (value) BigNum A
104 // nsA size of A
105 // pM source (modulus) BigNum M
106 // nsM size of M
107 // pInv result BigNum
108 // bufInv buffer of Inv
109 // bufA buffer of A
110 // bufM buffer of M
111 //
112 *F*/
113
cpModInv_BNU(BNU_CHUNK_T * pInv,const BNU_CHUNK_T * pA,cpSize nsA,const BNU_CHUNK_T * pM,cpSize nsM,BNU_CHUNK_T * bufInv,BNU_CHUNK_T * bufA,BNU_CHUNK_T * bufM)114 int cpModInv_BNU(BNU_CHUNK_T* pInv,
115 const BNU_CHUNK_T* pA, cpSize nsA,
116 const BNU_CHUNK_T* pM, cpSize nsM,
117 BNU_CHUNK_T* bufInv, BNU_CHUNK_T* bufA, BNU_CHUNK_T* bufM)
118 {
119 FIX_BNU(pA, nsA);
120 FIX_BNU(pM, nsM);
121
122 /* inv(1) = 1 */
123 if(nsA==1 && pA[0]==1) {
124 pInv[0] = 1;
125 return 1;
126 }
127
128 {
129 cpSize moduloSize = nsM;
130
131 BNU_CHUNK_T* X1 = pInv;
132 BNU_CHUNK_T* X2 = bufM;
133 BNU_CHUNK_T* Q = bufInv;
134 cpSize nsX1 = 1;
135 cpSize nsX2 = 1;
136 cpSize nsQ;
137
138 COPY_BNU(bufA, pA, nsA);
139
140 ZEXPAND_BNU(X1, 0, moduloSize);
141 ZEXPAND_BNU(X2, 0, moduloSize);
142 X2[0] = 1;
143
144 //printf("\n");
145 for(;;) {
146 nsM = cpDiv_BNU(Q, &nsQ, (BNU_CHUNK_T*)pM, nsM, bufA, nsA);
147 //Print_BNU(" q: ", Q, nsQ);
148 //Print_BNU(" m: ", pM, nsM);
149 nsX1 = cpMac_BNU(X1,moduloSize, Q,nsQ, X2,nsX2);
150 //Print_BNU("X1: ", X1, nsX1);
151
152 if (nsM==1 && pM[0]==1) {
153 ////ZEXPAND_BNU(X2, nsX2, moduloSize);
154 nsX2 = cpMac_BNU(X2,moduloSize, X1,nsX1, bufA, nsA);
155 COPY_BNU((BNU_CHUNK_T*)pM, X2, moduloSize);
156 cpSub_BNU(pInv, pM, X1, moduloSize);
157 FIX_BNU(pInv, moduloSize);
158 return moduloSize;
159 }
160 else if (nsM==1 && pM[0]==0) {
161 cpMul_BNU_school((BNU_CHUNK_T*)pM, X1,nsX1, bufA, nsA);
162 /* gcd = buf_a */
163 return 0;
164 }
165
166 nsA = cpDiv_BNU(Q, &nsQ, bufA, nsA, (BNU_CHUNK_T*)pM, nsM);
167 //Print_BNU(" q: ", Q, nsQ);
168 //Print_BNU(" a: ", bufA, nsA);
169 nsX2 = cpMac_BNU(X2,moduloSize, Q,nsQ, X1,nsX1);
170 //Print_BNU("X2: ", X2, nsX2);
171
172 if(nsA==1 && bufA[0]==1) {
173 ////ZEXPAND_BNU(X1, nsX1, moduloSize);
174 nsX1 = cpMac_BNU(X1, moduloSize, X2, nsX2, pM, nsM);
175 COPY_BNU((BNU_CHUNK_T*)pM, X1, moduloSize);
176 COPY_BNU(pInv, X2, nsX2);
177 return nsX2;
178 }
179 else if (nsA==1 && bufA[0]==0) {
180 /* gcd = m */
181 COPY_BNU(X1, pM, nsM);
182 cpMul_BNU_school((BNU_CHUNK_T*)pM, X2, nsX2, X1, nsM);
183 return 0;
184 }
185 }
186 }
187 }
188