1. If a is coprime to p, then a^p−1≡1 (mod p)

2. a^p≡a (mod p) for any integer a

1. If a is coprime to pq, then

2. For any integer a,

ϕ(21)=ϕ(3)×ϕ(7)=2×6=12, that is, 12 elements in the group, and each is coprime to 21.

ϕ(10)=ϕ(2)×ϕ(5)=1×4=4

{1, 3, 7, 9}

Primitive Roots

In the multiplicative group G=<Z_n*, x>, when the order of an element is the same as ϕ(n), then that element is called the primitive root of the group.

G=<Z_8*, x> has no primitive roots. The order of this group is, ϕ(8)=4

1, 2, 4 each divide the order of the group which is 4:

In the example above, none of the elements have an order of 4; hence this group has no primitive roots. The group G=<Z_n*, x> has primitive roots only if n is 2, 4, p^t, or 2p^t, where p is an odd prime not including 2 and t is an integer.

If the group G=<Z_n*, x> has any primitive roots, the number of primitive roots is ϕ(ϕ(n)). If a group, G=<Z_n*, x> has primitive roots, then it is cyclic, and each of its primitive root is a generator of the whole group.

Group G=<Z_10*, x> has two primitive roots because ϕ(10)=4, and ϕ(ϕ(10))=2. These two primitive roots are {3, 7}:

Group, G=<Z_p*, x> is always cyclic.

The group G=<Z_p*, x> has the following properties:

Modern encryption algorithms such as DES, AES, RSA, and ElGammal to name a few are based on algebraic structures such as Group Theory and Field Theory as well as Number Theory. We will begin with a set S, with finite number of elements, and a binary operation (*) defined between any two elements of the set:

that is, if a and b∈S, then a*b∈S. This is important, for it implies that the set is closed under the binary operation. We have seen that the message space is finite, and we want to make sure that any algebraic operation on the message space satisfies the closure property. Hence, we want to treat the message space as a finite set of elements. We will remind the reader that messages that get encrypted must be finally decrypted by the received party; thus encryption algorithm must run in polynomial time. Furthermore, the algorithm must have the property that it be reversible to recover the original message. The goal of encryption is to confuse and diffuse the hacker such that it would make it almost impossible for the hacker to break the encrypted message. Therefore, encryption must consist of finite number substitutions and transpositions. The algebraic structure, Classical Group, facilitates the coding of the encryption algorithm. Next we give some relevant definitions and examples before we proceed to introduce the essential concept of a Galois Field, which is central to formulation of the Rijndael algorithm used in the Advanced Encryption Standard (AES).

Definition Group

A group (G, •) is a finite set G together with an operation • satisfying the following conditions:

Definition of Finite and Infinite Groups (Order of a Group)

A group G is said to be finite if the number of elements in the set G is finite. Otherwise, the group is infinite.

Definition of Abelian Group

A group G is abelian if for all a, b∈G, a•b=b•a

The reader should note that in a group, the elements in the set do not have to be a number or objects: They can be mappings, functions, or rules.

Examples of a Group

The set of integers Z is a group under addition (+); that is, (Z, +) is a group with identity e=0, and the inverse of an element a is (−a). This is an additive abelian group, but infinite.

Nonzero elements of Q (rationals), R (reals), and C (complex) form a group under multiplication, with the identity element e=1, and a⁻¹ being the multiplicative inverse. For any n≥1, the set of integers modulo n forms a finite additive group of n elements:

The set of Z_n* with multiplication operator, G=<Z_n*, x>is also an abelian group. The set Z_n*, is a subset of Z_n and includes only integers in Z_n that have a unique multiplicative inverse:

Definition Subgroup

A subgroup of a group G is a nonempty subset H of G, which itself is a group under the same operations as that of G. We denote that H is a subgroup of G as H⊆G, and H⊂G is a proper subgroup of G if the set H≠G. Examples of Subgroups:

Under addition, Z⊆Q⊆R⊆C.

H=<Z₁₀, +> is a proper subgroup of G=<Z₁₂, +>

Rings

Let R be a nonempty set with two binary operations: addition (+) and multiplication (*).

Then R is called a ring if the following axioms are met:

Definition Field

If the nonzero elements of a ring form a group under multiplication, then the ring is called a field.

Finite Fields GF(2ⁿ)

Construction of finite fields and computations in finite fields are based on polynomial computations. Finite fields play a significant role in cryptography and cryptographic protocols such as the Diffie and Hellman key exchange protocol, ElGamal cryptosystems, and Advanced Encryption Standard (AES):

