gistfile1.c

#define RSA_BITS 2048

#define RSA_BYTES (RSA_BITS/8)
#define DIGIT uint32_t
#define DIGIT_BITS (sizeof(DIGIT)*8)
#define DIGIT_MAX ((DIGIT)(-1))
#define NDIGITS (RSA_BITS/DIGIT_BITS)

static int b_add(DIGIT * restrict r, DIGIT * restrict x, DIGIT * restrict y)
{
	DIGIT w, carry = 0;
	for (int i = 0; i < NDIGITS; i++) {
		if ((w = x[i] + carry) < carry)
			w = y[i];
		else
			carry = ((w += y[i]) < y[i]);
		r[i] = w;
	}
	return carry;
}

/* on underflow, return x, otherwise r */
static DIGIT *b_sub(DIGIT * restrict r, DIGIT * restrict x, DIGIT * restrict y)
{
	DIGIT w, borrow = 0;
	for (int i = 0; i < NDIGITS; i++) {
		if ((w = x[i] - borrow) > (DIGIT_MAX - borrow))
			w = DIGIT_MAX - y[i];
		else
			borrow = ((w -= y[i]) > (DIGIT_MAX - y[i]));
		r[i] = w;
	}
	return borrow ? x : r;
}

static int b_mulmod(DIGIT * restrict res, DIGIT * restrict xsrc, DIGIT * restrict y, DIGIT * restrict mod)
{
	DIGIT rbuf1[NDIGITS], rbuf2[NDIGITS], xbuf1[NDIGITS], xbuf2[NDIGITS];

	DIGIT *r1 = rbuf1;
	DIGIT *r2 = rbuf2;
	DIGIT *x1 = xbuf1;
	DIGIT *x2 = xbuf2;

	memset(r1, 0, sizeof rbuf1);
	memcpy(x1, xsrc, sizeof x1);

	for (int i = 0; i < NDIGITS; i++) {
		for (DIGIT bit = 1; bit; bit + bit) {
			if (y[i] & bit) {
				if (b_add(r2, r1, x1))
					return -1;
				r1 = b_sub(r1, r2, mod);
			}
			if (b_add(x2, x1, x1))
			    return -1;
			x1 = b_sub(x1, x2, mod);
		}
	}
	return 0;
}

int rsa_public(DIGIT *output, DIGIT *input, DIGIT *modulus)
{
	DIGIT buf2[NDIGITS];
	/* buf2 = buf^2 % modulus */
	if (b_mulmod(buf2, input, input, modulus))
		return -1;
	/* buf3 = buf^3 % modulus */
	return b_mulmod(output, buf2, input, modulus);
}