US20070150794A1

Movatterモバイル変換

Info

Publication number: US20070150794A1
Application number: US10/271,945
Authority: US
Inventors: Mats Naslund; Rolf Blom
Original assignee: Individual
Current assignee: Individual
Priority date: 2002-10-17
Filing date: 2002-10-17
Publication date: 2007-06-28
Also published as: US7243292B1

Abstract

Binary data representing a code word of an error-correcting code is used for calculating a syndrome, wherein a given portion of the binary data comprises k groups of data bits and represents a field element of the finite field GF(p^k), p being an odd prime number, the field element comprising k coefficients in accordance with a polynomial basis representation, each group of data bits of the given portion representing a corresponding one of the k coefficients. The given portion is stored in a first general purpose register and is processed such that the k groups of data bits of the given portion are processed in parallel; determining whether the syndrome is equal to zero; and detecting and correcting errors in the binary data if the syndrome is not equal to zero.

Description

CROSS REFERENCE TO RELATED APPLICATIONS

The present application is related to U.S. patent application entitled “Efficient arithmetic in finite fields of odd characteristic on binary hardware”, Ser. No. ______ (Attorney Docket No. 040000-493), and to U.S. patent application entitled “Cryptography using finite fields of odd characteristic on binary hardware”, Ser. No. ______ (Attorney Docket No. 040001-177), both filed even date herewith, the disclosures of which are incorporated herein by reference in their entirety.

BACKGROUND

1. Field of the Invention

The present invention relates to methods and apparatuses for efficiently carrying out computations in finite fields of odd prime characteristic on binary hardware. The invention is particularly useful for carrying out such computations in cryptography and in error correction, but is not limited to such uses.

2. Background Information

Some Basic Aspects of Finite Fields

A finite field (also called a Galois field) is a finite algebraic structure, possessing two well-defined operations: an “addition” and a “multiplication”. A finite field with N elements exists if and only if N is the power of a prime number, i.e. N=pⁿfor some prime p=2, 3, 5, . . . such as discussed in R. Lidl and H. Niederriter,Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge, Revised ed., 1994. This field is unique up to an isomorphism and is normally denoted GF(pⁿ). For a prime p, the ground field GF(p) is simply the integers under addition and multiplication modulo p. In general, if F is a field of q=p^kelements (i.e. F=GF(p^k)), the extension field of degree l can be defined, denoted as F[t]/(f(t)), where f(t) is a polynomial of degree l, irreducible over F. This extension field may also be referred to as GF(p^lk). This then gives (the unique) finite field of q^lelements. In other words, this is the field of p^lk=pⁿelements. The number p is called the characteristic of the field. The well-known fact that the two fields of the same size are isomorphic does not necessarily mean that the mapping between the fields is trivial. However, constructions of such mappings are not necessary for the present invention and, in any event, are within the purview of one of ordinary skill in the art and are discussed in textbooks, such asIntroduction to Finite Fields and Their Applicationsreferred to above.

There are two predominant ways to represent a finite field. One representation is the normal basis representation well known to those of ordinary skill in the art and such as described inIntroduction to Finite Fields and Their Applicationsreferred to above. The main advantage with a normal basis is that it facilitates multiplying elements by themselves, i.e. squaring-type operations. The normal basis representation is not discussed further here. Some computational aspects associated with normal basis representations are discussed in U.S. Pat. No. 4,587,627 (Computational method and apparatus for finite field arithmetic), U.S. Pat. No. 4,567,600 (Method and apparatus for maintaining the privacy of digital messages conveyed by public transmission), and U.S. Pat. No. 5,854,759 (Method and apparatus for efficient finite field basis conversion), the entire contents of each of which are incorporated herein by reference.

Another representation is known as the polynomial basis representation. In this representation, field elements of GF(p^k) may be thought of as polynomials of degree at most k−1 whose coefficients are field elements of the ground field GF(p), i.e., integers in the set (0, . . . , p−1). A typical element, γ, in the field can therefore be expressed as
γ=γ_k−1t^k−1+ . . . +γ₁t+γ₀, (1)
for some integers γ_iwhere 0≦γ_i≦p−1, and where t is a formal variable. The field element γ may also be viewed as the k-dimensional vector (γ_k−1, . . . , γ₁, γ₀), and the polynomial basis representation as referred to herein is intended to encompass this view. Another aspect of the polynomial basis representation is the choice of a polynomial h(t) of degree k and irreducible over GF(p) that is utilized in multiplication of field elements. This will be discussed in greater detail below. Because any two fields of the same size are isomorphic, it does not matter which irreducible h(t) is chosen. From system point of view, h(t) is a system parameter that is agreed upon for the particular use in mind.

As noted above, an extension field of degree l over the field F=GF(p^k) can be denoted as F[t]/(f(t)) or as GF(p^lk). An element of the extension field can be viewed as a polynomial of degree at most l−1 whose coefficients are elements of GF(p^k). In other words, an element of the extension field may be viewed as a polynomial with other polynomials as field coefficients. An element γ of the extension field can be written as
γ=γ_l−1t^l−1+ . . . +γ₁t+γ₀, (2)
where each γ_jis a polynomial of degree at most k−1 having coefficients in the set (0, . . . , p−1). Thus, the polynomials γ_jcan be written as
γ_j=γ_k−1,ju^k−1+ . . . +γ_1,ju+γ_0,j (3)
where another formal variable, u, has been chosen for these polynomials to avoid confusing them with the extension-field polynomial, whose formal variable is t. This extension-field formulation using a polynomial basis representation will be used to describe the present invention.

The sum of two elements α, β in GF(p^k) is defined by simply adding the corresponding polynomials (or, equivalently, vectors):
α+β=(α_k−1+β_k−1)t^k−1+ . . . +(α₁+β₁)t+(α₀+β₀), (4)
where each (integer) coefficient (α_i+β_i) is computed modulo p. The complexity (in terms of the number of modulo-p operations) of adding two elements by directly using the definition inequation 4 above is equal to k. For example, for the finite field GF(3²) where p=3, a field element α=(2, 1) in vector notation can be written as the polynomial α=2t+1, and a field element β=(2, 2) in vector notation can be written as the polynomial β=2t+2. The sum of these field elements is (α+β)=(2+2)t+(1+2) where each coefficient is evaluated modulo 3 (mod 3). Thus, the sum reduces to (α+β)=t because 4mod 3=1 and 3mod 3=0. In vector notation, the sum is (1, 0).

The product of two field elements is defined by forming their product modulo h(t), where h(t) is a polynomial of degree k and irreducible (i.e., cannot be factored) over GF(p):
α·β=δ_2k−2t^2k−2+δ_2k−3t^2k−3+ . . . +δ₁t+δ₀modh(t) (5)
where δ_i=Σ_jα_jβ_i−jmod p. Here “mod h(t)” means taking the remainder when dividing by h(t), using standard polynomial division. This leaves the result with a degree strictly less that that of h(t), i.e. less than k, as desired. The complexity of multiplying two elements according to this definition is clearly on the order of k². Alternatively, using the Karatsuba algorithm known to those of ordinary skill in the art, multiplication can (asymptotically in k) be performed with roughly k^1.6operations, but this algorithm involves more administration of the computations. The Karatsuba algorithm is, therefore, only beneficial for large values of k, for example, k>100, as noted in §4.4.3 of D. Knuth,Seminumerical Algorithms, Vol. 2 ofThe Art of Computer Programming,2^nded, Addison-Wesley, Reading, Mass., 1981.

As an example, to multiply the field elements α=(2, 1) and β=(2, 2) of finite field GF(3²), a polynomial h(t) of degree k=2 and irreducible over GF(3) must be chosen, and thepolynomials 2t+1 and 2t+2 are then multiplied modulo h(t). An appropriate irreducible polynomial is h(t)=t²+t+2. Then, α·β=(4t²+6t+2)mod h(t)=4(t²+t+2)+2t−6=2t (because 2mod 3=2 and 6mod 3=0). Thus, α·β=2t or (2, 0) in vector notation.

For an extension field (also referred to as a composite field), the formulas for addition and multiplication are the same. However, it is recognized that all coefficient-wise operations are carried out over the ground field, which may itself involve polynomial arithmetic.

Subtraction in a finite field can be done by simply noting that in the field GF(p), the negative of an element x is p−x. Thus, an element x can be replaced with p−x to obtain the negative, and then normal coefficient-wise addition may be carried out to obtain the subtraction. Division can be carried out by multiplying by the inverse as known to those skilled in the art.

Conventional Utilization of Finite Fields

The use of finite fields is central to many applications. In particular, for communication purposes, finite fields are very useful. For example, by embedding messages into a finite field, one can transmit messages so that errors introduced by the transmission medium can be corrected at the receiver end. This is the principle behind error correcting codes. In addition, finite fields can be used to achieve protection (confidentiality, integrity, origin authentication, and non-repudiation) for messages by means of encryption, message authentication, and digital signatures.

To be useful, these coding and encryption operations involving finite fields must be as efficient as possible, especially if the computations are done on a lightweight platform such as a mobile phone or other handheld device. For instance, many cryptographic methods use the following exponentiation operation
exp_g(x)=g·g . . . g=g^x (6)

- (x times)
  where g is an element in the multiplicative group of a finite field, x is an integer and “·” denotes multiplication in the finite field. The reason for using the exp_g(x) function is that exp_g(x) can be computed with only approximately (log₂x)³field multiplications in the ground field, but no efficient (i.e. polynomial-time in log₂x) algorithm exists for the inverse transformation—finding x from exp_g(x). The latter is known as the discrete logarithm problem. In other words, exp_g(x) is a strong candidate for a so-called one-way function—a function easy to compute, but hard to invert. The discrete logarithm problem is well known to those of ordinary skill in the art and is discussed, for example, inHandbook of Applied Cryptographyby A. Menezes, P. van Oorschot, and S. A. Vanstone, CRC Press, Boca Raton, Fla., 1997.

However, on a computationally weak platform, even (log₂x)³multiplications may be computationally excessive, and for currently recommended field sizes (e.g., key size) such computations might in many situations take about 30 seconds, for example. A conventional way to improve performance is to restrict the computations to binary finite fields (fields of characteristic two). Restricting computations to binary finite fields improves performance because most available hardware is binary in nature (e.g., CPUs, etc.). Therefore, field operations can be composed of elementary binary operations, such as bitwise XORs, which are directly and efficiently supported by the hardware.

In addition, methods have been devised to improve efficiency by carrying out computations using a binary extension field whose extension degree is a composite number (non-prime), as disclosed in E. De Win, A. Bosselaers, S. Vanderberghe, P De Gersem, and J. Vandewalle, “A fast Software Implementation for Arithmetic Operations in GF(2ⁿ)”, Advances in Cryptology, Proceedings of Asiacrypt'96, LNCS 1163, Springer-Verlag, Berlin, 1996, pp. 65-76 (hereinafter “De Win et al.”). In the De Win et al. method, a standard binary hardware architecture is assumed to be able to perform operations (normal arithmetic and bit-operations) on k bit quantities (i.e., the word length is k bits). It is further noted that for an even characteristic (binary) field where p=2, forming remainders modulo 2 can be done by a simple bit operation.

When n is not a prime number, the finite field GF(2ⁿ) is viewed as a “non-trivial” extension of degree l over GF(2^k), where n=lk, and l,k>1. Thus, an element in the field can be written as
γ=γ_l−1t^l−1+ . . . +γ₁t+γ₀, (7)
where each γ_iis an element of GF(2^k). Adding field elements α and β in this representation can be done by carrying out the operation
α+β=(α_l−1+β_l−1)t^l−1+ . . . +(α₁+β₁)t+(α₀+β₀). (8)
Since α_i, β_iare elements of GF(2^k), their sum, α_i+β_ican be computed as the bitwise XOR between the α_iand β_i. Thus, if k is small enough to fit in a hardware register (typically k≦32), k additions can be performed in parallel using only one operation in hardware, and a factor of k is gained in the speed of executing the addition.

Multiplication using the De Win et al. method is carried out noting that the multiplicative group of GF(2^k) (or any other finite field) is always cyclic, meaning that there is an element g in GF(2^k) so that any non-zero element, α_j, in the field can be written as α_j=g^xfor someinteger 0≦x<2^k−1 (i.e., x is the discrete logarithm of α_j, and g is known as the generator). If k is moderately large (e.g., k≦16), the generator g can be found by exhaustive search. Also, in this case (e.g., k≦16), a table, ANTILOG{x}, of g^xfor all x where 0≦x<2^k−1 can be formed. In addition, a table for the discrete logarithms, DLOG{α_j}, for all non-zero α_jin the field GF(2^k) can also be formed. That is,
ANTILOG{DLOG{α_j}}=α_j (9)
and
DLOG{ANTILOG{x}}=x (10)
for all such α_jand x. The product of α and β in GF(pⁿ) is computed in accordance with the equation
α·β=δ_2l−2t^2l−2+δ_2l−3t^2l−3+ . . . +δ₁t+δ₀modf(t) (11)
where δ_i=Σ_jα_jβ_i−jis computed as a sum of products, and all operations take place in the field GF(2^k). Given that g^xg^y=g^x+y, each term α_jβ_i−jcan be computed by three table look-ups in the above-noted pre-computed tables in accordance with the equation
α_jβ_i−j=ANTILOG{DLOG{α_j}+DLOG{β_i−j} mod(2^k−1)}. (12)
The memory requirement is about k·2^k−2bytes, and the number of operations to perform the multiplication is on the order of l²=(n/k)². A factor of k²is thus gained in speed. The approach requires pre-computation of the tables and requires memory to store those tables. If k is moderate (e.g., k≦16), it is feasible to use this method using on the order of 2^kpre-computation operations.

In contrast, for finite fields of odd characteristic p where p is an odd prime, the situation is more complicated than for binary finite fields because the basic operations needed for odd-characteristic finite fields are not modulo-2 operations (bit-operations) but, rather, modulo-p operations. The De Win et al. addition method as described therein, for example, is not applicable to finite fields of odd characteristic (p=3, 5, 7, . . . ), and no similar method for finite fields of odd characteristic has been reported to the knowledge of Applicants. Carrying out odd-characteristic finite-field computations in a conventional manner involves modular arithmetic, which requires long divisions. Most hardware supports modular arithmetic, but only on a word-oriented level. Thus, the above-noted optimizations for computations involving binary finite fields are not realized for computations involving odd-characteristic finite fields.

For the above noted reasons, binary finite fields have been the most widely used finite fields in error correction and cryptography. However, Applicants note that restricting such computations to binary fields can have drawbacks. For example, algorithms for inverting the exp_g(x) function noted above are more efficient if the field has characteristic two (a binary field) than if the field has a characteristic that is odd. Thus, the cryptographic strength of the function exp_g(x) may be expected to be less for binary fields than for general odd-characteristic finite fields. Indeed, it has recently been suggested that implementing cryptography using finite fields of odd characteristic and composite degree can provide enhanced cryptographic security compared to other cryptographic approaches involving finite fields, and that the gains in cryptographic security can be expected to outweigh the computational costs of such computations (see K. Rubin and A. Silverberg, “Supersingular Abelian Varieties in Cryptology”, Crypto 2002, Lecture Notes in Computer Science, Vol. 2442, ed. M. Jung, Springer-Verlag, Berlin, pp. 336-353, 2002). In addition, in the case of binary fields of composite degree where the optimizations described in the De Win et al. article referred to above are applicable, attacks on elliptic curve cryptosystems over such fields have been recently found as described in N. P. Gaudry, F. Hess, and N. P. Smart “Constructive and Destructive Facets of Weil Descent on Elliptic Curves”, Technical Report CSTR-00-016, Department of Computer Science, University of Bristol, October 2000, and in N. P. Smart, “How secure are elliptic curves over composite extension fields?”, Technical Report CSTR-00-017, Department of Computer Science, University of Bristol, November 2000. Thus, it is advisable to avoid such binary fields of composite degree for encryption. These attacks are much less effective if the finite field has odd characteristic (even if the degree is non-prime), so they are not a relevant threat in that case. However, as noted above, utilizing conventional computational methods involving odd-characteristic finite fields requires sacrificing the computational optimizations that would otherwise be gained using a binary finite field structure.

SUMMARY OF THE INVENTION

Applicants have recognized a need for a computational approach that enables speeding up computations involving basic finite field operations (e.g., addition, multiplication, etc.) for non-binary finite fields even if the available hardware is binary in nature and that reduces need for special modulo-p hardware. In addition, Applicants have recognized a need for a computational approach for non-binary finite fields that utilizes register space more efficiently than conventional methods. For example, it is possible to perform conventional modulo-p arithmetic using a 32-bit CPU, but if p is small (e.g., p=3 or p=7) it is inefficient to devote 32 bits of register space for the operations since the involved quantities (field element coefficients) will only have 2 or 3 significant bits. Applicants have recognized that it would be desirable to make more efficient use of the available register space given that the numbers involved are quite small. The present invention fulfils these and other needs and provides advantages as will become apparent to those of ordinary skill in the art upon reading the detailed description in conjunction with the accompanying drawings.

It should be emphasized that the terms “comprises” and “comprising”, when used in this specification, are taken to specify the presence of stated features, integers, steps or components; but the use of these terms does not preclude the presence or addition of one or more other features, integers, steps, components or groups thereof.

In one exemplary aspect of the invention, there is provided an error-correction apparatus comprising an input device (e.g., an input/output device) and a processing unit configured to execute a plurality of operations on binary data intended to represent an allowed code word of an error-correcting code to detect and correct errors in the binary data. A portion of the binary data comprises k groups of data bits and represents a field element of a base field GF(p^k), the field element of the base field GF(p^k) having k base coefficients in accordance with a polynomial basis representation. The value p is an odd prime number. Each group of data bits represents a corresponding one of the k coefficients. The portion of the binary data is stored in a register and is processed by the processing unit such that the k groups of data bits are processed in parallel during at least some of said plurality of operations.

In another exemplary aspect of the present invention, there is provided a method of error-correction. The method comprises receiving binary data intended to represent an allowed code word of an error-correction code and calculating a syndrome based upon the binary data, wherein a given portion of the binary data comprises k groups of data bits and represents a field element of the finite field GF(p^k). The value p is an odd prime number, and the field element comprises k coefficients in accordance with a polynomial basis representation, each group of data bits of the given portion representing a corresponding one of the k coefficients. The given portion of the binary data is stored in a first register and is processed such that the k groups of data bits of the given portion are processed in parallel. The method further comprises determining whether the syndrome is equal to zero. The method also comprises detecting and correcting errors in the binary data if the syndrome is not equal to zero. The detecting and correcting can be carried out by processing an error-containing portion of the binary data such that k groups of data bits of the error-containing portion of the binary data are processed in parallel. In another aspect of the present invention, there is provided an apparatus comprising a memory and a processing unit coupled to the memory for executing the steps of the method. In another aspect of the present invention, there is provided a computer-readable carrier adapted to program a computer to execute the steps of the method. Exemplary forms of a computer-readable carrier include solid-state memory, magnetic disk, optical disk or modulated wave containing an appropriate set of computer instructions that would cause a processor to carry out the above-noted steps. A modulated wave can be, for example, a radio frequency modulated wave, an audio frequency modulated wave, an optical frequency modulated wave, or a modulated binary bit stream that can be downloaded via a network connection or modem.

As used herein, the terminology “in accordance with a polynomial basis representation” is intended to include any representation mathematically equivalent to a polynomial basis representation including, for example, a vector representation.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram illustrating a system for carrying out computations involving field elements of an odd-characteristic finite field according to an exemplary aspect of the present invention.

FIG. 2A is a schematic illustration of a hardware register with a data storage scheme configured in a single-guard-bit representation according to an exemplary aspect of the present invention for the example of GF(3¹⁰).

FIG. 2B is another schematic illustration of a hardware register with a data storage scheme configured in a single-guard-bit representation according to an exemplary aspect of the present invention for the example of GF(7⁵).

FIG. 2C is a schematic illustration of a hardware register with a data storage scheme configured in a multiple-guard-bit representation according to an exemplary aspect of the present invention for the example of GF(3⁸).

FIG. 3 is a flow diagram illustrating a method of processing binary data representing field elements of an odd-characteristic finite field according to an exemplary aspect of the present invention.

FIG. 4 is a flow diagram illustrating a method of processing binary data in order to determine the sum of two field elements where p=2^m−1 in accordance with the method illustrated inFIG. 3 according to an exemplary aspect of the present invention.

FIG. 5 is a schematic illustration of register contents for an example of addition in GF(3¹⁰) in accordance with the method illustrated inFIG. 4.

FIG. 6 is a functional block diagram of a hardware apparatus for carrying out computations involving field elements of an odd-characteristic finite field where p=2^m−1 according to an exemplary aspect of the present invention.

FIG. 7 is another functional block diagram of a hardware apparatus for carrying out computations involving field elements of an odd-characteristic finite field where p=2^m−1 according to another exemplary aspect of the present invention.

FIG. 8A is a schematic illustration of an exemplary guard-bit insertion circuit for use in conjunction with the apparatus illustrated inFIG. 7 according to an exemplary aspect of the present invention.

FIG. 8B is a schematic illustration of an exemplary guard-bit removal circuit for use in conjunction with the apparatus illustrated inFIG. 7 according to an exemplary aspect of the present invention.

FIG. 9 is a flow diagram illustrating a method of processing binary data representing field elements of an odd-characteristic finite field in order to determine the product of those elements according to an exemplary aspect of the present invention.

FIG. 10A is a schematic illustration of a DLOG look-up table for use in the method illustrated inFIG. 9 according to an exemplary aspect of the present invention.

FIG. 10B is an indexing table that reflects the finite-field elements a(t) and corresponding generator powers n corresponding to the binary information illustrated inFIG. 10A.

FIG. 11A is a schematic illustration of an ANTILOG look-up table for use in the method illustrated inFIG. 9 according to an exemplary aspect of the present invention.

FIG. 11B is an indexing table that reflects the finite-field elements a(t) and corresponding generator powers n corresponding to the binary information illustrated inFIG. 11A.

FIG. 12 is a functional block diagram illustrating a hardware apparatus for carrying out multiplication of field elements of an odd-characteristic finite field according to an exemplary aspect of the present invention.

FIG. 13 is a schematic illustration of a compression operation for compressing binary data stored in a register in a multiple-guard-bit representation according to an exemplary aspect of the present invention.

FIG. 14 is a flow diagram illustrating a method of processing binary data in order to determine the sum of two field elements where p=2^m+1 in accordance with the method illustrated inFIG. 3 according to an exemplary aspect of the present invention.

FIG. 15 is a schematic illustration of register contents for an example of addition in GF(5⁶) in accordance with the method illustrated inFIG. 14.

FIG. 16 is a functional block diagram of a hardware apparatus for carrying out computations involving field elements of an odd-characteristic finite field where p=2^m+1 according to an exemplary aspect of the present invention.

FIG. 17 is another functional block diagram of a hardware apparatus for carrying out computations involving field elements of an odd-characteristic finite field where p=2^m+1 according to another exemplary aspect of the present invention.

FIG. 18 is a flow diagram illustrating a method of processing binary data in order to determine the sum of two field elements where p=2^m−d and d≦(2^m+1)/3 in accordance with the method illustrated inFIG. 3 according to an exemplary aspect of the present invention.

FIG. 19 is a flow diagram illustrating a method of processing binary data in order to determine the sum of two field elements where p=2^m−d and (2^m+1)/3<d<2^m−1 in accordance with the method illustrated inFIG. 3 according to an exemplary aspect of the present invention.

FIG. 20 is a flow diagram illustrating a method of processing binary data in order to determine the sum of two field elements where p=2^m+d and d≦p/6 in accordance with the method illustrated inFIG. 3 according to an exemplary aspect of the present invention.

FIG. 21 is a flow diagram illustrating a method of processing binary data in order to determine the sum of two field elements where p=2^m+d and p/6<d<2^m−1 in accordance with the method illustrated inFIG. 3 according to an exemplary aspect of the present invention.

FIG. 22 is a block diagram of a system for carrying out error correction according to an exemplary aspect of the present invention.

FIG. 23 is a flow diagram illustrating a method for carrying out error correction according to an exemplary aspect of the present invention.

FIG. 24A is a functional block diagram illustrating a system for carrying out encryption/decryption according to an exemplary aspect of the present invention.

FIG. 24B is a flow diagram illustrating an exemplary cryptographic method according to the present invention.

FIG. 25 is a flow diagram illustrating an exemplary method for carrying out key exchange according to the present invention.

FIG. 26 is a flow diagram illustrating an exemplary method of public-key cryptography according to the present invention.

FIG. 27 is a flow diagram illustrating an exemplary method of public-key cryptography according to the present invention.

FIG. 28 is a flow diagram illustrating an exemplary method of public-key cryptography according to the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention provides approaches for efficiently carrying out arithmetic and logical operations involving elements of the finite field GF(p^lk) (an extension field) where p is an odd prime number. As will be discussed in detail below, one aspect of the present invention addresses how data representing elements of the field GF(p^k) are stored in binary hardware and how arithmetic operations are then carried out efficiently. As referred to herein, the finite field GF(p^k) should be understood to mean an odd-characteristic finite field wherein the characteristic p is an odd prime number.

Various aspects of the invention will be described below in greater detail in connection with a number of exemplary embodiments. To facilitate an understanding of the invention, many aspects of the invention are described in terms of actions to be performed by elements of a computer system. Further, it will be recognized that in each of the embodiments, the various actions could be performed by specialized circuits (e.g., discrete logic gates interconnected to perform a specialized function), by program instructions being executed by one or more processors, or by a combination of both. Moreover, the invention can additionally be considered to be embodied entirely within any form of computer-readable carrier such as solid-state memory, magnetic disk, optical disk or modulated wave containing an appropriate set of computer instructions that would cause a processor to carry out the techniques described herein. A modulated wave can be, for example, a radio frequency modulated wave, an audio frequency modulated wave, an optical frequency modulated wave, or a modulated binary bit stream that can be downloaded via a network connection or modem. Thus, the various aspects of the invention may be embodied in many different forms, and all such forms are contemplated to be within the scope of the invention. For each of the various aspects of the invention, any such form of embodiment may be referred to herein as “logic configured to” perform a described action, or alternatively as “logic that” performs a described action.

Before addressing aspects of the invention pertaining to computations involving elements of GF(p^k) themselves, algorithms that relate arithmetic operations in the field GF(p^k) to arithmetic operations in the extension field GF(p^lk) will first be described.

Given a polynomial f(t) of degree l, irreducible over GF(p^k), and given that α (=Σ_iα_ixⁱ, α_iin GF(p^k)) and β (=Σ_iβ_ixⁱ, β_iin GF(p^k)) are elements of GF(p^lk) to be operated on at a high level, algorithms for addition, SUM(α, β), and multiplication, PRODUCT(α, β), in GF(p^lk) are provided below. The notation GF_p_k_<op>(α_i, β_j) in these algorithms denotes a procedure carrying out the operation <op> (add, multiply, etc.) on field elements α_iand β_jin the field GF(p^k).

First, an addition algorithm, denoted SUM(α, β), that relates the addition of elements α and β of the extension field GF(p^lk) to computations to be carried out in the field GF(p^k) is given below.



	SUM(α, β):

for i=0 to l-1 do

δ₁=GF_p_k_ADD(α₁, β_i)

end

	return δ_l-1 t^l-1 + δ_l-2 t^l-2 + ... + δ₁ t + δ₀

where GF_p_k_ADD will be described in detail below.

In addition, a multiplication algorithm, denoted PRODUCT(α, β), that relates the multiplication of elements α and β of the extension field GF(p^lk) to computations to be carried out in the field GF(p^k) is now described. Here it is assumed that necessary initializations of DLOG and ANTILOG tables have already been made. Forms of the DLOG and ANTILOG tables will be described below. In addition, exemplary DLOG and ANTILOG tables are given inFIGS. 10A and 11A for a simple illustration for GF(3²) to be described later.



	PRODUCT(α, β):

