33 	 * We want to invert e modulo phi = (p-1)(q-1). This first  in br_rsa_i31_compute_privexp()
37 	 * Since p = 3 mod 4 and q = 3 mod 4, phi/4 is an odd integer.  in br_rsa_i31_compute_privexp()
39 	 * modulo phi, but this would involve assembling three modulus-wide  in br_rsa_i31_compute_privexp()
42 	 * slightly more than 3 kB of stack space for RSA-4096. This  in br_rsa_i31_compute_privexp()
47 	 *   - We compute phi = k*e + r  (Euclidean division of phi by e).  in br_rsa_i31_compute_privexp()
50 	 *     enforce non-ridiculously-small factors.  in br_rsa_i31_compute_privexp()
52 	 *   - We find small u, v such that u*e - v*r = 1  (using a  in br_rsa_i31_compute_privexp()
56 	 *   - Solution is: d = u + v*k  in br_rsa_i31_compute_privexp()
58 	 *     the above implies d < r + e*((phi-r)/e) = phi  in br_rsa_i31_compute_privexp()
76 	 * Check lengths of p and q, and that they are both odd.  in br_rsa_i31_compute_privexp()
78 	pbuf = sk->p;  in br_rsa_i31_compute_privexp()
79 	plen = sk->plen;  in br_rsa_i31_compute_privexp()
82 		plen --;  in br_rsa_i31_compute_privexp()
85 		|| (pbuf[plen - 1] & 1) != 1)  in br_rsa_i31_compute_privexp()
89 	qbuf = sk->q;  in br_rsa_i31_compute_privexp()
90 	qlen = sk->qlen;  in br_rsa_i31_compute_privexp()
93 		qlen --;  in br_rsa_i31_compute_privexp()
96 		|| (qbuf[qlen - 1] & 1) != 1)  in br_rsa_i31_compute_privexp()
104 	dlen = (sk->n_bitlen + 7) >> 3;  in br_rsa_i31_compute_privexp()
117 	 * Compute phi = (p-1)*(q-1), then move it over p-1 and q-1 (that  in br_rsa_i31_compute_privexp()
120 	 * p-1 and q-1, which is usually exact but may overshoot by one 1  in br_rsa_i31_compute_privexp()
123 	p[1] --;  in br_rsa_i31_compute_privexp()
124 	q[1] --;  in br_rsa_i31_compute_privexp()
136 	 * non-zero (otherwise, the key is invalid). The quotient is k,  in br_rsa_i31_compute_privexp()
140 	for (u = len; u >= 1; u --) {  in br_rsa_i31_compute_privexp()
159 	 * Compute u and v such that u*e - v*r = GCD(e,r). We use  in br_rsa_i31_compute_privexp()
163 	 *   b = r    u1 = r   v1 = e-1  in br_rsa_i31_compute_privexp()
165 	 *   a = u0*e - v0*r  in br_rsa_i31_compute_privexp()
166 	 *   b = u1*e - v1*r  in br_rsa_i31_compute_privexp()
176 	 *  - if a is even, then a <- a/2  in br_rsa_i31_compute_privexp()
177 	 *  - otherwise, if b is even, then b <- b/2  in br_rsa_i31_compute_privexp()
178 	 *  - otherwise, if a > b, then a <- (a-b)/2  in br_rsa_i31_compute_privexp()
179 	 *  - otherwise, if b > a, then b <- (b-a)/2  in br_rsa_i31_compute_privexp()
191 	 *  - When a is divided by 2, u0 and v0 must be divided by 2.  in br_rsa_i31_compute_privexp()
192 	 *  - When b is divided by 2, u1 and v1 must be divided by 2.  in br_rsa_i31_compute_privexp()
193 	 *  - When b is subtracted from a, u1 and v1 are subtracted from  in br_rsa_i31_compute_privexp()
195 	 *  - When a is subtracted from b, u0 and v0 are subtracted from  in br_rsa_i31_compute_privexp()
201 	 *  - When a is divided by 2, then a is even. Therefore:  in br_rsa_i31_compute_privexp()
203 	 *     * If r is odd, then u0 and v0 must have the same parity;  in br_rsa_i31_compute_privexp()
204 	 *       if they are both odd, then adding r to u0 and e to v0  in br_rsa_i31_compute_privexp()
208 	 *     * If r is even, then u0 must be even; if v0 is odd, then  in br_rsa_i31_compute_privexp()
212 	 *    Thus, all we need to do is to look at the parity of v0,  in br_rsa_i31_compute_privexp()
213 	 *    and add (r,e) to (u0,v0) when v0 is odd. In order to avoid  in br_rsa_i31_compute_privexp()
214 	 *    a 32-bit overflow, we can add ((r+1)/2,(e/2)+1) after the  in br_rsa_i31_compute_privexp()
216 	 *    is equal to (e+1)/2 since e is odd).  in br_rsa_i31_compute_privexp()
218 	 *  - When we subtract b from a, three cases may occur:  in br_rsa_i31_compute_privexp()
223 	 *         (u0, v0) <- (u0 + r - u1, v0 + e - v1)  in br_rsa_i31_compute_privexp()
226 	 *         (u0, v0) <- (u0 + r - u1, v0 + e - v1)  in br_rsa_i31_compute_privexp()
245 	v1 = e - 1;  in br_rsa_i31_compute_privexp()
253 		oa = a & 1;                  /* 1 if a is odd */  in br_rsa_i31_compute_privexp()
254 		ob = b & 1;                  /* 1 if b is odd */  in br_rsa_i31_compute_privexp()
258 		sab = oa & ob & agtb;        /* 1 if a <- a-b */  in br_rsa_i31_compute_privexp()
259 		sba = oa & ob & bgta;        /* 1 if b <- b-a */  in br_rsa_i31_compute_privexp()
261 		/* a <- a-b, u0 <- u0-u1, v0 <- v0-v1 */  in br_rsa_i31_compute_privexp()
263 		a -= b & -sab;  in br_rsa_i31_compute_privexp()
264 		u0 -= (u1 - (r & -ctl)) & -sab;  in br_rsa_i31_compute_privexp()
265 		v0 -= (v1 - (e & -ctl)) & -sab;  in br_rsa_i31_compute_privexp()
267 		/* b <- b-a, u1 <- u1-u0 mod r, v1 <- v1-v0 mod e */  in br_rsa_i31_compute_privexp()
269 		b -= a & -sba;  in br_rsa_i31_compute_privexp()
270 		u1 -= (u0 - (r & -ctl)) & -sba;  in br_rsa_i31_compute_privexp()
271 		v1 -= (v0 - (e & -ctl)) & -sba;  in br_rsa_i31_compute_privexp()
273 		da = NOT(oa) | sab;          /* 1 if a <- a/2 */  in br_rsa_i31_compute_privexp()
274 		db = (oa & NOT(ob)) | sba;   /* 1 if b <- b/2 */  in br_rsa_i31_compute_privexp()
276 		/* a <- a/2, u0 <- u0/2, v0 <- v0/2 */  in br_rsa_i31_compute_privexp()
278 		a ^= (a ^ (a >> 1)) & -da;  in br_rsa_i31_compute_privexp()
279 		u0 ^= (u0 ^ ((u0 >> 1) + (hr & -ctl))) & -da;  in br_rsa_i31_compute_privexp()
280 		v0 ^= (v0 ^ ((v0 >> 1) + (he & -ctl))) & -da;  in br_rsa_i31_compute_privexp()
282 		/* b <- b/2, u1 <- u1/2 mod r, v1 <- v1/2 mod e */  in br_rsa_i31_compute_privexp()
284 		b ^= (b ^ (b >> 1)) & -db;  in br_rsa_i31_compute_privexp()
285 		u1 ^= (u1 ^ ((u1 >> 1) + (hr & -ctl))) & -db;  in br_rsa_i31_compute_privexp()
286 		v1 ^= (v1 ^ ((v1 >> 1) + (he & -ctl))) & -db;  in br_rsa_i31_compute_privexp()
298 	 * Now we have u0*e - v0*r = 1. Let's compute the result as:  in br_rsa_i31_compute_privexp()