11 Exponentiation and Logarithm

epgp books

 

 

 

Learning Objectives

  • To discuss about Exponentiation and Logarithm algorithm
  • To understand the need for Order of group
  • To Know about the purpose of Primitive root
  • To discuss various examples related to the topic

   12.1 Exponentiation and Logarithm

 

Exponentiation and logarithms are inverse of each other. The following shows the relationship between them, in which a is called the base of the exponentiation or logarithm.

Exponentiation: 

 

12.2 Exponentiation

 

In cryptography, a common modular operation is exponentiation that is we often need to calculate

 

The RSA cryptosystems are exponentiation for both encryption and decryption with very large exponents. Unfortunately, most computer languages have no operator that can efficiently compute exponentiation, particularly then the exponent is very large. To make this type of calculation more efficient, we need algorithms that are more efficient.

  12.3 Logarithm

 

In cryptography, we also need to discuss modular logarithm. If we use exponentiation to encrypt or decrypt, the adversary can use logarithm to attack. We need to know how hard it is to reverse the exponentiation.

 

Executive search

 

 

The first solution that might come to mind is to solve x=log a y (mod n). We can write an algorithm

 

that continuously calculates y=ax mod n until it finds the value of given y. Algorithm shown below

 

shows this approach.

 

Modular _Logarithm (a ,y, n)

 

{

 

For (x=1 to n-1)  // k is the number of bits in x

 

{

 

If (y =    mod n) return x

 

}

 

Return failure

 

}

 

12.3.1 Discrete Logarithm

 

 

The second approach is to use the concept of discrete logarithm. Understand this concept requires understanding some properties of multiplicative groups. In mathematics, a discrete logarithm is an integer k exponent solving the equation bk = g, where b and g are elements of a group. Discrete logarithms are logarithms defined with regard to multiplicative cyclic groups. If G is a multiplicative cyclic group and g is a generator of G, then from the definition of cyclic groups, we know every element h in G can be written as gx for some x. The discrete logarithm to the base g of h in the group G is defined to be x.

 

For example, if the group is Z5*, and the generator is 2, then the discrete logarithm of 1 is 4 because 24 ≡ 1 mod 5.

 

Fix a prime p. Let a, b be nonzero integers (mod p). The problem of finding x such that ax ≡ b (mod p) is called the discrete logarithm problem. Suppose that n is the smallest integer such that an ≡1

(mod p), i.e., n=ord(a). By assuming 0≤x<n, we denote x=La(b), and call it the discrete log of b w.r.t. a (mod p)

 

Example: p=11, a=2, b=9, then x=L2(9)=6

Finite Multiplicative Group

 

In cryptography, we often use the multiplicative finite group: G=<Zn*,x>in which the operation is multiplication. The set Zn*contains those integers from 1 to n-1 that are relatively prime to n; the identity element is e=1. Note that when the modulus of the group is a prime, we have G=<Zp*,x>. This group is the special case of the first group, so we concentrate on the first group in this section.

 

12.3.2 Cyclic groups and generators

 

Some groups have an interesting property: all the elements in the group can be obtained by repeatedly applying the group operation to a particular group element. If a group has such a property, it is called a cyclic group and the particular group element is called a generator. A trivial example is the group Zn, the additive group of integers modulo n. In Zn, 1 is always a generator:

 

1 ≡ 1 mod n

1+1 ≡ 2 mod n

1+1+1 ≡ 3 mod n

…

1+1+1+…+1 ≡ n ≡ 0 mod n

 

If a group is cyclic, then there may exist multiple generators. For example, we know Z5 is a cyclic group. The element 1 is a generator for sure. And if we take a look at 2, we can find:

 

2 ≡ 2 mod 5

2+2 ≡ 4 mod 5

2+2+2 ≡ 6 ≡ 1 mod 5

2+2+2+2 ≡ 8 ≡ 3 mod 5

2+2+2+2+2 ≡ 10 ≡ 0 mod 5

 

So all the group elements {0, 1, 2, 3, 4} in Z5 can also be generated by 2. That is to say, 2 is also a generator for the group Z5

 

Order of the Group

 

The order of the finite group. |G|, to be the number of elements in the group G. In G=<Zn*,x>, it can be proven that the order of group is ɸ(n). We have shown how to calculate ɸ(n), when n can be forced into primes.

There are 12 elements in this group: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, and 20. All are relatively prime with 21.

 

Order of Element

 

In G=<Zn*,x>, we continue with the same definition. The order of an element, a , is the smallest integer i such that ai≡e(mod n). The identity element e is 1 in this case

Example : Find the order of all elements in G = <Z10∗, ×>.

 

This group has only f(10) = 4 elements: 1, 3, 7, 9. We can find the order of each element by trial and error.

    a. 11 ≡ 1 mod (10) → ord(1) = 1.

 

b. 34 ≡ 1 mod (10) → ord(3) = 4.

 

c. 74 ≡ 1 mod (10) → ord(7) = 4.

 

d. 92 ≡ 1 mod (10) → ord(9) = 2.

12.3.6 Primitive roots

 