for i=0 to 2l-2 do

	δ₁=0
	for j=max(0,i-l+1) to min(i, l-1) do

δ₁=GF_p_k_ADD(δ_i, GF_p_k_MUL(α_j, β_1-J))

end

	return REDUCE(δ_2l-2 t^2l-2 + δ_2l-3 t^2l-3 + . . . + δ₁ t + δ₀ , f(t))

where GF_p_k_MUL and REDUCE(δ, f) (the latter computing z(t) mod f(t)) will be described in detail below.

It should be noted that the above multiplication algorithm is merely one example of possible multiplication algorithms. For large values of l (e.g., l>100), faster performance may be obtained by using Karatsuba's method instead of the simple PRODUCT algorithm above. Karatsuba's method is known to those of ordinary skill in the art and is described, for example, inSeminumerical Algorithmsreferred to above.

Finally, a reduction operation “mod f(t)” necessary for completing the multiplication algorithm, PRODUCT(α, β), can be done with a well-known algorithm given below and denoted as REDUCE(δ, f). This algorithm can also make use of the present inventive approach for efficient arithmetic in the field GF(p^k) to be described. For computational efficiency, f(t) can be chosen to be “sparse”, meaning that f(t) has only a few non-zero coefficients (e.g., 3 non-zero coefficients). In this case, f(t) has form f(t)=f_lt^l+f_jt^j+f₀for some j between l and 0. It should be noted, however, that it is not necessary in general for f(t) to have such a sparse. For any value of l, an irreducible polynomial f(t) of degree l can be readily found by methods known to those of ordinary skill in the art. A general approach for determining an irreducible polynomial f(t) may be found inSeminumerical Algorithmsreferred to above, for example. With these comments in mind, the reduction algorithm, denoted REDUCE(δ, f), is as follows.



REDUCE(δ, f)

	tmp1=GF_p_k_MUL(GF_p_k_INVERSE(f_l), f₀)
	tmp2=GF_p_k_MUL(GF_p_k_INVERSE(f_l), f_j)
	for i=2l-2downto 1 do

	δ_i-l=GF_p_k_SUB(δ_1-l, GF_p_k_MUL(tmp1, δ_i))
	δ_i-l+J=GF_p_k_SUB(δ1-l+j, GF_p_k_MUL(tmp2, δ_i))

end

return δ_l-1 t^l-1 + δl-2 t^l-2 + . . . + δ₁ t + δ₀.

The REDUCE algorithm above is just a normal polynomial division algorithm adapted for the special form of f(t) given above. It should be noted that tmp1 and tmp2 can be pre-computed because they are fixed once the representation is given, that is, once f(t) is defined. The function GF_p_k_SUB refers to field subtraction in the field GF(p^k), and the function GF_p_k_INVERSE refers to multiplicative inverse computation, both of which are easily implemented given algorithms for GF_p_k_ADD and GF_p_k_MUL and both of which will be described below.

Anexemplary apparatus100 for executing the above-noted algorithms and for implementing other aspects of the invention will now be described with reference to the block diagram ofFIG. 1. Theapparatus100 comprises amemory101 and aprocessing unit105 coupled to thememory101. Theapparatus100 can also comprise an input/output device103. Theprocessing unit105 comprises a plurality of registers107-121, which are controlled by logic circuits (not shown) within theprocessing unit105. Theprocessing unit105 can communicate with the input/output device103 and thememory101 via electrical connections (e.g., electrical buses) represented by the arrows shown inFIG. 1. It is also possible for theprocessing unit105 to communicate with external registers (not shown) located outside theprocessing unit105.

Theprocessing unit105 can be, for example, any conventional type of processing unit, such as a Pentium-class processor or other CPU typically found in personal computers, or it may be a special purpose processor, such as may be found in wireless phones or other handheld devices. It is common for conventional processors used in personal computers to have eight general purpose registers, such as illustrated by the eight registers107-121 inFIG. 1 (also denoted as registers a-h). Theregisters107 can be, for example, 8-bit registers, 16-bit registers, 32-bit registers, 64-bit registers, etc. Present generation processors for conventional personal computers commonly have 32-bit registers.

Thememory101 can be, for example, any suitable memory capable of storing computer programs, such as a magnetic disk, a CD ROM, a magneto-optical disk, a flash memory, or other types of memory. In addition to storing computer programs, thememory101 can also be used to store intermediate or final computational results generated by theprocessing unit105 and can also be used to store look-up tables to be utilized during computations.

The input/output device103 can be, for example, any suitable device for passing data to and/or from theprocessing unit105, such as a hard-wired modem or network interface, a wireless modem, a second memory, an analog-to-digital/digital-to-analog (AD/DA) converter, or other similar types of devices. Separate input and output devices can be utilized in place of a combined input/output device if desired. In addition, the input/output device103 can be configured to perform guard-bit insertion and guard-bit removal. Guard-bit insertion and guard-bit removal are described later in relation toFIGS. 8A and 8B, for example.

In one aspect, thememory101 can store one or more computer programs, and theprocessing unit105 can access thememory101 to execute steps of the computer program(s). These computer programs can include, for example, programs representing the algorithms noted above and programs implementing other aspects of the invention as described below.

In addition, although asingle processing system100 having asingle processing unit105 is shown inFIG. 1, it should be understood that theprocessing system100 can comprisemultiple processing units105. Moreover, it is possible to embody the present invention using multiple processing systems instead of asingle processing system100.

The remainder of the detailed description will focus on describing the inventive approaches for storing binary data representing field elements of GF(p^k) in hardware registers and for executing operations on such binary data in a manner to enhance the speed of arithmetic computations involving field elements of GF(p^k). In this regard, descriptions of the algorithms GF_p_k_ADD and GF_p_k_MUL, which provide for adding and multiplying field elements of the field GF(p^k), will be described. In addition, other apparatuses for implementing the approaches will also be described.

According to one aspect of the invention, theapparatus100 illustrated inFIG. 1 can be used to carry out computations involving field elements of an odd-characteristic finite field GF(p^k) in a manner that enhances computational efficiency compared to conventional approaches for carrying out computations involving field elements of odd-characteristic finite fields. In particular, theprocessing unit105 is configured (e.g., programmed) to store binary data representing at least a portion of a field element of an odd-characteristic finite field GF(p^k) in a register, such asregister107 shown inFIG. 1, wherein p is an odd prime number and wherein the field element comprises k coefficients in accordance with a polynomial basis representation. Theprocessing unit105 and the register can be viewed as means for storing binary data representing at least a portion of a field element of GF(p^k). The binary data comprise plural groups of data bits, wherein each group of data bits represents an associated one of the k coefficients. Thus, binary data representing multiple coefficients of a field element of the odd-characteristic finite field GF(p^k) are packed into a single hardware register according to an aspect of the present invention. In contrast, conventional approaches for carrying out computations involving field elements of odd-characteristic finite fields merely place binary data representing a single coefficient of an odd-characteristic finite field into a single hardware register.

In addition, theprocessing unit105 is also configured to execute at least one operation on the contents of the above-notedregister107 such that the plural groups of data bits are processed in parallel. For example, one or more operations can include a shift operation, an addition operation, a binary subtraction operation, a logical AND operation, and a NOT operation (logical negation) to name a few. In this regard, theprocessing unit105 can be viewed as means for executing at least one operation on the binary data such that the plural groups of data bits are processed in parallel. Thus, by storing binary data representing multiple coefficients of a field element of GF(p^k) in a single hardware register and by processing the plural groups of data bits in parallel, the speed of computations according to the present invention can be greatly increased compared to conventional methods for computations involving field elements of odd-characteristic finite fields. For example, if all k coefficients of a field element of GF(p^k) are represented in a single hardware register, such asregister107 shown inFIG. 1, the speed of processing the binary data representing the field element can be increased by a factor of k for addition and k²for multiplication over conventional methods.

Multiple coefficients of a field element of GF(p^k) can be stored in a single hardware register using two exemplary approaches according to the present invention. These approaches are referred to herein as the single-guard-bit representation and the multiple-guard-bit representation, respectively, each of which has different advantages as will be described below. In describing each of these representations, it is assumed that the hardware architecture is capable of performing basic arithmetic and logical operations on w-bit words, e.g., the hardware registers can be w-bit registers for some w≧k(m+1) where binary data representing an entire field element is to be stored in a single register. In conventional terms, this means that the hardware architecture can perform arithmetic and logical operations on binary encoded integers in the range (0 . . . 2^w−1). In principle, larger values of w are preferable because more information can thereby be processed per operation. Bit positions are numbered from right to left wherein the least significant bit is indexed by “0”, the next bit by “1”, the next bit by “2”, and so on, up to most significant bit (the word size), which is indexed by “w−1”.

Examples of the single-guard-bit representation are shown inFIGS. 2A and 2B for 32-bit hardware registers.FIG. 2A is a schematic illustration of ahardware register200 with a data storage scheme for storing binary data representing a field element α_i=(α_9,i, . . . , α_1,i, α_0,i) of GF(3¹⁰).

In the example ofFIG. 2A, ten groups of bit positions201-r(unshaded bit positions) are allocated to store ten groups of data bits representing the field coefficients α_9,i, . . . , α_1,i, α_0,i. Two bit positions are allocated for storing the binary data representing each coefficient α_j,i(which is sufficient since α_j,i≦3<2²). A group of data bits representing the coefficient α_0,iare stored in bit positions zero and one (from the right). Another group of data-bits representing the coefficient α_1,iare stored in bit positions three and four, and so on. In addition, ten bit positions203-rare allocated to store “guard bits” (lightly shaded regions), which are initially assigned binary values of 0. In the example ofFIG. 2A, bit positions two, five, eight, etc. are allocated for guard bits. The guard-bit positions (also referred to as separating-bit positions) serve to separate binary data representing the field coefficients and to accept any carry bit from an immediately preceding group of bit positions201-r. For example, when arithmetic and logical operations are carried out, a carry bit from the group of bit positions201-1 is prevented from carrying over into the adjacent group of bit positions201-2 and, instead, carries over into the guard-bit position203-1. Also, in the Example ofFIG. 2A, the two mostsignificant bit positions205 in theregister200 are unused (darkly shaded regions). Generally, unused bit positions are located at the most significant bit locations. However, unused bit positions can also be located at the least significant bit locations. If the unused bit positions are located at the most significant bit locations, it is not necessary to assign any particular values to the unused bit positions. Otherwise, the unused bit positions must initially be assigned values of zero.

In the example ofFIG. 2A for GF(3¹⁰), the ground field is GF(3), and the following mapping between integer values of each coefficient and corresponding binary data is applicable (the quantities in parentheses are binary data): 0˜(0, 0); 1˜(0, 1); 2˜(1, 0); 3˜(1, 1) where 3 also corresponds to 0 (because 3mod 3=0). Thus, in one aspect of the present invention, a dual representation is provided wherein two different numbers in GF(p) (3 and 0 in this example, where p=3) represent a same value (zero). In GF(3^k), two binary bits are used to represent each coefficient of a field element. In general for GF(p^k), the number of bits used to represent a coefficient of a field element depends on the value of p. Where p is given by p=2^m−1, m binary bits (not including guard bits) are used to represent each coefficient of a field element.

Another example of the single-guard-bit representation is shown inFIG. 2B.FIG. 2B is a schematic illustration of ahardware register210 with a data storage scheme for storing a field element α_i=(α_4,i, . . . , α_1,i, α_0,i) of GF(7⁵). In the example ofFIG. 2B, five groups of bit positions211-r(unshaded bit positions) are allocated to store binary data representing the field coefficients α_4,i, . . . , α_1,i, α_0,i. In this example, p=7=2^m−1. Therefore, m=3, and three bits (not including guard bits) are allocated to store the binary data representing each coefficient α_j,i. Binary data representing coefficient α_0,iare stored in bit positions zero, one and two (from the right). Binary data representing coefficient α_1,iare stored in bit positions four, five and six, and so on.

In the example ofFIG. 2B for GF(7⁵), the ground field is GF(7), and the following mapping between integer values of each coefficient and corresponding binary data is applicable (the quantities in parentheses are the binary data): 0˜(0, 0, 0); 1˜(0, 0, 1); 2˜(0, 1, 0); 3˜(0, 1, 1); 4˜(1, 0, 0); 5˜(1, 0, 1); 6˜(1, 1, 0); and 7˜(1, 1, 1) where 7 also corresponds to 0 (because 7mod 7=0). Thus, the present invention provides a dual representation wherein two different numbers in the field GF(p) (7 and 0 in this example, where p=7) represent a same value (zero).

In addition, in the example ofFIG. 2B, five bit positions213-rare allocated to store guard bits (lightly shaded regions), which are initially assigned binary values of 0. In addition, bit positions three, seven, eight, eleven, etc. are allocated for guard bits. Also, in the Example ofFIG. 2B, the twelve mostsignificant bit positions215 in theregister210 are unused (darkly shaded regions).

An example of the multiple-guard-bit representation is shown inFIG. 2C.FIG. 2C is a schematic illustration of ahardware register220 with a data storage scheme for storing a field element α_i=(α_7,i, . . . , α_1,i, α_0,i) of GF(3⁸). In the example ofFIG. 2C, eight groups of bit positions221-r(unshaded bit positions) are allocated to store binary data representing the field coefficients α_7,i, . . . , α_1,i, α_0,i, and adjacent groups of bit positions221-rare separate by a group of two guard bit positions213-r(lightly shaded bit positions). In this example, p=3=2^m−1. Therefore, m=2, and two bits (not including guard bits) are allocated to store the binary data representing each coefficient α_j,i. Binary data representing coefficient α_0,iare stored in bit positions zero and one (from the right). Binary data representing coefficient α_1,iare stored in bit positions four and five and six, and so on. Eight groups of bit positions223-rare allocated to store two guard bits each (lightly shaded regions), which are initially assigned binary values of 0. In the example ofFIG. 2C, bit positions two, three, six, seven, eight, ten, eleven, etc. are allocated for guard bits. There are no unused bit positions in this example.

It is typically desirable to store binary data representing an entire field element of GF(p^k) in asingle hardware register107. However, in cases where a field element is sufficiently large such that its binary representation exceeds the storage capacity of a single register, it is desirable to store binary data representing at least a portion of the field element in theregister107. The arithmetic and logical operations noted above can be carried out by coordinating the operations in multiple registers that together store binary data representing a single field element of GF(p^k). For example, if two registers are used to store binary data representing a single field element of GF(p^k), a right shift by m bits over all the binary data can be carried out by coordinating the two registers such that the least significant bit in left hand register is shifted to the most-significant-bit side of the right-hand register. (The terminology “right-hand” and “left-hand” are used merely to distinguish the registers in the sense that a left-most-bit position in a register corresponds to the most-significant-bit position. The terminology is not intended to suggest that one register is necessarily physically positioned to the left of another register). It should be noted, however, that where two registers are used to store binary data representing a field element, if unused bit spaces are present in the most-significant-bit positions of the right-hand register, a right-shift operation must be implemented to skip over the unused bit spaces.

According to another exemplary aspect of the present invention, thesystem100 illustrated inFIG. 1 can be configured to execute the steps shown in the flow diagram illustrated inFIG. 3.FIG. 3 illustrates anapproach300 comprising a plurality of steps that can be executed by theprocessing unit105 shown inFIG. 1. As shown atstep301 shown inFIG. 3, theprocessing unit105 stores first binary data representing a first field element of GF(p^k) in a first register (e.g., register109), p being an odd prime number, wherein the first binary data comprises k groups of first data bits, and wherein each group of first data bits corresponds to an associated one of the k coefficients of the first field element. Similarly, as shown atstep303, theprocessing unit105 stores second binary data representing a second field element of GF(p^k) in a second register (e.g., register111), wherein the second binary data comprises k groups of second data bits, and wherein each group of second data bits corresponds to an associated one of the k coefficients of the second field element. Further, as shown atstep305 theprocessing unit105 then generates third binary data by executing at least one operation on contents of the first register and contents of the second register such that the k groups of first data bits are processed in parallel and such that the k groups of second data bits are processed in parallel. For example, the operation or operations referred to instep305 can include an addition operation, a subtraction operation, a shift operation, a logical AND operation, and a NOT operation just to name a few. Combinations of such operations may be carried out, for example, to generate third binary data that represents a third field element equal to the sum of the first and second field elements or a third field element equal to the product of the first and second field elements as will be described in detail below.

The k groups of first data bits can be structured in thefirst register109 such that at least one first guard bit is positioned adjacent to the most significant bit of each group of first data bits, each group of first data bits being separated from an adjacent group of first data bits by a corresponding at least one first guard bit. The k groups of second data bits can be structured in thesecond register111 such that at least one second guard bit is positioned adjacent to the most significant bit of each group of second data bits, each group of second data bits being separated from an adjacent group of second data bits by a corresponding at least one second guard bit. In addition, the third binary data can comprise k groups of third data bits stored and structured in a third register (e.g., register113) such that at least one third guard bit is positioned adjacent to the most significant bit of each group of third data bits, each group of third data bits being separated from an adjacent group of third data bits by a corresponding at least one third guard bit. In this regard, the third field element comprises k third coefficients in accordance with the polynomial-basis representation, and each group of third data bits represents an associated one of the k third coefficients. (In the discussion above, “first”, “second” and “third” are used as labels.)

Theprocessing unit105 and a first register (e.g., register109) can be viewed as means for storing first binary data representing a first field element of GF(p^k). Theprocessing unit105 and a second register (e.g., register111) can be view as means for storing second binary data representing a second field element of GF(p^k). Theprocessing unit105 and a third register (e.g., register113) can be viewed as means for storing third binary data representing a third field element of GF(p^k). Theprocessing unit105 can be viewed as means for executing at least one operation on the first binary data and the second binary data such that the k groups of first data bits are processed in parallel and such that the k groups of second data bits are processed in parallel.

Atstep307, it is determined whether or not more data should be processed. If more data should be processed, the flow then proceeds back tostep301. If the additional processing involves processing binary data that have already been stored in a manner consistent withsteps301 and/or303 as a result of another calculation, steps301 and/or303 can be skipped as appropriate. If it is determined atstep307 not to process more data, the algorithm ends.

Exemplary approaches for executingstep305 shown inFIG. 3 will now be described. Step305 can be implemented, for example, using an algorithm GF_p_k_ADD or an algorithm GF_p_k_MUL, which will be described below. GF_p_k_ADD and GF_p_k_MUL were referred to above in the discussion of the algorithms SUM(α, β), PRODUCT(α, β), and REDUCE(δ, f). As will be described below, certain aspects of algorithms for both GF_p_k_ADD and GF_p_k_MUL depend upon the functional form of the characteristic value p and upon whether the single-guard-bit representation or the multiple-guard-bit representation is used. In particular, certain aspects of these algorithms depend on whether p is written as p=2^m−1, p=2^m+1 or p=2^m±d for some integer m and some small integer d. The integer d is to chosen such that d<2^m−1. However, choosing d to be smaller, e.g. d≦p/6, has some advantages as will be described below. Accordingly, exemplary forms for GF_p_k_ADD and exemplary forms for GF_p_k_MUL will be described below with reference to the functional form of the characteristic value p and with reference to whether the single-guard-bit representation or the multiple-guard-bit representation is used.

In view of the comments above, a question arises as to which form of GF_p_k_ADD or which form of GF_p_k_MUL should be used where a given odd prime p can be written in more than one functional form. For example, p=5 can be written as p=2^m+1 for m=2, and p=5 can also be written as p=2^m−d for m=3 and d=3). Generally, it is preferable to utilize the approach for p=2^m−1 over approaches for the other two functional forms. In addition, it is preferable to use the approach for p=2^m+1 over the approach for p=2^m±d with d>1. In general, for p=2^m±d, it is desirable to choose d odd and as close to 1 as possible. Given a value of p, a good (m, d)-pair can be found by trying all m=1, 2, . . . , (2 log₂(p)), and for each such m, selecting d to satisfy p=2^m±d, until a small d is found.

Addition Using Single-Guard-Bit Representation, p=2^m−1

A form of GF_p_k_ADD for the single-guard-bit representation where p=2^m−1 will now be described, and it will be shown how one full addition of two field elements in GF(p^k) (i.e., k additions pertaining to the k coefficients of each field element), including the associated modular reduction, can be performed with a small, fixed number of operations (and without modular reductions which require long divisions) on a hardware architecture having at least w=k(m+1) bit word size. For example, for a 32-bit architecture, full additions in GF(3¹⁰) can be performed using only five instructions.

In the single-guard-bit representation, first binary data representing a first field element α_i=(α_k−1,i, . . . , α_1,i, α_0,i) of GF(p^k) is stored in a first single hardware register (e.g., register107 shown inFIG. 1) by storing binary data representing α_0,iinbit positions0 through m−1, binary data representing α_1,iin bit positions m+1 through2m, etc., such that a group of data bits representing one field coefficient is separated by one bit position from an adjacent group of data bits representing another field coefficient. Second binary data representing a second field element β_jis stored similarly in a second single hardware register (e.g., register109). Bit positions v(m+1)−1 where v=1, 2, . . . , k are allocated to separate the binary data representing the coefficients α_0,i, α_1,i, etc. These positions are referred to as guard-bit positions or separating-bit positions and are initially assigned values of “0”. Examples of storing binary data according to the single-guard-bit representation for a w=32-bit architecture are shown inFIGS. 2A and 2B described previously for elements of the fields GF(3¹⁰) and GF(7⁵), respectively. For example, inFIG. 2A for GF(3¹⁰), two bit positions are reserved for each α_j,i(which is sufficient since α_j,i≦3<2²).

With first and second binary data representing first and second field elements of GF(p^k) stored in first and second registers, respectively, operations can be carried out to determine the sum of the first and second field elements. The contents of the first and second registers may be referred to as a and b, respectively. Let M2 be a binary quantity whose only “1” bits are in positions j(m+1)−1, j=1, 2, . . . , k, and “0” elsewhere (i.e., M2=2^m+2^2m+1+ . . . +2^k(m+1)−1), and let M1 be a binary quantity given by M1=NOT(M2) (bitwise negation). The sum of the first and second field elements can be determined by carrying out the operations given in Equation 13
c=((a+b)&M1)+(((a+b)&M2)>>m) (13)
where “&” denotes bitwise logical AND, “>>” denotes right shift, “+” denotes addition with carry, and c refers to the register contents comprising third binary data that represents a third field element equal to the sum of the first and second field elements. The operations reflected in equation 13 can be executed in any manner that is desired. For example, the intermediate quantity (a+b) can be stored in a given register, and the given register can then be overwritten with the final result given by the quantity c, such that the operation (a+b) is performed only once. The binary quantities M1 and M2 may be thought of as mask quantities because, when combined with the quantity (a+b) via the respective logical AND operations as shown in Equation 13, the binary quantities M1 and M2 mask out (set to zero) bits in certain bit positions in the quantities ((a+b) & M1) and ((a+b) & M2). The binary quantity M1 masks out bits in the quantity ((a+b) & M1) corresponding to guard-bit positions. The binary quantity M2 masks out bits in the quantity ((a+b) & M2) corresponding to non-guard-bit positions.

In carrying out Equation 13 with guard bits at positions m,2m+1, etc., no carry bit will propagate from an m-bit segment corresponding to some α_j,i(or β_j,i), into the segment representing α_j+1,i(or β_j+1,i). Thus, the field-element sum is really computed component-wise, modulo p, on α_iand β_i. The mask operation by M1 ensures the result will have the correct representation with zeros in the guard-bit positions. In the above discussion, M2 is determined first, and then M1 is defined in terms of M2. However, it would be equivalent to first determine M1 as a binary quantity having values of zero at bit positions corresponding to bit positions of first guard bits stored in the first register and having values of one elsewhere and to then determine M2 as M2=NOT(M1).

An example of this form of GF_p_k_ADD where p=2^m−1 is shown in the flow diagram ofFIG. 4. The operations shown inFIG. 4 can be executed by a system such assystem100 shown inFIG. 1. It is assumed that

steps

301 and303 shown inFIG. 3 have already been executed by theprocessor105 such that first binary data representing a first field element of GF(p^k) are stored in a first register (e.g., register107 shown inFIG. 1) and such that second binary data representing a second field element are stored in a second register (e.g., register109). The steps illustrated inFIG. 4 then represent an exemplary implementation ofstep305 shown inFIG. 3.

As indicated atstep401, theprocessing unit105 adds the contents, a, of thefirst register107, and the contents, b, of thesecond register109. The addition may involve a carry into a given next most significant bit where necessary. The result of the addition can be stored in anotherregister111. As indicated atstep403, theprocessing unit105 then executes a logical AND operation between the quantity (a+b) stored inregister111 and a first predetermined binary quantity M1 stored in one of the registers (e.g., register113). The quantity M1 has values of zero at bit positions corresponding to bit positions of first guard bits stored in thefirst register107 and has values of one at bit positions corresponding to bit positions of the groups of first data bits stored in the first register. The result of this operation can be referred to as first intermediate data c1 and is stored in one of registers (e.g., register115).

As indicated atstep405, the processing unit executes a logical AND operation between the quantity (a+b) store inregister111 and a second predetermined binary quantity M2 where M2 is given by M2=NOT(M1). The NOT operation is bitwise logical negation. The result of this operation is stored in one of registers (e.g., register117). Also indicated atstep405, theprocessing unit105 then executes a right shift by m bits on the quantity given by ((a+b)&M2). The result of this operation can be stored in thesame register117 or in a different register. The result of this operation may be referred to as second intermediate data c2 as shown instep405. Atstep407 the processor executes addition between the first intermediate binary data c1 and the second intermediate binary data c2 to generate the third binary data, represented by c, which can be stored in one of the registers (e.g., register119). According to this approach, the third binary data c represents the sum of the first field element and the second field element.

The algorithms according toFIGS. 3 and 4 have been described in terms of a specified sequence of steps to facilitate the description. However, it is not necessary to carry the steps indicated inFIGS. 3 and 4 in the exact order illustrated. Those of ordinary skill in the art will recognize that the order of steps can be varied and that some of the steps can be carried out simultaneously. For example, steps301 and303 shown inFIG. 3 can be carried out simultaneously, and steps403 and405 shown inFIG. 4 can be carried out simultaneously.

Additional insight into aspects of the exemplary form for GF_p_k_ADD described above can be gained by considering the following special case for k=1. In the description above, the number “0” has two representations: both 0 itself and also p=2^m−1. It is only necessary to take this duality into account during input and output operations. Given that p=0 mod p, there is no mathematical problem with this dual representation. Integers in this dual representation can be added modulo p in accordance with the following equation
(a+b)modp=((a+b)mod 2^m)+((a+b) div 2^m) (14)
wherediv 2^mrefers to a function that returns the floor of a quotient where the divisor is 2^m. Stated differently, the sum of a and b (in the dual representation) is a+b if a+b<2^m; otherwise, the sum is ((a+b) mod 2^m)+1. These two cases (depending on whether the sum is less than 2^mor not) can thus jointly be treated by the formula (a+b) mod p=[(a+b) mod 2^m]+[(a+b) div 2^m]. Observe that (a+b)≦2(2^m−1)=2^m+1−2 and that the mod and div operations can be efficiently implemented as bit operations (logical AND, shift) since the module and the divisor are each powers of 2. Thus, given a hardware architecture that can perform operations on (at least) m+1 bit quantities and given the dual representations for a and b, the quantity (a+b) mod p (in the dual representation) can be determined in accordance with Equation 15:
c=((a+b)&(2^m−1))+(((a+b)&2^m)>>m) (15).
Because a+b<2^m+1−2, no overflow results from carrying out Equation 15 if w≧m+1, where w is the register size. Thus, instead of one addition and one modular reduction (a long division) by p, five simple operations are performed where the

quantities

2^mand 2^m−1 are fixed and can be considered constant bit-masks. In the discussion above, it was assumed that k=1 to facilitate the discussion. Of course, the present invention is to be carried out using a value of k that is greater than one. Nevertheless, the discussion for k=1 provides insight into the form of GF_p_k_ADD and the choices of the binary quantities M1 and M2 according to the present invention for use where k is greater than one.

