view release on metacpan or  search on metacpan

src/rsa/rsa_i15_privexp.c  view on Meta::CPAN

/*
 * Copyright (c) 2018 Thomas Pornin <pornin@bolet.org>
 *
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include "inner.h"

/* see bearssl_rsa.h */
size_t
br_rsa_i15_compute_privexp(void *d,
	const br_rsa_private_key *sk, uint32_t e)
{
	/*
	 * We want to invert e modulo phi = (p-1)(q-1). This first
	 * requires computing phi, which is easy since we have the factors
	 * p and q in the private key structure.
	 *
	 * Since p = 3 mod 4 and q = 3 mod 4, phi/4 is an odd integer.
	 * We could invert e modulo phi/4 then patch the result to
	 * modulo phi, but this would involve assembling three modulus-wide
	 * values (phi/4, 1 and e) and calling moddiv, that requires
	 * three more temporaries, for a total of six big integers, or
	 * slightly more than 3 kB of stack space for RSA-4096. This
	 * exceeds our stack requirements.
	 *
	 * Instead, we first use one step of the extended GCD:
	 *
	 *   - We compute phi = k*e + r  (Euclidean division of phi by e).
	 *     If public exponent e is correct, then r != 0 (e must be
	 *     invertible modulo phi). We also have k != 0 since we
	 *     enforce non-ridiculously-small factors.
	 *
	 *   - We find small u, v such that u*e - v*r = 1  (using a
	 *     binary GCD; we can arrange for u < r and v < e, i.e. all
	 *     values fit on 32 bits).
	 *
	 *   - Solution is: d = u + v*k
	 *     This last computation is exact: since u < r and v < e,
	 *     the above implies d < r + e*((phi-r)/e) = phi
	 */

	uint16_t tmp[4 * ((BR_MAX_RSA_FACTOR + 14) / 15) + 12];
	uint16_t *p, *q, *k, *m, *z, *phi;
	const unsigned char *pbuf, *qbuf;
	size_t plen, qlen, u, len, dlen;
	uint32_t r, a, b, u0, v0, u1, v1, he, hr;
	int i;

	/*
	 * Check that e is correct.
	 */
	if (e < 3 || (e & 1) == 0) {
		return 0;
	}

	/*
	 * Check lengths of p and q, and that they are both odd.
	 */
	pbuf = sk->p;
	plen = sk->plen;
	while (plen > 0 && *pbuf == 0) {
		pbuf ++;
		plen --;
	}
	if (plen < 5 || plen > (BR_MAX_RSA_FACTOR / 8)
		|| (pbuf[plen - 1] & 1) != 1)
	{
		return 0;
	}
	qbuf = sk->q;
	qlen = sk->qlen;