A very interesting concept in multiplicative group is that of primitive root, which is used in the ElGamal cryptosystems. In the group G = <Zn∗, ×>, when the order of an element is the same as ɸ(n), that element is called the primitive root of the group.

 

Example: There are no primitive roots in G = <Z8∗, ×> because no element has the order equal to f (8) = 4. The order of elements are all smaller than 4.

Example: shows the result of ai ≡ x (mod 7) for the group G = <Z7∗, ×>. In this group, f(7) = 6.

 

The orders of elements are ord(1)=1, ord(2)=3, ord(3)=6, ord(5)=6, and ord(6)=1.The table 37.1 shows that only two elements, 3 and 5, have the order at i = ɸ(n)=6.Therefore, this group has only two primitive roots: 3 and 5.

 

It has been proved that the group G = <Zn*, ×> has primitive roots only if n is 2, 4, pt, or 2pt.in which p is an odd prime (not 2) and t is an integer.

Example: For which value of n, does the group G = <Zn∗, ×> have primitive roots: 17, 20, 38, and 50?

a.        G = <Z17∗, ×> has primitive roots, 17 is a prime.

b.        G = <Z20∗, ×> has no primitive roots.

c.        G = <Z38∗, ×> has primitive roots, 38 = 2 × 19 prime.

d.        G = <Z50∗, ×> has primitive roots, 50 = 2 × 52 and 5 is a prime.

If a group has a primitive root, then it normally has several of them. The number of primitive roots can be calculated as ɸ(ɸ(n)). For example, the number of primitive roots of

 

G=<Z17*,x>isɸ(ɸ(17))=ɸ(16)=8.Note that we should first check to see if the group has any primitive root, before we find the number of roots.

 

If the group G=<Zn*, ×> has primitive roots, the number of primitive roots is ɸ(ɸ(n)).

 

12.3.7 Cyclic Group

 

If the group G=<Zn*, ×> has primitive roots, it is cyclic. Each primitive root is a generator and can be used to create the whole set. In other words, if g is a primitive root in the group, we can generate the set Zn*as

as Zn∗ = {g1, g2, g3, …, gf(n)}

 

Example:

The group G = <Z10*, ×> has two primitive roots because f(10) = 4 and f(f(10)) = 2. It can be found that the primitive roots are 3 and 7. The following shows how we can create the whole set Z10* using each primitive root.

Note that the group G = <Z10*, ×> is always cyclic because p is a prime. The group G =< Z n *, X > is a cyclic group if it has primitive roots. The group G =< Z p*, X > is always cyclic .

 

The idea of Discrete Logarithm

 

Properties of G = <Zp*, ×> :

    1.  Its elements include all integers from 1 to p − 1.

 

2.  It always has primitive roots.

 

3.  It is cyclic. The elements can be created using gx where x is an integer from 1 to f(n) = p − 1.

  1. The primitive roots can be thought as the base of logarithm. If the group has k primitive roots, calculation can be done in k different base. Given x=log, y for any element y is the set, there is another element x that is the log of y in base g. this type of logarithm is called discrete logarithm.

   Solution to Modular Logarithm Using Discrete Logs

 

Now let us see how to solve problems of type y=ax (mod n) when y is given and we need to find x

 

Tabulation of Discrete Logarithms

 

One way to solve the above mentioned problem is to use a table for each Zp* and different bases.This type of table can be pre calculated and saved. For example, the below table shows the tabulation of the discrete logarithm for Z7*. We know that we have two primitive roots or base in the set.

 

 

Table 12.1 Discrete logarithm for G = <Z7*, ×>

 

Example: Find x in each of the following cases:

  1. 4 ≡ 3x (mod 7).
  2. 6 ≡ 5x (mod 7).

We can easily use the tabulation of the discrete logarithm.

 

a. 4 ≡ 3x mod 7 → x = L34 mod 7 = 4 mod 7

 

b. 6 ≡ 5x mod 7 → x = L56 mod 7 = 3 mod 7

One-way function

A function f(x) is called a one-way function if f(x) is easy to compute, but, given y, it is computationally infeasible to find x with y=f(x). La(b) is a one-way function if p is large

 

Using Properties of Discrete Logarithms

To see that discrete logarithms behave just like traditional logarithms, several properties of both types of logarithms are given in table 12 .3.Note that the modulus is Φ(n) instead of n.

 

Table 12.3 Comparison of traditional and discrete logarithms

 

Using Algorithms Based on Discrete Logarithms

 

Tabulation and the properties of discrete logarithms cannot be used to solve y ≡ ax (mod n) when n is very large. Several algorithms have been devised that use the basic idea of discrete logarithms to solve the problem. Although all of these algorithms are more efficient that the exhaustive-search algorithm that we mentioned at the beginning of this section, none of them have polynomial complexity. Most of these algorithms have the same level of complexity as the factorization problem.

 

The discrete logarithm problem has the same complexity as the factorization problem.

 

Summary

  • We have learnt about Exponentiation and  Logarithm algorithm
  •  Observed the need for Order of group and Cyclic Group
  •  Learnt about the purpose of Primitive root
  •  Understand the Discrete Logarithm problem
you can view video on Exponentiation and Logarithm