In addition, the dual representation, in which the number “0” is represented as both 0 itself and also as p=2^m−1, facilitates determining the sum of two field elements according to the approach described above. As noted above, instead of using one addition and one modular reduction (a long division) by p to determine the sum of two field elements, the dual representation allows using five simple operations on binary data representing the two field elements to determine their sum.

With regard to the extension field GF(p^lk), as noted above in the discussion regarding SUM(α, β) and PRODUCT(α, β), each element of the extension field is represented as a vector (polynomial) of length l, where each component (coefficient) is an element of GF(p^k) and can be stored according to the single guard-bit representation as described above. Adding two elements in the extension field GF(p^lk) can now be done using 5l operations instead of lk operations as would be required using conventional approaches. Thus, even for relatively small values of k, a significant increase in computational speed can be achieved.

In addition, as will be described later, the above-described exemplary form for GF_p_k_ADD is also applicable to binary data stored according to the multiple-guard-bit representation for p=2^m−1.

EXAMPLE 1

A numerical example illustrating the approach shown inFIGS. 3 and 4 will now be described with reference toFIG. 5. The operations described below can be carried out using a system such assystem100 shown inFIG. 1, which has been previously described.FIG. 5 illustrates register contents resulting from carrying out the operations as described above with regard toFIGS. 3 and 4. InFIG. 5, reference numerals501-517 refer to 32-bit registers, and the binary data stored within the registers501-517 are configured according to a single guard-bit representation. In addition, in this example the binary data represents field elements of the finite field GF(3¹⁰), and the characteristic p is given by p=2^m−1=3. Accordingly, M=2, and 2 bits of register space are allocated for each coefficient of the finite field element. A single guard bit (lightly shaded bit locations) separates adjacent binary data representing adjacent coefficients of the finite field element. In addition, in this example there are two unused bits of register space (darkly shaded bit locations) at the most significant bit positions of each register501-517.

In this example, first binary data, a, representing a first field element (2, 2, 0, 2, 0, 3, 2, 2, 0, 0) (in vector notation) and second binary data, b, representing a second field element (0, 1, 2, 2, 0, 2, 1, 3, 0, 0) (in vector notation) are stored in first and

second registers

501 and503, respectively (steps301 and303). Each coefficient of the field elements is itself an element of the ground field GF(3), and each coefficient is represented by binary data according to the following associations: 0˜(0, 0); 1˜(0, 1); 2˜(1, 0); 3˜(1, 1). A dual representation is provided wherein two different numbers in GF(p) (3 and 0 in this example, where p=3) represent a same value (zero). Thus, binary data given by (1, 1), which corresponds to 3, also represents 0 (because 3mod 3=0). Each guard-bit position in

registers

501 and503 is initially assigned a value of zero.

The register contents a and b stored in

registers

501 and503, respectively, are then added via addition (corresponding to step401). The result (a+b) is stored in athird register505. The contents (a+b) ofregister505 are then combined via a logical AND operation with the contents ofregister507, in which the quantity M1 has been stored), and the result c1=(a+b)&M1 is stored in register509 (corresponding to step403). In addition, the quantity M2=NOT (M1) is stored inregister511. The contents (a+b) ofregister505 and the contents M2 ofregister511 are then combined via a logical AND operation, and the result (a+b)&M2 is stored in register513 (corresponding to step405). The contents (a+b)&M2 ofregister513 are then right shifted by m=2 bits, and the result is stored in register515 (corresponding to step405). The contents c1 ofregister509 and the contents c2 ofregister515 are then added via addition, and the result is stored inregister517. The result is given by (2, 3, 2, 1, 0, 2, 3, 2, 0, 0) (in vector notation) and is equivalent to (2, 0, 2, 1, 0, 2, 0, 2, 0, 0) as expected.

In the above example, carries are generated into three guard-bit positions (bit positions eight, fourteen and twenty) as shown inregister505 upon adding the first binary data, a, and the second binary data, b. The guard-bit positions prevent the carry bits from affecting the values of the adjacent group of data bits. Accordingly, in this example, the guard-bit positions (lightly shaded bit positions) allow carrying out operations on ten groups of data bits in parallel, where the ten groups of data bits represent the ten field coefficients.

As a matter of convenience in describing the above operations, the binary results of various steps as shown inFIG. 5 have been described as being stored in separately identified registers. However, those of ordinary skill in the art will recognize that various steps can be carried out by reusing registers in a manner that over-writes previously stored binary data from an earlier step. For example, the first and second intermediate binary data c1 and c2 shown in

registers

509 and515 can instead be stored in

registers

501 and503 by over-writing the previously stored binary a and b to utilize register space more efficiently. This completes the discussion of Example 1.

In another aspect of the invention relating to computations involving field elements of an odd-characteristic finite field where p=2^m−1, a hardware apparatus can be provided for carrying out operations for the exemplary form of GF_p_k_ADD illustrated inFIG. 4.FIG. 6 is a functional block diagram of such an exemplary hardware apparatus. In particular, theapparatus600 illustrated inFIG. 6 provides another approach for generating third binary data, denoted as c inFIGS. 4 and 6, that can represent the sum of a first field element and a second field element of GF(p^k). InFIG. 6, solid lines represent electrical connections for the flow of data, and dotted lines represent electrical connections for the flow of control signals. Solid lines that cross are not connected unless a black dot is present at the intersection of the lines, such asconnection623. Theapparatus600 is described here in the discussion pertaining to the single-guard-bit representation, but theapparatus600 is equally applicable to a multiple-guard-bit representation, which is described later.

Theapparatus600 comprises afirst register601 and asecond register603 for holding first binary data (register contents “a”) and second binary data (register contents “b”), respectively. The first binary data and the second binary data represent field elements of the finite field GF(p^k). Here, it is assumed that the first and second binary data in the first and

second registers

601 and603 are already configured with zeros at guard-bit locations such as illustrated, for example, as inFIG. 2A. Theapparatus600 also comprises a combinatorial logic and clock device (clock/logic)605, an addition gate (+)607 (also referred to as an adder), aregister609 for holding the sum of register contents a and b, a first logical AND gate (&1)611, amask register613 for generating and holding a first predetermined binary quantity M1 upon input m, a NOT gate (NOT)615, and a second logical AND gate (&2)617. In addition, theapparatus600 comprises a right shift gate (>>)619 and anoutput register621 for holding a result “c”. Right shift gates are known to those of ordinary skill in the art, and such gates shift the values therein to the right by a selected number of bits and enter a corresponding number of zeros into the most significant bit positions. The clock/logic unit605 can also have an output terminal (not shown) for providing a signal to be input to another hardware apparatus to initiate computations in another hardware apparatus when computations in theapparatus600 are complete. For example, another hardware apparatus can be anotherapparatus600 or amultiplier apparatus1200 such as illustrated inFIG. 12 to be described later.

The operation of theapparatus600 illustrated inFIG. 6 will now be described. First binary data representing a first field element and second binary data representing a second field element of GF(p^k) are input on lines labeled a and b to thefirst register601 and thesecond register603, respectively. It is assumed that the first and second binary data are already configured with zeros at guard-bit positions (e.g., by a processor that is not shown). Binary data representing the quantity m is also provided to the right-shift gate (>>)619.Mask register613 receives a first predetermined binary quantity M1 (a mask quantity) from a processor (not shown), where M1 is a quantity with values as described previously. Alternatively,mask register613 can also comprise a circuit that generates the quantity M1 upon input of binary data representing the quantity m. Making such a circuit is within the purview of one of ordinary skill in the art.

Computation is initiated by a start signal on the input line labeled s. The first and second binary data, the binary data representing the quantity m, and the start signal can be provided from a processor (not shown) or from another hardware apparatus (not shown), such as a multiplier apparatus as illustrated inFIG. 12 to be described later, via a conventional routing circuit, for example.

When the values of the first binary data and second binary data in the

registers

601 and603 are stable, a signal s1 locks those values into the

registers

601 and603, respectively. Theadder607 then adds the values provided at its two inputs from

register

601 and603. When the output of theadder607 is stable, the output fromadder607 is locked intoregister609 by a signal on the line labeled s2. The time required for a given value to become stable in a given register can be conventionally determined by one of ordinary skill in the art in view of the circuitry design, and a locking signal (e.g., on line s1 or line s2) can be timed to occur after this time. At this point, theregister609 holds binary data representing corresponding to the quantity a+b shown instep401 ofFIG. 4.

The binary data inregister609 are then directed fromregister609 to the ANDgate611. The ANDgate611 performs a logical AND between the binary data fromregister609 and the mask quantity M1 frommask register613. The result of this logical AND operation is equivalent to the quantity c1 illustrated atstep403 ofFIG. 4. The output from the first ANDgate611 is then directed back to the input of thefirst register601, and another signal on the line labeled s1 then locks the corresponding values into thefirst register601 at the appropriate time. In this regard, it will be understood that a signal on the line s1 can be timed appropriately such that it is unnecessary to provide a multiplexer or switch at the point labeled623 to route data output fromregister609. Of course, theapparatus609 could be provided with a multiplexer or switch at thepoint623 for routing data if desired.

While the operations described in the immediately preceding paragraph are being carried out, the following operations are more or less simultaneously carried out. Output from theregister609 is directed to the second ANDgate617, and the first predetermined binary quantity M1 is directed to alogical NOT gate615. The output from thelogical NOT gate615 is also directed to an input of the second ANDgate617. The data at these the inputs of the second ANDgate617 are then combined via a logical AND operation and are directed to a right-shift gate619. The right-shift gate619 executes a right-shift by m bits on the data input from the second ANDgate617 according to the input on the line labeled m. The output of the right-shift gate619 is then directed to the input of thesecond register603. The result of this group of operations, which is input to thesecond register603, corresponds to the quantity c2 referred to instep405 ofFIG. 4.

When the values of the binary data now stored in the first and

second registers

601 and603 are stable, the signal s1 locks these values into the first and

second registers

601 and603. At this point, theadder607 adds the binary data from the first and

second registers

601 and603 and directs the output tooutput register609. The binary data now stored inregister609 is then directed to theoutput register621, and a signal on line s3 locks the binary data into theregister621 at the appropriate time. This binary data corresponds to third binary data denoted as c atstep407 ofFIG. 4.

Those of ordinary skill in the art will appreciate that many variations of theapparatus600 are possible according to the present invention. For example, each internal w-

bit register

601,603,609,613, and621 can be replaced with multiple parallel (i.e., coordinated) registers, at least one of which holds binary data representing at least two coefficients of a field element. Further, the first ANDgate611, theadder607, the second ANDgate617, theNOT gate615, and the right-shift gate619 shown inFIG. 6 are accordingly replaced with multiple parallel (i.e., coordinated) copies of each.

In theapparatus600 as described with reference toFIG. 6, first and second binary data are input to first and

second registers

601 and603, respectively, with zeros already configured at appropriate guard-bit positions. The first and second binary data may be provided in this configuration by a processor (not shown), for example, that inserts zeros at guard-bit positions as appropriate. Thus, the processor (not shown) and thefirst register601 can be viewed as means for storing first binary data, and the processor (not shown) and thesecond register603 can be viewed as means for storing second binary data. Further, theregister621 and/or theregister609 can be viewed as means for storing third binary data. Moreover, the clock/logic device605 and any or all of the remaining devices illustrated inFIG. 6 can be viewed as means for executing at least one operation on the first binary data and the second binary data.

By utilizing theapparatus600 along with a processor (not shown), theapparatus600 has flexibility to be used with field elements for various choices of p and k for the finite field GF(p^k), where p is of form p=2^m−1. In particular, the quantity m is a variable, and the right-shift gate619 responds accordingly to the input value of m. In addition, themask register613 holds an appropriate form of the first predetermined binary quantity M1 that depends upon the quantity m. The quantity M1 is “predetermined” in the sense that once the quantity m is chosen (which determines the quantity p), the form of the quantity M1 directly follows as described above.

In another exemplary aspect of the invention, theapparatus600 can be modified, such as shown byhardware apparatus700 illustrated in the block diagram ofFIG. 7, for a situation in which a dedicated choice of the finite field GF(p^k) is made and remains unchanged. That is, the quantities m, p, and k, as well as the choice of whether the representation is a single-guard-bit representation or a multiple-guard-bit representation, are fixed, and thehardware apparatus700 is dedicated to those choices. In this situation, thehardware apparatus700 can receive initial binary data representing field elements wherein the initial binary data are not configured with zeros in guard-bit positions. Rather, thehardware apparatus700 itself configures the initial binary data with zeros in appropriate guard-bit positions to generate first and second binary data without the need for a processor to configure the first and second binary data with zeros in guard-bit positions. Thehardware apparatus700 illustrated inFIG. 7 will now be described.

Thehardware apparatus700 illustrated in the functional block diagram ofFIG. 7 shares various common features and operational aspects with theapparatus600 illustrated inFIG. 6, and like features are given like reference numerals inFIGS. 6 and 7. Discussion of aspects of theapparatus700 that are common to theapparatus600 will not be duplicated here. Rather, aspects in which theapparatus700 differs from theapparatus600 will be discussed.

Theapparatus700 possesses several features not found in theapparatus600. In particular, theapparatus700 possesses guard-bit-insertion circuits701′ and703′ (GB insertion) and a guard-bit-removal circuit709′ (GB removal). Exemplary implementations of these circuits will be described inFIGS. 8A and 8B. As shown inFIG. 7, the guard-bit-insertion circuits701′ and703′ are functionally arranged at the input to thehardware apparatus700, and the guard-bit-removal circuit709′ is functionally arranged between theregister709 and theoutput register721. The guard-bit-insertion circuits701′ and703′ operate to receive initial binary data a′ and b′ (without guard bits) corresponding to first and second field elements of GF(p^k) and to insert appropriate guard bits into that data. In other words, the guard-bit-insertion circuits701′ and703′ transform the initial binary data a′ and b′ into first binary data and second binary data having guard bits, in particular, with zeros at guard-bit positions. The guard-bit-removal circuit709′ has the opposite function—namely, to receive third binary data c representing a computational result and having guard bits and to remove those guard bits, thereby forming final binary data c′ representing the computational result, but without guard bits.

Theapparatus700 also lacks certain features present in theapparatus600 because they are not needed in theapparatus700. In particular, theapparatus700 lacks an input line for the quantity m into the right-shift gate719 and into themask register713. Such an input line is not necessary given that m is fixed. Rather, the right-shift gate719 is initialized once with the value of m to execute the appropriate right shift. Similarly, themask register713 is initialized once with the appropriate form of M1. Conventional electrical connections can be used for carrying out these initializations and are not shown inFIG. 7. The operation of theapparatus700 illustrated inFIG. 7 is substantially similar to that described for theapparatus600 illustrated inFIG. 6 except for the operational distinctions noted above.

In theapparatus700 as described above, thefirst register701 and the guard-bit insertion circuit701′ can be viewed as means for storing first binary data. Thesecond register703 and the guardbit insertion circuit703′ can be viewed as means for storing second binary data. Further, theregister709 can be viewed as means for storing third binary data. Moreover, the clock/logic device705 and any or all of the remaining devices illustrated inFIG. 7 can be viewed as means for executing at least one operation on the first binary data and the second binary data.

The guard-bit-insertion circuits701′ and703′ and the guard-bit-removal circuit709′ referred to inFIG. 7 will now be described in greater detail with reference toFIGS. 8A and 8B. The exemplary circuits illustrated inFIGS. 8A and 8B reflect a 32-bit register arrangement configured for the field GF(7⁸); however, the concepts reflected inFIGS. 8A and 8B are generally applicable to registers of others sizes and to other finite fields GF(p^k).FIG. 8A illustrates an exemplary guard-bit-insertion circuit800 that can be used for guard-bit-insertion circuits (GB insertion) referred to byreference numerals701′ and703′, respectively, inFIG. 7. As shown inFIG. 8A, thecircuit800 comprises afirst register801 with a plurality of bit positions803 (e.g., 32 bits). Thecircuit800 also comprises aregister805 havingplural groups807 of bit positions intended to store binary data representing field coefficients of a field element of GF(p^k) and a plurality of guard-bit positions809 (lightly shaded regions). Thecircuit800 also comprises a plurality ofelectrical connections811 configured to route data fromregister801 to register805 in a manner that provides a guard-bit position809 adjacent to the most significant bit position of the preceding group of 3-bit positions807. The guard-bit positions809 are electrically grounded to provide zeros for these bit values, but these electrical connections are not shown in theFIG. 8A. Such a circuit can be formed, for example, using conventional lithographic techniques.

In this manner, each 3-bit group807 of bit positions inregister805 can store binary data representing a coefficient of a field element of GF(7⁸), and eachgroup807 of bit positions inregister805 is separated from anadjacent group807 of bit positions by asingle guard bit809. Accordingly, the guard-bit-insertion circuit800 allows initial binary data representing coefficients of a field element to be transferred in parallel fromregister801 to register805 in a manner that inserts guard bits between groups of data bits representing coefficients of the field element.

Multiplication Using Single-Guard-Bit Representation

According to another aspect of the invention, an exemplary form of GF_p_k_MUL for the single-guard-bit representation will now be described for computing the product of two (non-zero) field elements α_iand β_jin GF(p^k). The case where one field element is zero is trivial and does not need to be described. This discussion is applicable to p written in the functional forms p=2^m−1, p=2^m+1, p=2^m−d and p=2^m+d.

As noted previously in the discussion pertaining to Equations 9-12, a multiplicative group is cyclic, and a field element g, therefore, can be found such that any other non-zero field element can be written as g^xfor some integer x<p^k. Thus, the discrete logarithms of all field elements, as well as the corresponding anti-logarithms, can be pre-computed once, and table “look-ups” can be used to calculate the product of two field elements. Similarly, with regard to the present invention for binary data “a” representing any α_jaccording to the single-guard-bit representation (i.e., where guard bits of value zero are placed in bit positions v(m+1)−1 where v=1, 2, . . . , k—that is, every successive m-th bit position), the following relations are applicable:
DLOG{a}=x (16)
ANTILOG{x}=a (17)
where 0≦x<p^ksuch that g^x=α_j. Accordingly, in the single-guard-bit representation, multiplication of field elements of GF(p^k) can be accomplished in accordance with the relation:
c=ANTILOG{(DLOG{a}+DLOG{b})mod(p^k−1)} (18)
where “a” is first binary data (register contents) stored according to the single-guard-bit representation representing a first field element, “b” is second binary data (register contents) stored according to the single-guard-bit representation representing a second field element, and “c” is third binary data (register contents) representing a third field element equal to the product of the first and second field elements. For example, in terms of the notation used with the algorithms PRODUCT(α,β) and GF_p_k_MUL described previously, “a” can represent a field element α_jof GF(p^k), and “b” can represent a field element β_i−jof GF(p^k). Accordingly, the product of two field elements of GF(p^k) in the single-guard-bit representation according to the present invention can be computed using only three table look-ups and one modular addition.

According to an exemplary aspect of the present invention, thesystem100 illustrated inFIG. 1 can be used to implement the above-noted approach for multiplication of field elements. In particular, thesystem100 can be configured such that theprocessor105 executes the exemplary series of steps illustrated inFIG. 9 to generate third binary data referred to instep305 ofFIG. 3. It is assumed that

steps

301 and303 shown inFIG. 3 have already been executed by theprocessor105 such that first binary data representing a first field element of GF(p^k) are stored in a first register (e.g., register107 shown inFIG. 1) and such that second binary data representing a second field element are stored in a second register (e.g., register109). The steps illustrated inFIG. 9 then represent an exemplary implementation ofstep305 shown inFIG. 3. Theapproach900 illustrated in the flow diagram ofFIG. 9 will now be described.

FIG. 9 is a flow diagram illustrating steps executed by theprocessing unit105 for processing the first and second binary data to generate third binary data that represents the product of the first and second field elements. As indicated atstep901 ofFIG. 9, the processor determines the quantities DLOG(a) and DLOG(b) where “a” represents the contents of the first register and “b” represents the contents of the second register. Instep901, the DLOG operation represents a look-up operation from a look-up table of discrete logarithms in binary form of non-zero field elements of GF(p^k). The look-up table of discrete logarithms can be stored inmemory101 illustrated inFIG. 1. An example of a simple look-up table for the DLOG operation for GF(3²) is given inFIG. 10A. The look-up table inFIG. 10A will be described in greater detail below.

Atstep903, theprocessing unit105 executes addition of the quantities DLOG(a) and DLOG(b) and reduces the result of this addition modulo (p^k−1). Atstep905, theprocessing unit105 determines the quantity ANTILOG{(DLOG(a)+DLOG(b))mod(p^k−1)}. The ANTILOG operation represents a look-up operation from a look-up table of anti-logarithms, wherein ANTILOG(X)=g^x, where g is a generator of GF(p^k). An example of a simple look-up table for the ANTILOG operation for GF(3²) is given inFIG. 11A. The look-up table inFIG. 11A will be described in greater detail below. The result of the operations set forth instep905 is third binary data referred to instep305 ofFIG. 3 which, in this example, represents a third field element that is the product of the first and second field elements.

Exemplary look-up tables of discrete logarithms and anti-logarithms referred to above for the single-guard-bit representation will now be described. For the sake of brevity, a look-up table of discrete logarithms may hereinafter also be referred to as a DLOG table, and a look-up table of anti-logarithms may hereinafter also be referred to as an ANTILOG table.

In one example, the DLOG table can be indexed by binary data corresponding to field elements of GF(p^k) wherein the binary data are viewed as memory addresses. This type of DLOG table is referred herein as a “directly addressed” DLOG table and uses consecutive binary data corresponding to field elements as memory addresses. For p=2^m−1, for example, the DLOG table can be indexed (addressed) by k(m+1)-bit binary strings. Alternatively, the DLOG table can be indexed using binary strings k(m+1)−1 bits in length if the most significant guard bit of the binary data representing each field element not used for addressing (the most significant guard bit is not needed for table look-ups). If the most significant guard bit is not used for addressing, the size of the DLOG table can be reduced by a factor of two. Assuming that binary data representing field elements is referred to as a(t) (where t is the polynomial variable in a polynomial basis representation), the corresponding looked-up value from the DLOG table at an address corresponding to a(t) is the integer “x” where x=DLOG{a(t)}. In a directly addressed DLOG table for p=2^m−1, given that the single-guard-bit representation of field elements allocates every m-th bit to be a guard bit (for a total of k guard bits), there are only 2^kmrelevant entries in the DLOG table that are actually used during look-up. These relevant entries are those for which a quantity a(t) has zeros in the guard-bit positions. Such a DLOG table overall has 2^k(m+1)reserved memory locations (rows), if indexed using binary strings k(m+1) bits in length, or 2^k(m+1)−1rows, if indexed using binary strings k(m+1)−1 bits in length. Stated differently, rows in a direct addressing DLOG table for which the field element a(t) (the memory address) has a “one” in any guard-position are not used.

For example, if k=8 and p=3 (i.e., m=2), each element of the field can be represented as a 24-bit string (with zeros in every third bit position), and the DLOG table can, accordingly, be indexed by strings of length 8(2+1)=24 (equivalent to 8(log₂(3)+1)). In this example, there are 2²⁴reserved memory locations in the DLOG table, but only one in every 256 of these will contain data that is actually accessed, since look-ups will only be conducted for addresses corresponding to field elements, i.e. strings whose guard-bit locations are zeros. In the above example, there are k=8 guard-bit locations, so only one table index in every 2⁸(=256) will be used for actual table look-ups. However, for moderate k and m (e.g., k(m+1)<25), implementing a look-up table in this manner is in many cases still feasible.

As noted above, the most significant guard bit is not needed to index a directly addressed DLOG table, and this observation allows saving a factor of two in the size of the DLOG table. As will be described below, for p of the form p=2^m+1, p=2^m−d and p=2^m+d (d>1 and d odd), each coefficient of a field element is represented using m+2, m+1 and m+2 bits of binary data (not including guard bits), respectively, instead of m bits as for p=2^m−1. Directly addressed DLOG tables for p of forms other than p=2^m−1, therefore, are correspondingly larger than directly addressed DLOG tables for p of the form p=2^m−1.

An exemplary DLOG table1000 illustrating concepts described above for the single-guard-bit representation is shown inFIG. 10A for the simple case of GF(3²) where p=2^m−1 for m=2. The example inFIG. 10A was constructed for GF(3²) using the generator g(t)=t and the irreducible polynomial p(t)=t²+t+2. Such a DLOG table can be implemented, for example, using an 8-bit, 16-bit, 32-bit, etc., architecture. As noted previously, choosing an appropriate generator and irreducible polynomial for a given finite field GF(p^k) is within the purview of one of ordinary skill in the art.

The exemplary DLOG table1000 illustrated inFIG. 10A comprises memory addresses1001 corresponding to the field elements a(t) in binary form and storedvalues1003 corresponding to the associated integers x in binary form. In addition, the exemplary DLOG table1000 comprises 2^k(m+1)=2⁶=64 rows (entries)1005. In the example ofFIG. 10A, each memory address comprises a k(m+1)=2(2+1)=6-bit string, and the left-most bit of eachmemory address1001 corresponds to the most significant guard bit of a corresponding field element. This most significant guard bit can be eliminated from the memory addresses1001, if desired, allowing the DLOG table1000 to be indexed by binary strings k(m+1)−1 bits in length.

The memory addresses1001 comprise groups of data bits corresponding to coefficients of field elements in the manner previously described. Eachmemory address1001 further comprises a plurality ofguard bits1005

The storedvalues1003 of the DLOG table1000 are illustrated as being functionally adjacent to the memory addresses1001 for purposes of illustration. Each storedvalue1003 comprises binary data representing an integer x as defined above.Reference information1050 is presented inFIG. 10B in a manner that is aligned via rows with the information in the DLOG table1000 shown inFIG. 10A. Thereference information1050 inFIG. 10B is not part of the DLOG table1000 and is merely provided for convenience to reflect the association between the binary information shown in the DLOG table1000 and the field elements a(t) in polynomial form and the actual integer values x. Various blank entries denoted by “--” are present in the “x” and “a(t)” columns of bothFIG. 10B andFIG. 10A. These blank entries stem from two considerations. First, some blank entries reflect the fact that there is no integer x that satisfies g^x=0 for the field element “0” (a(t)=0), as is known to those of ordinary skill in the art. Other blank entries correspond tomemory addresses1001 having a “one” in any corresponding guard-bit position. As noted above, these entries are not used in the exemplary DLOG table1000.

In the above-described direct-addressing example, the DLOG table1000 has reserved memory locations that are not used for look-up operations corresponding to the two types of blank entries described above. The majority of these blank entries are associated with memory addresses having a “one” in any guard-bit position. However, compact DLOG tables can be implemented without such blank entries. For example, instead of associating field elements with consecutive memory addresses, binary data representing field elements a(t) with only zeros at guard-bit positions can be stored in a DLOG table. Corresponding values for x=DLOG(a(t)) can also be stored in the DLOG table. The stored a(t) entries and x entries can be associated with each other such that looking up a given a(t) entry returns the corresponding x entry. This approach does not have the simplicity of using consecutive binary data corresponding to a(t) entries as addresses, but it does have the advantage of requiring less memory space.

In one aspect of the present invention, a multiple-guard-bit representation can be used to obtain compact tables without significantly complicating the look-ups, as will be described later. In general, such a compact DLOG table can be configured with 2^km+1reserved memory locations (e.g., viewed as 2^kmrows with 2 entries per row), all of which can be used for look-up operations. Alternatively, such a compact DLOG table can be implemented using 2^kmreserved memory locations if the most significant guard bit is eliminated. In comparison, a directly addressed DLOG table comprises 2^k(m+1)reserved memory locations (or 2^k(m+1)−1reserved memory locations if the most significant guard bit is eliminated). Thus, utilizing a compact DLOG table can be useful for computations involving relatively larger field elements (e.g., field elements represented by binary data of greater than 25 bits including guard bits).

