I need to convert elements of the finite field $GF(p^k)$, where $p$ is an odd prime, to octet strings.

To be more precise, I want to include elliptic curve points over $GF(p^2)$ in a Subject Public Key Info of an X.509 certificate. In the document IEEE P1363 there is a FE2OSP function which is probably not usable for that case.

Do you know of any well accepted standard which describes that encoding?

  • $\begingroup$ The question's tag includes ASN.1, but refers to FE2OSP, which does not use ASN.1. $\;$ FE2OSP formally does not cover $GF(p^k)$ when $p$ is odd and $k>1$; it is possible to extend FE2OSP to that case, though, but in a number of different ways. $\;$ So it is unclear if you want an ASN.1 encoding or not, and if that should be on top of an extension of FE2OSP or not, and which one (the appropriate extension might depend, among other things, about if $x$ is kept as $k$ integers modulo $p$, and or a single integer modulo $p^k$). $\;$ Also, if that's the case, please restrict to $p$ an odd prime. $\endgroup$ – fgrieu Sep 26 '15 at 9:37
  • $\begingroup$ Are the coordinates of a point in $GF(p^2)^2$, or in $GF(p)^2$? $\endgroup$ – fgrieu Sep 26 '15 at 11:08
  • $\begingroup$ $(x,y) \in E(p^2)$, $x \in GF(p^2)$, $y \in GF(p^2)$ $\endgroup$ – user27950 Sep 26 '15 at 11:14
  • $\begingroup$ So a stupid question from a developer: can you determine a maximum size in bytes of $GF(p^2)$? Because after that it seems just a question of left padding the big endian number representation to that size. $\endgroup$ – Maarten Bodewes Sep 26 '15 at 11:27
  • $\begingroup$ Please be a little bit more polite, Maarten. If you read my question carefully, you will notice that I do not ask for some way but for a standardized way to do this. $\endgroup$ – user27950 Sep 26 '15 at 12:11

Ok, if there is no standard, then "I do it my way":

Let $i$ be a root of a fixed minimum polynomial of $GF(p^2)$ and $x$ be an element in $GF(p^2)$. Then $x:= x_1+x_2*i$ can be represented as a vector $(x_1,x_2) \in GF(p)^2$. Now convert $x_1$ and $x_2$ with the FE2OSP function form IEEE P1363 and concatenate them
$FE2OSP(x_1)|| FE2OSP(x_2)$.

An elliptic curve point $(x,y) \in E(GF(p^2))$ can then be represented either compressed or not compressed.

not compressed:

  • $04|| FE2OSP(x_1)|| FE2OSP(x_2)|| FE2OSP(y_1)|| FE2OSP(y_2)$


  • $02|| FE2OSP (x_1)|| FE2OSP (x_2)$ if $LSB(FE2OSP(y_1))=0$

  • $03|| FE2OSP(x_1)|| FE2OSP (x_2)$ if $LSB(FE2OSP (y_1))=1$

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy