6.2. IEEE Standards

In this section, we outline the first three of the drafts from IEEE, shown in Table 6.1. At the time of writing this book, these are the latest versions of the drafts available from IEEE. In future, these may be superseded by newer documents. We urge the reader to visit the web-site http://grouper.ieee.org/groups/1363/ for more up-to-date information. Also see the standard IEEE 1363–2000: Standards Specifications for Public-key Cryptography [134].

Table 6.1. IEEE drafts on public-key cryptography

Draft	Date	Description
P1363 / D13	12 November 1999	Traditional public-key cryptography based on IFP, DLP and ECDLP
P1363a/D12	16 July 2003	Additional techniques on traditional public-key cryptography
P1363.1/D4	7 March 2002	Lattice-based cryptography
P1363.2/D15	25 May 2004	Password-based authentication
P1363.3/D1	May 2008	Identity-based public-key cryptography

6.2.1. The Data Types

Public-key protocols operate on data of various types. The IEEE drafts specify only the logical descriptions of these data types. The realizations of these data types should be taken care of by individual implementations and are left unspecified.

Bit strings

A bit string is a finite ordered sequence a₀a₁ . . . a_l–1 of bits, where each bit a_i can assume the value 0 or 1. The length of the bit string a₀a₁ . . . a_l–1 is l. The bit a₀ in the bit string a₀a₁ . . . a_l–1 is called the leftmost or the first or the leading or the most significant bit, whereas the bit a_l–1 is called the rightmost or the last or the trailing or the least significant bit.

The order of appearance of the bits in a bit string is important, rather than the way the bits are indexed or named. That is to say, the most and least significant bits in a given bit string are uniquely determined by their positions of occurrences in the string, and not by the way the individual bits in the string are numbered. Thus, for example, if we call the bit string 01101 as a₀a₁a₂a₃a₄, then the leading and trailing bits are a₀ and a₄ respectively. If we index the bits in the same bit string as a₂a₃a₅a₇a₁₁, the first bit is a₂ and the last bit is a₁₁. Finally, for the indexing a₅a₄a₃a₂a₁, the leftmost and rightmost bits are a₅ and a₁ respectively.

Octet strings

Though bits are the basic building blocks in computer memory, programs typically access memory in groups of 8 bits, known as octets. Thus, an octet is a bit string of length 8 and can have one of the 256 values 0000 0000 through 1111 1111. It is convenient to write an octet as a concatenation of two hexadecimal digits, the first (resp. second) one corresponding to the first (resp. last) 4 bits in the octet being treated as an 8-bit integer in base 2. For example, the octet 0010 1011 is represented by 2b. It is also often customary to treat an octet a₀a₁ . . . a₇ as the integer (between 0 and 255, both inclusive) whose binary representation is a₀a₁ . . . a₇.

An octet string is a finite ordered sequence of octets. The length of an octet string is the number of octets in the string. The leftmost (or first or leading or most significant) and the rightmost (or last or trailing or least significant) octets in an octet string are defined analogously as in the case of bit strings. These octets are dependent solely on their positions in the octet string and are independent of how the individual octets in the octet string are numbered.

Integers

Integers are the whole numbers 0, ±1, ±2, . . . . For cryptographic applications, one typically considers only non-negative integers. Integers used in cryptography may have binary representations requiring as many as several thousand bits.

Prime finite fields

Let p be a prime (typically, odd). The elements of are represented as integers 0, 1, . . . , p – 1 under the standard way of associating the integer with the congruence class [a]_p in . Arithmetic operations in are the corresponding integer operations modulo the prime p.

Finite fields of characteristic 2

The elements of the field are represented as bit strings of length m. In order to provide the mathematical interpretation of these bit strings, we recall that is an m-dimensional -vector space. Let β₀, . . . , β_m–1 be an ordered basis of over . The bit string a₀ . . . a_m–1 is to be identified with the element a₀β₀ + · · · + a_m–1β_m–1, where the bit a_i represents the element [a_i]₂ of . Selection of the basis β₀, . . . , β_m–1 renders a complete meaning to this representation and determines how arithmetic operations on these elements are to be performed. The following two cases are recommended.

For the polynomial-basis representation, one chooses an irreducible polynomial of degree m and represents as . Letting x denote the canonical image of X in one chooses the ordered basis β₀ = x^m–1, β₁ = x^m–2, . . . , β_m–1 = 1. Arithmetic operations in under this representation are those of followed by reduction modulo the defining polynomial f(X). Choice of the irreducible polynomial f(X) is left unspecified in the IEEE drafts.