Exemplary aspects of ANTILOG tables according to the present invention will now be described. ANTILOG tables according to the present invention are similar to DLOG tables described above. In particular, ANTILOG tables also contain binary information representing the quantities x and a(t). However, ANTILOG tables are indexed (addressed) by binary data representing the quantity x=DLOG(a(t)). Thus, for a memory address corresponding to a given value of x, the looked-up quantity is a(t)=ANTILOG(x). Given that ANTILOG tables are indexed by x instead of a(t) (as for DLOG tables), ANTILOG tables are considerably smaller than corresponding DLOG tables. In particular, ANTILOG tables have p^k−1 reserved memory locations regardless of the functional form of p. The fact that there are p^k−1 reserved memory locations instead of p^kreserved memory locations stems from the fact that there is no integer x corresponding to the field element a(t)=g^x=0.

An exemplary ANTILOG table1100 is shown inFIG. 11A for the simple case of GF(3²) for the single-guard-bit representation where p=2^m−1 and m=2. The example inFIG. 11A was constructed for GF(3²) using the generator g(t)=t and the irreducible polynomial p(t)=t²+t+2. Such an ANTILOG table can be implemented, for example, using an 8-bit, 16-bit, 32-bit, etc., architecture. The exemplary ANTILOG table1100 illustrated inFIG. 11A comprises memory addresses1101 corresponding to integers x in binary form and storedvalues1103 corresponding to the associated field elements a(t) in binary form.

The memory addresses1101 of the exemplary ANTILOG table1100 are illustrated inFIG. 11A as being functionally adjacent to the storedvalues1103 for purposes of illustration. Each storedvalue1103 comprises groups of data bits representing coefficients of field elements in the manner previously described. Each storedvalue1103 further comprises a plurality ofguard bits1105 whose entries are zeros.

As noted above, DLOG tables and ANTILOG tables according to the present invention can be stored using any suitable hardware architecture (e.g., 8-bit, 16-bit, 32-bit, etc.). In addition, as noted above, directly addressed DLOG tables can be implemented with consecutive binary data representing field elements used as memory addresses. Alternatively, compact DLOG tables can be implemented that do not use direct addressing as described above. Such compact DLOG tables use less memory space but do not allow indexing directly by binary data representing field elements, and a more time-consuming table look-up is needed for compact DLOG tables. However, in the multiple-guard-bit representation described below, a considerably more compact DLOG table can be provided (approximately afactor 2^ksmaller) that still allows direct addressing and in which only a very small decrease in efficiency is encountered with regard to table look-ups.

Memory requirements for directly addressed look-up tables for the single-guard-bit representation for p=2^m−1 are as follows. For a directly addressed DLOG table, each row contains the binary form of an integer x of size k*log₂(p)≈km bits, and (not including the most significant guard bit) the table is indexed by (k−1)(m+1)+m=k(m+1)−1 bit binary strings corresponding to the field elements. Thus, the size of the DLOG table is roughly km2^k(m+1)−1bits. For the ANTILOG table, each entry contains at most a k(m+1)-bit string, and there are p^k−1 entries. Thus, the size is k(m+1)(p^k−1) bits, which is roughly equal to k(m+1)2^kmbits. Accordingly, the DLOG table is roughly afactor 2^k−1larger than the ANTILOG table.

It is possible to reduce table sizes even further (for both the single-guard-bit representation and the multiple-guard-bit representation) at the cost of carrying out a larger number of multiplications. For example, the aforementioned Karatsuba's method for multiplying polynomials of degree k works by replacing a single multiplication of two degree-k polynomials with three multiplications, each involving polynomials of degree k/2. Those of ordinary skill in the art will recognize that above-described exemplary multiplication according to the present invention can be similarly modified to use tables of smaller size in conjunction with more table look-ups. For instance, if S is a table size for carrying exemplary multiplication according to the present invention as described above, a modification can be made wherein tables of size S^1/2are used in conjunction with three times as many table look-ups. Notwithstanding the increased cost in table look-ups, this approach can be desirable for memory-constrained environments.

In view of the discussion above with regard to GF_p_k_MUL and the corresponding DLOG and ANTILOG tables, it can be seen that the above-described exemplary approach for carrying out multiplication of field elements of GF(p^k) according to the present invention differs significantly from conventional approaches. First, in comparison to approaches for binary finite fields with characteristic p=2, the present approach stores binary data representing field elements differently by utilizing guard bits. Accordingly, the DLOG and ANTILOG tables according to the present invention also possess guard bits, such as illustrated inFIGS. 10A and 11A, whereas the look-up tables for conventional approaches involving binary finite fields do not possess (or require) guard bits.

In addition, in comparison to conventional approaches for multiplication of field elements of an odd-characteristic finite field, the present method accomplishes the multiplication task with significantly fewer operations. In particular, with regard to the extension field GF(p^lk) referred to above in the discussion regarding SUM(α, β) and PRODUCT(α, β), each element of the extension field is represented as a vector (polynomial) of length l, where each component (coefficient) is stored according to the single-guard-bit representation. Multiplying two elements in the extension field requires approximately 3l²operations rather than (lk)²operations as would be required using conventional approaches. Thus, even for relatively small values of k, a significant increase in computational speed is achieved.

In another aspect of the invention relating to multiplications of field elements of an odd-characteristic finite field, a dedicated hardware apparatus can be provided for carrying out operations of GF_p_k_MUL illustrated inFIG. 9.FIG. 12 is a functional block diagram illustrating such an exemplary hardware apparatus. In particular, theexemplary apparatus1200 illustrated inFIG. 12 provides another approach for generating third binary data, denoted as c inFIG. 4, that can represent the product of a first field element and a second field element of GF(p^k). InFIG. 12, solid lines represent electrical connections for the flow of data, and dotted lines represent electrical connections for the flow of control signals. Theapparatus1200 is described here in the discussion pertaining to the single-guard-bit representation, but theapparatus1200 is equally applicable to a multiple-guard-bit representation, which is described later. Moreover, theapparatus1200 is independent of the form of the characteristic value p (i.e., p=2^m±1 or p=2^m±d).

Theapparatus1200 comprises afirst register1201 and asecond register1203 for holding first binary data (register contents “a”) and second binary data (register contents “b”), respectively. The first binary data and the second binary data represent field elements of the finite field GF(p^k). Here, it is assumed that the first and second binary data in the first and

second registers

1201 and1203 are already configured with zeros at appropriate guard-bit locations. However, guard-bit insertion and removal circuits, such as described with regard toFIGS. 7 and 8 could also be included if desired such that initial binary data without guard bits could be input to theapparatus1200. Theapparatus1200 also comprises a combinatorial logic and clock device (clock/logic)1205, a first multiplexer1207 (MUX1), a DLOG look-up memory1209, and an ANTILOG look-up memory1211. The DLOG and ANTILOG look-up memories can be implemented, for example, using a random access memory (RAM) or a flash memory. Theapparatus1200 also comprises aregister1213 for holding the binary quantity DLOG(a), aregister1215 for holding the binary quantity DLOG(b), an addition gate (+)1217 (also referred to as an adder), and aregister1219 for holding the integer value p^k−1 in binary form, which can be received, for example, from a processor. Alternatively, a specialized circuit can be provided along with theregister1219 to generate the value p^k−1 upon input of values for p and k. Configuring such a specialized circuit is within the purview of one of ordinary skill in the art. Theapparatus1200 also comprises a modulo arithmetic circuit1221 (MOD) for computing the remainder of an input quantity divided by p^k−1, which is supplied byregister1219. Thecircuit1221 can be conventional modular arithmetic hardware known to those of ordinary skill in the art and does not need to be described further. Theapparatus1200 further comprises a second multiplexer1223 (MUX2) and anoutput register1225 for holding third binary data “c” resulting from computations within the apparatus. The clock/logic unit1205 can also have an output terminal (not shown) for providing a signal to be input to another hardware apparatus to initiate computations in another hardware apparatus when computations in theapparatus1200 are complete. For example, another hardware apparatus can be anotherapparatus1200 or anaddition apparatus600 such as illustrated inFIG. 6.

The operation of theexemplary apparatus1200 illustrated inFIG. 12 will now be described. First, the DLOG look-up memory1209 and the ANTILOG look-up memory1211 are initialized once with appropriate discrete logarithm and anti-logarithm data. This can be accomplished by providing an initial programming signal to the clock/logic unit1205 via the line labeled s, and by simultaneously supplying discrete logarithm and anti-logarithm data to the DLOG look-up memory1209 and the ANTILOG look-up memory1211, respectively, via external data buses labeled eD1 and eD2. At the same time, address data is supplied to theDLOG memory1209 and to theANTILOG memory1211 by external address buses eA1 and eA2, respectively, viaMUX11207 andMUX21223, respectively. As noted above, the look-up

memories

1209 and1211 can be implemented with RAM or flash memory, for example. Alternatively, if theapparatus1200 is to be dedicated for particular values of p and k, the look-up

memories

1209 and1211 can be implemented using ROM, and pre-computations of the discrete logarithm and antilogarithm data can be done once and loaded into the ROM at manufacture.

With the look-up

memories

1209 and1211 initialized, first binary data representing a first field element and second binary data representing a second field element can be input on lines labeled a and b to thefirst register1201 and thesecond register1203, respectively. It is assumed that the first binary data and the second binary data are already configured with zeros at appropriate guard-bit positions. Alternatively, guard-bit insertion circuits can be utilized to insert appropriate guard bits before loading the first binary data and second binary data into the first and

second registers

1201 and1203, respectively, such as described with regard toFIGS. 7 and 8. Binary data representing the quantity p^k−1 are input on the line labeled “p^k−1” to theregister1219. The first binary data, the second binary data, the discrete logarithm and antilogarithm data, and the binary data representing the quantities p and k can be provided, for example, from a processor (not shown) or from one or more hardware apparatuses (not shown). For example, anaddition apparatus600 as illustrated inFIG. 6 or7 can be used to provide at least some of this data (e.g., first binary data and second binary data) via a conventional routing circuit.

Computation is initiated by a start signal on the line labeled s as shown inFIG. 12. The start signal can also be provided from a processor (not shown) or from one or more hardware apparatuses (not shown). When the values of the first binary data and second binary data in the

registers

1201 and1203 are stable, a signal s1 locks those values into the first and

second registers

1201 and1203, respectively. When values of the binary data representing the quantity p^k−1 inregister1219 are stable, a signal s5 locks those values inregister1219. A signal s2 is then input toMUX11207 which then passes the contents, a, of thefirst register1201 to theDLOG memory1209 to access theDLOG memory1209. When the output values from the DLOG memory are stable, the output values are locked intoregister1213 by a signal s4.Register1213 now holds the value of DLOG(a). Another signal s2 is then input toMUX21223 which then passes the contents, b, of thesecond register1203 to theDLOG memory1209 to access theDLOG memory1209. When the output values from the DLOG memory are stable, the output values are locked intoregister1215 by a signal s3.Register1213 now holds the value of DLOG(b). Theadder1217 then computes the integer sum of the contents of

registers

1213 and1215 and sends the result to the modulo arithmetic circuit1221 (MOD) to compute the remainder of the value input thereto when divided by the quantity p^k−1, which is available fromregister1219. The output from MUX2 is then input to theANTILOG memory1211 to access theANTILOG memory1211. When the output values from theANTILOG memory1211 are stable, the output values are locked intoregister1225 by a signal s6.Register1225 now holds the value ANTILOG{(DLOG(a)+DLOG(b)) mod (p^k−1)} in the single-guard-bit representation, which is available for output as register contents, c. If desired, however, a guard-bit-removal circuit, such as illustrated inFIGS. 7 and 8, could be placed functionally between theANTILOG memory1211 and theregister1225 to remove guard bits from the result of the computations. This completes the description of theexemplary multiplication apparatus1200 illustrated inFIG. 12.

In theapparatus1200 as described, thefirst register1201 and a processor (not shown) can be viewed as means for storing first binary data. Alternatively, thefirst register1201 and a guard-bit insertion circuit (not shown) can be viewed as means for storing first binary data. Thesecond register1203 and a processor (not shown) can be viewed as means for storing second binary data. Alternatively, thesecond register1203 and a guard-bit insertion circuit (not shown) can be viewed as means for storing second binary data. Further, theregister1225 can be viewed as means for storing third binary data. Moreover, the clock/logic device1205 and any or all of the remaining devices illustrated inFIG. 12 can be viewed as means for executing at least one operation on the first binary data and the second binary data.

Addition Using Multiple-Guard-Bit Representation, p=2^m−1

Exemplary aspects of the invention pertaining to addition of field elements where p=2^m−1 are now described for the multiple-guard-bit representation. Here it is assumed that invention is implemented using a hardware architecture operating on at least 2km bit quantities (i.e., registers are at least 2km bits in size). The invention according to the multiple-guard-bit representation may be implemented, for example, using thesystem100 illustrated inFIG. 1, which has already been described. In addition, dedicated hardware apparatuses, such as illustrated inFIGS. 6, 7,8 and12 and which have already been described, may also be used to implement the invention according to the multiple-guard-bit representation. Descriptions of these apparatuses are not reproduced here. However, appropriate modifications to the apparatuses illustrated inFIGS. 6, 7,8 and12 for the multiple-guard-bit representation, where necessary, will be described below.

The representation of field elements of GF(p^k) in the multiple-guard-bit representation was described previously in the discussion pertaining to the example ofFIG. 2C. As noted in that discussion, elements of a finite field are stored as binary strings, but instead of having only one guard-bit position between adjacent groups of data bits representing coefficients of a field element, a plurality of guard-bit positions (e.g., m guard-bit positions) are provided between adjacent groups of bit positions that are allocated to store binary data representing the field coefficients of a field element. For example, as illustrated inFIG. 2C for GF(3⁸), eight groups of bit positions221-r(unshaded bit positions) are allocated to store binary data representing field coefficients α_7,i, . . . , α_1,i, α_0,i, and adjacent groups of bit positions221-rare separated by groups of two guard-bit positions213-r(lightly shaded bit positions). The guard-bit positions are initialized to each contain a binary value of zero.

An implementation of an exemplary form of GF_p_k_ADD for the field GF(p^k) where p=2^m−1 is now described for the multiple-guard-bit representation. To perform the addition of two field elements α_iand β_iusing first and second binary data stored in first and second registers according to the multiple-guard-bit representation, the operations associated with GF_k_ADD are in principle the same as those for the single-guard-bit representation. Only the number of guard-bit positions between adjacent groups of data bits representing field coefficients and the forms of the first and second predetermined binary quantities, M1 and M2, are changed. Where multiple guard-bit positions (e.g., “m” guard-bit positions) are configured between adjacent groups of data bits associated with field coefficients, the approach proceeds as previously described with regard toFIG. 4. That is, M1 is assigned to have values of zero at bit positions corresponding to bit positions of first guard bits in the first register and binary values representing thequantity 2^m−1 at bit positions corresponding to bit positions of groups of first data bits in the first register. M2 is given by M2=NOT(M1). Then, in a manner similar to that described above for the single-guard-bit representation, third binary data representing the sum of the first and second field elements of GF(p^k) can be generated by carrying out the operations in Equation 19
c=((a+b)&M1)+(((a+b)&M2)>>m) (19)
where a and b represent contents of the first and second register, respectively, in which the first and second binary data are stored according to the multiple-guard-bit representation and where c represents the resulting contents of a third register holding third binary data also stored according to the multiple-guard-bit representation. The explanation of how the above-noted operations result in correctly providing third binary data representing a third field element of GF(p^k) equal to the sum of the first and second field elements is the same as described above for the single guard-bit representation and is not repeated here.

As noted above, hardware apparatuses illustrated inFIGS. 6, 7 and8 can be used to implement the invention according to the multiple-guard-bit representation. No modifications to theapparatus600 illustrated inFIG. 6 are necessary in this regard. It is merely necessary to recognize that the first and second binary data are stored in the first and

second registers

601 and603 according to the multiple-guard-bit representation and that the first and second predetermined binary quantities M1 and M2 are configured as described above.

For the multiple-guard-bit representation, a modification to theaddition apparatus700 illustrated inFIG. 7 is required in the sense that the guard-bit-insertion circuits701′ and703′ and the guard-bit removal circuit709′ must be configured to insert multiple guard bits, instead of a single guard bit, between adjacent groups of data bits representing coefficients of a field element. In this regard, the exemplary guard-bit-insertion circuit800 illustrated inFIG. 8A can be configured such that theelectrical connections811 are displaced wherein more than one guard-bit position809 without anelectrical connection811 is inserted between adjacent groups ofbit positions807 in theregister805. Similarly, the exemplary guard-bit-removal circuit820 illustrated inFIG. 8B can be configured such that theelectrical connections831 are displaced to remove more than one guard-bit position between adjacent groups ofbit positions807 in theregister825. With such modifications for the multiple-guard-bit representation, the operation of theapparatus700 illustrated inFIG. 7 is the same as previously described.

Multiplication Using Multiple-Guard-Bit Representation

Implementations of exemplary forms of GF_p_k_MUL for the field GF(p^k) will now be described for the multiple-guard-bit representation. This discussion is applicable to p given by the functional forms p=2^m±1 and p=2^m±d. The only differences that occur for different functional forms of p relate to the number of bits used to store binary data representing a given coefficient of a field element and how many bits are allocated in ANTILOG tables for each coefficient of a field element. These differences will be discussed in greater detail below. The immediate discussion will proceed for the case where p=2^m−1 for which m bits are used to store each coefficient of a field element, but the discussion is applicable to the other functional forms for p noted above.

In a first exemplary implementation of GF_p_k_MUL for the multiple-guard-bit representation, a compression function is used to more efficiently utilize memory space allocated for DLOG and ANTILOG tables. This approach uses directly addressed DLOG and ANTILOG tables in a manner somewhat similar to that described above for the single-guard-bit representation, but the forms of the directly addressed DLOG and ANTILOG tables are different. In particular, to save memory space allocated for the DLOG and ANTILOG tables, the DLOG and ANTILOG are configured without guard bits (making them about km2^kmbytes in combined size). For a directly addressed DLOG table, where binary data corresponding to field elements are used as memory addresses, eliminating guard bits from the DLOG table means that the total number of consecutive memory addresses are reduced. Thus, the number of reserved memory locations are also reduced. For the ANTILOG table, which is also directly addressed and which uses binary data representing integers x=DLOG(a(t)) as memory addresses, eliminating guard bits reduces the number of bits used to store binary data representing field elements a(t), thereby reducing memory requirements. To utilize such tables, binary data representing field elements of GF(p^k) stored in the multiple guard representation are compressed before carrying out a DLOG table look-up. In addition, resulting binary data is then decompressed after carrying out an ANTILOG table look-up. This is now described in greater detail.

Here it is assumed that field elements are stored according to the multiple-guard-bit representation with m guard bits between adjacent groups of data bits that represent coefficients of a field element. However, the present approach is not limited to m guard bits between adjacent groups of data bits and modifications for multiple guard bits other than m guard bits between adjacent groups of data bits will be apparent from the discussion below. Let t=INT(k/2) where INT(k/2) is the integer value of k/2 rounded down to nearest integer. A compression can be executed on register contents, a, stored in the multiple-guard-bit representation using a compression function (COMP) given by
COMP(a)={(aXOR(a>>(2t−1)m))&M3} (20)
where M3 is predetermined binary quantity representing thevalue 2^km−1 so that COMP(a) has km bits. (The XOR can be replaced by a bitwise OR-operation in equation 20 above.) The COMP function moves groups of data bits representing field coefficients (that is, relevant, information-carrying data) from bit-position blocks2jm, . . . , (2j+1)m−1, where j≧t, to the reserved guard-bit-position blocks (2(j−t)+1)m, . . . , (2(j−t)+2)m−1. This is shown, for example, inFIG. 13 which illustrates the above-noted mapping of bit positions from aregister1301 to bit positions of aregister1302 where uncompressed data inregister1301 is compressed intoregister1302. Dottedoblique lines1303 illustrate the mapping of bit-position blocks shifted relative to their original positions. Dottedvertical lines1304 illustrate the mapping of bit position blocks which are not shifted relative to their original positions. As illustrated inFIG. 13 for the case of GF(3⁸) where t=4 and m=2 (because p=2^m−1), as an example for j=t=4, data in bit positions16 (i.e.,2jm) and17 (i.e., (2j+1)m−1) are mapped to bit positions2 (i.e., (2(j−t)+1)m) and3 (i.e., (2(j−t)+2)m−1). Other data blocks are similarly mapped. Accordingly, no groups of data bits representing coefficients of a field element are lost in the above-noted operations. The directly addressed DLOG table is configured such that the memory addresses correspond to COMP values of associated field elements for fast look-up. The directly addressed ANTILOG table stores COMP values of binary data representing field elements. Moreover, all entries in the DLOG and ANTILOG tables will contain relevant (i.e., information-carrying) data. Hence, there is no empty or unused space in the DLOG and ANTILOG tables.

A decompression of compressed binary data can be carried out using a decompression function (DECOMP) in an analogous manner. Let M4 be a predetermined binary quantity with ones in bit-positions2jm,2jm+1,2jm+2, . . . , (2j+1)m−1, where j=0, 1, . . . , k−1, and zeros elsewhere. Then
DECOMP(z)={(zXOR(z<<(2t−1)m))&M4} (21)
where, again, the XOR can be replaced by a bitwise OR-operation and <<(2t−1)m represents a left shift by (2t−1)m bits. The mask M4 will make sure that guard-bit positions contain only zeros. After a table look-up using the ANTILOG table has been carried out, the value is decompressed by the above DECOMP function. Hence, if a and b are first and second binary data (register contents of first and second registers) stored according to the multiple-guard-bit representation where a and b represent first and second field elements α_iand β_jof GF(p^k), a full multiplication of α_iand β_jin GF(p^k) can be achieved by executing the operations given in Equation 22
c=DECOMP(ANTILOG{(DLOG{COMP(a)}+DLOG{COMP(b)})mod(p^k−1)}) (22)
where c is third binary data that can be stored in a third register and that represents a third field element equal to the product of the first and second field elements. Thus, nine fast operations and one modular addition can be carried out to effectively perform k²multiplications in parallel. By implementing GF_p_k_MUL in this exemplary manner, computations can be easily carried out in extension fields of the type GF(p^lk) via the algorithms PRODUCT(α, β) and REDUCE(δ, f) described earlier.

In a second exemplary implementation of GF_p_k_MUL for the multiple-guard-bit representation, it is possible to multiply field elements of GF(p^k) without utilizing the above-noted compression and decompression functions. In this exemplary approach, the operations associated with GF_p_k_MUL are in principle the same as those for the single-guard-bit representation described above with regard toFIGS. 9-12. Only the number of guard-bit positions between adjacent groups of data bits representing field coefficients in a given register and the form of the DLOG and ANTILOG tables1000 and1100, respectively, are changed. In this regard, field elements are stored according to the multiple-guard-bit representation as described above and as illustrated, for example, inFIG. 2C. Moreover, the DLOG and ANTILOG tables are similar in form to the exemplary tables shown inFIGS. 10A and 11A, respectively, but are modified such that more than one guard-bit is provided between adjacent groups of data bits representing field coefficients. For example, the exemplary DLOG table1000 illustrated inFIG. 10A can be modified for the multiple-guard-bit representation by providing more than one guard bit1009 (e.g., m guard bits) between adjacent groups of data bits1007. Similarly, the exemplary ANTILOG table1100 illustrated inFIG. 11A can be modified for the multiple-guard-bit representation by providing more than one guard bit1109 (e.g., m guard bits) between adjacent groups of data bits1107. With such modifications, multiplication in the multiple-guard-bit representation can be carried out in the same manner as described above with reference toFIGS. 9-12. Of course, this immediate approach does not have the benefit of saving memory space as described above with regard to the form of GF_p_k_MUL for the multiple-guard-bit representation that utilizes compression and decompression functions.

Other Computations Using Single-/Multiple-Guard-Bit Representation, p=2^m−1

Some other operations that can be easily performed using the single- and/or multiple-guard-bit representation will now be described. First, scalar multiplication can easily be carried out using the multiple-guard-bit representation. Scalar multiplication, i.e. multiplying an element α_i=(α_k−1,i, . . . , α_1,i, α_0,i) of GF(p^k) by some γ in the ground field GF(p), can be carried out in the multiple-guard-bit representation without the use of tables whatsoever. It is desired to compute the following quantity
γ·α=(γα_k−1,imodp, . . . ,γα_1,imodp,γα_0,imodp). (23)
As noted inSeminumerical Algorithmsreferred to above, for p=2^m−1, multiplication modulo p of two binary quantities u and v, both assumed to be in the

range

0, 1, . . . , p, can be performed in accordance with the relations

\begin{matrix} \begin{matrix} uv \mod p = {(uv \mod 2^{m}) + (uv div 2^{m})} \mod p \\ = {(uv & (2^{m} - 1)) + (uv >> m)} \mod p . \end{matrix} & \begin{matrix} (24) \\ (25) \end{matrix} \end{matrix}

Because u<2^mand v<2^m, it is clear that uv<2^2m. Let u be binary data representing α_istored in a first register according to the multiple-guard-bit representation, and let v be binary data representing γ (an element of GF(p)) stored in a second register according to the multiple-guard-bit representation where v has binary values representing the quantity γ in the right-most bit positions and zeros elsewhere. In other words, if v were viewed as binary data representing a vector quantity, the vector quantity would be (0, 0, . . . , 0, γ). Then, k modular multiplications can be performed in parallel by executing the following operations
c′=uv (26)
c=GF_—p_—k_ADD(c′&M1,(c′>>m)&M1) (27)
where M1 is a predetermined binary quantity with ones in bit-positions2jm, . . . , (2j+1)m−1 and binary values representing thequantity 2^m−1 elsewhere (j=0, 1, . . . , t, where t is defined as above), and where GF_p_k_ADD is the exemplary addition algorithm for the multiple-guard-bit representation as described above. In this regard, the multiplication of u and v in Equation 26 can be normal multiplication of register contents as conventionally carried out by known processors (e.g., integer multiplication or floating-point multiplication). Alternatively, the multiplication of u and v in Equation 26 can be carried out using table look-ups as described above with reference toFIG. 9. Hence, the convolution (multiplication) in this representation can be done in 4+5=9 simple operations, rather than 2k multiplication and modular reduction operations as would be conventionally required.

A special case of scalar multiplication is doubling. The field quantity α_i+α_i(or 2α_i) given α_ian element of GF(p^k) can be determined by executing the following operations
c′=a<<1 (28)
c=(c′&M1)+((c′&M2)>>m) (29)
where a is binary data representing α_istored according to the single-guard-bit representation or the multiple-guard-bit representation, and where M1 and M2 are predetermined binary quantities (mask quantities) defined as described above for either the single-guard-bit representation or the multiple-guard-bit representation as appropriate. Accordingly, it can be seen that doubling can be accomplished using five efficient operations.

Another computation that can be carried out is equality testing. For example, testing whether binary data, a, representing a field element of GF(p^k) represents the zero element can be done by checking whether a=2a, where the doubling is performed as described directly above. Because the characteristic, p, is odd, the quantity 2a can never be zero unless a=0. In principle, it would be desirable to test directly whether a=0 using a single word-operation. However, because theelement 0 in the ground field GF(p) has two representations (0 and p), it is possible for the binary data a to represent 0, even if all bits of the binary data a are not identically equal to zero. Thus, the doubling operation provides a convenient approach for testing whether a quantity is equal to zero. This approach can be applied for both the single-guard-bit representation and multiple-guard-bit representation.

Another computation that can be carried out is determining the additive inverse of a field element of GF(p^k), i.e., given a, it is desired to determine “−a” such that a+(−a)=0. Given first binary data, a, stored according to either the single-guard-bit representation or the multiple-guard-bit representation representing a field element of GF(p^k), it is possible to determine second binary data, c, representing the additive inverse field element as follows. Let z be binary data representing the quantity (p, p, . . . , p) in GF(p^k). That is, z comprises k groups of data bits with guard bits therebetween in the appropriate locations, wherein each group of data bits holds the binary equivalent of p (e.g., z may be pre-computed and treated as a constant). Then, c=−a can be determined by executing the single word operation
c=z−a, (30)
where “−” is the normal subtraction operator on words. From this it follows that general equality testing, i.e. determining whether a=b, can be done by checking whether a+(−b)=0, i.e. first using the above technique for additive inverse, then the aforementioned method for testing if an element is zero.

