Cryptography Reference
In-Depth Information
For example, F 19 is a field with elements {0,1,2,…,18}, and addition, subtraction,
multiplication, and inversion operations can be performed. Table 3.1 shows addition
modulo 19, and Table 3.2 shows multiplication modulo 19.
3.4 Binary Fields
Binary fields or characteristic-2 finite fields (denoted as F (2 m ) ) are fields of order 2 m .
Conventionally, polynomial basis representation is used to represent F 2 m . The elements
of the binary fields are the binary polynomials with at most degree m -1.
n
-
1
+ + + + + = å
m
-
1
m
-
2
3
2
1
i
=
+
F
{
a
x
a
x
a x
a x
a x
a
}
a x
(3.11)
m
m
-
1
m
-
2
3
2
1
0
i
2
i
=
0
a Î
where
{0,1}
0
Table 3.3 shows that binary field
F has 8 binary polynomials with degree 2.
A binary polynomial f ( z ) of degree m is an irreducible polynomial if it cannot
be factored as a product of binary polynomials with each of degree less than m . In
such cases, multiplication of the field elements is performed using the reduction
polynomial f ( z ).
3
3.5 Elliptic Curve Cryptography
One of the fundamental ideas of any public-key cryptographic system is the require-
ment of a hard problem and that, from such problems, secure public key exchange can
be facilitated (Diffie and Hellman 1976). Hard problems fall under the computational
security model, which measures the computational effort involved in defeating a system
by the currently best known method. A proposed technique is supposed to be compu-
tationally secure if the perceived level of computation required to defeat the method
(using the best known attack) exceeds the computational resources of the hypothesized
adversary. In addition, an encryption or digital signature can depend on the same hard
problem. In the past 30 years, many hard problems have been proposed, but only two
of them have gained a lot of public acceptance in cryptography. These are the inte-
ger factorization problem and the discrete log problem over a finite field (Simmons
1999). For instance, the RSA algorithm, named for its inventors, Rivest, Shamir, and
Adleman, is based on the difficulty of factoring large numbers. However, RSA is opera-
tionally expensive, with a minimum key size requirement of 1024 bits. Similarly, sys-
tems based on discrete logs involve the difficulty of calculating discrete logarithms in a
finite field (Section 3.5.1). In these systems, key sizes are comparable to those in RSA.
During the mid-1980s, cryptographers started studying the rich mathematical struc-
tures of elliptic curves and their applicability in primality testing and integer factoriza-
tion (Lenstra 1987; Menezes 1993). In 1985, Neal Koblitz and Victor Miller proposed
Search WWH ::




Custom Search