30 	const br_rsa_private_key *sk, uint32_t e)  in br_rsa_i15_compute_privexp()  argument
33 	 * We want to invert e modulo phi = (p-1)(q-1). This first  in br_rsa_i15_compute_privexp()
38 	 * We could invert e modulo phi/4 then patch the result to  in br_rsa_i15_compute_privexp()
40 	 * values (phi/4, 1 and e) and calling moddiv, that requires  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()
48 	 *     If public exponent e is correct, then r != 0 (e must be  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()
53 	 *     binary GCD; we can arrange for u < r and v < e, i.e. all  in br_rsa_i15_compute_privexp()
57 	 *     This last computation is exact: since u < r and v < e,  in br_rsa_i15_compute_privexp()
58 	 *     the above implies d < r + e*((phi-r)/e) = phi  in br_rsa_i15_compute_privexp()
61 	uint16_t tmp[4 * ((BR_MAX_RSA_FACTOR + 14) / 15) + 12];  in br_rsa_i15_compute_privexp()
69 	 * Check that e is correct.  in br_rsa_i15_compute_privexp()
71 	if (e < 3 || (e & 1) == 0) {  in br_rsa_i15_compute_privexp()
111 	plen = (p[0] + 15) >> 4;  in br_rsa_i15_compute_privexp()
114 	qlen = (q[0] + 15) >> 4;  in br_rsa_i15_compute_privexp()
128 	len = (phi[0] + 15) >> 4;  in br_rsa_i15_compute_privexp()
132 	len = (phi[0] + 15) >> 4;  in br_rsa_i15_compute_privexp()
135 	 * Divide phi by public exponent e. The final remainder r must be  in br_rsa_i15_compute_privexp()
142 		 * Upon entry, r < e, and phi[u] < 2^15; hence,  in br_rsa_i15_compute_privexp()
143 		 * hi:lo < e*2^15. Thus, the produced word k[u]  in br_rsa_i15_compute_privexp()
144 		 * must be lower than 2^15, and the new remainder r  in br_rsa_i15_compute_privexp()
145 		 * is lower than e.  in br_rsa_i15_compute_privexp()
150 		lo = (r << 15) + phi[u];  in br_rsa_i15_compute_privexp()
151 		phi[u] = br_divrem(hi, lo, e, &r);  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()
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()
167 	 *   0 < a <= e  in br_rsa_i15_compute_privexp()
170 	 *   0 <= v0 <= e  in br_rsa_i15_compute_privexp()
172 	 *   0 <= v1 <= e  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()
204 	 *       if they are both odd, then adding r to u0 and e to v0  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()
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()
223 	 *         (u0, v0) <- (u0 + r - u1, v0 + e - v1)  in br_rsa_i15_compute_privexp()
226 	 *         (u0, v0) <- (u0 + r - u1, v0 + e - v1)  in br_rsa_i15_compute_privexp()
237 	 *    We can thus handle the subtraction by adding (r,e) based  in br_rsa_i15_compute_privexp()
240 	a = e;  in br_rsa_i15_compute_privexp()
245 	v1 = e - 1;  in br_rsa_i15_compute_privexp()
247 	he = (e >> 1) + 1;  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()
271 		v1 -= (v0 - (e & -ctl)) & -sba;  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()
298 	 * Now we have u0*e - v0*r = 1. Let's compute the result as:  in br_rsa_i15_compute_privexp()
306 	m[2] = (v0 >> 15) & 0x7FFF;  in br_rsa_i15_compute_privexp()
311 	z[2] = (u0 >> 15) & 0x7FFF;  in br_rsa_i15_compute_privexp()