Another computation that can be carried out is the multiplicative inverse. In a multiplicative group of size s, it is true that x^s=1 for every x. In other words, for any x in the field, x⁻¹=x^s−1. For the finite field GF(p^k), the multiplicative group has size s=p^k−1. Therefore, the multiplicative inverse of a field element can be carried out by table look-ups in accordance with the relation
a⁻¹=ANTILOG{((p^k−2)·(DLOG{a})mod(p^k−1)} (31)
where first binary data, a, represents a field element of GF(p^k) and is stored according to the single-guard-bit representation or the multiple-guard-bit representation. Second binary data a⁻¹represents the multiplicative inverse field element. The above-operations in equation 35 can be carried out directly using the single-guard-bit representation using table look-ups in a manner similar to that described above with regard to the discussion of GF_p_k_MUL for the single-guard-bit representation. For the multiple-guard-bit representation, the operations in equation 35 can also be carried out directly where the DLOG look-up table is configured with multiple guard bits in the memory addresses and where the binary data stored in the ANTILOG table is configured with multiple guard bits positioned between groups of data bits representing field coefficients. Alternatively, the operations in equation 35 can be carried out for the multiple-guard-bit representation using “compressed” DLOG and ANTILOG look-up tables in conjunction with compression and decompression operations as previously described. That is, the first binary data a can be compressed using the COMP function described above prior to executing a DLOG table look-up, and a decompression operation can be carried out using the DECOMP function on resulting binary data after the ANTILOG table look-up has been carried out.

Another computation that can be carried out is exponentiation. Generalizing the multiplicative inverse discussion above, exponentiation of a field element to the n-th power can be computed by table look-ups in accordance with the relation
aⁿ=ANTILOG{(n·(DLOG{a}))mod(p^k−1)}. (32)
where a is first binary data representing a field coefficient according to either the single-guard-bit representation or multiple-guard-bit representation. In a manner like that described above, equation 36 can be implemented directly or, alternatively, it can be implemented using compression and decompression functions, if desired, prior to the DLOG table look-up and following the ANTILOG table look-up, respectively.
Assessment of Efficiency Enhancements

An assessment of efficiency enhancements obtained using the inventive approaches described above in comparison to conventional approaches are now discussed for a typical cryptographic application. From cryptographic security point of view, it is currently recommended to implement encryption using elliptic curves (seeHandbook of Applied Cryptography, referenced above) over finite fields of size approximately 2¹⁶⁰to provide sufficient complexity for the encryption schemes to be considered secure. Thus, in the case of p=3 according to the present invention, it would be necessary to use an extension of GF(3) of degree greater than 101 (i.e., 3¹⁰¹≈2¹⁶⁰). In the case of p=7 according to the present invention, the extension degree would need to be at least 57. That is, the necessary complexity could be achieved by carrying out computations in GF(3¹⁰²) or in GF(7⁶⁰), for example.

Rather than carry out computations in GF(3¹⁰²) or in GF(7⁶⁰) directly, the present invention provides for achieving the necessary complexity by carrying out the computations in an appropriate extension field GF(p^lk). For example, for p=3, the necessary complexity can be obtained by carrying out computations in the extension field GF(3^lk) where l=17 and k=6 (because 102=6·17). Similarly, for p=7, the necessary complexity can be obtained by carrying out computations in the extension field GF(7^lk) where l=12 and k=5 (because and 60=5·12). As described above, such computations will require carrying out arithmetic operations in a base field GF(p^k), which can be GF(3⁶) or GF(7⁵), respectively, in the immediate examples. In addition, it should be noted that computations in GF(3⁶) can be implemented using the single-guard-bit representation with a conventional 32-bit architecture. Moreover, computations in GF(7⁵) can be implemented using either the single-guard-bit representation or the multiple-guard-bit representation with a conventional 32-bit architecture. As described previously, the algorithms SUM(α, β) and PRODUCT(α, β) can be used to relate computations in the extension field GF(p^lk) with computations in the field GF(p^k). Various types of computations in GF(p^k) have been described above in detail, including various implementations of GF_p_k_ADD and GF_p_k_MUL.

The table below presents a summary of computational efficiency for the single-guard-bit representation and multiple-guard-bit representation according to the present invention as compared to the conventional approach for computations involving the specific finite fields of GF(3^lk) where l=17 and k=6 and GF(7^lk) where l=12 and k=5. In particular, the table below shows the approximate combined size (in bytes) of the DLOG and ANTILOG look-up tables and the number of operations needed to perform additions and multiplications in the respective fields. The number of operations required to perform multiplication using the multiple-guard-bit representation includes utilization of the compression and decompression operations described above.



Single-	Multiple
guard-bit	guard-bit	Conventional
Representation	Representation	Approach

				ops	ops		ops.	ops.		ops.	ops.
			Table	for	for	Table	for	for	Table	for	for
Field	k	l	size	add	mult.	size	add.	mult.	size	add.	mult.

GF(3^lk)	6	17	2¹⁹	85	578	2¹³	85	2890	—	102	10400
GF(7^lk)	5	12	2²¹	60	288	2¹⁶	60	1440	—	60	3600

As is evident from the table above, a large gain in efficiency over the conventional approach is achieved for multiplication using the inventive approaches described above. With regard to the indicated number of operations required for addition, it must be noted that the type of operations utilized in the single-guard-bit representation and multiple-guard-bit representation according to the present invention are mainly highly efficient, simple bit operations, whereas the type of operations associated with the conventional approach are much slower modular addition operations. Thus, it is evident that a significant gain in efficiency is also achieved for addition using the inventive approaches described above as compared to the conventional approach for carrying out addition in GF(p^k). Thus, the gains achieved using the present invention are, accordingly, even more significant than the table above may, at first glance, suggest. This same observation is also true for multiplication of field elements according to the present invention.

Considerations that are relevant in determining whether a single-guard-bit representation or a multiple-guard-bit representation will now be described. If memory consumption is not an issue, then the single-guard-bit representation is preferable due to its better computational performance. Depending on the application at hand, if addition operations are the predominant operations, then a single guard representation should be used because it enables making k as large as possible, and k additions can therefore be performed in parallel at a given time. Moreover, because the sizes of the DLOG and ANTILOG look-up tables scale with 2^k, if the additions are predominantly used rather than multiplications, it can be practical to avoid the DLOG and ANTILOG look-up tables entirely and simply use the conventional method for multiplying field elements.

If, on the other hand, multiplications are the predominant operations, the multiple-guard-bit representation is preferred because it minimizes the sizes of the DLOG and ANTILOG look-up tables. In view of the above discussion, it can be seen that the single-guard-bit representation and multiple-guard-bit representation represent, in a sense, opposite ends of a scale that involves considering trade-offs between compactness of the DLOG and ANTILOG look-up tables, ease of table look-ups, and the degree of parallelization (i.e., the number of field-element coefficients that can be represented in a single machine register). If w is the (fixed) word size of the hardware architecture (i.e., w is the register size), and m is the number of bits in the ground field GF(p), for p=2^m−1, some attributes of the single-guard-bit representation can be summarized as follows. Binary data representing k=w/(m+1) coefficients of GF(p^k) (the coefficients being elements of GF(p)) can be fit into one word, that is, into a single hardware register. This packing of binary data is optimal, for surely k<w/m is satisfied. No compression is needed before a DLOG table look-up, and no decompression is need following an ANTILOG table look-up (which is clearly optimal). The look-up tables for the single-guard-bit representation are about 2^ktimes as large as the look-up tables for the multiple guard bit representation. That is, the look-up tables for the single-guard-bit representation are bigger than the absolute minimum size required to store all elements of the field.

Some attributes of the multiple-guard-bit representation can be summarized as follows. Binary data representing k=w/(2m) coefficients of GF(p^k) (which are elements of GF(p)) can be fit into one word, that is, into a single hardware register. A small amount of computation can, and should, be devoted to compression and decompression operations associated with table look-ups, if desired, to save memory space required for DLOG and ANTILOG look-up tables. By utilizing the compression and decompression operations, the DLOG and ANTILOG tables are essentially optimal in size.

Extensions to p of the Form p=2^m+1 and p=2^m±d

In the discussion above, computations in finite fields of odd prime characteristic were described for p of the form p=2^m−1. Extensions of the above-described approaches will be described below for computations in finite fields of odd prime characteristic where p is of the form p=2^m+1 and p=2^m±d, where d is small. In principle, any values of d where d<2^mcan be used, but as will be seen, a smaller d is preferable. In particular, as discussed below, special optimizations are available when p=2^m−d, with d≦(2^m+1)/3, and p=2^m+d, with d≦p/6, which turn out to be essentially as efficient as the case d=1. Only small increases in memory requirements and computational overhead are needed for these extensions compared to the case where p=2^m−1. Whereas the above-described treatment for p=2^m−1 allowed p=3, 7, 31, etc., the extensions to p=2^m+1 and p=2^m±d allow utilization of the primes p=5, 11, 13, 17, etc. In principle, all primes are allowed, though as mentioned the invention is most beneficial where d is small as noted above. Also, the word size and memory of the hardware set some practical limits on how large a value of p may be utilized. As noted previously, where it is possible to write an odd characteristic prime p in terms of more than one functional form, it is generally preferable to utilize an approach for p=2^m−1 over approaches for the other two functional forms. In addition, it is preferable to use an approach for p=2^m+1 over an approach for p=2^m±d where d>1.

The following observation is relevant in understanding the extension to p of the form p=2^m+1 as well as for p=2^m±d. As suggested above using somewhat different notation (see e.g., equation 15) a reduction of some value e modulo p, when p=2^m−1, can be carried out in accordance with the following relation
emodp=(emod 2^m)+(ediv 2^m)=(e&(2^m−1))+(e>>m). (33)
As noted, this subtracts an integer multiple of p from e. Thus, the result is mathematically correct, and the only issue is “practical”, i.e. that the result may not always belong to the set {0, 1, . . . , p−1}, which is the conventional representation of integers modulo p. This was solved by the following observation. The representation of integers modulo p can be extended to the larger set Sp⁻={0, 1, . . . , p} such that zero has two representations, 0 and p. Then, if f and g are elements of Sp⁻, Equation 33 correctly computes (f+g) mod (p) in the dual representation where e is the binary sum of f and g. These observations will now be generalized. Let p=2^m+d (where d may be negative, but |d|<2^m). Then, for any integer e, the following relations hold
emod (p)=(emod 2^m)−d(ediv 2^m)=(e−2^m(ediv 2^m))−d(ediv 2^m) (34)
=e−(2^m+d)(ediv 2^m)=e−pr (35)
for an integer r. That is, the result is equal to e mod(p), up to an integer multiple of p. Hence, what is performed in equations 34 and 35 is a subtraction by a multiple of p. To get a complete reduction mod p such that the quantity c−pk is indeed in the set {0, 1, . . . , p−1}, the relations in Equations 34 and 35 should use k=e div p=e div (2^m+d). However, the present invention utilizes an approximation where k=e div 2^msuch that e−pk is not guaranteed to be in the set {0, 1, . . . , p−1}. For the case d=−1 (corresponding to p=2^m−1), for example, utilizing the slightly larger set Sp⁻ above allows the modular reduction operation in combination with addition to be closed with respect to the set Sp⁻ in the determination of e=f+g.

Generalizations of the algorithms GF_p_k_ADD and GF_p_k_MUL for the cases p=2^m+1 and p=2^m±d for odd |d|>1 will be described below in conjunction with determining suitable representation sets Sp corresponding to allowed values of coefficients of field elements of GF(p^k). As will be seen, the Sp sets depend on the functional form of p and on m and d, where p=2^m±d. In analogy to the above, these sets will be denoted by Sp⁺ for the case p=2^m+1, Sp^+dfor p=2^m+d, and Sp^−dfor p=2^m−d. As noted above, the coefficients of field elements of GF(p^k) themselves are elements of GF(p). It should be noted that as long as a modular reduction of a quantity c subtracts a multiple of p from c, there is mathematically no problem with allowing more general sets Sp if they are closed under addition followed by the modular reduction.

Addition and Multiplication in GF(p^k) where p=2^m+1

In the following descriptions of GF_p_k_ADD and GF_p_k_MUL for the case where p=2^m+1, it is assumed that m≧2 such that p≧5. This is because the case where p=3 is preferably addressed using the previously described approaches for addition and multiplication where p=2^m−1 (i.e., p=2²−1). Let the set Sp⁺ be given by Sp⁺={0, 1, . . . , 2p−2}. (Thus, for p=2^m+1 the present invention allows the

values

0, 1, . . . , p−2, to have two representations, whereas in the case p=2^m−1, only thevalue 0 had more than one representation.) Each coefficient of a field element of GF(p^k) is then an element of Sp⁺. Note that 2p−2=2^m+1, so that m+2 bits (not including guard bits) are used to represent a coefficient of a field element of GF(p^k), which is one more bit than was needed to represent coefficients in the set Sp⁻={0, . . . , p} utilized in the approaches for p=2^m−1.

For the case p=2^m+1, binary data representing field elements of GF(p^k) can be stored in hardware registers according to either the single-guard-bit representation or the multiple-guard-bit representation, such as described previously, except that for p=2^m+1, m+2 bits (not including guard bits) are allocated for each group of data bits representing a coefficient of a field element. For example, in the single-guard-bit representation, first binary data representing a first field element α_iof GF(p^k), wherein the first binary data comprises k groups of first data bits, can be stored as follows. Here it is assumed that (m+3)k is at most the hardware word size (i.e., register size). Let α_ibe a first field element of GF(p^k) where α_i=(α_k−1,i, . . . , α_0,i) and where each α_j,ibelongs to the set Sp⁺. A group of first data bits representing α_0,iis stored in a first register in

bit positions

0,1, . . . , m+1. A first guard bit having a value of zero is stored in the first register in bit position m+2 (a guard-bit position). Another group of first data bits representing α_1,iis stored in the first register in bit positions m+3, . . . , 2m+4, and so on. Accordingly, there is one first guard bit in every bit position v(m+3)−1 where v=1, 2, . . . —that is, every successive (m+3)-rd bit position. In other words, there is one first guard bit positioned adjacent to the most significant bit of each group of first data bits. Second binary data comprising k groups of second data bits representing a second field element of GF(p^k) can similarly be stored in a second register with one second guard bit adjacent to the most significant bit of each group of second data bits. (Here, the use of “first” and “second” merely distinguish between attributes corresponding to the first field element and the second field element, respectively.) By storing binary data representing first and second field elements of GF(p^k) in first and second hardware registers in this manner, no carry bit will propagate from one group of data bits representing a field coefficient into an adjacent group of data bits representing another field coefficient. The approach for storing binary data representing field elements according to the multiple-guard-bit representation is completely analogous, the only difference being that more than one guard-bit position is provided between adjacent groups of data bits representing field coefficients.

An exemplary form of GF_p_k_ADD where p=2^m+1 will now be described with reference to the flow diagram ofFIG. 14. The operations shown inFIG. 14 can be executed by a system such assystem100 shown inFIG. 1. Further, it is assumed that

steps

301 and303 shown inFIG. 3 have already been executed by theprocessor105 such that first binary data representing a first field element of GF(p^k) are stored in a first register (e.g., register107 shown inFIG. 1) and such that second binary data representing a second field element are stored in a second register (e.g., register109) in a manner such as described directly above. The first and second binary data can be stored according to either the single-guard-bit representation or the multiple-guard-bit representation—the approach is the same in either case. The steps illustrated inFIG. 14 then represent an exemplary implementation ofstep305 shown inFIG. 3.

As indicated atstep1401, theprocessing unit105 adds the contents, a, of thefirst register107, and the contents, b, of thesecond register109 using addition (that is, addition with a carry into the next most significant bit if necessary). The result of the addition can be stored in anotherregister111 such as illustrated inFIG. 1. As indicated atstep1403, theprocessing unit105 then executes a logical AND operation between the quantity (a+b) stored inregister111 and a first predetermined binary quantity M1 stored in one of the registers (e.g., register113). The quantity M1 has values of zero at bit positions corresponding to bit positions of first guard bits stored in thefirst register107 and has binary values representing thequantity 2^m−1 at bit positions corresponding to bit positions of each group of first data bits stored in the first register. For example, where p=5 (i.e., m=2 where p=2^m+1), the first predetermined binary quantity M1 comprises successive binary strings (0, 0, 1, 1) separated by bit values of zero (corresponding to guard-bit positions), because 2^m−1=3, which is given by (0, 0, 1, 1) in binary. The above definition for the quantity M1 is applicable to the multiple-guard-bit representation as well as to the single-guard-bit representation for the case where p=2^m+1. The result of the operations indicated atstep1403 can be referred to as first intermediate data c1 and is stored in one of registers (e.g., register115).

As indicated atstep1405, theprocessing unit105 executes a logical AND operation between the quantity (a+b) stored inregister111 and a second predetermined binary quantity M2 where M2 is given by M2=NOT(M1). The NOT operation is bitwise logical negation. The result of this operation is stored in one of registers (e.g., register117). Also indicated atstep1405, theprocessing unit105 then executes a right shift by m bits on the quantity ((a+b)&M2). The result of this operation can be stored in thesame register117 or in a different register. Atstep1407, theprocessing unit105 subtracts the quantity {((a+b)&M2)>>m} from a third predetermined binary quantity P1. The quantity P1 has values of zero at bit positions corresponding to bit positions of the first guard bits stored in the first register and has binary values representing thequantity 2^m+1 (=p) at bit positions corresponding to bit positions of each group of first data bits in the first register. For example, where p=5 (i.e., m=2) the third predetermined binary quantity P1 comprises successive binary strings (0, 1, 0, 1) separated by bit values of zero (corresponding to guard-bit positions), because 2^m+1=5 which is given by (0, 1, 0, 1) in binary. The result of the operations indicated atstep1409 can be referred to as second intermediate binary data c2 and is stored in one of the registers (e.g., register119). Atstep1409 the processor executes addition between the first intermediate binary data c1 and the second intermediate binary data c2 to generate the third binary data, represented by c, which can be stored in one of the registers (e.g., register121). According to this approach, the third binary data c represents the sum of the first field element and the second field element.

The algorithms according toFIGS. 3 and 14 have been described in terms of a specified sequence of steps to facilitate the description. However, it is not necessary to carry the steps indicated inFIGS. 3 and 14 in the exact order illustrated. Those of ordinary skill in the art will recognize that the order of steps can be varied and that some of the steps can be carried out simultaneously. For example, steps301 and303 shown inFIG. 3 can be carried out simultaneously, and

steps

1403 and1405 shown inFIG. 4 can be carried out simultaneously. Regardless of the sequence in which various operations are executed, it is merely necessary to determine the quantity c (third binary data) in accordance with the relation
c=((a+b)&M1)+(P1−{((a+b)&M2)>>m)}) (36)
where a is first binary data representing the first field element, b is second binary data representing the second field element, + represents addition, and M1, M2 and P1 are as defined above. In this regard, those of ordinary skill in the art will recognize that each group of data bits c_jof the resulting quantity c represents a value that is an element of the set Sp⁺, and each such c_jis given by c_j=(a_j+b_j) mod(p) (up to a single multiple of p), where the j subscript for the quantities a and b designate corresponding groups of data bits that represent an associated coefficient of the respective field element.

Thus, it is evident that addition of field elements in GF(p^k) where p=2^m+1 can be carried out using six simple instructions (compared to five simple instructions for p=2^m−1). Utilizing the second term (P1−{(c′&M2)>>m)}) as an additive quantity in equation 36 is, in principle, the same as subtracting the quantity ((a+b) div 2^m) modulo p, thus making equation 36 consistent with equation 33. However, implementing subtraction of a quantity q as an addition of the quantity p−q has advantages. In particular, if subtraction is implemented in a conventional way, i.e. by subtracting ((a+b) div 2^m) rather than by adding (P1−{((a+b)&M2)>>m)}), there is a possibility of encountering negative “borrows” even if no additive carries are encountered. In contrast, by utilizing the additive quantity (P1−{((a+b)&M2)>>m)}), such negative borrows can be avoided.

To prove that the approach given in equation 36 will produce correct addition results, observe that if a_jand b_jεSp⁺, then any c_jof the quantity c in equation 36 will satisfy 0≦c_j≦2^m−1+p=2p−2 (because 0≦(a_j+b_j)div 2^m≦4<p). Thus, each c_jof the quantity c in equation 36 is an element of Sp as claimed. As noted above, the reduction in equation 36 subtracts ((c_jdiv 2^m)−1)p from c_j, which is a multiple of p. Thus, each c_jwill indeed be in the set Sp⁺, and as such, equal to the remainder of (a_j+b_j) mod p, up to a (single) multiple of p.

As noted above, the treatment of addition (GF_p_k_ADD) of two field elements of GF(p^k) for p=2^m+1 in the multiple-guard-bit representation according to the present invention is substantially the same as that for the single-guard-bit representation. It is merely necessary to note that the first and second binary data representing the first and second field elements, respectively, are stored with multiple guard bits placed between adjacent groups of data bits representing coefficients of the respective field elements. Moreover, the prescriptions given above for determining the quantities M1, M2 and P1 require no modification for the multiple-guard-bit representation. Of course, applying those prescriptions to the multiple-guard-bit representation will generate different values of the quantities M1, M2 and P1 than will be generated for the single-guard-bit representation.

EXAMPLE 2

A numerical example illustrating the approach shown inFIG. 14 for p=2^m+1 will now be described with reference toFIG. 15.FIG. 15 schematically illustrates a collection of registers1501-1521 with exemplary register contents stored therein according to the single-guard-bit representation. Each register1501-1521 comprises 32 bit locations in this example according to a 32-bit architecture. In this particular example, computations are carried out using binary data representing field elements of GF(5⁶), where p=2^m+1=5, and m=2. Accordingly, m+2=4 bits are allocated for each coefficient of the field element (not including guard bits), and adjacent 4-bit groups are separated by a single guard-bit position (lightly shaded regions). In addition, in this example there are two unused bit positions (darkly shaded regions) at the most significant bit positions of each register. The computations described below can be carried out, for example, using a processing system, such asprocessing system100 illustrated inFIG. 1.

In this example, each coefficient a given field element is itself an element of the field GF(5). Values of the coefficients in GF(5) correspond to binary data according to the following associations: 0˜(0, 0, 0, 0); 1˜(0, 0, 0, 1); 2˜(0, 0, 1; 0); 3˜(0, 0, 1, 1); 4˜(0, 1, 0, 0). In addition, there is a dual representation with the following additional associations wherein two different numbers in GF(p) represent a same value: 5˜(0, 1, 0, 1), which also corresponds to 0; 6˜(0, 1, 1, 0), which also corresponds to 1; 7˜(0, 1, 1, 1), which also corresponds to 2; and 8˜(1, 0, 0, 0), which also corresponds to 3.

To begin, first binary data, a, representing a first field element given in vector notation as (0, 3, 1, 6, 3, 0) is stored in afirst register1501. In addition, second binary data, b, representing a second field element given in vector notation as (0, 7, 1, 4, 4, 0) is stored in asecond register1503. Each guard-bit position in

registers

1501 and1503 is initially assigned a value of zero. The contents of

registers

1501 and1503 are added via addition and the result (a+b) is stored in register1505 (corresponding to step1401 inFIG. 14). The contents of register1505 (a+b) are then combined with the first binary quantity M1 stored inregister1507 via a logical AND operation, and the result ((a+b)&M1) is stored in register1509 (corresponding to step1403 ofFIG. 14). In this example, the first predetermined binary quantity M1 comprises successive binary strings (0, 0, 1, 1) separated by bit values of zero (corresponding to guard-bit positions), because 2^m−1=3, which is given by (0, 0, 1, 1) in binary.

The second predetermined binary quantity M2=NOT (M1) is then formed and stored inregister1511, and the contents of register1511 (M2) are then combined with the contents of register1505 (a+b) via a logical AND operation, the result (c=((a+b)&M2)) being stored in register1513 (corresponding to step1405 inFIG. 14). The third predetermined binary quantity P1 is stored inregister1515 wherein P1 represents the repeated binary equivalent of thequantity 2^m+1 placed in adjacent 4-bit groups, each of which is separated by a bit value of zero (corresponding to guard-bit positions). In this example, the third predetermined binary quantity P1 comprises successive binary strings (0, 1, 0, 1) separated by bit values of zero (corresponding to guard-bit positions), because 2^m+1=5, which is given by (0, 1, 0, 1) in binary. The contents of register1513 ((a+b)&M2) are right shifted by m bits (e.g., 2 bits), and the result (((a+b)&M2)>>2) is stored in register1517 (corresponding to step1405 inFIG. 14). The contents of register1517 (((a+b)&M2)>>2) are subtracted from the contents of register1515 (P1) and the result (c2=P1−(((a+b)&M2)>>2)) is stored in register1519 (corresponding to step1407 ofFIG. 14). Finally, the contents of register1509 (c1) are added to the contents of register1519 (c2) using addition, and the resulting third binary data (c=c1+c2) is stored inregister1521. The resulting third binary data stored inregister1521 correspond to a field element given in vector notation as (5, 5, 7, 5, 7, 5), which is the expected result. If desired, this result can be reduced modulo 5 (which is mod(p) in this example) prior to an output operation, for example, providing the result (0, 0, 2, 0, 2, 0). This completes the discussion of Example 2.

In another aspect of the invention relating to computations involving field elements of an odd-characteristic finite field where p=2^m+1, a hardware apparatus can be provided for carrying out operations for the exemplary form of GF_p_k_ADD illustrated inFIG. 14.FIG. 16 is a functional block diagram of such an exemplary hardware apparatus. In particular, theapparatus1600 illustrated inFIG. 16 provides another approach for generating third binary data, denoted as c inFIGS. 14 and 16, that can represent the sum of a first field element and a second field element of GF(p^k). Theapparatus1600 is applicable to both the single-guard-bit representation and the multiple-guard-bit representation.

Thehardware apparatus1600 illustrated in the functional block diagram ofFIG. 16 shares various common features and operational aspects with theapparatus600 illustrated inFIG. 6, and like features are given like reference numerals inFIGS. 6 and 16. Discussion of aspects of theapparatus1600 that are common to theapparatus600 will not be duplicated here. Rather, aspects in which theapparatus1600 differs from theapparatus600 will be discussed.

Theapparatus1600 possesses several features not found in theapparatus600. In particular, theapparatus1600 possesses anadditional register1625 for holding the third predetermined binary quantity P1 and asubtraction gate1627 for subtracting the output from the right-shift gate1619 from the contents (P1) of theregister1625. The output from thesubtraction gate1627 is fed back into theregister1603 as indicated. In contrast, as illustrated inFIG. 6, theapparatus600 has no register analogous to register1625 and no subtraction gate analogous tosubtraction gate1627. Rather, for theapparatus600 illustrated inFIG. 6, the output from the right-shift gate619 is fed directly intoregister603 illustrated therein. By providing theregister1625 and thesubtraction gate1627 in the manner illustrated inFIG. 16B, theapparatus1600 is enabled to manipulate data in a manner corresponding to step1407 illustrated inFIG. 14. In other respects, theapparatus1600 operates like theapparatus600 illustrated inFIG. 6, and no additional discussion of the like aspects inFIG. 1600 is required.

In theapparatus1600 as described above, thefirst register1601 and a processor (not shown) can be viewed as means for storing first binary data such as described with regard toFIG. 6. Thesecond register1603 and a processor (not shown) can be viewed as means for storing second binary data. Further, theregister1621 and/or theregister1609 can be viewed as means for storing third binary data. Moreover, the clock/logic device1605 and any or all of the remaining devices illustrated inFIG. 16 can be viewed as means for executing at least one operation on the first binary data and the second binary data.