For the normal-basis representation, one selects an element which is normal over (see Definition 2.60, p 86), and takes the ordered basis β₀ = θ = θ²⁰, β₁ = θ²¹, β₂ = θ²², . . . , β_m–1 = θ^2m–1. Arithmetic in is carried out as explained in Section 2.9.3.

The IEEE draft P1363a also specifies a composite-basis representation of elements of , provided that m is composite. Let m = ds with 1 < d < m. One chooses an (ordered) polynomial or normal basis γ₀, γ₁, . . . , γ_s–1 of over . An element of is of the form a₀γ₀ + a₁γ₁ + · · · + a_s–1γ_s–1 and is represented by a₀a₁ . . . a_s–1, where each a_i, being an element of , is represented by a bit string of length d. The interpretation of the representation of a_i is dependent on how is represented. One can use a polynomial- or normal-basis representation of (over ), or even a composite-basis representation of over , if d happens to be composite with a non-trivial divisor d′.

Extension fields of odd characteristics

A non-prime finite field of odd characteristic is one with cardinality p^m for some odd prime p and for some , m > 1. The field is represented as , where is an irreducible polynomial of degree m. An element of is then of the form α = a_m–1x^m–1 + · · · + a₁x + a₀, where x := X + 〈f(X)〉 and where each a_i is an element of , that is, an integer in the range 0, 1, . . . , p – 1. The element α is represented as an integer by substituting p for x, that is, as the integer (see the packed representation of Exercise 3.39). In order to interpret an integer between 0 and p^m – 1 as an element of , one has to expand the integer in base p.

* Elliptic curves

An elliptic curve defined over a finite field is specified by two elements a, . Depending on the characteristic of this pair defines the following curves.

If char , 3, then 4a³ + 27b² must be non-zero in and the equation of the elliptic curve is taken to be Y² = X³ + aX + b.

For char , we must have b ≠ 0 in and we use the non-supersingular curve Y² + XY = X³ + aX² + b. Because of the MOV attack (Section 4.5.1), supersingular curves are not recommended for cryptographic applications.

Finally, if has characteristic 3, then both a and b must be non-zero in and the elliptic curve Y² = X³ + aX² + b is specified by (a, b).

* Elliptic curve points

A point on an elliptic curve defined over can be represented either in compressed or in uncompressed form. In the uncompressed form, one represents P as the pair (h, k) of elements of . The compressed form can be either lossy or lossless. In the lossy compressed form, P is represented by its X-coordinate h only. Such a representation is not unique in the sense that there can be two points on the elliptic curve with the same X-coordinate h. In applications where Y -coordinates of elliptic curve points are not utilized, such a representation can be used. In the lossless compressed form, one represents P as . There are two solutions (perhaps repeated) for Y for a given value h of X. The bit specifies which of these two values is represented. Depending on how the bit is computed, we have two different lossless compressed forms.

The LSB compressed form is applicable for odd prime fields or fields of even characteristic. For , the bit is taken to be the least significant (that is, rightmost) bit of k (treated as an integer). For , we have , if h = 0, whereas if h ≠ 0, then is the least significant bit of the element kh^–1 treated as an integer via the FE2I conversion primitive described in Section 6.2.2.

The SORT compressed form is used for q = p^m, m > 1. Let P′ = (h, k′) be the opposite of P = (h, k), that is, One converts k and k′ to integers and using the FE2I primitive and sets .

One may also go for a hybrid representation of the elliptic curve point P = (h, k), in which information for both the compressed and the uncompressed representations for P are stored, that is, P is stored as with computed by one of the methods (LSB or SORT) described above.

* Convolution polynomial rings

For NTRU public-key cryptosystems, we work in the ring . We denote as usual. An element of R is a polynomial a(x) = a₀ + a₁x + a₂x² + · · · + a_n–1x^n–1 with , and is represented by the ordered n-tuple of integers (a₀, a₁, . . . , a_n–1). Addition (resp. subtraction) in R is simply component-wise addition (resp. subtraction), whereas multiplication of a(x) = a₀ + a₁x + · · · + a_n–1x^n–1 and b(x) = b₀ + b₁x + · · · + b_n–1x^n–1 gives c(x) = c₀ + c₁x + · · · + c_n–1x^n–1, where a_jb_k (see Section 5.2.8). The IEEE draft P1363.1 designates elements of R as ring elements.

