LINEBURG

r

[4] Massey, J.L. (1992). “Contemporary cryptology: An

“little-ω” notation: T(x) = ω(U(x)) means that

introduction.” Contemporary Cryptology, The Sci-

for every constant c, T(x) > cU(x) for all suf¬-

ence of Information Integrity. ed. G.J. Simmons.

ciently large x.

IEEE Press.

The notations are analogous to the usual arith-

[5] Menezes, A.J., P.C. van Oorschot, and S.A. Vanstone

metic comparison operators >, ≥, =, ¤, and <:

(1997). Handbook of Applied Cryptography. CRC

Press, Boca Raton, FL.

Notation Operator

[6] Needham, R.M. and M.D. Schroeder (1978). “Using

ω >

encryption for authentication in large networks of

≥

computers.” Communications of the ACM, 21, 993“

=

999.

¤

O

[7] Pohlig, S.C. and M.E. Hellman (1978). “An improved

<

o

algorithm for computing logarithms over GF(p) and

448 Optimal extension ¬elds (OEFs)

For instance, if T(x) = O(U(x)) and U(x) = polynomial x 6 ’ 2. Note that the cardinality of this

O(V(x)), then T(x) = O(V(x)); if T(x) = o(U(x)) OEF is roughly (232 ’ 387)6 ≈ 2192 .

then U(x) = ω(T(x)), and so on. The main motivation for OEFs is that the ¬eld

The notations O(1) and o(1) deserve special ex- parameters can be chosen such that they are

planation. O(1) denotes a function of x that is a good match for the processor on which the

bounded by a constant as x ’ ∞, since one has ¬eld arithmetic is to be implemented. In partic-

that ular, it is often an advantage to choose an OEF

GF( pm ) such that the prime p can be represented

T(x) ¤ c — 1 = c

within one register of the target processor. For in-

stance, in the OEF example given above, GF((232 ’

for some constant c and all suf¬ciently large x.

387)6 ), the prime 232 ’ 387 ¬ts nicely in the reg-

Likewise, o(1) denotes a function of x that tends

isters of a 32-bit CPU. In this situation, ¬eld

toward 0 as x ’ ∞.

arithmetic can be implemented rather ef¬ciently.

The various notations can also be employed

The following theorem from [5] describes the

within more complex mathematical expressions.

cases when an irreducible binomial over GF( p)

For instance, in the expression

exists:

T(x) = e(γ +o(1))(log x) (log log x) ,

t 1’t

for x ’ ∞,

THEOREM 1. Let m ≥ 2 be an integer and ω ∈

the ¬rst term in the exponent tends toward γ as GF ( p)— . Then the binomial x m ’ ω is irreducible

x ’ ∞. in GF ( p)[x] if and only if the following two con-

Technically, notation such as O(U(x)) denotes ditions are satis¬ed: (i) each prime factor of m di-

the set of all functions which asymptotically grow vides the order e of ω over GF(p), but not ( p ’ 1)/e;

more slowly than U(x). Thus, formally one might (ii) p ≡ 1 mod 4 if m ≡ 0 mod 4.

write T(x) ∈ O(U(x)) to denote membership in this

set. Also, in mathematics, one is sometimes con- An important corollary is given in [4]:

cerned with the relationship between functions

as the input approaches some ¬nite value, rather COROLLARY 1. Let ω be a primitive element for

than as it tends toward in¬nity. However, in cryp- GF ( p) and let m be a divisor of p ’ 1. Then x m ’ ω

tography, the notation T(x) = O(U(x)) is standard, is an irreducible polynomial.

and the limit x ’ ∞ is assumed.

A brief outline of the arithmetic algorithms

Burt Kaliski

of OEFs follows, where we distinguish between

arithmetic in the sub¬eld GF(p) and arithmetic in

the extension ¬eld GF( pm ). Extension ¬eld arith-

metic requires sub¬eld calculations as a “subrou-

OPTIMAL EXTENSION tine”.

FIELDS (OEFs) Sub¬eld addition and subtraction. If p can

be represented in one register, all elements of

GF( p) = {0, 1, . . . , p ’ 1} can be represented as

Optimal extension ¬elds (OEFs) are a family of

¬nite ¬elds with special properties. They were de- simple one-word integers. Addition is straight-

signed in a way that leads to ef¬cient ¬eld arith- forward and very ef¬cient: One performs a reg-

metic if implemented in software. OEFs were in- ular integer addition and, if the sum is larger

troduced ¬rst in [3] and independently in [7]. They than p, the modulus p is subtracted from the

are de¬ned as follows: sum (see modular arithmetic). Subtraction can

be done analogously.

DEFINITION 1. An Optimal Extension Field is a ¬- Sub¬eld multiplication. Due to the fact that p

nite ¬eld GF( pm ) such that: is a pseudo-Mersenne prime, sub¬eld multipli-

