1 /*******************************************************************************
2 * Copyright 2017-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 //
43 // Purpose:
44 // Cryptography Primitive. Modular Arithmetic Engine. General Functionality
45 //
46 // Contents:
47 // alm_mont_inv()
48 //
49 */
50
51 #include "owndefs.h"
52 #include "owncp.h"
53 #include "pcpbnumisc.h"
54 #include "pcpbnuarith.h"
55 #include "gsmodstuff.h"
56 #include "pcpmask_ct.h"
57
58 /*
59 // almost Montgomery Inverse
60 //
61 // returns (k,r), r = (1/a)*(2^k) mod m
62 //
63 */
alm_mont_inv(BNU_CHUNK_T * pr,const BNU_CHUNK_T * pa,gsModEngine * pME)64 int alm_mont_inv(BNU_CHUNK_T* pr, const BNU_CHUNK_T* pa, gsModEngine* pME)
65 {
66 const BNU_CHUNK_T* pm = MOD_MODULUS(pME);
67 int mLen = MOD_LEN(pME);
68
69 const int polLength = 4;
70 BNU_CHUNK_T* pBuffer = gsModPoolAlloc(pME, polLength);
71
72 BNU_CHUNK_T* pu = pBuffer;
73 BNU_CHUNK_T* ps = pu+mLen;
74 BNU_CHUNK_T* pv = ps+mLen;
75 BNU_CHUNK_T* pt = pv+mLen;
76
77 int k = 0;
78 BNU_CHUNK_T ext = 0;
79
80 //gres: temporary excluded: assert(NULL!=pBuffer);
81
82 // u=modulus, v=a, t=0, s=1
83 COPY_BNU(pu, pm, mLen);
84 ZEXPAND_BNU(ps, 0, mLen); ps[0] = 1;
85 COPY_BNU(pv, pa, mLen);
86 ZEXPAND_BNU(pt, 0, mLen);
87
88 while(!cpEqu_BNU_CHUNK(pv, mLen, 0)) { // while(v>0) {
89 if(0==(pu[0]&1)) { // if(isEven(u)) {
90 cpLSR_BNU(pu, pu, mLen, 1); // u = u/2;
91 cpAdd_BNU(ps, ps, ps, mLen); // s = 2*s;
92 } // }
93 else if(0==(pv[0]&1)) { // else if(isEven(v)) {
94 cpLSR_BNU(pv, pv, mLen, 1); // v = v/2;
95 /*ext +=*/ cpAdd_BNU(pt, pt, pt, mLen); // t = 2*t;
96 } // }
97 else {
98 int cmpRes = cpCmp_BNU(pu, mLen, pv, mLen);
99 if(cmpRes>0) { // else if (u>v) {
100 cpSub_BNU(pu, pu, pv, mLen); // u = (u-v);
101 cpLSR_BNU(pu, pu, mLen, 1); // u = u/2;
102 /*ext +=*/ cpAdd_BNU(pt, pt, ps, mLen); // t = t+s;
103 cpAdd_BNU(ps, ps, ps, mLen); // s = 2*s;
104 } // }
105 else { // else if(v>=u) {
106 cpSub_BNU(pv, pv, pu, mLen); // v = (v-u);
107 cpLSR_BNU(pv, pv, mLen, 1); // v = v/2;
108 cpAdd_BNU(ps, ps, pt, mLen); // s = s+t;
109 ext += cpAdd_BNU(pt, pt, pt, mLen); // t = 2*t;
110 } // }
111 }
112 k++; // k += 1;
113 } // }
114
115 // test
116 if(1!=cpEqu_BNU_CHUNK(pu, mLen, 1)) {
117 k = 0; /* inversion not found */
118 }
119
120 else {
121 ext -= cpSub_BNU(pr, pt, pm, mLen); // if(t>mod) r = t-mod;
122 cpMaskMove_gs(pr, pt, mLen, cpIsNonZero(ext)); // else r = t;
123 cpSub_BNU(pr, pm, pr, mLen); // return r= (mod - r) and k
124 }
125
126 gsModPoolFree(pME, polLength);
127 return k;
128 }
129