It is customary to deal with polynomials in R with small coefficients. If all the coefficients of are known to be from {0, 1}, it is convenient to represent a(x) as the bit string a₀a₁ . . . a_n–1 instead of as an n-tuple of integers. In this case, a(x) is called a binary ring element or simply a binary element.

6.2.2. Conversion Among Data Types

The IEEE drafts P1363 and P1363.1 specify algorithms for converting data among the formats discussed above. The standardized data conversion primitives are summarized in Figure 6.1. Though these drafts support elliptic curve cryptography, it is not specified how data representing elliptic curves can be converted to data of other types (like octet strings and bit strings).

We now provide a brief description of the data conversion primitives at a logical level. The implementation details depend on the representations of the data types and are left out here.

Converting bit strings to octet strings (BS2OS)

A bit string a₀a₁ . . . a_l–1 can be broken up in groups of eight bits and packed into octets. But we run with difficulty, if the length of the input bit string is not an integral multiple of 8. We have to add extra bits in order the make the length of the augmented bit string an integral multiple of 8. This can be done is several ways and in this context a standard convention needs to be adopted. The IEEE drafts prescribe the following rules:

In order to see what these rules mean, let a₀a₁ . . . a_l–1 be a bit string of length l to be converted to the octet string A₀A₁ . . . A_d–1. The length of the output octet string must be d = ⌈l/8⌉. 8d – l zero bits should be added to the left of the input bit string in order to create the augmented bit string 0 . . . 0a₀a₁ . . . a_l–1 whose length is 8d. Now, we start from the left and pack blocks of consecutive eight bits in A₀, A₁, . . . , A_d–1. Thus, we have A₀ = 0 . . . 0a₀ . . . a_k–1, A₁ = a_k . . . a_k+7, . . . , A_d–1 = a_k+8(d–2) . . . a_k+8(d–2)+7, where k = 8 – (8d – l). Note that if l is already a multiple of 8, then 8d – l = 0, that is, no extra bits need to be added.

As an example, consider the input bit string 01110 01101011 of length 13. The output octet string should be of length ⌈13/8⌉ = 2. Padding gives the augmented bit string 00001110 01101011. The first octet in the output octet string will then be 00001110, that is, 0e; and the second octet will be 01101011, that is, 6b.

Converting octet strings to bit strings (OS2BS)

The OS2BS primitive is designed to ensure that if we convert an octet string generated by BS2OS, we should get back the original bit string (that is, the input to BS2OS) with which we started. Suppose that we want to convert an octet string A₀A₁ . . . A_d–1. Let us write the bits of A_i as a_i,0a_i,1 . . . a_i,7. The desired length l of the output bit string has to be also specified. If d ≠ ⌈l/8⌉, the procedure OS2BS reports error and stops. If d = ⌈l/8⌉, we consider the bit string

a_0,0a_0,1 . . . a_0,7a_1,0a_1,1 . . . a_1,7 . . . a_d–1,0a_d–1,1 . . . a_d–1,7

of length 8d. If the leftmost 8d – l bits of this flattened bit string are not all zero, OS2BS should quit after reporting error. Otherwise, the trailing l bits of the flattened bit string is returned.

The reader can check that when 0e 6b and l = 13 are input to OS2BS, it returns the bit string 01110 01101011. (See the example in connection with BS2OS.) Notice also that for this input octet string, OS2BS reports error if and only if a value l ≥ 17 or l ≤ 11 is supplied as the desired length of the output bit string.

Converting integers to bit strings (I2BS)

Let a non-negative integer n be given. The I2BS primitive outputs a bit string of length l representing n. If n ≥ 2^l, this conversion cannot be done and the primitive reports error and quits. If n < 2^l, we write the binary representation of n as

n = a_l–12^l–1 + a_l–22^l–2 + · · · + a₁2 + a₀ with .

Treating each a_i as a bit^[2], I2BS returns the bit string a_l–1a_l–2 . . . a₁a₀. One or more leading bits of the binary representation of n may be zero. There is no limit on how many leading zero bits are allowed during the conversion. In particular, the integer 0 gets converted to a sequence of l zero bits for any value of l supplied.

^[2] Each a_i is logically an integer which happens to assume one of two possible values: 0 and 1. A bit, on the other hand, is a quantity that can also assume only two possible values. Traditionally, the values of a bit are also denoted by 0 and 1. But one has the liberty to call these values off and on, or false and true, or black and white, or even armadillo and platypus. To many people, bit is an abbreviation for binary digit which our a_is logically are. To others, binit is a safer and more individualistic acronym for binary digit. For I2BS, we identify the two concepts.

