While analyzing the source code of tpm-emulator I found that the RSA key decryption uses an algorithm that is unknown to me.
The original file with this mystery is located in rsa.c, where the rsa_private(...) function resides. The shortened content of this function is the following:
static int rsa_private(tpm_rsa_private_key_t *key,
const uint8_t *in, size_t in_len, uint8_t *out)
{
...
if (!key->p || !key->q || !key->u) {
/* c = p ^ d mod n */
tpm_bn_powm(c, p, key->d, key->n);
} else {
tpm_bn_init2(m1, key->size / 2);
tpm_bn_init2(m2, key->size / 2);
tpm_bn_init2(h, key->size);
/* m1 = p ^ (d mod (p-1)) mod p */
tpm_bn_sub_ui(h, key->p, 1);
tpm_bn_mod(h, key->d, h);
tpm_bn_powm(m1, p, h, key->p);
/* m2 = p ^ (d mod (q-1)) mod q */
tpm_bn_sub_ui(h, key->q, 1);
tpm_bn_mod(h, key->d, h);
tpm_bn_powm(m2, p, h, key->q);
/* h = u * ( m2 - m1 ) mod q */
tpm_bn_sub(h, m2, m1);
if (tpm_bn_sgn(h) < 0) tpm_bn_add(h, h, key->q);
tpm_bn_mul(h, key->u, h);
tpm_bn_mod(h, h, key->q);
/* c = m1 + h * p */
tpm_bn_mul(h, h, key->p);
tpm_bn_add(c, m1, h);
tpm_bn_clear(m1);
tpm_bn_clear(m2);
tpm_bn_clear(h);
}
...
return 0;
}
The basic idea of this function is to decrypt input message in (p in a formula) of size in_len with the help of private RSA key key (exponent is d and modulus is n).
While this part of the code (1st algorithm of decryption):
/* c = p ^ d mod n */
is clear, the other possible algorithm of the decryption code is a mystery to me:
/* m1 = p ^ (d mod (p-1)) mod p */
/* m2 = p ^ (d mod (q-1)) mod q */
/* h = u * ( m2 - m1 ) mod q */
/* c = m1 + h * p */
