1 /*
2 * Copyright (c) 2001-2019, Arm Limited and Contributors. All rights reserved.
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7
8
9 #include "cc_pal_types.h"
10 #include "cc_pal_mem.h"
11 #include "cc_common_math.h"
12 #include "cc_ecpki_types.h"
13 #include "pka.h"
14 #include "ec_wrst.h"
15 #include "pki.h"
16 #include "pki_modular_arithmetic.h"
17
18 #include "pki_dbg.h"
19 /* virt. pointers to pka regs. (regs. ID-s)*/
20 #include "pka_point_compress_regs_def.h"
21
22
23
24 /*********** PkiCalcJacobiSymbol function **********************/
25 /**
26 * @brief Calculate Jacobi symbol for a and prime b numbers.
27 * Assumed: a, b are a positive numbers.
28 * Note: PKA_REG_A, PKA_REG_B registers are destroed by the function.
29 *
30 * @author reuvenl (10/26/2014)
31 *
32 * @return int32_t jacobi symbol value.
33 */
PkiCalcJacobiSymbol(void)34 int32_t PkiCalcJacobiSymbol(void)
35 {
36 int32_t r, t;
37 uint32_t stat, w, w1;
38
39
40 /* Note: Check GCD - not need because b - prime.
41 Convert a to positive numbers - not need */
42
43 /* case PKA_REG_A = 0 or PKA_REG_A = 1 */
44 PKA_COMPARE_IM_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, 0, stat); /*if(a==0) r = 0*/
45 if(stat == 1) {
46 r = 0;
47 goto End;
48 }
49
50 PKA_COMPARE_IM_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, 1, stat); /*if(a==0) r = 0*/
51 if(stat == 1) {
52 r = 1;
53 goto End;
54 }
55
56 r = 1;
57
58 /* Evaluate Jacobi symb. */
59 do {
60 /* 1. Remove 0-LS bits of PKA_REG_A */
61 t = 0;
62 w = 0;
63
64 while(w == 0) {/* remove 0- words */
65 PKA_READ_WORD_FROM_REG(w, 0, PKA_REG_A);
66 if(w == 0) {
67 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, PKA_REG_A, 32-1);
68 t += 32;
69 }
70 }
71
72 while((w & 1) == 0){
73 w >>= 1;
74 t += 1;
75 }
76 if((t & 0x1F) != 0) {/* removes 0-bits */
77 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, PKA_REG_A, (t & 0x1F) - 1);
78 }
79
80 /* 2. Change sign if b mod 8 == 3 or 5 */
81 PKA_READ_WORD_FROM_REG(w1, 0, PKA_REG_B);
82
83 if(t & 1) {
84 if((w1 & 7) == 3 || (w1 & 7) == 5)
85 r = -r;
86 }
87
88 /* 3. Quadratic reciprocity law */
89 if((w & 3) == 3 && (w1 & 3) == 3){
90 r = -r;
91 }
92
93 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_C, PKA_REG_A);
94 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, PKA_REG_B);
95 PKA_DIV(LEN_ID_N_PKA_REG_BITS, PKA_REG_B, PKA_REG_A, PKA_REG_C); /* a = b mod a */
96 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_B, PKA_REG_C); /* b = a prev. */
97
98 PKA_COMPARE_IM_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, 0, stat);
99
100 } while(stat != 1); /*while a != 0*/
101 End:
102
103 return r;
104
105 } /* End of PkiCalcJacobiSymbol*/
106
107
108 /*********** PkiIsModSquareRootExists function **********************/
109 /**
110 * @brief The function calculates square root modulo prime:
111 * PKA_REG_Y1 = PKA_REG_Y2 ^ 1/2 mod rP if root exists, else returns an error.
112 *
113 * Assuming: 1. The modulus N is a prime.
114 * 2. Y2 is less than modulus.
115 *
116 * @return true if the root exists, or false if not.
117 */
PkiIsModSquareRootExists(void)118 bool PkiIsModSquareRootExists(void)
119 {
120 uint32_t w=0, stat;
121 int32_t s, i;
122 bool rootEx = false;
123 int32_t jcb;
124
125
126 /* if Y^2 = 0, return Y=0 */
127 PKA_COMPARE_IM_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y2, 0, stat);
128 if(stat == 1){
129 PKA_CLEAR(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y1); /* Y1=0*/
130 rootEx = true;
131 goto End;
132 }
133
134 /* read w = mod[0]*/
135 PKA_READ_WORD_FROM_REG(w, 0/*i*/, PKA_REG_N);
136
137 /* ----------------------------------------- */
138 /* Case P=3 mod 4, then PKA_REG_Y1 = +- PKA_REG_Y2^(P+1)/4 */
139 /* ----------------------------------------- */
140 if((w & 0x3) == 3) {
141 PKA_ADD_IM(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y1, PKA_REG_N, 1);
142 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, PKA_REG_Y1, 2-1);
143 PKA_MOD_EXP(LEN_ID_N_BITS, PKA_REG_Y1, PKA_REG_Y2, PKA_REG_T);
144 goto End;
145 }
146
147 /* ------------------------------------------------ */
148 /* Case P=5 mod 8, then PKA_REG_Y1 calculated by algorithm */
149 /* ------------------------------------------------ */
150 if((w & 0x7) == 5) {
151 PKA_SUB_IM(LEN_ID_N_PKA_REG_BITS, PKA_REG_YT, PKA_REG_N, 1); /* PKA_REG_YT = PKA_REG_N-1*/
152 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_Z, PKA_REG_YT, 2-1);
153 PKA_MOD_EXP(LEN_ID_N_BITS, PKA_REG_T, PKA_REG_Y2, PKA_REG_Z); /* d = PKA_REG_T = PKA_REG_Y2^((PKA_REG_N-1)/4)*/
154 PKA_COMPARE_IM_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, 1, stat);
155 if(stat == 1) {
156 PKA_ADD_IM(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, PKA_REG_N, 3);
157 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, PKA_REG_T, 3-1);
158 PKA_MOD_EXP(LEN_ID_N_BITS, PKA_REG_Y1, PKA_REG_Y2, PKA_REG_T);
159 }
160 else {
161 PKA_COMPARE_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, PKA_REG_YT, stat); /* PKA_REG_T =? PKA_REG_N-1*/
162 if(stat == 1) {
163 PKA_SUB_IM(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, PKA_REG_N, 5);
164 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, PKA_REG_T, 3-1);
165 PKA_SHL_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_YT, PKA_REG_Y2, 2-1); /* PKA_REG_YT = 4*PKA_REG_Y2 */
166 PKA_MOD_EXP(LEN_ID_N_BITS, PKA_REG_Z, PKA_REG_YT, PKA_REG_T);
167 PKA_SHL_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_YT, PKA_REG_Y2, 1-1); /* PKA_REG_YT = 2*PKA_REG_Y2 */
168 PKA_MOD_MUL(LEN_ID_N_BITS, PKA_REG_Y1, PKA_REG_Z, PKA_REG_YT); /* PKA_REG_Y1 = 2*PKA_REG_Y2*(4rY2)^((PKA_REG_N-5)/8) */
169 }
170 }
171
172 goto End;
173 }
174
175
176 /* --------------------------------- */
177 /* Case of other modulus structure */
178 /* --------------------------------- */
179
180 /* check if root exist using jacoby symbol */
181 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, PKA_REG_Y2);
182 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_B, PKA_REG_N);
183 jcb = PkiCalcJacobiSymbol(/*, PKA_REG_A, PKA_REG_B*/);
184 if(jcb == -1)
185 goto End;
186
187 /* state P-1 as Q * 2^s, where Q is odd */
188 PKA_SUB_IM(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y1, PKA_REG_N, 1); /**/
189 w -= 1;
190 s = 0;
191 while(w == 0) { /*remove 0-words*/
192 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y1, PKA_REG_Y1, 32-1);
193 s += 32;
194 PKA_READ_WORD_FROM_REG(w, 0/*i*/, PKA_REG_Y1);
195 }
196 /* remove 0-bits */
197 i = 0;
198 while((w & 1) == 0){
199 w >>= 1;
200 i++;
201 }
202 s += i;
203 if(i > 0)
204 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y1, PKA_REG_Y1, i-1);
205
206 /* find first non residue number (modulo N) starting from 2 */
207 jcb = 0;
208 PKA_CLEAR(LEN_ID_N_PKA_REG_BITS, PKA_REG_Z);
209 PKA_SET_BIT0(LEN_ID_N_PKA_REG_BITS, PKA_REG_Z, PKA_REG_Z); /* z = 1*/
210 while (jcb != -1) {
211 PKA_ADD_IM(LEN_ID_N_PKA_REG_BITS, PKA_REG_Z, PKA_REG_Z, 1);
212
213 /*set jacoby input values */
214 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_A, PKA_REG_Z);
215 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_B, PKA_REG_N);
216 jcb = PkiCalcJacobiSymbol(/*, PKA_REG_A, PKA_REG_B*/);
217 }
218
219 PKA_MOD_EXP(LEN_ID_N_BITS, PKA_REG_Z, PKA_REG_Z, PKA_REG_Y1); /* */
220 PKA_ADD_IM(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y1, PKA_REG_Y1, 1);
221 PKA_SHR_FILL0(LEN_ID_N_PKA_REG_BITS, PKA_REG_Y1, PKA_REG_Y1, 1-1); /* PKA_REG_Y1 = (PKA_REG_Y1+1)/2 */
222 PKA_MOD_EXP(LEN_ID_N_BITS, PKA_REG_Y1, PKA_REG_Y2, PKA_REG_Y1); /* PKA_REG_Y1 = PKA_REG_Y2^PKA_REG_Y1 */
223 PKA_COPY(LEN_ID_N_PKA_REG_BITS, PKA_REG_YT, PKA_REG_Y2);
224 PKA_MOD_INV(LEN_ID_N_BITS, PKA_REG_T, PKA_REG_YT);
225 for(;;) {
226 PKA_MOD_MUL(LEN_ID_N_BITS, PKA_REG_YT, PKA_REG_Y1, PKA_REG_Y1); /* PKA_REG_YT = PKA_REG_Y1^2 */
227 PKA_MOD_MUL(LEN_ID_N_BITS, PKA_REG_YT, PKA_REG_YT, PKA_REG_T); /* PKA_REG_YT = PKA_REG_YT * PKA_REG_Y2^-1 */
228 i = 0;
229 while(1) {
230 /*if(PKA_REG_YT == 1) break;*/
231 PKA_COMPARE_IM_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_YT, 1, stat);
232 if(stat == 1)
233 break;
234 i++;
235 PKA_MOD_MUL(LEN_ID_N_BITS, PKA_REG_YT,PKA_REG_YT, PKA_REG_YT); /* PKA_REG_YT = PKA_REG_YT^2 */
236 }
237 /* if PKA_REG_Y1^2 * PKA_REG_Y2^-1 == 1 (mod rP), return */
238 if(i == 0) {
239 rootEx = true;
240 goto End;
241 }
242 if(s-i == 1) { /* mul instead pow */
243 PKA_MOD_MUL(LEN_ID_N_BITS, PKA_REG_Y1, PKA_REG_Y1, PKA_REG_Z);
244 } else {
245 w = 1 << ((s-i-1) & 31);
246 i = (s-i-1) / 32; /*i was free*/
247 PKA_CLEAR(LEN_ID_N_PKA_REG_BITS, PKA_REG_EX);
248 PKA_WRITE_WORD_TO_REG(w, i, PKA_REG_EX);
249 PKA_MOD_EXP(LEN_ID_N_BITS, PKA_REG_YT, PKA_REG_Z, PKA_REG_EX);
250 PKA_MOD_MUL(LEN_ID_N_BITS, PKA_REG_Y1, PKA_REG_Y1, PKA_REG_YT); /* PKA_REG_Y1 = r * PKA_REG_Z^(2^(s-i-1)) */
251 }
252 }
253 End:
254 /* Check result for PKA_REG_N mod 8 = {3,5} */
255 if((w & 3) == 3 || (w & 7) == 5){
256 PKA_MOD_MUL(LEN_ID_N_BITS, PKA_REG_T, PKA_REG_Y1, PKA_REG_Y1);
257 PKA_COMPARE_STATUS(LEN_ID_N_PKA_REG_BITS, PKA_REG_T, PKA_REG_Y2, stat);
258 if(stat == 1)
259 rootEx = true;
260 }
261
262 return rootEx;
263 }
264
265