A request to I2BS to convert n = 2357 = 2¹¹ + 2⁸ + 2⁵ + 2⁴ + 2² + 2⁰ with l = 12 returns 1001 00110101, one with l = 18 returns 00 00001001 00110101 and finally one with l ≤ 11 reports failure. Note that for neater look we write bit strings in groups of eight and grouping starts from the right. This convention reflects the relationship between bit strings and octet strings, as mentioned above.

Converting bit strings to integers (BS2I)

The primitive BS2I converts the bit string a₀a₁ . . . a_l–1 to the integer a₀2^l–1 + a₁2^l–2 + · · · + a_l–22 + a_l–1, where we again identify a bit with an integer (or a binary digit). As an illustrative example, the bit string 1001 00110101 (or 00 00001001 00110101) gets converted to the integer 2¹¹ + 2⁸ + 2⁵ + 2⁴ + 2² + 2⁰ = 2357. The null bit string (that is, the one of zero length) is converted to the integer 0.

Converting integers to octet strings (I2OS)

In order to convert a non-negative integer n to an octet string of length d, we write the base-256 expansion of n as

n = A_d–1256^d–1 + A_d–2256^d–2 + · · · + A₁256 + A₀,

where each and can be naturally identified with an octet. I2OS returns the octet string A_d–1A_d–2 . . . A₁A₀. Note that the above representation of n to the base 256 is possible if and only if n < 256^d. If n ≥ 256^d, I2OS should return failure. Like bit strings, an arbitrary number of leading zero octets are allowed.

Consider the integer 2357 = 9 × 256 + 53. The two-digit hexadecimal representations of 9 and 53 are 09 and 35 respectively. Thus, a call of I2OS on this n with d = 3 (resp. d = 2, resp. d = 1) returns 00 09 35 (resp. 09 35, resp. failure).

Converting octet strings to integers (OS2I)

Let an octet string A₀A₁ . . . A_d–1 be given. Each A_i can be identified with a 256-ary digit. OS2I returns the integer A₀256^d–1 + A₁256^d–2 + · · · + A_d–2256 + A_d–1. If d = 0, the integer 0 should be output.

Converting field elements to octet strings (FE2OS)

In the IEEE P1363 jargon, a field element is an element of the finite field , where q is a prime or an integral power of a prime. We want to convert an element to an octet string. Depending on the value of q, we have two cases:

If char is odd, β is represented as an integer in {0, 1, . . . , q – 1}. FE2OS converts β to an octet string of length ⌈log₂₅₆ q⌉ by calling the primitive I2OS.

If q = 2^m, β is represented as a bit string of length m. The primitive BS2OS is called to convert β to an octet string.

Converting octet strings to field elements (OS2FE)

Assume that an octet string is to be converted to an element of the finite field . Again we have two possibilities depending on q.

If is of odd characteristic, the primitive OS2I is called to convert the given octet string to an integer. This integer is returned as the field element.

If q = 2^m, one calls the primitive OS2BS with the given octet string and with the length m supplied as inputs. The resulting bit string is returned by OS2FE. If OS2BS reports error, so should do OS2FE too.

Converting field elements to integers (FE2I)

Let and the integer equivalent of β be sought for. If q is odd, then β is already represented as an integer (in {0, 1, . . . , q – 1}) and is itself output. If q = 2^m, one first converts β to an octet string by FE2OS and subsequently converts this octet string to an integer by calling the primitive OS2I.

* Converting elliptic curve points to octet strings (EC2OS)

The point at infinity (on an elliptic curve over ) is defined by an octet string comprising a single zero octet only. So let P = (h, k) be a finite point. The EC2OS primitive produces an octet string PO = P C ‖ H ‖ K which is the concatenation of a single octet PC with octet strings H and K representing h and k respectively. The values of PC and K depend on the type of compression used. One has , where

S = 1 if and only if the SORT compression is used.

U = 1 if and only if uncompressed or hybrid form is used.

C = 1 if and only if compressed or hybrid form is used.

= if compression is used, it is 0 otherwise.

The first four bits of PC are reserved for (possible) future use and should be set to 0000 for this version of the standard. H is the octet string of length ⌈log₂₅₆ q⌉ obtained by converting h using FE2OS. If the compressed form is used, K is the empty octet string, whereas if uncompressed or hybrid form is used, we have K = FE2OS(k, ⌈log₂₅₆ q⌉). Finally, for the lossy compression we have PC = 0000 0001, H = FE2OS(h, ⌈log₂₅₆ q⌉) and K is empty. Table 6.2 summarizes all these possibilities. Here, l := ⌈log₂₅₆ q⌉, and p is an odd prime.

