[Cryptech Tech] Storage of curve parameters for ECDSA

[Russ Housley]

I'm assuming that we are only supporting a few well-known curves.  Therefore, you need to provide some form of identifier for the curve, but the actual parameters can be inside the FPGA.

I see no problem treating "mu" as a curve parameter.

Russ


On Jan 13, 2016, at 10:25 AM, Pavel Shatov wrote:

> 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