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 */ 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 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
