Abstract Algebra

Abstract algebra [6], [7] represents a class of powerful mathematical tools which have application in diverse fields. It is an extension of classical algebra which deals with abstract structures like groups, rings and fields instead of the usual number system. In this section, we will have an overview of these structures which is a prerequisite in understanding the core of cryptosystems.

An algebraic structure is characterized by the following three components:

  • • An underlying set, which is often called the carrier set of the algebraic structure.
  • • Operations defined on the elements of the underlying set.
  • • Distinguished elements of the set called the constants of the algebraic structure.

For example: (Z, +, 0) is an algebraic structure, where Z = Set of integers, + = Binary operation (Mapping from Z2 —> Z), Z2 means the operation is applied between the two elements of the set Z and the resulting element also belongs to the set Z, 0 = Constant of algebra.

In general, the operator may take m elements: S’" —> S, here, m is called the arity of the operation. Any two algebraic structures may have the same signature, same number of operations with the same arity and the same number of constants. For example, (Z, +, -, -, 1, 0) and (R, +, -, -, 1, 0), here R is the set of real numbers. The two algebras having the same signature may not have the same property, (Z, 0) and (Q, +, 0). Here, commutative law holds for

the second but not for the first.

Sub-Algebraic Structure-. Let A = < S, a, k> and A' = (S', o', A'k') be two algebras then A' is a subalgebra of A if i) S' c S, ii) a o' b = a°b, Va, b e. S', iii) д =дй, /a e S' and iv) k’ = k. If A' is subalgebra of A then A' has the same signature as A and obeys the same axioms.

Zero and One Element: Let о be a binary operation on S. An element 1 e S is an identity for operation о if for every x eS, 1/ ox = xolr = x. An element 0 e S is a zero for operation о if for every x e S, 0/ ox = xo0r = 0.

Consider the following algebraic structure: = {a, b, c}, operation: o, group о a b c

table: f й f ^. pjncj zeros anc| ones. babe

c a b c

Solution: Right zero = a, b, No left zero, Left Identity = b, No right identity.

Theorem: Let « be a binary operation on 5 with left identity 1/ and right identity lr. Then 1/ = lr and this is referred as a two-sided identity.

Proof: From left identity: 1/ ox = x Put x = lr. From right identity: 1/ °lr = lr. x о lr = x Put x = 1/, 1/ olr = 1,. Hence lr = 1/.

Semigroup

A semigroup is an algebraic structure with signature < S, о >. Semigroups usually consist of algebraic structures with single binary operation and satisfy the closure and associative properties. For example: < Z, + >, < Z, •>, < R, + >,

< X , concatenation >.

Monoid

A monoid is an algebraic structure with signature < S, о, 1 > where о is a binary associative operation and 1 is a two-sided identity for operation o. It satisfies the closure, associative and identity axioms. Examples of monoids include:

< Z, +, 0 >, < Z, •, 1 >, < R, +, 0 >, < X , concatenation, X >.

Group

A group is an algebraic structure with signature 1, -> where » is a binary associative operation and constant 1 is a two-sided identity for operation a and - is a unary operation defined over the carrier such that Vx e S, x is an inverse of x w.r.t. a. It satisfies the closure, associative, identity and inverse axioms. Examples of the group includes: < Z, +, 0, - >, here, - represents unary minus. If о operation is commutative then the group is known as an abelian group. Groups are rhe most commonly used algebraic structure in the construction of cryptosystems. Therefore, we will try to cover as much detail as possible keeping in mind the page limit.

The groups possess a unique inverse: Let element a of the group have two inverses b and c,b°a = e and coa = e, which implies boa = coa=s b°a°b = соa°b. Let a°b = d,b°d = cod. Now, we know each element in the group has an inverse, bodod '=codod '=sboe = coe. Therefore, b = c.

The left and right cancellation is permitted in groups because of the existence of inverses.

Symmetric finite group

The symmetric finite group is defined over the finite set л e N = {l,2,3,4,......,n}

and is often represented as S„. For construction of symmetric groups, we have to consider the set permutation of n elements and give each permutation a name. These permutations will be the elements of group S„ and then we have to define the composition law. For example:

St = {/} Permutation for Sj:

Composition law for S,:

S2 = {*’, x) Permutations for Sr.

Composition law for Sr.

The order of S„ is the number of elements in S„ and it is the number of permutations possible with n elements which is n. The symmetric groups from S3 onwards are not abelian.

Group isomorphism

To understand the concept of group isomorphism, consider the following two groups: G: S2 = {/, t) G' = {+1, -1}

