Modular Arithmetic

---

Modular arithmetic involves performing arithmetic operations within a finite set of integers, specifically using the modulo operation.

• modulo gives the remainder after division
• crucial for creating secure cryptographic systems
  • especially in public-key cryptography and finite field arithmetic

How It’s Used in Cryptography

1. Public-Key Cryptography
   • RSA
     • RSA relies heavily on modular exponentiation and finding modular inverses
     • security of RSA depends on the difficulty of factoring large numbers
   • Diffie-Hellman
     • uses modular exponentiation to allow two parties to securely establish a shared secret key over an insecure channel
   • Elliptic Curve Cryptography (ECC)
     • uses the concept of points on elliptic curves, which are defined over finite fields
     • modular arithmetic is essential for performing operations within these fields, ensuring the security of ECC-based encryption and digital signatures
2. Symmetric-Key Cryptography
   • AES, IDEA, RC4
     • symmetric-key algorithms use modular arithmetic in their internal operations to provide diffusion and confusion, making them resistant to cryptanalysis
       • e.g. byte substitution or key mixing

Why Modular Arithmetic is Suitable for Cryptography

• Finite Fields
  • modular arithmetic provides a framework for creating finite fields
    • are mathematical structures with a finite number of elements and well-defined operations (addition, multiplication, etc.)
  • these fields are essential for cryptographic algorithms
• Computational Efficiency
  • Modular arithmetic operations can be implemented efficiently in hardware and software
    • making it practical for real-time encryption and decryption
• Security
  • the mathematical properties of modular arithmetic form the basis for security of many cryptographic algorithms
    • i.e. the difficulty of solving factoring and discrete logarithm problems