[U-Boot] [PATCH v2] Implement generalised RSA public exponents for verified boot

[Michael van der Westhuizen]

Hi Simon,

Thanks for the feedback.

I'll take care of the nits and look into removing some special casing.

On 30 May 2014, at 9:04 PM, Simon Glass <sjg at chromium.org> wrote:

> Hi Michael,
> 
<snip>
>> 
>> /**
>> + * num_pub_exponent_bits() - Number of bits in the public exponent
>> + *
>> + * @key:       RSA key
>> + * @k:         Storage for the number of public exponent bits
>> + */
>> +static int num_public_exponent_bits(const struct rsa_public_key *key, int *k)
> 
> s/k/keyp/ or something like that.
> 
> Also is this function able to just use ffs() or similar?

flsll() yes, but that's not portable to Linux.

> 
<snip>

>> +}
>> +
>> +/**
>>  * pow_mod() - in-place public exponentiation
>>  *
>>  * @key:       RSA key
>> @@ -132,6 +171,7 @@ static int pow_mod(const struct rsa_public_key *key, uint32_t *inout)
>> {
>>        uint32_t *result, *ptr;
>>        uint i;
>> +       int j, k;
>> 
>>        /* Sanity check for stack size - key->len is in 32-bit words */
>>        if (key->len > RSA_MAX_KEY_BITS / 32) {
>> @@ -141,18 +181,49 @@ static int pow_mod(const struct rsa_public_key *key, uint32_t *inout)
>>        }
>> 
>>        uint32_t val[key->len], acc[key->len], tmp[key->len];
>> +       uint32_t a_scaled[key->len];
>>        result = tmp;  /* Re-use location. */
>> 
>>        /* Convert from big endian byte array to little endian word array. */
>>        for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--)
>>                val[i] = get_unaligned_be32(ptr);
>> 
>> -       montgomery_mul(key, acc, val, key->rr);  /* axx = a * RR / R mod M */
>> -       for (i = 0; i < 16; i += 2) {
>> -               montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod M */
>> -               montgomery_mul(key, acc, tmp, tmp); /* acc = tmp^2 / R mod M */
>> +       if (0 != num_public_exponent_bits(key, &k))
>> +               return -EINVAL;
>> +
>> +       if (k < 2) {
>> +               debug("Public exponent is too short (%d bits, minimum 2)\n",
>> +                     k);
>> +               return -EINVAL;
>> +       }
>> +
>> +       if (!is_public_exponent_bit_set(key, k - 1) ||
>> +           !is_public_exponent_bit_set(key, 0)) {
>> +               debug("Invalid RSA public exponent 0x%llx.\n", key->exponent);
> 
> What is invalid about it? Perhaps expand the message?
> 
>> +               return -EINVAL;
>> +       }
>> +
>> +       /* the bit at e[k-1] is 1 by definition, so start with: C := M */
>> +       montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */
>> +       /* retain scaled version for intermediate use */
> 
> Join these two comments, also the style should be:
> 
> /*
> * The bit at ...
> * ...
> */
> 
>> +       memcpy(a_scaled, acc, key->len * 4);
> 
> What is 4? is it sizeof(uint32_t?). I wonder if we could replace the
> line immediately above and remove this memcpy()?
> 
> For example, if you did:
> 
>       montgomery_mul(key, result, val, key->rr); /* acc = a * RR / R mod n */

Yes, it's sizeof(uint32_t) - that would probably be a good thing to spell out too.

result points to tmp, which is going to be repeatedly overwritten in the loop, but we need a_scaled to stay constant (as the result of the first montgomery_mul) throughout... or did I misunderstand your point?

> 
>> +
>> +       for (j = k - 2; j > 0; --j) {
>> +               montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
>> +
>> +               if (is_public_exponent_bit_set(key, j)) {
>> +                       /* acc = tmp * val / R mod n */
>> +                       montgomery_mul(key, acc, tmp, a_scaled);
>> +               } else {
>> +                       /* e[j] == 0, copy tmp back to acc for next operation */
>> +                       memcpy(acc, tmp, key->len * 4);
>> +               }
>>        }
>> -       montgomery_mul(key, result, acc, val);  /* result = XX * a / R mod M */
>> +
>> +       /* the bit at e[0] is always 1 */
>> +       montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
>> +       montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */
>> +       memcpy(result, acc, key->len * 4);


<snip>

Michael