Lines Matching +full:1 +full:- +full:v0
33 * We want to invert e modulo phi = (p-1)(q-1). This first in br_rsa_i15_compute_privexp()
39 * modulo phi, but this would involve assembling three modulus-wide in br_rsa_i15_compute_privexp()
40 * values (phi/4, 1 and e) and calling moddiv, that requires in br_rsa_i15_compute_privexp()
42 * slightly more than 3 kB of stack space for RSA-4096. This in br_rsa_i15_compute_privexp()
47 * - We compute phi = k*e + r (Euclidean division of phi by e). in br_rsa_i15_compute_privexp()
50 * enforce non-ridiculously-small factors. in br_rsa_i15_compute_privexp()
52 * - We find small u, v such that u*e - v*r = 1 (using a in br_rsa_i15_compute_privexp()
56 * - Solution is: d = u + v*k in br_rsa_i15_compute_privexp()
58 * the above implies d < r + e*((phi-r)/e) = phi in br_rsa_i15_compute_privexp()
65 uint32_t r, a, b, u0, v0, u1, v1, he, hr; in br_rsa_i15_compute_privexp() local
71 if (e < 3 || (e & 1) == 0) { in br_rsa_i15_compute_privexp()
78 pbuf = sk->p; in br_rsa_i15_compute_privexp()
79 plen = sk->plen; in br_rsa_i15_compute_privexp()
82 plen --; in br_rsa_i15_compute_privexp()
85 || (pbuf[plen - 1] & 1) != 1) in br_rsa_i15_compute_privexp()
89 qbuf = sk->q; in br_rsa_i15_compute_privexp()
90 qlen = sk->qlen; in br_rsa_i15_compute_privexp()
93 qlen --; in br_rsa_i15_compute_privexp()
96 || (qbuf[qlen - 1] & 1) != 1) in br_rsa_i15_compute_privexp()
104 dlen = (sk->n_bitlen + 7) >> 3; in br_rsa_i15_compute_privexp()
112 q = p + 1 + plen; in br_rsa_i15_compute_privexp()
117 * Compute phi = (p-1)*(q-1), then move it over p-1 and q-1 (that in br_rsa_i15_compute_privexp()
120 * p-1 and q-1, which is usually exact but may overshoot by one 1 in br_rsa_i15_compute_privexp()
123 p[1] --; in br_rsa_i15_compute_privexp()
124 q[1] --; in br_rsa_i15_compute_privexp()
125 phi = q + 1 + qlen; in br_rsa_i15_compute_privexp()
129 memmove(tmp, phi, (1 + len) * sizeof *phi); in br_rsa_i15_compute_privexp()
131 phi[0] = br_i15_bit_length(phi + 1, len); in br_rsa_i15_compute_privexp()
136 * non-zero (otherwise, the key is invalid). The quotient is k, in br_rsa_i15_compute_privexp()
140 for (u = len; u >= 1; u --) { in br_rsa_i15_compute_privexp()
159 * Compute u and v such that u*e - v*r = GCD(e,r). We use in br_rsa_i15_compute_privexp()
161 * u0, u1, v0 and v1. Initial values are: in br_rsa_i15_compute_privexp()
162 * a = e u0 = 1 v0 = 0 in br_rsa_i15_compute_privexp()
163 * b = r u1 = r v1 = e-1 in br_rsa_i15_compute_privexp()
165 * a = u0*e - v0*r in br_rsa_i15_compute_privexp()
166 * b = u1*e - v1*r in br_rsa_i15_compute_privexp()
170 * 0 <= v0 <= e in br_rsa_i15_compute_privexp()
175 * adjust u0, u1, v0 and v1 to maintain the invariants: in br_rsa_i15_compute_privexp()
176 * - if a is even, then a <- a/2 in br_rsa_i15_compute_privexp()
177 * - otherwise, if b is even, then b <- b/2 in br_rsa_i15_compute_privexp()
178 * - otherwise, if a > b, then a <- (a-b)/2 in br_rsa_i15_compute_privexp()
179 * - otherwise, if b > a, then b <- (b-a)/2 in br_rsa_i15_compute_privexp()
181 * is the GCD of e and r; it must be 1 (otherwise, the private in br_rsa_i15_compute_privexp()
182 * key or public exponent is not valid). The (u0,v0) or (u1,v1) in br_rsa_i15_compute_privexp()
185 * Since either a or b is reduced by at least 1 bit at each in br_rsa_i15_compute_privexp()
191 * - When a is divided by 2, u0 and v0 must be divided by 2. in br_rsa_i15_compute_privexp()
192 * - When b is divided by 2, u1 and v1 must be divided by 2. in br_rsa_i15_compute_privexp()
193 * - When b is subtracted from a, u1 and v1 are subtracted from in br_rsa_i15_compute_privexp()
194 * u0 and v0, respectively. in br_rsa_i15_compute_privexp()
195 * - When a is subtracted from b, u0 and v0 are subtracted from in br_rsa_i15_compute_privexp()
201 * - When a is divided by 2, then a is even. Therefore: in br_rsa_i15_compute_privexp()
203 * * If r is odd, then u0 and v0 must have the same parity; in br_rsa_i15_compute_privexp()
204 * if they are both odd, then adding r to u0 and e to v0 in br_rsa_i15_compute_privexp()
208 * * If r is even, then u0 must be even; if v0 is odd, then in br_rsa_i15_compute_privexp()
209 * adding r to u0 and e to v0 makes them both even, and the in br_rsa_i15_compute_privexp()
212 * Thus, all we need to do is to look at the parity of v0, in br_rsa_i15_compute_privexp()
213 * and add (r,e) to (u0,v0) when v0 is odd. In order to avoid in br_rsa_i15_compute_privexp()
214 * a 32-bit overflow, we can add ((r+1)/2,(e/2)+1) after the in br_rsa_i15_compute_privexp()
215 * division (r+1 does not overflow since r < e; and (e/2)+1 in br_rsa_i15_compute_privexp()
216 * is equal to (e+1)/2 since e is odd). in br_rsa_i15_compute_privexp()
218 * - When we subtract b from a, three cases may occur: in br_rsa_i15_compute_privexp()
220 * * u1 <= u0 and v1 <= v0: just do the subtractions in br_rsa_i15_compute_privexp()
222 * * u1 > u0 and v1 > v0: compute: in br_rsa_i15_compute_privexp()
223 * (u0, v0) <- (u0 + r - u1, v0 + e - v1) in br_rsa_i15_compute_privexp()
225 * * u1 <= u0 and v1 > v0: compute: in br_rsa_i15_compute_privexp()
226 * (u0, v0) <- (u0 + r - u1, v0 + e - v1) in br_rsa_i15_compute_privexp()
228 * The fourth case (u1 > u0 and v1 <= v0) is not possible in br_rsa_i15_compute_privexp()
238 * solely on the comparison between v0 and v1. in br_rsa_i15_compute_privexp()
242 u0 = 1; in br_rsa_i15_compute_privexp()
243 v0 = 0; in br_rsa_i15_compute_privexp()
245 v1 = e - 1; in br_rsa_i15_compute_privexp()
246 hr = (r + 1) >> 1; in br_rsa_i15_compute_privexp()
247 he = (e >> 1) + 1; in br_rsa_i15_compute_privexp()
253 oa = a & 1; /* 1 if a is odd */ in br_rsa_i15_compute_privexp()
254 ob = b & 1; /* 1 if b is odd */ in br_rsa_i15_compute_privexp()
255 agtb = GT(a, b); /* 1 if a > b */ in br_rsa_i15_compute_privexp()
256 bgta = GT(b, a); /* 1 if b > a */ in br_rsa_i15_compute_privexp()
258 sab = oa & ob & agtb; /* 1 if a <- a-b */ in br_rsa_i15_compute_privexp()
259 sba = oa & ob & bgta; /* 1 if b <- b-a */ in br_rsa_i15_compute_privexp()
261 /* a <- a-b, u0 <- u0-u1, v0 <- v0-v1 */ in br_rsa_i15_compute_privexp()
262 ctl = GT(v1, v0); in br_rsa_i15_compute_privexp()
263 a -= b & -sab; in br_rsa_i15_compute_privexp()
264 u0 -= (u1 - (r & -ctl)) & -sab; in br_rsa_i15_compute_privexp()
265 v0 -= (v1 - (e & -ctl)) & -sab; in br_rsa_i15_compute_privexp()
267 /* b <- b-a, u1 <- u1-u0 mod r, v1 <- v1-v0 mod e */ in br_rsa_i15_compute_privexp()
268 ctl = GT(v0, v1); in br_rsa_i15_compute_privexp()
269 b -= a & -sba; in br_rsa_i15_compute_privexp()
270 u1 -= (u0 - (r & -ctl)) & -sba; in br_rsa_i15_compute_privexp()
271 v1 -= (v0 - (e & -ctl)) & -sba; in br_rsa_i15_compute_privexp()
273 da = NOT(oa) | sab; /* 1 if a <- a/2 */ in br_rsa_i15_compute_privexp()
274 db = (oa & NOT(ob)) | sba; /* 1 if b <- b/2 */ in br_rsa_i15_compute_privexp()
276 /* a <- a/2, u0 <- u0/2, v0 <- v0/2 */ in br_rsa_i15_compute_privexp()
277 ctl = v0 & 1; in br_rsa_i15_compute_privexp()
278 a ^= (a ^ (a >> 1)) & -da; in br_rsa_i15_compute_privexp()
279 u0 ^= (u0 ^ ((u0 >> 1) + (hr & -ctl))) & -da; in br_rsa_i15_compute_privexp()
280 v0 ^= (v0 ^ ((v0 >> 1) + (he & -ctl))) & -da; in br_rsa_i15_compute_privexp()
282 /* b <- b/2, u1 <- u1/2 mod r, v1 <- v1/2 mod e */ in br_rsa_i15_compute_privexp()
283 ctl = v1 & 1; in br_rsa_i15_compute_privexp()
284 b ^= (b ^ (b >> 1)) & -db; in br_rsa_i15_compute_privexp()
285 u1 ^= (u1 ^ ((u1 >> 1) + (hr & -ctl))) & -db; in br_rsa_i15_compute_privexp()
286 v1 ^= (v1 ^ ((v1 >> 1) + (he & -ctl))) & -db; in br_rsa_i15_compute_privexp()
290 * Check that the GCD is indeed 1. If not, then the key is invalid in br_rsa_i15_compute_privexp()
293 if (a != 1) { in br_rsa_i15_compute_privexp()
298 * Now we have u0*e - v0*r = 1. Let's compute the result as: in br_rsa_i15_compute_privexp()
299 * d = u0 + v0*k in br_rsa_i15_compute_privexp()
303 m = k + 1 + len; in br_rsa_i15_compute_privexp()
305 m[1] = v0 & 0x7FFF; in br_rsa_i15_compute_privexp()
306 m[2] = (v0 >> 15) & 0x7FFF; in br_rsa_i15_compute_privexp()
307 m[3] = v0 >> 30; in br_rsa_i15_compute_privexp()
310 z[1] = u0 & 0x7FFF; in br_rsa_i15_compute_privexp()