Week 03 Number Theory Finite Fields

UTS Cryptography Week 03: Number Theory and Finite Fields

Course InformationInstructor: Guangsheng (Saber) YuEmail: Guangsheng.Yu@uts.edu.auUTS CRICOS: 00099F

Overview of Advanced Encryption Standard (AES)

The Advanced Encryption Standard (AES) is a symmetric encryption algorithm widely used across the globe to secure sensitive data. AES operates on blocks of data and utilizes a dynamic key size (128, 192, or 256 bits) to enhance cryptographic strength. The AES algorithm employs arithmetic within the finite field GF(2^8), which is particularly effective for digital data processing.

• Irreducible Polynomial Used:m(x) = x^8 + x^4 + x^3 + x + 1

Contemplating the properties of this polynomial helps understand the structure of the finite field and provides essential insights into the complexity of the encryption mechanism employed by AES.

Key Concepts in Number Theory

Divisibility

• Definition: A nonzero integer b divides integer a if there exists an integer m such that a = mb.

• Notation: When we write b | a, it indicates that b is a divisor of a, resulting in no remainder upon division. For instance, positive divisors of 24 include 1, 2, 3, 4, 6, 8, 12, and 24, demonstrating the practical applications of divisibility in factoring numbers.

Properties of Divisibility

Basic Properties:

• If a | 1, then a can only be ±1, representing the fundamental nature of unit divisibility.

• If both a | b and b | a, then it infers that a and b are either +b or -b.

• Every nonzero integer b divides 0 without exceptions.

• If a | b and b | c, it implies a | c—a transitive property of divisibility that is foundational in number theory.

• If b | g and b | h, then b also divides any linear combination of g and h (expressed as mg + nh for any integers m and n).

Modular Arithmetic

• Definition of Modulus: For given integers a and a positive integer n, the expression a mod n yields the remainder when a is divided by n.

• Notation: The expression can be represented as a = qn + r, where 0 ≤ r < n, and q is the quotient derived from integer division [a/n].

• Examples:

  • 11 mod 7 = 4

  • -11 mod 7 = 3

Congruences

• Two integers a and b are said to be congruent modulo n if their residues are equivalent, i.e., (a mod n) = (b mod n).

• Notation: This relationship is denoted as a ≡ b (mod n).

Properties of Congruences

• Several vital properties include:

  • a ≡ b (mod n) iff n divides (a - b).

  • The symmetry property indicates that if a ≡ b (mod n), then it follows that b ≡ a (mod n).

  • The transitive property states if a ≡ b (mod n) and b ≡ c (mod n), then it concludes that a ≡ c (mod n).

Properties of Modular Arithmetic

• General properties that govern mathematical operations in modular contexts include:

  • Addition: [(a mod n) + (b mod n)] mod n = (a + b) mod n

  • Subtraction: [(a mod n) - (b mod n)] mod n = (a - b) mod n

  • Multiplication: [(a mod n) * (b mod n)] mod n = (a * b) mod n

Greatest Common Divisor (GCD)

• The GCD of two integers a and b is defined as the largest integer that divides both numbers without leaving a remainder.

• Notation: Represented as gcd(a, b).

• Characteristics:

  • The value of gcd(a, b) is equal to the maximum of k such that k divides both a and b.

  • If gcd(a, b) = 1, a and b are classified as relatively prime, indicating they share no common divisors apart from 1.

Euclidean Algorithm

• An efficient method devised to compute the GCD of two integers a and b involves the following steps:

  1. Set A = a; B = b.

  2. If B = 0, then return A = gcd(a, b).

  3. Calculate R = A mod B.

  4. Assign A = B and B = R.

  5. Repeat from step 2 until B reaches 0.

Groups, Rings, and Fields

Groups

• Definition: A group consists of a set of elements coupled with a binary operation that satisfies closure, associativity, identity, and inverse properties.

• Commutative (Abelian) Group: In an Abelian group, the operation is commutative, meaning for any elements a and b in the group, ab = ba holds true.

Rings

• A ring is a more complex structure that comprises a set equipped with two binary operations—addition and multiplication—that adhere to specific axioms.

• A ring is considered commutative if multiplication is commutative for all elements. An Integral Domain is a commutative ring that contains no zero divisors.

Fields

• A field is defined as a set that permits the operations of addition, subtraction, multiplication, and division (with the exception of division by zero). Notable examples of fields include rational numbers, real numbers, and complex numbers, each of which plays distinct roles in different mathematical contexts.

Finite Fields (GF)

• Finite fields, denoted as GF(p^n), hold significant importance in the discipline of cryptography, particularly within the context of the AES algorithm.

• Construction Properties of GF(p):

  • A finite field contains exactly p elements.

  • Operations within the field are defined such that they always yield results that remain within the set.

Polynomial Arithmetic

• Polynomial arithmetic finds application in distinguishing among types of polynomial operations including ordinary polynomial arithmetic, modulo p, and modulo an irreducible polynomial f(x), which forms the foundation for operations in cryptography.

Arithmetic in GF

• The addition and multiplication processes within finite fields are defined modulo p, facilitating secure computation.

• Furthermore, polynomials can be represented as bit strings, allowing efficient operations and implementations in cryptographic algorithms.

Conclusion

The course materials underscore the significance of number theory, finite fields, and modular arithmetic as foundational elements in cryptography. A solid grasp of polynomial arithmetic and finite fields is crucial for understanding the workings of the AES and similar systems, enabling robust encryption mechanisms essential for safeguarding digital communications.