[U-Boot] U-Boot RSA en/decryption

[Simon Glass]

Hi Or,

On Mon, Aug 26, 2013 at 10:18 AM, Or Yochanan <ory at annapurnalabs.com> wrote:
> Hi Simon, and thanks for the quick reply,
>
>
> On 26 August 2013 18:16, Simon Glass <sjg at chromium.org> wrote:
>>
>> Hi Or,
>>
>> On Sun, Aug 25, 2013 at 2:28 PM, Or Yochanan <ory at annapurnalabs.com>
>> wrote:
>> > Hello,
>> >
>> > This is my first message to the U-Boot mailing list, so please go easy
>> > on me
>> > if my syntax is flawed.. ;)
>> >
>> > I need to use RSA decryption on my U-Boot, for a specific task i have.
>> > In
>> > order to do so - I'd like to use some of the RSA code that have been
>> > added
>> > to lib (instead of porting some other encryption code into my
>> > environment).
>> >
>> > After going over the RSA code, I came to conclusion that the portion of
>> > the
>> > code that performs RSA verification using an RSA key (rsa_verify_key) is
>> > exactly what I need, since I don't intend to use FIT nor add anything to
>> > DT
>> > (it seems like an overkill for my requirements).
>> >
>> > However, I fail to understand how to use the RSA's data structures
>> > correctly. Specifically, rsa_public_key input parameter requires
>> > arguments
>> > that aren't clear to me. I searched online, yet couldn't find any
>> > reference
>> > code to parse i.o. to understand what is required from this struct..
>> >
>> > So my main questions are regarding the rsa_public_key struct that is
>> > also
>> > mentioned on the documentation:
>> > 1. There's a requirement for bot num-bits, and r^2 - how comes? From
>> > what I
>> > understand, r^2 can be calculated using num-bits - so currently I
>> > suspect
>> > that I got it wrong?
>>
>> Yes it can be calculated. The idea here is to pre-calculate things
>> that don't need to be done at run-time in U-Boot.
>
>
> Alright, thanks.
>>
>>
>> > 2. What is n0inverse? I didn't find anything on the web that explains
>> > this
>> > argument, nor did I find anything that resemble the calculation (-1 /
>> > N[0]
>> > mod 2^32).
>>
>> If you look at rsa_get_params() you will see where it calculates these
>> parameters from the RSA key. n0inverse is -1 / n mod 2^32.
>>
>> Normally these three parameters are stored in the DT, but if you don't
>> use that I suppose you could put them somewhere else.
>
>
> If it wasn't obvious - I looked at the documentation prior to this mail. I

Patches to docs welcome, once you do understand it :-)

> didn't understand it then, and I don't understand it now:
> What do you mean by -1 / n mod 2^32?
> Since we are speaking of integers, performing (-1 / n) doesn't make sense to
> me. Also, the calculation is performed only with the least significant
> integer of N, so it's even more unclear to me.
>
> Say I have N = LS-->{0x00001234, 0x00005678, 0x00009abc}<--MS
> what would be n0inverse..? How did you calculate it?

Well sure in normal integer arithmetic 1/N would be 0, but with modulo
arithmetic things are different. For example, in mod 9 arithmetic:

5 * 2 = 10 = 1 (mod 9)
So 5 * 2 = 1 (mod 9)
or put it another way: the inverse of 5 is 2 (mod 9)

I'm not sure about least-significant - I believe it is actually
most-significant, otherwise you would get the wrong answer.

Does that make sense? Probably you understand modulo arithmetic but
are not just sure about the steps...?

>>
>>
>> >
>> > If there's a possibility to better explain these arguments, or even
>> > better -
>> > provide a usage example, I'd be grateful.
>>
>> The basic idea is that with these values is to make it possible to
>> verify a signature using just the code in rsa-verify.c. There is no
>> 'bignum' code required, nor any openssl key management/decoding code.
>> If you look at rsa_verify_key() you will see that it only needs
>> exponentiation (pow_mod()) and the code size is quite small.

Regards,
Simon