view release on metacpan or  search on metacpan

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

 * the size of p.
 */
static uint32_t
invert_pubexp(uint32_t *d, const uint32_t *m, uint32_t e, uint32_t *t)
{
	uint32_t *f;
	uint32_t r;

	f = t;
	t += 1 + ((m[0] + 31) >> 5);

	/*
	 * Compute d = 1/e mod m. Since p = 3 mod 4, m is odd.
	 */
	br_i31_zero(d, m[0]);
	d[1] = 1;
	br_i31_zero(f, m[0]);
	f[1] = e & 0x7FFFFFFF;
	f[2] = e >> 31;
	r = br_i31_moddiv(d, f, m, br_i31_ninv31(m[1]), t);

	/*
	 * We really want d = 1/e mod p-1, with p = 2m. By the CRT,
	 * the result is either the d we got, or d + m.
	 *
	 * Let's write e*d = 1 + k*m, for some integer k. Integers e
	 * and m are odd. If d is odd, then e*d is odd, which implies
	 * that k must be even; in that case, e*d = 1 + (k/2)*2m, and
	 * thus d is already fine. Conversely, if d is even, then k
	 * is odd, and we must add m to d in order to get the correct
	 * result.
	 */
	br_i31_add(d, m, (uint32_t)(1 - (d[1] & 1)));

	return r;
}

/*
 * Swap two buffers in RAM. They must be disjoint.
 */
static void
bufswap(void *b1, void *b2, size_t len)
{
	size_t u;
	unsigned char *buf1, *buf2;

	buf1 = b1;
	buf2 = b2;
	for (u = 0; u < len; u ++) {
		unsigned w;

		w = buf1[u];
		buf1[u] = buf2[u];
		buf2[u] = w;
	}
}

/* see inner.h */
uint32_t
br_rsa_i31_keygen_inner(const br_prng_class **rng,
	br_rsa_private_key *sk, void *kbuf_priv,
	br_rsa_public_key *pk, void *kbuf_pub,
	unsigned size, uint32_t pubexp, br_i31_modpow_opt_type mp31)
{
	uint32_t esize_p, esize_q;
	size_t plen, qlen, tlen;
	uint32_t *p, *q, *t;
	union {
		uint32_t t32[TEMPS];
		uint64_t t64[TEMPS >> 1];  /* for 64-bit alignment */
	} tmp;
	uint32_t r;

	if (size < BR_MIN_RSA_SIZE || size > BR_MAX_RSA_SIZE) {
		return 0;
	}
	if (pubexp == 0) {
		pubexp = 3;
	} else if (pubexp == 1 || (pubexp & 1) == 0) {
		return 0;
	}

	esize_p = (size + 1) >> 1;
	esize_q = size - esize_p;
	sk->n_bitlen = size;
	sk->p = kbuf_priv;
	sk->plen = (esize_p + 7) >> 3;
	sk->q = sk->p + sk->plen;
	sk->qlen = (esize_q + 7) >> 3;
	sk->dp = sk->q + sk->qlen;
	sk->dplen = sk->plen;
	sk->dq = sk->dp + sk->dplen;
	sk->dqlen = sk->qlen;
	sk->iq = sk->dq + sk->dqlen;
	sk->iqlen = sk->plen;

	if (pk != NULL) {
		pk->n = kbuf_pub;
		pk->nlen = (size + 7) >> 3;
		pk->e = pk->n + pk->nlen;
		pk->elen = 4;
		br_enc32be(pk->e, pubexp);
		while (*pk->e == 0) {
			pk->e ++;
			pk->elen --;
		}
	}

	/*
	 * We now switch to encoded sizes.
	 *
	 * floor((x * 16913) / (2^19)) is equal to floor(x/31) for all
	 * integers x from 0 to 34966; the intermediate product fits on
	 * 30 bits, thus we can use MUL31().
	 */
	esize_p += MUL31(esize_p, 16913) >> 19;
	esize_q += MUL31(esize_q, 16913) >> 19;
	plen = (esize_p + 31) >> 5;
	qlen = (esize_q + 31) >> 5;
	p = tmp.t32;
	q = p + 1 + plen;