For a prime number p, the quotient Z/p (or F_p) is a finite field with p number of elements. For any positive integer q, GF(q)=F_q

We define A to be algebraic structure such as a ring or a group or a field.

Modular Polynomial Arithmetic over GF(2)

The Galois Field GF(2³): Construct this field with eight elements that can be represented by polynomials of the form:

Two choices for a, b, c gives 2×2×2=8 polynomials of the form:

What is our choice of the irreducible polynomials for this field?

These two polynomials have no factors: (x³+x²+1), (x³+x+1). So we choose polynomial (x³+x+1). Hence all polynomial arithmetic multiplication and division is carried out with respect to (x³+x+1). The eight polynomials that belong to GF(2³):

You will observe that GF(8)={0,1,2,3,4,5,6,7} is not a field, since every element (excluding zero) does not have a multiplicative inverse such as {2, 4, 6) (mod 8).

Using a Generator to Represent the Elements of GF(2ⁿ)

It is particularly convenient to represent the elements of a Galois Field with the help of a generator element. If α is a generator element, then every element of GF(2ⁿ), except for the 0 element, can be written down as some power of α. A generator is obtained from the irreducible polynomial that was used to construct a finite field. If f(α) is the irreducible polynomial used, then α is that element that satisfies the equation f(α)=0. You do not actually solve this equation for its roots since an irreducible polynomial cannot have actual roots in the field GF(2). Consider the case of GF(2³) defined with the irreducible polynomial x³+x+1. The generator α is that element which satisfies α³+α+1=0:

Suppose α is a root in GF(2³) of the polynomial p(x)=1+x+x³

All powers of α generate nonzero elements of GF₈.

We will now consider all polynomials defined over GF(2), modulo the irreducible polynomial x³+x+1. When an algebraic operation (polynomial multiplication) results in a polynomial whose degree equals or exceeds that of the irreducible polynomial, we will take for our result the remainder modulo the irreducible polynomial. For example,

Recall that 1+1=0 in GF(2). With multiplications modulo (x³+x+1), we have only the following eight polynomials in the set of polynomials over GF(2):

We will refer to this set as GF(2³) where the power of 2 is the degree of the modulus polynomial. The eight elements of Z₈ are to be integers modulo 8. Similarly, GF(2³) maps all of the polynomials over GF(2) to the eight polynomials shown above. But you will note that the crucial difference between GF(2³) and 2³: GF(2³) is a field, whereas Z₈ is NOT.

GF(2³) is a Finite Field

We know that GF(2³) is an Abelian group because the operation of polynomial addition satisfies all of the requirements on a group operator and because polynomial addition is commutative. GF(2³) is also a commutative ring because polynomial multiplication is a distributive over polynomial addition. GF(2³) is a finite field because it is a finite set and because it contains a unique multiplicative inverse for every nonzero element.

GF(2ⁿ) is a finite field for every n. To find all the polynomials in GF(2ⁿ), we need an irreducible polynomial of degree n. In general, GF(pⁿ) is a finite field for any prime p. The elements of GF(pⁿ) are polynomials over GF(p) (which is the same as the set of residues Z_p). Next we show how the multiplicative inverse of a polynomial is calculated using the Extended Euclidean Algorithm:

Chosen-Ciphertext Attack

Z_n is a set of all positive integers from 0 to (n−1).

is a set all integers such that gcd(n,a)=1, where

Φ(n) calculates the number of elements in that are smaller than n and coprime to n.

Therefore the number of integers in∈Z₂₁* is 12.

Example:

Choose p=3 and q=7, then m=3×7=21,

Encryption and decryption take place in the ring, R=<Z₂₁, +, x>.

Key-Generation Group,

Alice encrypts the message P using the public key e of Bob and sends the encrypted message C to Bob:

Eve the middle man intercepts the message and manipulates the message before forwarding to Bob:

Hence Z=[P x X] (mod m)

Eve, using the Extended Euclidean Algorithm, can then compute the multiplicative inverse of X and thus obtain P:

The eth Roots Problem

Given:

Discrete Logarithm Problem

Discrete logarithms are perhaps simplest to understand in the group Z_p*, where p is the prime number. Let g be the generator of Z_p*; then the discrete logarithm problem reduces to computing a, given (g, p, g^a mod p) for a randomly chosen a<(p−1).

If we want to find the kth power of one of the numbers in this group, we can do so by finding its kth power as an integer and then finding the remainder after division by p. This process is called discrete exponentiation. For example, consider Z_23*

To compute 3⁴ in this group, we first compute 3⁴=81, and then we divide 81 by 23, obtaining a remainder of 12. Thus 3⁴=12 in the group Z_23*