1. p is a prime number of the form 2n ± c, log2 c ¤ cation is also ef¬cient. In fact, the overall per-

1

n (such primes are also referred to as pseudo- formance of OEFs greatly relies on the fact that

2

Mersenne prime), sub¬eld multiplication is fast. In a typical im-

2. An irreducible binomial P(x) = x m ’ ω exists plementation, in a ¬rst step the two operands

a, b ∈ GF( p) are multiplied yielding the integer

over GF( p).

product d = a — b. This is done with one in-

An example of an OEF is the ¬eld GF ( p6 ) teger multiplication. Note that in the general

with the prime p = 232 ’ 387 and the irreducible case, d has about twice the bit length of p if we

Optimal extension ¬elds (OEFs) 449

than or equal to 2m ’ 2:

assume that a and b both have about the same

bit lengths as the modulus p. Due to the spe-

C (x) = A(x) — B(x)

cial form of p, the following algorithm allows an

= c2m’2 x 2m’2 + · · · + c1 x + c0 ,

ef¬cient reduction d mod p without performing

an explicit integer division. We present a form ci ∈ GF ( p). (1)

of such a modular reduction algorithm, adapted

The schoolbook method to calculate the co-

from [6]. The operator is taken to mean

ef¬cients ci , i = 0, 1, . . . , 2m ’ 2, requires m2

“right shift”.

multiplications and (m ’ 1)2 additions in the

sub¬eld GF(p). Optionally, the Karatsuba algo-

ALGORITHM 1. Fast Sub¬eld Modular Reduction

rithm can be applied here to reduce the number

Require: p = 2n ’ c, log2 c ¤ , d < p2 is

1

n of coef¬cient multiplications. For instance, for

2

the integer to reduce ¬elds GF( p6 ), the polynomial multiplication can

Ensure: r ≡ d mod p be performed with 18 sub¬eld multiplications

q0 ← d n (as opposed to 36 with the schoolbook method)

r0 ← d ’ q0 2n when applying the Karatsuba algorithm recur-

r ← r0 sively [2].

i←0 In the second stage of the OEF multiplica-

while qi > 0 do tion, the intermediate result C (x) has to be re-

qi+1 ← qi c n duced modulo the irreducible polynomial P(x) =

ri+1 ← qi c ’ (qi+1 n) x m ’ ω. We note that the following congru-

i ←i +1 ences hold: x m ≡ ω mod P(x), x m+1 ≡ ωx mod

r ← r + ri P(x), . . . , x 2m’2 ≡ ωx m’2 mod P(x). Hence, the

end while terms cm x m , . . . , c2m’2 x 2m’2 can each be reduced

while r ≥ p do with one multiplication by ω and one addition in

r ←r’ p the sub¬eld. Thus, the entire modulo reduction

end while requires at most m ’ 1 multiplications by ω and

m ’ 1 additions, where both of these operations

This reduction algorithm requires two integer are performed in GF(p).

multiplications andsome shifts and additions. If Extension ¬eld inversion. The two most use-

we ignore the latter operations, the main costs ful methods for inversion are the Euclidean al-

for one OEF sub¬eld multiplication are 1 + 2 = gorithm and reduction of the extension ¬eld

3 integer multiplications. inversion to sub¬eld inversion via the Itoh“

An important special case is OEFs where the Tsujii algorithm. See Inversion in Finite Fields

prime has the form p = 2n ± 1. In this case, the and Rings for a detailed description of those two

modulo reduction itself can be performed with inversion methods.

one addition or subtraction, and the main costs Extension ¬eld exponentiation. One can use

for an entire sub¬eld multiplication are one in- either one of the standard exponentiation tech-

teger multiplication. The reduction method for niques, such as the sliding window method. A

primes 2n ’ 1 is described in the entry Mersenne particularly fast method for OEFs is the one de-

prime. OEFs with primes 2n ± 1 are sometimes scribed in [1] which is based on the fact that the

referred to as Type I OEFs [3]. Frobenius automorphism can be computed ef¬-

Extension ¬eld addition and subtraction. Ad- ciently in OEFs.

A generalization of OEFs, that is ¬elds GF( pm ),

dition of two ¬eld elements is simply an addition

p > 2, with p not necessarily a pseudo-Mersenne

of the corresponding coef¬cients of the two el-

ements. The coef¬cient additions follow GF(p) prime and the ¬eld polynomial not necessarily a

arithmetic rules. Subtraction is done analo- binomial, is discussed in [1]. Tables with OEFs and

gously. more details about the arithmetic of OEFs are de-

Extension ¬eld multiplication. It is usually ad- scribed in [2].

vantageous to represent elements of OEFs in a OEFs are applicable as underlying algebraic

standard (or polynomial) basis. Field multipli- structure for cryptosystems that rely on ¬-

cation can be performed in two stages. First, we nite ¬elds. In particular, they appear useful for

perform an ordinary polynomial multiplication elliptic curve cryptosystems and schemes using

