[Cryptech Tech] Storage of curve parameters for ECDSA

[Pavel Shatov]

Hello!

I've been working on ECDSA lately. I'm now trying to figure out, where 
we're going to store curve parameters. The problem is that FPGA needs to 
know coordinates of the base point and modulus in order to be able to 
sign anything. So there will be buffers for these parameters, but the 
question is, how exactly are we going to fill them?

When we do RSA with ModExpS6 we have a buffer for modulus, that is 
actually a chunk of dual-port block RAM. The first port is read-write 
and faces the user, while the second port is read-only and faces the 
internals of the core. So user can fill in his modulus (which is 
effectively his public key) and read it back in case he wants to verify, 
that FPGA is operating with the correct key. The internal 
square-and-multiply exponentiation algorithm can retrieve the modulus 
through the other port.

We can do the same for ECDSA, this way STM32 will have to read all the 
curve parameters (from where?) and then fill them in FPGA buffers every 
time the board is turned on.

Now the difference between RSA and ECDSA is that for elliptic curves the 
modulus is fixed. Because of that the buffer for modulus can potentially 
be turned into block ROM and automatically initialized during FPGA 
configuration. This way all the curve parameters can be embedded into 
the bitstream and loaded automatically during configuration. The first 
read-only port can still be accessed by STM32 to read back curve 
parameters from the FPGA and verify, that ECDSA core is operating with 
correct data.

I'm somewhat worried, because according to the document called "Suite B 
Implementer’s Guide to FIPS 186-3 (ECDSA)", curve parameters must only 
be obtained from a trustworthy source, their validity should be assured 
prior to generation of keys and signatures, they must be protected from 
unauthorized modification, etc, etc. Well, yeah, the document itself 
comes from (Achtung! Achtung!) the NSA, but it kind of makes sense, that 
integrity of curve parameters is important.

So the question is, where are we going to store curve parameters? I 
personally believe, that it would be better to embed them into the 
bitstream and store in chunks of FPGA block ROM. But I may be wrong, 
because I'm looking at it from my level of wires and registers. I would 
really appreciate to hear from someone with "bigger" picture in his head.

Btw, there's another similar problem. ECDSA core uses Montgomery 
algorithm for multiplication. The algorithm works on numbers, that are 
in Montgomery form. To convert ordinary numbers into Montgomery form and 
back, we need special coefficient, that depends on the modulus. In Rob's 
software implementation this factor is called "mu" and is stored along 
with other curve parameters. FPGA obviously needs to know this factor 
too. Right now I've just hardcoded it into the testbench, that I use for 
development. How exactly are we going to deal with this factor, when 
times comes to work in real hardware? Are we going to calculate this 
factor every time? It depends on the modulus, and given that the modulus 
is always the same, this factor is fixed too. So same question here, can 
we just calculate it once, dump into a text file and embed into the 
bitstream using $readmemh?


--
With best regards,
Pavel Shatov