2
$\begingroup$

The reference below refers to "FE2OSP (Field Element to Octet String Conversion Primitive)".

Would appreciate any help in finding the definition (algorithm) for FE2OSP, and the format of its input and output parameters.

Thank you!

Reference: IETF RFC8446, The Transport Layer Security (TLS) Protocol Version 1.3, August 2018), section 7.4.2. "Elliptic Curve Diffie-Hellman"

$\endgroup$
2
$\begingroup$

FE2OSP and OS2FEP convert between finite field element (such as the X or Y coordinate of a point on an Elliptic Curve) and octet string (equivalently bytestring). They were originally defined by IEEE Std 1363-2000 and revised by IEEE P1363a-2004.

Finite field are sets with $q$ elements noted $\operatorname{GF}(q)$ or $\mathbb F_q$, where $q$ is a large integer of the form $q=p^m$, with $p$ prime, and $m$ an integer at least $1$.

FE2OSP (Field Element to Octet String Conversion Primitive) takes as input a field element $x$ and the field size $q$. It outputs an octet string, of size dependent on $q$ only.

OS2FEP (Octet String to Field Element Conversion Primitive) takes as input an octet string (and it's size) and the field size $q$. It outputs a field element, or an error indication.

The standard distinguishes 3 cases:

  1. $m=1$, for so-called prime curves like secp256k1 or secp384r1 (by far the most common nowadays). The field element $x$ is an integer in $[0,p)$. The corresponding octet string has $\left\lceil\log_2(p-1)/8\right\rceil$ octets (bytes), representing $x$ per big-endian convention. This matches the conversions done by PKCS#1's I2OSP and OS2IP in RSA.
  2. $p=2$, for so-called binary curves like sect239k1 or sect283r1. The field element $x$ is a bitstring of $m$ bits noted $b_i$. The corresponding octet string has $\left\lceil m/8\right\rceil$ octets (bytes), with $b_0$ the least significant bit of the last octet, and the $7-(m\bmod 8)$ most significant bits of the first byte at zero.
  3. Others (covered by P1363a only). The field element $x$ is $m$ integers $a_i\in[0,p)$. The corresponding octet string has $\left\lceil\log_2(q-1)/8\right\rceil$ octets (bytes), representing the integer $\sum_{i=0}^{m-1}a_i\,p^i$ per big-endian convention. That makes 1 and 2 special cases of the more general 3.

In all cases the multiplicative neutral of the field ( $1$ ) is represented by $\left\lceil\log_2(q-1)/8\right\rceil$ octets (bytes), with the last octet 01h and all the others 00h.

Per my review of drafts P1363-D13 (1999) and P1363a-D12 (2003), the differences with the modern SEC1-v2's Field-Element-to-Octet-String Conversion and Octet-String-to-Field-Element Conversion are minimal:

  • only P1363a covers case 3.
  • P1363 names bytes $M_i$ with $M_0$ last/right. SEC1 reverses that notation (and correspondingly changes the formulas), which is more natural to programmers which see index zero as first/left. That does not change the octet string.
  • OS2FEP's "error" is Octet-String-to-Field-Element Conversion's "invalid".
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.