Author

Alejandro Alcalde

Graduado en Ingeniería Informática en la ETSIIT, Granada. Creador de El Baúl del Programador

More Alejandro Alcalde's posts

Spot a typo?: Help me fix it by contacting me.

Modular Aritmethic

Before going straight to cryptography, it is necessary to have clear a few mathematical concepts, as cryptography in based on them.

First, I am going to talk about modular arithmetic, also known as clock arithmetic, which is defined as:

\[a \equiv b\pmod n,\]

if \(b - a\) is multiple of \(n\), in other words, \(a\) and \(b\) have the same remainder when divided by \(n\).

For example, \(3\equiv 8\pmod 5\), because \(8 - 3 = 5\), which is a 5 multiple. Another way would be knowing that both remainders of 3 divided by 5 and 8 divided by 5 are 3. From now on, I'll write the remainder of a number like this:

\[a\bmod n = r,\]

where \(r\) is the remainder of \(a\) divided by \(n\).

Computing modular inverses

Given \(a \in \mathbb Z_n\), \(a\) has inverse (also called unit) if \(\exists b \in \mathbb Z_n\ :\ ba = 1\), and its written \(a^{-1}\).

The set of all \(\mathbb Z_n\) units is called \(\mathcal{U}(\mathbb Z_n)\) and is defined as:

\[\mathcal{U}(\mathbb Z_n) = \{ a \in \mathbb Z_n : \exists a^{-1}\} = \{ a \in \mathbb Z_n : gcd(a, n) = 1\},\]

where gcd is Greatest Common Divisor.

If \(p\) is prime, every element in \(\mathbb Z_p\) but zero has inverse, therefore, \(\mathbb Z_p\) is a field. Cryptography works with fields \(\mathbb Z_p\) where \(p\) is prime.

The number of units in \(\mathbb Z_n\) can be computed with Euler's function \(\phi(n)\):

Practical example

Lets see an example. \(\#\mathcal{U}(\mathbb Z_5) = 4\), because all its elements have inverse (1,2,3,4), and \(\phi(5) = 4\), therefore \(\mathbb Z_5\) is a field. However, \(\#\mathcal{U}(\mathbb Z_{15}) = 8\), because \(\phi(15) = \phi(3)\phi(5) = 2\cdot 4 = 8\). The units of \(\mathbb Z_{15}\) are 1,2,4,7,8,11,13,14.

The code below uses the Euclidean algorithm to compute the inverse of a number in \(\mathbb Z_n\). This python code is on my github:

  def extGcd(a,b):
      """
      Compute the Greatest Common Divisor d of a and b, and integers x and
      y satisfying ax + by = d.

      :returns: a tuple (d,x,y)
      """

      if b == 0:
          return a,1,0
      x2 = 1
      x1 = 0
      y2 = 0
      y1 = 1

      while b != 0:
          q = a//b
          r = a - q * b
          x = x2 - q * x1
          y = y2 - q * y1
          a = b
          b = r
          x2 = x1
          x1 = x
          y2 = y1
          y1 = y

      if a < 0:
          return map(int, (-a, -x2, -y2))
      return map(int, (a, x2, y2))

This algorithm returns a tuple (d, x, y), where d is gcd(a,b) and x is a mod b inverse. For example, gcd(2, 5), will return [1, -2, 1], where 1 is gcd(2, 5), and \(-2\) its inverse, if you want a positive number, just sum 5 to \(-2\), which is 3, therefore 2 mod 5 inverse is 3, because \(2 \cdot 3 = 6\), and 6 mod 5 = 1.

In order to make the task of computing a number's inverse, I've created the method bellow, the code is also available at my github:

def moduloInverse(a,n):
    """:returns: the inverse of a modulo b, if it exists"""
    d,x,y = extGcd(a,n)

    if d > 1:
        return u' a inverse does not exist'
    else:
        return x % n

Execute it with the same numbers as before, 2 and 5, and it'll return \(2^{-1},\) that is, 3.

Aknowledgements

I'd like to thank josealberto4444 for helping me with some corrections.

References

The code shown along this series is hosted on my github

Cryptography course notes by Professor Jesús García Miranda, Higher Technical School of Information Technology and Telecommunications Engineering of the University of Granada.

More resources

Maybe this posts are also worth reading