Table 6.2. The EC2OS primitive

Representation	PC	H	K	q
uncompressed	0000 0100	FE2OS(h, l)	FE2OS(k, l)	All
LSB compressed		FE2OS(h, l)	Empty	p, 2m
LSB hybrid		FE2OS(h, l)	FE2OS(k, l)	p, 2m
SORT compressed		FE2OS(h, l)	Empty	2m, pm
SORT hybrid		FE2OS(h, l)	FE2OS(k, l)	2m, pm
lossy compression	0000 0001	FE2OS(h, l)	Empty	All
point at infinity	0000 0000	Empty	Empty	All

* Converting octet strings to elliptic curve points (OS2EC)

The OS2EC data conversion primitive takes as input an octet string PO, the length l = ⌈log₂₅₆ q⌉ and the method of compression. If PO contains only one octet and that octet is zero, is output. Otherwise, the elliptic curve point P = (h, k) is computed as follows. OS2EC decomposes PO = PC ‖ H ‖ K, with PC the first octet and with H an octet string of length l. If PC does not match with the method of compression, OS2EC returns error. Otherwise, it uses OS2FE to compute the field element h. If no or hybrid compression is used, the Y -coordinate k is also computed using OS2FE on K. If (h, k) is not a point on the elliptic curve, error is reported. For the LSB or SORT compression, the Y -coordinate is computed using h and . If the hybrid scheme is used and , OS2EC halts after reporting error. If all computations are successful till now, the point (h, k) is output.

Note that the checks for (h, k) being on the curve or for the equality are optional and may be omitted. For the lossy compression scheme, the Y -coordinate k is not necessarily uniquely determined from the input octet string PO. In that case, any of the two possibilities is output.

* Converting ring elements to octet strings (RE2OS)

Ring elements are elements of the convolution polynomial ring and can be identified as polynomials with integer coefficients and of degrees < n. The element (where ) is represented by the n-tuple of integers (a₀, a₁, . . . , a_n–1). The IEEE draft P1363.1 assumes that the coefficients a_i are available modulo a positive integer β ≤ 256. But then each a_i is an integer in {0, 1, . . . , β – 1} and can be naturally encoded by a single octet. RE2OS, upon receiving a(x) as input, outputs the octet string a₀a₁ . . . a_n–1 of length n.

An example: Let n = 7 and β = 128. The ring element a(x) = 2 + 11x + 101x³ + 127x⁴ + 71x⁵ = (2, 11, 0, 101, 127, 71, 0) is converted to the octet string 02 0b 00 65 7f 47 00.

* Converting octet strings to ring elements (OS2RE)

Let an octet string a₀a₁ . . . a_n–1 of length n be given, which we want to convert to an element of . Once again a modulus β ≤ 256 is assumed, so that each octet a_i can be viewed as an integer reduced modulo β. Making the natural identification of a_i with an integer, the polynomial is output. Thus, for example, the octet string 02 0b 00 65 7f 47 00 gets converted to the ring element 2 + 11x + 101x³ + 127x⁴ + 71x⁵.

* Converting ring elements to bit strings (RE2BS)

The RE2BS primitive assumes that the modulus β is a power of 2, that is, β = 2^t for some positive integer t ≤ 8. Let a ring element be given, where each . One applies the I2BS primitive on each a_i to generate the bit string a_i,0a_i,1 . . . a_i,t–1 of length t. The concatenated bit string

a_0,0a_0,1 . . . a_0,t–1 a_1,0a_1,1 . . . a_1,t–1 . . . a_n–1,0a_n–1,1 . . . a_n–1,t–1

of length nt is then returned by RE2BS.

As before, take the example of n = 7, β = 128 = 2⁷ (so that t = 7) and a(x) = 2 + 11x + 101x³ + 127x⁴ + 71x⁵ = (2, 11, 0, 101, 127, 71, 0). The coefficients 2, 11, 0, . . . should first be converted to bit strings of length 7 each, that is, 2 gives 0000010, 11 gives 0001011 and so on. Thus, the bit string output by RE2BS will be 0000010 0001011 0000000 1100101 1111111 1000111 0000000. Note that here we have shown the bits in groups of 7 in order to highlight the intermediate steps (the outputs from I2BS). With the otherwise standard grouping in blocks of 8, the output bit string looks like 0 00001000 01011000 00001100 10111111 11100011 10000000 and hence transforms to the octet string 00 08 58 0c bf d3 80 by an invocation of BS2OS. This example illustrates that RE2BS followed by BS2OS does not necessarily give the same output as the direct conversion RE2OS, even when every underlying parameter (like β) remains unchanged.

