In Daniel Bernstein's implementation of NIST P-224 elliptic curves, what is the encoding used by the secret e?

Tom

1/20/24, 7:42 PM

I'm working with https://cr.yp.to/nistp224/library.html and trying to correctly format my integer e for the library. The doc states:

The integer e is 2^224 + 2^216(e[0] - 136) + 2^208(e[1] - 136) + ... + 2^0(e[27] - 136).

I already have an integer e in mind, but I've got it encoded as a big endian array of bytes. What is the encoding above called (if it has a name)? Is there a known method for taking an integer and encoding it in the above format?

1 + 0

elliptic-curves

Score:0

Crypto

poncho

1/20/24, 8:07 PM

What is the encoding above called (if it has a name)?

I don't expect so - it appears that Dan specified this specifically for P224. The addition of $2^{224}$ is to prevent someone from being tempted to optimize the point multiplication routine by skipping leading ones (although it doesn't do a perfect job; bit 224 may be a one or a zero based on what e[0] is, because of the subtraction of 136). I do not know why he specified subtracting 136 from each byte - the only immediately obvious reason for doing something like that would be to avoid accidentally running into a multiple of the order of the curve, and this doesn't do that (although, as Dan mentions on his page, the probability of doing that is fantastically small).

Is there a known method for taking an integer and encoding it in the above format?

It can easily be done with a two-step process:

Take your string of 28 bytes (in bigendian format) and convert it into an integer
Add the constant 0x77777777777777777777777777777777777777777777777777777778

which is $2^{224} - 136 \cdot (2^{216} + 2^{208} + ... + 2^8 + 2^0)$, this will add in the $2^{224}$ and effectively subtract 136 from each byte).

+ 1

Samuel Neves

1/22/24, 5:29 AM

136 = 0x88, so I assume that the value has something to do with the [implementation](https://cr.yp.to/talks/2001.11.02/slides-djb-20011102-nistp224-a4.pdf#page=23) treating each 4-bit chunk of the scalar as a value in $[-8,\dots,7]$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: In Daniel Bernstein's implementation of NIST P-224 elliptic curves, what is the encoding used by the secret e?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.