In another exemplary aspect of the invention, theaddition apparatus1600 used for p=2^m+1 can be modified, such as shown for thehardware apparatus1700 illustrated in the block diagram ofFIG. 17, for a situation in which a dedicated choice of the finite field GF(p^k) is made and remains unchanged. That is, the quantities m, p, and k, as well as the choice of whether the representation is a single-guard-bit representation or a multiple-guard-bit representation, are fixed, and thehardware apparatus1700 is dedicated to those choices. In this situation, thehardware apparatus1700 can receive initial binary data representing field elements wherein the initial binary data are not configured with zeros in guard-bit positions. Rather, thehardware apparatus1700 itself configures the initial binary data with zeros in appropriate guard-bit positions to generate first and second binary data without the need for a processor to configure the first and second binary data with zeros in guard-bit positions. Thehardware apparatus1700 illustrated inFIG. 17 will now be described.

Thehardware apparatus1700 illustrated in the functional block diagram ofFIG. 17 shares various common features and operational aspects with theapparatus1600 illustrated inFIG. 16, and like features are given like reference numerals inFIGS. 16 and 17. Discussion of aspects of theapparatus1700 that are common to theapparatus1600 will not be duplicated here. Rather, aspects in which theapparatus1700 differs from theapparatus1600 will be discussed.

Theapparatus1700 possesses several features not found in theapparatus1600. In particular, theapparatus1700 possesses guard-bit-insertion circuits1701′ and1703′ (GB insertion) and a guard-bit-removal circuit1709′ (GB removal). The guard-bit-insertion and guard-bit-removal circuits,1701′,1703′ and1709′ can be implemented, for example, using circuits similar to those shown in the examples ofFIGS. 8A and 8B, which have already been described. As shown inFIG. 17, the guard-bit-insertion circuits1701′ and1703′ are functionally arranged at the input to thehardware apparatus1700, and the guard-bit-removal circuit1709′ is functionally arranged between theregister1709 and theoutput register1721. The guard-bit-insertion circuits1701′ and1703′ operate to receive initial binary data a′ and b′ (without guard bits) corresponding to first and second field elements of GF(p^k) and to insert appropriate guard bits into that data. In other words, the guard-bit-insertion circuits1701′ and1703′ transform the initial binary data a′ and b′ into first binary data and second binary data having guard bits, in particular, with zeros at guard-bit positions. The guard-bit-removal circuit1709′ has the opposite function—namely, to receive third binary data c representing a computational result and having guard bits and to remove those guard bits, thereby forming final binary data c′ representing the computational result, but without guard bits.

Theapparatus1700 also lacks certain features present in theapparatus1600 because they are not needed in theapparatus1700. In particular, theapparatus1700 lacks an input line for the quantity m into the right-shift gate1719 and into themask register1713. Such an input line is not necessary given that m is fixed. Rather, the right-shift gate1719 is initialized once with the value of m to execute the appropriate right shift. Similarly, themask register1713 and theregister1725 are initialized once with the appropriate forms of M1 and P1 depending upon whether the single-guard-bit representation or multiple-guard-bit representation is being used. Conventional electrical connections can be used for carrying out these initializations and are not shown inFIG. 17. In respects other than the operational distinctions noted above, the operation of theapparatus1700 illustrated inFIG. 17 is substantially similar to that described for theapparatus1600 illustrated inFIG. 16, and no further discussion is necessary.

In theapparatus1700 as described above, thefirst register1701 and the guard-bit insertion circuit1701′ can be viewed as means for storing first binary data. Thesecond register1703 and the guardbit insertion circuit1703′ can be viewed as means for storing second binary data. Further, theregister1709 can be viewed as means for storing third binary data. Moreover, the clock/logic device1705 and any or all of the remaining devices illustrated inFIG. 7 can be viewed as means for executing at least one operation on the first binary data and the second binary data.

Multiplication of field elements in GF(p^k) where p=2^m+1 can be carried out using the exemplary forms of GF_p_k_MUL previously described with reference toFIGS. 9-12 for p=2^m−1 for both the single-guard-bit representation and multiple-guard-bit representation. It is merely necessary to recognize that m+2 bits (not including guard bits) are allocated to store each group of data bits representing a coefficient of a field element of GF(p^k) for p=2^m+1 as opposed to m bits for the case where p=2^m−1. This difference, of course, must also be applied to the form of the DLOG and ANTILOG tables. Where the compression function (COMP) and decompression function (DECOMP) are utilized with the multiple-guard-bit representation, these functions must also take into consideration that m+2 bits, rather than m bits, are allocated to store each group of data bits representing a field coefficient.

Addition and Multiplication in GF(p^k) where p=2^m±d

In another aspect of the present invention, the above-described treatments of carrying out computations in GF(p^k) for p=2m−1 and p=2^m+1 can be extended to p of the form p=2^m±d. Here, it is assumed that is assumed that d>1 and d is odd. Moreover, the choices of m and d are such that the resulting p is an odd prime. Where a given prime can be written as both p=2^m−d and p=2^m+d for different choices of m and d, it is preferable to use the form that allows the smallest value of d. For example, p=11 can be written as both p=2³+3 (m=3, d=3) and as p=2⁴−5 (m=4, d=5). It is preferable to use the choice p=2³+3 where m=3 and d=3. Approaches for carrying out addition and multiplication in GF(p^k)—that is, approaches for implementing GF_p_k_ADD and GF_p_k_MUL—for p=2^m±d will now be described.

For the case p=2^m±d, binary data representing field elements of GF(p^k) can be stored in hardware registers according to either the single-guard-bit representation or the multiple-guard-bit representation, such as described previously, except that for p=2^m−d, m+1 bits (not including guard bits) are allocated for each group of data bits representing a coefficient of a field element, and that for p=2^m+d, m+2 bits (not including guard bits) are allocated for each group of data bits representing a coefficient of a field element. For example, in the single-guard-bit representation for p=2^m−d, first binary data (register contents a) representing a first field element α_iof GF(p^k), wherein the first binary data comprises k groups of first data bits, can be stored as follows. Here it is assumed that (m+2)k is at most the hardware word size (i.e., register size). Let α_ibe a first field element of GF(p^k) where α_i=(α_k−1,i, . . . , α_0,i) and where each α_j,ibelongs to the a Sp (which will be a certain set Sp^−dor Sp^+d, depending on the form of p, as discussed below). A group of first data bits representing α_0,iis stored in a first register in

bit positions

0,1, . . . , m. A first guard bit having a value of zero is stored in the first register in bit position m+1 (a guard-bit position). Another group of first data bits representing α_1,iis stored in the first register in bit positions m+2, . . . ,2m+2, and so on. Accordingly, there is one first guard bit in every bit position v(m+2)−1 where v=1, 2, . . . —that is, every successive (m+1)-th bit position. In other words, there is one first guard bit positioned adjacent to the most significant bit of each group of first data bits. Second binary data (register contents b) comprising k groups of second data bits representing a second field element of GF(p^k) can similarly be stored in a second register with one second guard bit adjacent to the most significant bit of each group of second data bits. (The use of “first” and “second” is merely distinguish between attributes corresponding to the first field element and the second field element, respectively.) By storing binary data representing first and second field elements of GF(p^k) in first and second hardware registers in this manner, no carry bit will propagate from one group of data bits representing a field coefficient into an adjacent group of data bits representing another field coefficient. The approach for storing binary data representing field elements according to the multiple-guard-bit representation is completely analogous, the only difference being that more than one guard-bit position is provided between adjacent groups of data bits representing field coefficients.

Addition in GF(p^k) (that is, implementing GF_p_k_ADD) for the case where p=2^m−d will now be described with reference toFIGS. 18 and 19. The case where p=2^m−d can be treated by extending the approach used for p=2^m−1. It is assumed that d>1 and d is odd. It may be assumed, obviously, that 1<d<2^m−1, because otherwise p would be strictly smaller than 5 (or even negative). Two exemplary approaches for carrying out addition (two exemplary forms for implementing GF_p_k_ADD) can be used according to two regimes for the value of d: 1) d≦(2^m+1)/3, and 2) (2^m+1)/3<d<2^m−1.

First, anexemplary approach1800 for implementing GF_p_k_ADD where d≦(2^m+1)/3 for the case p=2^m−d will be described with reference toFIG. 18. This description is applicable to both the single-guard-bit representation and multiple-guard-bit representation. Let the set Sp^−dbe given by {0, 1, . . . , 2^m+d−1}, and let each coefficient of a field element of GF(p^k) be an element of the set Sp^−d. Of course, each integer referred to in the set Sp^−dhas an equivalent binary string that is used to store a corresponding coefficient of a field element, such as has been described previously. The operations shown inFIG. 18 can be executed by a system such assystem100 shown inFIG. 1. Further, it is assumed that

steps

301 and303 shown inFIG. 3 have already been executed by theprocessor105 such that first binary data representing a first field element of GF(p^k) are stored in a first register (e.g., register107 shown inFIG. 1) and such that second binary data representing a second field element are stored in a second register (e.g., register109) in a manner such as described directly above. The first and second binary data can be stored according to either the single-guard-bit representation or the multiple-guard-bit representation—the approach is the same in either case. The steps illustrated inFIG. 18 then represent an exemplary implementation ofstep305 shown inFIG. 3.

It will be noted that

steps

1801,1803 and1807 are the same as

steps

401,403 and407 shown inFIG. 4 for the case p=2^m−1. Moreover, the prescriptions for determining the predetermined binary quantities M1 and M2 for the approach illustrated inFIG. 18 are the same as forFIG. 4. The exact forms of M1 and M2 will depend, of course, upon whether the single-guard-bit representation or multiple-guard-bit representation is used as has been described previously. Also, unlike in the case for p=2^m−1 where m bits were used to represent each coefficient, m+1 bits are used to represent each coefficient for p=2^m−d. The masks M1 and M2 are thus modified in view of these considerations compared to the case for p=2^m−1. However, the definitions (prescriptions) for these quantities in terms of where zero/non-zero bits are located relative to the guard/non-guard bit locations is the same for each functional form of p. Having described these differences, no further description of

steps

1801,1803 and1807 is necessary.

Step

1805 is analogous to step405 shown inFIG. 4, except that the quantity c2 instep1805 is given by c2=d*{((a+b)&M2)>>m} instead of {((a+b)&M2)>>m}. That is, the quantity c2 instep1805 has a multiplicative factor of “d” that is not present instep405 shown inFIG. 4. The multiplication * by d is multiplication that is conventionally carried out with known processors (e.g., normal integer multiplication or floating-point multiplication). Binary data representing the quantity d is stored in the right-most bit positions of register with zeros elsewhere. In other words, if d were viewed as a vector quantity with coefficients corresponding to groups of data bits associated with field elements, the vector quantity would be (0, 0, 0, . . . , d). Thus, implementing theapproach1800 illustrated inFIG. 18 provides third binary data, c, that represents the sum of first and second field elements of GF(p^k).

Of course, the sequence of carrying out the operations shown inFIG. 18 can vary from the sequence illustrated inFIG. 18, such as has been previously described. Different sequences can be used as long as the quantity c is determined in accordance with the relation.
c=((a+b)&M1)+d*(((a+b)&M2)>>m) (37)
where a, b, c, M1 and M2 are as described above. Note equation 37 reduces to Equation 13 for the case d=1.

It will now be shown that the set Sp^−dis closed under the operations shown in equation 37 (addition followed by modular reduction) where a and b each comprise k groups of data bits a_jand b_j, respectively, where j=0, . . . , k−1 and where each a_jand b_jrepresents a group of data bits corresponding to an element of the set Sp^−d={0, 1, . . . , 2^m+d−1} referred to above. Then, with regard to each individual coefficient of the first and second field elements of GF(p^k), respectively, it can be seen that a_j+b_j≦2^m+1+2d−2 (this equation is intended to reflect a comparison of the integer values represented by a_jand b_j). Note that a function defined by h(x)=(x mod 2^m)+d(x div 2^m) (corresponding to equation 43 above) is a “sawtooth” function which monotonically increases locally on each interval of form {t2^m, (t+1)2^m−1}. Furthermore, for y<2^mand z<z′ where z and z′ are positive integers, h(z2^m+y)<h(z′2^m+y). For 0≦(a_j+b_j)≦2^m+1+2d−2, then ((a_j+b_j)div 2^m)≦2 (this equation is intended to reflect a comparison of the integer values represented by a_j+b_j). Thus, to show that h(a_j+b_j)≦2^m+d−1, for all a_j+b_jin the above-noted interval, it is enough to show that h(2^m+1−1) (the highest “peak” of any “sawtooth”) and h(2^m+1+2d−2) (for the largest possible input to h) are both bounded from above by 2^m+d−1. Evaluating h at these two points gives h(2^m+1−1)=2^m+d−1 and h(2^m+1+2d−2)=4d−2≦2^m+d−1 by the restriction d≦(2^m+1)/3. Thus, Sp^−dis closed with respect to equation 36 above. That completes the discussion for the case where d≦(2^m+1)/3 and p=2^m−d with reference toFIG. 18.

Anexemplary approach1900 for implementing GF_p_k_ADD where (2^m+1)/3<d<2^m−1 for the case p=2m-d will now be described with reference toFIG. 19. This description is applicable to both the single-guard-bit representation and multiple-guard-bit representation. When d is in the range given by (2^m+1)/3<d<2^m−1, it may be difficult to find a set Sp of reasonable size that is closed under the above reduction operation. In this regard, a reasonable size can mean that the set Sp is sufficiently small that at least two coefficients of a field element of GF(p^k) can be represented in a single hardware register or that a sufficient number of coefficients of a field element of GF(p^k) can be represented in a single hardware register such that a desired degree of parallelization and computational efficiency can be achieved using the approach set forth inFIG. 18. If such a set Sp of reasonable size can be found, then the approach illustrated inFIG. 18 can also be used when d is given by (2^m+1)/3<d<2^m−1.

When a set Sp of reasonable size is not available for d given by (2^m+1)/3<d<2^m−1, the exemplary approach for GF_p_k_ADD illustrated inFIG. 19 can be used to carry out addition in GF(p^k). In this situation, simply let the set Sp be the set given by Sp={0, 1, . . . , 2^m−1} (i.e., independent of d). Addition in GF(p^k) can then be carried out in accordance with a slightly modified modular reduction algorithm as reflected inFIG. 19. In particular, it can be seen that

steps

1901,1903,1905 and1907 shown inFIG. 19 are the same as

steps

1801,1803,1805 and1807 shown inFIG. 18, respectively, except thatstep1901 is written as c=a+b for convenience, the notation “c” is utilized in

steps

1903 and1905, and a reassignment of the quantity c occurs instep1907. Moreover, the prescriptions for determining M1 and M2 shown inFIG. 19 are the same as shown inFIG. 18 (the forms of M1 and M2 will, of course, depend upon whether the single-guard-bit representation or multiple-guard-bit representation is used). Accordingly, no further discussion of

steps

1901,1903,1905 and1907 is necessary.

Theapproach1900 illustrated inFIG. 19 is modified compared to theapproach1800 illustrated inFIG. 18 with regard tostep1909.Step1909 is a decision step that determines whether any c_j(of the result c) represents an integer value that is greater than or equal to 2^m. If the answer is yes, then steps1903,1905 and1907 are repeated using the present c. In other words, theapproach1900 illustrated inFIG. 19 executes the operations given in equations 38 and 39
c=a+b (38)

- while any c_j≧2^mdo
  c=(c&M1)+d*((c&M2)>>m) (39)
  where it is understood that c_j≧2^mis shorthand for determining whether a group of data bits c_jrepresents an integer value greater than 2^m. Thus, as reflected in equations 38 and 39 above, a modular reduction is carried out until each c_j<2^m, which guarantees that each c_jof the result c is in the set Sp. Thus, the approach above, in effect, involves subtracting a number of multiples of p from each coefficient of a field element of GF(p^k), where each coefficient is an element of the set Sp. Because p<2^mand c>0, each c_jof the result c is indeed a correct representation of (a_j+b_j) mod p, up to a multiple of p. Of course, the modular reduction may now take more time, and one question is how many times the reduction represented by equation 39 above is carried out. Under the approach described above, it can be seen that the reduction is carried out at most twice. In particular, suppose that a c_jin equation 38 becomes at least c_j≧2^m(otherwise there is nothing to show). Since a_jand b_jrepresent coefficients that are elements of Sp, it is also true that c_j≦2^m+1−2. Each execution of the reduction in equation 39 subtracts a multiple of p, e.g., t·p, where t≧1. Then, because c_j−2p≦2^m+1−2−2(2^m−d)=2d−2<2^m, it is seen that at most two modular reductions are necessary.

It remains to be shown how it is determined whether any c_j≧2^min equation 39. This test can be carried out on all c_jin parallel as follows. Suppose c=(c_k−1, . . . , c₀) holds a binary result following the reduction in equation 39. The reduction in equation 39 needs to be performed again if there is a j, 0≦j≦k−1, such that c_j≧2^m. With M2 as the predetermined binary quantity (mask quantity) defined above, performing the test (c_j&M2)≠0 is true if and only if at least one of the c_jsatisfies c_j≧2^m. Note that even if some other c_i<2^m, there is no harm in performing the reduction on such a component, because the reduction will not have any effect on that component (since c_idiv 2^m=0, and no multiple of p will be subtracted there). That completes the discussion for the case where (2^m+1)/3<d<2^m−1 and p=2^m−d with reference toFIG. 19.

Now, addition in GF(p^k) (that is, implementing GF_p_k_ADD) for the case where p=2^m+d will be described with reference toFIGS. 20 and 21. The case where p=2^m+d can be treated by extending the approach used for p=2^m+1. It is now assumed that d>1 and d is odd. Two exemplary approaches for carrying out addition (two exemplary forms for implementing GF_p_k_ADD) can be used according to two regimes for the value of d: 1) d≦p/6, and 2) p/6<d<2^m−1. (Note that the case d≧2^m−1 can be treated by the previously described methods, simply by rewriting p as p=2^m′±d′ where m′ and d′ are appropriately chosen.)

First, anexemplary approach2000 for implementing GF_p_k_ADD where d≦p/6 for the case p=2^m+d will be described with reference toFIG. 20. This description is applicable to both the single-guard-bit representation and multiple-guard-bit representation. Here, the set Sp^+dis given by {0, 1, . . . , 2p−(d+1)}, and each coefficient of a field element of GF(p^k) is an element of the set Sp^+d, requiring m+2 bits of storage for each such coefficient, not including the guard bit(s). The operations shown inFIG. 18 can be executed by a system such assystem100 shown inFIG. 1. Further, it is assumed that

steps

301 and303 shown inFIG. 3 have already been executed by theprocessor105 such that first binary data representing a first field element of GF(p^k) are stored in a first register (e.g., register107 shown inFIG. 1) and such that second binary data representing a second field element are stored in a second register (e.g., register109) in a manner such as described directly above. The first and second binary data can be stored according to either the single-guard-bit representation or the multiple-guard-bit representation—the approach is the same in either case. The steps illustrated inFIG. 20 then represent an exemplary implementation ofstep305 shown inFIG. 3.

It will be noted that

steps

2001,2003,2005 and2009 are the same as

steps

1401,1403,1405 and1409 shown inFIG. 14 for the case p=2^m+1. Moreover, the prescriptions for determining the predetermined binary quantities M1 and M2 are the same forFIG. 20 as forFIG. 14 (the exact forms of M1 and M2 will depend, of course, upon whether the single-guard-bit representation or multiple-guard-bit representation is used as has been described previously). As noted, here, m+2 bits are allocated to store each coefficient of field elements, not including the guard bit(s). Accordingly, no further description of these steps is necessary.Step2007 is analogous to step1407 shown inFIG. 14, except that the quantity c2 instep2007 is given by c2=P1−d*{((a+b)&M2)>>m} instead of P1−{((a+b)&M2)>>m}, where * is multiplication as discussed above (e.g., normal integer multiplication or floating-point multiplication). That is, the quantity c2 instep2007 has a multiplicative factor of “d” that is not present instep1407 shown inFIG. 14. In addition P1 instep2007 ofFIG. 20 comprises binary values representing thequantity 2^m+d rather than 2^m+1, as instep1407 ofFIG. 14. Thus, implementing theapproach2000 illustrated inFIG. 20 provides third binary data, c, that represents the sum of first and second field elements of GF(p^k).

Of course, the sequence of carrying out the operations shown inFIG. 20 can vary from the sequence illustrated inFIG. 18, such as has been previously described. Different approaches can be taken as long as the quantity c is determined as shown in equation 40 below, where a, b, c, M1, M2 and P1 are as described previously with reference toFIG. 14.
c=((a+b)&M1)+P1−d*(((a+b)&M2)>>m) (40)
Note that this reduces to equation 36 for the case d=1. That completes the discussion for the case where d≦p/6 and p=2^m+d with reference toFIG. 20. It can also be verified by one of ordinary skill in the art that the set Sp^+dis indeed closed with respect to the above reduction using methods in analogy to the case p=2^m−d, d>1, as discussed above.

Anexemplary approach2100 for implementing GF_p_k_ADD where p/6<d<2^m−1 for the case p=2^m+d will now be described with reference toFIG. 21. This description is applicable to both the single-guard-bit representation and multiple-guard-bit representation. As noted previously for the case where p=2^m−d, when d is in the range given by p/6<d<2^m−1, it may be difficult to find a set Sp of reasonable size that is closed under the above reduction operation. However, if a set Sp of reasonable size can be found, then the approach illustrated inFIG. 20 can also be used when d is given by p/6<d<2^m−1.

When a set Sp of reasonable size is not available for d given by p/6<d<2^m−1, the exemplary approach for GF_p_k_ADD illustrated inFIG. 21 can be used to carry out addition in GF(p^k), by repeatedly performing reductions, in analogy to what was done in equation 39 for the case p=2^m−d. However, it is now not clear that a coefficient that is already smaller than 2^mactually cannot get larger by this reduction. In fact, this is indeed the case. Considering the reduction function h′(z)=(z mod 2^m)+p−d(z div 2^m), notice that h′(0)=p>0. Moreover, in the interval {p, p+1, . . . , 2^m+1−1}, the function h′ has fixed-points; h′(z)=z, for all z in that interval. The approach of repeated reductions therefore needs slight modification. In this situation, the set Sp will instead be given by Sp={0, 1, . . . , 2^m+1−1} (i.e., independent of d). Note that now, m+1 bits are needed for storage of each coefficient, not including the guard bit(s). Addition in GF(p^k) can then be carried out in accordance with a slightly modified modular reduction algorithm as reflected inFIG. 21. In particular, it can be seen that

steps

2101,2103,2105,2107 and2109 shown inFIG. 21 are the same as

steps

2001,2003,2005,2007 and2009 shown inFIG. 20, respectively, except thatstep2101 is written using c=a+b, the notation “c” is utilized in steps2103-2107, and a reassignment of the quantity c occurs instep2109. Moreover, the prescriptions for determining the quantities M1, M2 and P1 shown inFIG. 21 are the same as inFIG. 20 (the exact forms of M1, M2 and P1 will, of course, depend upon whether the single-guard-bit representation or multiple-guard-bit representation is used). Accordingly, no further discussion of

steps

2101,2103,2105,2107 and2109 is necessary.

However, theapproach2100 illustrated inFIG. 21 is modified compared to theapproach2000 illustrated inFIG. 20 with regard tostep2111.Step2111 is a decision step that determines whether any c_j(of the result c) represents an integer value that is greater than 2^m+1, similar to what was described with reference toFIG. 19. If the answer is yes, then steps2103,2105,2107 and2109 are repeated. In other words, theapproach2100 illustrated inFIG. 21 executes the operations given in equations 41 and 42
c=a+b (41)

- while any c_j≧2^m+1do
  c=(c&M1)+P1−d*((c&M2)>>m) (42)
  where it is understood that c_j≧2^m+1is shorthand for determining whether a group of data bits c, represents an integer value greater than 2^m+1. The implementation of the loop represented by equation 42 is similar to that described with reference to equation 39 andFIG. 19. A difference is that in the previous case the test could be implemented by checking if (c & M2) was zero or not. In the present case, the test can be carried out by checking whether (c & M7) is zero or not, where M7 is a new binary quantity that is the same as M2, except that bit m, and in general, the least significant non-zero bit of any given segment of M2, is reset to zero. (For example, whereas the quantity M2 illustrated in the example ofFIG. 15 is given by repeated occurrences of (1, 1, 0, 0) as indicated byreference numeral1511, the quantity M7 as described above would be given by repeated occurrences of (1, 0, 0, 0) for the test for the present case, with guard bits in appropriate positions.) It can be easily seen by those of ordinary skill in the art that by using the above-noted choice of Sp and the test condition in equation 42, the reduction will eventually terminate, with all components of c being smaller than 2^m+1. That completes the discussion for the case where p/6<d<2^m−1 and p=2^m+d with reference toFIG. 21.

In the discussions above relating toFIGS. 18-21, it was noted that the approaches illustrated therein are applicable to both the single-guard-bit representation and multiple-guard-bit representation. When the multiple-guard-bit representation is used, it is merely necessary to note that the first and second binary data representing the first and second field elements, respectively, are stored with multiple guard bits placed between adjacent groups of data bits representing coefficients of the respective field elements, rather than single guard bits as is the case for the single-guard-bit representation. Moreover, the prescriptions for determining the quantities M1, M2 and P1 require no modification for the multiple-guard-bit representation. Of course, applying those prescriptions to the multiple-guard-bit representation will generate different values of the quantities M1, M2 and P1 than will be generated for the single-guard-bit representation. Moreover, given that separate descriptions for addition in GF(p^k) have been provided for the cases where p can be written in the form p=2^m−1 and p=2^m+1, it will be recognized the approaches described above for the cases where p=2^m−d and p=2^m+d are applicable primarily where d is an odd integer greater than or equal to 3 and less than 2^m−1, m is an integer greater than or equal to 3, and p≠2^N±1 for any integer N.

Multiplication of field elements in GF(p^k) where p=2^m−d and p=2^m+d can be carried out using the exemplary forms of GF_p_k_MUL previously described with reference toFIGS. 9-12 for p=2^m−1 for both the single-guard-bit representation and multiple-guard-bit representation. It is merely necessary to recognize that m+1 bits (not including guard bits) are allocated to store each group of data bits representing a coefficient of a field element of GF(p^k) for p=2^m−d as opposed to m bits for the case where p=2^m−1. This difference, of course, must also be applied to the form of the DLOG and ANTILOG tables. Where the compression function (COMP) and decompression function (DECOMP) are utilized with the multiple-guard-bit representation, these functions must also take into consideration that m+1 bits, rather than m bits, are allocated to store each group of data bits representing a field coefficient.

It was noted above for the case p=2^m−1 that a variety of other operations can be carried out according to the present invention including scalar multiplication (equation 23), doubling (equations 28-29), determining the additive inverse (equation 30), determining the multiplicative inverse (equation 31), and exponentiation (equation 32). In view of the discussion above, it will be apparent to those of ordinary skill in the art that these operations can also be carried out for the cases where p=2^m+1, p=2^m−d and p=2^m+d using the approaches described above. Moreover, it will also be apparent that hardware apparatuses, such as described with reference toFIGS. 6-8,12,16 and17, can be utilized for the cases where p=2^m−d and p=2^m+d. Themultiplication apparatus1200 illustrated inFIG. 12, in fact, requires no modification for use where p=2^m−d and p=2^m+d.

To modify the hardware apparatus ofFIG. 6 to be adapted to the case p=2^m−d (d>1), a multiplier circuit, performing multiplication (conventional multiplication) by the given quantity d, is inserted between the output connection of the right-shift gate619 and the input connection ofregister603, i.e., at the location indicated by “**” inFIG. 6. ForFIG. 7, the same type of multiplier circuit can be inserted between the output connection of right-shift gate719 and the input connection ofregister703, i.e., at the location indicated by “**” inFIG. 7. In complete analogy, the apparatuses illustrated inFIGS. 16 and 17 can be modified with the same kind of multiplier circuit at the locations indicated by “**” in those figures, respectively, to modify them for the general case p=2^m+d, d>1.