Discrete logarithm is just the inverse operation. For example, take the equation 3^k≡12 (mod 23) for k. As shown above k=4 is a solution, but it is not the only solution. Since 3²²≡1 (mod 23), it also follows that if n is an integer then 3⁴⁺²²ⁿ≡12×1ⁿ≡12 (mod 23). Hence the equation has infinitely many solutions of the form 4+22n. Since 22 is the smallest positive integer m satisfying 3^m≡1 (mod 23), that is, 22 is the order of 3 in Z_23*, these are all solutions. Equivalently, the solution can be expressed as k≡4 (mod 22) [1].

In designing public-key cryptosystems, two problems dominate the designs: the integer factorization problem and the discrete logarithm problem. Large instances of these problems are still intractable today.

Discrete logarithms have a natural extension into the realm of elliptic curves and hyperelliptic curves. And Elliptic ElGamal has proved to be a strong cryptosystem using elliptic curves and discrete logarithms. In the next part of the chapter, we will take a look at the discrete logarithm problem and discuss its application to cryptography.

1. Bob chooses a random large prime p and a generator α of the multiplicative group

2. Bob chooses a random integer a where 1≤a≤(p−2).

3. Bob computes α^a mod p.

4. The triple e_B=(p, α, α^a) is the public key, and d_B (p, α, a) is the private key.
Alice obtains Bob’s public key from some public key server.

Q—a large modulus to which the coefficient is reduced

P—a small modulus to which each coefficient is reduced

q and p are coprime

f—a polynomial that is a private key

g—a polynomial that is used to generate the public key h from f
NOTE: g (secret) is discarded later on.

H—a polynomial that is a public key

r—a random binding polynomial (discarded later on, but kept secret.

D—coefficient.

1 Choose two small polynomials f and g in the ring R; polynomial f must have an inverse.

2 The inverse of f modulo q and the inverse of f modulo p are computed.

3 F_q=f⁻¹(mod q) and F_p=f⁻¹(mod p)

4 f*F_q=1(mod q) and f*F_p=1(mod p)

5 Compute h=p*(F_q*g) mod q.

6 Alice’s private key: a pair of polynomials f and F_p

7 Alice’s public key: the polynomial h

Public parameters (N, p, q, d)=(7, 3, 41, 2).

1. Puts the message in the form of polynomial m whose coefficient is chosen modulo p between −p/2 and p/2 (centered lift).

2. Randomly chooses another small polynomial r (to obscure the message).

3. Computes the encrypted message:

Example of NTRU Encryption

Alice decides to send Bob the message:

using the random key

Example of NTRU Decryption

Bob computes

Bob then center lifts modulo q to obtain

Bob reduces a(x) modulo p and computes

Center lifting modulo p retrieves Alice’s plaintext

NTRU167≡ECC112≡RSA512

NTRU263≡ECC168≡RSA1024

NTRU503≡ECC196≡RSA2048

RSA Integer Factorization Problem

Diffe-Hellman Discrete Logarithm Problem in

Elliptic Curve Discrete Logarithm Problem on anCryptography  Elliptic Curve

Lattices SVP and CVP

1. True or False? Generation of a key in public-key cryptography involves exponentiation modulo a given modulus.

2. True or False? The order of a finite group is the number of elements in the group H.

3. True or False? In the multiplicative group, H=<Z_n*, x>; when the order of an element is the same as ϕ(n), then that element is called the primitive root of the group.

4. True or False? A group H is said to be finite if the number of elements in the set H is finite.

5. True or False? The set of integers Z is a group under addition (+); that is (Z, +) is a group with identity e=0, and inverse of an element a is (−a).

1. A subgroup of a group G is a nonempty subset H of G, which itself is a group under the same operations as that of:

A. R

B. I

C. N

D. E

E. G

2. What group is said to be cyclic if there exists an element a∈G such that for any b∈G, and i≥0, b=aⁱ?

A. O

B. W

C. S

D. G

E. A

3. Let _________ be a nonempty set with two binary operations addition (+), and multiplication (*).

A. R

B. I

C. W

D. C

E. S

4. If the nonzero elements of a ring form a group under multiplication, then the ring is called a:

A. field

B. denial-of-service attack

C. venyo

D. port traffic

E. taps

5. Construction of finite fields and computations in finite fields are based on:

A. systems security plan

B. polynomial computations

C. denying service

D. decision making

E. URL lists

Project

What is a key?

Problem

What is the difference between public and private keys?

Problem

Which types of data can be encrypted.