The composition table of G and G' look similar and by relabeling of symbols we can turn G into G', i.e. i —> +1 and x —> -1. We have seen that G and G' have exact same algebraic structure, we are only using different symbols. Isomorphism is a relabeling function (> G' (bijective mapping - surjective and injective). It is not necessary that groups having the same order are isomorphic. Collecting all the groups that are isomorphic to one another together forms the isomorphism class. If two groups share the same isomorphism class, this means they are isomorphic to each other.

Example: G = (R, +), where R is the set of real numbers and G is an abelian group. Consider another group G' = (R+,x), where R+ is the set of positive real numbers and G' is also an abelian group. Now, we need to define a bijective map, (p: G —> G' from G to G' (p: x —> ex, VxeG and cq is mapped to e& (0 —> 1). Hence G and G' are isomorphic (G = G').

Subgroup

The subset H c G of a group G is called subgroup H -< G of G if it is closed under composition. It is not necessary that all subsets of G form a group, so we have to cleverly choose the elements of H. The associativity axiom is trivial to prove. The identity element must be included in H from G. Each element in H should have its inverse /h e H, 3h ' e H, such that hh~l = e = h 'h.

Example of subgroups: Trivial cases includes i) G = Entire group G, ii) H = [e). Other than trivial cases: (Z, +) is a known abelian group. Consider a set containing integer multiples of a, aZ = {azVz e Z} =

{0, a, -a, 2a, -2a, За, -3a,......). Clearly, aZ If a = 0, aZ = (0) and

if c7 = l, aZ = Z represents the trivial subgroups. If a = 2, aZ = {0, 2, -2,

4, -4,......); it represents a proper subgroup which contains only even

numbers. In fact, aZ are the only possible subgroups of G = (Z, +).

Intersection of subgroups

The intersection of subgroups is also a subgroup, i.e. if HUH2 - then H n H2 -< G. The intersection of two subgroups is always non-empty because it will contain at least one element, i.e. identity of group.

Closure: Vg, geH, n H2, we have to show: gg g H and gg g H2. We know g,geHi, so their composition ggeH(. Similarly, ggeH2. Therefore, gg e Ht глН2. Associativity: Inherited. Identity: Trivial. Inverse: Vg e H] n H2, we need to show: g'1 e H, n H2. Vg g H( n H,-> g g Hx and g g H2. H, and H2 are groups so g“' g Hi and g'1 g H2.

Cyclic groups

If in a group there exists an element x e G (x is non-identity) called the generator of the group then that group is known as a cyclic group. As the name itself suggests, the generator element can generate all the elements of the group, i.e.

< x > = {e, x', x1, xJ,......x'1, x'2, x"J,......). The common examples of cyclic

groups include, (M, +) and (Z, +).

Ring

So far we have seen algebraic structures with one binary operation. Ring is an algebraic structure (A, +, •) with two binary operations and satisfies the following conditions: i) (A, +) is an abelian group, ii) (A, •) is a semigroup and iii) the operation • is distributive over the operation +. Example: (Z„, Ф, G).

Division ring-. Every non-zero element has a multiplicative inverse, i.e. if a g R and a * 0 then Зд~1 g R: a-a~' = 1 = a~' ■ a.

Integral domain: A commutative ring that has no zero divisors, i.e. a ■ b = 0 Vb g R iff a = 0 or b = 0.

Field

An algebraic structure (A, +, •) with two binary operations is called a field if the following conditions are satisfied: i) (A, +) is an abelian group, ii) (A - {0}, •) is an abelian group and iii) the operation ■ is distributive over the operation +. Example: (R, +, •), (Zp, Ф, O).

Finite fields

Finite fields are also known as Galois fields and have great application in the cryptography domain like the groups. Finite fields exist if the fields have pm elements where p is prime number and m is any positive integer, i.e. the order of the finite field is either a prime or a power of prime. GF(12) do not exist.

There are two types of finite fields depending upon the value of m: i) if m = 1, these are known as the prime fields; ii) if m > 1, these are known as the extension fields.

Prime fields and their arithmetic