of two ¬eld elements A(x) and B(x), resulting the discrete logarithm in ¬nite ¬elds. At the time

in an intermediate product C (x) of degree less of writing, it remains an open question whether

450 Order

OVERSPENDER

elliptic curve cryptosystems and discrete loga-

rithm schemes which use OEFs (rather than

DETECTION

prime ¬elds or ¬elds GF(2m )) have cryptographic

weaknesses.

In electronic payment schemes and electronic

Christof Paar cash that use prepaid electronic coins, there is a

natural fraud scenario where a customer tries to

References use an already spent electronic coin a second or

third time. An important security requirement in

ˇ

[1] Avanzi, R.A. and P. Mihailescu (2003). “Generic ef-

such schemes is thus overspender detection, i.e.,

¬cient arithmetic algorithms for PAFFs (Proces-

an effective way of determining the culprit who

sor Adequate Finite Fields) and related algebraic

has spent an electronic coin twice. A related and

structures.” Workshop in Selected Areas in Cryptog-

equally important security requirement is to de-

raphy (SAC), Lecture Notes in Computer Science,

tect coins that are overspent or even better to pre-

vol. 3006, eds. M. Matsui and R. J. Zuccheratop.

vent coins from being overspent (see overspending

Springer-Verlag, Berlin, Germany, 130“144.

prevention).

[2] Bailey, D.V. and C. Paar (2001). “Ef¬cient arithmetic

in ¬nite ¬eld extensions with application in elliptic If electronic coins bear the identities of cus-

curve cryptography.” Journal of Cryptology, 14 (3), tomers who have withdrawn them, then over-

153“176. spender detection is easy to accomplish and ap-

[3] Bailey, D.V. and C. Paar (1998). “Optimal exten- pears an almost trivial security requirement. If

sion ¬elds for fast arithmetic in public-key algo-

electronic coins can be spent anonymously (see

rithms.” Advances in Cryptology”CRYPTO™98, Lec-

anonymity) though, then each coin alone carries

ture Notes in Computer Science, vol. 1462, ed. H.

too little information to identify the spender. It is

Krawczyk. Springer-Verlag, Berlin, Germany, 472“

possible, however, to design systems where two or

485.

more transactions of spending the same coin re-

[4] Jungnickel, D. (1993). Finite Fields. B.I.-Wissen-

veal enough information to the veri¬er (bank) to

schaftsverlag.

recover the identity of the overspender.

[5] Lidl, R. and H. Niederreiter (1983). “Finite ¬elds.”

Encyclopedia of Mathematics and its Applications,

Gerrit Bleumer

vol. 20. Addison-Wesley, Reading, MA, USA.

[6] Menezes, A.J., P.C. van Oorschot, and S.A. Vanstone

(1997). Handbook of Applied Cryptography. CRC

Press, Boca Raton, FL, USA.

ˇ

[7] Mihailescu, P. (1997). “Optimal galois ¬eld bases

OVERSPENDING

which are not normal.” Recent Result Session, Fast

PREVENTION

Software Encryption.

In electronic payment schemes and electronic

cash that use prepaid electronic coins, there is a

ORDER natural fraud scenario where a customer tries to

use an already spent electronic coin a second or

third time. An important security requirement in

The order of a group G = (S, —¦) is the number of

such schemes is thus to detect coins that are over-

elements in the set S, and likewise the order of

spent or even better to prevent coins from being

a ring or ¬eld (S, +, —) is the number of elements

overspent. A related and equally important secu-

in S.

rity requirement is to detect culprits who have

In a group, the order of an element g ∈ S is the

overspent one or more of their electronic coins (see

least positive integer k such that gk = 1 (where

overspender detection).

the group law is written multiplicatively and 1 de-

If electronic coins bear the identities of cus-

notes the identity element).

tomers who have withdrawn them, overspending

In a ring or ¬eld, the order of an element typi-

detection and prevention are easy to accomplish

cally refers to multiplicative order, that is, the or-

and appear an almost trivial security require-

der of the element under the multiplication oper-

ment. The veri¬ers of coins only need to check

ation in the multiplicative group.

in a database whether the electronic coin at hand

The order of each element in a group divides the

has been spent before, and if so, who the respec-

order of the group.

tive double spender is. If electronic coins can be

Burt Kaliski spent anonymously (see anonymity) though, then

Overspending prevention 451

each coin alone carries too little information to more spending transactions of the same coin re-

identify the spender. Double spending of anony- veal enough information to the veri¬er (bank) to

mous coins can therefore only be prevented by detect whether a coin has been spent before, to re-

using hardware security devices that cannot be ject the second attempt to pay with such a coin,

manipulated by their holders (under reasonable and to recover the identity of the overspender.

assumptions). It is possible, however, to design

anonymous electronic coin schemes where two or Gerrit Bleumer

452

Copyright Design by: Sunlight webdesign