LINEBURG


<< . .

 2
( 2)



large x;
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

<< . .

 2
( 2)



Copyright Design by: Sunlight webdesign