* Converting bit strings to ring elements (BS2RE)

Once again we require the modulus β to be a power 2^t of 2. Let a bit string a₀a₁ . . . a_l–1 of length l be given, and we want to compute the ring element a(x) equivalent to this. If l is not an integral multiple of t, the algorithm should quit after reporting error. Otherwise we let l = nt for some , and repeatedly call the BS2I primitive on the bit strings a₀a₁ . . . a_t–1, a_ta_t+1 . . . a_2t–1, . . . , a_nt–ta_nt–t+1 . . . a_nt–1 to get the integers α₀, α₁, . . . , α_n–1 respectively. The polynomial a(x) = α₀ + α₁x + · · · + α_n–1x^n–1 is then output.

We urge the reader to verify that BS2RE with β = 128 and the bit string

0000010 0001011 0000000 1100101 1111111 1000111 0000000

as input produces the ring element .

* Converting binary elements to octet strings (BE2OS)

A binary (ring) element is an element with each . One can convert a(x) to an octet string A₀A₁ . . . A_l–1 of any desired length l as follows. We denote the bits in the octet A_i as A_i,7A_i,6 . . . A_i,0. Here, the index of the bits increases from right to left.

First we rewrite the polynomial a(x) as one of degree 8l – 1, that is, as a(x) = a₀ + a₁x + · · · + a_8l–1x^8l–1. If n ≤ 8l, this can be done by setting a_n = a_n+1 = · · · = a_8l–1 = 0. On the other hand, if n > 8l and one or more of the coefficients a_8l, a_8l+1, . . . , a_n–1 are non-zero (that is, 1), the above rewriting of a(x) cannot be done and BE2OS terminates after reporting failure.

When the above rewriting of a(x) becomes successful, one sets the bits of the output octets as A_0,0 := a₀, A_0,1 := a₁, . . . , A_0,7 := a₇, A_1,0 := a₈, A_1,1 := a₉, . . . , A_1,7 := a₁₅, A_2,0 := a₁₆, A_2,1 := a₁₇, . . . , A_2,7 := a₂₃, . . . , A_l–1,0 := a_8l–8, A_l–1,1 := a_8l–7, . . . , A_l–1,7 := a_8l–1.

As an example, take n = 20 and consider the binary element . First let l = 1. Rewriting a(x) as a polynomial of degree 7 is not possible, since the coefficients of x¹⁰ and x¹² are 1; so BE2OS outputs error in this case. If l = 2, then the output octet string will be 00000111 00010100, that is, 07 14. For l ≥ 3, the first two octets will be 07 and 14 as before, whereas the 3rd through l-th octet will be 00.

The BE2OS primitive can be quite effective for reducing storage requirements. For example, the polynomial a(x) of degree 12 of the previous paragraph, viewed as an element of , can be encoded in just two octets. Of course, by specifying l ≥ 3 one may add l – 2 trailing zero octets, if one desires. On the other hand, RE2OS requires exactly 200 octets, whereas RE2BS with β = 128 followed by BS2OS requires exactly ⌈(200 × 7)/8⌉ = 175 octets for storing the same a(x).

* Converting octet strings to binary elements (OS2BE)

Assume that an octet string A₀A₁ . . . A_l–1 of length l is given and the equivalent binary element in is to be determined. As in the case with BE2OS, we index the bits in the octet A_i as A_i = A_i,7A_i,6 . . . A_i,0. Now, consider the polynomial a(x) = a₀ + a₁x + a₂x² + · · · + a_8l–1x^8l–1, where a_8i+j = A_i,j. If n ≥ 8l, we set a_8l = a_8l+1 = · · · = a_n–1 = 0 and output the binary element . On the other hand, if n < 8l and a_n = a_n+1 = · · · = a_8l–1 = 0, then equals the polynomial a(x) and is returned. Finally, if n < 8l and if any of the coefficients a_n, a_n+1, . . . , a_8l–1 is non-zero, then OS2BE returns error.^[3]

^[3] In this case, it still makes full algebraic sense to treat a(x) as an element of R, though not in the canonical representation.

For example, assume that the octet string 07 14 is given as input to OS2BE. If n ≤ 12, the algorithm outputs error, because the polynomial a(x) in this case has degree 12. For any n ≥ 13, the binary element is returned.