Parallel Addition with Non-Prime Moduli

As should be clear to those of ordinary skill in the art, in none of the cases for describing k parallel additions modulo p=2^m±d, d≧1, did we actually make use of the fact that p was a prime number. While using prime p is important for multiplication in finite fields (otherwise, the group is not cyclic and no generator/log-tables can be found), addition operations are well defined and completely analogous even if p is not prime. Thus, in another aspect of the present invention, the exemplary approaches described above for GF_p_k_ADD can be used to perform k parallel additions modulo p for any p (prime or not) that is close to a power of 2, i.e. p=2^m±d. In complete analogy, the above-described approaches can be used for different functional forms of p depending on the sign in front of d, and the magnitude of d.

Other Aspects, Including Cryptography and Error Correction

In another aspect of the present invention, the approaches described above can be used in an error correction apparatus and in a method of error correction. The purpose of an error correcting code is to enable a receiver to reconstruct an original message even if the message disturbed by errors in transit, i.e. to correct the errors in the received message. This is done by introducing redundancy to the message. As known to those of ordinary skill in the art, a number of check equations are utilized in error-correcting codes. Upon reception of a message, the receiver can determine if an error occurred by checking the received data in accordance with these equations, and if so, can also determine the error. Depending upon these equations, which define the error-correcting code, multiple errors can sometimes be corrected.

In many cases the codes/equations are constructed using finite field arithmetic. The code will then consist of N-tuples (or “vectors”) of the form g=(g₀, g₁, . . . , g_N−1) where each g_iis an element in GF(q) for some q. Note that only a relatively small set of all such possible g can be valid code words; if all g were allowed, it would be impossible to tell whether an error occurred or not.

Conventionally, each message is mapped into such an N-tuple and transmitted. If a limited number of the g_iare corrupted, the receiver can still retrieve g to obtain the original message. Examples of such codes include Reed-Solomon codes, BCH codes, and Goppa codes known to those of ordinary skill in the art, such as described inThe Theory of Error Correcting Codesby F. J. MacWilliams and N. J. A. Sloane, Elsevier Science B.V., Amsterdam, 1977. As noted above, these codes can utilize arithmetic operations over finite fields. However, conventional implementations of such codes either utilize binary finite fields or utilize odd-characteristic finite fields in the conventional inefficient manner in which a single coefficient of GF(p^k) is operated upon in a hardware register. In contrast, the present invention provides an approach for carrying out error correction involving odd-characteristic finite fields in which data representing coefficients of a finite field are processed in a parallel and highly efficient manner by storing binary data representing multiple coefficients of an odd characteristic finite field in a single hardware register and by processing the binary data representing the multiple coefficients in parallel.

A conventional approach for decoding a BCH code, such as discussed inThe Theory of Error Correcting Codesreferred to previously, can be described as follows. The field F=GF(q) is the field of q=pⁿelements, and we let w denote the multiplicative order of q modulo N (i.e., w is the smallest y such that q^y=1 mod N). Let an element α in GF(q^N) be a primitive N-th root of unity, i.e., N is the smallest integer for which α^N=1 in that field. Important special cases occur when N=q^w−1, which corresponds to a primitive BCH code, and when N=q−1, which corresponds to a Reed-Solomon code. The corresponding BCH code will consist of all N-dimensional vectors g=(g₀, g₁, . . . , g_N−1) with components in GF(q) that satisfy the matrix-vector equation Hg^T=0, where H is a (D−1)-by-N matrix given by

\begin{matrix} H = [\begin{matrix} 1 & α & α & ^{2} & \dots & α^{(N - 1)} \\ 1 & α^{2} & α^{4} & \dots & α^{2 (N - 1)} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 1 & α^{d - 1} & α^{2 (D - 1)} & \dots & α^{(D - 1) (N - 1)} \end{matrix}] & (43) \end{matrix}

where T denotes transpose and where D can assume any value between 1 and N−1. This description pertains to a narrow sense BCH code, which is not the most general form.

In an aspect of the present invention, an exemplary error-correctingapparatus2200 is provided, such as illustrated in the block diagram ofFIG. 22. Theapparatus2200 comprises an input device2201 (which can also be an input/output device, for example) that receives a signal intended to represent an allowed code word of an error correcting code and aprocessing unit2203 programmed for error correction. Theapparatus2200 can also comprise a memory that can be accessed by the processing unit2203 (e.g., to retrieve a computer program that can cause the processing unit to execute steps of the approaches described herein) and that can store binary data provided by the processor (e.g., calculation results). The signal can be binary data or it can be an analog signal that is converted (e.g., mapped with a mapping device) to binary data in the input/output unit2201. The phrase “binary data intended to represent an allowed code word” as used herein is intended to encompass both of these possibilities.

Theprocessing unit2203 can be any suitable processing unit, including conventional or specialized processors, for carrying out the approaches described herein, and the input/output unit22 can be any suitable interface or device for inputting/outputting data. For example, theprocessing unit2203 can be the processing unit of a conventional computer, and the input/output device2201 can be a conventional modem. As another example, theprocessing unit2203 can be that of a hand-held device, such as a mobile telephone or personal digital assistant, and the input/output device2201 can be a wireless receiver/transmitter. As another example, theprocessing unit2203 can be that of a compact disk (CD) player or digital video disk (DVD) player, and the input/output device can be an optical signal receiver that receives a signal from a laser beam modulated by the CD or DVD and outputs a corresponding electrical signal.

The processing unit is programmed to correct errors in the binary data where allowed code words are N-tuples of field elements of GF(p^lk). The finite field GF(p^lk) is an extension field of a base field GF(p^k) where p is an odd prime number and where field elements of GF(p^k) comprise k base coefficients. A portion of the binary data comprises k groups of data bits and represents a field element of GF(p^k) wherein the field GF(p^k) has k base coefficients in accordance with a polynomial basis representation, each group of data bits representing a corresponding one of the k base coefficients. The portion of the binary data is stored in a register, and the processing unit processing processes the portion of the binary data such that the k groups of data bits are processed in parallel using, for example, arithmetic operations previously described above. This will be described in greater detail below.

In particular, the error-correctingapparatus2200 can be programmed for error correction according to the present invention using anexemplary approach2300 illustrated inFIG. 23. For example, theapproach2300 can be implemented for decoding a BCH code in which the inventive computational approaches described previously are applied to the matrix formulation for error correction described above with reference to equation 50. Theapproach2300 can correct d/2 errors (and sometimes more errors) in received binary data g′=(g′₀, g′₁, . . . , g′_N−1) intended to represent an allowed code word.

First, as indicated atstep2301 inFIG. 23, the error-correcting apparatus receives binary data intended to represent an allowed code word of an error correcting code wherein the allowed code word is an N-tuple of field elements of GF(p^lk) where p is an odd prime number. In other words, each allowed code word comprises N field elements of GF(p^lk). The binary data can be received directly or can be converted from an analog signal as noted above. In addition, each field element of GF(p^lk) can be viewed as comprising l primary coefficients in accordance with a polynomial basis representation, wherein each primary coefficient is a field element of GF(p^k) having k base coefficients. The binary data intended to represent an allowed code word can be viewed as comprising N collections of data bits, wherein each collection of data bits comprises l segments of data bits, each segment of data bits representing a corresponding one of the l primary coefficients. Further, each segment of data bits can be viewed as comprising k groups of data bits, wherein each group of data bits represents a corresponding one of the k base coefficients.

As indicated atstep2303, the error-correctingapparatus2200 then calculates a syndrome based upon the received binary data, wherein a given portion of the binary data (e.g., a given segment of data bits corresponding to one of the l primary coefficients) is stored in a register, and wherein k groups of data bits of the given portion of the binary data are processed in parallel. In particular, for the example of the matrix formulation described above with reference to equation 43 (pertaining to a BCH code), a syndrome can be calculated as follows. Transmitted binary data g=(g₀, g₁, . . . , g_N−1) (or a transmitted signal corresponding to such binary data) is received as binary data g′=(g′₀, g′₁, . . . , g′_N−1). Let the error locations in the binary data g′ be those indices j for which g′_j≠g_j, and let the error values be the (non-zero) values e_jin GF(p^lk) satisfying g′_j=g_j+e_j. Finally, for convenience define η_j=α^jwhere α^jis α to the power of j (computed in the field). Then, in conjunction with the matrix equation 43 referred to above, the syndrome S can be calculated in accordance with the relation
S=Hg′^T (44)
giving S=(S₁, S₂, . . . , S_d−1). It should be noted that the components g′_jin g′ are elements in GF(p^lk), and the syndrome entries S_iare elements of GF(p^Nlk), where GF(p^Nlk) is an extension field of GF(p^lk). In calculating the syndrome S in accordance with equation 44, arithmetic operations must be carried out in the field GF(p^k). As noted above, each of the l segments of data bits comprises k groups of data bits, each group of data bits represents a corresponding one of the k base coefficients. As reflected atstep2303, the syndrome is calculated such that k groups of data bits stored in a register are processed in parallel using, for example, exemplary implementations of GF_p_k_ADD and GF_p_k_MUL, as well as any other needed operations, described previously.

Next, as indicated atstep2305, it is determined whether the syndrome S is equal to zero, i.e., whether S=0=(0, 0, . . . , 0). If S=0, then no error occurred, and the procedure skips to step2309 where it is determined whether more data should be processed. If S≠0, the procedure proceeds to step2307 where the errors are detected.

As indicated atstep2307, the error-correcting apparatus detects errors in an error-containing portion of the binary data (e.g., an error-containing segment of data bits) based upon the syndrome, and corrects the errors in the error-containing portion of the binary data by processing k groups of data bits of the error-containing portion of the binary data in parallel. This process is repeated for all error-containing portions of the binary data. For example, with regard to the matrix formulation of equation 44 pertaining to a BCH code, assuming r errors occurred, equation 45 below must be satisfied for each j, where 0≦j≦d−1
S_j=e₁η_i1^j+ . . . +e_rη_ir^j (45)
for some e_i(the error values) in GF(p^lk) and some η_ikbelonging to the set {η₀, . . . , η_n−1} (the error locations).

Moreover, in determining the error values in accordance with this example, the maximum number r must be determined, such that the system of equations
S_j+r+S_j+r−1τ₁+ . . . +S_jτ_r=0 (46)
(where 1≦j≦r−1) has a unique solution for values of τ_i, and those τ_imust be determined (here r is the number of corrupt indices in g′). This can be accomplished, for example, using the Berlekamp-Massey algorithm known to those of ordinary skill in the art and described, for example, inThe Theory Of Error Correcting Codesreferred to previously. Then a degree r error-locator polynomial can be established, which has the form as set forth in equation 47 below
s(x)=(1−η_i1x)(1−η_i2x) . . . (1−η_irx)=τ_rx^r+τ_r−1x^r−1+ . . . +τ₀ (47)
where τ₀=1 for determining error locations. By equation 47, a given j (0≦j≦N−1) is an error location if and only if s(η_j⁻¹)=0, which can be determined by evaluating each s(x), in turn, by Horner's evaluation rule for polynomials, which is known to those of ordinary skill in the art and is described, for example, inSeminumerical Algorithms, Vol. 2 ofThe Art of Computer Programming, referred to above. Each such computation involves on the order of r additions and multiplications in GF(p^lk), which can be carried out using exemplary approaches for SUM(α, β, PRODUCT(α, β), GF_p_k_ADD and GF_p_k_MUL according to the present invention, which have been described above.

Then, the error values e_iare found by introducing the η_jvalues found as described above into the equations defined by equation 45 and solving them. For locations j where no error has occurred, the value e_jis defined as e_j=0. Next, the errors are corrected in accordance with the relation g=g′−e, where e=(e₀, e₁, . . . , e_N−1). That is, for each j between 0 and N−1, the quantity g_jis determined in accordance with g_j=g′_j−e_j. This latter step is accomplished by carrying out N subtractions in GF(p^lk). At this point,step2307 is completed for the exemplary treatment of error correction involving a BCH code.

As indicated atstep2309 shown inFIG. 23, it is determined whether more data should be processed—that is, whether more binary data intended to represent an allowed code word has been received and should be processed. If more data should be processed, the procedure returns to step2301. If no further data should be processed, the procedure ends.

In another aspect of the invention, the inventive arithmetic approaches described above, including but not limited to the exemplary approaches for GF_p_k_ADD, GF_p_k_MUL and exponentiation, can be used in cryptography, for example, in cryptography utilizing elliptic curves and in key exchange. Cryptography utilizing elliptic curves is well known to those of ordinary skill in the art. For example, an approach for encrypting plaintext onto elliptic curves is described, for example, in U.S. Pat. No. 6,307,935 (Method and apparatus for fast elliptic encryption with direct embedding), the entire contents of which are incorporated herein by reference. In addition, a key agreement and transport protocol that can use elliptic curves is described in U.S. Pat. No. 6,122,736 (Key agreement and transport protocol with implicit signatures), the entire contents of which are incorporated herein by reference. Further, a public key protocol that can utilize elliptic curves is described in U.S. Pat. No. 5,933,504 (Strengthened public key protocol), the entire contents of which are incorporated herein by reference. Moreover, an approach for implementing key exchange involving elliptic curves is described in U.S. Pat. No. 5,159,632 (Method and apparatus for public key exchange in a cryptographic system), the entire contents of which are incorporated herein by reference. It should be noted, however, that U.S. Pat. Nos. 6,307,935, 6,122,736, 5,933,504 and 5,159,632 do not disclose storing binary data representing multiple field-element coefficients in a single register and processing such binary data in parallel as taught herein.

Some aspects of elliptic curves will now be described. For a finite field F and two elements α and β in F, an elliptic curve over F can be considered (informally) the set of points (x, y) in F×F that satisfies the equation
y²=x³+αx+β. (48)
In addition, there is a point at infinity, O, which is conceptually thought of as lying “infinitely” high up on the y-axis. These points together form an abelian group under a group “addition” operation, denoted as {circle around (x)}. This group addition operation is defined in terms of arithmetic operations in the underlying field, F, as is known to those of ordinary skill in the art. Thus, according to the present invention, the underlying field can be chosen to be an odd-characteristic finite field GF(p^k) (or an extension thereof), and the exemplary arithmetic approaches described above, including but not limited to GF_p_k_ADD and GF_p_k_MUL and exponentiation, can be used to enhance computational efficiency in cryptographic computations carried out for an elliptic-curve group over the odd-characteristic finite field GF(p^k).

For example, if g is a point on such an elliptic curve, g may be combined with itself, x times, under the {circle around (x)} operation to provide
z=g{circle around (x)}g{circle around (x)} . . . {circle around (x)}g. (49)
The operations in equation 49 may be thought of as a kind of exponentiation wherein z=g^x. In the remainder of the description, we generically use g^xto denote the composition of the group operation with itself, x times acting on g. From the context it will always be clear if this operation is finite field multiplication, or, elliptic curve point addition. In the elliptic curve case, this thus gives rise to a special case of the discrete logarithm problem referred to previously. Current state of the art suggests that the elliptic curve version of the discrete logarithm can be harder to solve than in other settings, making it especially attractive for cryptography.

According to an aspect of the present invention, there is provided a cryptographic apparatus comprising a key source and an odd-characteristic finite-field cryptographic unit coupled to the key source for use in a cryptographic system, such as the exemplary cryptographic system illustrated inFIG. 24A. The cryptographic apparatus is configured to implement cryptographic computations involving the field GF(p^k) (p being an odd prime) and can utilize the single-guard-bit representation or the multiple-guard-bit representation. An exemplary cryptographic system according to the present invention will now be described with reference toFIG. 24A.

FIG. 24A is a functional block diagram illustrating acryptographic system2400 comprising a firstcryptographic apparatus2401, a secondcryptographic apparatus2403, afirst transceiver2405 for transmitting and receiving ciphertext over aninsecure channel2417, and asecond transceiver2407 for transmitting and receiving ciphertext over theinsecure channel2417. Aneavesdropper2419 is assumed to be able to observe the communications over theinsecure channel2417. The firstcryptographic apparatus2401 comprises a firstkey source2409 and a first odd-characteristic finite-field cryptographic unit2411 (also referred to herein as the first FFCU) for encrypting and decrypting messages. Either or both the firstkey source2409 and thefirst FFCU2411 can be implemented, for example, using one or more processing units of a conventional computer or of a hand-held device such as a mobile phone. In addition, the firstcryptographic apparatus2401 can also comprise a memory that can be accessed by the FFCU2411 (e.g., to retrieve a computer program that can cause theFFCU2411 to execute steps of cryptographic approaches described herein) and that can store binary data provided by the FFCU2411 (e.g., calculation results).

The secondcryptographic apparatus2403 comprises a secondkey source2413 and a second odd-characteristic finite-field cryptographic unit2415 (also referred to herein as the second FFCU2415) for encrypting and decrypting messages. (Here, “first” and “second” are used merely to distinguish aspects of the firstcryptographic apparatus2401 and the secondcryptographic apparatus2403.) Either or both the secondkey source2413 and thesecond FFCU2415 can be implemented, for example, using one or more processing units of a conventional computer or of a hand-held device such as a mobile phone. In addition, the secondcryptographic apparatus2403 can also comprise a memory that can be accessed by the FFCU2415 (e.g., to retrieve a computer program that can cause theFFCU2415 to execute steps of cryptographic approaches described herein) and that can store binary data provided by the FFCU2415 (e.g., calculation results). In addition, the first and second

key sources

2409 and2413 can include random number generators.

As noted above, the firstcryptographic apparatus2401 comprises a firstkey source2409 and a first odd-characteristic finite-field cryptographic unit (FFCU)2411 coupled to the key source. In one aspect of the present invention, the FFCU2411 (or FFCU2415) can be configured to execute steps of anexemplary cryptographic method2450 illustrated in the flow diagram ofFIG. 24B. Themethod2450 comprises storing binary data representing at least a portion of a field element of an odd-characteristic finite field GF(p^k) in a register (e.g., an internal register of a processing unit used to implement the FFCU2411), p being an odd prime number (step2451). The field element comprises k coefficients in accordance with a polynomial-basis representation, and the binary data comprises plural groups of data bits, wherein each group of data bits represents an associated one of the k coefficients. The method also comprises processing the binary data in accordance with a cryptographic algorithm such that the plural groups of data bits are processed in parallel (step2453).

Additional details relating to an exemplary operation of thecryptographic system2400 illustrated inFIG. 24A and relating to theexemplary cryptographic method2450 illustrated inFIG. 24B will now be described. The description will address the case where a message is sent from the firstcryptographic apparatus2401 and is received by the secondcryptographic apparatus2403, but the description is equally applicable to the situation where the message originates at the secondcryptographic apparatus2403 and is received by the firstcryptographic apparatus2401.

A first converser and a second converser each have secure keys. In one aspect, a secure key can be generated by key exchange according to the present invention. In this regard, the binary data referred to above can be key data, and the cryptographic algorithm referred to above can be a key exchange algorithm such as described below with reference toFIG. 25. A secure key can be thereby exchanged via theinsecure channel2417. Alternatively, in another exemplary aspect, each of the conversers can have a public key/private key pair, wherein the public keys of each converser are made available to the other converser over a public channel. In this regard the binary data referred to above can be message data, and the cryptographic algorithm referred to above can be a public-key encryption algorithm used to encrypt/decrypt the message data, such as described below with reference toFIG. 26.

As illustrated inFIG. 24A, a secure key generated by key exchange, or a public key, can be provided from thekey source2409 to thefirst FFCU2411 of thefirst encryption apparatus2401. Plaintext P is provided to thefirst FFCU2411, and the plaintext is encrypted by thefirst FFCU2411 using a suitable encryption algorithm, thereby generating ciphertext C. The encryption algorithm is agreed upon by the first and second conversers in advance, and the key fromkey source2409 is appropriately configured for the encryption algorithm. If key exchange according to the present invention is used to generate a secure key, the encryption algorithm used for encrypting the plaintext can be any suitable encryption algorithm, such as DES or RSA, for example. If public/private key pairs are used, the encryption algorithm used for encrypting the plaintext can be public-key encryption such as described below with reference toFIGS. 26, 27 and28 or any suitable encryption algorithm that can be implemented in accordance with themethod2450 illustrated inFIG. 24B.

The ciphertext C is then provided to the transceiver2405 (e.g., a network interface, modem or wireless transmitter/receiver) which transmits the ciphertext C over theinsecure channel2417 totransceiver2407. It is assumed that the transmission can be observed by aneavesdropper2419.

The ciphertext is then provided to thesecond FFCU2415 of the secondcryptographic apparatus2403. Thesecond FFCU2415 decrypts the ciphertext according to a decryption algorithm that corresponds to the encryption algorithm agreed upon by the first and second conversers. The decryption algorithm utilizes a key from thekey source2413 in conjunction with the decryption. The key can be, for example, a key generated using key exchange, or a private key corresponding to a public key used for encryption. Additional exemplary aspects according to the present invention relating toFIGS. 24A and 24B will now be discussed.

In one aspect of the present invention, the binary data stored in the register can represent all k coefficients the field element. In addition, the plural groups of data bits can be stored in the register such that at least one guard bit is positioned adjacent to the most significant bit of each group of data bits, each group of data bits being separated from an adjacent group of data bits by a corresponding at least one guard bit. One guard bit (single-guard-bit representation) or multiple guard bits (multiple-guard-bit representation) can positioned adjacent to the most significant bit of each group of data bits. An initial value of zero can assigned to each at least one guard bit.

In one aspect of the present invention, the cryptographic apparatus2401 (and/or2403) can implement key exchange, as one example of thecryptographic method2450, using computations involving the odd-characteristic finite field GF(p^k). Such key exchange can be carried out using the single-guard-bit representation or the multiple-guard-bit representation. Anexemplary method2500 of key exchange according to the present invention, e.g., implemented using thecryptographic system2400, will now be described with reference toFIGS. 24A and 25.

A first converser having a firstcryptographic apparatus2401 and a second converser having a secondcryptographic apparatus2403 want to communicate securely over theinsecure channel2417 such than an eavesdropper cannot decrypt their transmissions. Thus, the first and second conversers must first agree on a key to use for encryption, data authentication, etc. Such a key can be generated using Diffie-Hellman key exchange adapted for finite-field computations over GF(p^k) according to the present invention. Conventional Diffie-Hellman key exchange is described in U.S. Pat. No. 4,200,770 (Cryptographic apparatus and method), the entire contents of which are incorporated herein by reference. Moreover, as noted above, conventional key exchange over elliptic curves is described in U.S. Pat. No. 5,159,632 previously incorporated herein.

The first and second conversers agree on a quantity g, wherein g is an element of a finite field F or a point on an elliptic curve over F, F being an odd-characteristic finite field GF(p^k) or an extension field of GF(p^k), p being an odd prime number. In practice, g will generate a group over which calculations are carried out, the group having an exponentiation operation. If g is chosen, for example, as a point on an elliptic curve over F, the group can be viewed as an elliptic curve group defined over the F. If g is chosen as an element of F, the group can be viewed as a conventional multiplicative group over the finite field F. In either case, the quantity g should be chosen such that a smallest integer x, where g^x=1, is sufficiently large to provide for sufficient security (“1” is the identity element in the group). For example, the binary representation of this integer x should be at least 160 bits in size in view of the computational power of present generation processors. This smallest integer x can be denoted by |G| (the size of the group). Sufficient security in this regard means that the exponentiation is secure in the sense that the discrete logarithm problem is intractable (i.e., computationally infeasible).

To generate a key, a number xA is generated (step2501) by thekey source2409 of thefirst cryptographic unit2401 associated with the first converser and is provided to thefirst FFCU2411. The number xA can be, for example, an integer generated randomly or pseudorandomly, as these terms are conventionally understood in the art. The number xA is not intended to be shared with other conversers, and, in this regard, can be considered a secret number. It will be understood that an integer in this context is intended to include both an integer stored as an integer as well as an integer stored as a floating-point decimal. Thefirst FFCU2411 generates and sends yA, wherein yA=g^xA(step2503) to thesecond cryptographic unit2403 associated with the second converser over theinsecure channel2417. As noted above, g is an element of a finite field F or a point on an elliptic curve over F, F being an odd-characteristic finite field GF(p^k) or an extension field of GF(p^k), p being an odd prime. The quantity g comprises plural first base coefficients, wherein the first base coefficients are elements of GF(p). For example, if g is chosen as an element of GF(p^k), then g would comprise k first base coefficients that are elements of GF(p). If g is chosen as an element of an extension field GF(p^lk), then g would comprise l·k first base coefficients that are elements of GF(p). If g is chosen as a point on an elliptic curve over GF(p^k), then g would comprise 2·k first base coefficients that are elements of GF(p), because g would then be represented by a pair of quantities, both of which are elements of GF(p^k). Similarly, if g is chosen as a point on an elliptic curve over GF(p^lk), then g would comprise 2·l·k base coefficients that are elements of GF(p).

Thefirst FFCU2411 carries out the computation of yA by storing multiple groups of first data bits representing at least some of the plural first base coefficients of g in a first register and by processing the multiple groups of first data bits in parallel to generate yA (step2503). The multiple groups of first data bits can be stored in the first register such that at least one first guard bit is positioned adjacent to the most significant bit of each group of first data bits, each group of first data bits being separated from an adjacent group of first data bits by a corresponding at least one first guard bit. One first guard bit can be positioned adjacent to the most significant bit of each group of first data bits (i.e., the single-guard-bit representation), or multiple first guard bits can be positioned adjacent to the most significant bit of each group of first data bits (i.e., the multiple-guard-bit representation). An initial value of zero can be assigned to each first guard bit. The computation of yA can be carried out using the exponentiation function referred to in equation 32 such that the multiple groups of first data bits are processed in parallel in the manner previously described. Even though equation 32 was described with regard to p of the form p=2^m−1, equation 32 is also applicable for p of the form p=2^m+1 and p=2^m±d, as noted previously. Depending upon the register size of the hardware and the number of first base coefficients that g comprises, it may be possible to store multiple groups of first data bits representing all base coefficients of g in a single register.

Thefirst FFCU2411 receives the quantity yB, wherein yB comprises plural second base coefficients, the second base coefficients being elements of GF(p) (step2505). TheFFCU2411 stores multiple groups of second data bits representing at least some of the plural second base coefficients of yB in a second register, and then calculates K=(yB)^xAby processing the plural groups of second data bits in parallel (step2507). Thesecond FFCU2415 computes the same value K in accordance with K=(yA)^xB. These computations can also be carried out using exponentiation operation referred to in equation 32 wherein multiple groups of data bits representing associated base coefficients (elements of GF(p)) of yB and yA are respectively processed in parallel. Under the above assumptions, only the first and second conversers can compute K, and the first and second conversers may use K (or a function thereof) as a key. By implementing the above-described adaptation of Diffie-Hellman key exchange over an elliptic curve or other group defined over GF(p^k) using the single-guard-bit representation or multiple-guard-bit representation, the present invention offers increased computational efficiency compared to conventional approaches, which can either be manifested as increased speed compared to conventional approaches or increased security for the same computational effort.

Having generated a secure key K in accordance with the key exchange algorithm described above, the first and second conversers can utilize that key in conjunction with their first and

second FFCUs

2411 and2415, respectively, to encrypt and decrypt exchanged messages. The encryption/decryption algorithm in this regard can be, for example, conventional cryptographic methods such as RSA or DES known to those of ordinary skill in the art, or any other suitable encryption algorithm.

The firstcryptographic apparatus2401 and the secondcryptographic apparatus2403 have each been described as comprising a finite-field cryptographic unit and a key source. It should be understood that the first finite-field cryptographic unit2411 and the firstkey source2409 of the firstcryptographic apparatus2401 can be implemented using a memory and a processing unit coupled to the memory. In other words, the first cryptographic apparatus2410 can comprise a memory and a processing unit coupled to the memory, wherein the processing unit is configured to execute steps noted above for the first cryptographic unit. Similarly, the second cryptographic apparatus can also comprise a memory and a processing unit coupled to the memory, wherein the processing unit of the second cryptographic apparatus is configured to execute steps noted above for the second cryptographic unit.