The elements of a prime field GF(p) are integers {0,1,2,...,p-1). For a,b eGF(p), we can perform addition: (a + b)modp; subtraction: (a-b)modp; multiplication: (ab)modp; division: (ab~')modp and inversion: aeGF(p) then aa_1 = modp. a~' can be computed with the extended Euclidean algorithm.

Extension fields and their arithmetic

In cryptography we are mainly interested in extension fields where p = 2. The elements of GF(2"') are polynomials A[X] of the following type:

where д, 6 GF(2) (In general: a, e GF{p) = {0,1,2,......,p-1}).

For example: GF(8) = GF(2J). A[X] = д,х2 + ДХ + До, where д, e GF(2). This polynomial is considered as a vector (д,,Д1,д0) with possible combinations from 000 to 111.

Let A[X], B[X] e GF[2’"). The addition and subtraction operation is performed as follows:

For example, A[X] = x2+x +1 and B[X] = x2 +1. A[X] + B[X] = (2mod2)x1 + x + 2mod2 = x and Л[Х]-В[Х] = х.

Note that the addition and subtraction in GF(2"') are the same operation. For the multiplication operation it seems like multiplying two polynomials will return the correct result, i.e. C'[X] = A[X]B[X] = (x2 + x + l)(x2 +1) = x4 + x3 +x + l £ GF{2"'). However, it is not true; the resulting element does not belong to the field under consideration. Now recall prime fields: GF(7) = {0,1,...6), multiply the following two elements: 3.4 = 2mod7 = 5 e GF[7). The correct result is obtained by computing the modulo operation. The same is the case with extension fields, we have to divide the multiplication result by a polynomial, i.e. reduce C'[X] by a polynomial that behaves like a prime called an irreducible polynomial. Find the irreducible polynomial P[X] = YfiLopiX', where p, e GF(2). For GF(23): P[X] = x3 + x +1. Therefore, the correct method of multiplication in extensions fields is: C[X] = A[X]B[X]modP[X], For every field there exists several irreducible polynomials.

For the inversion operation in GF(2"') the extended Euclidean algorithm can be used. For example, to find the multiplication inverse of (x3 + x + l)modulo(x5 + x3 +1), use the extended Euclidean algorithm as follows:

Characteristic of a field

The characteristic of a field is a number (non-negative integer) associated with every field. It is denoted as Cb(F); it is the smallest number of times the multiplicative identity (1) is added to itself to get back 0 (additive identity). For example: f2 = Kk 1) with the following composition table is Ch(F) = 2(1 +1 = 0).

Theorem: Characteristic of a field is either 0 or a prime number.

Proof: The proof is by contradiction. Let Ch[F) = n, where n is not a prime. Therefore, n = ab such that neither of a or b is 1 and 1 < a, b < n. By definition of characteristic of a field, n-1 = 0, which implies (ab) • 1 = 0. By expanding the dot representation, (a • 1) * (b ■ 1) = 0. In fields there is no zero divisor, so either of (a ■ 1) or (b ■ 1) is 0. Let us say, (a ■ 1) = 0. This contradicts the assumption that n is the smallest positive integer. Hence, Ch(F) = 0 or p.

Application To Cryptography

These number theory and abstract algebraic [1] concepts have direct application in modern cryptography. The cryptosystems are designed in a way that involves one-way processes which are easy to compute but hard to reverse. These one-way processes are developed using the concepts in number theory. Consider the example of factoring, a very basic concept in number theory, which is a very famous example of such a one-way process in the sense that it is quite easy to multiply any two large prime, but extremely difficult to recover these prime factors given the number. This factoring problem linked with Euler’s theorem forms the foundation of the most popular RSA cryptosystems. Another example of such a one-way process is the discrete logarithm problem which states that given two co-prime integers a and n and another integer k it is easy to find akmodn, but extremely difficult to find k, given akmodn. Discrete logarithm problems form the foundation of many cryptosystems and the Diffie-Hellman key exchange algorithm is the first successful example of this problem. More recently, these ideas have been extended and enriched by replacing modular arithmetic by the more exotic operations on points on elliptic curves.

Summary

In this chapter we have discussed the fundamentals of number theory and abstract algebra which play an important role in understanding and the development of cryptosystems. Modern cryptography is totally based on the abstract algebra and number theory. Therefore, we have tried to briefly cover every aspect of these two prerequisites with respect to their application in cryptography. Further, keeping in mind the page limit as well as the clarity of concepts, we have selectively chosen topics and elaborated only those whose application can be directly seen in the cryptographic world.

References

  • 1. V. Shoup, A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2009.
  • 2. J. J. Tattersall, Elementary Number Theory in Nine Chapters. Cambridge University Press, 2005.
  • 3. A. Weil, Basic Number Theory, vol. 144. Springer Science & Business Media, 2013.
  • 4. B. Gupta, D. P. Agrawal, and S. Yamaguchi, eds. Handbook of Research on Modern Cryptographic Solutions for Computer and Cyber Security. IGI Global, 2016.
  • 5. P. Premkamal, S. Kumar, P. J. A. Kumar Pasupuleti, and Alphonse, “Efficient escrow-free CP-ABE with constant size ciphertext and secret key for big data storage in cloud.”, International Journal of Cloud Applications and Computing (IJCAC), vol. 10, no. 1, pp. 28-45, 2020.
  • 6. С. C. Sims, “Abstract algebra: a computational approach,” No. 512.02 S5. J. Wiley, 1984.
  • 7. D. S. Dummit, and R. M. Foote, Abstract Algebra, vol. 3. Wiley Hoboken, 2004.
 
Source
< Prev   CONTENTS   Source   Next >