Of course, previously described exemplary aspects of the invention including but not limited to the utilization of single or multiple guard bits, storing a portion of a field element or the entire field element in a single register (or storing a portion of or an entire quantity representing a point on an elliptic curve over F in a single register), the options of various functional forms of p, etc. are applicable to theexemplary method2500 illustrated inFIG. 25.

In another aspect of the present invention, there is provided a method of public-key cryptography as another example of thecryptographic method2450. An exemplary method of public-key cryptography2600 according to the present invention will now be described with reference toFIGS. 24A and 26. Theexemplary method2600 corresponds to an adaptation of ElGamal public-key encryption and decryption modified according to the present invention. It will be understood that each

cryptographic apparatus

2401 and2403 illustrated inFIG. 24A can be implemented using a memory and a processing unit coupled to the memory, wherein each respective processing unit executes steps associated with the corresponding cryptographic apparatus.

In theexemplary method2600, the second converser obtains a public key yA associated with a first converser, wherein yA=g^xAand wherein xA is the first converser's private key (step2601). For example, the second converser can receive a transmission comprising the first converser's public key and the quantity g, or the second converser can look-up the first converser's public key and the quantity g from a directory in which this information is published. The quantity g is an element of a finite field F or a point on an elliptic curve over F, wherein F is an odd-characteristic finite field GF(p^k) or an extension field of GF(p^k), p being an odd prime. The first and second conversers can agree in advance on a particular choice for F to be used and for whether an elliptic curve is to be used, or the first converser can publish this information in a directory along with the public key yA and the quantity g. The quantity yA comprises plural first base coefficients, and the quantity g comprises plural second base coefficients, the first and second base coefficients being elements of GF(p). The first converser can use the firstcryptographic apparatus2401 to generate the public key yA=g^xA. The first converser's private key xA can be a randomly or pseudorandomly generated integer as these terms are conventionally understood in the art and is not intended to be shared with other conversers. In this regard, theFFCU2411 associated with the first converser can store multiple groups of data bits representing coefficients of g in a register and can process the multiple groups of data bits in parallel using the exponentiation operation referred to in equation 32 in conjunction with the single-guard-bit representation or the multiple-guard-bit representation to generate yA. As noted above, the first converser's public key yA can be published in a directory, but it is intended for the first converser to keep the quantity xA (the private key) secret.

The second converser generates a number r (e.g., using a random-number generator or psuedo-random-number generator that can be incorporated, for example, into the key source2413) and calculates a pair of quantities (u, v)=(g^r, f⁻¹(P)*(yA)^r) using the FFCU2415 (e.g. a processing unit), wherein P represents a plaintext message of a set of plaintext messages, f is a mapping function that maps at least a portion of a vector space over F to the set of plaintext messages, and * denotes a suitable binary operation on the vector space over F (step2603). Additional details relating to the mapping function f, the vector space over F and the operation * will be described below and with reference toFIG. 27 (which addresses the case where g is an element of F) andFIG. 28 (which addresses the case where g is a point on an elliptic curve over F).

The number r can be a randomly or pseudorandomly generated integer as these terms are conventionally understood in the art. The number r is not intended to be shared with other conversers, and, in this regard, can be considered a secret number. To calculate the quantity v, multiple groups of first data bits representing at least some of the plural first base coefficients of yA are stored in a first register and processed in parallel. The multiple groups of first data bits can be stored in the first register such that at least one first guard bit is positioned adjacent to the most significant bit of each group of first data bits, each group of first data bits being separated from an adjacent group of first data bits by a corresponding at least one first guard bit. In other words, either the single-guard-bit representation or the multiple-guard-bit representation can be used. An initial value of zero can be assigned to each first guard bit. Where, g is chosen to be an element of F, the exponentiation of yA can be carried according to equation 32 described previously. Where g is chosen to be a point on an elliptic curve over F, the exponentiations associated with (yA)^rand g^xAdenote r-fold (or xA-fold) elliptic-curve point addition.

The first and second conversers agree in advance on the set of plaintext messages they will use in their communications. The function f is a mapping function that maps at least a portion of the vector space over F to the set of plaintext messages, and the first and second conversers agree on the mapping function f in advance. For example, the set of plaintext messages can comprise words, sentences and/or individual characters, and each plaintext message can be encoded as an integer.

The quantity g will generate a group over which cryptographic calculations are carried out, and the nature of the group depends upon the choice of g. In addition, it will be appreciated by those of ordinary skill in the art that the choice of g (and thus the group) also impacts the dimension of the vector space over F. Moreover, the nature of the group affects how exponentiation is carried out instep2603 and affects the choice of the binary operation *. For example, the group generated by g can be the finite field F, in which case the vector space is the one-dimensional vector space corresponding to F, and the operation * is multiplication in F. Alternatively, the group generated by g can be a subgroup of the finite field F, in which case the vector space is also the one-dimensional vector space corresponding to F, and * is again multiplication in F. As another alternative, the group generated by g can be an elliptic-curve group over F, and the operation * can be elliptic-curve point addition or component-wise multiplication in F×F as will be discussed in greater detail with reference toFIG. 28. In this latter case, the vector space over F can be chosen according to two options. In the first option, the vector space over F can be the two dimensional vector space corresponding to F×F where “x” denotes the Cartesian product. In the second option, the vector space can be a three-dimensional vector space over F in which projective coordinates known to those of ordinary skill in the art are used in conjunction with the elliptic-curve group. To the extent that the group generated by g can be smaller than any of the above-noted vector spaces, it can be sufficient for f to map merely a portion of the vector space over F to the set of plaintext messages.

The quantity g should therefore be chosen such that the size of the group generated by g is equal to or larger than the set of plaintext messages. Moreover, it is assumed that the quantities g and yA, which are assumed to be publicly available, are chosen such that determining xA from yA and g would be computationally infeasible. Other considerations involving the relationship between security and the size of the group generated by g will be apparent to those of ordinary skill in the art in view of conventionally known attributes of ElGamal public-key cryptosystems, such as described, for example, inHandbook of Applied Cryptographyreferred to previously. For example, it is known to those of ordinary skill in the art how to choose the size of a group utilized in conventional ElGamal public-key cryptosystems. Alternatively, it is also known to those of ordinary skill in the art how to approximate the size of the group based on a given choice of the generator. These aspects are also applicable to the above-describedmethod2600 according to the present invention.

The mapping function f should be chosen such that each element of the group generated by g corresponds to a different plaintext message. In other words, the mapping function f can be uniquely invertible. Alternatively, if the group generated by g is larger than the set of plaintext messages, the mapping function f can be chosen such that more than one element of the group generated by p is associated with the same plaintext message. Where plaintext messages are encoded as integers, the mapping function f can be then chosen such that f is an almost injective mapping from the group generated by g to the set of integers {0, 1, 2, . . . , Q−1}, where Q≈|G| (|G| is the size of the group). For example, this can be essentially an identity mapping. Choosing a given mapping function f is within the purview of one of ordinary skill in the art in view of the above-described teachings.

The second converser then sends the pair of quantities (u, v) to the first converser over the insecure channel2417 (step2605). The pair of quantities (u, v) corresponds to an encrypted version of the plaintext message.

In addition, the calculation of the quantity u can be carried out by the second converser by storing multiple groups of second data bits representing at least some of the plural second base coefficients of g in a second register and by processing the multiple groups of second data bits in parallel. In this regard either the single-guard-bit representation or the multiple-guard-bit representation can be used. The calculation of g^xA(to calculate u) can be carried out using exponentiation according to equation 32 or using xA-fold elliptic-curve point addition depending upon the choice for g. The quantities g, u and v can be elements of the finite field F, wherein F can be chosen as GF(p^k) or as an extension field of GF(p^k). Alternatively, the quantities g, u and v can be points on an elliptic curve over F.

The first converser can decrypt a received pair of quantities (u, v), thereby retrieving the plaintext message P, by computing P=f(u^−xA*v) where u^−xA*v=v/u^xAand wherein “/” denotes the inverse of the operation of * (step2607). The quantity u^xAcan be computed by thefirst FFCU2411 according to the exponentiation function of equation 32 or according to xA-fold elliptic-curve point addition as appropriate. This computation can be carried out using the single-guard-bit representation or multiple-guard-bit representation, such as described above with regard to key exchange. Only the first converser who knows xA is assumed to be able to decrypt this message. By implementing the above-described adaptation of ElGamal public-key cryptography using the single-guard-bit representation or multiple-guard-bit representation, the present invention offers increased computational efficiency compared to conventional approaches, which can either be manifested as increased speed compared to conventional approaches or increased security for the same computational effort.

Of course, previously described exemplary aspects of the invention including but not limited to the utilization of single or multiple guard bits, storing a portion of a field element or the entire field element in a single register (or storing a portion of or an entire quantity representing a point on an elliptic curve over F in a single register), the options of various functional forms of p, etc. are applicable to theexemplary method2600 illustrated inFIG. 26.

Exemplary implementations of themethod2600 will now be described with reference toFIG. 27 (which addresses the case where g is an element of F) andFIG. 28 (which addresses the case where g is a point on an elliptic curve over F).

FIG. 27 is a flow diagram of an exemplary method of public-key cryptography2700. In theexemplary method2700, the second converser obtains a public key yA associated with a first converser, wherein yA=g^xAand wherein xA is the first converser's private key (step2701). For example, the second converser can receive a transmission comprising the first converser's public key and the quantity g, or the second converser can look-up the first converser's public key and the quantity g from a directory in which this information is published. The quantity g is an element of a finite field F wherein F is an odd-characteristic finite field GF(p^k) or an extension field of GF(p^k), p being an odd prime. The first and second conversers can agree on particular choices for F to be used in advance, or the first converser can publish this information in a directory along with the public key and the quantity g. The quantity yA comprises plural first base coefficients, and the quantity g comprises plural second base coefficients, the first and second base coefficients being elements of GF(p). The first converser can use the firstcryptographic apparatus2401 to generate the public key yA=g^xA. The first converser's private key xA can be a randomly or pseudorandomly generated integer as these terms are conventionally understood in the art and is not intended to be shared with other conversers. In this regard, theFFCU2411 associated with the first converser can store multiple groups of data bits representing coefficients of g in a register and can process the multiple groups of data bits in parallel using the exponentiation operation referred to in equation 32 in conjunction with the single-guard-bit representation or the multiple-guard-bit representation to generate yA. As noted above, the first converser's public key yA can be published in a directory, but it is intended for the first converser to keep the quantity xA (the private key) secret.

The second converser generates a number r (e.g., using a random-number generator or psuedo-random-number generator that can be incorporated, for example, into the key source2413) and calculates a pair of quantities (u, v)=(g^r, f⁻¹(P)*(yA)^r) using the FFCU2415 (e.g. a processing unit), wherein * denotes multiplication in F and wherein P represents a plaintext message of a set of plaintext messages (step2703). The number r can be a randomly or pseudorandomly generated integer as these terms are conventionally understood in the art. The number r is not intended to be shared with other conversers, and, in this regard, can be considered a secret number. To calculate the quantity v, multiple groups of first data bits representing at least some of the plural first base coefficients of yA are stored in a first register and processed in parallel. The multiple groups of first data bits can be stored in the first register such that at least one first guard bit is positioned adjacent to the most significant bit of each group of first data bits, each group of first data bits being separated from an adjacent group of first data bits by a corresponding at least one first guard bit. In other words, either the single-guard-bit representation or the multiple-guard-bit representation can be used. An initial value of zero can be assigned to each at least one first guard bit. In addition, the exponentiation of yA can be carried according to equation 32 described previously.

The first and second conversers agree in advance on the set of plaintext messages they will use in their communications. The function f is a mapping function that maps at least a portion of F to the set of plaintext messages, and the first and second conversers agree on the mapping function f in advance. For example, the set of plaintext messages can comprise words, sentences and/or individual characters, and each plaintext message can be encoded as an integer. The quantity g will generate a group over which cryptographic calculations are carried out. This group can be the multiplicative group of the finite field F, or a subgroup of that multiplicative group, depending upon the choice of g. To the extent that the group generated by g can be smaller than F, it can be sufficient for f to map merely a portion of F to the set of plaintext messages.

The second converser then sends the pair of quantities (u, v) to the first converser over the insecure channel2417 (step2705). The pair of quantities (u, v) corresponds to an encrypted version of the plaintext message.

In addition, the calculation of the quantity u can be carried out by the second converser by storing multiple groups of second data bits representing at least some of the plural second base coefficients of g in a second register and by processing the multiple groups of second data bits in parallel. In this regard either the single-guard-bit representation or the multiple-guard-bit representation can be used, and the exponentiation of g (to calculate u) can be carried out using equation 32 described previously. The quantities g, u and v can be elements of the finite field F, wherein F can be chosen as GF(p^k) or as an extension field of GF(p^k).

The first converser can decrypt a received pair of quantities (u, v), thereby retrieving the plaintext message P, by computing P=f(u^−xA*v) where u^−xA*v=v/u^xAand wherein “/” denotes division in F (step2707). Carrying out division in F is within the purview of those of ordinary skill in the art and requires no further discussion. The quantity u^xAcan be computed by thefirst FFCU2411 by applying the exponentiation function of equation 32 using the single-guard-bit representation or multiple-guard-bit representation, such as described above with regard to key exchange. Only the first converser who knows xA is assumed to be able to decrypt this message. By implementing the above-described adaptation of ElGamal public-key cryptography over a group defined over GF(p^k), or the field itself, using the single-guard-bit representation or multiple-guard-bit representation, the present invention offers increased computational efficiency compared to conventional approaches, which can either be manifested as increased speed compared to conventional approaches or increased security for the same computational effort.

Of course, previously described exemplary aspects of the invention including but not limited to the utilization of single or multiple guard bits, storing a portion of a field element or the entire field element in a single register (or storing a portion of or an entire quantity representing a point on an elliptic curve over GF(p^k) in a single register), the options of various functional forms of p, etc. are applicable to theexemplary method2700 illustrated inFIG. 27.

The above-described public-key cryptography method2700 can also be modified according to the present invention for implementation using elliptic curves over F where F is as above. Anexemplary method2800 of public-key cryptography and will now be described with reference toFIG. 28. In fact, the treatment is completely analogous to that described with regard toFIG. 27, and the discussion here will be abbreviated, describing mainly the differences that need to be considered. We assume the first and second converser have agreed on an elliptic curve group, or, that a description of the group to be used is transmitted between the conversers. This can, for instance, be done as a preamble to actual messages.Step2801 is completely analogous to step2701 described previously, except that in themethod2800, g is a point on an elliptic curve over F. Thus, in theexemplary method2800, the second converser obtains a public key yA associated with a first converser, wherein yA=g^xAand wherein xA is the first converser's private key (step2801). The quantity g is a point on an elliptic curve over the finite field F wherein F is an odd-characteristic finite field GF(p^k) or an extension field of GF(p^k), p being an odd prime. The quantity yA comprises plural first base coefficients, and the quantity g comprises plural second base coefficients, the first and second base coefficients being elements of GF(p).

The second converser generates a number r (e.g., using a random-number generator or psuedo-random-number generator that can be incorporated, for example, into the key source2413) and calculates a pair of quantities (u, v)=(g^r, f⁻¹(P)*(yA)^r) using the FFCU2415 (e.g. a processing unit), wherein P represents a plaintext message of a set of plaintext messages, wherein * is elliptic-curve point addition or component-wise multiplication in F×F, and wherein r can be generated as described above (step2803). The function f is a mapping function that maps at least a portion of F×F to the set of plaintext messages, wherein multiple groups of first data bits representing at least some of the plural first data base coefficients of yA are stored in a first register and processed in parallel to calculate v. Additional aspects relating to the calculation of u and v will be described below.

As noted atstep2805, the second converser then sends the pair of quantities (u, v) to the first converser, the pair of quantities corresponding to an encrypted version of the plaintext message. As noted atstep2807, the first converser can then can decrypt a received pair of quantities (u, v), thereby retrieving the plaintext message P, by computing P=f(u^−xA*v) where u^−xA*v=v/u^xAand wherein “/” denotes the inverse of the operation * (step2807). Additional details relating to the operation “/” will be described below. The quantity u^xAcan be computed by thefirst FFCU2411 by applying the exponentiation function in equation 32 using the single-guard-bit representation or multiple-guard-bit representation, such as described above with regard to key exchange. Only the first converser who knows xA is assumed to be able to decrypt this message. By implementing the above-described adaptation of ElGamal public-key cryptography over an elliptic curve over F using the single-guard-bit representation or multiple-guard-bit representation, the present invention offers increased computational efficiency compared to conventional approaches, which can either be manifested as increased speed compared to conventional approaches or increased security for the same computational effort.

Additional aspects relating to calculation of the pair of quantities u and v by the first converser and relating to retrieving a plaintext message P from the pair of quantities u and v by the first converser will now be described. From a notational point of view, such as already mentioned in connection to equation 49, the exponentiations associated with (yA)^r, g^r, etc., now denote r-fold (or xA-fold) elliptic curve point addition. Computing the quantity u is thus completely analogous to the approach set forth with regard toFIG. 27, and u will now be an elliptic curve point. For v, two cases can be considered for the operation * and the mapping function f, as will now be described. In either of the two cases, the second converser needs to compute a value of the form f⁻¹(P)*(yA)^r, where (yA)^ris now a point on the elliptic curve, i.e. an (x, y)-coordinate pair in F×F, where × denotes Cartesian product, i.e. pairs of elements from F. Thus, f⁻¹needs to produce a value that can be composed with this two-dimensional value. In the first case that f can be chosen so that f⁻¹is guaranteed to be a point on the elliptic curve, * can simply be the usual elliptic curve point addition operation. For the first converser in this case, the “/” operation is point subtraction (the inverse of addition, which is well-known to those of ordinary skill in the art). For the first case, the f mapping can be done in several ways, an example of which is as follows. We can assume that the plaintext message space consists of binary strings of length smaller than lk log₂(p), where l, k, p are the values defining the field F. Note that this can be assumed without loss of generality, since we can cut a message of longer size into smaller blocks, satisfying this length constraint, and can process each block individually. We can also interpret P in the natural way as a set of base coefficients of the field F. Note that P does not uniquely determine the element associated with this set of base coefficients, since some bits are left unspecified. (The actual position of the unspecified bits can be agreed upon in advance or communicated between the conversers.) We can assign a random value, R, to the unspecified bits, and obtain a value x=x(P, R) in F. This x value is evaluated as the right-hand side of equation 48. As is well-known to those of ordinary skill in the art, the probability that there exists a left-hand y-value satisfying the equality of equation 48 is one half, and if so, finding a matching y-value can be done with well-known methods. If no matching y-value exists, we repeat the process with a new random R, etc. The probability that the process would repeatedly fail for a large number of consecutive attempts is small. The above approach describes how f⁻¹can be computed by the second converser. The first converser computes f by simply discarding the y-coordinate of the elliptic curve point, and also by discarding the bit-positions corresponding to the randomly chosen R-bits.

The above-described procedure merely serves as an example how to embed messages as elliptic curve points, other approaches to defining f are possible. With regard to such approaches, it can be slightly complicated in general to assure that the mapping always produces points on the elliptic curve, satisfying equation 48. This concludes the discussion relating to the first exemplary case for choices of the mapping function f and the operation “*” associated with

steps

2803 and2807.

In the second exemplary case for choices of the mapping function f and the operation “*”, it is not required to carry out the calculations in

steps

2803 and2807 to produce points on an elliptic curve. Thus, approaches involving the second case described here may be more attractive. We now describe one exemplary approach for the second case. In the second case, one chooses f to be a mapping that maps at least a fraction of arbitrary values in F×F to the plaintext space. That is, we produce more or less arbitrary (x, y) coordinate pairs, not necessarily satisfying48. This is done so that unique decryption is almost always guaranteed (thus, the field F in general needs to be at least as large as the square root of the size of the plaintext space). Finding such f is easy and well-known to those of ordinary skill in the art. For instance, interpreting P as a set of base coefficients, encoded as binary strings, f can be essentially the identity mapping. In the second case, the combination operation * is defined to simply be coordinate-wise multiplication in F, i.e. (a, b)*(x, y)=(ax, by). For the second converser (the receiver in this exemplary description), the operation “/” is correspondingly defined as coordinate-wise division in F (the inverse operation of “*”). The approach of using coordinate-wise multiplication and division rather elliptic curve operations is known in the literature as the Menezes-Vanstone method and can be applied to the present invention as described above.

In both of the above-described approaches associated with the two cases for choices of the mapping function f, parallel processing multiple groups of data bits representing base coefficients takes place as described before.

Observe that in all of the three above-described approaches according to the present invention relating toFIGS. 27 and 28 (modified ElGamal over F, modified ElGamal over an elliptic curve E over F with plaintext embedding in E, and modified ElGamal over an elliptic curve E over F without plaintext embedding in E), the function f can be viewed as mapping at least a portion of a one-dimensional vector space (that is, F) or two-dimensional vector space over F (e.g., F×F) to the set of plaintext messages.

In another exemplary aspect, themethod2800 can be modified such that instead of mapping at least a portion of a two-dimensional vector space over F (that is, F×F) to the set of plaintext messages, the mapping function f can be chosen such that f maps at least a portion of a three-dimensional vector space over F to the set of plaintext messages. In this aspect, projective coordinates in a three dimensional vector space are used in conjunction with an elliptic curve approach. Other aspects of the approach remain the same as those set forth inFIG. 28 for theexemplary method2800. Projective coordinates are known to those of ordinary skill in the art, and no further discussion of modifying themethod2800 according to this aspect is necessary.

In another aspect of the present invention, encryption, decryption and/or authentication can be implemented using a secure key chosen by one of the conversers and exchanged over a secure channel, such as thesecure channel2421 illustrated inFIG. 24A. For example, either the first converser or the second converser can generate a secure key using the firstkey source2409 or the secondkey source2413. Such a secure key can then be exchanged over the secure channel2421 (e.g., using a courier). Encryption and decryption can then be carried out using the

FFCUs

2411 and2415 illustrated inFIG. 24A. In this regard, the cryptographic algorithm referred to inFIG. 24B can be any suitable encryption algorithm that can be implemented in accordance withmethod2450, and encrypted information can be thereby transmitted over theinsecure channel2417. As another example, information can be encrypted using any conventional encryption algorithm, and the cryptographic algorithm referred to inFIG. 24B can be any suitable authentication algorithm that can be based upon the secure key exchanged over thesecure channel2421 and that can be implemented in accordance withmethod2450. Implementing a suitable authentication algorithm in accordance withmethod2450 is within the purview of one of ordinary skill in the art in view of the teachings provided herein.

In another aspect of the present invention, a variant of ElGamal public-key cryptography can be implemented using the present inventive approaches over a finite field F, where F is the finite field GF(p^k) or an extension field of GF(p^k) (p being an odd prime) to provide digital signatures using thecryptographic system2400 illustrated inFIG. 24A. For example, such a variant based upon the basic DSA (Digital Signature Algorithm) will now be described. Other variants exist as well.

Once again, a group defined over F, a quantity g (e.g., an element of F or a point on an elliptic curve over F), and a mapping function f are agreed upon by first and second conversers, such as described above with regard to the exemplary implementation of ElGamal public-key cryptography over GF(p^k) according to the present invention inFIG. 26. In addition, the first converser generates a private key xA and a public key yA as described above. To sign a message P (e.g., plaintext or ciphertext encoded as an integer), the first converser can proceed as follows. The first converser generates a number r (e.g., a randomly or pseudorandomly generated integer) using, for example, a random number generator or a pseudorandom number generator that can be incorporated, for example, into thekey source2409, and computes a=g^rusing thefirst FFCU2411 by applying the exponentiation function32 in conjunction with either the single-guard-bit representation or multiple-guard-bit representation. The number r is not intended to be shared with other conversers, and, in this regard, can be considered a secret number. The first converser then computes a solution to the equation
P=−xA*f(a)+r*b(mod |G|) (50)
where * is ordinary multiplication to find a quantity b that satisfies equation 50. Only the first converser, knowing xA, is assumed to be able to do this. The signature to the message P is then defined as the pair (a, b).

The first converser can then sign the plaintext message P using thefirst FFCU2411 by applying one of the cryptographic approaches described above, thereby generating the signature, (a, b), and sends P and the pair (a, b) to the second converser over theinsecure channel2417.

To verify that the pair (a, b) represents a valid signature on P of the first converser, the second converser computes the following quantities u and v
u=P*b⁻¹(mod |G|) (51)
v=f(a)*b⁻¹(mod |G|) (52)
where b⁻¹is the multiplicative inverse of b and * represents multiplication (conventional multiplication). The second converser then computes g^u(yA)^vusing thesecond FFCU2415 by applying the exponentiation function32 in conjunction with the inventive approaches for storing plural groups of first data bits representing coefficients of yA in a first register, storing plural groups of second data bits representing coefficients of a representation of g in a second register, processing the plural groups of first data bits in parallel, and processing the plural groups of second data bits in parallel. The second converser accepts the signature as valid if, and only if, g^u(yA)^v=a. Accordingly, computational approaches involving the field GF(p^k) according to the present invention can be applied to digital signatures, and the corresponding computations can be executed in a manner much faster than conventional approaches involving GF(p^k) or in a manner that provides significantly greater security against forged signatures for the same computational effort.

Using elliptic curves over F according to the present invention is also a possible setting for digital signatures. In the case of elliptic-curves, the differences that need to be considered in comparison to the above-described implementation of digital signatures are completely analogous to the differences in implementation of public-key cryptography where g is an element of a finite field F (FIG. 27) and where g is a point on an elliptic curve over F (FIG. 28). Accordingly, no further discussion of using elliptic curves in conjunction with digital signatures according to the present invention is necessary.

In another aspect of the invention, a pseudorandom number generator can be provided that carries out computations in the field GF(p^t) (p being an odd prime number) using computational approaches previously described herein. A pseudorandom number generator deterministically expands short random seeds to longer strings that appear to be random. Many conventional constructions are known to those of ordinary skill in the art, and such constructions can be based on finite fields and elliptic curves, for example. The inventive computational approaches described herein can be applied to such constructions.

For example, let F=GF(pⁿ) be a finite field, defined as an extension field of GF(p^t) for some t=n/w where w is an integer. Let g be an field element of F that generates a sufficiently large subgroup of F's multiplicative group. In addition, let f be a function as described above with regard to the application of the present inventive approaches to ElGamal public-key cryptography. Finally, let Tr be trace-mapping well known to those of ordinary skill in the art, which maps elements of F to elements of GF(p^t) in accordance with the following equation

\begin{matrix} Tr (x) = x + x^{p^{t}} + x^{p^{2 t}} + \dots + x^{p^{n - t}} & (53) \end{matrix}

for any x in F. Finally, define the function I(x) as I(x)=g^x.

Upon input of a random seed s (as a binary encoded integer), the generator is now defined as follows. Let x₀=I(s), and let x_i+1=I(f(x_i)) for i=0, 1, 2, . . . , T. In principle T can be taken to be very large, e.g. of magnitude comparable to square root of the field size, though a smaller T will give higher security. In addition, define the output of the pseudorandom number generator to be the concatenation of Tr(x₀), Tr(x₁), Tr(x₂), . . . . This approach provides an output consisting of pseudorandom elements of GF(p^t). If a binary string is desired as output, a suitable conversion function is applied to the outputs. Under the assumption that the discrete logarithm problem in the group is intractable (i.e., computationally infeasible), the above-described pseudorandom number generator will be secure. As indicated above, the pseudorandom number generator utilizes various operations in GF(p^t), including addition, multiplication and exponentiation, and the previously described inventive approaches based upon either the single-guard-bit representation or the multiple-guard-bit representation can be used to efficiently carry out the necessary computations.

The embodiments described herein are merely illustrative and should not be considered restrictive in any way. The scope of the invention is given by the appended claims, rather than the preceding description, and all variations and equivalents which fall within the range of the claims are intended to be embraced therein.